基于固定探针位置的带内网络遥测最优探测路径规划方法

摘要

本发明实施例提供了一种基于固定探针位置的带内网络遥测最优探测路径规划方法，包括：将各探针设备接入点确定为指定节点；将所有待探测的节点中除指定节点之外的节点，确定为目标点集，并在目标点集中确定所有的奇点；在目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；基于各指定节点、各奇点以及各奇点对应的目标最短路径，构造节点对应的加权图；为加权图添加辅助边，得到添加辅助边之后的目标连通图；针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。本发明实施例，在对网络稳定遥测的情况下，减小网络遥测的开销和网络负载。

权利要求

1.一种基于固定探针位置的带内网络遥测最优探测路径规划方法，其特征在于，所述方法包括：将各探针设备接入点确定为指定节点，各所述探针设备接入点为：预先指定的待接入探针设备的网络节点；

将所有待探测的节点中除所述指定节点之外的节点，确定为目标点集，并在所述目标点集中确定所有的奇点，所述奇点表示节点度数为奇数的节点，所述节点度数用于表示与该节点相关联的边的条数；

在所述目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；

基于各所述指定节点、各所述奇点以及各所述奇点对应的目标最短路径，构造节点对应的加权图；

为所述加权图添加辅助边，得到添加辅助边之后的目标连通图；

针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径；

其中，所述针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤，包括：确定所述目标连通图中包含奇点的个数；

在所述奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找所述目标连通图中的第一欧拉路径，并将所述第一欧拉路径确定为目标探测路径；

在所述奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

2.根据权利要求1所述的方法，其特征在于，所述针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径的步骤，包括：针对每一奇点，确定该奇点与其余各所述奇点之间的第一最短路径，以及该奇点与所述指定节点之间的第二最短路径；

将所述第一最短路径与所述第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

3.根据权利要求1所述的方法，其特征在于，所述为所述加权图添加辅助边，得到添加辅助边之后的目标连通图的步骤，包括：针对所述加权图，利用最小权重完全匹配算法，得到所述加权图中权重最小且互不相交的边集；

根据所述边集，沿各所述奇点对应的目标最短路径逐跳添加辅助边，得到目标连通图。

4.根据权利要求1所述的方法，其特征在于，所述分别提取每一对奇点之间的子路径的步骤，包括：基于每一对奇点，对所述目标连通图进行分割，得到多个包含奇点个数不超过两对的子连通图；

针对每一子连通图，利用Fleury弗罗莱算法寻找所述子连通图中的第二欧拉路径，并将所述第二欧拉路径确定为所述子连通图对应的子路径，得到每一对奇点之间的子路径。

5.根据权利要求1所述的方法，其特征在于，在所述目标点集中不存在奇点的情况下，基于网络中所有待探测的节点，以及各节点之间的边生成无向连通图；将所述无向连通图确定为目标连通图，并执行针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤。

6.一种基于固定探针位置的带内网络遥测最优探测路径规划装置，其特征在于，所述装置包括：接入点确定模块，用于将各探针设备接入点确定为指定节点，各所述探针设备接入点为：预先指定的待接入探针设备的网络节点；

奇点确定模块，用于将所有待探测的节点中除所述指定节点之外的节点，确定为目标点集，并在所述目标点集中确定所有的奇点，所述奇点表示节点度数为奇数的节点，所述节点度数用于表示与该节点相关联的边的条数；

路径确定模块，用于在所述目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；

加权图构建模块，用于基于各所述指定节点、各所述奇点以及各所述奇点对应的目标最短路径，构造节点对应的加权图；

辅助边添加模块，用于为所述加权图添加辅助边，得到添加辅助边之后的目标连通图；

路径获取模块，用于针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径；

其中，所述路径获取模块，包括：

奇点个数确定子模块，用于确定所述目标连通图中包含奇点的个数；

第一路径获取子模块，用于在所述奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找所述目标连通图中的第一欧拉路径，并将所述第一欧拉路径确定为目标探测路径；

第二路径获取子模块，用于在所述奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

7.根据权利要求6所述的装置，其特征在于，所述路径确定模块，包括：第一路径确定子模块，用于针对每一奇点，确定该奇点与其余各所述奇点之间的第一最短路径，以及该奇点与所述指定节点之间的第二最短路径；

第二路径确定子模块，用于将所述第一最短路径与所述第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

8.一种电子设备，其特征在于，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；

存储器，用于存放计算机程序；

处理器，用于执行存储器上所存放的程序时，实现权利要求1‑5任一所述的方法步骤。

9.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1‑5任一所述的方法步骤。

说明书

基于固定探针位置的带内网络遥测最优探测路径规划方法

技术领域

