Skip to main content

A Framework for Loop-Free Convergence
draft-ietf-rtgwg-lf-conv-frmwk-07

The information below is for an old version of the document that is already published as an RFC.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 5715.
Authors Mike Shand , Stewart Bryant
Last updated 2018-12-20 (Latest revision 2009-10-20)
Replaces draft-bryant-shand-lf-conv-frmwk
RFC stream Internet Engineering Task Force (IETF)
Intended RFC status Informational
Formats
Reviews
Additional resources Mailing list discussion
Stream WG state (None)
Document shepherd (None)
IESG IESG state Became RFC 5715 (Informational)
Action Holders
(None)
Consensus boilerplate Unknown
Telechat date (None)
Responsible AD Ross Callon
Send notices to (None)
draft-ietf-rtgwg-lf-conv-frmwk-07
Internet-Draft    A Framework for Loop-free Convergence     October 2009

   additional mechanisms these loops could remain in place for a
   significant time.

   It should be noted that this method requires per router ordering, but
   not per prefix ordering.  A router must wait its turn to update its
   FIB, but it should then update its entire FIB.

   When an SRLG failure occurs a router must classify traffic into the
   classes that pass over each member of the SRLG.  Each router is then
   independently assigned a ranking with respect to each SRLG member for
   which they have a traffic class.  These rankings may be different for
   each traffic class.  The prefixes of each class are then changed in
   the FIB according to the ordering of their specific ranking.  Again,
   as for the single failure case, signaling may be used to speed up the
   convergence process.

   Note that the special SRLG case of a full or partial node failure,
   can be dealt with without using per prefix ordering, by running a
   single reverse SPF computation rooted at the failed node (or common
   point of the subset of failing links in the partial case).

   There are two classes of signaling optimization that can be applied
   to the ordered FIB loop-prevention method:

   o  When the router makes NO change, it can signal immediately.  This
      significantly reduces the time taken by the network to process
      long chains of routers that have no change to make to their FIB.

   o  When a router HAS changed, it can signal that it has completed.
      This is more problematic since this may be difficult to determine,
      particularly in a distributed architecture, and the optimization
      obtained is the difference between the actual time taken to make
      the FIB change and the worst case timer value.  This saving could
      be of the order of one second per hop.

   There is another method of executing ordered FIB which is based on
   pure signaling [SIG].  Methods that use signaling as an optimization
   are safe because eventually they fall back on the established IGP
   mechanisms which ensure that networks converge under conditions of
   packet loss.  However a mechanism that relies on signaling in order
   to converge requires a reliable signaling mechanism which must be
   proven to recover from any failure circumstance.

6.8.  Synchronised FIB Update

   Micro-loops form because of the asynchronous nature of the FIB update
   process during a network transition.  In many router architectures it
   is the time taken to update the FIB itself that is the dominant term.

Shand & Bryant           Expires April 23, 2010                [Page 17]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

   One approach would be to have two FIBs and, in a synchronized action
   throughout the network, to switch from the old to the new.  One way
   to achieve this synchronized change would be to signal or otherwise
   determine the wall clock time of the change, and then execute the
   change at that time, using NTP [RFC1305] to synchronize the wall
   clocks in the routers.

   This approach has a number of major issues.  Firstly two complete
   FIBs are needed which may create a scaling issue and secondly a
   suitable network wide synchronization method is needed.  However,
   neither of these are insurmountable problems.

   Since the FIB change synchronization will not be perfect there may be
   some interval during which micro-loops form.  Whether this scheme is
   classified as a micro-loop prevention mechanism or a micro-loop
   mitigation mechanism within this taxonomy is therefore dependent on
   the degree of synchronization achieved.

   This mechanism works identically for both "bad-news" and "good-news"
   events.  It also works identically for SRLG failure.  Further
   consideration needs to be given to interoperating with routers that
   do not support this mechanism.  Without a suitable interoperating
   mechanism, loops may form for the duration of the synchronization
   delay.

