基于逐跳測(cè)量的IP鏈路性能評(píng)估方法

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

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

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

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

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

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

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

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

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

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

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

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

2.2 基于逐跳測(cè)量的故障定位方法

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

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

2.2.1 單點(diǎn)測(cè)量

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

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

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

上式成立條件是∏k∈[1,i-1]X(ek-1,k|s)不為0，即Δt內(nèi)s 與vi-1之間所有鏈路分組通過(guò)概率均不為0。計(jì)算遵循3個(gè)基本規(guī)則：①依序計(jì)算。按照i從1到n的順序依次計(jì)算一條路徑中所有鏈路分組通過(guò)率X(ei-1,i|s)，前提是該鏈路所有前驅(qū)鏈路分組通過(guò)率均不為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?？紤]動(dòng)態(tài)選路因素，該時(shí)間周期內(nèi)該鏈路的所有后繼鏈路均處于不可計(jì)算狀態(tài)，即從源點(diǎn)s角度無(wú)法確定其準(zhǔn)確的通阻狀態(tài)，不再計(jì)算這些后續(xù)鏈路的通阻狀態(tài)（但不影響從其他測(cè)量源點(diǎn)角度來(lái)測(cè)量并計(jì)算該鏈路）。若后續(xù)計(jì)算周期內(nèi)計(jì)算出X(ei-1,i|s)不為0，則該鏈路所有鏈路將退出不可計(jì)算狀態(tài)，繼續(xù)進(jìn)行計(jì)算。③最高限值。X(ex,y|s)取值范圍為[0,1]，若利用算式(2)計(jì)算X(ex,y|s)取值大于1時(shí)，則應(yīng)近似表示為1。

2.2.2 多點(diǎn)測(cè)量

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

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

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

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

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

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

3 結(jié)論

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