[0001] 本发明涉及通信技术领域，特别是涉及一种基于固定探针位置的带内网络遥测最优探测路径规划方法。

背景技术

[0002] 随着互联网应用的不断发展，基于人工智能、大数据等概念衍生出的产品技术正经历着快速升级，随之而来的是对基础网络性能更高的要求，例如，接入带宽的不断增加要求网络转发能力长时间维持可靠状态；实现端到端业务的低延时转发也要求大规模复杂网络的运维稳定可控。使得数据中心网络的维护和故障排除至关重要，现有网络管理协议，例如，SNMP(Simple Network Management Protocol，简单网络管理协议)可以使网络管理员能够管理网络效能，发现并解决网络问题以及规划网络增长，通过SNMP接收随机消息网络管理系统获知网络出现的问题，然而，由于SNMP轮询机制效率低，不能很好地适应当今高密度数据中心激烈的流量变化，对网络问题做出及时的反应，从而无法实现细粒度的监控。

[0003] NT(Network Telemetry，网络遥测)是一种新的快速故障排除模型，能够检测故障并隔离故障，按照网络状态整合数据，主动将网络设备状态信息推送到监控设备上，数据具有很强的时效性。基于此，相关技术中，使用INT(In‑band Network Telemetry，带内网络遥测)对网络进行探测，INT允许探测包在通过数据平面管道时查询设备内部状态，比如数据包的排队时延等。

[0004] 为了实现全网络的遥测，相关技术中，基于网络遥测的探测路径规划方法使用DFS(Depth‑First‑Search，深度优先搜索算法)规划探测路径。具体的，基于网络中所有待探测节点构成无向连通图，在无向连通图中随机选定一个待探测节点作为起始节点，基于起始节点，创建待探测路径；基于无向连通图，针对待探测路径中的下一节点，选择该节点中未被访问的一条边，将所选择的边对应的另一端点添加至待探测路径中，并将所选择的边标记为已访问；在下一节点中不包含未被访问的边时，将该节点标记为已完全访问，并回溯到待探测路径中与第一个下一节点具有并列位置关系的另一节点，将另一节点更新为起始节点，创建新的待探测路径，以及执行针对待探测路径中的下一节点，选择该节点中未被访问的一条边的步骤，至无向连通图中所有的节点均已完全访问。最后，将无向连通图中所有的节点均已访问时得到的待探测路径，确定为目标探测路径。

[0005] 然而，因使用DFS规划探测路径是对无向连通图中所有节点进行遍历，进而无法保证生成的路径数据最少，需要的INT探测包较多，使得网络遥测的开销增大，网络负载加重，且在网络出现故障导致网络拓扑结构变化的情况下，需要重新确定探测路径以及重新连接探针设备，使得网络遥测不稳定。

发明内容

[0006] 本发明实施例的目的在于提供一种基于固定探针位置的带内网络遥测最优探测路径规划方法，以在对网络稳定遥测的情况下，减小网络遥测的开销和网络负载。具体技术方案如下：

[0007] 第一方面，本发明实施例提供了一种基于固定探针位置的带内网络遥测最优探测路径规划方法，所述方法包括：

[0008] 将各探针设备接入点确定为指定节点，各所述探针设备接入点为：预先指定的待接入探针设备的网络节点；

[0009] 将所有待探测的节点中除所述指定节点之外的节点，确定为目标点集，并在所述目标点集中确定所有的奇点，所述奇点表示节点度数为奇数的节点，所述节点度数用于表示与该节点相关联的边的条数；

[0010] 在所述目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；

[0011] 基于各所述指定节点、各所述奇点以及各所述奇点对应的目标最短路径，构造节点对应的加权图；

[0012] 为所述加权图添加辅助边，得到添加辅助边之后的目标连通图；

[0013] 针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0014] 可选地，所述针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径的步骤，包括：

[0015] 针对每一奇点，确定该奇点与其余各所述奇点之间的第一最短路径，以及该奇点与所述指定节点之间的第二最短路径；

[0016] 将所述第一最短路径与所述第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

[0017] 可选地，所述为所述加权图添加辅助边，得到添加辅助边之后的目标连通图的步骤，包括：

[0018] 针对所述加权图，利用最小权重完全匹配算法，得到所述加权图中权重最小且互不相交的边集；

[0019] 根据所述边集，沿各所述奇点对应的目标最短路径逐跳添加辅助边，得到目标连通图。

[0020] 可选地，所述针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤，包括：

[0021] 确定所述目标连通图中包含奇点的个数；

[0022] 在所述奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找所述目标连通图中的第一欧拉路径，并将所述第一欧拉路径确定为目标探测路径；

[0023] 在所述奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

[0024] 可选地，所述分别提取每一对奇点之间的子路径的步骤，包括：

