0 引言

    近年來(lái)，數(shù)據(jù)中心呈現(xiàn)爆炸式的急速發(fā)展，大量公司開(kāi)始建立自己的大型互聯(lián)網(wǎng)數(shù)據(jù)中心(Internet Data Center，IDC)。云計(jì)算技術(shù)的出現(xiàn)對(duì)數(shù)據(jù)中心網(wǎng)絡(luò)提出了新的挑戰(zhàn)，比如網(wǎng)絡(luò)安全、虛擬機(jī)遷移、多租戶管理、負(fù)載均衡等。傳統(tǒng)的數(shù)據(jù)中心采用專(zhuān)用的負(fù)載均衡設(shè)備實(shí)現(xiàn)網(wǎng)絡(luò)資源的有效利用，具有設(shè)備成本高昂和可擴(kuò)展性差等問(wèn)題，而基于軟件定義網(wǎng)絡(luò)的集中化的調(diào)度方式能夠提高資源利用率，簡(jiǎn)化網(wǎng)絡(luò)管理，降低運(yùn)維成本。

    SDN^[1]是一種將控制層和轉(zhuǎn)發(fā)層分離的新型網(wǎng)絡(luò)架構(gòu)，交換機(jī)只負(fù)責(zé)數(shù)據(jù)流的轉(zhuǎn)發(fā)，降低了網(wǎng)絡(luò)交換機(jī)的負(fù)載，控制層的功能全部由運(yùn)行于服務(wù)器上的控制器實(shí)現(xiàn)。控制器需要下發(fā)流表到交換機(jī)才能支持轉(zhuǎn)發(fā)層設(shè)備的有效運(yùn)行，而控制層與轉(zhuǎn)發(fā)層之間的通信需要遵守一定的規(guī)則，目前較普遍的是采用OpenFlow^[2]協(xié)議來(lái)實(shí)現(xiàn)信息交互。本文目的是在SDN網(wǎng)絡(luò)架構(gòu)下解決網(wǎng)絡(luò)流量高峰期鏈路的負(fù)載分布不均勻問(wèn)題，設(shè)計(jì)了負(fù)載均衡機(jī)制的總體框架、實(shí)現(xiàn)流程圖以及具體實(shí)現(xiàn)。

1 數(shù)據(jù)中心網(wǎng)絡(luò)流量特征

    國(guó)內(nèi)外學(xué)者對(duì)真實(shí)數(shù)據(jù)中心網(wǎng)絡(luò)流量特征進(jìn)行了深入的觀察研究。Mckeown研究表明數(shù)據(jù)中心網(wǎng)絡(luò)流量與傳統(tǒng)的局域網(wǎng)和廣域網(wǎng)流量有著極大的不同，內(nèi)部節(jié)點(diǎn)間的數(shù)據(jù)流量在數(shù)據(jù)中心網(wǎng)絡(luò)所有流量中占主導(dǎo)地位^[3]。Greenberg指出數(shù)據(jù)中心80%的數(shù)據(jù)流量為數(shù)據(jù)中心內(nèi)部的流量，而且85%的數(shù)據(jù)流小于100 KB^[4]。目前采用最多的是Fattree^[5]網(wǎng)絡(luò)拓?fù)?，它可以為兩兩?jié)點(diǎn)之間的流量提供多條路徑，這樣從理論上能降低單一路徑的負(fù)載率過(guò)高的問(wèn)題，而在實(shí)際應(yīng)用中還是會(huì)出現(xiàn)某條路徑上流量擁塞嚴(yán)重而其他可用路徑卻處于閑置狀態(tài)的問(wèn)題。

    數(shù)據(jù)中心網(wǎng)絡(luò)流量模型由大流和小流組成，每個(gè)數(shù)據(jù)流由許多數(shù)據(jù)包組成，這些數(shù)據(jù)包具有5個(gè)相同特征（源IP地址、源端口號(hào)、目的IP地址、目的端口號(hào)、協(xié)議類(lèi)型）。而大流是造成部分鏈路擁塞的主要原因，所以負(fù)載均衡機(jī)制主要針對(duì)大流，在調(diào)度過(guò)程中盡量忽視小流來(lái)降低調(diào)度開(kāi)銷(xiāo)。數(shù)據(jù)流的大小由其所含字節(jié)數(shù)決定，同時(shí)數(shù)據(jù)流越大，持續(xù)的時(shí)間越長(zhǎng)，小流持續(xù)時(shí)間很短。本文將字節(jié)數(shù)大于100 KB的流界定為大流。

2 負(fù)載均衡實(shí)現(xiàn)的總體框架

    控制器的負(fù)載均衡功能模塊如圖1所示，主要包括拓?fù)浒l(fā)現(xiàn)模塊、大流監(jiān)測(cè)模塊、流量收集模塊、路徑計(jì)算模塊、流表導(dǎo)入模塊。拓?fù)浒l(fā)現(xiàn)模塊幫助控制器掌握通過(guò)全局的拓?fù)湫畔?，包括主機(jī)的位置信息、交換機(jī)之間的連接等。大流監(jiān)測(cè)模塊在鏈路利用率最大路徑上找出并標(biāo)記大流。流量收集模塊周期性地收集OpenFlow交換機(jī)網(wǎng)絡(luò)的流量信息，為兩個(gè)節(jié)點(diǎn)之間的多條路徑選擇提供參考流量監(jiān)測(cè)模塊統(tǒng)計(jì)交換機(jī)接口的流量信息，用于分析計(jì)算各鏈路的鏈路利用率。路徑計(jì)算模塊為大流的重路由提供支持，是實(shí)現(xiàn)負(fù)載均衡功能的重要部件。流表導(dǎo)入模塊是通過(guò)控制器向OpenFlow交換機(jī)發(fā)送Packet_out消息實(shí)現(xiàn)的，動(dòng)態(tài)地將大流的最終得出的重路由路徑添加到交換機(jī)流表，從而實(shí)現(xiàn)OpenFlow網(wǎng)絡(luò)的負(fù)載均衡功能。負(fù)載均衡算法的實(shí)現(xiàn)流程如圖2所示。

3 各功能模塊的數(shù)學(xué)建模與實(shí)現(xiàn)

    首先為負(fù)載均衡制定一個(gè)啟動(dòng)閾值，這里采用負(fù)載均衡參數(shù)：

其中l(wèi)oad_i，j(t)代表在t時(shí)刻鏈路<i，j>上的已經(jīng)被占用的帶寬^[6]，N是網(wǎng)絡(luò)中所有鏈路的數(shù)目。下面簡(jiǎn)單描述各模塊的實(shí)現(xiàn)方式。

3.1 拓?fù)浒l(fā)現(xiàn)模塊

    拓?fù)浒l(fā)現(xiàn)模塊的功能是收集網(wǎng)絡(luò)的拓?fù)湫畔ⅲ瑢⑵浔４嬖谕負(fù)鋱D表中，并對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行管理?？刂破髋c交換機(jī)之間是在OpenFlow標(biāo)準(zhǔn)協(xié)議的基礎(chǔ)下進(jìn)行通信的，但是控制器并不能通過(guò)Open。Flow協(xié)議獲得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，是通過(guò)LLDP組件^[7]發(fā)送LLDP(Link Layer Discovery Protocol)數(shù)據(jù)包到OpenFlow交換機(jī)，再收集并解析交換機(jī)反饋的LLDP數(shù)據(jù)包，從而實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涓兄?/p>

3.2 大流監(jiān)測(cè)模塊

    由于本文所提出的負(fù)載均衡機(jī)制是針對(duì)大流的，所以必須有一種方法將大流和小流區(qū)分開(kāi)來(lái)。文獻(xiàn)[8]對(duì)3種主流的大流監(jiān)測(cè)機(jī)制進(jìn)行了分析比較，包括采樣監(jiān)測(cè)、應(yīng)用監(jiān)測(cè)和統(tǒng)計(jì)監(jiān)測(cè)。文獻(xiàn)[9]中提出探測(cè)大流最有效的方式是在終端主機(jī)進(jìn)行，一方面占用的資源比例相對(duì)交換機(jī)要少，從而避免大流監(jiān)測(cè)占用過(guò)多的交換機(jī)端資源；另一方面流的狀態(tài)也取決于終端應(yīng)用程序生成數(shù)據(jù)包的快慢，而不是網(wǎng)絡(luò)的鏈路狀態(tài)，終端對(duì)應(yīng)用程序發(fā)包速率的可知性更強(qiáng)。監(jiān)測(cè)原理是通過(guò)觀測(cè)終端主機(jī)socket緩存區(qū)，當(dāng)緩存區(qū)內(nèi)具有相同特征的數(shù)據(jù)包大小超過(guò)100 KB，它就會(huì)被標(biāo)記為大流，本文便采用對(duì)主機(jī)端的統(tǒng)計(jì)監(jiān)測(cè)方式來(lái)進(jìn)行大流監(jiān)測(cè)，主機(jī)端需要精確統(tǒng)計(jì)和維護(hù)數(shù)據(jù)流的速率和字節(jié)等信息，再將統(tǒng)計(jì)信息通過(guò)交換機(jī)發(fā)送到控制器，從而實(shí)現(xiàn)控制器的大流監(jiān)測(cè)功能。

3.3 流量收集模塊

    這個(gè)組件的目的是詢問(wèn)每個(gè)OpenFlow交換機(jī)的流量信息，再將所有收到的反饋信息進(jìn)行聯(lián)合并最終存儲(chǔ)到控制器的存儲(chǔ)單元。這些收集到的數(shù)據(jù)被路徑計(jì)算模塊用來(lái)計(jì)算不同鏈路上的負(fù)載，因?yàn)榛跈?quán)重的多路徑路由的核心思想是將大流的數(shù)據(jù)包分配到負(fù)載較輕的鏈路上，因此需要確切知道路徑上所有可能的鏈路負(fù)載。這個(gè)單元模塊周期性地通過(guò)輪詢的方式收集每個(gè)OpenFlow交換機(jī)的流數(shù)量、流表以及端口數(shù)據(jù)，并作為一個(gè)快照對(duì)象進(jìn)行存儲(chǔ)。每個(gè)快照對(duì)象都會(huì)通過(guò)一串?dāng)?shù)字標(biāo)識(shí)，每個(gè)周期生成新的快照對(duì)象后數(shù)字標(biāo)識(shí)會(huì)自動(dòng)加1，存儲(chǔ)區(qū)只會(huì)保存最新的2個(gè)快照對(duì)象，其他的功能模塊都有獲得快照對(duì)象數(shù)據(jù)的權(quán)限。

3.4 路徑計(jì)算模塊

    初始狀態(tài)采用Floyd^[10]算法計(jì)算基于跳數(shù)的Top-K最短路徑，然后需要對(duì)每條路徑的狀態(tài)進(jìn)行評(píng)估。本文主要對(duì)路徑的兩個(gè)方面指標(biāo)進(jìn)行評(píng)估，一個(gè)是路徑所包含鏈路的長(zhǎng)度，這個(gè)體現(xiàn)在跳數(shù)（Hop Count）；另外一個(gè)指標(biāo)是路徑上的負(fù)載，這個(gè)體現(xiàn)在這條路徑所包含的交換機(jī)和鏈路上的流量。由于每條路徑上包含多個(gè)交換機(jī)以及多條鏈路，不能簡(jiǎn)單地以總流量的平均數(shù)來(lái)表示這條路徑的負(fù)載，而應(yīng)該根據(jù)特定的交換機(jī)和鏈路來(lái)代表該路徑的負(fù)載情況。交換機(jī)的負(fù)載通過(guò)它所統(tǒng)計(jì)的PC(Packet Count)和BC(Byte Count)來(lái)體現(xiàn)，鏈路的負(fù)載通過(guò)端口的轉(zhuǎn)發(fā)率（Forwarding Rate）來(lái)表示。這些數(shù)據(jù)可以通過(guò)控制器周期性地向OpenFlow交換機(jī)發(fā)送狀態(tài)請(qǐng)求消息得到。每條路徑的負(fù)載狀況可以表示為S=(H，P，B，F(xiàn))，其中H表示跳數(shù)；P=Max(P₁，P₂，…，P_H)，P_i表示該路徑的第i臺(tái)交換機(jī)所轉(zhuǎn)發(fā)的封包數(shù)量，共包含H臺(tái)交換機(jī)；B=Max(B₁，B₂，…，B_H)，B_i表示該路徑的第i臺(tái)交換機(jī)所轉(zhuǎn)發(fā)的字節(jié)數(shù)量。F=Max(F₁，F(xiàn)₂，…，F(xiàn)_H)，F(xiàn)_i表示該鏈路經(jīng)過(guò)的第i臺(tái)交換機(jī)出端口的轉(zhuǎn)發(fā)率。由于參數(shù)之間的差異比較大，需要先進(jìn)行如下變換^[11]：

    每一條路徑可以用矩陣R=(r_h r_p r_b r_f)表示,權(quán)重向量W=(0.35，0.20，0.20，0.25)，各個(gè)參數(shù)值根據(jù)經(jīng)驗(yàn)自己定義，這里路徑的長(zhǎng)度取0.35顯示了其重要性。每個(gè)節(jié)點(diǎn)對(duì)之間的所有路徑可以通過(guò)一個(gè)矩陣表示為：

    Q_i表示路徑i最后的權(quán)值，根據(jù)權(quán)值可以確定數(shù)據(jù)流經(jīng)i節(jié)點(diǎn)傳輸?shù)絡(luò)節(jié)點(diǎn)的最佳路徑。路徑計(jì)算模塊偽代碼如下：

    Algorithm : Route Construction

    (1)Connect the topology with the RYU controller

    (2)Detect the topology and do the following activities:

    (3)Calculate top K shortest paths between each pair of nodes using Top-K Shortest Path algorithm(TKSP is the extension of Open Shortest Path First).

    (4)Evaluate the Top-K path with the proposed method.

    (5)Sort the paths between each pair of nodes according to the evaluation and store the results to the controller.

    (6)Reconstruct the path using step1-5 in case of a node/link failure.

3.5 流表導(dǎo)入模塊

    中心控制器通過(guò)路徑計(jì)算模塊產(chǎn)生的結(jié)果生成轉(zhuǎn)發(fā)規(guī)則，然后封裝到Packet_out消息中導(dǎo)入到支持OpenFlow的交換機(jī)，交換機(jī)流表添加該轉(zhuǎn)發(fā)規(guī)則并根據(jù)更新的流表項(xiàng)來(lái)指導(dǎo)流量轉(zhuǎn)發(fā)。由于網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)都是不可預(yù)測(cè)的，交換機(jī)流表會(huì)伴隨負(fù)載均衡機(jī)制實(shí)時(shí)、動(dòng)態(tài)地更新，而且過(guò)期的流表項(xiàng)會(huì)根據(jù)交換機(jī)配置而刪除。

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

    本文采用Mininet2.2.0^[12]作為一個(gè)開(kāi)發(fā)環(huán)境模擬數(shù)據(jù)中心網(wǎng)絡(luò)場(chǎng)景，搭建如圖3所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，在Ubuntu Kylin 14.04.3上運(yùn)行RYU控制器，結(jié)合iperf工具來(lái)產(chǎn)生TCP(Transmission Control Protocol)數(shù)據(jù)流和UDP(User Datagram Protocol)數(shù)據(jù)流，并且能夠測(cè)量端到端的吞吐量，從而得出整個(gè)網(wǎng)絡(luò)的吞吐量。host1～4同時(shí)向host5～8發(fā)送數(shù)據(jù)流量，在RYU^[12]控制器中結(jié)合拓?fù)浒l(fā)現(xiàn)模塊、流量監(jiān)測(cè)模塊、路徑計(jì)算模塊和流表導(dǎo)入模塊來(lái)對(duì)負(fù)載均衡算法進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)通過(guò)h1～h16傳輸時(shí)延、總吞吐量和總體鏈路利用率這3個(gè)指標(biāo)來(lái)驗(yàn)證本文所提出的負(fù)載均衡算法的有效性。總體鏈路利用率通過(guò)下式得到：

其中，MAX_LOAD代表每條物理鏈路最大帶寬，仿真實(shí)驗(yàn)的信息見(jiàn)表1。

    選擇h1和h16為網(wǎng)絡(luò)時(shí)延測(cè)量的觀測(cè)對(duì)象,實(shí)驗(yàn)結(jié)果如圖4所示，在實(shí)驗(yàn)進(jìn)行的前47 s數(shù)據(jù)包從h1～h16延時(shí)很低，而且本文所提出的LB(Load balance)算法和基于最短路徑算法的時(shí)延曲線表現(xiàn)出了極高的相似度。這是因?yàn)閯傞_(kāi)始時(shí)鏈路負(fù)載較輕，兩種算法都是采用h1-S1-S9-h16來(lái)傳輸流量，而LB算法由于需要監(jiān)測(cè)數(shù)據(jù)流量并且周期性地向控制器發(fā)送網(wǎng)絡(luò)狀態(tài)信息，這樣會(huì)產(chǎn)生部分開(kāi)銷(xiāo)而導(dǎo)致延時(shí)略高于基于最短路徑算法；但是47 s之后LB算法下的時(shí)延明顯低于采用OSPF算法的時(shí)延，這是因?yàn)樘嗟牧髁考性谧疃搪窂絟1-S1-S9-h16，而其他可用路徑處于空閑狀態(tài)，負(fù)載不均衡度大于判決門(mén)限，就會(huì)觸發(fā)負(fù)載均衡機(jī)制，原路徑上的流量會(huì)轉(zhuǎn)移到其他可用路徑，鏈路利用率也得到了明顯提升，如圖5所示。網(wǎng)絡(luò)整體吞吐量的性能比較如圖6所示，當(dāng)負(fù)載低于550 Mb/s時(shí)，兩者的性能曲線非常相似，由于LB算法需要傳輸額外的鏈路狀態(tài)信息導(dǎo)致吞吐量會(huì)略高于550 Mb/s；當(dāng)負(fù)載超過(guò)550 Mb/s，基于最短路徑算法網(wǎng)絡(luò)出現(xiàn)擁塞，其他可用鏈路得不到有效利用，吞吐量的增長(zhǎng)明顯放緩。而LB算法下的網(wǎng)絡(luò)吞吐量在550～700 Mb/s區(qū)間能一直保持快速增長(zhǎng)。因此本文提出的LB算法相比傳統(tǒng)的OSPF算法能夠在負(fù)載不均衡情況下改善網(wǎng)絡(luò)性能。

