Subject: On Demand Flaw

From: Kevin Grace <[email-masked]>
Date: Thu, 06 Jul 2000 18:04:06 -0400

In reflecting upon the behavior of the on demand routing protocols, I
made a very disturbing observation. I don't believe that I have seen
anyone discuss this issue before, so I submit it now to alert
others. 

The motivation behind the on demand routing protocols was to increase
scalability by not having to distribute topology information like
traditional routing protocols. In the on demand approach, when a
source has a packet to send to a destination for which it does not
have a route, the source initiates a flooded route
request. Unfortunately, if the intended destination is disconnected
from the network, the flooded route request propagates across the
entire network but produces no useful result. Even worse, since the
source never discovers a route, it is forced to try flooding another
route request again later which will continue to waste resources as
long as the destination is disconnected.

The problem here is that the source has no way of determining what
nodes are disconnected from the network. This is exactly why topology
information is useful! A link state protocol would consume no
additional resources for a disconnected destination since the source
would know that there was no route.

Consider now that the network has one well known server that all the
other nodes try to connect to, and the server happens to be
disconnected. The number of messages sent as part of the unsuccessful
flooded route requests are enough to distribute the entire network
topology to every node! At this point a link state algorithm would be
superior to the on demand protocol. In fact, the resources consumed
and wasted by the on demand routing protocol grows linearly with the
number of disconnected well known servers. Eg. a network with 3
disconnected well known servers would cause an on demand protocol to
consume and waste 3 times the resources of a link state protocol.

It appears to me that the on demand routing protocols have a fatal flaw
which preclude them from scaling well and that the link state approach
is superior.

*********************************************************
Kevin H. Grace
The MITRE Corporation
202 Burlington Rd
Bedford, MA  01730
(781) 271-8388
[email-masked]

---

From: Zygmunt Haas <[email-masked]>
Date: Thu, 6 Jul 2000 20:08:58 -0400 (EDT)

Hi Kevin,

> which preclude them from scaling well and that the link state approach

I am not for on-demand protocols, you know, just hybrid protocols (:-) ...
However, I would like to comment on your observation. You are right in
saying that on-demand may be costly, but everything is relative and
depends on the two parameters that I have mentioned in my previous e-mail.

Say, you have a network with very little activity, say, one message per
day. But the network reconfigures very often, say a link lifetime is on
the order of 100 [msec]. Would you still prefer the "link state" approach -
obviously not, since even if you need to flood the network hundred of
times to discover the one-per-day route request in the reactive (on
demand) approach, you still will be much better off then the very frequent
link (on the order of 10 [updates/sec]) exchanges in the proactive state.

So, again, the ratio of how much proactive/reactive a protocol should be
depends on the two parameters:
	1. mobility, and 
	2. activity 
s per my prsvious e-mail.

Best,

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: Jyoti Raju <[email-masked]>
Date: Thu, 6 Jul 2000 19:29:07 -0700 (PDT)

We presented a discussion of this problem, which we called
"searching to infinity" in our paper
"A New Approach to On-demand Loop-Free Multipath Routing"
presented at IEEE IC3N 99. We also presented an
on-demand protocol (ROAM) based on diffusing computations that would
not suffer from the problem. ROAM requires reliable updates. It can be
efficiently implemented if  the MAC protocol allows reliable updates.
Adding reliability at the network layer will result in increased control
overhead.
 
Your observation is right; table-driven routing protocols
(distance vector or link state) will not suffer from this problem.
 
Jyoti Raju
Graduate Student Researcher
Computer Communications Research Group
UC-Santa Cruz

---

From: "Kevin H. Grace" <[email-masked]>
Date: Fri, 07 Jul 2000 13:01:55 -0400

Hi Laura,

I hope the example has not obfuscated my observation. My hope was to
simply illustrate that the resources wasted by flooded route requests to
disconnected destination can quickly grow to a level where a link state
approach would have been more efficient.

