Subject: RE: [manet] capacity of ad hoc networks

From: "Bush, Stephen F \(Research\)" <[email-masked]>
Date: Tue, 25 Oct 2005 14:34:24 -0400

Perhaps another facet of capacity is the ability to maintain viable routes
in a manet. 

Some work on that and it's relation to K&G is in: "The Limits of Motion 
Prediction Support for Ad hoc Wireless Network Performance" 
somewhere under http://www.research.ge.com/~bushsf.

Steve

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of
Brown Tim
Sent: Tuesday, October 25, 2005 11:05 AM
To: Pietro Michiardi
Cc: [email-masked]
Subject: Re: [manet] capacity of ad hoc networks

A few comments:
The Gupta and Kumar results consider a unit disk with power control. As
nodes are added, the power is allowed to decrease so that interference is
"optimal" for the theoretical result. In your case, a fixed grid spacing
and power level means that as you add nodes the size of the network grows.
Scaling this to a unit disk will be similar to the scaling of power in the
unit disk in the G&K result.

G&K also considers arbitrary traffic patterns to get bounds on the
capacity. We could place many closely spaced 1 hop communication pairs of
nodes in a given space to get many simultaneous flows. But this sends lots
of data over very little distance. So, they pose the problem as the
distance forwarding capacity.  In this case an arbitrary network can not
forward more than O(W sqrt(A n))  bit meters per second for a network of
area A.

So, the do address many of the points you discuss below.
	Regards,
		Tim
On Tue, 25 Oct 2005, Pietro Michiardi wrote:

> Thanks for your answer Gabirel,
> please find my comments in line
>
> On 10/24/05, Gabi Kliot <[email-masked]> wrote:
>
> >> Hi Peitro
> >>
> >> I first wanted to refer to your last sentence - "I think proving that a
> >> content distribution scheme reaches a theoretical ..."
> >> As I understood you are not trying to prove it (Gupta and Kumar already
> >> did) but to show that some practical setup actually behaves like the
> >> theoretical result, right? I mean - you can't prove it by experiment.
> >> You can disprove it, thought.
> >
> >
>
> Sure, I don't want to prove theoretical results: I'm trying to see if my
> practical setup (that depends of course on some parameters that will be optimized)
> achieves a theoretical limit.
>
>
>
> >>
> >> I have been also wandering a bit about the exact meaning of this
> >> theoretical bound of diminishing capacity of W/sqrt(n) available for
> >> every node. First I think it greatly depends on whether all source nodes
> >> send their info to different destination nodes simultaneously. I think
> >> the result refers to the fact that EVERY node tries to send some data
> >> ALL the time to some random destination. Do you do the same in your
> >> setup?
> >
> >
>
> Traffic patterns in our content distribution scheme are pretty complex.
> There is one source of information that distributes the content, and as many
> receivers as N-1 where N is the number of nodes in the network
> (note: I could add some passive relay nodes too, but I don't want to add too
> many parameters right now). Every receiver is connected to a subset of the
> N-2 other receivers (the cardinality of this subset is a parameter) and exchange
> partial content downloaded so far.
>
> In summary, traffic patterns can be assumed to be pretty dense.
>
> NOTE: I'm dealing with bulk data transfer, so delay is not such
> a big issue in my setting.
>
>
>
> >>
> >> Second, the interference plays very important role in the result. Here
> >> what is very important is that in Gupta and Kumar work they assumed the
> >> network is a Unit disk graph, nodes placed randomly at place. As a
> >> result of this transmission range should be set such that connectivity
> >> is preserved. According to their other paper about connectivity range,
> >> the transmition range should be such that node has at least O(log(n))
> >> neighbors and transmition range depends on number of nodes or nodes
> >> density. In your scheme transmition range is constant and does not
> >> depend on a number of nodes. I can not tell you exactly how does it
> >> influence the result, but it very much might be that there is MUCH less
> >> interferences in your setup and as a result much better capacity is
> >> achieved.
> >>
> >> So I think you might consider changing the topology and see what
> >> happens. No one of course can say for sure what is the right topology
> >> for ad hoc network that will model  the real networks as exact as
> >> possible. Unit disks are believed to be not so bad model. Grid is not
> >> such a good model, I think.
> >
> >
>
> Sure, I'm doing simulations with different initial topologies,
> the grid one was the only way I had to control (a little) the number of
> multi-hop path i have. Anyway I'm planning to include mobility to the
> simulations, so node placement would quickly follow a random pattern.
>
>
> >>
> >> Another issue is the asymptotic O and theta notations. The theoretical
> >> result talks about theta or O of W/sqrt(n), but the constant here could
> >> play an important role.
> >>
> >
> >
>
> And this is why I was wondering if there is any rough practical
> way of estimating the capacity of the network!!
>
>
>
> >> These are some of my thoughts,
> >> I would be glad to discuss it further on,
> >>
> >> Best regards,
> >>
> >>
> >> Gabriel Kliot
> >> Technion - Israel Institute of Technology
> >>
> >>
> >
> >
> >>> > -----Original Message-----
> >>> > From: [email-masked] [mailto:[email-masked]]
> >>> > On Behalf Of Pietro Michiardi
> >>> > Sent: Tuesday, October 25, 2005 10:04 AM
> >>> > To: [email-masked]
> >>> > Subject: [manet] capacity of ad hoc networks
> >>> >
> >>> >
> >>> > Dear all,
> >>> > I have a very basic yet practical question.
> >>> > I am studying the performance of a content distribution mechanism for
> >>> > MANET designed and implemented by my group. Throughout this
> >>> > scheme, one
> >>> > source distributes some content (in the order of 10MB up to a
> >>> > maximum of
> >>> > 100MB) to every other node in the network.
> >>> > Right now I'm considering no mobility and two basic scenarios:
> >>> > - no multihopping (every node is in transmission range of
> >>> > every other node)
> >>> > - multihopping (some S-D pairs are more than one hop far away)
> >>> >
> >>> > I have a scenario with 16 nodes using 802.11b and the data
> >>> > rate has been
> >>> > set to 11Mbps. For sake of simplicity we consider a grid
> >>> > network, i.e.
> >>> > nodes are positioned on a grid (4x4). If multihopping is
> >>> > allowed, node
> >>> > distance is a little less then the data transmission range.
> >>> >
> >>> > Based on papers from Gupta&Kumar and Grossglauser&Tse, I tried to
> >>> > characterize the upper-bound aggregate upload capacity of the network
> >>> > without success.
> >>> >
> >>> > Do you have any suggestions on how to determine this
> >>> > upper-bound value? Obviously it depends on many factors such
> >>> > as traffic pattern, node
> >>> > positioning, ... However, even a rough estimate could be enough.
> >>> >
> >>> > I think proving that a content distribution scheme reaches a
> >>> > theoretical
> >>> > upper-bound value for the aggregate (sum on all nodes) amount
> >>> > of upload
> >>> > capacity of the network would be a good way of assessing its
> >>> > properties.
> >>> >
> >>> > Thanks for your support!
> >>> >
> >>> > Pietro
> >>> >
> >>> > _______________________________________________
> >>> > manet mailing list
> >>> > [email-masked]
> >>> > https://www1.ietf.org/mailman/listinfo/manet
> >>> >
> >>
> >>
>
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
>

Timothy X Brown
Interdisciplinary Telecommunications
Electrical and Computer Engineering
ECOT 256 Campus Box 530
University of Colorado
Boulder, CO 80309
Tel: (303) 492-1630
Fax: (303) 492-1112
http://ece.colorado.edu/~timxb

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet