樹形網(wǎng)絡(luò)中的副本更新策略及算法*

王 旭，武繼剛，侯 睿

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387;

2.中國科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

樹形網(wǎng)絡(luò)中的副本更新策略及算法*

王 旭，武繼剛，侯 睿

(1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387;

2.中國科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室，北京 100190)

樹形網(wǎng)絡(luò)中的副本放置和更新是網(wǎng)絡(luò)通訊中值得研究的重要問題之一。面對網(wǎng)絡(luò)中數(shù)據(jù)訪問需求的動態(tài)變化，好的副本放置和更新策略可以在保證服務(wù)質(zhì)量的前提下有效減少網(wǎng)絡(luò)運(yùn)行及副本更新成本。針對此問題提出了兩種貪心的動態(tài)副本更新策略，最大重用策略和請求覆蓋策略。通過算法復(fù)雜度分析和仿真實(shí)驗(yàn)可以看出，所提出的兩種算法的最壞時間復(fù)雜度為O(nlogn)，遠(yuǎn)低于現(xiàn)有的使用動態(tài)規(guī)劃求最優(yōu)解的最壞時間復(fù)雜度O(n5)，而網(wǎng)絡(luò)運(yùn)行及副本更新成本與最優(yōu)解相差不超過11%。在極大地縮短了運(yùn)算時間的同時，保持了盡可能低的網(wǎng)絡(luò)運(yùn)行及副本更新成本。

樹形網(wǎng)絡(luò)；副本放置；更新策略

1 引言

網(wǎng)絡(luò)中的副本放置問題廣泛應(yīng)用于視頻點(diǎn)播(VOD)、互聯(lián)網(wǎng)服務(wù)的提供(ISP)、內(nèi)容分發(fā)系統(tǒng)(CDS)等重要領(lǐng)域[1～7]。在樹形網(wǎng)絡(luò)中，葉節(jié)點(diǎn)會周期性地發(fā)送數(shù)據(jù)訪問請求，該請求會被含有相應(yīng)數(shù)據(jù)副本的祖先節(jié)點(diǎn)滿足。為了降低訪問延遲，提高數(shù)據(jù)的可用性，一般將同一數(shù)據(jù)的多份副本部署在網(wǎng)絡(luò)中[8～10]。副本放置問題的目標(biāo)是在網(wǎng)絡(luò)中選擇一些節(jié)點(diǎn)放置副本，以最少的副本數(shù)量滿足所有的數(shù)據(jù)訪問請求。

為解決網(wǎng)絡(luò)中的副本放置問題，提出了許多副本放置算法[11～18]。文獻(xiàn)[15]證明了在一般網(wǎng)絡(luò)中的副本放置問題是NP完全的。文獻(xiàn)[16]將一般網(wǎng)絡(luò)中的副本放置問題轉(zhuǎn)換成經(jīng)典的裝箱問題，并給出了多項(xiàng)式時間的近似算法。為了提高網(wǎng)絡(luò)的服務(wù)質(zhì)量(QoS)，文獻(xiàn)[17]在選擇節(jié)點(diǎn)放置副本時，額外考慮了副本和葉節(jié)點(diǎn)間的通信距離，證明了新問題在一般情況下是NP 難的，并給出了二叉樹形網(wǎng)絡(luò)中的最優(yōu)解和任意網(wǎng)絡(luò)中的求解該問題的近似算法。文獻(xiàn)[18]對請求的最長響應(yīng)時間加以限制，提出了偽多項(xiàng)式和多項(xiàng)式時間的近似算法。文獻(xiàn)[19]將副本放置算法應(yīng)用在混合的內(nèi)容分發(fā)網(wǎng)絡(luò)和對等網(wǎng)絡(luò)中，并通過實(shí)驗(yàn)證明了該網(wǎng)絡(luò)中的副本放置代價小于內(nèi)容分發(fā)網(wǎng)絡(luò)中的副本放置代價。為了提高數(shù)據(jù)的可擴(kuò)展性和穩(wěn)定性，文獻(xiàn)[20]提出了針對相關(guān)數(shù)據(jù)的分布式副本放置算法。文獻(xiàn)[21]對已存在的一些副本放置和選擇策略做出了較為全面的介紹和分析。

