MPLS網絡中基于信息反饋的流量工程路徑計算

徐 方，趙國濤

（1.湖北工程學院 現代教育技術中心，湖北 孝感432000；2.湖北工程學院 外國語學院，湖北 孝感432000）

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

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

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

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

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

1 流量工程的路徑計算

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

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

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

使用如下函數分配動態鏈路的權限w（i，j）：

● Assign＿Dynamic＿link＿weights（）：

圖1 MIRA算法

圖2 B＿MIRA算法

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

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

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

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

●Identify＿CN（）：

●Assign＿Dynamic＿link＿Weight（）：

每一個鏈路被分配一個動態權重w（i，j），

●關鍵的路徑P定義為：

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

圖3 MCKS算法

2 性能分析

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

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

圖4 服務請求數與帶寬擁塞

圖5 平均路徑負載

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

3 結論

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

［1］唐治果，李樂民，虞紅芳，等.針對MPLS網絡流量工程的鏈路關鍵性路由算法［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］張靜，邱學紹.網絡最大流模型算法及其實現［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.