Assignment 2 (20 marks)
Due: March 2, 2010 (3:30pm)
The purpose of this assignment is to gain experience with simulation methods that can be used in computer systems performance evaluation.
Please do any one of the following 3 questions. Note that the marks allocated are the same for each question, but they may not be of the same difficulty.
Q1. Weasley Barber Shop (20 marks)
Write a computer simulation (8 marks) of the Weasley Barber Shop from Assignment 1.
- (2 marks) Use your simulation to determine the proportion of lost customers when lambda = 4, mu1 = 3, and mu2 = 2.
- (2 marks) Use your simulation to validate your analytical solution to the problem (if any).
- (4 marks) Use your simulation to compare your results to those for an M/M/2 queue, where the servers have homogeneous rates mu1 = mu2. Comment on your results.
- (4 marks) Use your simulation to compare your results to those for an M/M/1/K queue, where the single server has an aggregate service rate of mu1 + mu2. Comment on your results.
Bonus (up to 4 marks)
Conduct a one-factor simulation experiment varying the waiting room size to see the effect on the loss of customers at high load.
Q2. Vehicular Adhoc Network Modeling (20 marks)
In today's high-tech world, passengers in vehicles traveling on highways can make use of wireless Internet access to browse the Web and check their email even while they are mobile. These networks are called Vehicular Adhoc Networks (VANETs). There are lots of papers on VANETs in the networking literature, including measurement, simulation, and analysis papers.
One recent paper [Bai et al. 2003] proposes a mobility model for VANETs. A simplified description of this model is as follows:
- Vehicular traffic is unidirectional, and in a single lane.
- Initial vehicular speeds are chosen uniformly at random from a specified speed range (V_min,V_max).
- Vehicular speeds are adjusted dynamically with time using V_i(t + delta) = V_i(t) + A * random() * delta, where V_i(t) is the speed of node i at time t and A is the acceleration factor. random() is a function that returns a random value in the range [-1,1]. The resulting speed is constrained to fall within the specified speed range (V_min,V_max).
- If the distance between any two vehicles is less than a specified safety threshold distance (50 m), then the speed of the approaching car is decreased to avoid a collision between the two cars.
One concern with this mobility model is that it is not clear whether it produces a Poisson distribution of cars on the highway or not. Many of the analytical models for channel access protocols assume that the distribution of nodes is Poisson.
Your goal is to investigate the properties of this traffic model, using simulation. You can assume that cars enter the highway according to a Poisson process, and then depart according to an unknown process after traveling 10 kilometers of highway. Your task is to study the (unknown) departure process, and see if it is Poisson or not.
- (8 marks) Design and implement a VANET simulation scenario with this vehicular mobility model, using a programming language and environment of your own choice. Parameterize your simulation reasonably, and document any additional assumptions you make. Instrument the simulator adequately so that you can collect the timing information required for your analysis of results.
- (4 marks) Conduct a one-factor simulation experiment varying the vehicle arrival rate to see the impact, if any, on the vehicle departure process.
- (4 marks) Conduct a one-factor simulation experiment varying the speed range (V_min,V_max) to see the impact, if any, on the vehicle departure process.
- (4 marks) Conduct a one-factor simulation experiment varying the number of lanes on the highway to see the impact, if any, on the vehicle departure process.
Bonus (up to 4 marks)
Conduct a one-factor simulation experiment varying the vehicle arrival process (i.e., non-Poisson) to see the impact, if any, on the vehicle departure process.
Q3. Elevator Scheduling (20 marks)
A fictitious office building that is H stories high has N functional elevators. People arrive to the building at random times and enter on the ground floor (Level 1) according to a Poisson process with aggregate average rate lambda. They request an elevator, enter it, ride upwards, and get off at a floor that is chosen uniformly at random. They remain at work on that floor for a randomly chosen amount of time (exponential distribution), before returning to the elevators, requesting one, riding down to Level 1, and departing the building (also with aggregate average rate lambda, in steady state). The performance metric of interest is the user-perceived response time, which is the elapsed time between requesting an elevator and getting off at the desired floor.
There are many possible variations that can be made to the configuration and operation of elevators: number, speed, capacity, scheduling. Your goal is to explore a small subset of these possibilities. In terms of other parameters, you can assume that N = 3, H = 7, and that the movement time between adjacent floors of the building is 10 seconds, regardless of occupancy, distance, or direction traveled by the elevator. You can assume that the elevator can hold as many people as required.
- (8 marks) Design and implement a simulation model of this office building, including its elevators, using a programming language and environment of your choice. Parameterize your simulation reasonably, and document any additional assumptions you make. Instrument the simulator adequately so that you can collect the timing information required for your analysis of results. (Tip: Design, debug, and test your simulation with just 1 elevator initially. Then you should be able to extend it to N elevators by changing scalar state variables (e.g., occupancy, floor, direction) into array variables.)
- (4 marks) Conduct a one-factor simulation experiment varying the customer arrival rate lambda over a reasonable range of values. Show the impact, if any, on the average user-perceived response time.
- (4 marks) Conduct a one-factor simulation experiment varying the number of elevators from N = 1 to N = 2 to N = 3. Show the impact, if any, on the average user-perceived response time.
- (4 marks) There are several choices for what an elevator can do when it is empty: stay where it is, go to the bottom floor, go to the top floor, or go to the "middle". For N = 1, conduct a one-factor simulation experiment varying this idling policy to see the impact, if any, on the average user-perceived response time.
Bonus (up to 4 marks)
There are several choices for what an elevator can do when multiple requests are pending. One choice is to only service requests that are in the same vertical direction being traveled. Another is to service the closest request, regardless of the direction being traveled. For N = 1, conduct a one-factor simulation experiment varying this scheduling policy to see the impact, if any, on the average user-perceived response time.
Submitting Your Assignment
When you are finished, hand in a hardcopy version of your solution to your instructor, either in person, or under his office door. Provide proper citation for any literature or Internet sources used. Submissions must be received on or before the stated submission deadline, otherwise a late penalty of 10% (2 marks) per day will apply.