Subject: RE: Overhead analysis

From: "Groten, D." <[email-masked]>
Date: Thu, 06 Jul 2000 15:40:59 +0100

Hi Philippe and Laurent,

I have a reaction on your paper concerning the terminology you use: on the
one hand, we can distinguish between on-demand (reactive) and table-driven
(proactive) protocols. On the other hand, you have identified the first
category as "flooding", and the second category as "hello". I find this
quite confusing: both types of protocols flood routing information over the
network. And while "hello"-type neighbour discovery is mandatory in a
table-driven protocol, it may also be used in an on-demand protocol in order
to establish and repair routes more quickly.

Of course, strictly speaking, a purely on-demand protocol cannot use
"hellos" because such neighbour discovery is performed pro-actively. But
from the point-of-view of the general concept, the distinction between
on-demand (end-to-end routes are only found when necessary) and pro-active
(end-to-end routes always available) is more easy to grasp than that between
hello and flooding.

I have two questions:
1. Am I correct when concluding that your analysis is based  purely on the
extreme case where on-demand actually is equivalent to flooding of the
entire network (no hellos to help)?
2. Is the combination of a simple neighbour discovery (via pro-active
hellos) and on-demand route discovery equivalent to ZRP with zone radius 1? 

Regards,
Dirk.

------------------------------------------------------------------
Dirk Groten	      	       KPNResearch		
------------------------------------------------------------------	
P. O. Box 421		       Tel: +31 6 53747220
2260 AK Leidschendam	      Fax: +31 70 3326477
The Netherlands	              E-mail: mailto:[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: maandag 3 juli 2000 18:29
To: Zygmunt Haas
Cc: Laurent Viennot; [email-masked]
Subject: Re: Overhead analysis

Dear Zygmunt,

I feel uncomfortable to talk about ZRP because it does not specify the link
state algorithm it uses for intra-zone routing. If you use non-optimized
OSPF link state, then I will agree with your plot, but if you use another
optimized link state, like OLSR for example, you will obtain a completely
different plot. 

As we see in our study, the leading overhead in OLSR is in the hello
transmissions. Therefore ZRP implemented on OLSR will likely do worse than
OLSR or flooding protocols as soon ZR is greater than 1 and smaller than
infinity, because ZRP would include both hellos cost for intra-zone and
flooding cost for inter-zone. We also expect that ZRP on OSPF will do worse
than ZRP on OLSR. 

For example, I would expect a plot like this one, which depends on traffic
scenarios, mobility, etc... But I am not sure at 100 %, it needs more work
and we prefer to skip this in our first version.

total traffic ZRP on OLSR
	^
	|
	|                      
	|      * * * * * 
	|   *             *
	|  *                *
	|             
	| *                  *
	|        
	|       
	|
	---|------------------|-----> Zone Radius
            the optimal ZR

Best regards,
Philippe

PS: Laurent will come back soon, I will not able to continue this
interesting discussion because I leave for a one week travel. 

A 10:48 03/07/00 -0400, Zygmunt Haas a écrit :
>Hi Philippe,
>
>Hmmm, this is not so. Hybrid protocols, through their ability to adjust to
>the network operational conditions will *always* result in less control
>traffic than pure proactive or pure reactive protocols. This statement is
>nearly self-explanatory, as *hyrbrid protocols degrade to either pure
>reactive or pure proactive behavior, based on their parameter settings.*
>
>Let me comment on the last statement: in the Zone Routing Protocol (ZRP),
>for instance, there is a single parameter to set - the Zone Radius
>(ZR). If ZR=1, then ZRP degrades to pure reactice protocol, while when
>ZR=\infty, then ZRP degrades to pure proactive protocol. The
>characteristic curves of ZRP look as follows: (see for instance the
>paper: [M.R. Pearlman and Z.J. Haas, "Determining the Optimal Configuration

>of for the Zone Routing Protocol," IEEE JSAC, special issue on Ad-Hoc 
>Networks, vol. 17, no.8, August 1999])
>
>
>total traffic
>	^
>	|*
>	| *                     *
>	|  *                 *
>	|   *              *
>	|   *            *
>	|    *         *
>	|     *      *
>	|      *   *
>	|       ***
>	|
>	---------|--------------> Zone Radius
>            the optimal ZR
>
>The protocol should dynamically adjust the ZR, so as to minimize the total
>control traffic. Depending on the operational conditions of the network,
>the reduction of the hybrid scheme can be "quite dramatic" - please see
>the above paper for more quantitative results.
>
>Thus, repeating myself, the hybrid protocols yield *much* reduction in the
>control traffic and are a natural choice in an environment with changing
>operational conditions, as well as for a broad range of MANETs.
>
>Congratulations to Laurent on his new baby !
>
>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
>~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
>On Mon, 3 Jul 2000 [email-masked] wrote:
>
>> Hi, Zygmunt,
>> 
>> It is not exactly the conclusion of our study. It looks like that hybrid
>> protocol overheads are roughly the sum of flooding protocol overheads and
>> hello protocol overheads. They would be very likely always above. This is
>> the reason why we a priori prefered not to include it in the first
version
>> of our study.
>> 
>> Philippe and Laurent
>> 
>> PS: Laurent just got a baby yesterday, so I replace him on the spot.
>> 
>> A 07:47 30/06/00 -0400, Zygmunt Haas a écrit :
>> >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
>>
>~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
>> >
>> >On Tue, 27 Jun 2000, Laurent Viennot wrote:
>> >
>> >> 
>> >> 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: Marc Pearlman <[email-masked]>
Date: Fri, 7 Jul 2000 16:02:35 -0400

Hi Dirk,

> hellos) and on-demand route discovery equivalent to ZRP with zone radius 
1?

