網(wǎng)絡(luò)的轉(zhuǎn)發(fā)是通信的基本功能，其完成信息在網(wǎng)絡(luò)中傳遞，實(shí)現(xiàn)有序的數(shù)據(jù)交換。通過(guò)SDN控制器的集中控制，可以輕松實(shí)現(xiàn)基礎(chǔ)的轉(zhuǎn)發(fā)算法有二層MAC學(xué)習(xí)轉(zhuǎn)發(fā)和基于跳數(shù)的最短路徑算法。然而，網(wǎng)絡(luò)跳數(shù)并不是決定路徑優(yōu)劣的唯一狀態(tài)。除了跳數(shù)以外，還有帶寬，時(shí)延等標(biāo)準(zhǔn)。本文將介紹如何通過(guò)SDN控制器Ryu開(kāi)發(fā)基于流量的最短路徑轉(zhuǎn)發(fā)應(yīng)用。

 [[158380]]

Forwarding Algorithm

目前基于流量的路由算法基本的解決思路有兩種：

(1) 首先基于跳數(shù)計(jì)算***K條路徑，然后在這些路徑中選擇可用帶寬***的路徑。

(2) 首先基于跳數(shù)計(jì)算***路徑，歸一化路徑的評(píng)價(jià)分?jǐn)?shù)，然后基于流量計(jì)算***路徑，歸一化基于帶寬的評(píng)價(jià);設(shè)置跳數(shù)和帶寬的權(quán)重，對(duì)基于跳數(shù)和帶寬的評(píng)分求其加權(quán)總和;按照加權(quán)求和值降序排序，取前K條作為***評(píng)價(jià)路徑。

本文以***種算法為例，介紹基于網(wǎng)絡(luò)流量的最短路徑轉(zhuǎn)發(fā)應(yīng)用開(kāi)發(fā)。第二種算法基于前者的基礎(chǔ)修改即可完成。

Network Awareness

首先我們需要編寫一個(gè)網(wǎng)絡(luò)感知應(yīng)用，用于發(fā)現(xiàn)網(wǎng)絡(luò)的資源，包括節(jié)點(diǎn)，鏈路，終端主機(jī)等。并根據(jù)拓?fù)湫畔⒂?jì)算基于條數(shù)的最短路徑。開(kāi)發(fā)此應(yīng)用基本步驟如下：

創(chuàng)建繼承app_manager.RyuApp的應(yīng)用network_awareness

從topology.switches獲取拓?fù)湫畔?，包括交換機(jī)節(jié)點(diǎn)信息，鏈路信息

使用Networkx 創(chuàng)建拓?fù)鋱D的對(duì)象，用于存儲(chǔ)網(wǎng)絡(luò)拓?fù)?/p>

使用Networkx的函數(shù)all_simple_paths(G, source, target, cutoff=None)計(jì)算K條***路徑并存儲(chǔ)，該函數(shù)實(shí)現(xiàn)了Yen's algorithm

示例代碼可由muzixing/ryu/network_awareness獲取。

Note that: 以上的示例代碼中，拓?fù)湫畔⒌拇鎯?chǔ)并沒(méi)有使用networkx，所以讀者需要獨(dú)立完成基于networkx的存儲(chǔ)和算法調(diào)用部分。

Network Monitor

第二個(gè)應(yīng)用是網(wǎng)絡(luò)流量監(jiān)控應(yīng)用。網(wǎng)絡(luò)流量監(jiān)控應(yīng)用完成網(wǎng)絡(luò)流量的實(shí)時(shí)監(jiān)控，計(jì)算出實(shí)時(shí)的流量統(tǒng)計(jì)數(shù)據(jù)?；诒緫?yīng)用的數(shù)據(jù)，可以完成轉(zhuǎn)發(fā)算法的第二部分內(nèi)容。示例代碼可由muzixing/ryu/network_monitor獲取。

為了讓其他模塊獲取到***的流量信息，可在Ryu中自定義事件，具體教程請(qǐng)查看《基于Ryu打造自定義控制器》的自定義事件部分內(nèi)容。不定義事件的情況下，需要將此模塊作為新模塊的CONTEXT。詳情可閱讀《Ryu:模塊間通信機(jī)制分析》的相關(guān)內(nèi)容。

