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