Yes.

Technically speaking, a purely reactive ZRP configuration would correspond 
to a zone radius == 0 hops.  In such a case, there is no neighbor discovery 
and route requests (RREQs) are distributed via unreliable shared-channel 
neighbor broadcast.

Sometimes, unreliable shared channel neighbor broadcast is not advisable 
(due to low success rate) or even available (in a multiple channel system). 
 In these situations, neighbor discovery is needed, either to track 
neighbor ACKs from a *reliable* neighbor broadcast or to resolve the 
neighbor broadcast into individual unicasts to each neighbor.  If this 
neighbor information is provided to the ZRP, then the zone radius will be 
== 1 hop

Within this context, we sometimes refer to a zone radius == 1 as being 
purely reactive.  What we really mean is that this is the *most reactive* 
configuration possible, given that neighbor discovery is already present to 
support other networking services.

regards,

Marc

============================================================
Marc R. Pearlman		             tel: (607) 255-0236
Wireless Networks Laboratory         fax: (607) 255-9072
School of Electrical Engineering
Cornell University                   [email-masked]
389 Frank Rhodes Hall                www.ee.cornell.edu/~pearlman
Ithaca, NY 14853

---

From: Laurent Viennot <[email-masked]>
Date: Mon, 10 Jul 2000 14:38:58 +0200 (CEST)

Hi Dirk,

A word about our terminology:

We call flooding protocols, protocols that construct routes by
flooding like AODV.

We call hello protocols those that discover the topology by
neighborhood hellos (hellos containing lists of neighbors) and that
use the knowledge of the topology to optimize broadcasting like OLSR
(see the nice properties of multi-point relay sets).

This can be seen as a refinement of the reactive/pro-active
classification. We have chosen a different terminology to insist on a
classification according to the way routes are constructed.

 > entire network (no hellos to help)?

No.

 > hellos) and on-demand route discovery equivalent to ZRP with zone radius 1? 

I guess yes, Zygmunt is the right person for answering that.

---

From: Nitin H Vaidya <[email-masked]>
Date: Mon, 10 Jul 2000 09:10:27 -0500 (CDT)

hi Laurent

  >> From: Laurent Viennot <[email-masked]>
  ...
  >> If planar coordinates are available to each node, what about limiting
  >> the flooding to an even narrower area, for example a rectangle
  >> containing the source and the estimated position of the destination ?
  >> Do you have some hints about such ideas ?

Yes ... you might want to take a look at the paper on
Location-Aided Routing from the 1998 MobiCom, Dallas.

- nitin

---

From: Nitin H Vaidya <[email-masked]>
Date: Mon, 10 Jul 2000 10:57:03 -0500 (CDT)

>> > Do you have some hints about such ideas ?

By the way, also take a look at the Query Localization scheme
from 1999 MobiCom by Castaneda & Das. That scheme
also limits route discovery to a small region (as does
Location-Aided Routing LAR), but without using physical
location information (unlike LAR).

Cheerio.

- nitin

---

From: Marc Pearlman <[email-masked]>
Date: Fri, 14 Jul 2000 15:25:26 -0400

Hi Philippe,

> In summary we obtain for Z_R>0
>  ZRP over DSDV: h*N+tau*N+mu*N^2*a*L*(1-Z_R/L)/Z_R+beta*mu*N^2*Z_R/L
>  ZRP over OLSR: h*N+4*tau*N*Z_R+mu*N^2*a*L*(1-Z_R/L)/Z_R+4*mu*N*Z_R

First of all, thank you for taking the time to extend your protocol 
analyses to the ZRP framework.  I've looked over your ZRP traffic equations 
for the 1-D narrow strip, and they look fine to me.  Your results seem to 
support the assertions that we've made thus far about the ZRP.

Decomposing your final traffic equations into their respective proactive 
and reactive components, we have:

			reactive 				proactive
DSDV		mu*N^2*a*L*(1-Z_R/L)/Z_R		h*N + tau*N + beta*mu*N^2*Z_R/L

OLSR		mu*N^2*a*L*(1-Z_R/L)/Z_R		h*N + 4*tau*N*Z_R + 4*mu*N*Z_R

For the DSDV and OLSR implementations of IARP, the reactive (IERP) traffic 
is identical, and of the form C*(1/Z_R) - B.  The DSDV and OLSR 
implementations of IARP generate different amounts of proactive traffic, 
but both expressions take on the form A*(Z_R)+ B.

Thus, the total ZRP traffic takes on the form A*(Z_R) + B + C*(1/Z_R).  A 
and C are positive, B may be positive or negative.

(Please excuse my reuse of the coefficients A,B,C.  They're just intended 
to serve as place holders)

If you plot the equation A*(Z_R) + B + C*(1/Z_R), you'll *always* end up 
with a convex ("U-shaped") curve.  Depending on the actual values of A,B 
and C, you may only get the increasing or decreasing section of the "U". 
 An example of this is your ZRP/OLSR curve.

> ^ZRP/OLSR
 > 	|
 > 	| *
 > 	|   *
 > 	|     *
 > 	|       *
 > 	|         *
 > 	|           *
 > 	|             *
 > 	|               *
 > 	|                 *
 > 	-------------------|----> Zone Radius
 >             the optimal ZR

The fact that your curve is strictly decreasing is due to your assumption 
of large N.

> For OLSR the optimal Z_R is the closest value between 1 and L to 
sqrt(a*N*mu*L/(tau+mu)). When N increases,
> this value will be likely be L. Therefore the optimal ZRP will act as a 
pure proactive scheme.

As N decreases, the optimal zone radius may be smaller than L, indicating 
that a hybrid approach outperforms purely proactive routing.

The important point to walk away with here is that the ZRP/DSDV and 
ZRP/OLSR curves aren't really shaped so differently.  They both belong to 
the family of convex (U-shaped) curves.  Given that OLSR is a very 
efficient proactive protocol, it seems reasonable to expect that *any* IARP 
implementation will produce a convex (U-shaped) traffic curve.

regards,

Marc