算法代写 | CPE-593 Data Structures and Algorithms

这个作业是使用队列数据结构模拟排队系统
Homework assignment 6 CPE-593 Data Structures and Algorithms
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 25
Comments explaining data structures and algorithms 10
Graph with correct results 15
What do you learn about packet length distribution comparing the two queue types? 5 (Bonus)