6.02 Lab #5: Media Access Control (MAC) Protocols

Deadlines

Useful links

Goal

Using WSim, a shared medium network simulator, develop and experiment with various media access (MAC) protocols. This lab's primary purpose is to help you understand MAC protocols better with a series of relatively simple experiments. It is best done either after reading the notes for Lecture 10, which covers the material taught in lectures 10 and 11, using that as reference.

Instructions

See Lab #1 for a longer narrative about lab mechanics. The one-sentence version:

Complete the tasks below, submit your task files on-line before the deadline, and sign-up for your check-off interview with your TA.

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 to help in debugging, you will need wxPython (2.8.x), which has already been installed on the athena machines. To install it on your computer, visit http://www.wxpython.org/

Introduction

This lab uses WSim, a simple packet-level network simulator for a shared medium network. You will be writing a small amount of code to develop various MAC protocols and measure how they perform under different conditions. Much of your work will be on experimenting with various parameters and explaining what you observe. In each experiment, all the nodes run the same MAC protocol. The simulator executes a set of steps every time slot; time increments by 1 each slot.

Three files -- lab5_wnet.py, lab5_wnode.py, and lab5_util.py -- implement the bulk of WSim. You won't need to modify these files for tthis lab. The five lab task files (lab5_n.py) contain the classes 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). This lab does not work well in IDLE (you can use IDLE to edit files, but running them may not work as expected).

To understand the different parameters one can set in WSim, go to a shell (i.e., command line prompt) and enter:

python602 lab5_1.py -h

(Or, in ipython, run lab5_1.py -h)

This command prints out the various options; the important ones are:

  1. 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 of 100% (which is what we will use in this lab), 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.
  2. 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. Notice that setting a large packet size (say, 10) emulates an "unslotted" network.
  3. Skew: The -k option specifies whether the load is skewed or not. The load itself is generated according to a random process, whose details aren't important for this lab. By default, the skew is off, so all nodes generate the same load on average. When the -k 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.
  4. Number of nodes: The number of nodes in a run of WSim; default is 16. Set using -n.
  5. GUI: The -g option turns on the graphical user interface, which may be of some use in debugging your code. We recommend 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.

Experimental method

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 (L10-11). 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 three methods that you can use to implement the core of the MAC protocol:

boolean = node.channel_access(time,ptime,numnodes)
This method is called by WSim every time slot when the node has a packet waiting to be sent in its queue. This method should return True if the MAC protocol you're implementing would like a packet sent in the current time slot, and False otherwise. time is current time, ptime is the packet size in time slots, and (for TDMA) numnodes is the number of nodes in the network.

node.on_collision(packet)
Called every time slot in which the node has experienced a collision.

node.on_xmit_success(packet)
Called every time slot in which the node has successfully sent a packet (i.e., no collisions occurred during transmission).

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 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.)

Task #1: TDMA (1 point)

Implement a simple TDMA scheme by suitably filling in the channel_access() method in the template file lab5_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. Note that a node can determine its unique node number (an integer between 0 and numnodes-1) by calling self.get_id().

The slightly tricky part of this function is to correctly handle packet sizes that are larger than 1 time slot. We want the TDMA scheme to treat each packet as an atomic unit of transmission; when the protocol determines that a given node can send, that node should send the complete packet. Put another way, we want the effective size of a time slot in the scheme to be equal to the packet size. You will probably find it easier to first write the function and run it for a packet size of 1 slot, then modify your code to correctly handle larger packet sizes. Note that when the packet size is set to some value using the -s option, all nodes will use that value.

Run the following using python602 or ipython602 (after you test it for various packet sizes to ensure that there are no collisions):

When you're ready to submit your code on-line, enable the call to lab5.checkoff. This will just upload your file to the server. When submitting, run your task file using python602 since the submission will not work correctly when run from idle602.

Please enter your answers to the following questions on-line on the lab questions page.

1.1: With a skewed load (-k), as one increases the number of nodes, what happens to the utilization? Why?

1.2: What is the number of nodes at which the network utilization is smaller than 0.25 for the skewed workload? (Because each run is randomized, run it a few times to be confident of your answer.)

Task #2: Aloha with Fixed Probability of Sending (1 point)

