程序代写案例-TELCOM 2310
TELCOM 2310 Spring 2021
Project 1
As we discussed in class, routers use queues (also called buffers) to temporarily store packets
when they cannot immediately send them on an outgoing link. As we’ve seen, these queues are
finite. Once the queue is filled with packets, any new packets that arrive before a packet transmission
makes space in the queue again are dropped and lost.
Recall that the details of this phenomenon are tightly related to the rates at which packets
arrive at the queue and can be transmitted on the outgoing link, as well as the size of the buffer.
We will use λ to denote the packet arrival rate (in packets per second), µ to denote the packet
departure (or transmission) rate (in packets per second), and n to denote the size of the buffer (in
packets). See Figure 1 for an illustration. If you are interested in more details for queuing theory
and its application to computer networks, you can see [1] and [2].
In this project, you will write a software tool that will simulate the arrival and departure of
packets to/from the router. You will then use this tool examine scenarios with different arrival /
departure rates and queue sizes.
Figure 1: A router buffer representation.
1 Discrete event simulator
Every arrival or departure of a packet to/from the router is a discrete event. Whenever a new
event takes place, the state of the queue is altered. We can define the state S of the queue Q as
the following tuple:
S(Q) = (# of packets in the queue,# of packets dropped) (1)
For example if S(Q) = (143, 4), there are currently 143 packets in the buffer, and 4 packets
have been dropped so far in total.
For this project, we have two different possible events: (i) packet arrival and (ii) packet depar-
ture. In order to decide if a simulated event is a packet arrival or departure we have to calculate
the probability of each event. Since we have an arrival rate of λ packets/sec, and a departure rate
of µ packets/sec, the corresponding probabilities P are:
1
Parrival =
λ
µ+ λ
(2)
Pdeparture = 1− Parrival = µ
µ+ λ
(3)
After every event, the state S(Q) is changed, that is, the number of packets in the queue and/or
the number of dropped packets are changed. Our objective in this project is to keep track of the
state changes for a number of discrete events and understand the reasons behind the observed
changes.
2 Programming assignment
You can use any programming language you are familiar with to complete this project. The basic
steps you need to take to complete the assignment are given below in pseudocode.
2.1 Initialization phase
Initialize variables/counters related to the queue status.
• pkt in q = 0
• pkt dropped = 0
2.2 Simulating the events
Repeat for x times (that is, the number of events we want to simulate) algorithm 1.
Data: λ (arrival rate), µ (departure rate), n (buffer size)
Result: pkt in q, pkt dropped
begin
y=rand([0,1])1
if y ≤ λ
µ+ λ
then // arrival event
2
if pkt in q < n then3
pkt in q++4
end
else5
pkt dropped++6
end
end
else // departure event7
if pkt in q > 0 then8
pkt in q- -9
end
Write pkt in q and pkt dropped in a file10
end
Algorithm 1: Pseudo code for event
2
In line 1 you need to call a random number generator routine that returns a random real number
in the range [0, 1]. Note that this is must a real number between 0 and 1 (inclusive); it is NOT an
integer (i.e. you need to be able to generate numbers between 0 and 1, not just either 0 or 1). For
example, Python’s random.random() can be used here, but random.randint() will not give the
correct results (https://docs.python.org/3/library/random.html).
3 Analyzing performance
After implementing the simulator you will experiment with it using different values for the input
parameters (λ, µ, n). Therefore, it is not advisable to hardcode the parameters within the simu-
lator’s code. It is preferable to pass them to the program as command line arguments. For each
combination of input parameters, you will be required to simulate at least 1,000,000 total events
(i.e., x = 1, 000, 000).
3.1 Constant rates
In the first set of experiments, you will use constant input rates. Table 1 summarizes the different
values of λ, µ and n that you are going to use1. Note that you will have to use all the different
combinations (27 in total).
λ(pkt/sec) 30 80 120
µ (pkt/sec) 50 100 120
n (packets) 50 100 150
Table 1: Simulation parameters.
3.2 Variable input rate
In the second set of simulations, the input rate λ will vary over the events, while the departure
rate stays constant at µ = 120pkt/sec and the buffer size n = 100 packets. You will again have to
simulate at least 1,000,000 events, and during the simulation λ will vary according to Table 2.
Events (%) 0-10 10-70 70-80 80-90 90-100
λ(pkt/sec) 70 200 130 120 70
Table 2: Variations of λ as the simulation progresses.
Table 2 should be interpreted as follows: “For the first 10% of the events the input rate will be
70 pkt/sec, for the next 60% of the events λ = 200pkt/sec” and so on.
4 Deliverables
You are required to deliver the following:
1Note that these number are just representative for the purposes of our simulations. If you are interested in more
realistic numbers for the buffer sizing you are referred to [4].
3
• Clean event simulator code (i.e., structured and with comments) that will compile and run
without modifications, and a text README file that clearly explains exactly how to compile
(if needed) and run the code (35% of the total project’s points).
• A report (65% of the total project’s points) that will, (i) briefly describe the implementation
of your simulator, and (ii) analyze the simulation results. In particular, for the second part,
you are asked to provide figures for every scenario, for the number of packets in the queue
and the number of packets dropped from the queue, versus the number of simulated events.
Additionally, you will need to provide a (brief) explanation of the behaviors observed based
on our discussions in class. Figure 2 shows a sample evaluation plot. We have 10 simulated
events and the queue size is n = 5. The relation between the incoming and outgoing rate
is such that the queue gets filled up quickly and packet drops start to be observed after the
6th event (but, you will have to provide a more detailed explanation, and show results for 1
million events, not 10).
To help you create your figures, we are providing a Python program that you can use/modify
for this purpose (although you are also free to use a tool of your choice to create the figures).
Note that in some cases, it may be helpful to create “zoomed-in” plots that focus on the
initial behavior (e.g. the first 2000 events rather than all 1 million) to better understand the
effects of the different parameters.
0 2 4 6 8 10
0
1
2
3
4
5
ID of simulated events
Nu
m
be
r o
f p
kts


Packets in the queue
Packets dropped from the queue
Figure 2: Sample evaluation plot.
The deadline is Monday March 1, 2021 AoE. Projects must be submitted on Canvas. As
with the homework assignments, you may use your textbook and notes to complete this assign-
ment, and may discuss concepts with other students or use online resources that help you better
understand the concepts involved. You are NOT permitted to look at other students’ solutions
(including code), or online solutions/code for substantially similar problems. Similarly, you are
not permitted to share your solutions with other students, or post your solutions online. Ask the
instructor if you have any questions about this policy.
4
References
[1] L. Kleinrock, ”Queueing Systems. Volume 1: Theory”, Wiley-Interscience, 1975, ISBN
0471491101.
[2] L. Kleinrock, ”Computer Applications, Volume 2, Queueing Systems”, Wiley-Interscience, 1976,
ISBN 978-0-471-49111-8.
[3] A. Law and W.D. Kelton, ”Simulation Modeling and Analysis”, McGraw-Hill College, 1999,
ISBN 9780070592926.
[4] N. Buckshot, Y. Ganjali, M. Ghobadi, N. McKeown and G. Salmon, ”Experimental Study of
Router Buffer Size”, in ACM IMC, 2008.
5

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie