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

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

0 引 言

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

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

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

1 相關(guān)研究

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

圖1 SDN架構(gòu)

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

2 多路徑路由負載均衡的設計與實現(xiàn)

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

(1)首先由控制器通過深度優(yōu)先遍歷算法(DFS)獲取多路徑及每條路徑拓撲，同時采集并保存各路徑的帶寬與時延信息；

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

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

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

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

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

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

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

2.2 路徑信息采集

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

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

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

(1)最大剩余帶寬

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

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

(1)

其中，UsedBands代表采集時間間隔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交換機端口的最小剩余帶寬值，因此路徑最大剩余帶寬Bp計算公式如式(2)所示

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

(2)

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

(2)時延

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

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

Dl=(D1+D2-Da-Db)

(3)

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

(4)

圖2 時延原理

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

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

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

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

2.4 流量分配傾向度(FDP)

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

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

(5)

在網(wǎng)絡拓撲中，鏈路的帶寬通常為10 Mbps以上，而流量傳輸過程中各鏈路的時延通常為小數(shù)，在設置流量分配傾向度時，本文期待路徑的帶寬越高、時延越低，則其流量分配傾向度越高。因此式(5)中采用路徑的時延作為分母，路徑可用帶寬最小值作為分子。

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

wp=Ip

(6)

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

(7)

∑qpi=Q

(8)

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

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

3 實驗及結(jié)果分析

3.1 實驗環(huán)境與網(wǎng)絡拓撲配置

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

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

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

圖5 實驗網(wǎng)絡拓撲

為模擬主機之間的通信，本實驗使用iperf命令設置h1為服務主機，h2-h4為客戶端主機。

3.2 實驗過程與結(jié)果分析

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

實驗首先通過深度優(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ù)控制器采集的路徑信息計算出3條路徑的流量分配傾向度(FDP)比值為5∶2∶3。

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

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

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

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

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

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

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

4 結(jié)束語

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