DFS 是一个递归算法,就算额外建立堆栈,本质上处理数据的规则和利用的 空间大小是依旧不变的。它的空间复杂度无论选择哪种方式,都是 O ( N ) (N 为节点数)。而 DFS 计算路径几乎是遍历全图输出路径,因此其耗费的时间受存 储拓扑信息的结构决定。 因此 DFS 选择两种实现方式在效率上没有差异。但就代码长度来说,第二种实现方式更为简洁明了并且简短。因此在实现的过程中本文选择第二种方法。
变量说明
符号
含义
u
当前检索的交换机
i
与 u 有相连边的邻接交换机
dst
目标终点主机对应的交换机
visited
用于标记交换机的变量
cur_path
i 和 u 之间的路径,一个边
allpaths
所有可行路径的集合
DFS实现
(一)获得邻居节点
1 2 3 4 5 6 7 8 9
#获得邻居节点 defget_adjacent(self,links): adjacent = {} for switch in self.switches: adjacent.setdefault(switch,[]) #初始化字典 for switch in self.switches: for link in links: if link['src_dpid'] == switch: adjacent[switch].append(link['dst_dpid']) #作为源交换机时添加目的交换机
(二)使用 DFS 寻找源宿全部路径
1 2 3 4 5 6 7 8 9 10 11 12 13
defDFS(self,u,dst,visited,cur_path,allpaths): #根据传过来的源主机和目的主机来探索最短路,采用递归方法 adjacent = self.get_adjacent(self.links) if u ==dst: allpaths.append(cur_path.copy()) return else: for i in adjacent[u]: if visited[i] == 0: visited[i] = 1 cur_path.append(i) self.DFS(i,dst,visited,cur_path,allpaths) cur_path.pop() visited[i] = 0
(三)计算路径上的时延
1 2 3 4 5 6 7 8 9
defsum_delay(self,all_path,links): sum_delay = [0]*len(all_path) #时延列表初始化 for i inrange(len(all_path)): #分别计算每一条路径上的时延并储存在 sum_delay 列表中,作为返回值返回 path = all_path[i] for j inrange(len(path)-1): for link in links: if (link['src_dpid'] == path[j]) and (link['dst_dpid'] == path[j+1]): sum_delay[i] += int(link['delay']) return sum_dela
if dst in self.mac_to_port[dpid]:#目的主机地址在 mac_to_port 表中 if src notin self.host_mac_to.keys(): self.host_mac_to[src]=(dpid,in_port)#若源主机地址不在 host_mac_to 表中,则在该表中增加这一项 if dst,src in self.host_mac_to.keys():#如果目的主机和源主机 mac 地址在host_mac_to 表中,则读取主机和交换机之间的链路 src_switch=self.host_mac_to[src][0] first_port=self.host_mac_to[src][1] dst_switch=self.host_mac_to[dst][0] final_port=self.host_mac_to[dst][1] path=self.search_path(src_switch,dst_switch,first_port,final_port)#寻找路径 self.configure_path(path,src,dst,datapath)#配置路径
#发流表 out_port=self.mac_to_port[dpid][dst] actions=[ofp_parser.OFPActionOutput(out_port)] match=ofp_parser.OFPMatch(in_port=in_port,eth_dst=dst,eth_src=src) self.add_flow(datapath,1,match,actions) else: if src notin self.host_mac_to.keys(): self.host_mac_to[src]=(dpid,in_port) actions=[] for port in datapath.ports: if(port notin self.banport[dpid]) and (port != in_port): actions.append(ofp_parser.OFPActionOutput(port))