在樹形網(wǎng)絡(luò)中，之前的研究大多采用最近原則，即任一節(jié)點(diǎn)的所有請求均由距離該節(jié)點(diǎn)最近的且含有對應(yīng)副本的祖先節(jié)點(diǎn)滿足。本文所研究的問題基于同樣的原則。另外，大部分相關(guān)文獻(xiàn)假設(shè)最初的網(wǎng)絡(luò)中不存在任何副本。對于這種假設(shè)，在滿足所有客戶請求的前提下，放置的副本越少，則整個網(wǎng)絡(luò)花費(fèi)的代價越低。但是，在實(shí)際問題中，客戶發(fā)送的數(shù)據(jù)訪問請求數(shù)目會動態(tài)變化，這時重用舊副本的成本通常小于添加新副本的成本。因此，當(dāng)在網(wǎng)絡(luò)中的數(shù)據(jù)需求動態(tài)變化后，為了有效降低副本更新成本，同時令整個網(wǎng)絡(luò)保持較低的運(yùn)行成本，要平衡重用舊副本和添加新副本之間的關(guān)系。對于樹形動態(tài)網(wǎng)絡(luò)中的副本更新問題，目前只有文獻(xiàn)[22]提出了一種用動態(tài)規(guī)劃求最優(yōu)解的方法，然而該方法的最壞時間復(fù)雜度高達(dá)O(n5)，其中n為樹形網(wǎng)絡(luò)中的內(nèi)部節(jié)點(diǎn)數(shù)。而本文提出的兩種更新算法不僅會大大縮短問題求解時間，而且不會過多增加網(wǎng)絡(luò)運(yùn)行及副本更新成本。

2 問題描述與前期工作

給定一個樹形網(wǎng)絡(luò)，將其節(jié)點(diǎn)分成兩部分，可以發(fā)送數(shù)據(jù)訪問請求的葉節(jié)點(diǎn)集合C和含有n個內(nèi)部節(jié)點(diǎn)的集合N?？蛻鬷∈C在每個單位時間內(nèi)發(fā)送ri個請求。E表示已存在的服務(wù)器，即含有副本的內(nèi)部節(jié)點(diǎn)集合，從而E?N，集合E中的每一個副本在網(wǎng)絡(luò)中的數(shù)據(jù)訪問請求發(fā)生變化后或被重用，或被刪除。N-E表示由不含有副本的內(nèi)部節(jié)點(diǎn)構(gòu)成的集合，在更新的過程中，可以在集合N-E中選擇節(jié)點(diǎn)添加新副本，使其成為服務(wù)器。需要說明，如果算法在葉節(jié)點(diǎn)放置副本，則將該節(jié)點(diǎn)切分成一個葉節(jié)點(diǎn)和一個內(nèi)部節(jié)點(diǎn)，因此副本只可能放在內(nèi)部節(jié)點(diǎn)。本文研究的問題是找到一個新的服務(wù)器集合R?N，使所有的數(shù)據(jù)訪問請求都能夠由集合R中的服務(wù)器滿足，即對于每一個客戶i，都有唯一的服務(wù)器serveri∈R滿足其所有請求數(shù)ri。在本文中，假設(shè)所有服務(wù)器的性能都是相同的，其最大處理能力為W，若內(nèi)部節(jié)點(diǎn)j∈R，則其需要處理的請求數(shù)reqj為:

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

(1)

此外，根據(jù)E、R的定義可知，|E|為已存在的副本數(shù)，|R|為解決副本更新問題所需的副本數(shù)，|R∩E|為重用的舊副本數(shù)。由于所有服務(wù)器的性能都是相同的，本文將運(yùn)行一個服務(wù)器的成本歸一化為1。當(dāng)放置一個新副本時，需要花費(fèi)額外代價create，因此運(yùn)行一個新副本的代價為1+create，重復(fù)使用舊副本可看做直接運(yùn)行服務(wù)器，代價為1。刪除未使用的舊副本的代價為delete，則整個網(wǎng)絡(luò)的運(yùn)行及副本更新成本為:

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

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

(2)

副本更新問題的目標(biāo)是找出一個新的服務(wù)器集合R，在不超過每個服務(wù)器的最大處理能力W且為所有客戶的請求提供服務(wù)的前提下，使cost(R)最小。

