基于虚拟向量的主机基数分布测量算法

摘要

主机基数定义为一段时间内网络中的某主机链接的其他不同主机的数量，对于主机基数的检测是当前网络测量中的一个重要内容。随着互联网的发展，网络入侵事件频繁发生，如蠕虫病毒、DDOS攻击等，短时间内受感染主机向大量其他目的主机发送链接或大量不同源主机向某目的主机发送攻击，造成网络阻塞，导致网络中的主机基数分布发生变化。因此，主机基数分布的测量对网络管理和应用有着重要的意义。
　　 现有的基数分布测量算法，或者存储空间消耗大、或者执行速度慢。为了解决上述问题，我们提出了一种基于虚拟向量的主机基数分布测量算法，将连续虚拟向量的概念应用到该算法中，实现了以较少的存储空间消耗和较快的执行速度记录处理网络中所有的报文信息，获得最终的主机基数分布结果。我们的算法由两大模块组成，分别是在线处理模块和离线处理模块。在线处理模块利用三个一维bitmap位数组记录下网络中所有主机的流信息，同时该模块还设计了一个BloomFilter数据结构对网络中的源IP进行过滤，并将所有不同的源IP记录到一个数组中。离线处理模块以在线处理模块记录下来的所有不同的源IP为依据，参照bitmap位数组存储下的主机的流信息，获得每个源主机的主机基数估计，得到最终的主机基数分布结果，并将结果以＜主机基数:主机数目＞的元组形式输出。
　　 论文采用来自两个不同网络的四个数据源Trace对我们提出的算法进行实验。实验结果表明，基于虚拟向量的主机基数测量分布算法不仅节省了存储空间，还可以快速准确地检测出网络中的主机基数分布。

目录

声明

摘要

第1章 绪论

1．1 网络测量的必要性

1．2 主机基数的相关定义

1．2．1 流的定义

1．2．2 超点的定义

1．2．3 主机基数的定义

1．3 国内外研究现状

1．4 论文的研究内容及组织结构

第2章 网络测量的相关技术

2．1 抽样技术

2．2 Bloom Filter

2．2．1 标准的Bloom Filter

2．2．2 Bloom Filter的误差分析

2．3 本章小结

第3章 主机基数分布的相关算法研究

3．1 基于有损数据结构的流分布测量算法

3．1．1 基于单分辨率的流分布算法

3．1．2 基于多分辨率的流分布算法

3．2 基于连续FM sketch的主机基数分布检测算法

3．2．1 在线流处理模块

3．2．2 统计推断模块

3．3 基于虚拟向量的主机基数分布检测算法

3．3．1 记录流信息的虚拟向量

3．3．2 主机基数的估计模块

3．4 基于抽样和数据流的超点检测算法

3．4．1 基于bitmap和流抽样的超点检测算法

3．4．2 基于二维bitmap和流抽样的超点检测算法

3．5 基于双层过滤的超点检测算法

3．5．1 双层过滤模块

3．5．2 主机基数估计模块

3．6 本章小结

第4章 基于虚拟向量的主机基数分布测量算法

4．1 算法描述

4．1．1 算法的总体设计

4．1．2 算法的具体描述

4．2 算法分析

4．2．1 算法的性能分析

4．2．2 算法的误差分析

4．2．3 算法的参数分析

4．2．4 算法的对比分析

4．3 实验说明

4．3．1 实验数据源

4．3．2 实验的测量测度

4．3．3 实验中哈希函数的设置

4．3．4 实验中相关参数的设置

4．3．5 实验结果

4．4 本章小结

第5章 总结与展望

5．1 论文的创新点

5．2 论文完成的主要工作

5．3 工作展望

参考文献

致谢