networkx高效開發(fā)SDN應用路由算法

SDN(Software Defined Networking)是一種新型的網絡架構，通過集中式的控制平面管理數(shù)據(jù)層面的轉發(fā)等操作。網絡的連通性是最基礎的需求，為保證網絡連通，控制器需應用相應的圖論算法，計算出轉發(fā)路徑，完成數(shù)據(jù)轉發(fā)。在開發(fā)SDN應用時，為完成基礎的路徑計算，時常需要開發(fā)者獨立編寫網絡算法，不僅麻煩，性能和代碼可復用性還受開發(fā)者個人編程水平影響。所以本篇文章將介紹網絡算法工具networkx，用于完成路徑算法的開發(fā)工作。

networkx是用于創(chuàng)建、操作和研究復雜網絡動態(tài)、結構和功能的Python語言包。networkx支持創(chuàng)建簡單無向圖、有向圖和多重圖（multigraph）；內置許多標準的圖論算法，節(jié)點可為任意數(shù)據(jù)，如圖像文件；支持任意的邊值維度，功能豐富，簡單易用。

由于Networkx代碼經過多次測試，性能方面也做了很多的工作，使用Networkx內置的多種圖論算法能給開發(fā)SDN應用帶來很多的便利，可以節(jié)省開發(fā)時間，降低代碼故障率。networkx的安裝和使用，讀者可從中快速得到，不加贅述。接下來的內容將簡要介紹Networkx的經典圖論算法內容， 包括最短路徑,?KSP(K Shortest Paths)算法和Traversal(遍歷)算法BFS（Breadth First Search）/DFS(Depth First Search)。

最短路徑算法Dijkstra和Floyd

計算單源到其他所有節(jié)點的最短路徑的Dijkstra算法和計算所有節(jié)點之間最短路徑的Floyd算法是最經典的網絡算法之一。在networkx中對于二者的實現(xiàn)將在如下介紹。

Dijkstra
無論有向圖還是無向圖均可以使用Dijkstra算法，G為networkx生成的圖數(shù)據(jù)結構。source為起點，target為終點。起點、終點和權重均為可選參數(shù)。
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算法，有無權圖和有權圖兩種實現(xiàn)：

無權圖
networkx.all_pairs_shortest_path(G[, cutoff])

有權圖
networkx.all_pairs_dijkstra_path(G[, cutoff, weight])

對于路徑的長度計算可以調用network.XXX_length函數(shù)獲得，XXX為對應的路徑計算算法名稱。除了以上提到的幾個算法以外，networkx還針對很多需求設計了變種的函數(shù)，如返回同樣長度的多條最佳路徑算法等，讀者可根據(jù)需求自定義學習內容。

K-Shortest paths
在研究網絡路由算法/轉發(fā)算法時，除了使用跳數(shù)作為計算最優(yōu)路徑的標準以外，還會使用到很多其他的指標，如帶寬、時延等，也有可能根據(jù)多種指標，建立多維度評價系統(tǒng)，計算加權值，從而計算最佳路徑。例如，當涉及到帶寬為標準時，計算量就會很大。首先，獲取網絡鏈路的剩余帶寬數(shù)據(jù)，然后從源頭開始，選途徑路徑中帶寬最大的路徑。由于一條鏈路中的最大剩余帶寬取決與剩余帶寬最小的那一條，若使用貪心算法逐跳排除，很可能計算錯誤，所以每遇到一個分支就需要選擇一個路徑，并保存其他未選擇的路徑數(shù)據(jù)。每一個節(jié)點都需要對所有的數(shù)據(jù)進行對比，從而選擇當下最優(yōu)的路徑，直至所有的鏈路都比較完成。這樣的算法可以通過修改Dijkstra算法完成，邏輯不困難，但效率并不高，具體實現(xiàn)不加贅述，讀者可查看筆者在網上找到的一個介紹文章:基于SDN的最短路徑算法(迪杰斯特拉)dijkstra。

