Complete the tasks below, submit your task files on-line before the deadline, and complete your check-off interview within a week of the file submission deadline.
As always, help is available in 32-083 (see the Lab Hours web page).
For this lab, if you would like to use the GUI, you will need wxPython (2.8.x). This has already been installed on the athena machines. To install it on your computer, visit http://www.wxpython.org/
Three files---lab8_wnet.py, lab8_wnode.py, and lab8_util.py---implement the bulk of WSim. You won't need to modify these files for this lab. The lab task files (lab8_n.py) contain the objects and methods that you will need to work on.
You can run the python programs for this lab using ipython or python (ipython602 and python602 on the athena machines). The lab will not work in IDLE.
To understand the different parameters one can set in WSim, go to a shell and enter:
python602 lab8_1.py -h
(Or, in ipython, run lab8_1.py -h)
This command prints out the various options.
Load: Each node generates traffic according to a random process (whose details aren't important to us) and queues packets up. The rate of packet generation at the various nodes is controlled with the "-l" option, which specifies the total expected offered load from all the nodes, as a percentage. For example, "-l 90" says that the average offered load from all the nodes is 90% of the maximum channel rate. By default, the simulation picks a load average of 100%.
Skew: The -k option specifies whether the load is skewed or not. By default, the skew is off, so all nodes generate the same load on average, and the total is as specified by the -l option. When the option is set, then the total offered load, L, is divided in geometrically-spaced amounts. Node 0 presents a load of L/2, node 1 L/4, and so on. The last two nodes each present the same load, L/2N-1, where N is the total number of nodes.
Retry: If two or more nodes are actively sending a packet in the same time slot, they collide and both packets are considered lost. The -r option decides whether the node should retry the packet or not upon failure. In WSim, the feedback about whether a packet succeeded or not (i.e., collided) is instantaneous, with the sending node discovering it in the same time slot as the transmission. By default, the retry option is "off". When it is turned on, at an offered load (-l option) of 100%, the actual load presented to the system exceeds the channel's maximum rate. That is, we would expect most queues to be backlogged most of the time with these settings. Of course, by using a smaller value after the -l option, you can change this "mostly always backlogged" behavior.
Packet size: In any given experiment, the size of a packet is fixed. It has to be an integral number of time slots in size (1 or more). To set the packet size, use the "-s" option; the default is 1.
GUI: The "-g" option turns on the graphical user interface, which may be of some use in debugging your code. It is recommended that you set the parameters for the simulation from the command line and NOT from the GUI, as the GUI's parameter setting code may not port well across different python installations.
WSim runs for a specified number of time slots (settable using the "-t" option, with a default of 10000) and prints out some performance numbers (and possibly displays some graphs) at the end. Of interest to us are the utilization and fairness numbers, which are defined in the lecture notes (L18). The code reports a "weighted" fairness number as well, which is the fairness index calculated over the ratio of the observed throughputs to offered loads. The (unweighted) inter-node fairness is calculated over the throughputs alone without regard to the offered load.
In this lab, you will implement the core of three MAC protocols---TDMA, stabilized Aloha (with backoffs), and CSMA---and understand their performance. Each node is an object, which has several methods which you can use to implement a particular MAC protocol:
You can modify any per-node state that you want to in these methods (e.g., the state maintained by the backoff scheme, statistics of interest, etc.). Make sure to add the code to initialize this state in the Node object's __init__ function, whose body is included in the lab task files.
In many (but not all) of our experiments, we will use the "-r" option, which cause the nodes to retry upon experiencing a collision. (Of course, the MAC protocol's channel_access() method will determine when the retry actually occurs.)
Implement a simple TDMA scheme by suitably filling in the channel_access() method in the template file lab8_1.py. Recall that in a TDMA scheme, time is divided into numnodes equal-size slots, each long enough to accommodate the transmission of a single packet and that each node is allocated one of the slots to use when it has a packet to transmit.
The slightly tricky part of this function is to correctly handle packet sizes that are larger than 1 time slot. You might find it easier to first write the function and run it for a packet size of 1 slot, then modify your code for larger packet sizes.
Test your code by running each of the following using python602 or ipython602:
If your code is correct, there should be no collisions. The last run above tests TDMA with a skewed load with 20 nodes.
Q1.1: Under what conditions does TDMA provide good utilization and fairness? And when does it perform poorly?
In this task, we will implement Aloha with a fixed transmission probability and measure its performance under different conditions. The program allows you to set the transmission probability using the "-p" option. Looking at lab8_2.py, note that the __init__ function of AlohaWirelessNetwork sets each node's "p" to the configured value of the transmission probability. Your task is to implement the Aloha MAC protocol by providing the correct code in channel_access().
Please note: For this task as well as the subsequent ones, do not use numnodes in your code, even though it is accessible. The reason is that we want your algorithm to work for arbitrarily distributed offered loads, and using numnodes will not help achieve that.
Test your code by running each of the following using python602 or ipython602 and observe the resulting utilization:
Q2.1: There appears to be some threshold transmission probability above which the utilization is the same. What is that threshold? Can you explain what's going on here?
Now run the following using python602 or ipython602 and observe the resulting utilization:
Q2.2: What setting of p maximizes the utilization in this case? Why is that utilization higher than when p = 1?
Now let's turn retries on. Run the following:
Q2.3: Why is the utilization so much lower than for the same value of p with no retries?
Q2.4: With -l 100 and -r, what value of p maximizes utilization? Why?
Now let's try the unslotted mode, which we can emulate by setting the packet size to be many slots long. Let's pick a packet size of 20 slots, so run:
Q2.5: Does the reported utilization match what you expect from theory?
First, copy over your solution for Task 2 for the channel_access() function into the lab8_3.py file.
We will use two parameters, pmax and pmin. These correspond to the maximum and minimum values of the transmission attempt probability, p. The values of these parameters can be set from the command line when you run the program, and are available as self.network.pmax and self.network.pmin respectively (see the __init__ function of AlohaWirelessNetwork).
We would like to improve the performance of slotted Aloha when the nodes are backlogged a significant fraction of the time. To ensure that there is usually a backlog, we will turn the "-r" (retry) option on for this task.
Our goal is to develop a way to backoff and adaptively select the transmission attempt probability, p.
Modify the channel_access method to implement slotted Aloha with backoff. Use the intuition you developed in Task #2, specifically the performance of the backlogged case for different fixed values of p. You should write your algorithm for what the MAC protocol should do to adapt the transmission probability in response to prevailing conditions. To do this, fill in the suitable steps in the two methods, on_collision() and on_xmit_success().
We have given the code for what happens when the backoff method is "None" (nothing much happens!). You can call your backoff method "Mine", as shown in the options parsing code.
Run your code as follows:
Q3.1: How well does your MAC protocol perform for different values of n, picked at random between 5 and 100. You should be able to get utilization close to 1/e and fairness more than 0.9. The higher the utilization and closer the fairness to 1, the better.
Note: The performance of your MAC protocol should not depend on setting pmax and pmin particularly accurately. The bigger the gap between pmin and pmax, the better. Even better would be not having to set pmax at all (or pmin), if you're able to come up with such a scheme!
Note: You can use (and modify if necessary) the code commented out in __main__ that plots the graphs of each node's p as a function of time.
Q3.2: How well does your protocol perform with the skew option (-k) turned on? Run:
In this task, we will try to get the best utilization and fairness we can for a MAC protocol that uses CSMA. To check if the channel is busy, you can use the self.network.channel_busy() from inside channel_access(). This function returns True if there is any on-going transmission in the current time slot, and False otherwise.
Every carrier sensing mechanism has a detection time, defined as the time interval between the ending of a previous transmission and the detection of the channel as "idle" by a node. For the purposes of this lab, we will assume that the detection time is 0. Hence, a node can sense that the carrier is idle in the immediate next slot after the termination of the previous transmission. However, it is still possible for collisions to occur, for multiple nodes could simultaneously sense the channel and conclude that the channel is "idle", and possibly attempt a transmission in the same future time slot.
Using the intuition, and possibly the code from Task 3, implement the channel_access() method assuming that the node has the ability to sense the carrier for idleness. Obviously, you should fill in the steps for the on_collision() and on_xmit_success() methods as well.
Run your code with packet size of 1 slot (-s 1), as follows:
Q4.1: Is the performance different from that of slotted Aloha (without CSMA) with the same backoff function (i.e., from task 3)? Why (not)?
Run the same code for larger packets, i.e., run:
Q4.2: What is the utilization and fairness of your protocol. We will consider a utilization above 0.6 and fairness above 0.9 as "good".