Subject: Does 802.11b do multi-hop well?

From: Phillip Neumiller <[email-masked]>
Date: Thu, 8 Nov 2001 09:25:16 -0500

Hi,

In the June 2001 IEEE Communications Magazine, 802.11 is berated for
extremely poor performance as a multi-hop MAC.  Has anybody got any
further evidence to either corroborate or show counter examples to 
the claims that are made.  These claims are:

1).  It is pointed out that 802.11 still has the hidden node problem
     when configured as a multi-hop network.

2).  The exposed node problem is not handled at all by the 802.11 MAC.

3).  Carrier Sensing as used in 802.11 is bad since the sensing and
     interference range is greater than the effective communication 
     range.

4).  The binary exponential back off always favors the latest successful
     node leading to severe unfairness.

From my limited testing and simulation I can corroborate each of these
except 1.

Any anecdotal information is welcome.  I feel this discussion is important
to the MANET list since many researchers use various forms of 802.11 in
their tests beds.

Thanks,

Phil

--
Mesh Networks, Inc. (www.meshnetworks.com)
Phillip D. Neumiller, Staff Scientist
[email-masked] PH: 1-407-659-5387
****************************************************************************
This e-mail is intended only for the addressee named above and may contain
confidential, proprietary or privileged information. If you are not the
named addressee or the person responsible for delivering the message to the
named addressee, please inform us promptly by reply e-mail, then delete the
e-mail and destroy any printed copy. The contents should not be disclosed to
anyone and no copies should be made. We take reasonable precautions to
ensure that our emails are virus free. However we accept no responsibility
for any virus transmitted by us and recommend that you subject any incoming
e-mail to your own virus checking procedures.

---

From: Jose Garcia-Luna <[email-masked]>
Date: Thu, 08 Nov 2001 11:10:15 -0800

Yes, it has been shown that 802.11 is not 
an effective channel access method for multihop networks.
A problem is that the collision avoidance exchange does not work
with hidden terminals.  That should not be a surprise. 

One added problem is the inability to support multipoint communication
efficiently, which happens to be a need for minor things that must go
on in multihop radio nets, like routing :)))

Pointers to old work:

J.J. Garcia-Luna-Aceves and C. Fullmer, "Floor Acquisition Multiple
Access (FAMA) in Single-Channel Wireless Networks", ACM Mobile
Networks and Applications Journal, Special Issue on Ad-Hoc Networks,
Vol. 4, 1999, pp. 157-174.

J.J. Garcia-Luna-Aceves and C. Fullmer, "Performance of Floor
Acquisition Multiple Access in Ad-Hoc Networks", Proc. Third IEEE
Symposium on Computers and Communications (ISCC'98), Athens, Greece,
June 30-July 2, 1998.
http://www.soe.ucsc.edu/research/ccrg/publications/chane.iscc98.pdf

JJ

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 9 Nov 2001 11:13:02 +0100

BEB is also known to provide unfairness in overloaded networks. This was
established for wired Ethernet. One remedy is to prevent the number of
packet retry in the MAC to be less than half a dozen instead of 16. But in
this case the evasion against hidden nodes is unsufficient. Therefore
RTS/CTS + short retry number may be the best solution.

By the way, if unfairness can be avoided in wired network, it may be
unavoidable in wireless network where some nodes are more exposed than
other, because of their location or fading conditions. Amir Qayyum has shown
in his PhD thesis that BEB significantly amplifies the unfairnesses due to
location and fadings. In every case HIPERLAN 1 MAC was doing better.

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 9 Nov 2001 10:59:53 +0100

Yes, in our old times we have criticised some feature of IEEE 802.11 which
was not well adapted (and not only with regard to multihop). We had promoted
some remedies in the HIPERLAN 1 standard (which was intended to be a true
multihop MAC design).

1. In particular it was known that BEB does not handle well against hidden
nodes. When RTS/CTS fails, the best to do is to switch CSMA with short
backoff to an ALOHA with longer backoff. In HIPERLAN we introduced such
feature. When a collision was detected then the MAC turned to ALOHA for
certain time. Of course ALOHA performs less than CSMA but it is better than
a permanent deadlock due to hidden nodes.

2. Another IEEE 802.11 annoying  feature is the fixed carrier sense level
that may lead to exposed node deadlock. In HIPERLAN 1 the carrier sense
level was adaptable. The rule was that the carrier sense level automatically
fits to the minimal energy level detected during a certain window of time.
So that an exposed node cannot be prevented to transmit for ever. In other
words,  the more noise you have around, the deafer is the HIPERLAN node, so
it is not prevented to speak.  This is more a less how we all communicate
during IETF parties ;-)

