面向数据中心网络的链路故障实时检测即服务

王军晓 齐 恒 李克秋 周晓波

1(大连理工大学计算机科学与技术学院 辽宁大连 116024) 2 (天津大学计算机科学与技术学院 天津 300072) (wangjunxiao@mail.dlut.edu.cn)

链路故障检测作为一种十分重要的网络性能保障手段，目前已被广泛应用于大规模网络环境中，例如数据中心网络等[1].链路故障检测可以为许多大规模在线业务例如搜索引擎、社交网络、文件系统等提供网络连通性方面的保障.随着网络规模的增长、链路数量的上升，如何快速地、实时地完成探测成为链路故障检测中的一个重要挑战[2].

传统被动式的检测办法依赖于简单网络管理协议(simple network management protocol, SNMP)查询网络设备例如路由器或交换机中的计数器，或通过命令行界面(command line interface, CLI)登录到网络设备上查看运行信息.这些方法在网络设备不发生故障的情况下可以检测出一些问题，例如设备端口故障.但是一旦与网络设备间的连接发生中断，这些检测方法将无法正常工作.此外，这些方法需要对网络设备进行配置，因此很难适应网络设备的升级、服务的迁移、网络规模的扩展.

网络功能虚拟化(network function virtualiza-tion, NFV)[3]概念的出现为链路故障检测的实现方法带来了更多的可能性.网络功能虚拟化的思想由众多运营商例如AT&T、中国移动等提出，目前已经被逐渐应用于简化网络服务的部署难度方面以及加快网络服务的升级速度方面.从2012年起，欧洲电信标准化协会ETSI发布了一系列关于网络功能虚拟化的白皮书，介绍了其面临的机遇与挑战、标准架构以及演进方向.网络功能虚拟化的思想是利用标准IT虚拟化技术，将传统网络服务转化为可运行于通用x86平台服务器之上的软件服务.这些基于软件驱动的网络服务可以实现按需弹性供给，而不需要对原有设备进行变动.网络管理者可以灵活地创建、删除或升级特定的网络服务，大大降低了网络服务的部署和维护成本.除此之外，网络服务的部署方式从传统的基于设备的集中式部署模式转化为支持分布式的部署模式，部署于多个服务器上的虚拟网络服务可以联合提供一种复杂的网络功能.这种分布式的部署模式有利于服务实例间的负载均衡和故障切换.

基于网络功能虚拟化，一些主动式的检测办法出现.Pingmesh[4]通过发送基于端到端的探针实现了虚拟的链路故障检测功能.由于这些探针是由运行于服务器中的软件服务进行管理，使得该方法不涉及网络设备，因此不需要对网络设备进行配置，也不需要保持与网络设备之间的连接，可以更好地体现出对场景的适应性，从而检测出更多情况下的链路故障.然而，Pingmesh在网络中每对服务器之间维护一个探针.当网络规模扩展时，需要维护的探针数量将以指数级增长，导致每次探测的用时过长，同时产生过多的带宽负载，难以实现实时的、快速的探测.

我们发现导致以上问题的根本原因是缺乏对探测路径的选择.在如图1所示场景，我们可以借助一些其他技术获取到网络中服务器间的路径信息，例如借助软件定义网络(SDN)技术[5]，从管理底层网络的SDN控制器集群处获取可用路径.但我们不依赖控制器集群对这些可用路径进行链路故障检测(SDN控制器有时检测到的故障是控制器与转发设备之间的控制信道连接故障而不是真正的数据平面故障).如果我们可以仅用网络中的一部分路径而不是全部路径作为链路故障检测时的探测路径并发送端到端探针，那么就有可能降低维护探针的代价，减少每次探测的用时，降低探测流对正常工作负载流的影响，从而实现一种新型的虚拟化网络功能，以支持面向大规模数据中心网络的链路故障实时检测即服务.

Fig. 1 The architecture of virtualized link fault detection function图1 虚拟化链路故障检测功能架构

因此，我们提出一种新型的主动式的、基于网络功能虚拟化的链路故障检测架构，如图1所示.该架构主要由3部分构成：SDN控制器集群[6]、链路故障检测控制器和探针代理.其中SDN控制器集群与底层网络中的转发设备建立连接，从底层网络获取转发路径信息与链路拓扑信息.当SDN控制器集群改变拓扑结构时，例如SDN控制器集群下发命令将转发设备的某些端口禁用等，SDN控制器集群可以及时将这些拓扑的变化推送给链路故障检测控制器.故障检测控制器作为虚拟化链路故障检测功能的大脑，从SDN控制器集群获取最新的转发路径信息，执行探测路径选择算法，从所有底层转发路径中选择一部分路径作为探测路径，并建立探测路径与探针代理之间的映射.探针代理被部署在底层网络的服务器中，并与故障检测控制器保持连接.其中，被探测路径映射到的探针代理与故障检测控制器间的连接被激活.这些连接被激活的探针代理可以从故障检测控制器处接收探针地址，并以自身的网络地址为源地址，以探针地址为目的地址构建并发送网络探针.当某个探针代理收到其他探针代理返回的对于自己探针的回复时，该探针代理将构建链路正常的消息发送给故障检测控制器，否则构建发现故障的消息发送给故障检测控制器.

本文的主要贡献有4个方面：

1) 提出了一种在已知底层转发路径的前提下，仅基于端到端测量即可实现链路故障检测的链路故障实时检测即服务架构；

