基于網絡流量的SDN最短路徑轉發(fā)應用
網絡的轉發(fā)是通信的基本功能，其完成信息在網絡中傳遞，實現有序的數據交換。通過SDN控制器的集中控制，可以輕松實現基礎的轉發(fā)算法有二層MAC學習轉發(fā)和基于跳數的最短路徑算法。然而，網絡跳數并不是決定路徑優(yōu)劣的唯一狀態(tài)。除了跳數以外，還有帶寬，時延等標準。本文將介紹如何通過SDN控制器Ryu開發(fā)基于流量的最短路徑轉發(fā)應用。
Forwarding Algorithm
目前基于流量的路由算法基本的解決思路有兩種：
(1) 首先基于跳數計算***K條路徑，然后在這些路徑中選擇可用帶寬***的路徑。
(2) 首先基于跳數計算***路徑，歸一化路徑的評價分數，然后基于流量計算***路徑，歸一化基于帶寬的評價;設置跳數和帶寬的權重，對基于跳數和帶寬的評分求其加權總和;按照加權求和值降序排序，取前K條作為***評價路徑。
本文以***種算法為例，介紹基于網絡流量的最短路徑轉發(fā)應用開發(fā)。第二種算法基于前者的基礎修改即可完成。
Network Awareness
首先我們需要編寫一個網絡感知應用，用于發(fā)現網絡的資源，包括節(jié)點，鏈路，終端主機等。并根據拓撲信息計算基于條數的最短路徑。開發(fā)此應用基本步驟如下：
創(chuàng)建繼承app_manager.RyuApp的應用network_awareness
從topology.switches獲取拓撲信息，包括交換機節(jié)點信息，鏈路信息
使用Networkx 創(chuàng)建拓撲圖的對象，用于存儲網絡拓撲
使用Networkx的函數all_simple_paths(G, source, target, cutoff=None)計算K條***路徑并存儲，該函數實現了Yen's algorithm
示例代碼可由muzixing/ryu/network_awareness獲取。
Note that: 以上的示例代碼中，拓撲信息的存儲并沒有使用networkx，所以讀者需要獨立完成基于networkx的存儲和算法調用部分。
Network Monitor
第二個應用是網絡流量監(jiān)控應用。網絡流量監(jiān)控應用完成網絡流量的實時監(jiān)控，計算出實時的流量統(tǒng)計數據。基于本應用的數據，可以完成轉發(fā)算法的第二部分內容。示例代碼可由muzixing/ryu/network_monitor獲取。
為了讓其他模塊獲取到***的流量信息，可在Ryu中自定義事件，具體教程請查看《基于Ryu打造自定義控制器》的自定義事件部分內容。不定義事件的情況下，需要將此模塊作為新模塊的CONTEXT。詳情可閱讀《Ryu:模塊間通信機制分析》的相關內容。
Forwarding Application
基于以上兩個模塊的數據，轉發(fā)應用模塊需要完成如下幾個步驟，從而完成基于流量的***路徑轉發(fā)。
獲取network awareness和network monitor的數據
將network monitor的數據整合到networkx存儲的網絡拓撲信息中
比較最短K條路徑中各路徑的剩余帶寬，選擇***路徑，剩余路徑為備份路徑和逃生路徑
基于路徑信息，安裝流表項
整合流量信息代碼示例代碼如下, 其中，link2port為鏈路信息，bw_dict為network monitor模塊的流量數據。
- 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條路徑函數示例代碼如下所示。
- 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 <= 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
安裝流表項函數示例代碼如下：
- 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) > 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) > 1:
- # the last flow entry: tor -> 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的代碼進行修改。該代碼是初始版本，質量欠佳，但是可以成功運行。
Note that: 以上的代碼均為示例代碼，不可直接運行，完整版代碼后續(xù)將發(fā)布。
Implementation and Test
啟動network_awareness, network_monitor,和寫好的forwarding模塊，再啟動一個簡單拓撲連接到控制器Ryu。拓撲中，h1, h2到h39有兩條路徑：[1,2,4]和[1,3,4]。每條鏈路的***帶寬為500Mbits/s。然后xterm到h1, h2 和還h39，并在h39之上啟動iperf服務端程序。先啟動h1上的iperf客戶端程序，向h39打流，等一個Monitor模塊的周期之后，啟動h2的iperf客戶端程序，向h39打流。此操作的原因在于需要等待控制器獲取流量信息和計算出***路徑。測試截圖如下圖所示。
上圖左上為控制器的顯示，路徑選擇了[1,2,4]和[1,3,4]。右側的數據為h1的流量信息，左下為h2的流量信息，可以發(fā)現h1和h2各自獨占一條路徑，都打滿了500Mbits。實驗成功。
Conclusion
本文介紹了在Ryu控制器中開發(fā)基于流量的***轉發(fā)的流程。不過內容僅僅涉及了解決思路，實際工程代碼的發(fā)布還需要等待一段時間。文中提到的第二種算法的解決方法與本文舉例類似，僅需加上歸一化數據，求加權求和評分步驟就可以完成新解決方案的工作。希望本文能給讀者帶來一些幫助。
