Subject: 1s dead-interval + sub-second hellos

From: Paul Jakma <[email-masked]>
Date: Fri, 14 Oct 2005 16:52:16 +0100

Hi,

Are there any drafts regarding $SUBJECT (aka "fast hellos")? Any 
plans to formally specify this useful OSPF extension?

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
No house is childproofed unless the little darlings are in straitjackets.

---

From: Liem Nguyen <[email-masked]>
Date: Fri, 14 Oct 2005 09:11:25 -0700

Paul,

> plans to formally specify this useful OSPF extension?

None planned at the moment.  But BFD may be a better general solution.

-- 

Liem Nguyen

---

From: Dave Katz <[email-masked]>
Date: Fri, 14 Oct 2005 13:17:41 -0600

This seems like a pretty ugly hack, and at the end of the day you're  
still stuck with a one second detection time.

Using BFD as an advisory mechanism to OSPF seems cleaner to me, but  
then I'm biased.

---

From: Erblichs <[email-masked]>
Date: Fri, 14 Oct 2005 12:59:58 -0700

Dave Katz and group,

	Even with one sec interval hello intervals, wouldn't a a down 
	connection occur on avg every 0.5 sec. Yes worst case is
	1 sec.

	However, it is possible that consistantly xmit interval of
	of say 0.5 sec COULD implicitly imply more freq xmits, and
	that a drop of 1 of these COULD imply a dropped connection.

	If random drops are possible, then 3 xmits within 0.5 secs (as an
	example) could be used and again imply either congestion,
	a dropped connection, or .... AND alternate routing paths
	should/could be taken for priority realtime data/control traffic.

	So, bottom line, within the current spec, "fast hellos"
	COULD be implicitly used, if history is kept that determines that
	this is being used to more closely monitor router adj
	status.

	Mitchell Erblich
	----------------

---

From: vijay gill <[email-masked]>
Date: Fri, 14 Oct 2005 15:38:19 -0400

Dave Katz wrote:
> Using BFD as an advisory mechanism to OSPF seems cleaner to me, but then 
> I'm biased.
>

As a customer, we are fully behind BFD as the mechanism for fast failure 
detection, as opposed to tweaking timers in the protocol.

/vijay

---

From: Scott Whyte <[email-masked]>
Date: Fri, 14 Oct 2005 13:43:21 -0700

> detection, as opposed to tweaking timers in the protocol.

Seconded. OSPF with default timers and BFD doing aggressive failure
detection is working very well for us.

-Scott

/vijay

---

From: Dave Katz <[email-masked]>
Date: Fri, 14 Oct 2005 15:07:11 -0600

>     connection occur on avg every 0.5 sec. Yes worst case is

If the dead timer is one sec, then it takes one second from the last  
hello received to fail a neighbor.  The actual detection time for a  
failure will be between 1 and 1-i, where i is the longest interpacket  
gap.

>     that a drop of 1 of these COULD imply a dropped connection.

Giving up the ghost based on the drop of a single packet is exactly  
the wrong thing to do as you descend into fast detection territory,  
as the odds of a false negative increase faster than linearly as it  
is.  What you *really* don't want is a bunch of flapping adjacencies.

>     this is being used to more closely monitor router adj

Many things are possible, but the set of practical and stable things  
is rather smaller.  What you describe sounds highly dangerous to me.   
As Milo Medin used to say, "with enough thrust, anything will fly."

I have several problems with hacking OSPF.  First, if I understand  
the way some vendors are doing it, the hellos are going out with an  
advertised dead time of 1 and an advertised interval of 0.  This is  
called "lying."  It may have been a dumb idea to force each side to  
know the other's parameters and require that they match, but that's  
the way the protocol is defined.  Heuristic hacks lead to madness.

Second, as you start speeding things up, you really need a mechanism  
whereby the rate can be slowed down if things get ugly, or you end up  
with continuous flappage and a network that has gone into protocol  
fibrillation.  It's spectacular and fascinating to watch, in the same  
way as a train wreck, but it's equally unpleasant.

Third, as you start speeding things up, you need to be able to  
control the rate on a per-neighbor basis.  Otherwise, one slower guy  
can totally hose things, so either everybody has to go slow  
(suboptimal) or everybody flaps with the guy (really suboptimal.)

