网络流量分布式测量新方法

夏靖波，任高明

（1.厦门大学 嘉庚学院，福建 厦门　363105；2.空军工程大学 信息与导航学院，陕西 西安　710077）

网络流量分布式测量新方法

夏靖波1，任高明2

（1.厦门大学 嘉庚学院，福建 厦门363105；2.空军工程大学 信息与导航学院，陕西 西安710077）

主机连接度作为网络流量测量的一个重要测度，近年来倍受关注。针对现有主机连接度测量方法不能应用于大型网络的问题，提出了一种基于位域的主机连接度分布式测量方法。方法在借鉴共享存储单元思想的基础上，使用哈希函数将到达的数据包映射至位域存储；测量完成后，将各测量点采集得到的位域按位取或，并利用极大似然估计方法估算主机连接度值，有效地解决了分布式测量中各点采集数据难以融合的关键问题。最后，通过理论推导和实验证明了方法的有效性和准确性。

计算机网络；网络流量；分布式测量；主机连接度

流量测量是理解网络行为和掌握网络运行规律的有效方法之一，主机连接度测量作为其重要组成部分，对网络安全检测等应用具有非常重要的意义。通常，主机连接度定义为测量时间内和某一源主机发生关联的不同目的主机的数目。在检测端口扫描、蠕虫传播、DDoS攻击时均可用到主机连接度测量，因为端口扫描和蠕虫传播是由在短时间内源主机与不同目的主机建立大量的连接引起的［1］；另外，大型的服务器厂家可通过主机连接度测量去分析服务器内容的受欢迎程度等等。

随着互联网的高速化、复杂化以及网络规模的不断扩大，主机连接度测量的难度越来越大。单点测量由于获取的信息有限，往往难以反映整个网络的运行状况。分布式测量具有单点测量无法比拟的优势，通过在大型网络的不同节点部署多个测量设备，综合测量结果可以得到较为详尽、全面的信息，进而推断出全网运行状况。但大型网络中主机连接度的分布式测量问题非常有挑战性，原因有二：一是网络链路传输速率愈来愈高，要求必须在更短的时间内处理单位数据分组；二是获取全网范围的主机连接度，需要融合各测量点采集到的信息。上述两个条件均增加了主机连接度测量的难度。

1　相关工作

测量主机连接度，最直接的方法是记录测量时间内两两不同的连接对［2-3］（连接对是指一个数据包的源地址和目的地址构成的地址对）。测量结束后，统计得到的每个源地址对应的连接对数目，即为该源地址的主机连接度。同时，文献［2］提出使用哈希表存储连接对，提高了处理效率。该方法的缺点是所需存储空间大。

文献［4］提出使用两个哈希表存储的方式估算主机连接度。一个哈希表用于存储连接对，另一个用于存储源地址和连接对计数；同时，引入抽样机制用于降低处理数据量。和直接测量法相比较，该方法可以支持快速查询操作，但抽样方法降低了测量准确率。文献［5］引入位图减小所需存储空间，较好地节省了空间资源，每个连接对只需占用1 bit的存储空间，但是该方法的空间利用率和准确率之间的平衡难以把握。

文献［6］提出共享位图的思想，提高了空间利用率，可以在较小空间条件下，准确地测量主机连接度，但由于无法完成测量数据的融合，不能直接应用于大型网络的分布式测量。例如，当某个数据包P依次通过图1中的B、C、D节点，假定在B、C、D 3个节点均布置了测量设备，那么，P将被测量并记录3次。在融合测量记录时，假设B、C、D节点对应的记录中，源地址S的连接度分别为10，20，15，那么全网内源地址S的连接度究竟是多少？是最大值20？还是45？本文正是针对主机连接度的分布式测量中存在的测量数据融合问题，提出一种新的测量方法，实现大型网络的主机连接度测量。

图1　分布式网络测量结构Fig.1　The structure of distributed measurement

2　分布式主机连接度测量方法

单点测量是分布式测量的基础，分布式测量是单点测量的融合。文章借鉴文献［3］提出的主机连接度单点测量方法CSE，提出一种可用于大型网络的分布式主机连接度测量方法（文中称为DSM方法）。

2.1单点测量

