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