2) 采用了基于贪婪策略的探测矩阵近似优化算法，可以有效减少探测路径数量，从而使实时探测成为可能；

3) 在减少探测路径数量的基础上，我们还针对探测路径的质量进行分析，并结合了2种可反映探测路径质量的指标，实现高质量探测路径的选择.

4) 基于仿真的实验结果表明，我们提出的实时探测方法与之前工作中的方法相比，在单次探测用时、网络带宽占用以及端点负载方面具有明显优势，且优化探测矩阵所带来的开销是可容忍的.

1 相关工作

链路故障的快速检测是大规模网络系统中的一个被广泛关注的问题.针对这个问题，近年来许多网络监控系统被提出，例如Pingmesh[4]，它将整个底层网络看作是一个黑盒系统，然后考虑如何在网络边缘的服务器之间构建端到端的探测路径.这种方式虽然在理论上可以测量出任何故障场景下，网络边缘端到端的链路故障，无论这些链路故障是基于软件层面的、操作系统内核层面的、网卡层面的、转发设备芯片层面的、安全层面的或是线缆层面的.但是这种检测方法在网络规模大幅度扩展的情况下，相应的探测路径会成指数级增长.这样会导致单次探测的用时无法被控制在一定范围内，大量的探测路径报文传输和端到端探针维护工作会给底层网络的带宽以及边缘服务器处理能力带来显著的压力，并且这种常驻性负载在服务高峰时可能导致业务应用相关的工作负载和传输受到严重影响.

Duffield最先提出了一种名为布尔网络诊断的技术[7].随后在这项技术的基础上出现了许多其他工作，例如Cunha等人的工作[8]、Netdiagnoser[9]，Nguyen等人的工作[10-11]、PlanetSeer[12]还有Zhao等人的工作[13].这些工作基于的假设都是探测路径是不变且不可控的.基于该假设，导致这些工作很难实现覆盖整个底层网络的链路故障检测.NetSonar[14]则考虑探测路径是变化的，即改变探针代理的部署从而改变探测路径，这样就可以实现对整个底层网络的链路故障检测，但由于该方法考虑特殊的骨干网应用场景，导致该方法的扩展性较差.

与基于端到端探针实现的探测方法不同，Sharma等人利用网络编码的方式实现探测[15]，类似的工作还有Yao等人[16]、Kandula等人[17]以及Herodotou等人[18]的网络诊断工作.其中，有些工作借助转发设备的日志信息实现探测，还有一些工作借助多播技术实现探测.在网络监控方面，Pivot Tracing[19]考虑以分布式的方式从底层网络中收集数据并进行分析从而找到造成链路故障的根本原因.LossRadar[20]提出一种基于转发设备实现的监控手段，该方法需要可编程设备支持.文献[21]提出一种基于OpenFlow协议的链路故障检测方案，与本文方法相比，其检测到的故障有可能来自控制器与转发设备之间的控制信道连接故障而不是真正的数据平面故障.

综合来看，现有相关工作中缺乏对大规模网络场景下实时探测的关注.这一研究现状驱动我们去设计一种能够实时快速检测故障链路的方法.

2 最少探测路径数量问题

本节主要介绍如何用矩阵的方式去定义一个最少探测路径数量问题，并说明该问题的解决思想.

2.1 基于转发设备故障的探测矩阵

我们将任意底层网络G定义为

G=(P,N)，

(1)

其中，P是网络G中所有转发路径的集合，N是G中所有转发设备的集合.我们将转发路径与转发设备之间的关系矩阵R定义为

(2)

其中，当转发设备位于转发路径之上时，关系矩阵R中对应位置的值为1，否则值为0.关系矩阵R可以看成由多个行向量构成的集合，其中每个行向量对应一条转发路径.探测矩阵是由行向量所构成的矩阵，其中探测路径由转发路径构成.根据探测矩阵可以确定探针依次经过哪些转发设备.

我们假设某一底层网络G的拓扑如图2所示.根据探测矩阵的定义，可以写出G的含有2条探测路径的探测矩阵D为

(3)

这2条探测路径分别依次经过N1，N2，N5三个转发设备以及N1，N3，N6三个转发设备.假设我们分别在这2条探测路径的源头发送探针，一段时间后如果我们能收到探测路径另一侧回复的探针，就说明这条探测路径上的转发设备及其链路是正常的，否则就说明这条探测路径上发生了链路故障.如果N2对应的转发设备发生了单点故障，那么第1条路径上的探测结果应为故障，第2条路径结果应为正常.同理，如果N5对应的转发设备发生了单点故障，2条路径上的探测结果也是相同的.通过观察可以发现，造成这2种情况下探测结果相同的根本原因是N2和N5对应的转发设备在探测矩阵中的列向量是完全相同的.

Fig. 2 The example network图2 示意网络图

引理1. 如果某个转发设备在探测矩阵中的列向量与其他转发设备的列向量都不相同，那么当该转发设备发生单点故障时，相应的链路故障可被探针检测到.

根据引理1可以发现，N1对应的转发设备在探测矩阵中的列向量与其他转发设备的列向量都不相同，因此当N1对应的转发设备发生单点故障时，相应的链路故障可被探针检测到.虽然N4对应的转发设备在探测矩阵中的列向量也与其他转发设备的列向量都不相同，但由于没有探测路径经过该转发设备，因此也无法根据探测结果推断其是否发生故障.

