RFC 6976

Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach

📅 published July 2013, from ietf

RFC 6976 Rewrite Part 1 💖

okay bestie, let's get into it 🎀 this is RFC 6976, titled Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach 🦋 It's an Informational doc from the IETF (not a Standards Track thing), published July 2013. The ISSN is 2070-1721.

The authors are M. Shand, who is listed as an Individual Contributor, S. Bryant, S. Previdi, C. Filsfils (all at Cisco Systems), P. Francois (Institute IMDEA Networks), and O. Bonaventure (Universite catholique de Louvain) 👑 Its header doesn't have any "Obsoletes" or "Updates" line, so it isn't listed as replacing or amending anything.

Abstract ✨

ok so this doc is basically an illustrative framework 🌸 It's for use with link-state routing protocols, and its whole job is to stop the transient loops that would otherwise pop up during topology changes. The trick? It correctly sequences the forwarding information base (FIB) updates on the routers. Iconic, honestly 💅

It can be used for non-urgent (management action) link or node shutdowns and restarts, or for link metric changes 🔥 It can also work alongside a fast reroute mechanism that turns a sudden link or node failure into a non-urgent topology change. That only works where a complete repair path is provided for all affected destinations, so keep that in mind 💜

After a non-urgent topology change, each router computes a rank, which defines the time at which it can safely update its FIB 🧚 There's also a method for speeding up this loop-free convergence process using completion messages ✨

The technology here got extensive simulation using pathological convergence behavior and real network topologies and costs 🙈 BUT, and this is a big but, the mechanisms are purely illustrative of the general approach and do not constitute a protocol specification 😭 It's a snapshot of the Routing Area Working Group's work at the time of publication and it's published as a document of record. Further work is needed before implementation or deployment 🫶

Status of This Memo ✨

This document is not an Internet Standards Track specification 🌈 It's published for informational purposes only.

It's a product of the Internet Engineering Task Force (IETF), and it represents the consensus of the IETF community 💖 It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved doc is a candidate for any level of Internet Standard, so see Section 2 of RFC 5741 for the details 🎀

If you want the current status, any errata, or to give feedback, check http://www.rfc-editor.org/info/rfc6976 🦋

Copyright Notice ✨

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication 💜 Please read these carefully, because they describe your rights and restrictions. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Simplified BSD License 💅

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

1. Introduction ✨

1.1. The Purpose of This Document 🦋

okay so this doc describes that same illustrative framework 🌸 It's for link-state routing protocols, and it stops the transient loops that would otherwise happen during topology changes by correctly sequencing the forwarding information base (FIB) updates on the routers. Same main-character energy as the abstract, just in the body 💅

At publication time there's no demand to deploy this tech 🙈 But the subtleties in designing loop-free convergence extensions for routing protocols are real, so the Routing Area Working Group thought it was worth publishing to put the design thinking of the ordered FIB (oFIB) approach on record 🎀

The mechanisms are purely illustrative of the general approach and do not constitute a protocol specification 💖 This doc is a snapshot of the working group's work at publication time, published as a document of record. Extra work is still needed to specify the routing protocol extensions required to support this IP fast reroute (FRR) method before anyone can implement or deploy it 😭🫶

bestie, the vibe is "cool idea, not ready to ship yet" 🧚

Part 2 is coming next, so stay tuned 💜

1.2. Overview ✨

Okay so with link-state protocols like IS-IS [ISO10589] and OSPF [RFC2328], every time the network topology changes, some routers need to update their forwarding information bases (FIBs) to match the new layout 🗺️. Each change kicks off a convergence phase 🌀. During that phase, routers may transiently have inconsistent FIBs, which can cause packet loops and losses, even if the destinations are still reachable after the change 😭. Packet losses and transient loops can also happen when a link goes down because of a maintenance operation, even if that operation is predictable and not urgent 🛠️. When the link-state change is a metric update, or a new link comes up, there's no direct loss of connectivity, but transient packet loops and loss can still happen 💀.

In this document, we split network events into two groups: urgent and non-urgent 🎀. Urgent events come from unpredictable outages, like node or link failures. They're usually handled by routing protocol convergence or by protection mechanisms that rely on fault detection and reporting (such as Operations, Administration, and Maintenance) 🚨. Non-urgent events come from predictable things, like a management system deliberately shutting down network resources, or someone tweaking network parameters such as routing metrics 📅. Typically, you can plan around non-urgent events, while urgent events have to be handled by dynamic systems 🤖. All network events, both urgent and non-urgent, may lead to transient packet loops and loss 🌈.

Let's look at an example. In Figure 1, if an operator shuts down the link between X and Y, packets destined to X can loop between R and Y when Y has updated its FIB but R hasn't yet updated its FIB 🔁. Packets destined to Y can loop between X and S if X updates its FIB before S does 🙈. 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 notice the failure, so they update their FIBs first 🥺.

                   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 next to it 👀.

[RFC5715] gives an introduction to a number of loop-free convergence methods, and if you're new to this tech, it's recommended to read it before studying this document in detail 📖. Note that, like 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 keep things consistent across the whole network 🧚. By correctly setting the FIB change order, no looping or packet loss can occur 🫶. This mechanism may be applied to 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 when one or more network elements are protected by a fast reroute mechanism (FRR) [RFC5714] [RFC4090] ⚡. The mechanisms used in the failure case are exactly the same as those used for managed changes, so 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 gives 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, we'll describe the correct ordering for single link changes first 🧩. The document then builds on that to show 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 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 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 it 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 that 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, so 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 the packet will reach X and be forwarded along X->Y, ultimately reaching its destination 🌟.

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 show up 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 the one 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 the one 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 🔁.

3. Applying Ordered FIB Updates 🧁

3.1. Deducing the Topology Change 🕵️‍♀️

As we've covered, 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's necessary to deduce from this collection of link-state notifications what type of event 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 ✨

okay so, there are some events that this mechanism literally can't handle 😭 like a second failure with conflicting repair requirements popping up before the ordered FIB process is done. for those, convergence has to fall back to the conventional mode of operation (see Section 6). no cap, it's a safety net 🧈

every time an event shows up, the router has to wait a hold-down period after getting the first notification. that's so it can collect the full set of link-state notifications for the single event. bestie, patience is a virtue here 🫶

if a link change notification comes in that wouldn't change anything in the receiving router's FIB, it's allowed to be ignored. lowkey iconic, less work for everyone 💅

if nothing else comes in during the hold-down time, the event gets treated as a link event. also, the IGP reverse connectivity check means only the first failure event or the second up event actually affects the FIB. so the rest is kind of background noise 👀

if an event received during the hold-down period does NOT reference the common router (R), then in this version of the specification, normal convergence kicks in right away (see Section 6). no ordered stuff for that one 🙈

now the tea 🍵: ordered FIB convergence takes longer than the normal process. if the failure is protected by an FRR mechanism, that extra delay causes no packet loss, so it's totally fine ✨. but if a link (or a set of links) that isn't FRR-protected fails suddenly, it has to go through the conventional, faster mode to keep packet loss low during reconvergence. it's giving speed when it matters 🔥

so, in summary, an ordered FIB process applies if the set of link state notifications received between the first event and the end of the hold-down period references a common router R, and one of these is true:

The set of notifications refers to link down events concerning protected links and metric increase events.
The set of notifications refers to link up events and metric decrease events.

4. Computation of the Ordering 🧮

this section is about how the required ordering actually gets computed. spoiler: it's a whole vibe 🌈

this computation needed a new concept, the reverse Shortest Path Tree (rSPT). the rSPT uses the cost towards the root (instead of from it), and it gives the best paths towards the root from other nodes in the network [IPFRR-TUNNELS]. so it's like looking at the network from the other end of the telescope 🔭

4.1. Link Down, Router Down, or Metric Increase 💔

so to respect the proposed ordering, routers compute a rank. the rank decides when they're allowed to do their FIB update ⏰. for a failure event rooted at router Y, or a metric increase on 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 below R is the set of shortest paths to R that are used by the routers that reach Y via R. main character energy 👑

the rank of router R is the depth (in number of hops) of this branch. with Equal Cost Multipath (ECMP), the maximum depth of the ECMP path set is used 🧠

router R is required to update its FIB at this 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. it reflects the maximum time needed to update a FIB, no matter what the change is. the value of MAX_FIB is network specific, and figuring out what it should be is out of the scope of this document 🤷‍♀️. it has to be agreed on by all the routers in the network, and that agreement can be done with a capability TLV as defined in Appendix B 🤝

all the routers that use R to reach Y will compute a lower rank than R, so the correct order gets respected 🪜. also, only the routers that used Y before the event need to compute their rank. the others don't have to bother 💅

4.2. Link Up, Router Up, or Metric Decrease 📈

for a link or router up event rooted at Y, or a link metric decrease affecting link Y->W, router R needs a rank higher than the rank of the routers it will use to reach Y, following the rule in Section 2. so the rank of R is the number of hops between R and Y in its renewed Shortest Path Tree. if 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 this time:

T0 + H + (rank * MAX_FIB)

and remember, only the routers that use Y after the event have to compute a rank. in other words, only the routers that have Y in their SPT after the link-state change 🥹

5. Acceleration of Ordered Convergence 🏎️

the mechanism above is conservative, which means it can be relatively slow 🐢. this section is about speeding up the controlled convergence while still guaranteeing ordered, loop-free convergence. it's giving glow-up 🌸

in lots of cases, a router finishes its required FIB changes way faster than MAX_FIB. and in lots of other cases, a router doesn't have to change its FIB at all 🙌

this section uses completion messages to speed things up. a router uses them to tell the routers waiting on it that it's done with any required FIB changes. once a router has heard completion from all the routers it's waiting for, it can safely update its own FIB without any extra delay 🏃‍♀️. in most cases this gives a sub-second reconvergence time, which is comparable to normal convergence. so, iconic 🍓

routers keep a waiting list of the neighbors they need to get a completion message from. when a completion message arrives from a neighbor, the router removes that neighbor from its waiting list. once the waiting list is empty, the router can update its FIB right away, even if its ranking timer hasn't expired yet. after that, it sends a completion message to the neighbors waiting on it. those routers are listed in a list called the Notification List. completion messages include an identification of the event they refer to 🪪

note that this is only an optimization. so if completion messages get lost, the routers will just wait their defined ranking time, and the loop-free properties are still preserved. no panic, the safety net holds 🫶

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 a cost increase on the link X->Y. router R computes rSPT_old(Y) to figure out its rank. while doing this, R also works out the set of neighbors that R uses to reach the failing node or link, and the set of neighbors that use R to reach the failing node or link. the notification list of R is equal to the first set, and the waiting list of R is equal to the second 🔁

note that R could put all its neighbors in the notification list except the ones in the waiting list. that wouldn't break correctness, but it would be unnecessarily inefficient 😅

5.1.2. Up Events

consider a link or node up event rooted at router Y, or a cost decrease on the link Y->X. router R computes 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) ⏳

in a simple implementation, the notification list of R is all the neighbors of R, excluding the ones in the waiting list. this can be optimized further by computing rSPT_new(Y), which tells you which routers are waiting for R to complete 🧠

5.2. Format of Completion Messages 📨

the format of completion messages and how they get delivered depends on the routing protocol, and that's outside the scope of this document 🙅‍♀️.

the following information is required:

Identity of the sender.
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 🪂

sometimes a router notices it's dealing with incomplete or inconsistent link-state information. or a further topology event shows up before the current ordered FIB update is done. in those moments, it may be smart to abandon the controlled convergence process 🏳️. Appendix A describes a number of possible fallback mechanisms. this is referred to as "Abandoning All Hope" (AAH) 😭. the state machine defined in the body of this document doesn't make any assumptions about which fallback mechanism gets 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 🌟.

an oFIB-capable router maintains a timer, Hold_down_timer. it's also configured with a value called HOLD_DOWN_DURATION. that configuration can be done manually or using Appendix B ⏱️.

an oFIB-capable router also maintains a timer, rank_timer 🕰️.

7.1. OFIB_STABLE 🧘‍♀️

OFIB_STABLE is the state of a router that isn't 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.

7.2. OFIB_HOLDING_DOWN ✨

okay so OFIB_HOLDING_DOWN is the state a router is in while it's collecting a bunch of link down or metric increase LSPs, so they can all get processed together with 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. 🫶

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 LSPs to be processed together using controlled convergence. It's giving collection era 💅

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.
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 to the set of LSPs it collected while in OFIB_HOLDING_DOWN or OFIB_HOLDING_UP. This is the main event, bestie 👑

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.

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 because it received LSPs that can't be dealt with together using oFIB. Ngl, this is the "we tried our best" state 🙈

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 🍓

okay, so a system for recording the dynamics of the convergence process needs to be deployed so you can do 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. Still, these needs apply to any loop-free convergence method and aren't 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. Please take this one seriously, bestie 🫶

10. Acknowledgments 💜

We would like to thank Jean-Philippe Vasseur and Les Ginsberg for their useful suggestions and comments. Iconic of them 🧚

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

Appendix A. Candidate Methods of Safely Abandoning Loop-Free Convergence (AAH) 🧚‍♀️

[RFC5714] and [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). lowkey the most dramatic name in networking 😭

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:

Hold-down timer only.
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. 😬

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. Synchronous or bust, babe 💅

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. ✨

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

