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

王 旭，武继刚，侯 睿

(1.天津工业大学计算机科学与软件学院，天津 300387;

2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190)

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

王 旭，武继刚，侯 睿

(1.天津工业大学计算机科学与软件学院，天津 300387;

2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190)

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

树形网络；副本放置；更新策略

1 引言

网络中的副本放置问题广泛应用于视频点播(VOD)、互联网服务的提供(ISP)、内容分发系统(CDS)等重要领域[1～7]。在树形网络中，叶节点会周期性地发送数据访问请求，该请求会被含有相应数据副本的祖先节点满足。为了降低访问延迟，提高数据的可用性，一般将同一数据的多份副本部署在网络中[8～10]。副本放置问题的目标是在网络中选择一些节点放置副本，以最少的副本数量满足所有的数据访问请求。

为解决网络中的副本放置问题，提出了许多副本放置算法[11～18]。文献[15]证明了在一般网络中的副本放置问题是NP完全的。文献[16]将一般网络中的副本放置问题转换成经典的装箱问题，并给出了多项式时间的近似算法。为了提高网络的服务质量(QoS)，文献[17]在选择节点放置副本时，额外考虑了副本和叶节点间的通信距离，证明了新问题在一般情况下是NP 难的，并给出了二叉树形网络中的最优解和任意网络中的求解该问题的近似算法。文献[18]对请求的最长响应时间加以限制，提出了伪多项式和多项式时间的近似算法。文献[19]将副本放置算法应用在混合的内容分发网络和对等网络中，并通过实验证明了该网络中的副本放置代价小于内容分发网络中的副本放置代价。为了提高数据的可扩展性和稳定性，文献[20]提出了针对相关数据的分布式副本放置算法。文献[21]对已存在的一些副本放置和选择策略做出了较为全面的介绍和分析。

在树形网络中，之前的研究大多采用最近原则，即任一节点的所有请求均由距离该节点最近的且含有对应副本的祖先节点满足。本文所研究的问题基于同样的原则。另外，大部分相关文献假设最初的网络中不存在任何副本。对于这种假设，在满足所有客户请求的前提下，放置的副本越少，则整个网络花费的代价越低。但是，在实际问题中，客户发送的数据访问请求数目会动态变化，这时重用旧副本的成本通常小于添加新副本的成本。因此，当在网络中的数据需求动态变化后，为了有效降低副本更新成本，同时令整个网络保持较低的运行成本，要平衡重用旧副本和添加新副本之间的关系。对于树形动态网络中的副本更新问题，目前只有文献[22]提出了一种用动态规划求最优解的方法，然而该方法的最坏时间复杂度高达O(n5)，其中n为树形网络中的内部节点数。而本文提出的两种更新算法不仅会大大缩短问题求解时间，而且不会过多增加网络运行及副本更新成本。

2 问题描述与前期工作

给定一个树形网络，将其节点分成两部分，可以发送数据访问请求的叶节点集合C和含有n个内部节点的集合N。客户i∈C在每个单位时间内发送ri个请求。E表示已存在的服务器，即含有副本的内部节点集合，从而E⊆N，集合E中的每一个副本在网络中的数据访问请求发生变化后或被重用，或被删除。N-E表示由不含有副本的内部节点构成的集合，在更新的过程中，可以在集合N-E中选择节点添加新副本，使其成为服务器。需要说明，如果算法在叶节点放置副本，则将该节点切分成一个叶节点和一个内部节点，因此副本只可能放在内部节点。本文研究的问题是找到一个新的服务器集合R⊆N，使所有的数据访问请求都能够由集合R中的服务器满足，即对于每一个客户i，都有唯一的服务器serveri∈R满足其所有请求数ri。在本文中，假设所有服务器的性能都是相同的，其最大处理能力为W，若内部节点j∈R，则其需要处理的请求数reqj为:

∀j∈R,reqj=∑i∈C|j=serveriri≤W

(1)

