徐 方，趙國濤

（1.湖北工程學院 現(xiàn)代教育技術(shù)中心，湖北 孝感432000；2.湖北工程學院 外國語學院，湖北 孝感432000）

隨著互聯(lián)網(wǎng)數(shù)據(jù)呈現(xiàn)指數(shù)級的增長，對網(wǎng)絡(luò)的管理和控制顯得越來越重要。顯然，增加網(wǎng)絡(luò)帶寬并不能解決所有網(wǎng)絡(luò)擁堵的問題。與此同時，越來越多的網(wǎng)絡(luò)運營商非常有興趣在他們的網(wǎng)絡(luò)中提供差異化的服務(wù)。這些需求使得通過自動流量工程（Traffic Engineering，TE）獲得網(wǎng)絡(luò)的控制權(quán)變得日益重要。TE能減少擁塞，提高網(wǎng)絡(luò)利用率，滿足多樣化的需求。

流量工程是MPLS網(wǎng)絡(luò)中最重要的應用［1］。MPLS流量工程（MPLS－TE）可以通過協(xié)調(diào)網(wǎng)絡(luò)資源的請求和當前可用資源來增加MPLS骨干網(wǎng)網(wǎng)絡(luò)傳輸能力。由于流量工程的本質(zhì)是將流量映射到物理拓撲結(jié)構(gòu)，這意味著，在MPLS－TE的核心部分是路徑計算的問題。

傳統(tǒng)的盡力而為的IP網(wǎng)絡(luò)一直青睞“最短路徑”的算法，是因為要考慮所有負載條件下的效率和穩(wěn)定性。但是隨著人們對網(wǎng)絡(luò)服務(wù)質(zhì)量的進一步重視，除了計算源端到目的端的最小路徑外，還非常有必要找到與最小路徑不同的其他路徑。這是因為最短路徑變得高度擁塞，而其他可用路徑卻只有相對較低的利用率。此外，由于不同的數(shù)據(jù)流量有不同的QoS要求，一個單一的路徑不能夠滿足所有源端到目的端流量的要求。

傳統(tǒng)的路徑計算算法，主要是通過優(yōu)化靜態(tài)指標（如鏈路成本／長度等）逐跳計算的算法。其中，新一代TE算法認為可以設(shè)置鏈路的動態(tài)權(quán)重，但這建立在已知將來帶寬請求的基礎(chǔ)上。MIRA［2］討論了源路由方案，它使用另一個動態(tài)約束（在網(wǎng)絡(luò)中可用的最大流量）確定關(guān)鍵鏈路，算法返回的路徑試圖避免那些不可靠的路徑。

本文提出了一種使用靜態(tài)和動態(tài)鏈路約束的源路由算法。該算法通過計算由首跳路徑長度來改進MIRA，以便它不超過某一閾值T；然后通過最大流計算［3］找到一個最小擁塞路徑。在MIRA的最大流計算中，應該注意到大型網(wǎng)絡(luò)運行中計算密集型的問題。作為替代方案，建議從動態(tài)識別的關(guān)鍵鏈路中使用相關(guān)信息反饋的方式。

1 流量工程的路徑計算

在本文中，QoS請求的形式為（A，B，Bw）：其中A為源節(jié)點，B為目的地節(jié)點，Bw為應用需要的最小帶寬。使用TE路徑計算算法，可以計算滿足BwPA－B的路徑。本文假設(shè)可以通過TE信令機制（如CR－LDP和RSVP［4］）在PA－B路徑上為應用程序預留帶寬資源。

1.1 約束路徑上的最大開放流

MIRA啟發(fā)式地提出要尋找一對節(jié)點之間的路徑的方法，在其所有源節(jié)點到目地節(jié)點中尋找擁塞程度最小的可用流路徑。下面給出了該算法的主要思想：

使用如下函數(shù)分配動態(tài)鏈路的權(quán)限w（i，j）：

● Assign＿Dynamic＿link＿weights（）：

圖1 MIRA算法

圖2 B＿MIRA算法

本文提出的第一個算法是對MIRA的改進，稱之為B＿MIRA（Bounded－MIRA）。使用u（i，j）作為靜態(tài)鏈路度量值。在這種新的路徑計算方案中，同時考慮了動態(tài)分配的 w（i，j）和靜態(tài)u（i，j）。在實驗中，使用的靜態(tài)度量值是鏈路的長度。B＿MIRA的特色是首先提出了使用基于靜態(tài)鏈路度量u（i，j）的K 短路徑［5］算法找到候選路徑集，它將返回一個K路徑集合，該集合是通過MIRA類計算找到在所有源－目的節(jié)點對中擁塞最小的最大流路徑。因此，返回的路徑是不會遜色于K－最短路徑。

2.2 使用TE信息降低算法的復雜度

