项目要求

  1. 在 Mininet 上搭建一个 7 个节点网络（拓扑给定），每个网络节点下挂一 个主机；
  2. 使用 Ryu 连接 Mininet 中的交换机；
  3. 并将拓扑读出来进行可视化展示；
  4. 在 Ryu 上实现深度优先遍历算法，并找出任意两个主机间的最短路和最长路；
  5. 使用最长路来配置任意两个主机间的通信连接；
  6. 将配置通的业务在可视化平台上进行展示 。

DFS算法原理

基本思想

深度优先搜索 DFS（Depth First Search）是从初始结点开始扩展，扩展顺 序总是先扩展最新产生的结点。这就使得搜索沿着状态空间某条单一的路径进行 下去，直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产 生新的结点的时候，就沿着结点产生顺序的反方向寻找可以产生新结点的结点， 并扩展它，形成另一条搜索路径。

基本步骤

  1. 从初始结点开始，将待扩展结点依次放到栈中。
  2. 如果栈空，即所有待扩展结点已全部扩展完毕，则问题无解，退出。
  3. 取栈中最新加入的结点，即栈顶结点出栈，并用相应的扩展原则扩展出所有的子结点，并按顺序将这些结点放入栈中。若没有子结点产生，则转（2）。
  4. 如果某个子结点为目标结点，则找到问题的解（这不一定是最优解）， 结束。如果要求得问题的最优解，或者所有解，则转（2），继续搜索新的目标结点。

示例

下图是一个无向图，如果我们从 A 点发起深度优先搜索（以下的访问次序并 不是唯一的，第二个点既可以是 B 也可以是 C,D），则我们可能得到如下的一个 访问过程：A->B->E（没有路了！回溯到 A)->C->F->H->G->D（没有路，最终 回溯到 A,A 也没有未访问的相邻节点，本次搜索结束）

示例拓扑图

DFS 与 BFS 比较

  • 遍历方式不同：DFS 的方式则是从一条路一直走到底后再回退，再走到底 而 BFS 遍历方式是围绕着根结点一圈一圈（level by level）向外遍历。
  • 数据结构不同：DFS 常借助栈的方式来实现，而 BFS 常借助队列的方式实 基于深度优先遍历算法框架的主机最长路连接配置项目实验报告 第 3 页 现。
  • 具体应用不同：DFS 比较适合判断图中是否有环，寻找两个节点之间的路径，有向无环图（DAG）的拓扑排序，寻找所有强连通片（SCC），无向图中寻找 割点和桥等； BFS 则比较适合判断二分图，以及用于实现寻找最小生成树（MST），如在 BFS 基础上的 Kruskal 算法以及寻找最短路径问题（如 Dijkstra算法）

代码分析

DFS 算法实现

可行实现方式

  • 自己建立堆栈以代替系统栈，从而进行 DFS
  • 利用系统栈以及循环实现递归，从而进行 DFS

实现方式比较

DFS 是一个递归算法，就算额外建立堆栈，本质上处理数据的规则和利用的 空间大小是依旧不变的。它的空间复杂度无论选择哪种方式，都是 O ( N ) （N 为节点数）。而 DFS 计算路径几乎是遍历全图输出路径，因此其耗费的时间受存 储拓扑信息的结构决定。 因此 DFS 选择两种实现方式在效率上没有差异。但就代码长度来说，第二种实现方式更为简洁明了并且简短。因此在实现的过程中本文选择第二种方法。

变量说明

符号含义
u当前检索的交换机
i与 u 有相连边的邻接交换机
dst目标终点主机对应的交换机
visited用于标记交换机的变量
cur_pathi 和 u 之间的路径，一个边
allpaths所有可行路径的集合

DFS实现

（一）获得邻居节点

