RFC 7811
An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)
Pages: 118
Proposed Standard
Proposed Standard
Part 6 of 6 – Pages 108 to 118
def Run_MRT_for_One_Source(topo, src):
MRT_Island_Identification(topo, src, 0, 0)
Set_Island_Intf_and_Node_Lists(topo)
Set_GADAG_Root(topo,src)
Sort_Interfaces(topo)
Run_Lowpoint(topo)
Assign_Remaining_Lowpoint_Parents(topo)
Construct_GADAG_via_Lowpoint(topo)
Run_Assign_Block_ID(topo)
Add_Undirected_Links(topo)
Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src)
Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src)
Select_Alts_For_One_Src_To_Island_Dests(topo,src)
Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src)
Create_Basic_Named_Proxy_Nodes(topo)
Attach_Named_Proxy_Nodes(topo)
Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src)
def Run_Prim_SPF_for_One_Source(topo,src):
Normal_SPF(topo, src)
Store_Primary_NHs_For_One_Source_To_Nodes(topo,src)
Create_Basic_Named_Proxy_Nodes(topo)
Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
def Run_MRT_for_All_Sources(topo):
for src in topo.node_list:
Reset_Computed_Node_and_Intf_Values(topo)
if src in topo.island_node_list_for_test_gr:
# src runs MRT if it is in same MRT island as test_gr
Run_MRT_for_One_Source(topo,src)
if src is topo.gadag_root:
Store_GADAG_and_Named_Proxies_Once(topo)
else:
# src still runs SPF if not in MRT island
Run_Prim_SPF_for_One_Source(topo,src)
def Write_Output_To_Files(topo,file_prefix):
Write_GADAG_To_File(topo,file_prefix)
Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix)
Write_Alternates_For_All_Dests_To_File(topo,file_prefix)
def Create_Basic_Topology_Input_File(filename):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10],
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10],
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10],
[78,79,10],[79,77,10]]
with open(filename + '.csv', 'w') as topo_file:
for item in data:
if len(item) > 3:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+','+str(item[3])+'\n')
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Create_Complex_Topology_Input_File(filename):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10],
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10],
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10],
[78,79,10],[79,77,10]]
with open(filename + '.csv', 'w') as topo_file:
for item in data:
if len(item) > 3:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+','+str(item[3])+'\n')
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
data = [[01,0],[02,0],[03,0],[04,0],[05,0],
[06,0],[07,0],
[51,0],[55,0],
[12,0],[13,0],[14,0],[15,0],
[16,0],[17,0],[76,0],[77,0],
[78,0],[79,0]]
with open(filename + '.profile', 'w') as topo_file:
for item in data:
line = (str(item[0])+','+str(item[1])+'\n')
topo_file.write(line)
data = [[2001,05,100],[2001,07,120],[2001,03,130],
[2002,13,100],[2002,15,110],
[2003,52,100],[2003,78,100]]
with open(filename + '.prefix', 'w') as topo_file:
for item in data:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Generate_Basic_Topology_and_Run_MRT():
this_gadag_root = 3
Create_Basic_Topology_Input_File('basic_topo_input')
topo = Create_Topology_From_File('basic_topo_input')
res_file_base = 'basic_topo'
Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_Basic_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
def Generate_Complex_Topology_and_Run_MRT():
this_gadag_root = 3
Create_Complex_Topology_Input_File('complex_topo_input')
topo = Create_Topology_From_File('complex_topo_input')
Add_Profile_IDs_from_File(topo,'complex_topo_input')
Add_Prefix_Advertisements_From_File(topo,'complex_topo_input')
Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
Add_Prefixes_for_Non_Island_Nodes(topo)
res_file_base = 'complex_topo'
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
Generate_Basic_Topology_and_Run_MRT()
Generate_Complex_Topology_and_Run_MRT()
<CODE ENDS>
Appendix B. Constructing a GADAG Using SPFs
The basic idea in this method for constructing a GADAG is to use
slightly modified SPF computations to find ears. In every block, an
SPF computation is first done to find a cycle from the local root and
then SPF computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops
from the minimized IN_GADAG node back to the SPF root.
To do this, first all cut-vertices must be identified and localroots
assigned as specified in Figure 12.
The slight modifications to the SPF are as follows. The root of the
block is referred to as the block-root; it is either the GADAG root
or a cut-vertex.
a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All
links between y and x are marked as TEMP_UNUSABLE. They should
not be used during the SPF computation.
b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It
should not be used during the SPF computation. This prevents
ears from starting and ending at the same node and avoids cycles;
the exception is because cycles to/from the block-root are
acceptable and expected.
c. Do not explore links to nodes whose localroot is not the block-
root. This keeps the SPF confined to the particular block.
d. Terminate when the first IN_GADAG node z is minimized.
e. Respect the existing directions (e.g., INCOMING, OUTGOING,
UNDIRECTED) already specified for each interface.
Mod_SPF(spf_root, block_root)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
found_in_gadag = false
while (spf_heap is not empty) and (found_in_gadag is false)
min_node = remove_lowest(spf_heap)
if min_node.IN_GADAG
found_in_gadag = true
else
foreach interface intf of min_node
if ((intf.OUTGOING or intf.UNDIRECTED) and
((intf.remote_node.localroot is block_root) or
(intf.remote_node is block_root)) and
(intf.remote_node is not TEMP_UNUSABLE) and
(intf is not TEMP_UNUSABLE))
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
intf.remote_node.spf_prev_intf = intf
insert_or_update(spf_heap, intf.remote_node)
return min_node
SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, method) Mark all interfaces between cand_intf.remote_node and cand_intf.local_node as TEMP_UNUSABLE if cand_intf.local_node is not block_root Mark cand_intf.local_node as TEMP_UNUSABLE Initialize ear_list to empty end_ear = Mod_SPF(spf_root, block_root) y = end_ear.spf_prev_hop while y.local_node is not spf_root add_to_list_start(ear_list, y) y.local_node.IN_GADAG = true y = y.local_node.spf_prev_intf if(method is not hybrid) Set_Ear_Direction(ear_list, cand_intf.local_node, end_ear,block_root) Clear TEMP_UNUSABLE from all interfaces between cand_intf.remote_node and cand_intf.local_node Clear TEMP_UNUSABLE from cand_intf.local_node return end_ear Figure 31: Modified SPF for GADAG Construction Assume that an ear is found by going from y to x and then running an SPF that terminates by minimizing z (e.g., y<->x...q<->z). Now it is necessary to determine the direction of the ear; if y<<z, then the path should be y->x...q->z; but if y>>z, then the path should be y<-x...q<-z. In Section 5.5, the same problem was handled by finding all ears that started at a node before looking at ears starting at nodes higher in the partial order. In this GADAG construction method, using that approach could mean that new ears aren't added in order of their total cost since all ears connected to a node would need to be found before additional nodes could be found. The alternative is to track the order relationship of each node with respect to every other node. This can be accomplished by maintaining two sets of nodes at each node. The first set, Higher_Nodes, contains all nodes that are known to be ordered above the node. The second set, Lower_Nodes, contains all nodes that are known to be ordered below the node. This is the approach used in this GADAG construction method.
Set_Ear_Direction(ear_list, end_a, end_b, block_root) // Default of A_TO_B for the following cases: // (a) end_a and end_b are the same (root) // or (b) end_a is in end_b's Lower Nodes // or (c) end_a and end_b were unordered with respect to each // other direction = A_TO_B if (end_b is block_root) and (end_a is not end_b) direction = B_TO_A else if end_a is in end_b.Higher_Nodes direction = B_TO_A if direction is B_TO_A foreach interface i in ear_list i.UNDIRECTED = false i.INCOMING = true i.remote_intf.UNDIRECTED = false i.remote_intf.OUTGOING = true else foreach interface i in ear_list i.UNDIRECTED = false i.OUTGOING = true i.remote_intf.UNDIRECTED = false i.remote_intf.INCOMING = true if end_a is end_b return // Next, update all nodes' Lower_Nodes and Higher_Nodes if (end_a is in end_b.Higher_Nodes) foreach node x where x.localroot is block_root if end_a is in x.Lower_Nodes foreach interface i in ear_list add i.remote_node to x.Lower_Nodes if end_b is in x.Higher_Nodes foreach interface i in ear_list add i.local_node to x.Higher_Nodes else foreach node x where x.localroot is block_root if end_b is in x.Lower_Nodes foreach interface i in ear_list add i.local_node to x.Lower_Nodes if end_a is in x.Higher_Nodes foreach interface i in ear_list add i.remote_node to x.Higher_Nodes Figure 32: Algorithm to Assign Links of an Ear Direction A goal of this GADAG construction method is to find the shortest cycles and ears. An ear is started by going to a neighbor x of an IN_GADAG node y. The path from x to an IN_GADAG node is minimal,
since it is computed via SPF. Since a shortest path is made of shortest paths, to find the shortest ears requires reaching from the set of IN_GADAG nodes to the closest node that isn't IN_GADAG. Therefore, an ordered tree is maintained of interfaces that could be explored from the IN_GADAG nodes. The interfaces are ordered by their characteristics of metric, local loopback address, remote loopback address, and ifindex, based on the Interface_Compare function defined in Figure 14. This GADAG construction method ignores interfaces picked from the ordered list that belong to the block root if the block in which the interface is present already has an ear that has been computed. This is necessary since we allow at most one incoming interface to a block root in each block. This requirement stems from the way next hops are computed as was seen in Section 5.7. After any ear gets computed, we traverse the newly added nodes to the GADAG and insert interfaces whose far end is not yet on the GADAG to the ordered tree for later processing. Finally, cut-links are a special case because there is no point in doing an SPF on a block of two nodes. The algorithm identifies cut- links simply as links where both ends of the link are cut-vertices. Cut-links can simply be added to the GADAG with both OUTGOING and INCOMING specified on their interfaces. add_eligible_interfaces_of_node(ordered_intfs_tree,node) for each interface of node if intf.remote_node.IN_GADAG is false insert(intf,ordered_intfs_tree) check_if_block_has_ear(x,block_id) block_has_ear = false for all interfaces of x if ( (intf.remote_node.block_id == block_id) && intf.remote_node.IN_GADAG ) block_has_ear = true return block_has_ear Construct_GADAG_via_SPF(topology, root) Compute_Localroot (root,root) Assign_Block_ID(root,0) root.IN_GADAG = true add_eligible_interfaces_of_node(ordered_intfs_tree,root) while ordered_intfs_tree is not empty cand_intf = remove_lowest(ordered_intfs_tree) if cand_intf.remote_node.IN_GADAG is false if L(cand_intf.remote_node) == D(cand_intf.remote_node) // Special case for cut-links
cand_intf.UNDIRECTED = false cand_intf.remote_intf.UNDIRECTED = false cand_intf.OUTGOING = true cand_intf.INCOMING = true cand_intf.remote_intf.OUTGOING = true cand_intf.remote_intf.INCOMING = true cand_intf.remote_node.IN_GADAG = true add_eligible_interfaces_of_node( ordered_intfs_tree,cand_intf.remote_node) else if (cand_intf.remote_node.local_root == cand_intf.local_node) && check_if_block_has_ear(cand_intf.local_node, cand_intf.remote_node.block_id)) /* Skip the interface since the block root already has an incoming interface in the block */ else ear_end = SPF_for_Ear(cand_intf.local_node, cand_intf.remote_node, cand_intf.remote_node.localroot, SPF method) y = ear_end.spf_prev_hop while y.local_node is not cand_intf.local_node add_eligible_interfaces_of_node( ordered_intfs_tree, y.local_node) y = y.local_node.spf_prev_intf Figure 33: SPF-Based Method for GADAG ConstructionAppendix C. Constructing a GADAG Using a Hybrid Method
The idea of this method is to combine the salient features of the lowpoint inheritance and SPF methods. To this end, we process nodes as they get added to the GADAG just like in the lowpoint inheritance by maintaining a stack of nodes. This ensures that we do not need to maintain lower and higher sets at each node to ascertain ear directions since the ears will always be directed from the node being processed towards the end of the ear. To compute the ear however, we resort to an SPF to have the possibility of better ears (path lengths) thus giving more flexibility than the restricted use of lowpoint/dfs parents. Regarding ears involving a block root, unlike the SPF method, which ignored interfaces of the block root after the first ear, in the hybrid method we would have to process all interfaces of the block root before moving on to other nodes in the block since the direction
of an ear is predetermined. Thus, whenever the block already has an ear computed, and we are processing an interface of the block root, we mark the block root as unusable before the SPF run that computes the ear. This ensures that the SPF terminates at some node other than the block-root. This in turn guarantees that the block-root has only one incoming interface in each block, which is necessary for correctly computing the next hops on the GADAG. As in the SPF GADAG, bridge ears are handled as a special case. The entire algorithm is shown below in Figure 34. find_spf_stack_ear(stack, x, y, xy_intf, block_root) if L(y) == D(y) // Special case for cut-links xy_intf.UNDIRECTED = false xy_intf.remote_intf.UNDIRECTED = false xy_intf.OUTGOING = true xy_intf.INCOMING = true xy_intf.remote_intf.OUTGOING = true xy_intf.remote_intf.INCOMING = true xy_intf.remote_node.IN_GADAG = true push y onto stack return else if (y.local_root == x) && check_if_block_has_ear(x,y.block_id) //Avoid the block root during the SPF Mark x as TEMP_UNUSABLE end_ear = SPF_for_Ear(x,y,block_root,hybrid) If x was set as TEMP_UNUSABLE, clear it cur = end_ear while (cur != y) intf = cur.spf_prev_hop prev = intf.local_node intf.UNDIRECTED = false intf.remote_intf.UNDIRECTED = false intf.OUTGOING = true intf.remote_intf.INCOMING = true push prev onto stack cur = prev xy_intf.UNDIRECTED = false xy_intf.remote_intf.UNDIRECTED = false xy_intf.OUTGOING = true xy_intf.remote_intf.INCOMING = true return
Construct_GADAG_via_hybrid(topology,root) Compute_Localroot (root,root) Assign_Block_ID(root,0) root.IN_GADAG = true Initialize Stack to empty push root onto Stack while (Stack is not empty) x = pop(Stack) for each interface intf of x y = intf.remote_node if y.IN_GADAG is false find_spf_stack_ear(stack, x, y, intf, y.block_root) Figure 34: Hybrid GADAG Construction MethodAcknowledgements
The authors would like to thank Shraddha Hegde, Eric Wu, Janos Farkas, Stewart Bryant, Alvaro Retana, and Deccan (Shaofu Peng) for their suggestions and review. We would also like to thank Anil Kumar SN for his assistance in clarifying the algorithm description and pseudocode.
Authors' Addresses
Gabor Sandor Enyedi Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Gabor.Sandor.Enyedi@ericsson.com Andras Csaszar Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Andras.Csaszar@ericsson.com Alia Atlas Juniper Networks 10 Technology Park Drive Westford, MA 01886 United States Email: akatlas@juniper.net Chris Bowers Juniper Networks 1194 N. Mathilda Ave. Sunnyvale, CA 94089 United States Email: cbowers@juniper.net Abishek Gopalan University of Arizona 1230 E Speedway Blvd. Tucson, AZ 85721 United States Email: abishek@ece.arizona.edu