draft-ietf-rtgwg-ordered-fib-02.txt   draft-ietf-rtgwg-ordered-fib-03.txt 
Network Working Group Pierre Francois Network Working Group Pierre Francois
Internet-Draft Olivier Bonaventure Internet-Draft Olivier Bonaventure
Intended status: Standards Track Universite catholique de Louvain Intended status: Experimental Universite catholique de Louvain
Expires: August 28, 2008 Mike Shand Expires: September 6, 2010 Mike Shand
Stewart Bryant Stewart Bryant
Stefano Previdi Stefano Previdi
Clarence Filsfils
Cisco Systems Cisco Systems
February 25, 2008 March 5, 2010
Loop-free convergence using oFIB Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-02 draft-ietf-rtgwg-ordered-fib-03
Abstract
This draft describes a mechanism for use in conjunction with link
state routing protocols which prevents the transient loops which
would otherwise occur during topology changes. It does this by
correctly sequencing the FIB updates on the routers.
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
in conjunction with a FRR mechanism which converts a sudden link or
node failure into a non-urgent topology change. This is possible
where a complete repair path is provided for all affected
destinations.
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
accelerating this loop-free convergence process by the use of
completion messages is also described.
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any This Internet-Draft is submitted to IETF in full conformance with the
applicable patent or other IPR claims of which he or she is aware provisions of BCP 78 and BCP 79.
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
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."
skipping to change at page 1, line 31 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
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."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 28, 2008. This Internet-Draft will expire on September 6, 2010.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2008). Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
Abstract
This draft describes a mechanism for use in conjunction with link This document is subject to BCP 78 and the IETF Trust's Legal
state routing protocols which prevents the transient loops which Provisions Relating to IETF Documents
would otherwise occur during topology changes. It does this by (http://trustee.ietf.org/license-info) in effect on the date of
correctly sequencing the FIB updates on the routers. publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the BSD License.
This mechanism can be used in the case of non-urgent link or node Table of Contents
shutdowns and restarts or link metric changes. It can also be used
in conjunction with a FRR mechanism which converts a sudden link or
node failure into a non-urgent topology change. This is possible
where a complete repair path is provided for all affected
destinations.
After a non-urgent topology change, each router computes a rank that 1. Conventions used in the document . . . . . . . . . . . . . . . 4
defines the time at which it can safely update its FIB. A method for 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
accelerating this loop-free convergence process by the use of 3. The required FIB update order . . . . . . . . . . . . . . . . 5
completion messages is also described. 3.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 5
3.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 5
3.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 6
3.2. Multi-link events . . . . . . . . . . . . . . . . . . . . 7
3.2.1. Router Down events . . . . . . . . . . . . . . . . . . 7
3.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 7
3.2.3. Linecard Failure/Restoration Events . . . . . . . . . 7
4. Applying ordered FIB updates . . . . . . . . . . . . . . . . . 7
4.1. Deducing the topology change . . . . . . . . . . . . . . . 7
4.2. Deciding if ordered FIB updates applies . . . . . . . . . 8
5. Computation of the ordering . . . . . . . . . . . . . . . . . 9
5.1. Link or Router Down or Metric Increase . . . . . . . . . . 9
5.2. Link or Router Up or Metric Decrease . . . . . . . . . . . 10
6. Acceleration of Ordered Convergence . . . . . . . . . . . . . 10
6.1. Construction of the waiting list and notification list . . 11
6.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 11
6.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 11
6.2. Format of Completion Messages . . . . . . . . . . . . . . 11
7. Fall back to Conventional Convergence . . . . . . . . . . . . 12
8. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 12
8.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 12
8.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 13
8.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 14
8.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 15
8.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 15
9. IANA considerations . . . . . . . . . . . . . . . . . . . . . 16
10. Security considerations . . . . . . . . . . . . . . . . . . . 16
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
12. Informative References . . . . . . . . . . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17
Table of Contents 1. Conventions used in the document
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
2. The required FIB update order . . . . . . . . . . . . . . . . 4 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
2.1. Single Link Events . . . . . . . . . . . . . . . . . . . . 4 document are to be interpreted as described in BCP 14, [4].
2.1.1. Link Down / Metric Increase . . . . . . . . . . . . . 4
2.1.2. Link Up / Metric Decrease . . . . . . . . . . . . . . 5
2.2. Multi-link events . . . . . . . . . . . . . . . . . . . . 5
2.2.1. Router Down events . . . . . . . . . . . . . . . . . . 6
2.2.2. Router Up events . . . . . . . . . . . . . . . . . . . 6
2.2.3. Linecard Failure/Restoration Events . . . . . . . . . 6
3. Applying ordered FIB updates . . . . . . . . . . . . . . . . . 6
3.1. Deducing the topology change . . . . . . . . . . . . . . . 6
3.2. Deciding if ordered FIB updates applies . . . . . . . . . 7
4. Computation of the ordering . . . . . . . . . . . . . . . . . 8
4.1. Link or Router Down or Metric Increase . . . . . . . . . . 8
4.2. Link or Router Up or Metric Decrease . . . . . . . . . . . 8
5. Acceleration of Ordered Convergence . . . . . . . . . . . . . 9
5.1. Construction of the waiting list and notification list . . 9
5.1.1. Down events . . . . . . . . . . . . . . . . . . . . . 10
5.1.2. Up Events . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Format of Completion Messages . . . . . . . . . . . . . . 10
6. Fall back to Conventional Convergence . . . . . . . . . . . . 10
7. oFIB state machine . . . . . . . . . . . . . . . . . . . . . . 11
7.1. OFIB_STABLE . . . . . . . . . . . . . . . . . . . . . . . 11
7.2. OFIB_HOLDING_DOWN . . . . . . . . . . . . . . . . . . . . 12
7.3. OFIB_HOLDING_UP . . . . . . . . . . . . . . . . . . . . . 13
7.4. OFIB_ONGOING . . . . . . . . . . . . . . . . . . . . . . . 14
7.5. OFIB_ABANDONED . . . . . . . . . . . . . . . . . . . . . . 14
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 14
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16
Intellectual Property and Copyright Statements . . . . . . . . . . 17
1. Introduction 2. Introduction
With link-state protocols [1][2], each time the network topology With link-state protocols, such as IS-IS [1] and OSPF [5], each time
changes, some routers need to modify their Forwarding Information the network topology changes, some routers need to modify their
Base (FIB) to take into account the new topology. Each topology Forwarding Information Base (FIB) to take into account the new
change causes a convergence phase. During this phase, routers may topology. Each topology change causes a convergence phase. During
transiently have inconsistent FIBs, which may lead to packet loops this phase, routers may transiently have inconsistent FIBs, which may
and losses, even if the reachability of the destinations is not lead to packet loops and losses, even if the reachability of the
compromised after the topology change. Packet losses and transient destinations is not compromised after the topology change. Packet
loops can also occur in the case of a link down event implied by a losses and transient loops can also occur in the case of a link down
maintenance operation, even if this operation is predictable and not event implied by a maintenance operation, even if this operation is
urgent. When the link state change is a metric update and when a new predictable and not urgent. When the link state change is a metric
link is brought up in the network, there is no direct loss of update and when a new link is brought up in the network, there is no
connectivity, but transient packet loops and loss can still occur. direct loss of connectivity, but transient 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 3, line 50 skipping to change at page 5, line 11
2 2
Figure 1: A simple topology Figure 1: A simple topology
It should be noted that the loops can occur remotely from the It should be noted that the loops can occur remotely from the
failure, not just adjacent to it. failure, not just adjacent to it.
The goal of this draft is to define a mechanism which sequences the The goal of this draft is to define a mechanism which sequences the
router FIB updates to maintain consistency throughout the network. router FIB updates to maintain consistency throughout the network.
By correctly setting the FIB change order no looping or packet loss By correctly setting the FIB change order no looping or packet loss
can occur. As described in [5] this mechanism may be applied to the can occur. This mechanism may be applied to the case of managed
case of managed link-state changes, i.e. link metric change, manual link-state changes, i.e. link metric change, manual link down/up,
link down/up, manual router down/up, and managed state changes of a manual router down/up, and managed state changes of a set of links
set of links attached to one router. It may also be applied to the attached to one router. It may also be applied to the case where one
case where one or more network elements are protected by a fast re- or more network elements are protected by a fast re-route mechanism
route mechanism [3] [8]. The mechanisms that are used in the failure [7] [6]. The mechanisms that are used in the failure case are
case are exactly the same as those used for managed changes. For exactly the same as those used for managed changes. For simplicity
simplicity this draft makes no further distinction between managed this draft makes no further distinction between managed and unplanned
and unplanned changes. changes.
2. 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 [7]. correctness proofs of the mechanism can be found in [3].
2.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 draft then builds on this to demonstrate that described first. The draft then builds on this to demonstrate that
the same principles can be applied to more complex scenarios such as the same principles can be applied to more complex scenarios such as
line card or node changes. line card or node changes.
2.1.1. Link Down / Metric Increase 3.1.1. Link Down / Metric Increase
First consider the non-urgent failure of a link or the increase of a First consider the non-urgent failure of a link or the increase of a
link metric. In this case, a router R MUST NOT update its FIB until link metric. In this case, a router R MUST NOT update its FIB until
all other routers that send traffic via R and the affected link have all other routers that send traffic via R and the affected link have
first updated their FIBs. first updated their FIBs.
The following argument shows that this rule ensures the correct order The following argument shows that this rule ensures the correct order
of FIB change when the link X->Y is shut down or its metric is of FIB change when the link X->Y is shut down or its metric is
increased. increased.
skipping to change at page 5, line 27 skipping to change at page 6, line 35
According to the proposed ordering, X will be the last router to According to the proposed ordering, X will be the last router to
update its FIB. Once it has updated its FIB, the link X->Y can update its FIB. Once it has updated its FIB, the link X->Y can
actually be shut down (or the repair removed). actually be shut down (or the repair removed).
If the link X-Y is bidirectional a similar process must be run to If the link X-Y is bidirectional a similar process must be run to
order the FIB update for destinations using the link in the direction order the FIB update for destinations using the link in the direction
Y->X. As has already been shown, no packet ever traverses the X-Y Y->X. As has already been shown, no packet ever traverses the X-Y
link in both directions, and hence the operation of the two ordering link in both directions, and hence the operation of the two ordering
processes is orthogonal. processes is orthogonal.
2.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.
2.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 be manifest as multiple link events. For example,
the failure of a router may be notified to the rest of the network as the failure of a router may be notified to the rest of the network as
the individual failure of all its attached links. The means of the individual failure of all its attached links. The means of
identifying the event type from the collection of received link identifying the event type from the collection of received link
events is described in Section 3.1. events is described in Section 4.1.
2.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 [7]. no loops will occur if this ordering is respected [3].
2.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 [7]. if this ordering is respected [3].
2.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
to service. to service.
3. Applying ordered FIB updates 4. Applying ordered FIB updates
3.1. Deducing the topology change 4.1. Deducing the topology change
As has been described, a single event such as the failure or As has been described, a single event such as the failure or
restoration of a single link, single router or a linecard may be restoration of a single link, single router or 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
skipping to change at page 7, line 11 skipping to change at page 8, line 20
If all events received within some hold-down period have a single If all events received within some hold-down period have a single
router (R) in common, then it is assumed that the change reflects an router (R) in common, then it is assumed that the change reflects an
event (line-card or router change) concerning the common router (R). event (line-card or router change) concerning the common router (R).
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 (R).
All ordering computations are based on treating the common router R All ordering computations are based on treating the common router R
as the root for both link and node events. as the root for both link and node events.
3.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 6). 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 reverse connectivity check
means that only the first failure event, or second up event have an means that only the first failure event, or second up event have an
effect on the FIB. effect on the FIB.
If an event is received within the hold down period which does NOT If an event is received within the hold down period which does NOT
reference the common router (R) then in this version of the reference the common router (R) then in this version of the
specification normal convergence is invoked immediately (see specification normal convergence is invoked immediately (see
Section 6). 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 iif the set of link In summary an ordered FIB process is applicable iif 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 . 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 . The set of notifications refer to link up events and metric
decrease events. decrease events.
4. 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.
4.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
reverse Shortest Path Tree in the topology before the failure reverse Shortest Path Tree in the topology before the failure
(rSPT_OLD) rooted at Y. This rSPT gives the shortest paths to reach Y (rSPT_OLD) rooted at Y. This rSPT gives the shortest paths to reach Y
before the failure. The branch of the reverse SPT that is below R before the failure. The branch of the reverse SPT that is below R
corresponds to the set of shortest paths to R that are used by the corresponds to the set of shortest paths to R that are used by the
routers that reach Y via R. routers that reach Y via R.
skipping to change at page 8, line 36 skipping to change at page 9, line 42
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]. [8].
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.
4.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
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 2. 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.
5. 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.
In many cases a router will complete its required FIB changes in a In many cases a router will complete its required FIB changes in a
time much shorter than MAX_FIB and in many other cases, a router will time much shorter than MAX_FIB and in many other cases, a router will
not have to perform any FIB change at all. not have to perform any FIB change at all.
skipping to change at page 9, line 47 skipping to change at page 11, line 9
not yet expired. Once this is done, the router sends a completion not yet expired. Once this is done, the router sends a completion
message to the neighbours that are waiting for it to complete. Those message to the neighbours that are waiting for it to complete. Those
routers are listed in a list called the Notification List. routers are listed in a list called the Notification List.
Completion messages contain an identification of the event to which Completion messages contain an identification of the event to which
they refer. they refer.
Note that, since this is only an optimization, any loss of completion Note that, since this is only an optimization, any loss of completion
messages will result in the routers waiting their defined ranking messages will result in the routers waiting their defined ranking
time and hence the loop-free properties will be preserved. time and hence the loop-free properties will be preserved.
5.1. Construction of the waiting list and notification list 6.1. Construction of the waiting list and notification list
5.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 neighbors 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 neighbors that are using R to reach the failing node or link. The
Notification list of R is equal to the former set and the Waiting Notification list of R is equal to the former set and the Waiting
list of R is equal to the latter. list of R is equal to the latter.
Note that R could include all its neighbors except those in the Note that R could include all its neighbors 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.
5.1.2. Up Events 6.1.2. Up Events
Consider a link or node up event rooted at router Y or the cost Consider a link or node up event rooted at router Y or the cost
decrease of the link Y->X. A router R will compute its new SPT decrease of the link Y->X. A router R will compute its new SPT
(SPT_new(R)). The Waiting list is the set of nexthop routers that R (SPT_new(R)). The Waiting list is the set of nexthop routers that R
uses to reach Y in SPT_new(R). uses to reach Y in SPT_new(R).
In a simple implementation the notification list of R is all the In a simple implementation the notification list of R is all the
neighbours of R excluding those in the Waiting list. This may be 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.
5.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 [4]. An encoding of completion message for IS-IS is proposed in [2].
The following information is required: The following information is required:
. Identity of the sender. . Identity of the sender.
. A list of routing notifications being considered in the . A list of routing notifications being considered in the
associated FIB change. Each notification is defined as : associated 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
6. 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. Fall back mechanisms are investigated in [11]. convergence process. Fall back mechanisms are investigated in [9].
The state machine defined in this version of the draft does not make The state machine defined in this version of the draft does not make
an assumption on which fall back mechanism will be used. an assumption on which fall back mechanism will be used.
7. 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 refered to as capable router is configured with a value refered 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 [8].
An ofib capable router maintains a timer, rank_timer. An ofib capable router maintains a timer, rank_timer.
7.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 : Set state to OFIB_HOLDING_DOWN. Start Hold_down_timer.
ofib_current_common_set = {X,Y}. Compute rank with respect to the ofib_current_common_set = {X,Y}. Compute rank with respect to the
event, as defined in Section 4. Store Waiting List and Notification event, as defined in Section 5. Store Waiting List and Notification
List for X--Y obtained from the rank computation. 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}
Compute rank with respect to the event, as defined in section Compute rank with respect to the event, as defined in section
Section 4 . Section 5 .
Store Waiting List and Notification List for X--Y obtained from Store Waiting List and Notification List for X--Y obtained from
the rank computation. the rank computation.
7.2. OFIB_HOLDING_DOWN 8.2. OFIB_HOLDING_DOWN
OFIB_HOLDING_DOWN is the state of a router that is collecting a set OFIB_HOLDING_DOWN is the state of a router that is collecting a set
of link down or metric increase link-state packets to be processed of link down or metric increase link-state packets to be processed
together using controlled convergence. together using controlled convergence.
EVENT : Reception of a link-state packet describing an event of the EVENT : Reception of a link-state packet describing an event of the
type link up or metric decrease which in itself can be processed type link up or metric decrease which in itself can be processed
using oFIB. using oFIB.
ACTION : ACTION :
skipping to change at page 12, line 35 skipping to change at page 13, line 43
ACTION : ACTION :
ofib_current_common_set = ofib_current_common_set =
intersection(ofib_current_common_set,{A,B}). intersection(ofib_current_common_set,{A,B}).
If ofib_current_common_set is empty, then there is no longer a If ofib_current_common_set is empty, then there is no longer a
node in common in all the pending link-state changes. node in common in all the pending link-state changes.
Set state to OFIB_ABANDONED Set state to OFIB_ABANDONED
Reset Hold_down_timer Reset Hold_down_timer
Trigger AAH mechanism. Trigger AAH mechanism.
If ofib_current_common set is not empty, update waiting list and If ofib_current_common set is not empty, update waiting list and
notification list as defined in Section 4. Note that in the notification list as defined in Section 5. Note that in the
case of a single link event, the link-state packet received when case of a single link event, the link-state packet received when
the router is in this state describes the state change of the the router is in this state describes the state change of the
other direction of the link, hence no changes will be made to other direction of the link, hence no changes will be made to
the waiting and notification lists. the waiting and notification lists.
EVENT : Hold_down_timer expires. EVENT : Hold_down_timer expires.
ACTION : ACTION :
Set state to OFIB_ONGOING. Set state to OFIB_ONGOING.
Start rank_timer with computed rank. Start rank_timer with computed rank.
EVENT : Reception of a completion message EVENT : Reception of a completion message
ACTION : Remove the sender from waiting list associated with the ACTION : Remove the sender from waiting list associated with the
event identified in the completion message. event identified in the completion message.
7.3. OFIB_HOLDING_UP 8.3. OFIB_HOLDING_UP
OFIB_HOLDING_UP is the state of a router that is collecting a set of OFIB_HOLDING_UP is the state of a router that is collecting a set of
link up or metric decrease link-state packets to be processed link up or metric decrease link-state packets to be processed
together using controlled convergence. together using controlled convergence.
EVENT : Reception of a link-state packet describing an event of the EVENT : Reception of a link-state packet describing an event of the
type link down or metric increase to be processed using oFIB. type link down or metric increase to be processed using oFIB.
ACTION : ACTION :
skipping to change at page 13, line 33 skipping to change at page 14, line 41
ACTION : ACTION :
ofib_current_common_set = ofib_current_common_set =
intersection(ofib_current_common_set,{A,B}). intersection(ofib_current_common_set,{A,B}).
If ofib_current_common_set is empty, then there is no longer a If ofib_current_common_set is empty, then there is no longer a
common node in the set of pending link-state changes. common node in the set of pending link-state changes.
Set state to OFIB_ABANDONED. Set state to OFIB_ABANDONED.
Reset Hold_down_timer. Reset Hold_down_timer.
Trigger AAH mechanism. Trigger AAH mechanism.
If ofib_current_common set is not empty, update waiting list and If ofib_current_common set is not empty, update waiting list and
notification list as defined in Section 4. Note that in the notification list as defined in Section 5. Note that in the
case of a single link event, the link-state packet received when case of a single link event, the link-state packet received when
the router is in this state describes the state change of the the router is in this state describes the state change of the
other direction of the link, hence no changes will be made to other direction of the link, hence no changes will be made to
the waiting and notification lists. the waiting and notification lists.
EVENT : Reception of a completion message EVENT : Reception of a completion message
ACTION : Remove the sender from the waiting list associated with the ACTION : Remove the sender from the waiting list associated with the
event identified in the completion message. event identified in the completion message.
EVENT : Hold_down_timer expires. EVENT : Hold_down_timer expires.
ACTION : ACTION :
Set state to OFIB_ONGOING. Set state to OFIB_ONGOING.
Start rank_timer with computed rank. Start rank_timer with computed rank.
7.4. OFIB_ONGOING 8.4. OFIB_ONGOING
OFIB_ONGOING is the state of a router that is applying the ordering OFIB_ONGOING is the state of a router that is applying the ordering
mechanism w.r.t. the set of LSP collected when in OFIB_HOLDING_DOWN mechanism w.r.t. the set of LSP collected when in OFIB_HOLDING_DOWN
or OFIB_HOLDING_UP state. or OFIB_HOLDING_UP state.
EVENT : rank_timer expires or waiting list becomes empty. EVENT : rank_timer expires or waiting list becomes empty.
ACTION : ACTION :
Perform FIB updates according to the change. Perform FIB updates according to the change.
skipping to change at page 14, line 32 skipping to change at page 15, line 37
EVENT : Reception of a link-state packet describing a link state EVENT : Reception of a link-state packet describing a link state
change event. change event.
ACTION : ACTION :
Set state to OFIB_ABANDONED. Set state to OFIB_ABANDONED.
Trigger AAH. Trigger AAH.
Start Hold_down_timer. Start Hold_down_timer.
7.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 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
8. Acknowledgments 9. IANA considerations
We would like to thank Clarence Filsfils and Jean-Philippe Vasseur There are no IANA considerations which arise from this document. Any
for their useful suggestions and comments. such considerations will be called out in protocol specific documents
such as [8]and [2]
9. References 10. Security considerations
[1] "Intermediate system to Intermediate system routeing This draft requires only minor modifications to existing routing
information exchange protocol for use in conjunction with the protocols and therefore does not add significant additional security
Protocol for providing the Connectionless mode Network Service risks. However a full security analysis would need to be provided
(ISO 8473). ISO/IEC 10589:2002, Second Edition". within the protocol specific specifications proposed for deployment.
[2] J. Moy, "OSPF Version 2", RFC 2328, April 1998. 11. Acknowledgments
[3] M. Shand and S. Bryant, "IP Fast Reroute Framework", We would like to thank Jean-Philippe Vasseur for his useful
draft-ietf-rtgwg-ipfrr-framework-07.txt (work in progress), suggestions and comments.
June 2007.
[4] O. Bonaventure, P. Francois, and S. Previdi, "ISIS extensions 12. Informative References
for ordered FIB updates", draft-bonaventure-isis-ordered-00.txt
(work in progress), Feb 2006.
[5] S. Bryant and M. Shand, "Applicability of Loop-free [1] International Organization for Standardization, "Intermediate
Convergence", draft-bryant-shand-lf-applicability-03.txt (work system to Intermediate system intra-domain routeing information
in progress), May 2007. exchange protocol for use in conjunction with the protocol for
providing the connectionless-mode Network Service (ISO 8473)",
ISO/IEC 10589:2002, Second Edition, Nov 2002.
[6] A. Zinin, "Analysis and Minimization of Microloops in Link- [2] Bonaventure, O., "ISIS extensions for ordered FIB updates",
state Routing Protocols", draft-bonaventure-isis-ordered-00 (work in progress),
draft-ietf-rtgwg-microloop-analysis-01.txt (work in progress), February 2006.
Oct 2005.
[7] P. Francois and O. Bonaventure, "Avoiding transient loops [3] P. Francois and O. Bonaventure, "Avoiding transient loops during
during IGP convergence in IP Networks", in IEEE/ACM IGP convergence in IP Networks", in IEEE/ACM Transactions on
Transactions on Networking, Networking, http://inl.info.ucl.ac.be/publications,
http://inl.info.ucl.ac.be/publications, December 2007. December 2007.
[8] P. Pan et al., "Fast Reroute Extensions to RSVP-TE for LSP [4] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Tunnels", RFC 4090. Levels", BCP 14, RFC 2119, March 1997.
[9] S. Bryant, A. Atlas, and M. Shand, "Synchronisation of Loop [5] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
Free Timer Values", draft-atlas-bryant-shand-lf-timers-03 (work
in progress), July 2007.
[10] P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, [6] Pan, P., Swallow, G., and A. Atlas, "Fast Reroute Extensions to
"Achieving sub-second IGP convergence in large IP Networks", RSVP-TE for LSP Tunnels", RFC 4090, May 2005.
in ACM SIGCOMM Computer Communication Review,
http://portal.acm.org/citation.cfm?id=1070873.1070877,
July 2005.
[11] S. Bryant, P. Francois, and M. Shand, "Mechanisms for safely [7] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC 5714,
abandoning loop-free convergence (AAH)", February 2008. January 2010.
[8] K, A. and S. Bryant, "Synchronisation of Loop Free Timer
Values", draft-atlas-bryant-shand-lf-timers-04 (work in
progress), February 2008.
[9] Shand, M., Bryant, S., and P. Francois, "Mechanisms for safely
abandoning loop-free convergence (AAH)",
draft-bryant-francois-shand-ipfrr-aah-01 (work in progress),
October 2008.
Authors' Addresses Authors' Addresses
Pierre Francois Pierre Francois
Universite catholique de Louvain Universite catholique de Louvain
Place Ste Barbe, 2 Place Ste Barbe, 2
Louvain-la-Neuve 1348 Louvain-la-Neuve 1348
BE BE
URI: http://inl.info.ucl.ac.be/ URI: http://inl.info.ucl.ac.be/
skipping to change at page 16, line 38 skipping to change at page 18, line 4
Email: mshand@cisco.com Email: mshand@cisco.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
Full Copyright Statement Clarence Filsfils
Cisco Systems
Copyright (C) The IETF Trust (2008). Brussels,
Belgium
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF Email: cfilsfil@cisco.com
Administrative Support Activity (IASA).
 End of changes. 73 change blocks. 
202 lines changed or deleted 186 lines changed or added

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