主被动结合的网络测量技术研究

王阿领，刘 渊，王晓锋

1.江南大学 数字媒体学院，江苏 无锡 214122

2.江南大学 物联网工程学院，江苏 无锡 214122

1 引言

随着互联网的快速发展和网络规模的不断扩大，网络的异构性变得越来越复杂，人们对网络行为的特征、网络结构，以及网络模型的理解会变得更加困难。因此在遇到网络漏洞和网络安全问题[1]的时候，很难及时地得到一个合理的解决方案，从而导致网络的服务质量（Quality of Service）与用户的实际需求产生较大的差距。在不完全了解目标网络的协议、配置以及拓扑的情况下，通过网络测量技术[2]能够获取当前的网络性能测量信息。这些信息能帮助网络研究者分析网络行为、查看网络潜在的网络安全以及发现异常和定位异常，这对网络运维有着非常重要的意义。如文献[3]在N-Nakagami信道下，通过建立移动通信网络模型，针对平均安全容量和安全中断概率使用Monte-Carlo技术进行仿真验证获取相应的网络性能测量信息，从而达到量化分析系统安全性能的目的。

网络测量是指按照一定的方法和技术，利用软件和硬件工具来测量网络性能、检测网络质量和理解网络行为的一系列活动的总和。一般常用的网络性能测量方法主要包括主动测量[4-9]和被动测量[4-9]：

（1）主动测量就是按照较小的时间间隔向待测网络中发送探测数据包，通过对主机的反馈信息做出判断，从而得到网络端到端的行为信息。一般情况下，对网络端到端的延迟、丢包率、路由以及网络拓扑的测量都是采用主动测量方式。如Ping[5]可以获得网络的连通状况，从而得到往返延迟、丢包率等性能参数。如Traceroute[10]主要是用来获得网络端到端路由信息。Pathload[5]通过UDP协议发送探测数据包队列获得可用带宽的性能参数。

（2）被动测量不需要向网络中发送探测数据包，而是通过两点监控或者单点监测的方式，在相应的网络节点上部署网络探针作为被动监测设备，监听和捕获经过测量设备的网络信息数据流，并采集真实的数据链路信息。如网络带宽、路径吞吐量[5]等参数使用的是被动测量方式。被动测量工具和技术主要有Sniffer（嗅探器）、Wireshark、WinCap、Network General、SNOR[4]等。被动测量不需要向网络发送探测数据包，所以一般不会对网络本身的运行产生影响。

主动测量和被动测量都有各自的优势。主动测量会向网络中注入探测流量包，导致测量有偏差；而被动测量方式可扩展性不强，难以对端到端网络行为进行整体地理解和分析。由于网络丢包率和路由信息能够比较直观地反映网络性能和网络结构，因此采用主动和被动相结合的测量方式可以更准确地获得网络丢包率和路由信息测量结果。该方式不仅保持了主动测量和被动测量各自的优点，更使得测量结果能更好地反映网络的真实情况，对理解网络性能和网络结构具有非常重要的意义。同时，也能够能达到简化网络运维、增强网络鲁棒性[11]的目的。

2 主要工作

目前针对网络丢包率和路由信息测量的研究成果有很多。文献[7]提出一种基于自适应采样的丢包率测量方法，利用时延和丢包率之间的相关特性调整主动发包测量周期。探测周期的调整采用减半和倍增的方式，并设置最大探测周期为5 s，最小探测周期为0.05 s。此方式在测量精度和测量时间开销上都较好的折中，能有效地降低发包探测量以及丢包率测量误差。文献[12]提出一种贪婪启发式拥塞链路丢包率范围推断算法，借助多时隙路径探测，避开单时隙对时钟同步的强依赖。代替传统以瓶颈链路作为拥塞链路定位的方法，通过聚类方式循环推断拥塞链路丢包率的范围。相对于通过网络吞吐量和时延信息推测链路情况，此方式鲁棒性较强。但是算法的时间复杂度较高，比较适合规模较小的链路。文献[10，13]提出一种基于软件定义网络的主动测量的方式。在控制器与交换机之间采用OpenFlow进行通信，让源交换机发出特定的测量报文序列，通过SDN 网络逐级跳转至目的交换机。目的交换机在收到探测报文后返还给源交换机之后，利用控制器周期轮询交换机上的数据流并统计测量数据，获得时延抖动、丢包率等重要网络性能参数。此方式虽然测量的丢包率结果比接收端测量得到的背景流量丢包率较低，但是此方式采集粒度较大，没有考虑往返网络测量数据包的匹配与处理。

