draft-ietf-rtgwg-uloop-delay-09.txt   rfc8333.txt 
Routing Area Working Group S. Litkowski Internet Engineering Task Force (IETF) S. Litkowski
Internet-Draft B. Decraene Request for Comments: 8333 B. Decraene
Intended status: Standards Track Orange Category: Standards Track Orange
Expires: May 16, 2018 C. Filsfils ISSN: 2070-1721 C. Filsfils
Cisco Systems Cisco Systems
P. Francois P. Francois
Individual Individual Contributor
November 12, 2017 March 2018
Micro-loop prevention by introducing a local convergence delay Micro-loop Prevention by Introducing a Local Convergence Delay
draft-ietf-rtgwg-uloop-delay-09
Abstract Abstract
This document describes a mechanism for link-state routing protocols This document describes a mechanism for link-state routing protocols
to prevent local transient forwarding loops in case of link failure. that prevents local transient forwarding loops in case of link
This mechanism proposes a two-step convergence by introducing a delay failure. This mechanism proposes a two-step convergence by
between the convergence of the node adjacent to the topology change introducing a delay between the convergence of the node adjacent to
and the network wide convergence. the topology change and the network-wide convergence.
As this mechanism delays the IGP convergence it may only be used for Because this mechanism delays the IGP convergence, it may only be
planned maintenance or when fast reroute protects the traffic between used for planned maintenance or when Fast Reroute (FRR) protects the
the link failure time and the IGP convergence. traffic during the time between the link failure and the IGP
convergence.
The proposed mechanism is limited to the link down event in order to The mechanism is limited to the link-down event in order to keep the
keep the mechanism simple. mechanism simple.
Simulations using real network topologies have been performed and Simulations using real network topologies have been performed and
show that local loops are a significant portion (>50%) of the total show that local loops are a significant portion (>50%) of the total
forwarding loops. forwarding loops.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This is an Internet Standards Track document.
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.
This Internet-Draft will expire on May 16, 2018. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc8333.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction ....................................................4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology .....................................................4
3. Transient forwarding loops side effects . . . . . . . . . . . 4 2.1. Acronyms ...................................................4
3.1. Fast reroute inefficiency . . . . . . . . . . . . . . . . 4 2.2. Requirements Language ......................................5
3.2. Network congestion . . . . . . . . . . . . . . . . . . . 7 3. Side Effects of Transient Forwarding Loops ......................5
4. Overview of the solution . . . . . . . . . . . . . . . . . . 7 3.1. FRR Inefficiency ...........................................5
5. Specification . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. Network Congestion .........................................8
5.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 8 4. Overview of the Solution ........................................9
5.2. Regular IGP reaction . . . . . . . . . . . . . . . . . . 8 5. Specification ...................................................9
5.3. Local events . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Definitions ................................................9
5.4. Local delay for link down . . . . . . . . . . . . . . . . 10 5.2. Regular IGP Reaction ......................................10
6. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 10 5.3. Local Events ..............................................10
6.1. Applicable case: local loops . . . . . . . . . . . . . . 10 5.4. Local Delay for Link-Down Events ..........................11
6.2. Non applicable case: remote loops . . . . . . . . . . . . 11 6. Applicability ..................................................11
7. Simulations . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1. Applicable Case: Local Loops ..............................12
8. Deployment considerations . . . . . . . . . . . . . . . . . . 12 6.2. Non-applicable Case: Remote Loops .........................12
9. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 13 7. Simulations ....................................................13
9.1. Local link down . . . . . . . . . . . . . . . . . . . . . 14 8. Deployment Considerations ......................................14
9.2. Local and remote event . . . . . . . . . . . . . . . . . 18 9. Examples .......................................................15
9.3. Aborting local delay . . . . . . . . . . . . . . . . . . 19 9.1. Local Link-Down Event .....................................15
10. Comparison with other solutions . . . . . . . . . . . . . . . 23 9.2. Local and Remote Event ....................................19
10.1. PLSN . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.3. Aborting Local Delay ......................................21
10.2. OFIB . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10. Comparison with Other Solutions ...............................23
11. Implementation Status . . . . . . . . . . . . . . . . . . . . 24 10.1. PLSN .....................................................23
12. Security Considerations . . . . . . . . . . . . . . . . . . . 25 10.2. oFIB .....................................................24
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 11. IANA Considerations ...........................................24
14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 12. Security Considerations .......................................24
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 13. References ....................................................25
15.1. Normative References . . . . . . . . . . . . . . . . . . 26 13.1. Normative References .....................................25
15.2. Informative References . . . . . . . . . . . . . . . . . 26 13.2. Informative References ...................................25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 Acknowledgements ..................................................26
Authors' Addresses ................................................26
1. Acronyms 1. Introduction
FIB: Forwarding Information Base Micro-loops and some potential solutions are described in [RFC5715].
This document describes a simple targeted mechanism that prevents
micro-loops that are local to the failure. Based on network
analysis, local micro-loops make up a significant portion of the
micro-loops. A simple and easily deployable solution for these local
micro-loops is critical because these local loops cause some traffic
loss after an FRR alternate has been used (see Section 3.1).
FRR: Fast ReRoute Consider the case in Figure 1 where S does not have an LFA (Loop-Free
Alternate) to protect its traffic to D when the S-D link fails. That
means that all non-D neighbors of S on the topology will send to S
any traffic destined to D; if a neighbor did not, then that neighbor
would be loop-free. Regardless of the advanced FRR technique used,
when S converges to the new topology, it will send its traffic to a
neighbor that is not loop-free and will thus cause a local micro-
loop. The deployment of advanced FRR techniques motivates this
simple router-local mechanism to solve this targeted problem. This
solution can work with the various techniques described in [RFC5715].
IGP: Interior Gateway Protocol D ------ C
| |
| | 5
| |
S ------ B
LFA: Loop Free Alternate Figure 1
LSA: Link State Advertisement In Figure 1, all links have a metric of 1 except the B-C link, which
has a metric of 5. When the S-D link fails, a transient forwarding
loop may appear between S and B if S updates its forwarding entry to
D before B does.
LSP: Link State Packet 2. Terminology
MRT: Maximum Redundant Trees 2.1. Acronyms
OFIB: Ordered FIB FIB: Forwarding Information Base
PLSN: Path Locking via Safe Neighbor FRR: Fast Reroute
RIB: Routing Information Base IGP: Interior Gateway Protocol
RLFA: Remote Loop Free Alternate LFA: Loop-Free Alternate
SPF: Shortest Path First LSA: Link State Advertisement
LSP: Link State Packet
TTL: Time To Live MRT: Maximally Redundant Tree
2. Introduction oFIB: Ordered FIB
Micro-forwarding loops and some potential solutions are well PLR: Point of Local Repair
described in [RFC5715]. This document describes a simple targeted
mechanism that prevents micro-loops that are local to the failure.
Based on network analysis, local failures make up a significant
portion of the micro-forwarding loops. A simple and easily
deployable solution for these local micro-loops is critical because
these local loops cause some traffic loss after a fast-reroute
alternate has been used (see Section 3.1).
Consider the case in Figure 1 where S does not have an LFA (Loop Free PLSN: Path Locking via Safe Neighbors
Alternate) to protect its traffic to D when the S-D link fails. That
means that all non-D neighbors of S on the topology will send to S
any traffic destined to D; if a neighbor did not, then that neighbor
would be loop-free. Regardless of the advanced fast-reroute (FRR)
technique used, when S converges to the new topology, it will send
its traffic to a neighbor that was not loop-free and thus cause a
local micro-loop. The deployment of advanced fast-reroute techniques
motivates this simple router-local mechanism to solve this targeted
problem. This solution can work with the various techniques
described in [RFC5715].
D ------ C RIB: Routing Information Base
| |
| | 5
| |
S ------ B
Figure 1 RLFA: Remote Loop-Free Alternate
In the Figure 1, all links have a metric of 1 except B-C which has a SPF: Shortest Path First
metric of 5. When S-D fails, a transient forwarding loop may appear
between S and B if S updates its forwarding entry to D before B does.
3. Transient forwarding loops side effects TTL: Time to Live
2.2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
3. Side Effects of Transient Forwarding Loops
Even if they are very limited in duration, transient forwarding loops Even if they are very limited in duration, transient forwarding loops
may cause significant network damage. may cause significant network damage.
3.1. Fast reroute inefficiency 3.1. FRR Inefficiency
D In Figure 2, we consider an IP/LDP routed network.
1 |
| 1
A ------ B
| | ^
10 | | 5 | T
| | |
E--------C
| 1
1 |
S
Figure 2 - RSVP-TE FRR case D
1 |
| 1
A ------ B
| | ^
10 | | 5 | T
| | |
E--------C
| 1
1 |
S
In the Figure 2, we consider an IP/LDP routed network. An RSVP-TE Figure 2
tunnel T, provisioned on C and terminating on B, is used to protect
the traffic against C-B link failure (the IGP shortcut feature,
defined in [RFC3906], is activated on C ). The primary path of T is
C->B and FRR is activated on T providing an FRR bypass or detour
using path C->E->A->B. On router C, the next hop to D is the tunnel
T thanks to the IGP shortcut. When C-B link fails:
1. C detects the failure, and updates the tunnel path using a An RSVP-TE tunnel T, provisioned on C and terminating on B, is used
preprogrammed FRR path. The traffic path from S to D becomes: to protect the traffic against C-B link failure (the IGP shortcut
feature, defined in [RFC3906], is activated on C). The primary path
of T is C->B and FRR is activated on T, providing an FRR bypass or
detour using path C->E->A->B. On router C, the next hop to D is the
tunnel T, thanks to the IGP shortcut. When the C-B link fails:
1. C detects the failure and updates the tunnel path using a
preprogrammed FRR path. The traffic path from S to D becomes
S->E->C->E->A->B->A->D. S->E->C->E->A->B->A->D.
2. In parallel, on router C, both the IGP convergence and the TE 2. In parallel, on router C, both the IGP convergence and the TE
tunnel convergence (tunnel path recomputation) are occurring: tunnel convergence (tunnel path recomputation) are occurring:
* The Tunnel T path is recomputed and now uses C->E->A->B. * The tunnel T path is recomputed and now uses C->E->A->B.
* The IGP path to D is recomputed and now uses C->E->A->D. * The IGP path to D is recomputed and now uses C->E->A->D.
3. On C, the tail-end of the TE tunnel (router B) is no longer on 3. On C, the tail-end of the TE tunnel (router B) is no longer on
the shortest-path tree (SPT) to D, so C does not continue to the shortest-path tree (SPT) to D, so C does not continue to
encapsulate the traffic to D using the tunnel T and updates its encapsulate the traffic to D using the tunnel T and updates its
forwarding entry to D using the nexthop E. forwarding entry to D using the next-hop E.
If C updates its forwarding entry to D before router E, there would If C updates its forwarding entry to D before router E, there would
be a transient forwarding loop between C and E until E has converged. be a transient forwarding loop between C and E until E has converged.
The table 1 below describes a theoretical sequence of events Table 1 describes a theoretical sequence of events happening when the
happening when the B-C link fails. This theoretical sequence of B-C link fails. This theoretical sequence of events should only be
events should only be read as an example. read as an example.
+-----------+------------+------------------+-----------------------+ +------------+--------+---------------------+-----------------------+
| Network | Time | Router C events | Router E events | | Network | Time | Router C Events | Router E Events |
| condition | | | | | Condition | | | |
+-----------+------------+------------------+-----------------------+ +------------+--------+---------------------+-----------------------+
| S->D | | | | | S->D | | | |
| Traffic | | | | | Traffic OK | | | |
| OK | | | | | | | | |
| | | | | | S->D | t0 | Link B-C fails | Link B-C fails |
| S->D | t0 | Link B-C fails | Link B-C fails | | Traffic | | | |
| Traffic | | | | | lost | | | |
| lost | | | | | | | | |
| | | | | | | t0+20 | C detects the | |
| | t0+20msec | C detects the | | | | ms | failure | |
| | | failure | | | | | | |
| | | | | | S->D | t0+40 | C activates FRR | |
| S->D | t0+40msec | C activates FRR | | | Traffic OK | ms | | |
| Traffic | | | | | | | | |
| OK | | | | | | t0+50 | C updates its local | |
| | | | | | | ms | LSP/LSA | |
| | t0+50msec | C updates its | | | | | | |
| | | local LSP/LSA | | | | t0+60 | C floods its local | |
| | | | | | | ms | updated LSP/LSA | |
| | t0+60msec | C schedules SPF | | | | | | |
| | | (100ms) | | | | t0+62 | C schedules SPF | |
| | | | | | | ms | (100 ms) | |
| | t0+70msec | C floods its | | | | | | |
| | | local updated | | | | t0+87 | | E receives LSP/LSA |
| | | LSP/LSA | | | | ms | | from C and floods it |
| | | | | | | | | |
| | t0+87msec | | E receives LSP/LSA | | | t0+92 | | E schedules SPF (100 |
| | | | from C and schedules | | | ms | | ms) |
| | | | SPF (100ms) | | | | | |
| | | | | | | t0+163 | C computes SPF | |
| | t0+117msec | | E floods LSP/LSA from | | | ms | | |
| | | | C | | | | | |
| | | | | | | t0+165 | C starts updating | |
| | t0+160msec | C computes SPF | | | | ms | its RIB/FIB | |
| | | | | | | | | |
| | t0+165msec | C starts | | | | t0+193 | | E computes SPF |
| | | updating its | | | | ms | | |
| | | RIB/FIB | | | | | | |
| | | | | | | t0+199 | | E starts updating its |
| | t0+193msec | | E computes SPF | | | ms | | RIB/FIB |
| | | | | | | | | |
| | t0+199msec | | E starts updating its | | S->D | t0+255 | C updates its | |
| | | | RIB/FIB | | Traffic | ms | RIB/FIB for D | |
| | | | | | lost | | | |
| S->D | t0+255msec | C updates its | | | | | | |
| Traffic | | RIB/FIB for D | | | | t0+340 | C convergence ends | |
| lost | | | | | | ms | | |
| | | | | | | | | |
| | t0+340msec | C convergence | | | S->D | t0+443 | | E updates its RIB/FIB |
| | | ends | | | Traffic OK | ms | | for D |
| | | | | | | | | |
| S->D | t0+443msec | | E updates its RIB/FIB | | | t0+470 | | E convergence ends |
| Traffic | | | for D | | | ms | | |
| OK | | | | +------------+--------+---------------------+-----------------------+
| | | | |
| | t0+470msec | | E convergence ends |
+-----------+------------+------------------+-----------------------+
Table 1 - Route computation event time scale Table 1
The issue described here is completely independent of the fast- The issue described here is completely independent of the FRR
reroute mechanism involved (TE FRR, LFA/rLFA, MRT ...) when the mechanism involved (e.g., TE FRR, LFA/RLFA, MRT, etc.) when the
primary path uses hop-by-hop routing. The protection enabled by primary path uses hop-by-hop routing. The protection enabled by FRR
fast-reroute is working perfectly, but ensures a protection, by works perfectly but only ensures protection until the PLR has
definition, only until the PLR has converged (as soon as the PLR has converged (as soon as the PLR has converged, it replaces its FRR path
converged, it replaces its FRR path by a new primary path). When with a new primary path). When implementing FRR, a service provider
implementing FRR, a service provider wants to guarantee a very wants to guarantee a very limited loss of connectivity time. The
limited loss of connectivity time. The previous example shows that example described in this section shows that the benefit of FRR may
the benefit of FRR may be completely lost due to a transient be completely lost due to a transient forwarding loop appearing when
forwarding loop appearing when PLR has converged. Delaying FIB PLR has converged. Delaying FIB updates after the IGP convergence
updates after the IGP convergence may allow to keep the fast-reroute (1) may allow the FRR path to be kept until the neighbors have
path until the neighbors have converged and preserves the customer converged and (2) preserves the customer traffic.
traffic.
3.2. Network congestion 3.2. Network Congestion
1 In Figure 3, when the S-D link fails, a transient forwarding loop may
D ------ C appear between S and B for destination D. The traffic on the S-B
| | link will constantly increase due to the looping traffic to D.
1 | | 5 Depending on the TTL of the packets, the traffic rate destined to D,
| | and the bandwidth of the link, the S-B link may become congested in a
A -- S ------ B few hundreds of milliseconds and will stay congested until the loop
/ | 1 is eliminated.
F E
Figure 3 1
D ------ C
| |
1 | | 5
| |
A -- S ------ B
/ | 1
F E
In the figure above, as presented in Section 2, when the link S-D Figure 3
fails, a transient forwarding loop may appear between S and B for
destination D. The traffic on the S-B link will constantly increase
due to the looping traffic to D. Depending on the TTL of the
packets, the traffic rate destined to D, and the bandwidth of the
link, the S-B link may become congested in a few hundreds of
milliseconds and will stay congested until the loop is eliminated.
The congestion introduced by transient forwarding loops is The congestion introduced by transient forwarding loops is
problematic as it can affect traffic that is not directly affected by problematic as it can affect traffic that is not directly affected by
the failing network component. In the example, the congestion of the the failing network component. In Figure 3, the congestion of the
S-B link will impact some customer traffic that is not directly S-B link will impact some customer traffic that is not directly
affected by the failure: e.g. A to B, F to B, E to B. Class of affected by the failure, e.g., traffic from A to B, F to B, and E to
service may mitigate the congestion for some traffic. However, some B. Class of service may mitigate the congestion for some traffic.
traffic not directly affected by the failure will still be dropped as However, some traffic not directly affected by the failure will still
a router is not able to distinguish the looping traffic from the be dropped as a router is not able to distinguish the looping traffic
normally forwarded traffic. from the normally forwarded traffic.
4. Overview of the solution 4. Overview of the Solution
This document defines a two-step convergence initiated by the router This document defines a two-step convergence initiated by the router
detecting a failure and advertising the topological changes in the detecting a failure and advertising the topological change in the
IGP. This introduces a delay between network-wide convergence and IGP. This introduces a delay between network-wide convergence and
the convergence of the local router. the convergence of the local router.
The proposed solution is limited to local link down events in order The solution described in this document is limited to local link-down
to keep the solution simple. events in order to keep the solution simple.
This ordered convergence is similar to the ordered FIB proposed This ordered convergence is similar to the ordered FIB (oFIB)
defined in [RFC6976], but it is limited to only a "one hop" distance. approach defined in [RFC6976], but it is limited to only a "one-hop"
As a consequence, it is more simple and becomes a local-only feature distance. As a consequence, it is more simple and becomes a local-
that does not require interoperability. This benefit comes with the only feature that does not require interoperability. This benefit
limitation of eliminating transient forwarding loops involving the comes with the limitation of eliminating transient forwarding loops
local router only. The proposed mechanism also reuses some concepts involving the local router only. The mechanism also reuses some
described in [I-D.ietf-rtgwg-microloop-analysis]. concepts described in [PLSN].
5. Specification 5. Specification
5.1. Definitions 5.1. Definitions
This document will refer to the following existing IGP timers. These This document refers to the following existing IGP timers. These
timers may be standardized or implemented as a vendor specific local timers may be standardized or implemented as a vendor-specific local
feature. feature.
o LSP_GEN_TIMER: The delay between two consecutives local LSP/LSA o LSP_GEN_TIMER: The delay between the consecutive generation of two
generation. From an operational point of view, this delay is local LSPs/LSAs. From an operational point of view, this delay is
usually tuned to batch multiple local events in one single local usually tuned to batch multiple local events in a single local
LSP/LSA update. In IS-IS, this timer is defined as LSP/LSA update. In IS-IS, this timer is defined as
minimumLSPGenerationInterval in [ISO10589]. In OSPF version 2, minimumLSPGenerationInterval [ISO10589]. In OSPF version 2, this
this timer is defined as MinLSInterval in [RFC2328]. It is often timer is defined as MinLSInterval [RFC2328]. It is often
associated with a vendor specific damping mechanism to slow down associated with a vendor-specific damping mechanism to slow down
reactions by incrementing the timer when multiple consecutive reactions by incrementing the timer when multiple consecutive
events are detected. events are detected.
o SPF_DELAY: The delay between the first IGP event triggering a new o SPF_DELAY: The delay between the first IGP event triggering a new
routing table computation and the start of that routing table routing table computation and the start of that routing table
computation. It is often associated with a damping mechanism to computation. It is often associated with a damping mechanism to
slow down reactions by incrementing the timer when the IGP becomes slow down reactions by incrementing the timer when the IGP becomes
unstable. As an example, [I-D.ietf-rtgwg-backoff-algo] defines a unstable. As an example, [BACKOFF] defines a standard SPF delay
standard SPF (Shortest Path First) delay algorithm. algorithm.
This document introduces the following new timer: This document introduces the following new timer:
o ULOOP_DELAY_DOWN_TIMER: used to slow down the local node o ULOOP_DELAY_DOWN_TIMER: Used to slow down the local node
convergence in case of link down events. convergence in case of link-down events.
5.2. Regular IGP reaction 5.2. Regular IGP Reaction
Upon a change of the status of an adjacency/link, the regular IGP When the status of an adjacency or link changes, the regular IGP
convergence behavior of the router advertising the event involves the convergence behavior of the router advertising the event involves the
following main steps: following main steps:
1. IGP is notified of the Up/Down event. 1. IGP is notified of the up/down event.
2. The IGP processes the notification and postpones the reaction for 2. The IGP processes the notification and postpones the reaction for
LSP_GEN_TIMER msec. LSP_GEN_TIMER ms.
3. Upon LSP_GEN_TIMER expiration, the IGP updates its LSP/LSA and 3. Upon LSP_GEN_TIMER expiration, the IGP updates its LSP/LSA and
floods it. floods it.
4. The SPF computation is scheduled in SPF_DELAY msec. 4. The SPF computation is scheduled in SPF_DELAY ms.
5. Upon SPF_DELAY timer expiration, the SPF is computed, then the 5. Upon SPF_DELAY timer expiration, the SPF is computed, and then
RIB and FIB are updated. the RIB and FIB are updated.
5.3. Local events 5.3. Local Events
The mechanism described in this document assumes that there has been The mechanism described in this document assumes that there has been
a single link failure as seen by the IGP area/level. If this a single link failure as seen by the IGP area/level. If this
assumption is violated (e.g. multiple links or nodes failed), then assumption is violated (e.g., multiple links or nodes failed), then
regular IP convergence must be applied (as described in Section 5.2). regular IP convergence must be applied (as described in Section 5.2).
To determine if the mechanism can be applicable or not, an To determine if the mechanism is applicable or not, an implementation
implementation SHOULD implement logic to correlate the protocol SHOULD implement logic to correlate the protocol messages (LSP/LSA)
messages (LSP/LSA) received during the SPF scheduling period in order received during the SPF scheduling period in order to determine the
to determine the topology changes that occured. This is necessary as topology changes that occurred. This is necessary as multiple
multiple protocol messages may describe the same topology change and protocol messages may describe the same topology change, and a single
a single protocol message may describe multiple topology changes. As protocol message may describe multiple topology changes. As a
a consequence, determining a particular topology change MUST be consequence, determining a particular topology change MUST be
independent of the order of reception of those protocol messages. independent of the order of reception of those protocol messages.
How the logic works is left to the implementation. How the logic works is left to the implementation.
Using this logic, if an implementation determines that the associated Using this logic, if an implementation determines that the associated
topology change is a single local link failure, then the router MAY topology change is a single local link failure, then the router MAY
use the mechanism described in this document, otherwise the regular use the mechanism described in this document; otherwise, the regular
IP convergence MUST be used. IP convergence MUST be used.
Example: In Figure 4, let router B be the computing router when the link B-C
fails. B updates its local LSP/LSA describing the link B-C as down,
+--- E ----+--------+ C does the same, and both start flooding their updated LSPs/LSAs.
| | | During the SPF_DELAY period, B and C learn all the LSPs/LSAs to
A ---- B -------- C ------ D consider. B sees that C is flooding an advertisement that indicates
that a link is down, and B is the other end of that link. B
determines that B and C are describing the same single event. Since
B receives no other changes, B can determine that this is a local
link failure and may decide to activate the mechanism described in
this document.
Figure 4 +--- E ----+--------+
| | |
A ---- B -------- C ------ D
Let router B be the computing router when the link B-C fails. B Figure 4
updates its local LSP/LSA describing the link B->C as down, C does
the same, and both start flooding their updated LSP/LSAs. During the
SPF_DELAY period, B and C learn all the LSPs/LSAs to consider. B
sees that C is flooding an advertisement that indicates that a link
is down, and B is the other end of that link. B determines that B
and C are describing the same single event. Since B receives no
other changes, B can determine that this is a local link failure and
may decide to activate the mechanism described in this document.
5.4. Local delay for link down 5.4. Local Delay for Link-Down Events
Upon an adjacency/link down event, this document introduces a change This document introduces a change in step 5 (see list in Section 5.2)
in step 5 (Section 5.2) in order to delay the local convergence so that, upon an adjacency or link-down event, the local convergence
compared to the network wide convergence. The new step 5 is is delayed compared to the network-wide convergence. The new step 5
described below: is described below:
5. Upon SPF_DELAY timer expiration, the SPF is computed. If the 5. Upon SPF_DELAY timer expiration, the SPF is computed. If the
condition of a single local link-down event has been met, then an condition of a single local link-down event has been met, then an
update of the RIB and the FIB MUST be delayed for update of the RIB and the FIB MUST be delayed for
ULOOP_DELAY_DOWN_TIMER msecs. Otherwise, the RIB and FIB SHOULD ULOOP_DELAY_DOWN_TIMER ms. Otherwise, the RIB and FIB SHOULD be
be updated immediately. updated immediately.
If a new convergence occurs while ULOOP_DELAY_DOWN_TIMER is running, If a new convergence occurs while ULOOP_DELAY_DOWN_TIMER is running,
ULOOP_DELAY_DOWN_TIMER is stopped and the RIB/FIB SHOULD be updated ULOOP_DELAY_DOWN_TIMER is stopped, and the RIB/FIB SHOULD be updated
as part of the new convergence event. as part of the new convergence event.
As a result of this addition, routers local to the failure will As a result of this addition, routers local to the failure will
converge slower than remote routers. Hence it SHOULD only be done converge slower than remote routers. Hence, it SHOULD only be done
for a non-urgent convergence, such as for administrative de- for a non-urgent convergence, such as administrative deactivation
activation (maintenance) or when the traffic is protected by fast- (maintenance) or when the traffic is protected by FRR.
reroute.
6. Applicability 6. Applicability
As previously stated, this mechanism only avoids the forwarding loops As previously stated, this mechanism only avoids the forwarding loops
on the links between the node local to the failure and its neighbors. on the links between the node local to the failure and its neighbors.
Forwarding loops may still occur on other links. Forwarding loops may still occur on other links.
6.1. Applicable case: local loops 6.1. Applicable Case: Local Loops
A ------ B ----- E In Figure 5, let us consider the traffic from G to F. The primary
| / | path is G->D->C->E->F. When the link C-E fails, if C updates its
| / | forwarding entry for F before D, a transient loop occurs. This is
G---D------------C F All the links have a metric of 1 sub-optimal as it breaks C's FRR forwarding even though upstream
routers are still forwarding the traffic to C.
Figure 5 A ------ B ----- E
| / |
| / |
G---D------------C F
Let us consider the traffic from G to F. The primary path is All the links have a metric of 1
G->D->C->E->F. When link C-E fails, if C updates its forwarding
entry for F before D, a transient loop occurs. This is sub-optimal Figure 5
as C has FRR enabled and it breaks the FRR forwarding while all
upstream routers are still forwarding the traffic to itself.
By implementing the mechanism defined in this document on C, when the By implementing the mechanism defined in this document on C, when the
C-E link fails, C delays the update of its forwarding entry to F, in C-E link fails, C delays the update of its forwarding entry to F, in
order to allow some time for D to converge. FRR on C keeps order to allow some time for D to converge. FRR on C keeps
protecting the traffic during this period. When the timer expires on protecting the traffic during this period. When
C, its forwarding entry to F is updated. There is no transient ULOOP_DELAY_DOWN_TIMER expires on C, its forwarding entry to F is
forwarding loop on the link C-D. updated. There is no transient forwarding loop on the link C-D.
6.2. Non applicable case: remote loops 6.2. Non-applicable Case: Remote Loops
A ------ B ----- E --- H In Figure 6, let us consider the traffic from G to K. The primary
| | path is G->D->C->F->J->K. When the C-F link fails, if C updates its
| | forwarding entry to K before D, a transient loop occurs between C and
G---D--------C ------F --- J ---- K D.
All the links have a metric of 1 except BE=15 A ------ B ----- E --- H
| |
| |
G---D--------C ------F --- J ---- K
Figure 6 All the links have a metric of 1 except B-E=15
Let us consider the traffic from G to K. The primary path is Figure 6
G->D->C->F->J->K. When the C-F link fails, if C updates its
forwarding entry to K before D, a transient loop occurs between C and
D.
By implementing the mechanism defined in this document on C, when the By implementing the mechanism defined in this document on C, when the
link C-F fails, C delays the update of its forwarding entry to K, link C-F fails, C delays the update of its forwarding entry to K,
allowing time for D to converge. When the timer expires on C, its allowing time for D to converge. When ULOOP_DELAY_DOWN_TIMER expires
forwarding entry to F is updated. There is no transient forwarding on C, its forwarding entry to F is updated. There is no transient
loop between C and D. However, a transient forwarding loop may still forwarding loop between C and D. However, a transient forwarding
occur between D and A. In this scenario, this mechanism is not loop may still occur between D and A. In this scenario, this
enough to address all the possible forwarding loops. However, it mechanism is not enough to address all the possible forwarding loops.
does not create additional traffic loss. Besides, in some cases However, it does not create additional traffic loss. Besides, in
-such as when the nodes update their FIB in the following order C, A, some cases -- such as when the nodes update their FIB in the order C,
D, for example because the router A is quicker than D to converge- A, D because the router A is quicker than D to converge -- the
the mechanism may still avoid the forwarding loop that would have mechanism may still avoid the forwarding loop that would have
otherwise occurred. otherwise occurred.
7. Simulations 7. Simulations
Simulations have been run on multiple service provider topologies. Simulations have been run on multiple service-provider topologies.
We evaluated the efficiency of the mechanism on eight different
service-provider topologies (different network size and design).
Table 2 displays the gain for each topology.
+----------+------+ +----------+------+
| Topology | Gain | | Topology | Gain |
+----------+------+ +----------+------+
| T1 | 71% | | T1 | 71% |
| T2 | 81% | | T2 | 81% |
| T3 | 62% | | T3 | 62% |
| T4 | 50% | | T4 | 50% |
| T5 | 70% | | T5 | 70% |
| T6 | 70% | | T6 | 70% |
| T7 | 59% | | T7 | 59% |
| T8 | 77% | | T8 | 77% |
+----------+------+ +----------+------+
Table 2 - Number of Repair/Dst that may loop Table 2
We evaluated the efficiency of the mechanism on eight different We evaluated the gain as follows:
service provider topologies (different network size, design). The
benefit is displayed in the table above. The benefit is evaluated as
follows:
o We consider a tuple (link A-B, destination D, PLR S, backup o We considered a tuple (link A-B, destination D, PLR S, backup
nexthop N) as a loop if upon link A-B failure, the flow from a next-hop N) as a loop if, upon link A-B failure, the flow from a
router S upstream from A (A could be considered as PLR also) to D router S upstream from A (A could be considered as PLR also) to D
may loop due to convergence time difference between S and one of may loop due to convergence time difference between S and one of
his neighbors N. its neighbors N.
o We evaluate the number of potential loop tuples in normal o We evaluated the number of potential loop tuples in normal
conditions. conditions.
o We evaluate the number of potential loop tuples using the same o We evaluated the number of potential loop tuples using the same
topological input but taking into account that S converges after topological input but taking into account that S converges after
N. N.
o The gain is how many loops (both remote and local) we succeed to o The gain is the relative number of loops (both remote and local)
suppress. we succeed in suppressing.
On topology 1, 71% of the transient forwarding loops created by the For topology 1, implementing the local delay prevented 71% of the
failure of any link are prevented by implementing the local delay. transient forwarding loops created by the failure of any link. The
The analysis shows that all local loops are prevented and only remote analysis shows that all local loops are prevented and only remote
loops remain. loops remain.
8. Deployment considerations 8. Deployment Considerations
Transient forwarding loops have the following drawbacks: Transient forwarding loops have the following drawbacks:
o They limit FRR efficiency: even if FRR is activated within 50msec, o They limit FRR efficiency. Even if FRR is activated within 50 ms,
as soon as PLR has converged, the traffic may be affected by a as soon as the PLR has converged, the traffic may be affected by a
transient loop. transient loop.
o They may impact traffic not directly affected by the failure (due o They may impact traffic not directly affected by the failure (due
to link congestion). to link congestion).
This local delay proposal is a transient forwarding loop avoidance The local delay mechanism is a transient forwarding loop avoidance
mechanism (like OFIB). Even if it only addresses local transient mechanism (like oFIB). Even if it only addresses local transient
loops, the efficiency versus complexity comparison of the mechanism loops, the efficiency versus complexity comparison of the mechanism
makes it a good solution. It is also incrementally deployable with makes it a good solution. It is also incrementally deployable with
incremental benefits, which makes it an attractive option both for incremental benefits, which makes it an attractive option for both
vendors to implement and service providers to deploy. Delaying the vendors to implement and service providers to deploy. Delaying the
convergence time is not an issue if we consider that the traffic is convergence time is not an issue if we consider that the traffic is
protected during the convergence. protected during the convergence.
The ULOOP_DELAY_DOWN_TIMER value should be set according to the The ULOOP_DELAY_DOWN_TIMER value should be set according to the
maximum IGP convergence time observed in the network (usually maximum IGP convergence time observed in the network (usually
observed in the slowest node). observed in the slowest node).
The proposed mechanism is limited to link down events. When a link This mechanism is limited to link-down events. When a link goes
goes down, it eventually goes back up. As a consequence, with the down, it eventually goes back up. As a consequence, with this
proposed mechanism deployed, only the link down event will be mechanism deployed, only the link-down event will be protected
protected against transient forwarding loops while the link up event against transient forwarding loops while the link-up event will not.
will not. If the operator wants to limit the impact of the transient If the operator wants to limit the impact of transient forwarding
forwarding loops during the link up event, it should take care of loops during the link-up event, it should make sure to use specific
using specific procedures to bring the link back online. As procedures to bring the link back online. As examples, the operator
examples, the operator can decide to put back the link online out of can decide to put the link back online outside of business hours, or
business hours or it can use some incremental metric changes to it can use some incremental metric changes to prevent loops (as
prevent loops (as proposed in [RFC5715]). proposed in [RFC5715]).
9. Examples 9. Examples
We will consider the following figure for the associated examples : We consider the following figure for the examples in this section:
D D
1 | F----X 1 | F----X
| 1 | | 1 |
A ------ B A ------ B
| | | |
10 | | 5 10 | | 5
| | | |
E--------C E--------C
| 1 | 1
1 | 1 |
S S
Figure 7 Figure 7
The network above is considered to have a convergence time about 1 The network above is considered to have a convergence time of about 1
second, so ULOOP_DELAY_DOWN_TIMER will be adjusted to this value. We second, so ULOOP_DELAY_DOWN_TIMER will be adjusted to this value. We
also consider that FRR is running on each node. also consider that FRR is running on each node.
9.1. Local link down 9.1. Local Link-Down Event
The table 3 describes the events and associated timing that happen on Table 3 describes the events and their timing on routers C and E when
router C and E when link B-C goes down. It is based on a theoretical the link B-C goes down. It is based on a theoretical sequence of
sequence of event that should only been read as an example. As C events that should only been read as an example. As C detects a
detects a single local event corresponding to a link down (its LSP + single local event corresponding to a link-down event (its LSP + LSP
LSP from B received), it applies the local delay down behavior and no from B received), it applies the local delay down behavior, and no
microloop is formed. micro-loop is formed.
+-----------+-------------+------------------+----------------------+ +------------+---------+---------------------+----------------------+
| Network | Time | Router C events | Router E events | | Network | Time | Router C Events | Router E Events |
| condition | | | | | Condition | | | |
+-----------+-------------+------------------+----------------------+ +------------+---------+---------------------+----------------------+
| S->D | | | | | S->D | | | |
| Traffic | | | | | Traffic OK | | | |
| OK | | | | | | | | |
| | | | | | S->D | t0 | Link B-C fails | Link B-C fails |
| S->D | t0 | Link B-C fails | Link B-C fails | | Traffic | | | |
| Traffic | | | | | lost | | | |
| lost | | | | | | | | |
| | | | | | | t0+20 | C detects the | |
| | t0+20msec | C detects the | | | | ms | failure | |
| | | failure | | | | | | |
| | | | | | S->D | t0+40 | C activates FRR | |
| S->D | t0+40msec | C activates FRR | | | Traffic OK | ms | | |
| Traffic | | | | | | | | |
| OK | | | | | | t0+50 | C updates its local | |
| | | | | | | ms | LSP/LSA | |
| | t0+50msec | C updates its | | | | | | |
| | | local LSP/LSA | | | | t0+53 | C floods its local | |
| | | | | | | ms | updated LSP/LSA | |
| | t0+60msec | C schedules SPF | | | | | | |
| | | (100ms) | | | | t0+60 | C schedules SPF | |
| | | | | | | ms | (100 ms) | |
| | t0+67msec | C receives | | | | | | |
| | | LSP/LSA from B | | | | t0+67 | C receives LSP/LSA | |
| | | | | | | ms | from B and floods | |
| | t0+70msec | C floods its | | | | | it | |
| | | local updated | | | | | | |
| | | LSP/LSA | | | | t0+87 | | E receives LSP/LSA |
| | | | | | | ms | | from C and floods it |
| | t0+87msec | | E receives LSP/LSA | | | | | |
| | | | from C and schedules | | | t0+90 | | E schedules SPF (100 |
| | | | SPF (100ms) | | | ms | | ms) |
| | | | | | | | | |
| | t0+117msec | | E floods LSP/LSA | | | t0+161 | C computes SPF | |
| | | | from C | | | ms | | |
| | | | | | | | | |
| | t0+160msec | C computes SPF | | | | t0+165 | C delays its | |
| | | | | | | ms | RIB/FIB update (1 | |
| | t0+165msec | C delays its | | | | | sec) | |
| | | RIB/FIB update | | | | | | |
| | | (1 sec) | | | | t0+193 | | E computes SPF |
| | | | | | | ms | | |
| | t0+193msec | | E computes SPF | | | | | |
| | | | | | | t0+199 | | E starts updating |
| | t0+199msec | | E starts updating | | | ms | | its RIB/FIB |
| | | | its RIB/FIB | | | | | |
| | | | | | | t0+443 | | E updates its |
| | t0+443msec | | E updates its | | | ms | | RIB/FIB for D |
| | | | RIB/FIB for D | | | | | |
| | | | | | | t0+470 | | E convergence ends |
| | t0+470msec | | E convergence ends | | | ms | | |
| | | | | | | | | |
| | t0+1165msec | C starts | | | | t0+1165 | C starts updating | |
| | | updating its | | | | ms | its RIB/FIB | |
| | | RIB/FIB | | | | | | |
| | | | | | | t0+1255 | C updates its | |
| | t0+1255msec | C updates its | | | | ms | RIB/FIB for D | |
| | | RIB/FIB for D | | | | | | |
| | | | | | | t0+1340 | C convergence ends | |
| | t0+1340msec | C convergence | | | | ms | | |
| | | ends | | +------------+---------+---------------------+----------------------+
+-----------+-------------+------------------+----------------------+
Table 3 - Route computation event time scale Table 3
Similarly, upon B-C link down event, if LSP/LSA from B is received Similarly, upon B-C link-down event, if LSP/LSA from B is received
before C detects the link failure, C will apply the route update before C detects the link failure, C will apply the route update
delay if the local detection is part of the same SPF run. The table delay if the local detection is part of the same SPF run. Table 4
4 describes the associated theoretical sequence of events. It should describes the associated theoretical sequence of events. It should
only been read as an example. only been read as an example.
+-----------+-------------+------------------+----------------------+ +------------+---------+---------------------+----------------------+
| Network | Time | Router C events | Router E events | | Network | Time | Router C Events | Router E Events |
| condition | | | | | Condition | | | |
+-----------+-------------+------------------+----------------------+ +------------+---------+---------------------+----------------------+
| S->D | | | | | S->D | | | |
| Traffic | | | | | Traffic OK | | | |
| OK | | | | | | | | |
| | | | | | S->D | t0 | Link B-C fails | Link B-C fails |
| S->D | t0 | Link B-C fails | Link B-C fails | | Traffic | | | |
| Traffic | | | | | lost | | | |
| lost | | | | | | | | |
| | | | | | | t0+32 | C receives LSP/LSA | |
| | t0+32msec | C receives | | | | ms | from B and floods | |
| | | LSP/LSA from B | | | | | it | |
| | | | | | | | | |
| | t0+33msec | C schedules SPF | | | | t0+33 | C schedules SPF | |
| | | (100ms) | | | | ms | (100 ms) | |
| | | | | | | | | |
| | t0+50msec | C detects the | | | | t0+50 | C detects the | |
| | | failure | | | | ms | failure | |
| | | | | | | | | |
| S->D | t0+55msec | C activates FRR | | | S->D | t0+55 | C activates FRR | |
| Traffic | | | | | Traffic OK | ms | | |
| OK | | | | | | | | |
| | | | | | | t0+55 | C updates its local | |
| | t0+55msec | C updates its | | | | ms | LSP/LSA | |
| | | local LSP/LSA | | | | | | |
| | | | | | | t0+70 | C floods its local | |
| | t0+70msec | C floods its | | | | ms | updated LSP/LSA | |
| | | local updated | | | | | | |
| | | LSP/LSA | | | | t0+87 | | E receives LSP/LSA |
| | | | | | | ms | | from C and floods it |
| | t0+87msec | | E receives LSP/LSA | | | | | |
| | | | from C and schedules | | | t0+90 | | E schedules SPF (100 |
| | | | SPF (100ms) | | | ms | | ms) |
| | | | | | | | | |
| | t0+117msec | | E floods LSP/LSA | | | t0+135 | C computes SPF | |
| | | | from C | | | ms | | |
| | | | | | | | | |
| | t0+160msec | C computes SPF | | | | t0+140 | C delays its | |
| | | | | | | ms | RIB/FIB update (1 | |
| | t0+165msec | C delays its | | | | | sec) | |
| | | RIB/FIB update | | | | | | |
| | | (1 sec) | | | | t0+193 | | E computes SPF |
| | | | | | | ms | | |
| | t0+193msec | | E computes SPF | | | | | |
| | | | | | | t0+199 | | E starts updating |
| | t0+199msec | | E starts updating | | | ms | | its RIB/FIB |
| | | | its RIB/FIB | | | | | |
| | | | | | | t0+443 | | E updates its |
| | t0+443msec | | E updates its | | | ms | | RIB/FIB for D |
| | | | RIB/FIB for D | | | | | |
| | | | | | | t0+470 | | E convergence ends |
| | t0+470msec | | E convergence ends | | | ms | | |
| | | | | | | | | |
| | t0+1165msec | C starts | | | | t0+1145 | C starts updating | |
| | | updating its | | | | ms | its RIB/FIB | |
| | | RIB/FIB | | | | | | |
| | | | | | | t0+1255 | C updates its | |
| | t0+1255msec | C updates its | | | | ms | RIB/FIB for D | |
| | | RIB/FIB for D | | | | | | |
| | | | | | | t0+1340 | C convergence ends | |
| | t0+1340msec | C convergence | | | | ms | | |
| | | ends | | +------------+---------+---------------------+----------------------+
+-----------+-------------+------------------+----------------------+
Table 4 - Route computation event time scale Table 4
9.2. Local and remote event 9.2. Local and Remote Event
The table 5 describes the events and associated timing that happen on Table 5 describes the events and their timing on router C and E when
router C and E when link B-C goes down, in addition F-X link will the link B-C goes down and when the link F-X fails in the same time
fail in the same time window. C will not apply the local delay window. C will not apply the local delay because a non-local
because a non local topology change is also received. The table 5 is topology change is also received. Table 5 is based on a theoretical
based on a theoretical sequence of event that should only been read sequence of events that should only been read as an example.
as an example.
+-----------+------------+-----------------+------------------------+ +-----------+--------+-------------------+--------------------------+
| Network | Time | Router C events | Router E events | | Network | Time | Router C Events | Router E Events |
| condition | | | | | Condition | | | |
+-----------+------------+-----------------+------------------------+ +-----------+--------+-------------------+--------------------------+
| S->D | | | | | S->D | | | |
| Traffic | | | | | Traffic | | | |
| OK | | | | | OK | | | |
| | | | | | | | | |
| S->D | t0 | Link B-C fails | Link B-C fails | | S->D | t0 | Link B-C fails | Link B-C fails |
| Traffic | | | | | Traffic | | | |
| lost | | | | | lost | | | |
| | | | | | | | | |
| | t0+20msec | C detects the | | | | t0+20 | C detects the | |
| | | failure | | | | ms | failure | |
| | | | | | | | | |
| | t0+36msec | Link F-X fails | Link F-X fails | | | t0+36 | Link F-X fails | Link F-X fails |
| | | | | | | ms | | |
| S->D | t0+40msec | C activates FRR | | | | | | |
| Traffic | | | | | S->D | t0+40 | C activates FRR | |
| OK | | | | | Traffic | ms | | |
| | | | | | OK | | | |
| | t0+50msec | C updates its | | | | | | |
| | | local LSP/LSA | | | | t0+50 | C updates its | |
| | | | | | | ms | local LSP/LSA | |
| | t0+54msec | C receives | | | | | | |
| | | LSP/LSA from F | | | | t0+54 | C receives | |
| | | and floods it | | | | ms | LSP/LSA from F | |
| | | | | | | | and floods it | |
| | t0+60msec | C schedules SPF | | | | | | |
| | | (100ms) | | | | t0+60 | C schedules SPF | |
| | | | | | | ms | (100 ms) | |
| | t0+67msec | C receives | | | | | | |
| | | LSP/LSA from B | | | | t0+67 | C receives | |
| | | | | | | ms | LSP/LSA from B | |
| | t0+69msec | | E receives LSP/LSA | | | | and floods it | |
| | | | from F, floods it and | | | | | |
| | | | schedules SPF (100ms) | | | t0+69 | | E receives LSP/LSA from |
| | | | | | | ms | | F, floods it and |
| | t0+70msec | C floods its | | | | | | schedules SPF (100 ms) |
| | | local updated | | | | | | |
| | | LSP/LSA | | | | t0+70 | C floods its | |
| | | | | | | ms | local updated | |
| | t0+87msec | | E receives LSP/LSA | | | | LSP/LSA | |
| | | | from C | | | | | |
| | | | | | | t0+87 | | E receives LSP/LSA from |
| | t0+117msec | | E floods LSP/LSA from | | | ms | | C |
| | | | C | | | | | |
| | | | | | | t0+117 | | E floods LSP/LSA from C |
| | t0+160msec | C computes SPF | | | | ms | | |
| | | | | | | | | |
| | t0+165msec | C starts | | | | t0+160 | C computes SPF | |
| | | updating its | | | | ms | | |
| | | RIB/FIB (NO | | | | | | |
| | | DELAY) | | | | t0+165 | C starts updating | |
| | | | | | | ms | its RIB/FIB (NO | |
| | t0+170msec | | E computes SPF | | | | DELAY) | |
| | | | | | | | | |
| | t0+173msec | | E starts updating its | | | t0+170 | | E computes SPF |
| | | | RIB/FIB | | | ms | | |
| | | | | | | | | |
| S->D | t0+365msec | C updates its | | | | t0+173 | | E starts updating its |
| Traffic | | RIB/FIB for D | | | | ms | | RIB/FIB |
| lost | | | | | | | | |
| | | | | | S->D | t0+365 | C updates its | |
| S->D | t0+443msec | | E updates its RIB/FIB | | Traffic | ms | RIB/FIB for D | |
| Traffic | | | for D | | lost | | | |
| OK | | | | | | | | |
| | | | | | S->D | t0+443 | | E updates its RIB/FIB |
| | t0+450msec | C convergence | | | Traffic | ms | | for D |
| | | ends | | | OK | | | |
| | | | | | | | | |
| | t0+470msec | | E convergence ends | | | t0+450 | C convergence | |
| | | | | | | ms | ends | |
+-----------+------------+-----------------+------------------------+ | | | | |
| | t0+470 | | E convergence ends |
| | ms | | |
| | | | |
+-----------+--------+-------------------+--------------------------+
Table 5 - Route computation event time scale Table 5
9.3. Aborting local delay 9.3. Aborting Local Delay
The table 6 describes the events and associated timing that happen on Table 6 describes the events and their timing on routers C and E when
router C and E when link B-C goes down. In addition, we consider the link B-C goes down. In addition, we consider what happens when
what happens when F-X link fails during local delay of the FIB the F-X link fails during local delay of the FIB update. C will
update. C will first apply the local delay, but when the new event first apply the local delay, but when the new event happens, it will
happens, it will fall back to the standard convergence mechanism fall back to the standard convergence mechanism without further
without further delaying route insertion. In this example, we delaying route insertion. In this example, we consider a
consider a ULOOP_DELAY_DOWN_TIMER configured to 2 seconds. The table ULOOP_DELAY_DOWN_TIMER configured to 2 seconds. Table 6 is based on
6 is based on a theoretical sequence of event that should only been a theoretical sequence of events that should only been read as an
read as an example. example.
+-----------+------------+-------------------+----------------------+ +------------+--------+----------------------+----------------------+
| Network | Time | Router C events | Router E events | | Network | Time | Router C Events | Router E Events |
| condition | | | | | Condition | | | |
+-----------+------------+-------------------+----------------------+ +------------+--------+----------------------+----------------------+
| S->D | | | | | S->D | | | |
| Traffic | | | | | Traffic OK | | | |
| OK | | | | | | | | |
| | | | | | S->D | t0 | Link B-C fails | Link B-C fails |
| S->D | t0 | Link B-C fails | Link B-C fails | | Traffic | | | |
| Traffic | | | | | lost | | | |
| lost | | | | | | | | |
| | | | | | | t0+20 | C detects the | |
| | t0+20msec | C detects the | | | | ms | failure | |
| | | failure | | | | | | |
| | | | | | S->D | t0+40 | C activates FRR | |
| S->D | t0+40msec | C activates FRR | | | Traffic OK | ms | | |
| Traffic | | | | | | | | |
| OK | | | | | | t0+50 | C updates its local | |
| | | | | | | ms | LSP/LSA | |
| | t0+50msec | C updates its | | | | | | |
| | | local LSP/LSA | | | | t0+55 | C floods its local | |
| | | | | | | ms | updated LSP/LSA | |
| | t0+60msec | C schedules SPF | | | | | | |
| | | (100ms) | | | | t0+57 | C schedules SPF (100 | |
| | | | | | | ms | ms) | |
| | t0+67msec | C receives | | | | | | |
| | | LSP/LSA from B | | | | t0+67 | C receives LSP/LSA | |
| | | | | | | ms | from B and floods it | |
| | t0+70msec | C floods its | | | | | | |
| | | local updated | | | | t0+87 | | E receives LSP/LSA |
| | | LSP/LSA | | | | ms | | from C and floods it |
| | | | | | | | | |
| | t0+87msec | | E receives LSP/LSA | | | t0+90 | | E schedules SPF (100 |
| | | | from C and schedules | | | ms | | ms) |
| | | | SPF (100ms) | | | | | |
| | | | | | | t0+160 | C computes SPF | |
| | t0+117msec | | E floods LSP/LSA | | | ms | | |
| | | | from C | | | | | |
| | | | | | | t0+165 | C delays its RIB/FIB | |
| | t0+160msec | C computes SPF | | | | ms | update (2 sec) | |
| | | | | | | | | |
| | t0+165msec | C delays its | | | | t0+193 | | E computes SPF |
| | | RIB/FIB update (2 | | | | ms | | |
| | | sec) | | | | | | |
| | | | | | | t0+199 | | E starts updating |
| | t0+193msec | | E computes SPF | | | ms | | its RIB/FIB |
| | | | | | | | | |
| | t0+199msec | | E starts updating | | | t0+254 | Link F-X fails | Link F-X fails |
| | | | its RIB/FIB | | | ms | | |
| | | | | | | | | |
| | t0+254msec | Link F-X fails | Link F-X fails | | | t0+300 | C receives LSP/LSA | |
| | | | | | | ms | from F and floods it | |
| | t0+300msec | C receives | | | | | | |
| | | LSP/LSA from F | | | | t0+303 | C schedules SPF (200 | |
| | | and floods it | | | | ms | ms) | |
| | | | | | | | | |
| | t0+303msec | C schedules SPF | | | | t0+312 | E receives LSP/LSA | |
| | | (200ms) | | | | ms | from F and floods it | |
| | | | | | | | | |
| | t0+312msec | E receives | | | | t0+313 | E schedules SPF (200 | |
| | | LSP/LSA from F | | | | ms | ms) | |
| | | and floods it | | | | | | |
| | | | | | | t0+502 | C computes SPF | |
| | t0+313msec | E schedules SPF | | | | ms | | |
| | | (200ms) | | | | | | |
| | | | | | | t0+505 | C starts updating | |
| | t0+502msec | C computes SPF | | | | ms | its RIB/FIB (NO | |
| | | | | | | | DELAY) | |
| | t0+505msec | C starts updating | | | | | | |
| | | its RIB/FIB (NO | | | | t0+514 | | E computes SPF |
| | | DELAY) | | | | ms | | |
| | | | | | | | | |
| | t0+514msec | | E computes SPF | | | t0+519 | | E starts updating |
| | | | | | | ms | | its RIB/FIB |
| | t0+519msec | | E starts updating | | | | | |
| | | | its RIB/FIB | | S->D | t0+659 | C updates its | |
| | | | | | Traffic | ms | RIB/FIB for D | |
| S->D | t0+659msec | C updates its | | | lost | | | |
| Traffic | | RIB/FIB for D | | | | | | |
| lost | | | | | S->D | t0+778 | | E updates its |
| | | | | | Traffic OK | ms | | RIB/FIB for D |
| S->D | t0+778msec | | E updates its | | | | | |
| Traffic | | | RIB/FIB for D | | | t0+781 | C convergence ends | |
| OK | | | | | | ms | | |
| | | | | | | | | |
| | t0+781msec | C convergence | | | | t0+810 | | E convergence ends |
| | | ends | | | | ms | | |
| | | | | +------------+--------+----------------------+----------------------+
| | t0+810msec | | E convergence ends |
+-----------+------------+-------------------+----------------------+
Table 6 - Route computation event time scale Table 6
10. Comparison with other solutions 10. Comparison with Other Solutions
As stated in Section 4, the proposed solution reuses some concepts As stated in Section 4, the local delay solution reuses some concepts
already introduced by other IETF proposals but tries to find a already introduced by other IETF proposals but tries to find a trade-
tradeoff between efficiency and simplicity. This section tries to off between efficiency and simplicity. This section tries to compare
compare behaviors of the solutions. behaviors of the solutions.
10.1. PLSN 10.1. PLSN
PLSN ([I-D.ietf-rtgwg-microloop-analysis]) describes a mechanism PLSN [PLSN] describes a mechanism where each node in the network
where each node in the network tries to avoid transient forwarding tries to avoid transient forwarding loops upon a topology change by
loops upon a topology change by always keeping traffic on a loop-free always keeping traffic on a loop-free path for a defined duration
path for a defined duration (locked path to a safe neighbor). The (locked path to a safe neighbor). The locked path may be the new
locked path may be the new primary nexthop, another neighbor, or the primary next hop, another neighbor, or the old primary next hop
old primary nexthop depending how the safety condition is satisfied. depending on how the safety condition is satisfied.
PLSN does not solve all transient forwarding loops (see PLSN does not solve all transient forwarding loops (see Section 4 of
[I-D.ietf-rtgwg-microloop-analysis] Section 4 for more details). [PLSN] for more details).
Our solution reuses some concept of PLSN but in a more simple The solution defined in this document reuses some concepts of PLSN
fashion: but in a more simple fashion:
o PLSN has three different behaviors: keep using old nexthop, use o PLSN has three different behaviors: (1) keep using the old next
new primary nexthop if it is safe, or use another safe nexthop, hop, (2) use the new primary next hop if it is safe, or (3) use
while the proposed solution only has one: keep using the current another safe next hop. The local delay solution, however, only
nexthop (old primary, or already activated FRR path). has one: keep using the current next hop (i.e., the old primary
next hop or an already-activated FRR path).
o PLSN may cause some damage while using a safe nexthop which is not o PLSN may cause some damage while using a safe next hop that is not
the new primary nexthop in case the new safe nexthop does not the new primary next hop if the new safe next hop does not provide
provide enough bandwidth (see [RFC7916]). This solution may not enough bandwidth (see [RFC7916]). The solution defined in this
experience this issue as the service provider may have control on document may not experience this issue as the service provider may
the FRR path being used preventing network congestion. have control on the FRR path being used, preventing network
congestion.
o PLSN applies to all nodes in a network (remote or local changes), o PLSN applies to all nodes in a network (remote or local changes),
while the proposed mechanism applies only on the nodes connected while the mechanism defined in this document applies only to the
to the topology change. nodes connected to the topology change.
10.2. OFIB 10.2. oFIB
OFIB ([RFC6976]) describes a mechanism where the convergence of the oFIB [RFC6976] describes a mechanism where the convergence of the
network upon a topology change is ordered in order to prevent network upon a topology change is ordered in order to prevent
transient forwarding loops. Each router in the network must deduce transient forwarding loops. Each router in the network deduces the
the failure type from the LSA/LSP received and computes/applies a failure type from the LSA/LSP received and computes/applies a
specific FIB update timer based on the failure type and its rank in specific FIB update timer based on the failure type and its rank in
the network considering the failure point as root. the network, considering the failure point as root.
This mechanism allows to solve all the transient forwarding loop in a The oFIB mechanism solves all the transient forwarding loops in a
network at the price of introducing complexity in the convergence network at the price of introducing complexity in the convergence
process that may require a strong monitoring by the service provider. process that may require careful monitoring by the service provider.
Our solution reuses the OFIB concept but limits it to the first hop
that experiences the topology change. As demonstrated, the mechanism
proposed in this document allows to solve all the local transient
forwarding loops that represents an high percentage of all the loops.
Moreover limiting the mechanism to one hop allows to keep the
network-wide convergence behavior.
11. Implementation Status
At this time, there are three different implementations of this
mechanism.
o Implementation 1:
* Organization: Cisco
* Implementation name: Local Microloop Protection
* Operating system: IOS-XE
* Level of maturity: production release
* Coverage: all the specification is implemented
* Protocols supported: ISIS and OSPF
* Implementation experience: tested in lab and works as expected
* Comment: the feature gives the ability to choose to apply the
delay to FRR protected entry only
* Report last update: 10-11-2017
o Implementation 2:
* Organization: Cisco
* Implementation name: Local Microloop Protection
* Operating system: IOS-XR
* Level of maturity: deployed
* Coverage: all the specification is implemented
* Protocols supported: ISIS and OSPF
* Implementation experience: deployed and works as expected
* Comment: the feature gives the ability to choose to apply the
delay to FRR protected entry only
* Report last update: 10-11-2017
o Implementation 3:
* Organization: Juniper Networks
* Implementation name: Microloop avoidance when IS-IS link fails
* Operating system: JUNOS
* Level of maturity: deployed (hidden command)
* Coverage: all the specification is implemented
* Protocols supported: ISIS only
* Implementation experience: deployed and works as expected The solution defined in this document reuses the oFIB concept but
limits it to the first hop that experiences the topology change. As
demonstrated, the mechanism defined in this document allows all the
local transient forwarding loops to be solved; these represent a high
percentage of all the loops. Moreover, limiting to one hop allows
network-wide convergence behavior to be kept.
* Comment: the feature applies to all the ISIS routes 11. IANA Considerations
* Report last update: 10-11-2017 This document has no IANA actions.
12. Security Considerations 12. Security Considerations
This document does not introduce any change in term of IGP security. This document does not introduce any change in terms of IGP security.
The operation is internal to the router. The local delay does not The operation is internal to the router. The local delay does not
increase the number of attack vectors as an attacker could only increase the number of attack vectors as an attacker could only
trigger this mechanism if he already has be ability to disable or trigger this mechanism if it already has the ability to disable or
enable an IGP link. The local delay does not increase the negative enable an IGP link. The local delay does not increase the negative
consequences. If an attacker has the ability to disable or enable an consequences. If an attacker has the ability to disable or enable an
IGP link, it can already harm the network by creating instability and IGP link, it can already harm the network by creating instability and
harm the traffic by creating forwarding packet loss and forwarding harm the traffic by creating forwarding packet loss and forwarding
loss for the traffic crossing that link. loss for the traffic crossing that link.
13. Acknowledgements 13. References
We would like to thanks the authors of [RFC6976] for introducing the
concept of ordered convergence: Mike Shand, Stewart Bryant, Stefano
Previdi, and Olivier Bonaventure.
14. IANA Considerations
This document has no actions for IANA.
15. References
15.1. Normative References 13.1. Normative References
[ISO10589] [ISO10589] International Organization for Standardization,
"Intermediate System to Intermediate System intra-domain "Information technology -- Telecommunications and
routeing information exchange protocol for use in information exchange between systems -- Intermediate
conjunction with the protocol for providing the System to Intermediate System intra-domain routeing
connectionless-mode network service (ISO 8473)", information exchange protocol for use in conjunction with
ISO 10589, 2002. the protocol for providing the connectionless-mode network
service (ISO 8473)", ISO/IEC 10589:2002, Second Edition,
November 2002.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998, DOI 10.17487/RFC2328, April 1998,
<https://www.rfc-editor.org/info/rfc2328>. <https://www.rfc-editor.org/info/rfc2328>.
15.2. Informative References [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[I-D.ietf-rtgwg-backoff-algo] 13.2. Informative References
Decraene, B., Litkowski, S., Gredler, H., Lindem, A.,
Francois, P., and C. Bowers, "SPF Back-off algorithm for
link state IGPs", draft-ietf-rtgwg-backoff-algo-06 (work
in progress), October 2017.
[I-D.ietf-rtgwg-microloop-analysis] [BACKOFF] Decraene, B., Litkowski, S., Gredler, H., Lindem, A.,
Zinin, A., "Analysis and Minimization of Microloops in Francois, P., and C. Bowers, "SPF Back-off Delay algorithm
Link-state Routing Protocols", draft-ietf-rtgwg-microloop- for link state IGPs", Work in Progress, draft-ietf-rtgwg-
analysis-01 (work in progress), October 2005. backoff-algo-10, March 2018.
[PLSN] Zinin, A., "Analysis and Minimization of Microloops in
Link-state Routing Protocols", Work in Progress,
draft-ietf-rtgwg-microloop-analysis-01, October 2005.
[RFC3906] Shen, N. and H. Smit, "Calculating Interior Gateway [RFC3906] Shen, N. and H. Smit, "Calculating Interior Gateway
Protocol (IGP) Routes Over Traffic Engineering Tunnels", Protocol (IGP) Routes Over Traffic Engineering Tunnels",
RFC 3906, DOI 10.17487/RFC3906, October 2004, RFC 3906, DOI 10.17487/RFC3906, October 2004,
<https://www.rfc-editor.org/info/rfc3906>. <https://www.rfc-editor.org/info/rfc3906>.
[RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free
Convergence", RFC 5715, DOI 10.17487/RFC5715, January Convergence", RFC 5715, DOI 10.17487/RFC5715, January
2010, <https://www.rfc-editor.org/info/rfc5715>. 2010, <https://www.rfc-editor.org/info/rfc5715>.
skipping to change at page 27, line 16 skipping to change at page 26, line 16
Francois, P., and O. Bonaventure, "Framework for Loop-Free Francois, P., and O. Bonaventure, "Framework for Loop-Free
Convergence Using the Ordered Forwarding Information Base Convergence Using the Ordered Forwarding Information Base
(oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July (oFIB) Approach", RFC 6976, DOI 10.17487/RFC6976, July
2013, <https://www.rfc-editor.org/info/rfc6976>. 2013, <https://www.rfc-editor.org/info/rfc6976>.
[RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K., [RFC7916] Litkowski, S., Ed., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational Management of Horneffer, M., and P. Sarkar, "Operational Management of
Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916, Loop-Free Alternates", RFC 7916, DOI 10.17487/RFC7916,
July 2016, <https://www.rfc-editor.org/info/rfc7916>. July 2016, <https://www.rfc-editor.org/info/rfc7916>.
Acknowledgements
We would like to thank the authors of [RFC6976] for introducing the
concept of ordered convergence: Mike Shand, Stewart Bryant, Stefano
Previdi, and Olivier Bonaventure.
Authors' Addresses Authors' Addresses
Stephane Litkowski Stephane Litkowski
Orange Orange
Email: stephane.litkowski@orange.com Email: stephane.litkowski@orange.com
Bruno Decraene Bruno Decraene
Orange Orange
Email: bruno.decraene@orange.com Email: bruno.decraene@orange.com
Clarence Filsfils Clarence Filsfils
Cisco Systems Cisco Systems
Email: cfilsfil@cisco.com Email: cfilsfil@cisco.com
Pierre Francois Pierre Francois
Individual Individual Contributor
Email: pfrpfr@gmail.com Email: pfrpfr@gmail.com
 End of changes. 149 change blocks. 
844 lines changed or deleted 782 lines changed or added

This html diff was produced by rfcdiff 1.46. The latest version is available from http://tools.ietf.org/tools/rfcdiff/