網絡斷層掃描中推斷分析理論與方法研究

摘 要：網絡斷層掃描是一種新的網絡測量技術，通過端到端的網絡外部測量來推斷網絡內部性能，從而克服了傳統網絡測量技術的諸多缺陷。推斷分析理論作為網絡斷層掃描的核心技術，直接關系到網絡測量的計算復雜度和推斷準確性。論述了網絡斷層掃描技術的基本概念，重點介紹并探討了目前推斷分析理論方法及其研究進展，最后提出了今后推斷分析理論需要研究和解決的關鍵問題。

關鍵詞：網絡斷層掃描； 網絡測量； 性能推斷

中圖法分類號：TP393文獻標識碼：A

文章編號：1001—3695(2007)02—0120—03

網絡測量（Network Measurement，NM）源于Internet的規模和復雜性的迅猛增長以及人們對于網絡性能測量和監視的需要，它通過對實際網絡環境的測量來研究當前網絡運行中存在的問題并提出解決辦法[1]。然而，傳統的NM是基于網絡內部的測量機制[2，3]，它需要網絡內部單元之間的協作但存在許多缺陷：它會給網絡帶來潛在的負載；它需要額外的通信和內部的協作而造成很大的開銷；出于安全等方面的考慮，它對網絡內部的訪問常常被ISP所限制。基于此，人們借鑒了醫學上的診斷工具CT的思想[4]，使NM的測試節點均為外部端節點而無須任何來自于網絡內部的協作。由端到端的路徑交叉來推斷其公共路徑上的諸多特性，這就叫作網絡斷層掃描（Network Tomography，NT） [5]。它把網絡看作黑盒子，通過對端到端通信行為的測量來推斷網絡內部鏈路性能特性。NT基于推斷分析理論，其目標就是以較小的網絡統計代價來揭示內在的網絡結構并發現局部的網絡擁塞、路由故障和網絡異常行為。顯然，基于外部測量的NT技術把對網絡的測量所造成的負載減小到最低程度。NT研究的問題有[6]：鏈路層延遲或丟包率估計；鏈路負載和吞吐量的評估；拓撲結構的發現。NT的測量過程分兩個階段：①數據采集。在端節點上進行觀測和收集測量數據，測量的方法有主動測量和被動測量，測量的通信方式有單播或多播。②數據分析。用統計推斷理論來確定網絡內部性能屬性。由此可知，推斷分析理論作為NT應用的核心技術，直接關系到NM的效率和準確性。本文在對NT技術的基本理論分析的基礎上，對目前主要的幾種NT推斷分析理論和方法進行了探究，并提出今后該領域所要研究和解決的幾個關鍵問題。

1 網絡斷層掃描的基本概念

為了測量鏈路，源節點發送數據包經共享路徑上若干個節點的傳送而到達目的節點。NT的測量問題常常近似地描述為線性模型[2，5]Y=Aθ+ε，其中的Y是個度量向量（如測量站點記錄包的計數或端到端的延遲），A是一個路由矩陣，而θ是待估的參數向量（如平均延遲），ε是誤差向量。為了簡化，常忽略ε并用關于待估參數θ的向量函數X代替上式中的θ，即

由于圖1中的A不是滿秩矩陣，不能直接解出θ_j。對于簡單的網絡，可對A進行擴充[7]，如利用節點2與節點3之間接收到包的相關性（條件概率），從中解出θ_j；對復雜網絡的NT問題要采用合適的推斷分析理論，使用已測得的數據并結合統計學上的推斷理論對未知參數進行估計。設θ為待估計的實參數，測量值Y是含N個樣本的一個向量y=(y₁，y₂，…，y_N)，通過使用N個樣本來得出該參數的一個值。每個分量yn是一個測量樣本，它表示同一隨機變量。一般的推斷過程模型如圖2所示。圖2中的概率密度函數f（y；θ）是參數空間和樣本空間之間的映射，表示數據y依賴于參數θ。這樣，通過選擇使測量值y具有最大概率的參數值來達到估計的目的。

2 推斷分析理論及方法研究

為了使NT推斷達到良好的效率和準確性，就要求所采用的推斷分析理論在計算復雜度與推斷準確性之間保持平衡[8]。以往的研究者在NT推斷中開發了不太理想卻是輕量級的算法：在組播結構中對于鏈路延遲分布推斷的快速遞歸算法和對OD（Original-Destination）矩陣推斷的矩方法（Method-of-Moments）。后來，人們開發了更準確的、計算上相對復雜的方法，這包括極大似然估計法（Maximum Likelihood Estimation，MLE）[9]、期望最大值（Expectation Maximum，EM）算法[10]、最大概似估計（Maximum-Pseudo Likelihood Estimation，MPLE）[8]和Bayesian推斷方法[11]等。

2.1 MLE方法

