while run != src_mac: for neighbor in self.adjacent[run]: nodeinfo.setdefault(neighbor, {}) nodeinfo[neighbor].setdefault('height', 9999999) nodeinfo[neighbor].setdefault('unchecked', 1) nodeinfo[neighbor].setdefault('father', -1) for link in self.links: if link['src_dpid'] == run and link['dst_dpid'] == neighbor: if nodeinfo[neighbor]['height'] > nodeinfo[run]['height']+1and rest[link['dst_dpid']][link['src_dpid']] > 0:#防止成环,以及发现路径 nodeinfo[neighbor]['height'] = nodeinfo[run]['height']+1#跳数加一 nodeinfo[neighbor]['father'] = run#更新父节点 break#update 操作 #寻找最短跳数 min_height = 99999 for new_run in nodeinfo.keys(): if nodeinfo[new_run]['unchecked'] and nodeinfo[new_run]['height'] < min_height: min_height = nodeinfo[new_run]['height'] run = new_run if nodeinfo[run]['unchecked']: nodeinfo[run]['unchecked'] = 0 else: break
(3)跳数最短路重建,并返回跳数最短路和该路径上的流量
1 2 3 4 5 6 7 8 9 10 11
if nodeinfo[src_mac]['unchecked']: #到最后 src_mac 也没有被检查到,则说明已经没有增广路径了,返回值为空 return [], 0 else: #有增广路径则按正序重建路径,并返回路径和路径上的流量 father = src_mac path = [] while father != dst_mac: path.append(father) father = nodeinfo[father]['father'] path.append(dst_mac) path_bw = self.min_bw(path, rest) #调用函数,求路径上的流量 return path, path_bw
rest = self.update_network([], 0, flow) for link in self.links: #建立剩余网络的框架 flow.setdefault(link['src_dpid'], {}) flow[link['src_dpid']].setdefault(link['dst_dpid'], 0)
defupdate_network(self, cur_path, cur_bw, flow): p = cur_path for i inrange(0, len(p)-1): if flow[p[i]][p[i+1]] == 0and flow[p[i+1]][p[i]] == 0:#尚未开始增加流量 flow[p[i]][p[i+1]] = cur_bw#将所选择的路径流量加入流网络 elif flow[p[i+1]][p[i]] > 0and flow[p[i]][p[i+1]] == 0:#边上正向的流量为0,有反向的流量 flow[p[i+1]][p[i]] -= cur_bw#发生流量抵消 self.cancel_flag = 1#流量抵消的标记位 else: flow[p[i]][p[i+1]] += cur_bw#将所选择的路径上流量加入流网络 rest = deepcopy(flow) for link in self.links:#构建剩余网络 if flow[link['src_dpid']][link['dst_dpid']] == 0and flow[link['dst_dpid']][link['src_dpid']] == 0:#边上没有流量,剩余容量即为边的带宽 rest[link['src_dpid']][link['dst_dpid']] = link['bw'] rest[link['dst_dpid']][link['src_dpid']] = link['bw'] if flow[link['dst_dpid']][link['src_dpid']] > 0and flow[link['src_dpid']][link['dst_dpid']] == 0:#边上反向有流量、正向没有流量 rest[link['src_dpid']][link['dst_dpid']] = flow[link['dst_dpid']][link['src_dpid']]#添加反向边 rest[link['dst_dpid']][link['src_dpid']] = link['bw'] - flow[link['dst_dpid']][link['src_dpid']]#边上反向的剩余容量为边的容量减去流量 return rest
读取邻接点
1 2 3 4 5 6 7
defget_adjacent(self, links): adjacent = {} for link in links: adjacent.setdefault(link['src_dpid'], []) adjacent[link['src_dpid']].append(link['dst_dpid']) return adjacent
找到路径上链路容量的最小值,即能够容纳的最大流量
1 2 3 4 5 6
defmin_bw(self, path, rest): bw = 999999 for i inrange(0, len(path)-1): if rest[path[i]][path[i+1]] < bw: bw = rest[path[i]][path[i+1]] return bw
对 packet_in 模块的修改
(1)将主机和交换机之间的链路加入拓扑网络
1 2 3 4 5 6 7 8 9 10 11 12 13 14
if src notin self.hosts: self.hosts.append(src) fd = open('./topo24.json', "r") topoinfo = json.load(fd) host_id = int(src.split(':')[-1],16) for edge in topoinfo['links']: if (['h'+str(host_id), 's'+str(dpid)] == edge['vertexs'] or ['s'+str(dpid), 'h'+str(host_id)] == edge['vertexs']): self.links.append({'src_dpid':src, 'dst_dpid':dpid, 'dst_port_no': in_port, 'delay':edge['delay'], 'bw':edge['bw']})