网络故障检测中的探测路径选择方法研究

doi:10.13232/j.cnki.jnju.2022.02.015

网络故障检测中的探测路径选择方法研究

齐小刚, 马文超^,, 李家慧

西安电子科技大学数学与统计学院，西安，710126

The study of detection path selection methods in network fault detection

Qi Xiaogang, Ma Wenchao^,, Li Jiahui

School of Mathematics and Statistics，Xidian University，Xi'an，710126，China

通讯作者: E⁃mail：15054438025@163.com

收稿日期: 2021-11-22

基金资助:

国家自然科学基金.  61877067
数据链技术重点实验室基金.  CLDL⁃20182115
近地面探测与感知技术重点实验室基金.  TCGZ2019A002
基础研究项目.  61424140502

Received: 2021-11-22

摘要

通信网络中数据传输能力强的节点实时负载高、传输价值高，在进行故障探测时会产生较高的探测成本.为了减少探测成本，提出一种基于主动探测的探测路径选择算法，该算法定义节点权值以衡量节点的数据传输能力.在探测站选择阶段，算法迭代地选择权值最小的节点作为探测站；在选取探针时，通过合适的 $K$ 值来限制探针长度，减少探针往返时间.算法在确保网络中所有节点都被探测到的情况下，选择满足条件的探针，扩大节点覆盖范围，以减少探针数量，降低探测成本.随机网络拓扑和真实网络拓扑的仿真结果表明，提出的故障检测算法和其他算法相比，能有效地减少探针数量和降低探测成本.

关键词： 故障检测 ; 主动探测 ; 探测成本 ; 传输价值 ; 通信网络

Abstract

An important objective in existing detection⁃based network monitoring methods is to reduce the probing costs. Low probing costs mean low resource consumption and less negative impact on the transmission of data. Nodes with high data transmission capacity in the communication network have high real⁃time loads and high transmission value，therefore incur higher probing costs when performing fault detection. In this paper，a detection path selection algorithm based on active detection is proposed on the issue of reducing probing costs. The node weights are used to measure the data transmission capability of the nodes. In each iteration，the node with the lowest weight is selected as the probing station，which avoids the situation where detection packets are lost at nodes with large weights to lead to inaccurate detection results. When selecting probes，the probe length is limited by a suitable K value to reduce the probe round trip time. The algorithm expands node coverage by selecting suitable probes to ensure that all nodes in the network are detected. It reduces the number of probes and probing costs. Simulation results of random and real network topologies show that the fault detection algorithm proposed in this paper is effective in reducing the number of probes and decreasing probing costs compared to other algorithms.

Keywords： fault detection ; active detection ; detection costs ; transmission values ; communication network

