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

From: Phillip Neumiller <[email-masked]>
Date: Mon, 12 Nov 2001 08:29:55 -0500

Yong,

I really like your thinking here, as it seems correct to me.
Obviously on the edges of the network, a random access MAC is 
required, and SOMETHING like an ad hoc improved version of 
802.11b could fit the bill.  However, when you start routing
and aggragating traffic a more efficient scheduled MAC seems
to be required.  Does anyone on the list know how we could 
bring this to the IEEE?  The reasons we need a new MAC are
the following:

A).  We need a MAC that does ad hoc networking better than 802.11
     This could be an improvement to 802.11.
B).  We need a MAC that can function both as a backhauld MAC and
     a  random access MAC simultaneously.

This may be an improved hybrid between 802.11 and 802.16 perhaps.
Perhaps Ken Pierce (I know he is on this list) can tell us what he
thinks?

Thanks,

Phil

> -----Original Message-----
> From: Yong Kang [mailto:[email-masked]]
> 
> 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
> 
****************************************************************************
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: Hollos Daniel <[email-masked]>
Date: Mon, 12 Nov 2001 18:53:59 +0100 (CET)

Dear All,

  I don't really understand why we obviously need a random access MAC on
the edge of the network. There are some well-defined scheduled MAC systems
which work quite well as a "last-hop", e.g. ETSI Hiperlan 2. You can reach
very high channel efficiency without any major disadvantages.
However the H/2 standard does not consider multi-hop extension yet, there
are many works about this problem, and some solutions seem to be quite
realistic, easy to implement and promising according to simulation
results.
The only think which is against the H/2, as far as I know the
complexity of the system: It's more complex than 802.11, so you probably
need more expensive devices. Do anyone know about something else?

Anyway, it seems to be a very interesting idea, to differentiate the MACs
between the wireless backbone and the last hop. 
I can imagine it either using two physical device types, but in this case
the WAN devices shouldn't be mobile in order to ensure full connectivity,
or just in very limited manner.

Or use one device type, which may act as a WAN-supporter when there is
unused by its owner for a longer time for example, and as a client 
otherwise. Of course some fixed WANs are also needed in this situation.

There are thousands of possibilities how to do that.
So, if anyone has a good idea, throw it here and let's discuss it!

Yours, Daniel Hollos

****************** Daniel Hollos *************************
*                                                        *
* Technical University of Berlin                         *
* Faculty of Electrical Engineering and Computer Science *
* Telecommunication Networks Group                       *
* Phone: +49 30 31479677 (Office)                        *
*        +49 16095401825 (Cell/Mobile)                   *
*                                                        *
**********************************************************

---

From: Yong Kang <[email-masked]>
Date: Mon, 12 Nov 2001 11:13:25 -0800 (PST)

> the edge of the network. There are some well-defined scheduled MAC systems
I think for efficiency purpose, scheduled MAC usually out perform the
random access Mac, but the point is, from past experience of internet,
simplicity is more important at the edge(e.g ether) while critical
performance is more important at the core.

> the WAN devices shouldn't be mobile in order to ensure full connectivity,
why full connectivity, we want multihop core, if full connectivity, 802.11
maybe ok :)

another thinking.
no matter the backbone node move or not(mil or commercial), 802.11
performance is too poor to fit there. 

thanks
yong

---

From: Yong Kang <[email-masked]>
Date: Mon, 12 Nov 2001 12:48:40 -0800 (PST)

thanks Phillip,
 another point I think we need an high efficient core Mac standard is
imposed by the demand of routing protocol. It's kind of weird to tie Mac
and routing together. But I do meet some fundamental question when design
and implement ad hoc routing protocol, and they are Mac dependent though
the network layer model try to make it transparent.

for example, schedule Mac v.s. random access Mac:
1.how expensive a flooding routing pkt will be?
2.what's the efficient diff between a limited broadcast pkt v.s. several
  unicast Xmit to all neighbors?
