[發明專利]基于三路子拓撲測量的網絡拓撲發現方法

有效

• 申請號: 202010884969.5
• 申請日: 2020-08-28
• 公開（公告）號: CN111970202B
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 潘勝利;梁應敞;易長勝;張宗旺
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/721;G06K9/62
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

1.一種基于三路子拓撲測量的網絡拓撲發現方法，其特征在于，包括：

A1、在待測量的拓撲網絡中，隨機選擇三個葉子節點組成初始三路子拓撲作為初始拓撲；

A2、從剩下的葉子節點中隨機選擇葉子節點作為下一個待插入節點；

A3、找到當前拓撲中擁有最長公共路徑的兩個葉子節點，選擇從源節點到這兩個葉子節點之間的二分內部節點，以該二分內部節點作為公共祖先節點，隨機選擇一個節點，若該節點與兩個葉子節點中的其中一個葉子節點的最近公共祖先節點為二分內部節點，則選擇該節點，進而將該節點與這個葉子節點作為選出的兩個節點，與待插入節點組成新的三路子拓撲；

A4、測量新的三路子拓撲的類型；

A5、根據新的三路子拓撲的類型，確定該待插入節點的插入位置，從而得到更新的拓撲；

A6、重復步驟A2-A5，直至所有剩下的葉子節點完成插入，從而恢復整個拓撲網絡。

2.根據權利要求1所述的一種基于三路子拓撲測量的網絡拓撲發現方法，其特征在于，步驟A4包括以下分步驟：

A41、獲得當前三路子拓撲兩兩路徑的相似度量集合，計算相似度平均相對偏差；

A42、將平均相對偏差作為無監督聚類方法的輸入，進行二元聚類，得到當前三路子拓撲的類型。

3.根據權利要求2所述的一種基于三路子拓撲測量的網絡拓撲發現方法，其特征在于，步驟A5具體為：設定源節點為s，待插入節點為k，公共祖先節點為m，距離m最近的兩個葉子節點分別記為i、j；

若聚類結果為0，則當前三路子拓撲類型為τ(p_i,p_j,p_k)＝0，該待插入節點的插入位置為節點m；

若S(p_i,p_j)S(p_i,p_k)＝S(p_j,p_k)，則當前三路子拓撲類型為τ(p_i,p_j,p_k)＝1，該待插入節點的插入位置為節點s到m之間的鏈路；

若S(p_i,p_k)S(p_i,p_j)＝S(p_j,p_k)，則當前三路子拓撲類型為τ(p_i,p_j,p_k)＝2，該待插入節點的插入位置為節點m到i之間的鏈路；

若S(p_i,p_k)＝S(p_i,p_j)S(p_j,p_k)，則當前三路子拓撲類型為τ(p_i,p_j,p_k)＝3，該待插入節點的插入位置為節點m到j之間的鏈路；

其中，p_i,p_j,p_k為當前三路子拓撲對應的三條路徑，S(p_i,p_j)表示p_i與p_j的相似度量，S(p_i,p_k)表示p_i與p_k的相似度量，S(p_j,p_k)表示p_j與p_k的相似度量。

4.根據權利要求3所述的一種基于三路子拓撲測量的網絡拓撲發現方法，其特征在于，任意兩兩路徑p_i和p_j的相似度量計算為：

Cov(X,Y)＝E[XY]-E[X]E[Y]

其中，X表示路徑p_i的M次探測得到的時延數據，Y表示路徑p_j的M次探測得到的時延數據，E[X]為X期望值，E[Y]為Y的期望值，E[XY]為X和Y的聯合期望值。