7.  Using PLSN In Conjunction With Other Methods

   All of the tunnel methods and packet marking can be combined with
   PLSN (Section 5.2)[I-D.ietf-rtgwg-microloop-analysis] to reduce the
   traffic that needs to be protected by the advanced method.
   Specifically all traffic could use PLSN except traffic between a pair
   of routers both of which consider the destination to be type C. The
   type C to type C traffic would be protected from micro-looping
   through the use of a loop prevention method.

   However, determining whether the new next hop router considers a
   destination to be type C may be computationally intensive.  An
   alternative approach would be to use a loop prevention method for all
   local type C destinations.  This would not require any additional
   computation, but would require the additional loop prevention method
   to be used in cases which would not have generated loops (i.e. when
   the new next-hop router considered this to be a type A or B
   destination).

   The amount of traffic that would use PLSN is highly dependent on the
   network topology and the specific change, but would be expected to be
   in the region %70 to %90 in typical networks.

Shand & Bryant           Expires April 23, 2010                [Page 18]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

   However, PLSN cannot be combined safely with Ordered FIB.  Consider
   the network fragment shown below:

                      R
                     /|\
                    / | \
                  1/ 2|  \3
                  /   |   \    cost S->T = 10
           Y-----X----S----T   cost T->S = 1
           |  1     2      |
           |1              |
           D---------------+
                  20

   On failure of link XY, according to PLSN, S will regard R as a safe
   neighbor for traffic to D. However the ordered FIB rank of both R and
   T will be zero and hence these can change their FIBs during the same
   time interval.  If R changes before T, then a loop will form around
   R, T and S. This can be prevented by using a stronger safety
   condition than PLSN currently specifies, at the cost of introducing
   more type C routers, and hence reducing the PLSN coverage.

8.  Loop Suppression

   A micro-loop suppression mechanism recognizes that a packet is
   looping and drops it.  One such approach would be for a router to
   recognize, by some means, that it had seen the same packet before.
   It is difficult to see how sufficiently reliable discrimination could
   be achieved without some form of per-router signature such as route
   recording.  A packet recognizing approach therefore seems infeasible.

   An alternative approach would be to recognize that a packet was
   looping by recognizing that it was being sent back to the place that
   it had just come from.  This would work for the types of loop that
   form in symmetric cost networks, but would not suppress the cyclic
   loops that form in asymmetric networks, and as a result of multiple
   failures.

   This mechanism operates identically for both "bad-news" events,
   "good-news" events and SRLG failure.

9.  Compatibility Issues

   Deployment of any micro-loop control mechanism is a major change to a
   network.  Full consideration must be given to interoperation between
   routers that are capable of micro-loop control, and those that are

Shand & Bryant           Expires April 23, 2010                [Page 19]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

   not.  Additionally there may be a desire to limit the complexity of
   micro-loop control by choosing a method based purely on its
   simplicity.  Any such decision must take into account that if a more
   capable scheme is needed in the future, its deployment might be
   complicated by interaction with the scheme previously deployed.

10.  Comparison of Loop-free Convergence Methods

   PLSN [I-D.ietf-rtgwg-microloop-analysis] is an efficient mechanism to
   prevent the formation of micro-loops, but is only a partial solution.
   It is a useful adjunct to some of the complete solutions, but may
   need modification.

   Incremental cost advertisement in its simplest form is impractical as
   a general solution because it takes too long to complete.  Optimized
   Incremental cost advertisement, however, completes in much less time
   and requires no assistance from other routers in the network.  It is
   therefore, useful for network reconfiguration operations.

   Packet Marking is probably impractical because of the need to find
   the marking bit and to change the forwarding behavior.

   Of the remaining methods, distributed tunnels is significantly more
   complex than nearside or farside tunnels, and should only be
   considered if there is a requirement to distribute the tunnel
   decapsulation load.

   Synchronised FIBs is a fast method, but has the issue that a suitable
   synchronization mechanism needs to be defined.  One method would be
   to use NTP [RFC1305], however the coupling of routing convergence to
   a protocol that uses the network may be a problem.  During the
   transition there will be some micro-looping for a short interval
   because it is not possible to achieve complete synchronization of the
   FIB changeover.

   The ordered FIB mechanism has the major advantage that it is a
   control plane only solution.  However, SRLGs require a per-
   destination calculation, and the convergence delay may be high,
   bounded by the network diameter.  The use of signaling as an
   accelerator may reduce the number of destinations that experience the
   full delay, and hence reduce the total re-convergence time to an
   acceptable period.

   The nearside and farside tunnel methods deal relatively easily with
   SRLGs and uncorrelated changes.  The convergence delay would be
   small.  However these methods require the use of tunneled forwarding
   which is not supported on all router hardware, and raises issues of

