MPLS網(wǎng)絡(luò)中基于信息反饋的流量工程路徑計(jì)算

徐 方，趙國(guó)濤

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

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

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

傳統(tǒng)的盡力而為的IP網(wǎng)絡(luò)一直青睞“最短路徑”的算法，是因?yàn)橐紤]所有負(fù)載條件下的效率和穩(wěn)定性。但是隨著人們對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量的進(jìn)一步重視，除了計(jì)算源端到目的端的最小路徑外，還非常有必要找到與最小路徑不同的其他路徑。這是因?yàn)樽疃搪窂阶兊酶叨葥砣渌捎寐窂絽s只有相對(duì)較低的利用率。此外，由于不同的數(shù)據(jù)流量有不同的QoS要求，一個(gè)單一的路徑不能夠滿足所有源端到目的端流量的要求。

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

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

1 流量工程的路徑計(jì)算

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

1.1 約束路徑上的最大開(kāi)放流

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

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

● Assign＿Dynamic＿link＿weights（）：

圖1 MIRA算法

圖2 B＿M(jìn)IRA算法

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

2.2 使用TE信息降低算法的復(fù)雜度

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

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

●Identify＿CN（）：

●Assign＿Dynamic＿link＿Weight（）：

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

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

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

圖3 MCKS算法

2 性能分析

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

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

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

圖5 平均路徑負(fù)載

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

3 結(jié)論

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

［1］唐治果，李樂(lè)民，虞紅芳，等.針對(duì)MPLS網(wǎng)絡(luò)流量工程的鏈路關(guān)鍵性路由算法［J］.電子與信息學(xué)報(bào)，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］張靜，邱學(xué)紹.網(wǎng)絡(luò)最大流模型算法及其實(shí)現(xiàn)［J］.重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，29（5）：132－134.

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

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