文献[14]提出基于接触图的预计算路由策略和动态路由响应机制，利用主动发包的方式，对测量的数据流进行粒度匹配。此方式需要预先建立一个邻接网络节点结构图，并对网络节点的权值进行标记。但是这种方法时间复杂度较高，比较适合规模较小的网络。文献[15-16]提出基于流粒度生成的接触图路由算法，通过捕获探测数据包对数据流进行逐跳跟踪，并输出完整的路由跟踪路径。但是这种方式同样需要提前构建好网络拓扑节点数据库，并且每次遍历节点都要重新启动路由，测量周期较长，时间复杂度也比较高。文献[17]提出一种基于背景流量感知的主被动结合的Traceroute测量算法，当网络中没有流量时，采用主动测量的方式周期性地向目标网络发送探测数据包；当网络中有流量时，采用被动测量方式监听目标网络。此方法虽然一定程度上降低了因背景流量带来的测量误差，但没有具体说明主动测量和被动测量之间的触发和调度机制。文献[18]采用主动测量的方式，预先建立一个邻接网络节点结构图，对网络节点的权值进行标记，并以Dijkstra算法为基础增广每个信宿节点的路由集。在路由寻路探测过程中设置一个组播延迟上界，利用延迟ts作为路径长度的度量，将延迟过大的路由舍弃。但是理论上延迟上界往往使网络达不到最大的组播容量，所以每次寻路都需要分离经过相同的信宿节点。

本文在分析目前现有的针对网络丢包率和路由信息测量技术的基础上，提出了一种主被动结合的网络测量技术。在网络链路中合理地设置被动监测设备和软件，实时监听捕获的网络数据报文信息。被动测量将捕获采集到的数据信息经控制器进行哈希过滤、分类和统计计数，最终进行匹配和筛选。当匹配到有效的数据信息时，则会触发引导丢包率和路由信息测量任务的执行。与传统的网络测量技术相比，主被动结合的网络测量技术能够在压缩测量规模的同时还保持了测量精度的稳定。对于规模较大或较小的网络都适用。在测量网络丢包率时，本文提出了一种周期动态调整的主动发包方式，以降低网络突发情况下持续丢包对测量结果产生的影响。文献[7]采用的是减半或者倍增的发包调整策略，但是这种调整幅度是几何量级的，相比较一些需要快速测量丢包率的网络应用，此方式调整周期的相对误差率超过20%。本文采用的是一种周期动态调整的发包策略，利用时延和丢包率之间的相关特性判定网络是否处于突发时段，并据此设置两个动态调整参量和调整区间，动态调整参量取调整区间内的随机值。相较于几何形式的发包调整策略，动态参量随机值的调整策略误差抖动较小，稳定性和准确性都较高。由于高速网络吞吐量较高，突发丢包并不频繁。因此，本文研究并采用基于泊松分布的丢包率采样方式，相比较一般的周期采样方式，采样样本的准确率较高。

在测量网络路由路径信息时，本文提出一种多路径动态路由测量算法，目的是减少路由寻路探测跟踪时间，提升单位时间内的路由探测效率。针对已经探测过的目标网络节点不再重复地发送探测数据包，以降低主动发送探测包的时间开销。与文献[14]、文献[15]和文献[18]相比，本文最大的优势在于不需要预先建立一个邻接网络节点结构图，在主动测量任务执行之前就已经将无关测量的数据过滤掉，提炼并压缩了测量的有效数据量。并且算法在执行过程中匹配的相关指标参量较少，减少了路由寻路执行过程中的算法迭代次数，因而算法的时间复杂度相对较低。文献[18]以Dijkstra 算法为基础增广每个信宿节点的路由集，将延迟较大的节点舍弃。而本文则利用栈的方式记录探测寻路路由信息，根据设置的时延阈值将匹配遍历的节点进行入栈和出栈操作，其算法的平均时间复杂度为O(knlgmn)。此方式在寻路探测过程中不会额外增加路由负载。

3 主被动结合的网络测量关键技术实现

针对本文中具体的研究内容，搭建了一个基于主被动结合的网络测量实验测试环境，并部署相应的硬件和软件设备。测量的网络数据均来自于真实的校园网络。相应的硬件和软件设备主要包括服务器、Open-Flow 交换机、控制器、被动监测设备Netflow、两台可供实验操作的控制平台以及监测软件Wireshark和网络仿真器NS3（Network Simulator version 3）等。

