李道全，黃泰銘，于 波，王 雪

(青島理工大學(xué) 信息與控制工程學(xué)院，山東 青島 266520)

0 引 言

在傳統(tǒng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)流量的傳輸通常使用最短路徑的單路徑路由機(jī)制。然而隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，單路徑的路由機(jī)制易導(dǎo)致部分鏈路負(fù)載過重、鏈路負(fù)載不均衡、整體網(wǎng)絡(luò)資源浪費(fèi)等問題。

軟件定義網(wǎng)絡(luò)[1](software defined network)是一種新型網(wǎng)絡(luò)體系架構(gòu)。SDN的出現(xiàn)與迅速發(fā)展，為傳統(tǒng)網(wǎng)絡(luò)單路徑路由方式向多路徑路由方式的轉(zhuǎn)變提供了諸多便利，多路徑路由的出現(xiàn)增加了網(wǎng)絡(luò)傳輸?shù)穆窂竭x擇，一定程度上降低了部分鏈路的傳輸負(fù)載。盡管如此，現(xiàn)有的多路徑路由通常是依靠路徑選擇算法從多路徑中選取最優(yōu)路徑進(jìn)行網(wǎng)絡(luò)流量的傳輸，或是多路徑平均分配流量實(shí)現(xiàn)多路徑路由，并沒有依據(jù)各路徑的性能而完全利用所有可用路徑資源，易導(dǎo)致資源浪費(fèi)與鏈路負(fù)載不均衡的問題。

本文提出的基于多路徑路由的負(fù)載均衡策略在查找所有可用路徑的同時(shí)收集各鏈路的帶寬與時(shí)延參數(shù)，并將本文提出的一種流量分配傾向度(FDP)應(yīng)用到OpenFlow組表技術(shù)中，依據(jù)每條路徑的帶寬與時(shí)延的不同公平地分配網(wǎng)絡(luò)流量到所有可用路徑。仿真結(jié)果表明，該策略可有效降低單一路徑的負(fù)載，提高SDN網(wǎng)絡(luò)中對于多路徑的使用率，實(shí)現(xiàn)了多路徑路由的負(fù)載均衡。

1 相關(guān)研究

SDN技術(shù)概念由OpenFlow協(xié)議發(fā)展而來[2]。OpenFlow協(xié)議是用來描述控制器和OpenFlow交換機(jī)之間交互所用信息的標(biāo)準(zhǔn)，以及控制器和OpenFlow交換機(jī)的接口標(biāo)準(zhǔn)[3]。SDN技術(shù)將控制功能從網(wǎng)絡(luò)設(shè)備中分離出來，實(shí)現(xiàn)了對于網(wǎng)絡(luò)功能的全局集中控制(其架構(gòu)如圖1所示)，其可編程性也為多路徑路由的部署和應(yīng)用提供了便利。

圖1 SDN架構(gòu)