In this task, we will implement slotted 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 lab5_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(), so that the node will transmit packets with the configured probability. Your scheme should work when a packet is 1 slot long, but also for longer packet sizes (of course, the utilization may be different for different packet sizes).

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 the following for different values of p and observe the resulting utilization. These tests use the -r option to force multiple nodes to usually be backlogged. With this option, each collision causes a retry. Because the (default) offered load is 100%, the retries ensure that the total offered load exceeds the channel rate. You can also observe this backlog if you run the following tests with the -g option and pay attention to the queue lengths at the nodes.

    python602 lab5_2.py -n 16 -r -p PROBABILITY_HERE

When you're ready to submit your code on-line, enable the call to lab5.checkoff. This will just upload your file to the server. When submitting, run your task file using python602 since the submission will not work correctly when run from idle602.

Please enter your answers to the following questions on-line on the lab questions page.

2.1: What value of p in the range (0,1) maximizes the utilization in your experiments? What is the maximum utilization?

2.2: We will now explore a skewed load to see whether that affects the best choice of p. Run the following for a few values of p.

    python602 lab5_2.py -n 16 -r -k -p PROBABILITY_HERE

What value(s) of p in the range (0,1) maximizes the utilization in your experiments in this case? What is the maximum utilization?

2.3: How do the optimal values of p and the corresponding utilization compare with the no-skew case? Why are they different?

Task #3: Stabilizing Aloha (with Backoff) (1 point)

In this task, we will develop a stablization method for Aloha using randomized backoffs to replace the fixed probability of Task #2. Our goal is to adaptively select the transmission attempt probability, p, used in the channel_access method. To do that, write your code in lab5_3.py to adjust p in the on_collision and on_xmit_success methods, which are called when a packet transmission fails and succeeds, respectively.

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). In your code, ensure that pmin ≤ p ≤ pmax.

You can use any algorithm you want to set p in these functions, including the ones discussed in lecture. Good schemes achieve high utilization, but ensure also that fairness is high (as close to 1 as possible -- lower than 0.9 is a sign that there is significant unfairness when the number of nodes is between 8 and 16) and avoid the capture effect. There is no absolute correct answer (though there are bad methods!), so feel free to be creative if you think you have a good idea. Note that you are not allowed to use the number of backlogged nodes in your scheme, because that information would not be available in practice.

In the on_collision function, if you add the line self.coll.append(self.network.time) and in the on_xmit_success() function, if you add the line self.sent.append(self.network.time), you'll be able to see a plot of the red and blue points corresponding to collisions and successful packets, respectively. Remember to initialize each list to [] in __init__().

Run your code as follows for a few different settings of pmin and pmax and observe the utilization and inter-node fairness values.

    python602 lab5_3.py -r -n 8 --pmax=PROBABILITY_HERE --pmin=PROBABILITY_HERE

(Note the two dashes in front of the pmax and pmin options.)

When you're ready to submit your code on-line, enable the call to lab5.checkoff. This will just upload your file to the server. When submitting, run your task file using python602 since the submission will not work correctly when run from idle602.

Please enter your answers to the following questions on-line on the lab questions page.

3.1: Run python602 lab5_3.py -r -n 8 --pmin=0 --pmax=1. Would you recommend running a real network with these parameters for pmin and pmax? Briefly explain your answer.

3.2: Pick pmin and pmax so that the fairness is as large as possible when the number of nodes is 8 and there is no load skew. What is the utilization of your protocol when the packet size is 10 slots? How does it compare to the utilization when the packet size is 1?

For the first case (packet size of 10), run
    python602 lab5_3.py -s 10 -t 70000 -r -n 8 --pmax=PROBABILITY_HERE --pmin=PROBABILITY_HERE
For the second case (packet size of 1), run
    python602 lab5_3.py -r -n 8 --pmax=PROBABILITY_HERE --pmin=PROBABILITY_HERE

Task #4: CSMA (1 point)

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 idle, you can use the self.network.channel_idle() from inside channel_access(). This function returns True if there is no 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, when it does the check for whether the channel is busy. However, it is still possible for collisions to occur, for multiple nodes could simultaneously sense the channel at the beginning of a slot, and conclude that the channel is "idle", and possibly attempt a transmission in that time slot (or in the same future time slot).