3.1 主被动结合的网络测量技术描述

本文提出一种主被动结合的网络测量技术，其主要思路是：通过被动测量的结果触发引导主动测量任务的执行，得到目标网络丢包率和路由信息。主被动结合的网络测量技术体系架构主要分为三个模块：目标网络、数据转发和被动监测以及控制中心。目标网络来源于真实的校园网网络。数据转发和被动监测控制的主要功能就是控制被动监测数据的转发以及主动探测数据包的传送。控制中心主要包括数据采集模块、数据存储和管理模块、数据匹配和筛选模块、丢包和路由测量模块。连接目标网络和控制中心的依次是OpenFlow交换机、网络控制器以及被动监测设备NetFlow。基于图1的主被动结合的网络测量技术体系架构，其测量过程描述如下：

（1）目标网络通过实体交换机和路由器接入本地服务器。通过使用OpenFlow测量控制协议[10，19-20]，实现控制器与其相连的OpenFlow交换机之间能进行数据流的转发。即当源交换机收到目的主机发送的协议报文之后，根据数据流表对数据包进行识别，并由Netflow被动检测设备和TCPDUMP进行捕获。OpenFlow交换机依据内部的多级流表（flow table）和组表（group table）对被动采集的数据报文进行分类，经控制器传送给数据采集模块。数据报文信息在数据采集模块中进行简单的预处理。

（2）为了保证在高速链路中能及时地捕获到探测数据包，报文的获取、打时间戳、基于流的压缩和转发等过程均采用线程技术[21]来实现。捕获的数据报文信息在数据采集模块中通过简单的预处理操作将包中的协议字段、标识位、源和目的IP地址字段、端口等读取出来并进行分类。分类的数据报文信息会生成实时更新的本地聚合日志，并存储在数据存储和管理模块中的本地MySQL数据库中。本地聚合日志可供控制中心的Kali Linux控制平台实时查看和调用。

图1 主被动结合的网络测量技术体系架构

（3）待监测任务结束后，更新的本地聚合日志依据匹配和筛选机制在数据匹配和筛选模块中依次进行匹配和筛选，匹配和筛选机制基于正则表达式、散列匹配技术、以及可扩展的统计函数，筛选、过滤掉冗余和无效的数据信息，提取并保留实际有效的目标网络信息。最终匹配生成的数据信息将触发引导丢包率和路由测量任务的执行。

（4）在丢包和路由测量模块中，控制平台会根据构造不同类型的测量数据包分别对目标网络的丢包率和路由信息进行测量。主动探测数据包类型的构造依据事先被动监测统计分类的数据流信息。在对目标网络进行丢包率测量时，采用周期动态调整的主动发包方式，目的是降低因网络突发而导致的持续丢包事件。最终根据测量的丢包率数据分析当前网络性能；在对目标网络进行路由路径跳数跟踪测量时，事先要在NS3网络仿真软件上进行仿真测试，测试其链路是否可通。随后测量真实目标网络的路由路径信息，并统计测量结果。每次测量的路由路径跳数信息会实时传送至控制平台。

3.2 基于正则表达式的数据信息处理

传统的网络测量技术研究主要是基于抽样技术和数据流技术[13]，通过牺牲测量精度来压缩采样测量数据的规模，可拓展性不强，在实际应用中受到很大程度的制约。而本文采用的是一种主被动结合的网络测量技术，采用基于正则表达式的过滤和筛选机制从被动采集的海量测量数据中过滤掉冗余和无效的数据报文信息，保留实际有效的测量信息。此方式不仅压缩了采样测量的数据规模，同时保持了测量精度的稳定。被动捕获的一些冗余和无效的数据报文信息直接被内核丢弃掉，而有效的数据报文信息则需要经过控制中心的数据采集平台进行哈希过滤、分类与计数处理生成本地聚合日志。由于被动测量的数据包粒度很细，则测量记录产生的数据量比较庞大，所以要从本地聚合日志中匹配和筛选出有效的测量数据，则必须要调用事先编写的基于正则表达式的匹配和筛选算法，实现对本地聚合日志的数据处理和分析的能力。开发语言使用的是Python，采用CentOS 7操作系统自带的编译器对算法进行编译和执行。

