Assignment 4: Budgie Bedlam (32 marks)

Due: Thursday, April 10, 2014 (11:59pm)

Learning Objectives

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.

Background

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.

Problem Description

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.0 minutes, and the silent period for each budgie is exponentially distributed with a mean duration of 30.0 minutes. (With these settings, the value of S is 0.25, since on average there are 10 minutes of song followed by 30 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 Pet Land will certainly verify this!) In between is the "right" number of budgies that maximizes Melodious operation. But how many is it? Maybe 2? Or 5? Or 12? Or 20? Or 3.14? Who knows?

Technical Requirements

Your task in this assignment is to find out how many budgies to bring home, 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, either on the command line, via user input, or in the code itself. 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 20 marks, allocated based on discrete-event simulation design (4 marks), budgie ON-OFF activity model (4 marks), proper use of (floating point) random numbers (4 marks), adequate instrumentation (4 marks), and reasonable input and output formats (4 marks).

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

Questions

1. (4 marks) Use your simulation program to determine the optimal number of budgies to have in your BLAN to maximize the proportion of Melodious time. Do this by running your simulation program with several different settings for N, and plotting the results. Specifically, draw a graph showing how the proportions for Quiet, Melodious, and Squawky time vary as a function of N. Indicate on your graph the optimal value of N that maximizes Melodious-ness. Comment on why this value makes sense (if it does).
2. (4 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 30.0 minutes (exponentially distributed, as before). For this purpose, please assume an exponentially-distributed song duration, but consider different mean values (e.g., 5.0 minutes, 10.0 minutes, 15.0 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.
3. (4 marks) Define a "perfect song" as a song by an individual budgie that does not experience any Squawky-ness during its entire duration. That is, the song is not interfered with by any other budgie's song. If you have only 1 budgie, then all songs will be perfect, by definition. But for multiple budgies, some songs might be perfect, and some might not. Modify your simulation to report the percentage of songs that are perfect, using some of the sample scenarios above. Plot a graph showing your results. Explain your results as best you can, perhaps by relating it to our in-class analysis of the ALOHA protocol.

Bonus: (2 marks) Suppose that budgies can be trained to sing for exactly 10 minutes every time, 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, or the proportion of perfect songs? Modify your simulation model to answer this question. Explain your result as best you can.

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

Tips

• If you have never done discrete-event simulation before, you should make sure to get to your CPSC 441 tutorial on simulation methods. You might also find the following barber shop example instructive (or at least amusing!).