> You raise interesting questions, but I'm not sure I accept your
> example.
> 
> Why would you choose to have a well-known server, rather than a
> replicated service, in a wireless network that is subject to frequent
> partitions?
> 
> Even if your application is built around connectivity to a particular
> host (e.g. physical apparatus), you might still be better off with an
> higher-level protocol that provides notification of an essential
> host's status.
> 
> Regards,
> Laura

---

From: Laura Feeney <[email-masked]>
Date: Fri, 7 Jul 2000 18:30:16 +0200

>>>>> Kevin Grace <[email-masked]> writes:

Kevin> Consider now that the network has one well known server that
Kevin> all the other nodes try to connect to, and the server happens
Kevin> to be disconnected. The number of messages sent as part of the
[...]
Kevin> fact, the resources consumed and wasted by the on demand
Kevin> routing protocol grows linearly with the number of disconnected
Kevin> well known servers. Eg. a network with 3 disconnected well
[...]

Hi Kevin, 

Regards,
Laura

-- 
Laura Marie Feeney				[email-masked]
Visiting Researcher				http://www.sics.se/
Computer and Network Architectures Lab	 	Tel: +46 8 633 15 09 
Swedish Institute of Computer Science		Mobile: +46 70 246 56 63     
Box 1263, SE-164 29 KISTA, SWEDEN		Fax: +46 8 751 72 30

---

From: Laurent Viennot <[email-masked]>
Date: Mon, 10 Jul 2000 15:19:25 +0200 (CEST)

Hi Kevin,

The analysis I have mentionned in a previous mail shows that all
protocols include at least a O(N^2) control overhead where N is the
number of nodes. This is not surprising since the topology of a radio
network is certainly proportional to O(N^2) (imagine for example an
IETF meeting room). If you call scalable a protocol that has a cost
proportional to the size of the topology, you should not be alarmed by
what you call the on demand flaw...

laurent

---

From: Laurent Viennot <[email-masked]>
Date: Mon, 10 Jul 2000 16:32:20 +0200 (CEST)

With such a heavy traffic, you'd rather consider a pro-active protocol
like OLSR. 

You can model the traffic with the average number a of active routes
per node. Simulations I have read often suppose a<1. If you consider
the connections you initiate with your own computer in an every day
use, you wouldn't expect a to be greater than 2 or 3.

However there may be some applications producing such traffics. If you
know some serious examples, I am curious to know them.

laurent

Kevin Grace writes:
 > Hi Laurent,
 > 
 > >> If you call scalable a protocol that has a cost
 > The problem is that on-demand protocols can actually have an overhead
 > of O(N^3). This is much worse than the overhead of a link state
 > protocol which is O(N^2).
 > 
 > To see why an on-demand protocol has an overhead of O(N^3) consider a
 > network of N nodes in which every node communicates to every other
 > node. Now consider that the network is severed into two halves, each
 > with N/2 nodes. Each node in a partition now sends flooded route
 > requests for N/2 disconnected destinations resulting in N/2 * N/2
 > flooded route requests and since each flood consumes N/2
 > transmissions, the total resources consumed is O(N^3).
 > 
 > It still appears to me that on-demand protocols have a fatal flaw that
 > precludes them from scaling well.
 > 
 > Laurent Viennot wrote:

---

From: Kevin Grace <[email-masked]>
Date: Mon, 10 Jul 2000 12:14:41 -0400

Oops...I failed to address this to the group previously.

Hi Laurent,

---

From: Kevin Grace <[email-masked]>
Date: Mon, 10 Jul 2000 14:03:20 -0400

Hi Laurent,

> With such a heavy traffic, you'd rather consider a pro-active protocol

The flaw with on-demand protocols is independent of traffic
models. Any disconnected destination node results in a wasteful
sequence of flooded route requests. As soon as there are N route
requests for disconnected destination(s), regardless of how the
requests are distributed across source(s) and destination(s), the
amount of wasted resources exceeds that necessary to distribute
topology information to every node. 

> use, you wouldn't expect a to be greater than 2 or 3.

I would think 2 or 3 routes per computer would be more than enough to
result in N route requests for disconnected destinations. Suppose one
route on every computer was for a DNS server that became
disconnected...that would be sufficient to make the link state
approach more efficient than the on-demand approach.

