\documentclass[twocolumn]{article}

\usepackage{graphicx}

\begin{document}

\title{Improving 802.11 Range with Forward Error Correction}

\author{Reina E. Riemann, Keith J. Winstein}

\date{\small\emph{\{riemann,keithw\}@mit.edu}\\
Computer Science and Artificial Intelligence Laboratory,
Massachussets Institute of Technology}

\maketitle

\begin{abstract}
The ISO/IEC 8802-11:1999(E) specification\footnote{ANSI/IEEE Std
  802.11, 1999 edition.} uses a 32-bit CRC for error detection and
whole-packet retransmissions for recovery. In long-distance or
high-interference links where the probability of a bit error is high,
this strategy results in excessive losses, because any erroneous bit
causes an entire packet to be discarded. By ignoring the CRC and
adding redundancy to 802.11 payloads in software, we achieved
substantially reduced loss rates on indoor and outdoor long-distance
links and extended line-of-sight range outdoors by 70 percent.
\end{abstract}

\section{Introduction}

Bit errors are a rare phenomenon in most wired local area
networks. Wired Ethernet\footnote{Formally, ISO/IEC 8802-3:2000(E) or
IEEE Std 802.3, 2000 edition.} rarely operates close to the noise
threshold --- link distances are limited by restrictions on delay, not
by signal power. See Figure \ref{fig:ipping}. As such, the cause of
misbehavior in wired Ethernet is typically congestion, not noise, and
the type of error usually manifested is the loss of an entire packet,
not a flipped bit.

\begin{figure}
\begin{centering}
\includegraphics[scale=.6]{ipping.eps}

\end{centering}
\caption{An example 802.3 waveform at 10 Mbit/sec (the sequence number
  ``212'' in an ICMP ping packet). Up-transitions in the middle of bit
  intervals indicate ones, down-transitions zeros. Note the almost
  complete lack of noise.}
\label{fig:ipping}
\end{figure}