Some ads about old works:

Philippe Jacquet, Pascale Minet, Paul Muhlethaler, Nicolas Rivierre,
"Priority and Collision Detection with active Signaling: The Channel Access
Mechanism of HIPERLAN," in Wireless Personal Communications Vol 4, No 1, pp.
11-25, 1997.

Philippe Jacquet, Pascale Minet, Paul Muhlethaler, Nicolas Rivierre,
"Increasing reliability in cable-free Radio LANs: Low level forwarding in
HIPERLAN," in Wireless Personal Communications Vol 4, No 1, pp. 51-63, 1997.

Philippe Jacquet, Pascale Minet, Paul Muhlethaler, Nicolas Rivierre, "Data
transfer in HIPERLAN," in Wireless Personal Communications Vol 4, No 1, pp.
65-80, 1997.

Philippe

---

From: Leonard Miller <[email-masked]>
Date: Fri, 09 Nov 2001 10:07:59 -0500

It is natural for a receiver's detection range to be greater than its
demodulation range, hence the exposed terminal problem that is made so
much of in the article you mention.  If the exposed terminal could "get
a word in edgewise" the disparity in these ranges would not be such a
factor because the situation would be reciprocal.  However, an
"unfairness" to exposed terminals arises due to a kind of capture of the
contention channel: the BEB scheme backoff favors successful
transmitters by immediately resetting their contention windows to the
minimum value.  In our group at NIST we are studying alternative backoff
schemes that should be more fair because the contention window size in
the alternative schemes is not immediately reset to the minimum value
after a node's transmission is successful.
	The 802.11 WLAN contention scheme is analyzed by Giuseppe Bianchi in an
article in the March 2000 issue of JSAC.  In a PIMRC '96 paper, he also
analyzes an adaptive contention window size for maximizing WLAN
performance based on estimating the number of users; this does not
address the multihop issue directly, but perhaps the good congestion
control exercised by the adaptive scheme would carry over to the
multihop scenario. 
	The situation with 802.11 is actually more complicated in that a node
that does not win the contention, because it randomly selected a larger
backoff value than some other node, does not reset its timer but
suspends the countdown until the next contention period.

--Len Miller

-- 

._.. . _.   __ .. ._.. ._.. . ._.   ._ _   _. .. ... _

Leonard E. Miller, Wireless Commun. Technologies Group
    National Institute of Standards & Technology (NIST)
    100 Bureau Drive Stop 8920, Bldg. 820, Room 445
    Gaithersburg, Maryland 20899-8920
Phone: 301-975-8018        Fax: 301-590-0932
email: [email-masked], [email-masked]
http://w3.antd.nist.gov/wctg/
._ _. ._ ._.. _.__ ... .. ...   ._ _. _..  ... .. __ .._
.._. ._ _ .. ___ _. ___...   .__ .. ._. . ._.. . ... ...

---

From: Vikas Kawadia <[email-masked]>
Date: Mon, 12 Nov 2001 14:15:23 -0600 (CST)

We have done experiments on a testbed of laptops inside buildings and
using 802.11 bases wireless cards. The results are summarized in this paper.

 "Piyush Gupta, Robert Gray and P. R. Kumar, 
``An Experimental Scaling Law for Ad Hoc Networks.'' 
on my website at
http://black.csl.uiuc.edu/~prkumar/postscript_files.html#Wireless Networks?

One of the siginificant difficulties in setting up a true multi-hop
network was the greater sensing range of the cards comapred to their
communication range. Thus when you set up a multihop network, you still do
not get benefits of spatial reuse and pay the penalty of relaying.

If somebody knows how to turn off carrier sensing on any of the commercial
802.11 cards, that would be very useful information.

Thanks.
Vikas Kawadia

------------- Begin Forwarded Message -------------

From: Phillip Neumiller <[email-masked]>
To: [email-masked]
Subject: Does 802.11b  do multi-hop well?
Date: Thu, 8 Nov 2001 09:25:16 -0500 
MIME-Version: 1.0

Hi,

Thanks,

Phil

---

From: Chip Elliott <[email-masked]>
Date: Tue, 13 Nov 2001 09:20:35 -0500

I think this is one of the most interesting papers I've seen
in quite a while, and a very good companion piece to the earlier
paper on theoretical limits to multihop throughput.

Just my two cents, but it's a paper well worth reading for
all MANET fans.

The SURAN folks in the 80s showed that you had to
divide the nominal channel bandwidth by at least 3 just to account
for multihop relay, but this paper shows that a "2 mbps"
802.11 card might in reality deliver something like 100 Kbps
(given specific scenarios of laydowns & traffic flows).

Bravo and many thanks to the authors!

-- Chip

---

From: Dominique Dhoutaut <[email-masked]>
Date: Tue, 13 Nov 2001 18:38:45 +0100

Hi

I'm a PhD student, and I actually work on those problems with 802.11
when used for multi-hop ad-hoc networks.
I already have a small amount of studies and simulation results, and I
will release them completely very soon (I hope).

What I would like to add to this discussion thread is that I strongly
think one could obtain quite reasonable results by only acting on the
backoff scheme of 802.11.

I have run a lot of simulations under NS2, using both UDP and TCP. Most
of my scenarios were based on one "normal" traffic (say a string of
nodes, relaying packets from one extremity of the string to the other)
perturbed by a wandering pair of node.
The two nodes of the pair are wandering together through the field, one
of them sending data to the other.
In almost all cases, as the perturbing pair is configured to try to send
as much data as possible, the "multi-hop traffic" is completely stopped,
until the pair is far enought again.

In my mind, this kind of scenario modelize some realistic situations
(imagine someone transfering datas to a friend of him passing nearby a
group of nodes involved in a multi-hop communication).

After those simulations, I tried different techniques. What was working
the best, was to penalyse nodes which were sending packets at a too high
rate and thus completely blocking some others. The main idea was to
artificially increment the backoff, depending on the number of packet
sent over the air during a fixed amount of time. The time is then
divided in cycles, the penalty added to the backoffs beeing reseted at
the begining of each cycle.

Of course, using this technique, the maximum throughput between two
nodes is reduced (of 10 to 20%). But the total bandwith in the network
is not. And it appeared that parameters (essentialy the progressing law
of the penalty and the cycle length), were easy to tune in order to
achieve a quite reasonnable equity between all communications in the
network. Moreover, I added a trivial test, allowing all paquets related
to the routing protocol (AODV or DSR in my simulations) to be sent with
no penalty. And this seems to sometime greatly improve the overall
results, by drasticaly reducing the links lost rate (as for exemple
"hello" packet are no more losts).

Of course, this work is in progress. But feel free to ask any question
you may have.

Dominique

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 14 Nov 2001 11:15:20 +0100

We arrived to the same conclusions. There are two carrier sense thresholds
on the cards (dense or sparse threshold).  Paul Muhlethaler has conducted
several experiments. He will probably tell more when he will be able to
reach the mailing list.

An alternative solution could be to adapt the transmission power (i.e to
reduce power when density increases). But power is not tunable on IEEE
802.11 cards.

Philippe

---

From: Vikas Kawadia <[email-masked]>
Date: Thu, 15 Nov 2001 12:22:09 -0600 (CST)

> reduce power when density increases). But power is not tunable on IEEE

The power IS tunable on the some of the 802.11 cards. We use CISCO Aironet
350 cards in our testbed and they have 6 adjustible power levels : 1, 5,
20, 30, 50 and 100mW. The hardware seems capable of per packet power
control but the firmware on the card does not seem to support that. 

We have developed a power control protocol for Ad hoc networks and
implemented it in the Linux kernel. We have also carried out some
experiments in the testbed we have here. 

Links to papers :
http://black1.csl.uiuc.edu/~prkumar/postscript_files.html#Wireless%20Networks
http://www.uiuc.edu/~kawadia/acads.html

..vikas

> > to the MANET list since many researchers use various forms of 802.11 in

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
                          Vikas Kawadia
                          -------------
                    http://www.uiuc.edu/~kawadia
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-