Assignment 4: Budgie Bedlam (25 marks)

Due: Thursday, March 29, 2012 (11:59pm)

The purpose of this assignment is to learn about Medium Access Control (MAC) protocols. In particular, you will study an ALOHA-like protocol, with simple principles of randomization for distributed operation. Along the way, you will also learn how to develop and use a simple discrete-event simulation for network performance analysis.

A budgie (short for Budgerigar) is a cute little bird that is native to Australia. They are popular as housepets because they are small, smart, easily domesticated, and incredibly fun to have around. Budgies are quiet most of the time, but are also good songbirds, known for their happy chirps and tweets when they sing.

In this assignment, you will construct a discrete-event simulation model of budgie behaviour, and use your model to answer some basic questions about the performance of a Budgie Local Area Network (BLAN).

You will use the following assumptions in your work:

• There are N budgies in the BLAN, where N is a finite positive integer.
• On average, budgies spend a fraction S of their day singing, and the other fraction 1-S in quiet mode (e.g., staring, listening, grooming, eating, drinking, pooping, sleeping).
• Budgies start singing at random times (day or night), and the duration of a budgie song is random. Specifically, the song duration for each budgie is exponentially distributed with a mean duration of 10 minutes, and the silent period for each budgie is exponentially distributed with a mean duration of 90 minutes. (With these settings, the value of S is 0.1, since on average there are 10 minutes of song followed by 90 minutes of quiet, a pattern that is repeated over and over all day long.)
• Each budgie operates independently of other budgies. That is, they can choose to burst into song whenever they want, regardless of what the other budgies are doing.
• When no budgies are singing, the BLAN is Quiet.
• When exactly one budgie is singing, the BLAN is Melodious (i.e., very beautiful music).
• When more than one budgie is singing at the same time, the BLAN is Squawky. That is, the overlapping songs of the multiple budgies confuse the budgies, as they each try to sing even louder than the others. The result is painful to the ears, and hence the term "squawky".

As a potential budgie owner (and network optimization freak!), you want to figure out exactly how many budgies you should purchase from the pet shop so as to maximize the Melodious time in your household. If you have very few budgies, then your house will be Quiet most of the day. If you are foolish enough to buy 50 budgies, then it will be Squawky almost all the time. (A trip to Petcetera will certainly verify this!) In between is the "right" number of budgies that maximizes Melodious operation. But how many is it? Maybe 5? Or 12? Or 20? Or 14.667? Who knows?

Your task in this assignment is to find out, by writing and using a simple discrete-event simulation program for the BLAN. Your program can be written in either C or C++. Regardless of the language chosen, make sure you are familiar with how to generate and use (pseudo-)random numbers to study the statistical properties of the BLAN performance.

Your program should be easily parameterizable for different values of N. Your program should be carefully instrumented to keep track of the different events that can happen in the BLAN (e.g., start of a song for Budgie i, end of a song for Budgie j), and to record exactly when the BLAN is Quiet, Melodious, or Squawky. Simulating a week or a month of budgie activity is probably sufficient for your needs. Your program is worth 15 marks, allocated based on discrete-event simulation design (3 marks), budgie activity model (3 marks), proper random number use (3 marks), adequate instrumentation (3 marks), and reasonable output results (3 marks).

Once you have your program successfully working, use it to answer as many of the following questions as you can.

Questions

1. (5 marks) Draw a graph showing how the proportion of Quiet, Melodious, and Squawky time vary as a function of N. Use your simulation program to determine the optimal number of budgies to have in your BLAN to maximize the proportion of Melodious time. Indicate this value on your graph. Comment on why this value makes sense (if it does).
2. (2 marks) Suppose that budgies can be trained to sing for exactly 10 minutes, rather than for an exponentially-distributed random duration with a mean of 10 minutes. Would fixed-duration songs change the optimal value of N for the BLAN? Modify your simulation model to answer this question. Explain your result as best you can.
3. (3 marks) Use your simulation model to determine the relationship (if any) between S and the optimal N. You will do so by varying the setting for the average song duration, while keeping the average quiet time setting at 90 minutes (exponentially distributed, as before). For this purpose, please assume an exponentially-distributed song duration, but consider different mean values (e.g., 5 minutes, 10 minutes, 20 minutes). Plot a graph showing how the proportion of Melodious time varies as a function of N, with one line for each of three different song durations considered. Calculate and show the S value for each. Determine the best N for each value of S. Explain your observations.

When you are finished, please email your assignment solution to your TA, on or before the stated deadline.

TIPS: If you have never done discrete-event simulation before, then you might find the following barber shop example particularly educational (if not downright amusing).