Subject: BFD State Machine

From: Dave Katz <[email-masked]>
Date: Wed, 2 Mar 2005 13:42:53 -0700

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             |      |<---+
                 +------+                      +------+

---

From: Chris Nogradi <[email-masked]>
Date: Thu, 3 Mar 2005 14:07:24 -0500

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:
>                                   |
>                    |
>                    |
>                    |  |
>                    |  |

---

From: Dave Katz <[email-masked]>
Date: Thu, 3 Mar 2005 13:01:16 -0700

On Mar 3, 2005, at 12:07 PM, Chris Nogradi wrote:

> negotiations?

Yes, the parameters always apply, even during session bringup.  In the 
case you specify, the local transmitter would be required to send at 3 
second intervals.

My workaround hack ensures that, during session bringup, both sides are 
transmitting at the same rate (since each side advertises the same 
value for TX and RX, then they will converge on the larger value and 
both will transmit at that rate.)  But that's overtaken by events now;  
the new state machine is much cleaner, I think (though the silence has 
been deafening thus far.)

>  I suppose that since the peer's Desired Tx/Multiplier pair is
> init state, the Required RX time should also be honored during this 
> time.

Yes, all the timing parameters and procedures apply at all times.

>   I

Hmm, this is not the case;  if the spec is confusing on that aspect, 
please let me know what led you to that conclusion.  It is true that a 
true Demand Mode Poll Sequence requires you to be in Up state, but the 
verbiage in 6.7.3 talks about what to do when Demand Mode is not active 
(which it would not be during session establishment.)  I should 
probably point out in the text that this applies at all times, though 
it is less of an issue in session establishment, since the session is 
already down (the mechanism is designed to avoid dropping the session 
if the parameters change on the fly.)  It's also the case that the 
advertised values are unlikely to change during session bringup, except 
during the transition to Up state.

> to interoperate with an implementation using a different rate.  Is 

There should be no permanent deadlock condition, yes.  You may run into 
probabilistic difficulties (recoverable from the timer firing in Init 
state) but it should eventually come up.  However, I am pushing hard 
for completely deprecating the original version.  I've already worked 
up the spec changes, and they're really quite minor.  It would be a 
Really Good Idea to not ship version 0, to avoid having to deal with 
compatibility issues (at least I'm the one suffering the most by this, 
so there is justice after all.)

--Dave

---

From: Chris Nogradi <[email-masked]>
Date: Thu, 3 Mar 2005 15:38:04 -0500

> during the transition to Up state.

I guess the confusion arose as a result of your response to a previous 
question of mine below:

> >
> > 2.  While I am not sure that the document specifically states this, it 
> > appears
> > to me that the poll and final bits should only be set when in the up 
> > state?

> Yep.  Originally the P/F bits were only used when Demand Mode was 
> active, which can only happen in Up state.  However, we leveraged P/F 
> for parameter changes.  This should only apply in Up state.  Will be 
> fixed...

Which lead me to believe that section 6.7.3, since it deals with P/F bits, did 
not apply during negotiations.  As you pointed out, the main purpose for the 
P/F sequence is to ensure we do not drop the session during the parameters 
changes.  So it would seem unnecessary (and mostly cumbersome) to require the 
use of these flags during negotiations.  As far as the unlikeliness of 
changing the timing parameters during negotiations, I would imagine that it 
may be possible for an implementation to choose to use a back off algorithm 
during session establishment (similar to the one you use in your 
implementation for the high speed parameters).

---

From: Reshad Rahman <[email-masked]>
Date: Thu, 03 Mar 2005 16:44:46 -0500

Has the AdminDown state been removed?

Regards,
Reshad.

Dave Katz wrote:

> and I've come to the conclusion that the BFD state machine as 
> specified is flawed.  It has (at least) the following issues:
>
> symmetry in the protocol, combined with the state ambiguity, causes 
> the deadlock opportunity.
>
> 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 
> networking.  It also takes one less packet in each direction to come up.
>
> which customers rely, I am not going to attempt to document any kind 
> of interoperability or version negotiation scheme.  Version 0 should 
> 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.
>

---

From: Dave Katz <[email-masked]>
Date: Thu, 3 Mar 2005 14:55:38 -0700

> implementation for the high speed parameters).

Oh, well there's the problem!  You've discovered my multiple 
personality disorder.  ;-)  I guess I should make up my mind, hm.

I'm of two minds on this (obviously.)  On the one hand, doing the P/F 
stuff during session bringup (where it's unlikely to happen anyhow) is 
mildly pointless.  On the other hand, it is probably more code to *not* 
do this during session establishment.  I'll see if I can put in a MAY 
in a way that works, and people can implement it either way.

--Dave

---

From: Dave Katz <[email-masked]>
Date: Thu, 3 Mar 2005 14:57:18 -0700

> Has the AdminDown state been removed?

No, I just left it out of the picture for clarity.  AdminDown state is 
entered from any state via administrative action, and exits to Down 
state via administrative action.  Receipt of AdminDown goes to Down 
state regardless of the previous state.

This will be clear in the updated spec.

--Dave

---

From: Dave Katz <[email-masked]>
Date: Thu, 3 Mar 2005 15:15:40 -0700

On Mar 3, 2005, at 2:55 PM, Dave Katz wrote:

Ah, to heck with it, trying to shoehorn a MAY into this makes the spec 
too ugly.  I've left it
with requiring the P/F thing when in Up state.  Note however that there 
is no admonition against sending the P bit outside of Up state, and the 
remote end is always required to reply with F, so there's nothing to 
stop anyone from doing so if they feel like it.

--Dave

> mildly pointless.  On the other hand, it is probably more code to 
> *not* do this during session establishment.  I'll see if I can put in 
> a MAY in a way that works, and people can implement it either way.
>
> --Dave
>
>