Implementation

Under GNU/Linux, we implemented an ``RSenc'' device that encodes outgoing packets by adding redundancy, and corrects errors in incoming packets. The implementation in user space, with the Linux TUN/TAP (user space network devices) module.

Figure 5: Structure of rs-link implementation, including a planned addition: feedback as to the appropriate amount of redundancy to add.

We use Reed-Solomon error correction at the byte level, with a transmitted codeword of 255 bytes. Of these, some are the ``message bytes'' (the input to the coder) and the rest are ``redundancy bytes.'' Every two redundancy bytes we add decreases our message capacity by two bytes, but it adds one byte of error tolerance. That is, with two redundancy bytes and 253 message bytes, any one byte in the entire 255-byte received codeword may be corrupted arbitrarily in flight, and the decoder will still be able to recover the original message bytes.

Based on our measurements of the 0.55-mile link, we chose a code that has 191 message bytes, and 64 redundancy bytes, in each 255-byte codeword (known as an $RS(255,191)$ code).

The RSenc device accepts packets of up to 1,146 bytes ($= 6 \cdot 191$). It splits them into blocks of 191 bytes and appends the 64-byte redundancy information to each block, making a codeword of 255 bytes, for a total of $6 \cdot 255 =$ 1,530 bytes in each output packet.¹²

Our measurements also indicated that errors tend to occur in bursts of several bytes. We must drop a packet if any one of its Reed-Solomon codewords has more than 32 bytes wrong, so it is to our advantage to try to spread those errors out. So before transmission, we scramble the message by interleaving each codeword in a round-robin manner.¹³ We then send each 1,530-byte encoded packet to the 802.11 card.

On receipt, we reverse the procedure: unscramble, then rectify each 255-byte Reed-Solomon codeword, extract the 191 message bytes from each, and deliver the resulting packet to the operating system.

The 802.11 card itself must be in ``ad hoc'' mode and can only communicate with other ``ad hoc'' 802.11 stations. (When the card is in ``managed'' mode, it disassociates from its access point when it starts to receive errors.)