[發明專利]骨干網絡及其動態路徑規劃系統和規劃方法

有效

• 申請號: 201711276678.2
• 申請日: 2017-12-06
• 公開（公告）號: CN108111411B
• 公開（公告）日: 2020-12-22
• 發明（設計）人: 趙興宇;嚴鵬;吳彬彬;陳亢
• 申請（專利權）人: 上海神添實業有限公司;上海無線電設備研究所
• 主分類號: H04L12/707
• 分類號: H04L12/707;H04L12/715;H04L12/735;H04L12/751;H04Q11/00
• 代理公司: 上海信好專利代理事務所(普通合伙) 31249
• 代理人: 朱成之

1.一種骨干網絡動態路徑規劃方法，其特征在于，該規劃方法包含：

根據骨干網絡構建基于光載波波長的分層網絡拓撲；

基于光載波波長的分層網絡拓撲通過Bhandari算法得到源節點至目的節點的兩條不相交的路徑；

所述根據光纖骨干網絡構建基于光載波波長的分層網絡拓撲的方法包含：

骨干網絡包含若干節點和連接節點的光纖鏈路，其中各個節點周期性地向外發送自己與相鄰節點的通信的帶寬占用情況；

節點通過收到的帶寬占用信息，建立實際網絡拓撲，周期性地更新分層網絡拓撲中的每條光纖鏈路信息；

源節點產生通信需求時，根據帶寬需求，為每條光纖鏈路計算權重；

根據實際網絡拓撲構建基于光載波波長的分層網絡拓撲，分層網絡拓撲分為若干層，每一層對應一個光載波波長，每層包含虛擬節點和鏈路；

有通信需求的源節點和目的節點在分層網絡拓撲中定義虛擬源節點和虛擬目的節點，虛擬源節點和虛擬目的節點分別通過權重為0的鏈路連接到分層網絡拓撲每一層中屬于實際網絡拓撲的源節點和目的節點的節點。

2.如權利要求1所述的骨干網絡動態路徑規劃方法，其特征在于，所述虛擬源節點通過權重為0的鏈路與屬于源節點的所有虛擬節點相連，分層鏈路上每條邊的權重與相應波長的可用光纖數量成反比，可用光纖越多，權重越小，反之越大；數量不滿足當前通信需求時，權重設為正無窮，建立路徑時不被采用。

3.如權利要求1所述的骨干網絡動態路徑規劃方法，其特征在于，所述基于光載波波長的分層網絡拓撲通過Bhandari算法得到源節點至目的節點的兩條不相交的路徑的方法包含：

利用Dijkstra算法在分層網絡拓撲中找到虛擬源節點至虛擬目的節點最優路徑；

根據最優路徑更新分層網絡拓撲的權重；

根據更新權重后的分層網絡拓撲，利用Bellman-Ford算法得出次優路徑；

采用最優路徑和次優路徑構建一個新網絡，若該新網絡中有相同的共用鏈路，則刪除相同的共用鏈路；

利用兩次Dijkstra算法得出兩條路徑，新生成的路徑即為兩條不相交的路徑。

4.如權利要求3所述的骨干網絡動態路徑規劃方法，其特征在于，所述利用Dijkstra算法在分層網絡拓撲中找到虛擬源節點至虛擬目的節點最優路徑的方法包含：

分層網絡拓撲G中包含n個節點，有n×n的權重值矩陣W＝[w(i,j)]，1≤i,j≤n，初始化相鄰矩陣W，其中w(i,j)為節點i到節點j的距離，若i到j無通路，則初始化為無窮大，若i＝j，初始化為0，有距離向量dist[i]和前驅節點向量path[i]，與起始節點V_s的相鄰節點V_i有dist[i]＝w(s,i)，path[i]＝s或dist[i]＝∞，path[i]＝∞即無前驅節點；對于集合S和U，則有S＝{V_s}，U＝{V₁,V₂,…V_n}-{V_s}，即U＝V-S；其中S是搜索過的點的集合，U是S的補集；

若U中有節點，則從U中選擇min{dist[k],k∈U}，將k加入到S中，即S＝S+{V_k}，U＝U-{V_k}，k指第k個節點；

更新與k直接相鄰頂點j的距離值dist和路徑path，有狀態轉移方程：

dist[j]＝min{dist[j],dist[k]+W[k][i]}

path[j]＝path[j]或k；

若U中無節點，計算結束。

5.如權利要求3所述的骨干網絡動態路徑規劃方法，其特征在于，所述根據最優路徑更新分層網絡拓撲的權重的方法包含：

在的最優路徑中，找到其包含鏈路的物理路徑，并將分層網絡拓撲中所有屬于這些物理鏈路的其他鏈路權重設為無窮大，即下次路徑查找避免有相同的物理鏈路。