摘 要： MATE算法通過檢測多條路徑的狀態(tài)并計(jì)算其成本實(shí)現(xiàn)多條等價路徑上的自適應(yīng)流量調(diào)整，從而實(shí)現(xiàn)流量均衡" title="流量均衡">流量均衡，能有效地解決交換式網(wǎng)絡(luò)" title="交換式網(wǎng)絡(luò)">交換式網(wǎng)絡(luò)中多TRUNK路徑間的流量均衡。
　　關(guān)鍵詞： 交換式網(wǎng)絡(luò)； TRUNK； MATE; 流量均衡

?

　　互聯(lián)網(wǎng)服務(wù)提供商正面臨著設(shè)計(jì)網(wǎng)絡(luò)為客戶提供快速、可靠和區(qū)分服務(wù)的挑戰(zhàn)。在計(jì)算網(wǎng)絡(luò)成本的模式下，互聯(lián)網(wǎng)流量工程成為實(shí)現(xiàn)這個目標(biāo)的一種關(guān)鍵技術(shù)^[1]。根據(jù)IETF，互聯(lián)網(wǎng)流量工程被定義為:在運(yùn)行的IP網(wǎng)絡(luò)上進(jìn)行性能評估和性能優(yōu)化的網(wǎng)絡(luò)工程^[2]。更精確地講，流量工程經(jīng)常有效地將流量需求映射到網(wǎng)絡(luò)拓?fù)?，并自動調(diào)節(jié)這種映射關(guān)系以適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化。值得一提的是，流量工程是通過滿足一些限定條件來實(shí)現(xiàn)整個運(yùn)行網(wǎng)絡(luò)的最高效率，而QoS路由的主要目標(biāo)是滿足某些給定的源-目的數(shù)據(jù)流的QoS限制，從這個角度講，流量工程的意義更為廣泛。
　　交換式網(wǎng)絡(luò)的發(fā)展，尤其是交換式以太網(wǎng)技術(shù)的發(fā)展(如千兆以太網(wǎng)標(biāo)準(zhǔn)^[3]的提出)滿足了高速網(wǎng)絡(luò)的多" title="的多">的多種關(guān)鍵需求，以太網(wǎng)技術(shù)的應(yīng)用范圍已經(jīng)由局域網(wǎng)(LAN)擴(kuò)展到城域網(wǎng)(WAN)。以太網(wǎng)是采用基于生成樹的路由算法，網(wǎng)絡(luò)結(jié)構(gòu)都簡化為簡單的樹形結(jié)構(gòu)。虛擬局域網(wǎng)(VLAN)^[4]及多生成樹協(xié)議(MSTP)[5]的提出為以太網(wǎng)流量均衡的實(shí)現(xiàn)提供了條件?；赩LAN和MSTP的以太網(wǎng)流量均衡選路算法[6]通過控制VLAN與生成樹拓?fù)涞挠成潢P(guān)系來實(shí)現(xiàn)業(yè)務(wù)流的選路，從而達(dá)到流量均衡的目的。但這種算法只是提高了有效鏈路" title="鏈路">鏈路的利用率及整個網(wǎng)絡(luò)樹形路徑上的流量均衡，并沒有解決網(wǎng)絡(luò)中兩個節(jié)點(diǎn)（尤其是匯聚節(jié)點(diǎn)）之間多條TRUNK鏈路的流量均衡。目前市場上的交換式網(wǎng)絡(luò)設(shè)備都是采用靜態(tài)配置的方法在多條TRUNK鏈路上進(jìn)行流量分配，一旦某條TRUNK路徑產(chǎn)生流量擁塞，網(wǎng)絡(luò)就不能在多條TRUNK上進(jìn)行流量自適應(yīng)調(diào)整，必須由人工修改配置，這大大增加了網(wǎng)絡(luò)維護(hù)的難度和網(wǎng)絡(luò)擁塞發(fā)生的概率。交換式網(wǎng)絡(luò)中多TRUNK路徑的MATE流量均衡旨在解決這個問題，實(shí)現(xiàn)多TRUNK之間的自適應(yīng)動態(tài)流量均衡。
1 問題場景描述
　　交換式網(wǎng)絡(luò)中多TRUNK路徑一般出現(xiàn)在網(wǎng)絡(luò)的匯接層面，如互聯(lián)網(wǎng)服務(wù)供應(yīng)商局端設(shè)備匯接了多臺接入設(shè)備，或匯接設(shè)備與核心設(shè)備之間的路由等。這里的TRUNK路徑指兩個節(jié)點(diǎn)間用于傳輸其他節(jié)點(diǎn)數(shù)據(jù)的鏈路，多TRUNK路徑指兩個節(jié)點(diǎn)間的多條等價鏈路。在交換式以太網(wǎng)中，如802.1Q封裝的就是VLAN TRUNK。下文描述兩個以太網(wǎng)接入過程中的多TRUNK路徑的場景。
1.1 二層交換網(wǎng)絡(luò)中的多TRUNK
　　二層交換網(wǎng)絡(luò)中的TRUNK環(huán)境如圖1所示。在小區(qū)、商務(wù)中心等駐地寬帶網(wǎng)建設(shè)過程中，一般采用以太網(wǎng)交換機(jī)組成的二層交換網(wǎng)絡(luò)，每幢樓根據(jù)用戶接入需求設(shè)置樓層接入交換機(jī)，多臺樓層交換機(jī)串連方式互聯(lián)，最終接到小區(qū)的匯接交換機(jī)，交換機(jī)上采用VLAN技術(shù)進(jìn)行安全隔離。在圖1所示的小區(qū)網(wǎng)絡(luò)中，共有五幢小區(qū)居民樓，其中‘2’號和‘4’號樓因用戶數(shù)較多串連了三臺樓層交換機(jī)，各采用了兩條到匯接交換機(jī)的TRUNK鏈路，其他三幢樓都是兩臺樓層交換機(jī)和一條TRUNK鏈路。小區(qū)匯接交換機(jī)接入網(wǎng)絡(luò)提供商的局端交換機(jī)時，考慮峰值流量和線路備份，也采用了兩條TRUNK鏈路。

