Subject: Re: Ad Hoc Network Scalability

From: Nitin H Vaidya <[email-masked]>
Date: Thu, 5 Jul 2001 09:57:16 -0500 (CDT)

>> From [email-masked] Thu Jul  5 09:01:17 2001
  >> 
  >> 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.

Certainly an interesting result.

It might be also useful to point out some limitations though.

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).

Nevertheless, I think the paper makes the interesting point that
mobility can increase capacity of the network.

- nitin

  >> 
  >> 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: Chip Elliott <[email-masked]>
Date: Thu, 05 Jul 2001 11:19:12 -0400

Hi Nitin, Hi Scott,

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.

Cheers,

-- Chip

---

From: "Samir R. Das" <[email-masked]>
Date: Thu, 5 Jul 2001 13:20:16 -0400

With the risk of digressing a little, I would like to point out that even
with a more conventional model, mobility increases capacity. By conventional
model I mean a model where we want to relay packets between end points as
soon as possible, instead of waiting and buffering for the most opportune
moments. This is the model the MANET community is most familiar with.

The intuition here is that mobility randomizes the node positions enough
that radio congestion points are now less on average or are more avoidable
with an idealized routing protocol (assuming CSMA-based MAC). We have
analyzed this effect using simulations (results forthcoming). Also, some
published ns-2 based simulation results in the last few years also did show
occassional routing performance improvements with mobility!

Samir

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Chip Elliott
> Sent: Thursday, July 05, 2001 11:19 AM
> To: Nitin H Vaidya; [email-masked]
> Cc: [email-masked]
> Subject: Re: Ad Hoc Network Scalability
>
>
>
> Hi Nitin, Hi Scott,
>