Subject: Re: On Demand Flaw

From: "Pete Sholander" <[email-masked]>
Date: Fri, 07 Jul 2000 17:13:05 -0400

Greetings!

It's been well known (since the mid-90's) that OSPF simply fails in MANETs, while my U.S. DoD contacts claim that NTDR's improvements on OSPF start to perform poorly at about 50 nodes in their testbed networks.  Anyone else have any recent data-points from real, deployed networks ... as opposed to theoretical results or simulation studies?  It seems like TORA (or maybe OLSR) should have some real-life numbers by now ... although maybe not over the "realistic terrain" (hills, foliage, jarheads in foxholes, ...) found in DoD exercises.

Regards,
Pete Sholander

Scientific Research Corporation 
2300 Windy Ridge Parkway, Suite 400S
Atlanta, GA  30339

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

>>> "Kevin H. Grace" <[email-masked]> 07/07/00 01:01PM >>>
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.

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

> 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: Nitin H Vaidya <[email-masked]>
Date: Tue, 11 Jul 2000 09:14:13 -0500 (CDT)

>> From [email-masked] Tue Jul 11 07:00:10 2000
  >> 
  >> Hi Nitin,
  >> 
  >> > 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).
  >> 
  >> 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

Indeed true, although I made that choice only for the
sake of illustration.

Like I said earlier, we have too many variables to deal
with, including mobility patterns, traffic patterns,
performance metrics, capabilities of the mobile nodes, etc.
Delay falls in the "performance metrics" category.

My point was that it is not possible to claim that one scheme is
more scalable than another one without defining all of the above,
including whether you care about delay, message overhead, which
bits can tolerate delay and which cannot, etc.

- nitin

  >> 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
  >> > of choice in general.
  >> 
  >> Agreed!
  >> 
  >> Regards,
  >> -Kevin
  >> 
  >> 
  >> 
  >> Nitin H Vaidya wrote:
  >> > 
  >> > 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.
  >> >   >>
  >> >   >> 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.
  >> >   >> >  >
  >> >   >> >  > 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
  >> >   >>
  >> >   >>
  >> 
  >> -- 
  >> Kevin Grace          The MITRE Corporation 
  >> 781-271-8388         202 Burlington Rd
  >> [email-masked]     Bedford MA, 01730
  >> 
  >>