[0025] 基于每一对奇点，对所述目标连通图进行分割，得到多个包含奇点个数不超过两对的子连通图；

[0026] 针对每一子连通图，利用Fleury弗罗莱算法寻找所述子连通图中的第二欧拉路径，并将所述第二欧拉路径确定为所述子连通图对应的子路径，得到每一对奇点之间的子路径。

[0027] 可选地，在所述目标点集中不存在奇点的情况下，基于网络中所有待探测的节点，以及各节点之间的边生成无向连通图；将所述无向连通图确定为目标连通图，并执行针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤。

[0028] 第二方面，本发明实施例提供了一种基于固定探针位置的带内网络遥测最优探测路径规划装置，所述装置包括：

[0029] 接入点确定模块，用于将各探针设备接入点确定为指定节点，各所述探针设备接入点为：预先指定的待接入探针设备的网络节点；

[0030] 奇点确定模块，用于将所有待探测的节点中除所述指定节点之外的节点，确定为目标点集，并在所述目标点集中确定所有的奇点，所述奇点表示节点度数为奇数的节点，所述节点度数用于表示与该节点相关联的边的条数；

[0031] 路径确定模块，用于在所述目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；

[0032] 加权图构建模块，用于基于各所述指定节点、各所述奇点以及各所述奇点对应的目标最短路径，构造节点对应的加权图；

[0033] 辅助边添加模块，用于为所述加权图添加辅助边，得到添加辅助边之后的目标连通图；

[0034] 路径获取模块，用于针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0035] 可选地，所述路径确定模块，包括：

[0036] 第一路径确定子模块，用于针对每一奇点，确定该奇点与其余各所述奇点之间的第一最短路径，以及该奇点与所述指定节点之间的第二最短路径；

[0037] 第二路径确定子模块，用于将所述第一最短路径与所述第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

[0038] 可选地，所述辅助边添加模块，包括：

[0039] 边集获取子模块，用于针对所述加权图，利用最小权重完全匹配算法，得到所述加权图中权重最小且互不相交的边集；

[0040] 辅助边添加子模块，用于根据所述边集，沿各所述奇点对应的目标最短路径逐跳添加辅助边，得到目标连通图。

[0041] 可选地，所述路径获取模块，包括：

[0042] 奇点个数确定子模块，用于确定所述目标连通图中包含奇点的个数；

[0043] 第一路径获取子模块，用于在所述奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找所述目标连通图中的第一欧拉路径，并将所述第一欧拉路径确定为目标探测路径；

[0044] 第二路径获取子模块，用于在所述奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

[0045] 可选地，所述第二路径获取子模块，具体用于：

[0046] 基于每一对奇点，对所述目标连通图进行分割，得到多个包含奇点个数不超过两对的子连通图；

[0047] 针对每一子连通图，利用Fleury弗罗莱算法寻找所述子连通图中的第二欧拉路径，并将所述第二欧拉路径确定为所述子连通图对应的子路径，得到每一对奇点之间的子路径。

[0048] 可选地，在所述目标点集中不存在奇点的情况下，基于网络中所有待探测的节点，以及各节点之间的边生成无向连通图；将所述无向连通图确定为目标连通图，并触发所述路径获取模块，执行针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤。

[0049] 第三方面，本发明实施例提供了一种电子设备，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；

[0050] 存储器，用于存放计算机程序；

[0051] 处理器，用于执行存储器上所存放的程序时，实现上述第一方面所述的方法步骤。

[0052] 第四方面，本发明实施例提供了一种计算机可读存储介质，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现实现上述第一方面所述的方法步骤。

[0053] 本发明实施例有益效果：

[0054] 本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0055] 当然，实施本发明的任一产品或方法并不一定需要同时达到以上所述的所有优点。

附图说明

[0056] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，还可以根据这些附图获得其他的实施例。

[0057] 图1为本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法的流程示意图；

[0058] 图2为本发明实施例提供的一种最优探测路径规划架构示意图；

[0059] 图3a为本发明实施例提供的一种节点度数示意图；

[0060] 图3b为本发明实施例提供的另一种节点度数示意图；

[0061] 图3c为本发明实施例提供的再一种节点度数示意图；

[0062] 图4a为本发明实施例提供的一种节点添加辅助边的示意图；

[0063] 图4b为本发明实施例提供的另一种节点添加辅助边的示意图；

[0064] 图5为本发明实施例提供的一种带内网络遥测的图形示意图；

[0065] 图6为本发明实施例提供的一种节点加权图示意图；

[0066] 图7为本发明实施例提供的一种添加辅助边之后的目标连通图示意图；

[0067] 图8为本发明实施例提供的一种获取探测路径的实施方式流程示意图；

[0068] 图9为本发明实施例提供的一种对目标连通图进行分割的示意图；

