draft-ietf-rtgwg-ordered-fib-00.txt   draft-ietf-rtgwg-ordered-fib-01.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: Standards Track Universite catholique de Louvain
Expires: June 11, 2007 Mike Shand Expires: January, 2008 Mike Shand
Stewart Bryant Stewart Bryant
Stefano Previdi Stefano Previdi
Cisco Systems Cisco Systems
December 8, 2006 July, 2007
Loop-free convergence using oFIB Loop-free convergence using oFIB
draft-ietf-rtgwg-ordered-fib-00 draft-ietf-rtgwg-ordered-fib-01
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes 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. 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
skipping to change at page 1, line 38 skipping to change at page 1, line 38
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 June 11, 2007. This Internet-Draft will expire on January 7, 2008.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2006). Copyright (C) The IETF Trust (2007).
Abstract Abstract
This draft describes a mechanism for use in conjunction with link This draft 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 3, line 27 skipping to change at page 3, line 27
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 [4] this mechanism may be applied to the can occur. As described in [5] this mechanism may be applied to the
case of managed link-state changes, i.e. link metric change, manual case of managed link-state changes, i.e. link metric change, manual
link down/up, manual router down/up, and managed state changes of a link 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 set of 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- case where one or more network elements are protected by a fast re-
route mechanism [3] [7]. The mechanisms that are used in the failure route mechanism [3] [8]. The mechanisms that are used in the failure
case are exactly the same as those used for managed changes. For case are exactly the same as those used for managed changes. For
simplicity this draft makes no further distinction between managed simplicity this draft makes no further distinction between managed
and unplanned changes. and unplanned changes.
2. The required FIB update order 2. 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 [6]. correctness proofs of the mechanism can be found in [7].
2.1. Single Link Events 2.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 2.1.1. Link Down / Metric Increase
skipping to change at page 5, line 30 skipping to change at page 5, line 30
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 2.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. events is described in Section 3.1.
2.2.1. Router Down events 2.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 [6]. no loops will occur if this ordering is respected [7].
2.2.2. Router Up events 2.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 [6]. if this ordering is respected [7].
2.2.3. Linecard Failure/Restoration Events 2.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. Deducing the topology change 3. Applying ordered FIB updates
3.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
router's FIB, the routers at the near and far end of the link are
noted.
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
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
link is deemed to be the common router (R).
All ordering computations are based on treating the common router R
as the root for both link and node events.
3.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 6).
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.
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
noted.
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 all events received within the hold-down period have a single
router (R) in common, then it is assumed that the change reflects an
event (line-card or router change) concerning the common router (R).
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 6).
In the case of a link change event, the router at the far end of the The sudden failure of a link or a set of links that are not protected
link is deemed to be the common router (R). using a FRR mechanism must be processed using the conventional mode
of operation.
All ordering computations are based on treating the common router R In summary an event can be dealt with an ordered FIB process iif the
as the root for both link and node events. set of link state notifications received between the first event and
the hold down period reference a common router R, and one of the
following assertions is verified :
. The set of notifications refer to link down events concerning
protected links and metric increase events
. The set of notifications refer to link up events and metric
decrease events.
4. Calculation of the ordering 4. Calculation of the ordering
This section describes how the required ordering is calculated. This section describes how the required ordering is calculated.
4.1. Link or Router Down or Metric Increase 4.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
skipping to change at page 7, line 47 skipping to change at page 8, line 16
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
[8]. [9].
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 4.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 9, line 44 skipping to change at page 10, line 11
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 5.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].
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
. Identity of the set of routing notifications being considered in associated FIB change. Each notification is defined as :
the associated FIB change. . Node ID of the near end of the link
. Node ID of the far end of the link
. Old Metric
. New Metric
6. Fall back to Conventional Convergence 6. 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 and revert to conventional convergence by convergence process and revert to conventional convergence by
immediately expiring all the associated ranking timers. This immediately expiring all the associated ranking timers. This
mechanism is similar to the one described in section 3.1 of [5]. mechanism is similar to the one described in section 3.1 of [6].
Abandoning the controlled convergence process may be instigated by Abandoning the controlled convergence process may be instigated by
any router within the network. any router within the network.
7. Acknowledgments 7. Acknowledgments
We would like to thank Clarence Filsfils and Jean-Philippe Vasseur We would like to thank Clarence Filsfils and Jean-Philippe Vasseur
for their useful suggestions and comments. for their useful suggestions and comments.
8. References 8. References
[1] "Intermediate system to Intermediate system routeing [1] "Intermediate system to Intermediate system routeing
information exchange protocol for use in conjunction with the information exchange protocol for use in conjunction with the
Protocol for providing the Connectionless mode Network Service Protocol for providing the Connectionless mode Network Service
(ISO 8473). ISO/IEC 10589:2002, Second Edition". (ISO 8473). ISO/IEC 10589:2002, Second Edition".
[2] J. Moy, "OSPF Version 2", RFC 2328, April 1998. [2] J. Moy, "OSPF Version 2", RFC 2328, April 1998.
[3] Shand, M. and S. Bryant, "IP Fast Reroute Framework", [3] M. Shand and S. Bryant, "IP Fast Reroute Framework",
draft-ietf-rtgwg-ipfrr-framework-05.txt (work in progress), draft-ietf-rtgwg-ipfrr-framework-07.txt (work in progress),
Oct 2006. June 2007.
[4] Bryant, S. and M. Shand, "Applicability of Loop-free [4] O. Bonaventure, P. Francois, M. Shand, and S. Previdi, "IP Fast
Convergence", draft-bryant-shand-lf-applicability-02.txt (work Reroute Framework", draft-bonaventure-isis-ordered-00.txt (work
in progress), Oct 2006. in progress), Feb 2006.
[5] Zinin, A., "Analysis and Minimization of Microloops in Link- [5] S. Bryant and M. Shand, "Applicability of Loop-free
Convergence", draft-bryant-shand-lf-applicability-03.txt (work
in progress), May 2007.
[6] A. Zinin, "Analysis and Minimization of Microloops in Link-
state Routing Protocols", state Routing Protocols",
draft-ietf-rtgwg-microloop-analysis-01.txt (work in progress), draft-ietf-rtgwg-microloop-analysis-01.txt (work in progress),
Oct 2005. Oct 2005.
[6] Francois, P. and O. Bonaventure, "Avoiding transient loops [7] P. Francois and O. Bonaventure, "Avoiding transient loops
during IGP convergence in IP Networks", in Proceedings of during IGP convergence in IP Networks", in Proceedings of
INFOCOM'05, www.info.ucl.ac.be/people/OBO/papers/ INFOCOM'05, http://inl.info.ucl.ac.be/publications/
pfr-infocom05.pdf, March 2005. avoiding-transient-loops-during-convergence-link-state-routing-
protocols, March 2005.
[7] Pan, P. and al, "Fast Reroute Extensions to RSVP-TE for LSP [8] P. Pan et al., "Fast Reroute Extensions to RSVP-TE for LSP
Tunnels", RFC 4090. Tunnels", RFC 4090.
[8] Atlas, A., Bryant, S., and M. Shand, "Synchronization of Loop [9] A. Atlas, S. Bryant, and M. Shand, "Synchronization of Loop
Free Timer Values", draft-atlas-bryant-shand-lf-timers-02.txt Free Timer Values", draft-atlas-bryant-shand-lf-timers-03.txt
(work in progress), Oct 2006. (work in progress), Jul 2007.
[9] Francois, P., Filsfils, C., Evans, J., and O. Bonaventure, [10] P. Francois, C. Filsfils, J. Evans, and O. Bonaventure,
"Achieving sub-second IGP convergence in large IP Networks", "Achieving sub-second IGP convergence in large IP Networks",
in ACM SIGCOMM Computer Communication Review, in ACM SIGCOMM Computer Communication Review,
http://portal.acm.org/citation.cfm?id=1070873.1070877, http://portal.acm.org/citation.cfm?id=1070873.1070877,
July 2005. July 2005.
Appendix A. General SRLG Case Appendix A. General SRLG Case
This appendix describes the operation of oFIB when multiple link This appendix describes the operation of oFIB when multiple link
events which DO NOT have a node in common occur at approximately the events which DO NOT have a node in common occur at approximately the
same time. The covered events are the failure of a set of links and same time. The covered events are the failure of a set of links and
the restoration of a set of links. Note that for the case of a the restoration of a set of links. Note that for the case of a
sudden SRLG failure, it is assumed that this is fully protected by a sudden SRLG failure, it is assumed that this is fully protected by a
Fast Reroute mechanism, thus converting it into an non-urgent event. Fast Reroute mechanism, thus converting it into an non-urgent event.
In order to be applicable, this solution requires that routers have In order to be applicable, this solution requires that routers have
the same, consistent, view of the set of events. This can be the same, consistent, view of the set of events. This can be
achieved by means of the hold down mechanism described in Section 3 achieved by means of the hold down mechanism described in Section 3.1
and [5]. and [6].
A.1. SRLG Down Events A.1. SRLG Down Events
A.1.1. Determining the ordering A.1.1. Determining the ordering
Consider the case where there are two failing components F and G. In Consider the case where there are two failing components F and G. In
the general case, the ranking for any given router R will be the general case, the ranking for any given router R will be
different for destinations reached through F and those reached different for destinations reached through F and those reached
through G. R must therefore partition its FIB changes into a number through G. R must therefore partition its FIB changes into a number
of destination sets. In the worst-case, the number of destination of destination sets. In the worst-case, the number of destination
skipping to change at page 13, line 19 skipping to change at page 14, line 4
Email: bonaventure@info.ucl.ac.be Email: bonaventure@info.ucl.ac.be
Mike Shand Mike Shand
Cisco Systems Cisco Systems
Green Park, 250, Longwater Avenue, Green Park, 250, Longwater Avenue,
Reading RG2 6GB Reading RG2 6GB
UK UK
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: sbryant@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 Full Copyright Statement
Copyright (C) The Internet Society (2006). Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property Intellectual Property
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights 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 might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
 End of changes. 35 change blocks. 
54 lines changed or deleted 79 lines changed or added

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