李 帥，黨 鑫，王 旭，武繼剛

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

2.廣東工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣州 510006

副本放置中的更新策略及算法*

李 帥1，黨 鑫1，王 旭1，武繼剛2+

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

2.廣東工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣州 510006

LI Shuai,DANG Xin,WANG Xu,et al.Replica update strategy and algorithms for replica placement.Journal of Frontiers of Computer Science and Technology,2016,10(11):1633-1640.

副本技術(shù)廣泛應(yīng)用于云計(jì)算及分布式系統(tǒng)中，合理的數(shù)據(jù)副本放置是降低網(wǎng)絡(luò)運(yùn)行成本的重要手段，也是副本技術(shù)的核心問題。副本更新是針對(duì)網(wǎng)絡(luò)中數(shù)據(jù)訪問請(qǐng)求的動(dòng)態(tài)變化而進(jìn)行的副本添加與刪除。針對(duì)副本放置問題，提出了一種基于多訪問策略的副本動(dòng)態(tài)更新算法MPFSF（min_placement far servers first）。該算法在引入通信距離限制的同時(shí)，盡可能多地重用網(wǎng)絡(luò)中已存在的副本，并根據(jù)需要實(shí)施必要的副本更新，最大使用每個(gè)副本的處理能力，以便降低數(shù)據(jù)訪問的時(shí)延，提高數(shù)據(jù)訪問效率。最后通過實(shí)驗(yàn)結(jié)果和分析證明，該算法在不同的通信距離限制下，網(wǎng)絡(luò)的運(yùn)行成本得到了明顯的降低，對(duì)原有算法的改進(jìn)最高可達(dá)84.6%。

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

1 引言

在樹形網(wǎng)絡(luò)中，副本放置問題是指在網(wǎng)絡(luò)中如何合理地放置副本以及如何使放置的副本數(shù)量最少。通過將副本分布在網(wǎng)絡(luò)中，可以進(jìn)行負(fù)載均衡，提高數(shù)據(jù)的可用性、可靠性，降低訪問時(shí)延，節(jié)省網(wǎng)絡(luò)帶寬等。副本放置問題廣泛應(yīng)用于視頻點(diǎn)播、互聯(lián)網(wǎng)服務(wù)、內(nèi)容分發(fā)系統(tǒng)等重要領(lǐng)域[1-7]。

為了解決網(wǎng)絡(luò)中的副本放置問題，許多副本放置算法被提出[8-15]。文獻(xiàn)[8]證明了在一般網(wǎng)絡(luò)中的副本放置問題是NP完全的。文獻(xiàn)[9]提出了一種副本放置節(jié)點(diǎn)選擇的分布式算法，并將該問題轉(zhuǎn)化為背包問題，在考慮對(duì)副本的訪問頻率的基礎(chǔ)上，提出了一種近似算法。文獻(xiàn)[10]將一般網(wǎng)絡(luò)中的副本放置問題轉(zhuǎn)換成經(jīng)典的裝箱問題，并給出了多項(xiàng)式時(shí)間的近似算法。文獻(xiàn)[11]提出了一種廣域分布式存儲(chǔ)系統(tǒng)中的通用數(shù)據(jù)副本放置策略，實(shí)現(xiàn)最小化系統(tǒng)數(shù)據(jù)通信時(shí)延。文獻(xiàn)[12]面向線性總線網(wǎng)絡(luò)的需要，提出了兩種數(shù)據(jù)副本優(yōu)化放置策略，可以最大化數(shù)據(jù)有效性和最小化數(shù)據(jù)訪問的代價(jià)。文獻(xiàn)[13]面向提高云系統(tǒng)可用性的需要，通過建立數(shù)學(xué)模型，描述了系統(tǒng)有效性和副本數(shù)量關(guān)系，給出了副本計(jì)量方法和副本機(jī)制算法。文獻(xiàn)[14]在Hadoop架構(gòu)內(nèi)，根據(jù)節(jié)點(diǎn)間距離與負(fù)載計(jì)算每個(gè)節(jié)點(diǎn)的調(diào)度評(píng)價(jià)值，選擇最佳節(jié)點(diǎn)放置數(shù)據(jù)副本。為了降低數(shù)據(jù)訪問延遲，提高網(wǎng)絡(luò)的服務(wù)質(zhì)量（quality of service，QoS），文獻(xiàn)[15]在選擇節(jié)點(diǎn)放置副本時(shí)，考慮了副本和客戶間的通信距離，證明了新問題在距離約束下是NP難的，并給出了在二叉樹上解決該問題的一個(gè)多項(xiàng)式時(shí)間最優(yōu)算法。文獻(xiàn)[16]提出了一種改進(jìn)的近似算法，在多項(xiàng)式時(shí)間內(nèi)解決副本位置選擇問題，提高了網(wǎng)絡(luò)容錯(cuò)性能。文獻(xiàn)[17-18]對(duì)已存在的一些副本放置和選擇策略進(jìn)行了較為全面的介紹和分析。