[0069] 图10为本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划装置的结构示意图；

[0070] 图11为本发明实施例提供的一种电子设备的结构示意图。

具体实施方式

[0071] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员基于本申请所获得的所有其他实施例，都属于本发明保护的范围。

[0072] 为了解决相关技术中，无法保证生成的路径数据最少，需要的INT探测包较多，使得网络遥测的开销增大，网络负载加重，且在网络出现故障导致网络拓扑结构变化的情况下，需要重新确定探测路径以及重新连接探针设备，使得网络遥测不稳定的问题，本发明实施例提供了一种基于固定探针位置的带内网络遥测最优探测路径规划方法，该方法包括：

[0073] 将各探针设备接入点确定为指定节点，各所述探针设备接入点为：预先指定的待接入探针设备的网络节点；将所有待探测的节点中除所述指定节点之外的节点，确定为目标点集，并在所述目标点集中确定所有的奇点，所述奇点表示节点度数为奇数的节点，所述节点度数用于表示与该节点相关联的边的条数；在所述目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；基于各所述指定节点、各所述奇点以及各所述奇点对应的目标最短路径，构造节点对应的加权图；为所述加权图添加辅助边，得到添加辅助边之后的目标连通图；针对所述目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0074] 本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0075] 本发明实施例基于固定探针位置的带内网络遥测最优探测路径规划方法，可以通过电子设备实现或电子设备上的控制器实现，具体的，该电子设备可以为个人电脑或服务器等。

[0076] 下面进行具体说明，参见图1，图1为本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法的流程示意图，该方法可以包括：

[0077] S101，将各探针设备接入点确定为指定节点。

[0078] 本发明实施例中，可以采用集中式路径规划方法对网络的探测路径进行规划，在集中式架构中，收集整个网络拓扑的信息以进行全局最优路径规划。本发明实施例提供的一种基于固定探针位置的带内网络遥测，可以称为INT‑probe(INT‑探针)，INT‑probe依赖于源路由来指定探测包通过网络的路由，该源路由即为指定的转发路径。源路由信息由中央控制器上的路径规划方法计算得到，下发到每个探测包生成器中，进而嵌入到探测包的包头中，探测包收集器将带有INT信息的探测包发送回控制器。当网络拓扑结构发生变化时，控制器将重新计算探测路径并更新探测包生成器和收集器上相应的配置信息。

[0079] 实际应用中，并不是所有的网络设备都可以连接探针设备作为探测路径的端点。例如，将探针设备连接到spine/core交换机将占用原来用于流量负载平衡的链路，并破坏数据中心网络的对称拓扑结构，将探针设备连接到主干路由器则需要互联网服务提供商的进一步许可等等。故而，本发明实施例中，预先指定待接入探针设备的网络节点，即各探针设备接入点，并将各探针设备接入点确定为指定节点，避免探针设备连接到无法连接的网络中间节点或者网络核心节点上，以使得INT‑probe不会随着网络拓扑的改变而改变探针设备的连接点，保证遥测功能不发生严重中断。

[0080] 如图2所示，本发明实施例中，可以预先指定待接入探针设备的网络节点E和F，即节点E和F为指定节点，该指定节点可以为一个网络设备子集，用于探针设备的接入点，使得探针设备只允许连接到这些指定的网络设备上。

[0081] 为了避免在网络拓扑结构发生变化时，指定的探针设备接入点重新连接探针设备，可以将一个物理探针设备静态地绑定到每个指定节点，例如，两个探针设备分别绑定到节点E和F。实际应用中，指定节点可以根据网络的实际情况确定，以及可以根据实际需要确定指定节点的数量，且可以通过限制指定节点的数量，进一步根据需要控制获取的探测路径数，以减少探针设备的资本支出和控制器上的遥测开销。

[0082] 本发明实施例在探测路径的规划过程中，因将物理探针设备与指定节点绑定，计算得到的探测路径端点仍可能在拓扑更改期间发生变化，故而，可以将探测功能进行虚拟化。具体的，每个物理探针设备可以处于激活或非激活状态，当处于激活状态时，可以充当虚拟探测包生成器、虚拟探测包收集器，甚至同时充当两者，例如，在图2中，连接节点E的探测设备处于非激活状态，而连接节点F的探测设备处于激活状态，同时充当虚拟探针发生器和收集器(探测路径可以为F‑>C‑>E‑>B‑>D‑>A‑>E‑>B‑>F‑>A‑>D‑>C‑>F)。实际应用中，为了减少中断延迟，可以预先分配虚拟探测设备实例，以便随时响应来自控制器的物理探针设备状态切换指令。

[0083] S102，将所有待探测的节点中除指定节点之外的节点，确定为目标点集，并在目标点集中确定所有的奇点。

