计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2015年
3期
440-445
,共6页
树形网络%副本放置%更新策略
樹形網絡%副本放置%更新策略
수형망락%부본방치%경신책략
tree network%replica placement%update strategy
树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一.面对网络中数据访问需求的动态变化,好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本.针对此问题提出了两种贪心的动态副本更新策略,最大重用策略和请求覆盖策略.通过算法复杂度分析和仿真实验可以看出,所提出的两种算法的最坏时间复杂度为O(n logn),远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5),而网络运行及副本更新成本与最优解相差不超过11％.在极大地缩短了运算时间的同时,保持了尽可能低的网络运行及副本更新成本.
樹形網絡中的副本放置和更新是網絡通訊中值得研究的重要問題之一.麵對網絡中數據訪問需求的動態變化,好的副本放置和更新策略可以在保證服務質量的前提下有效減少網絡運行及副本更新成本.針對此問題提齣瞭兩種貪心的動態副本更新策略,最大重用策略和請求覆蓋策略.通過算法複雜度分析和倣真實驗可以看齣,所提齣的兩種算法的最壞時間複雜度為O(n logn),遠低于現有的使用動態規劃求最優解的最壞時間複雜度O(n5),而網絡運行及副本更新成本與最優解相差不超過11％.在極大地縮短瞭運算時間的同時,保持瞭儘可能低的網絡運行及副本更新成本.
수형망락중적부본방치화경신시망락통신중치득연구적중요문제지일.면대망락중수거방문수구적동태변화,호적부본방치화경신책략가이재보증복무질량적전제하유효감소망락운행급부본경신성본.침대차문제제출료량충탐심적동태부본경신책략,최대중용책략화청구복개책략.통과산법복잡도분석화방진실험가이간출,소제출적량충산법적최배시간복잡도위O(n logn),원저우현유적사용동태규화구최우해적최배시간복잡도O(n5),이망락운행급부본경신성본여최우해상차불초과11％.재겁대지축단료운산시간적동시,보지료진가능저적망락운행급부본경신성본.
