Subject: [manet] capacity of ad hoc networks

From: Pietro Michiardi <[email-masked]>
Date: Tue, 25 Oct 2005 10:03:31 +0200

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

---

From: Christian de Waal <[email-masked]>
Date: Tue, 25 Oct 2005 18:35:11 +0200

Dear Pietro,

unfortunately, you don't give any details on your "content distribution 
mechanism", but I assume that it is some kind of efficient flooding scheme.

If you really restrict yourself to the special case that you have only 
one data source, things are quite simple. I was immediately reminded of 
the publication [1], which considers the opposite case that there are 
many sources, but only one destination, assuming that all streams have 
the same data rate. I guess all you have to do is to identify what in 
[1] is called the "bottleneck collision domain", i.e. a set of maximal 
cardinality containing links which cannot be scheduled simultaneously. 
(Things only get complicated if you have multirate hardware, because 
then, the stations may require different transmission durations even 
though they have the same amount of data to send!)

If you also want to consider the general case of several data sources, I 
don't think that the G&K work you cite is very helpful for two reasons: 
First, it examines the capacity of arbitrary / random networks as the 
number of stations approaches infinity, and second, it deals with the 
"transport capacity", i.e. the capacity of unicast streams.

As you wrote in your other mail, what you need is a method for 
calculating the achievable throughput for a given network. This can be 
done with the graph colouring algorithm we have published in [2] -- 
though our application actually was to measure the transport capacity, 
the algorithm can just as well be run with a set of trees as input 
rather than a set of unicast routes.

However, you should keep in mind that a theoretical bound on the 
achievable throughput is quite different from what you can achieve with 
IEEE 802.11 which "wastes" a lot of resources due to medium access 
control and transmission failures.

Hope this helps!

Regards,
Christian de Waal

[1] Jangeun Jun, Mihail Sichitiu. "The Nominal Capacity of Wireless Mesh 
Networks." IEEE Wireless Communications, Vol. 10, Issue 5, pp. 8-14, 
October 2003.

[2] Patrick Peschlow, Michael Gerharz, Christian de Waal, Peter Martini. 
"An Efficient Transport Capacity Estimation Method for Wireless Multihop 
Network Topologies." Proc. of the 34th Annual Conference of the 
Gesellschaft für Informatik (2nd German Workshop on Mobile Ad-hoc 
Networks), Vol. 1, pp. 90-94, Ulm, Germany, September 2004.

-- 
____________________________________________________________________
Christian de Waal

University of Bonn                            Phone: +49 228 73-4548
Institute of Computer Science IV                Fax: +49 228 73-4571
Roemerstr. 164                         E-mail: [email-masked]
53117 Bonn, Germany                    http://www.cs.uni-bonn.de/IV/