Subject: [Fwd: Re: Does 802.11b do multi-hop well?]

From: Leonard Miller <[email-masked]>
Date: Fri, 09 Nov 2001 15:00:37 -0500

I think Rex meant to copy this to the list.

-------- Original Message --------
Subject: Re: Does 802.11b  do multi-hop well?
Date: Fri, 9 Nov 2001 10:41:10 -0800
From: Rex Buddenberg <[email-masked]>
To: Leonard Miller <[email-masked]>

interesting to see others getting to some similar thinking.

Back up another conceptual step.  802.11 adapted the basic ethernet 
CSMA/CD scheme as you described.  But it's still a contention MAC. 
Token systems don't work in this environment because they all make 
similar assumptions about neighbors hearing each other which are true 
in wired networks, but not in wireless (aka 'silent host').  The 
problem with ethernet-style contention systems is that they're not 
bandwidth-efficient.  In wired networks, this has been an acceptable 
tradeoff but in RF networks the economy changes -- trading off 
bandwidth efficiency for a computationally simple MAC is less tenable.

Does it make sense to work out some open standards (there are 
proprietary ones now in satcom systems) for a scheduling algorithm? 
We can max channel efficiency by providing small windows for hosts 
wanting into the net and keeping the successful entries out of the 
window -- they have a xmit sched and don't need it.  Perhaps the more 
relevant question is whether the industry is ready to revisit the 
subject of MACs... ???  For several years now, the answer has been 
'no' because of the dominance of ethernet and its need to fight off a 
bunch of wannabes (like ATM ... which has no MAC at all).

>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
>
>Phillip Neumiller wrote:
>>
>>  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.
>
>--
>
>._.. . _.   __ .. ._.. ._.. . ._.   ._ _   _. .. ... _
>
>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/
>._ _. ._ ._.. _.__ ... .. ...   ._ _. _..  ... .. __ .._
>.._. ._ _ .. ___ _. ___...   .__ .. ._. . ._.. . ... ...

-- 
b

---

From: Yong Kang <[email-masked]>
Date: Fri, 9 Nov 2001 13:35:32 -0800 (PST)

Rex, 
I think it's really good to point out what should we do on
Mac to make wireless network happen. 
Has anyone think that we use different Mac between wirelss LAN
and wireless WAN, base on the fact that 802.11 is popular but not
efficient for multihop traffic while wireless WAN is clean.
Just like in the internet, p2p optical NIC is used for core and
ethernet is for edge. we could model it as, scheduled Mac in wireless
core and 802.11 at wireless edge.

without a good Mac, multihop wireless network is never practical.

thanks
yong

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 14 Nov 2001 10:35:31 +0100

I don't think we can expect a significant breakthrough by using a new and
complexified scheduling algorithm (eg aka wireless token ring). The paper of
Gupta and Kumar, "The capacity of wireless networks" (IEEE trans IT) shows
upper bounds which are not far to what could be obtained with a slotted
ALOHA.

Philippe