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

Strategy and algorithms for replica update in tree networks

作　　者：王旭[1,2] 武继刚[1,2] 侯睿[1,2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190

出　　处：《计算机工程与科学》2015年第3期440-445,共6页Computer Engineering & Science

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

摘　　要：树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一。面对网络中数据访问需求的动态变化,好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本。针对此问题提出了两种贪心的动态副本更新策略,最大重用策略和请求覆盖策略。通过算法复杂度分析和仿真实验可以看出,所提出的两种算法的最坏时间复杂度为O(nlog n),远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5),而网络运行及副本更新成本与最优解相差不超过11%。在极大地缩短了运算时间的同时,保持了尽可能低的网络运行及副本更新成本。The problem of replica placement and update in tree networks plays an important role in network communications.When the data access requirements change over time,the replica placement and update strategy should make sure the quality of service and reduce the cost of network operating and replica update.We propose two greedy update strategies named MAX_REUSE strategy and REQUEST_COVER strategy to solve the update problem.Time complexity analysis and simulation show that the complexity of the proposed algorithms is just O（nlog n）in worst case,while the optimal solution obtained by dynamic programming is O（n^5）.The cost of network operating and replica update in two algorithms is no more than 11% compared to the optimal solution.The proposed strategies not only reduce the time complexity but also keep a low total cost.

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

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]