[發明專利]覆蓋網備用路徑生成方法和裝置

有效

• 申請號: 200910085466.5
• 申請日: 2009-05-26
• 公開（公告）號: CN101562568A
• 公開（公告）日: 2009-10-21
• 發明（設計）人: 楊清峰;李彥君;張國清
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 北京泛華偉業知識產權代理有限公司
• 代理人: 王 勇

1.一種覆蓋網備用路徑生成方法，用于在包括接入服務器節點、標志服務器節點、轉發節點和用戶節點的覆蓋網上為源用戶節點選取合適的轉發節點以構建從源用戶節點到目的用戶節點的備用路徑，該方法包括：

步驟1)、利用所述覆蓋網中的標志服務器節點對所述轉發節點做網絡測距，根據網絡測距結果計算任意兩個轉發節點間的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉發節點構建邏輯轉發網絡；其中，在所述覆蓋網的一個自由域內屬于同一邏輯轉發網絡的轉發節點擁有同一個入口轉發節點；

步驟2)、所述接入服務器節點根據所述源用戶節點的請求轉發節點消息在所述源用戶節點所在的自由域中選擇邏輯轉發網絡，然后通過所述邏輯轉發網絡的入口轉發節點找到與所述入口轉發節點在同一自由域且同一邏輯轉發網絡的轉發節點作為服務轉發節點；所述服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據該算法的運行結果選擇轉發節點作為一次候選轉發節點；其中，

所述的BFBB算法在計算網絡拓撲圖中每個節點的度和核度后，在當前節點上通過廣度優先算法在所述網絡拓撲圖上選取核度值大于當前節點的核度值，且度與核度的商大于當前節點的度與核度的商的節點；若所能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞減后，重新在當前節點上利用廣度優先算法選取核度值大于當前節點的核度值，且度與核度的商大于當前節點的度與核度的商的節點，直到滿足對所選取節點的數目要求；

步驟3)、對候選轉發節點所能形成的路徑做性能檢測，保留通過性能檢測的候選轉發節點，在所述用戶節點間進行業務通信時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用路徑。

2.根據權利要求1所述的覆蓋網備用路徑生成方法，其特征在于，在所述步驟2)中所得到的一次候選轉發節點的數目小于用戶的需求時，在所述的步驟2)和所述的步驟3)之間還包括選取二次候選轉發節點的步驟，該步驟包括：

在所述覆蓋網的網絡拓撲圖上運行BFBB算法；

根據所述BFBB算法的計算結果，從所述覆蓋網中選取一個自由域，在該自由域內選擇轉發節點作為二次候選轉發節點；所選取的轉發節點盡量不屬于所述源用戶節點所在自由域內的邏輯轉發網絡。

3.根據權利要求1或2所述的覆蓋網備用路徑生成方法，其特征在于，所述的步驟1)包括：

步驟1-1)、所述覆蓋網中的所有轉發節點對所述覆蓋網中的所有標志服務器節點做網絡測距，得到關于延遲、丟包率和瓶頸帶寬的指標；

步驟1-2)、根據所述指標計算任意兩個轉發節點間的綜合性能相似度；

步驟1-3)、對所有的綜合性能相似度結果做排序，然后為所述排序結果分段，將具有相近綜合性能的轉發節點分配到同一個邏輯轉發網絡。

4.根據權利要求3所述的覆蓋網備用路徑生成方法，其特征在于，所述的步驟1)還包括：

步驟1-4)、由所述邏輯轉發網絡的入口轉發節點向鄰居域的入口轉發節點做鏈路性能探測；所述鏈路性能包括路徑的延遲、丟包率和瓶頸帶寬；

步驟1-5)、所述鏈路性能探測的結果保存到入口轉發節點的鏈路狀態表中，所述鏈路狀態表的信息定時向鄰居域的入口轉發節點更新。