此外，根据E、R的定义可知，|E|为已存在的副本数，|R|为解决副本更新问题所需的副本数，|R∩E|为重用的旧副本数。由于所有服务器的性能都是相同的，本文将运行一个服务器的成本归一化为1。当放置一个新副本时，需要花费额外代价create，因此运行一个新副本的代价为1+create，重复使用旧副本可看做直接运行服务器，代价为1。删除未使用的旧副本的代价为delete，则整个网络的运行及副本更新成本为:

cost(R)= |R|+(|R|-|R∩E|)·

create+(|E|-|R∩E|)·delete

(2)

副本更新问题的目标是找出一个新的服务器集合R，在不超过每个服务器的最大处理能力W且为所有客户的请求提供服务的前提下，使cost(R)最小。

在文献[22]提出的动态规划算法中，对每个节点j∈N构造大小为(E+1)×(N-E+1)的表，该表表示以节点j为根节点(不包含节点j)时，其子树中可能存在的重用旧副本和添加新副本的数目情况。动态规划算法自底向上更新每个节点的表中的信息，该算法依次合并该节点的各个孩子节点，当合并第k个孩子节点时，节点j中的表已经包含了前k-1个孩子节点的副本放置情况。若合并第k个孩子节点时，节点j的子树中未得到服务的数据访问请求数小于合并前未得到服务的数据访问请求数，则更新节点j的表中的信息。当执行到根节点时，算法结束并得到最终解。

3 副本更新的策略及算法

在本文提出的算法中，childrenj表示节点j的所有孩子节点集合，subtreej表示以节点j为根的子树，Sj是subtreej中未被满足的请求之和，则:

Sj=∑j′∈childrenj∩Crj′+∑j′∈childrenj∩NSj′

(3)

主体算法main(j)在树形网络中递归地自底向上对每一个节点j计算Sj，直至根节点root。若Sj>W，为j构造包含其所有子节点的有序表listj，调用本文提出的两种新策略放置副本，使Sj≤W。否则，未被满足的数据访问请求可从节点j或j的祖先节点中的副本获得服务，继续计算，直至根节点。由于问题要求满足所有的数据访问请求，所以在根节点root，必有Sroot=0，若Sroot≠0，则在根节点放置副本。伪代码请参考算法1。

算法1 主体算法

Input:root;

Output:Replica SetR。

1:Proceduremain(j∈N)

2:Sj=0;

3:forj′∈childrenj∩Cdo

4:Sj=Sj+rj′;

5:end for

6:forj′∈childrenj∩Ndo

7:main(j′);

8:Sj=Sj+Sj′;

9:end for

10:ifSj≤Wthen

11: ifj=rootandSj≠ 0 then

12:R=R∪{j};/*若j是根节点且其子树中含有未得到服务的数据访问请求，则节点j一定放置副本。若j含有副本，则重复使用，否则添加新副本*/

13: end if

14:else

15: 构造有序表listj, 按照Sj′的值从小到大排列;

16:MAX_REUSE(j,listj,R) orREQUEST_COVER(j,listj,R);/*调用本文提出的两种贪心策略*/

17:end if

18:returnR;

19:end Procedure

3.1 最大重用策略及算法

考虑到重用旧副本的成本低于添加新副本的成本，为使Sj≤W，最大重用策略优先选择保留subtreej中的旧副本。如果保留全部旧副本仍然不能使Sj足够小，则在subtreej中添加部分新副本。另外，在前文中已经提到，为降低网络运行成本，网络中的副本总数越少越好。为了用尽可能少的副本就可以令Sj足够小，算法在保留旧副本或添加新副本时，均优先选择subtreej中Sj′较大的子节点j′。最大重用策略的伪代码请参考算法2。

算法2 最大重用算法

Input:j;

Output:Subset ofR。

1:ProcedureMAX_REUSE(j,listj,R)

2: repeat

3: 在listj中选择Sj′最大且含有副本的节点j′;

4:Sj=Sj-Sj′;Sj′= 0;R=R∪{j′};/*重用节点j′中的副本，并更新通过该节点的请求数为0*/

