基于逐跳測量的IP鏈路性能評估方法

魏鎮韓,江蘭,劉桂英

（解放軍75842部隊，廣東廣州 510500)

隨著IP 網絡快速發展，及時有效地判斷IP 鏈路擁塞或故障狀況對網絡運維及管理具有重要意義。網絡斷層掃描(Networks Tomography,NT)[1]根據網絡邊界的測量信息來分析和推斷網絡內部的性能及狀態，網絡測量節點均為外部端節點，在沒有網絡節點協作的條件下，把網絡看作一個黑盒子，通過端到端路徑的性能指標結合不同端到端路徑之間的交叉狀況，推斷網絡內部鏈路的性能參數[2-3]。其目標是以較小網絡統計代價來揭示局部網絡擁塞、路由故障及異常情況。本文簡要分析了傳統NT 技術的局限，提出了一種簡便的分布式IP鏈路故障評估方法。

1 傳統NT的應用局限

從源點s向目標d發送測量分組，令分組轉發路徑為p，時間Δt內分組成功通過該路徑的概率為t(p)，通過某鏈路e∈p的概率為t(e)，設各鏈路分組通過率相互獨立，則存在表達式即一條路徑的分組通過概率為其各鏈路分組通過概率的積，上式兩端取對數，令Yp=logt(p)，Xe=logt(e)，可轉化為線性表達式選取不同s和d進行測量，記錄相應Yp作為已知變量，所有相關Xe均為未知變量。設有m條路徑進行了測量，其中涉及n條鏈路，則可形成n元線性方程組（常以矩陣形式表達）。NT 基本思想即通過求解上述n元線性方程組來獲取各鏈路的分組通過概率，不同研究中分別采用高斯消元[4]、逆矩陣[5-6]和增廣矩陣[7]等代數方法進行求解。

實踐中若鏈路出現阻斷則對傳統NT技術造成嚴重不利影響。鏈路阻斷后路由器短時間內重新選擇路由，源點到目標的分組轉發路徑發生變化，難以及時確定路徑與鏈路準確的對應關系，無法建立準確的測量方程，更不利的是若路由更改后原有端到端測量仍能成功完成，則NT 技術完全無法察覺發生鏈路阻斷。

從應用角度來看，目前各種網絡斷層掃描技術多為模擬環境下的理論研究，簡化了實際網絡運行機制，僅將IP 網絡理解為一個簡單拓撲圖；同時過于依賴各種數學模型，缺乏對網絡底層技術機理深入探討和融合，導致在應用可靠性和網絡可測量性上均存在較大限制[8]，長期以來無法真正實用化。為解決此突出問題，本文深入研究了路由器動態選路的內在機制，設計一種基于逐跳測量中間路由器接口的方式來實現鏈路性能及阻斷的評估判斷。

2 逐跳測量的鏈路故障定位技術

2.1 基于中間路由器端口可達性判斷鏈路阻斷

Ping 獲取的是端到端（通常跨越多個IP 鏈路）通阻數據，需進一步獲得鏈路級通阻數據。如圖1所示，從源點S依次向端口地址a11、a21、a31、a41發送Ping分組，正常情況下均能獲得成功響應。當R2與R3之間的IP鏈路出現某種故障時（如線路故障、路由器本身故障、端口故障、協議配置不當等），無論實踐還是仿真結果都能驗證下列結果：源點S 無法正常Ping 通地址a31（此時動態選路協議不更新直連網段的路由表項，因此該端口即使處于激活狀態也不存在迂回路由）；地址a11、a21仍能Ping 通，而地址a41經動態選路更新后若存在迂回路由則能Ping通。

圖1 基于Ping獲取IP鏈路級的通阻數據

得出如下結論：使用Ping依次測量一條穩定的分組轉發路徑上的路由器接口地址，相繼觀察返回結果，若某個接口無法Ping 通，則反映了其直連IP 鏈路存在故障。據此可設計一種基于Ping的測量方法，將IP 端到端/路徑級的測量結果解析為鏈路級通阻數據。

2.2 基于逐跳測量的故障定位方法

