Subject: LDP/CR-LDP Fault Tolerance - progress report

From: Paul Brittain <[email-masked]>
Date: Tue, 21 Mar 2000 10:02:46 -0000

As you may have noticed, there have been two proposals submitted to the WG
recently on the provision of Fault Tolerance for LDP and CR-LDP:

-   draft-farrel-mpls-ldp-ft-00.txt
-   draft-matthews-mpls-lsp-ibb-00.txt

The authors of these drafts (Paul Brittain, Adrian Farrel and Philip
Matthews) plus Eric Gray have had considerable discussion over the past 2
weeks on how to merge the two drafts and present a single draft back to the
WG.

A SUMMARY of our deliberations is as follows:

-	Both proposals use similar overall approaches to avoid full
resynchronization of state after TCP failure/reconnection.
-	We will combine the drafts and issue a merged draft to the WG.
-	The ACK scheme will be based on [MATTHEWS], modified to use a new FT
sequence number in place of Message ID
-	FT/non-FT labels from [FARREL] will be included in the merged draft.
-	Address messages need to be protected by the FT ACK scheme, as well
as Label Request/Mapping etc..
-	The procedural detail from [FARREL] should help interoperability and
will be included in the draft, but with changes for the [MATTHEWS] ACKs
-	Philip Matthews will be presenting our plans for merging the
proposals at Adelaide.  
-	I am currently working on the merged draft and will issue it as soon
as possible.

READ ON if you want more detail on our deliberations.
STOP HERE if you just need to know what we plan to do.

This rest of this note provides more detail on our discussions, including
the logic behind the main decisions we made, in order to keep the WG
informed of our progress.  For clarity, the notes below refer to the two
drafts as [MATTHEWS] or [FARREL] where I need to make a distinction between
the two approaches. 

These notes appear as a record for the WG on the offline deliberations
between the authors.  To fully understand these notes you will need at least
a passing familiarity with both proposals.  Alternatively, you can wait for
Philip's presentation in Adelaide :-)

Thanks,

Paul Brittain.

----------------------------------------

_WHAT WE MEAN BY FT_

FT is the ability to preserve inbound and outbound segments plus X-connects
for some labels (known as FT labels) at an individual LSR when that LSR
experiences some form of h/w or s/w interruption.  In particular, FT should
enable an LDP implementation to handle upgrade to the hardware on which LDP
or TCP is running, or upgrades to the LDP or TCP software, without
interrupting the forwarding service on the FT labels.  

We discussed the fact that some scenarios could be handled using redundant
link hardware and asuming that the TCP connection will re-route to the
available link.  However, this does not cover all cases.  In particular, it
can be very expensive to provide such redundant links, so 1:1 redundancy may
not be available in all cases.  This also does not handle the case where the
TCP software is itself upgraded, causing an interruption to the TCP session.

SCTP was also discussed as being one way to improve on the fault tolerance
achieved using TCP, but we believe it is also unable to handle the software
upgrade or stack failure scenarios without hitting the same issues that
plague FT TCP implementations (duplication of data awaiting retransmission,
reconneciton of "sockets" or similar) - though this is an area we are
investigating further.

It should be possible for two FT transit switches to handle, say, an upgrade
to one of the LDP stacks without any of the end points for LSPs transiting
these switches being aware of the change, and without the need for
expensive, fully redundant hardware in both switches.  In order to achieve
this we need to introduce some level of co-operation between LSR peers to
allow them to recover from any interruption to the TCP connection.

Protection Switching is distinct from FT.  PS handles the use of redundant
links to preserve data forwarding across link failure.  FT is targetted at
preserving data forwarding across failure in the control plane, which would
currently bring down data forwarding un-necessarily.  

_FUNCTION NEEDED FOR LDP FT_

We see this as breaking down into four main pieces:

1)  Means of determining which LSR peers support and/or use the FT
extensions
2)  Means of identifying which LDP exchanges with these peers are
FT-protected
3)  Means of synchronizing state for the protected LDP exchanges on a
per-hop basis
4)  Some degree of trust in FT LSR peers.

Looking at each of these in more detail to clarify why it is needed:

1) is obviously needed to allow interop with peers that do not support these
extensions.  It is (relatively) easily achieved by adding options to the LDP
Initialization message.

2) is mainly a matter for policy.  As such, we cannot dictate that the only
option is that all labels are FT or none is. For example, consider the case
where TE is used to pre-program load-balanced "label trunks" across an FT
core network based on, say, traffic stats recorded over some interval, but
without reserving bandwidth for those labels.  LSRs at the edge of this core
would distribute labels to (potentially) non-FT CPE routers on request,
possibly using a label stack to tunnel across the core to the appropriate
destination CPE router.  In this case, the labels used in the core are FT,
but the labels assigned at the edge need not be.  Similarly, the edge
switches in this example may use FT hardware, but they need no be running
the FT extensions on all LDP sessions (e.g. to the CPE routers).

We need to have the flexibility to distinguish FT and non-FT labels, and to
allow each LSR to choose whether to run the FT enhancements one any given
LDP session according to the nature of the services it is providing. 

3) is obviously required to achieve any form of FT!  If you're wondering why
the requirements said "per-hop", see the previous paragraph.  In this case,
the edge routers will want to preserve the FT behavior of the core labels
even if they drop any LSPs initiated/terminated by a CPE router when the CPE
router dies.  Besides, per-hop behavior can be used to build end-to-end
behavior depending on policy choice.  

In practice, this synchronization will have to involve some form of
acknowledgement of LDP exchanges so that the LSR peers can recover after TCP
reconnection without re-exchanging _FULL_ state information (which doesn't
scale), and some form of ACK reduction mechanism to ensure the ACKs don't
slow down normal operation too much.

4) is a consequence of (3).  If we allow FT for LDP, implicitly we have to
trust adjacent LSRs to have preserved the information they claim to have
kept from the previous TCP session.  

_HOW THIS FUNCTION IS ADDRESSED BY BOTH PROPOSALS_          

1)  Identifying peers that use the FT extensions.

Both proposals have essentially similar means of doing this - an option that
says "I can do FT" and a separate option that says "I want to use preserved
state".   We will merge the proposals, incorporating the use of U-bit from
[MATTHEWS] and the procedural detail from [FARREL].

2)  Identification of FT LDP Exchanges

We will use a variant on the scheme in [FARREL] to identify FT labels.

3)  Synchronizing state

Both proposals use acknowledgements to determine when a state change has
been handed over to the LSR peer, though the philosophy is a bit different.
[MATTHEWS] adds an explicit ACK to every message (bad), but then uses
piggybacking and a sequence number to reduce the number of ACKs flying about
(good).  [FARREL] exploits the implicit "acks" already in the LDP protocol
(good), but has to add explicit acks to cover the cases where the base LDP
protocol is insufficient (bad).

[MATTHEWS] uses ACKs based on the LDP message ID.  We decided this was
unacceptable becaue of the constraints it placed on the use of the message
ID, but that a variant using a new FT sequeunce number is workable. This is,
in fact, then very reminiscent of the Nr handling in LLC2.  One possible
implementation would be to always include the last received (& secured) FT
sequence number (assuming we use seq# not msg ID) in each LDP PDU sent by an
FT peer.  This gives timely acks to all messages if the LDP session is busy,
with a fall-back of ACKing at least at every keepalive interval.  This would
lead to a degenerate case where the protocol introduces an 8-byte overhead
on every message (if only one message is sent in each PDU), but does avoid
building up lots of unacknowledged state.  The actual overhead should be
less than that in most cases.  

In comparison, [FARREL] has a fixed overhead of one additional Notification
message sent per down-stream unsolicited Label Mapping and per Address
message (assuming we add that - see (4) below) plus a variable overhead of
one Notification message per Label Release/Label Abort in a couple of X-over
cases.  [FARREL] also does not allow for "early" acking of, say, a Label
Request message before the Label Mapping is sent back upstream, which
[MATTHEWS] does permit.

Extendability is an issue for both proposals.  Although [MATTHEWS] has the
edge here in that should provide a mechanic that works for new message
flows, both proposals potentially suffer from future interop problems if the
authors of future MPLS drafts don't give some consideration to how their
enhancements interact with FT.  In particular, the procedures that a LSR
should use to recover a new message flow are not necessarily as simple as
just reissuing the "lost" messages.  There's not much we can do about this,
though, other than put some text into our draft encouraging future MPLS
authors to consider how their proposals interact with FT.

We did also discuss some concerns about whether the [MATTHEWS] ACK scheme
would complicate multi-threading of LDP message handling, but came to the
conclusion that as long as the FT sequence number is a per-label space
entiry, [MATTHEWS] presents no greater MP issues than the base LDP protocol.

On balance, we agreed to adope the [MATTHEWS] ACK scheme, modified to use a
new FT sequence number.

4)  Trusting the peer LSRs

Both proposals place a high degree of trust on the peer LSRs.  In
particular, there is no resynchronization of the preserved label state.
This is not a trivial assumption to make, though it is an important one if
we are to end up with a scalable FT solution.  This makes it very important
that the FT draft includes sufficient detail on procedures to give us better
confidence that trusted LSR peers will behave in an interoperable manner.  

One particular focus of our discussions was the Address messages.  It is
relatively easy to make this exchange secure using the mechanics from either
proposal, but if this information ever gets out of sync, it could affect the
operation of many labels. In contrast, failure to synchronize state on one
label affects only that label.  On balance, though, we think it is better to
avoid any ambiguity over the validity of Address ranges exchanged on a
previous instantiation of a recovered LDP session and require that both FT
LSRs treat such exchanges having continued validity after recovery until an
address range is explicitly withdrawn.