(解放軍信息工程大學(xué) 信息工程學(xué)院 信息技術(shù)研究所， 鄭州 450002)

摘 要：多下一跳路由機(jī)制中，各個(gè)節(jié)點(diǎn)都預(yù)先建立多下一跳轉(zhuǎn)發(fā)表。在路由收斂期間，數(shù)據(jù)通過(guò)多下一跳轉(zhuǎn)發(fā)表轉(zhuǎn)發(fā)，從而解決斷流問(wèn)題，提高網(wǎng)絡(luò)的自愈能力。提出了一種多下一跳路由機(jī)制下的負(fù)載均衡轉(zhuǎn)發(fā)算法。該算法包括三個(gè)部分，即選擇候選下一跳集、數(shù)據(jù)流分配映射和基于過(guò)載鏈路的反饋式動(dòng)態(tài)調(diào)整。采用哈希函數(shù)分配數(shù)據(jù)流保證了每個(gè)業(yè)務(wù)流的報(bào)文保序問(wèn)題。通過(guò)對(duì)下一跳鏈路的實(shí)時(shí)信息統(tǒng)計(jì)，采用動(dòng)態(tài)調(diào)整機(jī)制可以達(dá)到很好的均衡效果。

關(guān)鍵詞：負(fù)載均衡；多下一跳；候選下一跳集；流保序

中圖分類(lèi)號(hào)：TP309文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

近年來(lái)，隨著Internet網(wǎng)絡(luò)的迅猛、飛速發(fā)展，新型網(wǎng)絡(luò)應(yīng)用和用戶(hù)數(shù)的層出不窮，網(wǎng)絡(luò)中通信量的急劇增長(zhǎng)，造成網(wǎng)絡(luò)擁塞問(wèn)題越來(lái)越嚴(yán)重。網(wǎng)絡(luò)擁塞的原因之一是網(wǎng)絡(luò)的負(fù)載超過(guò)了網(wǎng)絡(luò)資源容量和處理能力，這需要對(duì)網(wǎng)絡(luò)進(jìn)行升級(jí)和擴(kuò)容；另一種更為普遍的原因是網(wǎng)絡(luò)的一部分負(fù)載嚴(yán)重超過(guò)了網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路容量，而其余部分則處于輕載狀態(tài)，網(wǎng)絡(luò)資源未能得到充分利用，即網(wǎng)絡(luò)出現(xiàn)了負(fù)載不均衡現(xiàn)象。

傳統(tǒng)網(wǎng)絡(luò)體系中，路由器都是根據(jù)現(xiàn)行的路由協(xié)議計(jì)算路由表，路由器以目的IP地址為關(guān)鍵字在轉(zhuǎn)發(fā)引擎中查找、轉(zhuǎn)發(fā)報(bào)文。路由協(xié)議的目標(biāo)都是找到一條源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑來(lái)轉(zhuǎn)發(fā)報(bào)文。但是隨著網(wǎng)絡(luò)通信量的爆炸式增長(zhǎng)，這種傳統(tǒng)單下一跳模式的最短路徑路由算法容易導(dǎo)致出現(xiàn)瓶頸鏈路，造成網(wǎng)絡(luò)擁塞和負(fù)載分配不均衡；另外，這種單下一跳在網(wǎng)絡(luò)路由收斂期間不能保證網(wǎng)絡(luò)中數(shù)據(jù)報(bào)文的正常傳輸。當(dāng)在軍事打擊、恐怖襲擊、自然災(zāi)害等極端環(huán)境下，以及在嚴(yán)重的惡意攻擊等情況下，或網(wǎng)絡(luò)遭受重大破壞時(shí)，在網(wǎng)絡(luò)路由收斂期間報(bào)文傳輸將中斷，造成傳輸斷流現(xiàn)象。國(guó)家“863”計(jì)劃專(zhuān)題課題——快速自愈路由協(xié)議和試驗(yàn)系統(tǒng)提出了多下一跳路由的概念。目的是解決斷流問(wèn)題，實(shí)現(xiàn)網(wǎng)絡(luò)的快速自愈，從而提高網(wǎng)絡(luò)資源的利用率。

