are loose segments that may traverse multiple routers.
A-----B--------+
/ \ / \ |
/ \ / \ |
P-----N-----H-----E
Figure 2
It can be proven that if segment ** 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 next-nexthop 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 be the set of shortest paths between A and B. If paths in
SP do not pass through N when N is available, then the set
Tian [Page 5]
Internet Draft draft-tian-frr-alt-shortest-path-01.txt July 2004
SP 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.
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 will not be changed. Therefore N's
failure will not remove any paths from SP.
So N's failure will not change SP.
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
can be safely 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 be the set of alternative shortest paths between A and
B that do not go through N. Let l(ASP_N) be the path length for
ASP_N. 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 do not go through N.
l(ASP_N) < 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
Tian [Page 6]
Internet Draft draft-tian-frr-alt-shortest-path-01.txt July 2004
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, and its length is l(ASP_N). Because
condition 1 is true, ASP_N is shorter than any path that goes
through N. Therefore ASP_N is the shortest among all paths
between A and B. Therefore ASP_N is SP. Since ASP_N do
not go through N, SP do not go through N.
END.
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 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 = **