田家翼，黃 韜，楊 帆

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

0 引言

企業(yè)網(wǎng)絡(luò)中通常利用MPLS 等技術(shù)提供專線業(yè)務(wù)，維護(hù)成本昂貴，配置復(fù)雜并且難以管理，在這樣的架構(gòu)下進(jìn)行路由方案調(diào)整，優(yōu)化用戶業(yè)務(wù)質(zhì)量異常困難[1]。針對(duì)此類問(wèn)題，現(xiàn)有的路由策略[2]無(wú)法提供合適的解決方案。傳統(tǒng)路由方案通常按照盡力而為的策略選擇單一路徑，不能有效的結(jié)合網(wǎng)絡(luò)當(dāng)前的負(fù)載情況，沒(méi)有考慮網(wǎng)絡(luò)中的流量特征和鏈路狀態(tài)，如等價(jià)多路徑算法（ECMP）[3]，可能會(huì)將多個(gè)流量分配到同一條鏈路上，當(dāng)鏈路間差異很明顯的時(shí)候，很難達(dá)到滿意的效果。

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

圖1 多個(gè)域路由拓?fù)?Fig.1 Muti-domain routing topology

本文主要研究一種結(jié)合軟件定義網(wǎng)絡(luò)，采用多級(jí)多域的路由方案的動(dòng)態(tài)流量調(diào)度方法。該方法可以提高整個(gè)網(wǎng)絡(luò)的鏈路利用率，調(diào)節(jié)網(wǎng)絡(luò)拓?fù)涞牧髁糠植己屯掏铝?，并且能夠達(dá)到更優(yōu)負(fù)載均衡，有效的調(diào)整網(wǎng)絡(luò)擁塞，最后算法擁有較低的時(shí)間復(fù)雜度，可以較快進(jìn)行計(jì)算和響應(yīng)。

1 相關(guān)研究

在已有的基于軟件定義網(wǎng)絡(luò)架構(gòu)的路由方案中，文獻(xiàn)[7]中提出了一種級(jí)連路由的多路徑算法，通過(guò)不同節(jié)點(diǎn)之間交換路徑信息構(gòu)建多條路徑來(lái)保障用戶服務(wù)。文獻(xiàn)[8]提出了一種網(wǎng)絡(luò)最壞適應(yīng)多路徑路由算法（AWMR），該算法根據(jù)網(wǎng)絡(luò)中可用的網(wǎng)絡(luò)資源和新加入節(jié)點(diǎn)的帶寬需求來(lái)選擇多條路徑和確定新加入節(jié)點(diǎn)的轉(zhuǎn)發(fā)路徑，而不是對(duì)每個(gè)流使用固定數(shù)量的轉(zhuǎn)發(fā)路徑。文獻(xiàn)[9]提出了一種基于網(wǎng)絡(luò)性能的路由算法（PBR），該算法通過(guò)測(cè)量往返時(shí)延作為路徑權(quán)重，利用bellman-ford 算法結(jié)合SPFA 進(jìn)行優(yōu)化，利用計(jì)算的路徑矢量圖進(jìn)行快速路由。

以上幾種算法都有著不可避免的一些問(wèn)題，級(jí)連路由的多路徑算法對(duì)于如何構(gòu)建滿足多個(gè)約束條件的級(jí)連路徑，沒(méi)有提出一種通用有效的方案。最壞適應(yīng)多路徑算法通過(guò)計(jì)算源節(jié)點(diǎn)與目的節(jié)點(diǎn)的最短路徑集，根據(jù)流量的帶寬需求選擇最壞匹配路徑，但是其收斂速度可能很慢，并不能適應(yīng)響應(yīng)速度要求很高的網(wǎng)絡(luò)環(huán)境。基于網(wǎng)絡(luò)性能的路由算法通過(guò)時(shí)延探測(cè)網(wǎng)絡(luò)性能，并沒(méi)有考慮整個(gè)網(wǎng)絡(luò)的流量狀態(tài)。

綜上所述，上述算法不能根據(jù)當(dāng)前網(wǎng)絡(luò)的全局負(fù)載情況，保證高效快速的路由轉(zhuǎn)發(fā)。本文的算法采用域間和域內(nèi)相結(jié)合的路由策略，當(dāng)鏈路負(fù)載過(guò)高時(shí)，根據(jù)域間流量分布和域內(nèi)鏈路狀態(tài)進(jìn)行重新路由。

2 基于軟件定義網(wǎng)絡(luò)的路由算法

