# 算法代写 | 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)