最大流計算的應用使得使用動態(tài)信息約束進行路徑計算成為可能。使用有界的MIRA類型算法，可以找到長度約束的最低阻塞路徑。然而，眾所周知的最大流算法的復雜度O（n2），而最簡單的最短路徑算法的復雜度是O（nlogn）。最大流量計算的計算開銷很大，尤其是當運行數(shù)以百萬計的請求時。本文建議使用另一種動態(tài)約束——鏈路負載（link＿load），它不需要很大的計算開銷。相反，可以依靠現(xiàn)有的流量工程基礎(chǔ)設(shè)施提供鏈路負載信息。假設(shè)大多數(shù)網(wǎng)絡(luò)運行鏈路狀態(tài)的內(nèi)部網(wǎng)關(guān)協(xié)議（IGP）計算路由。文獻［6］通過使用動態(tài)TE信息簡單的擴展的方法，如將預留鏈路帶寬定期反饋到源節(jié)點。這些信息可以用于取代使用最大流計算獲得的關(guān)鍵鏈路信息。鏈路負載的定義如下：

關(guān)鍵鏈路被定義為其運行負載超過閾值百分比U的鏈路，改進的算法使用下面的函數(shù)和參數(shù)。

●Identify＿CN（）：

●Assign＿Dynamic＿link＿Weight（）：

每一個鏈路被分配一個動態(tài)權(quán)重w（i，j），

●關(guān)鍵的路徑P定義為：

本文所提出的最小關(guān)鍵K－最短路徑算法（MCKS）的計算過程同時考慮了動態(tài)分配的鏈路權(quán)重w（i，j）和靜態(tài)鏈路度量u（i，j）。MCKS和B＿MIRA的不同之處在于臨界值的定義和計算復雜度的不同。MCKS算法如圖3所示。

圖3 MCKS算法

2 性能分析

下面對目前主流的路徑計算算法進行比較實驗，給出初步的比較結(jié)果。所有的實驗運行在一個由20個節(jié)點隨機組成的網(wǎng)絡(luò)上，所有鏈路都是均衡分布，并隨機分配權(quán)重。鏈接的傳輸能力變化是平緩的，從中度（12000單位的預留帶寬）到高（48000單位的預留帶寬）。所有鏈路的傳輸能力中和高的比例固定為3：1。對于每個網(wǎng)絡(luò)，所有可能的源－目節(jié)點對屬于一個固定的集合S。網(wǎng)絡(luò)資源的請求的形式為（src，dest，Bw）。從S中隨時挑選源節(jié)點和目的節(jié)點。

實驗結(jié)果由一個包含20個節(jié)點組成的網(wǎng)絡(luò)中進行。圖4是對比 MIRA、B＿MIRA和 Min＿Dist得到的帶寬請求被拒絕的情況。從圖4上可以看出，高負載下的網(wǎng)絡(luò)阻塞大約在請求數(shù)到20000才開始，Min＿Dist在帶寬請求被拒絕的情況相對較多。隨著負載的增加，MIRA和B＿MIRA兩種算法的表現(xiàn)相差不大。

圖4 服務(wù)請求數(shù)與帶寬擁塞

圖5 平均路徑負載

路徑的負載計算是在這條路徑的所有鏈路負載中選擇最大值。圖5是在高負載條件下的平均路徑負載對照結(jié)果，可以看出，MCKS路徑的平均負載是最低的，B＿MIRA的平均負載低于MIRA。

3 結(jié)論

由上述實驗結(jié)果可以看出，動態(tài)鏈接度量指標可以幫助網(wǎng)絡(luò)保持最佳的網(wǎng)絡(luò)負載水平，而結(jié)合使用靜態(tài)約束（如鏈路長度）來描述路徑特征能取得更好的效果，避免了在高負荷條件下使用過多的重要網(wǎng)絡(luò)資源。本文研究表明，利用TE反饋信息，代替高開銷的最大流計算，可以有效降低流量工程計算算法的復雜度，在高負載下能提供良好的性能。從這個角度來看，MCKS是一種高效的TE路徑計算算法。

［1］唐治果，李樂民，虞紅芳，等.針對MPLS網(wǎng)絡(luò)流量工程的鏈路關(guān)鍵性路由算法［J］.電子與信息學報，2007，29（5）：1187－1190.

［2］Kodialam M，Lakshman T.Minimum Interference Routing with Applications to MPLS Traffic Engineering［C］／／Proceedings of IEEE INFOCOM’2009，2009.

［3］張靜，邱學紹.網(wǎng)絡(luò)最大流模型算法及其實現(xiàn)［J］.重慶大學學報：自然科學版，2006，29（5）：132－134.

［4］李效虎，張興明，蘭巨龍，等.MPLS流量工程中的RSVP和CR－LDP［J］.信息工程大學學報，2003，4（4）：50－53.

［5］Eppstein D.Finding the k shortest paths［J］.SIAM Journal on Computing，1998，28：652－673.