RFC 7811
An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)
Pages: 118
Proposed Standard
Proposed Standard
Part 2 of 6 – Pages 18 to 36
5. MRT Lowpoint Algorithm Specification
The MRT Lowpoint algorithm computes one GADAG that is then used by a router to determine its MRT-Blue and MRT-Red next hops to all destinations. Finally, based upon that information, alternates are selected for each next hop to each destination. The different parts of this algorithm are described below. o Order the interfaces in the network graph. See Section 5.1. o Compute the local MRT Island for the particular MRT Profile. See Section 5.2. o Select the root to use for the GADAG. See Section 5.3. o Initialize all interfaces to UNDIRECTED. See Section 5.4. o Compute the DFS value, e.g., D(x), and lowpoint value, L(x). See Figure 8. o Construct the GADAG. See Section 5.5. o Assign directions to all interfaces that are still UNDIRECTED. See Section 5.6. o From the computing router x, compute the next hops for the MRT- Blue and MRT-Red. See Section 5.7. o Identify alternates for each next hop to each destination by determining which one of the MRT-Blue and the MRT-Red the computing router x should select. See Section 5.8. A Python implementation of this algorithm is given in Appendix A.5.1. Interface Ordering
To ensure consistency in computation, all routers MUST order interfaces identically down to the set of links with the same metric to the same neighboring node. This is necessary for the DFS in Lowpoint_Visit in Section 4.3, where the selection order of the interfaces to explore results in different trees. Consistent interface ordering is also necessary for computing the GADAG, where the selection order of the interfaces to use to form ears can result in different GADAGs. It is also necessary for the topological sort described in Section 5.8, where different topological sort orderings can result in undirected links being added to the GADAG in different directions.
The required ordering between two interfaces from the same router x is given in Figure 14. Interface_Compare(interface a, interface b) if a.metric < b.metric return A_LESS_THAN_B if b.metric < a.metric return B_LESS_THAN_A if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id return A_LESS_THAN_B if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id return B_LESS_THAN_A // Same metric to same node, so the order doesn't matter for // interoperability. return A_EQUAL_TO_B Figure 14: Rules for Ranking Multiple Interfaces (Order Is from Low to High) In Figure 14, if two interfaces on a router connect to the same remote router with the same metric, the Interface_Compare function returns A_EQUAL_TO_B. This is because the order in which those interfaces are initially explored does not affect the final GADAG produced by the algorithm described here. While only one of the links will be added to the GADAG in the initial traversal, the other parallel links will be added to the GADAG with the same direction assigned during the procedure for assigning direction to UNDIRECTED links described in Section 5.6. An implementation is free to apply some additional criteria to break ties in interface ordering in this situation, but those criteria are not specified here since they will not affect the final GADAG produced by the algorithm. The Interface_Compare function in Figure 14 relies on the interface.metric and the interface.neighbor.mrt_node_id values to order interfaces. The exact source of these values for different IGPs and applications is specified in Figure 15. The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is normative. The metric and mrt_node_id values for IS-IS Path Control and Reservation (PCR) in this table should be considered informational. The normative values are specified in [IEEE8021Qca].
+--------------+-----------------------+-----------------------------+ | IGP/flooding | mrt_node_id | metric of | | protocol | of neighbor | interface | | and | on interface | | | application | | | +--------------+-----------------------+-----------------------------+ | OSPFv2 for | 4-octet Neighbor | 2-octet Metric field | | IP/LDP FRR | Router ID in | for corresponding | | | Link ID field for | point-to-point link | | | corresponding | in Router-LSA | | | point-to-point link | | | | in Router-LSA | | +--------------+-----------------------+-----------------------------+ | OSPFv3 for | 4-octet Neighbor | 2-octet Metric field | | IP/LDP FRR | Router ID field | for corresponding | | | for corresponding | point-to-point link | | | point-to-point link | in Router-LSA | | | in Router-LSA | | +--------------+-----------------------+-----------------------------+ | IS-IS for | 7-octet neighbor | 3-octet metric field | | IP/LDP FRR | system ID and | in Extended IS | | | pseudonode number | Reachability TLV (type 22) | | | in Extended IS | or Multi-Topology | | | Reachability TLV (type| IS Neighbor TLV (type 222) | | | 22) or Multi-Topology | | | | IS Neighbor TLV (type | | | | 222) | | +--------------+-----------------------+-----------------------------+ | IS-IS PCR for| 8-octet Bridge ID | 3-octet SPB-LINK-METRIC in | | protection | created from 2-octet | SPB-Metric sub-TLV (type 29)| | of traffic | Bridge Priority in | in Extended IS Reachability | | in bridged | Shortest Path Bridging| TLV (type 22) or | | |SPB Instance sub-TLV | Multi-Topology | | networks | (type 1) carried in | Intermediate Systems | | | MT-Capability TLV | TLV (type 222). In the case| | | (type 144) and 6-octet| of asymmetric link metrics, | | | neighbor system ID in | the larger link metric | | | Extended IS | is used for both link | | | Reachability TLV (type| directions. | | | 22) or Multi-Topology | (informational) | | | Intermediate Systems | | | | TLV (type 222) | | | | (informational) | | +--------------+-----------------------+-----------------------------+ Figure 15: Value of interface.neighbor.mrt_node_id and interface.metric to Be Used for Ranking Interfaces, for Different Flooding Protocols and Applications
The metrics are unsigned integers and MUST be compared as unsigned integers. The results of mrt_node_id comparisons MUST be the same as would be obtained by converting the mrt_node_ids to unsigned integers using network byte order and performing the comparison as unsigned integers. In the case of IS-IS for IP/LDP FRR with point-to-point links, the pseudonode number (the 7th octet) is zero. Broadcast interfaces will be discussed in Section 7.5.2. MRT Island Identification
The local MRT Island for a particular MRT profile can be determined by starting from the computing router in the network graph and doing a breadth-first-search (BFS). The BFS explores only links that are in the same area/level, are not IGP-excluded, and are not MRT- ineligible. The BFS explores only nodes that support the particular MRT profile. See Section 7 of [RFC7812] for more-precise definitions of these criteria. MRT_Island_Identification(topology, computing_rtr, profile_id, area) for all routers in topology rtr.IN_MRT_ISLAND = FALSE computing_rtr.IN_MRT_ISLAND = TRUE explore_list = { computing_rtr } while (explore_list is not empty) next_rtr = remove_head(explore_list) for each intf in next_rtr if (not intf.IN_MRT_ISLAND and not intf.MRT-ineligible and not intf.remote_intf.MRT-ineligible and not intf.IGP-excluded and (intf in area) and (intf.remote_node supports profile_id) ) intf.IN_MRT_ISLAND = TRUE intf.remote_intf.IN_MRT_ISLAND = TRUE if (not intf.remote_node.IN_MRT_ISLAND)) intf.remote_node.IN_MRT_ISLAND = TRUE add_to_tail(explore_list, intf.remote_node) Figure 16: MRT Island Identification5.3. GADAG Root Selection
In Section 8.3 of [RFC7812], the GADAG Root Selection Policy is described for the Default MRT Profile. This selection policy allows routers to consistently select a common GADAG Root inside the local MRT Island, based on advertised priority values. The MRT Lowpoint algorithm simply requires that all routers in the MRT Island MUST select the same GADAG Root; the mechanism can vary based upon the MRT profile description. Before beginning computation, the network graph
is reduced to contain only the set of routers that support the specific MRT profile whose MRTs are being computed. As noted in Section 7, pseudonodes MUST NOT be considered for GADAG root selection. It is expected that an operator will designate a set of routers as good choices for selection as GADAG root by setting the GADAG Root Selection Priority for that set of routers to lower (more preferred) numerical values. For guidance on setting the GADAG Root Selection Priority values, refer to Section 9.1.5.4. Initialization
Before running the algorithm, there is the standard type of initialization to be done, such as clearing any computed DFS-values, lowpoint-values, DFS parents, lowpoint-parents, any MRT-computed next hops, and flags associated with algorithm. It is assumed that a regular SPF computation has been run so that the primary next hops from the computing router to each destination are known. This is required for determining alternates at the last step. Initially, all interfaces MUST be initialized to UNDIRECTED. Whether they are OUTGOING, INCOMING, or both is determined when the GADAG is constructed and augmented. It is possible that some links and nodes will be marked using standard IGP mechanisms to discourage or prevent transit traffic. Section 7.3.1 of [RFC7812] describes how those links and nodes are excluded from MRT Island formation. MRT-FRR also has the ability to advertise links MRT-Ineligible, as described in Section 7.3.2 of [RFC7812]. These links are excluded from the MRT Island and the GADAG. Computation of MRT next hops will therefore not use any MRT-ineligible links. The MRT Lowpoint algorithm does still need to consider MRT-ineligible links when computing FRR alternates, because an MRT-ineligible link can still be the shortest-path next hop to reach a destination. When a broadcast interface is advertised as MRT-ineligible, then the pseudonode representing the entire broadcast network MUST NOT be included in the MRT Island. This is equivalent to excluding all of the broadcast interfaces on that broadcast network from the MRT Island.
5.5. Constructing the GADAG Using Lowpoint Inheritance
As discussed in Section 4.2, it is necessary to find ears from a node x that is already in the GADAG (known as IN_GADAG). Two different methods are used to find ears in the algorithm. The first is by going to a DFS-child that is not IN_GADAG and then following the chain of lowpoint parents until an IN_GADAG node is found. The second is by going to a neighbor that is not IN_GADAG and then following the chain of DFS parents until an IN_GADAG node is found. As an ear is found, the associated interfaces are marked based on the direction taken. The nodes in the ear are marked as IN_GADAG. In the algorithm, first the ears via DFS-children are found and then the ears via DFS-neighbors are found. By adding both types of ears when an IN_GADAG node is processed, all ears that connect to that node are found. The order in which the IN_GADAG nodes are processed is, of course, key to the algorithm. The order is a stack of ears so the most recent ear is found at the top of the stack. Of course, the stack stores nodes and not ears, so an ordered list of nodes, from the first node in the ear to the last node in the ear, is created as the ear is explored and then that list is pushed onto the stack. Each ear represents a partial order (see Figure 4) and processing the nodes in order along each ear ensures that all ears connecting to a node are found before a node higher in the partial order has its ears explored. This means that the direction of the links in the ear is always from the node x being processed towards the other end of the ear. Additionally, by using a stack of ears, this means that any unprocessed nodes in previous ears can only be ordered higher than nodes in the ears below it on the stack. In this algorithm that depends upon Lowpoint inheritance, it is necessary that every node has a lowpoint parent that is not itself. If a node is a cut-vertex, that may not yet be the case. Therefore, any nodes without a lowpoint parent will have their lowpoint parent set to their DFS parent and their lowpoint value set to the DFS-value of their parent. This assignment also properly allows an ear between two cut-vertices. Finally, the algorithm simultaneously computes each node's localroot, as described in Figure 12. This is further elaborated as follows. The localroot can be inherited from the node at the end of the ear unless the end of the ear is x itself, in which case the localroot for all the nodes in the ear would be x. This is because whenever the first cycle is found in a block, or an ear involving a bridge is computed, the cut-vertex closest to the root would be x itself. In all other scenarios, the properties of lowpoint/dfs parents ensure
that the end of the ear will be in the same block, and thus inheriting its localroot would be the correct localroot for all newly added nodes. The pseudocode for the GADAG algorithm (assuming that the adjustment of lowpoint for cut-vertices has been made) is shown in Figure 17. Construct_Ear(x, Stack, intf, ear_type) ear_list = empty cur_node = intf.remote_node cur_intf = intf not_done = true while not_done cur_intf.UNDIRECTED = false cur_intf.OUTGOING = true cur_intf.remote_intf.UNDIRECTED = false cur_intf.remote_intf.INCOMING = true if cur_node.IN_GADAG is false cur_node.IN_GADAG = true add_to_list_end(ear_list, cur_node) if ear_type is CHILD cur_intf = cur_node.lowpoint_parent_intf cur_node = cur_node.lowpoint_parent else // ear_type must be NEIGHBOR cur_intf = cur_node.dfs_parent_intf cur_node = cur_node.dfs_parent else not_done = false if (ear_type is CHILD) and (cur_node is x) // x is a cut-vertex and the local root for // the block in which the ear is computed x.IS_CUT_VERTEX = true localroot = x else // Inherit localroot from the end of the ear localroot = cur_node.localroot while ear_list is not empty y = remove_end_item_from_list(ear_list) y.localroot = localroot push(Stack, y) Construct_GADAG_via_Lowpoint(topology, gadag_root) gadag_root.IN_GADAG = true gadag_root.localroot = None Initialize Stack to empty
push gadag_root onto Stack while (Stack is not empty) x = pop(Stack) foreach ordered_interface intf of x if ((intf.remote_node.IN_GADAG == false) and (intf.remote_node.dfs_parent is x)) Construct_Ear(x, Stack, intf, CHILD) foreach ordered_interface intf of x if ((intf.remote_node.IN_GADAG == false) and (intf.remote_node.dfs_parent is not x)) Construct_Ear(x, Stack, intf, NEIGHBOR) Construct_GADAG_via_Lowpoint(topology, gadag_root) Figure 17: Lowpoint Inheritance GADAG Algorithm5.6. Augmenting the GADAG by Directing All Links
The GADAG, regardless of the method used to construct it, at this point could be used to find MRTs, but the topology does not include all links in the network graph. That has two impacts. First, there might be shorter paths that respect the GADAG partial ordering and so the alternate paths would not be as short as possible. Second, there may be additional paths between a router x and the root that are not included in the GADAG. Including those provides potentially more bandwidth to traffic flowing on the alternates and may reduce congestion compared to just using the GADAG as currently constructed. The goal is thus to assign direction to every remaining link marked as UNDIRECTED to improve the paths and number of paths found when the MRTs are computed. To do this, we need to establish a total order that respects the partial order described by the GADAG. This can be done using Kahn's topological sort [Kahn_1962_topo_sort], which essentially assigns a number to a node x only after all nodes before it (e.g., with a link incoming to x) have had their numbers assigned. The only issue with the topological sort is that it works on DAGs and not ADAGs or GADAGs. To convert a GADAG to a DAG, it is necessary to remove all links that point to a root of block from within that block. That provides the necessary conversion to a DAG and then a topological sort can be done. When adding undirected links to the GADAG, links connecting the block root to other nodes in that block need special handling because the topological order will not always give the right answer for those links. There are three cases to consider. If the undirected link in question has another parallel link between the
same two nodes that is already directed, then the direction of the undirected link can be inherited from the previously directed link. In the case of parallel cut links, we set all of the parallel links to both INCOMING and OUTGOING. Otherwise, the undirected link in question is set to OUTGOING from the block root node. A cut-link can then be identified by the fact that it will be directed both INCOMING and OUTGOING in the GADAG. The exact details of this whole process are captured in Figure 18. Add_Undirected_Block_Root_Links(topo, gadag_root) foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if (i.remote_node.localroot is not x or i.PROCESSED ) continue Initialize bundle_list to empty bundle.UNDIRECTED = true bundle.OUTGOING = false bundle.INCOMING = false foreach interface i2 in x if i2.remote_node is i.remote_node add_to_list_end(bundle_list, i2) if not i2.UNDIRECTED: bundle.UNDIRECTED = false if i2.INCOMING: bundle.INCOMING = true if i2.OUTGOING: bundle.OUTGOING = true if bundle.UNDIRECTED foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.remote_intf.INCOMING = true else if (bundle.OUTGOING and bundle.INCOMING) foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.INCOMING = true i3.remote_intf.INCOMING = true i3.remote_intf.OUTGOING = true
else if bundle.OUTGOING
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.remote_intf.INCOMING = true
else if bundle.INCOMING
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.INCOMING = true
i3.remote_intf.OUTGOING = true
Modify_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING:
i.INCOMING = false
i.INCOMING_STORED = true
i.remote_intf.OUTGOING = false
i.remote_intf.OUTGOING_STORED = true
Revert_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING_STORED
i.INCOMING = true
i.remote_intf.OUTGOING = true
i.INCOMING_STORED = false
i.remote_intf.OUTGOING_STORED = false
Run_Topological_Sort_GADAG(topo, gadag_root)
Modify_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo
node.unvisited = 0
foreach interface i of x
if (i.INCOMING)
node.unvisited += 1
Initialize working_list to empty
Initialize topo_order_list to empty
add_to_list_end(working_list, gadag_root) while working_list is not empty y = remove_start_item_from_list(working_list) add_to_list_end(topo_order_list, y) foreach ordered_interface i of y if intf.OUTGOING i.remote_node.unvisited -= 1 if i.remote_node.unvisited is 0 add_to_list_end(working_list, i.remote_node) next_topo_order = 1 while topo_order_list is not empty y = remove_start_item_from_list(topo_order_list) y.topo_order = next_topo_order next_topo_order += 1 Revert_Block_Root_Incoming_Links(topo, gadag_root) def Set_Other_Undirected_Links_Based_On_Topo_Order(topo) foreach node x in topo foreach interface i of x if i.UNDIRECTED: if x.topo_order < i.remote_node.topo_order i.OUTGOING = true i.UNDIRECTED = false i.remote_intf.INCOMING = true i.remote_intf.UNDIRECTED = false else i.INCOMING = true i.UNDIRECTED = false i.remote_intf.OUTGOING = true i.remote_intf.UNDIRECTED = false Add_Undirected_Links(topo, gadag_root) Add_Undirected_Block_Root_Links(topo, gadag_root) Run_Topological_Sort_GADAG(topo, gadag_root) Set_Other_Undirected_Links_Based_On_Topo_Order(topo) Add_Undirected_Links(topo, gadag_root) Figure 18: Assigning Direction to UNDIRECTED Links Proxy-nodes do not need to be added to the network graph. They cannot be transited and do not affect the MRTs that are computed. The details of how the MRT-Blue and MRT-Red next hops are computed for proxy-nodes and how the appropriate alternate next hops are selected is given in Section 5.9.
5.7. Compute MRT Next Hops
As was discussed in Section 4.1, once an ADAG is found, it is straightforward to find the next hops from any node X to the ADAG root. However, in this algorithm, we will reuse the common GADAG and find not only the one pair of MRTs rooted at the GADAG root with it, but find a pair rooted at each node. This is useful since it is significantly faster to compute. The method for computing differently rooted MRTs from the common GADAG is based on two ideas. First, if two nodes X and Y are ordered with respect to each other in the partial order, then an SPF along OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a decreasing-SPF) can be used to find the increasing and decreasing paths. Second, if two nodes X and Y aren't ordered with respect to each other in the partial order, then intermediary nodes can be used to create the paths by increasing/decreasing to the intermediary and then decreasing/increasing to reach Y. As usual, the two basic ideas will be discussed assuming the network is 2-connected. The generalization to multiple blocks is discussed in Section 5.7.4. The full algorithm is given in Section 5.7.5.5.7.1. MRT Next Hops to All Nodes Ordered with Respect to the Computing Node
Finding two node-disjoint paths from the computing router X to any node Y depends upon whether Y>>X or Y<<X. As shown in Figure 19, if Y>>X, then there is an increasing path that goes from X to Y without crossing R; this contains nodes in the interval [X,Y]. There is also a decreasing path that decreases towards R and then decreases from R to Y; this contains nodes in the interval [X,R-small] or [R-great,Y]. The two paths cannot have common nodes other than X and Y. [Y]<---(Cloud 2)<--- [X] | ^ | | V | (Cloud 3)--->[R]--->(Cloud 1) MRT-Blue path: X->Cloud 2->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y Figure 19: Y>>X
Similar logic applies if Y<<X, as shown in Figure 20. In this case, the increasing path from X increases to R and then increases from R to Y to use nodes in the intervals [X,R-great] and [R-small, Y]. The decreasing path from X reaches Y without crossing R and uses nodes in the interval [Y,X]. [X]<---(Cloud 2)<--- [Y] | ^ | | V | (Cloud 3)--->[R]--->(Cloud 1) MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Red path: X->Cloud 2->Y Figure 20: Y<<X5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect to the Computing Node
When X and Y are not ordered, the first path should increase until we get to a node G, where G>>Y. At G, we need to decrease to Y. The other path should be just the opposite: we must decrease until we get to a node H, where H<<Y, and then increase. Since R is smaller and greater than Y, such G and H must exist. It is also easy to see that these two paths must be node disjoint: the first path contains nodes in interval [X,G] and [Y,G], while the second path contains nodes in interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is necessary to decrease and then increase for the MRT-Blue and increase and then decrease for the MRT-Red; if one simply increased for one and decreased for the other, then both paths would go through the root R.
(Cloud 6)<---[Y]<---(Cloud 5)<------------| | | | | V | [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] ^ | | | | | (Cloud 3)<---[X]<---(Cloud 2)<-----------| MRT-Blue path: decrease to H and increase to Y X->Cloud 2->H->Cloud 5->Y MRT-Red path: increase to G and decrease to Y X->Cloud 3->G->Cloud 6->Y Figure 21: X and Y Unordered This gives disjoint paths as long as G and H are not the same node. Since G>>Y and H<<Y, if G and H could be the same node, that would have to be the root R. This is not possible because there is only one incoming interface to the root R that is created when the initial cycle is found. Recall from Figure 6 that whenever an ear was found to have an end that was the root R, the ear was directed from R so that the associated interface on R is outgoing and not incoming. Therefore, there must be exactly one node M that is the largest one before R, so the MRT-Red path will never reach R; it will turn at M and decrease to Y.5.7.3. Computing Redundant Tree Next Hops in a 2-Connected Graph
The basic ideas for computing RT next hops in a 2-connected graph were given in Sections 5.7.1 and 5.7.2. Given these two ideas, how can we find the trees? If some node X only wants to find the next hops (which is usually the case for IP networks), it is enough to find which nodes are greater and less than X, and which are not ordered; this can be done by running an increasing-SPF and a decreasing-SPF rooted at X and not exploring any links from the ADAG root. In principle, a traversal method other than SPF could be used to traverse the GADAG in the process of determining blue and red next hops that result in maximally redundant trees. This will be the case as long as one traversal uses the links in the direction specified by the GADAG and the other traversal uses the links in the direction opposite of that specified by the GADAG. However, a different traversal algorithm will generally result in different blue and red
next hops. Therefore, the algorithm specified here requires the use of SPF to traverse the GADAG to generate MRT blue and red next hops, as described below. An increasing-SPF rooted at X and not exploring links from the root will find the increasing next hops to all Y>>X. Those increasing next hops are X's next hops on the MRT-Blue to reach Y. A decreasing-SPF rooted at X and not exploring links from the root will find the decreasing next hops to all Z<<X. Those decreasing next hops are X's next hops on the MRT-Red to reach Z. Since the root R is both greater than and less than X, after this increasing-SPF and decreasing-SPF, X's next hops on the MRT-Blue and on the MRT-Red to reach R are known. For every node Y>>X, X's next hops on the MRT-Red to reach Y are set to those on the MRT-Red to reach R. For every node Z<<X, X's next hops on the MRT-Blue to reach Z are set to those on the MRT-Blue to reach R. For those nodes that were not reached by either the increasing-SPF or the decreasing-SPF, we can determine the next hops as well. The increasing MRT-Blue next hop for a node that is not ordered with respect to X is the next hop along the decreasing MRT-Red towards R, and the decreasing MRT-Red next hop is the next hop along the increasing MRT-Blue towards R. Naturally, since R is ordered with respect to all the nodes, there will always be an increasing and a decreasing path towards it. This algorithm does not provide the complete specific path taken but just the appropriate next hops to use. The identities of G and H are not determined by the computing node X. The final case to consider is when the GADAG root R computes its own next hops. Since the GADAG root R is << all other nodes, running an increasing-SPF rooted at R will reach all other nodes; the MRT-Blue next hops are those found with this increasing-SPF. Similarly, since the GADAG root R is >> all other nodes, running a decreasing-SPF rooted at R will reach all other nodes; the MRT-Red next hops are those found with this decreasing-SPF.
E---D---| E<--D<--| | | | | ^ | | | | V | | R F C R F C | | | | ^ ^ | | | V | | A---B---| A-->B---| (a) (b) A 2-connected graph A spanning ADAG rooted at R Figure 22 As an example, consider the situation depicted in Figure 22. Node C runs an increasing-SPF and a decreasing-SPF on the ADAG. The increasing-SPF reaches D, E, and R; the decreasing-SPF reaches B, A, and R. E>>C. So, towards E the MRT-Blue next hop is D, since E was reached on the increasing path through D. The MRT-Red next hop towards E is B, since R was reached on the decreasing path through B. Since E>>D, D will similarly compute its MRT-Blue next hop to be E, ensuring that a packet on MRT-Blue will use path C-D-E. B, A, and R will similarly compute the MRT-Red next hops towards E (which is ordered less than B, A and R), ensuring that a packet on MRT-Red will use path C-B-A-R-E. C can determine the next hops towards F as well. Since F is not ordered with respect to C, the MRT-Blue next hop is the decreasing one towards R (which is B) and the MRT-Red next hop is the increasing one towards R (which is D). Since F>>B, for its MRT-Blue next hop towards F, B will use the real increasing next hop towards F. So a packet forwarded to B on MRT-Blue will get to F on path C-B-F. Similarly, D will use the real decreasing next hop towards F as its MRT-Red next hop, a packet on MRT-Red will use path C-D-F.5.7.4. Generalizing for a Graph That Isn't 2-Connected
If a graph isn't 2-connected, then the basic approach given in Section 5.7.3 needs some extensions to determine the appropriate MRT next hops to use for destinations outside the computing router X's blocks. In order to find a pair of maximally redundant trees in that graph, we need to find a pair of RTs in each of the blocks (the root of these trees will be discussed later) and combine them.
When computing the MRT next hops from a router X, there are three
basic differences:
1. Only nodes in a common block with X should be explored in the
increasing-SPF and decreasing-SPF.
2. Instead of using the GADAG root, X's localroot should be used.
This has the following implications:
A. The links from X's localroot should not be explored.
B. If a node is explored in the outgoing SPF so Y>>X, then X's
MRT-Red next hops to reach Y uses X's MRT-Red next hops to
reach X's localroot and if Z<<X, then X's MRT-Blue next hops
to reach Z uses X's MRT-Blue next hops to reach X's
localroot.
C. If a node W in a common block with X was not reached in the
increasing-SPF or decreasing-SPF, then W is unordered with
respect to X. X's MRT-Blue next hops to W are X's decreasing
(aka MRT-Red) next hops to X's localroot. X's MRT-Red next
hops to W are X's increasing (aka MRT-Blue) next hops to X's
localroot.
3. For nodes in different blocks, the next hops must be inherited
via the relevant cut-vertex.
These are all captured in the detailed algorithm given in
Section 5.7.5.
5.7.5. Complete Algorithm to Compute MRT Next Hops
The complete algorithm to compute MRT Next Hops for a particular
router X is given in Figure 23. In addition to computing the MRT-
Blue next hops and MRT-Red next hops used by X to reach each node Y,
the algorithm also stores an "order_proxy", which is the proper cut-
vertex to reach Y if it is outside the block, and which is used later
in deciding whether the MRT-Blue or the MRT-Red can provide an
acceptable alternate for a particular primary next hop.
In_Common_Block(x, y)
if ( (x.block_id is y.block_id)
or (x is y.localroot) or (y is x.localroot) )
return true
return false
Store_Results(y, direction)
if direction is FORWARD
y.higher = true
y.blue_next_hops = y.next_hops
if direction is REVERSE
y.lower = true
y.red_next_hops = y.next_hops
SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
Store_Results(min_node, direction)
if ((min_node is spf_root) or (min_node is not block_root))
foreach interface intf of min_node
if ( ( ((direction is FORWARD) and intf.OUTGOING) or
((direction is REVERSE) and intf.INCOMING) )
and In_Common_Block(spf_root, intf.remote_node) )
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty
SetEdge(y.localroot)
y.blue_next_hops = y.localroot.blue_next_hops
y.red_next_hops = y.localroot.red_next_hops
y.order_proxy = y.localroot.order_proxy
Compute_MRT_NextHops(x, gadag_root) foreach node y y.higher = y.lower = false clear y.red_next_hops and y.blue_next_hops y.order_proxy = y SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) // red and blue next hops are stored to x.localroot as different // paths are found via the SPF and reverse-SPF. // Similarly, any node whose localroot is x will have its // red_next_hops and blue_next_hops already set. // Handle nodes in the same block that aren't the localroot foreach node y if (y.IN_MRT_ISLAND and (y is not x) and (y.block_id is x.block_id) ) if y.higher y.red_next_hops = x.localroot.red_next_hops else if y.lower y.blue_next_hops = x.localroot.blue_next_hops else y.blue_next_hops = x.localroot.red_next_hops y.red_next_hops = x.localroot.blue_next_hops // Inherit next hops and order_proxies to other components if (x is not gadag_root) and (x.localroot is not gadag_root) gadag_root.blue_next_hops = x.localroot.blue_next_hops gadag_root.red_next_hops = x.localroot.red_next_hops gadag_root.order_proxy = x.localroot foreach node y if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND SetEdge(y) max_block_id = 0 Assign_Block_ID(gadag_root, max_block_id) Compute_MRT_NextHops(x, gadag_root) Figure 23: Complete Algorithm to Compute MRT Next Hops
(page 36 continued on part 3)