摘 要： MATE算法通過檢測多條路徑的狀態(tài)并計算其成本實現(xiàn)多條等價路徑上的自適應(yīng)流量調(diào)整，從而實現(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è)計網(wǎng)絡(luò)為客戶提供快速、可靠和區(qū)分服務(wù)的挑戰(zhàn)。在計算網(wǎng)絡(luò)成本的模式下，互聯(lián)網(wǎng)流量工程成為實現(xiàn)這個目標(biāo)的一種關(guān)鍵技術(shù)[1]。根據(jù)IETF，互聯(lián)網(wǎng)流量工程被定義為:在運行的IP網(wǎng)絡(luò)上進行性能評估和性能優(yōu)化的網(wǎng)絡(luò)工程[2]。更精確地講，流量工程經(jīng)常有效地將流量需求映射到網(wǎng)絡(luò)拓?fù)洌⒆詣诱{(diào)節(jié)這種映射關(guān)系以適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化。值得一提的是，流量工程是通過滿足一些限定條件來實現(xià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)擴展到城域網(wǎng)(WAN)。以太網(wǎng)是采用基于生成樹的路由算法，網(wǎng)絡(luò)結(jié)構(gòu)都簡化為簡單的樹形結(jié)構(gòu)。虛擬局域網(wǎng)(VLAN)[4]及多生成樹協(xié)議(MSTP)[5]的提出為以太網(wǎng)流量均衡的實現(xiàn)提供了條件。基于VLAN和MSTP的以太網(wǎng)流量均衡選路算法[6]通過控制VLAN與生成樹拓?fù)涞挠成潢P(guān)系來實現(xiàn)業(yè)務(wù)流的選路，從而達到流量均衡的目的。但這種算法只是提高了有效鏈路" title="鏈路">鏈路的利用率及整個網(wǎng)絡(luò)樹形路徑上的流量均衡，并沒有解決網(wǎng)絡(luò)中兩個節(jié)點（尤其是匯聚節(jié)點）之間多條TRUNK鏈路的流量均衡。目前市場上的交換式網(wǎng)絡(luò)設(shè)備都是采用靜態(tài)配置的方法在多條TRUNK鏈路上進行流量分配，一旦某條TRUNK路徑產(chǎn)生流量擁塞，網(wǎng)絡(luò)就不能在多條TRUNK上進行流量自適應(yīng)調(diào)整，必須由人工修改配置，這大大增加了網(wǎng)絡(luò)維護的難度和網(wǎng)絡(luò)擁塞發(fā)生的概率。交換式網(wǎng)絡(luò)中多TRUNK路徑的MATE流量均衡旨在解決這個問題，實現(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é)點間用于傳輸其他節(jié)點數(shù)據(jù)的鏈路，多TRUNK路徑指兩個節(jié)點間的多條等價鏈路。在交換式以太網(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)交換機組成的二層交換網(wǎng)絡(luò)，每幢樓根據(jù)用戶接入需求設(shè)置樓層接入交換機，多臺樓層交換機串連方式互聯(lián)，最終接到小區(qū)的匯接交換機，交換機上采用VLAN技術(shù)進行安全隔離。在圖1所示的小區(qū)網(wǎng)絡(luò)中，共有五幢小區(qū)居民樓，其中‘2’號和‘4’號樓因用戶數(shù)較多串連了三臺樓層交換機，各采用了兩條到匯接交換機的TRUNK鏈路，其他三幢樓都是兩臺樓層交換機和一條TRUNK鏈路。小區(qū)匯接交換機接入網(wǎng)絡(luò)提供商的局端交換機時，考慮峰值流量和線路備份，也采用了兩條TRUNK鏈路。
?
在匯接交換機到局端交換機之間的兩條TRUNK鏈路上配置了不同的VLAN用于輸送不同樓的流量，TRUNK1上配置了VLAN 20～23，TRUNK2配置了VLAN 24～26。因‘1’號樓具有特殊的通信重要性，其VLAN 20同時配置在兩條TRUNK上，以保證一條線路故障時能自動切換到另一條線路。根據(jù)以太網(wǎng)的工作原理，正常情況下，VLAN20只會選擇其中的一條鏈路，不會均分到兩條鏈路上，更不會根據(jù)兩條TRUNK鏈路的流量狀況自動調(diào)節(jié)其流量負(fù)載以達到最佳性能，一旦該TRUNK鏈路上其他VLAN的流量增大產(chǎn)生擁塞，VLAN20用戶的訪問質(zhì)量就會明顯下降，但目前情況下是沒有辦法解決的。
1.2 三層交換到路由之間的多TRUNK
三層交換到路由之間的多TRUNK環(huán)境如圖2所示。在網(wǎng)絡(luò)服務(wù)商提供的局端匯接交換機（三層交換機）與核心路由器之間有兩條TRUNK鏈路，TRUNK1上的VLAN 30～35和TRUNK2上的VLAN 36～39用于將一些專線用戶直接二層透傳到核心路由器，其三層路由在核心路由器上實現(xiàn)；TRUNK1上的VLAN 10和TRUNK2上的VLAN 11用于轉(zhuǎn)發(fā)匯接交換機到核心路由器之間的其他流量，匯接交換機上這兩個VLAN下直接配置IP地址和相關(guān)的默認(rèn)路由。假設(shè)這兩條路徑是等價的，根據(jù)PER-DESTINATION或PER-PACKET的三層轉(zhuǎn)發(fā)原則，其他流量會均分到TRUNK1的VLAN 10和TRUNK2的 VLAN 11兩個虛口上。當(dāng)某條TRUNK鏈路上的透傳VLAN流量增大造成擁塞時，該鏈路上的轉(zhuǎn)發(fā)流量是無法根據(jù)當(dāng)前鏈路狀況自動調(diào)整到另一條空閑鏈路上實現(xiàn)動態(tài)流量均衡的。
?
2 MATE算法
MATE(Multipath Adaptive Traffic Engineering)算法[1]是一個基于狀態(tài)的流量工程機制，稱為。它的特點有：
(1) 分布式自適應(yīng)負(fù)載均衡算法;
(2) 入節(jié)點和出節(jié)點之間的端到端控制;
(3) 不需要在中間節(jié)點引入新的硬件或協(xié)議;
(4) 不需要知道流量需求;
(5) 對節(jié)點上的調(diào)度或緩沖管理機制不做假定;
(6) 基于路徑擁塞測量的優(yōu)化決定;
(7) 最少的分組重排序;
(8) 在兩個節(jié)點之間沒有時鐘同步。
假設(shè)在鏈路l∈L上的流量為所有經(jīng)過l的TRUNK上的源速率的總和：
?與每個鏈路l相關(guān)聯(lián)的成本函數(shù)是Cl(xl)，作為鏈路流量xl的函數(shù)。假設(shè)對于所有的鏈路l，Cl(·)為凸函數(shù)，是連續(xù)的。算法的主要思想是：
(1)算法的目標(biāo)是通過在TRUNKs上最優(yōu)化流量路由，使總成本：C(x)=
為最小。
(2)將鏈路L的成本函數(shù)的一次導(dǎo)數(shù)看作鏈路的一次導(dǎo)數(shù)長度。
(3) 最優(yōu)速率是在最優(yōu)情況下，鏈路L的成本函數(shù)的一次導(dǎo)數(shù)長度最小。
成本函數(shù)的選擇決定了在執(zhí)行MATE中要測量和均衡的參數(shù)。鏈路成本的一個自然選擇是時延" title="時延">時延。圖3描述了流量均衡的基本模型。
?
測量和分析模塊主要用于發(fā)送探測包，獲取TRUNK路徑時延，并測量各VLAN和TRUNK上的流量，分析計算可以負(fù)荷調(diào)整的流量。流量工程模塊決定在多TRUNK路徑間轉(zhuǎn)移流量的時間和方式，用于實現(xiàn)流量均衡，是算法實現(xiàn)的核心。它基于使用探測包分組測量獲得的TRUNK路徑統(tǒng)計信息完成。流量工程有兩個階段：監(jiān)視階段和負(fù)載均衡階段。在監(jiān)視階段，如果探測到網(wǎng)絡(luò)狀態(tài)是可估計和持久變化的，就轉(zhuǎn)移到負(fù)載均衡階段。在負(fù)載均衡階段，算法試圖使多TRUNK路徑之間的擁塞測量結(jié)果相等。一旦測量結(jié)果相等，算法就轉(zhuǎn)移到監(jiān)視階段，重復(fù)以上過程。
3 多TRUNK路徑的MATE流量均衡
在多TRUNK路徑的MATE流量均衡中，將TRUNK上的流量劃分為：(1)需要負(fù)荷分擔(dān)的VLAN流量(如場景一中的VLAN20，場景二中的VLAN10和VLAN11)，稱為保障流量；(2)不需要負(fù)荷分擔(dān)的VLAN流量，稱為匯聚流量。選取TRUNK時延為成本函數(shù)，最優(yōu)速率的情況是TRUNK時延對流量的一次偏導(dǎo)數(shù)的絕對值最小。將導(dǎo)數(shù)絕對值最大的TRUNK的保障VLAN流量轉(zhuǎn)移fl/N至絕對值最小的TRUNK的保障VLAN，直到所有TRUNK的導(dǎo)數(shù)絕對值近似相等。
流量負(fù)荷分擔(dān)的過程分為四個階段，如圖4所示。
?
3.1 初始化
這一階段主要完成交換式網(wǎng)絡(luò)環(huán)境的初始化，包括匯聚VLAN流量初始化、保障VLAN流量初始化和TRUNK流量初始化，并獲取初始化時延，用Init()實現(xiàn)。
#define RAND_MAX 01010000?? //設(shè)置隨機函數(shù)最大值為80%*L（鏈路帶寬），以便為各VLAN FE鏈路產(chǎn)生鏈路利用率80%以下的正常流量。
//初始化
Init（）
{
// 匯聚VLAN流量初始化
for（int i=0;i++;i
//保障VLAN流量初始化
//假設(shè)有L條TRUNK,分為兩種情況:
//第一種，初始情況下，保障VLAN僅有一個，流量全部由Trunk0承載
//第二種，初始情況下，有L個保障VLAN，流量平均分擔(dān)在L條Trunk上,α為匯聚流量與保障流量的帶寬倍率。
//第一種情況 保障VLAN初始化
fu=rand()/α;
fvlan10=fu ;
for（int i=0;i++;i
//第二種情況 保障VLAN初始化：假設(shè)有L條TRUNK，也就有L個保障VLAN需要在L條TRUNK上負(fù)荷分擔(dān)流量
fu=rand( )/α;
for（int i=0;i++;i
//Trunk流量初始化
for（int j=0; j++;j
Qj=Q(Trunkj); ??//為Trunkj上的匯聚VLAN數(shù)量賦值
for（int i=0;i++;i
Dtrj(old)=ICMP1;} ??//發(fā)送ICMP探測包、獲取各TRUNK的時延
}
}
上面算法中，通過隨機函數(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ù)實現(xiàn)。
//產(chǎn)生流量變化
Burst（）
{
//為匯聚VLAN產(chǎn)生隨機流量增量
for（j=0;j++;j
???? ????β為流量增量因子
fvlan3j=fvlan3j + Δf;}
//為保障VLAN產(chǎn)生隨機流量增量，同時計算保障VLAN
?????????????????? 總流量增量fl
fl=0;
for（int i=0;i++;i
???? ?//如果是上面第一種情況，則只增加VLAN10的流量，跳出循環(huán)
Δfl=rand（）/αβ;??
fvlan1i=fvlan1i +Δfl;
fl=fl+Δfl;}
//更新所有Trunk流量
for（int j=0;j++;i
Qj=Q(Trunkj);???????
for（int i=0; i++; i
Dtrj(new)=ICMP1;}? ???//發(fā)送ICMP探測包、獲取各TRUNK的時延
}
上面算法中，通過隨機函數(shù)為每個VLAN產(chǎn)生一個合適的突發(fā)流量，然后根據(jù)通常情況下TRUNK流量分擔(dān)的情況，累加相關(guān)VLAN流量，得到各TRUNK的流量。由于負(fù)荷調(diào)整的VLAN僅為保障VLAN,因此還需要計算這部分增加的流量，用于下一步流量負(fù)荷調(diào)整。另外還需要獲取流量變化后各TRUNK的時延。
3.3 平衡流量
這個階段實現(xiàn)突發(fā)流量的平衡，將某個TRUNK路徑上產(chǎn)生的過大突發(fā)流量均衡到其他TRUNK路徑上，從而實現(xiàn)多TRUNK路徑之間的自適應(yīng)流量調(diào)整，用balance()函數(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
?????? 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
上述算法中，各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的時延變化率的絕對值相等。
實現(xiàn)流量均衡后，系統(tǒng)自動進入監(jiān)測狀態(tài)，通過發(fā)送ICMP探測報文監(jiān)測各TRUNK路徑的動態(tài)鏈路狀態(tài)信息。
3.4 流量監(jiān)測
每隔一段時間（這個時間最好是一個隨機的時間，可以減少由于多個入口TRUNK在同一時間發(fā)現(xiàn)網(wǎng)絡(luò)變化造成同步的影響）在每條TRUNK上發(fā)送探測包，發(fā)送的探測包不足鏈路上流量的百分之一，獲取TRUNKj的時延Dtrj（new）。如果發(fā)現(xiàn)新的時延增量大于門限值，則回到流量平衡階段。
采用適應(yīng)性流量工程[7]能更有效地利用網(wǎng)絡(luò)資源，使擁塞最小化。在兩個節(jié)點之間多條平行的流量主干上進行負(fù)載分配是一個十分重要的問題。在許多情況下，兩個節(jié)點之間的某業(yè)務(wù)量無法由任何一條單獨的鏈路或路徑來承擔(dān)。然而該業(yè)務(wù)流量所需的資源可能低于網(wǎng)絡(luò)中所有可用路徑能夠提供的總量。此時唯一的方法是將業(yè)務(wù)流量分解為一些流量子集，再將這些流量子集通過多條路徑來加以傳輸。在交換式網(wǎng)絡(luò)環(huán)境中，上述問題可以通過在兩個節(jié)點之間發(fā)起多條TRUNK路徑來解決。但要實現(xiàn)這一過程，必須要設(shè)計一種能夠?qū)Χ鄺l平行的流量主干靈活地進行負(fù)載分配的技術(shù)。文中給出了MATE多路徑自適應(yīng)算法，該算法在多TRUNK路徑之間分配流量，從而達到負(fù)載均衡化和擁塞最小化的目的。下一步工作將通過仿真平臺[8]驗證MATE算法解決多TRUNK路徑流量均衡的有效性。
參考文獻
[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]. 計算機工程，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.
?