如果我们将列向量相同的转发设备归为一组，那么可以认为上面的探测矩阵将转发设备分成了4组，分别是(N1)，(N2,N5)，(N3,N6)以及(N4,N7)，其中N7对应的转发设备是我们虚构的转发设备，用来代指探测路径不可达的转发设备.

引理2. 如果探测矩阵中的每个列向量都不相同，那么在每个转发设备发生单点故障时，相应的链路故障都可被探针检测到.且这种功能的探测矩阵可以从初始探测矩阵(一般为关系矩阵)中构建.

下面以一个例子对引理2展开进一步说明.如图2所示，分别以N1和N4对应的转发设备为探测路径的源头，构建一个初始的探测矩阵：

(4)

根据引理2可知，该初始探测矩阵可以探测出所有转发设备的单点故障.那么接下来，我们从中选择探测矩阵式(3)的2条探测路径构成一个新的探测矩阵：

(5)

该探测矩阵中的转发设备被分成了4组，分别是(N1)，(N2,N5)，(N3,N6)以及(N4,N7).从初始探测矩阵中其余的探测路径中选择一条加入该探测矩阵，新加入的探测路径应使得分组被分解得更为分散.根据这个原则，进一步构建探测矩阵：

(6)

该探测矩阵中的转发设备被分成了7组，分别是(N1)，(N2)，(N3)，(N4)，(N5)，(N6)，(N7).根据引理2可知，该探测矩阵具备和初始探测矩阵一致的功能，且与初始探测矩阵相比，探测路径的数量由初始的9条减少到现在的3条.

2.2 基于端口连接故障的探测矩阵

2.1节介绍的探测矩阵是基于转发设备单点故障的.现在，我们考虑基于端口连接单点故障的探测矩阵.即假设在任意时间内只有一条端口连接发生故障，我们可以通过探测结果推断出故障点是哪条端口连接.

首先，我们将前面提到的任意底层网络G中的每个转发设备看成一条端口连接，将每条端口连接看成一个转发设备，并进行如图3所示的转换.将转换后的底层网络定义为

(7)

(8)

(9)

我们将该关系矩阵作为初始探测矩阵，图3(b)中L4对应的端口连接是我们虚构的端口连接，用来代指探测路径不可达的端口连接.

Fig. 3 The example of transformation图3 转换示意图

引理3. 如果探测矩阵中的每个列向量都不相同，那么在每个端口连接发生单点故障时，相应的链路故障都可被探针检测到.且这种功能的探测矩阵可以从初始探测矩阵(一般为关系矩阵)中构建.

如图3所示，任何一个基于端口连接的探测矩阵都可以找到与其对应的基于转发设备的探测矩阵，其中，转换方式是将底层网络中的每个转发设备看成一条端口连接，将每条端口连接看成一个转发设备.根据引理2可知，转换后的探测矩阵满足引理3的性质，从而可以证明引理3的正确性.

根据引理3可以发现，上面的初始探测矩阵将端口连接分成了4组，分别是(L1)，(L2)，(L3)，(L4)，因此在任意时间内只有一条端口连接发生故障的前提下，该探测矩阵可根据探测结果推断出故障点是哪条端口连接.

事实上，我们还可以构建包含更少探测路径的探测矩阵，例如构建只包含第1条探测路径和第2条探测路径的探测矩阵：

(10)

可见，在只有一条端口连接发生故障的情况下，我们可通过优化探测矩阵的方式，将探测路径的数量由初始的3条减少到现在的2条.

值得注意的是:对于大部分数据中心底层网络，特别是冗余端口连接较多的底层网络，例如fat-tree拓扑，端口连接的数量通常大于转发设备的数量.因此，通过对比2.1节和2.2节可以发现，同基于转发设备的探测相比，基于端口连接进行探测往往需要构建包含更多探测路径的探测矩阵，但同时也带来了更细粒度的基于端口级别的探测.

2.3 探测矩阵优化

从2.1节和2.2节中分析可知，无论是基于转发设备的探测矩阵还是基于端口连接的探测矩阵，都可以通过对探测矩阵的优化实现探测路径数量的减少.因此，我们考虑如何优化探测矩阵才能实现最少的探测路径数量，从而降低探测的代价.以2.1节中的基于转发设备故障的探测矩阵为例(基于端口连接故障同理)，可以定义转发设备的初始集合：

S0={{N1,N2,N3,N4,N5,N6,N7}}，

(11)

我们从其初始探测矩阵中选择一条探测路径：

(12)

构建一个只含有该探测路径的探测矩阵，转发设备因此被该探测矩阵分解为(N1,N2,N5)和(N3,N4,N6,N7)两部分.通过观察，该探测路径经过(N1,N2,N5)，但不经过(N3,N4,N6,N7).可知，被该探测路径经过的部分形成了一个子集，没有被该探测路径经过的部分形成了另外一个子集：

S1={{N1,N2,N5},{N3,N4,N6,N7}}，

(13)

接下来，向该探测矩阵中加入一条探测路径：

(14)

