Subject: RE: [Ospf-manet] Adjacency Reduction??

From: "Henderson, Thomas R" <[email-masked]>
Date: Wed, 1 Feb 2006 08:22:41 -0800

> -----Original Message-----
> From: Russ White [mailto:[email-masked]] 
> Sent: Wednesday, February 01, 2006 4:05 AM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: [Ospf-manet] Adjacency Reduction??
> 
> 
> >>Now, as this applies to the MANET work specifically: A 
> number of the 
> >>people I've talked to who are considering deploying these solutions 
> >>say that adjacency reduction is not an acceptable alternative, in 
> >>their opinion, simply because when you reduce adjacencies, you 
> >>increase convergence time, in all cases. There's no way around the 
> >>fact that as you reduce adjacencies, you increase the time it takes 
> >>for a new member of the network to begin routing packets, 
> or a member 
> >>of the network to recover from losing it's current adjacencies.
> > 
> > I really don't see how you can support such a claim about 
> convergence 
> > in all cases.
> 
> Can you support the opposite claim? Is there any situation where:
> 
> - -- You've arbitrarily decided to reduce adjacencies for 
> optimal performance.
> - -- You've lost all "fully adjacent" neighbors.
> - -- Convergence is just as fast as the case when you didn't 
> reduce adjacencies?
> 
> No, there's not. In fact, even in the wired world, we give up 
> convergence on broadcast links for more efficiency--note the 
> wide interest in being able to declare a point-to-point 
> "broadcast type" link as an OSPF point-to-point link, in the 
> interest of faster convergence, for instance.
> 

You need to be careful when you say "in all cases."  You are citing a
specific case where you've lost all active adjacencies, would have
normally had another adjacency but had previously suppressed it, and now
need to bring it up.  However, even here, it is not clear that adjacency
bring up with a non-active neighbor is going to be slow due to
synchronization-- databases are probably pretty much aligned at that
point, through other adjacency relationships.  

A study on OSPF convergence in a large ISP network that I've looked at
suggests that convergence is actually hampered by having more
adjacencies, because links come up in sequence (slow adjacency bringup
due to timers, SPF hold-downs, and architectural constants like
MinLSInterval), and convergence is with the last SPF (possibly many tens
of seconds even for a single node bringup).  

Moreover, when you do not do topology control, and you have limited
bandwidth, you can clog the network with so many packets that the
protocol goes into congestion collapse.  That really has a negative
effect on convergence!  For a 1 Mb/s channel, for instance, we found
this to occur for fewer than 20 routers in point-to-multipoint mode even
when we took steps to randomize the time that new routers joined the
network-- it is even worse when everyone powers up at nearly the same
time.  So there are clearly cases where adjacency reduction improves
convergence.

> DR election in the wired world is based on the logical 
> assumption that movement will be rare, and device failure 
> will be rare. We can't make either assumption in a mobile world.

We are considering Overlapping Relays and MDR election, not DR election
(which I agree you do not want to apply to the wireless network, as
studies have shown).  

While we are on this point, there seems to be a misperception that
Overlapping Relays has some kind of fault tolerance property that allows
routers to flood more rapidly in the face of topology change, while MDRs
have to sit around and churn on an election algorithm to compute a new
flooding backbone before doing anything.  This was promulgated by Alvaro
Retana's and Fred Baker's comments at the last WG meeting; specifically,
that everyone is an overlapping relay until deselected by a neighbor
(opt-out), whereas MDR flooding has to wait for MDR backbone election
(opt-in).  Even if Overlapping Relays has such a feature (which is not
in the draft-chandra, by the way), it would only really matter upon
initial node bringup, because once MPRs are selected and disseminated to
neighbors, topology change requires a recomputation and re-notification,
and in this meantime, flooding will perhaps need to rely on backups
(pushbacks) and retransmissions to reach certain nodes.  In MDRs, there
are also (a configurable number of) backups and retransmissions along
adjacencies just as in ORs, so it is similar in design in that regard.  

If the argument is that all neighbors can back up the Overlapping
Relays, that is more a function of whether there are full or partial
mesh of adjacencies, since we have agreed that flooding only occurs
along adjacencies, and extensions such as Smart Peering will cut into
that property anyway, and it's not really predictable how often a
situation arises where a trimmed adjacency actually ends up hurting
convergence at some point.  Again, it leads us back to a question of
whether adjacency reduction hurts or helps convergence (it depends on
the particular scenario), and is difficult to fully analyze, in absence
of simulations or experiments, because of the complexities noted above.

Tom

_______________________________________________
Ospf-manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-manet

---

From: Russ White <[email-masked]>
Date: Wed, 01 Feb 2006 11:53:52 -0500

> point, through other adjacency relationships.  

I believe the number cited on list was that it would take n^2, with n as 
the number of reachable neighbors, to find the right set of flooding 
neighbors with MDR's.

> of simulations or experiments, because of the complexities noted above.

Then simulate various percentages of adjacent neighbors, and see what 
the results are. It only seems logical that there are various "tipping 
points," and it would be valuable to know what those "tipping points" 
are. With 2 backups/adjacencies, the overhead is x, with 3, it's y, with 
4, it's z.

What are x, y, and z?

:-)

Russ

- -- 
[email-masked] CCIE <>< Grace Alone