在樹形網(wǎng)絡(luò)中，葉節(jié)點(diǎn)作為客戶周期性地發(fā)送若干數(shù)據(jù)訪問請(qǐng)求，該請(qǐng)求從含有相應(yīng)副本的祖先節(jié)點(diǎn)獲得服務(wù)。樹形網(wǎng)絡(luò)中廣泛使用最近策略分配副本，即任一客戶的所有數(shù)據(jù)訪問請(qǐng)求只能由一個(gè)副本提供服務(wù)，且該副本是在客戶節(jié)點(diǎn)到根節(jié)點(diǎn)的唯一路徑上，距離客戶節(jié)點(diǎn)最近的副本節(jié)點(diǎn)。然而最近策略的限制過高，導(dǎo)致副本使用率過低。為了提高副本使用率，即以盡可能少的副本數(shù)量滿足所有客戶請(qǐng)求，文獻(xiàn)[19]提出了兩個(gè)高效的策略：（1）單一策略，任一客戶的所有請(qǐng)求由一個(gè)副本提供服務(wù)，該副本可以是客戶節(jié)點(diǎn)到根節(jié)點(diǎn)的唯一路徑上的任一副本。與最近策略相比，單一策略提高了副本的使用率，但若為客戶提供服務(wù)的副本放置偏遠(yuǎn)，可能會(huì)造成服務(wù)時(shí)間過長。（2）多訪問策略，任一客戶的所有數(shù)據(jù)訪問請(qǐng)求可由該客戶的祖先節(jié)點(diǎn)中的一個(gè)或多個(gè)副本共同提供服務(wù)。與最近策略和單一策略相比，多訪問策略更加靈活且副本使用率最高。同時(shí)，文獻(xiàn)[20]已證明異構(gòu)網(wǎng)絡(luò)中基于多訪問策略的副本放置問題是NP難解的。

初始時(shí)，大多相關(guān)文獻(xiàn)假設(shè)樹形網(wǎng)絡(luò)中不存在任何副本，然而客戶發(fā)送的數(shù)據(jù)訪問請(qǐng)求是單位時(shí)間動(dòng)態(tài)變化，因此這種假設(shè)并不完全符合實(shí)際要求。為了有效降低網(wǎng)絡(luò)運(yùn)行成本，需要平衡重用舊副本和添加新副本之間的關(guān)系。其中，重用舊副本的成本通常小于添加新副本的成本。對(duì)于樹形動(dòng)態(tài)網(wǎng)絡(luò)中的副本更新問題，目前僅有文獻(xiàn)[21]考慮了基于最近策略的副本更新問題，并提出了一種動(dòng)態(tài)規(guī)劃求最優(yōu)解的方法。

本文的主要貢獻(xiàn)：區(qū)別于最近策略，提出了基于多訪問策略的啟發(fā)式更新算法，即最小放置更新算法。本文算法是以最大重用網(wǎng)絡(luò)中已存在的副本，降低網(wǎng)絡(luò)放置的副本數(shù)量為目標(biāo)，從而實(shí)現(xiàn)降低網(wǎng)絡(luò)運(yùn)行及更新成本的目的。本文算法不僅能夠最大使用網(wǎng)絡(luò)中每個(gè)副本的處理能力，而且不會(huì)過多增加網(wǎng)絡(luò)運(yùn)行及副本更新成本。同時(shí)，在所研究的副本更新問題中，為了降低訪問時(shí)延，提高訪問效率，額外考慮了通信距離的限制，即所有客戶的數(shù)據(jù)訪問請(qǐng)求需要在一定通信距離內(nèi)獲得服務(wù)，從而保證整個(gè)網(wǎng)絡(luò)服務(wù)質(zhì)量。