5: untilSj≤Wor 没有满足条件的节点j′

6: ifSj>Wthen/*重用所有旧副本后，仍无法使Sj足够小*/

7: repeat

8: 在listj中选择Sj′最大且不含副本的节点j′;

9:Sj=Sj-Sj′;Sj′= 0;R=R∪{j′};/*在节点j′添加新副本，并更新通过该节点的请求数为0*/

10: untilSj≤W

11:end if

12:ifj=rootandSj≠ 0 then

13:R=R∪{j};

14:end if

15:returnR;

16:end Procedure

3.2 请求覆盖策略及算法

不同于最大重用策略，请求覆盖策略要求subtreej中的所有请求必须在子树内被满足，即Sj=0。首先在节点j添加新副本或重用旧副本，为使j提供的服务覆盖subtreej中尽可能多的客户，j贪心地选择请求数小的子节点提供服务。与最大重用策略相同的是，为了多重用旧副本，少添加新副本，j优先为不含副本的节点提供服务。当j不能覆盖更多子节点，即无法为更多的客户提供服务时，其余子节点或重用旧副本，或添加新副本。请求覆盖策略的伪代码请参考算法3。

算法3 贪心覆盖算法

Input:j;

Output:Subset ofR。

1:ProcedureREQUEST_COVER(j,listj,R)

2:R=R∪{j};Sj=0;/*节点j一定放置副本*/

3:T=0;/*令T记录该子树根节点可能服务的请求数量，初始值为0，即不为任何子节点中的请求提供服务 */

4: repeat

5: 在listj中选择Sj′最小且不含副本的节点j′;

6:T=T+Sj′;/*节点j′中的副本为请求Sj′提供服务*/

7：untilT>Wor 没有满足条件的节点j′

8: ifT

9: repeat

10: 在listj中选择Sj′最小且含有副本的节点j′;

11:T=T+Sj′;

12: untilT>W

13: end if

14:在未得到服务的节点及跳出循环的节点j′处重用旧副本或添加新副本，并更新集合R中的副本及通过相应节点的请求数为0；

15:returnR;

16:end Procedure

3.3 时间复杂度

对于含有n个内部节点的树形结构，使用最大重用策略和请求覆盖策略更新副本时，在最坏情况下，节点j含有n- 1个子节点，计算Sj的时间复杂度为O(n)，构造表listj的时间复杂度为O(nlogn)，至多花费O(n)决定其孩子节点的副本放置情况。因此，两种算法在最坏情况下的时间复杂度为O(nlogn)。

4 实验

当内部节点数分别为n=100，200，300，400，500时，对每个n值分别构造20个不同的树形结构，并随机放置|E|=n/4个副本。在每个树形结构中，内部节点含有6～9个孩子节点，叶节点发送1～6个数据访问请求，服务器能够提供的数据访问请求上限W= 10。对同一个树形结构，分别用最大重用算法、请求覆盖算法，与文献[22]中的动态规划算法求出的最优解比较。对每个节点数n在不同的分布树上运行20 次实验，计算其新添加的副本和重用的副本数目的平均值，如图1和图2所示。

Figure 1 Numbers of added copies of the three algorithms

Figure 2 Numbers of reused copies of the three algorithms

从图1可以看出，对不同节点数n，本文提出的两种算法新添加的副本数几乎相同，均不超过动态规划算法得到的最优解中新添加的副本数；而图2则表明，与最优解相比，本文提出的两种贪心算法重用的旧副本数较多，因此不会增加整个网络的更新成本。

与文献[22]相同，在本文的实验中，取create=0.1，delete=0.01，按照第2节中的公式(2)计算三种算法的网络运行及副本更新成本cost(R)，结果如图3所示。

Figure 3 Total cost of the three algorithms

从图3可以看出，最大重用策略和请求覆盖策略花费的网络运行及副本更新成本与解决该问题所需最小代价值相近。为了更直观地比较三种算法得到的可行解的总体代价，根据公式(4)计算本文提出的两种算法相对于动态规划得到的最优解的额外代价比。

