基于SDN 的多級多域路由算法研究

田家翼，黃 韜，楊 帆

(北京郵電大學信息與通信工程學院，北京 100876)

0 引言

企業網絡中通常利用MPLS 等技術提供專線業務，維護成本昂貴，配置復雜并且難以管理，在這樣的架構下進行路由方案調整，優化用戶業務質量異常困難[1]。針對此類問題，現有的路由策略[2]無法提供合適的解決方案。傳統路由方案通常按照盡力而為的策略選擇單一路徑，不能有效的結合網絡當前的負載情況，沒有考慮網絡中的流量特征和鏈路狀態，如等價多路徑算法（ECMP）[3]，可能會將多個流量分配到同一條鏈路上，當鏈路間差異很明顯的時候，很難達到滿意的效果。

將軟件定義網絡[4]與廣域網結合，利用軟件定義網絡數據平面和控制平面分離的架構進行路由規劃和路徑選擇，能夠靈活的控制和調度網絡流量，可以使網絡服務敏捷性大大增加。SDN-WAN[5]提供了基于SDN 架構的企業分支在廣域網中的解決方案。通過部署SDN 和SDN-WAN，可以提供更好的性能并且改善可用性，利用靈活的路由算法，保障用戶業務，讓鏈路處于輕載狀態。結合SDN-WAN通常連接不同的服務網絡，規模巨大的特點，本文采用一種分級路由的方案，將整個網絡劃分多個子域，路由計算分為域內路由和域間路由兩個部分[6]，實施不同的路由策略，并且將網絡拓撲進行抽象簡化，如下圖所示，域間由只需要獲取跨域鏈路的負載狀態，接收到簡化到全局視圖之后進行路由計算和流量調度，不僅減少了信息交互，而且降低了路由計算的復雜度。

圖1 多個域路由拓撲 Fig.1 Muti-domain routing topology

本文主要研究一種結合軟件定義網絡，采用多級多域的路由方案的動態流量調度方法。該方法可以提高整個網絡的鏈路利用率，調節網絡拓撲的流量分布和吞吐量，并且能夠達到更優負載均衡，有效的調整網絡擁塞，最后算法擁有較低的時間復雜度，可以較快進行計算和響應。

1 相關研究

在已有的基于軟件定義網絡架構的路由方案中，文獻[7]中提出了一種級連路由的多路徑算法，通過不同節點之間交換路徑信息構建多條路徑來保障用戶服務。文獻[8]提出了一種網絡最壞適應多路徑路由算法（AWMR），該算法根據網絡中可用的網絡資源和新加入節點的帶寬需求來選擇多條路徑和確定新加入節點的轉發路徑，而不是對每個流使用固定數量的轉發路徑。文獻[9]提出了一種基于網絡性能的路由算法（PBR），該算法通過測量往返時延作為路徑權重，利用bellman-ford 算法結合SPFA 進行優化，利用計算的路徑矢量圖進行快速路由。

以上幾種算法都有著不可避免的一些問題，級連路由的多路徑算法對于如何構建滿足多個約束條件的級連路徑，沒有提出一種通用有效的方案。最壞適應多路徑算法通過計算源節點與目的節點的最短路徑集，根據流量的帶寬需求選擇最壞匹配路徑，但是其收斂速度可能很慢，并不能適應響應速度要求很高的網絡環境。基于網絡性能的路由算法通過時延探測網絡性能，并沒有考慮整個網絡的流量狀態。

綜上所述，上述算法不能根據當前網絡的全局負載情況，保證高效快速的路由轉發。本文的算法采用域間和域內相結合的路由策略，當鏈路負載過高時，根據域間流量分布和域內鏈路狀態進行重新路由。

2 基于軟件定義網絡的路由算法

本節將提出一個基于軟件定義網絡的多級多域的路由算法。對鏈路負載進行監測，域內和域間基于不同的選路策略。

2.1 設計思路

本文設計了一種域間域內相結合的路由策略，可以使得全局流量得到最大化的合理均勻分配。為域的集合，每個域 di∈ G為有向圖的一個子集。

1）域內采用基于時延的路由算法：