近年來針對多路徑路由的相關(guān)研究有如下進(jìn)展：Chiesa等對等價(jià)多路徑(equal-cost-multipath，ECMP)在大型網(wǎng)絡(luò)中的應(yīng)用研究[4]。ECMP是指到達(dá)同一目的地的流量傳輸中，存在多條相同帶寬的路徑同時(shí)參與轉(zhuǎn)發(fā)，實(shí)現(xiàn)了多路徑的負(fù)載均衡和鏈路備份。ECMP部署較為簡單，且被廣泛應(yīng)用。但ECMP的缺點(diǎn)在于必須應(yīng)用到所有路徑帶寬相等的樹形網(wǎng)絡(luò)拓?fù)?，適用于大型網(wǎng)絡(luò)工程。然而在真實(shí)的網(wǎng)絡(luò)環(huán)境中，各路徑的帶寬、時(shí)延與可靠性等并不一樣，尤其是在路徑間帶寬差異較大的情況下，應(yīng)用ECMP會(huì)導(dǎo)致資源利用率較差[5]。針對于ECMP的不足，Zhou等提出了加權(quán)多路徑(weighted-cost-multipath，WCMP)[6]。WCMP可根據(jù)各路徑帶寬的不同按比例傳遞流量，解決了ECMP在處理拓?fù)洳粚ΨQ方面的弱點(diǎn)，從而提高了網(wǎng)絡(luò)中流量帶寬和負(fù)載均衡的公平性。但WCMP普遍依據(jù)路徑的帶寬屬性來設(shè)定權(quán)值，并未考慮到在流量傳輸過程中各鏈路的時(shí)延變化等因素。除了多路徑路由的算法研究以外，Ronald等曾提出多路徑路由協(xié)議(MPTCP)與OpenFlow的研究[7]。MPTCP在傳統(tǒng)的TCP內(nèi)核組件中添加了MPTCP組件和面向每個(gè)OpenFlow交換機(jī)端口的TCP子流組件。MPTCP組件將字節(jié)流拆分為多個(gè)分段，并將這些分段傳遞給TCP子流組件，且MPTCP組件中設(shè)置了子流擁塞控制機(jī)制，可將擁塞路徑的流量轉(zhuǎn)移到擁塞小的鏈路中，從而可以應(yīng)用于路徑帶寬不同的網(wǎng)絡(luò)環(huán)境下。MPTCP的解決方案使用多個(gè)隨機(jī)選擇的路徑，它作為一個(gè)TCP進(jìn)程工作，并不支持UDP等其它協(xié)議[8]。此外，MPTCP本身無法進(jìn)行全局鏈路感知，如何與SDN完美結(jié)合仍是一個(gè)難題，且通信過程中必須確保通信雙方都已安裝MPTCP協(xié)議棧，這為MPTCP的廣泛部署帶來了困難。

2 多路徑路由負(fù)載均衡的設(shè)計(jì)與實(shí)現(xiàn)

本文提出了一種基于流量分配傾向度的SDN多路徑路由的負(fù)載均衡策略，其實(shí)現(xiàn)過程共分為以下3個(gè)步驟：

(1)首先由控制器通過深度優(yōu)先遍歷算法(DFS)獲取多路徑及每條路徑拓?fù)洌瑫r(shí)采集并保存各路徑的帶寬與時(shí)延信息；

(2)隨后依據(jù)每條路徑的帶寬和時(shí)延參數(shù)計(jì)算出各路徑的流量分配傾向度(flow distribution propensity，F(xiàn)DP)；

(3)在各路徑中安裝OpenFlow組表，將計(jì)算好的流量分配傾向度設(shè)置成為OpenFlow Select組表中的bucket值，實(shí)現(xiàn)網(wǎng)絡(luò)流量依據(jù)各路徑FDP的比值分配到所有可用路徑。

仿真實(shí)驗(yàn)結(jié)果表明，該策略可有效提高SDN網(wǎng)絡(luò)中對于多路徑的使用率，實(shí)現(xiàn)了多路徑路由的負(fù)載均衡。

2.1 多路徑發(fā)現(xiàn)與信息采集

在傳統(tǒng)網(wǎng)絡(luò)環(huán)境下，因無法獲取全局網(wǎng)絡(luò)拓?fù)浜吐窂叫畔?，網(wǎng)絡(luò)流量的傳輸依靠逐跳路由和源路由兩種方式，通過最優(yōu)路徑算法選取最優(yōu)的單一路徑完成流量的傳遞[9]。而SDN技術(shù)因其數(shù)控分離和可編程性的特點(diǎn)，使得SDN控制器可以獲取并管理全局網(wǎng)絡(luò)拓?fù)湫畔?。拓?fù)涞陌l(fā)現(xiàn)與管理機(jī)制是由SDN控制器中的Switches模塊向底層網(wǎng)絡(luò)(OpenFlow交換機(jī))發(fā)送包含LLDP(link layer discovery protocol)的packet_out數(shù)據(jù)包來實(shí)現(xiàn)的，OpenFlow交換機(jī)在收到LLDP數(shù)據(jù)包后，會(huì)向控制器發(fā)出包含交換機(jī)間鏈路信息的packet_in數(shù)據(jù)包，SDN控制器再依據(jù)鏈路發(fā)現(xiàn)協(xié)議搜集到的反饋信息識(shí)別和管理網(wǎng)絡(luò)拓?fù)鋄10]。這樣的鏈路發(fā)現(xiàn)機(jī)制會(huì)消耗不小的通信流量，并產(chǎn)生一定的時(shí)延代價(jià)。

為簡化多路徑拓?fù)浒l(fā)現(xiàn)過程，減少通信消耗、降低時(shí)延代價(jià)，本文采用深度優(yōu)先遍歷(DFS)的算法思想來實(shí)現(xiàn)多路徑拓?fù)浒l(fā)現(xiàn)，深度優(yōu)先遍歷路徑獲取的過程描述如下所示：

假設(shè)給定網(wǎng)絡(luò)拓?fù)銰(H,S)，其中H代表主機(jī)集合，S為SDN控制器所管理的OpenFlow交換機(jī)集合。以查找任意兩個(gè)主機(jī)之間的所有可用多路徑為目的，則其深度優(yōu)先遍歷路徑查找過程可參考文獻(xiàn)[11]。

2.2 路徑信息采集

在多路徑拓?fù)浒l(fā)現(xiàn)的同時(shí)，SDN控制器可以借助OpenFlow協(xié)議提供的交互信息來采集各OpenFlow交換機(jī)端口參數(shù)的信息。

OpenFlow協(xié)議[12]主要支持3種消息類型，分別是controller-to-switch、symmetric(對稱型消息)以及asynchronous(異步型消息)，每種消息分別對應(yīng)多個(gè)事件。其中controller-to-switch消息類型中的Read-Stats事件可幫助SDN控制器獲取各OpenFlow交換機(jī)的狀態(tài)信息，包含各端口的帶寬和時(shí)延等。

考慮到在真實(shí)網(wǎng)絡(luò)環(huán)境中，各鏈路的帶寬和時(shí)延等參數(shù)不一定完全相同，因此本文在實(shí)現(xiàn)基于多路徑路由的負(fù)載均衡時(shí)，為確保分配到各路徑中的流量更為合理，需要采集各OpenFlow交換機(jī)端口的帶寬與時(shí)延信息，并結(jié)合應(yīng)用到后文提出的流量分配傾向度，實(shí)現(xiàn)網(wǎng)絡(luò)流量的按比例分配。

(1)最大剩余帶寬

在數(shù)據(jù)傳輸過程中，為防止路徑擁塞的情況發(fā)生，本文需使用SDN控制器獲取OpenFlow交換機(jī)端口的帶寬信息并計(jì)算出各路徑的最大剩余帶寬。

首先計(jì)算出路徑已用帶寬，其計(jì)算公式如式(1)所示

(1)

其中，UsedBands代表采集時(shí)間間隔T內(nèi)端口s的已用帶寬，bytesrx代表T間隔內(nèi)該端口接收的數(shù)據(jù)字節(jié)總數(shù)，bytestx代表T間隔內(nèi)該端口傳輸?shù)臄?shù)據(jù)字節(jié)總數(shù)。

對于每條路徑p={s1,s2,…,sn}，其最大剩余帶寬為p包含的所有OpenFlow交換機(jī)端口的最小剩余帶寬值，因此路徑最大剩余帶寬Bp計(jì)算公式如式(2)所示

Bp=min{Bsi-UsedBandsi|1≤i≤n}

(2)

其中，Bsi代表路徑p上的OpenFlow交換機(jī)si的總帶寬。

(2)時(shí)延

在SDN網(wǎng)絡(luò)中，任意路徑p={s1,s2,…,sn}的鏈路集合應(yīng)為l={l1,l2,…,ln-1}，且路徑p的時(shí)延應(yīng)為該路徑所包含的所有鏈路l的時(shí)延總和。

