算法代写|math代写|C语言|C++|数据结构代写 – ECE 610 Project Queue Simulation

算法代写|math代写|C语言|C++|数据结构代写: 任务旨在通过C、C++来掌握离散事件模拟的基本要素

ECE 610 Project Queue Simulation

Objective:After this experiment, the students should understand:i. The basic elements of discrete event simulation. In particular, the notion ofan event scheduler for simulating discrete event systems and the generationof random variables for a given distribution.ii. The behavior of a single buffer queue with different parameters C, L, K and (as defined below), as it is a key element of a computer network.iii. The need to be careful about when a system should be observed to obtainthe correct performance metrics.Programming Languages: Students can only use C or C++.

Overview:

The performance of a communication network is a key aspect of networkengineering. Performance measures like delay (how long a packet stays in a system ortakes to be delivered), loss ratio (the percentage of the packets that are lost in the system),etc. are some of the criteria that network engineers are trying to predict or measure sincethey affect the Quality of Service (QoS) offered to the users. In order to do so, modelsare built to help understand the system and predict its behavior. A model of a system is amathematical abstraction that captures enough of the systems features to give goodestimates of the systems performance. The purpose is to build a model and to analyze itto get results on the performance we can expect. Hence depending on the performancewe want to study (e.g., reliability, loss, delay,…) we will build a different model of thesystem. In real situations the complexity of a system can be extremely high (this is thecase in a network), and hence the model describing it can be very complicated. In thatcase it may be difficult to analyze the model exactly. We can either simplify the model(which is an art, since we need to keep it relevant) or try to solve the complicated model using approximations. In both cases, the results thus obtained SHOULD be validated bysimulation.Simulation is not only useful for validating approximate solutions but also inmany other scenarios. During the design of a system, it allows us to compare potentialsolutions at a relatively low cost. It is also very useful to dimension a system, i.e. todecide how much resources to allocate to the system based on an a-priori knowledge ofthe inputs. It is also used to check how potential modifications of an existing systemcould affect the overall performance. Simulation is also especially useful when it isdifficult or impossible to experiment with the real system or take the measurementsphysically, e.g., measuring the performance of the Internet as the whole, performingnuclear reactions, airplane crash tests, etc. With the use of computer simulations, theabove mentioned scenarios can be reproduced to help us gain insights about the behaviorof the system.To perform a simulation we need a model of the system, as well as models for itsinput(s). This will be discussed later in more detail.In communication networks, the most frequent basic-block model we encounter isa queue. You are going to design a simulator, and use it to understand the behavior oftwo basic types of queues.

Background Materials:

In this experiment, you will be asked to simulate a FIFO (First-In-First-Out)queue (see Figure 1). In general a queue is described by three to five parameters, with aslash ( / ) separating each of them, e.g., G/G/n/K/FIFO. This is referred to as Kendallnotation. We are interested in the first four parameters (the fifth parameter is the servicediscipline, which is FIFO by default).The first and second parameters are descriptions of the arrival process and theservice process, respectively. M means memoryless or Markovian, D meansDeterministic and G means General. The third one is the number of servers, and thefourth one is the size of the buffer. So, for example M/M/n means that both the arrivaland service processes are Markovian, and that there are n servers. If the fourth parameter is not present, it means that the buffer size is infinite. M/G/1 means the queue has oneserver, the arrival process is Markovian and the service process is general (some non-Markovian distributions, e.g., Gaussian). If the arrival process is M, it means that thedistribution of the time between successive arrivals (also called inter-arrival time) isidentical for all inter-arrivals, is independent from one interarrival to another and isexponentially distributed. This is equivalent to saying that the process counting thearrivals is Poisson. If the service process is M, it means that the distribution of theservice time is identical for each customer/packet, is independent from one customer toanother and is exponentially distributed. The exponential distribution is often used inperformance evaluation because it is an easy distribution to use (it is characterized byonly one parameter) and it is adequate to model call durations and call arrivals in atelephone system. In a data communication system such as the Internet, it is not soadequate for modeling the arrival process of packets but is still used due to its simplicity.If the service process is D, it means that each customer/packet will receive the sameconstant service time.