多下一跳路由機(jī)制的協(xié)議支撐是筆者所在課題組正在研究的新型路由協(xié)議——節(jié)點(diǎn)勢(shì)能導(dǎo)向的快速自愈路由協(xié)議[1]。為了實(shí)現(xiàn)網(wǎng)絡(luò)的快速自愈，網(wǎng)絡(luò)中的每個(gè)路由節(jié)點(diǎn)都預(yù)先建立多下一跳轉(zhuǎn)發(fā)表，在正常情況下運(yùn)行現(xiàn)有路由協(xié)議和轉(zhuǎn)發(fā)機(jī)制，當(dāng)網(wǎng)絡(luò)遭受重大破壞（路由收斂期間）時(shí)，利用節(jié)點(diǎn)勢(shì)能導(dǎo)向快速自愈路由協(xié)議得到的多下一跳轉(zhuǎn)發(fā)表進(jìn)行數(shù)據(jù)報(bào)文的轉(zhuǎn)發(fā)，路由收斂后，再運(yùn)行現(xiàn)有的路由協(xié)議。節(jié)點(diǎn)可以采取簡(jiǎn)單的方法把數(shù)據(jù)報(bào)文向其多個(gè)下一跳轉(zhuǎn)發(fā)，如隨機(jī)抽取(random)或輪詢(xún)方式(round-robin)。這樣轉(zhuǎn)發(fā)可以充分利用網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)的吞吐量。但是由于網(wǎng)絡(luò)中各鏈路的代價(jià)等因素不盡相同，該轉(zhuǎn)發(fā)方式容易造成同一個(gè)業(yè)務(wù)流的報(bào)文沿著不同的路徑到達(dá)目的節(jié)點(diǎn)，在接收端造成報(bào)文亂序。TCP協(xié)議的數(shù)據(jù)報(bào)文在接收端發(fā)生亂序后，將會(huì)導(dǎo)致報(bào)文重傳，這樣會(huì)加劇網(wǎng)絡(luò)資源的使用，降低網(wǎng)絡(luò)的性能。多下一跳路由機(jī)制中，負(fù)載均衡轉(zhuǎn)發(fā)和報(bào)文保序是一對(duì)矛盾。