3.How well the reliable Xmit can be handled by diff Mac and what's the
  cost?
4.how long the delay of a successful Xmit would be?(big delay deviation
  could be a fatal problem).
5.how the router detect it's neighbor base on different Mac?

So, it's only after we got a concrete Mac, we can compare the versatile
routing approach for different requirment.

sorry for abuse such a mass for these questions, but it's various
questions I met when making a design/implement decision for routing
protocol. 

has anyone study the dependency of routing protocol on diff Mac? 
or, how to make is really transparent for ad hoc network?

thanks.
yong

---

From: Marceau Coupechoux <[email-masked]>
Date: Tue, 13 Nov 2001 10:12:13 +0100

Hi,

Have you got some references on the works related to a multi-hop
extension of HL2?

-- 
Marceau Coupechoux
--------------------------------------
Alcatel CIT Corporate Research Center
Radio Department (UTR)

Route de Nozay 91460 Marcoussis France
tel : 01 69 63 43 59 fax : 43 60
mel : [email-masked]
--------------------------------------

---

From: Yang Xiao <[email-masked]>
Date: Tue, 13 Nov 2001 08:22:31 -0800 (PST)

Hi, Phillip

I am now in the meeting of IEEE 802.11 this week. If
you plan to bring something to the IEEE 802.11, just
attend the meeting two times and become a voting
member, then you can make a motion. You can propose
a revision to the standard. The voting members will
vote whether to add it into the draft first. I guess
that it depends how much you change the standard to be
accepted. If you change the standard a lot, the chance
to be accepted is small. However, it is still
possible.

Regards

Yang

--- Phillip Neumiller <[email-masked]>
> e-mail to your own virus checking procedures. 

__________________________________________________
Do You Yahoo!?
Find the one for you at Yahoo! Personals
http://personals.yahoo.com

---

From: Yang Xiao <[email-masked]>
Date: Tue, 13 Nov 2001 08:22:31 -0800 (PST)

Hi, Phillip

Regards

Yang

---

From: Rex Buddenberg <[email-masked]>
Date: Tue, 13 Nov 2001 10:12:39 -0800

There are about three problems here that need to get disentangled:

1.  network layer handoffs from one 802.11 subnet to another.  This 
is a routing problem and properly handled in the MANET working group 
in IETF.

2.  handoffs from one 802.11 AP to another within a single subnet. 
802.11 does indeed handle this, but with the problems noted in this 
thread (carrier detect outshouting modulation reception).

set both of these aside, although we can recognize 2. as a symptom of 
a larger problem.

3.  wireless multi-user networks (whether local or wide) have the 
silent host problem.  They also stretch (in local) and break (in 
wide) the basic assumption of LAN MACs: CSMA/CD and token systems 
both rest on the assumption that everybody can hear everybody else 
(or at least their 2 nearest neighbors in the case of token).  802.11 
stretched the basic ethernet algorithm -- it was the simplest 
approach and did indeed get something useful onto the street.

Quick side trip to straighten out the lingo: terrestrial WANs (frame 
relay, ATM, etc) are designed to connect switches together with 
point-to-point plumbing (e.g. fiber).  Consequently they have no MACs 
at all -- don't need them.  The protocol surgery to get a MAC in is 
pretty difficult because there are a bunch of non-multicast, 
non-shared-use tacit assumptions elsewhere in the protocols.
      On the other hand, the 802 networks are easier to deal with 
since we can leave the 802.2 part of the data link layer alone and we 
needn't fool with the framing solved problems in the PMI half of the 
physical layer -- we only need to do surgery on the MAC.

>      This could be an improvement to 802.11.

'improvement' needs definition.  Existing 802.11 MAC is fairly good 
vis interactivity, at least in a lightly loaded network.  But it 
isn't real good in a well-populated, busy net in the throughput 
efficiency department.

>      a  random access MAC simultaneously.