根據子域流量數目多，對時延敏感[10]等特點，每個子域內 di計算鏈路平均時延作為路徑的權重，采用基于時延進行權重選路的策略。設源節點s，目的節點d，鏈路為 ek，權重參數，代價計算：

每次當前節點選擇權重最優的鏈路進行構建，直到到達目的節點。其中時延計算方法為當前節點發送探測數據包，通過接收回傳的探測包，使用當前時間戳減去發送探測包的時間戳，得到路徑的往返時延，記為RTTSiSj， si,sj表示路徑。

2）域間采用基于流量[11]的動態路由算法：

由于域間流量具有動態性的特點，采用周期性檢測以更新網絡狀態， 根據當前鏈路狀態判斷負載情況，基于可選路徑統計域內平均鏈路利用率，計算當前流量帶寬情況，將較大的流量根據最大—最小公平原則進行路由。

步驟1 行鏈路負載檢測，當超過閾值則將負載過重的鏈路上的流量進行路徑轉換或者重新路由。鏈路負載參數為：

l 為某一時刻鏈路i 的負載率，N 為所有鏈路，當δ ＞ δ*時，需要進行流量調度重新路由。

步驟2 設網絡中有n 條數據流F={ f1, f2, f3,…, fn}，表示所有流的集合，一條流 fi定義為一個三元組( sk, dk, bk)，表示每條跨域流量的起始域 sk和目的域 dk和流量需要的帶寬 bk；每個子域 di周期性的下發統計消息，向交換機進行數據采集，流量的帶寬速率可以由以下公示計算：

式中，ψt是根據時間對流量大小進行的估計， bt是交換機在時刻t 接收到的該流的所有字節數，bs是時刻s 接收到該流的所有字節數，t - s是統計的時間間隔。

步驟3 將鏈路上S 條流量F={ f1, f2, f3,…, fs}進行重新路由，以各個子域內 di內的平均鏈路利用率作為權重，每個子域平均鏈路利用率為：

其中， bmi表示第m 條路徑第i 條鏈路在某時刻的已占用帶寬，可通過信息統計計算出，N 為鏈路的總條數，B 為鏈路的最大帶寬。在此基礎上，計算可選n 條路徑，路徑集合為P={ p1, p2, p3, …,pn}，每條路徑有k 條鏈路，將流量離散化以最大—最小公平原則[12]進行路由，對于F={ f1, f2, f3, … ,fs}，帶寬需求滿足 b1＜ b2＜ …＜bs，鏈路總帶寬為B，將 B /s 分配給帶寬需求最小的流量，超出部分回收，再次將(B -b1)/( s- 1)的帶寬分配給其他流量，對于所有路徑重復上述過程。

2.2 算法實現

將全局網絡抽象成一個有向圖G =(V, E)，V 是網絡節點（各個子域抽象成獨立節點）的集合，E是鏈路的集合，一條鏈路 eij定義為一個三元( vi, vj, c) 組， vi,vj∈ V為網絡節點，每一條鏈路 eij都有一個非負數值0c ＞ 表示鏈路帶寬。

算法1 getIntraDomainRounting

輸入：源節點s，目的節點d，節點V 和鏈路E 的集合

輸出：域內最優轉發路徑

Begin

delay[s] = 0;

for (int i = 0; i < vertices.length - 1; i++);

for(int j = 1; j < vertices.length; j++)

edgeDelay(i,j) = detectDelay(edge(i,j));

end for

end for

while(true)

if (s == d)

break

else

int minVertex =minCost()

for (V v： minVertex.adjcent())

int cost =delay[minVertex] + edgeDelay(v, minVertex);

delay[v] = delay[v] < cost? delay[v] ： cost;

updateVertex(v, delay[v]);

end for

return buildPath();

End

算法2 getInterDomainRounting

輸入：源節點s，目的節點d，節點V 和鏈路E 的集合，子域的集合D

輸出：流量重新優化路由結果

Begin

if (countLinkLoad() > loadMax)

for (flow f ： F)

for(Domain d ： D)

averageLoad[d] = Sum(V.links().load()) / Sum(V.links.size);

end for

paths = getOptimizedPath(f, D, averageLoad, k);

