[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02

Network Working Group                                        P. Francois
Internet Draft                                            O. Bonaventure
Expiration Date: January 2006                                   M. Shand
                                                              S. Previdi
                                                               S. Bryant

                                                              July 2005

            Loop-free convergence using ordered FIB updates
                   draft-francois-ordered-fib-00.txt


Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet Drafts are working documents of the Internet Engineering
   Task Force (IETF), its Areas, and its Working Groups. Note that other
   groups may also distribute working documents as Internet Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than a "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Abstract

   This draft proposes a mechanism to prevent transient loops during
   non-urgent topology changes by ordering the FIB updates on routers,
   in networks which use link state routing protocols. This mechanism
   can be used in case of graceful link shutdowns, metric changes and
   when a link is enabled. The solution can also be used in conjunction
   with an IPFRR mechanism wich turns a sudden link failure in a non-
   urgent change, by ensuring a local protection of the link. After a
   non-urgent topology change, each routers computes a rank that defines
   the time at which it can safely update its FIB. A completion message
   mechanism is also proposed in order to speed up the convergence
   process.



Francois et al.           Expires January 2006                  [Page 1]


Internet Draft             Ordered FIB Updates                July 2005


1. Introduction

   With link-state protocols [ISIS,OSPF], when the network topology
   changes, some routers need to modify their Forwarding Information
   Base (FIB) to take into account the new topology. Each topology
   change causes a convergence phase. During this phase, routers may
   transiently have inconsistent FIBs, which leads to packet loops and
   losses, even if the reachability of the destinations is not
   compromised after the topology change. When the link state change is
   a metric update and when a new link is brought up in the network,
   there is no direct loss of connectivity, but transient loops during
   the convergence phase may still cause packet loss. The same
   observation can be made in the case of a link failure. If the link is
   protected [IPFRR,MPLSFRR], a loop free convergence mechanism may also
   be used in place of the usual fast, best effort approach.

   The remainder of this document is organised as follows. We first show
   in section 2 that there is an ordering for the FIB updates when a
   single link fails, is activated or when an IGP metric changes. We
   also present an ordering for the cases of node failure and node
   activation. In section 3, we present an implementation of the
   ordering schemes. In section 4, a mechanism aimed at speeding up the
   loop-free convergence process is presented. In section 5, we present
   additional shortcuts to the ordering scheme.

2. Ordering of the FIB updates

   In this section, we briefly present an ordering of the FIB updates
   that allows to avoid transient forwarding loops in the network in the
   case of topology changes. A more precise analysis of the rerouting
   dynamics and correctness proofs of the mechanism can be found in
   [PFOB05].

2.1 Link down / metric increase

   We first consider the failure of a link or the increase of the metric
   associated with one directed link. In this case, to ensure the
   transient consistency of the forwarding tables of the routers, a
   router R should update its FIB AFTER all the routers that used R
   BEFORE the event, to reach the affected link.

   Let us show that this rule ensures the transient consistency of the
   routers.  We assume that the link X->Y goes down and is protected, or
   its metric is increased.

   Firstly, once a packet reaches a router R with an outdated FIB for
   its destination, it will only traverse routers with an outdated FIB,
   according to the rule.  It thus reaches X, whose protection will



Francois et al.           Expires January 2006                  [Page 2]


Internet Draft             Ordered FIB Updates                July 2005


   ensure that the packet reaches its destination. In the case of a
   metric increase, the packet will simply be forwarded along X->Y and
   reach its destination.

   Secondly, a packet cannot loop while being exclusively forwarded by
   routers with an updated FIB, so that any packet is proved to never
   enter a loop.

   In other words, when the ordering is respected, a packet entering the
   network that follows a path composed of updated or unaffected routers
   cannot loop. If it reaches an outdated router, it cannot reach an
   updated router anymore, so that it will not loop.

2.2 Link up / metric decrease

   In the case of link up events or metric decreases, to ensure the
   transient consistency of the forwarding tables of the routers, a
   router R should update its FIB BEFORE the routers that WILL use R to
   reach the affected link.

   Let us show that this rule ensures the transient consistency of the
   routers. We assume that the link X->Y goes up or that its metric is
   decreased.

   Firstly, when a packet reaches a router R that has updated its FIB,
   all the routers on the path from R to X have updated their FIB, so
   that the packet will reach X and be forwarded along X->Y, to finally
   reach its destination.

   Secondly, a packet could not loop between routers that have not yet
   updated their FIB, so that any packet is proved to never enter a
   loop.

2.3 Router down

   An ordering of the FIB updates can also be performed to avoid
   transient loops in the case of a router down event. There are
   multiple implementation choices to advertise the failure of a node.
   Firstly, a router being shut down can send a new link-state packet
   that describes the failure of all its links, by setting the age of
   each link to MAX_AGE. Secondly, the router can purge its own link-
   state packet. Finally, and only in IS-IS, the router can send its
   link-state packet by setting the overload-bit.  All those solutions
   will let the other routers of the network know about the failure by
   receiving one single message.

   The other routers of the network can avoid loops while adapting to
   the node failure by respecting a rule that is very similar to the one



Francois et al.           Expires January 2006                  [Page 3]


Internet Draft             Ordered FIB Updates                July 2005


   mentioned in the case of a link down event.

   A router R should update its FIB AFTER all the routers that use R to
   reach the router that is shutdown.

   Let us show that this ordering ensures the transient consistency of
   the forwarding.  We assume that the router X is shut down.

   Firstly, if a packet to a destination D reaches a router that has not
   updated its FIB and that used X to reach D, it will only traverse
   routers that have not updated their FIB, to finally reach X. X will
   then forward the packet to its nexthop for D, and the packet will
   reach its destination. This nexthop could not have X in its path(s)
   to D before the event, as the contrary would mean that there was a
   loop before the event.  Secondly, a packet that does not reach a
   router with an outdated FIB cannot loop.


2.4 Router up

   In IS-IS, when a router X is brought up, it should firstly send its
   link-state packet with an overload bit set.  After a while, each of
   its neighbours will have sent a link-state packet describing their
   links to X as being up. At that moment, X can send a link-state
   packet with an overload bit unset, so that the processing of this
   link-state packet by the other routers will make them consider all
   the links connected to X as being up, in one single FIB update.

   In OSPF, the overload-bit does not exists. An OSPF router that is
   brought up should thus wait for a while before sending its own LSA,
   or firstly send its LSA with a MAX-METRIC assigned to each of its
   links, and only send a LSA with the real metrics after a while.

   By proceeding like this, we have the opportunity to order those FIB
   updates and avoid forwarding inconsistencies during the convergence.

   The ordering of the FIB updates follows a rule that is very similar
   to the rule mentioned in the case of a link up event. A router R
   should update its FIB BEFORE all the routers that WILL use R to reach
   the router that is brought up.

   Let us show that this ordering ensures the transient consistency of
   the forwarding.  We assume that the router X comes in the network.

   Firstly, when a packet with destination D reaches a router R that has
   already updated its FIB, and that uses X to reach D, the packet will
   reach X as it will traverse routers that have already updated their
   FIB. X will then forward the packet to its nexthop for destination D.



Francois et al.           Expires January 2006                  [Page 4]


Internet Draft             Ordered FIB Updates                July 2005


   The path from this nexthop to D cannot contain X, so that the packet
   is proved to be consistently forwarded to D.  Secondly, a packet that
   exclusively traverses routers with an outdated FIB cannot loop.



3. Implementation of the ordering

   In this section, we show how the proposed ordering can be applied by
   routers that have to adapt to a topology change.

3.1 Link down / metric increase

   To respect the proposed ordering, routers can compute a rank that
   will be used to determine the time at which they can perform their
   FIB update. In the case of the failure of link X->Y or an increase of
   the metric of link X->Y, router R will compute the reverse Shortest
   Path Tree (rSPT) of Y. This rSPT gives the shortest paths to reach Y.
   The branch of the reverse SPT that is below R corresponds to the set
   of shortest paths to R that are used by the routers that reach X->Y
   via R.

   The rank of router R is defined as the depth (in number of hops) of
   this branch.  To avoid confusion in the case of ECM paths, we can say
   that the the maximum depth must be taken into account.

   Router R will update its FIB at time : T0 + rank * MAX_FIB where T0
   is the arrival time of the link-state packet containing the topology
   change and MAX_FIB a network-wide constant that reflects the maximum
   time required to update a FIB. The value of MAX_FIB is implementation
   specific and is out of the scope of this document.  This value must
   be agreed by all the routers of the network. This agreement can be
   done by using a capability TLV as defined in [SLFTV].

   All the routers that use R to reach X->Y will compute a lower rank
   than R, so that the order will be respected.  It should be noted that
   only the routers that used X->Y before the event have to compute
   their rank.


3.2 Link up / metric decrease

   In the case of a link up or a link metric decrease affecting link
   X->Y, a router R must have a rank that is higher than the rank of the
   routers that it will use to reach X->Y, according to the rule
   mentioned in 2.2. The rank of R is thus equal to the number of hops
   between R and X in its Shortest Path Tree. When R has multiple equal
   cost paths to X, the rank is the length of the longest path in hops



Francois et al.           Expires January 2006                  [Page 5]


Internet Draft             Ordered FIB Updates                July 2005


   to X.

   Router R will update its FIB at time : T0 + rank * MAX_FIB where T0
   is the arrival time of the link-state packet containing the topology
   change and MAX_FIB a network-wide constant that reflects the maximum
   time required to update a FIB.

   It should be noted that only the routers that use X->Y after the
   event have to compute a rank, i.e. only the routers that have X->Y in
   their SPT after the link-state change.

   3.3 Router down

   When a router X is shutdown, the rank that has to be applied by a
   router R is equal to the depth of the branch under R in rSPT(X). In
   the case of ECM paths to R, the maximum of the length must be taken
   into account.  Note that X will only be shutdown once all the routers
   have updated their FIB.  The rank that is computed by X thus gives
   the time at which X can be effectively shut down.


   3.4 Router up

   When a router X comes in the network, the rank that has to be applied
   by a router R is equal to the maximum length of its ECM paths to X,
   in its updated Shortest Path Tree. Note that X will be the first to
   update its FIB, as it will have a rank equal to 0. This translates
   the fact that X must have built its FIB before any router can use it
   to forward packets.

4. Completion messages

   As noted in the previous sections, only the routers that are
   currently using a link affected by a topology change need to update
   their FIB. The FIB of all the other routers does not need to be
   updated at all. Furthermore, the routers that need to update their
   FIB do not necessarily need MAX_FIB seconds to perform their FIB
   update [CCRJULY].

   In this section, we show how completion messages can be used to speed
   up the convergence after a non-urgent topology change by shortcuting
   the computed rank while respecting the transient consistency of the
   routers.

   To do this, we adapt the mechanism proposed in [INFOCOM].  Routers
   maintain a waiting list, that lists the neighbours from which they
   have to wait for a completion message before being allowed to update
   their own FIB. Upon reception of a completion message from a



Francois et al.           Expires January 2006                  [Page 6]


Internet Draft             Ordered FIB Updates                July 2005


   neighbour, a router removes this neighbour from its waiting list.
   Once its waiting list becomes empty, the router is allowed to update
   its FIB.  The next sections explain how the waiting list must be
   built for each type of event, and when completion messages are sent
   by the routers.


4.1 Link down / metric increase

   Let us assume that the link X->Y goes down, or its metric is
   increased.  A router R that currently has X->Y in its SPT computes
   rSPT(Y) to determine its rank.  By doing this, it computes the set of
   routers (and thus implicitly the set of its neighbours) that use it
   to reach link X->Y. The waiting list of R is equal to the set of
   neighbours that use it to reach X->Y. These are the neighbours below
   R in rSPT(Y).

   The current SPT of R gives the set of neighbours that it uses to
   reach X->Y.  These neighbours have to wait for R, and R is thus
   present in their waiting list. This set of neighbours is the set of
   neighbours to which R will send its completion messages, once it has
   updated its FIB.


4.2 Link up / metric decrease

   Let us assume that the link X->Y goes up, or its metric is updated.
   A router R will compute its new SPT (SPT_new(R)). If X->Y is in
   present in SPT_new(R), R will use link X->Y and thus needs to compute
   its rank.  For this, R computes the set of routers (and implicitly
   its set of neighbours) that it uses to reach X->Y. The nexthops for X
   in SPT_new(R).  R must reroute after those routers to respect the
   ordering. Its waiting list is thus equal to those nexthops.

   When R has updated its FIB, it can send a completion message to its
   neighbours, so that a neighbour that has R in its waiting list will
   be allowed to remove R from it.

4.3 Router down

   Let us assume that a router X goes down. A router R will compute
   rSPT(X) to determine its rank.  When doing this, it also computes the
   set of its neighbours that uses R to reach X. The waiting list of R
   is equal to this set.

   The current SPT of R gives the set of neighbours that will have R in
   their waiting list.  Once R has updated its FIB, it will send its
   completion messages to those neighbours.



Francois et al.           Expires January 2006                  [Page 7]


Internet Draft             Ordered FIB Updates                July 2005


4.4 Router up

   Let us assume that a router X comes in the network. A router R will
   compute its new SPT.  It thus also computes its nexthops for X. This
   set of nexthops (more than one in the case of equal cost paths to X)
   is the waiting list that R will use.

   Once R has updated its FIB, it sends a completion message to its
   neighbours, so that a neighbour that has R in its waiting list will
   be allowed to remove R from it.


5. Ranking Shortcuts.

   In the case of a link (X->Y) down or metric increase, a router R can
   sometimes shortcut its rank because it can decide, when computing the
   rSPT, which neighbours are not affected by the event. These are the
   neighbours that did not use the link X->Y, so that their paths to all
   the destinations do not change.

   Let us assume that link X->Y goes down. While R computes rSPT(Y), it
   can mark the routers that use the link X->Y. These are the routers
   that are below X->Y in the rSPT. If a neighbour N of R is not marked,
   all the FIB updates that will let packets be forwarded to N by R can
   be performed directly.  Note that if N uses Y->X, R can still reroute
   to N because R and N are not affected for the same set of
   destinations, so that the destinations affected in R, using X->Y, are
   never affected in a router N using Y->X.

   If a FIB update contains an ECMP entry for a destination d, and not
   all the nexthops for d were not marked, then the normal ranking can
   be applied for this destination, or the FIB update will have to be
   modified in order to only reroute to the unmarked nexthops.  In this
   case, a new FIB update will have to be performed for d when the rank
   timer has elapsed or all the necessary completion messages have
   arrived.  The choice between these two solutions is a trade-off
   between an increased number of FIB updates and a faster convergence.


References

   [OSPF]    J. Moy, OSPF Version 2. RFC 2328. Apr. 1998.

   [IS-IS]   "Intermediate system to Intermediate system routeing
             information exchange protocol for use in conjunction
             with the Protocol for providing the Connectionless-mode
             Network Service (ISO 8473)," ISO/IEC 10589:2002,
             Second Edition.



Francois et al.           Expires January 2006                  [Page 8]


Internet Draft             Ordered FIB Updates                July 2005


   [IPFRR]   M. Shand, S. Bryant, IP Fast Reroute Framework,
             draft-ietf-rtgwg-ipfrr-framework-03.txt, June 2005

   [MPLSFRR] Pan, P. et al, "Fast Reroute Extensions to RSVP-TE for LSP
             Tunnels", RFC 4090

   [PFOB05]  P. Francois, O. Bonaventure. Avoiding transient loops
             during IGP convergence. IEEE INFOCOM 2005, March 2005,
             Miami, Fl., USA

   [CCRJULY] P. Francois, C. Filsfils, J. Evans, O. Bonaventure.
             Achieving sub-second IGP convergence in large IP networks,
             ACM SIGCOMM Computer Communication Review, July 2005

   [SLFTV]   A. Atlas, S. Bryant, M. Shand, Synchronization of Loop Free
             Timer Values, draft-atlas-bryant-shand-lf-timers-00.txt



Appendix A : Pseudo-codes

   Figure 1 shows the pseudocode for the router reaction in case of non-
   urgent link failure or metric increase.

   Pseudo-code for link (X->Y) down/metric increase in router R :

   If(X->Y in SPT(R)){
     //R is affected by the event
     //Compute rspt(Y)
     rspt = rSPT(Y);

     //compute the rank from rspt (can also be done directly
     //during rspt computation)

     worst_case_update_delay = depth(R,rspt) * MAX_FIB

     //Build the waiting list : these are the neighbours below R in rspt
     //
     WaitingList = getNeighboursUpstream(R,rspt);
     //Build the list of neighbours to which R will send a
     //completion message :
     //these are the nexthops for X in the current SPT of R
     completionMessageSendingList = nexthops(X,SPT(R));

     //Wait for the waiting list to be empty or the rank time
     //to elapse.
     while(not WaitingList.empty()
           || worst_case_update_delay.elapsed()){



Francois et al.           Expires January 2006                  [Page 9]


Internet Draft             Ordered FIB Updates                July 2005


       if(completionMessageReceived()){
         //New completion message received
         WaitingList.remove(completionMessage.sender);
       }
     }
     //Rank time has elapsed or waiting list is empty
     UpdateFIB();
     //FIB has been updated, send completion messages
     ForEach(N in completionMessageSendingList){
     send(N,"FIB Updated for X->Y");
     }
   }

   else{
   //R is not affected by the event, nothing to do
   }
            Figure 1 : Pseudocode for link down/metric increase

   Figure 2 provides the pseudocode for the reaction of a router to a
   non-urgent link up or metric decrease event.


   Pseudo-code for link (X->Y) up/metric decrease in router R :

   //Compute the new SPT.
   newSPT = computeSPT(R)
   If(X->Y in newSPT){
     //R is affected by the event
     //compute the rank of the router. This is the length (in hops)
     //from R to X in the new spt. (note that it is equal to the
     //length from R to X in the old spt.
     worst_case_update_delay = PathLength(R,X,newSPT) * MAX_FIB

     //Build the waiting list : these are the nexthops for X in the new SPT.
     WaitingList = nexthops(R,X,newSPT);

     //Wait for the waiting list to be empty or the rank time to elapse.
     while(not WaitingList.empty() || worst_case_update_delay.elapsed()){
       if(completionMessageReceived()){
         //New completion message received
         WaitingList.remove(completionMessage.sender);
       }
     }
     //Rank time has elapsed or waiting list is empty
     UpdateFIB();
     //Fib updated, send completion messages to the neighbours.
     ForEach(N in Neighbours(R))
     Send(N,"Fib Updated X->Y");



Francois et al.           Expires January 2006                 [Page 10]


Internet Draft             Ordered FIB Updates                July 2005


   }

   else{
   //R is not affected by the event, nothing to do
   }
             Figure 2 : Pseudocode for link up/metric decrease

Authors Addresses

   Pierre Francois
   Universite catholique de Louvain
   Place Sainte Barbe, 2
   B-1348, Louvain-La-Neuve
   Belgium
   Email: pfr@info.ucl.ac.be

   Olivier Bonaventure
   Universite catholique de Louvain
   Place Ste Barbe, 2
   B-1348, Louvain-La-Neuve
   Belgium
   Email: Bonaventure@info.ucl.ac.be

   Mike Shand
   Cisco Systems,
   250, Longwater Avenue,
   Green Park,
   Reading, RG2 6GB,
   United Kingdom
   Email: mshand@cisco.com

   Stefano Previdi
   Cisco Systems
   Via Del Serafico 200
   00142 Roma - Italy
   Email : sprevidi@cisco.com


   Stewart Bryant
   Cisco Systems,
   250, Longwater Avenue,
   Green Park,
   Reading, RG2 6GB,
   United Kingdom
   Email: stbryant@cisco.com






Francois et al.           Expires January 2006                 [Page 11]


Internet Draft             Ordered FIB Updates                July 2005


Intellectual Property Considerations

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights. Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard. Please address the information to the IETF at ietf-
   ipr@ietf.org.

Full Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.














Francois et al.           Expires January 2006                 [Page 12]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/