[發(fā)明專利]一種路由波長(zhǎng)分配方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201210042038.6
• 申請(qǐng)日: 2012-02-23
• 公開（公告）號(hào): CN102546440A
• 公開（公告）日: 2012-07-04
• 發(fā)明（設(shè)計(jì)）人: 曹徐平;王家昱;張杰;黃善國(guó)
• 申請(qǐng)（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號(hào): H04L12/56
• 分類號(hào): H04L12/56;H04Q11/00
• 代理公司: 北京派特恩知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11270
• 代理人: 周義剛;張穎玲

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，特別是指一種路由波長(zhǎng)分配方法和系統(tǒng)。

背景技術(shù)

K條最短路徑算法(KSP，K-shortest?Path?Algorithm)算法是一種解決在網(wǎng)絡(luò)拓?fù)渲蝎@得指定的源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條路徑問題的算法，通過該算法可以在網(wǎng)絡(luò)拓?fù)渲蝎@得路徑權(quán)重和由小到大排序的K條路徑。KSP算法作為一種很實(shí)用的算法，被廣泛應(yīng)用到交通運(yùn)輸、通信路由計(jì)算、人工智能、經(jīng)濟(jì)理論研究、數(shù)學(xué)應(yīng)用等領(lǐng)域，具備很高的應(yīng)用價(jià)值，并能夠給使用者帶來(lái)巨大的經(jīng)濟(jì)利益。長(zhǎng)期以來(lái)，國(guó)內(nèi)外學(xué)術(shù)界對(duì)KSP算法都進(jìn)行了廣泛、深入的研究，旨在改善和提高算法的效率，盡可能減少算法的時(shí)間與空間復(fù)雜度，先后涌現(xiàn)了諸多的K優(yōu)路徑算法。

1966年Roth提出的D算法，可以認(rèn)為是拓?fù)浣Y(jié)構(gòu)測(cè)試中最經(jīng)典的方法，也是最早實(shí)現(xiàn)自動(dòng)化的測(cè)試生成算法之一。它是完備的測(cè)試算法，可以檢測(cè)非冗余電路中所有可以檢測(cè)的故障。雖然D算法是在20世紀(jì)60年代提出的，而且被修正過多次，但是，許多新的測(cè)試方法都是在它的基礎(chǔ)上發(fā)展起來(lái)的，而且一直沿用至今。

近年來(lái)，隨著光傳送網(wǎng)波長(zhǎng)交換光網(wǎng)絡(luò)(WSON，Wavelength?Switched?Optical?Network)技術(shù)的迅猛發(fā)展，KSP算法和D算法正被越來(lái)越多地應(yīng)用到解決路由波長(zhǎng)分配(RWA，Route?Wavelength?Assignment)算法的路由問題中來(lái)。由于RWA算法本身具有非確定型多項(xiàng)式的特征，其所包含的路由的R過程和波長(zhǎng)分配的WA過程要分為兩步實(shí)現(xiàn)。目前的(WSON)傳送網(wǎng)的WA波長(zhǎng)分配過程，往往不是全波長(zhǎng)交換的，由于面臨傳送節(jié)點(diǎn)有阻交叉約束的限制，需要在路由的計(jì)算過程中，提供K條可替代路由，以防止在選定路由上波長(zhǎng)分配失敗后提供可替換的路由以進(jìn)行再次的波長(zhǎng)分配過程。