?

3.1 初始化
　　這一階段主要完成交換式網(wǎng)絡(luò)環(huán)境的初始化，包括匯聚VLAN流量初始化、保障VLAN流量初始化和TRUNK流量初始化，并獲取初始化時延，用Init()實(shí)現(xiàn)。
#define RAND_MAX 01010000?? //設(shè)置隨機(jī)函數(shù)最大值為80%*L（鏈路帶寬），以便為各VLAN FE鏈路產(chǎn)生鏈路利用率80%以下的正常流量。
　　//初始化
　　Init（）
　　{
　　// 匯聚VLAN流量初始化
　　　　for（int i=0;i++;i　　　　　{fvlan3i=rand();}???? ?//初始化匯聚VLAN流量

　　//保障VLAN流量初始化
　　//假設(shè)有L條TRUNK,分為兩種情況:
　　//第一種，初始情況下，保障VLAN僅有一個，流量全部由Trunk0承載
　　//第二種，初始情況下，有L個保障VLAN，流量平均分擔(dān)在L條Trunk上,α為匯聚流量與保障流量的帶寬倍率。

　　//第一種情況 保障VLAN初始化
　　fu=rand()/α;
　　fvlan10=fu ;
　　for（int i=0;i++;i　　　{fvlan1i=0；};

　　//第二種情況 保障VLAN初始化：假設(shè)有L條TRUNK，也就有L個保障VLAN需要在L條TRUNK上負(fù)荷分擔(dān)流量
　　fu=rand( )/α;
　　for（int i=0;i++;i　　　　　{fvlan1i=fu/L;}

　　//Trunk流量初始化
　　for（int j=0; j++;j　　{Ftrj(old)=fvlan1j;
　　　　Qj=Q(Trunkj); ??//為Trunkj上的匯聚VLAN數(shù)量賦值
　　　　for（int i=0;i++;i　　　　{Ftrj(old)= Ftrj(old)+ fvlan3i ;}
　　　　Dtrj(old)=ICMP1;} ??//發(fā)送ICMP探測包、獲取各TRUNK的時延
　　}
　　}
　　上面算法中，通過隨機(jī)函數(shù)rand()為每個VLAN生成鏈路利用率80%以下的正常流量，根據(jù)VLAN的區(qū)分生成匯聚VLAN流量，然后根據(jù)通常情況下TRUNK流量分擔(dān)的情況，累加相關(guān)VLAN流量，得到各TRUNK的流量，最后通過發(fā)送ICMP包，獲取各TRUNK的初始化時延。
3.2 產(chǎn)生突發(fā)流量
　　這個階段通過產(chǎn)生突發(fā)流量來仿真網(wǎng)絡(luò)上流量發(fā)生變化的情況，從而使某TRUNK路徑上的流量過大產(chǎn)生擁塞問題，導(dǎo)致網(wǎng)絡(luò)質(zhì)量下降，用burst()函數(shù)實(shí)現(xiàn)。
　　//產(chǎn)生流量變化
　　Burst（）
　　{
　　//為匯聚VLAN產(chǎn)生隨機(jī)流量增量
　　for（j=0;j++;j　　{Δf=rand（）/β; ????//產(chǎn)生一個流量增量，
????　　　　　　　　　????β為流量增量因子
　　　fvlan3j=fvlan3j + Δf;}

　　//為保障VLAN產(chǎn)生隨機(jī)流量增量，同時計(jì)算保障VLAN
?????????????????? 總流量增量fl
　　fl=0;
　　for（int i=0;i++;i　　{cout << ' fvlan1i != 0' << endl;?
????　　?//如果是上面第一種情況，則只增加VLAN10的流量，跳出循環(huán)
　　Δfl=rand（）/αβ;??
　　fvlan1i=fvlan1i +Δfl;
　　fl=fl+Δfl;}

　　//更新所有Trunk流量
　　for（int j=0;j++;i　　{ Ftrj(new)=fvlan1j;
　　　Qj=Q(Trunkj);???????
　　　for（int i=0; i++; i　　　　{Ftrj(new)= Ftrj(new)+ fvlan3i ;}
　　　　Dtrj(new)=ICMP1;}? ???//發(fā)送ICMP探測包、獲取各TRUNK的時延
　　}
　　上面算法中，通過隨機(jī)函數(shù)為每個VLAN產(chǎn)生一個合適的突發(fā)流量，然后根據(jù)通常情況下TRUNK流量分擔(dān)的情況，累加相關(guān)VLAN流量，得到各TRUNK的流量。由于負(fù)荷調(diào)整的VLAN僅為保障VLAN,因此還需要計(jì)算這部分增加的流量，用于下一步流量負(fù)荷調(diào)整。另外還需要獲取流量變化后各TRUNK的時延。
3.3 平衡流量
　　這個階段實(shí)現(xiàn)突發(fā)流量的平衡，將某個TRUNK路徑上產(chǎn)生的過大突發(fā)流量均衡到其他TRUNK路徑上，從而實(shí)現(xiàn)多TRUNK路徑之間的自適應(yīng)流量調(diào)整，用balance()函數(shù)實(shí)現(xiàn)。
　　//平衡流量
　　Balance（）
　　{do
　　//獲取各TRUNK的時延導(dǎo)數(shù)絕對值U，找到最大和最小導(dǎo)數(shù)絕對值的TRUNK
　　U0=| Dtr0（new）-Dtr0（old）|/|Ftr0(new)-Ftr0(old)|;
　　MAX=U0; MIN=U0
　　for（int j=1;j++;i　　?{
　　　?Uj=|Dtrj（new）-Dtrj（old）|/| Ftrj(new)-Ftrj(old)|;
?? ?　　If Uj>MAX
??? ??　　MAX= Uj;
???? ??　　k=j;
???? ??　　v=0;
　　elseIf Uj　　??MIN=Uj;
　　?????? w=j;
????　　?? v=0;
　　else v=1;
　　}
　　//將導(dǎo)數(shù)絕對值最大的TRUNK的保障VLAN流量轉(zhuǎn)移fl/N至絕對值最小的TRUNK的保障VLAN
　　fvlan1k= fvlan1k - fl/N;
　　Ftrk= Ftr1 - fl/N;
　　fvlan1w= fvlan1w+ fl/N;
　　Ftrw= Ftrw+ fl/N;
　　Dtri（old）=Dtri（new）;
　　Dtri（new）=ICMPi;? ??//發(fā)送ICMP探測包、獲取TRUNK的時延
　　}
　　While (v != 1)
　　for（int j=1;j++;i　　{Ftrj(old) = Ftrj(new)；} }

