Reference no: EM132411814

EE509 Discrete-Event Simulation of a Random Early Detection

Scenario I - Modelling a Queue with No Loss

The first part of this assignment is to develop simulation code to model a single queue/transmission link, with an unlimited length queue, to measure the system delay and to compare your simulation results to known exact analytical results (the M/M/1 queue detailed in the EE509 lecture notes [4]). The purpose of this exercise is to familiarise you with the fundamentals of random variate transform, event-advance simulation programming and to allow you to validate some basic simulation results against easily-calculated exact mathematical formulae. This simulation will form the basis of the simulators in Scenarios II and III. The specification of the system to be modelled is as follows:

Link rate                                    10 Mbps

Mean Packet length                   8000 bits

Packet Length Distribution* Negative-Exponential

Interarrival Time Distribution Negative-Exponential

Maximum Queue Length Unlimited

Queue discipline                        FIFO

Scenario II - Modelling a Queue with a Drop-Tail Policy

The second part of this assignment involves modifying your unlimited length queue to model a limited length queue. Your simulation code will implement the measurement of system throughput and packet delay. This queue will reflect the behaviour of the drop- tail policy in a router and results will serve as a basis for comparison with the RED congestion control scheme, in Scenario III. The specification of the system to be modelled is the same as Scenario I but with a finite queue length of 30 packet buffering spaces. (Note that when a packet enters service it is removed from the head of the queue and stored in a transmission buffer in the output port, immediately starting its transmission. Thus, in total there are 31 storage spaces in the queue/port/link system).

Scenario III - Modelling a Queue with a RED Congestion Control

In this part of the assignment, you will extend the Scenario II model to implement the RED congestion control scheme and investigate its effectiveness when compared to the simple drop-tail policy. The overall purpose of the exercise is to familiarise you with simulation methods for performance evaluation of complex protocols and to illustrate the role of simulation in network protocol design. You will gain an understanding of how to take a description of a quite complex physical system and reduce it to a model to obtain estimates of pertinent performance measures. (In Assignment 2 (given at a later date), you will also compare simulation results to approximate analytical results and explore where inaccuracies in analytic approximations arise and explore the relative merits of simulation and analysis). The specification of the system to be modelled is the same as the previous scenarios with the addition of the following RED algorithms parameters:

wq	0.005
maxp	0.05
minth	5
maxth	15
s	0.2 / μ
Maximum Queue Length	30

Simple Queue Simulator (Scenario I)

Implement the M/M/1 queuing model simulation as specified in Scenario I. Your simulator should include a batched mean-delay statistic that calculates the mean delay at periodic intervals (see Section 1.6).

(1.1) Give a brief description of how your simulator generates random numbers with the specified distribution and a given mean value.
(1.2) Describe how the departure time of a packet from the system (completion of transmission) is calculated given the arrival time of the packet (the time the packet joined the end of the queue). Make reference to any relevant variables that are used in the code to represent the current state of the system.
(1.3) Give a brief description of the functioning of the event processing loop, making reference to insertion and removal/processing of arrival, departure and statistic events during a simulation run.

Set up your simulation according to the parameters of Scenario I and with a mean offered load of ρ=0.8 Erlangs. Run the simulation for 1000 simulated seconds. Gather mean delay statistics in batches of 10 sec intervals (100 batch means in total).

(1.4) Show how you have calculated the mean service rate μ (packet transmission rate) and the mean arrival rate λ for the given offered load.
(1.5) Plot the set of batch means against time (e.g. using MS Excel, Matlab or Scilab) and calculate the mean value over all batches.
(1.6) Calculate the 95% confidence interval, stating the answer as a ± percentage. Show your calculation, briefly commenting on the method/formulae you have used.
(1.7) Compare your mean simulation result to the theoretic result for system delay in the M/M/1 queuing system (see [4], pp. 61). Show your calculation. Comment briefly on the result.
(1.8) Using the analytic formula, plot a graph for mean system delay for the range of offered load values ρ = {0.4, 0.5, 0.6, 0.7, 0.8, 0.9} (with load values as x-axis).

Drop-Tail Queue Simulator (Scenario II)

Modify your previous simulator of Scenario I to implement the drop-tail queue of Scenario II. As well as a batched mean-delay statistic, your simulator should also implement a normalised throughput statistic and a statistic that records the proportion of packets whose delay is greater than a given value, as described in Section 1.6. A batch length of 5 seconds of simulated time should be used for all statistics.

(2.1) Explain briefly how the simulator of Scenario I has been modified to implement the drop-tail queue.
(2.2) Plot the instantaneous queue size vs time (all changes in queue size as packets arrive and depart the system) over a one second simulated interval, for ρ=1.2.
(2.3) Execute your simulator for the load values in Table 1 below. Use a total simulation run time that ensures that the 95% confidence interval for all mean delay measures is no greater than ±3%. What length simulation run (in simulated seconds) was required? Complete Table 1 with mean throughput, mean delay and the corresponding 95% confidences intervals, calculated from the set of batch means in each case.

Table 1: Drop-tail Policy Simulated Performance Statistics

Offered Load (Erlang)	Mean Throughput (As fraction of time link busy)	95% C.I. (as ±%)	Mean Delay (ms)	95% C.I. (as ±%)
0.7
0.8
0.9
1.0
1.1
1.2
1.3
1.4

(2.4) Calculate the theoretic value of normalised throughput (λeff / μ) for an offered load of 1 Erlang and compare to your simulation result. (See analysis of M/M/1/K queue in [4] pp. 68, noting that K=31 in this case).

(2.5) From your simulation statistics, when offered load is 1.1 Erlangs, what proportion of accepted packets are delayed by more than 25ms. Quote the 95% confidence interval with your answer.

RED Queue Simulator (Scenario III)

Modify your previous simulator to implement the RED congestion avoidance policy described in Section 1.4. Use the same total queue length as in the previous exercise.

(3.1) Explain briefly how the previous simulator has been modified to implement the RED algorithm, making reference in particular to the following questions and, where appropriate, listing code snippets to illustrate your implementation,
a) When is the instantaneous queue size updated?
b) When is the average queue size updated?
c) How is the start of an idle period detected?
d) How is it decided if a packet is to be dropped given some value of pa?

(3.2) Plot the instantaneous queue size over a one second interval when ρ=1.2 and the windowed average on the same plot. Choose an interval that includes at least one idle period (so that the effect of equation (2) is illustrated). Compare with the plot of (2.2).
(3.3) Execute your simulator for the load values in Table 2 below. Use the same total simulation run time and batch length as used in (2.3) above. Complete Table 2 with mean throughput, mean delay and 95% confidences intervals.

Table 2: RED Congestion Control Policy Simulated Performance Statistics

Offered Load (Erlang)	Mean Throughput (As fraction of time link busy)	95% C.I. (as ±%)	Mean Delay (ms)	95% C.I. (as ±%)
0.7
0.8
0.9
1.0
1.1
1.2
1.3
1.4

(3.4) Using your data from Tables 1 and 2, plot (i) a graph comparing the mean delay of the drop-tail and RED congestion avoidance policies and (ii) mean normalised throughput of the two policies (using offered load on x-axis of graphs). Briefly comment on the differences.

(3.5) From simulation results, when offered load is 1.1 Erlangs, what proportion of accepted packets are delayed by more than 25ms? Quote the 95% confidence interval with your answer. Assuming that a higher layer protocol ignores/discards packets that have been delayed longer than 25ms, estimate and compare the total effective throughput for the RED policy and the drop-tail policy (using your answer of (2.5) for the calculation for drop-tail).

Attachment:- Event Simulation of a Random Early Detection.rar