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:

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.