　　上述算法中，各TRUNKi的保障VLAN的總流量增量為f l，將總流量增量f l分為N份，TRUNKj時延的導(dǎo)數(shù)的絕對值Uj=|Dtrj(new)-Dtrj(old)|/|Ftrj(new)-Ftrj(old)|。如果TRUNKj的導(dǎo)數(shù)的絕對值最大，TRUNKi的導(dǎo)數(shù)絕對值最小，則從VLAN1j移動f l/N流量到VLAN1j，反之則相反，直到各條TRUNK的時延變化率的絕對值相等。
實(shí)現(xiàn)流量均衡后，系統(tǒng)自動進(jìn)入監(jiān)測狀態(tài)，通過發(fā)送ICMP探測報文監(jiān)測各TRUNK路徑的動態(tài)鏈路狀態(tài)信息。
3.4 流量監(jiān)測
　　每隔一段時間（這個時間最好是一個隨機(jī)的時間，可以減少由于多個入口TRUNK在同一時間發(fā)現(xiàn)網(wǎng)絡(luò)變化造成同步的影響）在每條TRUNK上發(fā)送探測包，發(fā)送的探測包不足鏈路上流量的百分之一，獲取TRUNKj的時延Dtrj（new）。如果發(fā)現(xiàn)新的時延增量大于門限值，則回到流量平衡階段。
采用適應(yīng)性流量工程[7]能更有效地利用網(wǎng)絡(luò)資源，使擁塞最小化。在兩個節(jié)點(diǎn)之間多條平行的流量主干上進(jìn)行負(fù)載分配是一個十分重要的問題。在許多情況下，兩個節(jié)點(diǎn)之間的某業(yè)務(wù)量無法由任何一條單獨(dú)的鏈路或路徑來承擔(dān)。然而該業(yè)務(wù)流量所需的資源可能低于網(wǎng)絡(luò)中所有可用路徑能夠提供的總量。此時唯一的方法是將業(yè)務(wù)流量分解為一些流量子集，再將這些流量子集通過多條路徑來加以傳輸。在交換式網(wǎng)絡(luò)環(huán)境中，上述問題可以通過在兩個節(jié)點(diǎn)之間發(fā)起多條TRUNK路徑來解決。但要實(shí)現(xiàn)這一過程，必須要設(shè)計(jì)一種能夠?qū)Χ鄺l平行的流量主干靈活地進(jìn)行負(fù)載分配的技術(shù)。文中給出了MATE多路徑自適應(yīng)算法，該算法在多TRUNK路徑之間分配流量，從而達(dá)到負(fù)載均衡化和擁塞最小化的目的。下一步工作將通過仿真平臺[8]驗(yàn)證MATE算法解決多TRUNK路徑流量均衡的有效性。