[0084] 其中，奇点表示节点度数为奇数的节点，节点度数用于表示与该节点相关联的边的条数。

[0085] 为了进行网络范围的遥测，预先指定待接入探针设备的网络节点(即指定节点，例如，ToR(Top of Rack，架顶)交换机或边缘路由器等)来连接物理探针设备。每个INT探测路径应该由一个物理探针设备(即，虚拟探测包生成器)生成，并由另一个(或同一个)物理探针设备(即，虚拟探测包收集器)收集。探测路径可以被定义为一个边序列，该边序列从连接有虚拟探测包生成器的网络设备开始，到连接有虚拟探测包收集器的另一个网络设备结束。探测路径长度可以定义为探测包所遍历的边序列中出现的边数。在一条探测路径中，探测包所遍历的边数可能不等于网络节点和边构成的图的边数，因为在实际部署中，探测包可能遍历某条边不止一次，而这在边序列中将被记录为多条边。

[0086] 可以将指定节点确定为指定节点集S，那么网络里所有待探测的节点中除指定节点之外的节点组成的目标点集，即指定节点集S的补集。在确定目标点集后，可以进一步确定目标点集中所包含的奇点。

[0087] 实际应用中，在探测路径中的任何中间节点的度数总是偶数，对应的该中间节点为偶点，如图3a所示；而路径中开始和结束节点的度数是奇数或偶数取决于开始节点和结束节点是否聚合到同一个节点上，如图3b和3c所示，即，如果一条路径的开始和结束节点聚合在同一节点上，那么该路径的开始/结束节点的度数为偶数，否则，该路径的开始/结束节点度数为奇数，该路径的开始/结束节点为奇点。

[0088] 作为本发明实施例一种可选的实施方式，在目标点集中不存在奇点的情况下，可以基于网络中所有待探测的节点，以及各节点之间的边生成无向连通图；将无向连通图确定为目标连通图，并执行步骤S106针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的操作。

[0089] 在目标点集中不存在奇点的情况下，表明探测路径的所有路径端点均属于指定节点，此时可以以网络中所有待探测的节点为顶点，结合各节点之间的边生成无向连通图，进一步将无向连通图确定为目标连通图，针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径，得到覆盖全网(目标连通图)且指定探针设备接入点的非重叠目标探测路径。这种情况下，可覆盖全网的总路径长度最小化，等于目标连通图的边数。

[0090] S103，在目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径。

[0091] 在目标点集中存在奇点的情况下，根据欧拉理论，表明一定有路径端点落入目标点集中，此时为使得目标点集中不再包含奇点，能够使用欧拉轨迹的路径规划方法获取目标探测路径，可以对目标点集中包含的奇点进行消除，具体的，可以执行步骤S103‑S105的操作消除目标点集中包含的奇点。

[0092] 本发明实施例一种可选的添加辅助边的实施方式中，可以通过为奇点添加辅助边的方式，以将奇点变为偶点。示例性的，如图4a所示，可以将辅助边e1’添加到e1，进而将待消除的奇点odd1的度数变为偶数。但是，简单地添加e1’会将奇点的度为偶数的邻居节点v1转换为奇点，如果v1在目标点集中则这种情况是不允许出现的。故而，为了消除指定奇点而不改变其相邻偶点的度数，可以选择另一个奇点(例如，图4a中的odd2)，并沿着两个奇点之间的选定路径逐跳添加辅助边(例如，在odd1和odd2之间添加辅助边e1’和e2’)。

[0093] 本发明实施例一种可选的添加辅助边的实施方式中，因本发明实施例中，连接到指定节点的物理探针设备可以处于激活状态，也可以处于非激活状态，因此，可以不关心指定节点集S中顶点的度数的奇偶性。在不关心添加的辅助边是否会改变集合S中偶点的度数的情况下，集合S中的节点即为指定节点，如图4b所示，在集合S中有两个顶点(v2和v3)，通过沿待消除的奇点odd1和S中顶点v2之间的路径添加辅助边e3’和e4’，可以将odd1的度数变为偶数，而不会更改其邻居顶点的度数。

[0094] 为添加最少的辅助边以消除目标点集中包含的奇点，可以先针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径。

[0095] 作为本发明实施例一种可选的实施方式，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径的实现过程，可以包括：

[0096] 针对每一奇点，确定该奇点与其余各奇点之间的第一最短路径，以及该奇点与指定节点之间的第二最短路径；

[0097] 将第一最短路径与第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

