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

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

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

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

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