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

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