獲得智能光網絡中鬆散路由的約束路徑的方法和裝置的製作方法
2023-04-27 01:07:16 1
專利名稱：獲得智能光網絡中鬆散路由的約束路徑的方法和裝置的製作方法
技術領域：
本發明涉及智能光網絡，具體涉及獲得智能光網絡中鬆散路由的約束路徑的方法和裝置。
背景技術：
光網絡，包括SDH/Sonet、波長網絡，傳統上是一種基於集中管理的系統。光網絡節點通常是「啞」的，光連接的創建、維護、拆除都需要人工幹預，這種方式建立的光連接稱為永久連接。這種光網絡系統不能滿足數據業務的不斷增長、動態和靈活的需求，解決這個問題的關鍵是動態光交換。ITU的自動交換光網絡(ASON)架構給傳統上的光網絡上增加了一個控制平面光網絡節點首先通過鏈路局部的發現技術獲得本網絡節點與其他光網絡節點的連接關係；再通過控制平面發布其節點和鏈路狀態，並接收網絡中其他網絡節點的狀態發布，最終每個光網絡節點都有一份描述網絡精確拓撲的「網絡地圖」，其中包括節點、鏈路、資源信息；光網絡節點被客戶設備或管理系統要求建立連接時，利用「網絡地圖」的信息，結合一定的路由算法得到一條可行的路徑，再通過信令協議驅動路徑上的節點建立交叉連接，直到目的節點完成光連接的動態建立；在網絡連接動態建立、拆除，或者故障引起鏈路資源變化時相應光網絡節點需要及時發布更新的節點、鏈路狀態信息，實現「網絡地圖」的再同步。
在目前的路徑計算方法中主要使用的是帶約束的最短路徑優先算法(CSPF算法)。主要約束包括帶寬、鏈路保護類型、禁止節點、禁止鏈路。CSPF算法實現如下CSPF算法使用兩個名為PATHS(路徑)和TENT(嘗試路徑)的資料庫。PATHS中保存了最短路徑樹的信息，而TENT中包含了在找到最短路徑之前的嘗試節點的信息。僅當找到了到達一個節點的最短路徑時，該節點才會放入PATHS資料庫中。
CSPF算法計算的步驟如下1.將參加計算的節點放入PATHS中(表示沒有比到它自身更短的路徑存在)，TENT中預先放入計算節點的鄰居節點。
2.當一個節點被放入PATHS時，檢查該節點到各個鄰居節點的鏈路，對鏈路的屬性與約束條件進行匹配，並對鄰居節點進行約束條件的匹配。如果約束匹配成功，則如果鄰居已經存在於PATHS中，表示新路徑是一條較長的路徑，這時忽略新路徑；如果鄰居存在於TENT中，並且新路徑更短，則用新路徑代替老路徑。如果新路徑和TENT中的路徑同樣長，則鄰居有等價的路徑。如果鄰居節點不在TENT中，則在將節點移到TENT之前，裁減不滿足LSP約束條件的鏈路和節點，並把滿足LSP約束條件的鏈路對應節點放入TENT。
3.將TENT中有最小代價的節點放入PATHS中。
4.當TENT為空時或者TENT中有最小代價的節點是目的節點，路由計算結束，輸出計算結果；否則，跳轉到步驟2。
在現有技術中，鬆散路由約束的實現是通過MPLS(多協議標籤交換)信令與CSPF算法結合完成的。主要實現方法是在鬆散路由的各個節點上多次進行CSPF計算完成。具體實現如下
1、在源節點設備上，以源節點為源節點、鬆散節點1作為目的節點利用CSPF算法計算路徑。如果計算成功，利用信令把這些路徑節點發送到鬆散節點1；2、鬆散節點1收到上個節點計算的路徑信息，把這些路徑上的節點作為排除計算節點，把本節點作為源節點，鬆散節點2作為目的節點進行CSPF路徑計算。如果計算成功，利用信令把這些路徑節點發送到鬆散節點3；3、鬆散節點N收到上個節點計算的路徑信息，把這些路徑上的節點作為排除計算節點，把本節點作為源節點，鬆散節點N+1作為目的節點進行CSPF路徑計算。如果計算成功，利用信令把這些路徑節點發送到鬆散節點N+1；4、直到信令達到最後的目的節點，完成整個路徑的計算。再向上遊節點返回信令，直到源節點。
圖1為有鬆散路由約束的網絡拓撲示意圖；本說明書將結合該示意圖描繪現有技術與本發明的實施例中實現獲得智能光網絡中鬆散路由的約束路徑的方法。
在該網絡中，路徑建立的要求是源節點是1，目的節點是10，鬆散路由約束是節點5、節點6，也就是說路徑必須順序經過節點5、節點6。
按照上述方法，建立過程為1)在源節點1進行計算路徑，計算從節點1到節點5的路徑。經過計算，最短路徑是{1，4，3，5}。
2)節點1的MPLS會發送PATH信令到下一跳節點4，在PATH信令中會攜帶路徑信息{1，4，3，5}、鬆散節點信息{5，6}、及目的節點信息{10}；節點4也會發送PATH消息到節點3，節點3也會發送PATH消息到節點5。
3)信令到達節點5，節點5發現沒有下一跳路徑可選，便計算源節點是5，目的節點是6的路徑(並排除路徑上的節點)。計算成功，路徑是{5，6}。如果計算失敗則向上遊節點3返回錯誤信令。
4)計算成功後，節點5把PATH信令發送到下一跳節點6，在PATH信令中會攜帶路徑信息{1，4，3，5，6}、鬆散節點信息{5，6}、及目的節點信息{10}。
5)信令到達節點6，節點6發現沒有下一跳路徑可選，便計算源節點是6，目的節點是10的路徑(並排除路徑上的節點)。計算成功，路徑是{6，9，8，10}。如果計算失敗則向上遊節點5返回錯誤信令。
6)計算成功後，節點6把PATH信令發送到下一跳節點9，在PATH信令中會攜帶路徑信息{1，4，3，5，6，9，8，10}、鬆散節點信息{5，6}、及目的節點信息{10}。
信令最後到達節點10，從節點10沿原路徑返回RESV(預留)信令，到達源節點1。LSP建立成功。
這個方法在源節點和各個鬆散節點分別計算路徑，在源節點處，如果沒有收到目標節點返回的信令，是不能知道能否成功到達目的節點路徑。因此需要與MPLS信令結合，在各個鬆散節點進行多次計算。而且在源節點和中間節點上是不能立即知道帶鬆散約束的LSP能否建立成功，需要等待返回信令，才能知道成功與否。
發明內容
本發明的目的是針對上述現有技術的缺點，提供一種獲得智能光網絡中鬆散路由的約束路徑的方法和裝置，用於針對鬆散路由約束，在源節點只需要計算一次，就能知道到目的節點能否找到一條符合鬆散路由約束的路徑。
本發明提供一種獲得智能光網絡中鬆散路由的約束路徑的方法，包括步驟獲得所述約束路徑的順序鬆散節點和源節點與目的節點；獲取所述網絡的拓撲結構；將所述源節點為起始節點，所述鬆散節點中的目前排序第一順序的鬆散節點為目的節點，利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑；以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點；以所述最後一個鬆散節點作為起始節點，所述目的節點作為目的節點，使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑；合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
可選地，所述獲取所述網絡的拓撲結構的步驟包括如果網絡路由為域內路由，所述源節點通過域內路由協議獲取所述網絡的拓撲結構；如果網絡路由包括域間路由，所述源節點通過域內路由協議與多域路由獲取所述網絡的拓撲結構。
優選地，所述利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑的步驟包括禁止所有其它鬆散節點。
可選地，所述使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑的步驟包括禁止已計算的路徑中的節點和還沒有參加計算的鬆散節點。
優選地，所述使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑的步驟還包括，禁止已計算的路徑中的節點。
可選地，所述以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點的步驟包括判斷是否存在下一個鬆散節點，如果存在，設定目前排序第一鬆散節點為起始節點，所述存在的下一個鬆散節點為目的節點；如果不存在，結束該步驟。
優選地，方法還包括步驟判斷所述路徑是否有約束鬆散節點，如果有，執行所述方法的步驟，如果沒有，直接利用CSPF算法獲取路徑。
可選地，方法還包括步驟判斷所述約束路徑的鬆散節點是否有順序，如果有，執行所述方法的步驟，如果沒有，利用其它方法獲取路徑。
優選地，方法還包括步驟通告MPLS完整的路徑信息；MPLS得到完整的路徑信息後，通過所述完整的路徑發送PATH消息，再返回RESV消息，如果資源預留成功，建立了所述路徑。
本發明還提供一種獲得智能光網絡中鬆散路由的約束路徑的裝置，包括
獲取裝置，位於源節點中，用於獲得所述約束路徑的順序鬆散節點和源節點與目的節點；和獲取所述網絡的拓撲結構；計算與控制裝置，用於將所述源節點為起始節點，所述鬆散節點中的目前排序第一順序的鬆散節點為目的節點，利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑；以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點；以所述最後一個鬆散節點作為起始節點，所述目的節點作為目的節點，使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑；路徑合併裝置，用於合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
可選地，所述計算與控制裝置還包括判斷裝置，用於判斷是否所有鬆散節點計算完畢。
利用本發明，實現了針對鬆散路由約束高效建立符合鬆散路由約束的路徑。利用本發明在源節點就能確定符合約束的路由是否能有，而不需要在各個鬆散節點分別進行計算確定路徑。提高了網絡效率，減少了對節點的處理能力的要求。
圖1為有鬆散路由約束的網絡拓撲示意圖，這是一個MESH(網格)網絡，鏈路是雙向的帶權圖，鏈路上的數值為權值；圖2示出了本發明實施例的獲得智能光網絡中鬆散路由的約束路徑的方法的流程圖。
具體實施例方式
為了便於本領域一般技術人員理解和實現本發明，現結合附圖描繪本發明的實施例。
圖2示出了本發明實施例的獲得智能光網絡中鬆散路由的約束路徑的方法的流程圖。本發明利用在源節點通過多次的CSPF計算來實現鬆散路由約束，以獲得建立網絡的路徑；其中，CSPF計算的次數與鬆散節點的數目有關。在本發明中，要求給出的鬆散節點是順序的，也就是說在給出的鬆散節點是在最終的路徑中是要順序經過的。本發明的方法的過程如下在開始建立網絡路徑時，首先在步驟10，設置所有鬆散節點禁止；然後在步驟15，初始化鬆散節點變量；在步驟20，設定源節點為起始節點。
在步驟25，判斷是否還存在鬆散節點未處理，如果還有，在步驟30，將鬆散節點1作為設定目的節點，然後在步驟35，使用CSPF算法計算路徑，保存結果，並在該次計算中禁止已計算的路徑中的節點和還沒有參加計算的鬆散節點，也就是排除這些節點；然後，在步驟40，將鬆散節點1作為源節點；並在步驟45，改變鬆散節點變量，這裡，將該變量加1；返回步驟25；如果沒有，在步驟50，將目的節點作為設定目的節點，然後在步驟55，使用CSPF算法計算路徑，保存結果；
然後，在步驟60，將所有獲得的路徑合併。方法結束。
換言之，該方法包括下面的過程1)首先，需要在給出的鬆散節點是順序的。也就是說在給出的鬆散節點是在最終的路徑中是要順序經過的；2)將源節點為起始節點，鬆散節點1作為目的節點，使用CSPF算法計算路徑，並在該次計算中禁止其他鬆散節點，也就是排除其他節點；3)再將鬆散節點1作為起始節點，鬆散節點2作為目的節點，使用CSPF算法計算路徑，並在此次計算中禁止先前計算的路徑中的節點和還沒有參加計算的鬆散節點；4)再將鬆散節點n作為起始節點，鬆散節點n+1作為目的節點，使用CSPF算法計算路徑，並在此次計算中禁止先前計算的路徑中的節點和還沒有參加計算的鬆散節點；5)最後將再將最後一個鬆散節點作為起始節點，目的節點作為目的節點，使用CSPF算法計算路徑，並在此次計算中禁止先前計算的路徑中的節點；6)合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
在本發明的實施例中，需要注意的是1)鬆散路由約束的定義必須節點是有順序的，也就是說在給出的鬆散節點是在最終的路徑中是要順序經過的。本發明對無序的鬆散約束是不適用的。
2)在本發明的方法使用的CSPF算法必須實現禁止節點約束，因為算法是需要使用到禁止節點約束的，即上文中提到的禁止先前計算的路徑中的節點和還沒有參加計算的鬆散節點。
3)在實際應用中需要判斷計算請求中是否攜帶鬆散約束，如果有則可使用本發明的方法，如果沒有則只需要CSPF算法就可以了。
現以圖1的網絡拓撲為例描繪在圖1的網絡拓撲中如何實現本發明。其中，在該實施例中，路徑建立的要求是源節點是1，目的節點是10，鬆散路由約束是節點5、節點6，也就是說路徑必須順序經過節點5、節點6。
獲得網絡路徑的方法包括以下步驟1)在源節點進行路由計算。首先以節點1作為源節點，鬆散節點5作為目的節點進行路徑計算。計算成功，路徑為{1，4，3，5}；如果計算失敗，在節點1就能知道要求的LSP是不能建立的。
2)再以節點5作為源節點，鬆散節點6作為目的節點，進行路徑計算。計算成功，路徑為{5，6}；如果計算失敗，在節點1就能知道要求的LSP是不能建立的。
3)再以節點6作為源節點，目的節點10作為目的節點，進行路徑計算。計算成功，路徑為{6，9，8，10}；如果計算失敗，在節點1就能知道要求的LSP是不能建立的。
4)合併路徑信息。完整的路徑信息就為{1，4，3，5，6，9，8，10}。通告MPLS完整的路徑信息。
5)MPLS得到完整的路徑信息後，就逐跳發送PATH消息1-＞4-＞3-＞5-＞6-＞9-＞8-＞10，從目的節點再返回RESV消息1＜-4＜-3＜-5＜-6＜-9＜-8＜-10，如果資源預留成功，則要求的LSP就建立成功了。
利用本發明在源節點就能確定符合約束的路由是否存在，而不需要在各個鬆散節點分別進行計算確定路徑。
本發明特別適用於域內路由，在域內路由情況下，可以提高效率。在多域路由情況下，通過利用域間的路由協議，可以高效地建立智能光網絡中鬆散路由的約束路徑。
本發明的實施例中的一種獲得智能光網絡中鬆散路由的約束路徑的裝置，包括獲取裝置，位於源節點中，用於獲得所述約束路徑的順序鬆散節點和源節點與目的節點；和獲取所述網絡的拓撲結構；計算與控制裝置，用於將所述源節點為起始節點，所述鬆散節點中的目前排序第一順序的鬆散節點為目的節點，利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑；以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點；以所述最後一個鬆散節點作為起始節點，所述目的節點作為目的節點，使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑；所述計算與控制裝置還包括判斷裝置，用於判斷是否所有鬆散節點計算完畢。
其中，還包括路徑合併裝置，用於合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
雖然通過實施例描繪了本發明，本領域普通技術人員知道，本發明有許多變形和變化而不脫離本發明的精神，希望所附的權利要求包括這些變形和變化而不脫離本發明的精神。
權利要求
1.一種獲得智能光網絡中鬆散路由的約束路徑的方法，其特徵在於，包括步驟獲得所述約束路徑的順序鬆散節點和源節點與目的節點；獲取所述網絡的拓撲結構；將所述源節點為起始節點，所述鬆散節點中的目前排序第一順序的鬆散節點為目的節點，利用最短路徑優先(CSPF)算法計算所述源節點到所述第一順序的鬆散節點的路徑；以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；將所述下一個鬆散節點作為當前排序第一鬆散節點，重複上一步驟直到最後一個鬆散節點；以所述最後一個鬆散節點作為起始節點，所述目的節點作為目的節點，使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑；合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
2.如權利要求1所述的方法，其中，所述獲取所述網絡的拓撲結構的步驟包括如果網絡路由為域內路由，所述源節點通過域內路由協議獲取所述網絡的拓撲結構；如果網絡路由包括域間路由，所述源節點通過域內路由協議與多域路由獲取所述網絡的拓撲結構。
3.如權利要求1所述的方法，其中，所述利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑的步驟包括禁止所有其它鬆散節點。
4.如權利要求3所述的方法，其中，所述使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑的步驟包括禁止已計算的路徑中的節點和還沒有參加計算的鬆散節點。
5.如權利要求4所述的方法，其中，所述使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑的步驟還包括，禁止已計算的路徑中的節點。
6.如權利要求1所述的方法，其中，所述以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點的步驟包括判斷是否存在下一個鬆散節點，如果存在，設定目前排序第一鬆散節點為起始節點，所述存在的下一個鬆散節點為目的節點；如果不存在，結束該步驟。
7.如權利要求1所述的方法，還包括步驟判斷所述路徑是否有約束鬆散節點，如果有，執行所述方法的步驟，如果沒有，直接利用CSPF算法獲取路徑。
8.如權利要求1所述的方法，還包括步驟判斷所述約束路徑的鬆散節點是否有順序，如果有，執行所述方法的步驟，如果沒有，利用其它方法獲取路徑。
9.如權利要求1所述的方法，還包括步驟通告MPLS完整的路徑信息；MPLS得到完整的路徑信息後，通過所述完整的路徑發送PATH消息，再返回RESV消息，如果資源預留成功，建立了所述路徑。
10.一種獲得智能光網絡中鬆散路由的約束路徑的裝置，其特徵在於，包括獲取裝置，位於源節點中，用於獲得所述約束路徑的順序鬆散節點和源節點與目的節點；和獲取所述網絡的拓撲結構；計算與控制裝置，用於將所述源節點為起始節點，所述鬆散節點中的目前排序第一順序的鬆散節點為目的節點，利用CSPF算法計算所述源節點到所述第一順序的鬆散節點的路徑；以所述目前排序第一鬆散節點為起始節點，所述鬆散節點中的下一個鬆散節點作為目的節點，使用CSPF算法計算所述目前排序第一鬆散節點到下一個鬆散節點的路徑；重複該步驟直到最後一個鬆散節點；以所述最後一個鬆散節點作為起始節點，所述目的節點作為目的節點，使用CSPF算法計算所述最後一個鬆散節點到所述目的節點的路徑；路徑合併裝置，用於合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。
全文摘要
本發明提供了一種獲得智能光網絡中鬆散路由的約束路徑的方法和裝置，方法包括獲得順序鬆散節點和源節點與目的節點和網絡的拓撲結構；計算所述源節點到所述第一順序的鬆散節點的路徑；合併所有計算完的路徑，將每條路徑按順序首尾相連形成完整的路徑輸出。裝置包括獲取裝置；計算與控制裝置；路徑合併裝置，利用本發明，實現了針對鬆散路由約束高效建立符合鬆散路由約束的路徑；提高了網絡效率，減少了對節點的處理能力的要求。
文檔編號H04Q3/52GK1592159SQ0315761
公開日2005年3月9日 申請日期2003年8月29日 優先權日2003年8月29日
發明者羅賢龍, 王彧 申請人:華為技術有限公司