在文獻(xiàn)[22]提出的動態(tài)規(guī)劃算法中，對每個節(jié)點(diǎn)j∈N構(gòu)造大小為(E+1)×(N-E+1)的表，該表表示以節(jié)點(diǎn)j為根節(jié)點(diǎn)(不包含節(jié)點(diǎn)j)時，其子樹中可能存在的重用舊副本和添加新副本的數(shù)目情況。動態(tài)規(guī)劃算法自底向上更新每個節(jié)點(diǎn)的表中的信息，該算法依次合并該節(jié)點(diǎn)的各個孩子節(jié)點(diǎn)，當(dāng)合并第k個孩子節(jié)點(diǎn)時，節(jié)點(diǎn)j中的表已經(jīng)包含了前k-1個孩子節(jié)點(diǎn)的副本放置情況。若合并第k個孩子節(jié)點(diǎn)時，節(jié)點(diǎn)j的子樹中未得到服務(wù)的數(shù)據(jù)訪問請求數(shù)小于合并前未得到服務(wù)的數(shù)據(jù)訪問請求數(shù)，則更新節(jié)點(diǎn)j的表中的信息。當(dāng)執(zhí)行到根節(jié)點(diǎn)時，算法結(jié)束并得到最終解。

3 副本更新的策略及算法

在本文提出的算法中，childrenj表示節(jié)點(diǎn)j的所有孩子節(jié)點(diǎn)集合，subtreej表示以節(jié)點(diǎn)j為根的子樹，Sj是subtreej中未被滿足的請求之和，則:

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

(3)

主體算法main(j)在樹形網(wǎng)絡(luò)中遞歸地自底向上對每一個節(jié)點(diǎn)j計(jì)算Sj，直至根節(jié)點(diǎn)root。若Sj>W，為j構(gòu)造包含其所有子節(jié)點(diǎn)的有序表listj，調(diào)用本文提出的兩種新策略放置副本，使Sj≤W。否則，未被滿足的數(shù)據(jù)訪問請求可從節(jié)點(diǎn)j或j的祖先節(jié)點(diǎn)中的副本獲得服務(wù)，繼續(xù)計(jì)算，直至根節(jié)點(diǎn)。由于問題要求滿足所有的數(shù)據(jù)訪問請求，所以在根節(jié)點(diǎn)root，必有Sroot=0，若Sroot≠0，則在根節(jié)點(diǎn)放置副本。偽代碼請參考算法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是根節(jié)點(diǎn)且其子樹中含有未得到服務(wù)的數(shù)據(jù)訪問請求，則節(jié)點(diǎn)j一定放置副本。若j含有副本，則重復(fù)使用，否則添加新副本*/

13: end if

14:else

15: 構(gòu)造有序表listj, 按照Sj′的值從小到大排列;

16:MAX_REUSE(j,listj,R) orREQUEST_COVER(j,listj,R);/*調(diào)用本文提出的兩種貪心策略*/

17:end if

18:returnR;

19:end Procedure

3.1 最大重用策略及算法

考慮到重用舊副本的成本低于添加新副本的成本，為使Sj≤W，最大重用策略優(yōu)先選擇保留subtreej中的舊副本。如果保留全部舊副本仍然不能使Sj足夠小，則在subtreej中添加部分新副本。另外，在前文中已經(jīng)提到，為降低網(wǎng)絡(luò)運(yùn)行成本，網(wǎng)絡(luò)中的副本總數(shù)越少越好。為了用盡可能少的副本就可以令Sj足夠小，算法在保留舊副本或添加新副本時，均優(yōu)先選擇subtreej中Sj′較大的子節(jié)點(diǎn)j′。最大重用策略的偽代碼請參考算法2。

算法2 最大重用算法

Input:j;

Output:Subset ofR。

1:ProcedureMAX_REUSE(j,listj,R)

2: repeat

3: 在listj中選擇Sj′最大且含有副本的節(jié)點(diǎn)j′;

4:Sj=Sj-Sj′;Sj′= 0;R=R∪{j′};/*重用節(jié)點(diǎn)j′中的副本，并更新通過該節(jié)點(diǎn)的請求數(shù)為0*/

5: untilSj≤Wor 沒有滿足條件的節(jié)點(diǎn)j′

6: ifSj>Wthen/*重用所有舊副本后，仍無法使Sj足夠小*/

7: repeat

8: 在listj中選擇Sj′最大且不含副本的節(jié)點(diǎn)j′;

