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

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

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