在SDN網(wǎng)絡(luò)中獲取某鏈路時(shí)延原理如圖2所示。設(shè)某單一鏈路包含兩個(gè)OpenFlow交換機(jī)SA和SB，SDN控制器可以通過向SA發(fā)送包含LLDP的數(shù)據(jù)包，并指示其將數(shù)據(jù)包轉(zhuǎn)發(fā)至SB，同時(shí)記錄數(shù)據(jù)發(fā)送的時(shí)間戳，然后與收到來自SB的packet_in報(bào)文的時(shí)間戳相減，即可得到SA的時(shí)延D1。同理可獲取SB的時(shí)延D2。除此之外，控制器與交換機(jī)之間的往返時(shí)延由圖2中虛線所示，此部分時(shí)延由echo報(bào)文測試，分別為Da和Db。因此鏈路l的時(shí)延計(jì)算公式如式(3)所示

Dl=(D1+D2-Da-Db)

(3)

因此路徑p的時(shí)延計(jì)算公式如式(4)所示

(4)

圖2 時(shí)延原理

2.3 OpenFlow組表技術(shù)應(yīng)用

OpenFlow所提供的組表(group table)技術(shù)[13]，允許把端口組合成一個(gè)輸出端口集合，是支持SDN多路徑路由的重要技術(shù)。組表(如圖3所示)的功能在于它包含獨(dú)立的操作列表，每個(gè)單獨(dú)的操作列表都被稱為動(dòng)作桶(OpenFlow bucket)，每個(gè)動(dòng)作桶或動(dòng)作桶列表都可用于輸入數(shù)據(jù)包，并為其指定確切的動(dòng)作(Action)，動(dòng)作的不同取決于組表類型的不同。組表共分為4種類型：All，Select，Indirect，F(xiàn)ast Failover。其中Select組表的應(yīng)用場景就是多路徑路由和負(fù)載均衡，如圖4所示，Select組中的每個(gè)動(dòng)作桶都有一個(gè)分配的權(quán)重(bucket weight)，且進(jìn)入組的每一個(gè)包都被發(fā)送到動(dòng)作桶中。值得注意的是，動(dòng)作桶分配的權(quán)值支持自定義。因此在基于多路徑路由的負(fù)載均衡方案設(shè)計(jì)中，合理的動(dòng)作桶權(quán)值設(shè)置是決定多路徑路由效果的關(guān)鍵。

圖3 OpenFlow組表結(jié)構(gòu)

圖4 Select類型組表結(jié)構(gòu)

2.4 流量分配傾向度(FDP)

現(xiàn)有的多路徑路由在進(jìn)行流量分配時(shí)廣泛采用等價(jià)多路徑(ECMP)，或是采用依據(jù)鏈路帶寬的加權(quán)多路徑(WCMP)，然而在網(wǎng)絡(luò)環(huán)境中各個(gè)路徑的差異不僅僅體現(xiàn)在帶寬的大小，時(shí)延和穩(wěn)定性等特點(diǎn)也會(huì)影響路徑的傳輸性能。

本文依據(jù)路徑的帶寬與時(shí)延差異，設(shè)置了流量分配傾向度(FDP)。設(shè)路徑p的流量分配傾向度為Ip，其定義如式(5)所示

(5)

在網(wǎng)絡(luò)拓?fù)渲校溌返膸捦ǔ?0 Mbps以上，而流量傳輸過程中各鏈路的時(shí)延通常為小數(shù)，在設(shè)置流量分配傾向度時(shí)，本文期待路徑的帶寬越高、時(shí)延越低，則其流量分配傾向度越高。因此式(5)中采用路徑的時(shí)延作為分母，路徑可用帶寬最小值作為分子。

在多路徑網(wǎng)絡(luò)環(huán)境下，本文將每一個(gè)包含多路徑的OpenFlow交換機(jī)安裝并使用OpenFlow組表技術(shù)中的select組表，將設(shè)置好的流量分配傾向度(FDP)應(yīng)用到select組表中的動(dòng)作桶的權(quán)值(bucket weight)中，設(shè)動(dòng)作桶權(quán)值為wp，其定義如式(6)所示

wp=Ip

(6)

為說明多路徑的流量分配過程，應(yīng)對其建立數(shù)學(xué)模型以進(jìn)行模擬。設(shè)兩個(gè)通信終端h1與h2之間包含n條可用路徑pi(1≤i≤n)，其動(dòng)作桶權(quán)值為wpi，且與其FDP值Ipi相等。每當(dāng)有新流量Tj(j≥1)到來時(shí)，select組表在處理流量Tj中所包含的所有數(shù)據(jù)包時(shí)，會(huì)根據(jù)各路徑wpi的不同，將需轉(zhuǎn)發(fā)的數(shù)據(jù)包散列到所有可用路徑pi中。設(shè)流量Tj中包含的數(shù)據(jù)包個(gè)數(shù)為Q，則每條可用路徑所分配的數(shù)據(jù)包流量定義如式(7)所示

(7)

∑qpi=Q

(8)

其中，式(8)為約束條件，表示所有可用路徑轉(zhuǎn)發(fā)的數(shù)據(jù)包總和應(yīng)為流量Tj所包含的數(shù)據(jù)包總量。

通過結(jié)合使用OpenFlow組表中的select組表和流量分配傾向度FDP，包含多轉(zhuǎn)發(fā)路徑的OpenFlow交換機(jī)在每次流量轉(zhuǎn)發(fā)過程中都可以實(shí)現(xiàn)數(shù)據(jù)包的按比例散列，從而實(shí)現(xiàn)了流量的均衡分配，達(dá)到了多路徑負(fù)載均衡的目標(biāo)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與網(wǎng)絡(luò)拓?fù)渑渲?/h3>

為驗(yàn)證前面提出的SDN多路徑路由負(fù)載均衡策略，本部分對該策略進(jìn)行了仿真實(shí)驗(yàn)。本實(shí)驗(yàn)以Ubuntu16.04為操作系統(tǒng)，應(yīng)用mininet作為網(wǎng)絡(luò)仿真軟件搭建網(wǎng)絡(luò)拓?fù)洌褂肦yu軟件作為SDN控制器。mininet和Ryu安裝在一臺(tái)處理器為Intel i5 6500，主頻為3.2 GHz，4 G內(nèi)存，操作系統(tǒng)為64位Linux的計(jì)算機(jī)上。Ryu控制器的運(yùn)行環(huán)境為64位Python2.7。

本文提出的多路徑路由策略通過編寫Ryu控制器應(yīng)用文件來實(shí)現(xiàn)，使用的是Python編程語言。

為展示較為明顯的實(shí)驗(yàn)效果，本實(shí)驗(yàn)拓?fù)鋺?yīng)用如圖5所示的網(wǎng)絡(luò)結(jié)構(gòu)，其中包含一個(gè)SDN控制器，H={h1,h2,h3,h4}代表主機(jī)集合，S={s1,s2,s3,s4,s5}為SDN控制器所管理的OpenFlow交換機(jī)集合，且每條鏈路應(yīng)用了默認(rèn)的帶寬和時(shí)延參數(shù)，以簡單模擬真實(shí)的網(wǎng)絡(luò)環(huán)境。

圖5 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>

為模擬主機(jī)之間的通信，本實(shí)驗(yàn)使用iperf命令設(shè)置h1為服務(wù)主機(jī)，h2-h4為客戶端主機(jī)。

3.2 實(shí)驗(yàn)過程與結(jié)果分析

本文的實(shí)驗(yàn)為模擬h2-h4這3個(gè)客戶端主機(jī)同時(shí)發(fā)送流量至服務(wù)器主機(jī)h1，通過對比使用多路徑路由策略前后，s5交換機(jī)的3個(gè)轉(zhuǎn)發(fā)端口Pt={port1,port2,port3}對于數(shù)據(jù)包傳輸量的變化來驗(yàn)證負(fù)載均衡的效果。

實(shí)驗(yàn)首先通過深度優(yōu)先遍歷可查找出h2-h4和h1之間共有3條可用路徑：①s5→s3→s2→s1；②s5→s4→s1；③s5→s1。通過使用Open vSwitch自帶的指令dump-flows、dump-groups和dump-ports分別查看數(shù)據(jù)流和組表的狀態(tài)信息以及端口的數(shù)據(jù)包轉(zhuǎn)發(fā)情況，可以判斷出Pt={port1,port2,port3}分別對用路徑①②③。

