于約束的GMPLS恢復(fù)算法

在分析與恢復(fù)技術(shù)有關(guān)的GMPLS技術(shù)特性基礎(chǔ)上，提出了一種基于約束的GMPLS恢復(fù)算法(CGR)，并對相關(guān)的約束條件的設(shè)置做了具體的規(guī)定和說明，以網(wǎng)狀網(wǎng)為例，詳細(xì)介紹了所提出算法的實現(xiàn)方法和特點。該算法借鑒了傳統(tǒng)恢復(fù)技術(shù)的優(yōu)點，又充分考慮到GMPLS網(wǎng)的特性，使其具有繼承性和兼容性。
關(guān) 鍵 詞 通用多協(xié)議標(biāo)簽交換; 標(biāo)簽交換路徑; 生存性; 恢復(fù)

隨著IP技術(shù)的發(fā)展，用戶對IP網(wǎng)的依賴越來越大，但由于技術(shù)的局限性，使得采用IP技術(shù)進(jìn)行實時和寬帶業(yè)務(wù)的傳遞時，無法保證所傳業(yè)務(wù)的服務(wù)質(zhì)量。光傳送網(wǎng)的發(fā)展為IP技術(shù)的應(yīng)用提供了一個可靠的傳送平臺，通用多協(xié)議標(biāo)簽交換 (Generalized Multi-protocol Label Switching, GMPLS)技術(shù)則是實現(xiàn)IP技術(shù)與光傳送技術(shù)結(jié)合的最佳途徑。為了適應(yīng)對這種網(wǎng)絡(luò)進(jìn)行動態(tài)控制的要求,GMPLS對傳統(tǒng)的[1]多協(xié)議標(biāo)簽交換(Multi-protocol Label Switching, MPLS)進(jìn)行了擴(kuò)展更新。在這種通用、高帶寬網(wǎng)絡(luò)環(huán)境下，網(wǎng)絡(luò)中的任何故障都會造成大量數(shù)據(jù)的丟失。因此無論是從用戶的角度，還是從運(yùn)營商的角度，都迫切需要在網(wǎng)絡(luò)發(fā)生故障后能盡快地將受故障影響的業(yè)務(wù)恢復(fù)，特別是一些對實時性要求高的業(yè)務(wù)，其恢復(fù)速度必須滿足業(yè)務(wù)的需求[2]。
恢復(fù)算法是網(wǎng)絡(luò)在發(fā)生故障后對受故障影響的業(yè)務(wù)進(jìn)行重新建立路由的過程。這里，路由的重新建立一定要遵循“在中斷前完成”的原則，即在新通道被建立時仍使用原通道，執(zhí)行完路由倒換后再將原路由拆除。傳統(tǒng)的IP網(wǎng)中故障恢復(fù)采用集中控制的方式，當(dāng)故障發(fā)生時，網(wǎng)絡(luò)管理員發(fā)現(xiàn)故障告警信號后，對受故障影響的業(yè)務(wù)流進(jìn)行手動重新配置。與IP網(wǎng)不同，基于GMPLS的網(wǎng)絡(luò)是在傳送數(shù)據(jù)前建立標(biāo)簽交換路徑(Label Switch Paths, LSPs)，GMPLS 的恢復(fù)是基于LSP的恢復(fù)，這為基于GMPLS網(wǎng)絡(luò)的恢復(fù)技術(shù)提供了很多方便，可大大提高恢復(fù)速度[3,4]。

有關(guān)GMPLS恢復(fù)技術(shù)的研究則剛剛開始，在進(jìn)行這方面的研究時，一方面要借鑒傳統(tǒng)恢復(fù)技術(shù)的優(yōu)點，使其具有繼承性和兼容性，同時還要充分考慮到GMPLS網(wǎng)的特性[5]。本文正是在這種背景下提出一種基于約束的GMPLS恢復(fù)算法。
1 恢復(fù)算法的基本思想
在進(jìn)行GMPLS恢復(fù)算法的設(shè)計時，首先要充分考慮到其網(wǎng)絡(luò)特性。從網(wǎng)絡(luò)恢復(fù)技術(shù)的角度來看，GMPLS有以下特性：1) 多類型的交換和轉(zhuǎn)發(fā)層次。GMPLS可以支持時分復(fù)用(Time Division Multiplexing, TDM)、波長交換(Lambda Switch Capable, LSC)和光纖交換(Fiber Switch Capable, FSC)，這些新型的交換設(shè)備可以提供多種不同速率的交換接口，適用于在網(wǎng)絡(luò)邊緣對多種不同業(yè)務(wù)的接入。2) GMPLS 對IGP的擴(kuò)展。GMPLS對內(nèi)部網(wǎng)關(guān)協(xié)議(Internal Gateway Protocol, IGP)進(jìn)行擴(kuò)展，使它能夠?qū)⒏鞣N類型的鏈路廣播發(fā)送到常規(guī)鏈路上或非包/分組(TDM時隙、波長或光纖)鏈路上，并支持鄰近轉(zhuǎn)發(fā)(Adjacent Forwarding)。3) GMPLS中LSP的分級。GMPLS通過定義LSP的等級來完成LSP的嵌套，從而支持業(yè)務(wù)量干線隧道的建立。最低等級的LSP(FSC接口)是開始和終結(jié)于分組交換的節(jié)點上，比它高一級的LSP(TDM接口)是開始和終結(jié)在TDM交換節(jié)點上，更高一級的LSP(LSC接口)是開始和終結(jié)在波長交換節(jié)點上，最高等級的LSP(FSC接口)是開始和終結(jié)在光纖交換節(jié)點上[5]。4) 雙向LSP的建立。在GMPLS中，雙向LSP的建立是被允許的。無論上游或者下游通道，都使用相同的一套信令系統(tǒng)，從而降低了延遲時間，減少了控制開銷。5) 鏈路綁定。為了提高流量工程的可擴(kuò)展性并減少標(biāo)簽資源的使用，GMPLS允許把一套平行的鏈路歸并到同一個IGP中作為單個鏈路使用，產(chǎn)生的這條邏輯鏈路稱為綁定鏈路(Bundled Link)，其物理鏈路被稱作組成鏈路(Component Link)。6) 約束路由。GMPLS使用約束路由機(jī)制來分配相關(guān)的傳輸網(wǎng)絡(luò)拓?fù)?a target='_blank' class='arckwlink_none'>信息，包括使用IGP轉(zhuǎn)發(fā)相鄰節(jié)點的狀態(tài)信息。約束路由的出現(xiàn)使傳統(tǒng)的路由算法有了改進(jìn)的可能，基于約束的GMPLS恢復(fù)算法就是基于這種約束的路由算法。
在進(jìn)行恢復(fù)路由的選擇時，考慮到GMPLS的技術(shù)特性，對所選的路由給出相應(yīng)的約束條件(包括帶寬需求、最大跳數(shù)等)，從而使選出的恢復(fù)路由不僅最短，同時能合理地利用帶寬資源，并適應(yīng)不同業(yè)務(wù)及交換類型對恢復(fù)路由的要求，使恢復(fù)算法達(dá)到最優(yōu)。
2 約束條件的設(shè)置
GMPLS的約束條件通常對信令類、編解碼類和交換類三個方面進(jìn)行考慮，具體又可分為對LSP的約束和對LINK的約束兩部分。
2.1 LSP的約束條件
1) 帶寬需求。即當(dāng)此LSP加載在該鏈路或路徑上的時候，該鏈路或者路徑是否能夠具有足夠的帶寬加載這條LSP。
2) 節(jié)點限制。節(jié)點限制包括編解碼類型限制和交換類型限制。其中編解碼類型限制是說在源節(jié)點和目的節(jié)點之間應(yīng)具有相同的編解碼類型，這種類型由目的節(jié)點確定，源節(jié)點與之相匹配。
3) 優(yōu)先權(quán)。優(yōu)先權(quán)包括建立優(yōu)先權(quán)和保持優(yōu)先權(quán)，即如果網(wǎng)絡(luò)中LSP存在優(yōu)先權(quán)問題則優(yōu)先權(quán)低的LSP在和優(yōu)先權(quán)高的LSP發(fā)生搶占資源的時候，應(yīng)首先滿足優(yōu)先權(quán)高的LSP的要求。
4) 路由類型。路由類型指的是顯示路由或者逐跳路由，其中顯示路由還包括嚴(yán)格顯示路由和松散顯示路由。
2.2 LINK的約束條件
1) 鏈路保留帶寬：鏈路保留帶寬即安全帶寬，當(dāng)鏈路加載某個LSP的時候，如果不能保證剩余10％的安全帶寬則認(rèn)為不能加載此LSP。
2) 鏈路限制：鏈路限制是因鏈路的具體狀況確定該鏈路的優(yōu)先級別，包括閑忙參數(shù)α和故障參數(shù)β。
3 算法的實現(xiàn)
CGR算法要求網(wǎng)絡(luò)上所有的節(jié)點都具有一張鄰接節(jié)點路由狀況表。有了狀況表，節(jié)點只要知道它到與它鄰接的節(jié)點的鏈路開銷，而不用獲得它到目標(biāo)節(jié)點的路徑開銷就可以繪制出一張恢復(fù)路由表。環(huán)路的問題在CGR算法中不予考慮，因為每個節(jié)點都具有整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而且CGR算法通過對節(jié)點是否已標(biāo)記來判斷選路的走向，根本不會出現(xiàn)環(huán)路現(xiàn)象。
節(jié)點的鄰接節(jié)點路由狀況表記錄的信息包括源節(jié)點地址，鄰接節(jié)點地址，鄰接節(jié)點開銷，鄰接鏈路狀況參數(shù)α 和β，以及節(jié)點參數(shù)τ 等5個部分。因此，如果節(jié)點A通過一條開銷為3的鏈路直接連接到節(jié)點B(不經(jīng)過中間節(jié)點)，并且路由器A通過一條開銷為5的鏈路直接連接到節(jié)點C，那么節(jié)點A將把將會向網(wǎng)絡(luò)上所有的節(jié)點廣播鏈路狀態(tài)包。每個節(jié)點將可以從接收到的鏈路狀態(tài)包中推算出一條通向目的節(jié)點的最短路徑。下面我們就來具體的講解一下CGR算法的實現(xiàn)過程。
3.1 CGR算法的建立
CGR算法的建立階段主要有以下幾部分組成：1) 建立鄰接節(jié)點路由狀況表。網(wǎng)絡(luò)中節(jié)點A通過發(fā)送Hello包到它的鄰接節(jié)點，獲得鄰接節(jié)點的地址、開銷、鏈路參數(shù)和節(jié)點參數(shù)等信息，建立了鄰接關(guān)系，所得到的信息都記錄在鄰接節(jié)點路由狀況表。2) 建立鏈路狀態(tài)數(shù)據(jù)庫。將本節(jié)點的數(shù)據(jù)收集起來，構(gòu)建鏈路狀態(tài)數(shù)據(jù)庫。節(jié)點間的數(shù)據(jù)發(fā)送和收集是通過泛洪(Flood)算法來完成的。3) CGR算法計算最優(yōu)路徑。CGR算法把某一節(jié)點(假設(shè)為節(jié)點A)設(shè)為源節(jié)點，初始狀態(tài)下通過鏈路狀態(tài)數(shù)據(jù)庫提供的信息進(jìn)行最優(yōu)路徑的計算；發(fā)生故障之后，通過更新后的鏈路狀態(tài)數(shù)據(jù)庫計算最佳恢復(fù)路徑。
3.2 算法的步驟 節(jié)點，其他節(jié)點均設(shè)為未標(biāo)記數(shù)n，鄰接節(jié)點開銷識節(jié)點中選擇一個進(jìn)行標(biāo)識的其中一個鄰接節(jié)點該節(jié)點和鄰接鏈路置斷
假設(shè)網(wǎng)絡(luò)中源節(jié)點為s，任意一點j都對應(yīng)兩個參量dj和pj。其中dj表示從源點s到點j的最優(yōu)路徑開銷；pj則是表示從s到j(luò)的最優(yōu)路徑中j點的前一節(jié)點。求解從源點s到網(wǎng)絡(luò)中任意點j的最優(yōu)路徑算法的基本過程如下：1) 初始化節(jié)點的開銷。源節(jié)點為0，其他所有節(jié)點為∞；標(biāo)記源點s，其它所有節(jié)點設(shè)為未標(biāo)記。2) 檢測是否滿足節(jié)點限制。檢驗該節(jié)點到其鄰接的未標(biāo)記節(jié)點的鏈路是否滿足節(jié)點限制。如果編解碼類型τ1和交換類型τ 2都滿足則置通過；如果僅不滿足τ1則可作為中間節(jié)點，不可作目的節(jié)點；如果τ 2不滿足則無論編解碼類型是否滿足都置為斷點，表示鏈路和節(jié)點均不可用。3) 檢測是否帶寬需求。檢驗所選鏈路是否滿足帶寬需求和鏈路保留帶寬需求。滿足則通過，跳到步驟5)，不滿足跳到步驟4)。4) 檢測優(yōu)先權(quán)。檢測LSP優(yōu)先權(quán)等級，如果高于已加載LSP，且斷開低等級LSP后，可成功加載高等級LSP則加載；否則置丟棄。5) 計算鄰接鏈路的CGR算法開銷。γ =γ×α (β=1) 或者γ =γ×β (β ≠1)。6) 選擇鏈路。比較鄰接鏈路的CGR算法開銷值，選取其中最小的一條進(jìn)行加載。如果有兩條或者以上開銷相同的鏈路，則選擇跳數(shù)最少的一條。7) 檢驗鏈路開銷。如果小于以前的CGR算法開銷則替代；大于則丟棄，如果相等，則選擇跳數(shù)少的路徑丟棄跳數(shù)多的。8) 找尋上一節(jié)點進(jìn)行標(biāo)記。如果步驟6)中替代了原有CGR算法開銷則找尋上一節(jié)點進(jìn)行標(biāo)記。9) 檢測算法是否完成。檢測是否所有節(jié)點都已標(biāo)記，如果都已標(biāo)記則算法完成；否則將步驟8中的上一節(jié)點轉(zhuǎn)到步驟2)繼續(xù)進(jìn)行計算。
在實現(xiàn)過程中需要配合鏈路狀態(tài)數(shù)據(jù)庫完成。此算法由于添加了故障參數(shù)和閑忙參數(shù)，因此可以在一定的程度上避開故障易發(fā)節(jié)點和鏈路，與其他恢復(fù)算法相比在網(wǎng)絡(luò)的生存性方面具有一定的優(yōu)勢。
圖1給出了CGR算發(fā)法的流程圖。