Subject: [manet] scalability in ad hoc networks

From: Dmitri Deshun Perkins <[email-masked]>
Date: Tue, 17 Sep 2002 16:35:54 -0400 (EDT)

Hello:

I have read several papers on routing in ad hoc networks (i.e., manet
and sensor). The term scalability is often used. Does the manet group
have some specific idea of what is meant by scalable? I have a few
questions here.

1. Are we saying an algorithm is scalable depending on its performance
   (e.g., packet delivery ratio) versus network density? traffic load?
   control overhead? or some combination of performance measures?

2. What is considered a small, medium, or large network?

These questions are motivated by some simulations done using
glomosim. For example, for various network sizes, mobility
patterns and traffic loads, protocol A and protocol B achieve very
very similar throughput, but protocol A produces significantly more
control packets.

3. While, we may conclude that protocol B uses control packet more
efficienty (number of packet deliver per control packet), can we say
that is more scalable since the performance of both protocols is the
same (at least from an external view)? That is, both protocols
deliver the same number of packets, but one must work harder to do
so, which may impact battery usage.

Thanks for your time and thoughtful responses.

==================================================
Dmitri D. Perkins, Assistant Professor
The Center for Advanced Computer Studies
University of Louisiana at Lafayette
P.O. Box 44330, Lafayette, LA 70503

office: (337)482-6732   fax: (337)482-5791
http://www.cacs.louisiana.edu/~perkins
==================================================

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

---

From: Cesar Santivanez <[email-masked]>
Date: Wed, 18 Sep 2002 22:00:55 -0400

Dmitri,

We were also looking at the issue of scalability for MANETs and
found that there were not clear consensus of what it meant for a
routing protocol to be deemed scalable. There was a confusion
about network scalability (what the network can support) and
routing protocol scalability (what the routing protocol can handle
provided that the network can).

For example, if we consider the class of `power controlled' networks
where the node degree is bounded and with a uniformly distributed
traffic pattern, we may see that as we increase the size of the network
the traffic requirements become unbearable. This is due to the traffic
increasing much faster than the network rate (sum of all possible
simultaneous transmissions). Thus, this class of network does not
scale w.r.t.  network size. So, if the network does not scale w.r.t. network
size, what is the meaning of a routing prrotocol being scalable???

In our INFOCOM paper (reference below), we presented our position
on this topic, stating that  a routing protocol is scalable
(w.r.t. a parameter X) if  -- as the parameter X increases --
the routing protocol does not significantly degrades network
performance.  Simply speaking, if the network can support thousands of
nodes for a given traffic load, then the routing protocols (to be considered
scalable) should not break when run over that network of thousands
of nodes with that traffic load. So, basically, routing protocol
scalability means matching (or improving) the network scalability properties.

Respect to your point (3), respect comparing routing protocols scalability,
the answer is not so simple. You need to extrapolate the results to what
will happen when you increase size, mobility, etc.  Measuring
the control packets generated for a routing protocol does not provide enough
information to produce this extrapolation since there are other factor as for
example route sub-optimality that may become more relevant as you increase
traffic and network size. For example, the routing protocol that produces
less control overhead may be forming longer paths than necessary, which
may not be an issue at your current traffic rate, but as the traffic rate increases
the extra hops may be comparable (or greater than) the control overhead.

For this reason, we prefer tackle this scalability issue from a theoretical point.
We develop a framework for studying scalability in ad hoc networks and applied this
framework to the study of several representative protocols in the literature.
The class of networks we studied were bounded-degree with uniformly distributed traffic,
but the methodology can be extended to other type of MANETs.

Hope this helps

Cesar

References:

 C. Santivanez, B. McDonald, I. Stavrakakis, and R. Ramanathan, "On the Scalability of Ad Hoc Routing Protocols," Proceedings of IEEE INFOCOM'02, New York, June, 2002. Available at :
http://www.ir.bbn.com/documents/articles/infocom07.pdf

C. Santivanez, R. Ramanathan, and I. Stavrakakis, "Making Link-State Routing Scale for Ad
Hoc Networks," Proceedings the 2001 ACM International Symposium on Mobile Ad Hoc
Networking & Computing, MobiHOC'2001, Long Beach, California, October 4-5, 2001.
Available at :  http://www.ir.bbn.com/documents/articles/mobihoc01v4.ps

---

From: Cesar Santivanez <[email-masked]>
Date: Wed, 18 Sep 2002 22:00:55 -0400

Dmitri,

Hope this helps

Cesar

References: