RFC 5715

A Framework for Loop-Free Convergence 🎀

okay bestie, this is RFC 5715 💖 It's called A Framework for Loop-Free Convergence and it's by M. Shand and S. Bryant, both from Cisco Systems. The category is Informational 🌸 which means it isn't a Standards Track spec (more on that in the Status part, babe). It's ISSN 2070-1721 and dated January 2010. The title block doesn't list any RFCs that it obsoletes or updates, so no drama there. ✨

Abstract ✨

so a micro-loop is a packet forwarding loop that can pop up for a little bit, among two or more routers, in a hop-by-hop forwarding setup. 🌀

this framework gives you the rundown on what causes micro-loops and what they do to a network, so you can decide if they're something you need to deal with in your own network. 🧐 it also surveys the mechanisms that have been proposed so far to stop micro-loops from forming or to suppress them. these come into play when an IP or MPLS network has a topology change from a failure, a repair, or a management action. 🛠️ if fast enough convergence isn't available and your topology is prone to micro-loops, using one or more of these mechanisms might be a good move. 💅

Status of This Memo 📜

this document is not an Internet Standards Track specification. it's published for informational purposes. 🦋

this document is a product of the Internet Engineering Task Force (IETF). it represents the consensus of the IETF community, and it went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). not every document the IESG approves is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 if you want the details. 🤓

for info on the current status of this document, any errata, and how to give feedback, go to http://www.rfc-editor.org/info/rfc5715. 🔗

Copyright Notice ©️

Copyright (c) 2010 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, which you can find at http://trustee.ietf.org/license-info, as in effect on the date this document was published. please read these carefully, bestie, because they spell out your rights and restrictions for this document. any Code Components pulled out of this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License. ⚖️

Table of Contents 🗂️

1. Introduction ....................................................3
2. The Nature of Micro-Loops .......................................4
3. Applicability ...................................................5
4. Micro-Loop Control Strategies ...................................6
5. Loop Mitigation .................................................8
   5.1. Fast Convergence ...........................................8
   5.2. PLSN .......................................................8
6. Micro-Loop Prevention ..........................................10
   6.1. Incremental Cost Advertisement ............................10
   6.2. Nearside Tunneling ........................................12
   6.3. Farside Tunnels ...........................................13
   6.4. Distributed Tunnels .......................................14
   6.5. Packet Marking ............................................14
   6.6. MPLS New Labels ...........................................15
   6.7. Ordered FIB Update ........................................16
   6.8. Synchronised FIB Update ...................................18
7. Using PLSN in Conjunction with Other Methods ...................18
8. Loop Suppression ...............................................19
9. Compatibility Issues ...........................................20
10. Comparison of Loop-Free Convergence Methods ...................20
11. Security Considerations .......................................21
12. Acknowledgments ...............................................21
13. Informative References ........................................21

1. Introduction 🌷

okay so when the network topology changes (because a link or router fails or comes back, or because someone did a management action), the routers have to converge on one shared picture of the new topology and the paths they'll use to forward traffic to each destination. 🗺️ this is called a routing transition, and during it, packet delivery between some source/destination pairs can get disrupted. 😭 that happens because it takes time for the change to spread around the network, and it also takes time for each router to work out and then update its forwarding information base (FIB) for the affected destinations. 🐢 packets can get lost while routers keep trying to use the failed component, and they can also get lost in forwarding loops. those loops happen because the FIBs are inconsistent: routers don't all finish the transition at the same time. 🌀 this problem can show up in both IP networks and MPLS networks that use the label distribution protocol (LDP) [RFC5036] as their label switched path (LSP) signaling protocol. 🧚

the service failures caused by routing transitions are mostly hidden by higher-level protocols that retransmit the lost data, so most people never notice. 🙈 but new Internet services might come along that are way more sensitive to the packet disruption that happens during a transition. to make the transition invisible to their users, those services would need a short routing transition. 💫 ideally, routing transitions would take zero time and lose no packets. 🥹

no matter how well the mechanisms involved are designed and implemented, a routing transition is always going to take some minimum interval that's greater than zero. 😤 that's why a traffic engineering (TE) fast-reroute mechanism for MPLS was developed [RFC4090]. other mechanisms that might be deployed in an MPLS network or an IP network are current work items in the IETF [RFC5714]. 🔧 the repair mechanism can still get disrupted, though, by micro-loops that form between the moment the failure is announced and the moment all FIBs have been updated to reflect the new topology. 💀

there are two main ways to deal with the effects of micro-loops. one is to make sure the network reconverges fast enough that the effects don't matter. ⚡ the other is to design the network topology so the chance of micro-loops is minimised or even eliminated. 💅

the tendency to form micro-loops depends heavily on the topology, and there are algorithms that can identify which links in a network are subject to micro-looping. 🔍 in topologies that are critically susceptible to micro-loops, there's little point in adding new fast-reroute mechanisms unless you also deploy mechanisms that prevent the disruptive effects of micro-loops. 🙅‍♀️ otherwise, packets may never reach the repair, and the micro-looping packets can cause congestion, which leads to even more packet loss. 📉

the disruptive effect of micro-loops isn't limited to times when a component has failed. 🫠 micro-loops can form, for example, when a component is put back into service after repair. they can also form because of a network-maintenance action, like adding a new network component, removing one, or changing a link cost. 🛠️

this framework gives you a summary of the causes and consequences of micro-loops, so you can judge whether micro-looping is something your specific networks need to address. 🧐 it also surveys the currently proposed micro-loop mitigation mechanisms. when sufficiently fast convergence isn't available and the topology is susceptible to micro-loops, using one or more of these mechanisms may be desirable. ✨

2. The Nature of Micro-Loops 🌀

a micro-loop is a packet forwarding loop that can occur transiently among two or more routers in a hop-by-hop, packet forwarding paradigm. 🔁

micro-loops can form during the periods when a network is re-converging after ANY topology change. they're caused by inconsistent FIBs in the routers. 🙃 during the transition, a micro-loop can happen over a single link between a pair of routers that temporarily use each other as the next hop for a prefix. 🫣 micro-loops can also form when each router in a cycle of three or more routers has the next router in the cycle as its next hop for a given prefix. 🌪️

cyclic loops may occur if one or more of the following conditions are met:

1. Asymmetric link costs.
2. An equal-cost path exists between a pair of routers, each of which makes a different decision regarding which path to use for forwarding to a particular destination. Note that even routers that do not implement equal-cost, multi-path (ECMP) forwarding must make a choice between the available equal-cost paths, and unless they make the same choice, the condition for cyclic loops will be fulfilled.
3. Topology changes affecting multiple links, including single node and line card failures.

micro-loops have two undesirable side effects: congestion and repair starvation. 😩