Shand & Bryant           Expires April 23, 2010                [Page 20]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

   forwarding performance.  When used with PLSN, the amount of traffic
   that was tunneled would be significantly reduced, thus reducing the
   forwarding performance concerns.  If the selected repair mechanism
   requires the use of tunnels, then a tunnel based loop prevention
   scheme may be acceptable.

11.  IANA Considerations

   There are no IANA considerations that arise from this draft.

12.  Security Considerations

   This document analyzes the problem of micro-loops and summarizes a
   number of potential solutions that have been proposed.  These
   solutions require only minor modifications to existing routing
   protocols and therefore do not add additional security risks.
   However a full security analysis would need to be provided within the
   specification of a particular solution proposed for deployment.

13.  Acknowledgments

   The authors would like to acknowledge contributions to this document
   made by Clarence Filsfils.

14.  Informative References

   [I-D.atlas-bryant-shand-lf-timers]
              K, A. and S. Bryant, "Synchronisation of Loop Free Timer
              Values", draft-atlas-bryant-shand-lf-timers-04 (work in
              progress), February 2008.

   [I-D.bryant-ipfrr-tunnels]
              Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP
              Fast Reroute using tunnels", draft-bryant-ipfrr-tunnels-03
              (work in progress), November 2007.

   [I-D.ietf-rtgwg-ipfrr-framework]
              Shand, M. and S. Bryant, "IP Fast Reroute Framework",
              draft-ietf-rtgwg-ipfrr-framework-12 (work in progress),
              September 2009.

   [I-D.ietf-rtgwg-ipfrr-notvia-addresses]
              Shand, M., Bryant, S., and S. Previdi, "IP Fast Reroute
              Using Not-via Addresses",

Shand & Bryant           Expires April 23, 2010                [Page 21]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

              draft-ietf-rtgwg-ipfrr-notvia-addresses-04 (work in
              progress), July 2009.

   [I-D.ietf-rtgwg-microloop-analysis]
              Zinin, A., "Analysis and Minimization of Microloops in
              Link-state Routing Protocols",
              draft-ietf-rtgwg-microloop-analysis-01 (work in progress),
              October 2005.

   [I-D.ietf-rtgwg-ordered-fib]
              Francois, P., "Loop-free convergence using oFIB",
              draft-ietf-rtgwg-ordered-fib-02 (work in progress),
              February 2008.

   [OPT]      Francois, P., Shand, M., and O. Bonaventure, "Disruption
              free topology reconfiguration in OSPF networks"", IEEE
              INFOCOM May 2007, Anchorage, 2007.

   [RFC1305]  Mills, D., "Network Time Protocol (Version 3)
              Specification, Implementation", RFC 1305, March 1992.

   [RFC2475]  Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z.,
              and W. Weiss, "An Architecture for Differentiated
              Services", RFC 2475, December 1998.

   [RFC3168]  Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
              of Explicit Congestion Notification (ECN) to IP",
              RFC 3168, September 2001.

   [RFC4090]  Pan, P., Swallow, G., and A. Atlas, "Fast Reroute
              Extensions to RSVP-TE for LSP Tunnels", RFC 4090,
              May 2005.

   [RFC5036]  Andersson, L., Minei, I., and B. Thomas, "LDP
              Specification", RFC 5036, October 2007.

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

Shand & Bryant           Expires April 23, 2010                [Page 22]
Internet-Draft    A Framework for Loop-free Convergence     October 2009

Authors' Addresses

   Mike Shand
   Cisco Systems
   250, Longwater Ave,
   Green Park,, Reading,  RG2 6GB,
   United Kingdom.

   Email: mshand@cisco.com

   Stewart Bryant
   Cisco Systems
   250, Longwater Ave,
   Green Park,, Reading,  RG2 6GB
   United Kingdom.

   Email: stbryant@cisco.com

Shand & Bryant           Expires April 23, 2010                [Page 23]