okay so the router state machine is basically the brain of the whole operation 🧠 under a normal topology change it only ever hangs out in three states: Quiescent (Q), Hold-down (Hold), and Controlled Convergence (CC). the other states only show up when an AAH event is involved, so we'll get to those 💅

The chill resting state is Quiescent 😌 when a router sitting in Quiescent gets an LSP that signals a topology change which would normally trigger an SPF, it starts the hold-down timer and switches to Hold-down 🫶 it usually stays there collecting extra LSPs until that timer runs out. and heads up, all routers must use a common value for the hold-down timer 🙅 when the hold-down timer expires, the router enters Controlled Convergence (CC) and runs the CC mechanism to reconverge the topology 🔄 once CC has finished on that router, it goes back to Quiescent 💜

Now if a router in CC gets a topology-changing LSP, it jumps into the AAH state and sends a "go to TX-AAH" command to every per-neighbor state machine 📣 each of those then tells its neighbor about the state change. Or, if the router gets an AAH message from any neighbor while it's in any state other than AAH, it starts the AAH timer and enters AAH 🦋 the per-neighbor state machine for the neighbor that sent the AAH does the RX AAH action (so it sends back an AAH ACK), and everyone else gets the "go to TX-AAH" command. The net result is that the AAH gets acknowledged to whoever sent it and passed along to all the other neighbors 🎀 and when a router enters AAH, all of its CC timers get expired so normal convergence can happen 🌈

While the router is in AAH, LSPs get processed the traditional way, and every time an LSP comes in, the AAH timer gets restarted 🔁 In an unstable network, ALL routers will hang out in this state for a while, and the network just behaves in the old-school uncontrolled convergence way 😤

When the AAH timer expires, the router enters AAH-hold and starts the AAH-hold timer ⏳ the whole point of AAH-hold is to get the entire network moving from AAH to Quiescent together 🤝 that extra state means the network can never be a messy mix of AAH and Quiescent routers 💀 If a router in AAH-hold gets a topology-changing LSP, it goes back into AAH and tells all of its per-neighbor state machines to "go to TX-AAH". And if it gets an AAH from one of its neighbors while in AAH-hold, it goes back into AAH and tells all the other per-neighbor state machines to "go to TX-AAH", while the one that received the AAH acknowledges it on its own 💅 That "go to TX-AAH" command is needed because routers can be sitting in any mix of Quiescent, Hold-down, and AAH-hold states, so the whole network has to be brought back together into AAH 🫂

Finally, when the AAH-hold timer expires, the router switches to Quiescent and is ready for loop-free convergence 🎉✨

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's one instance of the per-neighbor state machine (PNSM) for each neighbor inside the convergence control domain 🏡

The normal state is IDLE 😴

When the router state machine sends the "go to TX-AAH" command, the state machine enters TX-AAH, transmits an AAH message to its neighbor, and starts a timer ⏱️

Once it's in TX-AAH and receives an AAH ACK, it cancels the timer and enters IDLE ✅

In IDLE, any AAH ACK that shows up gets ignored 🙈

If the timer expires while in TX-AAH, the state machine transmits an AAH to the neighbor and restarts the timer. (The timer cannot expire in any other state.) 🔁

In any state, receiving an AAH makes the state machine transmit an AAH ACK and enter IDLE 🫶

For correct operation, the state machine must remain in TX-AAH until an AAH ACK or an AAH is received, or until the state machine is deleted 💖 Deletion of the PNSM happens when routing determines the neighbor has gone away, or when the interface goes away 🗑️

When routing detects a new neighbor, it creates a new PNSM in IDLE 🆕 the router's own LSP generated as a result will then cause the router state machine to run the LSP receipt actions. If needed, those actions will make the new PNSM receive a "go to TX-AAH" command and move into TX-AAH 🌷

Appendix B. Synchronization of Loop-Free Timer Values 🕰️

This appendix gives you access to the design considerations originally described in [LF-TIMERS]. 📚

B.1. Introduction

Most of the loop-free convergence mechanisms [RFC5715] need one or more convergence delay timers, and those timers have to be a consistent duration throughout the routing domain ⏲️ This time is the worst-case time any router will take to calculate the new topology and make the necessary changes to the FIB. The timer is what routers use to know when it's safe to move between loop-free convergence states. How long a router takes for each phase depends on the size of the network and on that router's design and implementation 🛠️ So the optimum delay will probably need retuning every so often as the network evolves. Setting the timer by hand is a pain for two reasons 😩 First, it's always hard to make sure the right value is installed on every router. Second, if a change in the network means the timer has to change (say, a new hardware or software version), then every router has to be reconfigured to the new value. So it's really desirable to have a way for the convergence delay timer to be synchronized automatically across the network ✨