转发设备被该探测矩阵分解为(N1)，(N2,N5)，(N3,N6)以及(N4,N7)四部分.通过观察，可以发现这4组分别表示2条探测路径都经过、第1条路径经过而第2条路径不经过、第1条路径不经过而第2条路径经过以及2条路径都不经过.可知，(N1,N2,N5)中被新的探测路径经过的部分形成了一个子集，没有被新的探测路径经过的部分形成了另外一个子集.同理，(N3,N4,N6,N7)中也根据有没有被新的探测路径经过形成了2个子集：

S2={{N1},{N2,N5},{N3,N6},{N4,N7}}，

(15)

最后，再向该探测矩阵中加入一条探测路径：

(16)

同理，(N1)，(N2,N5)，(N3,N6)以及(N4,N7)中分别根据有没有被新的探测路径经过各形成了2个子集：

S3={{N1},{N2},{N5},{N3},{N6},
{N4},{N7}}，

(17)

分解过程进行到这一步，如果仍存在子集不由单个元素构成，那么还需继续向探测矩阵中添加新的探测路径，直至所有形成的子集都是由单个元素构成.

通过这种故障点集合分解的方法，我们可以获得一个由初始探测矩阵(一般为关系矩阵)中探测路径的子集构成的探测矩阵，但这并不能保证该探测矩阵中包含的探测路径数量是最优的.并且，我们还发现当探测路径的数量达到最优时，对应的最优探测矩阵可能并不是唯一的.

无论是基于转发设备的探测矩阵还是基于端口连接的探测矩阵.假设探测路径的数量是m，那么探测结果最多为2m种,并且其中有一种探测结果为无故障发生.假设需要检测的故障点有n个，且在任意时间点只可能发生单点故障的情况下，理想上检测所需的探测路径数量为

(18)

当然，具体数量还与底层网络拓扑有关.搜索最优探测矩阵的过程中可以使用指数时间复杂度的穷举搜索算法.但由于时间复杂度过高，在大规模场景下并不实用.因此，我们采用一种基于贪婪策略的近似算法对最优探测矩阵进行搜索.该近似算法的思想是：每次向探测矩阵中添加新的探测路径时，选择产生最大信息熵的探测路径进行添加.我们以一个例子来说明该近似算法的原理.假如，在第2次添加探测路径时，选择的探测路径产生了情况的分解：

(19)

即使该分解可使3个子集只由单个元素组成，但由于其后还必须再添加至少2条探测路径才能使所有子集都由单个元素构成.相较之下，

S2={{N1},{N2,N5},{N3,N6},{N4,N7}}，

(20)

该分解虽然只能使一个子集由单个元素组成，但由于其后可能只需要再添加一条探测路径就能使所有子集都由单个元素构成，因此我们认为它具有更大的混乱度，即信息熵，使得分解更接近于最终状态.进而我们认为后者探测路径的优先级比前者更高.

假设选择并添加某条探测路径后所对应的分解M由i个子集构成，那么将这i个子集分解到最终状态还必须再添加的探测路径可表示为

(21)

同时，这也是该探测路径所对应的信息熵的倒数.

假设初始探测矩阵(一般为关系矩阵)中行向量的数量为x，那么当每次选择并添加探测路径时，需要与其余候选的探测路径所对应的信息熵进行比较，因此该算法的时间复杂度可表示为

(22)

3 探测路径质量问题

在本节中，我们主要介绍如何定义一条探测路径的质量，并说明如何找到满足质量的探测路径.

3.1 探测路径质量标准

在减少探测路径数量的基础上，我们还需要针对探测路径的质量进行分析，为此我们首先给出2个用于反映探测路径质量的指标.

定义1.Θ并发的探测矩阵.如果存在这样的探测矩阵，在任意时间点至多有Θ个故障点同时发生故障的情况下，仍能够根据探测结果推断出故障点.我们将这样的探测矩阵定义为Θ并发的探测矩阵.

前面提到的探测矩阵都是基于任意时间点只有一个故障点发生故障的，即在Θ=1的情况下，现在我们需要将这个前提进行推广.为此，我们以2.2节中底层网络的关系矩阵为例进行考虑，假设我们想要检测出L1和L3对应的端口连接可能同时发生故障，则需要构建一个扩展的关系矩阵：

(23)

其中，最后一个列向量是对L1和L3对应故障点列向量中的元素依次执行或运算所生成的.通过这种构建额外列向量的方式，我们可以在探测矩阵中表示可能同时发生的多个故障.假设需要检测的故障点为n个，为了保证探测矩阵是Θ并发的，初始化阶段应额外构建的列向量数目为

(24)

其中，全部故障点都发生故障与都正常同属于Θ=1情况下.接下来，我们只需对构建了额外列向量的关系矩阵实施2.3节中介绍的Θ=1情况下的分解步骤，最终就可以得到满足Θ并发的探测矩阵.

定义2.Γ冗余的探测矩阵.如果每个故障点都被至少Γ条探测路径经过，满足这样条件的探测矩阵，我们将它定义为Γ冗余的探测矩阵.Γ冗余决定了故障点的探测可靠性，当Γ>1时，有多条探测路径经过故障点，即使其中部分探测路径失效(如转发设备的缓存溢出导致探针丢失等)，也能使故障被正常检测出来.

此外，通过Γ冗余还可以使探测路径更为均匀地分布在需要检测的故障点上，从而使链路故障检测所带来的额外负载能够均衡分布在底层网络中.为此，我们为每一条候选探测路径设置了一个参数Φ：

(25)