PDF (973KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

齐小刚, 马文超, 李家慧. 网络故障检测中的探测路径选择方法研究. 南京大学学报（自然科学）[J], 2022, 58(2): 320-327 doi:10.13232/j.cnki.jnju.2022.02.015

Qi Xiaogang, Ma Wenchao, Li Jiahui. The study of detection path selection methods in network fault detection. Journal of nanjing University[J], 2022, 58(2): 320-327 doi:10.13232/j.cnki.jnju.2022.02.015

现代网络的规模和复杂性的增加使网络管理具有挑战性，故障检测和满足用户的服务质量需求是高效网络管理面临的两个主要问题^［1］.随着关键任务和实时应用程序对提高网络可用性的要求越来越高^［2-3］，意外故障和常规操作降低了网络可用性^［4］，故障检测的重要性日益凸显.现代网络需要及时的故障检测和恢复措施以确保网络的正常运行，保证系统的生存能力和可靠性.故障检测技术分被动监测、主动监测和网络层析.被动监测是经典的故障检测工具，通过使用故障组件发送的警报来监控网络的运行状态并检测故障的存在，检测到故障后，被动方法根据故障信息进一步定位故障位置，它的主要限制在于对网络组件的高度依赖，每个网络组件在出现故障时都要发出警报^［5］.主动探测是在网络中主动发送探针来推断网络组件的健康状况，探针通常用于获取端到端的统计信息，如延迟、吞吐量、损失和路由可用性^［6］.主动探测分两种：预计划探测和自适应探测.图1和图2是预计划故障探测和自适应故障探测的图例.Brodie et al^［7］提出预计划探测来解决单节点故障定位问题，在给定的网络拓扑条件下寻找合适的探测路径，根据不同路径返回的信息判断网络状态，定位网络故障.Xuan et al^［8］的基于预计划探测的算法可以在大型稀疏网络中定位多个链路故障，先间断性地发出能够覆盖网络所有节点的探针，然后根据返回的信息推断网络各组件的状态.但是该方法需要使用大量探针，且大部分探针会被浪费，另外，在发送和接收探针时由于时延会造成信息不完整，导致判断产生误差.自适应探测方法选取一小部分能够覆盖网络中所有节点的探针进行探测，所以探测结果只能确定网络故障是否发生，不能确定具体组件故障，必须进一步探测，每次探测都根据以前的探测结果在可能的故障区域进行信息的获取.和预计划探测相比，主动探测有效减少了探针数量.因为探针是从探测站发送的，所以不论是预计划探测还是自适应探测都需要确定探测站和选择探针集.现有的文献提出了多种方法来选择探测站和探针，希望利用最小数量的探针集来探测整个网络状态^［9-10］.一旦确定了探测站，接下来就是选择合适的探针集来检测和定位故障，同时，选择合适的探针可使检测和定位时间最短^［11-12］.网络层析^［13-15］是检测网络中链路性能的一种方法，从端到端测量中推断链路状态和包延迟情况，监控网络以保证服务质量.Li et al^［16］重点研究动态网络的优先链路层析成像问题，解决如何分配最小数量的监视器以识别所有可能也会改变的拓扑的链接.Ma et al^［17］开发一种算法来放置最少数量的监视器来识别所有的链接指标.Feng et al^［18］提出一种部署新监控器的方法以最大限度地减少总错误范围.Geng et al^［19］提出一种新的混合链路保护（HLP）方案，保护失败的链路，以非常高效的方式提供完整的网络保护.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 预计划故障探测

Fig.1 Pre⁃plan fault detection

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 自适应故障探测

Fig.2 Adaptive fault detection

本文基于主动探测方法对故障检测中的探测路径选择进行研究，根据节点的最短路径权重、节点的最短路径数和节点度来定义节点的权重（用来衡量节点的数据传输能力，即传输价值）.在探针集的选择上考虑路径长度对探测成本的影响，选择一组探针长度不超过 $K$ 的最小探针集，尽可能覆盖所有节点，降低探测成本.

1 相关概念

假设网络拓扑已知，将其建模为一个无向加权连通图 $G = (V, E, W)$ ，其中， $V$ 表示顶点或节点， $E$ 表示网络节点之间的链接， $W$ 表示节点权值向量.节点 $i$ 的权值 $w_{i}$ 表示节点在网络拓扑中的数据传输能力.将网络中的一些节点作为探测站来监测整个网络状态，这些探测站通过发送探针来检测节点.故障检测的探针是从候选探针集里选择的，每个探针都能沿着指定的探测路径进行传输并检测路径上所有的节点和链路.假设探测数据包总是采取最短路径从源到目的地，那么在放置探测站之前，首先限制探针的最大长度为 $K$ ，限制探针长度的好处是减少探针的往返时间，加快故障检测的过程.大规模网络中，如果不加限制，探针的长度可能达到几百跳甚至更高.在放置探测站的过程中忽略探针长度的限制可能会导致某些节点不被任何探测站探测到（ $K$ 跳内）.因此在探测站放置和探针选择中都需要考虑这个约束.本文定义节点的权值来表示节点的数据传输能力，权值越高的节点数据传输能力越大，传输价值越高.若将高权值节点作为探测站会增加探测成本，故在选择探测站时应避免选择高权值节点作为探测站.在控制探测站数量的情况下选择最小探针集来覆盖所要监测的网络，可以降低探测成本.本文将节点的权值表示为：

w_{i} = \frac{W P_{i}}{H_{i}}

(1)

其中， $H_{i} = \{δ_{i}, μ_{i}\}$ .节点权值的定义有两种表示方法： $H_{i} = δ_{i}$ 时， $δ_{i}$ 是节点 $i$ 到其他节点的最短路径总数； $H_{i} = μ_{i}$ 时， $μ_{i}$ 是节点度（表示节点的邻居节点的数目），具有较大节点度的节点与其他节点的通信能力更强. $W P_{i}$ 是节点 $i$ 的最短路径权重和：

W P_{i} = \sum_{j \neq i} w p_{i j}

(2)

其中， $w p_{i j} = \sum_{s \in n o d e s (p_{i j})} d_{s}$ ， $w p_{i j}$ 是从节点 $i$ 到节点 $j$ 的最短路径 $p_{i j}$ 的权重，是经过的各节点度之和.

探针选择是从候选探针集中选择覆盖所有节点的探针的过程，每个探针的成本定义如下：

C O S T_{p} = \sum_{i \in n o d e s (p)} w_{i}

(3)

其中， $n o d e s (p)$ 表示探针 $p$ 经过的节点集合， $w_{i}$ 是节点的权值.当探针经过高权值节点时，探针成本增加.因为高权值节点传输价值高、实时流量大、比其他节点更拥挤，所以更容易拥塞.因此在选择探测站时，尽量避免经过高权值节点.对于给定的探针集 $P S$ ，故障检测的探测成本表示为所有探针的成本之和：

C O S T = \sum_{p \in P S} C O S T_{p}

(4)

故障检测的目的是确定网络中可能出现故障的区域，从而减少进一步准确定位故障节点的探针数量.探测站选择问题是NP完备的，因此常用贪婪算法来近似求解，不从整体最优上考虑，而是在某种意义上寻求局部最优解.使用式（2）计算每个节点的最短路径权重，使用式（1）计算每个节点的权重，在确定探测站阶段，选择最小权值的节点作为探测站.在确定探针阶段，最小探针集要能覆盖所有节点以确保在节点发生故障时进行检测. $C P_{i}$ 是探测站 $i$ 到拓扑中其他节点的候选路径集，对此提出一种探针选择的思路：在每次确定一个探测站后，随机进行探针的选择，将 $C P_{i}$ 中的候选探针按照其长度进行降序排列，并依次选择未覆盖节点数量大于 $γ$ 的候选探针加入探针集 $P S$ . $γ$ 是一个小于 $C P_{i}$ 中的最大路径长度的整数，根据候选路径集中的最大路径长度动态地确定 $γ$ 的值.本文设置的 $γ$ 可在最大化地扩大网络覆盖范围的情况下确保每个探测站发出的探针数量尽可能均衡.如果 $γ$ 过高，则符合条件的探针数量很少，可能会出现探针集无法覆盖所有节点的情况；如果 $γ$ 值很小（等于1），则可能会出现从某个探测站发出的探针数量过多，从而导致网络拥塞.

定义1

已知给定探测站以及候选探针集，选择的探针满足其未覆盖节点数大于等于 $γ$ .

假设探测站 $i$ 是选择的第 $n$ 个探测站，探测站 $i$ 的候选探针集 $C P_{i}$ ，对于候选路径 $p_{i j}$ 所经过的节点集 $\{v_{1}, v_{2}, \dots, v_{j}\}$ ，在已覆盖节点集 $C o v e r N$ 中，要求至少有 $γ$ 个节点在 $C o v e r N$ 中不存在.满足 $p_{i j} \in P S$ 的条件是：

\forall n o d e s (p_{i j}), \exists γ, s t, \{v_{1}, \dots, v_{γ}\} ⊄ C o v e r N

(5)

算法迭代地选择探测站和探测路径直到网络中所有的节点都至少被一条路径覆盖，如果一个节点发生故障，则经过该节点的探针历经的所有节点都将不被探测到.因此，沿着探测路径发送的探针能够缩小故障可能发生的区域，可进一步探测以确定故障点.

2 探测路径选择方法

本文提出的故障检测的探测路径选择算法（Detection Path Selection Algorithm，DPSA）给出了故障检测过程的细节.算法1将网络节点权重图 $G$ 、探针最大长度 $K$ 和探测站数量 $m$ 作为输入，输出探测站集 $P S$ 和探针集 $P$ .初始化阶段，将探测站集合 $P S$ 、探针集合 $P$ 和已覆盖节点集合 $C N$ 设置为 $\emptyset$ ，未覆盖节点集是所有节点（ $U C N = V$ ）.首先使用Dijkstra最短路径算法生成网络中任意两个节点的最短路径，计算该路径的权值，并计算所有节点的权值.当目前探测站数量小于输入的探测站数量 $m$ 并且未覆盖节点集不是空集时，进行探测站和探针的选择，选择当前节点集中的节点权重最小的节点 $i$ 作为探测站，将该节点 $i$ 添加到 $P S$ 中，并从当前节点集中移除该节点.对于探测站 $i$ 的候选路径集 $C P_{i}$ 中的所有路径按长度降序排列，若候选路径集合中的路径未覆盖节点数量大于或等于 $γ$ ，将其作为探针加入 $P$ ，并将 $n o d e s (c p_{i})$ 从未覆盖节点集合 $U C N$ 中移除.

算法1

故障检测的探测路径选择算法

输入：网络 $G = (V, E, W)$ ，探针长度 $K$ ，探测站数量 $m$

输出：探测站集 $P S$ ，探针集 $P$

step1.初始化 $P S = []$ ， $P = []$ ， $C N = []$ ， $U C N = V$ ， $K$ ；

step2.对 $i, j \in V$ ，计算节点 $i$ 到节点 $j$ 的最短路径，计算路径 $p_{i j}$ 的权重 $w p_{i j}$ 和节点 $i$ 的权重 $w_{i}$ ；

step3.当 $|P S| < m$ 且 $U C N \neq \emptyset$ 时，选择当前节点集中的节点权值最小的节点 $i$ 作为探测站，将节点 $i$ 添加到 $P S$ 中，并从当前节点集中移除该节点；

step4.将 $C P_{i}$ 中的所有路径长度降序排列，对 $c p_{l} \in C P_{i}$ ，如果 $|n o d e s (c p_{l}) - n o d e s (c p_{l}) ⋂ C N| \geq γ$ ，将 $c p_{l}$ 加入 $P$ 中，并将 $n o d e s (c p_{l})$ 从 $U C N$ 中移除，更新 $U C N$ 和 $C N$ ，返回step3.

图3a是八个节点的简单网络图，可以帮助理解算法1的故障检测算法.在图3a所示的简单网络中放置两个探测站.将探针长度 $K$ 设置为2，即跳数最大为2， $γ$ 设置为2.使用Dijkstra最短路径算法来计算任意两个节点间的最短路径，并计算路径权值和节点权值.每个节点的权值为 $W = \{8.14,7.29,7.57,7.57,7.14,7.14,7.14,8.0\}$ .选择节点权值最小的节点作为第一个探测站，选择节点6作为第一个探测站.表1是作为探测站的节点6的候选路径集 $C P_{6}$ ，满足条件 $|n o d e s (c p_{l}) - n o d e s (c p_{l}) ⋂ C N| \geq 2$ 的探测路径是 $c p_{6}^{3}$ 和 $c p_{6}^{4}$ .选择 $\{6,5, 4\}$ 和 $\{6,7, 8\}$ 作为探针，选定第一个探测站和第一部分探针后的网络的节点覆盖范围是 $\{4,5, 6,7, 8\}$ ，未覆盖节点 $\{1,2, 3\}$ ，从未覆盖的节点中选择第二个探测站，在未覆盖节点中选择节点权值最小的作为第二个探测站，此时，选择节点2作为探测站，探针选择为 $\{2,1\}$ 和 $\{2,3\}$ .因此，选择的探测站为2和6，探针为 $\{2,1\}$ 、 $\{2,3\}$ 、 $\{6,5, 4\}$ 和 $\{6,7, 8\}$ .探测站和探测路径的部署情况如图3b所示.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 八个节点的简单网络

Fig.3 Simple network of eight nodes

表1 候选探针集

Table 1 Candidate probe sets

$c p_{6}^{1}$	$\{6,5, 4,3\}$
$c p_{6}^{2}$	$\{6,7, 2,1\}$
$c p_{6}^{3}$	$\{6,5, 4\}$
$c p_{6}^{4}$	$\{6,7, 2\}$
$c p_{6}^{5}$	$\{6,7, 8\}$
$c p_{6}^{6}$	$\{6,5\}$
$c p_{6}^{7}$	$\{6,7\}$

新窗口打开| 下载CSV

3 结果和分析

3.1　实验设置

通过对随机生成的网络拓扑和真实网络拓扑进行仿真来评估本文提出的算法，使用前面定义的两种节点权值的参数生成节点的权值.DPSA1表示使用第一种参数定义节点的权值 $H_{i} = δ_{i}$ ，DPSA2表示使用第二种参数定义的节点权值 $H_{i} = μ_{i}$ .本文同时也仿真了三种不考虑节点权值和探针长度的故障检测算法作对比.

（1）MaxFD：选择节点度最大的部分节点作为探测站并选择探针；（2）MinFD：选择权值最小的部分节点作为探测站并选择探针；（3）RandomFD：随机选择部分节点作为探测站并选择探针.首先在随机生成包含少量节点的网络上比较了这四种算法的探针数量和探测成本，然后在真实网络拓扑上进行性能评估，选择的真实网络拓扑是从Rocketfuel项目^［20］导出的Internet Service Provi⁃der （ISP）拓扑.将DPSA算法与其他三种算法的探针数量和探测成本进行比较，以显示考虑节点权值的故障检测方法的优势.

3.2　随机生成拓扑

图4是节点数量从7到10的四个小规模网络.因为网络规模小，设置探针最大长度 $K = 2$ ，探测站数量最多布置两个.表2和表3展示了四种算法在不同网络拓扑上执行的结果.从表2可以看出，在小规模网络图上本文算法选择的探针数量和其他算法的选择几乎一样.DPSA算法每次选择的最大探针长度不大于 $K$ ，特别是在图4d中，最大探针长度为4.限制探针长度虽然可以减少探针的往返时间，但是会增加探针数量，因此在真实网络中，应该根据实际需求选择最合适的 $K$ .表3显示了不同算法的探测成本，由探针们的总权值表示.不难看出，DPSA算法在小网络上的探测成本较低，表明本文算法选择的探针对网络中的节点影响最小，特别是具有高传输价值的节点，这使得探测站发送的探针不仅能够检测所有节点的健康状况，还能较小地影响网络中的正常流量.因此在较少节点的网络中，DPSA算法在探测成本和探测效率上和其他算法相比，具有明显的优势.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 小规模网络拓扑

Fig.4 Small⁃scale network topologies

表2 故障检测的探针数目

Table 2 Number of probes for fault detection

Network	DPSA1	PDSA2	MaxFD	MinFD	RandomFD
(a)	3	4	4	4	4
(b)	4	4	5	3	4
(c)	4	5	4	4	4
(d)	4	5	4	5	5

新窗口打开| 下载CSV

表3 故障检测成本

Table 3 Cost of fault detection

Network	DPSA1	DPSA2	MaxFD	MinFD	RandomFD
(a)	26	30	28	35	35
(b)	26	27	45	30	36
(c)	39	39	39	41	39
(d)	42	43	42	60	55

新窗口打开| 下载CSV

3.3　真实网络拓扑

在真实网络拓扑实验中使用的真实拓扑是从火箭燃料项目^［20］中导出的，广泛应用于相关研究.表4总结了在 $K = 8$ 时每个自主系统（AS）中的节点数和链路数.记录探测站数量在3~10个时的探针数量和探测成本，表5

表4 真实网络拓扑

Table 4 Real network topologies

AS	Nodes	Edges
3967	79	147
6461	141	374
3257	161	328
1239	315	972

新窗口打开| 下载CSV

表5 故障检测后的可疑节点数

Table 5 Number of suspicious nodes after fault detection

AS	DPSA1	DPSA2	MaxFD	MinFD	RandomFD
3967	20	19	51	49	53
6461	31	34	57	63	68
3257	45	49	64	71	78
1239	53	57	161	153	179

新窗口打开| 下载CSV

是故障检测后的可疑节点数，图5表示了用于故障检测的探针数量.从比较结果可以看出，本文算法总能使故障检测后的可疑节点的数量最少，说明与其他算法相比，本文算法选择的探针对具有高传输价值的节点们的影响较小，更适用于现实通信网络中的故障检测.在大规模的网络拓扑中，DPSA算法在探针数量上有明显的优势，可以有效提高网络管理的效率.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 真实网络拓扑的探针数量

Fig.5 Number of probes for real network topology

图6比较了四种故障检测算法的检测成本，显然，本文的DPSA算法的检测成本明显低于其他三种算法，算法选择的探针对具有高传输价值的节点的影响较小，适用于现实通信网络中的故障检测.在注重成本预算的情况下，DPSA故障检测算法在降低探测成本方面有显著优势.图7记录了探测站数量为六个时，四种真实网络拓扑的探测时间的对比，在大规模的网络中DPSA算法的探测时间小于RandomFD算法.因此，在实际的大规模网络中，在网络管理成本有限的情况下，DPSA能显著降低探测成本和探针数量.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 真实网络拓扑的故障检测成本

Fig.6 Fault detection costs for real network topologies

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 四种真实网络拓扑的探测时间

Fig.7 Detection time for four real network topologies

4 结论

通信网络中一些负载很高的节点更重要且容易受到额外流量的干扰而造成性能下降，本文旨在研究故障检测过程中根据节点传输价值的差异和探针长度的限制来放置探测站和选择探针的问题.提出的故障检测的探测路径选择算法DPSA是一种有效的算法，可以减少被发送的探针对具有高传输价值的节点们的影响.为了减少探针的探测时间，设置探针的最大长度为 $K$ .在探测站放置过程中，DPSA选择具有最低传输价值的节点们放置探测站，使所有节点尽可能在 $K$ 跳以内到达探测站.在选择用于故障检测的探针时，DPSA选择覆盖最多的未覆盖节点大于 $γ$ 探针.利用在随机生成的网络拓扑和ISP网络拓扑上的实验来评估提出的算法的性能.与其他忽略节点传输价值的故障检测算法相比，该算法可以显著降低探测成本，对网络管理有一定的价值.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Tayal

， Sharma

， Hubballi

，et al.

Traffic dynamics⁃aware probe selection for fault detection in networks

Journal of Network and Systems Management，2020，28(4)：1055-1084.