cybiko:macimpl:chkpoint3

CS 395 Project Checkpoint #3

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

  • Clock Synchronization
  • Delay before ACK
  • Detect Overdue ACKs
  • Extend User Interface

You should also get a new copy of rf.c, as a number of significant changes have been made. The interface is exactly the same as the original. A copy of my executable and rf.c are zipped here.

The four-byte MAC address 0xFFFFFFFF specifies that a message should be received by all stations instead of just one. Extend your MAC layer implementation to handle broadcasts properly: When a frame arrvies with a broadcast address, retrieve it and process it as though it were addressed specifically to you. Since you return the destination address in the call to MAC_Recv, the user can determine if the data was part of a broadcast or point-to-point message. In our implementation we'll ignore the sequence number carried in broadcast frames.

When we implement the full CSMA/CA mechanism, it will be important that the clocks on all participating Cybikos are synchronized as closely as possible. We can't just set the system clocks manually, as they are only accurate to the nearest second and we need greater precision. The only clock with sufficient precision (the built-in clock() routine) returns the number of milliseconds from the time the Cybiko was started, and we can't assume that they were all started simultaneously. What we'll do is use clock() to get a measure of time, but add to it an offset – different on each Cybiko – that attempts to bring all clocks into agreement.

Implement LocalTime() as an internal MAC-layer function. It should return a value of type clock_t, as does clock(), that represents the Cybiko's “local time” in milliseconds. We want this local time to be identical across all machines, but its actual value is otherwise unimportant. When your application starts, the local time should be initialized from get_trusted_time(). The trusted time is set each time a Cybiko uses CyberLoad to link with the application repository, and should be accurate to within a second or two across any collection of machines.

To initialize, turn the seconds and hundreds fields from get_trusted_time into the equivalent number of milliseconds and declare this to be the local time. Once initialized, LocalTime should measure time in milliseconds. Thus, in determining a LocalTime value, you'll need to rely on clock(), but add to it the offset you determined during initialization. Local times can be off by as much as several thousand milliseconds across machines, which is unacceptably large, but the approach described below will adjust the offsets on each machine to bring the local times closer together.

Actual 802.11 implementations have exactly the same problem with clock synchronization. If a network includes a base station, the base station broadcasts a timestamp that all other stations adopt. That won't work for ad-hoc networks like the one we're simulating, so another approach is used: All machines try to adjust their clocks to match the host with the greatest local time. Periodically, stations broadcast a special frame called a beacon that contains a copy of the local time. When a beacon frame arrives, if it contains a local time greater than our own, we adjust our clock offset to synchronize with the time specified in the beacon.

Because of delays in transmission and reception, the timestamp carried by a beacon frame would already be out of date if we didn't take the delays into account. Instead of just sending the result of LocalTime(), hosts add in an amount equal to the delay between building a frame and finishing its transmission. On the receiving side, an additional adjustment is made to compensate for the time it takes to process the incoming data. You should add in 1950ms on the sending side (call this TX_DELAY), and another 250 on the receiving side (call this RX_DELAY) in your implementation.

Beacon frames need to be sent periodically to ensure that all hosts have agreed upon the largest timestamp, and so that new hosts can quickly synchronize with the rest of the group. You must send a beacon every 20 seconds, even if outgoing data is waiting in the queue. If necessary, postpone the processing of the lead data frame and use the standard access rules to send the beacon instead. Given your current implementation, that means wait until the channel is clear and then send. Once you've finished the CSMA/CA mechanism, it will be used to manage the transmission of beacon frames (and all others).

You must also send a beacon as part of the initialization process, and whenever the Del key is pressed. In both of these cases, you can simply place the beacon frame in the outgoing queue. If there's no room in the queue, you can choose to ignore the request to send a beacon. (This is only true when responding to the Del key. As stated in the previous paragraph, when the 20-second interval rolls around, you must send a beacon even if the queue is full.) Also, since beacon frames are not acknowledged, you can remove them from the queue as soon as they've been sent.

One easy way to get a sense of how well a group of Cybikos is synchronized is to have them beep at two-second intervals. It will be reassuring during the next implementation phase to know that the clocks are synchronized, so you should implement this functionality now. This beeping feature should be disabled initially, but its status should toggle on and off each time you press the Ins key. When it's on, watch the value of LocalTime() during calls to MAC_Service and beep if it's within 100ms of being evenly divisible by 2000. (Use beep(BEEP_OK); to do the beeping.)

As currently implemented, you're sending back an ACK immediately upon receipt of a valid data frame. The 802.11 specification says that we should wait an amount of time designated SIFS before returning an ACK. (This allows the channel to go idle briefly so that other stations know the data frame has finished.) We'll define SIFS to be 200ms, and you should wait this long now before sending back an ACK.

In your current implementations, data frames are discarded from the outgoing queue as soon as they've been transmitted. You must now make this slightly more realistic and wait either for an acknowledgement, or for enough time to elapse that you declare the ACK missing. (You're not required to retransmit at this point – just notice that the ACK is overdue and discard the frame.) Record the local time once you've finished transmitting the frame. We know that there will be a delay at the destination before the data frame is processed (RX_DELAY), a wait of size SIFS, a delay while the ACK is transmitted (TX_DELAY), and a delay while the data is discovered on our end (another RX_DELAY). The 802.11 specification requires that we wait an additional two slot times just to be sure. (We'll define a slot to be 250ms.) Using these values, we can compute the local time value at which the ACK is declared overdue.

Finally, to make testing easier, you will modify main.c so that it no longer requires that you use a dialog box to identify the destination each time you send a data frame. Instead, at startup, it will locate all neighbors and map their names to the number keys on the keyboard, printing the assignments to the screen as it goes. You should perform this mapping again each time the Tab key is pressed, in case we missed somebody the first time around. (The AddrToName routine in main.c illustrates everything you'll need to know to do the mapping.) When a number key is pressed, the fixed-size string is sent to the appropriate destination. (The zero key should broadcast to all destinations.) In my code, if you hold down shift and press a number, you can specify the string to send instead of getting “hello wireless world!”.


Brad Richards 2002

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