Network Working Group Venkata Naidu
Internet Draft Marconi
Expiration Date: Dec 2004 June 2004
IP Fast Reroute using
Stitched Shortest Paths Algorithm (SSPA)
draft-venkata-ipfrr-sspa-00.txt
Status of this Memo
By submitting this Internet-Draft, I certify that any applicable
patent or other IPR claims of which I am aware have been disclosed,
and any of which I become aware will be disclosed, in accordance with
RFC 3668.
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.
This Internet-Draft will expire on December 29, 2004.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
This document describes a practical mechanism to implement IP fast
reroute using dynamic SPF to compute local and remote loop free
nexthops efficiently. Upon link failure, all the destinations
reachable via the primary nexthop will be forwarded to alternative
loop free nexthop, if any. If the alternative nexthop is remote,
packet will be forwarded using any connectionless (for example,
IP-in-IP) or connection-oriented (for example, MPLS) tunnels. This
mechanism doesn't impose any new protocol message/capability
exchange. It is shown that simple changes to existing IGP shortest
path computation and routing table structures are sufficient to
achieve the desired functionality. More over, routers which
implement the proposed mechanism can co-exist and can be fully
backward compatible with existing unmodified routers.
Venkata Expires Dec 2004 [Page 1]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
Table of Contents
1. Introduction .................................................... 2
2. Terminology ..................................................... 3
3. Framework ....................................................... 4
4. Local and Remote NextHops ....................................... 5
5. Changes to Routing Table Structure .............................. 8
6. Computing Protective Nexthops using Dynamic SPF ................ 10
7. Conclusion ..................................................... 12
8. Security Considerations ........................................ 13
9. IANA Considerations ............................................ 13
10. Normative References .......................................... 13
11. Informative References ........................................ 13
12. Appendix: Dynamic SPF Framework ............................... 14
13. Author's Address .............................................. 16
1. Introduction
A primary function in today's Internet router is to determine
the next hop to which a packet should be forwarded. The algorithm
used by each router to obtain the next-hop information for a packet
should always result in a loop free routing path to the packet's
destination. An example of such an algorithm is the interior
gateway link-state protocols like OSPF and ISIS. In an IGP-based
router, all packets with the same destination are forwarded to a
next hop that lies on a path of shortest distance to the
destination. Given a set of link states, all packets between the
same source and destination are forwarded along one or more paths
of the same shortest distance.
This document presents an algorithm that enables a packet to be
forwarded to its destination along multiple alternative loop-free
paths, which are not necessarily of shortest distance. The key
idea of this mechanism is to maintain an efficient data structure
in a router that helps to compute, alternate viable local/remote
next hops in order to ensure loop free routing for each
destination. The data structure used in this algorithm can be
implemented as an add-on software to existing link-state protocols,
Venkata Expires Dec 2004 [Page 2]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
such as OSPF. This algorithm is totally interoperable with
link-state protocols in the sense that loop free routing is still
guaranteed in a network in which only some of the routers use the
algorithm.
2. Terminology
A network will be modeled as a directed graph where each router
corresponds to a node and each link corresponds to an edge in the
graph.
G = (V,E) - A directed connected graph where V is the set of nodes
and E is the set of edges in the graph.
ei - Each edge ei (where i=0, . . ., E-1) has an associated
weight (cost) of wi, which is assumed to be positive.
w(A, B) - The weight of an edge connecting node A to node B is
denoted by w(A, B).
T - A rooted tree T is a subgraph of G such that a
particular node is specified as the root and every node
in G is reachable from the root through a unique
directed path using only edges in T.
SPT - A tree T is said to be a shortest path tree (SPT) for
G if the distance of every node Ni in T is the shortest
distance of Ni in G. Note that there can be multiple
SPTs in a graph, but the shortest distance of any node
is unique.
Local Nexthop -
A node Nj is called the local/direct next hop of node Ni
along a directed path to a destination, if Ni is
directly connected to Nj via an edge of the path.
Remote Nexthop -
A node Nj is called the remote/indirect next hop of node
Ni along a directed path to a destination, if Ni is
connected to Nj via a tunnel (either connectionless or
connection-oriented)
d(S, D) - The shortest distance d(S, D) from node S to node D is
the length of the shortest path from node S to node D.
The length of a path is the sum of the weights of the
edges in that path. The distance of a node Ni
(where i=1, . . ., N) in T is the length of the directed
path in T connecting the root to Ni. The shortest
distance of a node Ni is the length of a shortest path
in G connecting the root to Ni.
Venkata Expires Dec 2004 [Page 3]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
P(S, D) - The set includes all paths between the routers S and D.
D(S, D) - The subset of P(S,D) consists of all paths from S to D
such that the shortest distance from each consecutive
hop to the destination D decreases as the path is
traversed, i.e., if Nj is the next hop of Ni along the
path, then d(Nj,D) < d(Ni,D).
S(S, D) - The subset of D(S,D) consists of all paths from S to D
such that the shortest distance from each consecutive
hop to the destination D decreases and the distance from
S to each consecutive hop increases as the path is
traversed, i.e., if Nj is the next hop of Ni along the
path, then d(Nj,D) < d(Ni,D) AND d(S,Ni) < d(S,Nj)
M(S, D) - The subset of S(S,D) consists of all shortest paths from
S to D.
3. Framework
In the Internet, a packet from a source traverses intermediate
network routers before reaching its destination. When a packet
arrives at a router, a routing table is used to determine the
next hop and the corresponding outgoing link (interface) to which
the packet should be forwarded. Interior gateway link-state routing
protocol, such as OSPF [OSPF], computes this next-hop information
in two phases. First, given the current link states in the network,
each router S keeps track of a shortest path tree (SPT) rooted at S
to every other node. Since the SPT determines a unique path from S
to each router Ri, the first hop from S along this path will then be
used as the next hop to forward any packet that has Ri as its
destination.
Although a router using OSPF has global information about the
network topology, it determines only the local route of a packet -
the next hop. When each router computes such next-hop information
based on an SPT, then each packet is guaranteed to be forwarded
along a loop-free path to its destination. If multiple SPTs rooted
at router S co-exist in a network, there can be multiple choices of
next hops from S to forward a packet, each of which will lead to a
different shortest path of the same distance (also called equal cost
multi-path - ECMP). In this case, the packet can be forwarded to any
of these next hops, which would also result in a loop-free path.
This document presents a new Stitched Shortest Paths Algorithm (SSPA)
which generalizes the idea by allowing a router to forward packets
to multiple viable local/remote next hops that are not necessarily
part of a shortest path from the router to the packet's destination.
The essence of SSPA is the implementation of an efficient data
structure in a router that helps computes alternate viable next hops
(possibly remote) for each destination. When each router forwards
its packets to any of the viable next hops, all packets will be
Venkata Expires Dec 2004 [Page 4]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
routed to their destinations on loop-free paths. If the nexthop is
a remote nexthop, then the packet will be tunneled to the nexthop
using either connectionless or connection-oriented tunnels.
An advantage of maintaining multiple viable next hops in a router
for each destination is to speed up recovery from link failures. A
router supporting SSPA can recover from link failures much faster
since the recovery mechanism using alternate paths can be
implemented locally by the forwarding engine in the router, and
there is almost no delay incurred by the link failure. On the other
hand, without supporting SSPA, after detecting its link failure, the
router would need to first inform other routers about the status of
the link failure by flooding the information throughout the network.
The routers would then re-compute the shortest path tree from scratch
or update an outdated SPT using dynamic SPF algorithms.
Another desirable property of our SSPA scheme is that the algorithm
and its data structure can be efficiently implemented as an add-on
component to existing IGPs such as OSPF and ISIS. It only adds
a small constant overhead to the shortest path tree computation of
the underlying routing protocol. Each SSPA-enhanced router computes
multiple paths based on the topology information exchanged by the
routing protocols.
Conventional routers based on shortest path routing can co-exist
with SSPA-enhanced routers in the same routing area and still
guarantee loop-free routing for each packet. As we will discuss in
more detail later, such interoperability is a consequence of the
loop-free routing policy employed by the SSPA scheme. In general,
an SSPA-enhanced router can interoperate with any router whose
routing protocol uses the loop-free routing policy.
4. Local and Remote Nexthops
IGPs compute an immediate nexthop to forward a packet using global
topological link-state information. Every router in the network
forwards the packet in the shortest path(s) to the destination.
In other words, IGPs compute M(S,D) space for every destination D
from itself as source S.
It is shown in [IPFRR-MPA] that in fact any path in space D(S,D) can
also be used to forward the packet to the destination with out any
loops. Though [IPFRR-MPA] is simple and efficient, but computes only
restricted number of nexthops. In other words, the [IPFRR-MPA]
algorithm is myopic and doesn't look beyond immediate nexthops.
Figure 1 shows and example network topology. Using existing IGPs SPF
computation, source S computes a shortest path (S->N1->D) to
destination D using N1 as the immediate nexthop.
Venkata Expires Dec 2004 [Page 5]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
S
/ \
2 / \ 2
/ \
N1 N2
| |
| | 2
| |
. N3
\ /
2 \ /
\ / 1
\ /
D
Figure 1. Example simple network topology
[IPFRR-MPA] algorithm computes another alternative loop free
(non-shortest) path - (S->N2->N3->D) in the S(S,D) space. But, if
the edge weights are different, as shown in Figure 2, [IPFRR-MPA]
doesn't compute N2 as an alternative nexthop.
S
/ \
2 / \ 1
/ \
N1 N2
| |
| | 3
| |
. N3
\ /
2 \ /
\ / 3
\ /
D
Figure 2. Example simple network topology with modified
edge weights from Figure 1.
By using hop-by-hop routing, it is still possible to use some other
router (along the path) as a remote nexthop, to reach destination D.
In other words, it is possible to reach a remote router (M) along a
shortest with a guaranteed loop-free routing from M to destination D.
This is possible by stitching two shortest paths: one from source S
to intermediate router (either local or remote nexthop) and then
another shortest path from intermediate router M to destination D.
Venkata Expires Dec 2004 [Page 6]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
As shown in Figure 3, N2 can't be used as an alternative link
protective nexthop for destination D. But, N3 can be used as a
(remote) next-hop. We can use IP-in-IP/MPLS tunnel mechanism to
reach destination D via N3.
S
/ \
/ \
N1 N2
. .
. |
. .
. |
. M
. .
. .
. .
. .
. .
D
Figure 3. From source S, destination D is reachable via
direct Nexthop N1 or alternative remote nexthop
M using IP-in-IP/MPLS tunnels
This mechanism is not myopic when compared to [IPFRR-MPA] in a
way that forwarding to a destination is not restricted to local
nexthops. It is possible to fast-reroute (or traffic engineer) an
IP packet by stitching multiple shortest paths (when the single
shortest path in the original SPT is unusable by transient
failures).
Formally, let,
dN1(S, D) via N1 is the shortest path to destination D from S and
dN2(S, M) via N2 is the shortest path to destination M from S and
d(M, D) is the shortest path to destination D from M then
If d(M, D) < dN1(S,D) then M is a viable loop-free next hop to D
The above definition is a generalized version of [IPFRR-MPA]. If
M is directly connected (i.e., local nexthop) to S then the above
definition will degenerate to [IPFRR-MPA].
There may be many such alternative nexthops for each source
destination pair. Searching for each and every such nexthop is
impractical. By using [DYNAMIC-SPF], it is fairly simple and
computationally inexpensive to compute at least one such link-
protective nexthop for each destination.
Venkata Expires Dec 2004 [Page 7]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
We can generalize this mechanism by using more alternative nexthops
recursively along the path to support multiple link-failures.
For example, Figure 4 shows when link to local nexthop N fails
(where N is the shortest path towards D) S can reroute the packet
to M1 using IP-in-IP/MPLS tunnel. After getting the packet M1 makes
its own local decision, which may take the packet to another
non-shortest path but still leads towards the destination.
S
/ .
/ .
N .
. M1
. / .
. N1 .
. . .
. . M2
. . / .
. . N2 .
. . . .
. . . M3
.........N3/
D
Figure 4. Destination D can be reached by using
recursive stitched loop free shortest paths
To reach remote nexthops, we can use any tunneling techniques such
as IP-in-IP, GRE, MPLS etc. Connection oriented forwarding such as
MPLS is not a strict requirement because the effort is to support
IP fast reroute using traditional hop-by-hop routing. If MPLS is
used to support IP fast reroute, then more advanced MPLS traffic
engineering methods are already in-place. Connectionless
hop-by-hop forwarding like, IP-in-IP etc. tunneling techniques
are recommended.
5. Changes to Routing Table Structure
A conventional SPF algorithm (e.g., in Dijkstra, Bellman-Ford,
etc.) during its execution usually keeps track of certain state
information about each node in the network. Typically, such
information consists of:
* a distance attribute
* the next hop attribute from the router, and
* an optional parent attribute for each node.
At each instant of the algorithm execution, the distance attribute
of a node usually represents the distance of the shortest path found
so far from the source router to that node, while the next hop
attribute and the parent attribute respectively identify the first
hop and the last hop of that path.
Venkata Expires Dec 2004 [Page 8]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
+-----------------------------------------------------------------+
| Destination | Local | Remote | Edge Weight/ | Total |
| | NextHop | NextHop | Distance to M | Distance |
+-----------------------------------------------------------------+
| X | N1 | - | w(S, N1) | d(S,X) via N1 |
| X | -- | M | d(S, M) | d(S,X) via N2 |
+-----------------------------------------------------------------+
Table 1: Routing Table structure for a destination X
To compute alternate viable next hops, the SSPA uses a data structure
that obtains more state information about each node in the network
than those described above without incurring significant computational
complexity. More specifically, the SSPA in a given router S maintains
the following data structure for each destination X:
1. For each node X, the first entry in the data structure will
contain the shortest distance dopt(S,X) from the router S to
X discovered so far. This information is computed by existing
SPF algorithms such as Dijkstra or Bellman-Ford.
2. In addition, the cost w(S,Ni) for each outgoing link connecting
the router S to a potential next hop Ni is also maintained.
3. Furthermore, the data structure keeps track of the length of
the shortest path found so far that uses Ni as the next hop
from S, which is denoted by d(S,X) via Ni.
4. Subsequent entries for destination X represent alternative
nexthops. Such alternative nexthops are result of dynamic
SPF computation (Section 6). After completing SSPA algorithm
every destination X might have an alternative nexthops, if
any. These nexthops can be either directly connected or
remote. Every remote nexthop, M will be reachable by some
action (for example, using tunnels)
5. The data structure also keeps track of the length of the
shortest path found so far that uses M as the next hop
from S, which is denoted by d(S,M) via M.
By maintaining this data structure, the SSPA identifies viable next
hops for destination X by making use of the following equation:
IF { d(S,X) via M } - d(S,M) < d(S,X)
THEN M is a viable Next Hop for destination X from source S.
Once the SSPA has obtained information about the distance attribute
for each possible next hop, it can easily determine which next hops
are viable for a given destination (although not all viable next
hops might be discovered). By searching through different paths,
the data structure at every node can be updated, increasing the
Venkata Expires Dec 2004 [Page 9]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
number of viable next hops. As long as the shortest distance between
two nodes is computed correctly, the resulting viable next hops will
not lead to a routing loops.
6. Computing Protective Nexthops using Dynamic SPF
This section describes how to compute alternative, possibly remote,
nexthops using dynamic SPF algorithms [DYNAMIC-SPF]. Appendix
(section 12) gives an idea of Dynamic SPF framework.
Up on a link failure or increase/decrease of an edge weight, usually
link-state protocols compute SPT from scratch. It has been proved
that an outdated SPT can be updated using dynamic SPF algorithms
efficiently. As an added advantage, it is computationally inexpensive
to keep track of the possible alternative paths while updating the
SPT.
Figure 5 shows a SPT computed using a stable link-state topology. As
shown in the figure, S has multiple subtrees rooted at different
nexthops. All prefixes in the corresponding nexthop tree can be
reached using that nexthop. For example, prefix P is in the tree
rooted at nexthop N1. So, S is going to forward all packets destined
to P to nexthop N1.
S
/ \
/ \
/ \
N1 N2 . . .
. .
. . .
. . . .
. . . .
. P . . .
........... .........
Figure 5. From source S SPT, prefix P is reachable
via Nexthops N1 in the SPT.
If the link between S and N1 fails, then the reachability of
prefix P is either:
1. unreachable (because the graph is disconnected) or
2. reachable by some other next hop
If the graph is disconnected, it becomes an impossibility result
for IP FRR mechanism. Where as in the case of, P still connected
by some other path, can be solved by finding the alternative
nexthop to reach P.
Venkata Expires Dec 2004 [Page 10]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
In a normal scenario, after the link failure, S is going to
flood new link-state information to all the routers in the network.
After getting the new link-state information, every router
(including S) is going to re-compute new SPT. In the worst case,
even using Dynamic SPF algorithms, IP reroute after link-failure
is going to take time. But, we can reduce the rerouting/switchover
time by pre-computing fault-tolerant routes.
Source S can pre-compute an alternative path to each prefix Pi in
SPT rooted at N1 as if the link between S and N1 failed. For
example, as shown in Figure 6, prefix P can be reached via nexthop
N2 if the link to primary nexthop N1 fails.
S
/ \
\\ \
/ \
N1 N2 . . .
. .
. . .
. . .----M .
. ./ . .
. P . . .
........... .........
Figure 6. If (S,N1) link fails, prefix P is reachable via
different Nexthops N2 in the new SPT.
There is no need to re-compute the whole SPT for every outgoing
link from source S. By using Dynamic SPF algorithms, [RECONF]
[DYNAMIC-SPF], we can speedup SPT computation dramatically.
More over, one can parallalize the SPFs for each and every
direct link. Though it seems there are multiple SPFs (one per
link) involved, the amortized cost is based on destination and
original SPT. In other words, the pre-computation is done for
each and every destination in the original SPT by cutting
only the directly connected links at source S.
IPFRR-SSPA steps are as follows:
1. Source S computes off-line SPT using link-state topology
(this step is same, as it is done in today's IGPs)
2. For every STEP1 SPT link, i, connected from S to nexthop Ni,
do steps 3 to 5. Every link's SPT is independent and can be
done in parallel.
Venkata Expires Dec 2004 [Page 11]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
3. Cut link i (assume as if link is down) between S and neighbor
Ni. By cutting the link i, all the destinations Pi (previously
reachable via nexthop Ni) will be unreachable.
4. Compute new off-line SPT, call it SPT_i for this failed link i,
using any dynamic SPF algorithm given in [DYNAMIC-SPF] or
[RECONF]. Appendix (section 12) gives a rough framework for
dynamic SPF.
5. While computing the SPT_i, maintain a data structure about the
new nexthop and merge point for every destination Pi.
The resulting SPT_i is going to give new nexthops Nj (reachable
via link j) for each and every prefix in Pi. In other words, the
new nexthop, Nj for Pi in SPT_i is the 'link i protection
nexthop' for destination Pi.
The merge point Mi, is the last common node in the SPT_i path
to destination P where the path from S to Mi is same as in
original SPT.
After all the SPT_i's are computed, SSPA will result in at least
one alternative nexthop, if any, for each and every destination in
the network. These alternative nexthops can be used to fast
reroute IP packets to respective destinations.
7. Conclusion
The stitched shortest path algorithm is an addition to a regular
shortest path algorithm used in routers. Its purpose is to obtain
alternative possibly remote nexthops to reach a destination. The
SSPA is interoperable with most existing shortest path algorithms,
including the Dijkstra algorithm used in routing protocols such
as OSPF and ISIS.
The extra paths obtained by the SSPA are guaranteed to forward the
packet in such a way that there will never be a loop in the packet's
route even if other routers don't use the SSPA. The data structure
contained in every node determines how much the packet is advancing
toward its destination. If the advance is positive, there clearly
can be no loop. This metric can also be used to decide on the
desirability of the path.
The MPA algorithm described in [IPFRR-MPA] document is limited
in scope in a way that only directly connected neighbor routers
are used as viable loop free nexthops. Where as the algorithm
described in this document, SSPA, presents a more advanced
mechanism to compute and reroute packets using dynamic SPF and
tunnels to local/remote nexthops.
Venkata Expires Dec 2004 [Page 12]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
8. Security Considerations
The mechanism described in this document is an add-on off-line
component to existing link-state IGPs. In the worst case, the
behavior and operation of the proposed algorithm is as good as
existing hop-by-hop routing. There are no known security issues
with the proposed mechanism.
9. IANA considerations
There are no IANA considerations that arise from this document.
10. Normative References
Internet-drafts are works in progress available from
http://www.ietf.org/internet-drafts/
11. Informative References
Internet-drafts are works in progress available from
http://www.ietf.org/internet-drafts/
[IPFRR] Shand, M., "IP Fast Reroute Framework",
draft-ietf-rtgwg-ipfrr-framework-01.txt, Work In Progress.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[RECONF] P. Narvaez, "Routing Reconfiguration in IP Networks",
Doctoral Thesis, MIT, May 2000.
[DYNAMIC-SPF] L.S. Buriol, M.G.C. Resende, and M. Thorup,
"Speeding up dynamic shortest path algorithms", INFORMS
J. on Computing
http://www.densis.fee.unicamp.br/~buriol/dspa.ps.gz
[IPFRR-MPA] Venkata Naidu, "IP Fast-Reroute using Multiple Path
"Algorithm", draft-venkata-ipfrr-mpa-00.txt,
Work In Progress.
Venkata Expires Dec 2004 [Page 13]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
12. Appendix - Dynamic SPF Framework
S(e) - Source node of edge e
E(e) - End node of edge e
I(N) - The set of edges directed into the nodes in set N
{ e belongs to E such that E(e) belongs to set N }
O(N) - The set of edges directed out of the nodes in set N
{ e belongs to E such that S(e) belongs to set N }
P(n, T) - is the parent node of n in tree T
D(n, T) - is the distance attribute of n in tree T
B(n, T) - can be just node n itself OR n with the immediate
children in tree T OR n with all the descendents in
the tree T (implementation dependent)
Bmax(e, T) - the set of end node of edge e and all its descendents
in tree T
STEP 1: Initialization
----------------------
(A) Static version
------------------
FOR every vertex v in V
{
P(v, T) = NULL
D(v, T) = INFINITY
}
ENQUEUE(Q, {S, (NULL, 0)})
(B) Dynamic version (SPT exists)
--------------------------------
Case (Edge e increases its weight by Delta)
W(e) = W(e) + Delta
IF e is in T
{
FOR every vertex v in Bmax(E(e), T)
{
// Increase the distance of each descendent
// of E(e) and itself by Delta
D(v, T) = D(v, T) + Delta
}
Venkata Expires Dec 2004 [Page 14]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
// Consider edges directed into descendents of E(e)
// and itself
FOR every edge e' inb I(N)
{
// If the increased distance of a node is larger
// than its distance in another path
IF D(E(e'), T) > D(S(e'), T) + W(e')
{
// choose the smaller distance as the new
// potential distance
newdist = D(S(s'), T) + W(e')
// Update the node with the new distance and
// new parent in the list Q
ENQUEUE(Q, {E(e'), (S(e'), newdist)})
}
}
}
STEP 2: Node Selection
----------------------
IF Q == NULL
{
TERMINATE
}
ELSE
{
// select and remove and element from the queue
{y, (x, d)} = EXTRACT(Q)
// Compute the difference between new and old distance
Delta = (d - D(y, T))
// If there is no improvement in the distance
IF Delta >= 0
{
// Discard this information and go back to Step 2
GO TO STEP 2
}
// Otherwise, update the parent attribute of the
// selected node
P(y, T) = x
// Consider the selected node and a selected subset
// of its descendents
N = B(y, T)
}
Venkata Expires Dec 2004 [Page 15]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
STEP 3: Distance Update
-----------------------
FOR every vertex v in N
{
// update the distance of the selected node and each
// descendents considered
D(v, T) = D(v, T) + Delta
}
STEP 4: Node Search
-------------------
// Consider all edges directed out of the selected subset
// of nodes
FOR every edge e in O(N)
{
// If the reduced distance of selected node also
// reduces the distance of another node
IF D(E(e), T) > D(S(e), T) + W(e)
{
// Choose the smaller distance as the new potential
// distance
newdist = D(S(e), T) + W(e)
// Update the node with the new distance and new
// parent in the list Q
ENQUEUE(Q, {E(e), (S(e), newdist)})
}
}
GO TO STEP 2
13. Author's Address
Venkata Naidu
Marconi Communications
900 Chelmsford Street,
Cross Point III, 4th Floor
Lowell, MA 01851
Phone: (978) 275-7418
EMail: Venkata.Naidu@Marconi.com
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the IETF's procedures with respect to rights in IETF Documents can
be found in BCP 78 and BCP 79.
Venkata Expires Dec 2004 [Page 16]
INTERNET DRAFT IP Fast Reroute using SSPA June 2004
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Venkata Expires Dec 2004 [Page 17]