2 問題描述

在給定的樹形網(wǎng)絡(luò)中，將其節(jié)點(diǎn)分成兩部分，客戶集合C和內(nèi)部節(jié)點(diǎn)集合N。任一葉節(jié)點(diǎn)代表一個(gè)客戶，且客戶i∈C在每個(gè)單位時(shí)間內(nèi)發(fā)送ri個(gè)數(shù)據(jù)訪問請(qǐng)求。內(nèi)部節(jié)點(diǎn) j∈N是可以放置副本的節(jié)點(diǎn)，且放有副本的節(jié)點(diǎn)稱為服務(wù)器，并可為該節(jié)點(diǎn)子樹中的客戶提供服務(wù)。

設(shè)R是網(wǎng)絡(luò)中放置副本的集合，ris表示服務(wù)器s為客戶i提供服務(wù)的請(qǐng)求數(shù)。根據(jù)多訪問策略可知，任一客戶i的數(shù)據(jù)訪問請(qǐng)求ri都能夠被一個(gè)或多個(gè)服務(wù)器Servers(i)∈R提供服務(wù)：

為了滿足客戶的請(qǐng)求，需要通過不斷地在網(wǎng)絡(luò)中放置副本來實(shí)現(xiàn)這一目標(biāo)，而每個(gè)副本的處理能力是相異的。設(shè)服務(wù)器s的處理能力為Ws，則該服務(wù)器能夠提供的數(shù)據(jù)訪問請(qǐng)求不得超過其最大處理能力：

為了有效降低訪問時(shí)延，提高訪問效率，本文在增加通信距離受限的條件下研究副本更新問題，即客戶的請(qǐng)求必須在有限的通信距離內(nèi)獲得服務(wù)。因此該問題可定義為：對(duì)任一客戶i，為其提供服務(wù)的服務(wù)器s與其距離d(i,s)不得超過給定的邊界值qi：

若某客戶的數(shù)據(jù)請(qǐng)求被其自身處理，即該客戶節(jié)點(diǎn)上放有副本，將該節(jié)點(diǎn)分割成一個(gè)葉節(jié)點(diǎn)和一個(gè)內(nèi)部節(jié)點(diǎn)。因此，副本只能是放置在樹形網(wǎng)絡(luò)中的內(nèi)部節(jié)點(diǎn)上，且該節(jié)點(diǎn)與放有副本節(jié)點(diǎn)之間的通信距離為0。

設(shè)E表示網(wǎng)絡(luò)中已存在的服務(wù)器集合，即含有副本的內(nèi)部節(jié)點(diǎn)集合，集合E中的每一個(gè)副本在客戶請(qǐng)求發(fā)生變化后或被重用，或被刪除。N-E表示由不含有副本的內(nèi)部節(jié)點(diǎn)構(gòu)成的集合，在更新過程中，可在集合N-E中選擇節(jié)點(diǎn)添加新副本。由于重用已存在的副本代價(jià)小于放置副本的代價(jià)，刪除副本的代價(jià)小于重用副本的代價(jià)，根據(jù)上述描述，添加副本s的代價(jià)為其自身的處理能力Ws，重用副本s的代價(jià)為αWs(0<α<1)，刪除副本s的代價(jià)為βWs（0<β<α<1）。則整個(gè)網(wǎng)絡(luò)的運(yùn)行及更新成本為：

本文的目標(biāo)是找出一個(gè)新的服務(wù)器集合R，在保證每個(gè)客戶的數(shù)據(jù)訪問請(qǐng)求能夠獲得服務(wù)，且不超過其允許的最大通信距離前提下，使得cost_upd (R)最小，這可形式化如下：

3 副本更新的策略及算法

基于多訪問策略的副本放置問題，文獻(xiàn)[4]提出一種啟發(fā)式算法——最近優(yōu)先放置算法（multiple small QoS close servers first，MSQoSC）。其中qi表示客戶i的最大獲得服務(wù)的通信距離，d(i,r)表示客戶i到根節(jié)點(diǎn)r的距離。