Wireless networks are different. The range of a 32 mW 802.11 base
station indoors is only a few tens of feet before bit errors begin to
appear. Outdoors, there is much interest in stretching 802.11 links as
far as possible, including MIT's own Roofnet
project\footnote{\texttt{http://www.pdos.lcs.mit.edu/roofnet/}} to
build a citywide 802.11 mesh network in Cambridge, Massachusetts.

\begin{figure}
\begin{centering}
\includegraphics[scale=.25, angle=-90]{802err.ps}

\end{centering}
\caption{An example 802.11 packet at 1 Mbit/sec, received over a
  0.55-mile outdoor line-of-sight link. This packet has 90 octets
  received incorrectly (indicated with \texttt{*}) out of 1,392.}
\label{fig:802err}
\end{figure}

The causes of misbehavior on an 802.11 link thus include, in addition
to congestion, low signal-to-noise ratio and interference. These
latter two produce incorrectly received bits, causing a failed CRC, a
lack of acknowledgement, and the sender's retransmitting the entire
packet. (Low signal-to-noise and interference can also cause a
receiver not to hear the sender's preamble and miss the packet
entirely.)

Figure \ref{fig:802err} shows an example 802.11 payload after
transmission 2,900 feet along an outdoor line-of-sight link. The
payload was 1,392 octets, of which 1,301 were received correctly and
90 incorrectly (indicated with \texttt{*}). At this error rate, most
802.11 senders will give up on retransmissions before the receiver is
able to receive an entire packet correctly.

With some fraction of each packet devoted to forward error correction,
the receiver can recover from bit errors. By adding redundancy to each
packet in software --- essentially, increasing the noise margin of the
transmission path by reducing throughput --- we were able to extend
the outdoor range of 802.11 by up to 70 percent, from 0.5 miles to
0.85 miles.

\section{Related Work}

Many papers have presented strategies to improve the performance of
reliable transports, such as TCP, over wireless networks. In
\cite{balakrishnan97comparison}, Balakrishnan \emph{et al.} compare
and analyze several techniques for improving TCP throughput over a
precursor to 802.11, including modifications to TCP endpoints such as
selective acknowledgements, and making the link-layer protocol
reliable and ``TCP-aware,'' with immediate retransmission of lost
packets. The authors were not able to obtain the contents of errored
frames\footnote{Balakrishnan, personal communication, November 2003.}
and did not analyze forward error correction in this context.

Khayam \emph{at al.} (\cite{802.11b}) measured the error
characteristics of two indoor one-way 802.11 links across a hallway at
2, 5.5, and 11 Mbits/sec. Because their links were one-way (for
multicast video broadcast), they used forward error correction to
recover from dropped packets as well as bit errors.\footnote{When a
two-way connection is available and latency is not important, forward
error correction is not useful for dealing with dropped packets. The
ideal strategy is acknowledgement and retransmission of the dropped
packet, because the redundantly-transmitted information is exactly
what was lost.} The authors found that, for these two links operating
at 5.5 Mbits/sec, giving the application layer access to frames
received with bit errors reduced by about 40 percent the amount of
redundant information necessary to achieve perfect transmission. At 11
Mbits/sec, there was no advantage to looking at frames received with
bit errors, because the vast majority of errors were long strings of
dropped packets, not frames received with bit errors. Their two links
had almost no dropped packets or errored octets at 2 Mbits/sec. The
Khayam authors did not try to extend 802.11's range or discuss two-way
connections.

\section{Measurements}

In order to design a reasonable error-correction strategy for 802.11
packets with bit errors, we sought to observe the error
characteristics of several indoor and outdoor
environments. Unfortunately, most consumer 802.11 implementations do
not advertise an interface that allows the host to receive frames with
failed CRC. To our knowledge, only cards based on the
Intersil\footnote{Now sold by GlobespanVirata, Inc.} Prism 2/2.5/3
chipset have a publicly known method to access errored frames.

We modified the GNU/Linux Host AP driver\footnote{By Jouni
  Malinen. \texttt{http://hostap.epitest.fi/}.} for these cards to
  ignore the card's report of a failed CRC and put the card in
  ``\texttt{HFA384X\_RID\_PROMISCUOUSMODE}.'' These two changes were
  necessary to receive errored frames outside of the card's ``monitor
  mode.''

Because our goal is to improve 802.11's range, we conducted all
measurements at 1 Mbit/sec, the slowest and most noise-resilient
802.11 modulation. We set up a laptop with a 32 mW Lucent Orinoco card
on top of MIT's Green Building, about 310 feet above ground level. The
laptop transmitted 1,400-byte ICMP ping packets to the Ethernet
broadcast address. We wanted there to be no link-layer
retransmissions, because they don't make sense when we are trying to
salvage errored frames: the sender will keep trying to retransmit
until the receiver gets the frame perfectly. This is not what we want.

We attempted to receive the pings at various distances with a Prism 2
card in another laptop, using a Global Positioning System receiver to
mark our location. The links we tested were line-of-sight over the
Charles River, which separates Boston and Cambridge.

We made three measurements: (1) \emph{How far is a line-of-sight
  outdoor link functional without receiving bit errors?} (2) \emph{How
  far out can a line-of-sight outdoor link consistently receive
  packets, with or without bit errors?} and (3) \emph{What is the
  distribution of bit errors per packet on an example long-distance
  link?}\footnote{We acknowledge that these definitions are
  subjective, and should not substitute for rigorous link-quality
  statistics. How many successful transmissions must a link receive
  to be ``functional''?  What percentage of packets must be received
  before we can say our link does so ``consistently''?}

The difference between (2) and (1) is essentially the ``marginal
zone'': the increase in range we expect to receive by using forward
error correction.

We made measurement (3) by taking just over three minutes of data on
the Boston bank of the river, 0.55 miles away from the
transmitter. See Figure \ref{fig:link}.

\begin{figure}
\begin{centering}
\includegraphics[scale=.3]{link.eps}

\end{centering}
\caption{The 0.55-mile marginal link across the Charles
  River. Courtesy MassGIS and the MIT Department of Urban Studies and
  Planning.}
\label{fig:link}
\end{figure}

\section{Results}

The distance in measurement (1) --- the maximum distance for
zero-error reception --- was 0.50 miles.\footnote{More rigorous
measurements are needed here, along with signal strength. The zone of
perfect reception dropped out conclusively at 0.50 miles, but seemed
to reappear briefly at one spot 0.70 miles away. Was this the result
of a coherence of lucky bounces, a low-noise spot, or what?
Unfortunately, the Prism 2 card does not produce any measurement of
signal strength at these long distances.} The distance in measurement
(2) --- the maximum distance at which we could get packets at all ---
was 0.87 miles.

The ``marginal zone'' is about 0.37 miles, or a 70 percent increase in
distance if we can recover from received bit errors.

\begin{figure}
\begin{centering}
\includegraphics[scale=.33, angle=-90]{br3graph2.ps}

\end{centering}
\caption{Fraction of packets lost versus error tolerance on
  the 0.55-mile one-way link. Note log-log scale.}
\label{fig:br3}
\end{figure}

The measurements on the 0.55-mile link were as follows:

\begin{enumerate}
\item 195 pings were transmitted, each with a 1,392-byte known payload.

\item 23 packets, or 12 percent of those sent, were lost entirely.

\item 63 received packets, or 32 percent of those sent, were received
perfectly.

\item 10 received packets, or 5 percent of those sent, had 192 or more
octets incorrect.

\item The remaining 99 packets, or 51 percent of those sent, had
between 0 and 192 octets incorrect.

\end{enumerate}

Figure \ref{fig:br3} presents these data in graphical form: the
fraction of packets with more than a given number of octets
incorrect. Normal 802.11, which can only make use of
perfectly-received packets, is at the left-hand side of the graph ---
a loss rate of 100 - 32 = 68 percent.\footnote{Note that most 802.11
implementations retransmit four times, so for non-broadcast traffic
the loss rate that normal 802.11 users would experience in practice is
closer to $0.68^4 = 0.21$.} If we can salvage packets with up to 192
incorrect octets, we would instead have a loss rate of 100 - (32 + 51)
= 17 percent.\footnote{Why all the talk of incorrect octets, instead
of bit errors? 802.11 at 1 Mbit/sec uses differential binary phase
shift keying (DBPSK), where each bit gets its own modulated symbol, so
there does not seem to be a theoretical reason to expect errors to
come in octets. Nevertheless, the errors we observe in practice
generally corrupt a whole octet or a string of octets, not just
scattered bits. See Figure \ref{fig:802err}.}

These results --- a 70 percent increase in distance, a 75 percent
decrease in packet loss rate --- convince us that adding redundancy so
that the receiver can salvage errored packets can be a useful
software-only addition to 802.11.

\section{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.

\begin{figure}
\begin{centering}
\includegraphics[scale=.4, angle=90]{structure2.ps}

\end{centering}
\caption{Structure of rs-link implementation, including a planned
  addition: feedback as to the appropriate amount of redundancy to
  add.}
\label{fig:structure}
\end{figure}

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.\footnote{We have to increase the MTU of the wireless card to
  this number, from the default of 1,500 bytes.}

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.\footnote{We leave the Ethernet header unscrambled so the card
knows we are sending to the broadcast address and turns off link-layer
retransmissions.} 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.)

\section{Tests}

We tested the rs-link software indoors, on a link through several
walls, between two laptops with Prism 2 cards. The link distance was
picked to be in the ``marginal zone'' where each station could receive
packets from the other, but with errors.\footnote{Most transmission
problems were in one direction, because one card, the ``access
point,'' was operating at 200 mW and the other at 32 mW.}

Unlike the measurements in Figure \ref{fig:br3}, this was a two-way
test over our error-corrected link. One laptop sent 105 ICMP ping
queries to the Ethernet broadcast address and tallied the responses.

The measurements were as follows:

\begin{enumerate}
\item 105 pings were transmitted, each with a 1,146 known contents.

\item 31 pings, or 30 percent of those transmitted, did not receive
  a response.

\item 8 pings, or 8 percent of those transmitted, received a perfect
response.

\item 10 pings, or 10 percent of those sent, received a response that
  the rs-link decoder could not salvage (i.e., more than 192 octets
  incorrect).

\item The remaining 66 pings, or 63 percent of those sent, received a
  an errored response that the rs-link decoder was able to salvage.

\end{enumerate}

These data are presented graphically in Figure \ref{fig:indoors}. Our
two-way loss rate is at the right-hand side of the figure --- 192
errored octets permitted. The two-way loss rate for normal 802.11
(without link-layer retransmissions) is at the left-hand side of the
figure -- no errored octets permitted.

\begin{figure}
\begin{centering}
\includegraphics[scale=.33, angle=-90]{indoors.ps}

\end{centering}
\caption{Fraction of two-way pings lost as a function of octet error
tolerance, in a 1,530-byte ping response. Note log-log scale.}
\label{fig:indoors}
\end{figure}

The CPU load is tolerable on modern PCs. A 200 MHz Pentium Pro is just
able to saturate a 1 Mbit/sec link using all its processing power. A 2
GHz Pentium 4 has no trouble.

\section{Conclusions and Extensions}

By adding redundancy to transmitted 802.11 frames in software, we were
able to extend the range of an outdoor line-of-sight link by 70
percent, or 0.37 miles, and reduce losses significantly on marginal
indoor and outdoor links. But without link retransmissions for packets
that fail error correction, users will still have difficulty making
productive use of a marginal link, even with error coding. To be
more usable, we will need to examine:

\emph{Retransmissions after error correction.} To be able to use TCP
over a marginal link, users of rs-link will have to duplicate the
functionality of link-layer retransmissions at a higher level, after
error correction. A loss rate of 17 percent, while certainly better
than 68 percent, is still not good enough to run TCP. One way to add
link-layer retransmissions above the error-correction layer is by
using the LL-SMART-TCP-AWARE protocol described in
\cite{balakrishnan97comparison}. Under LL-SMART-TCP-AWARE (or the
simpler ``snoop'' protocol also discussed), link endpoints cache TCP
segments as they cross the link, suppress duplicate acknowledgements,
and retransmit segments that appear to have failed.

\emph{Error feedback.} As implemented, rs-link uses 34 percent of the
802.11 link bandwidth for redundancy information. This is worth it if
the result is a 75 percent reduction in loss rate, as in the case of
our 0.55-mile link. But it's not worth it for a less-marginal
link. rs-link should receive feedback on the amount of observed errors
from the receiver and adjust the level of added redundancy as
appropriate.

\emph{Why are Roofnet's results different?} Preliminary efforts by the
Roofnet group to record and salvage errored frames at 1 Mbit/sec have
given disappointing results --- errored frames end up completely
corrupted. Why are their results so different from ours? Are urban
links with multipath fundamentally different from the line-of-sight
outdoor and through-walls indoor links we have examined?

\section{Acknowledgments}

The authors are deeply indebted to Austin Roach and Sanjit Biswas for
lending equipment and much time to help us throughout this
project. Phil Karn's free-software Reed Solomon library was very
helpful, and we appreciate the assistance of Professor Hari
Balakrishnan, Daniel Aguayo, John Barnett, Waseem Daher, Allie
Brownell, Marissa Cheng, John Hawkinson, and the MIT Radio Society.

\bibliographystyle{plain}
\bibliography{paper}

\end{document}