本文就多下一跳路由機(jī)制下報(bào)文分發(fā)和多下一跳之間負(fù)載均衡問(wèn)題進(jìn)行研究。在轉(zhuǎn)發(fā)表中，凡是目的IP地址最長(zhǎng)前綴匹配相同的，其對(duì)應(yīng)的多下一跳轉(zhuǎn)發(fā)表是相同的。最長(zhǎng)前綴匹配不相同時(shí)，其對(duì)應(yīng)的多下一跳轉(zhuǎn)發(fā)表可能相同也可能不同。本文主要針對(duì)在最長(zhǎng)前綴匹配相同時(shí)，各業(yè)務(wù)流之間的轉(zhuǎn)發(fā)和負(fù)載均衡問(wèn)題進(jìn)行了研究，提出了多下一跳負(fù)載均衡算法——MNHLB(multi next hop load balancing algorithm）。

1 相關(guān)研究現(xiàn)狀

目前有兩種典型的負(fù)載分配調(diào)度機(jī)制，即基于包水平和流水平的調(diào)度機(jī)制。基于包水平的調(diào)度機(jī)制常采用隨機(jī)或輪詢(xún)方式分配流量，這種方式?jīng)]有考慮報(bào)文在網(wǎng)絡(luò)中傳輸?shù)捻樞?，方法比較簡(jiǎn)單，易于實(shí)現(xiàn)；基于流水平的調(diào)度機(jī)制采用哈希函數(shù)或者歷史分配信息來(lái)分發(fā)流量，這種方式維持?jǐn)?shù)據(jù)報(bào)文進(jìn)入節(jié)點(diǎn)的最初順序，在傳輸過(guò)程中能很好地保證業(yè)務(wù)流中報(bào)文的順序。TCP協(xié)議的數(shù)據(jù)流在整個(gè)傳輸過(guò)程中，如果所有的報(bào)文都沿著相同的路徑到達(dá)目的節(jié)點(diǎn)，TCP的性能將能得到很好的保障。反之，網(wǎng)絡(luò)的整體性能將嚴(yán)重降低[2，3]。現(xiàn)在網(wǎng)絡(luò)上的業(yè)務(wù)流大部分都是基于TCP協(xié)議的，避免報(bào)文亂序?qū)CP報(bào)文至關(guān)重要，基于哈希函數(shù)的流量分配算法可以很好地保證業(yè)務(wù)流中報(bào)文的順序并且在網(wǎng)絡(luò)負(fù)載均衡領(lǐng)域得到了廣泛的應(yīng)用。TCP報(bào)文在多徑中轉(zhuǎn)發(fā)時(shí)，造成報(bào)文亂序的原因可能是由于報(bào)文在網(wǎng)絡(luò)中傳輸時(shí)被丟棄了，也有可能是先發(fā)送的報(bào)文還滯留在網(wǎng)絡(luò)中沒(méi)有到達(dá)接收端，文獻(xiàn)[4]給出了三種提高TCP協(xié)議報(bào)文傳輸性能的方法：a）發(fā)送端解決方案，增加快重傳門(mén)限。在等待重傳計(jì)時(shí)器超時(shí)的時(shí)間段內(nèi)，不是收到三個(gè)相同的ACK報(bào)文就開(kāi)始重傳相應(yīng)的報(bào)文，而是收到至少大于三個(gè)ACK報(bào)文后再開(kāi)始重傳。b）接收端解決方案，修改ACK延時(shí)。接收端不是收到報(bào)文后就發(fā)送確認(rèn)報(bào)文ACK，而是等待一段時(shí)間后再發(fā)送，這樣做的目的是增加確認(rèn)時(shí)間，以便滯留在網(wǎng)絡(luò)中的報(bào)文能夠到達(dá)接收端，避免報(bào)文重傳。c）綜合解決方案，即增加快重傳門(mén)限又修改ACK延時(shí)。

當(dāng)前多下一跳的相關(guān)研究還很少，大部分都是關(guān)于多徑路由及其流量工程的。清華大學(xué)的梁志勇等人［5］提出了一種基于TCAM的多下一跳路由查找方案，方案通過(guò)兩級(jí)索引表實(shí)現(xiàn)了多下一跳路由的存儲(chǔ)和快速訪(fǎng)問(wèn)，但是該方案只是針對(duì)目前路由表中存在一定多下一跳路由而提出的。網(wǎng)絡(luò)中各鏈路的情況千差萬(wàn)別，在各鏈路的代價(jià)都相同的條件下，文獻(xiàn)[6]提供了三種可行的方法(modulo-N hash，hash-threshold and highest weight(HRW)）來(lái)決定業(yè)務(wù)流的下一跳，并且討論了這些方法在單播、組播轉(zhuǎn)發(fā)的適用性[7]。給出了這些方法的分析，分析包括算法的性能以及下一跳集合改變引起的流量分裂度。這些方法雖然實(shí)現(xiàn)起來(lái)比較容易，但是它們適用的條件比較特別，只適用于各鏈路等代價(jià)的情況，方法不具有普適性。轉(zhuǎn)發(fā)調(diào)度策略的好壞直接影響著轉(zhuǎn)發(fā)的性能，文獻(xiàn)[8]評(píng)估了五種直接哈希方法和一種基于哈希表項(xiàng)的方法。研究發(fā)現(xiàn)利用16 bit CRC對(duì)五元組進(jìn)行哈希運(yùn)算可以得到很好的負(fù)載均衡性能，基于哈希表項(xiàng)的哈希算法也可以實(shí)現(xiàn)相同的性能。流媒體業(yè)務(wù)的不斷興起，在一定程度上也加劇了網(wǎng)絡(luò)資源的使用，文獻(xiàn)[9]研究了VOIP報(bào)文在多路徑分散傳輸時(shí)的服務(wù)質(zhì)量問(wèn)題，提出了兩種解決方案：a）增大接收端的緩存。這種方法雖然可以在一定程度上解決報(bào)文亂序問(wèn)題，但是需要對(duì)各終端進(jìn)行硬件升級(jí)。b)在接收端增加容錯(cuò)機(jī)制。主要是采取一定的檢錯(cuò)、糾錯(cuò)機(jī)制。這種方案的缺點(diǎn)是檢錯(cuò)、糾錯(cuò)機(jī)制只能是針對(duì)某個(gè)類(lèi)型的業(yè)務(wù)流，針對(duì)性太強(qiáng)，不適合所有的數(shù)據(jù)類(lèi)型。

