基于和覆蓋的SDN路由算法研究.pdf

1、在當(dāng)前，計算機網(wǎng)絡(luò)正處于一個革新的時期，網(wǎng)絡(luò)的的基本架構(gòu)自從提出之后，多年來并未發(fā)生本質(zhì)改變。而另一方面互聯(lián)網(wǎng)的飛速發(fā)展使得其對網(wǎng)絡(luò)的需求越來越高，這導(dǎo)致了傳統(tǒng)網(wǎng)絡(luò)架構(gòu)越來越無法滿足當(dāng)前新技術(shù)對其的需求。為了滿足新的需求，SDN出現(xiàn)了，并且迅速發(fā)展，取得了眾多碩果。其核心思想是將轉(zhuǎn)發(fā)平面從數(shù)據(jù)平面分離，數(shù)據(jù)平面只需要關(guān)心報文的轉(zhuǎn)發(fā)，控制平面則用來做出轉(zhuǎn)發(fā)的決策。這使得網(wǎng)絡(luò)創(chuàng)新門檻大大降低，網(wǎng)絡(luò)的配置工作就如同計算機軟件在操作系統(tǒng)上一般，

2、可任意安裝卸載。同時也解決了傳統(tǒng)網(wǎng)絡(luò)分布式架構(gòu)的種種難題，比如配置復(fù)雜，網(wǎng)絡(luò)不可控等許多疑難雜癥。
　　在傳統(tǒng)網(wǎng)絡(luò)中，路由問題一直是一個瓶頸，因為無法知曉網(wǎng)絡(luò)全局拓撲，所以只能根據(jù)局部信息采用分布式算法，這樣一來整個路由過程都是不可控的，或者說需要非常大的代價才能控制。而在SDN中由于其有個統(tǒng)一的中心控制器，可以獲取整個網(wǎng)絡(luò)的拓撲信息，并且能夠控制報文轉(zhuǎn)發(fā)決策，使得在傳統(tǒng)網(wǎng)絡(luò)中的路由難題可以在SDN中輕松解決。而在SDN網(wǎng)絡(luò)中大多

3、數(shù)路由算法是基于多路徑路由算法或者動態(tài)鏈路調(diào)整算法。而本文與大多數(shù)方法不同是采用從網(wǎng)絡(luò)拓撲結(jié)構(gòu)入手的方式提出了一種基于盒覆蓋算法以及分級路由思想的改進版的Dijkstra算法來進行路由選擇。
　　盒覆蓋算法最初是應(yīng)用在復(fù)雜網(wǎng)絡(luò)中，用來研究網(wǎng)絡(luò)自相似性質(zhì)的一個方法。它是用來查找給定一個一定“尺寸”的盒子，然后用這個盒子來覆蓋網(wǎng)絡(luò)，所有的盒子中的結(jié)點距離都不超過“尺寸”大小的，所用的最小的盒子數(shù)。這正與分級路由策略的思想不謀而合。所以

4、可以通過盒覆蓋算法將網(wǎng)絡(luò)分解成許多小的子網(wǎng)，然后在路由階段，于子網(wǎng)之間使用Dijkstra算法計算最短路徑，然后在處于最短路徑上的子網(wǎng)內(nèi)部進行最短路計算，最后將這些子網(wǎng)的路徑組合得到我們所求的路由。
　　因為我們知道Dijkstra算法的時間復(fù)雜度是O(V+ElogE)。結(jié)點和邊的數(shù)目會直接影響了整個算法的所耗費時間，而在真實的大型網(wǎng)絡(luò)中往往有許多的結(jié)點和邊，所以不可避免的會導(dǎo)致Dijkstra算法性能下降。而通過分級后，網(wǎng)絡(luò)的規(guī)