探测数据信息匹配的目的一方面是为了对本地聚合日志做进一步过滤和筛选，保留所需要的真正有效的探测数据包。同时，对被动测量触发引导主动测量任务的执行起到了辅助作用，为下一步主动测量获取网络丢包率和路由信息做准备。与传统的数据信息挖掘方式相比，基于正则表达式的数据信息匹配和筛选机制实现方式相对方便，一方面不需要额外的硬件支持，另一方面算法在匹配和筛选时循环迭代比较的次数相对较少，降低了其执行过程中的时间复杂度。

数据信息的匹配和筛选策略：建立一个实时更新的动态采集数据存储数据库和一个动态调用的匹配规则库，针对聚合日志中的每条数据都进行细粒度的匹配、筛选、过滤和分类。探测数据的匹配和筛选算法遵循正则表达式，匹配的内容主要包括本地IP地址、目标IP地址、端口以及数据包类型等信息。数据的筛选基于哈希函数并依据筛选条件对特定的数据流信息按照指定的字段依次过滤，筛选掉与测量无关的冗余数据，以达到降低数据耦合度的目的。图2 描述的是数据信息的匹配和筛选过程。

算法1 描述了测量的数据信息匹配和筛选的具体算法。对已经过滤掉的数据进行统计和分类，将源端和目的端信息在总控中心映射为端信息EPI（End Point Information），即IP 信息、端口信息等。并用组表（group table）的形式存储数据，目的是方便引导主动测量任务的执行。

算法1数据信息匹配和筛选算法

1.Receive_Match（）{

图2 数据信息的匹配和筛选过程

2.whilepacketsis inLocate_log

3.do setmatch_process（）

4.Target.addr（）

5.Target.ports（）

6.Target.type（）

7.whileTarget.addris not in Match andportnot inrange

8.do setfilter_algorithm（）

9.ifTarget_add.freq>1

10.SkipnextTarget.addr

11.else

12.do setClassify_process（）

13.Target.type=TRUE

14.end if

15.end while

16.resetreceive packets

17.end while

18.}

当数据匹配和筛选过滤结束后，通过主动发送探测数据包的方式测量目标网络的丢包率和路由信息。针对已经探测过的目标网络节点不再重复地发送探测数据包，以降低主动发包对测量结果的影响。根据本地聚合日志中不同类型的数据信息构造不同类型的探测数据包，如TCP类型、UDP类型、ICMP类型等。

3.3 基于周期动态调整的丢包率测量

丢包率是指在某段时间内由源主机向目的主机发送的数据包中丢失的数据包占传输总数据包的比率，链路丢包率能及时反映网络传输性能以及由网络突发[22]导致的网络拥塞[23]等问题。假设从源端发送的数据包个数为Packets_start，达到目的端的数据包个数为Packets_end，则数据包在单条链路上的丢包率为：

丢包率的测量方法主要是主动测量和被动测量，但是被动测量无法取得端到端的路径信息，所以一般链路丢包率大多采用主动测量的方式。主动测量丢包率的基本过程是在指定时间内，周期性地由源端向目的端持续发送探测数据包，若某个探测包在规定的时间阈值内没有收到响应数据包，则记为一次丢包事件。如Ping、BADABING[8]、Iperf均采用此方式。丢包率的测量需要线程监听目标流的首尾交换机，根据两个交换机节点的抽样结果进行估算和后继测量。每一次测量任务结束，任务线程都会记录相应的测量结果，以便回溯到上层调用和查看。

3.3.1 网络突发判定及发包周期调整

在IP网络中，由于网络流量的波动具有不规则的特性，所以丢包事件一般是由网络流量的突发和急剧波动造成的。网络流量的突发和急剧波动往往会导致网络在短时间内出现拥塞，增加网络链路的往返时延，从而导致探测数据包的丢失。由于网络流量具有随机突发性，因此丢包也具有随机突发的特性。在使用主动测量方式测量链路丢包率时，若测量周期过大，则丢包率的测量结果不准确；若测量周期过小，则会影响网络端到端的测量负载，导致测量结果出现偏差。所以要准确地测量链路丢包率，就需要一种周期动态调整的发包策略。本文在研究过程中采用周期动态调整的主动发包测量方式，根据网络是否处于突发时段来适度调整主动发包的测量周期。

