[發明專利]一種互聯網測試床拓撲結構分解方法及裝置

有效

• 申請號: 201810564523.7
• 申請日: 2018-06-04
• 公開（公告）號: CN108880872B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 焦波;石建邁;張文生;邢立寧;戎海武;何敏藩;于輝;王向東
• 申請（專利權）人: 佛山科學技術學院
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 王國標

1.一種互聯網測試床拓撲結構分解方法，其特征在于：互聯網測試床拓撲結構被分解至七個二分圖、一個匹配圖和一個內核圖，該方法包括以下步驟：

步驟1，獲取真實世界互聯網拓撲結構的探測數據，并以簡單無向圖G＝(V,E)建模自治系統級互聯網拓撲結構，其中集合V中節點的物理意義為真實世界互聯網的自治系統，集合E中邊的物理意義為不同自治系統之間的數據通信路徑；

步驟2，計算節點集P＝{v∈V|d_v＝1}；

步驟3，計算節點集

步驟4，計算節點集

步驟5，計算節點集

步驟6，計算節點集

步驟7，計算節點集

步驟8，計算節點集II＝{v∈V_I|d_I(v)＝0}；

步驟9，構建二分圖

步驟10，構建二分圖

步驟11，構建二分圖

步驟12，構建二分圖

步驟13，構建二分圖G_QI-PI＝(QI,PI,E_QI-PI)；

步驟14，構建二分圖

步驟15，構建二分圖G_Q-P＝(Q,P,E_Q-P)；

步驟16，構建匹配圖G_BI-BI＝(BI,E_BI-BI)；

步驟17，構建內核圖G_Core＝(V_Core,E_Core)；

在步驟9中，所述II和為二分圖的兩個節點集，且為二分圖的邊集；

在步驟10中，所述BI和為二分圖的兩個節點集，且為二分圖的邊集；

在步驟11中，所述RI和為二分圖的兩個節點集，且為二分圖的邊集；

在步驟12中，所述和為二分圖的兩個節點集，且為二分圖的邊集；

在步驟13中，所述QI和PI為二分圖G_QI-PI的兩個節點集，且為E_QI-PI＝{e＝(v,w)|e∈E∧v∈PI∧w∈QI}為二分圖G_QI-PI的邊集；

在步驟14中，所述PI和為二分圖的兩個節點集，且為二分圖的邊集；

在步驟15、步驟16、步驟17中，所述Q和P為二分圖G_Q-P的兩個節點集，且E_Q-P＝{e＝(v,w)|e∈E∧v∈P∧w∈Q}為二分圖G_Q-P的邊集；BI為匹配圖G_BI-BI的節點集，且E_BI-BI＝{e＝(v,w)|e∈E∧v,w∈BI}為匹配圖G_BI-BI的邊集；V_Core＝Q∪QI為內核圖G_Core的節點集，且E_Core＝{e＝(v,w)|e∈E∧v,w∈V_Core}為內核圖G_Core的邊集。

2.根據權利要求1所述的一種互聯網測試床拓撲結構分解方法，其特征在于，在步驟1中，所述自治系統是指互聯網中有權自主確定在本系統中應采用何種路由協議的小型單位。

3.一種互聯網測試床拓撲結構分解裝置，其特征在于，互聯網測試床拓撲結構被分解至七個二分圖、一個匹配圖和一個內核圖，所述裝置包括：

第一單元，用于獲取真實世界互聯網拓撲結構的探測數據，并以簡單無向圖G＝(V,E)建模自治系統級互聯網拓撲結構，其中集合V中節點的物理意義為真實世界互聯網的自治系統，集合E中邊的物理意義為不同自治系統之間的數據通信路徑；

第二單元，用于計算節點集P＝{v∈V|d_v＝1}；

第三單元，用于計算節點集

第四單元，用于計算節點集

第五單元，用于計算節點集

第六單元，用于計算節點集

第七單元，用于計算節點集

第八單元，用于計算節點集II＝{v∈V_I|d_I(v)＝0}；

第九單元，用于構建二分圖

第十單元，用于構建二分圖

第十一單元，用于構建二分圖

第十二單元，用于構建二分圖

第十三單元，用于構建二分圖G_QI-PI＝(QI,PI,E_QI-PI)；

第十四單元，用于構建二分圖

第十五單元，用于構建二分圖G_Q-P＝(Q,P,E_Q-P)；

第十六單元，用于構建匹配圖G_BI-BI＝(BI,E_BI-BI)；

第十七單元，用于構建內核圖G_Core＝(V_Core,E_Core)；

其中，所述II和為二分圖的兩個節點集，且為二分圖的邊集；

所述BI和為二分圖的兩個節點集，且為二分圖的邊集；

所述RI和為二分圖的兩個節點集，且為二分圖的邊集；

所述和為二分圖的兩個節點集，且為二分圖的邊集；

所述QI和PI為二分圖G_QI-PI的兩個節點集，且為E_QI-PI＝{e＝(v,w)|e∈E∧v∈PI∧w∈QI}為二分圖G_QI-PI的邊集；

所述PI和為二分圖的兩個節點集，且為二分圖的邊集；

所述Q和P為二分圖G_Q-P的兩個節點集，且E_Q-P＝{e＝(v,w)|e∈E∧v∈P∧w∈Q}為二分圖G_Q-P的邊集；BI為匹配圖G_BI-BI的節點集，且E_BI-BI＝{e＝(v,w)|e∈E∧v,w∈BI}為匹配圖G_BI-BI的邊集；V_Core＝Q∪QI為內核圖G_Core的節點集，且E_Core＝{e＝(v,w)|e∈E∧v,w∈V_Core}為內核圖G_Core的邊集。