其中，参数Φ表示分解过程中添加该探测路径的优先级；参数Δ是每个故障点的一个属性，用于保障探测路径的冗余性；参数Υ表示分解过程中与该探测路径产生交集的子集数量.如果探测路径的参数Φ较小，一方面说明它所经过的故障点被已添加的探测路径所覆盖的程度较小，另一方面说明添加它对于分解过程所带来的信息熵较大.可见，这样设置既可保证探测的可靠性，又可保证探测负载的均衡性，还可保证探测路径数量的最少化.

3.2 探测路径选择

基于以上2方面的探测路径质量指标，我们采用了一种基于贪心策略的探测矩阵的近似优化算法，如算法1所示.首先，算法1会根据Θ值构建底层网络的扩展关系矩阵，从而将Θ>1情况下的问题转换为Θ=1情况下可以解决的问题.在每轮向探测矩阵中添加探测路径之前，需要更新所有待选路径的Φ值并以正序排列，然后选择排序中第1条待选路径作为探测路径，并把它添加到探测矩阵中.最后，更新已选路径上所有故障点的Δ值.算法1输出探测矩阵的条件为，经过若干轮路径选择后，所有故障点的Δ值都大于Γ且所有子集都由单个元素构成.如果添加完所有路径后仍然不能满足条件，算法1将输出找不到合适的探测矩阵.

算法1. 探测矩阵构建算法.

输入：关系矩阵R、并行度Θ、冗余度Γ、故障点集N；

输出：探测矩阵D.

④ while (num≠|N|‖points≠∅) &&

paths≠∅ do

⑤ fori∈pathsdo

⑦ end for

⑨P←P∪{i}；

⑩paths←paths{i}；

引理4. 在探测路径的数量最少化方面，该基于贪心策略的探测矩阵优化算法的近似比为

(26)

其中，e为自然对数.证明时，首先定义一个函数f：

(27)

由于探测路径经过的故障点数量应大于分解过程中与该探测路径产生交集的子集数量.可知：

(28)

(29)

根据式(28)(29)，Φ(Pi)的非负性得证.又因为：

f(s)≥0，

(30)

0≤f(S)≤f(S∪s)，

(31)

根据式(30)(31)，f的非负性得证，且f为单调非递减.由于我们的目标是最小化S的模，此时原目标可以被转换为最小化f.

由于越多的路径被选择，分解所产生的子集数量就会变得越多，同时与新加入路径产生交集的子集数量也会变得越多.因此可以得到：

f(s|S)≤f(s|T)，

(32)

f(s|S)=f(S∪s)-f(S)，

(33)

其中，T⊆S.根据式(32)(33)，f的子模性得证.由于目标的非负性、单调性以及子模性都可以得到证明，因此该近似算法的近似比可以得到证明.

由于该算法的时间复杂度为关系矩阵中转发路径数量的平方级，因此如何有效降低算法的执行时间是一个需要考虑的问题.我们选择从2个方面进行优化:

1) 基于底层网络的关系矩阵构建一张二分图，图中的一个点集代表故障点，另一个点集代表转发路径，两点之间若存在边则代表故障点位于转发路径之上.如果某2条转发路径所经过的故障点完全不同，则形成更小规模的子图以及子关系矩阵.经过这样的处理，原问题可被拆分为多个独立的子问题，在每个子问题中算法可以并行执行.通过线性时间的算法可实现对二分图的一次遍历以及对子问题的拆分.

2) 基于数据中心底层网络的拓扑对称性，当某条转发路径被添加到探测矩阵时，其对称路径也会被加入.经过这样的处理，原问题的规模可以被进一步降低.为此，我们需要在探测开始之前一次性计算出关系矩阵中的对称路径.

4 实验与结果

在本节中，我们针对探测矩阵的探测性能与计算开销展开仿真实验，并根据实验结果进行分析.

4.1 实验环境设置

在仿真实验中，我们基于Java开发环境实现了基于探测矩阵的链路故障检测方法BPM-N以及BPM-L.其中，BPM-N是基于故障点为转发设备的，BPM-L是基于故障点是端口连接的.我们考虑的链路故障为所有经过故障点的报文全部无法被对端收到(中途被转发设备丢弃、报文丢失或转发表配置错误路由到错误的目的地后被丢弃).在探测矩阵构建时，我们考虑Θ=1，Γ=2的情况.

我们采用了2种底层网络设置分别是一个FatTree(12)拓扑和一个VL2(20,12,20)拓扑，以验证我们的方法在不同拓扑结构和规模下的效果.其中，FatTree和VL2拓扑都是广泛应用的，且具有冗余传输链路的数据中心内部网络拓扑结构.这2种拓扑中的流量转发路径具有一定规律，所有从源服务器中发送的流量会先经过一个ToR交换机，之后再经过汇聚层交换机或核心层交换机到达目的服务器所在的ToR交换机.相同Pod内的流量只经过汇聚层交换机，不经过核心层交换机；而不同Pod之间的流量则需要先经过汇聚层交换机上传至核心层，再由核心层下传至汇聚层.我们考虑每条转发路径都是双向的，即探针回复时的路径与探针发送时的路径相同.因此部分链路故障可能不是在探针发送时被检测出来，而是在探针回复时被检测到.

