学位论文 > 优秀研究生学位论文题录展示

面向骨干网络流量统计的聚集计算研究

作　者: 梁峰
导　师: 刘任任；谭建龙
学　校: 湘潭大学
专　业: 计算机软件与理论
关键词: 数据流概要数据结构聚集 K-Bloom Filter
分类号: TP393.06
类　型: 硕士论文
年　份: 2009年
下　载: 43次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,随着互联网的发展,越来越多的新型应用对传统数据库技术提出了挑战。一个显著的改变就是数据以一个无限的值序列的方式源源不断地产生。数据流(data stream)的处理与实际应用密不可分,股票交易记录、网络流量、传感器网络中的数据、web日志等等。其中骨干网络流量统计是最为典型的例子之一,数据量非常庞大,而且持续速度也很惊人。2008年我国骨干网络上31个省的总流量大于12TB/S,而且这个速度在逐渐增大。于是对这些数据进行查询、分析的难度越来越大。因此在一个远小于数据规模的内存空间里不断更新一个代表数据集的概要数据结构(synopsis data structure)成为了研究的重点和难点。本文对数据流研究进行了相关工作的叙述,并在面向骨干网络流量统计这一应用背景下明确了研究方向,然后在现存的概要数据结构的基础上,提出了K-Bloom Filter结构,并从理论上对假阳性误判进行了分析,得出了两者具有相同的在误判率f 0下表示集合规模的上限n0 ,因此K-Bloom Filter的误判率是在可控范围之内的。我们提出了基于K-Bloom Filter的流统计算法,相比3.2.1节中的基于Bloom Filter的流统计算法,在相同的空间复杂度和时间复杂度的情况下,统计结果比起基于Bloom Filter的流统计算法的误差有了进一步的降低。最后,我们开发了一个基于Netflow流数据的网络流量监测分析系统,应用于骨干网络的在线实时分析。系统的核心部分采用了我们的数据流聚集计算算法。实际应用表明,我们的系统具有良好的实时性和准确性。

全文目录

摘要  4-5
ABSTRACT  5-8
第一章引言  8-15
  1.1 数据流模型  8-12
  1.2 研究问题的描述  12-13
  1.3 本文的研究内容和组织结构  13-15
    1.3.1 本文的研究内容  13
    1.3.2 本文的组织结构  13-15
第二章数据流研究概述  15-28
  2.1 数据流管理系统（DSMS）  15-18
    2.1.1 STREAM  15-16
    2.1.2 Aurora  16-17
    2.1.3 TelegraphCQ  17-18
  2.2 数据流模型的划分  18-21
    2.2.1 快照模型  19
    2.2.2 界标模型  19-20
    2.2.3 滑动窗口模型  20-21
  2.3 概要数据结构  21-23
  2.4 布鲁姆过滤器(Boom Filter)  23-28
    2.4.1 标准Bloom Filter 查询算法  24-25
    2.4.2 计数式Bloom Filter 查询算法  25-26
    2.4.3 压缩Bloom Filter 查询算法  26-28
第三章一种新的基于 K-Bloom Filter 的流统计算法  28-37
  3.1 引言  28-29
    3.1.1 应用背景  28
    3.1.2 问题描述  28-29
  3.2 基于数据流模型的聚集计算研究与实现  29-34
    3.2.1 基于Bloom Filter 结构的流统计算法  29-30
    3.2.2 基于K-Bloom Filter 结构的流统计算法  30-34
  3.3 实验结果与分析  34-36
  3.4 小结  36-37
第四章基于流数据的网络流量监测分析系统  37-48
  4.1 引言  37
  4.2 系统总体介绍  37-42
    4.2.1 系统的相关介绍  37-40
    4.2.2 系统总体框架设计  40-42
  4.3 精确的 SUM COUNT TOP-K 聚集计算  42-47
  4.4 小结  47-48
结论  48-49
参考文献  49-54
致谢  54-55
附录 A(攻读硕士学位期间参与的科研项目和研究成果)  55

面向骨干网络流量统计的聚集计算研究

内容摘要

全文目录

相似论文