You got to the same conclusion that both Graham Campbell (at IIT) and 
I got to independently*.  Graham calls this Dual Queue (I didn't get 
so presumptions as to coin a name).  You use one queue (like CSMA/CD) 
to get into the network -- it's free-for-all with hosts out-shouting 
others.  But it works because each customer who gets through _once_ 
in this queue is then removed from the queue and put into the 
scheduled queue.  The scheduled queue has a sched that is promulgated 
by the net control (AP in 802.11-ese) and nobody transmits except on 
that schedule.  The assumption about everybody hearing everybody else 
changes to everybody able to hear the net control -- an assumption 
that fits both satellite systems and 802.11 APs ... and HF nets for 
that matter.

There is definitely a tradeoff between interactivity and efficiency. 
In this case, the trade is heavily toward efficiency -- the outgoing 
frame is answered, in best case, in the next cycle.  And the shorter 
the cycle times in the scheduled queue the more overhead it costs 
you.  Technically this can be accommodated by teaching end systems to 
recognize source quench properly (uSoft TCP implementations didn't 
and still may not) and a few other implementation details.

Graham's algorithm differs from my description in detail; I can't 
recite his version from memory.  DQSA -- Dual Queue Switch 
Architecture and DQRAP -- Dual Queue Reservation Access Protocol are 
terms he uses for much the same things.

*mine in my thesis 15 years ago!!;)

>Yong:
>>Does anyone on the list know how we could
>bring this to the IEEE?

I don't know the direct answer to this question ... but run up IEEE's 
web page, find out who's on the 802.11 committee and ask one of them.

I could also be convinced that this would be a worthwhile IETF 
working group.  There are >1 right answers here.  The reason for this 
suggestion has to do with standards-making ethic -- IETF requires 
demonstrated implementations in parallel with the standards doc.  On 
the other hand, IEEE 802 has been pretty successful over the years.

-- 
b

---

From: Yang Xiao <[email-masked]>
Date: Tue, 13 Nov 2001 22:11:48 -0800 (PST)

Hi, all

One reason that the IEEE 802.11 standard committee
decided to adopt a random access is that random access
MAC provides flexibility, robustness and unconstrained
movement of mobile hosts. Yong kang is right that
simplicity is also a more important issue than
performance sometime. One example is Ethernet versus
Token Ring. They are both the IEEE LAN standards.
Ethernet becomes more popupar even though Token Ring
performs better in heavy load conditions. A. S.
Tanebaum wrote "Keep it simple and stupid (KISS)" in
his book. Moreover, the success of a technology (or
protocol) depends on many factors. Performance is only
a factor. One example is ATM versus IP in QoS aspects.
ATM is still dying even though it outperforms IP in
many aspects. However, it is worthwhile studing all
kinds of possibilities since no one can know the
future.

Regards

Yang

---

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

HIPERLAN1 MAC could be also another source of inspiration. To my knowledge
it is the only MAC that was thought "multihop" from the origin. It avoids
BEB and fixed carrier sense starvations.

Philippe
----- Original Message -----
From: "Phillip Neumiller" <[email-masked]>
To: "'Yong Kang'" <[email-masked]>; "Leonard Miller"
<[email-masked]>
Cc: "MANET Discussion" <[email-masked]>
Sent: Monday, November 12, 2001 2:29 PM
Subject: RE: [Fwd: Re: Does 802.11b do multi-hop well?]

---

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

HIPERLAN 2 is terribly non ad-hoc oriented. For example there is a kind of
frequency planning needed in order to separate the access points which
cannot work on same channels. I think there has been a discussion about it
earlier.

Philippe

---

From: Yong Kang <[email-masked]>
Date: Wed, 14 Nov 2001 10:38:54 -0800 (PST)

> it is the only MAC that was thought "multihop" from the origin. It avoids
I know rooftop Inc.'s  Mac handle multihop very well. After bought by
Nokia, it's more a commercial product now. Maybe it's a company policy
that make those smart guy don't talk alot in this list :)

is that true rooftop guys?

