光通信網絡內的光路徑路由的製作方法
2023-10-26 11:37:42 6
專利名稱：光通信網絡內的光路徑路由的製作方法
技術領域：
本發明涉及光通信網絡內的光路徑路由，更具體地，涉及在具有有限再生和/或波長轉換的光網絡內的路徑路由。
光學光子技術的新近發展已經使全光網絡和全光交叉連接系統(OXC)的實現成為可能。儘管避免使用波長再生和波長轉換具有明顯的經濟優勢，但是全光網絡仍舊受到光路徑長度以及波長爭用的限制，光路徑長度以及波長爭用限定了節點之間的波長鏈路。為了降低網絡成本，在避免對路徑設備進行很複雜限制的同時，許多所謂的全光網絡都包括具有有限轉換/再生能力的OXC。因此，這些網絡就需要一種在對光路徑進行路由的同時能夠將網絡的阻塞概率減至最小的方法。
波長分配是一個必須要考慮到以下事實的問題，即如果通過某一數目的鏈路不能實現波長轉換，那麼可用的波長組就是在不同鏈路上可用的波長的交集。因此，如果一個波長在一個鏈路上空閒而在它所連接的鏈路上被佔據的話，那麼該波長即使在第一鏈路上也不能被使用。
路徑的可行性必須要考慮鏈路引入的所有物理限制，以確定在沒有再生時信號是否具有可以接受的質量。在沒有再生時，信號將會受到所有互連的鏈路引入的所有缺陷的影響。
在很多情形下，全光系統的這些限制會阻止電路的形成。為此，如上所述，優選地是在網絡節點處提供某種轉換和/或再生能力來實現「虛擬全光」網絡。但為了節約成本起見，這種有限的再生/轉換能力只能添加有限量。
由於這種能力是受限的(OXC可同時實現的轉換和/或再生的數目)，因此很顯然，重要的對這種能力加以最好地利用，即根據以下標準分配這種能力能使網絡進行良好工作，同時能將因在網絡節點處所述能力的耗盡所引起的網絡阻塞的機率降至最小。
因此，需要設法改進光路徑的路由，以將因有限的轉換和/或再生能力的耗盡而引起的網絡阻塞的機率降至最小。
本身來講，在傳輸網絡中電路的自動路由這個問題是眾所周知的，而且屬於網絡管理和網絡控制平面(ASTN和GMPLS)領域。
通常，這個問題用公知的路由算法(例如，如果整個網絡上的信息在單點處不可用時，用於集中計算的Dijkstra或Bellman-Ford)解決。然而，這些算法只能應用於那些旨在將路徑成本最低化的簡單度量。
發明內容
本發明的目標在於通過在具有有限的轉換和/或再生能力的光網絡內使光路徑路由方法可以使用，至少部分地改善上述缺點。
根據本發明，提供一種用於光網絡中的路徑的路由方法，該光網絡包括具有有限轉換和/或再生能力的節點，其中採用基於鏈路成本考慮的路由算法，並且包含轉換和/或再生成本的成本信息與這些節點相關聯，在所述路由算法中這種轉換和/或再生成本信息與其他用來計算路由的成本信息一起被考慮。
優選地，轉換和/或再生成本是動態函數，該動態函數指示在節點處進行轉換和/或再生操作的成本，假定該節點處有限轉換和/或再生能力的佔有量。
優選地，如下這樣的信息與這些節點相關聯，這些信息對每個節點而言都代表著在從節點退回到原點並在執行轉換的第一個節點上終止的所有鏈路上空閒的波長組。
優選地，如下這樣的信息與這些節點相關聯，這些信息對每個節點而言都代表著信號的質量，並聚積了由從節點退回到原點的節點並且在執行轉換的第一個節點上終止的所有鏈路所引入的損害。
優選地，有關從原點到節點的路由成本的信息與每個節點相關聯，如果路徑需要轉換到從原點到節點之間的某個節點時，所述成本信息包括轉換的成本。
所述算法優選地包括Dijkstra算法或Bellman-Ford算法。
在本發明方法的一種優選實施方式中，這些節點與以下信息相關聯
-與wlset表示的波長組有關的信息，這些波長在從節點退回到原點並在實現轉換的第一個節點上終止的所有鏈路上空閒；-以sq向量的形式、並代表著信號的質量以及聚積了由從節點退回到原點節點並在執行轉換的第一個節點上終止的所有鏈路所引入的限制的信息；在逐漸考慮所有未用公式表示的v個節點以將成本分配給路由的這種路由算法的迭代中，對於每個鏈路，從所考慮的v節點到未用公式表示的w節點，證實-wlset(v)∩wlset(v，w)是空組，-sq(v)+sq(v，w)＜baresq，其中baresq表示最小可接受的信號質量，如果上述兩個條件之一被證實，那麼將節點v處轉換和/或再生的成本增加到迭代時利用的成本中。
為使本發明及其優點與現有技術相比可以被更好地理解，下面藉助於應用本發明原理的非限定性實例描述一個可能的實施例。
如上所述，本發明可以應用於具有特定數目的節點和本身是已知類型鏈路的光網絡，以及本領域技術人員很容易想到，本發明可以應用於只具有有限的轉換和/或再生能力的一些節點的光網絡。
為了在數據網絡中實現電路的路由，不僅需要決定節點列表以及要連接的鏈路，而且還需要決定如果執行轉換和/或再生，在哪裡執行轉換和/或再生，以及在各個全光區段(即那些不執行轉換和/或再生的區段)中使用哪個波長。而且，在出現多個路由可能性的情形中，必須在具有不同轉換配置的不同路由之間做出選擇。這意味著成本的標準化(normalization)，允許在具有轉換和不具有轉換的路線之間進行成本比較。
需要考慮的度量(metric)包括每個鏈路還記錄所使用的可用波長組，以在可能的全光區段中估計組的交集。
每個鏈路還記錄它引入的物理光損害。考慮到可能彼此獨立的多個參數，這些度量會相當複雜，但是對所屬領域技術人員而言是容易想到的。因此，這裡不再詳細描述這些度量。這裡僅假設光學參數的向量，存在專門求和運算以聚積通過多個鏈路的效應，以及對於給定向量指示光路徑是否滿足可行性標準的布爾函數。這些參數的例子可以是光信噪比(OSNR)，色散，偏振模色散模(PMD)以及其他。
由于波長轉換事實上也意味著信號的再生，而且從另一方面講，在本申請中再生可以被看作是到相同起始波長的波長轉換，因此，在本申請中術語「轉換」和「轉換/再生」或「再生」可以交換使用。
在確定轉換成本之後，一旦認為路徑上的轉換是必需的(因為在鏈路鏈上缺少可用的波長，或者因為物理損害而使路徑不可行)，在路徑的總成本中還必須考慮轉換成本。轉換成本是一個參數，該參數可以為了路由算法的最優性能而進行調節。由於轉換能力是有限的，因此轉換成本應當很高，其高得足以阻止轉換。與此同時，在某些情形下，優選地是某些鏈路因一些原因應當被取消，這是由於它們的成本比得上轉換的成本，也就是說，轉換的成本不應當比鏈路的成本高得不能比較。
舉例來說，在傳輸網絡的範圍中，如果一個鏈路裝填得接近它的最大容量，那麼該鏈路應當避免給未來的電路留下空間，這些電路沒有替代的路由。按照「交通工程」策略，動態的成本可以分配給鏈路，當鏈路的佔有提高時動態成本變得更高。模擬顯示，這種策略會導致阻塞狀況明顯推遲。
類似的策略也可以應用到轉換上。在這種情形下，動態成本函數與轉換相關聯，轉換成本隨著單元轉換能力的利用而提高。這樣，例如，如果用相似的成本可以實現兩個相當的路由，那麼該算法將優先選擇在更自由的轉換單元上實現轉換的路由。
從下面的實例可以看出，交通工程的考慮也可以應用到波長選擇上。
路由算法通常被定義為是一種在圖表中找出路線的方法。具體地，路由算法的輸入數據通常採用圖表的形式，G＝(V，E)，其中V是頂點(或節點)的組，E是邊緣(或鏈路)的組。在下面，術語節點、頂點、邊緣以及鏈路將用作同義詞。
成本函數cE-N將在數目N中映射鏈路E，以將成本值分配給每個鏈路。這樣做的含義是給鏈路分配優先選擇的可能性，以選擇(favour)一些線路而不是其他線路。
另外的輸入是原始節點和目的節點對，即將兩個節點與線路連接的請求。
可以採用各種路由算法。作為舉例的方式，簡單提及一下著名的Dijkstra算法，這種算法被認為是已知最好的路由算法。用下面的偽碼描述這種眾所周知的算法。
INITassociate cost and pred values with each vertexset cost(origin)＝0 and cost(v)＝∞ for any other vertex vmark all vertices unprocessedITERATIONselect the unprocessed vertex v having minimum costfor each link(v，w)to an unprocessed vertex w，doif cost(v)+c(v，w)＜cost(w)thenset cost(w)＝cost(v)+c(v，w)set pred(w)＝vendifmark v processedITERATION繼續進行直到所有的節點都被處理。
在迭代結束時，Cost(destination)包含了所發現路由的成本。這個線路還可以從目的地開始經過pred(destination)，pred(pred(destination))等向後進行到原始節點。
為了更實際地使用這種算法，可以增加交通工程的考慮。為此，另外一種能力E-N函數在N圖形(figure)內映射E個鏈路，該N圖形表示鏈路所支持的帶寬。「請求容量」圖形也增加到電路請求中，並且當電路被建立時，它的容量(capacity)被記錄在它相互連接的鏈路上，以記錄鏈路上佔據的且自由的帶寬。當自由(可用)帶寬減小時，動態的成本函數可以替代靜態的函數來加以使用，以施加提高的成本。
基於與Dijkstra算法相同數據結構的其他算法也都是眾所周知的，因而本發明可以直接應用到其上。實際上，由於本發明涉及的是具體的數據結構、信息以及比較成本的方式，而不是特定的算法，因此本發明可以很容易地應用到這些其他算法。特別地，已經發現，將本發明應用到公知的Bellman-Ford算法是很有利的。
基於簡化和清楚的原因，下面參考為Dijkstra算法而上面描述的偽碼，雖然本發明的原理與特定的算法不相關聯。對所屬領域的技術人員而言，不需要任何其他信息或描述，就可以從下面的描述直接推導出對Belmann-Ford算法的應用。
如上所述，在包含具有有限轉換和/或再生能力的節點的網絡中，在計算路由時，算法都被修改以容許這些有限能力的存在(這些有限能力的使用包括網絡的「成本」)。
根據本發明，包括轉換和/或再生成本的成本信息與節點相關聯。在路由算法中，這種轉換和/或再生成本信息要與其他用來計算路由的成本信息一起考慮。
有利的是，轉換和/或再生成本是一個動態成本函數(convcost)，它表示在節點上進行的轉換操作的成本，假定轉換單元的佔有。
因而，在每個節點上保持的成本信息就是一個成本，這個成本代表著從原點到節點這個路由的成本(例如，在上述的常規Dijkstra算法中)。與已知的成本不同，如果路徑在某個節點處需要從原點到這個節點的轉換時，這個成本還包括轉換的成本。
有關可用波長組的信息還與每個節點相關聯。所述組(在下面指定為wlset)表示的是在從這個節點向後到原點、並在執行轉換的第一個節點處終止的所有鏈路上空閒的波長。由於W是網絡中所使用的所有波長的組，因此如果v是原點或執行轉換的節點，那麼路徑開始於wlset(v)＝W。
還存在表示信號質量的信息(採用向量的形式，在下面指定為sq)，其聚積了從節點向後到原點節點、並在執行轉換的第一節點處終止的所有鏈路所引入的損害。從作為原點或執行轉換和/或再生的節點的節點v開始，信號就作為新的信號以launchsqsq(v)＝launchsq表示的圖形開始。另外，為了滿足可行性標準，信號的質量不必比特定值baresq差，為了簡化符號，將寫入sq(v)＜baresq，其中比較符「＜」表示復向量的可能比較。
如上所述，除了已知的數據和信息結構外，依照本發明的原理，下面的其他信息和其他數據結構同樣可以使用-網絡中使用的所有波長的組W；-用於每個鏈路的可用波長組；-每個鏈路使用的波長組；-鏈路引入的物理損害的向量；-用於每個節點的轉換容量值；-用於轉換單元的佔有值(occupation value)；以及-用於每個波長「fabric」的佔有值。
可用以及使用的波長還說明了鏈路的容量。自由波長的數目被用來計算鏈路的動態成本。
應用本發明上述的原理，為Dijkstra算法而給出的上面偽碼變成(方便起見，增加的部分用下劃線標出)INITassociate cost，pred，wlset，wlset，andsqwith each vertexset cost(origin)＝0 and cost(v)＝∞ for any other vertex vset wlset(origin)＝Wset sq(origin)＝launchsqmark all vertices unprocessedset conv(v)＝falsc for each vITERATIONselect the unprocessed vertex v with minimum costfor each link(v，w)to an unprocessed vertex w，dosetconversion＝0(where conversion is a local variable)if wlset(v)∩wlset(v，w)＝empty then set conversion＝convcoost(v)if sq(v)+sq(v，w)＜baresq then set conversion＝convcost(v)if cost(v)+c(v，w)+conversion＜cost(w)thenset cost(w)＝cost(v)+c(v，w)+conversionset pred(w)＝vif conversion is not equal to 0 then set conv(W)＝trueendifmark v as processed
ITERATION繼續進行直到所有的節點都被處理。
在節點處，變量pred指的是計算路由中的前一個節點，布爾變量conv表示前一個節點是否執行轉換。
通過解釋的方式，這裡描述一種目前存在於網絡節點中的已知光交叉連接(OXC)的可能結構。如果希望使用「全光」技術，那麼這種OXC通常會包括一組波分復用(WDM)接口，光多路復用器將WDM光纖暴露於網絡(光纖對應於網絡鏈路)，並將單個波長暴露給執行鏈路的光矩陣(光學織物)。光矩陣被假設是「不阻塞的」，也就是說，來自於任何接口的任何波長都可以移動到與其他任何接口相同的波長處。
為了在該取網絡時能夠選擇波長，將一個波長選擇模塊放置在支流部分與光矩陣之間。
節點的光矩陣可以依據眾所周知的技術考慮在單獨平面上實現，每個波長實現一個。這不會導致這裡所述方法喪失普遍性，因為缺少波長轉換仍然能使波長保持分開。
為了彌補光矩陣不具有波長轉換和/或再生能力的事實，將公知的轉換和/或再生單元插入OXC中，以實現虛擬的全光節點。例如，根據現有技術，可以用電學開關或光開關實現轉換和/或再生單元，該電學開關或光開關在每個存取接口(OEOEO)上具有應答器。這些單元也可以在附屬接口上實現選擇功能。
因此，具有某個波長的平面就被認為包括透明的無阻塞光開關、到光多路復用器的多個通道(access)、一個網絡鏈路以及到轉換和/或再生單元的較少數目通道。
很顯然，可以有不同的轉換機會，因為每個波長平面都具有到轉換單元的某些存取接口。如上所述，交通工程的考慮也可以應用到波長的選擇上。
舉例來說，假設λ1和λ2對需要轉換的入口路徑都是空閒的。還假設在沒有轉換的情況下λ1光學織物已經充滿轉接鏈路，而λ2光學織物是空的。非常可能的是，未來的需求將要求轉換單元進行λ2存取，而不太可能出現對λ1的另一個請求。因此，在轉換節點處選擇波長所依據的標準應當是選擇更完整的波長平面。這個策略可以毫不費力地進行概括，因為對所屬領域技術人員而言不需要額外描述就可以很容易地想到。
對於在沒有路由轉換所發現的每一段，如果在該段中可以利用更多的波長，那麼有利地是，可以選擇光矩陣平面的頻率在該段的兩個端節點處都被完全佔據的那個波長。
容易證實，運用本發明方法所修改的Dijkstra算法能夠容許將路由成本分配給各個節點，從而能夠允許選擇更低的總成本(路徑成本以及轉換和/或再生資源的使用成本)。
現在，清楚的是，通過使適用於各種已知路由算法的路由方法變得可以使用，從而能夠在網絡中存在有限轉換和/或再生能力時使路由最優化，可以實現本發明設定的目的。
很顯然，在所附權利要求書專利權的範圍內，上面對應用本發明創新原理的實施例的描述通過所述原理的非限制性示例給出。
權利要求
1.用於在光網絡中的路徑的路由方法，該光網絡包括具有有限轉換和/或再生能力的節點，在該路由方法中，採用基於鏈路成本考慮的路由算法，並且包含轉換和/或再生成本的成本信息與這些節點相關聯，在所述路由算法中這種轉換和/或再生成本信息與其他用來計算路由的成本信息一起被考慮。
2.依照權利要求1的方法，其中轉換和/或再生的成本是動態函數，該動態函數指示在節點處進行轉換和/或再生操作的成本，假定該節點處有限轉換和/或再生能力的佔有量。
3.依照權利要求1的方法，其中如下這樣的信息與這些節點相關聯，這些信息對每個節點而言都代表著在從節點退回到原點並在執行轉換的第一個節點上終止的所有鏈路上空閒的波長組。
4.依照權利要求1的方法，其中如下這樣的信息與這些節點相關聯，這些信息對每個節點而言都代表著信號的質量，並聚積了由從節點退回到原點的節點並在執行轉換的第一個節點上終止的所有鏈路所引入的損害。
5.依照權利要求1的方法，其中有關從原點到節點的路由成本的信息與每個節點相關聯，如果路徑需要轉換到從原點到節點之間的某個節點時，所述成本信息包括轉換的成本。
6.依照權利要求1的方法，其中所述算法是Dijkstra算法。
7.依照權利要求1的方法，其中所述算法是Bellman-Ford算法。
8.依照權利要求1的方法，其中這些節點與以下信息相關聯-與wlset表示的波長組有關的信息，這些波長在從節點退回到原點並在實現轉換的第一個節點上終止的所有鏈路上空閒；-以sq向量的形式、並代表著信號的質量以及聚積了由從節點退回到原點的節點並在執行轉換的第一個節點上終止的所有鏈路所引入的限制的信息；以及在逐漸考慮所有未用公式表示的v個節點以將成本分配給路由的這種路由算法的迭代中，對於每個鏈路，從所考慮的v節點到未用公式表示的w節點，證實-wlset(v)∩wlset(v，w)是空組，以及-sq(v)+sq(v，w)＜baresq，其中baresq表示最小可接受的信號質量，如果上述兩個條件之一被證實，那麼將節點v處轉換和/或再生的成本增加到迭代時利用的成本中。
全文摘要
用於在光網絡中的路徑的路由方法，該光網絡包括具有有限轉換和/或再生能力的節點，在該路由方法中，採用基於鏈路成本考慮的路由算法，並且包含轉換和/或再生成本的成本信息與這些節點相關聯。這種轉換和/或再生成本信息與其他用來計算路由的成本信息一起被考慮。
文檔編號H04L12/56GK101095320SQ200580045714
公開日2007年12月26日 申請日期2005年10月31日 優先權日2004年11月2日
發明者G·費亞, D·卡維利亞 申請人:愛立信股份有限公司