CSE方法中用于存储主机连接度信息的是一个长度为m的位域。当有数据包p到达时，根据哈希函数H（src⊕R［H （des⊕K）mods］）确定数据包在位域中的位置，其中src为p的源地址，dst为P的目的地址；k为防止哈希碰撞攻击而引入的关键字；H为哈希函数，后文实验部分分别选取MD5和SHA1两种哈希函数，对测量结果进行了比较。根据极大似然估计，推导后得到源地址src的主机连接度的估计值为

其中s为逻辑位域的长度，Vs是LB（src）中0所占的比例，Vm为位域中0所占的比例。具体推导过程请参考文献［3］，在此不再赘述。

2.2分布式测量

为解决主机连接度分布式测量中各测量点存储记录的融合问题，本文方法实现时，在多个节点布置测量设备，并为每个测量点分配一个长度为m的位域，分别记为BF1、BF2…BFn，n为测量点的个数。每个测量点，使用相同的哈希函数H，按照单点测量方法，将通过各测量点的数据包记录至对应的位域中。在测量结束后，将各位图按位取或，得到的位域表示为BF，即为全网主机连接度信息。

根据单点测量中估算方法，从位域BF中估算主机连接度即可。

2.3复杂度分析

2.3.1时间复杂度

在流量测量领域，通常使用哈希查找次数和内存读写次数作为衡量算法时间复杂度的性能指标。在高速网络链路中，流量测量面临的主要困难之一是单位数据包的处理时间越来越短，这就要求算法处理单位数据包的操作次数尽量少。本文方法根据到达数据包的连接对信息，只需使用1个哈希函数H进行1次哈希查找，即可完成连接对至位图的定位；之后，只用1次写操作，即可置位图中相应的位置为1，完成信息的记录。

2.3.2空间复杂度

根据位共享的思路，单点测量中，位图的长度为m，即所需的存储空间为m bit。在分布式测量中，每个测量点所需空间和单点测量相同，整个分布式结构共需的存储空间为各测量点所需空间之和n×m bit。

2.3.3实现的考虑

在处理速度方面，采用哈希查找的方式确定位图的位置，可以实现时间复杂度为O（1）的查找速度；为实现高速网络环境中数据包的线速处理，考虑采用处理速度较快的SRAM，由前述易知，处理单位数据包需要访问内存的次数为1次，根据当前硬件技术，SRAM具备2 ns完成1次操作的处理速度，意味着本文方法处理一个数据包只需要2 ns。在OC-768链路上，假定满速率传输包长为64 byte的数据包，则包到达间隔为12.5 ns，说明本文方法的处理速度完全满足OC-768链路的测量需求。

3　实验验证

3.1实验一

文献［3］提出的CSE方法采用位共享思路，准确率高，速度快，但文中并没有明确指出使用什么哈希函数，而哈希函数的选择合理与否，对于测量结果的准确性来说，非常重要。因此，实验一选择MD5和SHA1两种常用的哈希函数，应用于CSE方法，比较二者测量主机连接度的准确性，后文分别称之为CSE_MD5和CSE_SHA1。为保证两种方法具有可比性，选择和文献［3］相同的参数，即存储空间分别取4 M，2 M，1 M，0.5 M。

所用仿真环境如下：仿真工具为MATLAB R2010a；计算机cpu为pentium（R）Dual-Core，主频2.69 GHz；内存3G；操作系统为windows XP SP3。实验数据取自CAIDA提供的实际互联网数据，该数据采集于2011年某2.5 G链路。

图2　CSE_MD5、CSE_SHA1两种方法测量结果Fig.2　The two measure results of CSE_MD5 and CSE_SHA1

如图2所示，为CSE_MD5方法和CSE_SHA1两种方法测量主机连接度的结果，图中每个点表示一个源地址的主机连接度，横轴为该源地址的真实主机连接度值，纵轴为对应的估计值。对于实验数据中主机连接度真实值相同的多个源，本文只随机选择一个点展示在图中。图2中（a）～（d）分别表示存储空间取4M、2M、1M和0.5M时CSE_MD5的测量结果。图2中的四组图（e）～（h）分别表示存储空间取4M、2M、1M和0.5M时CSE_SHA1的测量结果。测量图中的点越靠近直线y=x周围，估算方法越准确。表1列出了CSE_MD5和CSE_SHA1两种方法的测量主机连接度的平均误差。

