Subject: RE: overhead tradeoff between on-demand and generic link state routing protocols

From: Marc Pearlman <[email-masked]>
Date: Wed, 29 Mar 2000 09:10:03 -0500

Hi John,

A little shameless self promotion (but for a good cause:-)...

The Zone Routing Protocol (ZRP) proivdes a hybrid proactive ("all the 
time") / reactive ("on demand") routing framework.  Specifically, each node 
employs a localized version of a proactive routing protocol (eg. a 
localized OSPF) to track the connectivity of a surrounding region (routing 
zone).  This local knowledge is then used to improve the efficiency of a 
*globally reactive* route discovery protocol (eg. AODV, TORA, DSR), by 
guiding route requests to the edge of routing zones.

The ZRP can be configured based on the size (radius, in hops) of each 
node's routing zone.  When a node knows nothing about its surrounding 
topology (or at most, only who its neighbors are), then the ZRP operates in 
a purely reactive mode (AODV, TORA, DSR, etc.).  At the other extreme, when 
the nodes' routing zones are infinitely large, then everyone has access to 
routing information "all the time" (purely proactive) and route discovery 
is not necessary.  In many cases, the "optimal" configuration is somewhere 
between these two extremes.

In general, large population (span), low node mobility and great route 
demand favor larger routing zones (more proactivity).  On the other hand, a 
smaller routing zone radius (more reactivity) is more suitable for smaller 
populations (span), higher node mobility and low route demand.  A more 
thorough discussion/analysis of these trends can be found in:

	M.R. Pearlman and Z.J. Haas, "Determining the Optimal Configuration for 
the Zone Routing Protocol,"
	IEEE JSAC, August 1999.

The important point is that one does not necessarily have to choose, 
all-or-nothing, between a purely reactive protocol (like AODV, DSR, TORA, 
etc.) vs. a purely proactive protocol (OSPF, RIP, WRP, etc.).  There is a 
rich hybrid proactive/reactive middle ground which often provides the best 
results.  Furthermore, hybrid proactive/reactive operation is not the 
exclusive domain of the ZRP.  Many protocols provide exhibit both proactive 
and reactive behavior...  for example ZHLS, CEDAR, IMEP's multipoint relay 
(all locally proactive and globally reactive).  Even TORA, traditionally 
purely reactive, now offers a proactive mode of operation.

regards,

Marc

On Tuesday, March 28, 2000 1:48 PM, John Zavgren [SMTP:[email-masked]] wrote:
> Greetings:
>
>  I have been reading about on-demand routing protocols that are being 
proposed by the manet group.  Is there any analysis that compares this 
class of routing protocol with the class of protocol that maintains routes 
"all the time", i.e., generic link state, or distance vector?
>
> Of course, this comparison would need to be made for carefully chosen 
end-to-end traffic profiles. If there is no traffic being offered to the 
network, then the on-demand protocol will generate no routing update 
traffic. And I suspect that if a uniform, heavy end-to-end traffic load is 
presented to an on-demand routing protocol, the protocol will look pretty 
bad in comparison.
> Thanks
> John Zavgren
> [email-masked]
> 617-873-2280

---

From: Marc Pearlman <[email-masked]>
Date: Wed, 29 Mar 2000 09:20:57 -0500

Disclaimer (re: my previous posting)
... Any similarity between the response of a graduate student and his 
advisor is purely coincidental.  ;-)

regards,

Marc

On Wednesday, March 29, 2000 6:57 AM, Zygmunt Haas 
[SMTP:[email-masked]] wrote:
> Hi John,
>
> Actually, such an analysis should take into the account not only the
> traffic distribution, but the mobility of the nodes as well. Let me
> explain further.
>
> Another way of looking at the issue that you have raised is to see 
whether
> some mix of proactive vs. reactive (on-demand) behavior of the routing
> protocol would be more efficient for a specific network operational 
condition.
> In other words, if the network load is heavy and uniform, proactive 
protocols
> should do better, while when the load is low and highly localized, 
reactive
> protocols should be preferred. In the middle, there is a broad range of
> traffic mixes that would justify some degree of proactivity/reactivity.
>
> You see where I am getting at ... the ZRP is exactly such a protocol. It
> allows to adjust the degree of reactivity/proactivity in the protocol
> behavior based on a single parameter - the Zone Radius (ZR). It has been
> shown that for a highly dynamic network (i.e., high mobility nodes) and
> for low traffic load, small ZR leads to optimal performance - of course
> small ZR corresponds to a purely reactive protocol. On the other hand, 
for
> a stationary, highly loaded network, large ZR is much better, 
corresponding
> to purely proactive behavior.
>
> The ZR is like a "knob" (Joe's analogy (:-)) that allows to adjust the
> behavior of the protocol to the current network conditions (mobility and
> traffic load). More information on the behavior of this "knob" could be
> found in:
> 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
>
> I believe that if there is to be a single (or a small set) of MANET
> routing protocols, some mechanism to adapt to the current network
> conditions (again, traffic load and nodal mobility) is essential, since
> the ad hoc networking environment is so braodly defined.
>
> Cheers,
>
> 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, 28 Mar 2000, John Zavgren wrote:
> >
> > > Greetings:
> > >

---

From: "Pete Sholander" <[email-masked]>
Date: Wed, 29 Mar 2000 10:36:53 -0500

John,

I think that Royer and Toh made a first cut at this trade-study back in the April 1999 issue of IEEE Personal Communications.  The title was "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks".  Although I don't believe that they considered network load in their analysis.

Kind Regards,
Pete Sholander

Scientific Research Corporation		
Atlanta, GA		

E: [email-masked]
V: 770-859-9161, x551

>>> "John Zavgren" <[email-masked]> 03/28/00 01:48PM >>>
Greetings:

 I have been reading about on-demand routing protocols that are being proposed by the manet group.  Is there any analysis that compares this class of routing protocol with the class of protocol that maintains routes "all the time", i.e., generic link state, or distance vector? 

Of course, this comparison would need to be made for carefully chosen end-to-end traffic profiles. If there is no traffic being offered to the network, then the on-demand protocol will generate no routing update traffic. And I suspect that if a uniform, heavy end-to-end traffic load is presented to an on-demand routing protocol, the protocol will look pretty bad in comparison.

Thanks

John Zavgren
[email-masked] 
617-873-2280