[0098] 如图5所示，指定节点表示为集合S，集合S中探测设备附着点即为指定节点(图5中A，B和C)，目标点集中的奇点为节点odd1，odd2，odd3以及odd4。针对每一奇点，确定该奇点与其余各奇点之间的第一最短路径，以及该奇点与指定节点之间的第二最短路径。例如：对于奇点odd1，odd1与集合S中的节点A的距离为1，因此奇点odd1与集合S之间的距离为1；奇点odd1与奇点odd2之间的最短距离为2，路由路径为odd1‑>D‑>odd2；奇点odd1与奇点odd3之间的最短距离为3，路由路径为odd1‑>D‑>odd2‑>odd3；奇点odd1与奇点odd4之间的最短距离为4，路由路径为odd1‑>D‑>odd2‑>E‑>odd4。进而，奇点odd1对应的目标最短路径为odd1‑>A。同理可以计算出，奇点odd2对应的目标最短路径为odd2‑>odd3，奇点odd4对应的目标最短路径为odd4‑>C等等。

[0099] S104，基于各指定节点、各奇点以及各奇点对应的目标最短路径，构造节点对应的加权图。

[0100] 在确定各奇点对应的目标最短路径后，可以根据各指定节点、各奇点之间的路径，以及各奇点对应的目标最短路径，构造节点对应的加权图，如图6所示。图6中，S1、S2、S3和S4为指定节点，与节点A、B和C等同，为了便于利用最小权重完全匹配算法确定边集，将S1与Si之间的权重设置为0，i＝2,3,4。示例性的，图6中，边(odd1,odd4)的权值为4，即两个奇点odd1和odd4之间的最短路径长度为4；边(odd2,s2)的权值为2，即odd2与集合S之间的最短路径长度为2。

[0101] S105，为加权图添加辅助边，得到添加辅助边之后的目标连通图。

[0102] 作为本发明实施例一种可选的实施方式，为加权图添加辅助边，得到添加辅助边之后的目标连通图的实现方式，可以包括：

[0103] 针对加权图，利用最小权重完全匹配算法，得到加权图中权重最小且互不相交的边集；

[0104] 根据边集，沿各奇点对应的目标最短路径逐跳添加辅助边，得到目标连通图。

[0105] 针对上述图6所示的加权图，可以利用最小权重完全匹配算法，得到加权图中权重最小且互不相交的边集。最小权重完全匹配算法，可以在加权图中，选取没有任何两条边存在公共顶点的边集，且每个顶点恰好与边集中的一条边相交，同时所选取的边集权重最小。

[0106] 示例性的，加权图可以表示为图Gp＝(Vp,Ep,w)，Vp表示加权图中的顶点，Ep表示加权图中的边，w表示加权图中边的权重，进而，可以利用最小权重完全匹配算法，找出加权图中权重最小且互不相交的边集M，使得图Gp中每个顶点与边集M中一条边相关联，且M中边的总权重最小。

[0107] 因边集M是图Gp的完全匹配，进而能够保证图Gp中的每个奇点仅与边集M中的一条边相关联。在图Gp中每条与奇点相关联的边都可以代表一种添加辅助边将奇点转化为度数为偶数的节点的方法。也就是说，寻找一个完全匹配边集M也就意味着，寻找一种在图Gp中沿着M所指示的路径消除目标点集中所有奇点的添加辅助边的方式。例如，在图6中，可以找到一个完全匹配M＝{(odd2,odd3)，(odd1,s1)，(odd4,s4)}。相应的，可以沿着odd2和odd3、odd1和S、odd4和S之间的三条最短路径逐跳添加辅助边，以消除目标点集中所有奇点。添加辅助边之后的目标连通图可以如图7所示，其中，odd表示目标点集中的奇点。

[0108] 如图6所示，使用一条权重为0的虚边连接每对指定节点或称墟节点(si,sj)，如果边(si,sj)在M中已经出现的话，就不需要再为它们添加相应的辅助边。但如果在Gp中的虚节点之间没有添加辅助边，最小权重完全匹配算法就不能被正确的执行。特别是如果虚节点之间的边被移除，那么就只剩下一条边与si相连，如(oddi,si)，此时如果M中的节点oddi和oddj之间进行了匹配，那么si不能在此时与oddi进行匹配，si就会变成一个没有被匹配的独立的节点。考虑到这种没有被匹配的虚节点通常是成对出现的，故而，在图Gp中将每两个独立的虚节点用一条权重为0的边连接起来，以便于正确的执行最小权重完全匹配算法，得到边集，获取目标探测路径。

[0109] S106，针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0110] 示例性的，如图7所示目标连通图中的指定节点包含2个奇点，最优探测路径的起点和终点分别位于节点A和C，获取的目标探测路径可以为：A‑>odd1‑>F‑>G‑>H‑>odd4‑>C‑>odd3‑>B‑>A ‑>odd1‑>D‑>odd2‑>odd3‑>odd2‑>E‑>odd4‑>C。

