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

From: "John Zavgren" <[email-masked]>
Date: Tue, 28 Mar 2000 13:48:23 -0500

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: "M. Scott Corson" <[email-masked]>
Date: Tue, 28 Mar 2000 20:36:26 -0500 (EST)

On Tue, 28 Mar 2000, John Zavgren wrote:

John,

Am not aware of any published results yet, but i think there are efforts
underway in this direction.

As for your conjecture that on-demand will perform porrly relative to
a proactive protocol in uniform, heavy load, this is not at all clear.
On-demand and proactive protocols come in diferent flavors.
More or less, on-demand protocols strive to put routing state only 
where it is needed.  On balance, whether this si more or less efficient 
than, for example, managed link state distribution needs to be determined
for various on-demand approaches.

-scott

> 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…

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************

---

From: Zygmunt Haas <[email-masked]>
Date: Wed, 29 Mar 2000 06:56:51 -0500 (EST)

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
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

---

From: Laurent Viennot <[email-masked]>
Date: Thu, 30 Mar 2000 03:37:10 +0200 (CEST)

Both pro-active and reactive protocols have significant traffic
control overhead to discover routes.

I see basically two approaches that differ by their main contribution
to traffic control :
- protocols that find routes by flooding (AODV, DSR, TORA, ...)
- protocols that discover topology with hellos (OLSR, STAR, ZRP, ...)

Another source of overhead is the use non-optimal routes. 

Concerning analytical models about overheads, you can also consult the
technical report by Jacquet and Laouiti "Analysis of mobile ad-hoc
routing protocols in random graph models".

Url : ftp://ftp.inria.fr/INRIA/tech-reports/RR/RR-3835.ps.gz

laurent

---

From: Fredrik Alriksson <[email-masked]>
Date: Thu, 30 Mar 2000 14:01:18 +0200

Hi John,
              actually, a paper presented at MobiCom'99 compares AODV, DSR, and DSDV in different scenarios. It is called "Scenario-Based Performance Analysis of Routing Protocols for Mobile Ad-Hoc Networks" and written by Per Johansson et.al.

There is also a paper by Josh Broch et.al., "A performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols", from MobiCom'98 that you might want to check out.

Regards,

    Fredrik Alriksson

---

From: Jose Garcia-Luna <[email-masked]>
Date: Thu, 30 Mar 2000 12:32:06 -0800

It appears that you are oversimplifying the way in which STAR works.
STAR does not use HELLOs.

JJ

---

From: Laurent Viennot <[email-masked]>
Date: Fri, 31 Mar 2000 03:29:17 +0200 (CEST)

I may have misunderstood how works your underlying neighbour protocol.
Don't you need periodic beaconing ? 

laurent

---

From: Jose Garcia-Luna <[email-masked]>
Date: Thu, 30 Mar 2000 20:56:39 -0800

nope!
JJ