基于葉節(jié)點DFS序列的網絡拓撲推斷算法

石佳玉，吳辰文，孔德弟，張耀方

（蘭州交通大學 電子與信息工程學院，甘肅 蘭州730070）

0 引 言

本文的具體重點是減少拓撲推斷過程中需要的成對探測包的總數，以便高效地解決網絡拓撲重構的問題。本文針對單播斷層掃描［1］探測方法，只需要外部端到端節(jié)點的基本測量，不需要中間節(jié)點的協(xié)作［2］。利用葉節(jié)點的深度優(yōu)先搜索 （DFS）序列［3］，以下簡稱葉節(jié)點的DFS 序列，并且巧妙的利用了相關性矩陣的特殊結構，找出具有共同祖先節(jié)點的葉節(jié)點，有效的減少成對探測包的數量，提高了拓撲推斷的效率。對于一個平衡 叉樹，以往所研究的基于聚類算法［2］的單播網絡斷層掃描拓撲推斷技術需要的成對探測包的數量級為O（N2），且需要滿足的假定條件太過嚴格，本文提出的利用葉節(jié)點DFS序列來推斷拓撲結構的算法，只使用數量級為O（Nlog（N））的成對探測包，且明顯的減少了相關性條件的限制，降低了算法的復雜度。

1 深度優(yōu)先搜索 （DFS）序列

使用深度優(yōu)先搜索 （DFS）方法遍歷一棵 叉樹的規(guī)則是先從根節(jié)點開始，然后逐步向下搜索每一個節(jié)點，并且標記每個節(jié)點，然后回溯，直到所有的節(jié)點被充分遍歷（即每個孩子節(jié)點已被標記）。這樣，一棵樹的每個葉節(jié)點被遍歷的先后順序就會有所不同，我們將通過深度優(yōu)先搜索的方法遍歷得到的葉節(jié)點的排序稱為深度優(yōu)先搜索（DFS）序列。

定義 一個DFS序列，πDFS：｛1.2，…N｝→ ｛1.2，…N｝，在一個邏輯樹結構T 中，按照深度優(yōu)先搜索方法找到的葉節(jié)點的排序，同時也揭示了其內部節(jié)點的深度優(yōu)先搜索順序。

如圖1所示，我們可以發(fā)現下面的DFS序列，所有這些序列都對應特定的深度優(yōu)先搜索樹的拓撲結構：

圖1 簡單的邏輯拓撲結構中的DFS序列

同時也有很多不滿足深度優(yōu)先搜索順序的葉節(jié)點序列，如 ｛a，c，d，b｝.以上面DFS序列中的 ｛a，b，c，d｝為例，我們可以找到這組葉節(jié)點滿足的共享路徑矩陣PDFS

將共享路徑的長度記為pi，j，即從根節(jié)點到這兩個葉節(jié)點xi，xj之間共享路徑中的共享節(jié)點的數量。如下面矩陣所示，PDFSa，b＝2表示從根節(jié)點到葉節(jié)點a，b有兩個共享節(jié)點 （如圖1所示）。以 ｛a，c，d，b｝為例，不滿足DFS序列的共享路徑矩陣PNotDFS如下所示

將網絡中的兩個終端記為xi，xj。利用斷層掃描技術，可以測量到端節(jié)點之間的成對相關性［4］，記為si，j（例如，兩個端節(jié)點之間的時延協(xié)方差和丟包率等）我們將重點放在這些成對的相關性是如何在特定的條件下生成與之符合的底層網絡樹的拓撲結構。

命題1：給定一組葉節(jié)點DFS序列，則共享路徑矩陣P 滿足如下條，pi，i＋1≥pi，i＋k，k＝｛1，2，…，N－i｝，i＝｛1，2，…，N－1｝。

證明：假設pi，i＋j≤pi，i＋k（0≤j≤k），則說明葉節(jié)點xi與xi＋j比葉節(jié)點xi和xi＋k具有更多的共享節(jié)點，即具有更長的共享路徑。然而，在使用深度優(yōu)先搜索方法遍歷拓撲樹的過程中，要求j＞k，也就是說節(jié)點xi＋k較節(jié)點xi＋j先被遍歷，這與我們的假設相違背。因此，如果葉節(jié)點的序列滿足DFS排序，則命題1的結論成立。

2 算法描述

本算法分為兩個主要部分：使用遞歸二分法找出葉節(jié)點的DFS序列；使用DFS序列推斷邏輯拓撲樹的結構。

2.1 遞歸二分法找出葉節(jié)點的DFS序列

假設我們所使用的斷層掃描方法符合下述單調條件，即測量得到的相關性矩陣S和共享路徑矩陣P 滿足下述單調條件。

單調條件：對于所有的葉節(jié)點i，j，k，所測量到的相關性滿足si，j＞sj，k＋δ（δ＞0），當且僅拓撲樹的共享路徑滿足pi，j＞pj，k。