minMaxFireAllocatePath(f, paths);

end for

return

End

2.3 算法復雜度

假設全局網絡節點數為N，而每個Domain 網絡的節點數是 /N n。在傳統網絡或者SDN 架構中路徑計算的復雜度是{ 2}N∧。在本文中，跨域路徑計算被劃分為域內路徑計算和域間路徑計算兩部分，其中域內路徑復雜度為，而域間復雜度為{ 2}n∧。因此，跨域路徑計算復雜度為當1N ＞ 且n N＜ 時，且較大時，所以本文提出的算法可降低網絡路徑計算[13]的復雜度。而當時，可以最大程度降低全局路徑計算復雜度。

2.4 仿真結果

為了驗證本文的設計，利用Mininet 仿真軟件和ONOS 控制器[14]進行實驗驗證。算法由域間控制模塊和域內控制模塊實現，各個子域與域間控制模塊之間進行周期性的信息交互，域內控制模塊從交換機[15]采集端口的統計信息，包括端口號，收發的包數和字節數，信息接收時間，鏈路狀態等統計信息，將當前域內路由狀態，域的標識和域間鏈路信息返回給域間控制模塊，根據這些信息計算流量速率和鏈路負載參數等。

本文構建了5 個域來模擬SDN-WAN 中多個域的網絡場景。每個域包括8 臺交換機，和80 臺主機，網絡中所有節點之間的鏈路均設置為全雙工鏈路，并將鏈路帶寬設定為100 Mbp/s，使用iperf 工具產生模擬的網絡流量，隨機的選擇源主機向目的主機發送報文，每個流的速率服從于均勻分布，平均為10 Mbp/s，每個流持續時間80 s。在本實驗中，逐步增加注入網絡的流量速率，變化范圍是鏈路總帶寬的1%～90%。

本文對多級多域負載均衡路由算法（標記為LBMD）和ECMP 以及針對SDN-WAN 提出的基于網絡性能（標記為PBR）的路由算法進行比較，結果如下圖所示。可以看到，圖5 分別采用不同算法進行路由的平均鏈路利用率仿真對比。仿真結果表明由于ECMP 在路由時沒有將網絡的鏈路狀態和流量分布情況考慮在內，只是將數據流均勻分配到各條等價路徑上，導致鏈路帶寬分配不均勻，增加了鏈路擁塞的可能性，因此它的平均鏈路利用率要低于PBR 和LBM。此外，從圖中可以看出PBR 算法中沒有考慮傳輸后路徑上的實時負載情況，這容易造成某條路徑上的負載過重，降低網絡鏈路利用率，而LBMD 算法對鏈路狀態進行實時檢測，采用動態的路由策略進行調整，因此性能要高于其他兩個算法。

下圖為網絡吞吐量性能的對比。從圖中可以看出，當流量速率超過一定大小之后，ECMP 的吞吐量要比LBMD 低的多，這是因為ECMP 按照地址散列的方式可能將多個流映射到同一條路徑上，造成網絡擁塞，導致數據包的丟失。PBR 的吞吐量也要比LBMD 低，是因為PBR 將時延作為參數進行路由計算，在網絡規模比較大的情況下不能夠及時的做出調整，而LBMD 針對域間路徑采用實時監測進行分流的策略，減少了開銷并且優化了流量分布。

圖2 平均鏈路利用率對比 Fig.2 Comparison of average link utilization

圖3 網絡吞吐量對比 Fig.3 Comparison of network throughput

3 結論

本文針對SDN-WAN 網絡中的路由問題，提出了一種多級多域的動態流量調度算法。該算法將網絡劃分為多個域，針對域間和域內不同的鏈路特點采用不同的路由計算方案。首先介紹了算法的總體流程，給出算法設計思想和實現步驟，最后在仿真平臺上對算法進行了驗證，結果表明，與其他算法相比，LDMD 算法可以提高多個域網絡對平均鏈路利用率和網絡吞吐量，并且有較低的時間復雜度。 下一個階段計劃進行更多的驗證實驗，算法沒有對其他性能進行仿真測試，比如時延等參數，以及與其他基于SDN 架構的路由算法的分析和比較。