9:Sj=Sj-Sj′;Sj′= 0;R=R∪{j′};/*在節(jié)點(diǎn)j′添加新副本，并更新通過該節(jié)點(diǎn)的請求數(shù)為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中的所有請求必須在子樹內(nèi)被滿足，即Sj=0。首先在節(jié)點(diǎn)j添加新副本或重用舊副本，為使j提供的服務(wù)覆蓋subtreej中盡可能多的客戶，j貪心地選擇請求數(shù)小的子節(jié)點(diǎn)提供服務(wù)。與最大重用策略相同的是，為了多重用舊副本，少添加新副本，j優(yōu)先為不含副本的節(jié)點(diǎn)提供服務(wù)。當(dāng)j不能覆蓋更多子節(jié)點(diǎn)，即無法為更多的客戶提供服務(wù)時，其余子節(jié)點(diǎn)或重用舊副本，或添加新副本。請求覆蓋策略的偽代碼請參考算法3。

算法3 貪心覆蓋算法

Input:j;

Output:Subset ofR。

1:ProcedureREQUEST_COVER(j,listj,R)

2:R=R∪{j};Sj=0;/*節(jié)點(diǎn)j一定放置副本*/

3:T=0;/*令T記錄該子樹根節(jié)點(diǎn)可能服務(wù)的請求數(shù)量，初始值為0，即不為任何子節(jié)點(diǎn)中的請求提供服務(wù) */

4: repeat

5: 在listj中選擇Sj′最小且不含副本的節(jié)點(diǎn)j′;

6:T=T+Sj′;/*節(jié)點(diǎn)j′中的副本為請求Sj′提供服務(wù)*/

7：untilT>Wor 沒有滿足條件的節(jié)點(diǎn)j′

8: ifT

9: repeat

10: 在listj中選擇Sj′最小且含有副本的節(jié)點(diǎn)j′;

11:T=T+Sj′;

12: untilT>W

13: end if

14:在未得到服務(wù)的節(jié)點(diǎn)及跳出循環(huán)的節(jié)點(diǎn)j′處重用舊副本或添加新副本，并更新集合R中的副本及通過相應(yīng)節(jié)點(diǎn)的請求數(shù)為0；

15:returnR;

16:end Procedure

3.3 時間復(fù)雜度

對于含有n個內(nèi)部節(jié)點(diǎn)的樹形結(jié)構(gòu)，使用最大重用策略和請求覆蓋策略更新副本時，在最壞情況下，節(jié)點(diǎn)j含有n- 1個子節(jié)點(diǎn)，計(jì)算Sj的時間復(fù)雜度為O(n)，構(gòu)造表listj的時間復(fù)雜度為O(nlogn)，至多花費(fèi)O(n)決定其孩子節(jié)點(diǎn)的副本放置情況。因此，兩種算法在最壞情況下的時間復(fù)雜度為O(nlogn)。

4 實(shí)驗(yàn)

當(dāng)內(nèi)部節(jié)點(diǎn)數(shù)分別為n=100，200，300，400，500時，對每個n值分別構(gòu)造20個不同的樹形結(jié)構(gòu)，并隨機(jī)放置|E|=n/4個副本。在每個樹形結(jié)構(gòu)中，內(nèi)部節(jié)點(diǎn)含有6～9個孩子節(jié)點(diǎn)，葉節(jié)點(diǎn)發(fā)送1～6個數(shù)據(jù)訪問請求，服務(wù)器能夠提供的數(shù)據(jù)訪問請求上限W= 10。對同一個樹形結(jié)構(gòu)，分別用最大重用算法、請求覆蓋算法，與文獻(xiàn)[22]中的動態(tài)規(guī)劃算法求出的最優(yōu)解比較。對每個節(jié)點(diǎn)數(shù)n在不同的分布樹上運(yùn)行20 次實(shí)驗(yàn)，計(jì)算其新添加的副本和重用的副本數(shù)目的平均值，如圖1和圖2所示。

Figure 1 Numbers of added copies of the three algorithms

Figure 2 Numbers of reused copies of the three algorithms

從圖1可以看出，對不同節(jié)點(diǎn)數(shù)n，本文提出的兩種算法新添加的副本數(shù)幾乎相同，均不超過動態(tài)規(guī)劃算法得到的最優(yōu)解中新添加的副本數(shù)；而圖2則表明，與最優(yōu)解相比，本文提出的兩種貪心算法重用的舊副本數(shù)較多，因此不會增加整個網(wǎng)絡(luò)的更新成本。

與文獻(xiàn)[22]相同，在本文的實(shí)驗(yàn)中，取create=0.1，delete=0.01，按照第2節(jié)中的公式(2)計(jì)算三種算法的網(wǎng)絡(luò)運(yùn)行及副本更新成本cost(R)，結(jié)果如圖3所示。

Figure 3 Total cost of the three algorithms

從圖3可以看出，最大重用策略和請求覆蓋策略花費(fèi)的網(wǎng)絡(luò)運(yùn)行及副本更新成本與解決該問題所需最小代價值相近。為了更直觀地比較三種算法得到的可行解的總體代價，根據(jù)公式(4)計(jì)算本文提出的兩種算法相對于動態(tài)規(guī)劃得到的最優(yōu)解的額外代價比。