2 理想模型

典型的負(fù)載均衡系統(tǒng)由流量分發(fā)器和多條輸出鏈路構(gòu)成，如圖1所示。在該系統(tǒng)中，流量分發(fā)器接收從高速輸入鏈路到達(dá)的數(shù)據(jù)流，并且負(fù)責(zé)將數(shù)據(jù)流轉(zhuǎn)發(fā)到相應(yīng)的輸出鏈路上。一個(gè)好的負(fù)載均衡系統(tǒng)應(yīng)該可以將數(shù)據(jù)流量均勻地或者是按照預(yù)先定義的比例分發(fā)到多個(gè)輸出鏈路上。

首先看一個(gè)流量無(wú)限可分的理想模型。假設(shè)該負(fù)載均衡系統(tǒng)有N條輸出鏈路，鏈路i的容量為Ci，si(t1，t2)是(t1，t2)時(shí)間段內(nèi)轉(zhuǎn)發(fā)到鏈路i的流量總計(jì)。則在時(shí)間段(t1，t2)內(nèi)理想的負(fù)載均衡系統(tǒng)中的理想分配因子γi為

γi=si(t1，t2)/k=1，…，Nsk(t1，t2)=ci/

k=1，…，Nck

如果任何時(shí)候流量分配都是鏈路容量的比值，鏈路要么忙碌要么空閑，沒(méi)有帶寬的浪費(fèi)，那么這樣的系統(tǒng)將是一個(gè)完美的均衡系統(tǒng)?，F(xiàn)實(shí)中沒(méi)有這樣的理想系統(tǒng)。但是這種理想模型可以作為調(diào)整和評(píng)估的參考標(biāo)準(zhǔn)。

一個(gè)負(fù)載均衡系統(tǒng)中，其流量調(diào)度機(jī)制必須考慮以下幾個(gè)基本的要求：a）高效率。流量分發(fā)器要盡可能快地分發(fā)報(bào)文。b）流保序。基于TCP協(xié)議的報(bào)文如果造成亂序，網(wǎng)絡(luò)的性能將會(huì)嚴(yán)重下降。

3 多下一跳負(fù)載均衡算法

