Subject: RE: Ad Hoc Network Scalability

From: Phillip Neumiller <[email-masked]>
Date: Thu, 5 Jul 2001 12:09:34 -0400

Well, this is sort of a "bait-and-switch title".  I don't 
consider this paper's results realistic or all that useful,
precisely since it does not put any upper bound on latency. 

A "real" system, if being used for anything interactive, will
have "real latency" bounds.

A far more interesting paper might analyze maximum bits/Hz/
second/user in a MANET (average, and variance (very important))
and show this with a variety of mobility models while increasing the 
number of mobiles distributed over a fixed area  and with fixed
mobile density per unit area (area increases with number of mobiles)
(alas a much more difficult nut to crack).

Hey I can wish, can't I?

Best regards,

Phil

> -----Original Message-----
> From: M. Scott Corson [mailto:[email-masked]]
> Sent: Thursday, July 05, 2001 8:35 AM
> To: Joe Macker; [email-masked]
> Cc: [email-masked]
> Subject: Re: Ad Hoc Network Scalability
> 
> 
> 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: Nitin H Vaidya <[email-masked]>
Date: Thu, 5 Jul 2001 11:19:36 -0500 (CDT)

hi Chip:

  >> From [email-masked] Thu Jul  5 10:19:26 2001
  >> 
  >> At first blush, it seems like this model could well handle an
  >> unlimited number of flows - again, assuming that memory is
  >> unbounded and unbounded delay is OK. It also doesn't
  >> strictly require all-to-all connectivity, if one has
  >> a non-zero probability of copying/moving a packet to any node
  >> that one encounters. This would add enough of a random
  >> walk element so that a packet could transit a non-fully-connected
  >> graph.

Surely one can generalize to an arbitrary number of flows,
but the per-flow throughput will not stay O(1).
A simple "proof" is to pretend that each node generates
packets destined for a single destination D.
So there are n-1 flows with D as the destination.
Throughput for each of these flows will be O(1/n), not O(1),
since the aggregate rate at which node D can receive is O(1)
and there are O(n) flows sharing this.

Similar argument for mobility: It is not necessary for each node-pair
to become neighbors over time. So long as we can guarantee
O(1) hops, i.e., constant with increasing n, the result will hold.

- nitin

  >> 
  >> Cheers,
  >> 
  >> -- Chip
  >> 
  >> 
  >> 
  >> >Correct me if I am mistaken, but as I recall, the result is only valid
  >> >when each node is source for one flow at any given time (or more
  >> >precisely, each node generates packets destined to only one other
  >> >node in the network). In addition, each node should be destination
  >> >for only one flow. These constraints, although they make it possible
  >> >to prove the above result (which is quite interesting), make
  >> >it difficult to use the result otherwise.
  >> >
  >> >Also, the result requires that each packet take at most 2 hops, which,
  >> >in turn, requires that each node must meet every other node in the
  >> >network eventually -- thus, for the result to be valid, it is not
  >> >enough for the nodes to be mobile, but also that over time each
  >> >node-pair becomes neighbors (often enough).
  >> >
  >> 
  >>