[0111] 目标连通图为消除目标点集中奇点之后得到的，故而，可以基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。因加权图中每条边都对应着各节点之间的最短路径，且所确定的边集为权重最小且互不相交的边集，故而，基于该边集添加辅助边之后得到的目标连通图，获取的目标探测路径为总路径长度最小的路径，能够减少网络遥测的开销。

[0112] 本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0113] 作为本发明实施例一种可选的实施方式，如图8所示，上述步骤S106中针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的实施方式，可以包括：

[0114] S1061，确定目标连通图中包含奇点的个数。

[0115] S1062，在奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找目标连通图中的第一欧拉路径，并将第一欧拉路径确定为目标探测路径。

[0116] S1063，在奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

[0117] 在图论中，没有奇点的目标连通图具有欧拉回路，只有一个奇数顶点的目标连通图不存在，具有2个奇数顶点的目标连通图具有从一个奇数顶点开始并在另一个顶点结束的欧拉轨迹，具有2k个奇数顶点的目标连通图包含至少k个不同的路径，一起遍历目标连通图的所有边缘一次。

[0118] 基于Euler‑trail欧拉轨迹的路径规划方法，可以在目标连通图中确定奇点的个数，进而在一对奇点之间反复提取路径，直到目标连通图中每个顶点的度数为零。也就是说，对于具有2k个奇点的目标连通图，能够获取k条非重叠的探测路径。

[0119] 作为本发明实施例一种可选的实施方式，分别提取每一对奇点之间的子路径的实施方式，可以包括：

[0120] 基于每一对奇点，对目标连通图进行分割，得到多个包含奇点个数不超过两对的子连通图；

[0121] 针对每一子连通图，利用Fleury弗罗莱算法寻找子连通图中的第二欧拉路径，并将第二欧拉路径确定为子连通图对应的子路径，得到每一对奇点之间的子路径。

[0122] 示例性的，如图9所示，目标连通图中包含顶点1‑7，其中，顶点1,3,5,6为奇点。随机选择两个奇点，对于奇点1,3，在提取路径1‑4‑3之后，将图9中左侧的目标连通图拆分成右侧的两个子连通图，进而针对子连通图{1,2,3}，因没有奇点，利用Fleury算法寻找该子连通图中的第二欧拉路径为1‑2‑3‑1，该第二欧拉路径1‑2‑3‑1为子连通图{1,2,3}对应的子路径。针对子连通图{4,5,6,7}，因只有一对奇点，也可以利用Fleury算法寻找该子连通图中的第二欧拉路径为5‑4‑6‑5‑7‑6，该第二欧拉路径5‑4‑6‑5‑7‑6为子连通图{4,5,6,7}对应的子路径。

[0123] 进一步，将所提取的子路径中能够首尾相连的子路径进行连接，即将路径1‑4‑3，1‑2‑3‑1以及5‑4‑6‑5‑7‑6进行连接，得到两条目标探测路径1‑2‑3‑1‑4‑3和5‑4‑6‑5‑7‑6。

[0124] 本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划方法，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0125] 相应于上述方法实施例，本发明实施例提供了一种基于固定探针位置的带内网络遥测最优探测路径规划装置，如图10所示，该装置可以包括：

[0126] 接入点确定模块201，用于将各探针设备接入点确定为指定节点，各探针设备接入点为：预先指定的待接入探针设备的网络节点。

[0127] 奇点确定模块202，用于将所有待探测的节点中除指定节点之外的节点，确定为目标点集，并在目标点集中确定所有的奇点，奇点表示节点度数为奇数的节点，节点度数用于表示与该节点相关联的边的条数。

[0128] 路径确定模块203，用于在目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径。

[0129] 加权图构建模块204，用于基于各指定节点、各奇点以及各奇点对应的目标最短路径，构造节点对应的加权图。

[0130] 辅助边添加模块205，用于为加权图添加辅助边，得到添加辅助边之后的目标连通图。

[0131] 路径获取模块206，用于针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0132] 本发明实施例提供的一种基于固定探针位置的带内网络遥测最优探测路径规划装置，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0133] 可选地，路径确定模块，包括：

[0134] 第一路径确定子模块，用于针对每一奇点，确定该奇点与其余各奇点之间的第一最短路径，以及该奇点与指定节点之间的第二最短路径。

[0135] 第二路径确定子模块，用于将第一最短路径与第二最短路径中的最小者，确定为该奇点对应的目标最短路径。

[0136] 可选地，辅助边添加模块，包括：

[0137] 边集获取子模块，用于针对加权图，利用最小权重完全匹配算法，得到加权图中权重最小且互不相交的边集。

[0138] 辅助边添加子模块，用于根据边集，沿各奇点对应的目标最短路径逐跳添加辅助边，得到目标连通图。