網(wǎng)絡(luò)中大部分的數(shù)據(jù)流都是基于TCP協(xié)議的，在進(jìn)行負(fù)載分發(fā)時(shí)要避免接收端報(bào)文亂序，均衡轉(zhuǎn)發(fā)和報(bào)文保序是一對(duì)矛盾的兩個(gè)對(duì)立面。針對(duì)多下一跳路由機(jī)制下負(fù)載轉(zhuǎn)發(fā)問(wèn)題，本文提出MNHLB算法，算法由三個(gè)過(guò)程構(gòu)成，如圖2所示。MNHLB算法包括選擇、映射、調(diào)整三個(gè)部分。首先，從由節(jié)點(diǎn)勢(shì)能導(dǎo)向路由協(xié)議得到的多個(gè)可用的下一跳中選擇滿(mǎn)足使用條件的下一跳，構(gòu)成候選下一跳集；然后，把業(yè)務(wù)流利用哈希函數(shù)映射成K束，再把K束的業(yè)務(wù)流映射到候選下一跳集所對(duì)應(yīng)的輸出端口；最后，為了更好地實(shí)現(xiàn)負(fù)載均衡，實(shí)時(shí)對(duì)輸出端口進(jìn)行狀態(tài)統(tǒng)計(jì)，根據(jù)各輸出端口的負(fù)載情況對(duì)業(yè)務(wù)流和輸出端口的映射表進(jìn)行適當(dāng)?shù)恼{(diào)整，從而實(shí)現(xiàn)流量的動(dòng)態(tài)調(diào)整。

3.1 候選下一跳集

多下一跳路由機(jī)制下，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都預(yù)先建立了一個(gè)多下一跳的轉(zhuǎn)發(fā)表，每個(gè)節(jié)點(diǎn)根據(jù)路由協(xié)議得到的多下一跳的個(gè)數(shù)是不盡相同的。與下一跳連接的各鏈路的帶寬、延時(shí)、丟包率、抖動(dòng)、開(kāi)銷(xiāo)等因素也是存在很大差別的，由路由協(xié)議獲得的這些多下一跳并不是所有的都需要用來(lái)轉(zhuǎn)發(fā)報(bào)文，節(jié)點(diǎn)要有選擇地利用這些下一跳，這個(gè)過(guò)程就是選擇候選下一跳集。

在計(jì)算候選下一跳集之前，先對(duì)一些符號(hào)進(jìn)行說(shuō)明：

N表示(next hop numbers)可行下一跳集合中下一跳的個(gè)數(shù)；N^表示(candidate next hop numbers) 候選下一跳集合中下一跳的個(gè)數(shù)；M表示候選下一跳集中下一跳個(gè)數(shù)的最大值；Hj表示可行下一跳集合；Canj表示候選下一跳集合；表示空集；lji表示節(jié)點(diǎn)j與其下一跳i之間的鏈路；B(lji)表示鏈路lji的帶寬；U(lji)表示鏈路lji的帶寬利用率；R(lji)表示鏈路lji的剩余帶寬，R(lji)=(1-U(lji))×B(lji)；α表示進(jìn)入候選下一跳集的鏈路剩余帶寬閾值；β 表示動(dòng)態(tài)調(diào)整時(shí)的調(diào)整門(mén)限。

由多下一跳路由機(jī)制得到的多下一跳稱(chēng)為可行下一跳集合。如果把可行下一跳集合看做一個(gè)全集，則候選下一跳集合只是全集的一個(gè)子集，剩余的下一跳構(gòu)成的集合稱(chēng)其為候選下一跳集的補(bǔ)集。圖3描述了計(jì)算候選下一跳集合算法的流程。為了不使節(jié)點(diǎn)用于轉(zhuǎn)發(fā)數(shù)據(jù)流的下一跳個(gè)數(shù)過(guò)大，造成網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算復(fù)雜度高，對(duì)候選下一跳集中個(gè)數(shù)的最大值進(jìn)行了限制。當(dāng)可行下一跳集中個(gè)數(shù)N小于門(mén)限值M時(shí)，所有的與下一跳相連的鏈路lji，當(dāng)其剩余帶寬R(lji)都大于鏈路的剩余帶寬閾值α?xí)r，這時(shí)的候選下一跳集就是當(dāng)前的可行下一跳集，若其中只有部分鏈路的剩余帶寬大于α，則候選下一跳集由這些剩余帶寬大于α的鏈路對(duì)應(yīng)的下一跳構(gòu)成。當(dāng)可行下一跳集中個(gè)數(shù)N大于門(mén)限值M時(shí)，若此時(shí)所有可行下一跳集中下一跳對(duì)應(yīng)的鏈路lji，其R(lji)小于α，說(shuō)明此時(shí)網(wǎng)絡(luò)的負(fù)載量很大，鏈路已經(jīng)飽和或接近于飽和，不能再承擔(dān)其他的負(fù)載，候選下一跳集為空集。若有部分鏈路的R(lji)大于α，則按照鏈路剩余帶寬多少的順序，把對(duì)應(yīng)的下一跳依次加入候選下一跳集，但是候選下一跳集的N^不能大于門(mén)限值M。