表1定義了網絡測量模型，Ri表示路由器，vi表示其接口地址，ex,y=(Ri,vy)表示兩個路由器之間的直連鏈路，通常使用測量分組進入路由器的接口地址標識路由器，而在多點測量環境中某鏈路的第一個路由器Ri可能具有多個分組進入接口，而該鏈路的第二個路由器的直連接口vj是確定的。s∈S表示測量源點，一般是位于中心機房附近的一臺計算機終端；d∈D表示測量目標，一般是各維護方向上的使用終端。

表1 網絡測量模型描述

2.2.1 單點測量

針對特定測量源點s和目標節點d，假設從s到d所途徑的穩定轉發地址為p(s,d)=(v1,v2,...,vn)，測量周期Δt內從s向v1...vn分別發送測量分組，可直接獲取一系列子路徑的分組通過概率：

設各鏈路分組通過率相互獨立，則一條測量路徑的分組通過概率等于該路徑各鏈路分組通過概率之積,令s=v0，則對于特定i∈[1,n]，存在下式：

利用上述兩式可依次計算各相關鏈路的分組通過概率：

上式成立條件是∏k∈[1,i-1]X(ek-1,k|s)不為0，即Δt內s 與vi-1之間所有鏈路分組通過概率均不為0。計算遵循3個基本規則：①依序計算。按照i從1到n的順序依次計算一條路徑中所有鏈路分組通過率X(ei-1,i|s)，前提是該鏈路所有前驅鏈路分組通過率均不為0。②阻斷判斷。較傳統NT技術，本方法具備確定性鏈路阻斷判斷手段，在(2)式中，若Y(s,vi)為0 而X(e0,1|s)直至X(ei-2,i-1|s)均不為0，則判斷鏈路ei-1,i處于阻斷狀態：X(ei-1,i|s)=0。考慮動態選路因素，該時間周期內該鏈路的所有后繼鏈路均處于不可計算狀態，即從源點s角度無法確定其準確的通阻狀態，不再計算這些后續鏈路的通阻狀態（但不影響從其他測量源點角度來測量并計算該鏈路）。若后續計算周期內計算出X(ei-1,i|s)不為0，則該鏈路所有鏈路將退出不可計算狀態，繼續進行計算。③最高限值。X(ex,y|s)取值范圍為[0,1]，若利用算式(2)計算X(ex,y|s)取值大于1時，則應近似表示為1。

2.2.2 多點測量

若鏈路ex,y僅存在于某特定源點的一條或多條測量路徑中，則直接按式(3)計算其分組通過概率。若ex,y存在于多個測量源點s1,...,sm的不同測量路徑中，則其特征是從m個源點到節點地址vy的m條測量路徑p(sk,vy)中的最后一條鏈路皆為ex,y，k∈[1,m]。令S={s1,...,sm},由m個源點向節點地址vy分別發送測量分組，則根據式(2)有：

Y(sk,vy)直接由測量獲取，設ex,y所有前驅鏈路均已計算出各自分組通過率，則上式存在m個方程1個未知量，屬于超定方程組，無法直接計算X(ex,y|s)值，需求其最小二乘解。

構造如下正規方程組：

其中，AT=[a1a2..am]為A 的轉置向量，則求解該正規方程組可得：

該解即為(5)式超定方程組的最小二乘解。故多個源點下某共同鏈路的分組通過率計算公式為：

若m條測量路徑中ex,y的各個前驅鏈路分組通過率均不為零，上式可簡化為：

3 結論

為解決傳統NT技術無法有效感知阻斷鏈路的問題，本文討論了路由器端口可達性與鏈路故障之間的內在關聯（對特定測量點而言），據此設計了一種分布式輕量級主動測量機制，通過簡單的Ping測量逐跳獲取中間路由器接口的響應數據，推導出分布式測量環境中鏈路分組通過率的計算公式來快速識別故障鏈路。實踐中，一線維護人員只需要進行一些簡單網絡配置即可實現IP 鏈路級分組通過率的自動監測和分析，具有較高的應用價值。