Subject: Overhead analysis

From: Laurent Viennot <[email-masked]>
Date: Tue, 27 Jun 2000 14:48:51 +0200 (CEST)

Dear MANet members,

After the discussions on the mailing, we have been thinking quite a
lot with Philippe on overhead. We have developed some analysis about
the relation between routing performance (overhead) and networks
parameters (size, mobility, traffic). Our aim is to identify the
scenarios which favor such and such MANet protocols. We consider a
mobile ad-hoc network with N nodes (N assumed large, say N>50 nodes).

We have identified two classes of protocols which more or less fit
the reactive and proactive boundary:

1. the flooding protocols (AODV/DSR, TORA)
2. the hello protocols (DSDV,OLSR)

The performance are quantified by the quantity of overhead generated
by each protocols. We have identified two source of overheads:

A. the control overheads
B. the route overheads

Our main findings are the following:

-Both classes have O(N^2) control overheads which is no surprising
from graph theory point of view. Flooding algorithm and hello
algorithm have different factors in front of N^2 which actually
depends on traffic, geometry, mobility. One can find scenarios in
favor of flooding and other scenarios in favor of hello.

-Flooding protocols may not provide optimal routes (in term of hop
number) the average deviation between optimal routes can be
significant (a factor of 33% in dense 1D networks, more in 2D and
3D). The overhead generated by the extra transmission of data may be
important since it is proportional to data traffic.

A research report detailing these results is available:
http://menetou.inria.fr/~viennot/postscripts/overhead.ps.gz (166 Kb)

Comments are welcome,

Laurent

---

From: Zygmunt Haas <[email-masked]>
Date: Fri, 30 Jun 2000 07:47:45 -0400 (EDT)

Hi Laurent,

There is another "class" of protocols, the hybrid class, which is a mix of
proactive-reactive behavior. Examples of such protocols include the Zone
Routing Protocol (ZRP) and the Fisheye protocol. 

As you have stated, pure proactive/reactive protocols may not present
"optimal" performance for a specific network operational conditions
(mobility and traffic). The bigest advantage of the hybrid class is that
it can adapt itself to the network operational conditions. More
specifically, by dynamically adjusting the ratio of the proactive
vs. reactive behavior, the amount of overhead control traffic can be
*drastically* reduced. In the Zone Routing Protocol, this is achieved
through the use of a single parameter - the Zone Radius, which is updated
based on continual measurement of the mobility (the rate of
creation/destruction of links with a node's neighbors) and the amout of
traffic a node sees. (More on updating of the zone radius could be found
in our paper in JSAC / August 1999.)

I guess, what I am trying to say is that the hybrid class of protocols is
the answer to the conclusions of your study - that in order to "cover" a
broad range of MANET topologies (size of networks) and operational
conditions, a *hybrid* strategy should be used.

Zygmunt.
==--==-===
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    tel: +1-607-255-3454
Wireless Networks Laboratory		                  
School of Electrical Engineering         fax: +1-607-255-9072 
Cornell University
323 Frank Rhodes Hall			 e-mail: [email-masked]
Ithaca, NY 14853			 
U.S.A                             http://www.ee.cornell.edu/~haas/wnl.html
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-