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作业君