給定一組葉節(jié)點的隨機順序，選擇一個葉節(jié)點（xi），并且獲取這個葉節(jié)點和其它葉節(jié)點 （＝ ｛s1，2，s1，3，s1，4，…，s1，N｝）的成對相關性。其中，一些葉節(jié)點與xi有很高的相關性，另一些因為與xi只有較少的共享節(jié)點，所以具有較低的成對相關性。然后將這些相關性值進行排序，將具有較多共享節(jié)點的葉節(jié)點放置在一個集合中，將具有較少共享節(jié)點的葉節(jié)點放置在另一個集合中，我們將葉節(jié)點xi稱為優(yōu)勢點，利用優(yōu)勢點得到偏序列，π：｛2，3，…，N｝→｛2，3，…，N｝（s1，πi≥s1，πi＋j，j≥1），但這個偏序不能被認為是DFS序列，如圖2所示。

圖2 利用一個葉節(jié)點所得到的偏序列

比較所劃分的這些葉節(jié)點簇，簇與簇之間的相關性值相差一定的幅度δ，如圖3 所示。然而，只使用一個優(yōu)勢點并不能估計出這些簇中節(jié)點的DFS序列。這只是利用其中一個葉節(jié)點與其它葉節(jié)點的相關性所判斷得到的，因此，還需要另外一些節(jié)點的成對相關性才能正確的排序整個葉節(jié)點集合。從圖3中可以看出，任何簇之間相關性都有一個δ的偏差，在 ｛CA，CB，CC｝這3個值中。在這3個簇的基礎上正確排序這些葉節(jié)點，然后再排序這些子簇。利用相關性劃分這些葉節(jié)點，劃分成每個簇，然后在每個簇中重復這種探測過程，即運用子簇中新的優(yōu)勢點以及節(jié)點之間的成對相關性重新排序這些子簇中的節(jié)點。使用遞歸二分法減少了我們尋找葉節(jié)點DFS序列的難度。

圖3 不同葉節(jié)點簇之間的相關性差

對于給定邊值δ的節(jié)點簇，使用這種二分法相對簡單，只需排序相關性值并且找到所有可能的平分點。以節(jié)點x1為例，定義集合Ι，i∈Ι，如果到第i個偏序列πi與第i＋1個偏序列πi＋1之間的相似性大于δ，則說明這兩個節(jié)點集合具有不同的父節(jié)點

平分的點即優(yōu)勢點，設為葉節(jié)點i＊，i＊∈Ι，這樣葉節(jié)點被分為兩個葉節(jié)點集合XA＝｛x1，xπ1，xπ2，…，xπi＊｝和

算法1：尋找葉節(jié)點DFS序列

（1）通過排隊時延或時延協(xié)方差［5］找出葉節(jié)點x1與其它葉節(jié)點的相關性值，并列出成對相關性矩陣S。

（2）比較相關性值的大小，找出偏序列π：｛2，3，…，N｝→｛2，3，…，N｝。

（3）找出集合I＝｛i：s1，πi－s1，πi＋1≥δ｝

（4）找到評分點i＊，使用二分法，將葉節(jié)點集合X 劃分 為 集 合XA＝｛x1，xπ1，…，xπi＊｝和XB＝｛xπi＊＋1，…，xπN－1｝。

使用上述迭代二分法可以成功找出葉節(jié)點的DFS 序列。利用葉節(jié)點的DFS序列，我們提出了下述DSTD 算法來推斷網絡拓撲結構。

2.2 DSTD算法推斷邏輯拓撲

條件1：測量到的相關性矩陣S 和共享路徑矩陣P 滿足單調性條件，如果對于所有的葉節(jié)點i.j.k滿足共享路徑pi，j＞pj，k，那么所觀測 到的相關性 滿足si，j＞sj，k。

由命題1和條件1得到，相關性矩陣S和共享路徑矩陣P的結構緊密相關。

命題2：給定一組葉節(jié)點 ｛x1，x2，…，xN｝的DFS序列，相關性矩陣滿足單調條件，那么相關性矩陣將有以下屬性

圖4 DSTD 算法中合并每個葉子節(jié)點

定理 若葉節(jié)點DFS 序列和成對相關性滿足單調條件，則只需要N－1 對探測包 （相關性值Si，i＋1，i＝ ｛1，2，…，N－1｝）來重構邏輯拓撲樹。

證明：由單調條件可知，在一個子簇中，找到具有最大相關性值的一對葉節(jié)點，也就找到了具有最大共享路徑的一對葉節(jié)點。對于N 各葉節(jié)來說，使用以往的方法獲得所有需要的相關性值的數量級O（N2）。但是，在已獲得葉節(jié)點的DFS序列和已知單調條件的情況下，只需要知道與葉節(jié)點xi（i＝｛1，2，…，N｝）直接相鄰的兩個葉節(jié)點xi－1和xi＋1之間的相關性值 （即si，i－1和si，i＋1需要）來推斷出合理的拓撲結構。由命題2可知，對任意的j＞1，每個葉節(jié)點的相關性值si，i＋1＞si，i＋j，因此，與葉節(jié)點xi具有最大的共享路徑的氣體葉節(jié)點只能是與其相鄰的xi＋1或xi－1。

算法2：描述

