V基于大象流的負載均衡路由算法研究報告目錄TOC\o"1-3"\h\u2812基于大象流的負載均衡路由算法研究報告 157611.1網(wǎng)絡模型 2179841.2問題描述 3260591.2.1網(wǎng)絡中流的定義 3188851.2.2大象流調度策略 4105491.2.3路由約束與路由模型 6120881.3大象流負載均衡算法設計 873981.3.1基于自適應閾值的大象流檢測算法 8201391.3.2基于概率選擇的重路由路徑算法 869441.3.3自適應輪詢周期調整算法 11230151.4仿真實驗與結果分析 1253291.4.1仿真實驗環(huán)境設置 1249301.4.2結果分析 13在網(wǎng)絡環(huán)境越來越復雜的情況下，大流小流現(xiàn)象的存在為快速提升網(wǎng)絡性能提供了一種有效的改善思路?，F(xiàn)有的研究表明，數(shù)據(jù)中心網(wǎng)絡中90%的流小于100KB（老鼠流），而10%的流則具有大量的數(shù)據(jù)（100KB到1GB）或更長的生存周期（大象流），它們產(chǎn)生超過80%的數(shù)據(jù)量。相比于小流，大象流更易于導致網(wǎng)絡擁塞而影響到網(wǎng)絡性能。考慮到大流和小流各有特點，其各自對應的調度算法也必然存在不同，如果采用相同的調度算法，其調度效果可能不顯著，甚至導致網(wǎng)絡性能惡化。為了有效提高整個網(wǎng)絡的擁塞避免和數(shù)據(jù)高效傳輸能力，實現(xiàn)大象流的檢測與鏈路負載均衡。本章提出了基于大象流的負載均衡路由算法。通過檢測大象流的自適應閾值，并基于概率選擇進行重路由以及設計自適應輪詢周期，進一步提高網(wǎng)絡性能，實現(xiàn)網(wǎng)絡負載均衡。1.1網(wǎng)絡模型圖1.1網(wǎng)絡架構圖如圖1.1所示，本章SDN網(wǎng)絡架構主要有OpenFlow交換機與SDN控制器組成，其中，SDN控制器主要由以下幾個模塊組成：拓撲發(fā)現(xiàn)模塊：控制器定期向交換機發(fā)送LLDP包以便搜集網(wǎng)絡設備的鏈接信息。網(wǎng)絡檢測模塊：定期收集交換機的接口數(shù)據(jù)以及流數(shù)據(jù)，以便獲取整個網(wǎng)絡的信息。閾值計算模塊：根據(jù)拓撲發(fā)現(xiàn)模塊以及網(wǎng)絡檢測模塊收集到的鏈路狀態(tài)信息，計算鏈路的平均剩余可用帶寬，基于平均剩余可用帶寬求出流分類的閾值，并且把該閾值發(fā)送給邊緣層交換機，由邊緣層交換機判定是否是大象流。大象流檢測模塊與重路由模塊：如果存在擁塞的鏈路，則控制器將查找通過該鏈路的大象流，并將具有最大傳輸速率的大象流依次重新調度到新的擁塞最少的路徑，直到消除該鏈路上的擁塞為止。大象流的新路徑將根據(jù)基于概率的路徑選擇算法進行計算。擁塞檢測模塊：根據(jù)端口統(tǒng)計信息，控制器可以獲取每個鏈路的負載。當鏈路的負載超過擁塞閾值時，該鏈路被標記為擁塞鏈路。在本文中擁塞閾值定義為鏈路容量的70％。輪詢周期調整模塊：控制器將會根據(jù)鏈路與流的狀態(tài)，按照自適應輪詢周期調整算法調整輪詢周期。流表管理模塊：一旦計算出流的轉發(fā)路徑，流表管理模塊則以流表的形式在路徑上的交換機中安裝轉發(fā)規(guī)則。當數(shù)據(jù)流進入交換機時，該交換機僅根據(jù)流表中的規(guī)則轉發(fā)數(shù)據(jù)包即可。為驗證本文的SDN的負載均衡算法啊，章節(jié)采用Fat-Tree拓撲，如圖1.2所示。圖1.2Fat-tree拓撲結構用圖來表示Fat-Tree網(wǎng)絡，其中V表示所有節(jié)點的集合，E表示所有鏈路的集合。表示任意兩個源、目的主機節(jié)點。整個網(wǎng)絡拓撲分為三層，從上到下依次為匯聚層、聚合層和邊緣層。匯聚層和邊緣層交換機構成一個Pod，用K表示網(wǎng)絡中Pod的數(shù)量。假設，則與不同Pod相連的主機之間均有4條路徑，并且每個邊緣層交換機連接著兩臺主機，一共有16臺主機，20個交換機，每個交換機均支持OpenFlow協(xié)議。每條鏈路可以傳輸?shù)淖畲笏俾蕿槠滏溌啡萘看笮?。對于給定的網(wǎng)絡拓撲，用R表示源、目的節(jié)點間的所有路徑的集合，表示第k條路徑。表示鏈路上的流量，表示鏈路總容量。定義瓶頸鏈路為每條路徑中具有最大帶寬利用率的鏈路，用表示鏈路帶寬利用率。(1.1)1.2問題描述1.2.1網(wǎng)絡中流的定義在龐大的數(shù)據(jù)中心網(wǎng)絡中，存在著兩種數(shù)據(jù)流量，一種是生存時間短的老鼠流，一種是生存時間長的大象流，當有大量的大象流出現(xiàn)在數(shù)據(jù)中心網(wǎng)絡中時網(wǎng)絡會出現(xiàn)擁塞等現(xiàn)象，因此會對網(wǎng)絡的性能產(chǎn)生影響，并且由于目前大數(shù)據(jù)以及云計算的不斷發(fā)展和普及，使得用戶對網(wǎng)絡的需求逐漸提升，大象流對于網(wǎng)絡的影響直接導致網(wǎng)絡的傳輸速率，因此對于大象流的研究十分必要。在數(shù)據(jù)中心網(wǎng)絡中存在多種流，并且每種流的生存時間均不相同，每條數(shù)據(jù)流所攜帶的信息量也均不相同，若數(shù)據(jù)流所攜帶的信息量越大，則表明數(shù)據(jù)流的生存時間越長，該數(shù)據(jù)流為大象流的可能性越大；經(jīng)Benson等人研究發(fā)現(xiàn)約50%的數(shù)據(jù)流小于10KB，將這種小于10KB的流稱之為老鼠流；而僅存在10%的數(shù)據(jù)流攜帶有大量的數(shù)據(jù)信息[36]，雖然這種數(shù)據(jù)流占比很小卻占網(wǎng)絡總流量的90%，同時生存時間也較長，將這種持續(xù)時間長并且攜帶數(shù)據(jù)量大的數(shù)據(jù)流量稱之為大象流，由于大象流的生存時間較長，在端口處的排列中老鼠流總在大象流的后面，使得網(wǎng)絡出現(xiàn)延時或者鏈路的擁塞等情況，為了使網(wǎng)絡傳輸更為高效并同時減少控制器的負載，需要對流量進行集中化的控制處理，所以在數(shù)據(jù)中心網(wǎng)絡中對于大象流的識別、數(shù)據(jù)流路徑選擇等對于網(wǎng)絡性能來講十分關鍵。數(shù)據(jù)中心網(wǎng)絡存在大量交換機的同時也存在多條等價鏈路，常用的等價鏈路路由算法為ECMP算法，該算法可以充分利用網(wǎng)絡中的帶寬，并可以均衡分配網(wǎng)絡中的流量，但是在數(shù)據(jù)中心網(wǎng)絡中大象流的占比為10%，其余的為數(shù)據(jù)流較小的老鼠流，ECMP算法主要采用哈希算法對傳輸?shù)臄?shù)據(jù)流進行分配，因此當同一個路徑上同時分配了兩種類型的數(shù)據(jù)流，就可能會導致鏈路的擁塞[37]，因此在進行流量傳輸前就必須要清楚分辨流量類型，然后根據(jù)不同數(shù)據(jù)流類型選擇不同的路由方式；ECMP算法對于老鼠流來說能夠很好地進行等價路徑的路由，但對于大象流不僅不能很好地實現(xiàn)等價多路徑，還會帶來額外的網(wǎng)絡資源浪費；在大象流與老鼠流之間除了攜帶信息量不同以外，這些流量對于帶寬的需求量也不相同，大象流具有較高的帶寬需求，老鼠流因為攜帶的信息量少因此對時延很敏感。當在老鼠流和大象流同時存在的情況下會首先傳輸老鼠流，而大象流因為攜帶的信息量大可能會占滿交換機上的緩存區(qū)，老鼠流傳輸延遲較長，因此必須對老鼠流與大象流分開轉發(fā)并制定不同的轉發(fā)路徑1.2.2大象流調度策略目前對于大象流的調度思路主要存在兩種：a)利用SDN全局網(wǎng)絡視圖和動態(tài)規(guī)則配置能力，對大象流進行動態(tài)調度，選擇無沖突路徑，避免大流沖突；b)將大象流分解成多個子流，多路徑傳輸。表1.1大象流調度策略對比方案檢測大象流位置多路徑轉發(fā)方案Hedera控制器對大象流重路由，采用全局優(yōu)先匹配算法計算路徑Mahout終端大象流重路由，采用increasingfirstfit算法TinyFlow控制器大象流分解成子流，再采用ECMP算法路由SMFS終端對部分大象流利用SR進行重路由，并采用全局優(yōu)先匹配算法計算路徑EFLB終端設置網(wǎng)絡負載閾值，將大象流分解成子流，選擇負載最小的下一跳Hedera[38]首次將SDN技術應用到數(shù)據(jù)中心網(wǎng)絡中的流量管理中，他認為大流是導致網(wǎng)絡擁塞的主要原因，提出動態(tài)地調度大流，以提高網(wǎng)絡吞吐量。Hedera界定大流的標準是一條流的傳輸帶寬大于鏈路帶寬的10%，則認為是大流。通常情況下，Hedera采用ECMP路由算法，同時周期性地檢測網(wǎng)絡中的大流和鏈路的負載情況，確定需要重新調度的大流，并估計大流的帶寬需求，計算出合適的傳輸路徑，完成對大象流動態(tài)調度。但由于Hedera中大象流和網(wǎng)絡狀態(tài)的檢測是周期性的，會導致控制粒度過粗，不夠精細，不能保障網(wǎng)絡中的突發(fā)狀況。同時，在大象流的路徑選擇上，Hedera采用的是全局優(yōu)先匹配(GFF)算法，該算法在所有可用路徑中選擇第一個符合帶寬需求的路徑，具有一定的局限性，精確度較低，無法保證轉發(fā)路徑為最優(yōu)路徑Mahout[36]同樣結合了SDN的集中控制方式，對大流進行精細路由。Mahout是在終端主機上對大象流進行檢測并標記，被標記的大流由increasingfirstfit算法計算轉發(fā)路徑，在多條可用路徑中選擇負載最少的路徑進行傳輸，沒有被標記的流則采用靜態(tài)的ECMP算法進行路由。相比于Hedera，Mahout可以更快地檢測到大象流，且減少了控制器的開銷。Mahout在路徑選擇上更加精細，相對來說算法復雜性也有所提高，并且還需要在終端主機上設置檢測大象流的算法，故Mahout算法的實現(xiàn)比較復雜。TinyFlow[39]很好地解決了ECMP中不區(qū)分大小流的問題。TinyFlow將大象流分解成老鼠流，并將其隨機均勻地分布在所有路徑上，即在僅有老鼠流的網(wǎng)絡中采用ECMP算法進行數(shù)據(jù)流傳輸，避免了大流路由碰撞的缺陷。文獻[40]提出基于SDN的大象流負載均衡機制EFLB，該機制也是一種有選擇地對大象流進行調度的方法。EFLB以輪詢方式監(jiān)聽網(wǎng)絡，當網(wǎng)絡負載超過閾值時，控制器將檢測到的大象流分解成多個老鼠流，并利用SDN控制器的全局網(wǎng)絡視圖，計算出負載最小的下一跳交換機。實驗結果表明，EFLB機制相比ECMP，提高了網(wǎng)絡吞吐量和鏈路利用率，更好地實現(xiàn)了網(wǎng)絡負載均衡。根據(jù)大象流的特性，無論是為大象流選擇可用帶寬大的無沖突路徑，還是將大象流分解成多個子流再傳輸，或設置網(wǎng)絡負載閾值，有選擇地對大流調度，這些方法均提高了網(wǎng)絡吞吐量，使網(wǎng)絡性能得到改善。然而對于大象流的調度還存在以下難點：在網(wǎng)絡比較繁忙時，可能會選擇不到適合大象流傳輸?shù)淖顑?yōu)路徑。將大象流分解成多個子流，并在不同的路徑上進行傳輸，但不同路徑的性能存在差異，比如丟包率和延遲的不同，這些會造成數(shù)據(jù)包的亂序，數(shù)據(jù)包的重新排序會增加接收端的占用內存和CPU利用率，既增加了傳輸開銷，也造成了額外的延遲;其次，大象流分解的數(shù)目也是一個難點，理想情況下子流的數(shù)目越多，越可以避免網(wǎng)絡擁塞的發(fā)生，但是子流的數(shù)目過多會造成維護費用和資源消耗的驟增，子流的數(shù)目太少，會達不到大象流分解的效果，不能避免大流的碰撞問題。1.2.3路由約束與路由模型通過SDN控制器獲取網(wǎng)絡節(jié)點和鏈路狀態(tài)信息，結合節(jié)點流表資源以及鏈路帶寬資源使用情況，本小節(jié)對網(wǎng)絡流路由約束進行闡述。SDN控制器具有網(wǎng)絡能力感知功能，收集網(wǎng)絡節(jié)點處的流表資源使用、鏈路帶寬資源占用、鏈路時延和丟包率等參數(shù)，定義節(jié)點v處前一時刻流表使用量為，鏈路l前一時刻帶寬使用量為，定義網(wǎng)絡流經(jīng)過節(jié)點v時占用的流表資源為。定義路徑是網(wǎng)絡流自源節(jié)點（即接入節(jié)點）至目的節(jié)點的可達路由路徑，集合R是網(wǎng)絡流自源節(jié)點至目的節(jié)點的可達路徑集合,。定義二進制變量，描述OF節(jié)點是否在路徑上；定義二進制變量，描述鏈路是否在路徑上；定義二進制變量，描述路徑是否被網(wǎng)絡流使用；定義節(jié)點v處的單位流表開銷為，鏈路上的單位帶寬開銷為。另外，考慮到交換機容量限制以及鏈路傳輸能力，分別定義節(jié)點處流表容量上限和鏈路容量上限。建立如下約束：（1）鏈路負載約束網(wǎng)絡流使用路徑p進行轉發(fā)時，經(jīng)過的每條回程鏈路都應符合帶寬資源容量約束，即已使用帶寬與網(wǎng)絡流即將占用帶寬資源之和不超過鏈路l的帶寬容量上限（1.2）（2）流表容量約束當網(wǎng)絡流在回程網(wǎng)絡中使用路徑p進行轉發(fā)，網(wǎng)絡流經(jīng)過節(jié)點時均需要滿足該節(jié)點處流表資源容量的約束，即經(jīng)過節(jié)點的網(wǎng)絡流對流表資源的占用不應超過該節(jié)點流表資源的容量上限，否則會在該節(jié)點處發(fā)生流表溢出現(xiàn)象，因此需要滿足流表容量約束：（1.3）網(wǎng)絡流在路由過程中經(jīng)過鏈路產(chǎn)生的帶寬資源開銷為：（1.4）網(wǎng)絡流經(jīng)過節(jié)點產(chǎn)生的流表資源開銷為：（1.5）綜上，以網(wǎng)絡流路由中的帶寬和流表資源開銷之和為優(yōu)化目標，考慮鏈路負載和流表流量等約束，建立優(yōu)化模型如下：（1.6）1.3大象流負載均衡算法設計為實現(xiàn)大象流的檢測與鏈路負載均衡，本文提出了基于自適應閾值的大象流檢測算法、基于概率選擇的重路由路徑算法以及自適應輪詢周期算法。1.3.1基于自適應閾值的大象流檢測算法通過設定閾值的方法檢測大象流，一般設置閾值為總帶寬的1%左右。但是這種設置方法無法根據(jù)網(wǎng)絡的狀態(tài)實時調整。在網(wǎng)絡狀態(tài)好的時候，100M可能才能作為大象流，但是網(wǎng)絡狀態(tài)不好時，10M的流都可能作為大象流。因此，本章節(jié)根據(jù)網(wǎng)絡的鏈路狀態(tài)，動態(tài)調整閾值，方法如下所示：（1.7）其中，N表示所有鏈路總數(shù)，表示鏈路l的帶寬利用率，表示鏈路l的帶寬，Th表示大流檢測的閾值。根據(jù)鏈路的平均剩余可用帶寬來計算大流檢測的閾值的好處是，平均剩余可用帶寬可以反映網(wǎng)絡負載的高低。平均剩余可用帶寬越多說明網(wǎng)絡負載越輕，閾值應該設置的比較大，因為有足夠的帶寬來傳輸更多的流量；反之負載越重，相應的閾值應該設置的較小，以避免鏈路擁塞[41]。1.3.2基于概率選擇的重路由路徑算法為了平衡網(wǎng)絡負載和減少帶寬碎片[42]，我們提出了一種基于概率的路徑選擇算法來計算大象流的最小擁塞路徑。為了提高網(wǎng)絡的吞吐量，在大象流進行重路由的時候，本章節(jié)采用大象流的傳輸速率而不是帶寬作為評估參數(shù)[43]。圖1.3示意圖如圖1.3所示，假設源節(jié)點與目的節(jié)點之間存在4條路徑（A、B、C、D），大象流的帶寬需求是30M，本應該在A路徑進行傳輸，但是因為A路徑擁塞（或者即將擁塞）導致帶寬容量僅為10M，因此需要對進行重路由。此時B、C、D三條路徑的剩余帶寬為11M，15M，25M，均不滿足大象流的傳輸需求。因此大象流將會繼續(xù)沿著路徑A進行傳輸。但是如果按照大象流的傳輸速率進行重路由，則將會選擇傳輸速率最快的路徑D，傳輸速率達到25M，遠高于現(xiàn)路徑A的10M，因此整體來看，網(wǎng)絡的吞吐量肯定會有所提升。假設大象流重路由后存在K條路徑，本文以大象流的傳輸速率以及每條路徑的剩余帶寬比值作為每條路徑的權重，即：（1.8）式中，l表示第l條路徑，表示大象流的傳輸速率，表示鏈路l的帶寬利用率，表示鏈路l的帶寬。定義每條路徑的選中概率為：（1.9）由此可見，當路徑的剩余帶寬與大象流的涮熟速率接近的時候，每條路徑的權重越大，概率越高。為防止某條路徑為重復選擇，導致鏈路擁塞。采用如下算法：在候選K條路徑中隨機選擇路徑。定義為前l(fā)條路徑的概率總和，表示0到1之間的一個隨機數(shù)，當某條路徑滿足以下關系的時候，則選擇該條路徑：（1.10）本章算法的偽代碼如下表所示：表1.1基于概率的路徑選擇算法基于概率的路徑選擇算法輸入：大象流F輸出：新的路徑Path獲取源節(jié)點與目的節(jié)點的所有路徑pathsForpaths中的所有路徑pathIfpath的剩余帶寬大于大象流F的傳輸速率then將path加入到候選路徑隊列candidate中EndifEndforfor候選路徑隊列candidate中的所有路徑path計算路徑的權重weightEndfor計算所有候選路徑的權重之和sumWeight產(chǎn)生一個0-1之間的隨機數(shù)random，以及sump＝０for候選路徑隊列candidate中的所有路徑path計算每個路徑的概率Psump＝sump+pifsump＞randomthenresult=pathEndifEndforReturnresult1.3.3自適應輪詢周期調整算法為了檢測象流并保持網(wǎng)絡的正確負載信息，控制器需要定期從交換機收集網(wǎng)絡統(tǒng)計信息。然后，控制器可以獲得網(wǎng)絡的全局視圖，并動態(tài)地重新調度象流以避免網(wǎng)絡擁塞。具體來說，輪詢周期不僅決定流檢測的準確性和網(wǎng)絡統(tǒng)計的正確性，而且還決定控制器的消息開銷。然而，在大多數(shù)現(xiàn)有的方法中，控制器查詢具有固定輪詢周期的交換機。如果輪詢周期較長，控制器收集到的網(wǎng)絡統(tǒng)計信息就不能及時更新，從而降低了象流檢測的準確性，并可能導致某些路徑上的持續(xù)擁塞。如果輪詢周期很短，則會增加控制器的消息開銷，因為控制器需要頻繁地查詢交換機[44]。為了在控制器的消息開銷和網(wǎng)絡統(tǒng)計的正確性之間進行權衡，本章節(jié)采用了動態(tài)輪詢周期，并提出了一種自適應輪詢周期調整算法，該算法可以根據(jù)網(wǎng)絡負載動態(tài)調整輪詢周期。當網(wǎng)絡穩(wěn)定且大部分鏈路負載較輕時，控制器不必頻繁地查詢交換機，因為這種情況下發(fā)生網(wǎng)絡擁塞的可能性很低。因此，控制器將設置更大的輪詢周期，以減少查詢交換機的頻率，并相應地節(jié)省消息開銷。當網(wǎng)絡繁忙，某些鏈路發(fā)生擁塞時，控制器會設置較小的輪詢周期，以便及時更新網(wǎng)絡統(tǒng)計信息，快速消除網(wǎng)絡擁塞。定義網(wǎng)絡的平均鏈路利用率如下：（1.11）但是為了防止某些鏈路擁塞而整體平均利用率較低的情況，并且充分測量網(wǎng)絡的負載并檢查某些鏈路是否擁塞，我們定義了如下總負載（1.12）公式（1.12）中，表示網(wǎng)絡中的鏈路最高利利用率，表示鏈路平均利用率，分別表示兩個參數(shù)的權重系數(shù)，且，其值分別為0.7、0.3。根據(jù)網(wǎng)絡負載情況，按照下式計算輪詢周期：（1.13）其中，表示基礎輪詢周期，一般設置為5秒。因為上式是遞減函數(shù)，隨著網(wǎng)絡負載的變大，輪詢周期變短。為了防止無限大與無限小的存在，給周期T設置上下限。本算法的偽代碼如下表所示：表1.2自適應輪詢周期調整算法自適應輪詢周期調整算法輸入：網(wǎng)絡拓撲，輸出：輪詢周期T獲取所有鏈路的鏈路利用率情況If多個（5個）鏈路利用率超過閾值Endif計算網(wǎng)絡負載計算輪詢周期IfthenEndififthenEndifReturnT1.4仿真實驗與結果分析1.4.1仿真實驗環(huán)境設置本實驗在較為穩(wěn)定的Ubuntu16.04系統(tǒng)上搭建，并選擇在輕量級網(wǎng)絡仿真工具Mininet上進行模擬，控制器使用開源的Ryu控制器，對于實驗拓撲采用K=4的胖樹DCN拓撲，鏈路帶寬設置為100Mbit/s，由于Fat-Tree架構可以采用一般商業(yè)的交換機來構建，因此網(wǎng)絡鏈路的帶寬能夠保持一致。仿真使用2種數(shù)據(jù)中心常用的流量模式：1)Random：每臺主機等概率地向其他主機發(fā)送數(shù)據(jù)。2)StaggeredProb(EdgeP，PodP)：主機以概率EdgeP發(fā)送到同一邊緣交換機中的另一個主機，稱為機柜流量。以概率PodP發(fā)送到其相同的pod且不在同一邊緣交換機的主機，即pod內流量。以概率1-EdgeP-PodP發(fā)送到網(wǎng)絡的其余部分，即pod間流量。1.4.2結果分析本文從平均吞吐率、平均流完成時間(FCT)和鏈路利用率這3個角度比較了本章算法、Hedera和ECMP這3種策略，以驗證本章算法的優(yōu)越性。如圖1.1所示，在EdgeP較低時，即網(wǎng)絡內有較多的pod內流和pod間流時，DPMS、Hedera和ECMP這3種策略的吞吐率差距較大。因為在pod內流和pod間流多的情境下，ECMP無法根據(jù)鏈路擁塞狀態(tài)動態(tài)地分配鏈路資源，大象流的碰撞率增大。Hedera區(qū)分大象流和老鼠流，動態(tài)對大象流進行調度，所以效果比ECM