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

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

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

最短路徑算法Dijkstra和Floyd

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

Dijkstra

無(wú)論有向圖還是無(wú)向圖均可以使用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)

無(wú)權(quán)圖

networkx.single_source_shortest_path(G, source[, cutoff])

有權(quán)圖

networkx.dijkstra_path(G, source, target, weight='weight')

Floyd

對(duì)于Floyd算法，有無(wú)權(quán)圖和有權(quán)圖兩種實(shí)現(xiàn)：

無(wú)權(quán)圖

networkx.all_pairs_shortest_path(G[, cutoff])

有權(quán)圖

networkx.all_pairs_dijkstra_path(G[, cutoff, weight])

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

K-Shortest paths

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

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

考慮跳數(shù)的原因在于：每經(jīng)過(guò)一個(gè)交換機(jī)，消耗的資源就多一份，所以需要考慮在內(nèi)。舉例：路徑A帶寬100M，跳數(shù)為2; 路徑B帶寬110M，跳數(shù)為5,若按照帶寬選擇則選擇B，然而B經(jīng)過(guò)的路徑是A的若干倍，消耗的資源更多，產(chǎn)生的傳輸時(shí)延，以及傳播時(shí)延(假設(shè)跳數(shù)為5的鏈路長(zhǎng)度大于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條***路徑， 保存為A[0]

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

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

外循環(huán)繼續(xù)，直至找到K條***路徑。

Networkx已經(jīng)實(shí)現(xiàn)了KSP算法，該算法patch于2015年4月份左右才加入networkx項(xiàng)目，由于networkx中all\_shrtest\_paths名字已被使用，所以新加入的算法在networkx中對(duì)應(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為搜索深度，只返回路徑長(zhǎng)度短于cutoff的路徑。為優(yōu)化性能，函數(shù)返回值為一個(gè)generator(生成器)， 讀者可通過(guò)for循環(huán)，生成對(duì)應(yīng)的K shortest paths。采用generator可以逐次計(jì)算結(jié)果，而不會(huì)一次運(yùn)算全部結(jié)果都寫入內(nèi)存，可以大大降低內(nèi)存使用。

Traversal

在某些網(wǎng)絡(luò)應(yīng)用場(chǎng)景中，會(huì)使用到遍歷算法，如BFS(Breadth First Search)/DFS(Depth First Search)算法， networkx已經(jīng)定義好的對(duì)應(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)用時(shí)，可采用networkx來(lái)保存網(wǎng)絡(luò)數(shù)據(jù)，計(jì)算路徑等，大大提高了開發(fā)效率。在學(xué)習(xí)的過(guò)程中，從自己不斷造輪子，到逐漸使用成熟的開源軟件，接觸了很多工具，學(xué)習(xí)到了很多有用的知識(shí)。自己造的輪子很多時(shí)候，性能、適用度以及接口的穩(wěn)定度都是很大的考驗(yàn)，逐漸嘗試優(yōu)秀的開源工具將成為我在未來(lái)編程學(xué)習(xí)的方向。