离线下载缓存替换算法

发布时间：2017-10-15 01:12

  本文关键词：离线下载缓存替换算法

  更多相关文章： 离线下载 缓存替换算法 预约

【摘要】：数据下载是人们获取信息的一种重要方式；近年来新兴的离线下载业务吸引了大量用户。与传统下载应用不同,在离线下载系统中,用户先向系统提交文件下载请求；然后,离线下载的服务器代替用户从网络中下载文件并存储在离线下载系统的缓存中；最后,用户再从缓存云中下载文件。这种设计,可以节省终端用户的时间和资源,给用户带来更好的下载体验。 离线下载系统的核心部件是缓存服务器,缓存算法是决定缓存服务器性能的关键。现有系统一般采用传统的算法,如LRU、LFU,这些算法并没有考虑离线下载业务的特殊性；随着离线下载日益普及和文件数量增长,缓存和带宽资源都面临压力。因此,需要寻找高效的缓存方法,充分利用有限的缓存空间,保障系统服务质量。 离线下载系统中,用户的请求时间和下载时间不同,二者往往存在时间间隔。我们称这个间隔为预约时间。预约时间为我们提供了设计新的缓存算法的空间。由于下载是预约的,因此在每次缓存调度发生时,我们能够获知未来一段时间,还有哪些下载任务有待完成。因此,可以将预约信息用于缓存设计,以提高缓存效率。 本文的主要工作是,针对离线下载的业务特征,寻找高效的缓存算法,减轻缓存的存储压力和带宽开销,提高系统性能。具体来说,本文的主要工作和贡献如下： (1)针对离线下载业务特征,提出了基于预约信息的缓存设计思想。该思想充分利用可用的预约信息和访问历史信息,提高字节命中率。在此基础上,提出了两种新的缓存算法,一种是基于文件预约信息和访问历史信息中的访问频率,一种是基于文件预约信息和访问历史信息中的访问时间间隔。分析了算法参数的设计依据并权衡了可能的取值范围。 (2)基于真实的离线下载业务数据,进行了不同缓存算法的比较和评估。结果显示,相比传统算法,本文提出的两种缓存替换算法都可以提高字节命中率。尤其在缓存较小的时候,效果更明显,字节命中率最高可以提高7.78%。 (3)最后,本文从理论上分析LRU算法的性能,建立了基于马尔科夫链的数学模型。模型可以计算每个文件的命中率。模型的特色在于把单个文件在缓存中的位置定义为状态,最大限度的减少状态的数量,减少运算复杂度。
【关键词】：离线下载 缓存替换算法 预约
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP333
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-9
• 目录9-11
• 1 序言11-16
• 1.1 引言11
• 1.2 研究背景和意义11-12
• 1.3 国内外研究现状12-14
• 1.3.1 离线下载系统的研究现状12-13
• 1.3.2 缓存替换算法的研究现状13-14
• 1.4 研究内容14-15
• 1.5 文章组织架构15-16
• 2 相关研究16-28
• 2.1 系统架构与工作原理16-18
• 2.1.1 离线下载系统架构16-17
• 2.1.2 离线下载工作原理17-18
• 2.2 现有缓存替换算法18-26
• 2.2.1 基于频率的缓存替换算法19-20
• 2.2.2 基于访问时间间隔的缓存算法20-21
• 2.2.3 基于对象大小的缓存替换算法21
• 2.2.4 基于成本价值的缓存替换算法21-23
• 2.2.5 基于预测的缓存替换算法23-25
• 2.2.6 最优缓存替换算法25-26
• 2.3 现有缓存算法分析26-27
• 2.4 本章小结27-28
• 3 离线下载缓存替换算法28-42
• 3.1 离线下载缓存算法基本思想28-32
• 3.1.1 算法基本思想28-31
• 3.1.2 应用场景分析31-32
• 3.2 离线下载缓存算法设计32-41
• 3.2.1 概念和术语32-35
• 3.2.2 基于前向时间窗口和访问频率的算法35-39
• 3.2.3 基于预约序列访问时间间隔的算法39-41
• 3.3 本章小结41-42
• 4 离线下载缓存替换算法有效性验证42-56
• 4.1 LRU算法理论分析42-45
• 4.1.1 建立模型42-44
• 4.1.2 性能评估44-45
• 4.2 数据提取与算法仿真45-54
• 4.2.1 数据集提取与分析45-48
• 4.2.2 仿真环境及仿真参数48-49
• 4.2.3 算法仿真及分析49-54
• 4.3 本章小结54-56
• 5 结论56-57
• 5.1 本文总结56
• 5.2 工作展望56-57
• 参考文献57-60
• 作者简历及攻读硕士学位期间取得的研究成果60-62
• 学位论文数据集6

【参考文献】

中国期刊全文数据库 前10条

1 许斌;;基于云存储的离线下载系统[J];电脑知识与技术;2013年03期

2 马卫民,王刊良;局内管理决策问题及其竞争策略[J];管理科学学报;2003年02期

3 谢应科;王建东;祝超;赵自力;韩承德;;网络测量中高精度时间戳研究与实现[J];计算机研究与发展;2010年12期

4 王世克;吴集;金士尧;;Web缓存技术概述[J];计算机与信息技术;2005年06期

5 石磊;叶海琴;卫琳;连卫民;;Web缓存命中率与字节命中率关系[J];计算机工程;2007年13期

6 石磊;孟彩霞;韩英杰;;基于预测的Web缓存替换策略[J];计算机应用;2007年08期

7 闫永权;张大方;;基于频繁的Markov链预测模型[J];计算机应用研究;2007年03期

8 林永旺,张大江,钱华林;Web缓存的一种新的替换算法[J];软件学报;2001年11期

9 韩向春;田玉根;;基于预测的Web缓存替换算法[J];计算机工程与设计;2010年01期

10 贺琛,陈肇雄,黄河燕;Web缓存技术综述[J];小型微型计算机系统;2004年05期

中国博士学位论文全文数据库 前1条

1 赵英杰;网络存储服务器缓存替换策略研究[D];国防科学技术大学;2010年

，

本文编号：1034219