1
2
3
4
5
6
7
8
9
#获得邻居节点
def get_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
def DFS(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
def sum_delay(self,all_path,links): 
    sum_delay = [0]*len(all_path) #时延列表初始化
    for i in range(len(all_path)): #分别计算每一条路径上的时延并储存在 sum_delay 列表中，作为返回值返回
        path = all_path[i]
        for j in range(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

（四）给全部路径加上时延属性，并找出最短和最长路

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
def search_path(self,src,dst,src_port,dst_port):
    print('Calculating all the path of {}:{} -> {}:{}...'.format(src,src_port,dst,dst_port))
    visited = {} #标记，判断是否已经被加入路径
    for s in self.switches: 
        visited[s] = 0
    visited[src] = 1 #将源主机标记为已被探索
        
    cur_path = []
    cur_path.append(src) #将源主机加入路径
    all_paths = []
        
    self.DFS(src,dst,visited,cur_path,all_paths) #调用 DFS，发现从 src 到 dst 的全部路径并存储在 all_paths 中         
    print('find {} paths'.format(len(all_paths))) #路径的数量
        
    sum_delay = self.sum_delay(all_paths,self.links) #计算出所有路径的时延，交换机和主机之间的时延存储在 links 列表中
    k = 0
    for path in all_paths: 
        print(path,sum_delay[k]) #打印各条路径的时延信息
        k = k+1
        #计算时延最长路和时延最短路
    max = 0
    min = 100000
    for i in range(len(sum_delay)): 
        if sum_delay[i] > max: 
            max_i = i
            max = sum_delay[i]
        if sum_delay[i] < min: 
            min_i = i
            min = sum_delay[i]
    #打印时延最短路和时延最长路
    print('the shortest path :',all_paths[min_i],'delay:',sum_delay[min_i])
    print('the longest path :',all_paths[max_i],'delay:',sum_delay[max_i])
    #要求配置的是时延最长路，因此用下列代码将最长路的主机、交换机和端口信息存入 ryu_path，返回给调用函数
    path = all_paths[max_i]
    ryu_path = []
    in_port = src_port
    for s1,s2 in zip(path[:-1],path[1:]):
        for link in self.links:
    #从原图的 links 列表中得到对应交换机的端口信息，从目的主机到源主机读取出端口，从源主机到目的主机读取入端口，其中 s1 是从目的主机一侧开始往源主机一侧推进，s2 是从源主机一侧开始往目的主机一侧推进。
            if link['src_dpid'] == s1 and link['dst_dpid'] == s2: 
                out_port = link['dst_port_no']
                ryu_path.append((s1,in_port,out_port))
        for link in self.links: 
            if link['src_dpid'] == s2 and link['dst_dpid'] == s1: 
                in_port = link['src_port_no']
                ryu_path.append((dst,in_port,dst_port))
    return ryu_path #返回最长路上的主机和所有交换机以及对应的端口信息，以便配置的时候调用

RYU通信实现

（一）初始化

1
2
3
4
5
6
7
8
9
10
11
class Kruskaltest(app_manager.RyuApp): 
    OFP_VERSIONS=[ofproto_v1_3.OFP_VERSION] #确定控制器的 openflow 版本
    def __init__(self,*args,**kwargs): 7. super(Kruskaltest,self).__init__(*args,**kwargs)#继承自己，方便后面的初始化步骤
    self.mac_to_port={} #arp 列表初始化
    self.topology_api_app=self
    self.sleep_interval = 0.5 #程序暂停的时间为 0.5 秒，以使 mininet 和 ryu 的拓扑建立保持同步，防止链路丢失
    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
@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)#配置缺省流表，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)]#收到后立即执行 actions
#以上内容为流表信息的获取
        mod=ofp_parser.OFPFlowMod(datapath=datapath,priority=priority,match=match,instructions=inst)#流表内容定义，第一个为流表从哪一个交换机发送过来，第二个为权重，第三个为匹配域，当收到的数据包和匹配域匹配上时执行 instructions 
    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
@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() #通过后面的 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) #ryu 每发现一个交换机之后都要暂停一段时间，让mininetd 建立拓扑的速度能跟上，否则会造成链路丢失
        
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)) #得到并打印链路信息，其中包含了源交换机的 dpid 和对应的端口号以及目的交换机的 dpid 和对应的端口号

    #file = open("./topo24.json","r")
    file = open("./topo7.json","r")#由于原来的 24 个交换机拓扑太大，故用 7 个交换机来作为测试，读取 topo7.json 里的信息
    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

