Re: BFD State Machine

[Chris Nogradi <[e-mail]>]

Dave,

Since all implementations of BFD that I have observed use a one packet per 
second sedate rate, I never noticed the fact that the draft specified this as 
the MINIMUM interval.   If fact when you described a possible solution for 
the deadlock, requiring the Desired TX and Required RX to match during 
negotiations, the thought occurred to me that you were suggesting that the 
Required RX value should be used during negotiations. For instance, suppose 
that an implementation uses a one second sedate rate but the peer 
implementation is advertising a three second Required RX value. Should this 
Required RX value be used instead of the one second interval during 
negotiations? I suppose that since the peer's Desired Tx/Multiplier pair is 
used to determine the detection time used during the negotiation while in the 
init state, the Required RX time should also be honored during this time.  I 
guess the confusion arises from the fact that when the session is being 
negotiated, the time values are used without requiring a poll sequence 
(poll/final).  However, when the session is up, timer value changes must be 
communicated using a poll sequence (poll/final).

BTW, assuming that an original draft implementation uses a fixed sedate rate, 
it would seem that it would not run into the deadlock problem unless it has 
to interoperate with an implementation using a different rate.  Is this true?

Any clarification in these matters is much appreciated,

Thanks,

Chris
   
On Wednesday 02 March 2005 15:42, Dave Katz wrote:
> 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             |      |<---+
>                  +------+                      +------+