3.1 最近優(yōu)先放置算法

所有客戶i∈C按其qi升序排序，若同一父節(jié)點(diǎn)的客戶節(jié)點(diǎn)具有相同的距離約束，則根據(jù)客戶請(qǐng)求大小降序，從而得到表list，依次對(duì)表list中的每個(gè)客戶節(jié)點(diǎn)執(zhí)行以下操作。

（1）在距離qi內(nèi)查詢客戶的祖先節(jié)點(diǎn)上是否存在已放副本。若不存在，在距離該客戶節(jié)點(diǎn)最近的祖先節(jié)點(diǎn)上放置副本；否則，轉(zhuǎn)（2）。

（2）判斷已放副本的處理能力是否能夠滿足客戶的數(shù)據(jù)訪問請(qǐng)求。若滿足，該副本的處理能力減去當(dāng)前客戶請(qǐng)求數(shù)，剩余處理能力可以繼續(xù)處理其他客戶請(qǐng)求；若不滿足，轉(zhuǎn)（3）。

（3）選擇距離該客戶最近祖先空節(jié)點(diǎn)添加副本，滿足當(dāng)前客戶剩余請(qǐng)求。

該算法的時(shí)間復(fù)雜度為O(n2)，n為樹形結(jié)構(gòu)大小。該算法并不適用于具有較小請(qǐng)求數(shù)的客戶，可能會(huì)造成副本資源的極大浪費(fèi)。隨著客戶請(qǐng)求每單位時(shí)間內(nèi)發(fā)生變化，最近優(yōu)先放置算法需要每單位時(shí)間內(nèi)重復(fù)部署副本，這需要花費(fèi)極高的代價(jià)。因此，需要重用網(wǎng)絡(luò)中已存在的副本，從而降低整個(gè)網(wǎng)絡(luò)的運(yùn)行成本。由于重用已存在副本的代價(jià)小于添加新副本的代價(jià)，在重新部署副本的過程中，從降低整個(gè)網(wǎng)絡(luò)運(yùn)行成本角度出發(fā)，應(yīng)優(yōu)先使用已存在副本。

3.2 最小放置更新算法

對(duì)所有客戶i∈C按其到根節(jié)點(diǎn)r的距離d(i,r)的升序進(jìn)行排序，構(gòu)成列表list_d，依次對(duì)表中的各個(gè)節(jié)點(diǎn)進(jìn)行操作。若按d(i,r)降序順序處理客戶請(qǐng)求，在處理距離根節(jié)點(diǎn)較遠(yuǎn)的客戶時(shí)，可能會(huì)在距離根節(jié)點(diǎn)較近的客戶節(jié)點(diǎn)的祖先節(jié)點(diǎn)上放置副本，從而導(dǎo)致距離根節(jié)點(diǎn)較近的客戶節(jié)點(diǎn)沒有足夠多的節(jié)點(diǎn)放置副本為其提供服務(wù)。

排序后，依次對(duì)表list_d中的每個(gè)客戶節(jié)點(diǎn)，在其允許的通信距離內(nèi)，選擇節(jié)點(diǎn)放置副本為其提供服務(wù)。由于處理節(jié)點(diǎn)前其祖先節(jié)點(diǎn)可能已存在若干副本，為了充分使用每個(gè)副本，減少副本放置個(gè)數(shù)，首先判斷已存在副本是否還有剩余能力繼續(xù)為該節(jié)點(diǎn)服務(wù)。選擇策略如下：

（1）判斷該節(jié)點(diǎn)的祖先節(jié)點(diǎn)中是否存在副本（集合E中的副本），若有則進(jìn)行副本更新，依次從距離該客戶節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)開始，重用已存在的副本，并最大使用每一個(gè)副本的處理能力，直至客戶請(qǐng)求均獲得服務(wù)或不存在符合條件的節(jié)點(diǎn)。

（2）若該節(jié)點(diǎn)的祖先節(jié)點(diǎn)不含任何副本或所有已放副本的剩余處理能力均為0或不滿足當(dāng)前客戶需求，依次在距離該客戶最遠(yuǎn)的節(jié)點(diǎn)添加副本，直至所有請(qǐng)求獲得服務(wù)或不存在能夠繼續(xù)放置副本的節(jié)點(diǎn)。