本節(jié)將提出一個(gè)基于軟件定義網(wǎng)絡(luò)的多級(jí)多域的路由算法。對(duì)鏈路負(fù)載進(jìn)行監(jiān)測(cè)，域內(nèi)和域間基于不同的選路策略。

2.1 設(shè)計(jì)思路

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

1）域內(nèi)采用基于時(shí)延的路由算法：

根據(jù)子域流量數(shù)目多，對(duì)時(shí)延敏感[10]等特點(diǎn)，每個(gè)子域內(nèi) di計(jì)算鏈路平均時(shí)延作為路徑的權(quán)重，采用基于時(shí)延進(jìn)行權(quán)重選路的策略。設(shè)源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d，鏈路為 ek，權(quán)重參數(shù)，代價(jià)計(jì)算：

每次當(dāng)前節(jié)點(diǎn)選擇權(quán)重最優(yōu)的鏈路進(jìn)行構(gòu)建，直到到達(dá)目的節(jié)點(diǎn)。其中時(shí)延計(jì)算方法為當(dāng)前節(jié)點(diǎn)發(fā)送探測(cè)數(shù)據(jù)包，通過(guò)接收回傳的探測(cè)包，使用當(dāng)前時(shí)間戳減去發(fā)送探測(cè)包的時(shí)間戳，得到路徑的往返時(shí)延，記為RTTSiSj， si,sj表示路徑。

2）域間采用基于流量[11]的動(dòng)態(tài)路由算法：

由于域間流量具有動(dòng)態(tài)性的特點(diǎn)，采用周期性檢測(cè)以更新網(wǎng)絡(luò)狀態(tài)， 根據(jù)當(dāng)前鏈路狀態(tài)判斷負(fù)載情況，基于可選路徑統(tǒng)計(jì)域內(nèi)平均鏈路利用率，計(jì)算當(dāng)前流量帶寬情況，將較大的流量根據(jù)最大—最小公平原則進(jìn)行路由。

步驟1 行鏈路負(fù)載檢測(cè)，當(dāng)超過(guò)閾值則將負(fù)載過(guò)重的鏈路上的流量進(jìn)行路徑轉(zhuǎn)換或者重新路由。鏈路負(fù)載參數(shù)為：

l 為某一時(shí)刻鏈路i 的負(fù)載率，N 為所有鏈路，當(dāng)δ ＞ δ*時(shí)，需要進(jìn)行流量調(diào)度重新路由。

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

式中，ψt是根據(jù)時(shí)間對(duì)流量大小進(jìn)行的估計(jì)， bt是交換機(jī)在時(shí)刻t 接收到的該流的所有字節(jié)數(shù)，bs是時(shí)刻s 接收到該流的所有字節(jié)數(shù)，t - s是統(tǒng)計(jì)的時(shí)間間隔。

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

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

2.2 算法實(shí)現(xiàn)

將全局網(wǎng)絡(luò)抽象成一個(gè)有向圖G =(V, E)，V 是網(wǎng)絡(luò)節(jié)點(diǎn)（各個(gè)子域抽象成獨(dú)立節(jié)點(diǎn)）的集合，E是鏈路的集合，一條鏈路 eij定義為一個(gè)三元( vi, vj, c) 組， vi,vj∈ V為網(wǎng)絡(luò)節(jié)點(diǎn)，每一條鏈路 eij都有一個(gè)非負(fù)數(shù)值0c ＞ 表示鏈路帶寬。

算法1 getIntraDomainRounting

輸入：源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d，節(jié)點(diǎn)V 和鏈路E 的集合

輸出：域內(nèi)最優(yōu)轉(zhuǎn)發(fā)路徑

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

輸入：源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d，節(jié)點(diǎn)V 和鏈路E 的集合，子域的集合D

輸出：流量重新優(yōu)化路由結(jié)果

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 算法復(fù)雜度

假設(shè)全局網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為N，而每個(gè)Domain 網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)是 /N n。在傳統(tǒng)網(wǎng)絡(luò)或者SDN 架構(gòu)中路徑計(jì)算的復(fù)雜度是{ 2}N∧。在本文中，跨域路徑計(jì)算被劃分為域內(nèi)路徑計(jì)算和域間路徑計(jì)算兩部分，其中域內(nèi)路徑復(fù)雜度為，而域間復(fù)雜度為{ 2}n∧。因此，跨域路徑計(jì)算復(fù)雜度為當(dāng)1N ＞ 且n N＜ 時(shí)，且較大時(shí)，所以本文提出的算法可降低網(wǎng)絡(luò)路徑計(jì)算[13]的復(fù)雜度。而當(dāng)時(shí)，可以最大程度降低全局路徑計(jì)算復(fù)雜度。

