魏鎮(zhèn)韓,江蘭,劉桂英

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

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

1 傳統(tǒng)NT的應(yīng)用局限

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

實踐中若鏈路出現(xiàn)阻斷則對傳統(tǒng)NT技術(shù)造成嚴(yán)重不利影響。鏈路阻斷后路由器短時間內(nèi)重新選擇路由，源點到目標(biāo)的分組轉(zhuǎn)發(fā)路徑發(fā)生變化，難以及時確定路徑與鏈路準(zhǔn)確的對應(yīng)關(guān)系，無法建立準(zhǔn)確的測量方程，更不利的是若路由更改后原有端到端測量仍能成功完成，則NT 技術(shù)完全無法察覺發(fā)生鏈路阻斷。

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

2 逐跳測量的鏈路故障定位技術(shù)

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

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

圖1 基于Ping獲取IP鏈路級的通阻數(shù)據(jù)

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

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

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

表1 網(wǎng)絡(luò)測量模型描述

2.2.1 單點測量

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

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

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

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

2.2.2 多點測量

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

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

構(gòu)造如下正規(guī)方程組：

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

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

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

3 結(jié)論

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