3.2 數(shù)據(jù)流分配映射

為了保證報(bào)文保序，候選下一跳集確定后，采用基于哈希函數(shù)的算法對(duì)數(shù)據(jù)流進(jìn)行流量分配。當(dāng)收到報(bào)文時(shí)，對(duì)報(bào)文中五元組（源地址、目的地址、源端口、目的端口、協(xié)議號(hào)）的部分或者是全部進(jìn)行哈希運(yùn)算得到相應(yīng)的哈希值，以哈希值作為報(bào)文的流標(biāo)志。這樣，凡是屬于同一個(gè)流標(biāo)志的報(bào)文將采用相同的均衡調(diào)度策略，從同一個(gè)端口轉(zhuǎn)發(fā)出去。相同流標(biāo)志的報(bào)文在每個(gè)節(jié)點(diǎn)都將沿著相同的端口轉(zhuǎn)發(fā)，也就意味著相同流標(biāo)志的報(bào)文將沿著同一個(gè)路徑到達(dá)接收端，保序問(wèn)題就可得到很好的解決。

MNHLB算法在對(duì)數(shù)據(jù)流進(jìn)行分配時(shí)，首先，利用直接哈希算法對(duì)五元組進(jìn)行哈希運(yùn)算，得到流標(biāo)志；其次，根據(jù)流標(biāo)志的不同將到達(dá)節(jié)點(diǎn)的業(yè)務(wù)流映射為K束，再把這K束業(yè)務(wù)流映射到N^個(gè)下一跳所對(duì)應(yīng)的輸出端口，如圖4所示。通過(guò)改變束與輸出端口的映射關(guān)系，就可以實(shí)現(xiàn)按預(yù)定義的比例分發(fā)數(shù)據(jù)。一般地，K都比N^大好幾個(gè)數(shù)量級(jí)，所以可以很好地實(shí)現(xiàn)負(fù)載的均衡分配。有兩種映射的方法，具體如圖5所示。一種是設(shè)定N^-1個(gè)門(mén)限值，每個(gè)輸出端口對(duì)應(yīng)一個(gè)門(mén)限。當(dāng)收到一個(gè)報(bào)文，先用哈希函數(shù)計(jì)算哈希值，再用哈希值和這N^-1個(gè)門(mén)限進(jìn)行比較，以此決定輸出端口；另一種方法是在K條哈希表項(xiàng)中標(biāo)明輸出端口的索引值。當(dāng)接收到一個(gè)報(bào)文，計(jì)算出其哈希值，確定出哈希值所在的表項(xiàng)就可以確定出其輸出端口。本文采用第二種映射方法，采用該方法，修改某一流標(biāo)志對(duì)應(yīng)的輸出端口時(shí)比較容易，只需修改索引值即可，能夠?qū)崿F(xiàn)任意比例的負(fù)載分配比。

3.3 基于過(guò)載鏈路的反饋式動(dòng)態(tài)調(diào)整

網(wǎng)絡(luò)業(yè)務(wù)流的發(fā)起往往具有一定的突發(fā)性，節(jié)點(diǎn)收到的數(shù)據(jù)流量并不是一成不變的，為了更好地實(shí)現(xiàn)負(fù)載均衡，需要對(duì)負(fù)載分配進(jìn)行實(shí)時(shí)的調(diào)整。調(diào)整的方法是減少帶寬利用率最大的鏈路在hash映射表中的條目數(shù)，增加帶寬利用率最小的鏈路在hash映射表中的條目數(shù)。

本文提出的過(guò)載鏈路反饋式動(dòng)態(tài)調(diào)整策略，對(duì)候選下一跳集中所對(duì)應(yīng)鏈路上的帶寬利用率進(jìn)行實(shí)時(shí)統(tǒng)計(jì)，并設(shè)定調(diào)整閾值βi（i≤N^）。當(dāng)候選下一跳集中所對(duì)應(yīng)的所有鏈路的帶寬利用率都小于其各自的βi時(shí)，說(shuō)明此時(shí)的可用資源充足，無(wú)須調(diào)整，按照hash表的映射關(guān)系直接進(jìn)行數(shù)據(jù)的傳輸。當(dāng)候選下一跳集對(duì)應(yīng)的所有鏈路的帶寬利用率都大于其各自的βi時(shí)，說(shuō)明網(wǎng)絡(luò)已處于嚴(yán)重?fù)砣麪顟B(tài)，任何的調(diào)整都不能解決問(wèn)題，此時(shí)只能丟棄報(bào)文。以上是兩種極端情況?？紤]一般情況，U(lji)表示鏈路的剩余帶寬，可以令

Um=maxi=1，…，N^(U(lji))

Un=mini=1，…，N^(U(lji))

當(dāng)Um＞β，減少該鏈路對(duì)應(yīng)的hash映射表中的條目數(shù)，將這部分條目數(shù)增加到Un所在鏈路的hash映射表中。更新hash映射表后，按照新的映射關(guān)系傳輸數(shù)據(jù)。顯然，一旦調(diào)整hash映射表，有可能會(huì)造成某些業(yè)務(wù)流的剩余數(shù)據(jù)包從另外的輸出端口轉(zhuǎn)發(fā)，從而造成報(bào)文亂序。所以要控制調(diào)整的頻率，不能太過(guò)于頻繁。

4 性能評(píng)估

從以下兩方面對(duì)MNHLB算法的性能進(jìn)行分析：

a)各鏈路利用率偏離其理想分配因子的程度。定義了鏈路利用率的偏離度ΔUij。在[0，t]時(shí)間段內(nèi)，對(duì)第i個(gè)（i≤N^）下一跳對(duì)應(yīng)的鏈路進(jìn)行了T次帶寬利用率的統(tǒng)計(jì)，則有

ΔUij=k=1，…，T(Uk(lji)-γik)2/T

理想情況下，偏離度ΔUij應(yīng)為0，但是不可能存在這種理想的狀況，MNHLB算法的目的就是讓偏離度盡可能地靠近理想值。

b)動(dòng)態(tài)調(diào)整的頻率。要盡量減少調(diào)整的頻率。每一次調(diào)整都將引起某些業(yè)務(wù)流的部分流量被偏移到另外的輸出鏈路，可能造成報(bào)文在接收端一定程度的亂序，特別是TCP協(xié)議的數(shù)據(jù)流，會(huì)造成網(wǎng)絡(luò)性能的下降。調(diào)整的頻率與調(diào)整門(mén)限βi的選取有關(guān)，通過(guò)βi可以有效地控制調(diào)整頻率。由于負(fù)載均衡和報(bào)文保序是矛盾的兩個(gè)對(duì)立面，往往需要在這兩者之間進(jìn)行一定的折中。

基于對(duì)以上兩方面的分析，還有幾個(gè)因素對(duì)MNHLB算法的性能有很大的影響：

（a）候選下一跳集中下一跳個(gè)數(shù)的門(mén)限值M。門(mén)限值的大小直接影響著網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算復(fù)雜度和所需維護(hù)的狀態(tài)信息。候選下一跳集中的N^越大，意味著輸出端口越多，hash映射表的映射關(guān)系將越復(fù)雜，節(jié)點(diǎn)需要統(tǒng)計(jì)的狀態(tài)信息也就越多，也增加了MNHLB算法的復(fù)雜度。

(b）選擇一個(gè)最佳的哈希函數(shù)。哈希函數(shù)、輸入的關(guān)鍵字等都影響著最終的映射結(jié)果。數(shù)據(jù)流的偏移量和MNHLB算法的穩(wěn)定度均受哈希函數(shù)和數(shù)據(jù)流本身特性的制約。

(c）哈希表項(xiàng)的大小K。哈希表項(xiàng)的大小影響著對(duì)數(shù)據(jù)流的動(dòng)態(tài)調(diào)整。K與N^的比值決定著調(diào)整的粒度。K值越大，調(diào)整后流量越均衡。一般K都比N^大好幾個(gè)數(shù)量級(jí)。

對(duì)如圖6所示的網(wǎng)絡(luò)拓?fù)湓谙鄬?duì)比較簡(jiǎn)單的情況下進(jìn)行了性能仿真，主要觀(guān)察節(jié)點(diǎn)3的性能。各鏈路的帶寬和鏈路代價(jià)如表1所示。

