draft-ietf-rtgwg-ordered-fib-06.txt   draft-ietf-rtgwg-ordered-fib-07.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: December 12, 2012 S. Previdi Expires: March 11, 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
June 10, 2012 September 7, 2012
Loop-free convergence using oFIB Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-06 draft-ietf-rtgwg-ordered-fib-07
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 forwarding information base (FIB) updates on
the routers.
This mechanism can be used in the case of non-urgent link or node This mechanism can be used in the case of non-urgent link or node
shutdowns and restarts or link metric changes. It can also be used shutdowns and restarts or link metric changes. It can also be used
in conjunction with a fast re-route mechanism which converts a sudden in conjunction with a fast re-route mechanism which converts a sudden
link or node failure into a non-urgent topology change. This is link or node failure into a non-urgent topology change. This is
possible where a complete repair path is provided for all affected possible where a complete repair path is provided for all affected
destinations. destinations.
After a non-urgent topology change, each router computes a rank that After a non-urgent topology change, each router computes a rank that
defines the time at which it can safely update its FIB. A method for defines the time at which it can safely update its FIB. A method for
skipping to change at page 2, line 10 skipping to change at page 2, line 11
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 December 12, 2012. This Internet-Draft will expire on March 11, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2012 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
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 . . . . . . . . . . . . . . . . . . . 18 A.2. Hold-down timer only . . . . . . . . . . . . . . . . . . . 17
A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 19 A.3. AAH messages . . . . . . . . . . . . . . . . . . . . . . . 18
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
A.4. Synchronisation of Loop Free Timer Values . . . . . . . . 23 Appendix B. Synchronisation of Loop Free Timer Values . . . . . . 22
A.4.1. Introduction . . . . . . . . . . . . . . . . . . . . . 23 B.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 22
A.4.2. Required Properties . . . . . . . . . . . . . . . . . 23 B.2. Required Properties . . . . . . . . . . . . . . . . . . . 22
A.4.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . 24 B.3. Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 23
A.4.4. Security Considerations . . . . . . . . . . . . . . . 25 B.4. Security Considerations . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24
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 [RFC2119]. document are to be interpreted as described in RFC2119 [RFC2119].
2. Introduction 2. Introduction
With link-state protocols, such as IS-IS [ISO10589] and OSPF With link-state protocols, such as IS-IS [ISO10589] and OSPF
[RFC2328], each time the network topology changes, some routers need [RFC2328], each time the network topology changes, some routers need
to modify their Forwarding Information Base (FIB) to take into to modify their forwarding information base (FIB) to take into
account the new topology. Each topology change causes a convergence account the new topology. Each topology change causes a convergence
phase. During this phase, routers may transiently have inconsistent phase. During this phase, routers may transiently have inconsistent
FIBs, which may lead to packet loops and losses, even if the FIBs, which may lead to packet loops and losses, even if the
reachability of the destinations is not compromised after the reachability of the destinations is not compromised after the
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 10, line 4 skipping to change at page 10, line 4
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.
[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
[I-D.bonaventure-isis-ordered].
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
Old Metric Old Metric
New Metric New Metric
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 Appendix A.4. using Appendix B.
An oFIB capable router maintains a timer, rank_timer. An oFIB capable router maintains a timer, rank_timer.
8.1. OFIB_STABLE 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 [I-D.atlas-bryant-shand-lf-timers]and defining the modification to any routing protocol that is to be
[I-D.bonaventure-isis-ordered] enhanced to support loop-free convergence using ordered FIB.
10. Security considerations 10. Security considerations
This document requires only minor modifications to existing routing This document requires only minor modifications to existing routing
protocols and therefore does not add significant additional security protocols and therefore does not add significant additional security
risks. However a full security analysis would need to be provided risks. However a full security analysis would need to be provided
within the protocol specific specifications proposed for deployment. within the protocol specific specifications proposed for deployment.
11. Acknowledgments 11. Acknowledgments
skipping to change at page 16, line 40 skipping to change at page 16, line 40
12. Informative References 12. Informative References
[ISO10589] [ISO10589]
International Organization for Standardization, International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain "Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in routeing 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.
[I-D.bonaventure-isis-ordered]
Bonaventure, O., "ISIS extensions for ordered FIB
updates", draft-bonaventure-isis-ordered-00 (work in
progress), February 2006.
[refs.PFOB07] [refs.PFOB07]
P. Francois and O. Bonaventure, "Avoiding transient loops P. Francois and O. Bonaventure, "Avoiding transient loops
during IGP convergence in IP Networks", in IEEE/ACM during IGP convergence in IP Networks", in IEEE/ACM
Transactions on Networking, Transactions on Networking,
http://inl.info.ucl.ac.be/publications, December 2007. http://inl.info.ucl.ac.be/publications, December 2007.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
skipping to change at page 23, line 8 skipping to change at page 22, line 16
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.
A.4. Synchronisation of Loop Free Timer Values Appendix B. Synchronisation of Loop Free Timer Values
The Appendix provided the reader with access to the design The Appendix provided the reader with access to the design
considerations originally described in considerations originally described in
[I-D.atlas-bryant-shand-lf-timers] since this draft is unlikely to be [I-D.atlas-bryant-shand-lf-timers].
published as an RFC in the near future.
A.4.1. Introduction B.1. Introduction
Most of the loop-free convergence mechanisms [RFC5715] require one or Most of the loop-free convergence mechanisms [RFC5715] require one or
more convergence delay timers that MUST have a duration that is more convergence delay timers that MUST have a duration that is
consistent throughout the routing domain. This time is the worst consistent throughout the routing domain. This time is the worst
case time that any router will take to calculate the new topology, case time that any router will take to calculate the new topology,
and to make the necessary changes to the FIB. The timer is used by and to make the necessary changes to the FIB. The timer is used by
the routers to know when it is safe to transition between the loop- the routers to know when it is safe to transition between the loop-
free convergence states. The time taken by a router to complete each free convergence states. The time taken by a router to complete each
phase of the loop-free transition will be dependent on the size of phase of the loop-free transition will be dependent on the size of
the network and the design and implementation of the router. It can the network and the design and implementation of the router. It can
skipping to change at page 23, line 37 skipping to change at page 22, line 44
from time to time as the network evolves. Manual configuration of from time to time as the network evolves. Manual configuration of
the timer is fraught for two reasons, firstly it is always difficult the timer is fraught for two reasons, firstly it is always difficult
to ensure that the correct value is installed in all of the routers, to ensure that the correct value is installed in all of the routers,
and secondly, if any change is introduced into the network that and secondly, if any change is introduced into the network that
results in a need to change the timer, for example due to a change in results in a need to change the timer, for example due to a change in
hardware or software version, then all of the routers need to be hardware or software version, then all of the routers need to be
reconfigured to use the new timer value. It is therefore desirable reconfigured to use the new timer value. It is therefore desirable
that a means be provided by which the convergence delay timer can be that a means be provided by which the convergence delay timer can be
automatically synchronized throughout the network. automatically synchronized throughout the network.
A.4.2. Required Properties B.2. Required Properties
The timer synchronization mechanism MUST have the following The timer synchronization mechanism MUST have the following
properties: properties:
o The convergence delay time must be consistent amongst all routers o The convergence delay time must be consistent amongst all routers
that are converging on the new topology. that are converging on the new topology.
o The convergence delay time must be the highest delay required by o The convergence delay time must be the highest delay required by
any router in the new topology. any router in the new topology.
o The mechanism must increase the delay when a new router in o The mechanism must increase the delay when a new router in
introduced to the network that requires a higher delay than is introduced to the network that requires a higher delay than is
skipping to change at page 24, line 16 skipping to change at page 23, line 27
timer value that it requires. timer value that it requires.
o A router which is in multiple routing areas, or is running o A router which is in multiple routing areas, or is running
multiple routing protocols may signal a different loop-free multiple routing protocols may signal a different loop-free
convergence delay for each area, and for each protocol. convergence delay for each area, and for each protocol.
How a router determines the time that it needs to execute each How a router determines the time that it needs to execute each
convergence phase is an implementation issue, and outside the scope convergence phase is an implementation issue, and outside the scope
of this specification. However a router that dynamically determines of this specification. However a router that dynamically determines
its proposed timer value must do so in such a way that it does not its proposed timer value must do so in such a way that it does not
cause the synchronized value to continually fluctuate. cause the synchronized value to continually fluctuate.
A.4.3. Mechanism B.3. Mechanism
The following mechanism is proposed. The following mechanism is proposed.
A new information element is introduced into the routing protocol A new information element is introduced into the routing protocol
that specifies the maximum time (in milliseconds) that the router that specifies the maximum time (in milliseconds) that the router
will take to calculate the new topology and to update its FIB as a will take to calculate the new topology and to update its FIB as a
result of any topology change. result of any topology change.
When a topology change occurs, the largest convergence delay time When a topology change occurs, the largest convergence delay time
required by any router in the new topology is used by the loop-free required by any router in the new topology is used by the loop-free
skipping to change at page 25, line 5 skipping to change at page 24, line 11
taken if a timer change (only) message and a topology change message taken if a timer change (only) message and a topology change message
are independently generated during the hold-off time. A suitable are independently generated during the hold-off time. A suitable
action would be to take the same action that would be taken if two action would be to take the same action that would be taken if two
uncorrelated topology changes occurred in the network. uncorrelated topology changes occurred in the network.
All routers that support loop-free convergence MUST advertise a loop- All routers that support loop-free convergence MUST advertise a loop-
free convergence delay time. The loop-free convergence mechanism free convergence delay time. The loop-free convergence mechanism
MUST specify the action to be taken if a router does not advertise a MUST specify the action to be taken if a router does not advertise a
convergence delay time. convergence delay time.
A.4.4. Security Considerations B.4. Security Considerations
If an abnormally large timer value is proposed by a router, the there If an abnormally large timer value is proposed by a router, the there
is a danger that the loop-free convergence process will take an is a danger that the loop-free convergence process will take an
excessive time. If during that time the routing protocol signals the excessive time. If during that time the routing protocol signals the
need for another transition, the loop-free transition will be need for another transition, the loop-free transition will be
abandoned and the default best case (traditional) convergence abandoned and the default best case (traditional) convergence
mechanism used. mechanism used.
It is still undesirable that the routers select a convergence delay It is still undesirable that the routers select a convergence delay
time that has an excessive value. The maximum value that can be time that has an excessive value. The maximum value that can be
 End of changes. 19 change blocks. 
33 lines changed or deleted 25 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/