（3）對(duì)于集合E中的副本，若在副本更新過程中沒有使用，則刪除對(duì)應(yīng)節(jié)點(diǎn)中的副本。

算法的偽代碼描述如下。

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

對(duì)于含有n個(gè)節(jié)點(diǎn)的樹形結(jié)構(gòu)，使用最小放置更新算法時(shí)，首先對(duì)所有的客戶節(jié)點(diǎn)進(jìn)行排序，最壞情況下時(shí)間復(fù)雜度為O(n lb n)。對(duì)任一客戶選擇節(jié)點(diǎn)重用或添加時(shí)，至多花費(fèi)O(n)，那么整個(gè)網(wǎng)絡(luò)中的副本放置至多花費(fèi)O(n2)。因此，算法在最壞情況下的時(shí)間復(fù)雜度為O(n2)。

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

任一客戶節(jié)點(diǎn)i的數(shù)據(jù)訪問請(qǐng)求量ri為r≤ri≤2r且r= |N|/|C|×50×λ。

當(dāng)考慮距離限制的副本放置問題時(shí)，根據(jù)通信距離范圍可分成3類；（1）通信距離限制嚴(yán)緊，即q∈{1,2}。（2）通信距離限制為樹高的一半，即q=h/2。（3）無通信距離限制，即q=h+1。其中，h為樹的高度。

在含有n個(gè)節(jié)點(diǎn)的樹形結(jié)構(gòu)中隨機(jī)放置|E|=N/4個(gè)副本。在樹形網(wǎng)絡(luò)中，重用舊副本的成本通常小于添加新副本的成本，而刪除未重用的舊副本成本通常小于重用舊副本的成本，即0<β<α<1。因此，為了研究網(wǎng)絡(luò)中重用和刪除副本的代價(jià)對(duì)算法性能的影響，β/α取值為0.1，0.2，…，0.9。隨機(jī)生成20個(gè)不同的且含有n=200個(gè)節(jié)點(diǎn)的樹形結(jié)構(gòu)。在同一樹形結(jié)構(gòu)中，本文提出的最小放置更新算法MPFSF和文獻(xiàn)[4]中啟發(fā)式算法MSQoSC，按照式（5）計(jì)算參數(shù)變化對(duì)整個(gè)網(wǎng)絡(luò)的運(yùn)行及更新成本的影響，如圖1所示。

圖1中，網(wǎng)絡(luò)運(yùn)行及更新成本是指網(wǎng)絡(luò)中的副本運(yùn)行和更新成本。在3種不同距離約束下，隨著β/α值的變化，本文算法MPFSF始終保持著整體較低的網(wǎng)絡(luò)運(yùn)行及更新成本，而算法MSQoSC則需要花費(fèi)極高的代價(jià)重新部署副本。當(dāng)通信距離限制嚴(yán)緊時(shí)，即q∈{1,2}，算法MPFSF和MSQoSC都需要放置較多的副本來滿足所有客戶的需求。然而本文算法在重新部署副本時(shí)，最大重用網(wǎng)絡(luò)中已存在的副本，減少了副本添加的數(shù)量，從而降低了整個(gè)網(wǎng)絡(luò)的運(yùn)行及更新成本。當(dāng)q=h/2和q=h+1時(shí)，通信距離限制寬松，本文算法通過重用網(wǎng)絡(luò)中已存在的副本，最大程度上降低整個(gè)網(wǎng)絡(luò)運(yùn)行成本，而算法MSQoSC為滿足所有的客戶動(dòng)態(tài)變化請(qǐng)求，需要花費(fèi)極高的代價(jià)去重新部署網(wǎng)絡(luò)中的副本。

隨機(jī)生成若干含有n個(gè)節(jié)點(diǎn)的樹形結(jié)構(gòu)，10≤n≤300（n=|N|+|C|）。每個(gè)節(jié)點(diǎn)最多有5個(gè)孩子節(jié)點(diǎn)，任一服務(wù)器j的處理能力為50≤Wj≤150。網(wǎng)絡(luò)中最重要的參數(shù)是負(fù)載，即所有客戶的數(shù)據(jù)訪問請(qǐng)求總和與所有服務(wù)器的處理能力之比，用λ表示，則

