cybiko:macimpl:final

CS 395 Project -- Final Checkpoint

For the final checkpoint, you'll add the following functionality. Each of these items are discussed in more detail below:

  • Constants
  • CSMA/CA Mechanism
  • Non-Random Backoff
  • Enhanced Beacon Handling
  • Misc

You must get a new copy of rf.c and the enhanced I/O code. More information is here.

Define SIFS to be 300ms, and the slot time to be 500ms. DIFS is defined to be (SIFS + 2*SLOT). Set the beacon interval to 60 seconds so they interfere with our data less frequently. (It will take longer for a group to synchronize their clocks, but we can speed the process by manually requesting that beacons be sent.) Also, define a constant specifying the maximum number of transmission attempts (10) that will be made for any given data frame. The frame must be discarded if it can't be delivered within the specified number of attempts.

Create the constants CWmin (2) and CWmax (64), that specify an upper and lower bound on the collision window values. Initially, the size of a collision window will be randomly selected in the range [0..CWmin-1]. At successive collisions, the upper limit on the random value will be doubled until it reaches CWmax. These values are quite a bit smaller than those used in actual 802.11 implementations, and will make collisions more likely.

The CSMA/CA mechanism is outlined in Figure 14.6 in the book. Even if the channel is idle when an outgoing frame is ready, your implementation must wait for DIFS. If the channel remains idle during this time, the frame can be sent immediately. If the channel becomes busy during the initial wait (or is busy when we first check), it is handled as though a collision had occurred – an initial backoff window is selected (measured as an integer number of slots) and, once the channel becomes idle for DIFS, they system begins counting down. If the channel becomes busy again during the countdown, the counting is paused until the channel has been idle for DIFS, at which point counting is resumed. Once our count has gone to zero without another station claiming the channel, we can transmit our frame and wait for an ACK. If the ACK doesn't arrive within the expected interval, we double our window size, select a backoff interval randomly within the window, and start over again.

When a countdown is interrupted by a transmission, any partial slots that have elapsed are ignored – only completely elapsed slots are subtracted from the count. Also, when a transmission ends, each station considers the actual ending time to be the start of the next slot. That is, round LocalTime up to the next multiple of SLOT, then wait for DIFS. This will ensure that all stations declare the end of transmission to have occurred simultaneously, even though each station will notice the actual end of transmission at slightly different times. It is possible that one or more stations will round to a different slot than the others, but this isn't a problem.

You must not use sleep for any of these waits, since you would ignore all events that occur during your nap. Instead, check the clock each time MAC_Service is called, and take the appropriate action once a given time interval has elapsed. (The exception to the “no sleep” rule is when a station waits for SIFS before sending an ACK – that's a small enough time interval that sleep can be used without harm.)

The whole point of selecting a random backoff interval is to decrease the chances of a collision. But we'll want to be able to cause occasional collisions so that we can watch how our implementations react and verify that they're working. Your implementation should select intervals randomly by default, but should support a mode where it always uses an interval equal to CW - 1. Each time the user presses Select, this setting should toggle. If two stations are using non-random intervals and try to send simultaneously, they will collide continuously until the maximum number of resends has been reached.

Again with the beacons! You had to get the beacons working as part of your last checkpoint, but we couldn't handle them authentically since the CSMA/CA mechanism was missing. The 802.11 specification says that beacons should be treated essentially like data frames: When it's time to send a beacon, we must wait for DIFS before sending. If the channel becomes busy while we're waiting, we have to pick a random backoff interval and follow the normal rules. The only difference is that, once we've claimed the channel and transmitted our beacon, we discard the beacon frame without waiting for an ACK. Since beacons are broadcast frames, no ACK will be coming. We might therefore lose a beacon to a collision and never know, but we'll try again before long. Make sure that the timestamp is stored in the beacon frame just before sending.

Each host must start its random number sequence at a unique spot, otherwise they may continually select the same “random” backoff intervals. During initialization, once you've computed the initial clock offset, use that value as an argument to srand.

Final code release 802.zip


Brad Richards 2002

  • cybiko/macimpl/final.txt
  • Last modified: 2009/11/27 17:56
  • by 127.0.0.1