diff options
Diffstat (limited to 'doc/rfc/rfc6976.txt')
| -rw-r--r-- | doc/rfc/rfc6976.txt | 1571 |
1 files changed, 1571 insertions, 0 deletions
diff --git a/doc/rfc/rfc6976.txt b/doc/rfc/rfc6976.txt new file mode 100644 index 0000000..9ce3528 --- /dev/null +++ b/doc/rfc/rfc6976.txt @@ -0,0 +1,1571 @@ + + + + + + +Internet Engineering Task Force (IETF) M. Shand +Request for Comments: 6976 Individual Contributor +Category: Informational S. Bryant +ISSN: 2070-1721 S. Previdi + C. Filsfils + Cisco Systems + P. Francois + Institute IMDEA Networks + O. Bonaventure + Universite catholique de Louvain + July 2013 + + + Framework for Loop-Free Convergence + Using the Ordered Forwarding Information Base (oFIB) Approach + +Abstract + + This document describes an illustrative framework of a mechanism for + use in conjunction with link-state routing protocols that prevents + the transient loops that would otherwise occur during topology + changes. It does this by correctly sequencing the forwarding + information base (FIB) updates on the routers. + + This mechanism can be used in the case of non-urgent (management + action) link or node shutdowns and restarts or link metric changes. + It can also be used in conjunction with a fast reroute mechanism that + converts a sudden link or node failure into a non-urgent topology + change. This is possible where a complete repair path is provided + for all affected destinations. + + After a non-urgent topology change, each router computes a rank that + defines the time at which it can safely update its FIB. A method for + accelerating this loop-free convergence process by the use of + completion messages is also described. + + The technology described in this document has been subject to + extensive simulation using pathological convergence behavior and real + network topologies and costs. However, the mechanisms described in + this document are purely illustrative of the general approach and do + not constitute a protocol specification. This document represents a + snapshot of the work of the Routing Area Working Group at the time of + publication and is published as a document of record. Further work + is needed before implementation or deployment. + + + + + + + +Shand, et al. Informational [Page 1] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +Status of This Memo + + This document is not an Internet Standards Track specification; it is + published for informational purposes. + + This document is a product of the Internet Engineering Task Force + (IETF). It represents the consensus of the IETF community. It has + received public review and has been approved for publication by the + Internet Engineering Steering Group (IESG). Not all documents + approved by the IESG are a candidate for any level of Internet + Standard; see Section 2 of RFC 5741. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + http://www.rfc-editor.org/info/rfc6976. + +Copyright Notice + + Copyright (c) 2013 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents + (http://trustee.ietf.org/license-info) in effect on the date of + publication of this document. Please review these documents + carefully, as they describe your rights and restrictions with respect + to this document. Code Components extracted from this document must + include Simplified BSD License text as described in Section 4.e of + the Trust Legal Provisions and are provided without warranty as + described in the Simplified BSD License. + + + + + + + + + + + + + + + + + + + + + +Shand, et al. Informational [Page 2] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +Table of Contents + + 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 + 1.1. The Purpose of This Document . . . . . . . . . . . . . . 4 + 1.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 4 + 2. The Required FIB Update Order . . . . . . . . . . . . . . . . 6 + 2.1. Single Link Events . . . . . . . . . . . . . . . . . . . 6 + 2.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 6 + 2.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 7 + 2.2. Multi-Link Events . . . . . . . . . . . . . . . . . . . . 8 + 2.2.1. Router Down Events . . . . . . . . . . . . . . . . . 8 + 2.2.2. Router Up Events . . . . . . . . . . . . . . . . . . 8 + 2.2.3. Line-Card Failure/Restoration Events . . . . . . . . 8 + 3. Applying Ordered FIB Updates . . . . . . . . . . . . . . . . 9 + 3.1. Deducing the Topology Change . . . . . . . . . . . . . . 9 + 3.2. Deciding If Ordered FIB Updates Apply . . . . . . . . . . 9 + 4. Computation of the Ordering . . . . . . . . . . . . . . . . . 10 + 4.1. Link Down, Router Down, or Metric Increase . . . . . . . 10 + 4.2. Link Up, Router Up, or Metric Decrease . . . . . . . . . 11 + 5. Acceleration of Ordered Convergence . . . . . . . . . . . . . 11 + 5.1. Construction of the Waiting List and Notification List . 12 + 5.1.1. Down Events . . . . . . . . . . . . . . . . . . . . . 12 + 5.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 12 + 5.2. Format of Completion Messages . . . . . . . . . . . . . . 13 + 6. Fallback to Conventional Convergence . . . . . . . . . . . . 13 + 7. oFIB State Machine . . . . . . . . . . . . . . . . . . . . . 13 + 7.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 14 + 7.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 15 + 7.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 16 + 7.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . 17 + 7.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . 18 + 8. Management Considerations . . . . . . . . . . . . . . . . . . 18 + 9. Security Considerations . . . . . . . . . . . . . . . . . . . 18 + 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18 + 11. Informative References . . . . . . . . . . . . . . . . . . . 19 + Appendix A. Candidate Methods of Safely Abandoning Loop-Free + Convergence (AAH) . . . . . . . . . . . . . . . . . 20 + A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . 20 + A.2. Hold-Down Timer Only . . . . . . . . . . . . . . . . . . 20 + A.3. AAH Messages . . . . . . . . . . . . . . . . . . . . . . 21 + A.3.1. Per-Router State Machine . . . . . . . . . . . . . . 22 + A.3.2. Per-Neighbor State Machine . . . . . . . . . . . . . 24 + Appendix B. Synchronization of Loop-Free Timer Values . . . . . 25 + B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 25 + B.2. Required Properties . . . . . . . . . . . . . . . . . . . 25 + B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 26 + B.4. Security Considerations Related to Router Timer Values . 27 + + + + +Shand, et al. Informational [Page 3] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +1. Introduction + +1.1. The Purpose of This Document + + This document describes an illustrative framework of a mechanism for + use in conjunction with link-state routing protocols that prevents + the transient loops that would otherwise occur during topology + changes. It does this by correctly sequencing the forwarding + information base (FIB) updates on the routers. + + At the time of publication there is no demand to deploy this + technology; however, in view of the subtleties involved in the design + of extensions for loop-free convergence routing protocols, the + Routing Area Working Group considered it desirable to publish this + document to place on record the design consideration of the ordered + FIB (oFIB) approach. + + The mechanisms presented in this document are purely illustrative of + the general approach and do not constitute a protocol specification. + This document represents a snapshot of the work of the working group + at the time of publication and is published as a document of record. + Additional work is needed to specify the necessary routing protocol + extensions necessary to support this IP fast reroute (FRR) method + before implementation or deployment. + +1.2. Overview + + With link-state protocols, such as IS-IS [ISO10589] and OSPF + [RFC2328], each time the network topology changes, some routers need + to modify their forwarding information bases (FIBs) to take into + account the new topology. Each topology change causes a convergence + phase. During this phase, routers may transiently have inconsistent + FIBs, which may lead to packet loops and losses, even if the + reachability of the destinations is not compromised after the + topology change. Packet losses and transient loops can also occur in + the case of a link down event implied by a maintenance operation, + even if this operation is predictable and not urgent. 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 + packet loops and loss can still occur. + + In this document, a distinction is made between urgent and non-urgent + network events. Urgent events are those that arise from + unpredictable network outages (such as node or link failures) that + are traditionally resolved through the convergence of routing + protocols or by protection mechanisms reliant on fault detection and + reporting (such as through Operations, Administration, and + Maintenance). Non-urgent events are those that arise from + + + +Shand, et al. Informational [Page 4] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + predictable events such as the controlled shutdown of network + resources by a management system, or the modification of network + parameters (such as routing metrics). Typically, non-urgent events + can be planned around, while urgent events must be handled by dynamic + systems. All network events, both urgent and non-urgent, may lead to + transient packet loops and loss. + + For example, in Figure 1, if the link between X and Y is shut down by + an operator, packets destined to X can loop between R and Y when Y + has updated its FIB while R has not yet updated its FIB, and packets + destined to Y can loop between X and S if X updates its FIB before S. + According to the current behavior of IS-IS and OSPF, this scenario + will happen most of the time because X and Y are the first routers to + be aware of the failure, so that they will update their FIBs first. + + 1 + X-------------/-------------Y + | | + | | + | | + | | + 1 | | 1 + | | + | | + | | + | | + S---------------------------R + 2 + + Figure 1: A Simple Topology + + It should be noted that the loops can occur remotely from the + failure, not just adjacent to it. + + [RFC5715] provides an introduction to a number of loop-free + convergence methods, and readers unfamiliar with this technology are + recommended to read it before studying this document in detail. Note + that in common with other loop-free convergence methods, oFIB is only + capable of providing loop-free convergence in the presence of a + single failure. + + The goal of this document is to describe a mechanism that sequences + the router FIB updates to maintain consistency throughout the + network. By correctly setting the FIB change order, no looping or + packet loss can occur. This mechanism may be applied to the case of + managed link-state changes, i.e., link metric change, manual link + down/up, manual router down/up, and managed state changes of a set of + links attached to one router. It may also be applied to the case + + + +Shand, et al. Informational [Page 5] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + where one or more network elements are protected by a fast reroute + mechanism (FRR) [RFC5714] [RFC4090]. The mechanisms that are used in + the failure case are exactly the same as those used for managed + changes. For simplicity, this document makes no further distinction + between managed and unplanned changes. + + It is assumed in the description that follows that all routers in the + routing domain are oFIB capable. This can be verified in an + operational network by having the routers report oFIB capability + using the IGP. Where non-oFIB-capable routers exist in the network, + normal convergence would be used by all routers. The operation of + mixed-mode networks is for further study. + + The technology described in this document has been subject to + extensive simulation using pathological convergence behavior and real + network topologies and costs. A variant of the technology described + here has been experimentally deployed in a production network. + +2. The Required FIB Update Order + + This section provides an overview of the required ordering of the FIB + updates. A more detailed analysis of the rerouting dynamics and + correctness proofs of the mechanism can be found in [refs.PFOB07]. + +2.1. Single Link Events + + For simplicity, the correct ordering for single link changes are + described first. The document then builds on this to demonstrate + that the same principles can be applied to more complex scenarios + such as line-card or node changes. + +2.1.1. Link Down / Metric Increase + + First, consider the non-urgent failure of a link (i.e., where an + operator or a network management system (NMS) shuts down a link, + thereby removing it from the currently active topology) or the + increase of a link metric by the operator or NMS. In this case, a + router R must not update its FIB until all other routers that send + traffic via R and the affected link have first updated their FIBs. + + The following argument shows that this rule ensures the correct order + of FIB changes when the link X->Y is shut down or its metric is + increased. + + An "outdated" FIB entry for a destination is defined as being a FIB + entry that still reflects the shortest path(s) in use before the + topology change. Once a packet reaches a router R that has an + outdated FIB entry for the packet destination, then, provided the + + + +Shand, et al. Informational [Page 6] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + oFIB ordering is respected, the packet will continue to X only + traversing routers that also have an outdated FIB entry for the + destination. The packet thus reaches X without looping and will be + forwarded to Y via X->Y (or in the case of FRR, the X->Y repair path) + and will reach its destination. + + Since it can be assumed that the original topology was loop-free, Y + will never use the link Y->X to reach the destination, and hence the + path(s) between Y and the destination are guaranteed to be unaffected + by the topology change. It therefore follows that the packet + arriving at Y will reach its destination without looping. + + Since it can also be assumed that the new topology is loop-free, by + definition a packet cannot loop while being forwarded exclusively by + routers with an updated FIB entry. + + In other words, when the oFIB ordering is respected, if a packet + reaches an outdated router, it can never subsequently reach an + updated router, and it cannot loop because from this point on it will + only be forwarded on the consistent path that was used before the + event. If it does not reach an outdated router, it will only be + forwarded on the loop-free path that will be used after the + convergence. + + According to the proposed ordering, X will be the last router to + update its FIB. Once it has updated its FIB, the link X->Y can + actually be shut down (or the repair removed). + + If the link X-Y is bidirectional, a similar process must be run to + order the FIB update for destinations using the link in the direction + Y->X. As has already been shown, no packet ever traverses the X-Y + link in both directions, and hence the operation of the two ordering + processes is orthogonal. + +2.1.2. Link Up / Metric Decrease + + In the case of link up events or metric decreases, a router R must + update its FIB before all other routers that will use R to reach the + affected link. + + The following argument shows that this rule ensures the correct order + of FIB changes when the link X->Y is brought into service or its + metric is decreased. + + Firstly, when a packet reaches a router R that has already updated + its FIB, all the routers on the path from R to X will also have + updated their FIB, so that the packet will reach X and be forwarded + along X->Y, ultimately reaching its destination. + + + +Shand, et al. Informational [Page 7] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + Secondly, a packet cannot loop between routers that have not yet + updated their FIB. This proves that no packet can loop. + +2.2. Multi-Link Events + + The following sections describe the required ordering for single + events that may manifest as multiple link events. For example, the + failure of a router may be notified to the rest of the network as the + individual failure of all its attached links. The means of + identifying the event type from the collection of received link + events is described in Section 3.1. + +2.2.1. Router Down Events + + In the case of the non-urgent shutdown of a router, a router R must + not update its FIB until all other routers that send traffic via R + and the affected router have first updated their FIBs. + + Using a proof similar to that for link failure, it can be shown that + no loops will occur if this ordering is respected [refs.PFOB07]. + +2.2.2. Router Up Events + + In the case of a router being brought into service, a router R must + update its FIB BEFORE all other routers that WILL use R to reach the + affected router. + + A proof similar to that for link up shows that no loops will occur if + this ordering is respected [refs.PFOB07]. + +2.2.3. Line-Card Failure/Restoration Events + + The failure of a line card involves the failure of a set of links, + all of which have a single node in common, i.e., the parent router. + The ordering to be applied is the same as if it were the failure of + the parent router. + + In a similar way, the restoration of an entire line card to service + as a single event can be treated as if the parent router were + returning to service. + + + + + + + + + + + +Shand, et al. Informational [Page 8] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +3. Applying Ordered FIB Updates + +3.1. Deducing the Topology Change + + As has been described, a single event such as the failure or + restoration of a single link, single router, or line card may be + notified to the rest of the network as a set of individual link + change events. It is necessary to deduce from this collection of + link-state notifications the type of event that has occurred in the + network and hence the required ordering. + + When a link change event is received that impacts the receiving + router's FIB, the routers at the near and far end of the link are + noted. + + If all events received within some hold-down period (the time that a + router waits to acquire a set of Link State Packets (LSPs) that + should be processed together) have a single router in common, then it + is assumed that the change reflects an event (line-card or router + change) concerning that router. + + In the case of a link change event, the router at the far end of the + link is deemed to be the common router. + + All ordering computations are based on treating the common router as + the root for both link and node events. + +3.2. Deciding If Ordered FIB Updates Apply + + There are some events (for example, a subsequent failure with + conflicting repair requirements occurring before the ordered FIB + process has completed) that cannot be correctly processed by this + mechanism. In these cases, it is necessary to ensure that + convergence falls back to the conventional mode of operation (see + Section 6). + + In all cases, it is necessary to wait some hold-down period after + receiving the first notification to ensure that all routers have + received the complete set of link-state notifications associated with + the single event. + + At any time, if a link change notification is received that would + have no effect on the receiving router's FIB, then it may be ignored. + + If no other event is received during the hold-down time, the event is + treated as a link event. Note that the IGP reverse connectivity + check means that only the first failure event or second up event has + an effect on the FIB. + + + +Shand, et al. Informational [Page 9] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + If an event that is received within the hold-down period does NOT + reference the common router (R), then, in this version of the + specification, normal convergence is invoked immediately (see + Section 6). + + Network reconvergence using the ordered FIB approach takes longer + than the normal reconvergence process. Where the failure is + protected by an FRR mechanism, this additional delay in convergence + causes no packet loss. When the sudden failure of a link or a set of + links that are not protected using an FRR mechanism occurs, the + failure must be processed using the conventional (faster) mode of + operation to minimize packet loss during reconvergence. + + In summary, an ordered FIB process is applicable if the set of link + state notifications received between the first event and the hold- + down period reference a common router R, and one of the following + assertions is verified: + + o The set of notifications refers to link down events concerning + protected links and metric increase events. + + o The set of notifications refers to link up events and metric + decrease events. + +4. Computation of the Ordering + + This section describes how the required ordering is computed. + + This computation required the introduction of the concept of a + reverse Shortest Path Tree (rSPT). The rSPT uses the cost towards + the root (rather than from it) and yields the best paths towards the + root from other nodes in the network [IPFRR-TUNNELS]. + +4.1. Link Down, Router Down, or Metric Increase + + To respect the proposed ordering, routers compute a rank that will be + used to determine the time at which they are permitted to perform + their FIB update. In the case of a failure event rooted at router Y + or an increase of the metric of link X->Y, router R computes the rSPT + in the topology before the failure (rSPT_old) rooted at Y. This rSPT + gives the shortest paths to reach Y before the failure. The branch + of the rSPT that is below R corresponds to the set of shortest paths + to R that are used by the routers that reach Y via R. + + The rank of router R is defined as the depth (in number of hops) of + this branch. In the case of Equal Cost Multipath (ECMP), the maximum + depth of the ECMP path set is used. + + + + +Shand, et al. Informational [Page 10] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + Router R is required to update its FIB at time + + T0 + H + (rank * MAX_FIB) + + where T0 is the arrival time of the Link State Packet containing the + topology change, H is the hold-down time, and MAX_FIB is a network- + wide constant that reflects the maximum time required to update a FIB + irrespective of the change required. The value of MAX_FIB is network + specific, and its determination is out of the scope of this document. + This value must be agreed to by all the routers in the network. This + agreement can be performed by using a capability TLV as defined in + Appendix B. + + All the routers that use R to reach Y will compute a lower rank than + R, and hence the correct order will be respected. It should be noted + that only the routers that used Y before the event need to compute + their rank. + +4.2. Link Up, Router Up, or Metric Decrease + + In the case of a link or router up event rooted at Y or a link metric + decrease affecting link Y->W, a router R must have a rank that is + higher than the rank of the routers that it will use to reach Y, + according to the rule described in Section 2. Thus, the rank of R is + the number of hops between R and Y in its renewed Shortest Path Tree. + When R has multiple equal-cost paths to Y, the rank is the length in + hops of the longest ECMP path to Y. + + Router R is required to update its FIB at time + + T0 + H + (rank * MAX_FIB) + + It should be noted that only the routers that use Y after the event + have to compute a rank, i.e., only the routers that have Y in their + SPT after the link-state change. + +5. Acceleration of Ordered Convergence + + The mechanism described above is conservative and hence may be + relatively slow. The purpose of this section is to describe a method + of accelerating the controlled convergence in such a way that ordered + loop-free convergence is still guaranteed. + + In many cases, a router will complete its required FIB changes in a + time much shorter than MAX_FIB, and in many other cases, a router + will not have to perform any FIB change at all. + + + + + +Shand, et al. Informational [Page 11] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + This section describes the use of completion messages to speed up the + convergence by providing a means for a router to inform those routers + waiting for it that it has completed any required FIB changes. When + a router has been advised of completion by all the routers for which + it is waiting, it can safely update its own FIB without further + delay. In most cases, this can result in a sub-second reconvergence + time, which is comparable with a normal convergence time. + + Routers maintain a waiting list of the neighbors from which a + completion message must be received. Upon reception of a completion + message from a neighbor, a router removes this neighbor from its + waiting list. Once its waiting list becomes empty, the router is + allowed to update its FIB immediately even if its ranking timer has + not yet expired. Once this is done, the router sends a completion + message to the neighbors that are waiting for it to complete. Those + routers are listed in a list called the Notification List. + Completion messages contain an identification of the event to which + they refer. + + Note that, since this is only an optimization, any loss of completion + messages will result in the routers waiting their defined ranking + time, and hence the loop-free properties will be preserved. + +5.1. Construction of the Waiting List and Notification List + +5.1.1. Down Events + + Consider a link or node down event rooted at router Y or the cost + increase of the link X->Y. A router R will compute rSPT_old(Y) to + determine its rank. When doing this, R also computes the set of + neighbors that R uses to reach the failing node or link, and the set + of neighbors that are using R to reach the failing node or link. The + notification list of R is equal to the former set, and the waiting + list of R is equal to the latter. + + Note that R could include all its neighbors in the notification list + except those in the waiting list; this would have no impact on the + correctness of the protocol but would be unnecessarily inefficient. + +5.1.2. Up Events + + Consider a link or node up event rooted at router Y or the cost + decrease of the link Y->X. A router R will compute its new SPT + (SPT_new(R)). The waiting list is the set of next-hop routers that R + uses to reach Y in SPT_new(R). + + + + + + +Shand, et al. Informational [Page 12] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + In a simple implementation, the notification list of R is all the + neighbors of R excluding those in the waiting list. This may be + further optimized by computing rSPT_new(Y) to determine those routers + that are waiting for R to complete. + +5.2. Format of Completion Messages + + The format of completion messages and means of their delivery is + routing protocol dependent and is outside the scope of this document. + + The following information is required: + + o Identity of the sender. + + o List of routing notifications being considered in the associated + FIB change. Each notification is defined as: + + Node ID of the near end of the link + + Node ID of the far end of the link + + Inclusion or removal of link + + Old metric + + New metric + +6. Fallback to Conventional Convergence + + In circumstances where a router detects that it is dealing with + incomplete or inconsistent link-state information, or when a further + topology event is received before completion of the current ordered + FIB update process, it may be expedient to abandon the controlled + convergence process. A number of possible fallback mechanisms are + described in Appendix A. This mechanism is referred to as + "Abandoning All Hope" (AAH). The state machine defined in the body + of this document does not make any assumption about which fallback + mechanism will be used. + +7. oFIB State Machine + + An implementation must be capable of interworking with the model of + an oFIB state machine described in this section. + + An oFIB-capable router maintains an oFIB state value, which is one + of: OFIB_STABLE, OFIB_HOLDING_DOWN, OFIB_HOLDING_UP, OFIB_ABANDONED, + or OFIB_ONGOING. + + + + +Shand, et al. Informational [Page 13] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + An oFIB-capable router maintains a timer, Hold_down_timer. An oFIB- + capable router is configured with a value referred to as + HOLD_DOWN_DURATION. This configuration can be performed manually or + using Appendix B. + + An oFIB-capable router maintains a timer, rank_timer. + +7.1. OFIB_STABLE + + OFIB_STABLE is the state of a router that is not currently involved + in any convergence process. This router is ready to process an event + by applying oFIB. + + EVENT: Reception of a Link State Packet that describes an event of + the type link X--Y down or metric increase and is to be processed + using oFIB. + + ACTION: + + Set state to OFIB_HOLDING_DOWN. + + Start Hold_down_timer. + + ofib_current_common_set = {X,Y}. + + Compute rank with respect to the event, as defined in Section 4. + + Store the waiting list and notification list for X--Y obtained + from the rank computation. + + EVENT: Reception of a Link State Packet that describes an event of + the type link X--Y up or metric decrease and is to be processed using + oFIB. + + ACTION: + + Set state to OFIB_HOLDING_UP. + + Start Hold_down_timer. + + ofib_current_common_set = {X,Y}. + + Compute rank with respect to the event, as defined in Section 4. + + Store the waiting list and notification list for X--Y obtained + from the rank computation. + + + + + +Shand, et al. Informational [Page 14] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +7.2. OFIB_HOLDING_DOWN + + OFIB_HOLDING_DOWN is the state of a router that is collecting a set + of link down or metric increase Link State Packets to be processed + together using controlled convergence. + + EVENT: Reception of a Link State Packet that describes an event of + the type link up or metric decrease and can be processed using oFIB. + + ACTION: + + Set state to OFIB_ABANDONED. + + Reset Hold_down_timer. + + Trigger AAH mechanism. + + EVENT: Reception of a Link State Packet that describes an event of + the type link A--B down or metric increase and can be processed using + oFIB. + + ACTION: + + ofib_current_common_set = + intersection(ofib_current_common_set,{A,B}). + + If ofib_current_common_set is empty, then there is no longer a + node in common in all the pending link-state changes. + + Set state to OFIB_ABANDONED. + + Reset Hold_down_timer. + + Trigger AAH mechanism. + + If ofib_current_common set is not empty, update the waiting list + and notification list as defined in Section 4. Note that in the + case of a single link event, the Link State Packet received when + the router is in this state describes the state change of the + other direction of the link; hence, no changes will be made to the + waiting and notification lists. + + + + + + + + + + +Shand, et al. Informational [Page 15] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + EVENT: Hold_down_timer expires. + + ACTION: + + Set state to OFIB_ONGOING. + + Start rank_timer with computed rank. + + EVENT: Reception of a completion message. + + ACTION: Remove the sender from the waiting list associated with the + event identified in the completion message. + +7.3. OFIB_HOLDING_UP + + OFIB_HOLDING_UP is the state of a router that is collecting a set of + link up or metric decrease Link State Packets to be processed + together using controlled convergence. + + EVENT: Reception of a Link State Packet that describes an event of + the type link down or metric increase and is to be processed using + oFIB. + + ACTION: + + Set state to OFIB_ABANDONED. + + Reset Hold_down_timer. + + Trigger AAH mechanism. + + EVENT: Reception of a Link State Packet that describes an event of + the type link A--B up or metric decrease and is to be processed using + oFIB. + + ACTION: + + ofib_current_common_set = + intersection(ofib_current_common_set,{A,B}). + + If ofib_current_common_set is empty, then there is no longer a + common node in the set of pending link-state changes. + + Set state to OFIB_ABANDONED. + + Reset Hold_down_timer. + + Trigger AAH mechanism. + + + +Shand, et al. Informational [Page 16] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + If ofib_current_common set is not empty, update the waiting list + and notification list as defined in Section 4. Note that in the + case of a single link event, the Link State Packet received when + the router is in this state describes the state change of the + other direction of the link; hence, no changes will be made to the + waiting and notification lists. + + EVENT: Reception of a completion message. + + ACTION: Remove the sender from the waiting list associated with the + event identified in the completion message. + + EVENT: Hold_down_timer expires. + + ACTION: + + Set state to OFIB_ONGOING. + + Start rank_timer with computed rank. + +7.4. OFIB_ONGOING + + OFIB_ONGOING is the state of a router that is applying the ordering + mechanism with respect to the set of Link State Packets collected + when in OFIB_HOLDING_DOWN or OFIB_HOLDING_UP state. + + EVENT: rank_timer expires or waiting list becomes empty. + + ACTION: + + Perform FIB updates according to the change. + + Send completion message to each member of the notification list. + + Set state to OFIB_STABLE. + + EVENT: Reception of a completion message. + + ACTION: Remove the sender from the waiting list. + + EVENT: Reception of a Link State Packet describing a link-state + change event. + + + + + + + + + +Shand, et al. Informational [Page 17] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + ACTION: + + Set state to OFIB_ABANDONED. + + Trigger AAH. + + Start Hold_down_timer. + +7.5. OFIB_ABANDONED + + OFIB_ABANDONED is the state of a router that has fallen back to fast + convergence due to the reception of Link State Packets that cannot be + dealt with together using oFIB. + + EVENT: Reception of a Link State Packet describing a link-state + change event. + + ACTION: Trigger AAH, reset AAH_Hold_down_timer. + + EVENT: AAH_Hold_down_timer expires. + + ACTION: Set state to OFIB_STABLE. + +8. Management Considerations + + A system for recording the dynamics of the convergence process needs + to be deployed in order to make a post hoc diagnosis of the + reconvergence. The sensitivity of applications to any packet + reordering introduced by the delayed convergence process will need to + be studied. However, these needs apply to any loop-free convergence + method and are not specific to the ordered FIB method described in + this document. + +9. Security Considerations + + This document requires only minor modifications to existing routing + protocols and therefore does not add significant additional security + risks. However, a full security analysis would need to be provided + within the protocol-specific specifications proposed for deployment. + + Security considerations related to timer values set by routers are + noted in Appendix B.4. + +10. Acknowledgments + + We would like to thank Jean-Philippe Vasseur and Les Ginsberg for + their useful suggestions and comments. + + + + +Shand, et al. Informational [Page 18] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +11. Informative References + + [IPFRR-TUNNELS] + Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP + Fast Reroute using tunnels", Work in Progress, November + 2007. + + [ISO10589] International Organization for Standardization, + "Intermediate system to Intermediate system intra-domain + routing 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, November 2002. + + [LF-TIMERS] + Atlas, A., Bryant, S., and M. Shand, "Synchronisation of + Loop Free Timer Values", Work in Progress, February 2008. + + [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. + + [RFC4090] Pan, P., Swallow, G., and A. Atlas, "Fast Reroute + Extensions to RSVP-TE for LSP Tunnels", RFC 4090, May + 2005. + + [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC + 5714, January 2010. + + [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free + Convergence", RFC 5715, January 2010. + + [refs.PFOB07] + Francois, P. and O. Bonaventure, "Avoiding transient loops + during the convergence of link-state routing protocols", + IEEE/ACM Transactions on Networking, Vol. 15, No. 6, pp. + 1280-1292, December 2007, + <http://dx.doi.org/10.1109/TNET.2007.902686>. + + + + + + + + + + + + + + + +Shand, et al. Informational [Page 19] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +Appendix A. Candidate Methods of Safely Abandoning Loop-Free + Convergence (AAH) + + IP Fast Reroute [RFC5714] and loop-free convergence techniques + [RFC5715] can deal with single topology change events, multiple + correlated change events, and in some cases even certain uncorrelated + events. However, in all cases, there are events that cannot be dealt + with, and the mechanism needs to quickly revert to normal + convergence. This is known as "Abandoning All Hope" (AAH). + + This appendix describes the outcome of a design study into the AAH + problem and is included here to trigger discussion on the trade-offs + between complexity and robustness in the AAH solution space. + +A.1. Possible Solutions + + Two approaches to this problem have been proposed: + + 1. Hold-down timer only. + + 2. Synchronization of AAH state using AAH messages. + + They are described below. + +A.2. Hold-Down Timer Only + + The "hold-down timer only" AAH method uses a hold-down to acquire a + set of LSPs that should be processed together. On expiry of the + local hold-down timer, the router begins processing the batch of LSPs + according to the loop-free prevention algorithm. + + There are a number of problems with this simple approach. In some + cases, the timer value will be too short to ensure that all the + related events have arrived at all routers (perhaps because there was + some unexpected propagation delay, or one or more of the events are + slow in being detected). In other cases, a completely unrelated + event may occur after the timer has expired but before the processing + is complete. In addition, since the timer is started at each router + on reception of the first LSP announcing a topology change, the + actual starting time is dependent upon the propagation time of the + first LSP. So, for a subsequent event occurring around the time of + the timer expiry, because of variations in propagation delay, it may + reach some routers before the timer expires and others after it has + expired. In the former case, this LSP will be included in the set of + changes to be considered; while in the latter, it will be excluded + leading to serious routing inconsistency. In such cases, continuing + to operate the loop-free convergence protocol may exacerbate the + situation. + + + +Shand, et al. Informational [Page 20] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + The simple approach to this would be to revert to normal convergence + (AAH) whenever an LSP is received after the timer has expired. + However, this also has problems for the reasons above and therefore + AAH must be a synchronous operation, i.e., it is necessary to arrange + that an AAH invoked anywhere in the network causes ALL routers to + invoke AAH. + + It is also necessary to consider the means of exiting the AAH state. + Again, the simplest method is to use a timer. However, while in AAH + state, any topology changes that are previously received or + subsequently received should be processed immediately using the + traditional convergence algorithms, i.e., without invoking controlled + convergence. If the exit from the AAH state is not correctly + synchronized, a new event may be processed by some routers + immediately (as AAH), while those that have already left AAH state + will treat it as the first of a new batch of changes and attempt + controlled convergence. Thus, both entry and exit from the AAH state + need to be synchronized. A method of achieving this is described in + Appendix A.3. + +A.3. AAH Messages + + Like the simple timer AAH method, the "AAH messages" method uses a + hold-down to acquire a set of LSPs that should be processed together. + On expiry of the local hold-down timer, the router begins processing + the batch of LSPs according to the loop-free prevention algorithm. + This is the same behavior as the hold-down timer only method. + However, if any router, having started the loop-free convergence + process receives an LSP that would trigger a topology change, it + locally abandons the controlled convergence process and sends an AAH + message to all its neighbors. This eventually triggers all routers + to abandon the controlled convergence. The routers remain in AAH + state (i.e., processing topology changes using normal "fast" + convergence), until a period of quiescence has elapsed. The exit + from AAH state is synchronized by using a two-step process. To + achieve the required synchronization, two additional messages are + required, AAH and AAH ACK. The AAH message is reliably exchanged + between neighbors using the AAH ACK message. These could be + implemented as a new message within the routing protocol or carried + in existing routing hello messages. Two types of state machines are + needed -- a per-router AAH state machine and a per-neighbor AAH state + machine (PNSM). These are described below. + + + + + + + + + +Shand, et al. Informational [Page 21] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +A.3.1. Per-Router State Machine + + +-------------+----------+---------+--------+------------+----------+ + | EVENT | Q | Hold | CC | AAH | AAH-hold | + +=============+==========+=========+========+============+==========+ + | RX LSP | Start | - | TX-AAH | Restart | TX-AAH | + | triggering |hold-down | | Start | AAH timer. | Start | + | change | timer. | | AAH | [AAH] | AAH | + | | [Hold] | | timer. | | timer. | + | | | | [AAH] | | [AAH] | + +-------------+----------+---------+--------+------------+----------+ + | RX AAH | TX-AAH | TX-AAH | TX-AAH | [AAH] | TX-AAH | + |(Neighbor's |Start AAH | Start | Start | | Start | + | PNSM | timer. | AAH | AAH | | AAH | + | processes | [AAH] | timer. | timer. | | timer. | + | RX AAH.) | | [AAH] | [AAH] | | [AAH] | + +-------------+----------+---------+--------+------------+----------+ + | Timer | - | Trigger | - | Start | [Q] | + | expiry | | CC. | | AAH-hold | | + | | | [CC] | | timer. | | + | | | | | [AAH-hold] | | + +-------------+----------+---------+--------+------------+----------+ + | Controlled | - | - | [Q] | - | - | + | convergence | | | | | | + | completed | | | | | | + +-------------+----------+---------+--------+------------+----------+ + + RX = Reception + TX = Transmission + TX-AAH = Send "go to TX-AAH" to all other PNSMs. + + Per-Router State Table + + Operation of the per-router state machine is as follows: + + Operation of this state machine under normal topology change involves + only states: Quiescent (Q), Hold-down (Hold) and Controlled + Convergence (CC). The remaining states are associated with an AAH + event. + + The resting state is Quiescent. When the router in the Quiescent + state receives an LSP indicating a topology change, which would + normally trigger an SPF, it starts the hold-down timer and changes + state to Hold-down. It normally remains in this state, collecting + additional LSPs until the hold-down timer expires. Note that all + routers must use a common value for the hold-down timer. When the + hold-down timer expires, the router then enters Controlled + + + + +Shand, et al. Informational [Page 22] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + Convergence (CC) state and executes the CC mechanism to reconverge + the topology. When the CC process has completed on the router, the + router re-enters the Quiescent state. + + If this router receives a topology-changing LSP whilst it is in the + CC state, it enters AAH state and sends a "go to TX-AAH" command to + all per-neighbor state machines; this causes each per-neighbor state + machine to signal this state change to its neighbor. Alternatively, + if this router receives an AAH message from any of its neighbors + whilst in any state except AAH, it starts the AAH timer and enters + the AAH state. The per-neighbor state machine corresponding to the + neighbor from which the AAH was received executes the RX AAH action + (which causes it to send an AAH ACK), while the remainder of + neighbors are sent the "go to TX-AAH" command. The result is that + the AAH is acknowledged to the neighbor from which it was received + and propagated to all other neighbors. On entering AAH state, all CC + timers are expired, and normal convergence takes place. + + Whilst in the AAH state, LSPs are processed in the traditional + manner. Each time an LSP is received, the AAH timer is restarted. + In an unstable network, ALL routers will remain in this state for + some time, and the network will behave in the traditional + uncontrolled convergence manner. + + When the AAH timer expires, the router enters AAH-hold state and + starts the AAH-hold timer. The purpose of the AAH-hold state is to + synchronize the transition of the network from AAH to Quiescent. The + additional state ensures that the network cannot contain a mixture of + routers in both AAH and Quiescent states. If, whilst in AAH-hold + state the router receives a topology changing LSP, it re-enters AAH + state and commands all per-neighbor state machines to "go to TX-AAH". + If, whilst in AAH-hold state, the router receives an AAH message from + one of its neighbors, it re-enters the AAH state and commands all + other per-neighbor state machines to "go to TX-AAH". Note that the + per-neighbor state machine receiving the AAH message will + autonomously acknowledge receipt of the AAH message. Commanding the + per-neighbor state machine to "go to TX-AAH" is necessary, because + routers may be in a mixture of Quiescent, Hold-down, and AAH-hold + states, and it is necessary to rendezvous the entire network back to + AAH state. + + When the AAH-hold timer expires, the router changes to Quiescent and + is ready for loop-free convergence. + + + + + + + + +Shand, et al. Informational [Page 23] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + +A.3.2. Per-Neighbor State Machine + + +----------------------------+--------------+-----------------------+ + | EVENT | IDLE | TX-AAH | + +============================+==============+=======================+ + | RX AAH | Send ACK. | Send ACK. | + | | [IDLE] | Cancel timer. | + | | | [IDLE] | + +----------------------------+--------------+-----------------------+ + | RX ACK | ignore | Cancel timer. | + | | | [IDLE] | + +----------------------------+--------------+-----------------------+ + | RX "go to TX-AAH" from | Send AAH | ignore | + | Router State Machine | [TX-AAH] | | + +----------------------------+--------------+-----------------------+ + | Timer expires | impossible | Send AAH | + | | | Restart timer. | + | | | [TX-AAH] | + +----------------------------+--------------+-----------------------+ + + Per-Neighbor State Table + + There is one instance of the per-neighbor state machine (PNSM) for + each neighbor within the convergence control domain. + + The normal state is IDLE. + + On command ("go to TX-AAH") from the router state machine, the state + machine enters TX-AAH state, transmits an AAH message to its + neighbor, and starts a timer. + + On receipt of an AAH ACK in state TX-AAH, the state machine cancels + the timer and enters IDLE state. + + In state IDLE, any AAH ACK message received is ignored. + + On expiry of the timer in state TX-AAH, the state machine transmits + an AAH message to the neighbor and restarts the timer. (The timer + cannot expire in any other state.) + + In any state, receipt of an AAH causes the state machine to transmit + an AAH ACK and enter the IDLE state. + + Note that for correct operation the state machine must remain in + state TX-AAH until an AAH ACK or an AAH is received or until the + state machine is deleted. Deletion of the per-neighbor state machine + occurs when routing determines that the neighbor has gone away or + when the interface goes away. + + + +Shand, et al. Informational [Page 24] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + When routing detects a new neighbor, it creates a new instance of the + per-neighbor state machine in state IDLE. The consequent generation + of the router's own LSP will then cause the router state machine to + execute the LSP receipt actions that, if necessary, will result in + the new per-neighbor state machine receiving a "go to TX-AAH" command + and transitioning to TX-AAH state. + +Appendix B. Synchronization of Loop-Free Timer Values + + This appendix provides the reader with access to the design + considerations originally described in [LF-TIMERS]. + +B.1. Introduction + + Most of the loop-free convergence mechanisms [RFC5715] require one or + more convergence delay timers that must have a duration that is + consistent throughout the routing domain. This time is the worst- + case time that any router will take to calculate the new topology and + to make the necessary changes to the FIB. The timer is used by the + routers to know when it is safe to transition between the loop-free + convergence states. The time taken by a router to complete each + phase of the loop-free transition will be dependent on the size of + the network and the design and implementation of the router. + Therefore, it can be expected that the optimum delay will need to be + tuned from time to time as the network evolves. Manual configuration + of the timer is fraught for two reasons. Firstly, it is always + difficult to ensure that the correct value is installed in all of the + routers. Secondly, if any change is introduced into the network that + results in a need to change the timer (for example, due to a change + in hardware or software version), then all of the routers need to be + reconfigured to use the new timer value. Therefore, it is desirable + that a means be provided by which the convergence delay timer can be + automatically synchronized throughout the network. + +B.2. Required Properties + + The timer synchronization mechanism must have the following + properties: + + o The convergence delay time must be consistent amongst all routers + that are converging on the new topology. + + o The convergence delay time must be the highest delay required by + any router in the new topology. + + o The mechanism must increase the delay when a new router that + requires a higher delay than is currently in use is introduced to + the network. + + + +Shand, et al. Informational [Page 25] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + o When the router that had the longest delay requirements is removed + from the topology, the convergence delay timer value must, within + some reasonable time, be reduced to the longest delay required by + the remaining routers. + + o It must be possible for a router to change the convergence delay + timer value that it requires. + + o A router that is in multiple routing areas or is running multiple + routing protocols may signal a different loop-free convergence + delay for each area and for each protocol. + + How a router determines the time that it needs to execute each + convergence phase is an implementation issue and outside the scope of + this specification. However, a router that dynamically determines + its proposed timer value must do so in such a way that it does not + cause the synchronized value to continually fluctuate. + +B.3. Mechanism + + The following mechanism is proposed. + + A new information element is introduced into the routing protocol + that specifies the maximum time (in milliseconds) that the router + will take to calculate the new topology and to update its FIB as a + result of any topology change. + + When a topology change occurs, the longest convergence delay time + required by any router in the new topology is used by the loop-free + convergence mechanism. + + If a routing protocol message is issued that changes the convergence + delay timer value but does not change the topology, the new timer + value must be taken into consideration during the next loop-free + transition but must not instigate a loop-free transition. + + If a routing protocol message is issued that changes the convergence + timer value and changes the topology, a loop-free transition is + instigated, and the new timer value is taken into consideration. + + The loop-free convergence mechanism should specify the action to be + taken if a timer change (only) message and a topology change message + are independently generated during the hold-off time. A suitable + action would be to take the same action that would be taken if two + uncorrelated topology changes occurred in the network. + + + + + + +Shand, et al. Informational [Page 26] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + All routers that support loop-free convergence must advertise a loop- + free convergence delay time. The loop-free convergence mechanism + must specify the action to be taken if a router does not advertise a + convergence delay time. + +B.4. Security Considerations Related to Router Timer Values + + If an abnormally large timer value is proposed by a router, then + there is a danger that the loop-free convergence process will take an + excessive amount of time. If during that time the routing protocol + signals the need for another transition, the loop-free transition + will be abandoned and the default best-case (traditional) convergence + mechanism used. + + It is still undesirable that the routers select a convergence delay + time that has an excessive value. The maximum value that can be + specified in the LSP or Link State Advertisement (LSA) is limited + (through the use of a 16-bit field) to about 65 seconds. When + sufficient implementation experience is gained, an architectural + constant will be specified as the upper limit of the convergence + delay timer. + +Authors' Addresses + + Mike Shand + Individual Contributor + + EMail: imc.shand@googlemail.com + + + Stewart Bryant + Cisco Systems + 10 New Square, Bedfont Lakes + Feltham, Middlesex TW18 8HA + United Kingdom + + EMail: stbryant@cisco.com + + + Stefano Previdi + Cisco Systems + Via Del Serafico 200 + 00142 Roma + Italy + + EMail: sprevidi@cisco.com + + + + + +Shand, et al. Informational [Page 27] + +RFC 6976 Loop-Free Convergence Using oFIB July 2013 + + + Clarence Filsfils + Cisco Systems + Brussels + Belgium + + EMail: cfilsfil@cisco.com + + + Pierre Francois + Institute IMDEA Networks + Avda. del Mar Mediterraneo, 22 + Leganese 28918 + Spain + + EMail: pierre.francois@imdea.org + + + Olivier Bonaventure + Universite catholique de Louvain + Place Ste Barbe, 2 + Louvain-la-Neuve 1348 + Belgium + + EMail: Olivier.Bonaventure@uclouvain.be + URI: http://inl.info.ucl.ac.be/ + + + + + + + + + + + + + + + + + + + + + + + + + + +Shand, et al. Informational [Page 28] + |