Network Working Group Albert J. Tian
Internet Draft Naiming Shen
Expiration Date: Jan 2005 Redback Networks
July 2004
Fast Reroute using Alternative Shortest Paths
draft-tian-frr-alt-shortest-path-00.txt
1. Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
2. Abstract
Repair path mechanism is an important element in IP/LDP fast reroute.
In this document we propose a way to calculate local repair paths
using alternative shortest paths that do not go through the nexthop
router that is being protected.
This document also provide a way to maximize the use of loose
segments in order to simplify the implementation of repair paths.
Tian [Page 1]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
3. Introduction
To construct a repair path, the termination point of the repair path
must be determined first. Then we can calculate the repair path from
the router at point of local repair (PLR) to the termination point
without going through the nexthop router being protected. The
resulting explicit path from the calculation is usually a strict path
that lists all nodes on the path. The path can then be simplified by
maximizing the use of loose hops. The resulting path can then be
implemented using mechanisms such as LSP source route or RSVP-TE.
4. Select the Termination Point of Repair Path
Since node protection can also cover link failure and its in general
difficult to distinguish between link and node failure, node failure
is always assumed, unless the nexthop is a single point of failure.
On a PLR router P, to protect a destination D from the failure of
nexthop N, the termination point T of a repair path can be one of the
following:
If the nexthop N is not the primary egress point E for D, then
either
a) terminate at the primary egress point E for D, or
b) terminate at the next-nexthop node from P to E [NHFRR].
If the nexthop N is the primary egress point E for D, then
c) if there exists an alternative egress point E' for D, terminate
at E';
d) if there are no alternative egress points, terminate at E and
attempt link protection.
Terminating repair path at next-nexthop has several advantages over
terminating at egress point:
1) since there are usually much less next-nexthops than egress
points, next-nexthop based solution requires much less repair
paths to be calculated and maintained.
2) next-nexthop based repair path can protect multicast traffic
[NHFRR-MCAST], while egress based repair path can not.
In some cases, next-nexthop based repair paths may be less optimal
for some destinations, but this usually is not a concern.
If the nexthop is the only egress, then it is a single point of
failure. In this case, link protection is attempted. Repair paths can
Tian [Page 2]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
be calculated easily by disqualifying the link between P and N. The
rest of the discussions in this document will focus on the node
protection cases (i.e. cases a, b and c above).
5. Use Alternative Shortest Paths as Repair Paths
Once the termination point T is decided, we can move on to the
calculation of repair paths from P to T.
Repair paths are used by the PLR router P to quickly recover from the
failure of a nexthop N, therefore the repair path can not go through
the nexthop N that is being protected.
For a destination D, one way to find the repair path on PLR router P
to protect nexthop N's failure is to calculate shortest alternative
paths from P to termination point T that do not go through N.
For networks that are running link state IGP such as OSPF or ISIS, a
simple way to calculate alternative shortest paths is to remove N
from the link state database and re-run SPF from PLR P's point of
view. This SPF will find all the alternative shortest paths from P to
all possible T not going through N, therefore it will find out all
the repair paths needed to cover N's failure, except for cases where
N is a single point of failure. To protect all P's nexthops, the same
calculation needs to be done for each nexthop.
We use the notion ASP-N<A,B> to represent the set of alternative
shortest paths between A and B that do not go through N.
6. Construct Repair Paths using Explicit Paths
Since repair paths can not follow normal IP routing, therefore they
have to be explicitly paths. Even in ECMP cases, when one of the ECMP
nexthop fails, traffic has to be explicitly directed to the other
ECMP nexthops. Therefore the ECMP based repair paths are still
explicit paths.
An explicit path can be expressed as a list of nexthops that the path
must traverse. Each hop can be either strict or loose.
In general there are two ways to implement an explicit path:
a) Stateful Explicit Path: this method installs special forwarding
state on each router that is specified in the explicit path. An
example of this method is RSVP-TE. There is little or no per
packet overhead, but states need to be maintained in the network.
Tian [Page 3]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
This method can handle arbitrary explicit paths. Also RSVP-TE can
support QoS along the path.
b) Source Routed Explicit Path: this method use some form of source
routing to encode the path in the packet itself. An example of
this method is LSP source route [LSP-SRC-RT]. The benefit of
this method is that no state need to be maintained in the
network, therefore this method can scale to a large number of
explicit paths. The limitation is that due to the per packet
overhead, this method is only suitable for simple paths with
small number of routers specified. Please note that a simple path
is not necessarily short. One loose hop specified in the path can
traverse a large number of routers.
There are other solutions for fast reroute. They can all be viewed as
some form of limited source routing. We will discuss this later in
appendix A.
7. Loose Hops in Explicit Repair Paths
There are several benefits of using loose segments in repair paths.
7.1. Reduce Number of Hops Specified
In any case, there is incentive to reduce the number of hops that
need to be specified in an explicit path. The simplest way to reduce
the number of routers that need to be specified in an explicit path
is through the use of loose hops.
For stateful explicit paths, if loose segment optimization using
tunnels is enabled [LOOSE-OPT], then the use of loose segments can
reduce the amount of state installed in the network.
For source routed explicit paths, the use of loose segments can
reduce the per packet overhead.
7.2. Last Loose Hop Optimization
If the last segment of an explicit repair path is a loose segment,
then as an optimization the explicit path can terminate early at the
beginning of the last loose segment. From there on, the packets can
be forwarded towards destination based on normal routing, and the
packets will not come back to the router being protected.
It can be proven that this optimization is also valid for repair
Tian [Page 4]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
paths terminating on next-nexthop router.
Consider the following topology where P is the PLR, N is the nexthop
being protected, H is the next-nexthop, E is the egress. Path P-A-B-H
is the next-nexthop based repair path. All links shown below except
link <P,N> are loose segments that may traverse multiple routers.
A-----B--------+
/ \ / \ |
/ \ / \ |
P-----N-----H-----E
Figure 2
It can be proven that if segment <B,H> can be a loose hop for repair
path P-A-B-H, then repair path P-A-B is sufficient to protect all
traffic from P that passes through H.
7.3. Characters of Loose Hops
One requirement for a repair path is that it can not pass through the
router being protected regardless of its status. Therefore any loose
hop in an explicit repair path must not pass through the router being
protected.
7.3.1. Theorem 1
The following theorem can help identifying the loose segments in an
explicit path.
Theorem 1:
Let SP<A,B> be the set of shortest paths between A and B. If paths in
SP<A,B> do not pass through N when N is available, then the set
SP<A,B> will not change when N and only N becomes unavailable.
Proof:
When node N becomes unavailable, the cost of the links between N and
its neighbors increase from some finite value to infinity. If the
cost of any path between A and B is changed after N's failure, it can
only become higher. Therefore N's failure will not add any new paths
to SP<A,B>.
Tian [Page 5]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
If N is the only node that becomes unavailable, then the costs of
links not connected to N will not be changed. Therefore the cost of
the paths not passing through N will not be changed. That means the
costs of the paths in SP<A,B> will not be changed. Therefore N's
failure will not remove any paths from SP<A,B>.
So N's failure will not change SP<A,B>.
END.
Basically theorem 1 means that if the shortest paths between A and B
do not pass through the router N being protected, then segment <A,B>
can be used as a loose segment in a repair path protecting N, because
the actual path for the loose segment will not be affected by N's
failure.
7.3.2. Theorem 2
The following theorem can further improve theorem 1.
Theorem 2:
Let ASP_N<A,B> be the set of alternative shortest paths between A and
B that do not go through N. Let l(ASP_N<A,B>) be the path length for
ASP_N<A,B>. It is the shortest distance between A and B for paths
that do not go through N. Let d(A,N) be the shortest distance
between A and N. Let d(N,B) be the shortest distance between N and
B.
If the following condition holds, then SP<A,B> do not go through N.
l(ASP_N<A,B>) < d(A,N) + d(N,B) ....... Condition 1
Proof
All the paths between A and B can be divided into two sets, those
that pass through N, and those that do not pass through N. For paths
that pass through N, the shortest distance between A and B is d(A,N)
+ d(N,B). For paths that do not pass through N, by definition the
shortest path is ASP_N<A,B>, and its length is l(ASP_N<A,B>). Because
condition 1 is true, ASP_N<A,B> is shorter than any path that goes
through N. Therefore ASP_N<A,B> is the shortest among all paths
between A and B. Therefore ASP_N<A,B> is SP<A,B>. Since ASP_N<A,B> do
not go through N, SP<A,B> do not go through N.
END.
Tian [Page 6]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
Essentially Theorem 2 means that if the length of the alternative
shortest path between A and B that do not go through N is shorter
than the distance between A and N plus the distance between N and B,
then the segment <A,B> can be used as a loose segment in a repair
path protecting N.
7.4. Finding Loose Segments in Alternative Shortest Path
Based on theorem 1 and theorem 2, an algorithm can be devised to find
loose hops in alternative shortest paths.
Given an alternative shortest path ASP_N<P,T> = <R1, R2, ..., Rm>
from PLR P to termination point T not going through nexthop N, it can
be used to protect N.
Run SPF from N's point of view to find out d(N,X), for all X.
If all link metrics are symmetrical, then d(X,N) = d(N,X), for all X.
If some link metrics are asymmetrical, then run an additional reverse
metric SPF from N's point of view to find out d(X,N), for all X.
Let c(Ri, Rj) be the link metric from Ri to Rj.
The following algorithm maximizes the length of loose hops in the
alternative shortest path. It evaluates a segment on the path against
theorem 2, if it can be a loose hop, then extend the segment by one
hop and re-evaluate again, till a point that the segment is no longer
a loose segment. In this way the algorithm finds the longest loose
segment on the path for a given starting point.
Algorithm Find_Loose_Hops
{
len = 0;
start = 1;
end = start;
while (end < m) {
if (len + c(R[end],R[end+1]) >= d(R[start],N) + d(N,R[end])) {
if (len == 0) {
output segment <R[end], R[end+1]> as a strict hop;
end = end+1;
start = end;
if (start > m) break;
} else {
output segment <R[start],R[end]> as a loose hop;
start = end;
}
} else {
Tian [Page 7]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
len = len + c(R[end],R[end+1]);
end = end+1;
if (end == m) {
output segment <R[start],R[end]> as a loose hop;
}
}
}
}
7.5. Implementing Repair Paths
LSP source route and RSVP-TE (possibly with loose segment
optimization), can be used to construct arbiturary repair paths.
Please note that under some topologies the repair paths may require
multiple strict hops to route around the router being protected. For
example, in the following topology as shown in Figure 1, P-N-H-E was
the primary path. In order for PLR P to implement repair path P-A-B-
H-E to protect failure in N, the first three segments must all be
strict. Link metrics are show next to the links.
10
A-----B
10 / \ / \ 10
/ 1\ /1 \
P-----N-----H-----E
1 1 10
Figure 2 A sample topology that requires complex repair path
This repair path can only be supported by LSP source route and RSVP-
TE today.
8. Security Considerations
This document does not introduce any new security issues.
Tian [Page 8]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
9. Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS 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.
10. References
[IPFRR] M. Shand, "IP Fast Reroute Framework",
draft-ietf-rtgwg-ipfrr-framework-01.txt, Work in progress.
[NHFRR] N. Shen, P. Pang, "Nexthop Fast ReRoute for IP and MPLS",
draft-shen-nhop-fastreroute-00.txt, Work in progress.
[NHFRR-MCAST] N. Shen, L. Wei, D. Farinacci, "Discovering PIM-SM
Next-Nexthop Downstream Nodes",
draft-shen-pim-nnhop-nodes-00.txt, Work in progress.
[LSP-SRC-RT] A. Tian, G. Apostolopoulos, "Source Routed MPLS LSP
using Domain Wide Label",
draft-tian-mpls-lsp-source-route-00.txt, May 2004, Work in
progress.
[LOOSE-OPT] A. Tian, N. Shen, "Loose Segment Optimization in
Explicit Paths", draft-tian-rsvp-loose-seg-opt-00.txt,
Work in progress.
Tian [Page 9]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
[LOOPFREE] Atlas, Torvi, Choudhury, Martin, Imhoff, Fedyk,
"IP/LDP Local Protection", draft-atlas-ip-local-protect-00.txt,
Work in progress.
[UTURN] Atlas, et al., "U-turn Alternates for IP/LDP Local
Protection", draft-atlas-ip-local-protect-uturn-00.txt, Work in
progress.
[TUNNEL] Bryant, Filsfils, Previdi, Shand, "IP Fast Reroute using
tunnels", draft-bryant-ipfrr-tunnels-00.txt, May 2004, Work In
Progress.
[RSVPTE] Awduche, et al., "Extensions to RSVP for LSP Tunnels",
RFC 3209, December 2001.
[LDP] L. Andersson, P. Doolan, N. Feldman, A. Fredette, and B.
Thomas, "LDP Specification", RFC 3036, January 2001.
11. Author Information
Albert Jining Tian
Redback Networks, Inc.
300 Holger Way
San Jose, CA 95134
Email: tian@redback.com
Naiming Shen
Redback Networks, Inc.
300 Holger Way
San Jose, CA 95134
Email: naiming@redback.com
12. Appendix A: Classification of Repair Path Mechanisms
12.1. Two Hops: Strict - Loose
Downstream Path (Loop-Free Alternative) [LOOPFREE]
ECMP
Tian [Page 10]
Internet Draft draft-tian-frr-alt-shortest-path-00.txt July 2004
12.2. Two Hops: Loose - Loose
Tunnel Approach without directed forwarding [TUNNEL].
12.3. Three Hops: Loose - Strict - Loose
Tunnel Approach with directed forwarding [TUNNEL].
12.4. Three Hops: Strict - Strict - Loose
U-Turn: only support a subset of the cases where the first hop node
must be an upstream node. [UTURN]
12.5. Three Hops: Strict - Loose - Loose
Tunnel Approach with first strict hop optimization and without
directed forwarding [TUNNEL].
12.6. Four Hops - Strict, Loose, then Strict, Loose
Tunnel Approach with first strict hop optimization and directed
forwarding [TUNNEL].
12.7. Arbitrary Mix of Loose and Strict
LSP Source Route [LSP-SRC-RT]
RSVP-TE [RSVPTE]
RSVP-TE with Loose Hop Optimization [LOOSE-OPT].
Tian [Page 11]