Description
The problem is to simulate a network node. Packets arrive randomly at the switch, and are sent out every
∆t seconds. If too many packets arrive, they are queued. A maximum of N packets can be queued. To model
the arrival of packets at the node, you can use the following function nextTime() which gives the next time a
packet arrives for a Poisson process.
#include <math.h>
#include <stdlib.h>
int nextTime(float rateParameter)
{
return (int)(-logf(1.0f – (float) random() / (RAND_MAX + 1)) / rateParameter);
}
The argument rateParameter is 1/∆t and a parameter of your simulation. If the queue grows too large, packets
are dropped.
A packet is an instance of a structure as follows:
typedef struct{
int id; // packet id
int t0; // arrival time of packet
int priority; // higher means more important
char contents[80]; // contents of packet
} PACKET;
We will not use priority here, but this can be a standard definition for a packet for later assignments. When a
packet is to be added, you need to first allocate it via
PACKET *p;
p = (PACKET *)malloc(sizeof(PACKET));
and then add it to the queue. Note that queue is a circular array of pointers, each pointing to a packet or to
NULL (if that queue element is not allocated
1. Write a program that will take λ = 1/∆t, N and µ (the rate at which packets are forwarded by the node)
and simulate the queue. λ and µ are real while N is integer. The program must collect a history of the
time spent in the queue and the percentage of packets dropped.
2. Vary the three parameters as follows and generate histograms for each case and enter the missing data
below:
1
N λ µ Avg Delay % dropped packets Time per packet
5 0.45 0.5 ? ? ?
10 0.45 0.5 ? ? ?
20 0.45 0.5 ? ? ?
5 0.4 0.5 ? ? ?
5 0.3 0.5 ? ? ?
and understand the way N and λ interact.
3. Is the time complexity to manage the queue per packet equal to O (1) or something else? Assume that
all CPU and memory operations are the same cost (which they are not).
Submit a single c code (with optional include file) along with a pdf report to Moodle.