2.4 仿真結(jié)果

為了驗(yàn)證本文的設(shè)計(jì)，利用Mininet 仿真軟件和ONOS 控制器[14]進(jìn)行實(shí)驗(yàn)驗(yàn)證。算法由域間控制模塊和域內(nèi)控制模塊實(shí)現(xiàn)，各個(gè)子域與域間控制模塊之間進(jìn)行周期性的信息交互，域內(nèi)控制模塊從交換機(jī)[15]采集端口的統(tǒng)計(jì)信息，包括端口號(hào)，收發(fā)的包數(shù)和字節(jié)數(shù)，信息接收時(shí)間，鏈路狀態(tài)等統(tǒng)計(jì)信息，將當(dāng)前域內(nèi)路由狀態(tài)，域的標(biāo)識(shí)和域間鏈路信息返回給域間控制模塊，根據(jù)這些信息計(jì)算流量速率和鏈路負(fù)載參數(shù)等。

本文構(gòu)建了5 個(gè)域來(lái)模擬SDN-WAN 中多個(gè)域的網(wǎng)絡(luò)場(chǎng)景。每個(gè)域包括8 臺(tái)交換機(jī)，和80 臺(tái)主機(jī)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的鏈路均設(shè)置為全雙工鏈路，并將鏈路帶寬設(shè)定為100 Mbp/s，使用iperf 工具產(chǎn)生模擬的網(wǎng)絡(luò)流量，隨機(jī)的選擇源主機(jī)向目的主機(jī)發(fā)送報(bào)文，每個(gè)流的速率服從于均勻分布，平均為10 Mbp/s，每個(gè)流持續(xù)時(shí)間80 s。在本實(shí)驗(yàn)中，逐步增加注入網(wǎng)絡(luò)的流量速率，變化范圍是鏈路總帶寬的1%～90%。

本文對(duì)多級(jí)多域負(fù)載均衡路由算法（標(biāo)記為L(zhǎng)BMD）和ECMP 以及針對(duì)SDN-WAN 提出的基于網(wǎng)絡(luò)性能（標(biāo)記為PBR）的路由算法進(jìn)行比較，結(jié)果如下圖所示?？梢钥吹?，圖5 分別采用不同算法進(jìn)行路由的平均鏈路利用率仿真對(duì)比。仿真結(jié)果表明由于ECMP 在路由時(shí)沒(méi)有將網(wǎng)絡(luò)的鏈路狀態(tài)和流量分布情況考慮在內(nèi)，只是將數(shù)據(jù)流均勻分配到各條等價(jià)路徑上，導(dǎo)致鏈路帶寬分配不均勻，增加了鏈路擁塞的可能性，因此它的平均鏈路利用率要低于PBR 和LBM。此外，從圖中可以看出PBR 算法中沒(méi)有考慮傳輸后路徑上的實(shí)時(shí)負(fù)載情況，這容易造成某條路徑上的負(fù)載過(guò)重，降低網(wǎng)絡(luò)鏈路利用率，而LBMD 算法對(duì)鏈路狀態(tài)進(jìn)行實(shí)時(shí)檢測(cè)，采用動(dòng)態(tài)的路由策略進(jìn)行調(diào)整，因此性能要高于其他兩個(gè)算法。

下圖為網(wǎng)絡(luò)吞吐量性能的對(duì)比。從圖中可以看出，當(dāng)流量速率超過(guò)一定大小之后，ECMP 的吞吐量要比LBMD 低的多，這是因?yàn)镋CMP 按照地址散列的方式可能將多個(gè)流映射到同一條路徑上，造成網(wǎng)絡(luò)擁塞，導(dǎo)致數(shù)據(jù)包的丟失。PBR 的吞吐量也要比LBMD 低，是因?yàn)镻BR 將時(shí)延作為參數(shù)進(jìn)行路由計(jì)算，在網(wǎng)絡(luò)規(guī)模比較大的情況下不能夠及時(shí)的做出調(diào)整，而LBMD 針對(duì)域間路徑采用實(shí)時(shí)監(jiān)測(cè)進(jìn)行分流的策略，減少了開(kāi)銷并且優(yōu)化了流量分布。

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

圖3 網(wǎng)絡(luò)吞吐量對(duì)比 Fig.3 Comparison of network throughput

3 結(jié)論

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