(4)

其中，opt代表最優(yōu)解，m代表最大重用策略或請求覆蓋策略得到的可行解。對上文給定的任意內(nèi)部節(jié)點(diǎn)數(shù)n，計(jì)算結(jié)果如圖4所示。從圖4中可以看出，最大重用策略和請求覆蓋策略得到的可行解的額外代價不會超過最優(yōu)解的11%和10%。因此，本文提出的兩種貪心策略得到的近似解與最優(yōu)解相差不大，能夠保持較低的網(wǎng)絡(luò)運(yùn)行及副本更新成本。

Figure 4 Percentage of additional cost of the three algorithms

三種算法的運(yùn)行時間如表1所示，單位為s。對不同節(jié)點(diǎn)數(shù)n，最大重用策略和請求覆蓋策略均可在0.01s內(nèi)得到可行解，而動態(tài)規(guī)劃算法在節(jié)點(diǎn)數(shù)增加到500時，執(zhí)行時間高達(dá)2 151.19s?？梢钥闯觯疚奶岢龅膬煞N更新算法在運(yùn)行時間上具有明顯優(yōu)勢。

Table 1 Running time of the three algorithms

為了研究已存在副本的數(shù)量對本文提出的兩種策略得到的可行解的影響，構(gòu)造100個隨機(jī)樹，使其內(nèi)部節(jié)點(diǎn)數(shù)n均為100，并在每個樹中隨機(jī)放置0 ≤E≤100個副本。根據(jù)公式(4)計(jì)算兩種策略得到的可行解的額外代價比，如圖5所示。從圖5可以看出，當(dāng)網(wǎng)絡(luò)中已存在的副本數(shù)很少或很多時，本文提出的兩種貪心策略得到的可行解與最優(yōu)解十分相近。

Figure 5 Influence of pre-existing copy

5 結(jié)束語

樹形網(wǎng)絡(luò)廣泛存在于計(jì)算機(jī)網(wǎng)絡(luò)的各個領(lǐng)域，數(shù)據(jù)的共享訪問是其亟待解決的一個重要問題。在實(shí)際網(wǎng)絡(luò)中，數(shù)據(jù)訪問請求是實(shí)時動態(tài)變化的，從降低網(wǎng)絡(luò)運(yùn)行成本和確?？蛻舻臄?shù)據(jù)訪問請求能夠及時得到數(shù)據(jù)服務(wù)的角度出發(fā)，快速副本更新策略的提出刻不容緩。因此，本文針對樹形網(wǎng)絡(luò)中的副本更新問題，提出了兩種貪心的更新策略：最大重用策略和請求覆蓋策略，兩種策略都是在內(nèi)部節(jié)點(diǎn)j無法單獨(dú)滿足所有以其為根的子樹中的數(shù)據(jù)請求時被調(diào)用。由于網(wǎng)絡(luò)中本身存在一定數(shù)量的副本，兩種策略均優(yōu)先選擇重用已有副本。所不同的是，在最大重用策略中，選擇在盡可能接近樹根的位置放置副本，而請求覆蓋策略則正相反。通過算法復(fù)雜度分析可知，兩種算法的最壞時間復(fù)雜度均不超過O(nlogn)，相比于求最優(yōu)解，大大縮短了算法的運(yùn)行時間。通過仿真實(shí)驗(yàn)的比較，新算法在副本更新時的總體代價與最優(yōu)解相近。

除了縮短副本更新時間，減少副本更新代價，為了提高服務(wù)質(zhì)量，網(wǎng)絡(luò)中的副本放置問題還有許多其他目標(biāo)，如通信代價最小、功率消耗最小等，這將是我們未來工作的主要方向。同時，也將考慮其他網(wǎng)絡(luò)模型上副本放置和更新的問題。

[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)，研究方向?yàn)槔碚撚?jì)算機(jī)科學(xué)和高性能體系結(jié)構(gòu)。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-),男，山西盂縣人，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)容錯。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基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61173032);計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室開放課題資助項(xiàng)目(CARCH201303)

TP393.0

A

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

王旭(1989-),女，山東城武人，碩士生，研究方向?yàn)楦咝阅苡?jì)算和數(shù)據(jù)中心。E-mail:wangxu_tjpu@126.com

通信地址：300387 天津市西青區(qū)賓水西道399號天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院

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