參考文獻(xiàn)
[1]?ELWALID A, CHENG Jin, LOW S, et al. MATE:MPLS?Adaptive Traffic Engineering[J], IEEE 2001.
[2]?AWDUCHE D, MALCOLM J, AGOGBUA J, et al.?Requirements for traffic engineering over MPLS[S].? IETF ??RFC 2702, Sep.1999.
[3]?Draft Standard IEEE 802.3z. Media Access Control(MAC)　Parameters, Physical Layer,Repeater and Management??Parameters for1000Mb/s Operation[S].1998.
[4]?IEEE Standard 802.1Q. Virtual Bridged Local Area?Networks[S]. 1998.
[5]?IEEE 802.1s/D7.Draft Supplement to Virtual Bridged?Local AreaNetworks:Multiple Spanning Tree.IEEE Standard ?for Local and Metropolitan Area Networks[S], 2000.
[6]?劉軍，雷振明.基于VLAN的以太網(wǎng)流量均衡選路算法[J]. 計(jì)算機(jī)工程，2003，(12).
[7]?ALI M, CHIRUVOLU G, AN Ge. Traffic engineering in?metro ethernet[J], IEEE Network, March/April 2005.
[8]?徐雷鳴，龐博,趙耀.NS與網(wǎng)絡(luò)模擬[M]，北京：人民郵電出版社, 2003.

?