一種級聯管理系統以及端到端路由選擇方法
2023-08-22 10:24:36
專利名稱：一種級聯管理系統以及端到端路由選擇方法
技術領域：
本發明涉及通信技術領域，尤其涉及一種級聯管理系統以及端到端路由選擇方法。
背景技術：
在通訊系統中，包括電信網絡管理系統、地理信息導航系統等，許多系統需要根據已有的數據源計算端到端的路由信息，用於生成一條最經濟的路徑。當這個系統中的規模達到一定程度，可能一個獨立的系統無法管理龐大的數據量，或者由於管理區域劃分、系統負荷等問題需要把系統劃分成若干子網來管理，而且還要有一個全局統一的管理系統。這時，級聯的管理系統是一個比較合理的解決方案，其中，網絡管理系統(NMS)只能看到本子網內的節點和連接，可以計算和生成網絡內所有節點間的最短路徑；級聯網絡管理系統(CNMS)作為上層網絡管理系統，管理幾個下層網絡管理系統，下層網絡管理系統可以是NMS，也可以是CNMS，作為上層網絡管理系統的CNMS可以計算跨下層子網的路徑。當採用級聯繫統的時候，每個管理系統都可能帶有自己的客戶端，用於本管理域內的數據更新和路由計算。管理系統往往把每兩個節點之間的連接開銷轉換成節點間的邊長，那麼生成最經濟的路徑的方法就轉換成了圖論中的最短路由算法。
現有的集中式最短路由計算方法是圖論中的Dijkstra算法，這個算法是廣度優先的有向圖最短路由算法，可以搜索出有向圖中指定節點到所有其它節點的最短距離，並且可以給出指定節點到所有其它節點的最短路徑，Dijkstra算法的時間複雜度為0(n2)。對於級聯的管理系統，如果中心管理系統使用Dijkstra算法生成最經濟路徑，要求上層管理系統具有所管網絡的所有拓撲數據，並處理所有的路徑生成請求，可能成為系統的瓶頸。更大的問題是對於一個可變的網絡，拓撲數據要動態生成，而且是不斷變化的。比如一個傳送網絡管理系統，由於業務調度，導致節點之間的可用時隙變化，創建新的路徑時，對應的服務層路徑拓撲會改變。這就要求上層管理系統與下層管理系統之間具有實時可靠的數據同步能力。尤其是下層管理系統有獨立的客戶端，可獨立改變數據的時候。在這種情況下，上層管理系統直接使用Dijkstra算法會導致整個系統在數據同步上設計複雜，並花費較大的開銷，造成實際系統中CNMs和NMS之間的信息傳輸開銷往往大於計算路由的開銷。
發明內容
本發明提供一種級聯管理系統以及在級聯管理系統中生成最經濟路徑的方法，該方法不需要在上層管理系統保存整個網絡的拓撲數據，可以大大減少上下層網絡管理系統之間數據傳輸的開銷。
本發明的技術方案為一種端到端路由選擇方法，設置一個或多個網絡管理系統及一級聯網絡管理系統，所述網絡管理系統用於管理一個子網，所述級聯網絡管理系統通過所述的網絡管理系統管理一個網絡；所述方法包括如下步驟A、由級聯網絡管理系統確定下層網絡的公有節點，並下發計算請求給各網絡管理系統；B、各網絡管理系統接收到所述計算請求後，計算各自所管理的子網內的公有節點間最短距離，形成子網內公有節點間最短距離矩陣；
C、所述級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成全網等效圖，並計算所述全網等效圖上起點和終點間的最短距離和選擇等效最短路由；D、所述各網絡管理系統選擇屬於本子網內相鄰節點等效連接對應的實際最短路由。
所述的方法，其中所述公有節點包括起點和終點，以及各子網的邊界節點和不屬於任何子網的節點。
所述的方法，其中所述的步驟A包括如下處理由級聯網絡管理系統確定下層網絡公有節點的分布，並將公有節點信息下發給各網絡管理系統。
所述的方法，其中所述步驟C包括如下處理所述級聯網絡管理系統匯總各網絡管理系統返回的子網內公有節點間最短距離矩陣、不屬於任何子網的節點、鏈路和網間連接，構建所管理的網絡各公有節點間距離矩陣，形成全網等效圖。
所述的方法，其中所述的步驟D包括如下具體步驟D1、遍歷所述等效最短路由中的每段連接，級聯網絡管理系統將等效最短路由上屬於同一子網的相鄰節點連接下發給所述網絡管理系統；D2、所述網絡管理系統計算子網內等效連接對應的實際最短路由。
一種級聯管理系統，包括一個或多個網絡管理系統和一個級聯網絡管理系統，所述網絡管理系統用於管理一個子網，計算和生成子網內所有節點間的最短路徑；所述級聯網絡管理系統與所述各網絡管理系統通訊連接，通過其子網的所述網絡管理系統管理一個網絡。
所述的系統，其中所述級聯網絡管理系統和網絡管理系統可以分布在不同計算機上。
所述的系統，其中所述級聯網絡管理系統和網絡管理系統為設置在同一計算機上的兩個子系統。
一種端到端路由選擇方法，設置多個網絡管理系統及多個級聯網絡管理系統，所述方法包括如下步驟A、由首層級聯網絡管理系統確定第二層網絡的公有節點，並下發含有選定的公有節點信息的第一計算請求給第二層網絡管理系統和第二層級聯網絡管理系統；B、第二層網絡管理系統和第二層級聯網絡管理系統接收到所述第一計算請求後，計算各自所管理的網絡內公有節點間最短距離，形成各網絡內公有節點間最短距離矩陣，並返給首層級聯網絡管理系統；C、首層級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成第一全網等效圖，並計算所述第一全網等效圖上起點和終點間的最短距離和選擇等效最短路由；D、遍歷所述等效最短路由中的每段連接，首層級聯網絡管理系統將等效最短路由上屬於同一子網的相鄰節點連接下發給第二層網絡管理系統或第二層級連網絡管理系統，由第二層網絡管理系統和第二層級連網絡管理系統計算屬於本子網內相鄰節點等效連接對應的實際最短路由。
所述的方法，其中步驟B所述的第二層級聯網絡管理系統構建所管理網絡內公有節點間最短距離矩陣包括如下具體步驟B1、第二層級聯網絡管理系統確定其管理網絡範圍內的公有節點集，然後向直屬第三層網絡管理系統下發第二計算請求，所述第二計算請求含有第三層各網絡管理系統管理的公有節點信息；
B2、第三層各網絡管理系統接收到所述第二計算請求後，計算各自所管理的子網內的公有節點間最短距離，形成子網內公有節點間最短距離矩陣返給第二層級聯網絡管理系統；B3、第二層級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成第二全網等效圖；B4、第二層級聯網絡管理系統依據所述第二全網等效圖計算所述第一層級連網絡管理系統下發請求的公有節點間最短距離矩陣，並返回給第一層級連網絡管理系統。
所述的方法，其中所述步驟1所述的公有節點集包括第一層級連網絡管理系統下發請求的公有節點，第三層各網絡管理系統的邊界節點，以及不屬於任何第三層網絡管理系統管理的節點。
一種級聯管理系統，包括多個網絡管理系統以及多個級聯網絡管理系統，所述網絡管理系統用於管理一個子網，計算和生成子網內所有節點間的最短路徑；首層級聯網絡管理系統分別與各第二層網絡管理系統以及第二層級聯網絡管理系統通訊連接；所述第二層級聯網絡管理系統與各第三層網絡管理系統以及第三層級聯網絡管理系統通訊連接；依此類推，直至第N層級聯網絡管理系統與直屬N+1層的所述各網絡管理系統通訊連接為止。
本發明的有益效果為本發明所採用的方法由於不要求上層CNMS知道子網內的細節，不需要在CNMS和NMS之間傳遞整個子網的信息，僅需要傳遞公有節點間的距離矩陣，從而大大減少數據傳輸的開銷。同時由於每個子網都有自己的NMS，k個子網構造距離矩陣的操作可以並行，若適當劃分子網，使公共節點數m遠小於子網內總節點數n，且公共節點數m小於子網數k2，則該方法還節省計算時間。
圖1為本發明級聯網絡管理系統示意圖；圖2為本發明子網示例圖；圖3為本發明方法流程圖；圖4為本發明子網的等效圖；圖5為本發明全網等效圖；圖6為本發明CNMS計算出的等效路由示意圖；圖7為本發明最終的實際路由示意圖。
具體實施例方式
下面根據附圖和實施例對本發明作進一步詳細說明本發明系統如圖1所示，設置若干NMS及CNMS，NMS用於管理一個子網，計算和生成子網內所有節點間的最短路徑；CNMS是網絡管理系統(NMS)的一種，與一個或多個直屬下層NMS通訊連接，例如CNMS2與直屬下層的NMS2、NMS3通訊，CNMS通過其子網的NMS管理一個網絡；CNMS和NMS之間可以部署在不同計算機上，也可能是同一臺計算機上的兩個子系統。當一個網絡劃分成若干子網後，每個子網中的與子網外節點有直接連接的節點叫做子網的邊界節點；兩端的節點屬於不同子網的連接叫做網間連接，很明顯，網間連接的端點都是子網的邊界節點；我們把所要選擇的端到端路由的起點、終點、各子網的邊界節點和不屬於任何子網的節點的併集，統稱為公有節點。
採用本發明的端到端路由選擇方法，不需要在上層管理系統保存整個網絡的拓撲數據，也不需要上下層管理系統之間做大量的數據同步。所述方法通過級聯的管理系統計算拓撲網絡節點間最短路由，先由一個或多個下層管理系統並行計算自己子拓撲各公有節點間最短距離，上層管理系統根據下層管理系統的計算結果計算整個拓撲網絡的等效最短路由，再由下層管理系統計算子拓撲內實際的最短路由。
假定有一個網絡，它被劃分成如圖2所示的k個子網，以及一些不屬於任何子網的節點和鏈路，每條鏈路都有各自的長度。這個網絡由一個級聯網絡管理系統(CNMS)管理，每個子網由一個網絡管理系統(NMS)管理。現在指定這個網絡內的任意兩個節點A和Z，要生成從A到Z之間的最短路由。採用本發明所述方法流程如圖3所示，具體包括以下步驟步驟1、首先由CNMS根據直屬下層NMS所管理的子網間的連接情況來確定公有節點，公有節點包括選擇最短路由的起點、終點、不屬於任何下層NMS的節點、各直屬下層NMS的邊界節點；並且CNMS將計算請求下發給直屬下層所有的NMS，計算請求中包括選定的公有節點信息。
步驟2、各子網的NMS收到計算請求後，依據所管子網內的節點和連接，採用任何高效算法計算該子網內所有公有節點之間的最短距離，例如，採用用Dijkstra算法，形成一個子網內公有節點最短距離矩陣，並將其返回給CNMS。例如依據圖2，計算出來的子網內公有節點最短距離矩陣見下表
有了這個子網內公有節點最短距離矩陣，相當於對圖2所示子網構造了一個如圖4所示的子網等效圖，這個等效圖上只有公有節點，節點間具有連接，連接的邊長等於NMS計算出的節點間的最短距離，這種連接叫做子網內等效連接。
步驟3、CNMs把所有子網內公有節點最短距離矩陣匯總在一起，加上不屬於任何子網的節點、鏈路和網間連接，就得到全網各公有節點間的距離矩陣，相當於形成了一個全網的等效圖，參見圖5，全網等效圖的節點數就是公有節點數。
步驟4、CNMS基於全網公有節點間距離矩陣，即在全網等效圖上計算A到Z的最短路由(如採用Dijkstra算法)，可以得到一條僅包括公有節點的等效最短路由，如圖6中帶箭頭的粗線所示。
步驟5、遍歷CNMS選擇出來的等效最短路由中的每段連接，若兩個相鄰節點之間的連接是某子網內等效連接，CNMS將這段連接下發給管理這個子網的NMS；由管理這個子網的NMS計算和提供這個子網內這兩個節點間實際最短路由，並且用這段實際最短路由替換等效連接。這樣得到的路由就是全網範圍內從A到Z的最短路由，如圖7中虛線所示的路由。
該方法可以應用於多層級聯的管理系統。系統包括多個NMS以及多個CNMS；首層CNMS1分別與第二層NMS以及第二層CNMS進行通訊；第二層CNMS與各第三層NMS和第三層CNMS進行通訊；依此類推，第N層級聯網絡管理系統與直屬N+1層的所述各網絡管理系統通訊。如圖1所示，本實施例為兩層級連管理系統，上層CNMS1管理直屬下層CNMS2和NMS1，下層CNMS2管理直屬的NMS2和NMS3；端到端路由選擇方法依此類推如下1、由上層CNMS1確定直屬下層網絡的公有節點，並下發含有選定的公有節點信息的計算請求給直屬下層的各NMS(NMS1)和下層CNMS2；2、直屬下層各NMS和CNMS2接收到計算請求後，計算自己所管理的網絡內的公有節點間最短距離，形成各下屬網絡內公有節點最短距離矩陣；其中NMS採用與單個級聯的管理系統步驟2相同的方法；而下層CNMS2採用以下步驟2.1、CNMS2確定它所管理網絡範圍內的公有節點集UCNMS2，UCNMS2包括上層CNMS1下發來的公有節點、不屬於CNMS2直屬任何下層NMS管理的節點、以及各直屬下層NMS的邊界節點，然後CNMS2向各直屬下層NMS下發計算請求，該請求包括該NMS管理的公有節點；2.2、CNMS2直屬各子網的NMS依據子網內的節點和連接，採用任何高效算法計算CNMS2請求的子網內公有節點間最短距離矩陣，並返回給CNMS2；2.3、CNMS2匯總各下層NMS返回的公有節點間最短距離矩陣，加上不屬於任何下層NMS管理的節點、鏈路和網間連接，就得到所管子網的公有節點集UCNMS2間的距離矩陣，相當於形成了本子網的等效圖；2.4、CNMS2根據UCNMS2間的等效距離矩陣，採用任何高效算法計算CNMS請求的本網絡內公有節點間最短距離矩陣並返回給CNMS1。
3、CNMS1把直屬下屬的所有子網CNMS2和NMS1內公有節點距離矩陣匯總在一起，加上不屬於任何子網的節點、鏈路和網間連接，就得到所管理網絡各公有節點間的距離矩陣，相當於形成了一個全網的等效圖。
4、CNM1S基於全網公有節點間距離矩陣，即在全網等效圖上計算起點到終點的最短距離(如採用Dijkstra算法)，可以得到一條僅包括公有節點的等效最短路由。
5、遍歷CNMS1選擇出來的等效最短路由中的每段連接，若兩個相鄰節點之間的連接是某子網內等效連接，CNM1S將這段連接下發給管理這個子網的NMS1或CNMS2；由管理這個子網的NMS1和CNMS2計算和提供這個子網內這兩個節點間實際最短路由，並且用這段實際最短路由替換等效連接，這樣得到的路由就是全網範圍內從A到Z的最短路由。由於CNMS2是級連網絡管理系統，為了得到其直屬下層子網1和子網2內對應等效連接的最短路由，需要在CNMS2內再執行單個級聯網絡管理系統的步驟1～5，即可得到對應等效連接的最短路由。
該方法可以大大減少上下層網管系統間數據傳輸的開銷。同時由於每個子網都有自己的NMS，k個子網構造距離矩陣的操作可以並行，在計算的時間複雜度上，如果子網劃分合理，也可以節省計算時間。可以按簡單情況估算一下假定整個網絡劃分成k個子網，每個子網有n個節點，其中m個公有節點，整個網絡有N＝k*n個節點，k*m個公有節點，沒有不屬於任何子網的節點。傳統的集中計算的Dijkstra算法計算兩點間路由的時間複雜度是0(N2)，即0((k*n)2)。此方法中中最耗時的步驟是步驟2和步驟4。如果使用Dijkstra算法，步驟2求出子網內距離矩陣的時間複雜度是0(m*n2)，由於每個子網都有自己的NMS，k個子網構造距離矩陣的操作可以並行；步驟4的時間複雜度是0((k*m)2)。若適當劃分子網，使m＜＜n，且m＜k2，則該算法會節省總共的計算時間。此方法基於整個網絡劃分成了多個子網，而每個子網內的公有節點數m遠小於子網內的所有節點數n。對於高連通度的網絡，不論如何劃分，大多數的節點是公有節點，該方法會消耗更多的計算時間。而對於一般的電信傳送網絡來說，出於成本考慮，是不太可能建立全連通或者高連通度的網絡的，更多的是環網和網孔型的MESH網，子網劃分就容易達到此方法的假定。
可以理解的是，對本領域普通技術人員來說，可以根據本發明的技術方案及其發明構思加以等同替換或改變，而所有這些改變或替換都應屬於本發明所附的權利要求的保護範圍。
權利要求
1.一種端到端路由選擇方法，設置一個或多個網絡管理系統及一級聯網絡管理系統，所述網絡管理系統用於管理一個子網，所述級聯網絡管理系統通過所述的網絡管理系統管理一個網絡；所述方法包括如下步驟A、由級聯網絡管理系統確定下層網絡的公有節點，並下發計算請求給各網絡管理系統；B、各網絡管理系統接收到所述計算請求後，計算各自所管理的子網內的公有節點間最短距離，形成子網內公有節點間最短距離矩陣；C、所述級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成全網等效圖，並計算所述全網等效圖上起點和終點間的最短距離和選擇等效最短路由；D、所述各網絡管理系統選擇屬於本子網內相鄰節點等效連接對應的實際最短路由。
2.根據權利要求1所述的方法，其特徵在於所述公有節點包括起點和終點，以及各子網的邊界節點和不屬於任何子網的節點。
3.根據權利要求1所述的方法，其特徵在於所述的步驟A包括如下處理由級聯網絡管理系統確定下層網絡公有節點的分布，並將公有節點信息下發給各網絡管理系統。
4.根據權利要求1所述的方法，其特徵在於所述步驟C包括如下處理所述級聯網絡管理系統匯總各網絡管理系統返回的子網內公有節點間最短距離矩陣、不屬於任何子網的節點、鏈路和網間連接，構建所管理的網絡各公有節點間距離矩陣，形成全網等效圖。
5.根據權利要求1所述的方法，其特徵在於所述的步驟D包括如下具體步驟D1、遍歷所述等效最短路由中的每段連接，級聯網絡管理系統將等效最短路由上屬於同一子網的相鄰節點連接下發給所述網絡管理系統；D2、所述網絡管理系統計算子網內等效連接對應的實際最短路由。
6.一種級聯管理系統，其特徵在於包括一個或多個網絡管理系統和一個級聯網絡管理系統，所述網絡管理系統用於管理一個子網，計算和生成子網內所有節點間的最短路徑；所述級聯網絡管理系統與所述各網絡管理系統通訊連接，通過其子網的所述網絡管理系統管理一個網絡。
7.根據權利要求6所述的系統，其特徵在於所述級聯網絡管理系統和網絡管理系統可以分布在不同計算機上。
8.根據權利要求6所述的系統，其特徵在於所述級聯網絡管理系統和網絡管理系統為設置在同一計算機上的兩個子系統。
9.一種端到端路由選擇方法，設置多個網絡管理系統及多個級聯網絡管理系統，所述方法包括如下步驟A、由首層級聯網絡管理系統確定第二層網絡的公有節點，並下發含有選定的公有節點信息的第一計算請求給第二層網絡管理系統和第二層級聯網絡管理系統；B、第二層網絡管理系統和第二層級聯網絡管理系統接收到所述第一計算請求後，計算各自所管理的網絡內公有節點間最短距離，形成各網絡內公有節點間最短距離矩陣，並返給首層級聯網絡管理系統；C、首層級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成第一全網等效圖，並計算所述第一全網等效圖上起點和終點間的最短距離和選擇等效最短路由；D、遍歷所述等效最短路由中的每段連接，首層級聯網絡管理系統將等效最短路由上屬於同一子網的相鄰節點連接下發給第二層網絡管理系統或第二層級連網絡管理系統，由第二層網絡管理系統和第二層級連網絡管理系統計算屬於本子網內相鄰節點等效連接對應的實際最短路由。
10.根據權利要求9所述的方法，其特徵在於步驟B所述的第二層級聯網絡管理系統構建所管理網絡內公有節點間最短距離矩陣包括如下具體步驟B1、第二層級聯網絡管理系統確定其管理網絡範圍內的公有節點集，然後向直屬第三層網絡管理系統下發第二計算請求，所述第二計算請求含有第三層各網絡管理系統管理的公有節點信息；B2、第三層各網絡管理系統接收到所述第二計算請求後，計算各自所管理的子網內的公有節點間最短距離，形成子網內公有節點間最短距離矩陣返給第二層級聯網絡管理系統；B3、第二層級聯網絡管理系統構建所管理的網絡各公有節點間距離矩陣，形成第二全網等效圖；B4、第二層級聯網絡管理系統依據所述第二全網等效圖計算所述第一層級連網絡管理系統下發請求的公有節點間最短距離矩陣，並返回給第一層級連網絡管理系統。
11.根據權利要求10所述的方法，其特徵在於所述步驟1所述的公有節點集包括第一層級連網絡管理系統下發請求的公有節點，第三層各網絡管理系統的邊界節點，以及不屬於任何第三層網絡管理系統管理的節點。
12.一種級聯管理系統，其特徵在於包括多個網絡管理系統以及多個級聯網絡管理系統，所述網絡管理系統用於管理一個子網，計算和生成子網內所有節點間的最短路徑；首層級聯網絡管理系統分別與各第二層網絡管理系統以及第二層級聯網絡管理系統通訊連接；所述第二層級聯網絡管理系統與各第三層網絡管理系統以及第三層級聯網絡管理系統通訊連接；依此類推，直至第N層級聯網絡管理系統與直屬N+1層的所述各網絡管理系統通訊連接為止。
全文摘要
一種級聯管理系統以及端到端路由選擇方法，設置若干網絡管理系統(NMS)及級聯網絡管理系統(CNMS)，NMS用於管理一個子網，CNMS通過NMS管理一個網絡；所述方法包括如下步驟A、由CNMS確定公有節點的分布，並下發計算請求給各NMS；B、各NMS計算自己子網內的公有節點間最短距離矩陣；C、CNMS匯總各NMS返回的最短距離矩陣，形成全網等效圖，並計算全網等效圖上起點和終點間的最短距離和等效最短路由；D、各NMS計算屬於本子網內相鄰節點等效連接對應的實際最短路由。該方法可以大大減少上下層網管系統間數據傳輸的開銷，並且由於k個子網構造距離矩陣的操作可以並行，該方法還節省計算時間。
文檔編號H04L12/24GK1984038SQ20061006025
公開日2007年6月20日 申請日期2006年4月6日 優先權日2006年4月6日
發明者張立巖, 程韶軍 申請人:華為技術有限公司