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為終點。起點、終點和權重均為可選參數。
無權圖
有權圖
Floyd對于Floyd算法，有無權圖和有權圖兩種實現：
無權圖
有權圖
對于路徑的長度計算可以調用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，具體參數如下所示：
其中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來保存網絡數據，計算路徑等，大大提高了開發效率。在學習的過程中，從自己不斷造輪子，到逐漸使用成熟的開源軟件，接觸了很多工具，學習到了很多有用的知識。自己造的輪子很多時候，性能、適用度以及接口的穩定度都是很大的考驗，逐漸嘗試優秀的開源工具將成為我在未來編程學習的方向。
作者簡介：
李呈，2014/09-至今，北京郵電大學信息與通信工程學院未來網絡理論與應用實驗室（FNL實驗室）攻讀碩士研究生。
京公網安備 11010502049343號