在給定測量值Y后，借助于式（1）就可以應用統計學上的MLE來估計θ的分量。其中的f(y;θ)=L(θ)為唯一待估計的參數θ的函數。估計值θ^使得似然函數取最大值，在隨機變量yn的獨立性假設條件下，似然函數為

當網絡節點數目很大時，要尋找確定的全局最優樹很困難，只能使用某些方法獲得次優解。可利用Monte Carlo Process[14]從全局而非局部的角度考查搜索方向，將搜索集中在具有最高似然概率的區域，其前提是假設從發送端到接收端的路由是固定的。

MLE在實際的運用中存在如下的缺陷：①如果似然函數（式（2））中關于θ不可微時，就無法求得θ的MLE值；如果可微時，所求似然方程的根不一定總是極大值點。②對于較大規模的網絡，要解決多維最大值化問題，用MLE會帶來極大的計算復雜度（如對似然函數求偏導會得到多個根的超越方程等）。

2.2 EM算法

EM算法是一種從不完全數據中求解模型分布參數的MLE的方法[15]，這種不完全數據有兩種：因觀測的缺陷所造成的數據錯漏；為了優化似然函數而引入額外的參數（隱含的或丟失的）。觀測數據相對于完全數據（觀測數據＋額外參數）就是不完全數據。在NT問題中，一般針對第二種情況。

一個子問題常常由一顆僅包含兩個葉節點的子樹所組成，而一顆子樹是通過選擇矩陣A的兩行來構成。如果用I表示葉節點的數量，那么子樹的總數就是I(I-1)/2。假設網絡拓撲的多播樹如圖4(a)所示，那么圖4(b)就是子問題及其邊緣似然函數的形成過程。

由上述可知，MPLE方法不但克服了MLE計算上的復雜度，而且還保持了良好的統計效率[5]。MPLE方法的關鍵是構建PLF，而在構建PLF時應注意：①每次也可選擇A中的三行或更多行構建一個PLF，但需保持計算復雜度和估計效率之間的平衡，一般都是選擇兩行來進行的。②理論上可選擇當前所有的對（Pairs）來構建PLF，為了克服計算難度，可以考慮選擇一個子集，但推斷的準確性較難保證。③將分治法（Divide-and-Conquer）的思想和概似方法相結合為大規模網絡NT推斷帶來希望，值得我們去研究。

2.4 Bayesian推斷

由統計學可知，Bayesian估計方法認為后驗分布集中體現了樣本和先驗分布所提供的關于總體信息的總和，因而估計應建立在后驗分布基礎上進行。在NT推斷中，Bayesian估計把先驗信息與樣本信息相結合得到后驗信息，再將其作為計算下一輪后驗的先驗信息，這樣不斷地迭代使后驗信息愈來愈接近真值。由于Bayesian的這種學習機制，起始時所采用的先驗信息對NM的影響隨著樣本增多而逐漸減弱。

由于NT問題的復雜性，尤其是當θ是一個多維向量時，很難直接計算E(f(θ)|D)的值。這時常常采用Monte Carlo積分法（它近似地計算Bayesian估計所需的后驗分布[18]），對潛在的后驗分布進行抽樣并使用樣本的平均值作為E(f(θ)|D)的近似值。而恰當的抽樣方法就是構建Markov鏈（狀態和時間參數都是離散的過程），構成Markov鏈的隨機變量是相關的，但其相關性表現在任一次試驗結果只依賴于上次結果[18]，其平穩分布完全等于P(θ|D)的后驗分布，這就是Markov Chain Monte Carlo[19]。在此，所采用的抽樣方法是Gibbs抽樣，這是因為Gibbs抽樣符合這種層次結構而常常用于Bayesian估計[18]。

由上述可知，Bayesian推斷不但解決了計算上的復雜性，而且其先驗信息可校正樣本所帶來的錯誤信息，只要先驗分布的方差足夠小，就能夠使NT的估計值趨于先驗信息。然而，所用的先驗分布如何取得及它能否反映網絡的實際是問題的難點。另外，由于對網絡內部狀況缺乏了解，推斷結果的有效性很難直接驗證，只能進行間接的驗證，這樣削弱了推斷效率。

3 總結與展望

盡管基于端到端的NT技術具有極其廣泛的應用前景，但縱觀目前的NT推斷分析理論和方法，仍存在一些關鍵問題有待于深入研究和解決：①這些理論和方法基本上都是在模擬環境中應用的，要應用到實際的網絡環境中，其可靠性、分布式同步測量和可測量性等問題需要進一步研究。②它們均基于空間和時間上的獨立性的假設條件，發展超越獨立性假設的推斷分析理論和方法是NT技術所面臨的最大挑戰。③這些理論和方法還不能做到對網絡進行實時在線、智能化測量。④它們大多是基于簡單網絡，還不能用于復雜的大規模互聯網絡環境。⑤它們都是針對有線網絡，還不能對動態網絡[4]（如Ad hoc網絡）進行推斷分析。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。