互联网测量系统可扩展性问题及其关键算法研究

论文摘要

近年来，互联网测量已经成为研究和管理互联网的基础。由于互联网的异质性和高速化特点，目前的网络测量系统在不同程度上缺乏可扩展性，不能适应当前及未来的测量需求。本文重点研究端到端单向时延测量、高速网络中流量测量、网络安全测量中超连接主机检测等方面中的可扩展性问题及其关键算法，以提高网络测量系统的性能。论文的工作主要包括以下几个方面： (1) 互联网测量中端系统时钟的时钟频差和时钟重置会给单向时延测量引入严重的误差，针对此问题，本文提出了一个基于模糊聚类分析的算法来检测并消除这些误差。大量实验表明：与同类算法相比，该算法有更好的准确性和鲁棒性。而且此算法时间复杂度为O(N)。 (2) 目前通用的流量测量解决方案NetFlow在互联网流量迅猛增长的条件下存在可扩展性问题，针对NetFlow中抽样方法的不足，本文提出了一种基于测量缓存区的时间分层分组抽样方法。通过理论分析，证明了抽样估计的无偏性，并推导出估计值相对标准差的理论上界。实验结果表明：该方法在保证测量准确性的同时具有简单性、自适应性及资源可控性等优点。 (3) 为适应高速网络中流量测量的准确性需求，提出了一种基于LRU大流检测算法。它引入了“小流早期丢弃”和“大流预保护”机制以提高准确性。实验结果显示：与已有算法相比，新算法具有更高的测量准确性和实用性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 章节目录
• 图目录
• 表目录
• 第一章 绪论
• 1.1 引言
• 1.2 本文主要贡献
• 1.3 本论文的结构和安排
• 1.4 本章参考文献
• 第二章 单向时延测量中消除时钟频差和时钟重置的模糊数学算法
• 2.1 引言
• 2.2 相关工作和我们的创新
• 2.3 基于模糊数学的时钟跳变检测和消除算法
• 2.3.1 模糊聚类分析基本方法
• 2.3.2 频差估计和初步纠斜
• 2.3.3 去噪声
• 2.3.4 确定时钟重置的次数和重置时刻
• 2.3.5 获得最优频差
• 2.4 实验与分析
• 2.4.1 准确性
• 2.4.2 鲁棒性（robustness）
• 2.4.3 算法时间复杂度
• 2.5 本章小结
• 2.6 本章参考文献
• 第三章 流测量中基于测量缓存区的时间分层分组抽样方法
• 3.1 引言
• 3.1.1 NetFlow简介
• 3.1.2 NetFlow现存不足及改进目标
• 3.2 相关工作
• 3.3 基于测量缓存区的时间分层分组抽样
• 3.3.1 基本思想
• 3.3.2 抽样及估值
• 3.3.3 理论分析
• 3.4 实验验证
• 3.4.1 理论结论验证
• 3.4.2 方法比较
• 3.5 本章小结
• 3.6 本章参考文献
• 第四章 基于LRU的大流检测算法
• 4.1 引言
• 4.2 相关工作
• 4.3 基于LRU的大流检测算法
• 4.3.1 简单算法及其缺点
• 4.3.2 基于LRU的大流检测算法设计
• 4.3.3 算法分析及实现考虑
• 4.4 实验
• 4.4.1 评价指标
• 4.4.2 实验评价及比较结果
• 4.5 本章小结
• 4.6 本章参考文献
• 第五章 高速网络超连接主机检测中的流抽样算法
• 5.1 引言
• 5.2 背景及相关工作
• 5.2.1 背景
• 5.2.2 相关工作
• 5.3 基于哈希流抽样算法及其缺陷
• 5.3.1 基于哈希流抽样（hash-based flow sampling）
• 5.3.2 哈希函数的需求及其选择
• 5.3.3 卡方检验及算法缺陷
• 5.4 基于BLOOM FILTER流抽样算法
• 5.4.1 Bloom filter简介
• 5.4.2 算法描述
• 5.4.3 哈希函数的选择
• 5.4.4 算法分析及实现考虑
• 5.5 实验
• 5.5.1 评价指标
• 5.5.2 “准确性”评价
• 5.5.3 “及时性”评价
• 5.6 本章小结
• 5.7 本章参考文献
• 结束语
• 略缩词
• 致谢
• 个人简历及参加的科研工作
• 附录：在攻博期间的论文及专利