通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

利用DFS算法，實作Ryu應用，并在Mininet上完成相關驗證

Ryu與Mininet相關安裝與配置詳見：

https://blog.csdn.net/haimianxiaojie/article/details/50705288

關于本文内所有完整代碼詳見：

https://github.com/PPPerry/Ryu_projects中的DFS部分

實作内容如下：

在Mininet上搭建一個20個節點網絡（拓撲給定），每個網絡節點下挂一個主機；

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

按照如圖所示的拓撲，編寫mininet的拓撲代碼，各個交換機與主機的序号均相同。

完整的拓撲代碼如下：

#!/usr/bin/python

from mininet.net import Mininet
from mininet.node import Controller, RemoteController, OVSController
from mininet.node import CPULimitedHost, Host, Node
from mininet.node import OVSKernelSwitch, UserSwitch
from mininet.node import IVSSwitch
from mininet.cli import CLI
from mininet.log import setLogLevel, info
from mininet.link import TCLink, Intf
from subprocess import call

def myNetwork():

    net = Mininet( topo=None,
                   controller=None,
                   ipBase='10.0.0.0/8')
    
    ## specify clearly to use a remote controller instead of the default one 
    c=RemoteController('c','0.0.0.0',6633)
    net.addController(c)

    info( '*** Add switches\n')
    s2 = net.addSwitch('s2', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s11 = net.addSwitch('s11', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s3 = net.addSwitch('s3', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s8 = net.addSwitch('s8', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s4 = net.addSwitch('s4', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s6 = net.addSwitch('s6', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s7 = net.addSwitch('s7', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s5 = net.addSwitch('s5', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s10 = net.addSwitch('s10', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s9 = net.addSwitch('s9', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s1 = net.addSwitch('s1', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s12 = net.addSwitch('s12', cls=OVSKernelSwitch,protocols=['OpenFlow13'])
    s13 = net.addSwitch('s13', cls=OVSKernelSwitch,protocols=['OpenFlow13'])

    info( '*** Add hosts\n')
    h3 = net.addHost('h3', cls=Host, ip='10.0.0.3', defaultRoute=None,mac='00:00:00:00:00:03')
    h10 = net.addHost('h10', cls=Host, ip='10.0.0.10', defaultRoute=None,mac='00:00:00:00:00:10')
    h2 = net.addHost('h2', cls=Host, ip='10.0.0.2', defaultRoute=None,mac='00:00:00:00:00:02')
    h5 = net.addHost('h5', cls=Host, ip='10.0.0.5', defaultRoute=None,mac='00:00:00:00:00:05')
    h1 = net.addHost('h1', cls=Host, ip='10.0.0.1', defaultRoute=None,mac='00:00:00:00:00:01')
    h11 = net.addHost('h11', cls=Host, ip='10.0.0.11', defaultRoute=None,mac='00:00:00:00:00:11')
    h6 = net.addHost('h6', cls=Host, ip='10.0.0.6', defaultRoute=None,mac='00:00:00:00:00:06')
    h4 = net.addHost('h4', cls=Host, ip='10.0.0.4', defaultRoute=None,mac='00:00:00:00:00:04')
    h7 = net.addHost('h7', cls=Host, ip='10.0.0.7', defaultRoute=None,mac='00:00:00:00:00:07')
    h13 = net.addHost('h13', cls=Host, ip='10.0.0.13', defaultRoute=None,mac='00:00:00:00:00:13')
    h9 = net.addHost('h9', cls=Host, ip='10.0.0.9', defaultRoute=None,mac='00:00:00:00:00:09')
    h12 = net.addHost('h12', cls=Host, ip='10.0.0.12', defaultRoute=None,mac='00:00:00:00:00:12')
    h8 = net.addHost('h8', cls=Host, ip='10.0.0.8', defaultRoute=None,mac='00:00:00:00:00:08')

    info( '*** Add links\n')
    net.addLink(h1, s1)
    net.addLink(h2, s2)
    net.addLink(h3, s3)
    net.addLink(h4, s4)
    net.addLink(h5, s5)
    net.addLink(h6, s6)
    net.addLink(h7, s7)
    net.addLink(h8, s8)
    net.addLink(h9, s9)
    net.addLink(h10, s10)
    net.addLink(h11, s11)
    net.addLink(h12, s12)
    net.addLink(h13, s13)
    net.addLink(s2, s1)
    net.addLink(s2, s3)
    net.addLink(s3, s4)
    net.addLink(s2, s5)
    net.addLink(s5, s7)
    net.addLink(s5, s6)
    net.addLink(s5, s8)
    net.addLink(s5, s9)
    net.addLink(s8, s9)
    net.addLink(s9, s11)
    net.addLink(s9, s10)
    net.addLink(s10, s11)
    net.addLink(s3, s10)
    net.addLink(s3, s13)
    net.addLink(s10, s13)
    net.addLink(s11, s12)
    net.addLink(s12, s13)

    ## start switch
    for i in range(1,7):
        net.get("s{}".format(i)).start([])

    info( '*** Starting network\n')
    net.start()

    #into the interactive mode
    CLI(net)
    net.stop()

if __name__ == '__main__':
    setLogLevel( 'info' )
    myNetwork()

其中，控制器c被設定為RemoteController，友善下一步與Ryu進行連接配接。

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

使用Ryu連接配接Mininet中的交換機；

使用Ryu連接配接mininet後，結果如下：

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用
Ryu讀出了所有的交換機，并發現了34個連接配接。
并将拓撲讀出來進行可視化展示；

利用mininet自帶的miniedit.py，我們可以直覺的實作mininet的靜态可視化，如圖所示：

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

在Ryu上實作深度優先周遊算法，并找出任意兩個主機間的最短路和最長路；

使用DFS可以找到任意兩個交換機之間的所有路徑，進而通過周遊，很容易找到任意兩個主機（交換機）之間的最短路和最長路。

實作DFS的遞歸算法如下：

def findpath(self,src_sw,dst_sw,sign,onepath,allpaths):
	       if src_sw==dst_sw:
	           #print(onepath)
	           allpaths.append(onepath.copy())
	           #print(allpaths)
	       else:
	           for u in self.switches:
	               if (self.get_adjacent(src_sw,u) is not None)and(sign[u]!=1):
	                       sign[u]=1
	                       onepath.append(u)
	                       
	                       self.findpath(u,dst_sw,sign,onepath,allpaths)
	                           
	                       onepath.remove(u)
	                       sign[u]=0

傳回值為一個二維清單，裡面存儲了從源交換機到目的交換機的所有路徑（用隊列存儲）

使用最長路來配置任意兩個主機間的通信連接配接

再得到所有路徑之後，通過周遊找到最長路和最短路并列印，再将最長路的路徑存儲到record中，進行下一步的路徑配置

def shortest_path(self,src_sw,dst_sw,first_port,last_port):
	        self.logger.info("topo calculate the shortest path from ---{}-{}-------{}-{}".format(first_port,src_sw,dst_sw,last_port))
	        self.logger.debug("there is {} swithes".format(len(self.switches)))
	        
	        sign={}
	        for s in self.switches:
	            sign[s]=0
	        sign[src_sw]=1
	        
	        onepath=[]
	        onepath.append(src_sw)
	
	        allpaths=[]
	        self.findpath(src_sw,dst_sw,sign,onepath,allpaths)
	        #print(allpaths)
	        print("paths num is: {}".format(len(allpaths)))
	        print("all paths:")
	        sp=allpaths[0]
	        lp=allpaths[0]
	        for i in allpaths:
	            if(len(i)>len(lp)):
	                lp=i
	            if(len(i)<len(sp)):
	                sp=i
	            print(i)
	
	        print("the shortest path is: ")
	        print(sp)
	        print("the longest path is: ")
	        print(lp)
	
	
	        if src_sw==dst_sw:
	                path=[src_sw]
	        else:
	                path=lp
	            
	        record=[]
	        inport=first_port
	
	            # s1 s2; s2:s3, sn-1  sn
	        for s1,s2 in zip(path[:-1],path[1:]):
	                # s1--outport-->s2
	            outport,_=self.get_adjacent(s1,s2)
	                
	            record.append((s1,inport,outport))
	            inport,_=self.get_adjacent(s2,s1)
	            
	        record.append((dst_sw,inport,last_port))
	        
	        #we find a path
	        # (s1,inport,outport)->(s2,inport,outport)->...->(dest_switch,inport,outport)
	        return record

傳回值record為最長路（一維清單），傳到路徑配置中

實作效果如圖：

以h1 ping -c 1 h9為例：（拓撲序号命名見前面的拓撲圖）

列印出h9到h1所有路徑和最長路、最短路，并配置最長路：

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

以pingall為例：

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

所有的交換機均ping通，無掉包，且均按最長路徑配置

輸出所有的路徑：

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

将配置通的業務在可視化平台上進行展示

利用networkx，将拓撲圖與最長路徑（配置的路徑）進行可視化展示：

以h1 ping -c 1 h9為例：（拓撲序号命名見前面的拓撲圖）

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

圖檔樣式是networkx随機生成的，但拓撲是不會變的，即從h1到h9的路徑就如圖中紅色的路徑所示。

實作networkx的部分代碼如下：

#draw
def draw_graph(graph,path):

    # extract nodes from graph

    nodes = set([n1 for n1, n2 in graph] + [n2 for n1, n2 in graph])

    # create networkx graph

    G=nx.Graph()

    # add nodes

    for node in nodes:

        G.add_node(node)


    # add edges
    G.add_edges_from(graph,color='b')
    G.add_edges_from(path,color='r')

    #G.add_edges_from(new)


    # draw graph

    edges = G.edges()
    colors = [G[u][v]['color'] for u,v in edges]

    nx.draw(G,with_labels=True,edges=edges,edge_color=colors)

    # show graph

plt.show()

通信網系列實驗（一）——基于DFS算法的Ryu+Mininet應用

Ryu與Mininet相關安裝與配置詳見：

關于本文内所有完整代碼詳見：

實作内容如下：

繼續閱讀

棋盤問題.…

C語言DFS(4)____棋盤問題

POJ 1321棋盤問題（dfs）

前序周遊/二叉樹/LeetCode 5418

另類樹形結構的周遊題目--員工的重要性題目：題解：DFS和BFS

POJ - 2488 A Knight's Journey解題報告

第一次CSP模測第一題第二題第三題

SDN學習筆記（一）NFV的一些筆記SDN與NFV的差別與融合

SDN基礎入門學習一

認識SDN

XMPP 在SDN中的角色：一路向前

一本SDN入門書籍讀書筆記——SDN 标準分析

Flood Fill—DFS和BFS算法的執行個體講解（C）（島嶼數量I）

dfs深度優先搜尋_圖的深度優先搜尋（DFS）

NETCONF協定之netopeer軟體安裝

SDN學習之Opendaylight淺析(五)