项目要求 配置一个广播通信业务,假设主机0 向所有其它主机进行广播。 使用Kruskal 算法计算广播使用的最小生成树。 将广播业务在可视化平台上进行展示。 基本原理 Kruskal 算法 最小生成树概念 引入一个实际问题:要在n 个城市中建立一个通信网络,则连通这n 个城市需要布置n-1 一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网?
将问题抽象出来,即n 个城市就是图上的n 个顶点,然后,边表示两个城市的通信线路,每条边上的权重就是我们搭建这条线路所需要的成本,所以现在我们有n 个顶点的连通网可以建立不同的生成树,每一颗生成树都可以作为一个通信网,当我们构造这个连通网所花的成本最小时,搭建该连通网的生成树,就称为最小生成树。
具体概念:在一给定的无向图G = (V, E) 中,( u , v ) (u,v) ( u , v ) 代表连接顶点u 与顶点v 的边,而 ω ( u , v ) \omega (u,v) ω ( u , v ) 代表此边的权重,若存在 t 为 E 的子集且为无循环图,使得ω ( t ) = ∑ ( u , v ) ∈ t ω ( u , v ) \omega (t) = \sum_{(u,v)\in t}^{} \omega (u,v) ω ( t ) = ∑ ( u , v ) ∈ t ω ( u , v ) 的ω ( t ) \omega (t) ω ( t ) 最小,则此T 为G 的最小生成树(最小权重生成树)。
基本思想 将所有边按照权值的大小进行升序排序,然后从小到大一一判断,条件为:如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分;反之,舍去。直到具有n 个顶点的连通网筛选出来n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
关键点 Kruskal 算法基本分为排序和成环检测两大环节,其中排序算法发展多年,已经将其复杂度压榨到了很小,尤其对于非线性时间比较类排序,其时间复杂度更是不能突破nlogn。
因此,kruskal 算法的关键点在于成环检测算法的优化。
最直接的实现方式是将图用邻接链表存储,调用广度优先算法(Breadth First Search,BFS),如果遍历到向相同的点,则说明有环,否则说明无环。引入新的数据结构——UNION-FIND,主要操作是UNION(C i C_i C i ,C j C_j C j ):将集合C i C_i C i 和C j C_j C j 合并为一个集合,并用FIND(x)返回元素x 所在集合的名字,记为leader。若一条边的两顶点的leader 不同,说明该边是一条割边,即不会成环。
拓扑可视化 可视化思路 利用mininet 的net 操作打印出所读取的拓扑的网络节点关系信息,并且修改mininet 文件中的相关代码使得net 操作打印出的信息能直接进入用于存储信息的txt 文件中。之后利用python 中的networkx 库读取txt 文件内容并且利用Matplotlib 的绘图功能即可画出相应的拓扑图。
NetworkX 原理 NetworkX 是一款python 的软件包,它内置了常用的图和网络分析算法。但是在本项目中我们只使用它的创建简单图(有向图或无向图)的功能,再导入Matplotlib 的绘图接口绘出所需拓扑图的图像。
代码实现 拓扑建立 主体代码 1 2 3 4 5 6 7 8 9 10 11 with open ("topo24.json" ,'r' ) as load_f: topoinfo=json.load(load_f) for h in range (1 , topoinfo["host_no" ]+1 ): self.addHost("h" +str (h)) for s in range (1 , topoinfo["switch_no" ]+1 ): self.addSwitch("s" +str (s)) for i in range (0 ,17 ): self.addLink(topoinfo["links" ][i]["vertexs" ][0 ],topoinfo["links" ][i]["vertexs" ][1 ],delay=str (topoinfo["links" ][i]["delay" ])+'ms' ,bw=int (topoinfo["links" ][i]["bw" ]))
读取topo24.json 文件里的信息,存入topoinfo 中。通过addHost 读取并存储主机信息,通过addSwitch 读取并存储交换机信息,通过addLink 读取交换机和主机之间以及交换机之间的连接信息和时延带宽信息。
库函数说明 1 2 3 4 5 6 7 8 from mininet.topo import Topo from mininet.net import Mininet from mininet.node import CPULimitedHost from mininet.link import TCLink from mininet.util import dumpNodeConnections from mininet.log import setLogLevel import osimport json
其中sys 和os 都是python 的系统操作模块,sys 提供了一组非常实用的服务,os 模块负责程序和操作系统的交互,提供了访问操作系统底层的接口。json 提供了读取json 文件的方法。
RYU通信 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Kruskaltest (app_manager.RyuApp): OFP_VERSIONS=[ofproto_v1_3.OFP_VERSION] def __init__ (self,*args,**kwargs ): super (Kruskaltest,self).__init__(*args,**kwargs) self.mac_to_port={} self.topology_api_app=self self.sleep_interval = 0.5 self.switches = [] self.links = [] self.mst_links = [] self.pathes = {} self.banport = {}
流表配置 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 @set_ev_cls(ofp_event.EventOFPSwitchFeatures,CONFIG_DISPATCHER ) def switch_features_handler (self,ev ): datapath=ev.msg.datapath ofproto=datapath.ofproto ofp_parser=datapath.ofproto_parser match =ofp_parser.OFPMatch() actions=[ofp_parser.OFPActionOutput(ofproto.OFPP_CONTROLLER,ofproto.OFPCML_NO_BUFFER)] self.add_flow(datapath,0 ,match ,actions) def add_flow (self,datapath,priority,match ,actions ): ofproto=datapath.ofproto ofp_parser=datapath.ofproto_parser inst=[ofp_parser.OFPInstructionActions(ofproto.OFPIT_APPLY_ACTIONS,actions)] mod=ofp_parser.OFPFlowMod(datapath=datapath,priority=priority,match =match ,instructions=inst) datapath.send_msg(mod)
拓扑发现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 @set_ev_cls(event.EventSwitchEnter,[CONFIG_DISPATCHER,MAIN_DISPATCHER] ) def switch_enter_handler (self,ev ): print ('==================================' ) print ('switch entered...' ) self.switches,self.links = self.get_topology() self.banport = self.find_banport(self.links[:]) for link in self.mst_links: print ("{} {}" .format (link['src_dpid' ],link['dst_dpid' ])) print ('==================================' ) time.sleep(self.sleep_interval) def get_topology (self ): switch_list = get_switch(self.topology_api_app,None ) switches = [switch.dp.id for switch in switch_list] print ('switches:{}' .format (switches)) for switch in switches: self.banport.setdefault(switch,[]) print ('------------------------------------' ) print ("banport first_list is{}" .format (self.banport)) link_list = get_link(self.topology_api_app,None ) links = [{'src_dpid' :link.src.dpid,'src_port_no' :link.src.port_no,'dst_dpid' :link.dst.dpid,'dst_port_no' :link.dst.port_no} for link in link_list] print ("the getted link_list is{}" .format (links)) file = open ("./topo7.json" ,"r" ) topoinfo = json.load(file) for link in links: for edge in topoinfo['links' ]: if (["s" +str (link["src_dpid" ]),"s" +str (link["dst_dpid" ])] == edge["vertexs" ] or ["s" +str (link["dst_dpid" ]),"s" +str (link["src_dpid" ])] == edge["vertexs" ]): link['delay' ] = edge['delay' ] break
控制器对收到的数据包的处理 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 @set_ev_cls(ofp_event.EventOFPPacketIn,MAIN_DISPATCHER ) 执行下面的代码 def packet_in_handler (self,ev ): print ("==========================================================" ) print ('it has entered packet_in_handler func' ) msg=ev.msg datapath=msg.datapaths ofproto=datapath.ofproto ofp_parser=datapath.ofproto_parser dpid=datapath.id self.mac_to_port.setdefault(dpid,{}) pkt=packet.Packet(msg.data) eth=pkt.get_protocol(ethernet.ethernet) in_port=msg.match ['in_port' ] print ("in_port is " ,in_port) src = eth.src self.mac_to_port[dpid][src]=in_port dst=eth.dst print ('the src is ' , src) print ('the dst is ' , dst) print ('the dpid is ' , dpid) print ("self.mac_to_port:" , self.mac_to_port) pathes={} if dst in self.mac_to_port[dpid]: print ('dst mac is known' ) 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) print ("add flow" ) self.pathes.setdefault(src,{}) self.pathes[src].setdefault(dst,[]) self.pathes[src][dst].append(dpid) print ("path appending:{}" .format (self.pathes[src][dst])) else : print ('dst mac is unknown' ) print ('the dpid is ' ,dpid) actions=[] for port in datapath.ports: if (port not in self.banport[dpid]) and (port != in_port): actions.append(ofp_parser.OFPActionOutput(port)) out=ofp_parser.OFPPacketOut(datapath=datapath,buffer_id=msg.buffer_id,in_port=in_port,actions=actions,data=msg.data) datapath.send_msg(out)
库函数说明 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from ryu.base import app_manager from ryu.topology.api import get_link,get_switchfrom ryu.base import app_managerfrom ryu.ofproto import ofproto_v1_3 from ryu.controller.handler import set_ev_clsfrom ryu.controller.handler import CONFIG_DISPATCHER,MAIN_DISPATCHER from ryu.lib.packet import packet from ryu.lib.packet import ethernet from ryu.topology import event from ryu.topology.api import get_switch,get_link from ryu.controller import ofp_event import timeimport jsonimport string
kruskal 算法运用 概述 在基于SDN 的实际网络拓扑中,每个交换机和所属主机可以看成一个顶点,各交换机相连接的信道看成一条边,其权重则为每条信道的时延。对于交换机,还有一个重要的属性——端口,即交换机连接其他网络设备的接口。为了洪泛简便,我们采用逆向kruskal 算法的原理,即找出最小生成树不在的端口,记为banport。只要数据包在banport 停止传输,只在允许通行的端口传输,那么一定不会成环,必然是在最小生成树上。
变量说明 代码实现 1 links.sort(key = lambda x:x['delay' ])
对于排序,我们使用python 自带的对列表的排序,将关键字设为delay,即按时延为权重升序排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 group = [[i] for i in range (1 ,len (self.switches)+1 )] for link in links: if link['src_dpid' ]<link['dst_dpid' ]: for i in range (len (group)): if link["dst_dpid" ] in group[i]: m = i if link["src_dpid" ] in group[i]: n = i if m == n and link['dst_port_no' ] not in banport[link["dst_dpid" ]]: banport[link["dst_dpid" ]].append(link['dst_port_no' ]) banport[link["src_dpid" ]].append(link['src_port_no' ]) else : group[m] = group[m] + group[n] group[n] = []
对于成环检测的实现,我们采用UNION-FIND 的思想,每个集合的leader 即为集合的序号,如果源交换机和目的交换机的leader 的相同,说明二者在同一个集合,即会成环,则将二者连接的两个端口禁掉;若二者的leader 不同,说明二者不会成环,则更新集合,将二者集合合并。由于边集是升序排列,因此遍历时也从小到大遍历,当最终所有交换机都在同一集合中时,说明最小生成树已经形成。
成果展示 拓扑构建 (一)mininet侧
(二)RYU侧
(三)拓扑可视化
kruskal 算法实现 (一)禁止端口
(二)最小生成树可视化
连通性测试 (一)随机ping测试
mininet侧,可以看到花费了0.499毫秒ping通
RYU侧,可以看到逐渐从2号主机沿着最小生成树扩展到达19号
(二)pingall测试
下图可见全部ping通,连通性良好。