5 結(jié)束語(yǔ)

    本文設(shè)計(jì)了負(fù)載均衡功能實(shí)現(xiàn)的總體框架，主要包括拓?fù)浒l(fā)現(xiàn)模塊、流量監(jiān)測(cè)模塊、路徑計(jì)算模塊、流表導(dǎo)入模塊。設(shè)計(jì)了負(fù)載均衡功能的實(shí)現(xiàn)流程圖，對(duì)相關(guān)的數(shù)學(xué)模型進(jìn)行了詳細(xì)的分析設(shè)計(jì)，確定了以大流為目標(biāo)流的調(diào)度策略，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該負(fù)載均衡算法相比傳統(tǒng)的OSPF算法能夠?qū)崿F(xiàn)更低的網(wǎng)絡(luò)延時(shí)和更高的總體鏈路利用率和吞吐量。

    該算法的不足之處是沒(méi)有考慮到大流出現(xiàn)重復(fù)調(diào)度的情況，如果某個(gè)大流被多次選為目標(biāo)流調(diào)度，可能會(huì)使情況更糟糕，而且流的轉(zhuǎn)移開(kāi)銷(xiāo)也會(huì)影響負(fù)載均衡的實(shí)現(xiàn)效率。降低大流在調(diào)度過(guò)程中的開(kāi)銷(xiāo)具有重要的意義，上述兩點(diǎn)將是下一步需要重點(diǎn)關(guān)注的內(nèi)容。

參考文獻(xiàn)

[1] 左青云，陳鳴，趙廣松.基于Open Flow的SDN技術(shù)研究[J].軟件學(xué)報(bào)，2013，24（5）：1078-1097.

[2] Open Networking Foundation.OpenFlow[EB/OL].(2016)[2016].https：//www.opennetworking.org/en/sdn-resources/openflow.

[3] MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al.OpenFlow：Enabling innovation in campus networks[J].SIGCOMM Computer Communication Review，2008，38(2)：69-74.

[4] GREENBERG A，HAMILTON J R，JAIN N，et al.VL2：A scalable and flexible data center network[C].Proceedings of the AC_MSIGCOMM 2009 Conference on Data Communication.Barcelona，Spain，2009：51-62.

[5] GREENBERG A，HAMILTON J，MALTZ D A，et al.The cost of a cloud：research problems in data center networks[C].In ACM SIGCOMM，2008：68-73.

[6] Long Hui.Research on the OpenFlow -based load-balancing routing in distributed networks[D].Shanghai：Shanghai Jiao Tong University，2013.

[7] 張遠(yuǎn).基于OpenFlow的負(fù)載均衡研究[D].北京：北京工業(yè)大學(xué)，2014.

[8] 李龍，付斌章.Nimble：一種適用于OpenFlow網(wǎng)絡(luò)的快速流調(diào)度策略[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（5）：1056-1068.

[9] CURTIS A R，KIM W.Mahout：low-overhead datacenter traffic management using end-host-based elephant detection[J].IEEE INFOCOM，2011，2(3)：1629-1637.

[10] BACKHOUSE R C，EIJINDE J P H W，GASTEREN A.J.M.V.Calculating path algorithms[J].Science of Computer Programming，1994，22(1-2)：3-19.

[11] Li Jun，Chang Xiangqing，Ren Yongmao，et al.An effective path load balancing mechanism based on SDN[C].IEEE 13th International Conference on Trust，Security and Privacy in Computing and Communications，2014.

[12] Mininet Team.Mininet：An instant virtual network on your laptop[EB/OL].(2016)[2016].http://www.mininet.org/.