< draft-ietf-rtgwg-lf-conv-frmwk-00.txt   draft-ietf-rtgwg-lf-conv-frmwk-01.txt >
INTERNET DRAFT A Framework for Loop-free Convergence Dec 2006
Network Working Group S. Bryant Network Working Group S. Bryant
Internet Draft M. Shand Internet Draft M. Shand
Expiration Date: June 2007 Cisco Systems Expiration Date: Dec 2007 Cisco Systems
Dec 2006 June 2007
A Framework for Loop-free Convergence A Framework for Loop-free Convergence
<draft-ietf-rtgwg-lf-conv-frmwk-00.txt> <draft-ietf-rtgwg-lf-conv-frmwk-01.txt>
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 36 skipping to change at page 1, line 33
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress." reference 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/1id-abstracts.html http://www.ietf.org/1id-abstracts.html
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
Copyright Notice
Copyright (C) The IETF Trust (2007). All rights reserved.
Abstract Abstract
This draft describes mechanisms that may be used to prevent or to This draft describes mechanisms that may be used to prevent or to
suppress the formation of micro-loops when an IP or MPLS network suppress the formation of micro-loops when an IP or MPLS network
undergoes topology change due to failure, repair or management undergoes topology change due to failure, repair or management
action. action.
Table of Contents Table of Contents
1. The Nature of Micro-loops...........................................4 1. The Nature of Micro-loops...........................................4
2. Applicability.......................................................5 2. Applicability.......................................................5
3. Micro-loop Control Strategies.......................................6 3. Micro-loop Control Strategies.......................................6
4. Loop mitigation.....................................................7 4. Loop mitigation.....................................................7
5. Micro-loop Prevention...............................................9 5. Micro-loop Prevention...............................................9
5.1. Incremental Cost Advertisement...................................9 5.1. Incremental Cost Advertisement..................................9
5.2. Nearside Tunneling..............................................10 5.2. Nearside Tunneling.............................................11
5.3. Farside Tunnels.................................................12 5.3. Farside Tunnels................................................12
5.4. Distributed Tunnels.............................................13 5.4. Distributed Tunnels............................................13
5.5. Packet Marking..................................................13 5.5. Packet Marking.................................................13
5.6. MPLS New Labels.................................................13 5.6. MPLS New Labels................................................14
5.7. Ordered FIB Update..............................................15 5.7. Ordered FIB Update.............................................15
5.8. Synchronised FIB Update.........................................17 5.8. Synchronised FIB Update........................................17
6. Using PLSN In Conjunction With Other Methods.......................17 6. Using PLSN In Conjunction With Other Methods.......................17
7. Loop Suppression...................................................18 7. Loop Suppression...................................................18
8. Compatibility Issues...............................................19 8. Compatibility Issues...............................................19
9. Comparison of Loop-free Convergence Methods........................19 9. Comparison of Loop-free Convergence Methods........................19
10. IANA considerations...............................................20 10. IANA considerations...............................................20
skipping to change at page 3, line 4 skipping to change at page 3, line 4
13. Disclaimer of Validity............................................21 13. Disclaimer of Validity............................................21
14. Copyright Statement...............................................21 14. Copyright Statement...............................................21
15. Normative References..............................................22 15. Normative References..............................................22
16. Informative References............................................22 16. Informative References............................................22
17. Authors' Addresses................................................23 17. Authors' Addresses................................................23
Introduction Introduction
When there is a change to the network topology (due to the failure When there is a change to the network topology (due to the failure
or restoration of a link or router, or as a result of management or restoration of a link or router, or as a result of management
action) the routers need to converge on a common view of the new action) the routers need to converge on a common view of the new
topology and the paths to be used for forwarding traffic to each topology and the paths to be used for forwarding traffic to each
destination. During this process, referred to as a routing destination. During this process, referred to as a routing
transition, packet delivery between certain source/destination pairs transition, packet delivery between certain source/destination pairs
may be disrupted. This occurs due to the time it takes for the may be disrupted. This occurs due to the time it takes for the
topology change to be propagated around the network together with topology change to be propagated around the network together with
the time it takes each individual router to determine and then the time it takes each individual router to determine and then
update the forwarding information base (FIB) for the affected update the forwarding information base (FIB) for the affected
skipping to change at page 4, line 15 skipping to change at page 4, line 15
The disruptive effect of micro-loops is not confined to periods when The disruptive effect of micro-loops is not confined to periods when
there is a component failure. Micro-loops can, for example, form there is a component failure. Micro-loops can, for example, form
when a component is put back into service following repair. Micro- when a component is put back into service following repair. Micro-
loops can also form as a result of a network maintenance action such loops can also form as a result of a network maintenance action such
as adding a new network component, removing a network component or as adding a new network component, removing a network component or
modifying a link cost. modifying a link cost.
This framework provides a summary of the mechanisms that have been This framework provides a summary of the mechanisms that have been
proposed to address the micro-loop issue. proposed to address the micro-loop issue.
1. The Nature of Micro-loops 1. The Nature of Micro-loops
Micro-loops may form during the periods when a network is re- Micro-loops may form during the periods when a network is re-
converging following ANY topology change, and are caused by converging following ANY topology change, and are caused by
inconsistent FIBs in the routers. During the transition, micro-loops inconsistent FIBs in the routers. During the transition, micro-loops
may occur over a single link between a pair of routers that may occur over a single link between a pair of routers that
temporarily use each other as the next hop for a prefix. Micro-loops temporarily use each other as the next hop for a prefix. Micro-loops
may also form when each router in a cycle of routers has the next may also form when each router in a cycle of routers has the next
router in the cycle as a next hop for a prefix. This can occur router in the cycle as a next hop for a prefix.
during the convergence of a network where all link costs are
symmetric when there exists an equal cost path (ECMP) between a pair Cyclic loops may occur if one or more of the following conditions
of routers and the routers make different decisions regarding which are met:-
path to use for forwarding a particular destination. In the absence
of ECMP, cyclic micro-loops always include at least one link with an 1. Asymmetric link costs.
asymmetric cost, or at least two symmetric cost link cost changes 2. The existence of an equal cost path between a pair of
within the convergence time. routers which make different decisions regarding which path
to use for forwarding a particular destination. Note that
even routers which do not implement equal cost multi-path
(ECMP) forwarding must make a choice between the available
equal cost paths and unless they make the same choice the
condition for cyclic loops will be fulfilled.
3. Topology changes affecting multiple links, including single
node and line card failures.
Micro-loops have two undesirable side-effects; congestion and repair Micro-loops have two undesirable side-effects; congestion and repair
starvation. A looping packet consumes bandwidth until it either starvation. A looping packet consumes bandwidth until it either
escapes as a result of the re-synchronization of the FIBs, or its escapes as a result of the re-synchronization of the FIBs, or its
TTL expires. This transiently increases the traffic over a link by TTL expires. This transiently increases the traffic over a link by
as much as 128 times, and may cause the link to congest. This as much as 128 times, and may cause the link to congest. This
congestion reduces the bandwidth available to other traffic (which congestion reduces the bandwidth available to other traffic (which
is not otherwise affected by the topology change). As a result the is not otherwise affected by the topology change). As a result the
"innocent" traffic using the link experiences increased latency, and "innocent" traffic using the link experiences increased latency, and
is liable to congestive packet loss. is liable to congestive packet loss.
skipping to change at page 5, line 20 skipping to change at page 5, line 28
packets over a path that includes the affected topology change. The packets over a path that includes the affected topology change. The
time taken to propagate the topology change through the network, and time taken to propagate the topology change through the network, and
the non-uniform time taken by each router to calculate the new the non-uniform time taken by each router to calculate the new
shortest path tree (SPT) and update its FIB may significantly extend shortest path tree (SPT) and update its FIB may significantly extend
the duration of the packet disruption caused by the micro-loops. In the duration of the packet disruption caused by the micro-loops. In
some cases a packet may be subject to disruption from micro-loops some cases a packet may be subject to disruption from micro-loops
which occur sequentially at links along the path, thus further which occur sequentially at links along the path, thus further
extending the period of disruption beyond that required to resolve a extending the period of disruption beyond that required to resolve a
single loop. single loop.
2. Applicability 2. Applicability
Loop free convergence techniques are applicable [APPL] to any Loop free convergence techniques are applicable [APPL] to any
situation in which micro-loops may form. For example the convergence situation in which micro-loops may form. For example the convergence
of a network following: of a network following:
1) Component failure. 1) Component failure.
2) Component repair. 2) Component repair.
3) Management withdrawal of a component. 3) Management withdrawal of a component.
skipping to change at page 5, line 42 skipping to change at page 6, line 4
4) Management insertion or a component. 4) Management insertion or a component.
5) Management change of link cost (either positive or negative). 5) Management change of link cost (either positive or negative).
6) External cost change, for example change of external gateway as a 6) External cost change, for example change of external gateway as a
result of a BGP change. result of a BGP change.
7) A Shared risk link group failure. 7) A Shared risk link group failure.
In each case, a component may be a link or a router. In each case, a component may be a link or a router.
Loop free convergence techniques are applicable to both IP networks Loop free convergence techniques are applicable to both IP networks
and MPLS enabled networks that use LDP, including LDP networks that and MPLS enabled networks that use LDP, including LDP networks that
use the single-hop tunnel fast-reroute mechanism. use the single-hop tunnel fast-reroute mechanism.
3. Micro-loop Control Strategies. 3. Micro-loop Control Strategies.
Micro-loop control strategies fall into three basic classes: Micro-loop control strategies fall into three basic classes:
1. Micro-loop mitigation 1. Micro-loop mitigation
2. Micro-loop prevention 2. Micro-loop prevention
3. Micro-loop suppression 3. Micro-loop suppression
A micro-loop mitigation scheme works by re-converging the network in A micro-loop mitigation scheme works by re-converging the network in
skipping to change at page 7, line 5 skipping to change at page 7, line 9
imperfect repair experiences a significantly longer outage than it imperfect repair experiences a significantly longer outage than it
would experience with conventional convergence. would experience with conventional convergence.
When a component is returned to service, or when a network When a component is returned to service, or when a network
management action has taken place, this additional delay does not management action has taken place, this additional delay does not
cause traffic disruption, because there is no repair involved. cause traffic disruption, because there is no repair involved.
However the extended delay is undesirable, because it increases the However the extended delay is undesirable, because it increases the
time that the network takes to be ready for another failure, and time that the network takes to be ready for another failure, and
hence leaves it vulnerable to multiple failures. hence leaves it vulnerable to multiple failures.
4. Loop mitigation 4. Loop mitigation
The only known loop mitigation approach is the Path Locking with The only known loop mitigation approach is the Path Locking with
safe-neighbors (PLSN) method described in [PLSN]. In this method, a safe-neighbors (PLSN) method described in [PLSN]. In this method, a
micro-loop free next-hop safety condition is defined as follows: micro-loop free next-hop safety condition is defined as follows:
In a symmetric cost network, it is safe for router X to change to In a symmetric cost network, it is safe for router X to change to
the use of neighbor Y as its next-hop for a specific destination if the use of neighbor Y as its next-hop for a specific destination if
the path through Y to that destination satisfies both of the the path through Y to that destination satisfies both of the
following criteria: following criteria:
1. X considers Y as its loop-free neighbor based on the topology 1. X considers Y as its loop-free neighbor based on the topology
skipping to change at page 9, line 5 skipping to change at page 9, line 5
B destinations as type C results in only a small degradation in loop B destinations as type C results in only a small degradation in loop
prevention. Also note that simulation results indicate that in prevention. Also note that simulation results indicate that in
production networks where some, but not all, links have asymmetric production networks where some, but not all, links have asymmetric
costs, using the stricter asymmetric cost criterion actually REDUCES costs, using the stricter asymmetric cost criterion actually REDUCES
the number of loop free destinations, because fewer destinations can the number of loop free destinations, because fewer destinations can
be classified as type A or B. be classified as type A or B.
This mechanism operates identically for both "bad-news" events, This mechanism operates identically for both "bad-news" events,
"good-news" events and SRLG failure. "good-news" events and SRLG failure.
5. Micro-loop Prevention 5. Micro-loop Prevention
Eight micro-loop prevention methods have been proposed: Eight micro-loop prevention methods have been proposed:
1. Incremental cost advertisement 1. Incremental cost advertisement
2. Nearside tunneling 2. Nearside tunneling
3. Farside tunneling 3. Farside tunneling
4. Distributed tunnels 4. Distributed tunnels
5. Packet marking 5. Packet marking
6. New MPLS labels 6. New MPLS labels
7. Ordered FIB update 7. Ordered FIB update
8. Synchronized FIB update 8. Synchronized FIB update
5.1. Incremental Cost Advertisement 5.1. Incremental Cost Advertisement
When a link fails, the cost of the link is normally changed from its When a link fails, the cost of the link is normally changed from its
assigned metric to "infinity" in one step. However, it can be assigned metric to "infinity" in one step. However, it can be
proved that no micro-loops will form if the link cost is increased proved that no micro-loops will form if the link cost is increased
in suitable increments, and the network is allowed to stabilize in suitable increments, and the network is allowed to stabilize
before the next cost increment is advertised. Once the link cost has before the next cost increment is advertised. Once the link cost has
been increased to a value greater than that of the lowest been increased to a value greater than that of the lowest
alternative cost around the link, the link may be disabled without alternative cost around the link, the link may be disabled without
causing a micro-loop. causing a micro-loop.
The criterion for a link cost change to be safe is that any link The criterion for a link cost change to be safe is that any link
which is subjected to a cost change of x can only cause loops in a which is subjected to a cost change of x can only cause loops in a
part of the network that has a cyclic cost less than or equal to x. part of the network that has a cyclic cost less than or equal to x.
Because there may exist links which have a cost of one in each Because there may exist links which have a cost of one in each
direction, resulting in a cyclic cost of two, this can result in the direction, resulting in a cyclic cost of two, this can result in the
link cost having to be raised in increments of one. However the link cost having to be raised in increments of one. However the
increment can be larger where the minimum cost permits. Determining increment can be larger where the minimum cost permits. Recent work
the minimum link cost in the network is trivial, but unfortunately, [PF] has shown that there are a number of optimizations which can be
calculating the optimum increment at each step is thought to be a applied to the problem in order to minimize the number of increments
costly calculation. required.
This approach has the advantage that it requires no change to the The incremental cost change approach has the advantage over all
routing protocol. It will work in any network that uses a link-state other currently known loop prevention scheme that it requires no
IGP because it does not require any co-operation from the other change to the routing protocol. It will work in any network because
routers in the network. However the method can be extremely slow, it does not require any co-operation from the other routers in the
particularly if large metrics are used. For the duration of the network.
transition some parts of the network continue to use the old
forwarding path, and hence use any repair mechanism for an extended Where large metrics are used and no optimization is performed, the
period. In the case of a failure that cannot be fully repaired, some method can be extremely slow. However in cases where the per link
destinations may become unreachable for an extended period. metric is small, either because small values have been assigned by
the network designers, or because of restrictions implicit in the
routing protocol (e.g. RIP restricts the metric, and BGP using the
AS path length frequently uses an effective metric of one, or a very
small integer for each inter AS hop), the number of required
increments can be acceptably small even without optimizations.
The number of increments required, and hence the time taken to fully
converge, is significant because for the duration of the transition
some parts of the network continue to use the old forwarding path,
and hence use any repair mechanism for an extended period. In the
case of a failure that cannot be fully repaired, some destinations
may become unreachable for an extended period.
Where the micro-loop prevention mechanism was being used to support Where the micro-loop prevention mechanism was being used to support
a fast re-route repair the network may be vulnerable to a second a fast re-route repair the network may be vulnerable to a second
failure for the duration of the controlled re-convergence. failure for the duration of the controlled re-convergence.
Where the micro-loop prevention mechanism was being used to support Where the micro-loop prevention mechanism was being used to support
a reconfiguration of the network the extended time is less of an a reconfiguration of the network the extended time is less of an
issue. In this case, because the real forwarding path is available issue. In this case, because the real forwarding path is available
throughout the whole transition, there is no conflict between throughout the whole transition, there is no conflict between
concurrent change actions throughout the network. concurrent change actions throughout the network.
skipping to change at page 10, line 35 skipping to change at page 11, line 5
the link in one step without causing a micro-loop. the link in one step without causing a micro-loop.
When the failure is an SRLG the link cost increments must be When the failure is an SRLG the link cost increments must be
coordinated across all members of the SRLG. This may be achieved by coordinated across all members of the SRLG. This may be achieved by
completing the transition of one link before starting the next, or completing the transition of one link before starting the next, or
by interleaving the changes. This can be achieved without the need by interleaving the changes. This can be achieved without the need
for any protocol extensions, by for example, using existing for any protocol extensions, by for example, using existing
identifiers to establish the ordering and the arrival of LSP/LSAs to identifiers to establish the ordering and the arrival of LSP/LSAs to
trigger the generation of the next increment. trigger the generation of the next increment.
5.2. Nearside Tunneling 5.2. Nearside Tunneling
This mechanism works by creating an overlay network using tunnels This mechanism works by creating an overlay network using tunnels
whose path is not affected by the topology change and carrying the whose path is not affected by the topology change and carrying the
traffic affected by the change in that new network. When all the traffic affected by the change in that new network. When all the
traffic is in the new, tunnel based, network, the real network is traffic is in the new, tunnel based, network, the real network is
allowed to converge on the new topology. Because all the traffic allowed to converge on the new topology. Because all the traffic
that would be affected by the change is carried in the overlay that would be affected by the change is carried in the overlay
network no micro-loops form. network no micro-loops form.
When a failure is detected (or a link is withdrawn from service), When a failure is detected (or a link is withdrawn from service),
skipping to change at page 12, line 30 skipping to change at page 12, line 40
the same mechanism protects against micro-looping of packets by the the same mechanism protects against micro-looping of packets by the
micro-loop preventing routers. micro-loop preventing routers.
When the failure is an SRLG, the required strategy is to classify When the failure is an SRLG, the required strategy is to classify
traffic according the first member of the SRLG that it will traverse traffic according the first member of the SRLG that it will traverse
on its way to the destination, and to tunnel that traffic to the on its way to the destination, and to tunnel that traffic to the
router that is closest to that SRLG member. This will require router that is closest to that SRLG member. This will require
multiple tunnel destinations, in the limiting case, one per SRLG multiple tunnel destinations, in the limiting case, one per SRLG
member. member.
5.3. Farside Tunnels 5.3. Farside Tunnels
Farside tunneling loop prevention requires the loop preventing Farside tunneling loop prevention requires the loop preventing
routers to place all of the traffic that would traverse the failure routers to place all of the traffic that would traverse the failure
in one or more tunnels terminating at the router (or in the case of in one or more tunnels terminating at the router (or in the case of
node failure routers) at the far side of the failure. The properties node failure routers) at the far side of the failure. The properties
of this method are a more uniform distribution of repair traffic of this method are a more uniform distribution of repair traffic
than is a achieved using the nearside tunnel method, and in the case than is a achieved using the nearside tunnel method, and in the case
of node failure, a reduction in the decapsulation load on any single of node failure, a reduction in the decapsulation load on any single
router. router.
Unlike the nearside tunnel method (which uses normal routing to the Unlike the nearside tunnel method (which uses normal routing to the
repairing router), this method requires the use of a repair path to repairing router), this method requires the use of a repair path to
the farside router. This may be provided by the not-via mechanism, the farside router. This may be provided by the not-via mechanism,
in which case no further computation is needed. in which case no further computation is needed.
The mode of operation is otherwise identical to the nearside The mode of operation is otherwise identical to the nearside
tunneling loop prevention method (Section 5.2). tunneling loop prevention method (Section 5.2).
5.4. Distributed Tunnels 5.4. Distributed Tunnels
In the distributed tunnels loop prevention method, each router In the distributed tunnels loop prevention method, each router
calculates its own repair and forwards traffic affected by the calculates its own repair and forwards traffic affected by the
failure using that repair. Unlike the FRR case, the actual failure failure using that repair. Unlike the FRR case, the actual failure
is known at the time of the calculation. The objective of the loop is known at the time of the calculation. The objective of the loop
preventing routers is to get the packets that would have gone via preventing routers is to get the packets that would have gone via
the failure into G-space [TUNNEL] using routers that are in F-space. the failure into G-space [TUNNEL] using routers that are in F-space.
Because packets are decapsulated on entry to G-space, rather than Because packets are decapsulated on entry to G-space, rather than
being forced to go to the farside of the failure, more optimum being forced to go to the farside of the failure, more optimum
routing may be achieved. This method is subject to the same routing may be achieved. This method is subject to the same
reachability constraints described in [TUNNEL]. reachability constraints described in [TUNNEL].
The mode of operation is otherwise identical to the nearside The mode of operation is otherwise identical to the nearside
tunneling loop prevention method (Section 5.2). tunneling loop prevention method (Section 5.2).
5.5. Packet Marking 5.5. Packet Marking
If packets could be marked in some way, this information could be If packets could be marked in some way, this information could be
used to assign them to one of: the new topology, the old topology or used to assign them to one of: the new topology, the old topology or
a transition topology. They would then be correctly forwarded during a transition topology. They would then be correctly forwarded during
the transition. This could, for example, be achieved by allocating a the transition. This could, for example, be achieved by allocating a
Type of Service bit to the task [RFC791]. This mechanism works Type of Service bit to the task [RFC791]. This mechanism works
identically for both "bad-news" and "good-news" events. It also identically for both "bad-news" and "good-news" events. It also
works identically for SRLG failure. There are three works identically for SRLG failure. There are three
problems with this solution: problems with this solution:
1) The packet marking bit may not available. The packet marking bit may not available.
2) The mechanism would introduce a non-standard forwarding The mechanism would introduce a non-standard forwarding procedure.
procedure.
3) Packet marking using either the old or the new topology would Packet marking using either the old or the new topology would double
double the size of the FIB, however some optimizations may be the size of the FIB, however some optimizations may be possible.
possible.
5.6. MPLS New Labels 5.6. MPLS New Labels
In an MPLS network that is using LDP [LDP] for label distribution, In an MPLS network that is using LDP [LDP] for label distribution,
loop free convergence can be achieved through the use of new labels loop free convergence can be achieved through the use of new labels
when the path that a prefix will take through the network changes. when the path that a prefix will take through the network changes.
As described in Section 5.2, the repairing routers issue a covert As described in Section 5.2, the repairing routers issue a covert
announcement to start the loop free convergence process. All loop announcement to start the loop free convergence process. All loop
preventing routers calculate the new topology and determine whether preventing routers calculate the new topology and determine whether
their FIB needs to be changed. If there is no change in the FIB they their FIB needs to be changed. If there is no change in the FIB they
take no part in the following process. take no part in the following process.
skipping to change at page 14, line 35 skipping to change at page 14, line 45
such time as all routers have carried out all of their covert such time as all routers have carried out all of their covert
announcement activities. On receipt of the overt announcement all announcement activities. On receipt of the overt announcement all
routers that were delaying convergence move to their new path for routers that were delaying convergence move to their new path for
both the new and the old labels. This involves changing the IP both the new and the old labels. This involves changing the IP
address entries to use the new labels, AND changing the old labels address entries to use the new labels, AND changing the old labels
to forward using the new labels. to forward using the new labels.
Because the new label path was installed during the covert phase, Because the new label path was installed during the covert phase,
packets reach their destinations as follows: packets reach their destinations as follows:
o If they do not go via any router using a new label they go If they do not go via any router using a new label they go via the
via the repairing router and the repair. repairing router and the repair.
o If they meet any router that is using the new labels they If they meet any router that is using the new labels they get marked
get marked with the new labels and reach their destination with the new labels and reach their destination using the new path,
using the new path, back-tracking if necessary. back-tracking if necessary.
When all routers have changed to the new path the network is When all routers have changed to the new path the network is
converged. At some time later, when it can be assumed that all converged. At some time later, when it can be assumed that all
routers have moved to using the new path, the FIB can be cleaned up routers have moved to using the new path, the FIB can be cleaned up
to remove the, now redundant, old labels. to remove the, now redundant, old labels.
As with other method methods the new labels may be modified to As with other method methods the new labels may be modified to
provide loop prevention for "good news". There are also a number of provide loop prevention for "good news". There are also a number of
optimizations of this method. optimizations of this method.
5.7. Ordered FIB Update 5.7. Ordered FIB Update
The Ordered FIB loop prevention method is described in [OFIB]. The Ordered FIB loop prevention method is described in [OFIB].
Micro-loops occur following a failure or a cost increase, when a Micro-loops occur following a failure or a cost increase, when a
router closer to the failed component revises its routes to take router closer to the failed component revises its routes to take
account of the failure before a router which is further away. By account of the failure before a router which is further away. By
analyzing the reverse spanning tree over which traffic is directed analyzing the reverse spanning tree over which traffic is directed
to the failed component in the old topology, it is possible to to the failed component in the old topology, it is possible to
determine a strict ordering which ensures that nodes closer to the determine a strict ordering which ensures that nodes closer to the
root always process the failure after any nodes further away, and root always process the failure after any nodes further away, and
hence micro-loops are prevented. hence micro-loops are prevented.
skipping to change at page 16, line 29 skipping to change at page 16, line 37
speed up the convergence process. speed up the convergence process.
Note that the special SRLG case of a full or partial node failure, Note that the special SRLG case of a full or partial node failure,
can be dealt with without using per prefix ordering, by running a can be dealt with without using per prefix ordering, by running a
single reverse SPF rooted at the failed node (or common point of the single reverse SPF rooted at the failed node (or common point of the
subset of failing links in the partial case). subset of failing links in the partial case).
There are two classes of signaling optimization that can be applied There are two classes of signaling optimization that can be applied
to the ordered FIB loop-prevention method: to the ordered FIB loop-prevention method:
1. When the router makes NO change, it can signal immediately. When the router makes NO change, it can signal immediately. This
This significantly reduces the time taken by the network to significantly reduces the time taken by the network to process long
process long chains of routers that have no change to make chains of routers that have no change to make to their FIB.
to their FIB.
2. When a router HAS changed, it can signal that it has completed. When a router HAS changed, it can signal that it has completed. This
This is more problematic since this may be difficult to is more problematic since this may be difficult to determine,
determine, particularly in a distributed architecture, and the particularly in a distributed architecture, and the optimization
optimization obtained is the difference between the actual time obtained is the difference between the actual time taken to make the
taken to make the FIB change and the worst case timer value. FIB change and the worst case timer value. This saving could be of
This saving could be of the order of one second per hop. the order of one second per hop.
There is another method of executing ordered FIB which is based on There is another method of executing ordered FIB which is based on
pure signaling [OB]. Methods that use signaling as an optimization pure signaling [OB]. Methods that use signaling as an optimization
are safe because eventually they fall back on the established IGP are safe because eventually they fall back on the established IGP
mechanisms which ensure that networks converge under conditions of mechanisms which ensure that networks converge under conditions of
packet loss. However a mechanism that relies on signaling in order packet loss. However a mechanism that relies on signaling in order
to converge requires a reliable signaling mechanism which must be to converge requires a reliable signaling mechanism which must be
proven to recover from any failure circumstance. proven to recover from any failure circumstance.
5.8. Synchronised FIB Update 5.8. Synchronised FIB Update
Micro-loops form because of the asynchronous nature of the FIB Micro-loops form because of the asynchronous nature of the FIB
update process during a network transition. In many router update process during a network transition. In many router
architectures it is the time taken to update the FIB itself that is architectures it is the time taken to update the FIB itself that is
the dominant term. One approach would be to have two FIBs and, in a the dominant term. One approach would be to have two FIBs and, in a
synchronized action throughout the network, to switch from the old synchronized action throughout the network, to switch from the old
to the new. One way to achieve this synchronized change would be to to the new. One way to achieve this synchronized change would be to
signal or otherwise determine the wall clock time of the change, and signal or otherwise determine the wall clock time of the change, and
then execute the change at that time, using NTP [NTP] to synchronize then execute the change at that time, using NTP [NTP] to synchronize
the wall clocks in the routers. the wall clocks in the routers.
skipping to change at page 17, line 35 skipping to change at page 17, line 43
mitigation mechanism within this taxonomy is therefore dependent on mitigation mechanism within this taxonomy is therefore dependent on
the degree of synchronization achieved. the degree of synchronization achieved.
This mechanism works identically for both "bad-news" and "good-news" This mechanism works identically for both "bad-news" and "good-news"
events. It also works identically for SRLG failure. events. It also works identically for SRLG failure.
Further consideration needs to be given to interoperating with Further consideration needs to be given to interoperating with
routers that do not support this mechanism. Without a suitable routers that do not support this mechanism. Without a suitable
interoperating mechanism, loops may form for the duration of the interoperating mechanism, loops may form for the duration of the
synchronization delay. synchronization delay.
6. Using PLSN In Conjunction With Other Methods 6. Using PLSN In Conjunction With Other Methods
All of the tunnel methods and packet marking can be combined with All of the tunnel methods and packet marking can be combined with
PLSN [PLSN] to reduce the traffic that needs to be protected by the PLSN [PLSN] to reduce the traffic that needs to be protected by the
advanced method. Specifically all traffic could use PLSN except advanced method. Specifically all traffic could use PLSN except
traffic between a pair of routers both of which consider the traffic between a pair of routers both of which consider the
destination to be type C. The type C to type C traffic would be destination to be type C. The type C to type C traffic would be
protected from micro-looping through the use of a loop prevention protected from micro-looping through the use of a loop prevention
method. method.
However, determining whether the new next hop router considers a However, determining whether the new next hop router considers a
skipping to change at page 18, line 35 skipping to change at page 18, line 43
20 20
On failure of link XY, according to PLSN, S will regard R as a safe On failure of link XY, according to PLSN, S will regard R as a safe
neighbor for traffic to D. However the ordered FIB rank of both R neighbor for traffic to D. However the ordered FIB rank of both R
and T will be zero and hence these can change their FIBs during the and T will be zero and hence these can change their FIBs during the
same time interval. If R changes before T, then a loop will form same time interval. If R changes before T, then a loop will form
around R, T and S. This can be prevented by using a stronger safety around R, T and S. This can be prevented by using a stronger safety
condition than PLSN currently specifies, at the cost of introducing condition than PLSN currently specifies, at the cost of introducing
more type C routers, and hence reducing the PLSN coverage. more type C routers, and hence reducing the PLSN coverage.
7. Loop Suppression 7. Loop Suppression
A micro-loop suppression mechanism recognizes that a packet is A micro-loop suppression mechanism recognizes that a packet is
looping and drops it. One such approach would be for a router to looping and drops it. One such approach would be for a router to
recognize, by some means, that it had seen the same packet before. recognize, by some means, that it had seen the same packet before.
It is difficult to see how sufficiently reliable discrimination It is difficult to see how sufficiently reliable discrimination
could be achieved without some form of per-router signature such as could be achieved without some form of per-router signature such as
route recording. A packet recognizing approach therefore seems route recording. A packet recognizing approach therefore seems
infeasible. infeasible.
An alternative approach would be to recognize that a packet was An alternative approach would be to recognize that a packet was
skipping to change at page 19, line 15 skipping to change at page 19, line 23
form in symmetric cost networks, but would not suppress the cyclic form in symmetric cost networks, but would not suppress the cyclic
loops that form in asymmetric networks. loops that form in asymmetric networks.
This mechanism operates identically for both "bad-news" events, This mechanism operates identically for both "bad-news" events,
"good-news" events and SRLG failure. "good-news" events and SRLG failure.
The problem with this class of micro-loop control strategies is that The problem with this class of micro-loop control strategies is that
whilst they prevent collateral damage they do nothing to enhance the whilst they prevent collateral damage they do nothing to enhance the
productive forwarding of packets during the network transition. productive forwarding of packets during the network transition.
8. Compatibility Issues 8. Compatibility Issues
Deployment of any micro-loop control mechanism is a major change to Deployment of any micro-loop control mechanism is a major change to
a network. Full consideration must be given to interoperation a network. Full consideration must be given to interoperation
between routers that are capable of micro-loop control, and those between routers that are capable of micro-loop control, and those
that are not. Additionally there may be a desire to limit the that are not. Additionally there may be a desire to limit the
complexity of micro-loop control by choosing a method based purely complexity of micro-loop control by choosing a method based purely
on its simplicity. Any such decision must take into account that if on its simplicity. Any such decision must take into account that if
a more capable scheme is needed in the future, its deployment will a more capable scheme is needed in the future, its deployment will
be complicated by interaction with the scheme previously deployed. be complicated by interaction with the scheme previously deployed.
9. Comparison of Loop-free Convergence Methods 9. Comparison of Loop-free Convergence Methods
PLSN [PLSN] is an efficient mechanism to prevent the formation of PLSN [PLSN] is an efficient mechanism to prevent the formation of
micro-loops, but is only a partial solution. It is a useful adjunct micro-loops, but is only a partial solution. It is a useful adjunct
to some of the complete solutions, but may need modification. to some of the complete solutions, but may need modification.
Incremental cost advertisement is impractical as a general solution Incremental cost advertisement is impractical as a general solution
because it takes too long to complete. However, it is universally because it takes too long to complete. However, it is universally
available, and hence may find use in certain network reconfiguration available, and hence may find use in certain network reconfiguration
operations. operations.
skipping to change at page 20, line 28 skipping to change at page 20, line 36
The nearside and farside tunnel methods deal relatively easily with The nearside and farside tunnel methods deal relatively easily with
SRLGs and uncorrelated changes. The convergence delay would be SRLGs and uncorrelated changes. The convergence delay would be
small. However these methods require the use of tunneled forwarding small. However these methods require the use of tunneled forwarding
which is not supported on all router hardware, and raises issues of which is not supported on all router hardware, and raises issues of
forwarding performance. When used with PLSN, the amount of traffic forwarding performance. When used with PLSN, the amount of traffic
that was tunneled would be significantly reduced, thus reducing the that was tunneled would be significantly reduced, thus reducing the
forwarding performance concerns. If the selected repair mechanism forwarding performance concerns. If the selected repair mechanism
requires the use of tunnels, then a tunnel based loop prevention requires the use of tunnels, then a tunnel based loop prevention
scheme may be acceptable. scheme may be acceptable.
10. IANA considerations 10. IANA considerations
There are no IANA considerations that arise from this draft. There are no IANA considerations that arise from this draft.
11. Security Considerations 11. Security Considerations
All micro-loop control mechanisms raise significant security issues All micro-loop control mechanisms raise significant security issues
which must be addressed in their detailed technical description. which must be addressed in their detailed technical description.
12. Intellectual Property Statement 12. Intellectual Property Statement
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 Intellectual Property Rights or other rights that might be claimed
to pertain to the implementation or use of the technology described to pertain to the implementation or use of the technology described
in this document or the extent to which any license under such in this document or the extent to which any license under such
rights might or might not be available; nor does it represent that rights might or might not be available; nor does it represent that
it has made any independent effort to identify any such rights. it has made any independent effort to identify any such rights.
Information on the procedures with respect to rights in RFC Information on the procedures with respect to rights in RFC
documents can be found in BCP 78 and BCP 79. documents can be found in BCP 78 and BCP 79.
skipping to change at page 21, line 29 skipping to change at page 21, line 29
of such proprietary rights by implementers or users of this of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr. at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
13. Disclaimer of Validity 13. Disclaimer of Validity
This document and the information contained herein are provided on This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE
INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS
FOR A PARTICULAR PURPOSE.
14.Copyright Statement 14. 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.
15. Normative References 15. Normative References
There are no normative references. There are no normative references.
16. Informative References 16. Informative References
Internet-drafts are works in progress available from Internet-drafts are works in progress available from
<http://www.ietf.org/internet-drafts/> <http://www.ietf.org/internet-drafts/>
[APPL] Bryant, S., Shand, M., "Applicability of Loop- [APPL] Bryant, S., Shand, M., "Applicability of Loop-
free Convergence", <draft-bryant-shand-lf- free Convergence",
applicability-02.txt>, October 2006, (work in <draft-bryant-shand-lf-applicability-03.txt>,
progress). June 2007, (work in progress).
[IPFRR] Shand, M., "IP Fast-reroute Framework", [IPFRR] Bryant, S., Shand, M., "IP Fast-reroute
<draft-ietf-rtgwg-ipfrr-framework-06.txt>, Framework",
October 2006, (work in progress). <draft-ietf-rtgwg-ipfrr-framework-07.txt>, June
2007, (work in progress).
[LDP] Andersson, L., Doolan, P., Feldman, N., [LDP] Andersson, L., Doolan, P., Feldman, N.,
Fredette, A. and B. Thomas, "LDP Fredette, A. and B. Thomas, "LDP
Specification", RFC3036, Specification", RFC3036,
January 2001. January 2001.
[MPLS-TE] Ping Pan, et al, "Fast Reroute Extensions to [MPLS-TE] Ping Pan, et al, "Fast Reroute Extensions to
RSVP-TE for LSP Tunnels", RFC 4090, May 2005. RSVP-TE for LSP Tunnels", RFC 4090, May 2005.
[NTP] RFC1305 Network Time Protocol (Version 3) [NTP] RFC1305 Network Time Protocol (Version 3)
Specification, Implementation and Analysis. D. Specification, Implementation and Analysis. D.
Mills. March 1992. Mills. March 1992.
[OB] P. Francois, O. Bonaventure, "Avoiding [OB] P. Francois, O. Bonaventure, "Avoiding
transient loops during IGP convergence" transient loops during IGP convergence"
IEEE INFOCOM 2005, March 2005, Miami, Fl., USA IEEE INFOCOM 2005, March 2005, Miami, Fl., USA
[OFIB] Francois et. al., "Loop-free convergence using [OFIB] Francois et. al., "Loop-free convergence using
ordered FIB updates", <draft-ietf-rtgwg- ordered FIB updates",
ordered-fib-00.txt>, December 2006 (work in <draft-ietf-rtgwg-ordered-fib-01.txt>, June
progress). 2007 (work in progress).
[PF] P. Francois, M. Shand, O. Bonaventure,
"Disruption free topology reconfiguration in
OSPF networks", IEEE INFOCOM 2007, May 2007,
Anchorage.
[PLSN] Zinin, A., "Analysis and Minimization of [PLSN] Zinin, A., "Analysis and Minimization of
Microloops in Link-state Routing Protocols", Microloops in Link-state Routing Protocols",
<draft-ietf-rtgwg-microloop-analysis-01.txt>, <draft-ietf-rtgwg-microloop-analysis-01.txt>,
October 2005 (work in progress). October 2005 (work in progress).
[RFC791] RFC791, "Internet Protocol Protocol" [RFC791] RFC791, "Internet Protocol Protocol"
Specification, September 1981 Specification, September 1981
[TIMER] S. Bryant, et. al. , "Synchronisation of Loop [TIMER] S. Bryant, et. al. , "Synchronisation of Loop
Free Timer Values", <draft-atlas-bryant-shand- Free Timer Values", <draft-atlas-bryant-shand-
lf-timers-02.txt>, October 2006 (work in lf-timers-02.txt>, October 2006 (work in
progress) progress)
[TUNNEL] Bryant, S., Shand, M., "IP Fast Reroute using [TUNNEL] Bryant, S., Shand, M., "IP Fast Reroute using
tunnels", <draft-bryant-ipfrr-tunnels-02.txt>, tunnels", <draft-bryant-ipfrr-tunnels-02.txt>,
Apr 2005 (work in progress). Apr 2005 (work in progress).
17. Authors' Addresses 17. Authors' Addresses
Mike Shand Mike Shand
Cisco Systems, Cisco Systems,
250, Longwater Ave, 250, Longwater Ave,
Green Park, Green Park,
Reading, RG2 6GB, Reading, RG2 6GB,
United Kingdom. Email: mshand@cisco.com United Kingdom. Email: mshand@cisco.com
Stewart Bryant Stewart Bryant
Cisco Systems, Cisco Systems,
 End of changes. 48 change blocks. 
98 lines changed or deleted 121 lines changed or added

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