关系矩阵中的转发路径由所有接入层ToR交换机之间的链路构成.在一个FatTree(12)拓扑中，转发路径中包含180个转发设备(共612个节点)以及864条端口连接(共1 296条链路)，而在一个VL2(20,12,20)拓扑中，转发路径中包含82个转发设备(共1 282个节点)以及240条端口连接(共1 440条链路).我们选择进行对比的方法是Pingmesh中提出的探测方法.它是一种对底层网络不进行感知的链路故障检测方法，即将整个底层网络视为一个黑盒系统，并基于服务器之间进行端到端的网络探测.该方法产生的探针数量由Pod内部以及Pod之间2种情况组成，在Pod内部，由所有的服务器以完全图的方式彼此发送探针；而在Pod之间，则是由所有的ToR交换机以完全图的方式彼此发送探针，其中，ToR交换机之间探针的发送也是由服务器实现的.在一个FatTree(12)拓扑中，该方法产生的探针数量为20 232，而在一个VL2(20,12,20)拓扑中，该方法产生的探针数量为26 340.我们选取了BPM-N，BPM-L以及Pingmesh这3种方法下10个探测周期的数据进行比较.

4.2 探测性能对比

为了检验我们提出的实时探测方法与之前工作中提出的方法在探测性能上的差别，我们分别针对单次探测用时、网络带宽占用以及端点负载3个指标在2种拓扑下进行了对比仿真实验.

评价指标中的单次探测用时包括3部分的用时：1)中央控制器(链路故障检测控制器)激活探测过程中涉及的所有服务器的探针代理所需的时间;2)探针代理发送网络探针并等待回复的时间;3)探针代理将探测结果上传到中央控制器所需的时间.其中，探针代理每隔固定一段时间就发送一个探针(而不是一直等待直到收到上轮探针的回复后再发送下一轮探针)，每个探针上用时间戳和自增序号进行标记，探针代理确认回复的时间存在阈值，一旦计时器检测到超过，就会向中央控制器发送链路故障消息.在任意时隙内，如果中央控制器已收到大部分探测结果(例如95%)，就认为当前一个探测周期已经完成，并进入下一个探测周期.

在单次探测用时方面，FatTree(12)拓扑下的实验结果如图4所示，可以看出我们采用的BPM-L和BPM-N的探测周期远远低于Pingmesh的探测周期，差距最大处接近47倍.造成这样结果的主要原因是BPM-L和BPM-N使用的探测路径的数量要远远小于Pingmesh使用的.另一方面，BPM-N的探测周期整体低于BPM-L的探测周期，差距最大处接近2.5倍.造成这样结果的主要原因是，BPM-N探测矩阵中故障点数小于BPM-L中的.但同时BPM-L带来了更细粒度的基于端口级别的探测.

Fig. 4 The results of FatTree on detection period图4 FatTree探测周期结果图

Fig. 5 The results of VL2 on detection period图5 VL2探测周期结果图

VL2(20,12,20)拓扑下的单次探测用时的实验结果如图5所示，可以看出在VL2拓扑下，BPM-L和BPM-N的探测周期与Pingmesh的差距更加明显，差距最大处已经接近89倍.造成这样结果的主要原因是由于BPM-N和BPM-L的探针数量分别是受转发设备以及端口连接数目影响的，而Pingmesh的探针数量则是受服务器数量影响的.与FatTree(12)拓扑相比，VL2(20,12,20)拓扑中的转发设备与端口连接数目更少，而服务器数量更多.在VL2拓扑中BPM-N的探测周期同样整体低于BPM-L的探测周期，差距最大处接近1.5倍.

在网络带宽占用方面，FatTree(12)拓扑下的实验结果如图6所示.我们考虑每条链路上的带宽数量是一定的，其中一定比例(如90%)的带宽需要传输工作负载，那么剩余比例(如10%)的带宽中，每条探测路径会消耗其中的一部分(如1%)，而且消耗的部分越多，越有可能对工作负载的传输造成不良影响.从实验结果可以看出我们采用的BPM-L和BPM-N的平均带宽占用远远低于Pingmesh的平均带宽占用，差距最大处接近9倍.同理，造成这样结果的主要原因是BPM-L和BPM-N使用的探测路径的数量要远远小于Pingmesh使用的探测路径数量.此外，BPM-N的平均带宽占用也同样低于BPM-L，差距最大处接近2倍.这也是由于BPM-N探测矩阵中的故障点数小于BPM-L中的故障点数所造成的结果.

Fig. 6 The results of FatTree on average bandwidth usage图6 FatTree平均带宽占用结果图

VL2(20,12,20)拓扑下的平均带宽占用的实验结果如图7所示，可以看出在VL2拓扑下，BPM-L和BPM-N的平均带宽占用与Pingmesh的差距更加明显，差距最大处已经接近17倍.由于我们考虑的是Γ=2情况下的BPM-L，因此在Fat-Tree和VL2两种拓扑下BPM-L的平均带宽占用的结果非常接近.在VL2拓扑中BPM-N的平均带宽占用同样整体低于BPM-L的平均带宽占用，差距最大处接近3倍.

Fig. 7 The results of VL2 on average bandwidth usage图7 VL2平均带宽占用结果图

