基于逐跳测量的IP链路性能评估方法

摘要：传统网络断层扫描技术仅依靠端到端测量无法有效判断动态选路语境下的IP链路阻断，长期以来存在实用性不高的问题。该文提出一种轻量级的分布式主动探测机制，逐跳测量IP路径的中间路由器接口，根据返回结果推导出分布式测量环境下IP链路分组通过率计算公式，能有效用于运维中实时观测网络基本运行质量并快速定位出现故障的链路。

关键词： 网络断层扫描；IP网络；主动测量；分组通过率

中图分类号：TP393        文献标识码：A

文章编号：1009-3044（2023）25-0011-03

开放科学（资源服务）标识码（OSID） ：

随着IP网络快速发展，及时有效地判断IP链路拥塞或故障状况对网络运维及管理具有重要意义。网络断层扫描（Networks Tomography， NT）[1]根据网络边界的测量信息来分析和推断网络内部的性能及状态，网络测量节点均为外部端节点，在没有网络节点协作的条件下，把网络看作一个黑盒子，通过端到端路径的性能指标结合不同端到端路径之间的交叉状况，推断网络内部链路的性能参数[2-3]。其目标是以较小网络统计代价来揭示局部网络拥塞、路由故障及异常情况。本文简要分析了传统NT技术的局限，提出了一种简便的分布式IP链路故障评估方法。

1 传统NT的应用局限

从源点s向目标d发送测量分组，令分组转发路径为p，时间[Δt]内分组成功通过该路径的概率为t（p），通过某链路[e∈p]的概率为t（e），设各链路分组通过率相互独立，则存在表达式：[t（p）=e∈pt（e）]，即一条路径的分组通过概率为其各链路分组通过概率的积，上式两端取对数，令[Yp=logt（p）]，[Xe=logt（e）]，可转化为线性表达式：[Yp=e∈pXe]。选取不同[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通。

得出如下结论：使用Ping依次测量一条稳定的分组转发路径上的路由器接口地址，相继观察返回结果，若某个接口无法Ping通，则反映了其直连IP链路存在故障。据此可设计一种基于Ping的测量方法，将IP端到端/路径级的测量结果解析为链路级通阻数据。

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

表1定义了网络测量模型，Ri表示路由器，[vi]表示其接口地址，[ex，y=（Ri，vy）]表示两个路由器之间的直连链路，通常使用测量分组进入路由器的接口地址标识路由器，而在多点测量环境中某链路的第一个路由器Ri可能具有多个分组进入接口，而该链路的第二个路由器的直连接口[vj]是确定的。[s∈S]表示测量源点，一般是位于中心机房附近的一台计算机终端；[d∈D]表示测量目标，一般是各维护方向上的使用终端。

2.2.1 单点测量

针对特定测量源点s和目标节点d，假设从s到d所途径的稳定转发地址为[p（s，d）=（v1，v2，...，vn）]，测量周期[Δt]内从s向[v1...vn]分别发送测量分组，可直接获取一系列子路径的分组通过概率：

[Y（s，vi）=R（s，vi）/N（s，vi），i∈[1，n]]       （1）

设各链路分组通过率相互独立，则一条测量路径的分组通过概率等于该路径各链路分组通过概率之积，令[s=v0]，则对于特定[i∈[1，n]]，存在下式：

[Y（s，vi）=k∈[1，i]X（ek-1，k|s）]    （2）

利用上述两式可依次计算各相关链路的分组通过概率：

[X（ei-1，i|s）=Y（s，vi）/k∈[1，i-1]X（ek-1，k|s）]  （3）

上式成立条件是[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（s1，vy）=（ep，q≺ex，y∈p（s1，vy）X（ep，q|s1））⋅X（ex，y|S）Y（s2，vy）=（ep，q≺ex，y∈p（s2，vy）X（ep，q|s2））⋅X（ex，y|S）......Y（sm，vy）=（ep，q≺ex，y∈p（sm，vy）X（ep，q|sm））⋅X（ex，y|S）]  （4）

[Y（sk，vy）]直接由测量获取，设[ex，y]所有前驱链路均已计算出各自分组通过率，则上式存在m个方程1个未知量，属于超定方程组，无法直接计算[X（ex，y|s）]值，需求其最小二乘解。

令[x=X（ex，y|S）]，[yk=（sk，vy）]，[ak=ep，q≺ex，y∈p（sk，vy）X（ep，q|sk）]，其中[k∈[1，m]]，式（4）可表示为：

[Ax=Y]    （5）

其中[A=a1a2..am]，[Y=y1y2..ym]。

构造如下正规方程组：

[ATAx=ATY]     （6）

其中，[AT=a1a2..am]为[A]的转置向量，则求解该正规方程组可得：

[x=k∈[1，m]ak⋅ykk∈[1，m]a2k]     （7）

该解即为（5）式超定方程组的最小二乘解。故多个源点下某共同链路的分组通过率计算公式为：

[X（ex，y|S）=k∈[1，m]（ep，q≺ex，y∈p（sk，vy）X（ep，q|sk））⋅Y（sk，vy）k∈[1，m]（ep，q≺ex，y∈p（sk，vy）X（ep，q|sk））2]   （8）

若m条测量路径中[ex，y]的各个前驱链路分组通过率均不为零，上式可简化为：

[X（ex，y|S）=k∈[1，m]Y（sk，vy）⋅Y（sk，vy）k∈[1，m]Y（sk，vy）2]    （9）

3 结论

为解决传统NT技术无法有效感知阻断链路的问题，本文讨论了路由器端口可达性与链路故障之间的内在关联（对特定测量点而言），据此设计了一种分布式轻量级主动测量机制，通过简单的Ping测量逐跳获取中间路由器接口的响应数据，推导出分布式测量环境中链路分组通过率的计算公式来快速识别故障链路。实践中，一线维护人员只需要进行一些简单网络配置即可实现IP链路级分组通过率的自动监测和分析，具有较高的应用价值。

参考文献：

[1] Vardi Y.Network tomography：estimating source-destination traffic intensities from link data[J].Journal of the American Statistical Association，1996，91（433）：365-377.

[2] 潘胜利，张志勇，费高雷，等.网络链路性能参数估计的层析成像方法综述[J].软件学报，2015，26（9）：2356-2372.

[3] 李惠康，高艺，董玮，等.网络断层扫描：理论与算法[J].软件学报，2021，32（2）：475-495.

[4] Ma L，He T，Leung K K，et al.Monitor placement for maximal identifiability in network tomography[C]//IEEE INFOCOM 2014 - IEEE Conference on Computer Communications.April 27 - May 2，2014，Toronto，ON，Canada.IEEE，2014：1447-1455.

[5] Gopalan A，Ramasubramanian S.On identifying additive link metrics using linearly independent cycles and paths[J].IEEE/ACM Transactions on Networking，2012，20（3）：906-916.

[6] Ma L，He T，Leung K K，et al.Inferring link metrics from end-to-end path measurements：identifiability and monitor placement[J].IEEE/ACM Transactions on Networking，2014，22（4）：1351-1368.

[7] Zheng Q，Cao G H.Minimizing probing cost and achieving identifiability in probe-based network link monitoring[J].IEEE Transactions on Computers，2013，62（3）：510-523.

[8] 陈宇，周巍，段哲民，等.一种IP网络拥塞链路丢包率范围推断算法[J].软件学报，2017，28（5）：1296-1314.

【通联编辑：代影】