1基于擁塞預測的負載均衡路由算法研究目錄 2 3 4 6 8 1 1數(shù)據(jù)中心網(wǎng)絡在運行中，網(wǎng)絡運行環(huán)境與網(wǎng)絡流量狀態(tài)總是在不斷發(fā)生改變，這也導致網(wǎng)絡的服務質(zhì)量(QualityofService,QoS)總是不斷發(fā)生改變。當網(wǎng)絡運行環(huán)境發(fā)生改變時，如何靈活調(diào)整和配置網(wǎng)絡資源來應對網(wǎng)絡狀態(tài)變化滿足用戶的服務質(zhì)量需求成為了一個極大的困難挑戰(zhàn)。如何實現(xiàn)網(wǎng)絡資源利用與路由調(diào)整收斂速度的平衡，在發(fā)生擁塞之前避免，這既能改善用戶體驗也有效防止網(wǎng)絡性能惡化。隨著通信網(wǎng)絡的不斷發(fā)展，流量工程成為解決上述困難的研究熱點之一。本章基于軟件定義網(wǎng)絡中的流量工程問題，提出了基于擁塞預測的路由算法。流量工程通過不斷的監(jiān)測和分析過去和當前2數(shù)據(jù)流鏈路擁塞數(shù)據(jù)流鏈路擁塞23數(shù)據(jù)流定的網(wǎng)絡中，終端用戶使用不同類型的應用程序，產(chǎn)生各類QoS要求的數(shù)據(jù)流量，同時換機集合，E代表網(wǎng)絡中的鏈路集合，定義網(wǎng)絡中有n個相互鏈接的OpenFlow交換機，Bnn表示網(wǎng)絡的帶寬矩陣，B;表示交換機i與交換機j之間的鏈路帶寬。定義P表示網(wǎng)i→j(1;)。考慮多個流量類別(本文考慮帶寬與時延),使用Cα2表示流量需求矩陣，其中C?1表示流f對應的帶寬矩陣，Cf?表示流f對應的時延矩陣(流f的最大可允許延遲3隨著移動互聯(lián)網(wǎng)迅猛發(fā)展，大量應用不斷涌現(xiàn)，網(wǎng)絡中對不同流量類別有不同的要求，但用戶對延遲敏感的業(yè)務體驗要求越來越高。解決由于網(wǎng)絡擁塞造成的傳輸延時增加問題以及由于流量狀況隨著空間和時間變化而造成的負載不均衡問題也是我們面臨的存在以下幾個問題，如：利用網(wǎng)絡的動態(tài)行為來實際地調(diào)整網(wǎng)絡資源問題和利用SDN控大都是在擁塞發(fā)生之后才進行擁塞處理，沒有很好的預測鏈路擁塞的可能性并進行流量調(diào)整。為了能夠更合理地解決上述問題，本文提出一種基于擁塞預測的負載均衡路由算理有效的進行流量分配，動態(tài)調(diào)節(jié)網(wǎng)絡負載，從而保證無論網(wǎng)絡狀態(tài)如何變化，都能夠本章的基本思想是依據(jù)控制器實時監(jiān)測交換機端□的吞吐量，當鏈路的剩余帶寬超過一定閾值的時候，根據(jù)之前時間的流量傳輸速率與鏈路剩余帶寬，預測鏈路發(fā)生擁塞的可能性，將此可能性作為權值加入到流量分配公式中，實時調(diào)節(jié)流量分配，來達到減緩以及預防網(wǎng)絡擁塞的目的。其整個工作流程如圖1.1所示。4聲”1.2.2鏈路剩余帶寬預測機制在網(wǎng)絡流量傳輸之前，根據(jù)QoS要求(如時延，帶寬等),尋找到符合要求的多條路徑，并進行流量分配。但隨著流量傳輸?shù)倪M行，鏈路中的流量在不斷增加，各鏈路與路徑都有可能導致?lián)砣a(chǎn)生丟包問題。因此需要周期性的測量交換機的吞吐率、計算鏈路的擁塞可能性，并適時更改流量的路徑，以防止鏈路擁塞，減少數(shù)據(jù)包的丟失。SDN控制器實時監(jiān)控各交換機的流量與各鏈路的剩余帶寬情況，當某個交換機的吞吐率超過一定閾值(鏈路剩余帶寬達到一定閾值),則開始計算當前路徑的擁塞可能性，并將其作為權值，加入到控制器的流量分配中。為了防止網(wǎng)絡中的“流量噪聲”造成的流量抖動帶來的極值影響，本章采用指數(shù)加權平均移動模型(ExponentiallyWeightedMoving-Average,EWMA)[33,使得本章中的流量傳輸速度不會因為“流量噪聲”的存在產(chǎn)生突變而影響預測結果，提升整個系統(tǒng)的魯棒性與穩(wěn)定性。其具體公式如下：5速率實際測量值。λ(t)表示上一時刻鏈路傳輸速率估計值的可信度，其值越接近1,表示t-1時刻的測量值越可信(其是突變數(shù)據(jù)的可能性越低)。其決定了鏈路傳輸速率估計器估計實際數(shù)據(jù)發(fā)生變化的能力，即時效性。顯而易見，隨著其值的增大，估計器的時公式(1.2)中，B?,表示鏈路!在t-1到t時刻所傳輸?shù)牧髁?，△T(t)表示t-1到t時其中，△max(t)表示最近觀察到的m個帶寬值中的最大值和最小值之間的差值，即樣本的極差；β為常數(shù)，是VHF的常數(shù)因子。m表示最近的帶寬個數(shù)。根據(jù)上述公式，可以估算經(jīng)過t時刻(即下一時刻t+1)后，鏈路的剩余帶寬：6公式(1.4)中，B表示鏈路l,的整體帶寬。1.2.3鏈路擁塞預測的流量分配與約束(1)基于擁塞預測的流量分配為保證各個鏈路的擁塞可能性的統(tǒng)一量綱處理，按照下式計算各個鏈路的擁塞可能性⑧:表示按照當前傳輸速率，傳輸完成閾值之后的剩余帶寬需要的時間。@;值越小，則擁塞的可能性就越大。@;值越大，當前鏈路產(chǎn)生擁塞的可能性就越小。在流量傳輸之前，按照傳統(tǒng)的QoS多路徑路由方法，選取符合帶寬與時延要求的n公式(1.7)中，R,表示整條路徑p的最少剩余帶寬，R表示鏈路!,剩余帶寬，D?表7若當前路徑中的各鏈路均未達到帶寬閾值，則按照無阻塞權重的公式計算流量分配可能性，并選擇該條路徑中的最小權值@;。因為當前路徑的擁塞情況由最可能擁塞的鏈路決定。本文中沒有對帶寬與時延最初優(yōu)先級區(qū)分，若需要區(qū)分時延與帶寬的優(yōu)先級，如時延的敏感度超過帶寬的敏感度，則公式(1.7)可以改寫為：以當前計算得到的流量分配概率φp,參與到控制器的流量分配中。本文使用為了進一步闡述多路徑的流量分配過程，建立簡單的數(shù)學模型進行模擬。假設兩個主機之間存在n條可選路徑p,,i∈(1,2,…,n),動作桶的權值為φp(即公式(1.8)計算的會根據(jù)各路徑的分配概率的不同，將需要轉(zhuǎn)發(fā)的數(shù)據(jù)包散列所有可選路徑P,,i∈(1,2,…,n)中。假設流量A中包含的數(shù)據(jù)包個數(shù)為Q,則每條可選路徑所分配的數(shù)通過結合使用OpenFlow組表中的select組表和各個路徑的流量分配概率，包含轉(zhuǎn)發(fā)現(xiàn)了流量的均衡分配，緩解了流量擁塞現(xiàn)象，減少了數(shù)據(jù)包的丟失，達到了多路徑負載(2)鏈路負載約束8網(wǎng)絡中節(jié)點根據(jù)角色可以分為源節(jié)點、目的節(jié)點以及轉(zhuǎn)發(fā)節(jié)點，流從源節(jié)點出發(fā)，經(jīng)過轉(zhuǎn)發(fā)節(jié)點，流向源節(jié)點。為保證流的有向性，建立約束1:對于當前流來說，若當前鏈路的剩余帶寬不足以通過，則不會選擇當前鏈路(或者率的條件，即約束2:對于當前流與當前路徑，當前路徑的所有鏈路總時延不能大于當前流所允許的最大時延，即約束3:A,∈{0,1},Vf∈{1,…,p},V1.2.4流量路由模型對于流f來說，取預測消耗帶寬與實際消耗帶寬的最大值，即MS,=max(PM,FM)根據(jù)以上分析，以最大化帶寬利用率為優(yōu)化目標，建立以下路由模型9在流量分配之初，鏈路剩余帶寬沒有超過閾值，不會進行擁塞 按照前述計算鏈路擁塞情況，并將結果帶入優(yōu)化目標中，進行路徑選取，具體過程1:For數(shù)據(jù)流中的第f個流Flowf:3:尋找源節(jié)點到目的節(jié)點之間的可選路徑4:For可選路徑中的每條路徑8:更新網(wǎng)絡的帶寬矩陣與時延矩陣20:If擁塞緩解then21:更新鏈路代價函數(shù)23:重新路由，更新流量分配策略24:endif25:endif調(diào)整鏈路的代價函數(shù)與流量分配策略，降低鏈路擁塞的可能性，實現(xiàn)網(wǎng)絡負載均衡，提1.4仿真實驗與結果分析1.1.1仿真實驗環(huán)境設置的主要原因是在任意兩點之間存在著多條可用鏈路，除了標注的鏈路帶寬，其余均為默認帶寬1Gbps。該實驗部分分別從丟包率、平均時延、網(wǎng)絡吞吐量以及資源利用率四個方面進行對比，本文所使用的測量工具包括iperf以及ping命令，4個數(shù)據(jù)發(fā)送端和41.1.2結果分析如圖1.4所示。一曰一·本文算法876432122023024095以及本章提出的算法。通過仿真結果可以看出：當數(shù)據(jù)流大小低于170MB/s時，3算法丟包現(xiàn)象，相比其他幾種算法，本章提出算法的丟包率基本不變，保持在一個相對較低的水平。通過分析實驗結果：ECMP算法的丟包率存在一定的反復性；WSP在跳數(shù)最少的鏈路集合中選擇帶寬最大的傳輸路徑；而ECMP算法作送端傳輸路徑的選擇算法為哈希算法，當發(fā)送端數(shù)據(jù)流被分配到負載較大的鏈路時導致丟包率增加，當數(shù)據(jù)流被分配到負載較少的鏈路時，整個網(wǎng)絡的丟包率會降低；本章所提出的算法依據(jù)鏈路擁塞情況及時調(diào)整不同的策略，相比于ECMP,WSP算法表現(xiàn)效果更優(yōu)。本章所提出算法通過鏈路擁塞預測動態(tài)遷移數(shù)據(jù)流的方式緩解鏈路負載，從而降吞吐量白白兇200210220230240該部分測量了各個算法在發(fā)送端不同數(shù)據(jù)流大小時的吞吐量大小，仿真實驗結果如圖1.5所示。從圖1.5可以看出：當數(shù)據(jù)流速率小于180M/s時，各算法吞吐量基本相同，呈現(xiàn)出線性增加的趨勢，隨著發(fā)送端數(shù)量逐漸增加；當發(fā)送速率大于180M/s時，幾種算法的吞吐量趨勢差距逐漸明顯，其中當數(shù)據(jù)流速率大于220M/s時，WSP算法的吞吐量達到飽和，這主要是由于WSP算法選擇跳數(shù)最小的傳輸路徑，但并沒有考慮該傳輸路徑的鏈路可用帶寬大??；當數(shù)據(jù)流數(shù)速率大于240M/s時，ECMP算法出現(xiàn)一定的平穩(wěn)趨勢，但總體來看還是逐漸升高；本章算法比ECMP算法吞吐量更高，本章提出的算法則呈現(xiàn)出線性上升的變化趨勢。主要原因在于，當發(fā)送端數(shù)量較少時，鏈路負載較小，各條數(shù)據(jù)流之間沒有干擾，整個網(wǎng)絡的吞吐量不會由于鏈路擁塞而發(fā)生變化；當發(fā)送端的數(shù)據(jù)流速率大于180M/s時，鏈路負載加重，由于鏈路發(fā)生擁塞導致吞吐量效果不佳。而本文提出的傳輸機制，充分考慮到了鏈路剩余帶寬以及鏈路時延對整個網(wǎng)絡吞吐量的影響，因此，相比較其他兩種種算法，能夠獲得更高的吞吐量。數(shù)據(jù)流大小(MB/s)最后，測量了各個算法的鏈路帶寬的利用率，從圖1.6中可以看出，隨著數(shù)據(jù)流的80時，ECMP和本文兩種算法的鏈路利用率呈現(xiàn)出先下降后上升的趨勢，這是由兩種算法本身的性質(zhì)所決定的：ECMP通過哈希的方式為每條數(shù)據(jù)流選擇路徑，在等數(shù)量大小現(xiàn)出和ECMP算法大致相同的趨勢是因為Hedera算法中使用在本實驗中并沒有嚴格區(qū)分大象流和老鼠流，因此二者的變化趨勢整體上相似。同時，從實驗結果中可以看出WSP算法的鏈路利用率隨著數(shù)據(jù)流數(shù)量的增加達到90%以上，這也與算法本身的性質(zhì)相關，由于選擇路徑的主要依據(jù)為跳數(shù)，無法根據(jù)鏈路的實時狀直到達到鏈路的飽和程度。相比于其他幾種算法，本章提出的算法，鏈路利用率呈現(xiàn)出算法鏈路帶寬資源利用率低效，造成資源的浪費。本章提出的算法既滿足了對數(shù)據(jù)發(fā)送不同策略使得各條路徑分配的流量各不相同，導致了時延上的差異。從圖1.7中可以看出：隨著發(fā)送數(shù)據(jù)流速率逐漸增加，三種算法的平均分組時延都