在圖6中，節(jié)點(diǎn)8是目的節(jié)點(diǎn)，節(jié)點(diǎn)1與2是兩個(gè)源節(jié)點(diǎn)，節(jié)點(diǎn)1到目的節(jié)點(diǎn)的最短路徑是{1，3，5，7，8}，節(jié)點(diǎn)2到目的節(jié)點(diǎn)的最短路徑是{2，3，5，7，8}。對(duì)節(jié)點(diǎn)3來(lái)說(shuō)，它的下一跳就是節(jié)點(diǎn)5。當(dāng)鏈路4或7或節(jié)點(diǎn)5出現(xiàn)故障后，由多下一跳路由機(jī)制得到的節(jié)點(diǎn)3的多下一跳為{4，6}。對(duì)節(jié)點(diǎn)3在這種情況下作了MNHLB算法的仿真。MNHLB算法相關(guān)參數(shù)的設(shè)定：M＝4，α＝50 Mbps，哈希函數(shù)，H(#8226;)＝CRC16（5-tuple），βi=70％（i＝1，2）。圖7是不進(jìn)行動(dòng)態(tài)調(diào)整的情況下得到的鏈路3與5的帶寬利用率，此時(shí)的偏離度ΔU(l3)＝0.019 105，ΔU(l5)=0.045 948。圖8是進(jìn)行動(dòng)態(tài)調(diào)整之后鏈路3和5的帶寬利用率，偏離度ΔU(l3)＝0.015 225，ΔU(l5)＝0.041 628。從仿真結(jié)果可以得出，動(dòng)態(tài)調(diào)整可以在一定程度上改善負(fù)載均衡的效果。

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

多下一跳路由機(jī)制下，數(shù)據(jù)流將被轉(zhuǎn)發(fā)到多個(gè)輸出端口，沿著不同的路徑到達(dá)目的節(jié)點(diǎn)，實(shí)現(xiàn)了網(wǎng)絡(luò)的快速自愈，并且提高了網(wǎng)絡(luò)的整體性能。針對(duì)目的IP最長(zhǎng)前綴匹配相同時(shí)多下一跳也相同的情況，本文提出了MNHLB算法來(lái)實(shí)現(xiàn)流量的均衡轉(zhuǎn)發(fā)和保序。MNHLB算法包括三部分，即候選下一跳集的計(jì)算、數(shù)據(jù)流的hash映射和鏈路流量的動(dòng)態(tài)調(diào)整。數(shù)據(jù)流與輸出端口的hash映射保證業(yè)務(wù)流的保序。利用輸出鏈路的實(shí)時(shí)統(tǒng)計(jì)信息，周期性地對(duì)輸出鏈路的流量進(jìn)行動(dòng)態(tài)調(diào)整，達(dá)到更好的均衡效果。MNHLB算法有效地解決了報(bào)文在網(wǎng)絡(luò)中傳輸時(shí)的保序問(wèn)題，可以按照預(yù)定義的比例完成負(fù)載分配，實(shí)現(xiàn)了很好的均衡效果。簡(jiǎn)單條件下的仿真結(jié)果表明，通過(guò)動(dòng)態(tài)調(diào)整可以改善多下一跳的負(fù)載均衡效果。MNHLB算法的性能受好幾個(gè)參數(shù)的制約，為了滿(mǎn)足一定的性能要求，往往需要在這些參數(shù)中進(jìn)行一定的折中。最佳參數(shù)值的確定有待進(jìn)一步研究。

參考文獻(xiàn)：

［1］

蘭巨龍.快速自愈路由協(xié)議與試驗(yàn)系統(tǒng)[R]．鄭州:解放軍信息工程大學(xué) ，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].軟件學(xué)報(bào)，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.