评价指标中的端点负载，与网络带宽占用相似，指的是网络边缘的服务器运行探针代理所产生的代价.我们考虑服务器中可用于运行探针代理的CPU利用率是一定比例(如5%)以内的，单位时隙内，每维护一个探针会占用一定比例(如0.5%)的CPU利用率，而且占用的部分越多，越有可能对其他应用进程的运行造成不良影响.在我们的方法中，所有探针代理产生的端点负载可以在ToR交换机下属的所有服务器间进行负载均衡.而在Pingmesh的方法中，仅有Pod之间情况下的端点负载可以在ToR交换机下属的所有服务器间进行负载均衡.

Fig. 8 The results of FatTree on average serverCPU usage图8 FatTree服务器平均CPU占用结果图

在端点负载方面，FatTree(12)拓扑下的实验结果如图8所示.可以看出我们采用的BPM-L和BPM-N的服务器平均CPU占用远远低于Pingmesh的平均CPU占用，差距最大处接近4.5倍.造成这样结果的主要原因是BPM-L和BPM-N在服务器间需要维护的探针数量要远远小于Pingmesh的.另一方面的原因是，在BPM-L和BPM-N中，由于所有的ToR交换机下属的服务器之间都可以进行负载均衡，从而可以进一步降低服务器平均CPU占用.BPM-N在服务器平均CPU占用方面仍然低于BPM-L，差距最大处接近1.5倍.说明由于基于端口连接的故障点数更多，导致对BPM-L的探针维护和端点负载的影响更大.

VL2(20,12,20)拓扑下的端点负载的实验结果如图9所示，可以看出在VL2拓扑下，BPM-L和BPM-N的端点平均CPU占用与Pingmesh之间仍存在差距，且差距最大处接近4倍，这与FatTree(12)拓扑中的结果相比有所下降.VL2拓扑下的BPM-N的服务器平均CPU占用同样整体低于BPM-L的，差距最大处接近1.5倍.

Fig. 9 The results of VL2 on average server CPU usage图9 VL2服务器平均CPU占用结果图

综合来看，我们采用的BPM-L和BPM-N链路故障检测方法在单次探测用时(探测周期)、网络带宽占用(平均带宽占用)和端点负载(服务器平均CPU占用)3方面与之前的工作Pingmesh相比较，具有显著的优势，主要原因是我们采用的方法可以根据已获取的底层网络转发路径构建近似最优的探测矩阵，从而减少探测路径和端到端探针的数量，进而降低单次探测用时、网络带宽占用以及端点负载，实现实时快速的虚拟故障链路检测功能.

4.3 探测矩阵计算开销

虽然探测矩阵在每次网络更新之后只需要进行一次优化，但每次对探测矩阵进行优化的过程中都存在一定的计算开销，该开销包括计算时间上的开销以及计算内存上的开销.在时间开销方面，我们考虑了算法1基于BPM-L的探测矩阵构建方法DMO，以及另外2种基于DMO并进一步优化了算法时间复杂度的构建方法.其中，DMO-S是考虑了子问题拆分后的改进方法，DMO-T则是考虑了拓扑对称性后的改进方法.我们分别在FatTree(12)和VL2(12,20,12)两种拓扑下对3种不同的探测矩阵构建方法的时间开销进行了仿真实验.

仿真实验的结果如图10所示.其中，未经过任何优化的DMO在FatTree(12)中的运行时间与它在VL2(12,20,12)中的运行时间分别为224.7 s和23.2 s.而经过DMO-S优化后的运行时间是6.8 s和24.3 s，可见DMO-S在Fat-Tree拓扑下的效果明显.经过DMO-T优化后的运行时间是1.1 s和1.9 s，说明在对称的数据中心网络拓扑中，DMO-T的效果最好.基于BPM-N的探测矩阵构建方法由于具有更少的故障点数量，因此与BPM-L相比，其运行时间会更短.

Fig. 10 The results on algorithm running time图10 算法运行时间结果图

在内存开销方面，我们考虑了BPM-L与BPM-N在FatTree(12)和VL2(12,20,12)两种拓扑下关系矩阵的内存消耗，仿真实验的结果如图11所示.其中，我们在Java中使用int类型保存关系矩阵中的位值.由于该类型包含4个字节即32 b，因此理论上测得的结果是最低内存开销的32倍.对比结果显示，关系矩阵在FatTree(12)下的内存占用更大，差不多是VL2(12,20,12)下的2.5倍；而在同一拓扑中，BPM-L的内存占用更小，差不多是BPM-N的45.

Fig.11 The results on algorithm memory usage图11 算法内存占用结果图

事实上，一般数据中心网络的层数都在3层以内，以最广泛应用的FatTree和VL2拓扑为例，每条路径最多包含5个故障点(基于端口连接的情况下为4个)，一个商用大规模12阶FatTree拓扑中的路径总数为184 032，而一个商用大规模(20,12,20)的VL2拓扑中的路径总数为70 800.这2种拓扑下单点故障的初始探测矩阵(基于关系矩阵)的大小可以计算出来分别为920 160 b和354 000 b，即115.02 KB和44.25 KB，一般被认为是可以忍受的内存开销.

综合来看，我们采用的BPM-L和BPM-N链路故障检测方法在构建探测矩阵的过程中所产生的计算开销是完全可以容忍的.在常见的商用大规模数据中心网络拓扑中，计算时间开销经过优化后可以达到秒级，计算内存开销可以维持在MB级别.

5 总 结