[0139] 可选地，路径获取模块，包括：

[0140] 奇点个数确定子模块，用于确定连通图中包含奇点的个数。

[0141] 第一路径获取子模块，用于在奇点的个数少于两对时，利用Hierholzer希霍尔泽算法寻找目标连通图中的第一欧拉路径，并将第一欧拉路径确定为目标探测路径。

[0142] 第二路径获取子模块，用于在奇点的个数不少于两对时，分别提取每一对奇点之间的子路径，并将所提取的子路径中能够首尾相连的子路径进行连接，得到目标探测路径。

[0143] 可选地，第二路径获取子模块，具体用于：

[0144] 基于每一对奇点，对目标连通图进行分割，得到多个包含奇点个数不超过两对的子连通图。

[0145] 针对每一子连通图，利用Fleury弗罗莱算法寻找子连通图中的第二欧拉路径，并将第二欧拉路径确定为子连通图对应的子路径，得到每一对奇点之间的子路径。

[0146] 可选地，在目标点集中不存在奇点的情况下，基于网络中所有待探测的节点，以及各节点之间的边生成无向连通图；将无向连通图确定为目标连通图，并触发路径获取模块，执行针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径的步骤。

[0147] 本发明实施例还提供了一种电子设备，如图11所示，包括处理器301、通信接口302、存储器303和通信总线304，其中，处理器301，通信接口302，存储器303通过通信总线
304完成相互间的通信，

[0148] 存储器303，用于存放计算机程序；

[0149] 处理器301，用于执行存储器303上所存放的程序时，实现如下步骤：

[0150] 将各探针设备接入点确定为指定节点，各探针设备接入点为：预先指定的待接入探针设备的网络节点；

[0151] 将所有待探测的节点中除指定节点之外的节点，确定为目标点集，并在目标点集中确定所有的奇点，奇点表示节点度数为奇数的节点，节点度数用于表示与该节点相关联的边的条数；

[0152] 在目标点集中存在奇点的情况下，针对每一奇点，基于该奇点与各节点之间的最短路径，确定该奇点对应的目标最短路径；

[0153] 基于各指定节点、各奇点以及各奇点对应的目标最短路径，构造节点对应的加权图；

[0154] 为加权图添加辅助边，得到添加辅助边之后的目标连通图；

[0155] 针对目标连通图，使用基于Euler‑trail欧拉轨迹的路径规划方法，获取目标探测路径。

[0156] 本发明实施例提供的一种电子设备，通过将探针设备接入点限定为预先指定的网络节点，可以避免将探针设备接入网络核心节点(例如spine/core交换机)，进而能够避免占用网络核心节点的资源，且将探针设备接入点限定为预先指定的网络节点，能够避免网络拓扑结构发生变化期间探针设备的不稳定重连接，实现网络的稳定遥测。进一步的，在固定探针设备接入点的情况下，构建基于指定节点之外的奇点对应的目标最短路径的目标连通图，使用基于Euler‑trail的路径规划方法，能够寻找到覆盖全网络总路径长度最小的探测路径，进而能够减小网络遥测的开销和网络负载。

[0157] 上述服务器设备提到的通信总线可以是PCI(Peripheral  Component Interconnect，外设部件互连标准)总线或EISA(Extended Industry  Standard 
Architecture，扩展工业标准结构)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。

[0158] 通信接口用于上述电子设备与其他设备之间的通信。

[0159] 存储器可以包括RAM(Random Access Memory，随机存取存储器)，也可以包括NVM(Non‑Volatile Memory，非易失性存储器)，例如至少一个磁盘存储器。可选的，存储器还可以是至少一个位于远离前述处理器的存储装置。

[0160] 上述的处理器可以是通用处理器，包括CPU(Central Processing Unit，中央处理器)、NP(Network Processor，网络处理器)等；还可以是DSP(Digital Signal Processing，数字信号处理器)、ASIC(Application Specific Integrated Circuit，专用集成电路)、FPGA(Field‑Programmable Gate Array，现场可编程门阵列)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。

[0161] 在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现上述任一一种基于固定探针位置的带内网络遥测最优探测路径规划方法的步骤，以达到相同的技术效果。

[0162] 在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一一种基于固定探针位置的带内网络遥测最优探测路径规划方法的步骤，以达到相同的技术效果。

[0163] 在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、DSL(Digital Subscriber Line，数字用户线))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，DVD(Digital Versatile Disc，数字多功能光盘))、或者半导体介质(例如SSD(Solid State Disk，固态硬盘))等。

[0164] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0165] 本说明书中的各个实施例均采用相关的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置/电子设备实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

[0166] 以上所述仅为本发明的较佳实施例，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。