Forwarding Application

基于以上兩個(gè)模塊的數(shù)據(jù)，轉(zhuǎn)發(fā)應(yīng)用模塊需要完成如下幾個(gè)步驟，從而完成基于流量的***路徑轉(zhuǎn)發(fā)。

獲取network awareness和network monitor的數(shù)據(jù)

將network monitor的數(shù)據(jù)整合到networkx存儲(chǔ)的網(wǎng)絡(luò)拓?fù)湫畔⒅?/p>

比較最短K條路徑中各路徑的剩余帶寬，選擇***路徑，剩余路徑為備份路徑和逃生路徑

基于路徑信息，安裝流表項(xiàng)

整合流量信息代碼示例代碼如下, 其中，link2port為鏈路信息，bw_dict為network monitor模塊的流量數(shù)據(jù)。

def create_bw_graph(self, graph, link2port, bw_dict): 
    for link in link2port: 
        (src_dpid, dst_dpid) = link 
        (src_port, dst_port) = link2port[link] 
  
        if src_dpid in bw_dict and dst_dpid in bw_dict: 
            bw_src = bw_dict[src_dpid][src_port] 
            bw_dst = bw_dict[dst_dpid][dst_port] 
            graph[src_dpid][dst_dpid]['bandwidth'] = min(bw_src, bw_dst) 
        else: 
            graph[src_dpid][dst_dpid]['bandwidth'] = 0 
    return graph 

獲取最短K條路徑函數(shù)示例代碼如下所示。

def k_shortest_paths(graph, src, dst): 
    path_generator = nx.shortest_simple_paths(graph, source=src, 
    target=dst, weight='weight') 
    return path_generator 

基于流量的***路徑比較算法示例代碼如下所示：

def band_width_compare(graph, paths, best_paths): 
    capabilities = {} 
    MAX_CAPACITY = 100000 
    for src in paths: 
        for dst in paths[src]: 
            if src == dst: 
                best_paths[src][src] = [src] 
                capabilities.setdefault(src, {src: MAX_CAPACITY}) 
                capabilities[src][src] = MAX_CAPACITY 
                continue 
            max_bw_of_paths = 0 
            best_path = paths[src][dst][0] 
            for path in paths[src][dst]: 
                min_bw = MAX_CAPACITY 
                min_bw = get_min_bw_of_links(graph, path, min_bw) 
                if min_bw > max_bw_of_paths: 
                    max_bw_of_paths = min_bw 
                    best_path = path</p> 
      best_paths[src][dst] = best_path 
        capabilities.setdefault(src, {dst: max_bw_of_paths}) 
        capabilities[src][dst] = max_bw_of_paths 
return capabilities, best_paths 

def best_paths_by_bw(graph, src=None, topo=None): 
    _graph = copy.deepcopy(graph) 
    paths = {} 
    best_paths = {} 
    # find ksp in graph. 
    for src in _graph.nodes(): 
        paths.setdefault(src, {src: [src]}) 
        best_paths.setdefault(src, {src: [src]}) 
        for dst in _graph.nodes(): 
            if src == dst: 
                continue 
            paths[src].setdefault(dst, []) 
            best_paths[src].setdefault(dst, []) 
            path_generator = k_shortest_paths(_graph, src, dst) 
<pre><code>        k = 2 
        for path in path_generator: 
            if k &lt;= 0: 
                break 
            paths[src][dst].append(path) 
            k -= 1 
# find best path by comparing bandwidth. 
capabilities, best_paths = band_width_compare(_graph, paths, best_paths) 
return capabilities, best_paths, paths 

安裝流表項(xiàng)函數(shù)示例代碼如下：

def install_flow(datapaths, link2port, access_table, path, flow_info, buffer_id, data): 
     ''' path=[dpid1, dpid2, dpid3...] 
        flow_info=(eth_type, src_ip, dst_ip, in_port) 
    ''' 
    if path is None or len(path) == 0: 
        LOG.info("PATH ERROR") 
        return 
    in_port = flow_info[3] 
    first_dp = datapaths[path[0]] 
    out_port = first_dp.ofproto.OFPP_LOCAL 
    reverse_flow_info = (flow_info[0], flow_info[2], flow_info[1]) 