结合图3和表1可以得出以下结论：随着分配空间的减小，两种方法的准确率均下降；在分配相同存储空间的情况下，两种哈希函数应用于CSE方法中测量主机连接度时，MD5的准确率稍高于SHA1方法，但优势并不明显。

表1　两种方法测量主机连接度的平均误差Tab.1　Average error of two measure spreader

3.2实验二

本文提出的分布式主机连接度测量方法，主要贡献是解决了分布式测量中各测量点采集数据的融合问题。为验证文中方法的分布式测量特性，按照图1所示的结构图，在实验室搭建模拟环境，其中A～F均表示交换机，每个交换机连接若干计算机；在除C点以外的其余5个节点布置测量设备，对采集到的数据包信息按照本文提出的分布式测量方法进行融合。同时，使用上文提到的直观方法，测量通过各节点的数据包的主机连接度，和本文方法的估计值进行比较，结果如图3所示，其中图（a）至（d）依次为存储空间取4 M，2 M，1 M，0.5 M时的测量结果。表4给出了4种存储空间条件下，文中方法的误差变化图。根据图3和图4易知，本文提出的分布式测量方法，对于全网主机连接度的测量具有较好的效果，在存储空间为4 M和2 M时，误差能保持在较小的范围内。

图3　分布式测量结果Fig.3　The result of distributed measurement

4　结束语

主机连接度测量对于网络安全等应用意义重大。网络规模的不断扩大，使得大型网络的主机连接度测量成为急切需要解决的问题。针对现有的主机连接度测量方法无法直接应用于大型网络的缺点，本文提出一种分布式主机连接度测量，在借鉴CSE方法中存储单元共享思路的基础上，提出对存储位域按位取并的方法解决分布式测量结构中各测量点数据的融合问题［7］。在分析算法的时间复杂度和空间复杂度后，结合当前半导体发展水平，给出了方法的可实现性。最后，使用实际互联网数据和实验室搭建网络环境采集的数据对方法进行了评价。结果表明该方法在保持准确性的同时，具有较好的实用性。

图4　误差比较图Fig.4　The comparison of error

［1］周爱平，程光，郭晓军.高速网络流量测量方法［J］.软件学报，2014，25（1）：135-153.

［2］Yoon M，Chen S.Real-Time Detection of Invisible Spreaders ［C］//Global Telecommunications Conference，2008.IEEE GLOBECOM 2008.IEEE.IEEE，2008：1-5.

［3］Yoon M，Li T，Chen S，et al.Fit a Spread Estimator in Small Memory［C］//INFOCOM 2009，IEEE.IEEE，2009：504-512.

［4］Venkatataman S，Song D，Gibbons P，et al.new streaming algorithms for fast detection of super spreaders.In：Proceeding of NDSS.2005.

［5］Estan C，Varghese G，Fish M.Bitmap algorithms for counting active flows on high-speed links.Proceeding IMC 03Proceedings of the 3rd ACM conference on Internet measurement，2003：153-166.

［6］Li T，Chen S.Traffic measurement on the internet.2012.

［7］徐敏，夏靖波，申健，等.基于LEAST的高速网络大流检测算法［J］.空军工程大学学报，2015（8）：25-30.

Novel algorithm for distributed measurement of network traffic

XIA Jing-bo1，REN Gao-ming2
（1.Tan Kahkee Cooege，Xiamen University，Xiamen 363105，China；2.School of Information and Navigation，Air Force Engineering University，Xi’an 710077，China）

The spreader is paid more attention as an important content of network traffic measurement in recent years.To address the problem of the existing spreader measurement algorithms can’t be applied to large-scale network，a novel distributed measurement algorithm of spreaders is proposed.A hash function is used by the algorithm based on dynamic bit sharing to map the packet data to bit field.The bit fields collected from all measurement point is OR by bit to bit and MLE method is used to estimate the spreaders.The algorithm integrates data in distributed measurement point effectively.Finally， the algorithm is proved to be effective and accuracy through theoretical and experiments.

computer network；network traffic；distributed measurement；spreader

TN91

A

1674－6236（2016）03-0137-04

2015-03-29稿件编号：201503424

陕西省自然科学基础研究计划项目（2012JZ8005）

夏靖波（1963—），男，河北秦皇岛人，教授。研究方向：网络管理和网络测量。