We know for a link state protocol that its worst case and average case
overhead are both O(N^2). We also know that for on-demand protocols,
worst case overhead is O(N^3) though we don't know what its average
case overhead is. But, we do know that as soon as an on-demand
protocol has N route requests for disconnected destinations, its
overhead exceeds that of link state. 

Regardless of average case overhead, the more scalable routing
approach is the one with the lower worst case overhead: link state.
Also, the advantage of using a link state approach is that we can know
ahead of time for a given network size, whether the network will have
enough capacity to disseminate routing information. Contrast this to
the on-demand approach where we don't know the amount of overhead it
will generate apriori even when we know the traffic model (who talks
to whom) since we don't know which nodes will become disconnected.

-- 
Kevin Grace          The MITRE Corporation 
781-271-8388         202 Burlington Rd
[email-masked]     Bedford MA, 01730

---

From: "M. Scott Corson" <[email-masked]>
Date: Mon, 10 Jul 2000 17:00:43 -0400

>which preclude them from scaling well and that the link state approach

The behavior you mention is (or can be) true for on-demand protocols that
utilize memoryless, non-suppressed query/route-request mechanisms,
depending on application behavior.  Assuming rather worst-case application
behavior (e.g. a frustrated surfer continuously issuing HTTP
requests--translated into route requests--for a mobile server currently
disconnected), the amount of flooding traffic could indeed be large.  This
is not such an issue for small ad hoc nets, but becomes a consideration for
those attempting to build larger ones.

The following is NOT intended to be a shameless plug ;-), just an example
of a protocol using suppression.  If others know of any, please contribute
as well.

A little known feature of TORA is its approach to query suppression during
route discovery.  When a node issues a query for a destination, it is
flooded throughout the network.  Nodes that receive and process the query
_remember_ this fact by setting a Route-Requested (RR) flag for the given
destination. Thus the query process is not memoryless.  It is
destination-oriented and independent of the source node issuing the query.
When a new link appears with a neighbor at a node with its RR flag set, it
transmits a query for that destination to the neighbor.  Thus the query
propagates like a virus, and is rather similar to the epidemic routing
concept, and some forms of reliable persistent flooding.  The current
specification states that a node retains its memory of the query
indefinitely so that, in effect, once issued a query is active forever.  We
are amending this behavior so that the time a RR flag remains set is
configurable (perhaps 30 seconds or so), we've not yet chosen a figure.
After this time the RR flag settings time out.  Nodes with RR flags set do
not generate new querys for the same destination, so the mechanism
suppresses multiple query floods and the behavior you mentioned does not
occur.  We are also adding an approach for query localization that can be
turned on if desired, and are sorting this out in the simulator as well.

I also do not think it is difficult to add memory/suppression behaviors to
other on-demand algorithms, so the on-demand vs. proactive debate will
likely continue.

-scott

---

From: Kevin Grace <[email-masked]>
Date: Tue, 11 Jul 2000 08:18:52 -0400

Hi Scott,

> We are amending this behavior so that the time a RR flag remains set
> is configurable (perhaps 30 seconds or so), we've not yet chosen a
> figure.  After this time the RR flag settings time out.
> Nodes with RR flags set do not generate new querys for the same
> destination, so the mechanism suppresses multiple query floods and the
> behavior you mentioned does not occur.

Hmmm...this appears to make an on-demand protocol much more vulnerable
to lost route requests and route replies. If a route request or route
reply is lost, the source is prevented from trying to reinitiate a
route discovery until the "configurable" time expires. You have, like
a previous poster, made the decision that efficiency is more important
than delay. I don't believe this is a desirable property for messages
that are time sensitive.  

Again, the underlying problem here is that for on-demand protocols, a
node does not know which nodes are disconnected from the network. To
overcome this problem, which is a direct result of the decision not to
distribute topology information, a node must occasionally retry the
route request. This results in the protocol designer being forced to
choose whether efficiency or delay is more important. I think it more
wise to avoid this dilemma altogether and distribute topology
information.

Regards,
-Kevin

---

