论文总字数：24479字

摘 要

随着当代网络的快速发展，网络流量的链接速率和规模急剧增长，由此带来的不仅是实时信息交互的便捷，也使得有效的网络异常检测和优化网络资源的配置变得异常困难。国内外经过近些年的研究后，发现了一种有效的概括全局数据的手段sketch。然而这种数据结构概括信息的时候往往会丢失流的原始信息，从而使得恢复流的信息变得异常困难。因此，本文的研究目标就是寻找一种适合高速网络环境的可逆的流量监测算法，并且在此前提下算法的流程越简便越好，时间和空间代价越小越好。在对FlowRadar、Reversible Sketch和Noisy Group Testing这三种可逆且支持合并的算法进行对比分析后，发现相对于前两种算法Noisy Group Testing更加符合本文的要求。于是在本文的剩余部分就对Noisy Group Testing进行了详细的研究和讨论。Noisy Group testing的sketch结构采取了分组的思想，将数据分成多个子组从而将关键的流随机、单独地分到不同的子组中，再利用流被分配的位置信息就可以恢复出子组中唯一个关键流的信息。此算法的误差主要来源于流分子组时所产生的哈希碰撞，也就是多个关键流被分到同一个子组的可能性。然而一味地追求误报率和漏报率的降低又会导致时间和空间代价的提高，所以需要操作人员设置参数来对算法精度和算法代价的限定做出平衡。

关键词：流量监测，可逆，group testing，理论评估，参数设定

ABSTRACT

With the rapid development of contemporary networks, the link rate and scale of network traffic have increased dramatically. This has brought about not only the convenience of real-time information exchange, but also makes it extremely difficult to effectively detect network anomalies and optimize the configuration of network resources. After research in recent years, it has found an effective method,sketch. However, this kind of data structure often loses the original information of the stream when it summarizes the information, which makes it very difficult to recover the information of the stream. Therefore, the research goal of this paper is to find a reversible traffic monitoring algorithm suitable for high-speed network environment, and under this premise, the flow of the algorithm is as simple as possible, and the smaller the time and space cost, the better. After comparing and analyzing the three reversible algorithms, FlowRadar, Reversible Sketch, and Noisy Group Testing, the last one is more in line with our requirements than the previous two algorithms. So in the rest of this article, a detailed study and discussion will be conducted on the Noisy Group Testing. The sketch structure of Noisy Group testing adopts the idea of grouping, divides the data into multiple subsets, and randomly and individually separates the key flows into different subsets. Then, the position information of the flow is used to recover the only key flow information. The error of this algorithm mainly comes from the hash collision generated hashing flows into subsets, which is the possibility of multiple key flows are divided into the same subset. However, blindly pursuing the decrease of false positive rate and false negative rate will lead to the increase of time and space cost. Therefore, operators need to set parameters to balance these two aspects.

KEY WORDS:flow monitoring, reversible, group testing, theoretical evaluation, parameter setting

目录

摘要 I

Abstract II

第一章 绪论 1

1.1 选题背景和意义 1

1.2 国内外研究现状 2

1.3 主要研究内容 3

第二章 相关算法 4

2.1 FlowRadar 4

2.1.1 算法简介 4

2.1.2 小结 5

2.2 Reversible Sketch 5

2.2.1 算法简介 5

2.2.2 小结 5

2.3 Noisy Group Testing 5

2.3.1 算法简介 5

2.3.2 小结 5

第三章 设计原理 7

3.1 相关工作 7

3.1.1 主机识别 7

3.1.2 基数估计 7

3.2 问题定义 8

3.3 算法核心 9

3.3.1 Noisy Group Testing 9

3.3.2 错误纠正代码 10

3.3.3 识别多个关键流的信息 10

第四章 算法设计 11

4.1 略图设计 11

4.2 更新过程 12

4.3 查询过程 13

4.3.1 阈值计算 13

4.3.2 基数测试 13

4.3.3 重获Super-spreader 14

4.3.4 降低误报率 15

4.3.5 小结 16

4.4 总结 16

第五章 理论评估 17

5.1 准确性 17

5.1.1 证明1 17

5.1.2 证明3 18

5.1.3 小结 18

5.2 空间复杂度 18

5.3 时间复杂度 18

5.3.1 单个路由器上的更新时间 18

5.3.2 算法可合并性和合并数据结构的时间消耗 19

5.3.3 查询过程所需要的运行时间 19

5.4 小结 19

第六章 实验评估 21

6.1 实验设计说明 21

6.2 评估标准 21

6.3 实验结果 22

6.3.1 改变测试数据参数 22

6.3.2 改变参数设定 23

6.3.3 改变错误过滤方法 24

总结 25

致谢 26

参考文献 27

绪论

选题背景和意义

随着当代网络的迅猛发展，网络速度和网络流量的规模达到了前所未有的规模。在如此高速的网络环境中，对于庞大的网络数据流量与有限的系统资源之间的矛盾，精准实时地检测和监管网络流量状况就显得尤为重要。

虽然数据中心网络运行中产生的海量流量数据使得完全实时地监测全部的数据流量变得异常困难，但是在大部分的网络报文处理系统中，我们往往会发现我们需要监测的流的某个特征服从幂律分布。有小部分的网络流，它们虽然总数不大，但是占据了总流量的相当一部分。当这项特征表现为流长时，这些流就会被称为heavy hitters或大象流；而当这项特征表现为流标识中的目标IP或是源IP时，这些IP所指的主机就会被称为super-spreader。无论是大象流的识别还是super-spreader检测都是网络流量监测的主要目标之一[5]。这就需要我们的流量检测算法不仅能够准确的估测流长，并且能够记录这些流的标识。

剩余内容已隐藏，请支付后下载全文，论文总字数：24479字