Fourth, OSPF hellos serve two purposes (liveness and state  
management.)  Once the neighbor comes up, the state information is  
redundant.  It seems wasteful to send all this redundant information  
at a faster and faster rate.

My position for awhile now is that the network as a whole needs to be  
able to pull its own fat out of the fire if things start to collapse,  
and OSPF is just too rigid to allow that.

--Dave

---

From: Paul Jakma <[email-masked]>
Date: Mon, 17 Oct 2005 15:13:35 +0100

On Fri, 14 Oct 2005, Dave Katz wrote:

> If the dead timer is one sec, then it takes one second from the 
> last hello received to fail a neighbor.  The actual detection time 
> for a failure will be between 1 and 1-i, where i is the longest 
> interpacket gap.

Surely it'd always be at least 1?

> false negative increase faster than linearly as it is.  What you 
> *really* don't want is a bunch of flapping adjacencies.

Yep, but that's operational more than anything else, I guess.

> the way the protocol is defined. Heuristic hacks lead to madness.

Indeed.

> Second, as you start speeding things up, you really need a 
> mechanism whereby the rate can be slowed down if things get ugly, 
> or you end up with continuous flappage and a network that has gone 
> into protocol fibrillation.  It's spectacular and fascinating to 
> watch, in the same way as a train wreck, but it's equally 
> unpleasant.
>
> control the rate on a per-neighbor basis.  Otherwise, one slower 
> guy can totally hose things, so either everybody has to go slow 

This would be because of a monolithic OSPF protocol implementation, 
unable to service the Hello sub-protocol because it's busy doing 
something else?

Presuming the machine is either fast enough to keep up (even with a 
monolithic implementation) or seperates the running of Hello from the 
rest of OSPF (which some implementations do I believe), then things 
should be ok.

In such a case, regular quick failures would still induce protocol 
"fibrilliation" (excellent term ;) ) wouldn't they, regardless of 
whether it's BFD or fast Hello or a slow monolithic implementation 
which indicates failure / causes flaps? I.E. the "fibrillation" 
problem probably should be examined, even with BFD (if it's even 
possible to solve it in the protocol)..

> redundant.  It seems wasteful to send all this redundant 
> information at a faster and faster rate.

Hmm, there's maybe 36 bytes of redundant information, not much. Plus, 
OSPF Hello does multicast, a BFD "full mesh" between a couple of 
machines on a multi-access network would have far more overhead ;).

Ie, Fast-Hello is still quite interesting for multi-access networks, 
for efficiency, isn't it? How does OSPF Hello compare to BFD here?

> My position for awhile now is that the network as a whole needs to 
> be able to pull its own fat out of the fire if things start to 
> collapse, and OSPF is just too rigid to allow that.

Hmm, interesting thought. What could be done though?

I suspect this might be more a combination of implementation + 
operational issues though, than a problem with OSPF.

-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"Love is a snowmobile racing across the tundra and then suddenly it flips
  over, pinning you underneath.  At night, the ice weasels come."
--Matt Groening

---

From: Dave Katz <[email-masked]>
Date: Thu, 20 Oct 2005 10:34:43 -0600

> Surely it'd always be at least 1?

If we're measuring the time from a failure until the time the dead  
timer expires, the time is always less than 1 (neglecting latency.)   
It's one second since the last time we received a hello that the  
neighbor emitted, so any failure must have come later than that (and  
thus the interval to declaring neighbor failure is less than that.)

> Yep, but that's operational more than anything else, I guess.

Um, yes, but as far as I know we're building operational networks and  
not a theoretical testbed.  There is ample historical evidence that  
many OSPF implementations cannot deal with high levels of flappage  
(including the dominant implementation, unless it has undergone very  
serious rework in the recent past.)  You would be right in saying  
that a properly implemented system should shrug off flapping as a  
mere annoyance, but most network operators are at the mercy of  
multiple vendors of various skill levels, and their networks will  
suffer.  The nature of OSPF is that flaps are propagated throughout  
the network and *every* implementation has to be able to cope.

> unable to service the Hello sub-protocol because it's busy doing  