<pre><code>if len(path) &gt; 2: 
    for i in xrange(1, len(path) - 1): 
        port = get_link2port(link2port, path[i-1], path[i]) 
        port_next = get_link2port(link2port, path[i], path[i + 1]) 
        if port and port_next: 
            src_port, dst_port = port[1], port_next[0] 
            datapath = datapaths[path[i]] 
            send_flow_mod(datapath, flow_info, src_port, dst_port) 
            send_flow_mod(datapath, reverse_flow_info, dst_port, src_port) 
if len(path) &gt; 1: 
    # the last flow entry: tor -&gt; host 
    last_dp = datapaths[path[-1]] 
    port_pair = get_link2port(link2port, path[-2], path[-1]) 
    if port_pair: 
        src_port = port_pair[1] 
    else: 
        return 
    dst_port = get_port(flow_info[2], access_table) 
  
    send_flow_mod(last_dp, flow_info, src_port, dst_port) 
    send_flow_mod(last_dp, reverse_flow_info, dst_port, src_port) 
  
    # the first flow entry 
    port_pair = get_link2port(link2port, path[0], path[1]) 
    if port_pair: 
        out_port = port_pair[0] 
    else: 
        return 
    send_flow_mod(first_dp, flow_info, in_port, out_port) 
    send_flow_mod(first_dp, reverse_flow_info, out_port, in_port) 
  
    send_packet_out(first_dp, buffer_id, in_port, out_port, data) 
    # ensure the first ping success. 
    # send_packet_out(last_dp, buffer_id, src_port, dst_port, data) 
# src and dst on the same datapath 
else: 
    out_port = get_port(flow_info[2], access_table) 
    send_flow_mod(first_dp, flow_info, in_port, out_port) 
    send_flow_mod(first_dp, reverse_flow_info, out_port, in_port) 
    send_packet_out(first_dp, buffer_id, in_port, out_port, data) 

讀者可以基于muzixing/ryu/shortest_route的代碼進(jìn)行修改。該代碼是初始版本，質(zhì)量欠佳，但是可以成功運(yùn)行。

Note that: 以上的代碼均為示例代碼，不可直接運(yùn)行，完整版代碼后續(xù)將發(fā)布。

Implementation and Test

啟動(dòng)network_awareness, network_monitor,和寫好的forwarding模塊，再啟動(dòng)一個(gè)簡(jiǎn)單拓?fù)溥B接到控制器Ryu。拓?fù)渲?，h1, h2到h39有兩條路徑：[1,2,4]和[1,3,4]。每條鏈路的***帶寬為500Mbits/s。然后xterm到h1, h2 和還h39，并在h39之上啟動(dòng)iperf服務(wù)端程序。先啟動(dòng)h1上的iperf客戶端程序，向h39打流，等一個(gè)Monitor模塊的周期之后，啟動(dòng)h2的iperf客戶端程序，向h39打流。此操作的原因在于需要等待控制器獲取流量信息和計(jì)算出***路徑。測(cè)試截圖如下圖所示。

上圖左上為控制器的顯示，路徑選擇了[1,2,4]和[1,3,4]。右側(cè)的數(shù)據(jù)為h1的流量信息，左下為h2的流量信息，可以發(fā)現(xiàn)h1和h2各自獨(dú)占一條路徑，都打滿了500Mbits。實(shí)驗(yàn)成功。

Conclusion

本文介紹了在Ryu控制器中開(kāi)發(fā)基于流量的***轉(zhuǎn)發(fā)的流程。不過(guò)內(nèi)容僅僅涉及了解決思路，實(shí)際工程代碼的發(fā)布還需要等待一段時(shí)間。文中提到的第二種算法的解決方法與本文舉例類似，僅需加上歸一化數(shù)據(jù)，求加權(quán)求和評(píng)分步驟就可以完成新解決方案的工作。希望本文能給讀者帶來(lái)一些幫助。