Subject: Re: On Demand Flaw

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

hi Kevin

  >> From [email-masked] Mon Jul 10 13:35:29 2000
  >> From: Kevin Grace <[email-masked]>
  ...
  >> 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.

Your conclusion may very well be right in certain situations - personally,
I do not believe any one approach is going to be a winner in all realistic
environments (as characterized by mobility patterns, traffic patterns,
performance metrics, capabilities of the mobile nodes, etc.).
Trying to prove such a conclusion in general is probably futile.

Unless I am missing something, the above analysis ignores time between
route discoveries performed by an on-demand protocol. For the
sake of argument, suppose that a minimum time interval of T is
enforced on consecutive route discoveries by a given node, with tau
being the time between link state updates transmitted by a node using
a link state protocol.

The results of your analysis could change depending on the
relationship between T and tau - for instance, what if T/tau > N ?

Note that with exponential backoff schemes, the time between route
discoveries can be increased very rapidly, particularly in the case
of partitions (i.e., a backoff scheme would tend to make T large).

I am not suggesting that on-demand is going to be the method
of choice in general.

The devil is in the details.

Cheerio.

- nitin

  >> 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 H. Grace
  >>  The MITRE Corporation
  >>  202 Burlington Rd
  >>  Bedford, MA  01730
  >>  (781) 271-8388
  >>  [email-masked]
  >>  
  >> 
  >> Laurent Viennot wrote:
  >> > 
  >> > 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
  >> >  > >> proportional to the size of the topology, you should not be alarmed by
  >> >  > >> what you call the on demand flaw...
  >> >  >
  >> >  > 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.
  >> >  >
  >> >  > *********************************************************
  >> >  >  Kevin H. Grace
  >> >  >  The MITRE Corporation
  >> >  >  202 Burlington Rd
  >> >  >  Bedford, MA  01730
  >> >  >  (781) 271-8388
  >> >  >  [email-masked]
  >> >  >
  >> >  >
  >> >  >
  >> >  > Laurent Viennot wrote:
  >> >  > >
  >> >  > > 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
  >> >  > >
  >> >  >
  >> 
  >> -- 
  >> Kevin Grace          The MITRE Corporation 
  >> 781-271-8388         202 Burlington Rd
  >> [email-masked]     Bedford MA, 01730
  >> 
  >>

---

From: Ravi Prakash <[email-masked]>
Date: Mon, 10 Jul 2000 15:24:53 -0500 (CDT)

The on-demand routing protocols that I am aware of (namely AODV and
DSR) rely on route caches to limit the number of route discoveries. 

However, based on some simple experiments we conducted we realized that
the time for which a route stays valid is quite small, and this
duration gets smaller as the network scales. 

So, route caching does not seem to scale well, and may have a benefit only
if a source has to send a large number of packets in a short time
immediately after route discovery. 

As the network size and diameter grow, in my opinion the following will
happen:

1. Proactive protocols will have to increase the frequency of route
updates, thus incurring higher overheads.

2. Reactive/on demand protocols like AODV and DSR will have to reduce
their cache-lifetimes, thus also increasing their route discovery
messages.

Relying on the simulation results obtained using ns-2 to advocate the
strengths of one's favorite protocol is risky because the propagation
model in ns-2 is very simplistic. The achievable data rate and link
stability will be far lower than what ns-2 tells us. 

Perhaps, this is why DOE's experiments with networks of 50 nodes have been
far less than satisfactory.

So, rather than trying to determine the strengths of one over the other,
we need to be really worried about the lack of scalability that affects
both. 

Just my humble opinion,

----Ravi.
========================================================================
Ravi Prakash ([email-masked])		www.utdallas.edu/~ravip
Department of Computer Science
The University of Texas at Dallas
Richardson, TX 75083-0688.  Phone: (972) 883-2289,   Fax: (972) 883-2349

---

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

Hi Nitin,

> of partitions (i.e., a backoff scheme would tend to make T large).

An exponential backoff will indeed reduce overhead but at the cost of
increasing the delay in discovering a route to a recently reconnected
node. As the protocol designer, you have now consciously made the
choice that efficiency is more important than delay and imposed a "one
size fits all" treatment of the bits. Not all bits are the same,
however, and a time sensitive message may now be delayed significantly
for the sake of efficiency. As a network user, I don't think I'd like
this behavior when I wanted to send a "I need help now!" message.

> I am not suggesting that on-demand is going to be the method

Agreed!

Regards,
-Kevin