基于聚類技術的NT網絡拓撲推測方法研究

摘要：網絡拓撲推測是網絡管理中一項非常重要的技術，及時獲取準確的網絡拓撲對于改進網絡協議和優化網絡性能起著關鍵的作用。本文首先給出了NT的概念、依賴樹模型，然后用聚類算法計算兄弟節點的度量函數值，最后在此基礎上提出了完整的基于聚類技術的NT網絡拓撲推測算法，該算法有著廣泛的適應能力和擴展能力。

關鍵詞：聚類 網絡斷層掃描 網絡拓撲推測

1 概述

網絡拓撲對于改進網絡協議、優化網絡性能和方便網絡管理起著非常重要的作用，但是隨著網絡規模的不斷擴大、異構性與復雜性的提高，傳統測量方法面臨一些困難。為了彌補傳統網絡拓撲測量方法的不足，近幾年國際上提出了網絡斷層掃描技術(Network Tomography，NT)，它是將醫學、地震學、地質勘探等領域成功應用的成熟理論和方法應用于網絡領域所形成的技術，其本質是把網絡看作黑盒子，通過對端到端測量，利用兄弟節點的性能相關性強于非兄弟節點相關性這一特性，借助數理統計和概率論相關知識來推斷網絡拓撲。

使用多播依賴二叉樹模型來描述網絡的邏輯拓撲結構，如圖1所示。依賴樹中的基本術語和數據結構中的二叉樹基本相同，丟包分布符合貝努利模型，節點4、5、6和7是葉節點，在這里稱其為觀測節點或接收節點，節點0為探測數據包的發送節點。

用隨機過程Xk(n)｛k∈V;n=1，2，3，…，N;Xk(n)∈(0，1)｝表示報文的接收情況。每個節點的報文序列長度為N，內容為0-1序列。

在網絡性能測量過程中，重點要對網絡內部節點經過的數據包進行推測，基于多播依賴樹描述，其原理如下：

1.1 父節點上沒有流過的探測數據包，其孩子節點（接收節點或觀測節點）也肯定收不到。

1.2 孩子節點收到的數據包在父節點上肯定經過。

以圖1為例，說明一下推測父節點探測包的過程，圖中節點2是節點4和5的父節點，假設節點4的報文序列為(11010111001111)，而節點5的報文序列為(11100101001111)，則節點2的報文序列為：

X2(n)= X4(n)∪X5(n)=(11110111001111) （1）

2 基于聚類分析的兄弟節點度量

在某次測量過程中，探測報文從發送節點自頂向下被發送到網絡中的每個節點，只有布置在網絡邊緣的接收節點才可以觀測到報文丟失情況，通過報文丟失情況推測網絡邏輯拓撲結構。由于在葉節點集合內兄弟節點的相似性大于非兄弟節點，所以首先要確定葉節點間的距離函數，根據距離函數判定哪兩個節點屬于兄弟節點，然后根據這兩個兄弟節點的報文丟失情況來推測父親節點的報文丟失情況。在測量過程中，由于待測網絡的突發性和不穩定性，導致在接收端的數據在某些性能上產生了較大的差異。本論文中將采用上述思想和方法對在接收節點的數據進行聚類分析，抽取性能較為穩定且相似的數據作為主要推測數據。

本文提出基于聚類技術的NT拓撲推測(Logic Tree Based on Clustering，LTBC)的方法，該方法的主要思想是：首先要對接收節點的數據進行聚類分析，計算兩兩節點間的相似度，然后再進行父節點推測，如此反復，就可推測出整個網絡的拓撲結構。

2.1 分析葉節點的接收數據

由于在探測包發送的過程中，物理線路長、中間通過路由節點過多（瓶頸問題）、在上網高峰期路由轉發能力下降和線路老化等很多原因都會造成網絡時延變大，這就導致在接收節點收到的數據的時延增大。在測量的過程中，雖然同一類型的數據包在其共享鏈路上有著相同的特性，但是由于某些不確定因素會導致數據包的性能差異較大，在相對穩定的網絡環境下的測量數據對拓撲推測有著更重要的意義。為此在接收點對數據的時延首先進行聚類分析，使得簇內的數據時延相差較小，簇間的數據時延相差較大，然后計算兩個節點之間簇的距離當作兄弟節點間的相似度。在發送節點發送m個數據包，用di(i∈m)表示每一個數據包的時延，如表1所示：