假设丢包测试实验共执行了N次测量任务，则探测时延结果序列为：{T1,T2,…,TN}。其中di表示每次主动发包后探测得到的平均时延。如果发送第i次探测包产生丢包，则设置Ti的值为0，否则Ti的值不变。只判断Ti的值是无法判断当前测量阶段是否属于丢包突发时段，此时根据排队时延定义一个丢包突发指标PT，如公式（2）所示：

其中，Tmin是第i次测量得到的往返时延的最小值，Tpre表示所探测到的前一个丢包事件中时延的平均值。公式（2）中的指标函数可视为判断当前时延信息是否发生丢包突发时段。当Ti的值为0时，表示当前探测已经产生时延，将PT的值置为1；当Ti的值为不等于0 且PT的值小于1 时，则表明第i次发包探测所产生的平均时延小于前一个丢包事件的最小排队时延，此时链路上的丢包事件属于突发；若Ti的值为不等于0且PT的值大于1 时，则表明第i次发包探测所产生的平均时延大于前一个丢包事件的最小排队时延，即连续发生丢包事件，则会增加下次发包丢包的概率。所以需要增加下次发包的探测周期，减小因网络突发导致的测量误差，使后续发包测量任务趋于稳定。

假设当前测量时间周期为ΔTi，引入两个周期动态调整参量β1、β2，其中β1∈(0,1)、β2∈(1,2)。β1是0到1 之间的随机数，而β2是1 到2 之间的随机数。若当前测量产生连续丢包事件时，则将下一个测量周期调整为ΔTi+1=ΔTi×β2；若测量趋于平稳时，则将下一个测量周期调整为ΔTi+1=ΔTi×β1，以提高测量精度。据此可定义每次测量周期最大时延阈值特征函数为式（3）所示：

其中，ΔTi表示当前发包测量周期，λ表示前i次测量周期的均值。φ(t)为规定的第i+1 次发包测量时最大约束时延阈值。

3.3.2 基于泊松分布的周期采样方式

依据以上网络突发引起的链路丢包情况，对发包周期做了动态调整，主动发包测量会在短时间内向目标网络发送大量的探测数据包，能够在网络突发时段采集到真实的丢包数据。一般高速网络吞吐量较高，突发丢包并不频繁。因此，本文研究并采用基于泊松分布的丢包采样方式，采集实际测量的链路丢包率。当出现往返时延较大且连续丢包事件时，则减小采样间隔，使采集的丢包率数据更为准确；当时延较为平缓时，则增大采样间隔，使其丢包率的测量保持较小的网络负载。

泊松分布的采样间隔特征函数如公式（4）所示：

P表示采样的样本间隔，λ表示前i次测量周期的均值。由于泊松采样具有渐进性的特点，在平均采样频率不高时可以降低因网络波动带来的测量误差，并提高丢包测量的准确性。

3.4 多路径动态路由测量描述

3.4.1 路由路径跳数测量策略

路由测量在网络性能测量中占据着非常重要的一部分，对研究链路吞吐量、改善网络负载均衡、理解网络结构以及网络行为等方面都具有非常重要的意义。选择合适的端到端路由测量方式可以有效地提高路由探测的效率，减少因网络负载带来的影响。网络路由测量一般采用的是以Traceroute[17]为主的主动测量方式。利用TTL记录终端节点的值与起始节点值之间的差值确定单条链路的路径跳数。一般一次目标网络路由跟踪的路径跳数不超过30跳。文献[15-16]提出基于流粒度生成的接触图路由算法，通过捕获探测数据包对数据流进行逐跳跟踪，并输出完整的路由跟踪路径。但是这种方式需要提前构建好网络拓扑节点数据库，每次遍历节点都要重新启动路由，测量周期较长，时间复杂度也比较高。因此，此方法比较适合规模较小的网络。

文献[18]提出一种Dijkstra广度优先搜索遍历算法，实现从源端到目标网络的路由测量。但是需要预先建立一个邻接网络节点结构图，并对网络节点的权值进行标记，从技术上来讲工程量太大。一般复杂的高速网络大都是基于网状网络结构，如图3所示。若要对目标网络节点进行理由跟踪，则必须要考虑到链路的空间复杂度。据此，本文提出一种多路径动态路由测量算法，探测目标网络路由路径跳数信息，采用此方式的目的是为了简化路由探测规模、减少路由寻路探测跟踪时间。

图3 典型的网状网络结构

3.4.2 多路径动态路由测量

在大规模的网状结构网络中，一般测量一个网络节点经过单条路径时的收敛时间在2～10 s 内。此时可定义单条路径最大传输时间阈值为End_Time。如公式（5）所示：

