CS 395 Project Checkpoint #2

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

• Buffering Multiple Frames
• Address Selectivity
• Sequence Numbers
• Control Information
• Channel Sensing
• Acknowledgements

In your current implementation, you store only the data frame that has arrived most recently. For this checkpoint, you must add a fixed-size buffering mechanism that holds the contents of at most four incoming data frames. (The size limit should be a constant so that the value can be easily changed.) Once the buffer is full (four frames have arrived but not yet been passed to the layer above), you must discard incoming data instead of overwriting current entries. A separate four-frame buffer should be used to hold outgoing data frames. It will buffer frames that cannot be sent immediately due to the channel being in use. (See below.)

For the previous checkpoint, your implementation passed all incoming data to the layer above. For this checkpoint, you'll start sending and inspecting destination addresses. The layer above specifies a destination address in the call to MAC_Send(), so all you need to do on the sending side is copy this address into the outgoing frame before broadcasting. On the receiving side, inspect the address when data arrives and only process it if it's addressed specifically to you. You'll have to copy the partner-selection code from your sleep server assignment into main.c to select a destination (or come up with some other clever way to come up with a destination address).

You must start using sequence numbers for this checkpoint. Each host will record which sequence numbers have been used on outgoing data frames, for each possible destination. (All sequence numbers start at zero.) For example, assume that a particular host has sent 10 frames to machine A and 7 to machine B. The frames to A contained sequence numbers 0 through 9, and those to B carried 0 through 6. Thus, the next transmission to B should use sequence number 7 regardless of whether additional frames are first sent to A.

On the receiving side, you should compare incoming sequence numbers to the expected values. If a frame arrives with a sequence number smaller than expected, it must be a retransmission and you should avoid passing it to the layer above. (You must still acknowledge the data frame, as discussed below, however.) When the expected frame arrives, it should be buffered if possible, and announced to the layer above. Only rarely should a frame arrive with a sequence number greater than expected. This implies that the sender tried repeatedly to send a frame with the missing sequence number, but eventually gave up. A subsequent transmission may use a new sequence number. If this case arises, you should reset the expected sequence number to be one larger than that of the frame just received.

All fields in the “control” header field must be set to appropriate values. The sequence numbers, discussed above, take up the lower 12 bits of this field. The upper three bits must be set to the appropriate frame type which, for now, will only be DATA or ACK. The retransmission flag must also be set appropriately. For this checkpoint, there will be no retransmissions, so the flag should always be zero.

We'll stop far short of implementing the full CSMA/CA mechanism for this checkpoint, but we'll take the first step: If the channel is in use when MAC_Send() is called, postpone the transmission of the frame. You should still return normally from MAC_Send() and report the appropriate number of bytes as being sent, but the frame you build will be copied into your outgoing frame buffer instead of immediately transmitted. In MAC_Service() you should check for any frames awaiting transmission and try again to send them. (You are welcome to put all outgoing data into the frame buffer first, and let it be sent at the next call to MAC_Send(), instead of trying to transmit it immediately.) As soon as a frame has been transmitted, its slot in the buffer can be made available to a new frame.

In the full implementation, the frames in the outgoing buffer could be in a variety of states (never been sent, sent but awaiting ACK, backed off and counting down, etc). You may therefore wish to associate an enumerated type value with each frame that records its state, though for now it isn't necessary – the only reason a frame would be in the buffer is that it has never been sent.

We won't implement full reliability for this checkpoint, but again we'll take the first step. When a data frame arrives, you must build an acknowledgement frame and return it immediately to the sender. (Don't bother looking to see if the channel is in use – in the full implementation the ACK will have precedence over other traffic so it won't be an issue.) An ACK frame should have its type field set properly, should be addressed to the data frame's sender, and should carry the sequence number of the data frame being acknowledged. No additional data should be transmitted. For this checkpoint, arriving ACKs can be ignored. The data frame to which they correspond is no longer in your outgoing buffer, so there's no way to match them to previously-sent data in any case. We'll clean this up in the next checkpoint. Acknowledgements should not be placed in the outgoing frame buffer first, and should be sent even if the outgoing frame buffer is full.

A zipped copy of my solution is here.

Brad Richards 2002