基于R/S分析的数据流缓冲队列控制算法的研究与实现

论文摘要

随着网络技术和计算机技术的迅速发展,数据越来越多地以流(streaming)的形式出现。由于数据流具有突发、潜在无限等特性,在某个瞬间,流速可能会突然急剧加大从而导致短时间内内存溢出,以至于不能继续正常的查询处理。因此,如能根据单位时间内流入、流出内存数据量以及内存最大容量提前预测流数据是否过载,从而决定如何执行缓冲队列管理,以便保证内存始终不会溢出具有重要意义。本文将数据流到达时的流速看成是一个关于数据流流速的时间序列。由于分形理论为时间序列分析提供了一个新的途径,通过对时间序列所具有的分形行为进行研究,可以从一个崭新的角度分析、预测时间序列的特征和规律,因此,本文首先利用分形理论中的R/S分析方法,根据Hurst值的大小(0＜H＜1),定性判断数据流流速变化趋势。其次,根据预测的数据流流速变化趋势,提出了两种控制内存缓冲队列长度算法,即定长△算法和自适应算法,其中△代表每个周期缓冲队列长度的基础变化量。根据是参照初始队列长度还是预测长度进行队列长度的计算,定长△算法又进一步分为△_Linit算法和△_Lcur算法。定长△算法的基本思想是,根据当前周期内的缓冲队列长度的实际变化量和基础变化量△求得下一个周期内队列长度的变化量。而自适应算法则完全根据当前周期内的缓冲队列长度的实际变化量确定下一个周期内队列长度的变化量。当预测量不足时,本文采用随机卸载策略进行卸载。最后,经实验测试和分析得知：1)Hurst值可以准确地预测数据流流速变化趋势；2)自适应算法与定长△算法相比,其预测队列长度更接近实际长度且滞后程度较轻；3)当预测队列长度不满足实际队列长度时,定长△算法的卸载量要少于自适应算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 背景
• 1.2 相关工作
• 1.2.1 数据流与传统数据库的比较
• 1.2.2 现有数据流系统
• 1.2.3 时间序列分析
• 1.2.4 缓冲队列管理
• 1.2.5 数据流调度技术
• 1.2.6 数据流卸载技术
• 1.3 论文组织结构
• 第2章 系统架构
• 2.1 系统架构
• 2.2 R/S分析流速趋势预测模块
• 2.3 缓冲队列控制模块
• 2.4 调度模块
• 2.5 卸载模块
• 2.6 小结
• 第3章 基于R/S分析的流速趋势预测
• 3.1 引言
• 3.1.1 分形理论的产生与发展
• 3.1.2 分形的定义
• 3.1.3 分形的性质
• 3.1.4 R/S分析理论
• 3.2 基于R/S分析的流速趋势预测
• 3.3 性能测试与评价
• 3.4 小结
• 第4章 缓冲队列控制
• 4.1 队列缓冲池
• 4.2 定长Δ算法
• L_init算法'>4.2.1 定长Δ_Linit算法
• L_cur算法'>4.2.2 定长Δ_Lcur算法
• 4.3 自适应算法
• 4.4 性能测试与评价
• 4.5 小结
• 第5章 结束语
• 参考文献
• 致谢
• 攻读硕士期间发表的论文和参加的项目