在研究的過程中，發(fā)現(xiàn)許多論文提到的方法都是基于拓撲信息算法K條最短路徑，然后在根據(jù)帶寬計算最優(yōu)路徑。根據(jù)算法可以直接在這K條中選擇最大的路徑最為最優(yōu)，也可以設置權重，計算跳數(shù)和帶寬的加權值，再選擇最優(yōu)。由于跳數(shù)的數(shù)值和帶寬的數(shù)值相差甚遠，所以二者均需進行歸一化/正則化。

考慮跳數(shù)的原因在于：每經過一個交換機，消耗的資源就多一份，所以需要考慮在內。舉例：路徑A帶寬100M，跳數(shù)為2； 路徑B帶寬110M，跳數(shù)為5,若按照帶寬選擇則選擇B，然而B經過的路徑是A的若干倍，消耗的資源更多，產生的傳輸時延，以及傳播時延（假設跳數(shù)為5的鏈路長度大于2，否則不成立）也更多，所以綜合考慮A可能是更好的路徑。

傳統(tǒng)的KSP算法很多，Yen, Jin Y于1971年發(fā)表的論文 "Finding the k Shortest Loopless Paths in a Network"中提出的Yen's algorithm就是經典算法之一，讀者可直接查看點擊Yen's algorithm的wiki。其算法思想并不復雜，基本思想為：

Dijkstra選擇第1條最優(yōu)路徑， 保存為A[0]

外循環(huán)，k從1到k。 內循環(huán)，以第k-1條（前一條）最優(yōu)路徑為路徑，從該路徑的第一個點開始作為分叉節(jié)點，分叉節(jié)點之前的為前一條最優(yōu)路徑與當前路徑一致的部分，稱之為rootpaths；將分叉點上已選的最優(yōu)路徑分支去掉（權值設置為正無窮），然后再運算dijkstra,將路徑計算結果放到臨時數(shù)據(jù)結構B中，隨著循環(huán)的進行，分叉點不斷前進，直至終點前一跳，內循環(huán)比較，已選出多條潛在的最優(yōu)路徑。

對臨時數(shù)據(jù)結構B中的路徑進行排序，找到最優(yōu)路徑，添加到A數(shù)據(jù)結構中， 存為A[k], 外循環(huán)一輪結束。

外循環(huán)繼續(xù)，直至找到K條最優(yōu)路徑。

Networkx已經實現(xiàn)了KSP算法，該算法patch于2015年4月份左右才加入networkx項目，由于networkx中all\_shrtest\_paths名字已被使用，所以新加入的算法在networkx中對應函數(shù)命名為all_simple_pay，具體參數(shù)如下所示：
all_simple_paths(G, source, target, cutoff=None)

其中G為networkx的圖數(shù)據(jù)結構，source為起點，target為終點，cutoff為搜索深度，只返回路徑長度短于cutoff的路徑。為優(yōu)化性能，函數(shù)返回值為一個generator(生成器)， 讀者可通過for循環(huán)，生成對應的K shortest paths。采用generator可以逐次計算結果，而不會一次運算全部結果都寫入內存，可以大大降低內存使用。

Traversal
在某些網絡應用場景中，會使用到遍歷算法，如BFS（Breadth First Search）/DFS(Depth First Search)算法， networkx已經定義好的對應函數(shù)，具體內容由于篇幅限制，不再介紹。讀者可查看networkx官方文檔中關于遍歷的文檔進行學習。

總結

在開發(fā)SDN應用中，網絡連通性是最基本的需求。在開發(fā)網絡應用時，可采用networkx來保存網絡數(shù)據(jù)，計算路徑等，大大提高了開發(fā)效率。在學習的過程中，從自己不斷造輪子，到逐漸使用成熟的開源軟件，接觸了很多工具，學習到了很多有用的知識。自己造的輪子很多時候，性能、適用度以及接口的穩(wěn)定度都是很大的考驗，逐漸嘗試優(yōu)秀的開源工具將成為我在未來編程學習的方向。