Homework assignment 6 CPE-593 Data Structures and Algorithms
Spring 2020 Ins: Dr. Aftab Ahmad Due by 4 PM on 5/04/2020
Simulate a queueing system using the queue data structure. You are not allowed to use built-in queues or any libraries that have queues in them.
Note: see the grading rubric at the end on the next page.
1. Consider a router buffer that is empty but can hold k Megabytes (MB) of data. The router will transmit any incoming packets from this buffer to an outgoing line of capacity C MBPS (Megabyte per sec).
2. After a random time ¦Ó sec the router receives a packet that has a random size L drawn from an exponential distribution with an average size of 1/¦Ì MB. The arrival time for this packet is random with an average 1/¦Ë sec.
3. Assume that the packet arrival time, T follows an exponential distribution. That is
f¦Ó(t) = ¦Ë e-¦Ët Which has an average of 1/¦Ë sec.
Also, assume that the packet length in bytes follows an exponential distribution. That is fL(b) = ¦Ì e-¦Ìb
In units of time, this is fL(t) = ¦ÌC e-¦ÌCt Which has an average of 1/(¦ÌC) sec.
Note: If x is a random number with uniform distribution [0, 1], then y = -E[y] ln x has an exponential distribution with mean of E[y]. To generate random time or length with exponential distribution, first generate a uniformly distributed random number x and then use the above equation to generate y.
4. The router starts transmission of the first packet as soon as it arrives. If L is the packet length, then it takes L/C sec. to transmit the packet. If more packets arrive during this time, they are queued and transmitted in a first in first out (FIFO) manner. Use FIFO queue data structure to add and delete packets to the queue as they arrive and leave.
5. You have simulated a FIFO queue which is in transient state. Let the router transmit about 1000 packets before you start taking any statistics from the simulation. We assume that after waiting this long, the queue is in a steady state. You can have a loop running the above queue for 1000 packets and then start another loop for steady state, say another 1000 times.
6. Every time a packet arrives, note the length of the current queue. This length (converted into transmission time) is the waiting time that we calculated in assignment # 4. By adding the packet¡¯s own length, you can get the queueing time. You notice that the waiting time can be zero if the queue is empty, but the minimum queueing time can¡¯t be zero and is the length of packet in sec.
7. By adding all the waiting times and dividing by the number of packets (e.g., 1000), you get the average waiting time. The quantity ¦Ë/(¦ÌC) = ¦Ñ is called the load.
8. By changing ¦Ë from, 0.1(¦ÌC) to 1.2(¦ÌC), in steps of 0.1(¦ÌC) thus find the average waiting times for ¦Ñ = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2.
9. Assume 1/¦Ì = k/100. You can choose values of k and ¦Ì arbitrarily to satisfy this condition. This simply means that on the average, the buffer can hold up to 100 packets including the one under transmission. For example, if you choose 1/¦Ì = 1 kB, then k = 0.1 MB. With C = 1 MBPS, 1/(¦ÌC) = 1 msec and ¦Ë can vary from 100 packets/sec to 1200 packets/sec in steps of 100.
1/(¦ÌC) or 1 msec is the average packet transmission time, and 1/¦Ë is the average packet interarrival time (¦Ë is the packet arrival rate).
10. You have simulated what is called an M/M/1/K queue with Markovian arrivals, Markovian service times, one server and room for K packets. K is 100.
11. Repeat the above simulation by making the packet length a constant and equal to 1/(¦ÌC). Now, this is called an M/D/1/K (Markovian arrivals, Deterministic service times, one server and room for K packets) queue.
12. Theoretical results for the average waiting time and queuing time M/M/1/K queue are easily available as a function of the load ¦Ñ. Find out the formula for the waiting or queueing time (whichever you measure).
13. Plot the waiting or queueing times (make your pick) for M/M/1/K (simulation), M/M/1/K (theoretical), and M/D/1/K (simulation).
14. Your *.dat file has what you plot, that is, four columns, namely, load, M/M/1/K time (sim), M/M/1/K time (theoretical), M/D/1/K time.
Grading Rubric
Running code with correct results in *.dat file
Comments explaining data structures and algorithms
Graph with correct results
What do you learn about packet length distribution comparing the two queue types?
25
10
15
5 (Bonus)