以往的針對(duì)網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)之間具有多條光纖鏈路的網(wǎng)絡(luò)狀況下，已經(jīng)存在某些針對(duì)路由和波長(zhǎng)分配的方案，比如可以采用在兩個(gè)相鄰節(jié)點(diǎn)間增加多個(gè)虛節(jié)點(diǎn)的方式，來(lái)區(qū)分原本存在于兩個(gè)相鄰節(jié)點(diǎn)間的多條光纖鏈路，這樣的改動(dòng)可以適應(yīng)現(xiàn)存的算路算法，如D算法和KSP算法。上述方法的確可以解決節(jié)點(diǎn)間多鏈路的選路問題，但是伴隨而來(lái)的問題仍不可小視。由于現(xiàn)在的網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模逐漸擴(kuò)大，節(jié)點(diǎn)間鏈路的數(shù)目也逐漸增多，在這樣的網(wǎng)絡(luò)環(huán)境中，如果仍然通過增加虛節(jié)點(diǎn)的方式來(lái)解決上述問題，就會(huì)使現(xiàn)有的網(wǎng)絡(luò)鏈路數(shù)目規(guī)模和節(jié)點(diǎn)數(shù)目規(guī)模都有很大幅度的增加，使得算路過程變得相當(dāng)復(fù)雜，消耗時(shí)間規(guī)模特別大。雖然運(yùn)用這種方法能夠算出最理想的路由，但是隨之付出的時(shí)間代價(jià)和計(jì)算代價(jià)太大。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明的主要目的在于提供一種路由波長(zhǎng)分配方法和系統(tǒng)，以解決現(xiàn)實(shí)網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)間擁有多條光纖鏈路的路由和波長(zhǎng)分配問題。

為達(dá)到上述目的，本發(fā)明的技術(shù)方案是這樣實(shí)現(xiàn)的：

一種路由波長(zhǎng)分配方法，根據(jù)節(jié)點(diǎn)間多鏈路的網(wǎng)絡(luò)拓?fù)洌A(yù)先存儲(chǔ)并更新相鄰節(jié)點(diǎn)間光纖鏈路和波長(zhǎng)的占用信息，該方法還包括：

將節(jié)點(diǎn)間多鏈路的網(wǎng)絡(luò)拓?fù)涑橄鬄楣?jié)點(diǎn)間單鏈路的網(wǎng)絡(luò)拓?fù)洌?/p>

基于所述節(jié)點(diǎn)間單鏈路網(wǎng)絡(luò)拓?fù)洌捎寐酚伤惴ù_定從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由；

通過信令從所述路由的源節(jié)點(diǎn)開始逐跳遍歷到目的節(jié)點(diǎn)，獲取對(duì)應(yīng)的多個(gè)所述占用信息；并依據(jù)獲取的多個(gè)占用信息，確定承載業(yè)務(wù)需要預(yù)留的波長(zhǎng)；

通過信令從所述路由的目的節(jié)點(diǎn)開始逐跳遍歷到源節(jié)點(diǎn)，獲取對(duì)應(yīng)的多個(gè)所述占用信息，并依據(jù)獲取的多個(gè)占用信息和需要預(yù)留的波長(zhǎng)，從目的節(jié)點(diǎn)到源節(jié)點(diǎn)、依次選擇所述路由上相鄰節(jié)點(diǎn)間承載業(yè)務(wù)的光纖鏈路；在選擇的光纖鏈路上進(jìn)行波長(zhǎng)預(yù)留。

其中，所述相鄰節(jié)點(diǎn)間光纖鏈路和波長(zhǎng)的占用信息包含：相鄰節(jié)點(diǎn)間各波長(zhǎng)在各光纖鏈路上的可用信息、相鄰節(jié)點(diǎn)間所有光纖鏈路上各波長(zhǎng)可用數(shù)目和所有光纖鏈路上各波長(zhǎng)總體可用信息；所述可用信息包括可用或不可用。

其中，所述確定的從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由的信息包括：所述路由中從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的每一跳節(jié)點(diǎn)的信息。

其中，所述依據(jù)獲取的多個(gè)占用信息，確定承載業(yè)務(wù)需要預(yù)留的波長(zhǎng)，為：對(duì)獲取的多個(gè)占用信息中的、各光纖鏈路上各波長(zhǎng)總體可用信息取交集，獲得在整個(gè)所述路由上可用的波長(zhǎng)集；并采用波長(zhǎng)分配算法從所述波長(zhǎng)集中選定需要預(yù)留的波長(zhǎng)；所述波長(zhǎng)分配算法包括FF或RF算法。