[發明專利]一種使用拓撲分散短路徑集的網絡路由方法

有效

• 申請號: 201710528851.7
• 申請日: 2017-07-01
• 公開（公告）號: CN107294852B
• 公開（公告）日: 2019-12-27
• 發明（設計）人: 陳光;胡勇堅;崔躍利;梅盼;鄔玲偉;王三秀
• 申請（專利權）人: 臺州學院
• 主分類號: H04L12/733
• 分類號: H04L12/733;H04L12/727
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種使用拓撲分散短路徑集的網絡路由方法，其特征在于：依次執行如下過程：過程一、收集網絡的拓撲信息；過程二、根據網絡的拓撲，為網絡中的每一對起始節點o、目的節點d，計算并存儲節點o到節點d的拓撲分散短路徑集PS_o,d，其中拓撲分散短路徑集PS_o,d是指包含一條或多條節點o到節點d的長度較短且彼此間包含較少共同節點的路徑的集合；過程三、對于每個待傳輸的網絡數據包Φ，為Φ從經過程二已存儲的Φ的起始節點o到目的節點d的拓撲分散短路徑集PS_o,d中選出一條估計傳輸時延最小的路徑P作為Φ的路由路徑。

2.如權利要求1所述的網絡路由方法，其特征在于：所述過程二中，對于網絡中的一對起始節點o、目的節點d，計算節點o到節點d的拓撲分散短路徑集的算法如下，

步驟1：設置一個空的路徑集合PS_o,d，設置一個用于保存PS_o,d中最短路徑的長度的變量L并將L初始化為+∞，同時，為網絡中的每個節點i，設置各自的重疊代價C_i并將C_i初始化為1.0；

步驟2：循環執行PNL次步驟2.1～步驟2.5，如下，

步驟2.1根據網絡的拓撲與當前網絡中各節點的重疊代價，使用Dijkstra最小代價路徑算法計算節點o到節點d的一條最小代價路徑P；

步驟2.2若路徑P的長度＞(L×LRL)，中止步驟2的循環并跳轉至步驟3；

步驟2.3若路徑P的長度＜L，更新L為P的長度；

步驟2.4若路徑P在PS_o,d中不存在，將P加入PS_o,d；

步驟2.5對于每個包含在路徑P中的節點j，將重疊代價C_j增加OCP；

步驟3：返回集合PS_o,d作為節點o到節點d的拓撲分散短路徑集，運算結束；上述算法中，路徑的長度定義為路徑包含的網絡節點的個數，路徑的代價定義為路徑包含的網絡節點的重疊代價之和，PNL(Path Number Limit)表示拓撲分散短路徑集可包含的路徑數量上限，OCP(Overlapping Cost Penalty)表示節點重疊代價懲罰增量，LRL(Length Ratio Limit)表示拓撲分散短路徑集中的任意一條路徑與其中的最短路徑的長度比值上限。

3.如權利要求1所述的網絡路由方法，其特征在于：所述過程三中，某一時刻網絡中一條路徑P的估計傳輸時延T_P定義為該時刻路徑P包含的除終止節點外的所有節點上的網絡數據包發送隊列長度與節點的發送速率的比值之和，即有

其中，(P-P_end)表示路徑P中除終止節點外的所有節點的集合，L_n和R_n分別是節點n上的網絡數據包發送隊列長度和節點n的發送速率。