(4)

其中，opt代表最优解，m代表最大重用策略或请求覆盖策略得到的可行解。对上文给定的任意内部节点数n，计算结果如图4所示。从图4中可以看出，最大重用策略和请求覆盖策略得到的可行解的额外代价不会超过最优解的11%和10%。因此，本文提出的两种贪心策略得到的近似解与最优解相差不大，能够保持较低的网络运行及副本更新成本。

Figure 4 Percentage of additional cost of the three algorithms

三种算法的运行时间如表1所示，单位为s。对不同节点数n，最大重用策略和请求覆盖策略均可在0.01s内得到可行解，而动态规划算法在节点数增加到500时，执行时间高达2 151.19s。可以看出，本文提出的两种更新算法在运行时间上具有明显优势。

Table 1 Running time of the three algorithms

为了研究已存在副本的数量对本文提出的两种策略得到的可行解的影响，构造100个随机树，使其内部节点数n均为100，并在每个树中随机放置0 ≤E≤100个副本。根据公式(4)计算两种策略得到的可行解的额外代价比，如图5所示。从图5可以看出，当网络中已存在的副本数很少或很多时，本文提出的两种贪心策略得到的可行解与最优解十分相近。

Figure 5 Influence of pre-existing copy

5 结束语

树形网络广泛存在于计算机网络的各个领域，数据的共享访问是其亟待解决的一个重要问题。在实际网络中，数据访问请求是实时动态变化的，从降低网络运行成本和确保客户的数据访问请求能够及时得到数据服务的角度出发，快速副本更新策略的提出刻不容缓。因此，本文针对树形网络中的副本更新问题，提出了两种贪心的更新策略：最大重用策略和请求覆盖策略，两种策略都是在内部节点j无法单独满足所有以其为根的子树中的数据请求时被调用。由于网络中本身存在一定数量的副本，两种策略均优先选择重用已有副本。所不同的是，在最大重用策略中，选择在尽可能接近树根的位置放置副本，而请求覆盖策略则正相反。通过算法复杂度分析可知，两种算法的最坏时间复杂度均不超过O(nlogn)，相比于求最优解，大大缩短了算法的运行时间。通过仿真实验的比较，新算法在副本更新时的总体代价与最优解相近。

除了缩短副本更新时间，减少副本更新代价，为了提高服务质量，网络中的副本放置问题还有许多其他目标，如通信代价最小、功率消耗最小等，这将是我们未来工作的主要方向。同时，也将考虑其他网络模型上副本放置和更新的问题。

[1] Kalpakis K, Dasgupta K, Wolfson O. Optimal placement of replicas in trees with read, write, and storage costs[J]. IEEE Transactions on Parallel and Distributed Systems, 2001,12(6):628-637.

[2] Lin Y F,Liu P,Wu J J.Optimal placement of replicas in data grid environments with locality assurance[C]∥Proc of the 12th International Conference on Parallel and Distributed Systems, 2006:1-8.

[3] Wu J J,Lin Y F,Liu P.Optimal replica placement in hierarchical data grids with locality assurance[J]. Journal of Parallel and Distributed Computing, 2008, 68(12):1517-1538.

[4] Benoit A,Rehn-Sonigo V,Robert Y.Replica placement and access policies in tree networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(12):1614-1627.

[5] Chen Y,Katz R H, Kubiatowicz J D.Dynamic replica placement for scalable content delivery[M]∥Peer-to-Peer Systems, Berlin:Springer, 2002:306-318.

[6] Wauters T,Coppens J,De Turck F,et al. Replica placement in ring based content delivery networks[J]. Computer Communications, 2006, 29(16):3313-3326.

[7] On G,Schmitt J,Steinmetz R.Quality of availability:Replica placement for widely distributed systems[C]∥Proc of IWQoS’03, 2003:325-342.

[8] Jia X, Li D, Hu X, et al. Placement of read-write Web proxies on the Internet[C]∥Proc of the 21st International Conference on Distributed Computing Systems,2001:687-690.