Write your code lab5_4.py for the channel_access() method assuming that the node has the ability to sense the carrier. Obviously, you should fill in the steps for the on_collision() and on_xmit_success() methods as well.

In the on_collision function, if you add the line self.coll.append(self.network.time) and in the on_xmit_success() function, if you add the line self.sent.append(self.network.time), you'll be able to see a plot of the red and blue points corresponding to collisions and successful packets, respectively. Remember to initialize each list to [] in __init__().

Test your code as follows. The -s option is important because it causes the packets to be longer than 1 slot, allowing a node to sense whether another transmission is in progress during a time slot.

python602 lab5_4.py -r -n 8 -s 10 -t 100000 --pmax=PROBABILITY_HERE --pmin=PROBABILITY_HERE

Note that you should run the above for 100000 time slots, because we have scaled up the packet size to 10 (from 1).

When you're ready to submit your code on-line, enable the call to lab5.checkoff. This will just upload your file to the server. When submitting, run your task file using python602 since the submission will not work correctly when run from idle602.

Please enter your answers to the following questions on-line on the lab questions page.

4.1: What is the utilization and fairness of your protocol when pmin = 0 and pmax = 1?

4.2: How would you set pmin and pmax in your protocol to make the fairness number be over 0.95 consistently?

Task #5: Practical CSMA, as in WiFi (802.11) and Ethernet (802.3) (3 points)

The ALOHA and CSMA schemes in the previous tasks pick a probability p for transmitting a packet, and adapt p to stabilize the protocol. The advantage of this method is that it is easy to analyze. In practice, however, real-world CSMA protocols like the popular 802.11 WiFi standard and the 802.3 Ethernet standard implement something a bit different, as explained below. Your task will be to write the code for the key parts of this scheme.

Rather than decide whether any given slot should have a transmission with probability p, each node maintains a contention window, which we denote by cw. cw is initially set to cwmin, which is a small positive integer (say, 1). Denote the current time slot by C. If the sender is backlogged, it picks a random integer t in [1, cw] and decides to send a packet in time slot C + t.

Of course, with carrier sense in place, the sender should only send a packet if the channel is idle in time slot C + t. So, the sender senses the carrier in that time slot, and then sends a packet only if the channel is idle then. If the channel is not idle, it waits until the channel is idle, and then sends the packet.

Whenever a collision occurs, the node doubles cw, but makes sure cw never exceeds cwmax (say, 512). Whenever a transmission is successful, the node might reset cw to cwmin, or might halve its current value of cw. You will note that this scheme is similar in spirit to the probabilistic transmission scheme from Task #4, but a crucial difference is that here each backlogged node is guaranteed to send a packet within a finite time, unlike in the probabilistic case where there is always a small probability that the node cannot send within any given number of time slots. In mathematical terms, the probability distribution that governs whether a node transmits a packet in a given time slot is uniform in this scheme (Task #5), while it is geometrically distributed in the previous case (Task #4).

You will first implement the scheme described thus far. It will turn out not to do as well as we would like, and in Task 5.2, you will fix an important weakness.

Implement this scheme by writing the appropriate code for channel_access(), on_collision(), and on_xmit_success() in lab5_5.py. How well does it work? To answer this question, measure the utilization and fairness by running
    python602 lab5_5.py -r -s 10 -n 8 -t 100000 -W 256

The -W option sets the maximum contention window size. The minimum contention window is 1 (you can change it using the -w option if you like (lower case "w"). Running the above, you will note that even with carrier sense being used, the utilization is quite a bit lower than in Task 4.

Please enter your answers to the following questions on-line on the lab questions page.

5.1: Report the utilization and fairness. Briefly explain why the utilization is low.
Hint: Think about what happens if more than one node is backlogged and waiting for an on-going transmission to complete; what happens when the on-going one finishes?

To fix this problem, each node needs to ignore the time slots when other nodes are transmitting data. That is, if a node picks a time slot t in [1, cw] to transmit, it should wait for that many idle slots before attempting its own transmission. Of course, before transmitting data, it should ensure that the channel is idle.

5.2: Modify your code to include the above suggestion and run the same command as before:
    python602 lab5_5.py -r -s 10 -n 8 -t 100000 -W 256

Report the utilization and fairness for your scheme after including the suggestion and running the same command as before.

End of Lab #5!

Don't forget to submit the on-line lab questions!