SDN(Software Defined Networking)是一種新型的網絡架構，通過集中式的控制平面管理數據層面的轉發等操作。網絡的連通性是最基礎的需求，為保證網絡連通，控制器需應用相應的圖論算法，計算出轉發路徑，完成數據轉發。在開發SDN應用時，為完成基礎的路徑計算，時常需要開發者獨立編寫網絡算法，不僅麻煩，性能和代碼可復用性還受開發者個人編程水平影響。所以本篇文章將介紹網絡算法工具networkx，用於完成路徑算法的開發工作。
networkx是用於創建、操作和研究複雜網絡動態、結構和功能的Python語言包。networkx支持創建簡單無向圖、有向圖和多重圖(multigraph);內置許多標準的圖論算法，節點可為任意數據，如圖像文件;支持任意的邊值維度，功能豐富，簡單易用。
由於Networkx代碼經過多次測試，性能方面也做了很多的工作，使用Networkx內置的多種圖論算法能給開發SDN應用帶來很多的便利，可以節省開發時間，降低代碼故障率。networkx的安裝和使用，讀者可從官網文檔中快速得到，不加贅述。接下來的內容將簡要介紹Networkx的經典圖論算法內容， 包括最短路徑, KSP(K Shortest Paths)算法和Traversal(遍歷)算法BFS(Breadth First Search)/DFS(Depth First Search)。
最短路徑算法Dijkstra和Floyd
計算單源到其他所有節點的最短路徑的Dijkstra算法和計算所有節點之間最短路徑的Floyd算法是最經典的網絡算法之一。在networkx中對於二者的實現將在如下介紹。
Dijkstra
無論有向圖還是無向圖均可以使用Dijkstra算法，G為networkx生成的圖數據結構。source為起點，target為終點。起點、終點和權重均為可選參數。
networkx.shortest_path(G, source=None, target=None, weight=None)
無權圖
networkx.single_source_shortest_path(G, source[, cutoff])
有權圖
networkx.dijkstra_path(G, source, target, weight='weight')
Floyd
對於Floyd算法，有無權圖和有權圖兩種實現：
無權圖
networkx.all_pairs_shortest_path(G[, cutoff])
有權圖
networkx.all_pairs_dijkstra_path(G[, cutoff, weight])
對於路徑的長度計算可以調用network.XXX_length函數獲得，XXX為對應的路徑計算算法名稱。除了以上提到的幾個算法以外，networkx還針對很多需求設計了變種的函數，如返回同樣長度的多條***路徑算法等，讀者可根據需求自定義學習內容。
K-Shortest paths
在研究網絡路由算法/轉發算法時，除了使用跳數作為計算***路徑的標準以外，還會使用到很多其他的指標，如帶寬、時延等，也有可能根據多種指標，建立多維度評價系統，計算加權值，從而計算***路徑。例如，當涉及到帶寬為標準時，計算量就會很大。首先，獲取網絡鏈路的剩餘帶寬數據，然後從源頭開始，選途徑路徑中帶寬***的路徑。由於一條鏈路中的***剩餘帶寬取決與剩餘帶寬最小的那一條，若使用貪心算法逐跳排除，很可能計算錯誤，所以每遇到一個分支就需要選擇一個路徑，並保存其他未選擇的路徑數據。每一個節點都需要對所有的數據進行對比，從而選擇當下***的路徑，直至所有的鏈路都比較完成。這樣的算法可以通過修改Dijkstra算法完成，邏輯不困難，但效率並不高，具體實現不加贅述，讀者可查看筆者在網上找到的一個介紹文章:基於SDN的最短路徑算法(迪傑斯特拉)dijkstra。
在研究的過程中，發現許多論文提到的方法都是基於拓撲信息算法K條最短路徑，然後在根據帶寬計算***路徑。根據算法可以直接在這K條中選擇***的路徑最為***，也可以設置權重，計算跳數和帶寬的加權值，再選擇***。由於跳數的數值和帶寬的數值相差甚遠，所以二者均需進行歸一化/正則化。
考慮跳數的原因在於：每經過一個交換機，消耗的資源就多一份，所以需要考慮在內。舉例：路徑A帶寬100M，跳數為2; 路徑B帶寬110M，跳數為5,若按照帶寬選擇則選擇B，然而B經過的路徑是A的若干倍，消耗的資源更多，產生的傳輸時延，以及傳播時延(假設跳數為5的鏈路長度大於2，否則不成立)也更多，所以綜合考慮A可能是更好的路徑。
傳統的KSP算法很多，Yen, Jin Y於1971年發表的論文 "Finding the k Shortest Loopless Paths in a Network"中提出的Yen's algorithm就是經典算法之一，讀者可直接查看點擊Yen's algorithm的wiki。其算法思想並不複雜，基本思想為：
Dijkstra選擇第1條***路徑， 保存為A[0]
外循環，k從1到k。 內循環，以第k-1條(前一條)***路徑為路徑，從該路徑的***個點開始作為分叉節點，分叉節點之前的為前一條***路徑與當前路徑一致的部分，稱之為rootpaths;將分叉點上已選的***路徑分支去掉(權值設置為正無窮)，然後再運算dijkstra,將路徑計算結果放到臨時數據結構B中，隨著循環的進行，分叉點不斷前進，直至終點前一跳，內循環比較，已選出多條潛在的***路徑。
對臨時數據結構B中的路徑進行排序，找到***路徑，添加到A數據結構中， 存為A[k], 外循環一輪結束。
外循環繼續，直至找到K條***路徑。
Networkx已經實現了KSP算法，該算法patch於2015年4月份左右才加入networkx項目，由於networkx中all\_shrtest\_paths名字已被使用，所以新加入的算法在networkx中對應函數命名為all_simple_pay，具體參數如下所示：
all_simple_paths(G, source, target, cutoff=None)
其中G為networkx的圖數據結構，source為起點，target為終點，cutoff為搜索深度，只返迴路徑長度短於cutoff的路徑。為優化性能，函數返回值為一個generator(生成器)， 讀者可通過for循環，生成對應的K shortest paths。採用generator可以逐次計算結果，而不會一次運算全部結果都寫入內存，可以大大降低內存使用。
Traversal
在某些網絡應用場景中，會使用到遍歷算法，如BFS(Breadth First Search)/DFS(Depth First Search)算法， networkx已經定義好的對應函數，具體內容由於篇幅限制，不再介紹。讀者可查看networkx官方文檔中關於遍歷的文檔進行學習。
總結
在開發SDN應用中，網絡連通性是最基本的需求。在開發網絡應用時，可採用networkx來保存網絡數據，計算路徑等，大大提高了開發效率。在學習的過程中，從自己不斷造輪子，到逐漸使用成熟的開源軟體，接觸了很多工具，學習到了很多有用的知識。自己造的輪子很多時候，性能、適用度以及接口的穩定度都是很大的考驗，逐漸嘗試優秀的開源工具將成為我在未來編程學習的方向。
【編輯推薦】
【責任編輯：
何妍TEL：（010）68476606】