Subject: Re: Ad Hoc Network Scalability

From: "M. Scott Corson" <[email-masked]>
Date: Thu, 05 Jul 2001 08:34:37 -0400

Actually, Matthias Grossglauser (AT&T Labs - Research), David Tse
(University of California at Berkeley) have a very interesting throughput
result (best paper Infocom 2001) for ad hoc networks.

Basic idea:  Take a message you wish to send to some destination, break it
up into N pieces, give those pieces to N different nodes that you randomly
bump into as you walk around, eventually all N of those nodes will bump
into the destination and give it their piece, effectively transferring the
whole file.

This result shows that the average long-term throughput per
source-destination pair can be kept *constant* even as the number of nodes
per unit area increases.  Of course, there is no bound on the message
delivery latency or memory requirements of the network nodes, but a very
interesting and rather counter-intuitive result nonetheless.

downloadable from http://www.ieee-infocom.org/2001/

-Scott

At 10:57 AM 6/29/01 -0400, Joe Macker wrote:
>At 07:21 PM 6/28/2001 +0200, you wrote:
>>It is clear that multihop impacts the performance.
>>
>>In a recent paper (in information theory, I must look in my records), it is
>>shown that the percentage of throughput in an ad hoc network of N users is
>>at best of order 1/sqrt(N) in a 2D network with power law signal
>>attenuation. The impact of routing makes that each packet has to be routed
>>in an average of sqrt(N) hop.
>
>Gupta and Kumar, IEEE transactions on Information Theory, vol IT-46, no.2, 
>pp 388-404, March 2000.
>
>
>>If the traffic would have been local (i.e. directed to neighbor), then the
>>average percentage traffic per node would be O(1) due to spatial reuse.
>>This is not too bad, since if the network would have been connected on a
>>single Ethernet hub, then the percentage would have been O(1/N). Notice
>>that even with routing overhead, the ad hoc network does better than the
>>Ethernet hub.
>>
>>This result is attainable because when the traffic density increases, the
>>distance between hops decreases and spatial reuse is possible.
>>Unfortunately this is not completely possible with IEEE 802.11 because the
>>CSMA carrier sense level is fixed and prevent close spatial reuse. To
>>obtain theoretical bounds  one should need at least a tunable carrier sense
>>level.
>>
>>Philippe
>>
>>A 15:36 27/06/01 -0400, Phillip Neumiller a écrit :
>> >Hello,
>> >
>> >In the paper found at http://www.pdos.lcs.mit.edu/papers/grid:mobicom01/
>> >"Capacity of Ad Hoc Networks" from MIT labs for CS, the paper concludes
>> >that the "key factor" determining whether large ad hoc networks are
feasible
>> >
>> >is the locality of traffic (which results in fewer hops on average between
>> >communicators).
>> >
>> >Have others found this to be the "key factor" in ad hoc network
feasibility?
>> >
>> >It would seem to me, that "WHAT" the key factor is would depend somewhat
>> >on the network architecture being analyzed and specifically it would
depend
>> >heavily on the MAC implementation.  It seems to me that this paper may
>> >have been more appropriately titled "Capacity of Ad Hoc 802.11 Wireless
>> >Networks".  Is it generally agreed that the 802.11 MAC can adequately
>> >represent what the "key scalability factors" are?  I think the 802.11 MAC
>> >is expedient but not necessarily that useful for generalized analysis.  Is
>> >there such a thing as a perfect MAC model?, i.e. a MAC that achieves X%
>> >efficiency (my guess is its just a circuit switch big enough to connect
>> >everyone to everyone else n(n+1)/2!!!).  This would not be very practical
>> >in an RF MANET so there must be some happy medium (pun intended)!
>> >
>> >Thanks,
>> >
>> >Phil Neumiller
>> >
>
>
>

---

From: "Philippe Jacquet" <[email-masked]>
Date: Sat, 7 Jul 2001 04:13:05 +0200

As far as I remember, the key of this result is in the mobility model. The
mobility must be uniform
in the sense that each node must visit every other node during fairly equal
times. This is a very restrictive
model and in some extend unrealistic (this is not because you can move that
you go equally everywhere).
If the mobility model were not uniform then the result would not hold.
For example imagine nodes moving only in their vicinity.
Phil network model is also another counterexample.

I think the flow model in nodes has a not too much impact excepted that the
global statistic on flows
must show uniformly distributed sources and uniformly distributed
destinations. Which is still
not a completely realistic model.

If each node would have an equal number of active flows to every destination
in the network, then there would
be no need of the two hops trick and one hop transmission would suffice.

Philippe