论文总字数：25806字

摘 要

随着互联网技术的不断发展，网络的性能在不断提高，用户人数和应用数也在急剧增长，同时网络行为也变得愈来愈复杂。在互联网日益普及的今天，人们对网络安全也提出了越来越高的要求，而网络流量测量，通过对网络中的报文进行存储，分析与统计，可以有效理解网络特性，研究网络行为，从而避免和排除网络中的安全隐患，为网络的管理和规划提供科学及依据，是网络安全中非常重要的组成部分。

在实际应用中，大部分情况下，掌握少数的大流信息就可以满足需要。所以，大流检测成为网络测量的研究热点之一。本文对两种常见的大流检测算法进行深入的了解与研究，然后比较两类算法的优缺点。

本文提出一种新的用于网络测量的框架SketchVisor，结合了counter-based和sketch-based两种大流检测算法的优点。然后把两类算法结合起来，实现SketchVisor混合算法：用sketch-based算法做主路径，用counter-based算法做快速路径。平时，数据包直接进入主路径，主路径记录大流信息；当网络出现突发流量导致报文缓冲溢出的时候（可在模拟环境中设置突发流量的比例），报文进入快路径。快路径可以在允许轻微的精度下降的同时提供高性能的本地测量最后通过采用压缩感知技术恢复快速路径中损失的小流信息并将其并入到主路径来得到准确的全网测量结果。

关键词：网络测量，大流检测，压缩感知，Sketch

Abstract

With the continuous development of the Internet technology, the performance of the network is constantly improving, and the number of users and the number of applications are both increasing rapidly. At the same time, the network behavior has become more and more complicated. As the popularity of the Internet increase, people’s requirement about network security are more and more serious. Network traffic measurement, through the storage, analysis and statistics of the messages in the network, can effectively understand the characteristics of the network and study the behavior of the network. Therefore, in order to avoid and eliminate the security risks in network and to provide scientific and scientific basis for network management and planning, network measurement is a very important part of network security.

In most cases, holding the information about heavy hitters(large flow) can satisfy our need enough. Therefore, large flow detection has become one of the research hotspots of network measurement. In this paper, two common large-flow detection algorithms are deeply understood and studied, and then the advantages and disadvantages of the two types of algorithms are also compared.

After studying, we find that existing sketch-based measurement solutions suffer from severe performance drops under high traffic load. Although sketches are efficiently designed, applying them in network measurement inevitably incurs heavy computational overhead. Therefore, we present SketchVisor, a robust network measurement framework for software packet processing, which combines the advantages of counter-based algorithm and sketch-based algorithm. It augments sketch-based measurement in the data plane with a fast path, which is activated under high traffic load to provide high-performance local measurement with slight accuracy degradations. It further recovers accurate network-wide measurement results via compressing sensing.

KEY WORDS: network measurement, Heavy hitter detection, compressive sensing, sketch

目录

摘要 I

Abstract II

第一章 绪论 2

1.1 研究背景 2

1.2 研究现状 2

1.3 本文研究内容 3

1.4 论文组织与结构 3

第二章 常见的大流检测算法 5

2.1 counter-based算法 5

2.1.1 Majority Algorithm（多数算法） 5

2.1.2 Frequent Algorithm 5

2.1.3 Space Saving 6

2.1.4 Misra-Gries algorithm 7

2.2 Sketch-based算法 8

2.2.1 Count Sketch算法 8

2.2.2 Count-Min Sketch算法 9

2.3 两种算法的比较 10

第三章 SketchVisor 11

3.1 SketchVisor综述 12

3.2 快速路径 13

3.2.1 核心 13

3.2.2 算法实现 13

3.3 全网恢复 16

3.3.1 核心 16

3.3.2 问题描述 16

3.3.3 压缩感知 17

第四章 实验结果及分析 20

4.1 实验环境 20

4.2 两种类型大流检测算法比较 20

4.2.1 输入数据 20

4.2.2 counter-based算法运行结果分析 20

4.2.3 sketch-based算法运行结果 21

4.2.4 两种算法比较 23

4.3 SketchVisor分析 24

第五章 总结与展望 27

5.1 论文工作总结 27

5.2 后续工作展望 27

参考文献 30

绪论

研究背景

随着互联网技术的不断发展，网络的性能在不断提高，用户人数和应用数也在急剧增长，同时网络行为也变得愈来愈复杂。在互联网日益普及的今天，人们对网络安全也提出了越来越高的要求，而网络流量测量，通过对网络中的报文进行存储，分析与统计，可以有效理解网络特性，研究网络行为，从而避免和排除网络中的安全隐患，为网络的管理和规划提供科学及依据，是网络安全中非常重要的组成部分。

随着网络规模的不断扩大和链路速率的迅速提高，数据分组到达的频率越来越高[1]，网络流量测量硬件的处理速度难以满足需要。这种情况下，传统的全流量测量方法并不适用[2]。所以，如何在有限的硬件资源条件下，完成高速链路下的流量测量成为当前亟待解决的问题。

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