thanks
yong

---

From: mase <[email-masked]>
Date: Thu, 15 Nov 2001 10:38:17 +0900

Hi, all

In connetion with the following discussion, we have proposed the 
integration of IEEE802.11 WLAN and MANET. In our model, APs of WLAN are 
treated as the mobile hosts of the MANET, which constitutes the backbone 
for conneting APs. The MANET is transparent from WLAN users. APs can be 
located on the roof of the car, for example. MANET is used only when 
loaming is required. As a result, multihop traffic load on the MANET is 
significantly reduced.  We study two architectures for realizing this 
network model, LAN Emulation (MAC over IP) and IP-in-IP encapsulation. The 
following paper will be presented to IEEE International Conference on 
Wireless LANs, PANs and Home Networks 5 - 7 December 2001, Singapore
Conference Web Site: www.icwlhn.org

K. Mase et al., Wireless LAN with Wireless Multihop Backbone Network (WMLAN)
Please contact, when you request a copy of the paper.

Kenichi Mase
Niigata University, Niigata, Japan

  At 10:12 01/11/13 -0800, Rex Buddenberg wrote:
>1.  network layer handoffs from one 802.11 subnet to another.  This is a 
>routing problem and properly handled in the MANET working group in IETF.
>
>2.  handoffs from one 802.11 AP to another within a single subnet. 802.11 
>does indeed handle this, but with the problems noted in this thread 
>(carrier detect outshouting modulation reception).
>
>set both of these aside, although we can recognize 2. as a symptom of a 
>larger problem.
>
>3.  wireless multi-user networks (whether local or wide) have the silent 
>host problem.  They also stretch (in local) and break (in wide) the basic 
>assumption of LAN MACs: CSMA/CD and token systems both rest on the 
>assumption that everybody can hear everybody else (or at least their 2 
>nearest neighbors in the case of token).  802.11 stretched the basic 
>ethernet algorithm -- it was the simplest approach and did indeed get 
>something useful onto the street.
>
>point-to-point plumbing (e.g. fiber).  Consequently they have no MACs at 
>all -- don't need them.  The protocol surgery to get a MAC in is pretty 
>difficult because there are a bunch of non-multicast, non-shared-use tacit 
>assumptions elsewhere in the protocols.
>      On the other hand, the 802 networks are easier to deal with since 
> we can leave the 802.2 part of the data link layer alone and we needn't 
> fool with the framing solved problems in the PMI half of the physical 
> layer -- we only need to do surgery on the MAC.
>
>'improvement' needs definition.  Existing 802.11 MAC is fairly good vis 
>interactivity, at least in a lightly loaded network.  But it isn't real 
>good in a well-populated, busy net in the throughput efficiency department.
>
>You got to the same conclusion that both Graham Campbell (at IIT) and I 
>got to independently*.  Graham calls this Dual Queue (I didn't get so 
>presumptions as to coin a name).  You use one queue (like CSMA/CD) to get 
>into the network -- it's free-for-all with hosts out-shouting others.  But 
>it works because each customer who gets through _once_ in this queue is 
>then removed from the queue and put into the scheduled queue.  The 
>scheduled queue has a sched that is promulgated by the net control (AP in 
>802.11-ese) and nobody transmits except on that schedule.  The assumption 
>about everybody hearing everybody else changes to everybody able to hear 
>the net control -- an assumption that fits both satellite systems and 
>802.11 APs ... and HF nets for that matter.
>
>There is definitely a tradeoff between interactivity and efficiency. In 
>this case, the trade is heavily toward efficiency -- the outgoing frame is 
>answered, in best case, in the next cycle.  And the shorter the cycle 
>times in the scheduled queue the more overhead it costs you.  Technically 
>this can be accommodated by teaching end systems to recognize source 
>quench properly (uSoft TCP implementations didn't and still may not) and a 
>few other implementation details.
>
>Graham's algorithm differs from my description in detail; I can't recite 
>his version from memory.  DQSA -- Dual Queue Switch Architecture and DQRAP 
>-- Dual Queue Reservation Access Protocol are terms he uses for much the 
>same things.
>
>
>I don't know the direct answer to this question ... but run up IEEE's web 
>page, find out who's on the 802.11 committee and ask one of them.
>
>I could also be convinced that this would be a worthwhile IETF working 
>group.  There are >1 right answers here.  The reason for this suggestion 
>has to do with standards-making ethic -- IETF requires demonstrated 
>implementations in parallel with the standards doc.  On the other hand, 
>IEEE 802 has been pretty successful over the years.
>
>>

---

From: Hollos Daniel <[email-masked]>
Date: Thu, 15 Nov 2001 17:44:11 +0100 (CET)

There is a paper worth reading related to this topic:

Csaba Keszei, Daniel Hollos, Laszlo Pap, Sandor Imre:
HIPERLAN/2 Dynamic CC Selection in Ad Hoc Multi-hop Environment 
proceeding, Mobile Summit 2000
(Session 6C Network Architecture and Planning Issues)

If you apply to the standard the solution inculded in that paper about the
CC selection procedure, you don't need any frequency planning, and
prevents you from creating any hidden nodes.

If any of you are interested in that paper, just send me an email and I
attach the pdf file for you, may be easier than looking for that.

Yours, Daniel

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 15 Nov 2001 18:14:29 +0100

I will read this paper with interest.

Do you mean that you can allow HIPERLAN/2 base stations to operate on the
same frequencies?

Philippe

---

From: Hollos Daniel <[email-masked]>
Date: Fri, 16 Nov 2001 15:47:04 +0100 (CET)

> Do you mean that you can allow HIPERLAN/2 base stations to operate on the
The paper introduces modifications to the H/2 CC selection, which
enables the H/2 CC selection to operate well when the area to be covered
is larger than one H/2 cell. If you make the CC selection process
according to the standard, in the most scanarios there are some nodes
which are unable to communicate because they are hidden terminals from the
point of view of some APs.

The goal of this paper was to correct the failures of the original
version, and letting the system to be configured automatically, without
any frequency planning, etc.
So, two APs can operate on the same frequency when they are far from each
other enough, so they don't disturb each other.
BUT: They can't communicate to each other using the same frequency.

I will send that papers to all who were interested, thank you for reading!

For information about interconnecting H/2 cells (on different working 
frequencies) using relaying terminals laying on the overlapping area of
two APs, follow this link:

http://www.comnets.rwth-aachen.de/pdl?BIBID=Pz_VTCspring01&NL=20010704

Yours, Daniel

---

From: Yang Xiao <[email-masked]>
Date: Fri, 30 Nov 2001 10:02:23 -0800 (PST)

Normally, we refer CSMA as 1-persistent CSMA. There are also
p-persistent CSMA (0<p<1) and Nonpersistant CSMA.

A CSMA with backoff algorithm is called Nonpersistent-CSMA. Therefore,
we can call Ethernet or 802.3 as Nonpersistant-CSMA/CD. Similarly, we
can call IEEE 802.11 MAC 's DCF basic mode as Nonpersistant-CSMA/CA.
When I read a lot of papers which provide performance analysis of
either 802.11 MAC 's DCF or 802.3, most of them make a asumption that
there exists a transmission probability (p) which is the same for each
station. Such an asumption claim that a Nonpersistant CSMA can be
approximated by a special case of p-persistant CSMA. If such an
assumption is accurate, why 802.3 adopted a Nonpersistant-CSMA/CD
instead of p-persistant-CSMA/CD, and why 802.11 adopted a
Nonpersistant-CSMA/CD instead of p-persistant-CSMA/CA ? What's the
drawback of p-persistant? Any paper to compare Nonpersistant vs.
p-persistant?

Any comment is appreciated.

Yang

__________________________________________________
Do You Yahoo!?
Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
http://geocities.yahoo.com/ps/info1