王 旭，武繼剛，侯 睿

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

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

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

王 旭，武繼剛，侯 睿

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

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

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

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

1 引言

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

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

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

2 問(wèn)題描述與前期工作

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

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

(1)

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

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

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

(2)

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

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

3 副本更新的策略及算法

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

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

(3)

主體算法main(j)在樹(shù)形網(wǎng)絡(luò)中遞歸地自底向上對(duì)每一個(gè)節(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ù)訪問(wèn)請(qǐng)求可從節(jié)點(diǎn)j或j的祖先節(jié)點(diǎn)中的副本獲得服務(wù)，繼續(xù)計(jì)算，直至根節(jié)點(diǎn)。由于問(wèn)題要求滿足所有的數(shù)據(jù)訪問(wèn)請(qǐng)求，所以在根節(jié)點(diǎn)root，必有Sroot=0，若Sroot≠0，則在根節(jié)點(diǎn)放置副本。偽代碼請(qǐng)參考算法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)且其子樹(shù)中含有未得到服務(wù)的數(shù)據(jù)訪問(wèn)請(qǐng)求，則節(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足夠小，算法在保留舊副本或添加新副本時(shí)，均優(yōu)先選擇subtreej中Sj′較大的子節(jié)點(diǎn)j′。最大重用策略的偽代碼請(qǐng)參考算法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′中的副本，并更新通過(guò)該節(jié)點(diǎn)的請(qǐng)求數(shù)為0*/

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

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

7: repeat

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

9:Sj=Sj-Sj′;Sj′= 0;R=R∪{j′};/*在節(jié)點(diǎn)j′添加新副本，并更新通過(guò)該節(jié)點(diǎn)的請(qǐng)求數(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 請(qǐng)求覆蓋策略及算法

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

4: repeat

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

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

7：untilT>Wor 沒(méi)有滿足條件的節(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中的副本及通過(guò)相應(yīng)節(jié)點(diǎn)的請(qǐng)求數(shù)為0；

15:returnR;

16:end Procedure

3.3 時(shí)間復(fù)雜度

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

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

當(dāng)內(nèi)部節(jié)點(diǎn)數(shù)分別為n=100，200，300，400，500時(shí)，對(duì)每個(gè)n值分別構(gòu)造20個(gè)不同的樹(shù)形結(jié)構(gòu)，并隨機(jī)放置|E|=n/4個(gè)副本。在每個(gè)樹(shù)形結(jié)構(gòu)中，內(nèi)部節(jié)點(diǎn)含有6～9個(gè)孩子節(jié)點(diǎn)，葉節(jié)點(diǎn)發(fā)送1～6個(gè)數(shù)據(jù)訪問(wèn)請(qǐng)求，服務(wù)器能夠提供的數(shù)據(jù)訪問(wèn)請(qǐng)求上限W= 10。對(duì)同一個(gè)樹(shù)形結(jié)構(gòu)，分別用最大重用算法、請(qǐng)求覆蓋算法，與文獻(xiàn)[22]中的動(dòng)態(tài)規(guī)劃算法求出的最優(yōu)解比較。對(duì)每個(gè)節(jié)點(diǎn)數(shù)n在不同的分布樹(shù)上運(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可以看出，對(duì)不同節(jié)點(diǎn)數(shù)n，本文提出的兩種算法新添加的副本數(shù)幾乎相同，均不超過(guò)動(dòng)態(tài)規(guī)劃算法得到的最優(yōu)解中新添加的副本數(shù)；而圖2則表明，與最優(yōu)解相比，本文提出的兩種貪心算法重用的舊副本數(shù)較多，因此不會(huì)增加整個(gè)網(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可以看出，最大重用策略和請(qǐng)求覆蓋策略花費(fèi)的網(wǎng)絡(luò)運(yùn)行及副本更新成本與解決該問(wèn)題所需最小代價(jià)值相近。為了更直觀地比較三種算法得到的可行解的總體代價(jià)，根據(jù)公式(4)計(jì)算本文提出的兩種算法相對(duì)于動(dòng)態(tài)規(guī)劃得到的最優(yōu)解的額外代價(jià)比。

(4)

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

Figure 4 Percentage of additional cost of the three algorithms

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

Table 1 Running time of the three algorithms

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

Figure 5 Influence of pre-existing copy

5 結(jié)束語(yǔ)

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

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

[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會(huì)員(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ò)容錯(cuò)。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)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61173032);計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題資助項(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號(hào)天津工業(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