Buffer Server
Incoming packet

Figure 1 Model of a queue

The queues you need to simulate in this experiment are M/M/1, D/M/1, M/G/with a bipolar packet length distribution, M/D/2, and M/D/1/K.

Simulation BasicsA simulation model consists of three elements: Input variables, Simulator andOutput variables. The simulator is a mathematical/logical relationship between the inputand the output. A simulation experiment is simply a generation of several instances ofinput variables, according to their distributions, and of the corresponding output variables

from the simulator. We can then use the output variables (usually some statistics) toestimate the performance measures of the system. The generation of the input variablesand the design of the simulator will be discussed below.

Generation of input variables with different distributions:You will need a uniformly distributed random variable (r.v.) generator. Inparticular, you will need to generate U(0,1), a uniform r.v. in the range (0,1). It isimportant to use a good uniform r.v. generator for better simulation results. A gooduniform r.v. generator will give you independent, identically distributed (i.i.d.) uniformrandom variables. You can test how good a uniform r.v. generator is by checking themean (0.5) and variance (1/12) of the random samples you have generated. The mean andvariance of a set of such samples should be very close to the theoretical values for 1000or more samples. Note that, in general, it is not enough to check the mean and varianceto conclude on the validity of your random generator, but we will assume that it is a goodenough test for our purposes. Since this is not a course on simulation we cannot spend toomuch time on the topic of the generation of a r.v. but note that you should always start byverifying the performance of your r.v. generator by checking that you are indeedgenerating what you want.If you need to generate a r.v. X with a distribution function^1 F(x), all you have todo is the following: Generate U~U(0,1) Return X = F-^1 (U)where F-^1 (U) is the inverse of the distribution function of the desired random variable.

Question 1: How to generate an exponential r.v. with parameter from U(0,1)? Showall your calculations. Write a short piece of C code to generate 1000 exponential r.v.from your equation, using 1 / =10s. What is the mean and variance of the 1000 randomvariables you generated? Do they agree with the expected value and the variance of a

1To learn more about density and distribution functions, please refer to the book by Alberto Leon-Garcia,Probability and Random Processes for Electrical Engineering, second edition(July 1993), pp. 87.

exponential r.v. with 1 / =10s? (if not, check your code, since this would really impactthe remainder of your experiment).

Simulator design:Discrete Event Simulation (DES) is one of the basic paradigms for simulatordesign. It is used in problems where the system evolves over time, and the state of thesystem changes at discrete points in time when some events happen. These discretepoints in time are not necessarily separated by equal duration. DES is suitable for thesimulation of queues. However, please note that it is not the only way to simulate a queueas simple as the ones that we are asking you to simulate. In this lab, we are not interestedin simulating a queue for the sake of it (this can easily be done with Matlab) but to use itas an application for learning about DES.A queue is made of 2 components, a buffer and one (or many) server(s). Since ourservice discipline is FIFO, the first packet in the buffer enters the server as soon as theprevious one has been served. If a packet enters an empty system, it enters directly intothe server. If the buffer has the maximum number of packets that it can hold (i.e. K),then the new packet is dropped. In the following, we describe the case of a queue withone server.The events that can happen in a queue are either an arrival of a packet in thebuffer or the departure of a packet from a server. Dropping of a packet because thebuffer is full when the packet arrives is NOT considered to be an event in the simulation,but a consequence of an arrival event.Figure 2 depicts the behavior of a typical single server queue with an infinitebuffer. Let Pn be the nth packet, an is its arrival time, sn is its service time, dn is itsdeparture time and Tn is its sojourn time (i.e., the total time spent in the system (bufferand server)). You might find it useful to record the time wn at which packet Pn enters theserver.

Figure 2: The dynamics of a infinite single server queue

The state of the system will depend on what you are interested in. In this project,we will use only the number of packets in the system N(t) as the state of the system. Weare interested in computing the time-average of the number of packets in the queue, E[N],the proportion of time the server is idle (i.e., the system is empty), PIDLE and in the case ofa finite queue, the probability that a packet will be dropped (due to the buffer being fullwhen it arrives). The measurement and recording of the state along time should beperformed such that we have statistically representative information on the performancethat we are interested in.Important note: if we record the state of the system only at times when a packetarrives or departs, we will in general see a biased (i.e., non representative) state of thesystem. As an example, consider a D/D/1 queue as shown in Figure 3, where packetsarrive at a constant rate of 1 packet every 5 minutes and the service time for each packetis 1 minute.