Fig.1 Effect of β/αfor algorithms in different distance constraints圖1 β/α取值在不同距離限制下對(duì)算法的影響

為了進(jìn)一步分析網(wǎng)絡(luò)規(guī)模對(duì)網(wǎng)絡(luò)中重用副本數(shù)的影響，取α=0.1,β=0.08。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)n=10, 50,100,150,200時(shí)，對(duì)同一樹形結(jié)構(gòu)，計(jì)算每個(gè)算法對(duì)副本的平均重用數(shù)目，如圖2所示。

在不同的通信距離限制下，由本文算法MPFSF得到的整個(gè)網(wǎng)絡(luò)運(yùn)行及更新成本低于算法MSQoSC。由圖2可知，本文算法MPFSF與MSQoSC相比，在最大使用網(wǎng)絡(luò)中已存在副本的同時(shí)，降低了網(wǎng)絡(luò)中新添加的副本數(shù)。

當(dāng)q∈{1,2}時(shí)，通信距離限制嚴(yán)緊，本文算法MPFSF最大且優(yōu)先重用網(wǎng)絡(luò)中已有的副本，而算法MSQoSC逐步放置副本且可能在客戶自身上放有副本，從而隨著網(wǎng)絡(luò)規(guī)模的變大，使得MPFSF算法和MSQoSC算法的重用副本數(shù)差別較大。

當(dāng)q=h/2和q=h+1時(shí)，通信距離放寬，隨著網(wǎng)絡(luò)規(guī)模的變大，本文算法MPFSF和算法MSQoSC對(duì)已存在副本的重用數(shù)逐漸增加，而本文算法MPFSF優(yōu)先重用網(wǎng)絡(luò)中已有的副本。因而，MPFSF算法和MSQoSC算法的重用副本數(shù)差別較小。

Fig.2 Number of replicas reused in different distance constraints圖2 在不同距離限制中的重用副本數(shù)

為了更直觀地比較算法的性能，根據(jù)式（5）計(jì)算整個(gè)網(wǎng)絡(luò)的運(yùn)行及更新成本，如圖3所示。

Fig.3 Effect of the size of a tree in different distance constraints圖3 不同距離限制下網(wǎng)絡(luò)規(guī)模對(duì)算法的影響

在圖3中，對(duì)于不同網(wǎng)絡(luò)規(guī)模的樹形結(jié)構(gòu)，本文算法MPFSF在不同的通信距離限制下，與算法MSQoSC相比，始終保持較低的網(wǎng)絡(luò)運(yùn)行及更新成本。

當(dāng)q∈{1,2}時(shí)，通信距離限制嚴(yán)緊，需要放置較多的副本來滿足客戶的需求，從而隨著網(wǎng)絡(luò)規(guī)模的變大，網(wǎng)絡(luò)運(yùn)行成本逐漸增加。在此過程中，本文算法MPFSF優(yōu)先重用網(wǎng)絡(luò)中已存在副本且最大使用每一個(gè)副本，與算法MSQoSC相比，網(wǎng)絡(luò)運(yùn)行及更新成本平均降低了20.3%。

當(dāng)q=h/2時(shí)，通信距離限制放寬，隨著網(wǎng)絡(luò)規(guī)模的變大，本文算法MPFSF對(duì)已存在副本的重用數(shù)逐漸增加，與嚴(yán)緊的通信距離限制相比，網(wǎng)絡(luò)運(yùn)行成本逐漸降低。算法MSQoSC隨著網(wǎng)絡(luò)規(guī)模的變大，重新部署副本所需花費(fèi)的成本不斷提高。與算法MSQoSC相比，網(wǎng)絡(luò)運(yùn)行及更新成本平均降低了79.8%。

當(dāng)q=h+1時(shí)，即無通信距離限制，客戶的請(qǐng)求可以被網(wǎng)絡(luò)中任意放有副本的節(jié)點(diǎn)處理。隨著網(wǎng)絡(luò)規(guī)模的變大，本文算法MPFSF在最大重用已存在的副本同時(shí)，最大使用網(wǎng)絡(luò)中每一個(gè)副本，而算法MSQoSC則需要不斷地重新部署網(wǎng)絡(luò)中的副本。與算法MSQoSC相比，網(wǎng)絡(luò)運(yùn)行及更新成本平均降低了84.6%。

