多下一跳路由機制下負載均衡算法研究
2009-01-01 00:00:00王超卜佑軍張興明鈕曉娜
計算機應用研究 2009年4期
(解放軍信息工程大學 信息工程學院 信息技術研究所， 鄭州 450002)
摘 要：多下一跳路由機制中，各個節點都預先建立多下一跳轉發表。在路由收斂期間，數據通過多下一跳轉發表轉發，從而解決斷流問題，提高網絡的自愈能力。提出了一種多下一跳路由機制下的負載均衡轉發算法。該算法包括三個部分，即選擇候選下一跳集、數據流分配映射和基于過載鏈路的反饋式動態調整。采用哈希函數分配數據流保證了每個業務流的報文保序問題。通過對下一跳鏈路的實時信息統計，采用動態調整機制可以達到很好的均衡效果。
關鍵詞：負載均衡；多下一跳；候選下一跳集；流保序
中圖分類號：TP309文獻標志碼：A
文章編號：1001-3695(2009)04-1476-04
Load balancing algorithm under multi next hop routing mechanism
WANG Chao，BU You-jun，ZHANG Xing-ming，NIU Xiao-na
(Institute of Information Technology， School of Information Engineering，PLA Information Engineering University， Zhengzhou 450002， China)Abstract:In the multi-hop routing mechanism， every node maintains a multi-hop forwarding lookup table beforehand. During routing convergence， traffic could be forwarded using this table， so as to solve the problem of traffic stoppage ， and enhance network’s self-cure ability.This paper gave a load balance forwarding algorithm for the multi-hop routing mechanism.It contained three parts: selecting the candidate next hop muster， the mapping of traffic splitting， dynamic adaptation based on over-loading link. Hash-based traffic disperse was adopted to ensure per-flow ordering. Meanwhile，by judging the real-time information of next-hop links，could get good traffic balance result using dynamic adaptation.
Key words:load balancing; multi next hop; candidate next hop muster; per-flow ordering
0 引言
近年來，隨著Internet網絡的迅猛、飛速發展，新型網絡應用和用戶數的層出不窮，網絡中通信量的急劇增長，造成網絡擁塞問題越來越嚴重。網絡擁塞的原因之一是網絡的負載超過了網絡資源容量和處理能力，這需要對網絡進行升級和擴容；另一種更為普遍的原因是網絡的一部分負載嚴重超過了網絡節點或鏈路容量，而其余部分則處于輕載狀態，網絡資源未能得到充分利用，即網絡出現了負載不均衡現象。
傳統網絡體系中，路由器都是根據現行的路由協議計算路由表，路由器以目的IP地址為關鍵字在轉發引擎中查找、轉發報文。路由協議的目標都是找到一條源節點到目的節點的最短路徑來轉發報文。但是隨著網絡通信量的爆炸式增長，這種傳統單下一跳模式的最短路徑路由算法容易導致出現瓶頸鏈路，造成網絡擁塞和負載分配不均衡；另外，這種單下一跳在網絡路由收斂期間不能保證網絡中數據報文的正常傳輸。當在軍事打擊、恐怖襲擊、自然災害等極端環境下，以及在嚴重的惡意攻擊等情況下，或網絡遭受重大破壞時，在網絡路由收斂期間報文傳輸將中斷，造成傳輸斷流現象。國家“863”計劃專題課題——快速自愈路由協議和試驗系統提出了多下一跳路由的概念。目的是解決斷流問題，實現網絡的快速自愈，從而提高網絡資源的利用率。
多下一跳路由機制的協議支撐是筆者所在課題組正在研究的新型路由協議——節點勢能導向的快速自愈路由協議[1]。為了實現網絡的快速自愈，網絡中的每個路由節點都預先建立多下一跳轉發表，在正常情況下運行現有路由協議和轉發機制，當網絡遭受重大破壞（路由收斂期間）時，利用節點勢能導向快速自愈路由協議得到的多下一跳轉發表進行數據報文的轉發，路由收斂后，再運行現有的路由協議。節點可以采取簡單的方法把數據報文向其多個下一跳轉發，如隨機抽取(random)或輪詢方式(round-robin)。這樣轉發可以充分利用網絡資源，提高網絡的吞吐量。但是由于網絡中各鏈路的代價等因素不盡相同，該轉發方式容易造成同一個業務流的報文沿著不同的路徑到達目的節點，在接收端造成報文亂序。TCP協議的數據報文在接收端發生亂序后，將會導致報文重傳，這樣會加劇網絡資源的使用，降低網絡的性能。多下一跳路由機制中，負載均衡轉發和報文保序是一對矛盾。
本文就多下一跳路由機制下報文分發和多下一跳之間負載均衡問題進行研究。在轉發表中，凡是目的IP地址最長前綴匹配相同的，其對應的多下一跳轉發表是相同的。最長前綴匹配不相同時，其對應的多下一跳轉發表可能相同也可能不同。本文主要針對在最長前綴匹配相同時，各業務流之間的轉發和負載均衡問題進行了研究，提出了多下一跳負載均衡算法——MNHLB(multi next hop load balancing algorithm）。
1 相關研究現狀
目前有兩種典型的負載分配調度機制，即基于包水平和流水平的調度機制。基于包水平的調度機制常采用隨機或輪詢方式分配流量，這種方式沒有考慮報文在網絡中傳輸的順序，方法比較簡單，易于實現；基于流水平的調度機制采用哈希函數或者歷史分配信息來分發流量，這種方式維持數據報文進入節點的最初順序，在傳輸過程中能很好地保證業務流中報文的順序。TCP協議的數據流在整個傳輸過程中，如果所有的報文都沿著相同的路徑到達目的節點，TCP的性能將能得到很好的保障。反之，網絡的整體性能將嚴重降低[2，3]。現在網絡上的業務流大部分都是基于TCP協議的，避免報文亂序對TCP報文至關重要，基于哈希函數的流量分配算法可以很好地保證業務流中報文的順序并且在網絡負載均衡領域得到了廣泛的應用。TCP報文在多徑中轉發時，造成報文亂序的原因可能是由于報文在網絡中傳輸時被丟棄了，也有可能是先發送的報文還滯留在網絡中沒有到達接收端，文獻[4]給出了三種提高TCP協議報文傳輸性能的方法：a）發送端解決方案，增加快重傳門限。在等待重傳計時器超時的時間段內，不是收到三個相同的ACK報文就開始重傳相應的報文，而是收到至少大于三個ACK報文后再開始重傳。b）接收端解決方案，修改ACK延時。接收端不是收到報文后就發送確認報文ACK，而是等待一段時間后再發送，這樣做的目的是增加確認時間，以便滯留在網絡中的報文能夠到達接收端，避免報文重傳。c）綜合解決方案，即增加快重傳門限又修改ACK延時。
當前多下一跳的相關研究還很少，大部分都是關于多徑路由及其流量工程的。清華大學的梁志勇等人［5］提出了一種基于TCAM的多下一跳路由查找方案，方案通過兩級索引表實現了多下一跳路由的存儲和快速訪問，但是該方案只是針對目前路由表中存在一定多下一跳路由而提出的。網絡中各鏈路的情況千差萬別，在各鏈路的代價都相同的條件下，文獻[6]提供了三種可行的方法(modulo-N hash，hash-threshold and highest weight(HRW)）來決定業務流的下一跳，并且討論了這些方法在單播、組播轉發的適用性[7]。給出了這些方法的分析，分析包括算法的性能以及下一跳集合改變引起的流量分裂度。這些方法雖然實現起來比較容易，但是它們適用的條件比較特別，只適用于各鏈路等代價的情況，方法不具有普適性。轉發調度策略的好壞直接影響著轉發的性能，文獻[8]評估了五種直接哈希方法和一種基于哈希表項的方法。研究發現利用16 bit CRC對五元組進行哈希運算可以得到很好的負載均衡性能，基于哈希表項的哈希算法也可以實現相同的性能。流媒體業務的不斷興起，在一定程度上也加劇了網絡資源的使用，文獻[9]研究了VOIP報文在多路徑分散傳輸時的服務質量問題，提出了兩種解決方案：a）增大接收端的緩存。這種方法雖然可以在一定程度上解決報文亂序問題，但是需要對各終端進行硬件升級。b)在接收端增加容錯機制。主要是采取一定的檢錯、糾錯機制。這種方案的缺點是檢錯、糾錯機制只能是針對某個類型的業務流，針對性太強，不適合所有的數據類型。
2 理想模型
典型的負載均衡系統由流量分發器和多條輸出鏈路構成，如圖1所示。在該系統中，流量分發器接收從高速輸入鏈路到達的數據流，并且負責將數據流轉發到相應的輸出鏈路上。一個好的負載均衡系統應該可以將數據流量均勻地或者是按照預先定義的比例分發到多個輸出鏈路上。
首先看一個流量無限可分的理想模型。假設該負載均衡系統有N條輸出鏈路，鏈路i的容量為Ci，si(t1，t2)是(t1，t2)時間段內轉發到鏈路i的流量總計。則在時間段(t1，t2)內理想的負載均衡系統中的理想分配因子γi為
γi=si(t1，t2)/k=1，…，Nsk(t1，t2)=ci/
k=1，…，Nck
如果任何時候流量分配都是鏈路容量的比值，鏈路要么忙碌要么空閑，沒有帶寬的浪費，那么這樣的系統將是一個完美的均衡系統。現實中沒有這樣的理想系統。但是這種理想模型可以作為調整和評估的參考標準。
一個負載均衡系統中，其流量調度機制必須考慮以下幾個基本的要求：a）高效率。流量分發器要盡可能快地分發報文。b）流保序。基于TCP協議的報文如果造成亂序，網絡的性能將會嚴重下降。
3 多下一跳負載均衡算法
網絡中大部分的數據流都是基于TCP協議的，在進行負載分發時要避免接收端報文亂序，均衡轉發和報文保序是一對矛盾的兩個對立面。針對多下一跳路由機制下負載轉發問題，本文提出MNHLB算法，算法由三個過程構成，如圖2所示。MNHLB算法包括選擇、映射、調整三個部分。首先，從由節點勢能導向路由協議得到的多個可用的下一跳中選擇滿足使用條件的下一跳，構成候選下一跳集；然后，把業務流利用哈希函數映射成K束，再把K束的業務流映射到候選下一跳集所對應的輸出端口；最后，為了更好地實現負載均衡，實時對輸出端口進行狀態統計，根據各輸出端口的負載情況對業務流和輸出端口的映射表進行適當的調整，從而實現流量的動態調整。
3.1 候選下一跳集
多下一跳路由機制下，網絡中的每個節點都預先建立了一個多下一跳的轉發表，每個節點根據路由協議得到的多下一跳的個數是不盡相同的。與下一跳連接的各鏈路的帶寬、延時、丟包率、抖動、開銷等因素也是存在很大差別的，由路由協議獲得的這些多下一跳并不是所有的都需要用來轉發報文，節點要有選擇地利用這些下一跳，這個過程就是選擇候選下一跳集。
在計算候選下一跳集之前，先對一些符號進行說明：
N表示(next hop numbers)可行下一跳集合中下一跳的個數；N^表示(candidate next hop numbers) 候選下一跳集合中下一跳的個數；M表示候選下一跳集中下一跳個數的最大值；Hj表示可行下一跳集合；Canj表示候選下一跳集合；表示空集；lji表示節點j與其下一跳i之間的鏈路；B(lji)表示鏈路lji的帶寬；U(lji)表示鏈路lji的帶寬利用率；R(lji)表示鏈路lji的剩余帶寬，R(lji)=(1-U(lji))×B(lji)；α表示進入候選下一跳集的鏈路剩余帶寬閾值；β 表示動態調整時的調整門限。
由多下一跳路由機制得到的多下一跳稱為可行下一跳集合。如果把可行下一跳集合看做一個全集，則候選下一跳集合只是全集的一個子集，剩余的下一跳構成的集合稱其為候選下一跳集的補集。圖3描述了計算候選下一跳集合算法的流程。為了不使節點用于轉發數據流的下一跳個數過大，造成網絡節點計算復雜度高，對候選下一跳集中個數的最大值進行了限制。當可行下一跳集中個數N小于門限值M時，所有的與下一跳相連的鏈路lji，當其剩余帶寬R(lji)都大于鏈路的剩余帶寬閾值α時，這時的候選下一跳集就是當前的可行下一跳集，若其中只有部分鏈路的剩余帶寬大于α，則候選下一跳集由這些剩余帶寬大于α的鏈路對應的下一跳構成。當可行下一跳集中個數N大于門限值M時，若此時所有可行下一跳集中下一跳對應的鏈路lji，其R(lji)小于α，說明此時網絡的負載量很大，鏈路已經飽和或接近于飽和，不能再承擔其他的負載，候選下一跳集為空集。若有部分鏈路的R(lji)大于α，則按照鏈路剩余帶寬多少的順序，把對應的下一跳依次加入候選下一跳集，但是候選下一跳集的N^不能大于門限值M。
3.2 數據流分配映射
為了保證報文保序，候選下一跳集確定后，采用基于哈希函數的算法對數據流進行流量分配。當收到報文時，對報文中五元組（源地址、目的地址、源端口、目的端口、協議號）的部分或者是全部進行哈希運算得到相應的哈希值，以哈希值作為報文的流標志。這樣，凡是屬于同一個流標志的報文將采用相同的均衡調度策略，從同一個端口轉發出去。相同流標志的報文在每個節點都將沿著相同的端口轉發，也就意味著相同流標志的報文將沿著同一個路徑到達接收端，保序問題就可得到很好的解決。
MNHLB算法在對數據流進行分配時，首先，利用直接哈希算法對五元組進行哈希運算，得到流標志；其次，根據流標志的不同將到達節點的業務流映射為K束，再把這K束業務流映射到N^個下一跳所對應的輸出端口，如圖4所示。通過改變束與輸出端口的映射關系，就可以實現按預定義的比例分發數據。一般地，K都比N^大好幾個數量級，所以可以很好地實現負載的均衡分配。有兩種映射的方法，具體如圖5所示。一種是設定N^-1個門限值，每個輸出端口對應一個門限。當收到一個報文，先用哈希函數計算哈希值，再用哈希值和這N^-1個門限進行比較，以此決定輸出端口；另一種方法是在K條哈希表項中標明輸出端口的索引值。當接收到一個報文，計算出其哈希值，確定出哈希值所在的表項就可以確定出其輸出端口。本文采用第二種映射方法，采用該方法，修改某一流標志對應的輸出端口時比較容易，只需修改索引值即可，能夠實現任意比例的負載分配比。
3.3 基于過載鏈路的反饋式動態調整
網絡業務流的發起往往具有一定的突發性，節點收到的數據流量并不是一成不變的，為了更好地實現負載均衡，需要對負載分配進行實時的調整。調整的方法是減少帶寬利用率最大的鏈路在hash映射表中的條目數，增加帶寬利用率最小的鏈路在hash映射表中的條目數。
本文提出的過載鏈路反饋式動態調整策略，對候選下一跳集中所對應鏈路上的帶寬利用率進行實時統計，并設定調整閾值βi（i≤N^）。當候選下一跳集中所對應的所有鏈路的帶寬利用率都小于其各自的βi時，說明此時的可用資源充足，無須調整，按照hash表的映射關系直接進行數據的傳輸。當候選下一跳集對應的所有鏈路的帶寬利用率都大于其各自的βi時，說明網絡已處于嚴重擁塞狀態，任何的調整都不能解決問題，此時只能丟棄報文。以上是兩種極端情況。考慮一般情況，U(lji)表示鏈路的剩余帶寬，可以令
Um=maxi=1，…，N^(U(lji))
Un=mini=1，…，N^(U(lji))
當Um＞β，減少該鏈路對應的hash映射表中的條目數，將這部分條目數增加到Un所在鏈路的hash映射表中。更新hash映射表后，按照新的映射關系傳輸數據。顯然，一旦調整hash映射表，有可能會造成某些業務流的剩余數據包從另外的輸出端口轉發，從而造成報文亂序。所以要控制調整的頻率，不能太過于頻繁。
4 性能評估
從以下兩方面對MNHLB算法的性能進行分析：
a)各鏈路利用率偏離其理想分配因子的程度。定義了鏈路利用率的偏離度ΔUij。在[0，t]時間段內，對第i個（i≤N^）下一跳對應的鏈路進行了T次帶寬利用率的統計，則有
ΔUij=k=1，…，T(Uk(lji)-γik)2/T
理想情況下，偏離度ΔUij應為0，但是不可能存在這種理想的狀況，MNHLB算法的目的就是讓偏離度盡可能地靠近理想值。
b)動態調整的頻率。要盡量減少調整的頻率。每一次調整都將引起某些業務流的部分流量被偏移到另外的輸出鏈路，可能造成報文在接收端一定程度的亂序，特別是TCP協議的數據流，會造成網絡性能的下降。調整的頻率與調整門限βi的選取有關，通過βi可以有效地控制調整頻率。由于負載均衡和報文保序是矛盾的兩個對立面，往往需要在這兩者之間進行一定的折中。
基于對以上兩方面的分析，還有幾個因素對MNHLB算法的性能有很大的影響：
（a）候選下一跳集中下一跳個數的門限值M。門限值的大小直接影響著網絡節點的計算復雜度和所需維護的狀態信息。候選下一跳集中的N^越大，意味著輸出端口越多，hash映射表的映射關系將越復雜，節點需要統計的狀態信息也就越多，也增加了MNHLB算法的復雜度。
(b）選擇一個最佳的哈希函數。哈希函數、輸入的關鍵字等都影響著最終的映射結果。數據流的偏移量和MNHLB算法的穩定度均受哈希函數和數據流本身特性的制約。
(c）哈希表項的大小K。哈希表項的大小影響著對數據流的動態調整。K與N^的比值決定著調整的粒度。K值越大，調整后流量越均衡。一般K都比N^大好幾個數量級。
對如圖6所示的網絡拓撲在相對比較簡單的情況下進行了性能仿真，主要觀察節點3的性能。各鏈路的帶寬和鏈路代價如表1所示。
在圖6中，節點8是目的節點，節點1與2是兩個源節點，節點1到目的節點的最短路徑是{1，3，5，7，8}，節點2到目的節點的最短路徑是{2，3，5，7，8}。對節點3來說，它的下一跳就是節點5。當鏈路4或7或節點5出現故障后，由多下一跳路由機制得到的節點3的多下一跳為{4，6}。對節點3在這種情況下作了MNHLB算法的仿真。MNHLB算法相關參數的設定：M＝4，α＝50 Mbps，哈希函數，H(#8226;)＝CRC16（5-tuple），βi=70％（i＝1，2）。圖7是不進行動態調整的情況下得到的鏈路3與5的帶寬利用率，此時的偏離度ΔU(l3)＝0.019 105，ΔU(l5)=0.045 948。圖8是進行動態調整之后鏈路3和5的帶寬利用率，偏離度ΔU(l3)＝0.015 225，ΔU(l5)＝0.041 628。從仿真結果可以得出，動態調整可以在一定程度上改善負載均衡的效果。
5 結束語
多下一跳路由機制下，數據流將被轉發到多個輸出端口，沿著不同的路徑到達目的節點，實現了網絡的快速自愈，并且提高了網絡的整體性能。針對目的IP最長前綴匹配相同時多下一跳也相同的情況，本文提出了MNHLB算法來實現流量的均衡轉發和保序。MNHLB算法包括三部分，即候選下一跳集的計算、數據流的hash映射和鏈路流量的動態調整。數據流與輸出端口的hash映射保證業務流的保序。利用輸出鏈路的實時統計信息，周期性地對輸出鏈路的流量進行動態調整，達到更好的均衡效果。MNHLB算法有效地解決了報文在網絡中傳輸時的保序問題，可以按照預定義的比例完成負載分配，實現了很好的均衡效果。簡單條件下的仿真結果表明，通過動態調整可以改善多下一跳的負載均衡效果。MNHLB算法的性能受好幾個參數的制約，為了滿足一定的性能要求，往往需要在這些參數中進行一定的折中。最佳參數值的確定有待進一步研究。
參考文獻：
［1］
蘭巨龍.快速自愈路由協議與試驗系統[R]．鄭州:解放軍信息工程大學 ，2007:5-22.
[2]JACOBSON V.Berkeley TCP evolution from 4.3-tahoe to 4.3-reno[C]//Proc of the 18th Internet Engineering Task Force.1990:365-374.
[3]BRAKMO L S，O’ MALLEY S W，PERERSON L L.TCP vegas:new techniques for congestion detection and avoidance[C]//Proc of ACM SIGCOMM.1994:24-35.
[4]LEE Y，PARK I，CHOI Y.Improving TCP performance in multipath packet forwarding networks[J].Communication and Networks， 2002，4(2):1-10.
［5］梁志勇，吳建平.支持壓縮和多下一跳查找的路由查找方案[J].軟件學報，2004，15(4):550-560.
[6]THALER D.HOPPS C.2991 RFC[S].2000.
[7]HOPPS C.2992 RFC[S].2000.
[8]CAO Zhi-ruo，WANG Zheng，ZEGURA E.Performance of hashing-based schemes for Internet load balancing[C]//Proc of IEEE INFOCOM.2000:332-341.
[9]ZLATOKRILOV H.Packet dispersion and the quality of voice over IP applications in IP networks[C]//Proc of IEEE INFOCOM.2004.
