网络诊断技术研究综述
摘要
关键词 网络诊断；网络测量；监视器放置；路径构建；可识别性；秩亏问题
0 引言
随着网络设备的日益普及和复杂性不断提高，在线掌握网络运行状况（包括带宽、丢包率、链路时延及抖动等关键指标）已成为网络管理的重要任务。然而，在功能虚拟化（NFV）与软件定义网络（SDN）时代背景下，“内部分析”使得获取这些信息变得困难。传统的管理手段则依赖于对内部分析能力的提升。
Vardi在其职业生涯早期即对路由拓扑推断问题展开了深入研究。基于其观察到的领域特点与医学CT成像存在高度相似之处，在此领域他首次提出了“网络诊断”这一专业术语。通过分析端到端路径上的性能数据来评估网络中连接设备或节点的性能状况。相比直接测量法而言，在实际应用中更为便捷的是采用“网络诊断”方案。在应用层面的优势主要体现在无需额外设备即可轻松获取关键路径数据的特点，并且操作简便经济实惠。相较于传统直接测站法而言，在实际部署上更为灵活方便的是采用若干监控点来进行间接评估工作模式
该新的网络管理策略推动形成了一系列关键理论、核心问题以及新型的网络诊断架构。例如，在成本最低的前提下实现监视器的部署；探索如何设计最优的测量路径以确保在低成本条件下实现网络内部状态的精确且可靠的诊断；针对不同类型的网络内部状态指标（如延迟、丢包率、带宽和设备故障）进行合理的设计与应用。
早期的网络诊断工作侧重于可加类型网络诊断模型，主要基于测量路径的测量结果设计网络诊断算法，恢复网络节点或链路的最可能的网络状态。研究的主要问题包括监测点的部署、测量路径的设计、网络诊断算法、网络诊断的安全性等问题。Shih等人研究了基于单播边测量的链路延迟分布估计。Adams等人研究了基于端到端多播和单播观测的内部拓扑结构；Xi等人介绍了双广播的检测方式；Duffield等人将背对背单播流作为探测路径来推断链路的丢包率。近年来，网络诊断技术得到了飞速的发展，涌现出面向布尔网络诊断、可加网络诊断、带宽网络诊断、随机网络诊断等新模型，以及网络诊断的攻击、防御等新问题。近年涌现出基于网络编码的网络诊断、基于神经网络的网络诊断和网络功能虚拟化中的网络故障定位等一些新的前沿工作。
已有研究对网络诊断技术的发展进行了系统性总结与对比分析。已有文献较早地对网络诊断技术的发展进行了综述性分析，并从基于网络链路级参数的推理分析、网络拓扑结构识别以及网络起讫点流量强度估计三个方面探讨了相关技术。随后的研究则主要关注并总结了基于端到端测量方法与技术在网络安全领域的应用。在现有研究中将链路性能参数的网络诊断方法主要分为两类：定量参数推断方法和定性参数推断方法，并根据不同参数对链路性能刻画的程度差异，在现有研究中将链路性能参数的网络诊断方法主要分为两类：定量参数推断方法和定性参数推断方法，并根据不同参数对链路性能刻画的程度差异，在现有研究中将链路性能参数的Network diag
nosis methods are typically classified into two categories based on the degree of detail with which they characterize network performance parameters.
本文旨在系统地分析网络诊断的各类新模型、关键技术以及相关算法，并结合新出现的问题展开深入研究。
总结系统归纳分析了布尔网络诊断技术、可加网络诊断技术、带宽受限的网络诊断技术和随机网络诊断技术等多类典型智能网关的智能网关拓扑结构特征与性能指标关系模型及对应的智能网关故障定位方法的关键问题。
（2）对网络诊断技术中的关键问题进行分析与整理主要包括：第一部分是监视器的安装位置与信标服务站点的选择；第二部分涉及路径规划与数据采集；第三部分重点解决"可达性"问题；第四部分则是针对可达性问题提出的新解决方案；最后还研究了在确保不可达性的前提下出现的新型攻击等问题。
（3）本节综述阐述了最新提出的基于网络编码机制的网络安全态势感知方法、采用神经元模型进行系统状态识别的技术以及面向NFV架构下的节点故障定位方案等前沿技术问题。针对当前网络安全态势感知技术和智能运维系统的发展现状及性能对比研究结果, 展开了对未来网络安全态势感知技术和智能运维系统发展趋势的技术预测。
图1清晰地展示了本文的核心框架。第1节详细介绍了包括布尔网络诊断技术、可加网络诊断技术在内的几种典型Network Diagnosis方法及其理论基础。详细阐述了包括Network Diagnosis Monitor placement策略以及Signaling Service deployment方案等关键技术，并深入探讨了基于Path Planning与Data Analysis相结合的Network Fault Detection & Localization算法。重点分析了影响Network Fault Detection能力的关键因素——"Identifiability"问题，并对其可能带来的检测效果下降风险进行了深入研究。综上所述，在第5节中我们重点介绍了基于Information Coding优化的新型故障定位方案以及基于Deep Learning驱动的智能故障预测方法，并展望了NFV环境下新型Node Fault Localization技术的发展趋势。本研究总结全文的主要研究成果，并对未来 Network Diagnosis 的发展趋势进行了展望
1 网络诊断的基础模型
本文主要将基础层面的模型归类为4大类：布尔网络诊断、可加网络诊断、带宽网络诊断以及随机网络 diagnosis. 表1系统性地对各类 model 进行了总结，并分析了各类 model 各自适用的情况.
本节将介绍网络诊断中的一些基础概念，并详细阐述这些核心知识的基本原理和应用方法。
该系统中的"延迟"（latency）是指信息在计算机网络中自发送方至接收方所经历的总时间间隔。通常包括四个主要组成部分：发送延迟（即信息在源节点上传输所需的时间）、传播延迟（信息在介质中传播所需的时间）、处理延迟（节点处理数据包所需的时长）以及排队延迟（由于队列满而必须等待释放存储空间的时间）。这些组成部分共同构成了整体传输延迟
带宽（bandwidth）：表示信息在网络传输线路中流通的能力，在固定时间段内能够传递的数据总量。它衡量了通信线路处理数据的信息容量。
丢包率（Loss）：它表示为在数据网络传输中丢失的数据量与总数据量的比例，并且这是路径上各链路累积的影响。
又称为延迟抖动（jitter），该术语代表了路径上链路的加法性能指标。如图2所示，在路径上的连续数据包之间，发送方与接收方的延迟差即为该路径上的延遲變異。
和路由矩阵
。路由矩阵
揭示了探测路径如何覆盖
中的元素（节点或链路）。以节点为例，路由矩阵
表示，如果
中的
在路径
，则
，否则
。设
表示节点状态向量，
表示路径状态向量。
和
分别表示节点
和路径
成功，
和
分别表示节点
和路径
失败。它们形成一个布尔线性系统：
|
|（1）||
|---|---|---|
其中
表示布尔矩阵乘积，
。
图3是一个有8个节点的网络，其中有3个监视器（
），5个非监视器的普通节点（
）。布尔网络诊断在3个监视器之间构造4条测量路径。生成的路由矩阵
如图4所示。
图3 布尔网络诊断实例
图4 布尔网络诊断的
矩阵
以这一布尔网络诊断实例为例，在各节点上的故障分别对应着不同的故障路径集合。此例具备1-可识别性,但节点集本身不具备这种特性.
，
，
和
发生故障时，对应的故障路径集都为
，由此可见该例不具备2-可识别性。为了提高监测精度需对监视器的位置进行优化配置 通过建立测量路径并规划信标与服务设施的布置成为布尔网络诊断中的关键研究方向之一
1.2 可加网络诊断模型
高效监控网络性能是网络运营商构建可靠通信网络的关键举措之一。可加网络诊断通过选择性地监测特定设备间的端到端路径性能，并利用状态恢复函数推断链路和节点的内部运行状态。这种方法避免了传统直接计量方法所带来的内部测量开销大及高成本的问题。
给定一个网络拓扑
，其中
和
是节点和链路的集合，
，
。集合
表示链路权值，其中
是描述链路
衡量网络性能的关键指标包括时延与数据包丢失率。这些指标具有可叠加性特征。其中时间延迟指标可以直接相加计算。而数据包丢失率或数据传输效率在对数尺度下同样具备可叠加性。
在网络环境中，在节点集合的一个子集上实施探针包的注入和接收操作的集合被称为监视器集合。
。网络诊断的探测路径
被定义为从源监视器
开始到目标监视器
结束的一系列链路。探测路径的度量用
表示。
是路径的集合，
是路径度量的集合。路由矩阵
揭示了探测路径如何覆盖
中的链路。如果
中的链路
在路径
，则
，否则
。网络诊断是解方程
找到一个解
，
表示估计的链路度量。
当路由矩阵
列满秩时，即
为唯一识别条件时，该线性方程具有唯一解。然而，由于
和拓扑问题相关联时，在生成满足识别条件的探测路径方面存在挑战。对于这一挑战而言，默认的做法是通过具备某种特定特征或能力来应对。
的路由矩阵。在这种情况下，通常使用伪逆（pseudo-inverse）来计算
:
|
|（2）||
|---|---|---|
链路状态也可以通过恢复的链路度量来诊断。
如图5所示，是一个有8个节点、11条链路（
）和3个监视器（
该网络的拓扑结构采用了三个监控设备来评估网络线路性能，在三个监控设备之间构建了六条测距路径以形成路由矩阵
如图6所示。
图5 可加网络诊断实例
图6 可加网络诊断的
矩阵
假设
为链路
的链路度量（如时延和丢包率），
为路径
的路径测量。然后得到下面的线性方程组：
|
|（3）||
|---|---|---|
通过对上述线性方程的高斯消元，可以推导出
，
。在给出的例子中，上述结果表明
和
是可识别的。即通过路径间端到端的测量，可以准确推出
和
链路性能评估的基础是什么？这构成了该领域研究的主要方向。
1.3 带宽网络诊断模型
基于端到端路径的带宽推断内部链路的带宽即为一个长期存在的未解决的问题，在该领域中现有的数学工具无法直接通过一组最小方程组来求解反问题。尽管在布尔网络诊断中能够识别出链路故障或链路拥塞的状态，但其目标辨识功能与之相比存在显著差异。基于布尔网络诊断的方法能够实现故障定位（正常/失败）以及拥塞状态（拥塞/不拥塞）的判断，并且其测量值均为二进制信息；而在这种情况下我们所关注的是连续型的信息量即为单个链路的具体带宽数值。
给定一个网络拓扑
，其中
和
是节点和链路的集合，
，
。给定一组测量路径
和路由矩阵
。
表示顶点
和顶点
之间的链路。路由矩阵
揭示了探测路径如何覆盖
中的链路。路由矩阵
揭示了探测路径如何覆盖
中的链路。如果
中的链路
在路径
，则
，否则
。用未知的
代表顶点
和
之间的链路
的带宽，如果顶点
和
之间没有链路，则
。
为无向图，因此
。用
表示路径
的带宽。由于带宽的特性，得出以下的最小方程：
|
|（4）||
|---|---|---|
其中
表示取最小值的运算。
如图7所示的宽带网络诊断实例中
和
）和6个非监视器的普通节点（
两台监控设备旨在获取不同传输路径上的带宽值，并通过在两台设备之间规划4条测速通道来实施网络性能分析。这种配置最终会生成一个包含所有可能传输路径的路由矩阵
如图8所示。
图7 带宽网络诊断实例
图8 带宽网络诊断的
矩阵
假设
为链路
的带宽，
为路径
的路径带宽。得到如下线性方程组：
|
|（5）||
|---|---|---|
在带宽网络诊断中，需要考虑如何在给定
和
的情况下，推断出
的值，将在后续的关键技术中介绍。
1.4 随机网络诊断模型
基于网络诊断获得的测量结果通常涉及节点或链路的状态函数，在确定单个元素的性能特征时必须通过反演这些函数来实现。我们关注的关键指标通常是具有持久性的性能指标如丢包率与延迟变化情况等。这些测量结果实际上是基于丢包率或延迟实例定义的具体函数，在进行反演时必须能够应对测量中的随机性不确定性。为了更精确地描述每个网络单元的行为模式，在建模过程中假设其性能表现为一个未知的概率分布变量形式是较为合理的选择之一。在现代网络诊断中常用的统计分析方法包括期望最大化算法贝叶斯估计以及极大似然估计等基础方法的基础上还衍生出了多种派生技术如文献中提出的基于EM迭代过程下的伪似然法以及文献中采用极大化对数似然方法来进行参数估计
随机网络诊断的测量采集主要采用两种技术:单播传输和分组广播模式。在单播传输技术中,每个数据包仅通过单播传输技术被单一接收端口接收;而在分组广播模式下,同一个数据包会被同时发送至一组指定的接收节点。如图9所示展示了这两种路由树的结构
图9 单播和多播的路由树
在配置多播路由协议的网络中，在每次组目的连接建立过程中，在线程中设置初始计数器值为1；当一个中间路由接收到来自源节点的一个新连接建立请求时，则立即生成一个新的连接实例，并将其附加到该链路上；之后系统将在该链路两端点处创建新的路由键，并将这些信息通过RIP协议传播至相关的路由器中。在网络规划阶段，在考虑网络性能指标时需要评估这条链路的最大吞吐量；如果这条链路的最大吞吐量低于某个阈值，则应立即采取措施提升其性能水平。
给定一个网络拓扑
，一组测量路径
和路由矩阵
。路由矩阵
揭示了探测路径如何覆盖
中的元素（节点或链路）。以链路为例，路由矩阵
表示，如果
中的链路
在路径
，则
，否则
运行期间，在路径上注入了探测数据包。基于概率模型分析，在所有探测包中均经过预先定义好的路径集合
上的任意一条路径
发送，探测包被分配到路径
的概率为
，
，
，
定义为探测包分配。
给定一组参数未知的链路度量分布
，
，随机网络诊断的目标是通过探测路径上相应性能度量的观测来推断
。用
表示路径度量
的条件概率，假设探测包在路径
上发送，链路参数为
。随机网络诊断就是从观测
来推断
，其中
是第
个探测包的探测结果，
是被探测路径
标识符，在假设探测包获取到性能数据在探测包与链路之间呈现相互独立的状态，则观测数据被视为服从独立同分布的过程。其中每个值的具体分布情况如下所示：
|
|（6）||
|---|---|---|
链路度量中有两种不同的度量：丢包率和延迟变化。
在随机网络诊断中, 当未知的链路度量指标为丢包率时, 我们的目的是利用探测路径上端到端的丢包率数据来推断单个链路的丢包率水平. 根据定义, 链路丢包率等于1减去该链路的成功传输速率. 由于成功传输速率通常更易于计算, 因此我们倾向于采用这一指标作为评估依据.
表示链路成功率。每个探测包的探测结果
表示探测包是否成功到达目的地，成功到达则
，未到达则
假设同一个探测包在各条链路上的能量损失以及在同一条链路中的多个探测包的能量损失彼此之间相互独立。观测模型为：
|
|（7）||
|---|---|---|
在随机网络诊断中，当未知的链路度量是延迟变化时，用
反映网络路径中的时延波动情况。我们的目标是基于观测到的数据流顶端至底端的时延变化来优化网络性能。
来估计
。假设链路
上的延迟变化符合正态分布
，均值为零，未知方差为
基于以下假设，在同一探测包中分别位于不同链路之间的时延波动与其他探测包在同一链路中的时差变化是相互独立的变化过程。观测模型为：
|
|（8）||
|---|---|---|
该文通过实例详细阐述了基于费雪信息矩阵的丢包率测量设计方案
，
和
上的端到端损耗来推断链路
和
的丢包率。
图10 随机网络诊断实例
随机给出探测包分配和实际丢包率进行说明。假设3个候选探测包分配
，链路实际丢包率为
则根据费雪信息矩阵逆对角线元素平均值得出丢包率估计量并将其纳入克拉美罗下界（Cramer-Rao lower bound, CRLB）评估
。假设3个候选探测包分配
，链路实际丢包率为
则基于费雪信息矩阵逆运算后的对角元素均值提供的丢包率估计量具有克拉美罗下界表现
。假设3个候选探测包分配
，链路实际丢包率为
则基于费雪信息矩阵倒置后的对角元素平均值给出的丢包率估计达到克拉美罗下界。
。
针对现有相关网络诊断的基础模型而言
2 网络诊断的监视器放置和信标服务放置
2.1 布尔网络诊断监视器放置算法
在布尔网络诊断体系中，监视器的布置位置具有重要性。然而，在其显著区别在于其布置策略并非独立于具体链路度量值之外的可加网络体系，在这里需要强调的是布尔网络诊断体系下可行的监视器布置策略受潜在的链路（或节点）状态影响。现有研究通过引入参数 k 来量化这种依赖关系，并在此基础上设计相应的检测算法。具体而言，在该框架下算法的主要目标是优化监视器配置以实现最多 k 个故障定位的同时最小化所需监视器数量，在此过程中充分考虑系统的部署成本和协调效率。
对于链路的故障定位，文献提出的监视器放置算法能够在路径中不包含重复链路的路由机制中实现 k 边可识别性，所提出的算法是多项式时间可解的。Ahuja等人通过使用监视循环和监视路径来唯一地确定共享风险链路组（shared risk link group，SRLG）故障。作者证明了，当使用单个监控位置时，为了定位所有的SRLG故障（最多达 k 条链路），一个网络必须是 k +2边连通的。对于小于 k +2边连通的网络，作者推导了设置监控位置来唯一定位任何SRLG故障（最多达 k 条链路）的充要条件。仿真结果也验证了所提出的监控技术和解决方案的有效性。文献证明了在任意的可控路由机制中实现 k 边可识别性是NP难的，其提出的贪婪启发式的监视器放置算法能够在任意的可控路由机制中实现 k 边可识别性。但是Cho等人提出的算法只适合处理较小的 k ，当 k 很大时，算法复杂度会达到指数级。这两种算法放置的监控器数量不一定是最低数量的监视器，可能会大于理论上需要的监视器数量的最小值，因此利用最低数量的监视器实现 k 边可识别性仍然是有待研究的问题。
针对节点故障定位问题，则也需要考虑到可能存在的监视器自身出现故障的情况。Ma等研究者则开发出了一种基于监视器布置的应用于所有路由机制的一般性贪心算法——MNMP（maximum node-identifiability monitor placement），该算法通过逐步选择合适的监视器以实现对特定目标函数值的最佳优化效果。然而这种贪心方法通常会得到次优解；但文献研究表明，在可控条件下该算法表现出了最佳效果，并为无环和无重复链路条件下的网络分别提供了上界和下界的理论结果
对于可加网络诊断，本文总结了可加网络诊断的相关监视器放置算法。
2.2 可加网络诊断监视器放置算法
为了确保唯一地识别每个网络中的链路度量值，在进行线性无关测量时所选择的路径数量必须与网络中所需的独立线路数目相等。当仅允许采用无环（环状）路径作为测量基础时，在绝大多数实际网络中无法仅通过部署两个监控设备就完全覆盖所有可能存在的线路参数；然而，在满足一组充要连接关系的前提下，则无需依赖特定监控设备即可达成对全部内部线路参数的数据采集任务。进一步发展出使用三个或更多监控设备确定网络中全部线路参数所需具备的关键必要条件后……
同时，在通信网络中，研究者们探讨了如何在给定数量的监视器内实现端到端测量数据中对最多可识别链路数量的最大化探测。已有研究表明，在当前条件下完全识别所有链路可能需要大量监视器资源。基于这些发现的启发性思路，在现有研究的基础上进行了拓展性工作。首先文献[6]提出了一种高效的DAIL算法（Determinative Algorithm for Identifiable Links），该方法旨在确定所有可被当前监视器配置所识别的链路连接关系。在此基础上进一步发展出了GMMP算法（Greedy Maximal Identifiability Monitor Placement），这种贪心策略能够在逐步增加监视器数量的同时最大限度地提升新增可识别链路的数量。
研究团队Gao等对通信网络中的链路度量问题进行了深入研究，在细粒度链路度量方面取得了一定成果。他们发现，在实际应用中将一个节点配置为监控器通常会带来显著的成本负担，并因此提出了优化策略——即尽可能减少监控节点数量的同时确保所有感兴趣链路都能被有效识别。文献[40]提出了一种高效的优先链路诊断方法Scalpel，在该方法中通过对原始网络图进行两阶段剪枝优化后实现了精准的链路诊断能力。进一步研究表明，在Scalpel算法的基础上构建的双阶段剪枝算法不仅可以提高资源利用率还能有效降低计算复杂度，并在此过程中实现了与完整图结构相同的监测效果；此外该方法还成功证明了其在资源消耗上的优势
Ren等人在端到端路径测量领域进行了深入研究，在给定任意 k 个链路故障的情况下成功定义了系统的可识别性拓扑条件。他们不仅定义了 k-可识别性的概念，还明确了该性质成立所需的充分必要条件。根据理论分析，文献开发出一种多项式时间算法IDK（identification of k-identifiable links），该算法能在指定条件下有效确定哪些链路属于 k-可识别范围。与此同时，文献[42]还开发出一种高效的多项式时间监测器放置算法MPK（monitor placement for maximal k-identifiability），该方法能够通过合理配置监测器实现对最多 k-可识别链路数量的最大化覆盖
研究者探讨在通信网络可能出现拓扑变化的情况下如何最少地布置监视器。
表2 可加网络诊断的监视器放置算法
与监视器的放置问题不同的是，在布尔网络诊断领域中
2.3 布尔网络诊断信标和服务放置算法
在IP网络环境中存在一种特殊的监控节点称为信标。这种节点与监视器具有相似之处，并均执行探测并收集测量数据。然而与监视器不同的是每个信标能够独立地完成其特定的测量任务而不受其他因素干扰例如一个信标 m 向一个非信标节点 v 发送一个探测响应包该非信标节点 v 则会将响应报文返回给 m 。这一过程可通过ICMP回声请求及回声应答报文得以实现由于每个信标的独立性它能够分别监护一组特定的链路而不受其他链路检测的影响这种特点使得跨接点解耦的问题本质上不同于传统的互相依赖式的覆盖问题
每个信标与所有探测目的之间的连接能够形成一种树形结构，在此网络中我们将其定义为路由树。当所有的信标都形成了一个完整的路由树时，则表明该系统能够检测到任意单一链路故障并实现精确定位这一特性。基于此特性可知，在确定单链路故障定位所需信标放置位置的问题上可通过集合覆盖理论进行建模与分析。根据已知的集合覆盖理论结果可知，在这种情况下该问题是NP难的，并且可以通过Bejerano等人提出的贪心算法来获得近似解法。值得注意的是虽然用于监测基础链路失效率的信标放置策略与用于增强性链路监测的信标放置策略是两个不同的概念但后者实际上可以被表述为广义集合覆盖问题的一种特例因此所得出的相关结论仍然适用这一理论框架对于多跳路径上的多线路上失效节点同时定位问题Nguyen等人则提出了另一种观点即其本质要求是在一跳范围内实现对所有可能失效节点的位置探测这相当于NP难的顶点覆盖问题在文献研究中则将其转化为寻找最小数量满足条件的信标集的问题进而提出了基于贪心算法的设计方案
电信网络经历了从简单数据传输通道向集成多种服务的复杂分布式系统的转变。这种转变带来了更为复杂的挑战（如软件缺陷和策略性冲突等），这些异常情况超出了现有传统故障检测机制的能力范围。为此，研究者们提出了基于布尔网络诊断框架的新颖方法来实现对网络内部故障状态的全面检测与定位。该方法通过在服务层面上分析客户端与服务器之间的端到端连接状态来建立最精确的数据模型。
虽然通常情况下客户端位置无法被网络提供商直接控制...
网络诊断的第二个核心问题是路径规划与数据处理手段，在下文中将详细阐述该核心问题在不同网络诊断模型中的现有研究方法。
3 网络诊断的路径构建和数据分析
3.1 布尔网络诊断的路径构建算法
给定一组监视器，在不可控路由机制下进行路径构建时的主要目标是确定一条具有最低探测成本且能有效覆盖所有关键节点的道路网络，并确保这些测量数据能够提供理想的监测故障能力。现有研究主要集中在链路故障的监测上，并在此基础上提出了不同的解决方案：一部分研究者侧重于精确的成本衡量与监测能力的定义；另一部分则关注如何在有限资源下实现最优的结果。基于不可控路由机制的研究表明，在这种情况下所涉及的道路网络构造仅限于由网络底层路由协议所指定的监视器之间的连接组成；而针对此类特定场景下的道路网络构造问题，则可以通过选择相应的起点终点对来简化相关操作过程；Nguyen等提出的PS（Probe Selection）算法通过选择能够区分不同故障集合的最小探测子集实现了这一目标；而最小探测子集的选择问题已经被证明属于NP难范畴；此外Stanić等提出的策略同样适用于最大冗余道路网中的某种特殊应用模式：即通过放弃对最大数量冗余道路子集的相关监控任务来实现对该系统运行状态的有效管理
对于可加网络诊断，本文总结了可加网络诊断的测量路径构建算法。
3.2 可加网络诊断的测量路径构建算法
Gopalan等人探讨了利用线性独立监控环和路径识别可加性链路度量的问题。文献表明三边连通性是利用一个监视器与监控环路来识别链路度量的必要且充分条件。文献提供了一个多项式时间算法用于计算线性无关环路集合（construct linearly independent cycles）。这是首次在网络架构中推导出该类链路度量识别所需充分条件，并开发了相应多项式时间算法用于计算线性无关环路与路径。文献研究了任意无向网络中基于测量节点识别可加性链路度量并在其间建立路径或环路的问题。对于给定测量节点位置，定义并推导了网络中的链路秩（compute link rank），即测量节点之间可建立的最大线性独立环路或路径数量。
在网络安全分析中，默认情况下会排除循环路径。假设所有测量路径都是无环的，在此前提下，Ma等研究者聚焦于解决如何确定单条链路的度量问题。根据线性代数的基本原理，在互不相关的测量路径数量等于链路总数时，则可唯一确定所有链路度量值。然而，在实际应用中收集全部可能路径的数据具有很高的计算成本——由于可能路径数量呈指数级增长，在复杂系统中这一数目可能达到 n 的指数级别；但互不相关的路径数量最多仅有 n 条（其中 n 表示系统中的节点数目）。相关研究重点开发了一种名为STPC（基于生成树的道路构建方法）的新算法以及一种高效的链路度量方法STLI（基于生成树的关键链识别）。相关证明指出：当一组互不相关的测量路径存在时，则必然存在一组由3条两两独立的道路构成的基础集合；这种特性成为开发STPC算法的核心依据，并在此基础上构建了相应的计算框架以实现高效的链路度量计算过程
Tati团队针对已知故障分布的情况，在满足探测成本预算的前提下，致力于通过优化路径选择来增强系统对故障的鲁棒性。研究表明该问题属于NP难范畴，并开发了一种基于RoMe（鲁棒测量）方法以保证近似的性能。鉴于计算期望秩通常具有挑战性，在此情况下作者提出了一个有效的上界估计方法以降低复杂度。针对故障分布未知的情形，在现有文献中采用强化学习方法作为主方案求解该优化问题，并将RoMe作为一种子程序辅助实现这一目标。其中一项研究采用了强化学习方法并将其作为主方案求解该优化问题，并将RoMe作为一种子程序辅助实现这一目标
表3 可加网络诊断的测量路径构建算法
该系统采用统计方法对各组成部分性能进行建模，并基于路径测量数据推断出各部分的概率分布模型。进一步探讨单播模式下的随机网络诊断方法及其特性，并同时研究多播模式下的相关技术。
3.3 基于单播的随机网络诊断
Coates等人深入探讨了基于端到端时延测量的内部时延估计与定位问题，并提出了创新性解决方案。研究者们基于观测数据构建了新的数学模型，在静态条件下计算出网络内部延迟分布的最大值与最小值；针对动态变化场景，则采用了自适应滤波技术以精确追踪非平稳延迟特性
Duffield等人研究如何采用单播流量作为测量探头来估算链路级的数据丢失率。借鉴了早期工作并采用了基于端到端多播流量测量的方法实现了准确估算。实验设计基于一个将数据包分组发送给两个或多个接收节点的概念（分组内连续发送的数据包之间无延迟）。这些分组的目的在于保证各接收节点能够准确识别其收到的数据块之间的关联性，并通过模拟具有相同路径到达各接收节点的实际多播探测器结果来优化测试效果。
该团队提出了一种解决方案，在使用费雪信息矩阵（FIM）的基础上评估了可探测路径所提供的链路参数的信息量。通过分析FIM信息，在可利用的路径中优化了数据包的分配策略，并最终使得估计误差得到了显著降低。通过对两个典型应用场景的测试结果表明，在丢包率较高的情况下仍能实现较低的数据延迟波动水平。
3.4 基于多播的随机网络诊断
Caceres等人开发了一种基于端到端多播流量测量的方法来推测网络内部特征。他们通过观察多播接收器检测到的数据包丢失情况，并在此基础上提出了基于极大似然估计的方法来计算内链路数据包丢失率，并通过模拟验证了这一方法的有效性。Lo等人则详细阐述了如何利用端到端多播测量技术推断逻辑多播树中的网络延迟特性，在时延独立假设下推导出了一种算法，在实测得到的时延分布基础上估计每个内线路上的具体时延分布和利用率。他们进一步对估计量的各种统计特性进行了分析，并证明其具有强一致性及渐近正态性。在模型模拟实验中证实了该方法在推测内线路上数据包丢失率方面的准确性和收敛性，并与实际分析预测结果高度一致
Duffield 等人提出了基于多播流量端到端延迟数据的逻辑 multicast 树延迟方差估算方法。Caceres 等人开发并分析了两种基于端到端丢包测量的 multicast 拓扑推断方案。第一类是分组方法，在该方案中我们依赖于接收器集合共享路径上的丢失数据来进行估算，并选择丢失最严重的节点集合来确定兄弟节点关系；第二类则是最大似然分类器方案，在此方案中我们利用链路丢包估计量具有最大似然性质这一特点来推导最优拓扑结构；通过对这些方法准确性和计算复杂度展开对比分析
第三位的关键议题是网络系统的可识别性挑战，在各类网络诊断模式中将逐一阐述该议题所面临的现有研究手段及其发展动态。
4 网络诊断的可识别性
网络诊断中的"可辨识性"问题表明了网络内部状态能否通过远程路径测量实现唯一重建。例如，在恢复可加属性链路度量时（如延迟或基于丢包率的数据），只有当路由矩阵的秩与链路数量相等时才能实现这种状态重建。然而，在实际应用中由于链路数量通常很大这一条件往往难以满足因此通常需要探测到至少与之相当数量的探测路径才能保证这种可识别性的实现而这将导致高昂的成本
在确保可识别性方面存在不足时
现有的防御策略多部署于主机系统中，并且能够识别特定目标系统的异常行为。然而，在制定有效的SYN攻击防御机制以及探索相关防护措施的实现路径方面仍存在显著的技术挑战，在网络诊断领域针对SYN攻击的研究仍处于探索阶段。
4.1 布尔网络诊断的可识别性
Ma等人探讨了布尔网络诊断在一般网络拓扑中实现节点故障定位的可能性。他们通过定义节点故障的最大可识别性（maximal identifiability），即给定拓扑中可唯一定位的同时发生的最多数量的节点故障来进行度量。研究者在不同的探测方案下，在考虑网络拓扑结构、监视器位置、测量路径限制以及同时发生故障的最大数量等因素的基础上，提出了故障定位所需条件的充要性证明，并展示了可以用多项式时间算法确定这些条件及最大可识别性的边界值。在实际应用中，网络管理员往往只需要关注全局拓扑中少数几个关键节点子集即可满足其管理需求。Ma等人继续研究了一个与现有文献类似的课题，在新的研究框架下明确了确保仅从全局拓扑确定关键节点子集可识别性的必要条件
不同于以往的研究工作，在设定不同的监控路径数量以及施加不同的网络拓扑限制条件（包括路由方案选择与最长路径长度设定）的情况下
下面介绍可加网络诊断中链路的可识别性。
4.2 可加网络诊断的可识别性
许多学者致力于从秩亏路由矩阵中正确恢复内部状态的优化算法的研发工作。这些方法主要可分为以下几个类别：首先,探讨不同网络状态下恢复可行性及所需条件;其次,在有限探测预算内进行恢复算法的设计工作;再次,在有限探测预算内进行路由矩阵的设计,并提升识别效能;最后,在有限监控成本下优化部署方案以提升识别效能。
确定所有链路的度量参数时需要使用一个具有秩与链路数量相等的路由矩阵；然而由于当前可测量的链路数目较多，在寻找满足这一条件的实际路由矩阵方面仍存在较大挑战，并且还存在拓扑依赖关系问题；当该类矩阵的秩不足时会导致解的结果不够精确或可靠；Chen等人指出仅凭一组测量数据通常无法唯一确定所有单个链路的具体测量值，并因此提出了矩量法这一通用估计方法；Nguyen等人则建议在进行小规模集合度量时采用布尔代数学习先验知识的方法以解决潜在的歧义性问题；拥塞事件发生的概率可以通过布尔代数的基本性质从同一组测量数据中唯一确定；Tati等人研究了在已知故障分布情况下的路径选择优化问题：在探测费用预算约束下寻求最优路径以最大化系统对故障的鲁棒检测能力；他们证明该优化问题属于NP难问题并提出了一种具有近似比保证的RoMe算法
另一个研究方向旨在规划监视器的部署位置及其探测路径设计，并通过该策略来保障系统的识别能力。研究表明，在有向网络架构下（其中各条线路在不同方向上的负载指标存在差异），并非所有线路负载指标都能被完全识别出来——只有当每个非孤立节点都配备有独立监视器时才能实现这一点。而在无向网络架构下——即各线路双向通行——Gopalan等人首次提出，在探测路径中可能存在回环情况时，在该拓扑结构上实现线路负载指标识别所需的必要且充分条件是什么？进一步证实三边连通性这一性质既是利用单一监视器实现线路负载指标识别的关键条件也是采用监控回路来进行此类识别的基础前提。
然而，在网络诊断领域中通常会尽量避免涉及环状路径的情况出现。此外
中所有的链路度量的充要条件是扩展图
是3点连通的。（
是在
上添加两个虚拟监视器
条在每一对虚拟-实际监视器之间的虚拟链路。）
准确地测定每条链路的性能指标，则要求独立测量路径的数量必须与链路数量相等。这表明系统的可识别性取决于其拓扑结构特征。在稀疏拓扑环境中实现可识别性往往需要部署大量监控节点配合才能达到目标效果。面对这一挑战性问题,Ma等人提出了一种有限数量监视器的部分识别方法,该方法通过优化这些监视器的位置来尽可能多地检测到可识别的链路,并在确定时间内计算所有可能的可识别链路数量的基础上开发了一种高效的贪心算法,该算法能够逐步部署监视器以最大化可检测到的链路数量。He等人则考虑了动态网络环境下监视器布局优化的问题,从路径度量中筛选出新增加的可加链路度量并据此推导出一套鲁棒性强化的监控布局方案,该方案能够根据不同的性能-复杂性权衡关系提供多样化的选择以适应多种可能网络拓扑结构的需求。此外,文献还研究了在给定监测集的情况下如何优化测量路径的问题,并开发了一种高效算法用于计算最优测量路径集合。最后,文献提出了一个能全面覆盖网络状态且具有经济性的最小端到端探测链条选择方案。
4.3 针对可识别问题的新解决方案
4.3.1 基于边界的可加网络诊断
网络诊断利用端到端测量来评估内部网络连接的关键性能参数。该领域中的现有研究主要依赖于布尔值进行判断：当确定一条链路是可识别时，则会提供相应的准确评估结果；而在不可辨识的情况下，则无法提供相关性能信息。然而，在多数场景下，在拥塞检测或者异常事件监测等方面往往只需掌握大致情况范围即可实现目标。这种需求推动了开发能够估算网络节点间路径带宽范围算法的努力
研究团队将基于布尔网络的故障诊断方法扩展至基于边界加权的新框架，并针对无法确定的具体线路，在该框架下推导出了性能上下限。在这一过程中, 他们开发了一种有效算法用于计算最优误差界限, 并进一步提出了一种优化策略以减少所需监测路径数量, 从而实现对最紧总误差界的快速收敛。此外, 研究团队设计了一种动态增加监视器位置的方法, 在每一步都尽可能缩小整体错误范围, 并在此过程中实现了对现有资源的有效利用优化。最后, 通过对多种典型场景下的性能对比分析表明, 所提出的方案相较于随机化部署方案或旨在最多识别可监测线路的情况下, 显现出明显的优势
先前的研究发现表明，在识别所有链路度量时需要投入大量资源。这一发现促使Li等人专注于研究一组特定链路性能边界相关的网络诊断问题。为了实现这一目标，作者开发了一种能够同时确定所有感兴趣链路最紧上界和下界的高效方法。在此基础上，作者进一步提出了一种创新性的方法：通过将新的监视器放置在现有监视器之上来提升感兴趣链路性能边界的最大化收敛速度算法效率。经过理论分析与实验验证后，在真实网络拓扑结构基础上展示了该算法的有效性。
此外，在带宽网络诊断的问题中关注其可识别性时
4.3.2 基于边界的带宽网络诊断
早期网络诊断的目标是对网络各条线路的具体性能进行数值化评估。
随着人们意识到现有方法在实际应用中可能出现偏差，
研究方向转向采用布尔网络诊断法，
在该方法中，
每条线路被简单判定为"好"或"坏"（当单条线路性能指标低于设定阈值时即被视为故障线路）。
尽管布尔方法具有较强的实用性，
但其分辨能力较为粗略。
Zarifzadeh等研究者提出了一种融合原有技术优势的新框架：
既能区分出"好"线路与"坏"线路，
又能推算出故障线路性能评估范围。
研究者将range to-mography框架应用于两个路径性能度量函数：
一方面考虑可叠加的链路度量指标（如延迟、丢包率等对数形式）；
另一方面则基于瓶颈链路决定路径最小度量指标（如可用带宽等）。
针对每种情况分别设计了有效的算法实现。
Feng等人开发了一个多项式时间算法CTB（compute the tightest bounds）来系统性地解决从端到端路径中的带宽推断问题，并准确确定内部链路的带宽值。该算法不仅输出所有可识别链路的确切带宽值，并且还能计算出无法确定的所有链路（基于给定测量路径集合）的最大可能误差范围。在未预先指定任何测量路径的情况下，作者证明了构建这些测量路径所需的复杂性，并展示了如何通过强化学习方法（reinforcement learning, RL）来优化这一过程。这种RL方法整合了网络性能诊断的知识，并结合了离线训练与在线预测能力。通过在真实网络和仿真环境中进行评估的结果表明，在现有方法的基础上显著降低了所需测量路径的数量的同时也大幅减少了各条链路平均误差范围。
4.4 不可识别性带来的风险
当识别不可靠时，则常用伪逆法与文献中所述方法来重建路径状态。近期研究发现，在可识别属性无法满足的情形下存在遭受攻击的可能性。Zhao团队提出替罪者问题，并通过理论分析与实验验证来探讨针对网络诊断的应用可行性。主要考察了主动参与者攻击、最大破坏性攻击以及混淆替罪者攻击等三种主要类型。Chiu团队则在无法定位攻击源的情况下尝试向某些路径引入延迟以降低网络性能水平，并通过真实拓扑结构评估表明所提出的策略能够显著减少通信性能损失的同时避免传统网络层析定位技术的探测到此攻击行为。此外他们还设计出一种新的组合优化算法来确定最优攻击策略并取得了一定的研究成果
替罪羊攻击可以由丢包攻击实现，它通过丢弃或延迟数据包来破坏网络。丢包攻击主要包括黑洞攻击和灰洞攻击。黑洞攻击是一种吸引并丢弃所有路由到恶意节点报文的攻击，而灰洞攻击是一种选择性转发攻击，只丢弃特定的报文。现有的防御策略通常部署在主机系统上，直接检测特定受害者的异常。例如，包标记和过滤机制可以标记合法的报文，这样受害的边缘路由器就可以对攻击流进行过滤。有一个IP回溯机制，可以追溯到伪造IP包的真正来源。流量监控用于检测异常包的转发，并设计了新的策略来检测丢弃或错误路由包的路由器。替罪羊攻击的防御难度和防御成本未知，目前有一些新提出的防御方法。这是一个实际问题。
最后，本文将介绍网络诊断在新领域的新发展。
5 网络诊断的新发展
5.1 基于网络编码的网络诊断
传统的网络诊断主要依赖于内部节点来实现数据包的转发。由于这种转发过程并未被直接记录在数据包中,导致对推断问题的研究具有较高的难度。然而,当内部节点采用网络编码技术时,来自不同传入链路的数据包会被组合在一起并发送到传出链路,这样在数据包中就能记录这些节点从多个不同的传入链路接收的数据,从而极大地方便了推理过程。这种思路已在多种领域得到了应用,包括在网络拓扑推断、路径优化以及端到端延迟估计等方面,它不仅在提高检测精度的同时也降低了计算复杂度。相关的综述文献详细探讨了基于网络编码技术的新型诊断方法
基于网络编码的新型网络诊断技术主要用于拓扑结构推断、链路丢包率估算以及时延测量等方面的研究与应用。文献研究首次将现代编码理论与图论分析相结合，在此基础上建立了新型的网络安全检测框架。研究发现，在节点接收端解码得到的一组线性组合码块中隐含了原始数据包的空间信息特征这一关键性质可被有效提取并加以利用；研究首次提出了一种新型的低复杂度时延估计方法；研究首次在无线传感器网环境下实现了一种新的带宽消耗低的同时具有较高估计精度的链路丢包率估计方案；研究首次提出了一种基于子空间性质的新颖时延相关性估计方法
此外，在采用网络编码机制的基础上开展网络诊断研究同样可以应用于瓶颈发现与故障定位领域。研究者们通过拓展传统网络诊断的应用范围，在点对点环境下实现了瓶颈识别与故障定位技术的发展，并基于观察结果提出了避免出现于网络编码架构下的点对点网络中的瓶颈与集群现象的拓扑管理策略。研究者首次提出了通过嵌入于随机网络编码机制中的编码系数来推断故障模式的方法，在这一过程中并未引入额外的探测开销即可实现目标效果。
需要注意的是，在网络编码实现中，中间节点不仅支持对信息进行编码处理并转发，并且接收节点通过解码过程能够恢复原始数据。在网络诊断过程中实现网络编码带来的理论利益，则需要从多个层面协调探测源与内部节点的编码能力，并涉及复杂的数学运算和较高的计算复杂度问题。这使得该技术的实际应用受到一定限制
5.2 基于深度神经网络的网络诊断
Ma等人开创性地提出了基于深度神经网络的一种轻量级断层扫描框架（NeuTomography），该框架专为网络监测任务设计，在无需对网络施加任何额外假设的前提下实现了对节点间子集端到端路径的有效测量。他们开发了路径增强层析成像（path augmented tomography, PAT）算法，并将其作为性能预测的基础方法之一，在这一过程中巧妙地利用了估计性能边界所提供的增强型输入数据来提升预测精度。尽管研究团队在该领域缺乏任何关于网络拓扑结构的前提知识，在这种情况下他们依然成功构建了一种能够利用所提出的层析框架重建网络拓扑关系的方法。通过大量真实数据测试发现，在预测任意路径性能方面该方法展现出极高的准确性水平；而Sartzetakis等人则提出了一个新的用于网络诊断的机器学习公式；研究结果表明与现有方法相比该方案显著提升了估计精度尤其是在面临未知链路数量较高且针对特定源目标对存在多种路由决策的情况下表现尤为出色
Ibraheem团队开发出一种结合网络安全分析与深度学习算法的新方案。该方案旨在通过选取关键路由数据构建训练集，并预测未被直接监控的道路传输时延。研究者进一步利用部分网络安全指标构建预测模型，在车辆网中实现对未测路段传输性能的有效估算。实证结果显示，在仅监控核心路段的情况下就能精确评估整体传输质量。随后的研究者们将现有文献中的延迟估算技术拓展至链路级分析层面，并分别开发了基于深度神经元架构的安全网路解析算法与传统的网络安全指标解析方案。接着他们对比分析了这两种算法的技术特性及其适用场景
5.3 NFV中节点故障定位
NFV展现出显著的发展势头，在常规IT基础设施上部署虚拟网络功能（VNF）以提供内部服务成为可能。现有研究主要聚焦于从提供者角度实现VNF服务配置，在用户层面对资源质量验证方面则相对薄弱。Lin团队开发了一种推理架构，在解决这一问题方面迈出了关键进展。本文提出的框架通过对VNF实例化所形成覆盖区域的状态与结构进行推断，并精确测量流量入口端点与出口端点之间的关键节点（如分支或连接节点），从而实现了对服务链相关信息的有效解析。这项研究不仅推动了拓扑推理技术的进步，在考虑一般度量路径的同时构建了更具通用性的拓扑模型，并深入分析了服务链信息的重要性。基于真实网络拓扑结构的实际评估结果表明，在提升服务配置精度方面本文提出的方法优于现有方案，并凸显出服务链信息在揭示底层网络架构方面的关键作用
6 总结与讨论
本文系统梳理了网络安全领域的基础理论，在布尔型、可加型、带宽型及随机型等主要模型中展开了深入探讨，并详细研究了监视器部署与信标服务部署策略的同时还重点阐述了"可识别性"这一核心问题。即使放弃"可识别性"这一前提条件，在实际应用中仍需警惕潜在的安全威胁。为提升检测效率，在不依赖传统边界感知的基础上引入边界感知型新型检测方案的同时还扩展至覆盖NFV（软件定义网）环境下的节点故障定位问题。
当前，在网络安全领域存在着诸多亟待深入探究的问题
在网络诊断方面存在另一个挑战在于现有方案所基于的网络模型过于简化。尽管如此，在大多数现有研究中仍假设路由在测量期间保持不变，并且链路性能处于稳定状态。然而，在实际应用中这些假设仅在负载较轻时基本成立。为了进一步提高网络诊断的有效性深入研究具有实际意义的关键链路参数，并探索能够反映时空相关性的更复杂模型将显著提升网络诊断的有效性