5 結(jié)束語

樹形網(wǎng)絡(luò)廣泛存在于計(jì)算機(jī)網(wǎng)絡(luò)的各個(gè)領(lǐng)域，數(shù)據(jù)的共享訪問是其亟待解決的一個(gè)重要問題。在實(shí)際網(wǎng)絡(luò)中，客戶發(fā)送的數(shù)據(jù)訪問請(qǐng)求是動(dòng)態(tài)變化的，為了確保網(wǎng)絡(luò)的服務(wù)質(zhì)量，降低數(shù)據(jù)訪問延遲，副本更新策略的提出刻不容緩。本文提出了基于多訪問策略解決樹形網(wǎng)絡(luò)中的副本更新問題的啟發(fā)式算法，與算法MSQoSC相比，不僅最大使用網(wǎng)絡(luò)中的每一個(gè)副本，同時(shí)大大降低網(wǎng)絡(luò)運(yùn)行及更新成本。

除了降低訪問數(shù)據(jù)時(shí)延，減少副本更新代價(jià)，為了提高服務(wù)質(zhì)量，網(wǎng)絡(luò)中的副本放置還要考慮其他問題，如通信代價(jià)最小，網(wǎng)絡(luò)的容錯(cuò)性等，這將是未來工作的主要方向。同時(shí)，也將考慮其他網(wǎng)絡(luò)模型上副本放置和更新問題。

[1]Han Guodong,Zhu Yige.Replica placement for time-shifted IPTV system[J].Application of Electronic Technique,2012, 38(7):116-119.

[2]Lin Yifang,Liu Pangfeng,Wu Janjan.Optimal placement of replicas in data grid environments with locality assurance [C]//Proceedings of the 12th IEEE International Conference on Parallel and Distributed Systems,Minneapolis, USA,Jul 12-15,2006.Piscataway,USA:IEEE,2006:465-474.

[3]Corporation H P.Efficient dynamic replication algorithm using agent for data grid[J].The Scientific World Journal,2014, 14(3):713-730.

[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,Heidelberg: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]Fu Xiong,Wang Yibo,Zhu Xinxin,et al.QoS-aware replica placement in data grids[J].Systems Engineering and Electronics,2014,36(4):784-788.

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

[9]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.

[10]Beaumont O,Bonichon N,Larchevêque H.Modeling and practical evaluation of a service location problem in large scale networks[C]//Proceedings of the 2011 IEEE International Conference on Parallel Processing,Taipei,China, Sep 13-16,2011.Piscataway,USA:IEEE,2011:482-491.

[11]Chandy J A.A generalized replica placement strategy to optimize latency in a wide area distributed storage system[C]// Proceedings of the 2008 International Workshop on Data-Aware Distributed Computing,Boston,USA,Jun 23-27, 2008.New York,USA:ACM,2008:49-54.

[12]Hsu F,Hu X D,Huang H J,et al.Optimal data replica placements in linear bus networks[C]//Proceedings of the 7th IEEE International Symposium on Parallel Architectures,Algorithms,and Networks,Hong Kong,China,May 10-12,2004.Piscataway,USA:IEEE,2004:129-134.

[13]Sun Dawei,Chang Guiran,Gao Shang,et al.Modeling a dynamic data replication strategy to increase system availability in cloud computing environments[J].Journal of Computer Science and Technology,2012,27(2):256-272.

[14]Lin Weiwei.An improved data placement strategy for ha-doop[J].Journal of South China University of Technology: Natural Science Edition,2012,40(1):65-71.

[15]Benoit A,Larchevêque H,Renaud-Goud P.Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks[C]//Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium,Shanghai,May 21-25,2012.Piscataway,USA:IEEE,2012:1022-1033.

[16]Chudak F A,Williamson D P.Improved approximation algorithms for capacitated facility location problems[J].Mathematical Programming,2005,102:207-222.

[17]Kingsy G 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.