From: "Vincent D. Park" <[email-masked]>
Date: Tue, 11 Jul 2000 10:22:26 -0400

>than delay. I don't believe this is a desirable property for messages

Kevin,

I think that any proactive routing protocol would be equally vulnerable to
lost control packets. Loss of routing updates or link-state advertisements
can result in an inability to route to certain destinations or worse (e.g.,
routing table loops). You are correct that a more persistent route request
approach leads to a robustness issue, thus the need for at least a long
term periodic refresh, but this is not unlike the need to periodically
refresh  routing updates in almost any proactive approach. As in any
protocol design the balance between the amount persistence in the route
request and the frequency of the refresh is an engineering tradeoff.

>choose whether efficiency or delay is more important.

I disagree. Under reasonable operating conditions (i.e., packet loss rates
tolerable by a proactive routing protocol design), the use of a persistent
route request approach will minimize the delay. 

 I think it more
>wise to avoid this dilemma altogether and distribute topology

I think you will find it difficult to convince many that both on-demand and
proactive routing approaches don't have their place. Most of the discussion
on the mailing list lately seems to support the notion that each has a
region of applicability.

-Vince

>> other on-demand algorithms, so the on-demand vs. proactive debate will

 Vincent D. Park                     Email: [email-masked]
 Information Technology Division     Voice: 202.767.5098
 Naval Research Laboratory           Fax: 202.767.1191
 4555 Overlook Avenue SW        
 Washington, DC 20375-5000

---

From: Kevin Grace <[email-masked]>
Date: Tue, 11 Jul 2000 10:44:46 -0400

Hi Vincent,

>route request approach will minimize the delay. 

It appears to me that lost route requests or route replies will result
in 1) no route being returned and 2) the network blocking a subsequent
route request until the "configurable" time expires. After this time
expires, another route request may be initiated which may again get
lost. This leads to an increase in delay...not a minimization.

>on the mailing list lately seems to support the notion that each has a

My intention is only to point out that there is a problem that
disconnected destinations create and I don't see a solution that is
efficient and minimizes delay. 

-Kevin

---

From: "M. Scott Corson" <[email-masked]>
Date: Tue, 11 Jul 2000 11:34:21 -0400

>than delay. I don't believe this is a desirable property for messages

Not really Kevin, but you have to look at TORA a bit more closely to
understand the way the RR flag interacts route discovery and construction,
the way TORA reliably sends about routing objects and other things.  In
short, while the RR flag is set, nodes will immediately detect reconnection
to a previously partitioned destination and routes will be built at
once...TORA's on-demand mode is actually a bit more proactive than some
other on-demand algorithms.

-scott

---

From: Kevin Grace <[email-masked]>
Date: Tue, 11 Jul 2000 11:39:10 -0400

>So, when new link rejoins two previously partitioned portions of a network
>and the proactive routing protocol advertisement regarding the new link is
>lost. How long will 1) no routes between the previously partitioned
>portions be unavailable and 2) subsequent route requests?/repairs? be
>blocked. ;^)
>
>-Vince

Answers:

1) As I think you know, it depends upon the rate at which Link State
Packets are sourced and relayed. The nice thing is that if we know
apriori the maximum size of the network and the expected packet error
and data rates of the links, we can knowingly tune this rate to
provide whatever tradeoff of efficiency and delay we'd like. Contrast
this to the on-demand approach where there is no way of predicting
overhead.

2) Hmmm...you do know that there are no route requests in a link state
protocol, yes?

-Kevin

"Vincent D. Park" wrote:
> 
> At 10:44 AM 7/11/00 -0400, Kevin Grace wrote:
> >Hi Vincent,
> >
> So, when new link rejoins two previously partitioned portions of a network
> and the proactive routing protocol advertisement regarding the new link is
> lost. How long will 1) no routes between the previously partitioned
> portions be unavailable and 2) subsequent route requests?/repairs? be
> blocked. ;^)
> 
> -Vince
>

---

From: "Vincent D. Park" <[email-masked]>
Date: Tue, 11 Jul 2000 11:14:26 -0400

-Vince