Implementation

We have implemented an AFF-based packet fragmentation service for use with low-power, short-range wireless radios. Our implementation was born out of a necessity to send large virtual packets over radios with a very small (27 byte) frame size, but it also served as an important proof of concept for AFF and a validation of the analytic model presented in Section 4.

Our current testbed consists of Radiometrix RPC 418 MHz radio modules⁵ attached to Toshiba Libretto laptops running the RedHat Linux operating system. The RPC is our radio of choice because of its low power requirements, ease of use, and small form factor. A simple packet controller on the radio accepts frames of up to 27 bytes from the host and attempts to broadcast each frame to all other RPC modules within receiving range. Any RPC in the area that successfully receives the frame transfers it back up to its host.

Our fragmentation driver accepts packets of up to 64Kbytes from applications, fragments them to fit into 27 byte frames, and sends them down to the RPC for transmission. It also watches for fragments coming in from the radio, reassembles them, and delivers successfully reconstructed packets to the host.

The fragmentation algorithm itself is simple, based on IP fragmentation. Each packet is given a random AFF identifier. A ``packet introduction'' fragment is transmitted first, containing the packet's AFF identifier, total length, and checksum. Each fragment is then transmitted with the packet's AFF identifier and the byte offset of the data it carries. The driver on the receiver reassembles fragments as they are received and delivers packets to the application when the checksum succeeds. Packets that suffer from identifier collisions are never delivered because of checksum failures or other inconsistencies.

Experiments

We created a specially instrumented version of our fragmentation driver in an attempt to validate our model of predicted collision rates given in Equation 4. In the instrumented driver, each node has a globally unique identifier; the fragment format is augmented to include this identifier along with the randomly selected AFF identifier. By examining both the AFF identifier and the guaranteed unique node identifier of received fragments, the receiver's driver is able to determine how many packets would have been lost due to AFF identifier collisions if the unique ID had not been present.

Our experimental testbed consisted of five radio transmitters simultaneously sending packets to a single wireless receiver. We tested this configuration over a range of AFF identifier sizes. Ten trials were executed for each identifier size. In each trial, each of the five transmitters attempted to transmit a continuous stream of random 80-byte packets for two minutes; each of these packets were fragmented into five fragments (a single fragment introduction and four data fragments). After attempting to reassemble all received fragments, the receiver reported the total number of packets successfully received using the packet's unique identifiers and the number that would have been received based on the AFF identifier alone.

We also tested the efficacy of a simple listening heuristic to reduce identifier collisions. In the listening mode, each transmitter also acts as a receiver, listening to packets transmitted by other nodes. When selecting an AFF identifier for outgoing packets, transmitters did not use identifiers they had recently heard in use by other transmitters. The choice of identifier was picked uniformly from pool of not-recently-used identifiers. We adaptively define ``recently'' as within the most recent $2T$ transactions; each node can estimate $T$ based on the number of concurrent transactions it observes. All of the transmitters and receivers were arranged so that they were fully connected (i.e., all the radios were well in range of each other).

The results of these experiments is shown in Figure 4 along with our model's prediction (for $T=5$). As evident in the figure, our collision model appears to be accurate. The simple listening algorithm also appeared to be very effective in reducing identifier collisions.

Figure 4: Collision rate predicted by our model vs. observed in our implementation. We tested one algorithm that selects identifiers randomly and one that avoids collisions by listening to other nodes' transmissions. The error bars represent the standard deviation from the mean for each trial.