Figure 3: Arrival and departure times in a D/D/1 queue

In this case, if we look at the system at only arrival and departure times (a 1 , d 1 ,a 2 ,d 2 ,…),Pidle = 100% which is not true (Question: what is Pidle in this system?). Note that a randomobserver (i.e., an observer who would come at random times) would see the proper state(i.e., 20% of the time, the system is non-idle and 80% it is idle). A solution to thisproblem is to add another type of events called the observer event. Here, we use anobserver coming at random times generated according to a Poisson distribution ofparameter (it can be shown mathematically that a random Poisson observer will see astatistically representative state of the system if the simulation is long enough and if ischosen correctly). Whenever you process an observer event, you will record the state ofthe system. Therefore, the simulation will now contain three events: packet arrival,packet departure, and observer arrival. Note that you have to ensure that the observerevent is independent of the other two events. (As you have learned in class, thanks to thePASTA property, adding observer events is not necessary if the arrival process isPoisson).DES uses the notion of an event scheduler (ES). Let An be the arrival event ofpacket Pn, Dn be the departure event of packet Pn, and On be the nth observer eventarrival. For each event, the time at which it will occur is recorded, i.e., t(An) = an, t(Dn) =dn, and t(On) = on. Then ES contains a set of time-ordered events Ei, i=1,…, N, such thatt(Ei)<t(Ei+1) for all i along with the time of their occurrences. Hence, an entry for event Eiin the ES contains its type (An, Dn or On) as well as the time of its occurrence t(Ei). Hereis an example of an ES: ES = {(E 1 =A 1 ,10), (E 2 =D 1 ,11), (E 3 =A 2 ,12), (E 4 =O 1 ,16),(E 5 =A 3 ,17), (E 6 =O 2 ,18), (E 7 =A 4 ,21), (E 8 =D 2 ,23), (E 9 =D 3 ,28), (E 10 =O 3 ,31),…}.

Given an arrival process, service process, and observation process, it is easy togenerate an ES beforehand. Then, you are going to move from event Ei to Ei+1 and decidehow to update your variables. Note that in general, you cannot generate all the eventsbeforehand.In summary, in order to create a DES for a simple queue with an infinite buffer,you should do the following:

1. Choose a duration T for your simulation (see later how to choose T).
2. Generate a set of random observation times according to a Poissondistribution with parameter and record the observer event times in theES (generate new events as long as their arrival times are less than T). Putall these events in ES.
3. Generate a set of packet arrivals (according to a Poisson distribution withparameter ) and their corresponding length (according to an exponentialdistribution with parameter 1/L), and calculate their departure times basedon the state of the system (the departure time of a packet of length Lpdepends on how much it has to wait and on its service time Lp/C where Cis the link rate). Put all these events (packet arrivals and departures) in ES.Recall ES is by definition a time-ordered list of events.
4. Now initialize the following variables to zero: Na = number of packetarrivals so far, Nd = number of packets departures so far, No = number ofobservations so far.
5. Dequeue one event at a time from your event scheduler (i.e., read oneevent at a time from the ES, starting with the first in the list), and call thecorresponding event procedure. Each event procedure (one per type ofevent) will consist of updating some of the variables. Clearly when theevent is the arrival of an observer, you record the values of yourperformance metrics. Record also the values of your performance metricsat each packet arrival.

Note:

1. Change state and output variables ONLY when events happen.
2. An event procedure consists of the update of the system variables (depends onwhat the event is) and the update of the output variables.An extremely important problem is to determine how long you should run yoursimulation (i.e. how many repetitions do you need) in order to get a stable result. Thereare a lot of variance reduction techniques out there that help you to determine when tostop, but that is not a requirement for this experiment. An easier way (again, not the bestway, but sufficient for this experiment) to do this is to run the experiment for T seconds,take the result, run the experiment again for 2T seconds and see if the expected values ofthe output variables are similar to the output from the previous run. For example, thedifference should be within x% of the previous run, where in our case x should be lessthan 5. If the results agree, you can claim the result is stable. If not, you try again for 3 T,4 T, … If you cannot seem to find a proper T, it may mean that your system is unstable.For the purpose of this experiment, the value of T should be more than 10, 000 secondsbut you should still use the procedure described above to check the stability (and hencethe validity) of your results.Note that while this is adequate for this lab, in practice you should becomefamiliar with the concept of a confidence interval.

Experiment:

Simulate an M/M/1 queue, a D/M/1 queue, an M/G/1 queue with a bipolar lengthdistribution (i.e., a packet is of length L 1 with probability p and of length L 2 with probability1 – p), an M/D/2 queue and an M/D/1/K queue. Let:

• = Average number of packets generated /arrived per second
• L = Average length of a packet in bits
• n = the number of servers (1 or 2 depending on the queue)
• = Average number of observer events per second
• C = The transmission rate of the output link in bits per second
• = Utilization of the queue (= L /nC)
• E[N] = Average number of packets in the buffer/queue as seen by anobserver
• Ea[N] = Average number of packets in the buffer/queue as seen by apacket arrival
• PIDLE = The proportion of time the n servers are idle
• PLOSS = The packet loss probability (for M/D/1/K queue). This is the ratioof the total number of packets lost because the buffer was full when theyarrived, to the total number of packets generatedNote that and should be of the same order.

M/M/1, D/M/1, M/G/1 QueuesRecall that these queues have an infinite buffer. Assume that the packets have the sameaverage packet length L in these 3 systems.

Question 2 : Build your simulator for these queues and explain in words what you havedone. Show your code in the report. In particular, define your variables.

Question 3 : Assume L=20, 000 bits, C=2 Mbits/second, L 1 = 16 ,0 00 bits (p=0.2),L 2 =21,0 00 bits (1-p=0.8), and give the following figures using the simulator you haveprogrammed. Provide comments on all your figures:

1. E[N], the average number of packets in the system as a function of (for 0. 35 0.9 5 , step size 0. 05 ) for the 3 queues. Explain how you do that.
2. PIDLE, the proportion of time the system is idle as a function of ,(for 0. 35 0.9 5 , step size 0. 05 ) for the 3 queues. Explain how you do that.

Question 4 : For the same parameters, simulate for for one of these queuesWhatdo you observe? Explain.

Question 5 : Compare E[N] and Ea[N] for the M/M/1 queue and for the D/M/1 queue.Explain.

Question 6 : Compare E[T] (the average sojourn time) for the 3 queues. Explain howyou have calculated E[T].

M/D/1/K QueueLet K denote the size of the buffer in number of packets. Since the buffer is finite,when the buffer is full, arriving packets will be dropped.

Question 7 : Build a simulator for an M/D/1/K queue. Explain what you had to do tomodify the previous simulator and what new variables you had to introduce. Show yourcode in the report. (Hint: do not forget that dropping is NOT considered an event)

Question 8 : Let L=20, 000 bits and C=2 Mbits/second. Use your simulator to obtain thefollowing figures (provide comments for each figure):PLOSS as a function of (for 0. 4 3 ,) for K=10, 5 0, 100 packets. (One curveper value of K on the same figure). Explain how you have obtained PLOSS. Usethe following step sizes for For , step size 0.1.For , step size 0.2.

M/D/2 QueueThis is the case where the queue has 2 identical servers of rate C each.

Question 9 : Plot on the same graph E[N] as a function of (for 0. 35 0.95, step size

1. 05 ) for the following 3 queues: M/D/2, M/D/1 (1 server of rate 2C). What do youobserve? Explain.

What To Turn In:

1. Submit a print copy of your report with the following details: Table of contents Answers/explanations/comments for all the questions.
2. Submit your source code in the LEARN dropbox. Be sure to include a makefilethat builds and runs your code.

Reference:Averill Law, W. David Kelton, Simulation Modeling and Analysis, 2nd edition, McGraw-Hill, 1991.