其中Max_TranTime是指所有目标节点的最大传输时间；Packet_TranSize是指单次路由测量发送的数据包的大小；Max_Bandwidth是指当前网络传输的最大带宽，主要与目标网络的链路吞吐量有关；Packet_Distance是指源节点和目标节点之间的通信距离；Packet_TranSpeed是指数据包的发送速度，也与链路带宽和吞吐量有关。由于每条链路的传输距离都不相同，设置单条路径最大传输时间阈值的目的是保证每条探测路径都有足够的探测时间。

依据多路径动态路由路径测量策略，将目标网络测量的节点通过算法和数据存储的方式加以实验验证。算法中所涉及到的数据变量如表1所示。

表1 算法中使用的相关变量

多路径动态路由测量算法结合了Nmap SYN 主动发送探测包的方式，通过p0f 日志捕获的方式跟踪其路由路径跳数。图4 描述了利用多路径动态路由测量方式探测寻路的执行过程。每次发包前均需按照不同协议的数据类型构造不同类型的探测数据包。探测数据包的预设信息主要包括源节点、目标节点、测量协议、端口等信息。在对数据包中的目标节点与探测节点进行匹配时，需要将节点的信息进行入栈操作。每一条探测路径在探测时均需要打印遍历节点，并记录单条路径的路径跳数。若单条路径的路径条数没有超过预设值且请求超时，则路径跳数TTL的值减1进入下一路径，对于已探测的节点不再重复发送探测包，并重复以上整个过程。直到发送的数据包中的探测节点与目标网络节点匹配成功时，则表示路由探测跟踪成功，输出其路径跳数。同时将TTL的值重新置为0，开始测量下一个目标网络节点。如果在规定时间阈值内或者超过最大路径跳数，则表示探测失败，开始测量下一个目标网络节点。重复以上整个过程，直至所有的目标网络节点路由跟踪测量任务结束。

探测路径的选择是随机的，在数据链路探测过程中事先不考虑邻近节点，只考虑路径是否可达。若探测到目的节点，则执行进入下一个目标节点的路径探测任务；否则，路径节点退栈，进入邻近节点路径，重复以上操作直至成功匹配目标节点。多路径动态路由测量算法如算法2所示。

图4 多路径动态路由探测寻路过程

算法2多路径动态路由测量算法

输入：Src_Nodes，Des_Nodes，Path_List，Stack_Nodes。

输出：Stack_Nodes，TTL。

1.whileSrc_addrinSrc_NodesandDes_addrinDes_Nodes

2.StoreCurrent_time，Each_Hop

3.AddDes_addrinPath_List

4.AddDes_addrinStack_Nodes

5.TTL←TTL+1

6.whileCurrent_timein beforeEnd_Time

7.UpdateCurrent_time

8.CalculateCurrent_time，TTL

9.whileDes_addris not inPath_List

10.ifCurrent_timeis beforeEnd_Time

11.ifTTLis beforeEach_Hop

12.print→Stack_Nodes

13.whileCurrent_Timeis afterEnd_Time||TTLis afterMax_Hop

14.wai（tDeadLine）

15.Send_an_ICMP_Reques（ttimeout）

16.RemoveDes_addrfromStack_Nodes

17.TTL←TTL-1

18.ifPath_ListandStack_Nodesis not empty

19.UpdatePath_List，Stack_Nodes，TTL

20.CalculateCurrent_time，timeout.Number，TTL

21.iftimeout.Numberis afterFinal.Number||TTLis afterMax_Hop

22.Send_an_ICMP_Reques（tTracking failure）

23.else

24.print→Stack_Nodes&&TTL

25.End while

26.ResetCurrent_time，Each_Hop，TTL

文献[17]一般情况下其路由寻路探测的平均时间复杂度为O(kn2)，而文献[18]以Dijkstra 算法为基础的路由增广路经集探测方式其平均时间复杂度为O(khs(E+nlgn))。而本文提出的多路径动态路由测量算法平均时间复杂度为O(knlgmn)。由于多路径动态路由测量算法在执行过程中需要匹配的相关指标参量较少，所以此方式可以有效地减少路由寻路执行过程中的算法迭代次数，因而算法的时间复杂度相对较低。路由探测过程中其算法的时间复杂度受到循环次数k和探测的数据量n以及匹配比较次数m等综合因素的影响。

4 实验结果与数据分析

