Topics in Performance Evaluation

Exercise 2b – Simulating an M/M/1 Queue

In this exercise we will simulate an M/M/1 queue and an M/G/1 queue and compare them.

Background

The M/M/1 queue can be analyzed analytically, as we did in class. It is also easy to write a simulation of how it behaves. Do these two approaches indeed provide the same results?

The same question can be considered for variations of the M/M/1 queue as well. For example, we will simulate a system in which the service times are Pareto distributed, rather than exponentially distributed. How does this affect the response time as a function of the load?

Assignment

1. Run simple M/M/1 experiments

   write an event-driven simulation of an M/M/1 queue, with the desired load as a parameter. This is a system with one server. Clients arrive randomly to the server, with exponentially distributed inter-arrival times. The time to serve each client is also exponentially distributed. The server can only serve one client at a time; if an additional client arrives, it needs to wait its turn. Waiting clients are served according to a FCFS (first come first served) discipline. In the simulation, the events are client arrivals and departures (after they finish to receive service).

   To create random inter-arrival or service times in simulations you use the system's "random" function. This gives you random variates u with a uniformly distribution on [0,1]. You can turn them into exponentially distributed random variates with a mean m by evaluating -m ln(u). Verify that you indeed get variates with the desired mean.

   Run your simulation for loads of 0.4, 0.5, 0.6, 0.7, 0.75, 0.8, 0.85, and 0.9 (the load is the same as the utilization of the server). Do this by changing the mean of the inter-arrival times, keeping the mean of the service time set to 2: when the inter-arrival times become shorter, the load increases. Use the simulation to find the average response time for each load condition.

   Note that your results may depend on how long you run the simulation. Experiment to find how much is required.

2. Run M/G/1 experiments

   Modify your code to use Pareto distributed service times. Use a Pareto distribution with parameter a = 2, for which the mean is defined and is also equal to 2. Pareto random variates are generated by evaluating 1 / u^1/a, in our case 1 / u^0.5. Verify that you indeed get variates with the desired mean. Run these simulations for the same load values, again by modifying the interarrival times.

3. Analyze the results

   Draw a graph and compare the response time results of the two simulations with the analytic results. Specifically, include 3 lines on the same plot:

   1. simulation of M/M/1 queue
   2. simulation of M/G/1 queue (where G in this case is a Pareto distribution)
   3. analysis of M/M/1 queue, where the mean response time is supposed to be m/(1-r) (where m is the mean service time and r is the load)

Submit

Use Moodle to submit a report on your work, in pdf format, with the following data.

1. Your names, logins, and IDs
2. Characterization of the experiments: (a) the means and standard deviations of the interarrival times and service times in all the simulations; (b) how long did you ran each simulation, and why.
3. The output plot of the simulation results, as explained above.
4. Your conclusion: (a) do the simulation and the analysis match? (b) what is the effect of having a Pareto service distribution?
5. An appendix with the simulator code, including the generation of both exponential and Pareto service times.

To the course home page