[18]Benoit A.Comparison of access policies for replica placement in tree networks[C]//LNCS 5704:Proceedings of the 15th International Conference on Parallel Processing,Delft, The Netherlands,Aug 25-28,2009.Berlin,Heidelberg: Springer,2009:253-264.

[19]Benoit A,Rehn V,Robert Y.Strategies for replica placement in tree networks[C]//Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium, Long Beach,USA,Mar 26-30,2007.Piscataway,USA:IEEE, 2007:1-15.

[20]Aupy G,Benoit A,Matthieu J,et al.Power-aware replica placement in tree networks with multiple servers per client[J]. Sustainable Computing:Informatics and Systems,2015,5: 41-53.

[21]Benoit A,Renaud-Goud P,Robert Y.Power-aware replica placement and update strategies in tree networks[C]//Proceedings of the 2011 IEEE International Parallel and Distributed Processing Symposium,Anchorage,USA,May 16-20,2011.Piscataway,USA:IEEE,2011:2-13.

LI Shuai was born in 1989.He is an M.S.candidate at Tianjin Polytechnic University.His research interest is data center.

李帥（1989—），男，江蘇贛榆人，天津工業(yè)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)中心。

DANG Xin was born in 1983.He received the Ph.D.degree in intelligence science from Shizuoka University in 2013.Now he is a lecturer at Tianjin Polytechnic University.His research interests include embedded system,high performance architecture and machine learning.

黨鑫（1983—），男，陜西合陽人，2013年于日本國立靜岡大學(xué)信息科學(xué)系獲得博士學(xué)位，現(xiàn)為天津工業(yè)大學(xué)講師，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)，高性能體系結(jié)構(gòu)，機(jī)器學(xué)習(xí)。

WANG Xu was born in 1989.She received the M.S.degree in computer technology from Tianjin Polytechnic University in 2015.Her research interests include high performance computing and data center.

王旭（1989—），女，山東城武人，2015年于天津工業(yè)大學(xué)計(jì)算機(jī)技術(shù)專業(yè)獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)楦咝阅苡?jì)算，數(shù)據(jù)中心。

WU Jigang was born in 1963.He received the Ph.D.degree from University of Science and Technology of China in 2000.Now he is a chair professor at Guangdong University of Technology.His research interests include theoretical computer science and high performance architecture.

武繼剛（1963—），男，江蘇沛縣人，2000年于中國科學(xué)技術(shù)大學(xué)獲得博士學(xué)位，現(xiàn)為廣東工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院特聘教授，主要研究領(lǐng)域?yàn)槔碚撚?jì)算機(jī)科學(xué)，高性能體系結(jié)構(gòu)。在國際重要學(xué)術(shù)期刊與會(huì)議上發(fā)表學(xué)術(shù)論文200余篇，主持國家自然科學(xué)基金課題、教育部博士點(diǎn)科研基金課題。

Replica Update Strategy andAlgorithms for Replica Placement?

LI Shuai1,DANG Xin1,WANG Xu1,WU Jigang2+
1.School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China
2.School of Computer Science and Technology,Guangdong University of Technology,Guangdong 510006,China
+Corresponding author:E-mail:asjgwucn@outlook.com

Replica technology is widely applied in cloud computing and distributed systems,the reasonable data replica placement is an important means to reduce the operation cost of network,and is also the key issue of replica technology. Replica update is that the replicas are added and deleted when data access requirements dynamically change.Based on multiple policy,this paper proposes a dynamic updating algorithm named MPFSF(min_placement far servers first)to solve the update problem.According to the need to implement the necessary replica update,this paper reuses as much as possible the pre-existing replicas and maximizes the capacity of each replica to reduce the date access latency and improve the efficiency of data access,by adding the constraint of communication distance.The experimental results show that,for the proposed algorithm with update policy,the running cost of the network gets a considerable reduction under the different distance limits,and the best improvement is up to 84.6%in comparison to the state-of-the-art.

tree network;replica placement;multiple policy;update

10.3778/j.issn.1673-9418.1507048

A

TP302

*The National Natural Science Foundation of China under Grant No.61403276(國家自然科學(xué)基金);the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20131201110002(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-09,http://www.cnki.net/kcms/detail/11.5602.TP.20151009.1542.004.html