[9] Xu J, Li B, Lee D L. Placement problems for transparent data replication proxy services[J]. IEEE Journal on Selected Areas in Communications, 2002, 20(7):1383-1398.

[10] Douceur J R, Wattenhofer R P. Competitive hill-climbing strategies for replica placement in a distributed file system[M]∥Distributed Computing, Berlin:Springer, 2001:48-62.

[11] Szymaniak M, Pierre G, Van Steen M. Latency-driven replica placement[C]∥Proc of the 2005 Symposium on Applications and the Internet, 2005:399-405.

[12] Rahman R M, Barker K, Alhajj R. Replica placement design with static optimality and dynamic maintainability[C]∥Proc of the 6th IEEE International Symposium on Cluster Computing and the Grid, 2006, 1:4-437.

[13] Yang M, Fei Z. A model for replica placement in content distribution networks for multimedia applications[C]∥Proc of IEEE International Conference on Communications, 2003:557-561.

[14] Zaman S, Grosu D. A distributed algorithm for the replica placement problem[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9):1455-1468.

[15] Tang X, Xu J. QoS-aware replica placement for content distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(10):921-932.

[16] Beaumont O, Bonichon N, Larchevêque H. Modeling and practical evaluation of a service location problem in large scale networks[C]∥Proc of 2011 International Conference on Parallel Processing (ICPP), 2011:482-491.

[17] Benoit A, Larchevêque H, Renaud-Goud P. Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks[C]∥Proc of 2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS), 2012:1022-1033.

[18] Rodolakis G, Siachalou S, Georgiadis L. Replicated server placement with QoS constraints[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(10):1151-1162.

[19] Khalaji F K, Analoui M. Hybrid CDN-P2P architecture:Replica content placement algorithms[C]∥Proc of the 5th Conference on Information and Knowledge Technology(IKT), 2013:7-12.

[20] Tu M H, Yen I L. Distributed replica placement algorithms for correlated data[J]. The Journal of Supercomputing, 2014,68(1):245-273.

[21] Kingsy Grace R, Manimegalai R. Dynamic replica placement and selection strategies in data grids—A comprehensive survey[J]. Journal of Parallel and Distributed Computing, 2014, 74(2):2099-2108.

[22] Benoit A, Renaud-Goud P, Robert Y. Power-aware replica placement and update strategies in tree networks[C]∥Proc of IEEE International Parallel & Distributed Processing Symposium (IPDPS),2011:2-13.

WANG Xu,born in 1989,MS candidate,her research interests include high performance computing, and data center.

武继刚(1963-),男，江苏沛县人，博士，教授，CCF会员(15924M)，研究方向为理论计算机科学和高性能体系结构。E-mail:asjgwu@gmail.com

WU Ji-gang,born in 1963,PhD,professor,CCF member(15924M)，his research interests include theoretical computer science, and high performance architecture.

侯睿(1989-),男，山西盂县人，硕士生，研究方向为网络可靠性和网络容错。E-mail:asrhou@gmail.com

HOU Rui,born in 1989,MS candidate,his research interests include network reliability, and network fault tolerance.

Strategy and algorithms for replica update in tree networks

WANG Xu,WU Ji-gang,HOU Rui

(1.School of Computer Science and Software,Tianjin Polytechnic University,Tianjin 300387;2.State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China)

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 justO(nlogn) in worst case, while the optimal solution obtained by dynamic programming isO(n5).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.

tree network;replica placement;update strategy

1007-130X(2015)03-0440-06

2014-01-17;

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

TP393.0

A

10.3969/j.issn.1007-130X.2015.03.005

王旭(1989-),女，山东城武人，硕士生，研究方向为高性能计算和数据中心。E-mail:wangxu_tjpu@126.com

通信地址：300387 天津市西青区宾水西道399号天津工业大学计算机科学与软件学院

Address:School of Computer Science and Software,Tianjin Polytechnic University,399 Binshui Avenue West,Xiqing District,Tianjin 300387,P.R.China