Subject: On-Demand vs Link State

From: Chip Elliott <[email-masked]>
Date: Mon, 10 Jul 2000 15:14:13 -0400

Another helpful way to look at these two protocol families
(on demand, link state) is to consider how a malicious intruder
would bring them to their knees. They fail in quite different
ways, I think.

For on-demand protocols, the worst attack is to keep requesting
addresses that are not reachable. For link state, it's rapid
change in the network topology. Both problems can be ameliorated
by rate-limiting the control traffic, of course at the expense
of making the network sluggish and irresponsive in some cases.

Once you look at the families that way, then it's easy to apply
Murphy's Law to determine how these networks are likely to
behave in practice! One doesn't really need a malicious
intruder - normal operation will suffice...

Cheers,

Chip Elliott
BBN

>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. 
>
>> 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.
>
>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 H. Grace
> The MITRE Corporation
> 202 Burlington Rd
> Bedford, MA  01730
> (781) 271-8388
> [email-masked]
>