draft-ietf-rtgwg-ordered-fib-08.txt   draft-ietf-rtgwg-ordered-fib-09.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: July 8, 2013 S. Previdi Expires: August 4, 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
January 4, 2013 January 31, 2013
Framework for Loop-free convergence using oFIB Framework for Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-08 draft-ietf-rtgwg-ordered-fib-09
Abstract Abstract
This document describes the framework of a mechanism for use in This document describes the framework of a mechanism for use in
conjunction with link state routing protocols which prevents the conjunction with link state routing protocols which prevents the
transient loops which would otherwise occur during topology changes. transient loops which would otherwise occur during topology changes.
It does this by correctly sequencing the forwarding information base It does this by correctly sequencing the forwarding information base
(FIB) updates on 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 (management
shutdowns and restarts or link metric changes. It can also be used action) link or node shutdowns and restarts or link metric changes.
in conjunction with a fast re-route mechanism which converts a sudden It can also be used in conjunction with a fast re-route mechanism
link or node failure into a non-urgent topology change. This is which converts a sudden link or node failure into a non-urgent
possible where a complete repair path is provided for all affected topology change. This is possible where a complete repair path is
destinations. provided 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 real network topologies and costs, and
pathological convergence behaviour. However mechanism described in pathological convergence behaviour. However the mechanism described
this document are purely illustrative of the general approach and do in this document are purely illustrative of the general approach and
not constitute a protocol specification. The document represents a do not constitute a protocol specification. The document represents
snapshot of the work of the Routing Area Working Group at the time of a snapshot of the work of the Routing Area Working Group at the time
publication and is published as a document of record. Further work of publication and is published as a document of record. Further
is needed before implementation or deployment. 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 July 8, 2013. This Internet-Draft will expire on August 4, 2013.
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
skipping to change at page 3, line 14 skipping to change at page 3, line 14
Table of Contents Table of Contents
1. The Purpose of this Document . . . . . . . . . . . . . . . . . 4 1. The Purpose of this Document . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. The required FIB update order . . . . . . . . . . . . . . . . 6 3. The required FIB update order . . . . . . . . . . . . . . . . 6
3.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 6 3.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 6
3.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 6 3.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 6
3.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 7 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 . . . . . . . . . . . . . . . . . . 8
3.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 8 3.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 8
3.2.3. Linecard Failure/Restoration Events . . . . . . . . . 8 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 . . . . . . . . . 9 4.2. Deciding if ordered FIB updates applies . . . . . . . . . 9
5. Computation of the ordering . . . . . . . . . . . . . . . . . 9 5. Computation of the ordering . . . . . . . . . . . . . . . . . 10
5.1. Link or Router Down or Metric Increase . . . . . . . . . . 10 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 . . . . . . . . . . . 11
6. Acceleration of Ordered Convergence . . . . . . . . . . . . . 11 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 . . 12
6.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 11 6.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 12
6.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 12 6.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 12
6.2. Format of Completion Messages . . . . . . . . . . . . . . 12 6.2. Format of Completion Messages . . . . . . . . . . . . . . 12
7. Fall back to Conventional Convergence . . . . . . . . . . . . 12 7. Fall back to Conventional Convergence . . . . . . . . . . . . 13
8. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 13 8. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 13
8.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 13 8.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 13
8.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 13 8.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 14
8.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 14 8.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 15
8.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 15 8.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 16
8.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 16 8.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 17
9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16 9. Management Considerations . . . . . . . . . . . . . . . . . . 17
10. Security considerations . . . . . . . . . . . . . . . . . . . 16 10. IANA considerations . . . . . . . . . . . . . . . . . . . . . 17
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 11. Security considerations . . . . . . . . . . . . . . . . . . . 17
12. Informative References . . . . . . . . . . . . . . . . . . . . 17 12. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17
Appendix A. Mechanisms for Safely Abandoning Loop-Free 13. Informative References . . . . . . . . . . . . . . . . . . . . 18
Appendix A. Candidate Methods of Safely Abandoning Loop-Free
Convergence (AAH) . . . . . . . . . . . . . . . . . . 18 Convergence (AAH) . . . . . . . . . . . . . . . . . . 18
A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 18 A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 19
A.2. Hold-down timer only . . . . . . . . . . . . . . . . . . . 18 A.2. Hold-down timer only . . . . . . . . . . . . . . . . . . . 19
A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 19 A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 20
A.3.1. Per Router State Machine . . . . . . . . . . . . . . . 19 A.3.1. Per Router State Machine . . . . . . . . . . . . . . . 20
A.3.2. Per Neighbor State Machine . . . . . . . . . . . . . . 21 A.3.2. Per Neighbor State Machine . . . . . . . . . . . . . . 22
Appendix B. Synchronisation of Loop Free Timer Values . . . . . . 23 Appendix B. Synchronisation of Loop Free Timer Values . . . . . . 24
B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 23 B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 24
B.2. Required Properties . . . . . . . . . . . . . . . . . . . 23 B.2. Required Properties . . . . . . . . . . . . . . . . . . . 24
B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 24 B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 25
B.4. Security Considerations . . . . . . . . . . . . . . . . . 25 B.4. Security Considerations . . . . . . . . . . . . . . . . . 26
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26
1. The Purpose of this Document 1. The Purpose of this Document
This document describes the framework of a mechanism for use in This document describes the framework of a mechanism for use in
conjunction with link state routing protocols which prevents the conjunction with link state routing protocols which prevents the
transient loops which would otherwise occur during topology changes. transient loops which would otherwise occur during topology changes.
It does this by correctly sequencing the forwarding information base It does this by correctly sequencing the forwarding information base
(FIB) updates on the routers. (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
skipping to change at page 4, line 25 skipping to change at page 4, line 25
of loop-free convergence routing protocol extensions the Routing Area of loop-free convergence routing protocol extensions the Routing Area
Working Group considered it desirable to publish this document to Working Group considered it desirable to publish this document to
place on record the design consideration of the ordered FIB place on record the design consideration of the ordered FIB
(oFIB)approach. (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.
The 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 IPFRR method before extensions necessary to support this IP fast re-route (IPFRR) method
implementation or deployment. 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 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.
skipping to change at page 5, line 26 skipping to change at page 5, line 26
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. recommended to read before studying this document in detail. Note
that in common with other loop-free convergence methods, oFIB is only
capable of providing loop free convergence in the presence of a
single failure.
The goal of this document is to describe a mechanism which sequences 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 (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.
skipping to change at page 6, line 20 skipping to change at page 6, line 23
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 (i.e. where an
link metric. In this case, a router R must not update its FIB until operator or a network management system (NMS) shuts down a link
all other routers that send traffic via R and the affected link have thereby removing it from the currently active topology) or the
first updated their FIBs. increase of a link metric by the operator or NMS . In this case, a
router R must not update its FIB until all other routers that send
traffic via R and the affected link have first updated their FIBs.
The following argument shows that this rule ensures the correct order 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
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
skipping to change at page 7, line 21 skipping to change at page 7, line 28
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
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 3.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 be manifest as multiple link events. For example, events which may manifest as multiple link events. For example, the
the failure of a router may be notified to the rest of the network as failure of a router may be notified to the rest of the network as the
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 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
skipping to change at page 8, line 41 skipping to change at page 8, line 49
restoration of a single link, single router or a linecard may be restoration of a single link, single router or a linecard 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 which 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 have a single If all events received within some hold-down period (the time that a
router (R) in common, then it is assumed that the change reflects an router waits to acquire a set of LSPs which should be processed
event (line-card or router change) concerning the common router (R). together) have a single router in common, then it is assumed that the
change reflects an event (line-card or router change) concerning that
router.
In the case of a link change event, the router at the far end of the In the case of a link change event, the router at the far end of the
link is deemed to be the common router (R). link is deemed to be the common router.
All ordering computations are based on treating the common router R All ordering computations are based on treating the common router as
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 4.2. Deciding if ordered FIB updates applies
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 convergence
falls back to the conventional mode of operation (see Section 7). falls back to the conventional mode of operation (see Section 7).
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 which 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 reverse connectivity check treated as a link event. Note that the IGP reverse connectivity
means that only the first failure event, or second up event have an check means that only the first failure event, or second up event
effect on the FIB. have an 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).
Network reconvergence under ordered FIB takes longer than the normal Network reconvergence under ordered FIB takes longer than the normal
reconvergence process. Where the failure is protected by an FRR reconvergence process. Where the failure is protected by an FRR
mechanism, this additional delay in convergence causes no packet mechanism, this additional delay in convergence causes no packet
loss. When the sudden failure of a link or a set of links that are loss. When the sudden failure of a link or a set of links that are
skipping to change at page 9, line 43 skipping to change at page 10, line 4
mechanism, this additional delay in convergence causes no packet mechanism, this additional delay in convergence causes no packet
loss. When the sudden failure of a link or a set of links that are 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 not protected using a FRR mechanism occurs this must be processed
using the conventional (faster) mode of operation to minimise packet using the conventional (faster) mode of operation to minimise packet
loss during re-convergence. 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.
5. Computation of the ordering 5. 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
reverse Shortest Path Tree (rSPT). The rSPT uses the cost towards
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].
5.1. Link or Router Down or Metric Increase 5.1. Link or 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 or an increase of the metric of link X->Y, router R computes the rSPT
reverse Shortest Path Tree (rSPT) in the topology before the failure in the topology before the failure (rSPT_OLD) rooted at Y. This rSPT
(rSPT_OLD) rooted at Y. This rSPT gives the shortest paths to reach Y gives the shortest paths to reach Y before the failure. The branch
before the failure. The branch of the reverse SPT that is below R of the reverse SPT that is below R corresponds to the set of shortest
corresponds to the set of shortest paths to R that are used by the paths to R that are used by the routers that reach Y via R.
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 ECMP, the maximum depth of the ECMP path this branch. In the case of Equal Cost Multi-path (ECMP), the
set is used. maximum 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 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.
skipping to change at page 10, line 51 skipping to change at page 11, line 17
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 3. The rank of R is thus
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 6. 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.
skipping to change at page 11, line 49 skipping to change at page 12, line 16
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 6.1. Construction of the waiting list and notification list
6.1.1. Down events 6.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
neighbors that R uses to reach the failing node or link, and the set neighbours that R uses to reach the failing node or link, and the set
of neighbors that are using R to reach the failing node or link. The of neighbours that are using R to reach the failing node or link.
Notification list of R is equal to the former set and the Waiting The 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 neighbors except those in the Note that R could include all its neighbours except those in the
Waiting list in the Notification list, this has no impact on the Waiting list in the Notification list, this has no impact on the
correctness of the protocol, but would be unnecessarily inefficient. correctness of the protocol, but would be unnecessarily inefficient.
6.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).
skipping to change at page 12, line 35 skipping to change at page 12, line 49
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.
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
skipping to change at page 13, line 30 skipping to change at page 13, line 43
8.1. OFIB_STABLE 8.1. OFIB_STABLE
OFIB_STABLE is the state of a router which is not currently involved OFIB_STABLE is the state of a router which 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 describing an event of the
type link X--Y down or metric increase to be processed using oFIB. type link X--Y down or metric increase to be processed using oFIB.
ACTION : Set state to OFIB_HOLDING_DOWN. Start Hold_down_timer. ACTION :
ofib_current_common_set = {X,Y}. Compute rank with respect to the Set state to OFIB_HOLDING_DOWN.
event, as defined in Section 5. Store Waiting List and Notification Start Hold_down_timer.
List for X--Y obtained from the rank computation. ofib_current_common_set = {X,Y}.
Compute rank with respect to the event, as defined in Section 5.
Store Waiting List and Notification List for X--Y obtained from
the rank computation.
EVENT : Reception of a link-state packet describing an event of the EVENT : Reception of a link-state packet describing an event of the
type link X--Y up or metric decrease which to be processed using type link X--Y up or metric decrease which 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}
skipping to change at page 16, line 35 skipping to change at page 17, line 14
8.5. OFIB_ABANDONED 8.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 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 Hold_down_timer. ACTION : Trigger AAH, reset AAH_Hold_down_timer.
EVENT : Hold_down_timer expires. EVENT : AAH_Hold_down_timer expires.
ACTION : Set state to OFIB_STABLE ACTION : Set state to OFIB_STABLE
9. IANA considerations 9. Management Considerations
A system for recording the dynamics of the convergence process needs
to be deployed in order to post hoc diagnose the re-convergence. The
sensitivity of applications to the any packet re-order introduced by
the delayed convergence process will need to be studied, however both
of these considerations apply to any loop-free convergence method and
are not specific to the ordered FIB method described in this
document.
10. IANA considerations
There are no IANA considerations which arise from this document. Any There are no IANA considerations which arise from this document. Any
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 11. 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. Additional security considerations are noted in Appendix B.4.
11. Acknowledgments 12. 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 13. 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
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/ 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/
http://inl.info.ucl.ac.be/publications, December 2007. 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, 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
Convergence", RFC 5715, January 2010. Convergence", RFC 5715, January 2010.
[I-D.atlas-bryant-shand-lf-timers] [I-D.atlas-bryant-shand-lf-timers]
K, A. and S. Bryant, "Synchronisation of Loop Free Timer K, A. and S. Bryant, "Synchronisation of Loop Free Timer
Values", draft-atlas-bryant-shand-lf-timers-04 (work in Values", draft-atlas-bryant-shand-lf-timers-04 (work in
progress), February 2008. progress), February 2008.
Appendix A. Mechanisms for Safely Abandoning Loop-Free Convergence [I-D.bryant-ipfrr-tunnels]
(AAH) 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
Convergence (AAH)
IPFRR[RFC5714] and loop-free convergence techniques [RFC5715] can IPFRR[RFC5714] and loop-free convergence techniques [RFC5715] can
deal with single topology change events, multiple correlated change deal with single topology change events, multiple correlated change
events, and in some cases even certain uncorrelated events. However, events, and in some cases even certain uncorrelated events. However,
in all cases there are events which cannot be dealt with and the in all cases there are events which cannot be dealt with and the
mechanism needs to quickly revert to normal convergence. This is mechanism needs to quickly revert to normal convergence. This is
known as "Abandoning All Hope" (AAH). 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
skipping to change at page 18, line 31 skipping to change at page 19, line 21
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. These are described below.
A.2. Hold-down timer only A.2. Hold-down timer only
This method uses a hold-down to acquire a set of LSPs which should be The "hold-down timer only" AAH method uses a hold-down to acquire a
processed together. On expiry of the local hold-down timer, the set of LSPs which should be processed together. On expiry of the
router begins processing the batch of LSPs according to the loop free local hold-down timer, the router begins processing the batch of LSPs
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 is complete. In addition, since the timer is started at processing is complete. In addition, since the timer is started at
each router on reception of the first LSP announcing a topology each router on reception of the first LSP announcing a topology
change, the actual starting time is dependant upon the propagation change, the actual starting time is dependant upon the propagation
skipping to change at page 19, line 16 skipping to change at page 20, line 6
(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. 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 previously received, or which are
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 which 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 needs to be synchronised. 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, this method uses a hold-down to Like the simple timer AAH method, the "AAH messages" AAH method uses
acquire a set of LSPs which should be processed together. On expiry a hold-down to acquire a set of LSPs which should be processed
of the local hold-down timer, the router begins processing the batch together. On expiry of the local hold-down timer, the router begins
of LSPs according to the loop free prevention algorithm. This is the processing the batch of LSPs according to the loop free prevention
same behaviour as the hold-down timer only method. However, if any algorithm. This is the same behaviour as the hold-down timer only
router, having started the loop-free convergence process receives an method. However, if any router, having started the loop-free
LSP which would trigger a topology change, it locally abandons the convergence process receives an LSP which would trigger a topology
controlled convergence process, and sends an AAH message to all its change, it locally abandons the controlled convergence process, and
neighbors. This eventually triggers all routers to abandon the sends an AAH message to all its neighbours. This eventually triggers
controlled convergence. The routers remain in AAH state (i.e. all routers to abandon the controlled convergence. The routers
processing topology changes using normal "fast" convergence), until a remain in AAH state (i.e. processing topology changes using normal
period of quiescence has elapsed. The exit from AAH state is "fast" convergence), until a period of quiescence has elapsed. The
synchronized by using a two step process. To achieve the required exit from AAH state is synchronized by using a two step process. To
synchronization, two additional messages are required, AAH and AAH achieve the required synchronization, two additional messages are
ACK. The AAH message is reliably exchanged between neighbours using required, AAH and AAH ACK. The AAH message is reliably exchanged
the AAH ACK message. These could be implemented as a new message between neighbours using the AAH ACK message. These could be
within the routing protocol or carried in existing routing hello implemented as a new message within the routing protocol or carried
messages. Two types of state machines are needed. A per-router AAH in existing routing hello messages. Two types of state machines are
state machine and a per neighbour AAH state machine(PNSM). These are needed. A per-router AAH state machine and a per neighbour AAH state
described below. machine(PNSM). These are described below.
A.3.1. Per Router State Machine A.3.1. Per Router State Machine
Per Router State Table Per Router State Table
+-------------+-----------+---------+--------+------------+----------+ +-------------+-----------+---------+--------+------------+----------+
| 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 | Re-start | 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 |
| (Neighbor's | Start AAH | Start | Start | | Start | |(Neighbour'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] | - | - |
skipping to change at page 21, line 6 skipping to change at page 22, line 6
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
neighbors whilst in any state except AAH, it starts the AAH timer and neighbours whilst in any state except AAH, it starts the AAH timer
enters the AAH state. The per neighbor state machine corresponding and enters the AAH state. The per neighbour state machine
to the neighbor from which the AAH was received executes the RX AAH corresponding to the neighbour from which the AAH was received
action (which causes it to send an AAH ACK), while the remainder are executes the RX AAH action (which causes it to send an AAH ACK),
sent the "goto TX-AAH" command. The result is that the AAH is while the remainder are sent the "goto TX-AAH" command. The result
acknowledged to the neighbor from which it was received and is that the AAH is acknowledged to the neighbour from which it was
propagated to all other neighbors. On entering AAH state, all CC received and propagated to all other neighbours. On entering AAH
timers are expired and normal convergence takes place. state, all CC 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 some
time and the network will behave in the traditional uncontrolled time and the network will behave in the traditional uncontrolled
convergence manner. 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 neighbour state machines to "goto 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 neighbours, it re-enters the AAH state and commands all
other per neighbour state machines to "goto TX-AAH". Note that the other per neighbour state machines to "goto TX-AAH". Note that the
per-neighbor state machine receiving the AAH message will per-neighbour 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-neighbour state machine to "goto 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 state, 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 state Quiescent
and is ready for loop free convergence. and is ready for loop free convergence.
A.3.2. Per Neighbor State Machine A.3.2. Per Neighbor State Machine
Per Neighbor State Table Per Neighbour State Table
+----------------------------+--------------+------------------------+ +----------------------------+--------------+------------------------+
| EVENT | Idle | TX-AAH | | EVENT | Idle | TX-AAH |
+============================+==============+========================+ +============================+==============+========================+
| RX AAH | Send ACK. | Send ACK. | | RX AAH | Send ACK. | Send ACK. |
| | | Cancel timer. | | | | Cancel timer. |
| | [IDLE] | [IDLE] | | | [IDLE] | [IDLE] |
+----------------------------+--------------+------------------------+ +----------------------------+--------------+------------------------+
| RX ACK | ignore | Cancel timer. | | RX ACK | ignore | Cancel timer. |
| | | [IDLE] | | | | [IDLE] |
+----------------------------+--------------+------------------------+ +----------------------------+--------------+------------------------+
| RX "goto TX-AAH" from | Send AAH | ignore | | RX "goto 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 (PN) state machine for There is one instance of the per-neighbour state machine(PNSM) for
each neighbour within the convergence control domain. each neighbour 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 ("goto 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. neighbour 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.
skipping to change at page 22, line 46 skipping to change at page 23, line 46
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 neighbour 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.
skipping to change at page 23, line 27 skipping to change at page 24, line 27
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 Secondly, if any change is introduced into the network that results
results in a need to change the timer, for example due to a change in 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:
 End of changes. 53 change blocks. 
135 lines changed or deleted 169 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/