• A looping packet keeps eating up bandwidth until it either escapes once the FIBs resync or its time to live (TTL) expires. this can transiently increase the traffic over a link by as much as 128 times, and it may make the link congested. 🚗💨 that congestion cuts down the bandwidth available to other traffic (which wasn't otherwise affected by the topology change). so the "innocent" traffic on that link gets increased latency and is liable to congestive packet loss. 🥺
• if the link or node failure has been protected by a fast-reroute repair, an inconsistency in the FIBs may stop some traffic from reaching the failure, and so it never gets repaired. the repair can end up starved of traffic and rendered ineffective. 🪦

micro-loops are usually thought about in the context of a failure, but similar problems of congestive packet loss and starvation can also happen when the topology change comes from management action. 🧑‍💻 for example, say a link is going to be taken out of service by management action. the link can stay in service throughout the transition, which means no repair is needed. 🙌 but if micro-loops form, they can cause congestion loss and may also keep traffic from reaching the link. 🫤

unless they're controlled, micro-loops may form in any part of the network that forwards (or, in the case of a new link, will forward) packets over a path that includes the affected topology change. ⚠️ the time it takes to propagate the change through the network, plus the non-uniform time each router takes to calculate the new shortest path tree (SPT) and update its FIB, both add to how long the packet disruption lasts. ⏳ in some cases, a packet can be hit by micro-loops that happen one after another at links along its path, which stretches the disruption well past what it'd take to resolve a single loop. 😵‍💫

part 1 of 5 done 🫶 the rest is coming, don't go anywhere 👀

3. Applicability ✨

okay so loop-free convergence techniques are applicable to ANY situation where micro-loops might form 🌀 for example, when a network is converging after:

1. Component failure 💥
2. Component repair 🔧
3. Management withdrawal of a component 🙅‍♀️
4. Management insertion or a component 🧩
5. Management change of link cost (either positive or negative) 📈📉
6. External cost change, for example, change of external gateway as a result of a BGP change 🌐
7. A Shared Risk Link Group (SRLG) failure 🫣

in each case, a component can be a link, a set of links, or an entire router 🖥️ throughout this document, we use the term SRLG when describing the procedure to be followed when multiple failures have occurred, whether or not they are members of an explicit SRLG 💅 and in the case of multiple independent failures, the loop-prevention method described for SRLG may be used, provided it is known that all of these failures have been repaired ✅

loop-free convergence techniques are applicable to both IP networks and MPLS-enabled networks that use LDP, including LDP networks that use the single-hop tunnel fast-reroute mechanism 🦋

an assessment of whether loop-free convergence techniques are required should take into account whether or not the interior gateway protocol (IGP) convergence is sufficiently fast that any micro-loops are of such short duration that they are not disruptive, and whether or not the topology is such that micro-loops are likely to form 🤔 the vibe check is literally about speed AND shape 🎀

---

4. Micro-Loop Control Strategies 🎀

micro-loop control strategies fall into four basic classes, bestie 👑

1. Micro-loop mitigation
2. Micro-loop prevention
3. Micro-loop suppression
4. Network design to minimise micro-loops

a micro-loop-mitigation scheme works by re-converging the network in such a way that it reduces, but does not eliminate, the formation of micro-loops 🫠 such schemes cannot guarantee the productive forwarding of packets during the transition 😭

a micro-loop-prevention mechanism controls the re-convergence of the network in such a way that no micro-loops form ✨ such a micro-loop-prevention mechanism allows the continued use of any fast repair method until the network has converged on its new topology, and it prevents the collateral damage that occurs to other traffic for the duration of each micro-loop 🛡️ iconic behaviour honestly

a micro-loop-suppression mechanism attempts to eliminate the collateral damage caused by micro-loops to other traffic 🧹 this may be achieved by, for example, using a packet-monitoring method that detects that a packet is looping and drops it 🙈 such schemes make no attempt to productively forward the packet throughout the network transition 💀

highly meshed topologies are less susceptible to micro-loops, so networks may be designed to minimise the occurrence of micro-loops by appropriate link placement and metric settings 🕸️ however, this approach may conflict with other design requirements, such as cost and traffic planning, and may not accurately track the evolution of the network or temporary changes due to outages 🥲

note that all known micro-loop-prevention mechanisms and most micro-loop-mitigation mechanisms extend the duration of the re-convergence process 🐢 when the failed component is protected by a fast-reroute repair, this implies that the converging network requires the repair to remain in place for longer than would otherwise be the case 🩹 the extended convergence time means any traffic that is not repaired by an imperfect repair experiences a significantly longer outage than it would experience with conventional convergence 😩

the trade-off is real, so don't skip past it!

when a component is returned to service, or when a network management action has taken place, this additional delay does not cause traffic disruption because there is no repair involved 🌸 however, the extended delay is undesirable because it increases the time that the network takes to be ready for another failure, and hence leaves it vulnerable to multiple failures 🥺

---

5. Loop Mitigation 🌷

there are two approaches to loop mitigation 💖

• Fast convergence
• A purpose-designed, loop-mitigation mechanism

5.1. Fast Convergence ⚡

the duration of micro-loops is dependent on the speed of convergence 🏃‍♀️ improving the speed of convergence may therefore be seen as a loop-mitigation technique 💜

5.2. PLSN 🧚

the only known purpose-designed, loop-mitigation approach is the Path Locking with Safe-Neighbors (PLSN) method described in PLSN [ANALYSIS] 📚 in this method, a micro-loop-free next-hop safety condition is defined as follows:

in a symmetric-cost network, it is safe for router X to change to the use of neighbor Y as its next hop for a specific destination if the path through Y to that destination satisfies both of the following criteria:

1. X considers Y as its loop-free neighbor based on the topology before the change, AND
2. X considers Y as its downstream neighbor based on the topology after the change.

in an asymmetric-cost network, a stricter safety condition is needed, and the criterion is that:

X considers Y as its downstream neighbor based on the topology both before and after the change. 🔒

based on these criteria, each router classifies destinations into three classes 🗂️

• Type A destinations: Destinations unaffected by the change (type A1) and also destinations whose next hop after the change satisfies the safety criteria (type A2).
• Type B destinations: Destinations that cannot be sent via the new, primary next hop because the safety criteria are not satisfied, but that can be sent via another next hop that does satisfy the safety criteria.
• Type C destinations: All other destinations.

following a topology change, type A destinations are immediately changed to go via the new topology 🏎️ type B destinations are immediately changed to go via the next hop that satisfies the safety criteria, even though this is not the shortest path 🐌 type B destinations continue to go via this path until all routers have changed their type C destinations over to the new next hop 🫶 routers must not change their type C destinations until all routers have changed their type A2 and B destinations to the new or intermediate (safe) next hop 🚦

simulations indicate that this approach produces a significant reduction in the number of links that are subject to micro-looping 📉 however, unlike all of the micro-loop-prevention methods, it is only a partial solution 🫣 in particular, micro-loops may form on any link joining a pair of type C routers 😬

because routers delay updating their type C destination FIB entries, they will continue to route towards the failure during the time when the routers are changing their type A and B destinations, and hence they will continue to productively forward packets, provided that viable repair paths exist 🥳

a backwards-compatibility issue arises with PLSN 🙃 if a router is not capable of micro-loop control, it will not correctly delay its FIB update 💔 if all such routers had only type A destinations, this loop-mitigation mechanism would work as it was designed 💫 alternatively, if all such incapable routers had only type C destinations, the "loop-prevention" announcement mechanism used to trigger the tunnel-based schemes (see Sections 6.2 to 6.4) could be used to cause the type A and B destinations to be changed, with the incapable routers and routers having type C destinations delaying until they received the "real" announcement 📣 unfortunately, these two approaches are mutually incompatible 😤

note that simulations indicate that in most topologies, treating type B destinations as type C results in only a small degradation in loop prevention 👌 also note that simulation results indicate that in production networks where some, but not all, links have asymmetric costs, using the stricter asymmetric-cost criterion actually reduces the number of loop-free destinations, because fewer destinations can be classified as type A or B 🙃

this mechanism operates identically for:

• events that degrade the topology (e.g., link failure),
• events that improve the topology (e.g., link restoration), and
• shared risk link group (SRLG) failure. 🫧

---

6. Micro-Loop Prevention 🛡️

eight micro-loop-prevention methods have been proposed, and they're all giving main character energy 👑

1. Incremental cost advertisement
2. Nearside tunneling
3. Farside tunneling
4. Distributed tunnels
5. Packet marking
6. New MPLS labels
7. Ordered FIB update
8. Synchronized FIB update 🌈

6.1. Incremental Cost Advertisement ✨

okay so when a link dies, the usual move is that its cost jumps from its normal metric straight to "infinity" in one go 💀. BUT here's the tea 🫖: it can be proved [OPT] that no micro-loops form if the cost goes up in suitable increments, and the network gets time to settle before the next bump is advertised. Once the link cost is higher than the cheapest alternative cost around that link, the link can be disabled without causing a micro-loop 🦋

the rule for a cost change to be safe is that any link getting a cost change of x can only cause loops in a part of the network whose cyclic cost is less than or equal to x 🧠 because some links cost one in each direction (so the cyclic cost is two), the link cost might have to go up in increments of one. the increment can be bigger when the minimum cost allows it though 🌸 recent work [OPT] found a bunch of optimizations that pin down the exact set of cost values needed, so you can minimise the number of increments. iconic 👑

when a link comes back into service, its cost drops in small steps from "infinity" down to its final cost. this gives you similar micro-loop prevention during a "good-news" event ✨ also, the link cost can be decreased from "infinity" to any value greater than the cheapest alternative cost around the link in one step, and that still won't cause a micro-loop 💖

when the failure is an SRLG, the link cost increments must be coordinated across all failing members of the SRLG. you can do this by finishing one link's transition before starting the next, or by interleaving the changes 🎀

the incremental cost change approach has an advantage over every other currently known loop-prevention scheme: it requires no change to the routing protocol 🙌 it works in any network because it doesn't need any cooperation from the other routers. literally no notes 💅

when the micro-loop-prevention mechanism is being used to support a planned reconfiguration of the network, the extra reconvergence time from the multiple increments is of limited consequence, especially if the number of increments has been optimized 🍓 that, plus the fact you can implement this technique in isolation, makes it a good candidate for management-initiated changes. good match fr fr

when the micro-loop-prevention mechanism is being used to support failure recovery, though, the number of increments, and so the time to fully converge, matters a lot, even when the number of increments is small 😭 during the transition, some parts of the network keep using the old forwarding path, so they use any repair mechanism for a long time. if a failure can't be fully repaired, some destinations might become unreachable for an extended period. on top of that, the network may be vulnerable to a second failure for the whole duration of the controlled re-convergence 🥺

⚠️ bestie, big deal: for failure recovery, the slow re-convergence can leave destinations unreachable for a while, and the network is exposed to a second failure the whole time. not a vibe.

where large metrics are used and no optimization (like the one described above) is performed, the incremental cost method can be extremely slow 🐌 but when the per-link metric is small, either because the network designers assigned small values or because of restrictions built into the routing protocol (e.g., RIP restricts the metric, and BGP using the autonomous system (AS) path length frequently uses an effective metric of one or a very small integer for each inter AS hop), the number of required increments can be acceptably small even without optimizations 🌈

6.2. Nearside Tunneling 🎀

this one builds an overlay network out of tunnels whose path isn't affected by the topology change, then carries the traffic affected by the change through that new network 🧚 once all the traffic is in the tunnel-based network, the real network is allowed to converge on the new topology. since all the affected traffic rides the overlay, no micro-loops form. so clean 😌

when a failure is detected (or a link is withdrawn from service), the router next to the failure issues a new "loop-prevention" routing message announcing the topology change 📣 every router propagates this message, but only routers that can use one of the tunnel-based, micro-loop-prevention mechanisms actually understand it 🫶

each micro-loop-preventing router builds a tunnel to the closest router adjacent to the failure. then they figure out which of their traffic would transit the failure and put that traffic in the tunnel 🚇 once all these tunnels are in place (for example, by waiting a suitable interval), the failure is announced as normal. the tunnels aren't affected by the transition, and the routers protecting the link keep the repair going (or forward across the link being withdrawn), so no traffic gets disrupted by the failure 💪 when the network has converged, the tunnels are withdrawn, and traffic follows its new "natural" path. the order of tunnel insertion and withdrawal doesn't matter, as long as all tunnels are in place before the normal announcement goes out and the repair stays in place until normal convergence is done 🍰

this method completes in bounded time and is generally way faster than the incremental cost method ⚡ depending on the exact design, it finishes in two or three flood-SPF-FIB update cycles.

at the moment the failure is announced as normal, micro-loops may form inside isolated islands of non-micro-loop-preventing routers 🏝️ but only traffic entering the network through those routers can micro-loop. any traffic entering through a micro-loop-preventing router gets tunneled correctly to the nearest repairing router (including, if necessary, being tunneled via a non-micro-loop-preventing router) and won't micro-loop 🙅‍♀️

where there's no requirement to prevent micro-loops involving non-micro-loop-preventing routers, a single "normal" announcement may be made, and a local timer can decide when the switch from tunneled forwarding to normal forwarding over the new topology starts ⏰

the catch is that this technique requires traffic to be tunneled during the transition 🙃 that's an issue in IP networks, because not all router designs can do high-performance IP tunneling. it's also an issue in MPLS networks, because the encapsulating router has to know the label set that the decapsulating router is distributing.

another downside: this method requires cooperation from all the routers within the routing domain to fully protect the network against micro-loops 🥲

when a new link is added, the mechanism runs in "reverse" 🔄 when the loop-prevention announcement is heard, routers work out which traffic they'll send over the new link, and tunnel that traffic to the router on the near side of that link. that path isn't affected by the presence of the new link. when the "normal" announcement is heard, they update their FIB to send traffic normally, according to the new topology. any traffic that hits a router that hasn't updated its FIB yet gets tunneled to the near side of the link, so it won't loop ✨

when a management change to the topology is required, exactly the same mechanism protects packets from micro-looping across the micro-loop-preventing routers 🫧

when the failure is an SRLG, the required strategy is to classify traffic according to the furthest failing member of the SRLG that it will traverse on its way to the destination, and then tunnel that traffic to the repairing router for that SRLG member 🎯 this needs multiple tunnel destinations. in the limiting case, that's one per SRLG member, which is a lot of tunnels, bestie 😵‍💫

6.3. Farside Tunnels 🌙

farside tunneling loop prevention means the loop-preventing routers put all the traffic that would cross the failure into one or more tunnels that terminate at the router (or, for a node failure, routers) on the far side of the failure 🌊 the perks are a more uniform spread of repair traffic than the nearside tunnel method gives you and, for a node failure, less decapsulation load on any single router. nice 💜

unlike the nearside tunnel method (which uses normal routing to reach the repairing router), this method needs a repair path to the farside router. that can come from the not-via [NOT-VIA] mechanism, in which case no further computation is needed ✅

otherwise it works exactly like the nearside tunneling loop-prevention method (Section 6.2) 💅

6.4. Distributed Tunnels 🧩

in the distributed tunnels loop-prevention method, every router calculates its own repair and forwards the affected traffic over that repair 🛠️ this is different from the fast reroute (FRR) case, because the actual failure is already known when the calculation happens. the goal of the loop-preventing routers is to get the packets that would have gone through the failure into Q-space [FRR-TUNN], using routers that are in P-space. packets get decapsulated on entry to Q-space instead of being forced to the farside of the failure, so you can get more optimum routing 🤩 this method is subject to the same reachability constraints described in [FRR-TUNN].

otherwise it's identical to the nearside tunneling loop-prevention method (Section 6.2) 🫶

one alternative distributed tunnel mechanism: all routers tunnel to the not-via address [NOT-VIA] associated with the failure 🦋

6.5. Packet Marking 🏷️

if packets could be marked somehow, that marking could be used to sort them into one of:

• the new topology,
• the old topology, or
• a transition topology.

they'd then get forwarded correctly during the transition 🎉 this works the same way for both "bad-news" and "good-news" events. it also works the same way for SRLG failure. but there are three problems with this solution 😬

• A packet-marking bit may not be available. For example, a network supporting both the differentiated services architecture [RFC2475] and explicit congestion notification [RFC3168] uses all eight bits of the IPv4 Type of Service field.
• The mechanism would introduce a non-standard forwarding procedure.
• Packet marking using either the old or the new topology would double the size of the FIB; however, some optimizations may be possible.

6.6. MPLS New Labels 🎀

okay so bestie, this one's for MPLS networks that use [RFC5036] for label distribution 🦋 The move here is that loop-free convergence happens through new labels whenever the path a prefix takes through the network changes ✨

Remember Section 6.2? The repairing routers send out a loop-prevention announcement to kick off the loop-free convergence process 📣 Then every loop-preventing router works out the new topology and checks whether its FIB actually needs to change. If it doesn't, that router just sits this one out 💤

The routers that do need a FIB change look at each change and check the new next hop. They're asking whether that next hop has a path in the OLD topology that reaches the destination without going through the failure (so, whether the next hop is in P-space with respect to the failure [FRR-TUNN]). If yes, the FIB entry can be updated straight away 🙌 For every other FIB entry, the router sends a new label to each of its neighbors. That new label locks the path during the transition, kind of like the tunnel method from Section 6.2 🔒 Routers that receive a new label install it in their FIB for MPLS label translation, but they don't remove the old label yet, and they don't use the new label to forward IP packets yet. They get ready to forward on the new path, but they hold off. Any packets that show up keep going the old way, using the old labels, towards the repair 🧚

Then, some time after the loop-prevention announcement, a normal routing announcement of the failure goes out 📢 This announcement must not be issued until all routers have finished every activity that was triggered by the loop-prevention announcement. Once the normal announcement arrives, every router that was holding back convergence moves to its new path for both the new and the old labels. That means changing the IP address entries to use the new labels AND changing the old labels to forward using the new labels 💅

Because the new label path was installed during the loop-prevention phase, packets get to their destinations like this:

• If they don't go via any router using a new label, they go via the repairing router and the repair 🛠️
• If they meet any router that is using the new labels, they get marked with the new labels and reach their destination using the new path, back-tracking if necessary 🔥

Once every router has switched to the new path, the network is converged 👑 Much later, when it's safe to assume every router is on the new path, the FIB gets cleaned up and the now-redundant old labels are removed 🧹

As with other methods, the new labels can be modified to provide loop prevention for "good news" 🌈 There are also a number of optimizations of this method, so there's more to explore if you're curious ✨

---

6.7. Ordered FIB Update 🪜

The ordered FIB loop-prevention method is described in "Loop-free convergence using oFIB" [oFIB]. Okay, this one is so clever 😭 Micro-loops happen after a failure or a cost increase, when a router closer to the failed component updates its routes for the failure before a router that's further away does. So the trick is analysing the reverse shortest path tree (rSPT) that traffic heads along toward the failed component in the old topology. From that, you can work out a strict ordering where nodes closer to the root always process the failure after any nodes further away 🌳 That's how micro-loops get prevented 🙌

When the failure has been announced, each router waits a multiple of the convergence timer [LF-TIMERS]. The multiple depends on the node's position in the rSPT, and the delay is picked so a node can finish its processing within that time ⏳ The convergence time can be cut down by using a signaling mechanism to tell the parent when all its children have finished processing. Then the parent knows when it's safe to instantiate its new routes 💜

The property here is that the delay is bounded by the network diameter, although in lots of cases it'll be way less 🦋

When a link comes back into service, the convergence process above runs in reverse 🔄 A router first works out its distance (in hops) from the new link in the NEW topology. Then, before it updates its FIB, it waits a time equal to that distance multiplied by the convergence timer ✨

It'll be seen that network-management actions can be handled the same way, by treating a cost increase like a failure and a cost decrease like a restoration 🎀

The ordered FIB mechanism requires all nodes in the domain to operate according to these procedures. Non-cooperating nodes can cause loops for any traffic that goes through them (not just traffic that originates from them) 😬 Without extra mechanisms, those loops could stick around for a significant amount of time 💀

It should be noted that this method needs per-router ordering but not per-prefix ordering 💅 A router has to wait its turn to update its FIB, but then it should update its entire FIB, all at once 🫶

When an SRLG failure happens, a router has to sort traffic into the classes that pass over each member of the SRLG 🗂️ Each router is then independently given a ranking for each SRLG member it has a traffic class for. These rankings can be different for each traffic class. The prefixes of each class then get changed in the FIB according to the order of their specific ranking 🌸 Like the single failure case, signaling can be used to speed up convergence too ⚡

Also, the special SRLG case of a full or partial node failure can be handled without per-prefix ordering, by running a single reverse-SPF computation rooted at the failed node (or the common point of the subset of failing links in the partial case) 🧠

There are two classes of signaling optimization for the ordered FIB loop-prevention method:

• When the router makes NO change, it can signal immediately. This significantly reduces the time the network takes to process long chains of routers that have no change to make to their FIB 🏃‍♀️💨
• When a router HAS changed, it can signal that it has completed. This is more problematic, since it may be difficult to determine, particularly in a distributed architecture. The optimization obtained is the difference between the actual time taken to make the FIB change and the worst-case timer value. This saving could be of the order of one second per hop ⏱️

There's another way to run ordered FIB that's based on pure signaling [SIG] 📡 Methods that use signaling as an optimization are safe, because they eventually fall back on the established IGP mechanisms that make sure networks converge even under packet loss 🛟 But a mechanism that relies on signaling in order to converge needs a reliable signaling mechanism, and that has to be proven to recover from any failure circumstance 🧐 Big ask, bestie 😅

---

6.8. Synchronised FIB Update ⏰

Micro-loops form because the FIB update process is asynchronous during a network transition 🌀 In many router architectures, the time it takes to update the FIB itself is the dominant term 🐢 One approach is to have two FIBs and, in a synchronized action across the whole network, switch from the old one to the new one 🔁 One way to get that synchronized change is to signal (or otherwise determine) the wall clock time of the change, and then execute the change at that time. NTP [RFC1305] is used to synchronize the wall clocks in the routers ⌚

This approach has a few major issues, though 😬 Firstly, two complete FIBs are needed, which may create a scaling issue. Secondly, a suitable network-wide synchronization method is needed. Neither of these is insurmountable, though, so don't panic 🫶

Since the FIB change synchronization won't be perfect, there may be some interval during which micro-loops form 🌊 So whether this scheme counts as a micro-loop-prevention mechanism or a micro-loop-mitigation mechanism in this taxonomy depends on how much synchronization is achieved 📏

This mechanism works identically for both "bad-news" and "good-news" events, and it also works identically for SRLG failure 🙌 Interoperating with routers that don't support this mechanism still needs more thought 🤔 Without a suitable interoperating mechanism, loops may form for the duration of the synchronization delay ⚠️

---

7. Using PLSN in Conjunction with Other Methods 🤝

All of the tunnel methods and packet marking can be combined with PLSN (see Section 5.2 of this document and [ANALYSIS]) to reduce the traffic that needs protecting by the advanced method 💖 Specifically, all traffic could use PLSN except traffic between a pair of routers where both consider the destination to be type C. That type-C-to-type-C traffic would be protected from micro-looping by using a loop-prevention method 🛡️

However, working out whether the new next-hop router considers a destination to be type C may be computationally intensive 🧮 An alternative is to use a loop-prevention method for all local type C destinations. That needs no extra computation, but it means the extra loop-prevention method gets used in cases that wouldn't have generated loops (i.e., when the new next-hop router considered the destination to be type A or B) 🥲

How much traffic would use PLSN depends heavily on the network topology and the specific change, but it's expected to be in the range of 70% to 90% in typical networks 📈

BUT, PLSN can't be combined safely with ordered FIB 🚫 Check out this network fragment:

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

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

---

8. Loop Suppression 🚫

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

Another approach would be to recognize that a packet was looping because it's being sent back to the place it had just come from 🔙 This would work for the types of loop that form in symmetric-cost networks, but it wouldn't suppress the cyclic loops that form in asymmetric networks or as a result of multiple failures 🌀

This mechanism operates identically for "bad-news" events, "good-news" events, and SRLG failure alike 🎀

9. Compatibility Issues 🎀

okay so bestie, deploying any micro-loop-control mechanism is a big deal 😭 it's a major change to a network, so you have to think really hard about how routers that can do micro-loop control will play with routers that can't 🫶 ngl this is the part people skip and then regret.

Also, you might be tempted to pick a method just because it's the simplest one 💅 totally valid, but you have to remember that if a fancier scheme is needed later, it could be way harder to roll out because it has to interact with whatever you already deployed. future-you will thank you 🔮

10. Comparison of Loop-Free Convergence Methods ✨

okay here's the tea on every method, no cap 🍵

PLSN [ANALYSIS] is an efficient way to prevent micro-loops, but it's only a partial solution 🌸 it's a useful sidekick for some of the complete solutions, though it may need modifications.

Incremental cost advertisement in its simplest form is impractical as a general solution because it takes way too long to finish 💀 optimized incremental cost advertisement is much faster, though, and it doesn't need any help from other routers in the network 🦋 so it's giving perfect for network-reconfiguration operations.

Packet marking is probably impractical, because you'd need to find the marking bit and change how forwarding behaves, and that's a lot 🙈

Of the rest, distributed tunnels are significantly more complex than nearside or farside tunnels 😩 they should only be considered if there's a requirement to spread the tunnel decapsulation load around.

Synchronised FIBs is a fast method, but it has the issue that a suitable synchronization mechanism still needs to be defined ✨ one option would be to use NTP [RFC1305]. However, tying routing convergence to a protocol that itself uses the network could be a problem 😬 also, during the transition there will be some micro-looping for a short interval, because it's impossible to get a perfectly synchronized FIB changeover 💜

The ordered FIB mechanism has a major advantage: it's a control-plane-only solution 👑 but SRLGs need a per-destination calculation, and the convergence delay may be high, bounded by the network diameter 🥲 using signaling as an accelerator may cut down how many destinations experience the full delay, which can bring the total re-convergence time down to an acceptable period 🌈

The nearside and farside tunnel methods handle SRLGs and uncorrelated changes pretty easily 🎀 the convergence delay would be small. The catch is that they need tunneled forwarding, which isn't supported on all router hardware, and it raises forwarding performance issues 😤 when you use them with PLSN, though, the amount of traffic that gets tunneled is significantly reduced, so those performance concerns shrink too ✨ and if your chosen repair mechanism needs tunnels anyway, a tunnel-based loop prevention scheme may be acceptable.

11. Security Considerations 🔐

bestie, this one is serious 🚨 this document analyzes the problem of micro-loops and summarizes a number of potential solutions that have been proposed. These solutions need only minor modifications to existing routing protocols, so they don't add any additional security risks 🫶

BUT (and this is a big but 😭), a full security analysis would need to be provided within the specification of any particular solution that gets proposed for deployment. so if you're picking one to actually ship, go do that homework first 📚💖

12. Acknowledgments 💜

The authors would like to give a huge shoutout to Clarence Filsfils for their contributions to this document 🫶🌸

13. Informative References 📚

[ANALYSIS]   Zinin, A., "Analysis and Minimization of Microloops in
             Link-state Routing Protocols", Work in Progress,
             October 2005.

[FRR-TUNN]   Bryant, S., Filsfils, C., Previdi, S., and M. Shand, "IP
             Fast Reroute using tunnels", Work in Progress,
             November 2007.

[LF-TIMERS]  Atlas, A., Bryant, S., and M. Shand, "Synchronisation of
             Loop Free Timer Values", Work in Progress,
             February 2008.

[NOT-VIA]    Shand, M., Bryant, S., and S. Previdi, "IP Fast Reroute
             Using Not-via Addresses", Work in Progress, July 2009.

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

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

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

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

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

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

[RFC5714]    Shand, M. and S. Bryant, "IP Fast Reroute Framework",
             RFC 5714, January 2010.

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

[oFIB]       Francois, P., "Loop-free convergence using oFIB", Work
             in Progress, February 2008.

Authors' Addresses 🧚

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

EMail: mshand@cisco.com


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

EMail: stbryant@cisco.com

---

That's the whole thing, bestie! 🌈✨ You made it to the end of RFC 5715 💅💖