已知：利用算法1找到的葉節(jié)點的DFS序列X ＝｛x1，x2，…，xN｝，并列出葉節(jié)點的成對相關性值序列， ｛s1，2，s2，3，s3，4，…，sN－1，N｝

輸入：拓撲樹節(jié)點集，V ＝｛x1，x2，…，xN｝

樹的邊集，E ＝

重構拓撲樹，T ＝（V，E）

邊節(jié)點集，Y ＝｛x1，x2，…，xN｝

For k＝ ｛1，2，…，N－1｝

（1）找出

（3）創(chuàng)建新的內部節(jié)點，x＊

（4）將新的內部節(jié)點加入到節(jié)點集中，V ＝V ∪x＊

（5）加入新的邊到新的內部節(jié)點，E＝E∪｛Yj，x＊｝∪｛Yj＋1｝

（6）參考舊的內部節(jié)點，找出邊節(jié)點集，I ＝｛i：Yi＝Yjor Yj＋1｝

（7）更新邊節(jié)點，Yi＝x＊for all i∈I

（8）更新相關性值，重復選擇相關性值，設sj，j＋1＝0

輸出：所估計的邏輯拓撲樹結構，T。

3 仿真實驗與性能分析

3.1 仿真實驗

在不同大小的網絡環(huán)境中，進行大量的仿真實驗，用來比較本文算法與目前常用的聚類算法的探測數量。為了避免網絡性能的不同所造成的偏差。實驗是在無噪聲的前提下進行，不同拓撲結構的每條鏈路的相關性值設為隨機的，共享路徑矩陣P均滿足δ－Margin邊距條件，且設定δ＝0.1。每個不同大小的網絡所使用的最終數據均是由100個隨機測量結果產生的。本實驗采用緊接分組隊的測量方法，采用時延協(xié)方差作為相關性參數。仿真結果對比圖如圖5所示，橫坐標表示網絡的大小，縱坐標表示拓撲推斷中所需要的成對探測包的數量。由圖5 可知，本文所提出的DSTD 算法所需要的成對探測包的數量低于目前常用的聚類算法的15%，很大程度的提高了拓撲推斷的效率。

圖5 DSTD 算法與傳統(tǒng)聚類算法的探測量的比較

3.2 性能分析

在已知葉節(jié)點的DFS序列的情況下，只需要N－1數量的成對探測包，若未知葉節(jié)點的DFS序列，則需要pN log1N 數量的成對探測包，其中

證明：

表1 聚類算法與DSTD 算法性能比較

4 結束語

本文提出的基于葉點DFS序列的DSTD 算法有效的減少了拓撲推斷中所需的成對探測包的數量，提高了網絡拓撲推斷的效率，充分發(fā)揮了網絡斷層掃描技術不需要中間節(jié)點的協(xié)作的優(yōu)勢。通過計算和仿真實驗證明，本算法需要的成對探測包的數量低于先前聚類算法需要的成對探測包數量的15%，有效的減少了測量流量，降低了因測量流量過大而造成的推斷誤差。

［1］ZHAO Honghua，CHEN Ming.Based tomography topology inference［J］.Computer Engineering，2009，35 （2）：92－95 （in Chinese）.［趙洪華，陳鳴.基于層析成像技術的拓撲推斷［J］.計算機工程，2009，35 （2）：92－95.］

［2］WU Wenjia，ZHANG Jianzhong.Based on the measured end to end network topology inference algorithm ［J］.Journal of Xiamen University，2010，49 （1）：34－37 （in Chinese）. ［吳 文佳，張建中.基于端到端測量的網絡拓撲推斷算法研究 ［J］，廈門大學學報，2010，49 （1）：34－37.］

［3］Brian Eriksson，Gautam Dasarathy，Paul Barford，et al.Efficient network tomography for internet topology discovery ［J］.IEEE／ACM Transactions on Networking，2012，20 （3）：931－943.

［4］ZHAO Honghua，CHEN Ming.Topology inference based on tomography ［J］.Journal of Software，2010，21 （1）：133－146 （in Chinese）.［趙洪華，陳鳴.基于王網絡層析成像技術的拓撲推斷 ［J］，軟件學報，2010，21 （1）：133－146.］

［5］ZHAO Honghua，HU Guyu，NI Guiqiang.A network topology inference algorithm based on 4－tupl packets measurement［J］.Journal of Beijing University of Posts and Telecommunications，2012，35 （2）：126－130 （in Chinese）. ［趙洪華，胡谷雨，倪桂強.基于四元分組測量的網絡拓撲推斷算法 ［J］.北京郵電大學學報，2012，35 （2）：126－130.］

［6］LI Guishan，CAI Wandong.Network link time delay distribution estimation method ［J］.Computer Engineering and Appli－cations，2009，45 （8）：21－28 （in Chinese）.［李貴山，蔡皖東.網絡鏈路時延分布估計方法研究 ［J］.計算機工程與應用，2009，45 （8）：21－28.］

［7］Srinivas Gorur Shandilya，Marc Timme.Inferring network topology from complex dynamics ［J］.New Journal of Physics，2011 （13）：1－12.