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

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

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

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

最短路徑算法Dijkstra和Floyd

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

Dijkstra
無論有向圖還是無向圖均可以使用Dijkstra算法，G為networkx生成的圖數(shù)據(jù)結(jié)構(gòu)。source為起點(diǎn)，target為終點(diǎn)。起點(diǎn)、終點(diǎn)和權(quán)重均為可選參數(shù)。
networkx.shortest_path(G, source=None, target=None, weight=None)

無權(quán)圖
networkx.single_source_shortest_path(G, source[, cutoff])

有權(quán)圖
networkx.dijkstra_path(G, source, target, weight='weight')

Floyd
對于Floyd算法，有無權(quán)圖和有權(quán)圖兩種實現(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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