下面是聚類算法的思想：①任意選擇k個數據作為初始簇的中心。②初始化nij=0。③如果|■ij-dm|≤εi。④則Pi∈Cij；nij=nij+1。■i=■。⑤將數據寫入簇數據庫，并置其值為1，否則為0。⑥如果該數據不屬于上面的簇，則使用上面的方法計算是否屬于下一簇。⑦重復③、④、⑤和⑥直到所有的數據都加入到簇中。

2.2 兄弟節點間的度量函數 由上面分析我們知道，在每個接收點根據數據包的時延將數據劃分為k簇，最后將所有接收節點的數據經過劃分的簇放到一個數據庫里。聚類數據庫中行為簇名，列為包的序號，每一個接收節點都產生了k個長度為m的0-1序列，則接收節點的數據轉化為一個二元變量數據庫，稱其為聚類二元變量數據庫，如表2所示。

表中每個數據包在任何一個節點中的屬性只有兩個值：0表示該報文沒有被接收節點接收，反之為1。這里采用基于二元變量的相異度計算方法，用公式2進行簇間相異度計算。

（2）

其中：

基于二叉樹模型，共享鏈路越多，節點相異度越小，在進行兩個節點的相異度計算時，每個接收節點的某個對象（簇）都與另一個節點的全部對象進行相異度計算。最后取其平均值，如公式2所示。

（3）

其中l表示節點i的簇的個數，k表示節點j的簇的個數。

3 樹狀拓撲結構推測算法

在拓撲推測過程中，首先從葉節點集合中計算所有葉子節點的相異度，并選擇相異度最小的兩個葉子節點作為兄弟節點，推測父節點的報文丟失情況，在葉節點集合中用構建的父節點代替這對兄弟節點，重復上述過程直至節點集合內剩下一個節點為止。

具體算法如下：

輸入：葉節點集合R包括葉節點接收報文情況和聚類二元變量數據庫和鏈路數據庫。

①計算q、t、r的值。②計算葉節點集合兩兩元素之間的Dij值，并從中找尋最小的Dij。③在葉集合R中加入新的節點n為節點i和j的父親節點，并將節點i和j從集合R中除去。④將鏈路(n→i)和(n→j)加入鏈路數據庫中。⑤估計新加入父親節點n的報文接收情況。⑥重復①、②、③、④和⑤步驟，直到葉節點集合中剩下一個元素。

輸出：根據父子關系得到網絡的邏輯拓撲結構。

4 結論

本文提出了基于聚類技術的NT網絡拓撲推測算法，通過聚類技術可以剔除了由于網絡的突發性和不穩定性而造成的錯誤數據，從而保證了網絡拓撲推測的正確性和高效性。本文所涉及的都是二叉樹模型的網絡拓撲推測，如何將此算法推廣到一般樹狀結構以及如何提高推測的準確度將是下一步研究的課題。

參考文獻：

[1]王志剛，王汝傳等.網絡拓撲發現算法的研究[J].通信學報2004，25(8):36-43.

[2]王偉莉，陳雷.網絡拓撲發現算法的研究與實現[J].沈陽工業大學學報2004，26(2):211-214.

[3]林文，林俊武.一種基于多播推測丟包率的算法.計算機與現代化，2009，1(6):9-12.

[4]李勇軍，蔡皖東，王偉等.基于端到端報文丟失的網絡拓撲推測算法研究.通信學報，2007，28(10):85-91.

[5]Yi Sun，Dong Li，Hongjie Sun Network Tomography and Improved Methods for Delay Distribution Inference.ICACT，2007:1433-1437.

[6]Nick Duffield.Network Tomography of Binary Network Performance Characteristics.IEEE 2006，52(12):5373-5388.

[7]Feng Qian，Guang-min Hu，and Xing-miao Yao.Unicast Network Loss Tomography using #R-cast Probes Scheme.IEEE，2009: 113-117.