draft-ietf-rtgwg-ordered-fib-05.txt   draft-ietf-rtgwg-ordered-fib-06.txt 
Network Working Group Pierre Francois Network Working Group M. Shand
Internet-Draft Olivier Bonaventure Internet-Draft Individual Contributor
Intended status: Experimental Universite catholique de Louvain Intended status: Informational S. Bryant
Expires: October 22, 2011 Mike Shand Expires: December 12, 2012 S. Previdi
Stewart Bryant C. Filsfils
Stefano Previdi
Clarence Filsfils
Cisco Systems Cisco Systems
April 20, 2011 P. Francois
Institute IMDEA Networks
O. Bonaventure
Universite catholique de Louvain
June 10, 2012
Loop-free convergence using oFIB Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-05 draft-ietf-rtgwg-ordered-fib-06
Abstract Abstract
This document describes a mechanism for use in conjunction with link This document describes a mechanism for use in conjunction with link
state routing protocols which prevents the transient loops which state routing protocols which prevents the transient loops which
would otherwise occur during topology changes. It does this by would otherwise occur during topology changes. It does this by
correctly sequencing the FIB updates on the routers. correctly sequencing the 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
skipping to change at page 1, line 37 skipping to change at page 1, line 39
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. A variant of the technology pathological convergence behaviour.
described here has been experimentally deployed in a production
network.
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 October 22, 2011. This Internet-Draft will expire on December 12, 2012.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2012 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
skipping to change at page 3, line 42 skipping to change at page 3, line 42
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 . . . . . . . . . . . . . . . . . . . . . . 15
9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16 9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16
10. Security considerations . . . . . . . . . . . . . . . . . . . 16 10. Security considerations . . . . . . . . . . . . . . . . . . . 16
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
12. Informative References . . . . . . . . . . . . . . . . . . . . 16 12. Informative References . . . . . . . . . . . . . . . . . . . . 16
Appendix A. Mechanisms for Safely Abandoning Loop-Free Appendix A. Mechanisms for Safely Abandoning Loop-Free
Convergence (AAH) . . . . . . . . . . . . . . . . . . 17 Convergence (AAH) . . . . . . . . . . . . . . . . . . 17
A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 17 A.1. Possible Solutions . . . . . . . . . . . . . . . . . . . . 17
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
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 A.4. Synchronisation of Loop Free Timer Values . . . . . . . . 23
A.4.1. Introduction . . . . . . . . . . . . . . . . . . . . . 23
A.4.2. Required Properties . . . . . . . . . . . . . . . . . 23
A.4.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . 24
A.4.4. Security Considerations . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
1. Conventions used in the document 1. Conventions used in the document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [4]. document are to be interpreted as described in RFC2119 [RFC2119].
2. Introduction 2. Introduction
With link-state protocols, such as IS-IS [1] and OSPF [5], each time With link-state protocols, such as IS-IS [ISO10589] and OSPF
the network topology changes, some routers need to modify their [RFC2328], each time the network topology changes, some routers need
Forwarding Information Base (FIB) to take into account the new to modify their Forwarding Information Base (FIB) to take into
topology. Each topology change causes a convergence phase. During account the new topology. Each topology change causes a convergence
this phase, routers may transiently have inconsistent FIBs, which may phase. During this phase, routers may transiently have inconsistent
lead to packet loops and losses, even if the reachability of the FIBs, which may lead to packet loops and losses, even if the
destinations is not compromised after the topology change. Packet reachability of the destinations is not compromised after the
losses and transient loops can also occur in the case of a link down topology change. Packet losses and transient loops can also occur in
event implied by a maintenance operation, even if this operation is the case of a link down event implied by a maintenance operation,
predictable and not urgent. When the link state change is a metric even if this operation is predictable and not urgent. When the link
update and when a new link is brought up in the network, there is no state change is a metric update and when a new link is brought up in
direct loss of connectivity, but transient packet loops and loss can the network, there is no direct loss of connectivity, but transient
still occur. packet loops and loss can still occur.
For example, in Figure 1, if the link between X and Y is shut down by For example, in Figure 1, if the link between X and Y is shut down by
an operator, packets destined to X can loop between R and Y when Y an operator, packets destined to X can loop between R and Y when Y
has updated its FIB while R has not yet updated its FIB, and packets has updated its FIB while R has not yet updated its FIB, and packets
destined to Y can loop between X and S if X updates its FIB before S. destined to Y can loop between X and S if X updates its FIB before S.
According to the current behaviour of ISIS and OSPF, this scenario According to the current behaviour of ISIS and OSPF, this scenario
will happen most of the time because X and Y are the first routers to will happen most of the time because X and Y are the first routers to
be aware of the failure, so that they will update their FIBs first. be aware of the failure, so that they will update their FIBs first.
1 1
skipping to change at page 5, line 16 skipping to change at page 5, line 16
failure, not just adjacent to it. failure, not just adjacent to it.
The goal of this document is to define a mechanism which sequences The goal of this document is to define 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 [7] [6]. The mechanisms that are used in the failure case mechanism [RFC5714] [RFC4090]. The mechanisms that are used in the
are exactly the same as those used for managed changes. For failure case are exactly the same as those used for managed changes.
simplicity this document makes no further distinction between managed For simplicity this document makes no further distinction between
and unplanned changes. managed and unplanned changes.
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
updates. A more detailed analysis of the rerouting dynamics and updates. A more detailed analysis of the rerouting dynamics and
correctness proofs of the mechanism can be found in [3]. correctness proofs of the mechanism can be found in [refs.PFOB07].
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
skipping to change at page 7, line 27 skipping to change at page 7, line 27
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 [3]. 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 [3]. 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
ordering to be applied is the same as if it were the failure of the ordering to be applied is the same as if it were the failure of the
parent router. parent router.
In a similar way, the restoration of an entire linecard to service as In a similar way, the restoration of an entire linecard to service as
a single event can be treated as if the parent router were returning a single event can be treated as if the parent router were returning
skipping to change at page 9, line 15 skipping to change at page 9, line 15
Section 7). Section 7).
The sudden failure of a link or a set of links that are not protected The sudden failure of a link or a set of links that are not protected
using a FRR mechanism must be processed using the conventional mode using a FRR mechanism must be processed using the conventional mode
of operation. of operation.
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 :
. 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
. 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.
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
skipping to change at page 10, line 5 skipping to change at page 10, line 5
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
[9]. [I-D.atlas-bryant-shand-lf-timers].
All the routers that use R to reach Y will compute a lower rank than All the routers that use R to reach Y will compute a lower rank than
R, and hence the correct order will be respected. It should be noted R, and hence the correct order will be respected. It should be noted
that only the routers that used Y before the event need to compute that only the routers that used Y before the event need to compute
their rank. their rank.
5.2. Link or Router Up or Metric Decrease 5.2. Link or Router Up or Metric Decrease
In the case of a link or router up event rooted at Y or a link metric In the case of a link or router up event rooted at Y or a link metric
decrease affecting link Y->W, a router R must have a rank that is decrease affecting link Y->W, a router R must have a rank that is
skipping to change at page 11, line 48 skipping to change at page 11, line 48
In a simple implementation the notification list of R is all the In a simple implementation the notification list of R is all the
neighbours of R excluding those in the Waiting list. This may be neighbours of R excluding those in the Waiting list. This may be
further optimized by computing rSPT_new(Y) to determine those routers further optimized by computing rSPT_new(Y) to determine those routers
that are waiting for R to complete. that are waiting for R to complete.
6.2. Format of Completion Messages 6.2. Format of Completion Messages
The format of completion messages and means of their delivery is The format of completion messages and means of their delivery is
routing protocol dependent and is outside the scope of this document. routing protocol dependent and is outside the scope of this document.
An encoding of completion message for IS-IS is proposed in [2]. An encoding of completion message for IS-IS is proposed in
[I-D.bonaventure-isis-ordered].
The following information is required: The following information is required:
. Identity of the sender. o Identity of the sender.
. A list of routing notifications being considered in the o List of routing notifications being considered in the associated
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
. 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. 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
skipping to change at page 12, line 33 skipping to change at page 12, line 33
8. oFIB state machine 8. oFIB state machine
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 [9]. using Appendix A.4.
An oFIB capable router maintains a timer, rank_timer. An oFIB capable router maintains a timer, rank_timer.
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
skipping to change at page 16, line 15 skipping to change at page 16, line 15
ACTION : Trigger AAH, reset Hold_down_timer. ACTION : Trigger AAH, reset Hold_down_timer.
EVENT : Hold_down_timer expires. EVENT : Hold_down_timer expires.
ACTION : Set state to OFIB_STABLE ACTION : Set state to OFIB_STABLE
9. IANA considerations 9. 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
such as [9]and [2] such as [I-D.atlas-bryant-shand-lf-timers]and
[I-D.bonaventure-isis-ordered]
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.
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
[1] International Organization for Standardization, "Intermediate [ISO10589]
system to Intermediate system intra-domain routeing information International Organization for Standardization,
exchange protocol for use in conjunction with the protocol for "Intermediate system to Intermediate system intra-domain
providing the connectionless-mode Network Service (ISO 8473)", routeing information exchange protocol for use in
ISO/IEC 10589:2002, Second Edition, Nov 2002. conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)", ISO/
IEC 10589:2002, Second Edition, Nov 2002.
[2] Bonaventure, O., "ISIS extensions for ordered FIB updates", [I-D.bonaventure-isis-ordered]
draft-bonaventure-isis-ordered-00 (work in progress), Bonaventure, O., "ISIS extensions for ordered FIB
February 2006. updates", draft-bonaventure-isis-ordered-00 (work in
progress), February 2006.
[3] P. Francois and O. Bonaventure, "Avoiding transient loops during [refs.PFOB07]
IGP convergence in IP Networks", in IEEE/ACM Transactions on P. Francois and O. Bonaventure, "Avoiding transient loops
Networking, http://inl.info.ucl.ac.be/publications, during IGP convergence in IP Networks", in IEEE/ACM
December 2007. Transactions on Networking,
http://inl.info.ucl.ac.be/publications, December 2007.
[4] Bradner, S., "Key words for use in RFCs to Indicate Requirement [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[5] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[6] Pan, P., Swallow, G., and A. Atlas, "Fast Reroute Extensions to [RFC4090] Pan, P., Swallow, G., and A. Atlas, "Fast Reroute
RSVP-TE for LSP Tunnels", RFC 4090, May 2005. Extensions to RSVP-TE for LSP Tunnels", RFC 4090,
May 2005.
[7] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 5714, [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
January 2010. RFC 5714, January 2010.
[8] 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.
[9] K, A. and S. Bryant, "Synchronisation of Loop Free Timer [I-D.atlas-bryant-shand-lf-timers]
Values", draft-atlas-bryant-shand-lf-timers-04 (work in K, A. and S. Bryant, "Synchronisation of Loop Free Timer
progress), February 2008. Values", draft-atlas-bryant-shand-lf-timers-04 (work in
progress), February 2008.
Appendix A. Mechanisms for Safely Abandoning Loop-Free Convergence Appendix A. Mechanisms for Safely Abandoning Loop-Free Convergence
(AAH) (AAH)
IPFRR[7] and loop-free convergence techniques [8] can deal with IPFRR[RFC5714] and loop-free convergence techniques [RFC5715] can
single topology change events, multiple correlated change events, and deal with single topology change events, multiple correlated change
in some cases even certain uncorrelated events. However, in all events, and in some cases even certain uncorrelated events. However,
cases there are events which cannot be dealt with and the mechanism in all cases there are events which cannot be dealt with and the
needs to quickly revert to normal convergence. This is known as mechanism needs to quickly revert to normal convergence. This is
"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
between complexity and robustness in the AAH solution-space. between complexity and robustness in the AAH solution-space.
A.1. Possible Solutions A.1. Possible Solutions
Two approaches to this problem have been proposed: Two approaches to this problem have been proposed:
1. Hold-down timer only. 1. Hold-down timer only.
skipping to change at page 22, line 14 skipping to change at page 23, line 8
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.
Authors' Addresses A.4. Synchronisation of Loop Free Timer Values
Pierre Francois The Appendix provided the reader with access to the design
Universite catholique de Louvain considerations originally described in
Place Ste Barbe, 2 [I-D.atlas-bryant-shand-lf-timers] since this draft is unlikely to be
Louvain-la-Neuve 1348 published as an RFC in the near future.
BE
URI: http://inl.info.ucl.ac.be/ A.4.1. Introduction
Olivier Bonaventure Most of the loop-free convergence mechanisms [RFC5715] require one or
Universite catholique de Louvain more convergence delay timers that MUST have a duration that is
Place Ste Barbe, 2 consistent throughout the routing domain. This time is the worst
Louvain-la-Neuve 1348 case time that any router will take to calculate the new topology,
BE 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-
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
the network and the design and implementation of the router. It can
therefore be expected that the optimum delay will need to be tuned
from time to time as the network evolves. Manual configuration of
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,
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
hardware or software version, then all of the routers need to be
reconfigured to use the new timer value. It is therefore desirable
that a means be provided by which the convergence delay timer can be
automatically synchronized throughout the network.
URI: http://inl.info.ucl.ac.be/ A.4.2. Required Properties
The timer synchronization mechanism MUST have the following
properties:
o The convergence delay time must be consistent amongst all routers
that are converging on the new topology.
o The convergence delay time must be the highest delay required by
any router in the new topology.
o The mechanism must increase the delay when a new router in
introduced to the network that requires a higher delay than is
currently in use.
o When the router that had the longest delay requirements is removed
from the topology, the convergence delay timer value must, within
some reasonable time, be reduced to the longest delay required by
the remaining routers.
o It must be possible for a router to change the convergence delay
timer value that it requires.
o A router which is in multiple routing areas, or is running
multiple routing protocols may signal a different loop-free
convergence delay for each area, and for each protocol.
How a router determines the time that it needs to execute each
convergence phase is an implementation issue, and outside the scope
of this specification. However a router that dynamically determines
its proposed timer value must do so in such a way that it does not
cause the synchronized value to continually fluctuate.
A.4.3. Mechanism
The following mechanism is proposed.
A new information element is introduced into the routing protocol
that specifies the maximum time (in milliseconds) that the router
will take to calculate the new topology and to update its FIB as a
result of any topology change.
When a topology change occurs, the largest convergence delay time
required by any router in the new topology is used by the loop-free
convergence mechanism.
If a routing protocol message is issued that changes the convergence
delay timer value, but does not change the topology, the new timer
value MUST be taken into consideration during the next loop-free
transition, but MUST NOT instigate a loop-free transition.
If a routing protocol message is issued that changes the convergence
timer value and changes the topology, a loop-free transition is
instigated and the new timer value is taken into consideration.
The loop-free convergence mechanism should specify the action to be
taken if a timer change (only) message and a topology change message
are independently generated during the hold-off time. A suitable
action would be to take the same action that would be taken if two
uncorrelated topology changes occurred in the network.
All routers that support loop-free convergence MUST advertise a loop-
free convergence delay time. The loop-free convergence mechanism
MUST specify the action to be taken if a router does not advertise a
convergence delay time.
A.4.4. Security Considerations
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
excessive time. If during that time the routing protocol signals the
need for another transition, the loop-free transition will be
abandoned and the default best case (traditional) convergence
mechanism used.
It is still undesirable that the routers select a convergence delay
time that has an excessive value. The maximum value that can be
specified in the LSP/LSA is limited through the use of a 16 bit field
to about 65 seconds. When sufficient implementation experience is
gained, an architectural constant will be specified which sets the
upper limit of the convergence delay timer.
Authors' Addresses
Mike Shand Mike Shand
Cisco Systems Individual Contributor
Green Park, 250, Longwater Avenue,
Reading RG2 6GB
UK
Email: mshand@cisco.com Email: imc.shand@googlemail.com
Stewart Bryant Stewart Bryant
Cisco Systems Cisco Systems
Green Park, 250, Longwater Avenue, Green Park, 250, Longwater Avenue,
Reading RG2 6GB Reading RG2 6GB
UK UK
Email: stbryant@cisco.com Email: stbryant@cisco.com
Stefano Previdi Stefano Previdi
Cisco Systems Cisco Systems
Via Del Serafico 200 Via Del Serafico 200
00142 Roma 00142 Roma
Italy Italy
Email: sprevidi@cisco.com Email: sprevidi@cisco.com
Clarence Filsfils Clarence Filsfils
Cisco Systems Cisco Systems
Brussels, Brussels,
Belgium Belgium
Email: cfilsfil@cisco.com Email: cfilsfil@cisco.com
Pierre Francois
Institute IMDEA Networks
Avda. del Mar Mediterraneo, 22
Leganese 28918
ES
Email: pierre.francois@imdea.org
Olivier Bonaventure
Universite catholique de Louvain
Place Ste Barbe, 2
Louvain-la-Neuve 1348
BE
Email: Olivier.Bonaventure@uclouvain.be
URI: http://inl.info.ucl.ac.be/
 End of changes. 41 change blocks. 
100 lines changed or deleted 199 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/