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

有效

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

本發明公開一種基于三路子拓撲測量的網絡拓撲發現方法，應用于網絡層析成像領域，針對現有三路子拓撲的推斷方法在網絡規模大的時候，測量復雜度較高的問題，本發明對三路子拓撲進行測量，將得到的相關性測量計算平均相對偏差，將平均相對偏差作為無監督聚類方法的輸入，進行二元分類，從而得到三路子拓撲的類型，根據三路子拓撲類型，進行剩余葉子節點的插入，最終恢復整個托普網絡；本發明的測量方法利用了反射的思想，可以應用到源節點不協作的情況；對于測量復雜度過大的問題，本發明中的拓撲推斷算法基于二分法，重復利用之前的測量結果中的信息，以減少測量冗余。

技術領域

本發明屬于網絡層析成像領域，具體涉及一種網絡拓撲發現方法。

背景技術

許多先前的研究都將直接測量方法應用到拓撲推理中。直接測量法利用內部節點的反饋信息，通過一些特殊的工具發現通信網絡的拓撲結構。然而，隨著人們對通信網絡隱私和安全問題的日益關注，這種方法受到了極大的阻礙。例如，traceroute是一個用于發現internet中從源節點到目標節點的中間路由器的工具。如果我們使用類似traceroute工具的測量結果來重建拓撲，首先需要解決的嚴重挑戰是匿名路由器和路由器別名，這限制了直接測量方法的應用。

作為一種替代方法，網絡層析成像應運而生。網絡層析成像是一種在直接測量不可用時，通過端到端測量(一種間接測量)發現網絡拓撲和診斷鏈路特定性能的強大技術。網絡層析成像的初始工作是基于多播測量的使用。多播探測很有吸引力，因為它只需要很少的探測包(其中N是拓撲中的路徑數)。然而，現實中能夠支持多播的節點很少，因此多播測量的方法變得不切實際。最近的工作大多基于單播測量。

端到端的測量(如時延、丟包率)被利用來獲得任意兩條路徑之間的相似度量，然后推理算法利用它們來恢復拓撲。在上述過程中，存在一個假設，即對于任何目的節點i、j、k，觀察到的相似性度量滿足s_i,js_j,k，當且僅當共享路徑滿足p_i,jp_j,k，這也被稱為單調條件。基于這一假設，近幾十年來提出了大量的拓撲推理算法。當拓撲規模不是很大時，單調條件是合理的。我們知道拓撲規模的大小直接關系到測量的復雜度和測量時間。當拓撲規模增大時，測量周期會很快的提高(對于兩兩測量為)，此時，這個假設就可能不成立，因為此時背景流量可能不具備一致性，背景流一致性指的是在測量期間，探測包經歷的背景流強度是基本不變的。其結果是，假設的違背會導致傳統方法錯誤的推斷。

在已有研究中，解決了這個假設違背的情況，并給出了理論證明，當獲取了所有三路子拓撲信息后，樹型拓撲一定可以推斷出來。那么關鍵的問題就是如何得到三路子拓撲的信息，即如何測量三路子拓撲。此外，在實際場景中，源節點可能出現不協作的情況，此時我們無法在源節點發包，這要求改進現有的探測方法。

基于三路子拓撲的推斷方法，輸入為三路子拓撲結構信息，在N條路徑的樹型拓撲中，一共有個三路子拓撲，若以此為輸入，則需要測量的三路子拓撲數量達到在網絡規模大的時候，這樣的測量復雜度幾乎不可接受的。

發明內容

為解決上述技術問題，本發明提出一種基于三路子拓撲測量的網絡拓撲發現系統與方法，其包括兩個板塊：(1)基于反射以及無監督聚類的三路子拓撲測量框架；(2)基于二分算法的網絡拓撲推斷系統。

基于反射以及無監督聚類的三路子拓撲測量框架用于測量由任意三條路徑組成的三路子拓撲結構(三路子拓撲所有可能的邏輯拓撲結構如圖3所示)。該測量框架包括兩個模塊：

(1)相似度量：相似度量細分為五個步驟

①數據包定制：每一次探測都會發出一個背靠背探測數據包(背靠背探測數據包由三個緊挨的探測數據包組成，如圖4所示)，將背靠背探測數據包中三個探測數據包的源IP地址分別修改為三路子拓撲中三個葉子節點的IP地址(如圖4中節點i、j、d的IP地址)，將目的IP地址修改為源節點(三路子拓撲的根節點，如圖4中節點S)的IP地址。