（四）DFS最长路配置

配置思路 : 将需要配置的路径存储在 path 中，其中有源主机和目的主机的 mac 地址、 路径上的交换机号和对应的端口，将对应流表下发。

1
2
3
4
5
6
7
8
9
10
11
12
def configure_path(self,path,src,dst,datapath): #路径配置函数
    print("configure the longgest path")
    path_print=src #将源主机的 mac 地址加入到打印序列中
    for switch,in_port,out_port in path: #向对应的交换机下发流表指导通信
        ofp_parser=datapath.ofproto_parser
        match=ofp_parser.OFPMatch(in_port=in_port,eth_src=src,eth_dst=dst)
        actions=[ofp_parser.OFPActionOutput(out_port)]
        self.add_flow(datapath,1,match,actions)
        path_print+="-->{}-{}-{}".format(in_port,switch,out_port)#将路径上的进入端
口、交换机和输出端口加入打印序列
    path_print+="--"+dst#将目的主机的 mac 地址加入打印序列
    print("the longgest path is:{}".format(path_print))#打印最长路

（五）控制器对数据包的处理

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
@set_ev_cls(ofp_event.EventOFPPacketIn,MAIN_DISPATCHER)#监视器，当有 packetin 消息进来时，执行下面的代码
    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 #id from switch
        #以上是对收到的数据包进行解析
        self.mac_to_port.setdefault(dpid,{})
        # 对控制器里面的 mac_to_port 列表初始化
        pkt=packet.Packet(msg.data)#读取需要传输的数据
        eth=pkt.get_protocol(ethernet.ethernet)#读取以太网地址的数据包，里面包含了 src 和dst 以及 ethertype 等信息
        in_port=msg.match['in_port'] #读取匹配域中的进入交换机的端口号
        print("in_port is ",in_port)
        src = eth.src 21. self.mac_to_port[dpid][src]=in_port#将源交换机的 MAC 地址和源交换机进入该交换机的端口号对应起来
        dst=eth.dst #目的主机的 MAC 地址
        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]: #如果目的主机的 MAC 地址已经在控制器的 mac_to_port列表里面有记录，直接下发流表
            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)#权值为 1，表示优先级先于缺省流表
            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:#如果控制器的 mac_to_port 列表里面没有目的主机的 mac 地址，执行以下代码
            print('dst mac is unknown')
            print('the dpid is ',dpid)
            actions=[]#actions 初始化
            for port in datapath.ports:#对于向控制器发送 packetin 消息的交换机中的每一个端口，执行下面的代码
                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
16
17
18
19
20
21
22
23
if dst in self.mac_to_port[dpid]:#目的主机地址在 mac_to_port 表中
    if src not in 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 not in self.host_mac_to.keys(): 
            self.host_mac_to[src]=(dpid,in_port)
        actions=[]
        for port in datapath.ports: 
            if(port not in self.banport[dpid]) and (port != in_port): 
                actions.append(ofp_parser.OFPActionOutput(port))

成果展示

拓扑构建

（一）mininet侧

mininet拓扑构建信息

（二）RYU侧

RYU侧拓扑发现

（三）七节点拓扑可视化

拓扑示意图

DFS算法实现

（一）mininet侧 —— 连通性良好

mininet侧连通性良好

以 h2 ping h7 示例

ping测试

（二）RYU侧

RYU侧连通性测试

（三）最短路和最长路可视化

（蓝色路径为最长路，黄色路径为最短路，绿色路径为重合的路径，黑色路径为未经过路径）

拓扑可视化