B.2. Required Properties

The timer synchronization mechanism must have the following properties:

The convergence delay time must be consistent amongst all routers that are converging on the new topology. 🤝
The convergence delay time must be the highest delay required by any router in the new topology. 📈
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. 🆙
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. 📉
It must be possible for a router to change the convergence delay timer value that it requires. 🔧
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 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 🧚

okay so here's the mechanism they're proposing 💖

a brand new information element gets added to the routing protocol, and it tells everyone the maximum time (in milliseconds) that a router will take to calculate the new topology and update its FIB because of any topology change 🎀

when a topology change happens, the longest convergence delay time that any router needs in the new topology is what the loop-free convergence mechanism uses ✨ (so the slowest router sets the pace, it's giving group project energy lol 💀)

if a routing protocol message changes the convergence delay timer value but doesn't 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 🙈 (it waits its turn, no drama)

if a message changes the convergence timer value AND the topology, then a loop-free transition gets instigated and the new timer value is taken into consideration 🔥

the loop-free convergence mechanism should specify what to do 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 do the same thing you'd do if two uncorrelated topology changes happened in the network 💅

all routers that support loop-free convergence must advertise a loop-free convergence delay time 👑 and the loop-free convergence mechanism must specify the action to be taken if a router does not advertise a convergence delay time 😭

okay security time, and this one is SERIOUS bestie 😭

if a router proposes an abnormally large timer value, the loop-free convergence process could take an excessive amount of time 🙈 and if the routing protocol signals that another transition is needed during that wait, the loop-free transition gets abandoned and the default best-case (traditional) convergence mechanism takes over 🧚

it's still undesirable for routers to pick an excessive convergence delay time value 💖 the maximum value that can go in the LSP or Link State Advertisement (LSA) is limited (because it's a 16-bit field) to about 65 seconds 🌈 once there's enough implementation experience, 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

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/

📦 where this page comes from

ietf: rfc6976 2013-07
💖 girlified by claude-haiku-5-5 on 2026-10-17: a language model's rewrite of the original, under its terms

RFC 6976

RFC 6976 Rewrite Part 1 💖

Abstract ✨

Status of This Memo ✨

Copyright Notice ✨

Table of Contents 🧚

1. Introduction ✨

1.1. The Purpose of This Document 🦋

1.2. Overview ✨

2. The Required FIB Update Order 📋

2.1. Single Link Events 🔗

2.1.1. Link Down / Metric Increase 📉

2.1.2. Link Up / Metric Decrease 📈

2.2. Multi-Link Events 🕸️

2.2.1. Router Down Events 🛑

2.2.2. Router Up Events 🌅

2.2.3. Line-Card Failure/Restoration Events 🃏

3. Applying Ordered FIB Updates 🧁

3.1. Deducing the Topology Change 🕵️‍♀️

3.2. Deciding If Ordered FIB Updates Apply ✨

4. Computation of the Ordering 🧮

4.1. Link Down, Router Down, or Metric Increase 💔

4.2. Link Up, Router Up, or Metric Decrease 📈

5. Acceleration of Ordered Convergence 🏎️

5.1. Construction of the Waiting List and Notification List 🧩

5.1.1. Down Events

5.1.2. Up Events

5.2. Format of Completion Messages 📨

6. Fallback to Conventional Convergence 🪂

7. oFIB State Machine 🎰

7.1. OFIB_STABLE 🧘‍♀️

7.2. OFIB_HOLDING_DOWN ✨

7.3. OFIB_HOLDING_UP 🌸

7.4. OFIB_ONGOING 🔥

7.5. OFIB_ABANDONED 💀

8. Management Considerations 🍓

9. Security Considerations 🔥🔥

10. Acknowledgments 💜

11. Informative References 📚

Appendix A. Candidate Methods of Safely Abandoning Loop-Free Convergence (AAH) 🧚‍♀️

A.1. Possible Solutions 🎀

A.2. Hold-Down Timer Only ⏰

A.3. AAH Messages 💌

A.3.1. Per-Router State Machine ✨

A.3.2. Per-Neighbor State Machine 🌸

Appendix B. Synchronization of Loop-Free Timer Values 🕰️

B.1. Introduction

B.2. Required Properties

B.3. Mechanism 🧚

B.4. Security Considerations Related to Router Timer Values 💀

Authors' Addresses 🦋