面向服务质量的副本放置及更新算法

摘要

随着科学技术的进步和网络的发展，网络数据信息也随之快速增长。为了使地理上分布广泛的信息资源能够有效共享，人们提出了被广泛应用于网络中的副本技术。副本技术可以有效地降低数据访问时延，提高数据访问效率，并确保网络负载均衡和提高数据可用性以及可靠性。
　　副本技术主要涉及三个问题:1）何时创建副本，2）创建何种文件的副本，3)将副本置于何种位置，其中副本放置是副本技术中的核心问题。副本放置问题是指在网络中如何合理的放置副本以及如何使放置的副本数量最少。合理的高效副本放置不仅可以提高系统的可用性、可靠性，而且可以缩短用户数据访问时间，提高数据访问效率。
　　为了提高客户服务质量，降低网络运行成本，本文提出了一个副本放置算法:最远优先放置算法。实现分析表明，与现有算法相比，本文提出的算法在最大使用每个副本的处理能力同时，大大降低了网络运行成本。在不同距离限制下，都得到了客观的改进，其中对现有算法的改进可达68％。
　　面对网络中客户请求的动态变化，本文基于不同的副本放置策略，提出了三个副本放置和更新算法:1）最小放置更新算法，2）贪心放置算法，3）踏步搜索算法。在时间复杂度上，与已有的动态规划算法相比，算法执行时间加快了87.9％，同时整个网络的运行及更新成本不高于最优解的2.5％。在网络运行及更新成本上，与已有的启发式算法相比，在充分利用网络中每个副本最大处理能力同时，提高访问数据效率，降低访问时延。在不同的距离限制下，网络的运行成本得到了可观的降低，对原有算法的改进最高可达84.6％。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 研究现状

1．3 存在的问题和发展趋势

1．4 研究内容和研究目标

1．5 论文组织结构

第二章 问题描述

2．1 问题模型

2．1．1 概述

2．1．2 优化目标

2．2 现有算法

2．2．1 最近优先放置算法

2．2．2 动态规划算法

2．3 本章小结

第三章 副本放置策略及算法

3．1 启发式算法

3．1．1 最远优先放置算法

3．2 时间复杂度分析

3．3 本章小结

第四章 副本放置和更新策略及算法

4．1 贪心算法

4．1．1 贪心放置算法

4．2 tabu搜索算法

4．3 最小放置更新算法

4．4 时间复杂度分析

4．5 本章小结

第五章 实验

5．1 副本放置

5．2 副本更新

5．2．1 多访问策略下的副本更新

5．2．2 最近策略下的副本更新

5．3 本章小结

第六章 总结与展望

6．1 回顾与总结

6．2 未来工作展望

参考文献

研究生期间发表论文及参加科研情况说明

致谢