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

1、在當(dāng)前，計(jì)算機(jī)網(wǎng)絡(luò)正處于一個(gè)革新的時(shí)期，網(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)心報(bào)文的轉(zhuǎn)發(fā)，控制平面則用來做出轉(zhuǎn)發(fā)的決策。這使得網(wǎng)絡(luò)創(chuàng)新門檻大大降低，網(wǎng)絡(luò)的配置工作就如同計(jì)算機(jī)軟件在操作系統(tǒng)上一般，

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

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

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