4.1 实验设计与环境搭建

为了验证通过引导被动测量结果引导主动测量的技术可行性和实验数据的有效性，本文搭建了一个主被动结合的网络测量实验环境。包括两台Dell Power-Edge R730 2U 机架式服务器，两台 Intel®Xeon®CPU E5-2620 v3 处理器，内存 16 GB。一台 OpenFlow 交换机，其中控制机通过带内方式与OpenFlow 交换机相连。一台操作系统为Centos 7的终端，用来采集和存储网络数据流。控制平台采用的是基于Debian 的Kali Linux 操作系统。软件工具包括Visual C++ 6.0、Wireshark、NS3 网络仿真器以及网络抓包工具TCPDUMP等。通过被动测量的结果触发引导主动测量任务的执行，即对网络丢包率以及路由信息进行测量。实验事先需要在NS3网络仿真器中进行仿真测试，测试目标网络链路是否连通，随后在真实测试环境下对目标网络进行丢包率和路由信息测量。

4.2 数据信息匹配和筛选机制实验验证

本次测试实验所采集的网络数据集均来自混杂模式下的本地校园网网络。采集的海量数据通过OpenFlow交换机转发，处理器处理，经被动检测设备检测以及内核处理。目的是清洗过滤出冗余的测量数据，匹配筛选出真实有效的测量数据。本次测量时间共持续了20天，采集源端和目标网络往返数据报文信息，以方便查看其往返数据包收发情况。测量数据结果如图5所示。

图5 往返数据包的收发测量结果

通过图5 可知大部分收发的无效和冗余的数据包是被过滤器和系统内核丢弃，而匹配和筛选过的有效的数据包占比低于30%，说明本文提出的基于正则表达式的匹配和筛选算法效率较高，能够将绝大多数无效或冗余数据包过滤掉。随着测量时间的增加，在第11天前后过滤和被动捕获的数据包数量均达到最大值，说明这段时间网络收发的数据包的数量持续增加，网络流量属于突发时段，在这段时间最容易产生丢包。但在随后一段时间内数据包的收发又趋于稳定状态。数据匹配和筛选的主要目的是为了去除冗余数据，而保留真实有效的测量数据。为后续目标网络丢包率和路由信息的测量做准备。

4.3 丢包率测量实验验证

在对链路丢包率进行测量时，本文采用周期动态调整的主动发包方式与文献[8]提到的Ping 和基于BADABING 测量结果做对比，分析周期动态调整的丢包率测量方式的有效性和优势。实验将被动采集匹配和筛选过滤的125个目标网络节点进行丢包率测量，发包时间周期采用周期动态调整的主动发包方式。而Ping和BADABING 则使用减半或倍增的周期发包方式，分别向目标网络发送125个探测数据包，测量其链路丢包率。将测量得到的丢包率数据采用泊松分布样本的采样间隔获取其丢包率数据。采样得到的丢包率数据如图6所示。

图6 丢包率测量结果

图6数据显示周期动态调整的主动发包方式与Ping和BADABING测量方式所测得的丢包率对比结果。从图6 整体可知，随着探测数据包数量的增加，三种丢包率测量方式单位时间内丢包率也都出现峰值，说明探测数据包的短时拥塞对丢包率会产生一定的影响。测量初期丢包率均处于较低水平，而随着探测数据包数量的增加，三种发包测量方式所测量得到的丢包率均呈现不规则的波动，说明网络波动也会对链路丢包率产生影响。

待发包周期调整之后，丢包率也会随之降低。据图6可知，利用周期动态调整的主动发包方式在测量链路丢包率时，整体上所测得的丢包率的值均低于Ping 和BADABING 测量方式。通过数据统计计算，可知周期动态调整的主动发包方式与Ping和BADABING利用减半或倍增的周期发包方式相比，可以将链路丢包率降低60%以上；说明周期动态调整的发包测量方式能够有效地调整主动测量的发包周期，降低探测链路的丢包率。更直观地说明了动态参量随机值的调整策略误差抖动较小，比减半或者倍增的几何发包周期调整策略更加稳定，降低链路丢包率的效果更明显。同时也证明了泊松分布的采样方式能够比较准确地采集到真实测量的丢包率数据。真正实现了在压缩采样规模的同时保持了测量精度的稳定。

4.4 多路径动态路由测量实验验证

