[發(fā)明專利]網絡拓撲測繪完備性評估方法、系統(tǒng)、電子設備及計算機可讀存儲介質

有效

• 申請?zhí)枺?/td>: 202110646020.6
• 申請日: 2021-06-10
• 公開（公告）號: CN113328893B
• 公開（公告）日: 2022-09-20
• 發(fā)明（設計）人: 張子清;楊旭
• 申請（專利權）人: 北京知道創(chuàng)宇信息技術股份有限公司
• 主分類號: H04L41/12
• 分類號: H04L41/12;H04L41/14
• 代理公司: 北京超凡宏宇專利代理事務所(特殊普通合伙) 11463
• 代理人: 張欣欣

1.一種網絡拓撲測繪完備性評估方法,其特征在于，包括：

根據測繪得到的被測網絡拓撲的所有測繪節(jié)點和所有第二時延鏈路，得到拓撲有向圖，并根據所述所有測繪節(jié)點得到源集和目標集，所述源集為所述測繪節(jié)點中發(fā)送方的集合，所述目標集為所述測繪節(jié)點中接收方的集合；

從所述源集的測繪節(jié)點中選擇任一節(jié)點作為觀測節(jié)點，根據所述拓撲有向圖，將所述目標集中的各測繪節(jié)點依次作為網絡連接路徑的一個頂點，將所述觀測節(jié)點作為每條網絡連接路徑的另一個頂點，進行網絡連接，且每次進行網絡連接前隨機去除所述目標集中任一為非頂點的測繪節(jié)點，得到所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和；

根據所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和，以及源集和目標集各自的測繪節(jié)點總數，得到預估節(jié)點總數；

根據所述被測網絡拓撲的所有測繪節(jié)點的測繪總數和預估節(jié)點總數，得到所述被測網絡拓撲的測繪完備性；

所述根據所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和，以及源集和目標集各自的測繪節(jié)點總數，得到預估節(jié)點總數的步驟，包括：

基于預估算法，得到預估節(jié)點總數，所述預估算法為：

其中，ω^*＝X/(n_T-1)，表示預估節(jié)點總數，n_S表示源集中的測繪節(jié)點總數，n_T表示目標集中的測繪節(jié)點總數，X表示目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和，N^*表示實際測量的測繪節(jié)點的總數。

2.根據權利要求1所述的方法，其特征在于，所述得到所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和的步驟，包括：

若所述目標集中未被單條所述網絡連接路徑覆蓋的測繪節(jié)點的個數為n，則記所述目標集中測繪節(jié)點未被發(fā)現(xiàn)的概率和個數分別為δ_i＝1,i＝n；

統(tǒng)計所有網絡連接路徑連接結束后，所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和為X，其中，k表示網絡連接路徑的總數。

3.根據權利要求1所述的方法，其特征在于，所述方法還包括：

根據所述目標集中測繪節(jié)點未被每條所述網絡連接路徑覆蓋的次數之和，以及網絡連接路徑總數，獲得單次未覆蓋平均次數；

取實際測量的測繪節(jié)點的總數和所述單次未覆蓋平均次數的比值，以推斷所述被測網絡拓撲的實際節(jié)點總數。

4.根據權利要求1所述的方法，其特征在于，所述方法還包括對被測網絡拓撲進行測繪得到測繪節(jié)點和第二時延鏈路的步驟，該步驟包括：

基于分布于不同網絡中的多個測繪點，使用路由跟蹤工具，測繪出被測網絡拓撲的IP節(jié)點和第二時延鏈路，以所述IP節(jié)點作為測繪節(jié)點。

5.根據權利要求4所述的方法，其特征在于，所述第二時延鏈路通過以下步驟測繪得到：

使所述路由跟蹤工具在各所述測繪點以周期性的方式多次測量第一時延鏈路，并將多次測量的第一時延鏈路的平均值作為第二時延鏈路。

6.根據權利要求1所述的方法，其特征在于，所述拓撲有向圖以測繪節(jié)點作為連接節(jié)點，以第二時延鏈路作為所述連接節(jié)點的連邊的權重。