树形网络中的副本更新策略及算法

来源：计算机工程与科学杂志2015年第3期北京时间：

作者：王旭，武继刚，侯睿

单位：1.天津工业大学计算机科学与软件学院，天津 300387;2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190

摘要：树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一。面对网络中数据访问需求的动态变化，好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本。针对此问题提出了两种贪心的动态副本更新策略，最大重用策略和请求覆盖策略。通过算法复杂度分析和仿真实验可以看出，所提出的两种算法的最坏时间复杂度为O(n log n)，远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5)，而网络运行及副本更新成本与最优解相差不超过11%。在极大地缩短了运算时间的同时，保持了尽可能低的网络运行及副本更新成本。

关键词：树形网络,副本放置,更新策略,

基金资助：国家自然科学基金资助项目(61173032);计算机体系结构国家重点实验室开放课题资助项目(CARCH201303）