本文在匹配筛选的所有目标网络节点中随机选取100 个进行路由跟踪探测实验，并按照文献[20]提出的Traceroute测量方法和文献[18]提出的Dijkstra路由测量方法以及本文提出的多路径动态路由测量方法的测量结果进行对比分析。三种测量方法均规定单次路由探测最大路径跳数均不超过30。并分别对三种测量方法所得到的路由测量结果进行分类统计，统计每次测试的路径跳数以及总的测量时间开销。测量结束后对所探测的目标节点路由信息进行分类统计和编号。

据图7可知，三种路由测量方法最终成功跟踪70个目标网络节点。在测量同一目标网络节点时，三种测量方法获得的路径跳数值相差很小。可以证明多路径动态路由测量方法在测量目标节点路由路径时其准确度较高，且路由寻路探测可行性较强。

图7 路由路径跳数测量结果

表2反映的是利用三种测量方式测量目标节点时，跟踪成功的路径跳数平均值、路由探测总的时间开销和跟踪成功的平均时间开销之间的数据对比结果。从表2统计数据可知，多路径动态路由测量方法与Dijkstra 和Traceroute测量方法跟踪成功的路径跳数的平均值分别为：15、16和18。可以看出多路径动态路由测量方法比Dijkstra 和Traceroute 测量方法测量的路由路径跳数的平均值都要少，说明多路径动态路由测量方法在探测路由路径时，能在一定程度上降低探测路径的复杂度。由于多路径动态路由测量方法算法开销较小，故在探测时会以最短路径作为路由跟踪成功的探测路径。三种测量方法路由探测总的时间开销分别为：1 962 s、1 682 s、1 887 s，跟踪成功的平均探测时间分别为：5.69 s、7.32 s、5.16 s。可以看出多路径动态路由测量方法与Dijkstra和Traceroute 测量方法相比，虽然路由探测总得时间开销相差不大，但是多路径动态路由测量方法比Dijkstra和Traceroute测量方法跟踪成功的平均路由探测时间都要低。多路径动态路由测量方法与Dijkstra测量方法相比，探测成功的平均路由跟踪时间降低了大约10%；与Traceroute 测量方法相比，探测成功的平均路由跟踪时间降低了大约42%。据此次路由测试实验数据结果可知，多路径动态路由测量方法可以有效地降低路由探测过程中的复杂度，减少探测过程中的平均路由跟踪时间。

表2 路由跟踪测量结果

5 结束语

本文通过搭建一个主被动结合的网络测量技术测试环境，并利用被动测量的数据结果触发引导主动测量任务的执行。相比较与传统的网络测量技术，主被动结合的网络测量技术能够实现在压缩测量规模的同时，还能保持测量精度的稳定。对于规模较大或较小的网络都适用。此方式不仅保持了主动测量和被动测量的优点，使得测量结果能更好地反映网络的真实情况，对理解网络性能和网络行为具有非常重要的意义。在对被动测量生成的本地聚合日志数据进行处理时，本文提出一种基于正则表达式的数据匹配和筛选算法，将采集到的无效和冗余的数据信息筛选过滤掉，保留有效的测量数据信息。与传统的数据信息挖掘方式相比，实现方式相对方便，一方面不需要额外的硬件支持，另一方面算法在匹配和筛选时迭代比较的次数相对较少，降低了其执行过程中的时间复杂度。在对目标网络进行丢包率测量时，本文研究并提出一种周期动态调整的主动发包方式测量链路丢包率，根据网络是否发生突发来适当调整探测包的发包时间周期。相较于减半或者倍增的几何形式的发包调整策略，动态参量随机值的调整策略测量误差抖动较小，相对来说比较稳定。随后对测量的丢包率数据采用泊松分布的采样方式进行采样，获取采样样本周期内的真实丢包率测量数据，降低因网络突发导致的测量误差。相比较一般的周期采样方式，采样样本的准确率较高。在对目的网络进行路由跟踪测量时，本文研究并提出一种多路径动态路由测量方法。与Dijkstra和Traceroute测量方法相比，多路径动态路由测量方法测量得到的路由路径跳数的平均值较小，且跟踪成功的平均路由探测时间较少。由于算法在执行过程中匹配的相关指标参量较少，减少了路由寻路执行过程中迭代次数，因而算法的时间复杂度相对较低，故属于一种轻型易用的路由信息测量方法。如何在减少路由跟踪时间的同时，又能提高总体目标节点路由跟踪的成功率，则是下一步工作要重点研究的内容。