Doesn't matter why.  Maybe the neighbor is an underpowered box that  
has I/O bandwidth limitations.  Not all routers are created equal,  
and there is always a point where the combination of neighbor count  
and packet speed will exceed the capabilities of some boxes while  
being within the realm of reason with others, even with perfect  
software.

> monolithic implementation) or seperates the running of Hello from  
> the rest of OSPF (which some implementations do I believe), then  
> things should be ok.

I happen to know one of those separated impelementations quite well,  
but I guarantee that if you push it hard enough it will fall over.   
Once the volume of incoming hellos exceeds the bandwidth (including  
processing power) of the path, you're SOL.

> possible to solve it in the protocol)..

Yes, and this is the one key ingredient of BFD--the timers for a  
session can be dialled back, in both directions, by unilateral action  
of one end of the session, without dropping the session.  A system  
has full control over its load (both RX and TX) and thus can  
autonomously protect itself by setting the load to any arbitrary  
level (trading off detection time, of course, but I don't think  
you'll find any operator that would rather have stability.)

> Hmm, there's maybe 36 bytes of redundant information, not much.  
> Plus, OSPF Hello does multicast, a BFD "full mesh" between a couple  
> of machines on a multi-access network would have far more overhead ;).

I'm not concerned about bytes so much as CPU, but yeah, it's a mostly  
specious argument if you do things properly in the OSPF receive  
routine (unless you've turned on crypto authentication, in which case  
you're really hosed.)

 From the point of view of a single system, the receive load for  
multicast versus a full mesh is identical (it's the transmit load  
that goes from O(1) to O(N).)  Overall load (TX+RX) as viewed by a  
single system is doubled in a full mesh.

>
> Ie, Fast-Hello is still quite interesting for multi-access  
> networks, for efficiency, isn't it? How does OSPF Hello compare to  
> BFD here?

Network bandwidth efficiency is uninteresting when even the cheapest  
consumer gear runs at 100 Mbps.  The Hello packet load goes from O(N)  
to O(N^2) as viewed on the subnet, but the load is still an  
unmeasurable percentage of the capacity of the link on any real  
network (if you had enough routers on a single subnet to make this  
number meaningful, you'd have other problems.)  Plus, nobody uses  
truly shared media any more--even the consumer gear keeps traffic off  
of links where it needn't go.  Plus, since it's all unicast, the  
total load as perceived by any machine only doubles.  In exchange for  
doubling the load you gain the ability to control independently the  
detection time on a pairwise basis.

OSPF is full of complexity in the name of efficiency, which is one of  
the reasons it's difficult to implement.  This stuff might have made  
sense back in the days of 9600bps links, but it just gets in the way  
these days.  EIGRP is even worse.  ISIS is the only protocol I know  
that uses multicast in a useful way (flooding creates a load  
independent of neighbor count.)  But that's a separate rant.

> Hmm, interesting thought. What could be done though?

BFD.  That's one of the reasons we did it.  Otherwise we'd have to  
overhaul every protocol that has a detection timer in an incompatible  
way.

> operational issues though, than a problem with OSPF.

OSPF has two fundamental problems.  First, architecturally it is  
incapable of detection times of less than two seconds unless you  
start making hacks (and is incapable of detection times of less than  
one second unless you start making incredibly egregious hacks.)   
Secondly, you cannot change the dead time and hello interval without  
dropping the adjacency.  That makes adaptation a non-starter.

I'm adamant about this stuff because I've watched networks collapse  
for years.  The simple fact is that *every* major network collapse  
that I know about in the 20 years I've been in this racket has been  
ultimately due to fibrillation.  It was true for AOL Down for 19  
Hours (1995), and the MCI frame relay network that was down for ten  
days in the late 90s (taking out the Chicago Board of Trade), and the  
ATT SS7 phone network collapse.  (OK, it wasn't true of the NSFnet in  
1990 when the 55th router was added, but that's another story.)  As  
networks get even bigger, and even faster, and the demand for shorter  
detection times grows, it is increasingly imperative that networks be  
self-repairing.  Manually reconfiguring during a network collapse is  
not practical, particularly when (as in OSPF) it creates even more  
outages.  When BFD was designed, adaptivity was the single biggest  
requirement (IMHO).

--Dave

---

From: Erblichs <[email-masked]>
Date: Thu, 20 Oct 2005 12:34:22 -0700

Group,

	I thought this thread had died after I got pulled
	to do a few things.. However, it seems like it is
	still alive. Also, sorry, I tend to be verbose..

	My long comments are inline and mostly it is not
	re-inforcing the previous comments.

	Mitchell Erblich
	---------------------

> the network and *every* implementation has to be able to cope.

	Implimentations do vary. If a router keeps history of its
	nbrs MTBF (mean time between failure) of missed one or more
	hellos. Assuming hellos are used to determine aliveness. IT
	"CAN THEN" determine
		* is it a missed / lost recv'd hello,
		* have we recv'd a OSPF control or data pkt
		   from this "adj nbr",
		* do we have alternate routes,
		* do we have immediate data/control pkts to send to 
		  this "adj nbr",
		* do we have any other communication with this
		  router,
		* do we need to recalc any algorithms,
		* is this a random or a freq drop of pkts,
		* IFF we bring down the adj, should we delay our
		  full adj or whatever status with that nbr,

		* SHOULD we send a OSPF control pkt that SHOULD
		  be acked and start a delay timer as long as we
		  are not losing/delaying any real data.

		**** etc...

	IF this router only adds a few elements to out LSDB and
	the two routers are only out of sync, then the effort to
	resume COULD be minimal.

	Thus, adj flapping should be a dead issue with current
	implimentations..
> being within the realm of reason with others, even with perfect

	Oh, however, if you prioritize control pkts with a algorithm
	so you send out hellos or such in a "just in time method" AND the
	OVERLOAD condition is short lived. Then the non peaks should
	be able to decrease the queue lengths that were built up at
	overload time. If the diff between overload and min loading is
	great enough or the times between two successive OVERLOAD
	conditions is long enough the queue lengths should return to
	normal length with normal pkt processing latencies..
> processing power) of the path, you're SOL.

	However, so given my above statement. You either get very
	large periodic queues, you impliment RED or such, and the
	pkts are rexmit'ed that were either delayed proc or
	dropped via RED.

	Its not like a router SHOULD fall over a play dead because
	it got overloaded. Overload should be a nice simple condition
	that can and SHOULD be dealt with in deterministic means.

	AND as we increase the bandwidth or with normal 10Mb/sec or
	faster, I can not see how sub sec hellos SHOULD effect
	adjs in a properly designed router software.

	If we push it to the extreme with say 1 ms hello interval,
	a separate input priority queue, identify that 10 of 10 pkts
	ARE just repeating previous hellos. We then COULD create a
	special hello update pkt that is just larger than runt
	size and only deal with JUST a pkt/per/sec processing overhead
	and remove the extraneous repeative nbr info.

	This would fit well with Kb wireless type links.

	NO SOL...
> you'll find any operator that would rather have stability.)

	I just have not had enough experience with BFD and
	admins trying to config DYNAMIC loads in a manual
	way.

	I don't see how a router in a non MPLS configuration
	can "control" its load. Its max load is based on the
	number of live interfaces, the summation of the
	bandwidth of those interfaces, what percentage of
	pkts coming in one interface is directed to one or
	more interfaces, the size of eack pkt, the interpkt gap,
	the memory allocated for the rcv /xmit queues, the
	latencies in handling the pkt, AND the percentage of
	pkts transversing the router (intermediate system).
	
> dropping the adjacency.  That makes adaptation a non-starter.

	Wow. Can I say that I COMPLETELY disagree.

	In many environments, two routers can speak to each other
	either across more than 1 interface or where 1 interface
	carries multiple VPN sessions, each doubling of the 
	communciation channel "implictly" halves the detection
	time between the two routers.

	Ex: If we approximate the avg of the hello intervals
	with say 2 channels each having a independently interval
	of say 2 secs, the avg hello seen by each should be about
	1 sec. A very common item was/is to use different auths
	per channel but if two routers had in common two different
	auths, then the hellos per auth would have the same effect
	as decreasing the hello interval.
	
	In addition, I don't know what would prevent a router
	from more freq sending hellos. Can anyone really say
	that if a OSPF router saw a hello every 1 sec when
	configured for rec hellos from a nbr every 2 secs, that
	the extra hello would be dropped and not reset the
	aliveness timer.

	And again sorry..

	What would be wrong with being able to change the
	timers before the adj was dropped. Changing the
	intervals only changes the field maching criteria
	which should drop the pkt, not the adj. If both
	routers could be changed approx within the dead time,
	the adj should be reinforced by the new values.

	One can simply login to both routers simultaneiously
	and type the CLI commands on both routers in separate
	windows and then hit return for both.

---

From: Dave Katz <[email-masked]>
Date: Thu, 20 Oct 2005 17:35:05 -0600

>     Thus, adj flapping should be a dead issue with current

It is certainly possible to improve the behavior of systems in the  
face of instability, and even to try to protect the lesser  
implementations (though it is arguably not in a competitor's best  
interest to do so.)  The fact remains that the reason people want to  
go to faster detection times is to detect failures (and reroute) more  
quickly.  This requires that the full rerouting mechanisms of OSPF  
are brought to bear (no dillydallying trying to figure out if things  
are "really" dead) and it requires that the detection mechanism have  
a very small probability of detecting false failures.

The validity of statistical methods in an application like this  
(particularly when jitter is being applied) is beyond my capabilities  
in that area, but I don't think it would be easy to do it well.

>     normal length with normal pkt processing latencies..

If overloads are short-lived, life is good (or at least better.)  But  
my experience is that overload creeps up (as more and more stuff gets  
deployed) or else comes on like a freight train (misconfiguration)  
and that's when you get metastable collapse states.  If there is  
simply not enough capacity to do the processing, no magic will get  
you out of it.  The only choice is to reduce the load.

>     pkts are rexmit'ed that were either delayed proc or

We're talking about accurate liveness maintenance here, in which  
neither RED nor retransmission has any place.

>     that can and SHOULD be dealt with in deterministic means.

No argument here.

>     adjs in a properly designed router software.

If you turn it up high enough, on enough neighbors, it WILL fail,  
either by sheer load, or by the fact that the aggregate jitter  
becomes a larger and larger component as the timescale is reduced,  
eventually overwhelming the detection time.  There is pressure to  
achieve traditional routing failover at MPLS/APS-like rates;  we're  
not talking about 500 msec detections here.

>     and remove the extraneous repeative nbr info.

The receive side is easier, since you can play games like this.  When  
the transmit side can't get 'em out fast enough, there's no saving  
you however.

>     pkts transversing the router (intermediate system).

I'm referring to the load created by BFD, and the sensitivity of the  
system to overall system congestion (separate queues and hardware  
switching tend to make the data traffic immaterial.)  The point is  
that if you are on the verge of a control protocol collapse, the  
ability to trade off detection time for stability is an important one  
(and the only way out of the situation.)

>     as decreasing the hello interval.

I guess I'd put this somewhere between "hack" and "egregious hack."   
To attempt to achieve, say, 50 msec detection times while staying  
within the current OSPF spec, I would have to have a one second  
interval with a two second dead time across 40 separate channels.   
Further, to enforce my detection time requirement, the neighbor must  
space those packets in such a way as to guarantee that under normal  
circumstances that there is never more than 50 msec between two of  
them (25 is more realistic.)  All of this would require mechanisms  
outside the protocol to achieve, as both sides need to know that this  
particular game is being played and then play it appropriately.  Yes,  
it can be made to work, but it's ugly.

>     the extra hello would be dropped and not reset the

You can always send them more often than you said in your hello;   
this always happens to some extent with jitter anyhow.  But the point  
is knowing when to declare the neighbor down.

>     windows and then hit return for both.

You're kidding, right?  Even if this made any sense at all, I don't  
think I could move my mouse between windows and hit a second CR  
within 50 msec, even if the CLI processing was instantaneous and the  
latency to each of the routers was identical, neither of which is  
true.  In the situation where my network was melting (assuming I  
could log in at all because the network was melting) I would want to  
do this on all of my links.

You're missing my point entirely.  I see it as a fundamental  
requirement that the network be able to save itself quickly and  
efficiently in the face of catastrophic collapse, and the probability  
of catastrophic collapse grows rapidly as the detection time  
requirements are tightened.  This cannot be done manually, and it  
cannot be done bilaterally (unless you don't mind flapping every  
adjacency first.)  To do it automatically within the confines of OSPF  
would require some very interesting (and possibly intractably  
unstable) heuristics to try to track what the other guy is doing with  
his announced timer values.

My point is that, yes, with enough complexity and heuristics and spec- 
bending it *might* be possible to make the existing OSPF spec handle  
arbitrarily small time values.  It would also require mechanisms  
negotiated outside the protocol to achieve, which has  
interoperability implications.

This is an interesting intellectual exercise, but it is not clear  
that there is any benefit to doing so when there is a mechanism that  
has been defined (and for which multiple interoperable  
implementations exist) that is clean, functional, nicely decoupled,  
requires no changes to the protocol spec, operates identically over  
six orders of magnitude of time intervals, has broader system-wide  
benefits, and addresses the problem at hand specifically and in a  
straightforward way.

Perhaps you're an optimist about networks, where all systems operate  
as they "should" and all developers are as talented as you and I.   
I'm a pessimist/realist, and all I care about is that the network is  
stable and functioning, and all experience points to the fact that  
most software is mediocre and fails miserably when it operates too  
close to the edge of the cliff.  I'd hazard a guess that the  
operators of networks on this list don't care about "should" very  
much, except that their network "should" stay up and not suffer  
catastrophic failure.

--Dave

---

From: vijay gill <[email-masked]>
Date: Thu, 20 Oct 2005 19:59:09 -0400

> 	windows and then hit return for both.

If any vendor came to me and said this, that vendor would be shown the 
door. Never, ever would this be deployed at any network I have a say in. 
EVER.

/vijay

---

From: Erblichs <[email-masked]>
Date: Thu, 20 Oct 2005 18:54:36 -0700

vijay gill,

	Are you saying that admins SHOULD BE prevented from
	modifying the timer values once a adj has been
	established? Do you consider this some type
	of DOS attack and prevent this without taking
	down the adj?

	The assumption is that the admin has a valid
	reason for doing so and that he has the proper
	creds for the login.

	All I am saying is that if the dead router interval
	is long enough then their is no guaranteed loss of
	adj.

	If you put checks into when CLI commands can be
	executed and changed even by authorized personal,
	this engineer would be interested.

	Don't we assume that the admin knows what he is
	doing? We don't always agree with what he wants,
	but I tend to give him enough "leeway" and hope..

	Mitchell Erblich
	----------------------------

---

From: Paul Jakma <[email-masked]>
Date: Fri, 21 Oct 2005 06:31:56 +0100

On Thu, 20 Oct 2005, Dave Katz wrote:

> Further, to enforce my detection time requirement, the neighbor 
> must space those packets in such a way as to guarantee that under 
> normal circumstances that there is never more than 50 msec between 
> two of them (25 is more realistic.)  All of this would require 
> mechanisms outside the protocol to achieve, as both sides need to 
> know that this particular game is being played and then play it 
> appropriately.  Yes, it can be made to work, but it's ugly.

It could be done in protocol, as we still have 0s dead-time to hang a 
hat on. 0s dead-interval -> "adaptive hello and dead interval" (say). 
With such a dead-interval:

- advertise number of hellos/s as your hello-interval
- on receiving hello:
 	- record the millisec hello/s value for that neighbour
 	- (re)?set neigbour specific dead-timer to
 		hello-interval * (X + Y)

   where X is an OSPF constant (eg 2, 3 or 4), and Y is at the
   discretion of the implemention, intended to be adapted according to
   perceived load.

That gets things down to 3ms hello-interval and 6ms or 9ms dead-time 
within confines of current OSPF Hello packet format (which I suspect 
is too "real-time" for most implementations to be able to reliably 
detect or meet). It also allows the hello-interval to be modified 
unilaterally during operation.

But I suspect that would be reinventing BFD poorly..

> My point is that, yes, with enough complexity and heuristics and 
> spec-bending it *might* be possible to make the existing OSPF spec 
> handle arbitrarily small time values.  It would also require 
> mechanisms negotiated outside the protocol to achieve, which has 

Wouldn't be that complex, see above ;).

regards,
-- 
Paul Jakma	[email-masked]	[email-masked]	Key ID: 64A2FF6A
Fortune:
"Wheee! ...ow, I bit my tongue!"

 	--Ralph Wiggum
 	  Bart's Inner Child (Episode 1F05)