draft-ietf-rtgwg-ordered-fib-07.txt   draft-ietf-rtgwg-ordered-fib-08.txt 
Network Working Group M. Shand Network Working Group M. Shand
Internet-Draft Individual Contributor Internet-Draft Individual Contributor
Intended status: Informational S. Bryant Intended status: Informational S. Bryant
Expires: March 11, 2013 S. Previdi Expires: July 8, 2013 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
September 7, 2012 January 4, 2013
Loop-free convergence using oFIB Framework for Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-07 draft-ietf-rtgwg-ordered-fib-08
Abstract Abstract
This document describes a mechanism for use in conjunction with link This document describes the framework of a mechanism for use in
state routing protocols which prevents the transient loops which conjunction with link state routing protocols which prevents the
would otherwise occur during topology changes. It does this by transient loops which would otherwise occur during topology changes.
correctly sequencing the forwarding information base (FIB) updates on It does this by correctly sequencing the forwarding information base
the routers. (FIB) updates on the routers.
This mechanism can be used in the case of non-urgent link or node This mechanism can be used in the case of non-urgent link or node
shutdowns and restarts or link metric changes. It can also be used shutdowns and restarts or link metric changes. It can also be used
in conjunction with a fast re-route mechanism which converts a sudden in conjunction with a fast re-route mechanism which converts a sudden
link or node failure into a non-urgent topology change. This is link or node failure into a non-urgent topology change. This is
possible where a complete repair path is provided for all affected possible where a complete repair path is provided for all affected
destinations. 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 real network topologies and costs, and
pathological convergence behaviour. pathological convergence behaviour. However mechanism described in
this document are purely illustrative of the general approach and do
not constitute a protocol specification. The document represents a
snapshot of the work of the Routing Area Working Group at the time of
publication and is published as a document of record. Further work
is needed before implementation or deployment.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on March 11, 2013. This Internet-Draft will expire on July 8, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2012 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. Conventions used in the document . . . . . . . . . . . . . . . 4 1. The Purpose of this Document . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. The required FIB update order . . . . . . . . . . . . . . . . 5 3. The required FIB update order . . . . . . . . . . . . . . . . 6
3.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 5 3.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 6
3.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 5 3.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 6
3.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 6 3.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 7
3.2. Multi-link events . . . . . . . . . . . . . . . . . . . . 7 3.2. Multi-link events . . . . . . . . . . . . . . . . . . . . 7
3.2.1. Router Down events . . . . . . . . . . . . . . . . . . 7 3.2.1. Router Down events . . . . . . . . . . . . . . . . . . 7
3.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 7 3.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 8
3.2.3. Linecard Failure/Restoration Events . . . . . . . . . 7 3.2.3. Linecard Failure/Restoration Events . . . . . . . . . 8
4. Applying ordered FIB updates . . . . . . . . . . . . . . . . . 8 4. Applying ordered FIB updates . . . . . . . . . . . . . . . . . 8
4.1. Deducing the topology change . . . . . . . . . . . . . . . 8 4.1. Deducing the topology change . . . . . . . . . . . . . . . 8
4.2. Deciding if ordered FIB updates applies . . . . . . . . . 8 4.2. Deciding if ordered FIB updates applies . . . . . . . . . 9
5. Computation of the ordering . . . . . . . . . . . . . . . . . 9 5. Computation of the ordering . . . . . . . . . . . . . . . . . 9
5.1. Link or Router Down or Metric Increase . . . . . . . . . . 9 5.1. Link or Router Down or Metric Increase . . . . . . . . . . 10
5.2. Link or Router Up or Metric Decrease . . . . . . . . . . . 10 5.2. Link or Router Up or Metric Decrease . . . . . . . . . . . 10
6. Acceleration of Ordered Convergence . . . . . . . . . . . . . 10 6. Acceleration of Ordered Convergence . . . . . . . . . . . . . 11
6.1. Construction of the waiting list and notification list . . 11 6.1. Construction of the waiting list and notification list . . 11
6.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 11 6.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 11
6.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 11 6.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 12
6.2. Format of Completion Messages . . . . . . . . . . . . . . 11 6.2. Format of Completion Messages . . . . . . . . . . . . . . 12
7. Fall back to Conventional Convergence . . . . . . . . . . . . 12 7. Fall back to Conventional Convergence . . . . . . . . . . . . 12
8. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 12 8. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 13
8.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 12 8.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 13
8.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 13 8.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 13
8.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 14 8.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 14
8.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 15 8.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 15
8.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 15 8.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 16
9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16 9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16
10. Security considerations . . . . . . . . . . . . . . . . . . . 16 10. Security considerations . . . . . . . . . . . . . . . . . . . 16
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17
12. Informative References . . . . . . . . . . . . . . . . . . . . 16 12. Informative References . . . . . . . . . . . . . . . . . . . . 17
Appendix A. Mechanisms for Safely Abandoning Loop-Free Appendix A. Mechanisms for Safely Abandoning Loop-Free
Convergence (AAH) . . . . . . . . . . . . . . . . . . 17 Convergence (AAH) . . . . . . . . . . . . . . . . . . 18
A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 17 A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 18
A.2. Hold-down timer only . . . . . . . . . . . . . . . . . . . 17 A.2. Hold-down timer only . . . . . . . . . . . . . . . . . . . 18
A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 18 A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 19
A.3.1. Per Router State Machine . . . . . . . . . . . . . . . 19 A.3.1. Per Router State Machine . . . . . . . . . . . . . . . 19
A.3.2. Per Neighbor State Machine . . . . . . . . . . . . . . 21 A.3.2. Per Neighbor State Machine . . . . . . . . . . . . . . 21
Appendix B. Synchronisation of Loop Free Timer Values . . . . . . 22 Appendix B. Synchronisation of Loop Free Timer Values . . . . . . 23
B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 22 B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 23
B.2. Required Properties . . . . . . . . . . . . . . . . . . . 22 B.2. Required Properties . . . . . . . . . . . . . . . . . . . 23
B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 23 B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 24
B.4. Security Considerations . . . . . . . . . . . . . . . . . 24 B.4. Security Considerations . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
1. Conventions used in the document 1. The Purpose of this Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", This document describes the framework of a mechanism for use in
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this conjunction with link state routing protocols which prevents the
document are to be interpreted as described in RFC2119 [RFC2119]. transient loops which would otherwise occur during topology changes.
It does this by correctly sequencing the forwarding information base
(FIB) updates on the routers.
At the time of publication there is no demand to deploy this
technology, however in view of the subtleties involved in the design
of loop-free convergence routing protocol extensions the Routing Area
Working Group considered it desirable to publish this document to
place on record the design consideration of the ordered FIB
(oFIB)approach.
The mechanisms presented in this document are purely illustrative of
the general approach and do not constitute a protocol specification.
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.
Additional work is needed to specify the necessary routing protocol
extensions necessary to support this IPFRR method before
implementation or deployment.
2. Introduction 2. Introduction
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 base (FIB) to take into to modify their forwarding information base (FIB) 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
skipping to change at page 5, line 8 skipping to change at page 5, line 24
| | | |
| | | |
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.
The goal of this document is to define a mechanism which sequences [RFC5715] provides an introduction to a number of loop-free
convergence methods and readers unfamiliar with this technology are
recommended to read before studying this document in detail.
The goal of this document is to describe a mechanism which 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 re-route
mechanism [RFC5714] [RFC4090]. The mechanisms that are used in the mechanism (FRR) [RFC5714] [RFC4090]. The mechanisms that are used in
failure case are exactly the same as those used for managed changes. the failure case are exactly the same as those used for managed
For simplicity this document makes no further distinction between changes. For simplicity this document makes no further distinction
managed and unplanned changes. between managed and unplanned changes.
It is assumed in the description that follows that all routers in the
routing domain are oFIB capable. This can be verified in an
operation network by the routers reporting oFIB capability using the
IGP in use. Where non-oFIB capable routers exist in the network,
normal convergence would be used. The operation of 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 real network topologies and costs and
pathological convergence behaviour. A variant of the technology pathological convergence behaviour. A variant of the technology
described here has been experimentally deployed in a production described here has been experimentally deployed in a production
network. network.
3. The required FIB update order 3. 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
skipping to change at page 5, line 43 skipping to change at page 6, line 21
3.1. Single Link Events 3.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 3.1.1. Link Down / Metric Increase
First consider the non-urgent failure of a link or the increase of a First consider the non-urgent failure of a link or the increase of a
link metric. In this case, a router R MUST NOT update its FIB until link metric. In this case, a router R must not update its FIB until
all other routers that send traffic via R and the affected link have all other routers that send traffic via R and the affected link have
first updated their FIBs. 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 change 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
skipping to change at page 6, line 43 skipping to change at page 7, line 20
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 3.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 change 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
skipping to change at page 7, line 22 skipping to change at page 7, line 47
The following sections describe the required ordering for single The following sections describe the required ordering for single
events which may be manifest as multiple link events. For example, events which may be 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 the 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 4.1.
3.2.1. Router Down events 3.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 shut-down 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 3.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 this ordering is respected [refs.PFOB07]. if this ordering is respected [refs.PFOB07].
3.2.3. Linecard Failure/Restoration Events 3.2.3. Linecard Failure/Restoration Events
The failure of a line card involves the failure of a set of links all 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 of which have a single node in common, i.e. the parent router. The
skipping to change at page 9, line 7 skipping to change at page 9, line 31
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 reverse connectivity check treated as a link event. Note that the reverse connectivity check
means that only the first failure event, or second up event have an means that only the first failure event, or second up event have an
effect on the FIB. effect on the FIB.
If an event is received within the hold down period which does NOT If an event is received within the hold down period which 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 7).
The sudden failure of a link or a set of links that are not protected Network reconvergence under ordered FIB takes longer than the normal
using a FRR mechanism must be processed using the conventional mode reconvergence process. Where the failure is protected by an FRR
of operation. mechanism, this additional delay in convergence causes no packet
loss. When the sudden failure of a link or a set of links that are
not protected using a FRR mechanism occurs this must be processed
using the conventional (faster) mode of operation to minimise packet
loss during re-convergence.
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 refer 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 refer to link up events and metric
decrease events. decrease events.
skipping to change at page 12, line 20 skipping to change at page 12, line 45
Old Metric Old Metric
New Metric New Metric
7. Fall back to Conventional Convergence 7. Fall back 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 fall back mechanisms are
described in Appendix A. The state machine defined in the body of described in Appendix A. This mechanism is referred to as
"Abandoning All Hope (AAH). The state machine defined in the body of
this document does not make any assumption about which fall back this document does not make any assumption about which fall back
mechanism will be used. mechanism will be used.
8. oFIB state machine 8. oFIB state machine
This section describes a model of an oFIB state machine which an
implementation must be capable of interworking with.
An oFIB capable router maintains an oFIB state value which can be one An oFIB capable router maintains an oFIB state value which can be 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. 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.
skipping to change at page 15, line 20 skipping to change at page 15, line 49
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 8.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 LSP collected when in OFIB_HOLDING_DOWN mechanism w.r.t. the set of Link State Packets (LSP) collected when
or OFIB_HOLDING_UP state. 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
skipping to change at page 16, line 24 skipping to change at page 17, line 7
such considerations will be called out in protocol specific documents such considerations will be called out in protocol specific documents
defining the modification to any routing protocol that is to be defining the modification to any routing protocol that is to be
enhanced to support loop-free convergence using ordered FIB. enhanced to support loop-free convergence using ordered FIB.
10. Security considerations 10. 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.
11. Acknowledgments 11. 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.
12. Informative References 12. Informative References
[ISO10589] [ISO10589]
International Organization for Standardization, International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain "Intermediate system to Intermediate system intra-domain
routeing 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/ connectionless-mode Network Service (ISO 8473)", ISO/
IEC 10589:2002, Second Edition, Nov 2002. IEC 10589:2002, Second Edition, Nov 2002.
[refs.PFOB07] [refs.PFOB07]
P. Francois and O. Bonaventure, "Avoiding transient loops P. Francois and O. Bonaventure, "Avoiding transient loops
during IGP convergence in IP Networks", in IEEE/ACM during IGP convergence in IP Networks", in IEEE/ACM
Transactions on Networking, Transactions on Networking,
http://inl.info.ucl.ac.be/publications, December 2007. http://inl.info.ucl.ac.be/publications, December 2007.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[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, Extensions to RSVP-TE for LSP Tunnels", RFC 4090,
May 2005. May 2005.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
RFC 5714, January 2010. RFC 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
skipping to change at page 20, line 11 skipping to change at page 20, line 43
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 Convergence
(CC) state and executes the CC mechanism to re-converge the topology. (CC) state and executes the CC mechanism to re-converge the topology.
When the CC process has completed on the router, the router re-enters When the CC process has completed on the router, the router re-enters
the Quiescent state. 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 "goto TX-AAH" command to
all per neighbour state machines which causes each per-neighbour all per neighbour state machines which causes each per-neighbour
state machine to signal this state change to its neighbour. state machine to signal this state change to its neighbour.
Alternatively, if this router receives an AAH message from any of its Alternatively, if this router receives an AAH message from any of its
skipping to change at page 21, line 51 skipping to change at page 22, line 44
In states IDLE, any AAH ACK message received is ignored. In states 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 an
AAH message to the neighbour and restarts the timer. (The timer AAH message to the neighbour 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 the state
machine is deleted. Deletion of the per neighbor state machine 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 neighbour 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 neighbour it creates a new instance of the
per-neighbour state machine in state Idle. The consequent generation per-neighbour 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, which will if necessary result in
the new per-neighbour state machine receiving a "goto TX-AAH" command the new per-neighbour state machine receiving a "goto 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. Synchronisation of Loop Free Timer Values
The Appendix provided the reader with access to the design The Appendix provided the reader with access to the design
considerations originally described in considerations originally described in
[I-D.atlas-bryant-shand-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 to make the necessary changes to the FIB. The timer is used by and to make the necessary changes to the FIB. The timer is used by
the routers to know when it is safe to transition between the loop- the routers to know when it is safe to transition between the loop-
free convergence states. The time taken by a router to complete each free convergence states. The time taken by a router to complete each
phase of the loop-free transition will be dependent on the size of 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. It can
therefore be expected that the optimum delay will need to be tuned therefore be expected that the optimum delay will need to be tuned
from time to time as the network evolves. Manual configuration of from time to time as the network evolves. Manual configuration of
the timer is fraught for two reasons, firstly it is always difficult the timer is fraught for two reasons, firstly it is always difficult
to ensure that the correct value is installed in all of the routers, to ensure that the correct value is installed in all of the routers,
and secondly, if any change is introduced into the network that and secondly, if any change is introduced into the network that
results in a need to change the timer, for example due to a change in results in a need to change the timer, for example due to a change in
hardware or software version, then all of the routers need to be 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. It is therefore 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 in
introduced to the network that requires a higher delay than is introduced to the network that requires a higher delay than is
currently in use. currently in use.
o When the router that had the longest delay requirements is removed o When the router that had the longest delay requirements is removed
skipping to change at page 23, line 42 skipping to change at page 24, line 31
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 largest 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
If an abnormally large timer value is proposed by a router, the there 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 is a danger that the loop-free convergence process will take an
excessive time. If during that time the routing protocol signals the excessive time. If during that time the routing protocol signals the
need for another transition, the loop-free transition will be need for another transition, the loop-free transition will be
abandoned and the default best case (traditional) convergence abandoned and the default best case (traditional) convergence
mechanism used. mechanism used.
 End of changes. 42 change blocks. 
72 lines changed or deleted 111 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/