隨后依據(jù)控制器采集的路徑信息計(jì)算出3條路徑的流量分配傾向度(FDP)比值為5∶2∶3。

為對比負(fù)載均衡效果，在實(shí)驗(yàn)在負(fù)載均衡前后使用Open vSwitch指令查看并記錄{port1,port2,port3}這3個(gè)端口轉(zhuǎn)發(fā)數(shù)據(jù)包量的變化。

如圖6所示，在使用多路徑路由策略前，port3端口所對應(yīng)的路徑為默認(rèn)的最短路徑，其轉(zhuǎn)發(fā)數(shù)據(jù)包個(gè)數(shù)達(dá)到106數(shù)量級(jí)，而port1與port2端口所對應(yīng)的路徑雖然設(shè)置了較高的帶寬和較低的時(shí)延參數(shù)，卻只轉(zhuǎn)發(fā)了102數(shù)量級(jí)的數(shù)據(jù)包，這使得port3對應(yīng)的路徑負(fù)載較高，而其余兩條路徑的負(fù)載很低，在流量請求高峰期時(shí)會(huì)出現(xiàn)負(fù)載失衡的情況，影響了網(wǎng)絡(luò)服務(wù)質(zhì)量。

圖6 多路徑路由前s5交換機(jī)各端口數(shù)據(jù)包轉(zhuǎn)發(fā)情況

而圖7所示的是使用了本文的多路徑路由策略后，3個(gè)端口轉(zhuǎn)發(fā)數(shù)據(jù)包個(gè)數(shù)對比，port3雖然是默認(rèn)的最短路徑，卻因鏈路性能(取決于帶寬和時(shí)延設(shè)置)較差、FDP值較低，其轉(zhuǎn)發(fā)的數(shù)據(jù)包個(gè)數(shù)明顯降低；port1與port2因具備較優(yōu)的鏈路性能也可以轉(zhuǎn)發(fā)大量的數(shù)據(jù)包，從而實(shí)現(xiàn)了基于多路徑的負(fù)載均衡。

圖7 多路徑路由后s5交換機(jī)各端口數(shù)據(jù)包轉(zhuǎn)發(fā)情況

圖8展示了在使用多路徑路由策略前后，port1-port3轉(zhuǎn)發(fā)端口所轉(zhuǎn)發(fā)的數(shù)據(jù)包所占百分比，由此圖可明顯看出，在負(fù)載均衡實(shí)現(xiàn)前，port1與port2兩個(gè)端口各僅轉(zhuǎn)發(fā)了0.02%的數(shù)據(jù)包，而負(fù)載均衡實(shí)現(xiàn)后，3個(gè)轉(zhuǎn)發(fā)端口所轉(zhuǎn)發(fā)的數(shù)據(jù)包占比為5.5∶2∶2.5，基本符合其相應(yīng)的FDP比值。

圖8 負(fù)載均衡前后s5交換機(jī)各端口轉(zhuǎn)發(fā)數(shù)據(jù)包占比

4 結(jié)束語

本文提出了一種基于流量分配傾向度(FDP)的SDN多路徑路由負(fù)載均衡策略。該策略首先通過SDN控制器實(shí)現(xiàn)多路徑的查找與信息采集，隨后結(jié)合OpenFlow組表技術(shù)，實(shí)現(xiàn)了SDN網(wǎng)絡(luò)中基于多路徑的負(fù)載均衡。在使用OpenFlow組表時(shí)，本文設(shè)計(jì)了流量分配傾向度，該傾向度綜合考慮了各路徑的帶寬和時(shí)延，使網(wǎng)絡(luò)流量可以依據(jù)傾向度按比例分配到所有可用路徑中，有效降低了單路徑的負(fù)載，實(shí)現(xiàn)了多路徑的負(fù)載均衡。最后的模擬仿真實(shí)驗(yàn)結(jié)果也驗(yàn)證了該策略的可行性和優(yōu)越性。下一步的研究將考慮在多路徑性能發(fā)生變化時(shí)如何動(dòng)態(tài)地應(yīng)用此策略。