BFD State Machine

[Dave Katz <[e-mail]>]

Richard Spencer's comments made me put on my thinking cap for awhile, 
and I've come to the conclusion that the BFD state machine as specified 
is flawed.  It has (at least) the following issues:

   Sessions could come up faster

   Unidirectional failures require a timeout of INIT state to restore 
service

   Service restoration is probabilistic

   Dissimilar timer values during session establishment can cause 
permanent deadlock

The first is a little unhappy, but not too bad.  The second and third 
are ugly, but not fatal;  the session will come up eventually.  The 
fourth is fatal as currently spec'ed--if one side has a transmit 
interval of one second and the other has a transmit interval of five 
seconds, the session will enter the deadlock loop that Richard pointed 
out.  This is fixable by requiring that the same value be sent for 
Desired TX and Required RX while not in Up state, but that's ugly too.

The heart of the problem is this--there are two symmetric wait states 
in the state machine, but there is insufficient state passed in the 
protocol (only one bit) to communicate what's happening.  The IHU bit 
tells you only that the other system is in one of two states.  The 
symmetry in the protocol, combined with the state ambiguity, causes the 
deadlock opportunity.

After some hemming and hawing, Dave2 and I have decided that we should 
bite the bullet and change the protocol.  This will require an 
incompatible change and a bump of the version number.  The change is 
fairly simple;  rather than communicate a single bit of state 
information (IHU), instead communicate the current state.

As we move an extra bit of state into the protocol, this allows us to 
remove a state from the state machine.  The new scheme fixes all of the 
above problems;  as a matter of fact the unidrectional failure case 
ends up taking one less packet to come up than the bidirectional 
failure case.  Since the state is carried in the protocol, every state 
change causes a change in packet contents, which in turn triggers an 
"extra" packet to be transmitted, so the sessions can come up rapidly, 
but safely, and in as deterministic a manner as is possible in 
networking.  It also takes one less packet in each direction to come 
up.

Given that this document hasn't even made proposed standard yet, and 
given that, as far as I know, I'm the only one with deployed code on 
which customers rely, I am not going to attempt to document any kind of 
interoperability or version negotiation scheme.  Version 0 should 
simply be discarded and replaced with Version 1.

I'm going to spin the document, which will appear after the IETF 
meeting (as the I-D sluice is blocked until after the meeting.)  Dave2 
will make a presentation at the meeting describing the changes.

Below is the new state machine.  It is pretty straightforward;  the 
notations on the arcs are the neighbor's state as signalled in received 
BFD packets (plus the detection timer expiration.)  I think this is 
much more transparent than the last one in terms of being able to 
intuit the mechanism and its side effects.  This should be sufficient 
for the motivated to analyze and pick apart.  Comments and brickbats to 
the list, please.

All this goes to show that protocol design is a subtle art...

--Dave

                                  +--+
                                  |  | UP
                                  |  V
                          DOWN  +------+  INIT
                   +------------|      |------------+
                   |            | DOWN |            |
                   |  +-------->|      |<--------+  |
                   |  |         +------+         |  |
                   |  |                          |  |
                   |  |                          |  |
                   |  |                     DOWN,|  |
                   |  |TIMER                TIMER|  |
                   V  |                          |  V
                 +------+                      +------+
            +----|      |                      |      |----+
        DOWN|    | INIT |--------------------->|  UP  |    |INIT, UP
            +--->|      | INIT, UP             |      |<---+
                 +------+                      +------+