#! /usr/bin/python # -*- coding: utf-8 -*- __author__ = 'Stefano Vissicchio ' # Copyright (C) 2013-2017 by # Stefano Vissicchio # All rights reserved. # BSD license. import networkx as nx import public_utils as md import sys import collections import time import copy ############## # Exceptions # ############## class MaxCPUTimeExceededException(Exception): pass ########### # Factory # ########### class GpiaFactory(): def __init__(self,algorithm='standard'): self.pool = dict() self.algorithm = algorithm self.__init_pool__() def __init_pool__(self): self.pool['fu2fu'] = FUGpia() self.pool['fu2fa'] = FAAndFUGpia() fa2fuGpia = FAAndFUGpia() fa2fuGpia.set_fa2fu() self.pool['fa2fu'] = fa2fuGpia self.pool['fa2fa'] = FAGpia() def get_Gpia(self,reconfig_type): pool_key = reconfig_type + "_" + self.algorithm if pool_key not in self.pool: raise Exception("Unknown Reconfiguration Type (%s) or Algorithm (%s)!" %(reconfig_type,self.algorithm)) return self.pool[pool_key] ################################ # Generic (Abstract) Algorithm # ################################ class Gpia: def __init__(self): self.verbose = 0 self.max_cpu_time = 60*60*24 self.migrated_nodes = set() self.unsafe_destinations = set() self.unsafe_dests2nodes = {} ### support functions ### def set_verbose(self,level): self.verbose = level def set_max_cpu_time(self, t): self.max_cpu_time = t def detect_path_inconsistency(self, current, init, final): for path in current: if path not in init and path not in final: return True return False def compute_changing_nodes(self,nh_init,nh_final,destinations): changing = dict() for d in destinations: changing[d]=set([]) for n in nh_init[d]: if n not in nh_final[d]: print "Strangeness: node %s in nh_init but not in nh_final" %(n) elif nh_init[d][n] != nh_final[d][n]: changing[d].add(n) return changing def build_actual_graph(self,nh_function,d): g = nx.DiGraph() for i in nh_function[d]: if i == d: continue for s in nh_function[d][i]: g.add_edge(i,s) return g def build_actual_paths(self,nh_function,destinations,mode="dfs"): real_fn = getattr(self, "_build_actual_paths_" + mode) if callable(real_fn): return real_fn(nh_function,destinations) def _build_actual_paths_dfs(self,nh_function,destinations, precomputed_paths={}, prune_d_n=lambda x,y: False): paths = copy.deepcopy(precomputed_paths) for d in destinations: paths.setdefault(d, {d: set([d])}) completed = set([d]) visited = set([d]) graph = self.build_actual_graph(nh_function, d) stack = [] if nx.is_directed_acyclic_graph(graph) and d in graph.nodes(): for n in graph.nodes(): if n not in visited and not(prune_d_n(d,n)): stack.append(n) while len(stack) > 0: peek = stack.pop() if isinstance(peek, list): (string, node) = peek paths[d].setdefault(node, set([])) for n2 in graph[node].keys(): paths_list = set(map(lambda x: node + ' ' + x, paths[d][n2])) paths[d][node].update(paths_list) completed.add(node) else: node = peek visited.add(node) stack.append(["Finished", node]) for n2 in graph[node].keys(): if n2 not in visited and not(prune_d_n(d,n2)): stack.append(n2) else: #there is a loop paths[d] = {d: set([d])} return paths def _build_actual_paths_networkx(self,nh_function,destinations): paths = dict([]) for d in destinations: paths[d] = dict() graph = self.build_actual_graph(nh_function, d) if nx.is_directed_acyclic_graph(graph) and d in graph.nodes(): for n in graph.nodes(): all_paths_strings = map(lambda x: " ".join(x), nx.all_simple_paths(graph,n,d)) paths[d][n] = set(all_paths_strings) else: #there is a loop pass paths[d][d] = set([d]) return paths ### main algorithm ### def compute_sequence(self,graph,nh_init,nh_final,destinations): seq = self._compute_sequence(graph,nh_init,nh_final,destinations,set([])) self._store_unsafe_node_destinations(self,graph,nh_init,nh_final,seq,destinations) return seq def _store_unsafe_node_destinations(self,graph,nh_init,nh_final,seq,destinations): self.migrated_nodes = set(seq) non_migrated = set(graph.nodes()).difference(seq) self.unsafe_destinations = set() self.unsafe_dests2nodes = {} for d in destinations: self.unsafe_dests2nodes[d] = set() for n in non_migrated: if not self.check_NSC_timeout(n,graph,nh_init,nh_final,[d],set(seq)): self.unsafe_destinations.add(d) if nh_init[d][n]!= nh_final[d][n]: self.unsafe_dests2nodes[d].add(n) if len(self.unsafe_dests2nodes[d]) == 0: self.unsafe_dests2nodes.pop(d) def _update_data_structures(self,graph,nh_init,nh_final,destinations,migrated): pass def _evaluate_candidates(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates): # try to build the sequence with different candidates by using recursion seq = [] for n in candidates: seq = self._evaluate_candidate(graph,nh_init,nh_final,destinations,migrated,non_migrated,n) if len(seq) == len(non_migrated): break if self.verbose >= 1: print "backtracking on %s" %(n) return seq def _evaluate_candidate(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,n): sequence = [] if self.verbose >= 1: print "migrating %s" %(n) new_migrated = set(migrated) new_migrated.add(n) tail = self._compute_sequence(graph,nh_init,nh_final,destinations,new_migrated) if self.verbose >= 1: print "growing sequence: %s" %(tail) sequence = [n] + tail if len(tail) == len(non_migrated)-1: return sequence return sequence def _compute_sequence(self,graph,nh_init,nh_final,destinations,migrated): nodes = set(graph.nodes()) non_migrated = set(nodes).difference(migrated) candidates = set(non_migrated) self._update_data_structures(graph,nh_init,nh_final,destinations,migrated) new_candidates = set(candidates) for n in candidates: if not self.check_NSC_timeout(n,graph,nh_init,nh_final,destinations,migrated): new_candidates.remove(n) candidates = new_candidates if self.verbose >= 1: print "\nstill to be migrated " + str(non_migrated) print "remaining destinations: " + str(destinations) print "candidates " + str(candidates) if len(candidates) == 0: self.print_report(destinations, migrated, nodes) return self._evaluate_candidates(graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates) def check_NSC_timeout(self,n,nodes,nh_init,nh_final,destinations,migrated): if time.clock() > self.max_cpu_time: raise MaxCPUTimeExceededException("Exceeded %d seconds of CPU time" %(self.max_cpu_time)) return self.check_NSC(n,nodes,nh_init,nh_final,destinations,migrated) def check_NSC(self,n,nodes,nh_init,nh_final,destinations,migrated): raise Exception("Abstract Method: check_NSC in class Gpia") def print_report(self, destinations, migrated, nodes): print "%s %d destinations, %d / %d routers CAN be safely migrated ( %.2f %%)" %( self.__class__.__name__.ljust(15), len(destinations), len(migrated), len(nodes), len(migrated)*100./len(nodes)) if self.verbose >= 1: all_nodes = len(nodes) all_migrated = len(migrated) all_left = all_nodes - all_migrated print "total # of routers: %s" %(all_nodes) print "# of routers that CAN be safely migrated: %s" %(all_migrated) print "percentage of routers that CAN be safely migrated: %s" %(all_migrated*100./all_nodes) print "# of routers that CANNOT be safely migrated: %s" %(all_left) print "percentage of routers that CANNOT be safely migrated: %s" %(all_left*100./all_nodes) print "# of remaining destinations: %s" %(len(destinations)) ### other interface functions ### def get_unsafe_destinations(self): return self.unsafe_destinations def get_unsafe_destinations_map(self): return self.unsafe_dests2nodes def get_migrated_nodes(self): return self.migrated_nodes ################### # FU-only updates # ################### class FUGpia(Gpia): def __init__(self): Gpia.__init__(self) self.changing_nodes = dict() self.final_paths = dict() self.current_paths = dict() self.migrated_nodes = set() ### support functions ### def build_current_nh(self,original_graph,migrated,nh_init,nh_final): if self.verbose >= 2: print "building current next-hop function fu" not_migrated = set(original_graph.nodes()).difference(migrated) nh_function = dict() for d in nh_init: nh_function[d] = dict() for n in not_migrated: nh_function[d][n] = nh_init[d][n] for n in migrated: nh_function[d][n] = nh_final[d][n] return nh_function def build_current_paths(self,original_graph,nh_init,nh_final,destinations,migrated): return self.build_actual_paths(self.build_current_nh(original_graph,migrated,nh_init,nh_final),destinations) ### sequence computation functions ### def compute_sequence(self,graph,nh_init,nh_final,destinations): self.changing_nodes = self.compute_changing_nodes(nh_init,nh_final,destinations) self.final_paths = self.build_actual_paths(nh_final,destinations) self.initial_paths = self.build_actual_paths(nh_init,destinations) seq = self._compute_sequence(graph,nh_init,nh_final,destinations,[]) self._store_unsafe_node_destinations(graph,nh_init,nh_final,self.migrated_nodes,destinations) return seq def _update_data_structures(self,graph,nh_init,nh_final,destinations,migrated): self.current_paths = self.build_current_paths(graph,nh_init,nh_final,destinations,migrated) def _evaluate_candidates(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates): seq = [] if len(candidates) > 0: seq = self._evaluate_candidate(graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates.pop()) return seq def _add_migration_step(self,candidates,seq,migrated_set): #### migrate all the nodes in a candidate set altogether #### migrated_set = migrated_set.union(candidates) seq.append(candidates) if self.verbose >= 2: print "DEBUG: migrating %s" %(candidates) return (seq,migrated_set) def _compute_sequence(self,graph,nh_init,nh_final,destinations,migrated,seq=None): nodes = set(graph.nodes()) num_nodes = len(nodes) if seq == None: seq = migrated[:] migrated_set = set(migrated) while len(migrated_set) < num_nodes: non_migrated = set(nodes).difference(migrated_set) candidates = set(non_migrated) self._update_data_structures(graph,nh_init,nh_final,destinations,migrated_set) if self.verbose >= 1: print "\nstill to be migrated " + str(non_migrated) print "remaining destinations: " + str(destinations) print "candidates " + str(candidates) new_candidates = set(candidates) for n in candidates: if not self.check_NSC_timeout(n,graph,nh_init,nh_final,destinations,migrated_set): new_candidates.remove(n) if self.verbose >= 2: print "DEBUG: removed %s from candidates" %(n) candidates = list(new_candidates) if len(candidates) == 0: break (seq,migrated_set) = self._add_migration_step(candidates,seq,migrated_set) self.migrated_nodes = migrated_set self.print_report(destinations, migrated_set, nodes) return seq def check_NSC(self,n,graph,nh_init,nh_final,destinations,migrated): for d in destinations: if n == d: continue if n in self.changing_nodes[d]: for path in self.final_paths[d][n]: for s in path.split()[1:]: if s in self.changing_nodes[d] and s not in migrated: if self.verbose > 1: print "Node %s, destination %s: condition 1 violated because of node %s" %(n,d,s) return False for m in self.changing_nodes[d]: for path in self.current_paths[d][m]: if m!= n and n in path.split(): if self.verbose > 1: print "Node %s, destination %s: condition 2 violated because of node %s" %(n,d,m) if self.verbose > 2: print "DEBUG: nh_init=%s, nh_final=%s" %(nh_init[d][m], nh_final[d][m]) print "DEBUG: CPATHS=%s" %(self.current_paths[d][m]) print "DEBUG: IPATHS=%s" %(self.initial_paths[d][m]) print "DEBUG: FPATHS=%s" %(self.final_paths[d][m]) print "DEBUG_CANDIDATE: nh_init=%s, nh_final=%s" %(nh_init[d][n], nh_final[d][n]) return False return True ### other interface functions ### def get_migrated_nodes(self): return self.migrated_nodes ######################## # FA-involving updates # ######################## class FAAndFUGpia(Gpia): def __init__(self): Gpia.__init__(self) self.changing_nodes = dict() self.cones = dict() self.current_paths_cone = dict() self.current_paths_outside = dict() self.fu2fa = False self.iterations = 0 self.cutting_iteration = sys.maxint ### support functions ### def build_fa_cone(self,graph,preferring_fa,dest): preferring_fu = set(graph.nodes()).difference(preferring_fa) if dest in preferring_fu: preferring_fu.remove(dest) f = graph.copy() f.remove_nodes_from(preferring_fu) dest_component = None for c in nx.connected_components(f): if dest in c: dest_component = c break return nx.subgraph(graph,dest_component) def compute_outside_paths(self,graph,cone,d): ideal_paths = md.single_destination_dijkstra_ecmp_paths(graph,d) out_paths = dict() for n in set(graph.nodes()).difference(set(cone.nodes())): curr_paths = [] for path_outside in ideal_paths[n]: path_array = [] for m in path_outside.split(): if m in cone.nodes(): break path_array.append(m) for path_inside in self.current_paths_cone[d][m]: path_array2 = path_array[:] path_array2.extend(path_inside.split()) curr_paths.append(" ".join(path_array2)) out_paths[n] = set(curr_paths[:]) return out_paths def compute_entire_outside_paths(self,graph,cone,cone_paths,d): ideal_paths = md.single_destination_dijkstra_ecmp_paths(cone,d) out_paths = dict() for n in set(graph.nodes()).difference(set(cone.nodes())): curr_path = '' if not ideal_paths.has_key(n): # there should be a loop continue for m in ideal_paths[n]: if m in cone.nodes(): break curr_path.append(m) out_paths[n] = curr_path + " " + cone_paths[d][m] return out_paths ### main functions ### def _update_data_structures(self,graph,nh_init,nh_final,destinations,migrated): preferring_fa = set(migrated) if not self.fu2fa: preferring_fa = set(graph.nodes()).difference(migrated) for d in destinations: cone = self.build_fa_cone(graph,preferring_fa,d) self.cones[d] = cone self.current_paths_cone[d] = dict() self.current_paths_cone[d] = md.single_destination_dijkstra_ecmp_paths(cone,d) self.current_paths_outside[d] = self.compute_outside_paths(graph,cone,d) def compute_sequence(self,graph,nh_init,nh_final,destinations): self.changing_nodes = self.compute_changing_nodes(nh_init,nh_final,destinations) self.initial_paths = self.build_actual_paths(nh_init,destinations) self.final_paths = self.build_actual_paths(nh_final,destinations) self.iterations = 0 seq = self._compute_sequence(graph,nh_init,nh_final,destinations,set([])) self._store_unsafe_node_destinations(graph,nh_init,nh_final,seq,destinations) pseq = [] for e in seq: pseq.append(set([e])) return pseq def check_NSC(self,n,graph,nh_init,nh_final,destinations,migrated): # add n to migrated and check if any router exhibits a traffic shift tentative = set(migrated) tentative.add(n) preferring_fa = set(tentative) if not self.fu2fa: preferring_fa = set(graph.nodes()).difference(tentative) current_paths = dict() for d in destinations: cone = self.build_fa_cone(graph,preferring_fa,d) current_paths[d] = dict() self.current_paths_cone[d] = md.single_destination_dijkstra_ecmp_paths(cone,d) current_paths[d] = self.current_paths_cone[d] current_paths[d].update(self.compute_outside_paths(graph,cone,d)) for d in destinations: if current_paths == set(['']): #in case of loops raise Exception("Loop with FA") return False for r in graph.nodes(): if not current_paths[d].has_key(r) or len(current_paths[d][r])==0: #in case of loops raise Exception("Loop with FA for d=%s and r=%s" %(d,r)) return False if self.detect_path_inconsistency(current=current_paths[d][r], init=self.initial_paths[d][r], final=self.final_paths[d][r]): if self.verbose >= 2: print "candidate %s failed for %s to destination %s" %(n,r,d) print "CPATHS=%s" %(current_paths[d][r]) print "IPATHS=%s" %(self.initial_paths[d][r]) print "FPATHS=%s" %(self.final_paths[d][r]) return False return True def _evaluate_candidates(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates): #### to run tests cutting the backtrack at a given depth #### need_backtrack = self.iterations < self.cutting_iteration self.iterations += 1 if need_backtrack: seq = self._evaluate_candidates_with_backtrack(graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates) else: seq = self._evaluate_candidates_no_backtrack(graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates) return seq def _evaluate_candidates_with_backtrack(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates): max_seq = [] for n in candidates: seq = self._evaluate_candidate(graph,nh_init,nh_final,destinations,migrated,non_migrated,n) if len(seq) == len(non_migrated): max_seq = seq if self.verbose >= 2: print "new max seq: %s" %(max_seq) break if len(seq) > len(max_seq): max_seq = seq if self.verbose >= 2: print "new max seq: %s" %(max_seq) if self.verbose >= 1: print "backtracking on %s" %(n) return max_seq def _evaluate_candidates_no_backtrack(self,graph,nh_init,nh_final,destinations,migrated,non_migrated,candidates): seq = [] if len(candidates) > 0: m = candidates.pop() self.migrated_nodes.add(m) seq = self._evaluate_candidate(graph,nh_init,nh_final,destinations,migrated,non_migrated,m) return seq ### other interface functions ### def get_migrated_nodes(self): return self.migrated_nodes def set_fu2fa(self): self.fu2fa = True def set_fa2fu(self): self.fu2fa = False #################### # FA -> FA updates # #################### class FAGpia(Gpia): def __init__(self): Gpia.__init__(self) self.initial_paths = dict() self.final_paths = dict() self.current_paths = dict() def get_subfunction(self,current_nh,nodes): subfunction = dict() for d in current_nh: for n in nodes: subfunction[d][n] = current_nh[d][n] return subfunction # an alternative is to progressively update the FA-cones each time a router is migrated def build_fa_cones(self,graph,migrated,dest): list_cone_init = [dest] list_cone_final = [dest] queue = [dest] visited = dict() visited[dest] = 1 while queue: next = queue.pop(0) # assing next to a FA-cone if possible assigned = False if next in migrated: for n in graph.neighbors(next): if n in list_cone_final: list_cone_final.insert(0,next) visited[next] = 1 assigned = True # if next has a neighbor not assigned yet to any FA-cone, do not assign next as well elif n not in list_cone_init: assigned = True # if next has only neighbors in the initial cone, put next in the initial cone as well if not assigned: list_cone_init.insert(0,next) visited[next] = 1 else: for n in graph.neighbors(next): if n in list_cone_init: list_cone_init.insert(0,next) visited[next] = 1 assigned = True # if next has a neighbor not assigned yet to any FA-cone, do not assign next as well elif n not in list_cone_final: assigned = True # if next has only neighbors in the initial cone, put next in the initial cone as well if not assigned: list_cone_final.insert(0,next) visited[next] = 1 # add neighbors to the queue for nei in graph.neighbors(next): if not visited.has_key(nei): queue.append(nei) cone_init = graph.subgraph(list_cone_init) cone_final = graph.subgraph(list_cone_final) return (cone_init,cone_final) def build_actual_paths(self,cone,d): return md.single_destination_dijkstra_ecmp_paths(cone,d) def _update_data_structures(self,graph,nh_init,nh_final,destinations,migrated): for d in destinations: (self.cone_init_fa,self.cone_final_fa) = self.build_fa_cones(graph,migrated,d) self.current_paths[d] = dict() self.current_paths[d] = self.build_actual_paths(cone_init_fa,d) self.current_paths[d].update(self.build_actual_paths(cone_final_fa,d)) def compute_sequence(self,graph,nh_init,nh_final,destinations): self.initial_paths = self.build_actual_paths(nh_init,destinations) self.final_paths = self.build_actual_paths(nh_final,destinations) return self._compute_sequence(graph,nh_init,nh_final,destinations,set([])) def check_NSC(self,n,graph,nh_init,nh_final,destinations,migrated): for d in destinations: if self.current_paths[d][n] != self.initial_paths[d][n] and self.current_paths[d][n] != self.final_paths[d][n]: return False return True