# Copyright (c) 2015, Juniper Networks, Inc.

# All rights reserved.

#

# Redistribution and use in source and binary forms, with or without

# modification, are permitted provided that the following conditions are met:

# * Redistributions of source code must retain the above copyright

# notice, this list of conditions and the following disclaimer.

# * Redistributions in binary form must reproduce the above copyright

# notice, this list of conditions and the following disclaimer in the

# documentation and/or other materials provided with the distribution.

# * Neither the name of the Juniper Networks nor the

# names of its contributors may be used to endorse or promote products

# derived from this software without specific prior written permission.

#

# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND

# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

# DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY

# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

# This program has been tested to run on Python 2.6 and 2.7

# (specifically Python 2.6.6 and 2.7.8 were tested).

# The program has known incompatibilities with Python 3.X.

# When executed, this program will generate a text file describing

# an example topology. It then reads that text file back in as input

# to create the example topology, and runs the MRT algorithm.This

# was done to simplify the inclusion of the program as a single text

# file that can be extracted from the IETF draft.

# The output of the program is four text files containing a description

# of the GADAG, the blue and red MRTs for all destinations, and the

# MRT alternates for all failures.

import random

import os.path

import heapq

# simple Class definitions allow structure-like dot notation for

# variables and a convenient place to initialize those variables.

class Topology:

self.named_proxy_dict = {}

class Node:

self.alt_list = []

class Interface:

self.PROCESSED = False

class Bundle:

self.INCOMING = False

class Alternate:

self.info = 'NONE'

class Proxy_Node_Attachment_Router:

self.nh_intf_list = []

class Named_Proxy_Node:

self.alt_dict = {}

def Interface_Compare(intf_a, intf_b):

return 0

def Sort_Interfaces(topo):

for node in topo.island_node_list:

node.island_intf_list.sort(Interface_Compare)

def Reset_Computed_Node_and_Intf_Values(topo):

intf.init_new_computing_router()

# This function takes a file with links represented by 2-digit

# numbers in the format:

# 01,05,10

# 05,02,30

# 02,01,15

# which represents a triangle topology with nodes 01, 05, and 02

# and symmetric metrics of 10, 30, and 15.

# Inclusion of a fourth column makes the metrics for the link

# asymmetric. An entry of:

# 02,07,10,15

# creates a link from node 02 to 07 with metrics 10 and 15.

def Create_Topology_From_File(filename):

return topo

def MRT_Island_Identification(topo, computing_rtr, profile_id, area):

explore_list.append(intf.remote_node)

def Compute_Island_Node_List_For_Test_GR(topo, test_gr):

topo.island_node_list_for_test_gr.append(node)

def Set_Island_Intf_and_Node_Lists(topo):

node.island_intf_list.append(intf)

global_dfs_number = None

def Lowpoint_Visit(x, parent, intf_p_to_x):

x.lowpoint_parent_intf = intf

def Run_Lowpoint(topo):

global global_dfs_number

global_dfs_number = 0

Lowpoint_Visit(topo.gadag_root, None, None)

max_block_id = None

def Assign_Block_ID(x, cur_block_id):

Assign_Block_ID(c, cur_block_id)

def Run_Assign_Block_ID(topo):

global max_block_id

max_block_id = 0

Assign_Block_ID(topo.gadag_root, max_block_id)

def Construct_Ear(x, stack, intf, ear_type):

stack.append(y)

def Construct_GADAG_via_Lowpoint(topo):

Construct_Ear(x, stack, intf, 'NEIGHBOR')

def Assign_Remaining_Lowpoint_Parents(topo):

node.lowpoint_number = node.dfs_parent.dfs_number

def Add_Undirected_Block_Root_Links(topo):

intf3.remote_intf.OUTGOING = True

def Modify_Block_Root_Incoming_Links(topo):

intf.remote_intf.OUTGOING_STORED = True

def Revert_Block_Root_Incoming_Links(topo):

intf.remote_intf.OUTGOING_STORED = False

def Run_Topological_Sort_GADAG(topo):

Revert_Block_Root_Incoming_Links(topo)

def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):

intf.remote_intf.UNDIRECTED = False

def Initialize_Temporary_Interface_Flags(topo):

intf.OUTGOING_STORED = False

def Add_Undirected_Links(topo):

Set_Other_Undirected_Links_Based_On_Topo_Order(topo)

def In_Common_Block(x,y):

return False

def Copy_List_Items(target_list, source_list):

del target_list[:] # Python idiom to remove all elements of a list

for element in source_list:

target_list.append(element)

def Add_Item_To_List_If_New(target_list, item):

if item not in target_list:

target_list.append(item)

def Store_Results(y, direction):

Copy_List_Items(y.collapsed_next_hops, y.next_hops)

# Note that the Python heapq fucntion allows for duplicate items,

# so we use the 'spf_visited' property to only consider a node

# as min_node the first time it gets removed from the heap.

def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction):

intf.remote_node.next_hops,nh_intf)

def Normal_SPF(topo, spf_root):

intf.remote_node.next_hops,nh_intf)

def Set_Edge(y):

y.order_proxy = y.localroot.order_proxy

def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x):

Set_Edge(y)

def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x):

y.red_next_hops)

def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x):

Copy_List_Items(x.alt_dict[y.node_id], y.alt_list)

def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x):

for y in topo.node_list:

x.pnh_dict[y.node_id] = []

Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)

def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):

P.red_next_hops)

def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x):

P.alt_list)

def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):

P.primary_next_hops)

def Select_Alternates_Internal(D, F, primary_intf,

return 'USE_RED'

def Select_Alternates(D, F, primary_intf):

D_lower, D_higher, D_topo_order)

def Is_Remote_Node_In_NH_List(node, intf_list):

return False

def Select_Alts_For_One_Src_To_Island_Dests(topo,x):

D.alt_list.append(alt)

def Write_GADAG_To_File(topo, file_prefix):

gadag_file.write(edge_string);

def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix):

mrt_file.write(edge_string);

def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix):

Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix)

Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix)

def Write_Alternates_For_All_Dests_To_File(topo, file_prefix):

alt_file.write(edge_string);

def Raise_GADAG_Root_Selection_Priority(topo,node_id):

node = topo.node_dict[node_id]

node.GR_sel_priority = 255

def Lower_GADAG_Root_Selection_Priority(topo,node_id):

node = topo.node_dict[node_id]

node.GR_sel_priority = 128

def GADAG_Root_Compare(node_a, node_b):

return -1

def Set_GADAG_Root(topo,computing_router):