Hi Chris,
Thanks for addressing this. I have to tell you that my
implementation MRT algorithm works perfectly fine (tested on smaller topology).
I have a architectural question, if MT_RED and MT_BLUE ID's are
allocated by IANA it would be default MT.
How about supporting MRT for multitopology environment ? where
there exist multiple topology all of them desire MRT as backup.
Thanks & Regards
Anil S N
"Be liberal in what you accept, and conservative in what you send" - Jon Postel
From: rtgwg [mailto:[email protected]] On Behalf Of Chris Bowers
Sent: 01 July 2015 02:12
To: [email protected]
Subject: changes to pseudocode and explanation of Select_Alternates_Internal( )
in draft-ietf-rtgwg-mrt-frr-algorithm
All,
I found the existing text and pseudo-code for Select_Alternates_Internal to be
difficult to understand. So I rewrote them in a more systematic way that
hopefully makes it easier to reason about. Anil also had some questions a few
weeks ago on this part of the code, which I hope this helps to clarify.
The diff of the changes can be found at:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/6c66de45bafe64e7e68469e60e9930115ce749d2
The next text is also copied below.
Please tell me if there are any errors or things that can be improved.
Chris
-------------
For each primary next-hop node F to each destination D, S can call
Select_Alternates(S, D, F, primary_intf) to determine whether to use
the MRT-Blue or MRT-Red next-hops as the alternate next-hop(s) for
that primary next hop. The algorithm is given in Figure 24 and
discussed afterwards.
Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order):
if D_higher and D_lower
if F.HIGHER and F.LOWER
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
if F.HIGHER
return USE_RED
if F.LOWER
return USE_BLUE
else if D_higher
if F.HIGHER and F.LOWER
return USE_BLUE
if F.LOWER
return USE_BLUE
if F.HIGHER
if (F.topo_order > D_topo_order)
return USE_BLUE
if (F.topo_order < D_topo_order)
return USE_RED
else if D_lower
if F.HIGHER and F.LOWER
return USE_RED
if F.HIGHER
return USE_RED
if F.LOWER
if F.topo_order > D_topo_order
return USE_BLUE
if F.topo_order < D_topo_order
return USE_RED
else //D is unordered wrt S
if F.HIGHER and F.LOWER
if primary_intf.OUTGOING and primary_intf.INCOMING
// this case should not occur
if primary_intf.OUTGOING
return USE_BLUE
if primary_intf.INCOMING
return USE_RED
if F.LOWER
return USE_RED
if F.HIGHER
return USE_BLUE
Select_Alternates(D, F, primary_intf)
if (D is F) or (D.order_proxy is F)
return PRIM_NH_IS_D_OR_OP_FOR_D
D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order)
Figure 24
It is useful to first handle the case where where F is also D, or F
is the order proxy for D. In this case, only link protection is
possible. The MRT that doesn't use the failed primary next-hop is
used. If both MRTs use the primary next-hop, then the primary next-
hop must be a cut-link, so either MRT could be used but the set of
MRT next-hops must be pruned to avoid the failed primary next-hop
interface. To indicate this case, Select_Alternates returns
PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three
sub-cases above is not provided.
The logic behind Select_Alternates_Internal is described in
Figure 25. As an example, consider the first case described in the
table, where the D>>S and D<<S. If this is true, then either S or D
must be the block root, R. If F>>S and F<<S, then S is the block
root. So the blue path from S to D is the increasing path to D, and
the red path S to D is the decreasing path to D. If the
F.topo_order<D.topo_order, then either F is ordered higher than D or
F is unordered with respect to D. Therefore, F is either on a
decreasing path from S to D, or it is on neither an increasing nor a
decreasing path from S to D. In either case, it is safe to take an
increasing path from S to D to avoid F. We know that when S is R,
the increasing path is the blue path, so it is safe to use the blue
path to avoid F.
If instead F.topo_order>D.topo_order, then either F is ordered lower
than D, or F is unordered with respect to D. Therefore, F is either
on an increasing path from S to D, or it is on neither an increasing
nor a decreasing path from S to D. In either case, it is safe to
take a decreasing path from S to D to avoid F. We know that when S
is R, the decreasing path is the red path, so it is safe to use the
red path to avoid F.
If F>>S or F<<S (but not both), then D is the block root. We then
know that the blue path from S to D is the increasing path to R, and
the red path is the decreasing path to R. When F>>S, we deduce that
F is on an increasing path from S to R. So in order to avoid F, we
use a decreasing path from S to R, which is the red path. Instead,
when F<<S, we deduce that F is on a decreasing path from S to R. So
in order to avoid F, we use an increasing path from S to R, which is
the blue path.
All possible cases are systematically described in the same manner in
the rest of the table.
+------+------------+------+------------------------------+------------+
| D | MRT blue | F | additional | F | Alternate |
| wrt | and red | wrt | criteria | wrt | |
| S | path | S | | MRT | |
| | properties | | | (deduced) | |
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F>>S | additional | F on an | Use Red |
| and | Increasing | only | criteria | increasing | to avoid |
| D<<S,| path to R. | | not needed | path from | F |
| D is | Red path: | | | S to R | |
| R, | Decreasing +------+-----------------+------------+------------+
| | path to R. | F<<S | additional | F on a | Use Blue |
| | | only | criteria | decreasing | to avoid |
| | | | not needed | path from | F |
| or | | | | S to R | |
| | +------+-----------------+------------+------------+
| | | F>>S | topo(F)>topo(D) | F on a | Use Blue |
| S is | Blue path: | and | implies that | decreasing | to avoid |
| R | Increasing | F<<S | F>>D or F??D | path from | F |
| | path to D. | | | S to D or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | path to D. | | topo(F)<topo(D) | F on an | Use Red |
| | | | implies that | increasing | to avoid |
| | | | F<<D or F??D | path from | F |
| | | | | S to D or | |
| | | | | neither | |
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F<<S | additional | F on | Use Blue |
| only | Increasing | only | criteria | decreasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to D. +------+-----------------+------------+------------+
| | Red path: | F>>S | topo(F)>topo(D) | F on | Use Blue |
| | Decreasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | S to R, | | | or | |
| | then | | | neither | |
| | decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | R to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Red | Use Blue |
| | | and | criteria | | to avoid |
| | | F<<S,| not needed | | F |
| | | F is | | | |
| | | R | | | |
+------+------------+------+-----------------+------------+------------+
| D<<S | Blue path: | F>>S | additional | F on | Use Red |
| only | Increasing | only | criteria | increasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to R, +------+-----------------+------------+------------+
| | then | F<<S | topo(F)>topo(D) | F on | Use Blue |
| | increasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | R to D. | | | or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | S to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Blue | Use Red |
| | | and | criteria | | to avoid |
| | | F<<S,| not | | F |
| | | F is | needed | | |
| | | R | | | |
+------+------------+------+-----------------+------------+------------+
| D??S | Blue path: | F<<S | additional | F on a | Use Red |
| | Decr. from | only | criteria | decreasing | to avoid |
| | S to first | | not needed | path from | F |
| | node H>>D, | | | S to H. | |
| | then incr. +------+-----------------+------------+------------+
| | to D. | F>>S | additional | F on an | Use Blue |
| | Red path: | only | criteria | increasing | to avoid |
| | Incr. from | | not needed | path from | F |
| | S to first | | | S to G | |
| | node G<<D, | | | | |
| | then decr. | | | | |
| | +------+-----------------+------------+------------+
| | | F>>S | GADAG link | F on an | Use Blue |
| | | and | direction | incr. path | to avoid |
| | | F<<S,| S->F | from S | F |
| | | F is +-----------------+------------+------------+
| | | R | GADAG link | F on a | Use Red |
| | | | direction | decr. path | to avoid |
| | | | S<-F | from S | F |
| | | +-----------------+------------+------------+
| | | | GADAG link | Implies F is the order |
| | | | direction | proxy for D, which has |
| | | | S<-->F | already been handled. |
+------+------------+------+-----------------+------------+------------+
Figure 25: determining MRT next-hops and alternates based on the
partial order and topological sort relationships between the
source(S), destination(D), primary next-hop(F), and block root(R).
topo(N) indicates the topological sort value of node N. X??Y
indicates that node X is unordered with respect to node Y. It is
assumed that the case where F is D, or where F is the order proxy for
D, has already been handled.
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