本文通过对已有的链路故障检测工作中存在的问题进行分析，发现了最少化探测路径数量对于提升检测速度具有重要的意义.因此，我们采用优化探测矩阵的方法，以此来构建数量最少化、质量最大化的探测路径集合.在解决该问题的过程中，我们给出了探测矩阵的定义和探测矩阵的优化方法，在提升探测路径的质量方面，我们定义了2种质量指标，并给出了结合质量指标的探测矩阵优化方法.最后，我们通过仿真实验的方式验证了该实时检测方法在单次探测用时、网络带宽占用以及端点负载3方面比之前工作中的方法具有显著优势，且优化探测矩阵所带来的开销是可容忍的.

[1]Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]Proc of ACM SIGCOMM’08. New York: ACM, 2008: 63-74

[2]Govindan R, Minei I, Kallahalla M, et al. Evolve or die: High-availability design principles drawn from Googles network infrastructure[C]Proc of ACM SIGCOMM’16. New York: ACM, 2016: 58-72

[3]Han B, Gopalakrishnan V, Ji L, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90-97

[4]Guo Chuanxiong, Yuan Lihua, Xiang Dong, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis[C]Proc of ACM SIGCOMM’15. New York: ACM, 2015: 139-152

[5]Kreutz D, Ramos F M V, Verissimo P J E, et al. Software-defined networking: A comprehensive survey[J]. Proceedings of the IEEE, 2014, 103(1): 10-13

[6]Berde P, Gerola M, Hart J, et al. ONOS: Towards an open, distributed SDN OS[C]Proc of ACM HotSDN’14. New York: ACM, 2014: 1-6

[7]Duffield N. Network tomography of binary network performance characteristics[J]. IEEE Trans on Information Theory, 2006, 52(12): 5373-5388

[8]Cunha í, Teixeira R, Feamster N, et al. Measurement methods for fast and accurate blackhole identification with binary tomography[C]Proc of ACM IMC’09. New York: ACM, 2009: 254-266

[9]Dhamdhere A, Teixeira R, Dovrolis C, et al. Netdiagnoser: Troubleshooting network unreachabilities using end-to-end probes and routing data[C]Proc of ACM CoNEXT’07. New York: ACM, 2007: 18-30

[10]Nguyen H X, Teixeira R, Thiran P, et al. Minimizing probing cost for detecting interface failures: Algorithms and scalability analysis[C]Proc of IEEE INFOCOM’09. Piscataway, NJ: IEEE, 2009: 1386-1394

[11]Nguyen H X, Thiran P. The Boolean solution to the congested IP link location problem: Theory and practice[C]Proc of IEEE INFOCOM’07. Piscataway, NJ: IEEE, 2007: 2117-2125

[12]Zhang M, Zhang C, Pai V S, et al. PlanetSeer: Internet path failure monitoring and characterization in wide-area services[C]Proc of USENIX OSDI’04. Berkeley, CA: USENIX Association, 2004: 167-182

[13]Zhao Yao, Chen Yan, Bindel D. Towards unbiased end-to-end network diagnosis[C]Proc of ACM SIGCOMM’06. New York: ACM, 2006: 219-230

[14]Zeng Hongyi, Mahajan R, Mckeown N, et al. Measuring and troubleshooting large operational multipath networks with gray box testing, MSR-TR-2015-55[R]. Redmond: Microsoft Research Lab, 2015

[15]Sharma G, Jaggi S, Dey B K. Network tomography via network coding[C]Proc of IEEE ITA’08. Piscataway, NJ: IEEE, 2008: 151-157

[16]Yao Hongyi, Jaggi S, Chen Minghua. Network coding tomography for network failures[C]Proc of IEEE INFOCOM’10. Piscataway, NJ: IEEE, 2010: 91-95

[17]Kandula S, Mahajan R, Verkaik P, et al. Detailed diagnosis in enterprise networks[C]Proc of ACM SIGCOMM’09. New York: ACM, 2009: 243-254

[18]Herodotou H, Ding B, Balakrishnan S, et al. Scalable near real-time failure localization of data center networks[C]Proc of ACM KDD’14. New York: ACM, 2014: 1689-1698

[19]Mace J, Roelke R, Fonseca R. Pivot tracing: Dynamic causal monitoring for distributed systems[C]Proc of ACM SOSP’15. New York: ACM, 2015: 378-393

[20]Li Yuliang, Miao Rui, Kim C, et al. LossRadar: Fast detection of lost packets in data center networks[C]Proc of ACM CoNEXT’16. New York: ACM, 2016: 481-495

[21]Hou Le, Wang Shuo, Lin Yikai, et al. Link failure recovery based on SDN[J]. Telecommunications Science, 2015, 31(6): 18-23 (in Chinese)(侯乐, 汪硕, 林毅凯, 等. 基于SDN的链路故障恢复[J]. 电信科学, 2015, 31(6): 18-23)WangJunxiao, born in 1991. PhD candidate at Dalian University of Technology. His main research interests include software defined networking, network function virtualization, and cloud computing.

QiHeng, born in 1981. PhD. Associate professor at Dalian University of Technology. Member of CCF. His main research interests include computer network, future Internet technology and multimedia computing.

LiKeqiu, born in 1971. PhD. Professor and PhD supervisor at Dalian University of Technology. Distinguished member of CCF. His main research interests include data center networks, cloud computing and wireless networks.

ZhouXiaobo, born in 1984. PhD. Associate professor at Tianjin University. Member of CCF. His man research interests include network information theory, cloud computing, and software defined networking.