基于流量分配傾向度的SDN多路徑負載均衡

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

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

0 引 言

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

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

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

1 相關研究

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

圖1 SDN架構

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

2 多路徑路由負載均衡的設計與實現

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

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

(2)隨后依據每條路徑的帶寬和時延參數計算出各路徑的流量分配傾向度(flow distribution propensity，FDP)；

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

仿真實驗結果表明，該策略可有效提高SDN網絡中對于多路徑的使用率，實現了多路徑路由的負載均衡。

2.1 多路徑發現與信息采集

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

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

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

2.2 路徑信息采集

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

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

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

(1)最大剩余帶寬

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

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

(1)

其中，UsedBands代表采集時間間隔T內端口s的已用帶寬，bytesrx代表T間隔內該端口接收的數據字節總數，bytestx代表T間隔內該端口傳輸的數據字節總數。

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

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

(2)

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

(2)時延

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

在SDN網絡中獲取某鏈路時延原理如圖2所示。設某單一鏈路包含兩個OpenFlow交換機SA和SB，SDN控制器可以通過向SA發送包含LLDP的數據包，并指示其將數據包轉發至SB，同時記錄數據發送的時間戳，然后與收到來自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組表技術應用

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

圖3 OpenFlow組表結構

圖4 Select類型組表結構

2.4 流量分配傾向度(FDP)

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

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

(5)

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

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

wp=Ip

(6)

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

(7)

∑qpi=Q

(8)

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

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

3 實驗及結果分析

3.1 實驗環境與網絡拓撲配置

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

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

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

圖5 實驗網絡拓撲

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

3.2 實驗過程與結果分析

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

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

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

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

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

圖6 多路徑路由前s5交換機各端口數據包轉發情況

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

圖7 多路徑路由后s5交換機各端口數據包轉發情況

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

圖8 負載均衡前后s5交換機各端口轉發數據包占比

4 結束語

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