內(nèi)容分塊數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移

揭水平,李泳成

(1.蘇州大學(xué) 電子信息學(xué)院,江蘇 蘇州 215006; 2.中天寬帶技術(shù)有限公司,江蘇 南通 226000)

0 引 言

數(shù)據(jù)中心光網(wǎng)絡(luò)中每個數(shù)據(jù)中心都存儲了用戶大量的重要數(shù)據(jù),一旦受到自然或人為災(zāi)難(例如地震、臺風(fēng)和戰(zhàn)爭等)影響,將造成重要數(shù)據(jù)的永久丟失。為避免這種情況發(fā)生,數(shù)據(jù)中心光網(wǎng)絡(luò)通常采用高效的內(nèi)容備份策略,如內(nèi)容復(fù)制(Content Replication,CR)[1]和內(nèi)容分塊(Content Fragmentation,CF)[2]。高效的內(nèi)容備份策略能確保單個數(shù)據(jù)中心發(fā)生故障后數(shù)據(jù)中心光網(wǎng)絡(luò)中存儲的數(shù)據(jù)被恢復(fù)[3]。然而,發(fā)生大范圍災(zāi)難時,多個數(shù)據(jù)中心同時毀壞,內(nèi)容備份無法保證所有內(nèi)容都被恢復(fù),必須轉(zhuǎn)移災(zāi)難區(qū)域內(nèi)存儲的部分?jǐn)?shù)據(jù)[4]。由于數(shù)據(jù)中心中存儲了海量數(shù)據(jù),其需要轉(zhuǎn)移的數(shù)據(jù)量為TB級甚至PB級。因此,如何對多個數(shù)據(jù)中心的大量數(shù)據(jù)在短時間內(nèi)進行快速數(shù)據(jù)轉(zhuǎn)移是一個具有挑戰(zhàn)性的問題。Ferdousi等人雖然針對CR數(shù)據(jù)中心光網(wǎng)絡(luò)提出了一種數(shù)據(jù)轉(zhuǎn)移算法[5],但目前并沒有針對更為復(fù)雜的CF數(shù)據(jù)中心光網(wǎng)絡(luò)數(shù)據(jù)快速轉(zhuǎn)移問題的相關(guān)研究。

本文對CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移問題展開研究,首次針對該問題進行了問題描述,構(gòu)建了混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)模型且為大規(guī)模網(wǎng)絡(luò)也提出了一種高效的最小時延(Least Delay,LD)快速數(shù)據(jù)轉(zhuǎn)移算法(簡稱LD算法)。仿真結(jié)果表明,LD算法性能與MILP模型接近,證明了其高效性。其次,本文也首次從災(zāi)前數(shù)據(jù)轉(zhuǎn)移性能的角度評估了CF與CR策略的性能差異。仿真結(jié)果表明,相同數(shù)據(jù)冗余度情況下(都為100%),采用LD算法的CF數(shù)據(jù)中心光網(wǎng)絡(luò)比CR數(shù)據(jù)中心光網(wǎng)絡(luò)最多節(jié)省42%的數(shù)據(jù)轉(zhuǎn)移時間。

1 CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移問題

CR策略是復(fù)制出x個備份,然后將所有的x+1份相同內(nèi)容存儲在不同的數(shù)據(jù)中心。該策略的優(yōu)點是只有當(dāng)所有x+1份內(nèi)容都被災(zāi)難損毀時內(nèi)容才會丟失；缺點是數(shù)據(jù)冗余度非常高(≥100%),嚴(yán)重降低了存儲資源的利用率。為降低數(shù)據(jù)冗余度,一種擁有更高存儲資源利用率的CF策略被提出。該策略使用(k,r)擦除編碼,首先將一個大小為F GB的內(nèi)容平均拆分為k個內(nèi)容塊,每個內(nèi)容塊的大小為F/k GB；然后,再額外添加r(r＜k)個大小為F/k GB的奇偶校驗塊,最終形成k+r個數(shù)據(jù)塊。CF策略允許在k+r個數(shù)據(jù)塊中≤r個數(shù)據(jù)塊丟失的情況下,整個內(nèi)容仍可被恢復(fù),因此其數(shù)據(jù)冗余度為r/k＜100%。本文中的CF策略采用了具有較小編碼開銷的Reed-Solomon(RS)擦除編碼[6]。大范圍災(zāi)難發(fā)生前,一旦某個內(nèi)容中有ψ(ψ＞r)個數(shù)據(jù)塊在災(zāi)難區(qū)域中,為保證內(nèi)容不丟失,則需將ψ-r個數(shù)據(jù)塊從受災(zāi)區(qū)域轉(zhuǎn)移到安全的數(shù)據(jù)中心中存儲。

1.1 CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移實例

圖1所示為一個CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移實例。假設(shè)該CF策略采用RS(5,2)編碼將內(nèi)容分成了5個內(nèi)容塊和2個奇偶校驗塊共7個數(shù)據(jù)塊(即k=5,r=2),并將其存儲在各個節(jié)點(N2、N3、N4和N5)的數(shù)據(jù)中心中。具體的,節(jié)點N2、N3和N5都存儲了2個數(shù)據(jù)塊,節(jié)點N4存儲了1個數(shù)據(jù)塊。假設(shè)M區(qū)域即將發(fā)生大范圍災(zāi)難,節(jié)點N2和N3將被損毀。這兩個數(shù)據(jù)中心存儲的ψ=4個數(shù)據(jù)塊即將丟失。因此,最少需要轉(zhuǎn)移ψ-r=2個數(shù)據(jù)塊。現(xiàn)有兩種數(shù)據(jù)轉(zhuǎn)移方案S1和S2。方案S1將數(shù)據(jù)塊4沿路徑N2-N1-N5轉(zhuǎn)移至數(shù)據(jù)中心N5,轉(zhuǎn)移時間為3 s；將數(shù)據(jù)塊6沿路徑N2-N1-N4轉(zhuǎn)移至數(shù)據(jù)中心N4。由于共享鏈路N2-N1,數(shù)據(jù)塊6需要等到數(shù)據(jù)塊4轉(zhuǎn)移完成后再進行轉(zhuǎn)移。因此,方案S1所需的轉(zhuǎn)移時間為6 s。方案S2則將數(shù)據(jù)塊4沿路徑N2-N1-N5轉(zhuǎn)移至N5,數(shù)據(jù)塊7沿路徑N3-N4轉(zhuǎn)移至數(shù)據(jù)中心N4,總轉(zhuǎn)移時間為4 s。方案S2比S1節(jié)省了33%的轉(zhuǎn)移時間。

圖1 CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移實例

1.2 問題描述

給定一個數(shù)據(jù)中心光網(wǎng)絡(luò)G(N,L,D,C)。其中,N為節(jié)點的集合；L為鏈路的集合；D為數(shù)據(jù)中心的集合；C為存儲內(nèi)容的集合；αc為內(nèi)容c的重要性權(quán)重。假設(shè)一個大范圍災(zāi)難即將影響區(qū)域M,Din為M內(nèi)數(shù)據(jù)中心集合,Do為M外數(shù)據(jù)中心集合。CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移問題的目標(biāo)是在恢復(fù)所有內(nèi)容的前提下,最小化數(shù)據(jù)轉(zhuǎn)移時間。

本文考慮多個約束條件,包括:(1)通過轉(zhuǎn)移,所有內(nèi)容都被恢復(fù)；(2)每一個數(shù)據(jù)塊有且只有一條轉(zhuǎn)移路徑；(3)重要性權(quán)重高的內(nèi)容先完成轉(zhuǎn)移；(4)數(shù)據(jù)中心光網(wǎng)絡(luò)中每條鏈路上帶寬資源有限；(5)任意兩個數(shù)據(jù)塊轉(zhuǎn)移路徑重疊時,其轉(zhuǎn)移時間不重疊；(6)每個數(shù)據(jù)中心存儲資源有限；(7)節(jié)點之間采用鏈路不相交的k-shortest算法搜索k條最短路由。

2 MILP模型

基于上節(jié)的問題描述,我們構(gòu)建了一個MILP模型,其集合、參數(shù)、變量和優(yōu)化目標(biāo)定義如下。

集合:

G(N,L,D,C) 網(wǎng)絡(luò)拓?fù)洹?/p>

Pd,sd、s兩節(jié)點間k條最短路徑的集合,d,s∈D:d≠s。

DinM內(nèi)數(shù)據(jù)中心集合。

DoM外數(shù)據(jù)中心集合。

Gc內(nèi)容c在M內(nèi)存儲的數(shù)據(jù)塊集合。

Pd節(jié)點d到安全數(shù)據(jù)中心路徑集合∪s∈DoPd,s。

參數(shù):

αc整數(shù),內(nèi)容c的重要性權(quán)重值。

Bp整數(shù),路徑p的可用傳輸容量。

N 內(nèi)容c數(shù)據(jù)塊總數(shù)。

r 內(nèi)容c需轉(zhuǎn)移數(shù)據(jù)塊總數(shù)。c

Sd/Gb yte 數(shù)據(jù)中心d可用存儲資源。

Δ 一個極大值。

變量:

T 整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間。

優(yōu)化目標(biāo):最小化T。

約束條件:

內(nèi)容c轉(zhuǎn)移數(shù)據(jù)塊總數(shù)達到恢復(fù)要求。

內(nèi)容c第k個數(shù)據(jù)塊沿路徑p轉(zhuǎn)移的傳輸時間。

內(nèi)容c第k個數(shù)據(jù)塊沿路徑p轉(zhuǎn)移的結(jié)束時間。

計算內(nèi)容c轉(zhuǎn)移的開始時間,該時間不大于內(nèi)容c任意一個數(shù)據(jù)塊轉(zhuǎn)移的開始時間。

計算內(nèi)容c轉(zhuǎn)移的結(jié)束時間,該時間不小于內(nèi)容c任意一個數(shù)據(jù)塊轉(zhuǎn)移的結(jié)束時間。

內(nèi)容c數(shù)據(jù)塊轉(zhuǎn)移路徑共享鏈路時,確保這些數(shù)據(jù)塊轉(zhuǎn)移時間不重疊。

重要性高的內(nèi)容優(yōu)先轉(zhuǎn)移。

重要性相同的內(nèi)容,內(nèi)容數(shù)據(jù)塊使用相同鏈路轉(zhuǎn)移時,確保內(nèi)容轉(zhuǎn)移時間不重疊。

數(shù)據(jù)中心存儲的數(shù)據(jù)不能超過其存儲資源限制。

計算整個網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)移時間。

整個網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)移時間大于所有內(nèi)容的傳輸時間之和(冗余公式加快模型求解速度)。

3 LD算法

雖然MILP模型能找到問題的最優(yōu)解,但受限于其高計算復(fù)雜度,無法為大規(guī)模網(wǎng)絡(luò)在有限時間內(nèi)獲得最優(yōu)解。目前,并沒有專門針對CF數(shù)據(jù)中心光網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移的算法。由于既要選擇轉(zhuǎn)移的數(shù)據(jù)塊,又要選擇轉(zhuǎn)移路徑,整個問題變得更加復(fù)雜。本文為CF數(shù)據(jù)中心光網(wǎng)絡(luò)提出一種LD算法,該算法主要分為兩部分,轉(zhuǎn)移內(nèi)容的選擇和轉(zhuǎn)移數(shù)據(jù)塊及轉(zhuǎn)移路徑的選擇。

3.1 轉(zhuǎn)移內(nèi)容的選擇

遍歷各個數(shù)據(jù)中心存儲的所有內(nèi)容,一旦某個內(nèi)容在災(zāi)難區(qū)域內(nèi)存儲的內(nèi)容塊總數(shù)超過r,則將其加入到轉(zhuǎn)移內(nèi)容集合CEva。遍歷完所有內(nèi)容后,將集合CEva中的內(nèi)容按照其重要性權(quán)重值αc由大到小排列。

3.2 轉(zhuǎn)移數(shù)據(jù)塊與轉(zhuǎn)移路徑的選擇

針對獲取的集合CEva,該啟發(fā)式算法將進一步為每個內(nèi)容選擇轉(zhuǎn)移的數(shù)據(jù)塊及每個轉(zhuǎn)移數(shù)據(jù)塊的轉(zhuǎn)移路徑。具體步驟如下:

End for

對于內(nèi)容c,遍歷其在災(zāi)難區(qū)域內(nèi)存儲的數(shù)據(jù)塊集合Gc,對其中每一個數(shù)據(jù)塊分別計算所有可能轉(zhuǎn)移路徑的轉(zhuǎn)移時間,并計算LD(即每個數(shù)據(jù)塊結(jié)束轉(zhuǎn)移的時間)。比較每一個數(shù)據(jù)塊的LD,選擇具有最小LD的數(shù)據(jù)塊k*進行轉(zhuǎn)移。從Gc中移除已轉(zhuǎn)移的數(shù)據(jù)塊k*,若轉(zhuǎn)移的數(shù)據(jù)不足以恢復(fù)內(nèi)容c,則重復(fù)以上步驟,否則選擇下一個內(nèi)容進行轉(zhuǎn)移。當(dāng)所有內(nèi)容完成轉(zhuǎn)移時,獲取整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間T。

圖2 測試網(wǎng)絡(luò)拓?fù)鋱D

4 結(jié)果與性能分析

4.1 測試條件

為評估所提算法的性能,我們考慮了如圖2所示的兩個測試網(wǎng)絡(luò),圖2(a)為具有6個節(jié)點、8條鏈路和6個數(shù)據(jù)中心的n6s8網(wǎng)絡(luò),圖2(b)為具有24個節(jié)點、43條鏈路和8個數(shù)據(jù)中心的USNET網(wǎng)絡(luò)。假設(shè)一個大范圍災(zāi)難將分別影響n6s8網(wǎng)絡(luò)中的節(jié)點1和2以及USNET網(wǎng)絡(luò)中的節(jié)點6、9和12。每個數(shù)據(jù)中心可用存儲資源在10～100 TB范圍內(nèi)均勻分布,且平均占用率為40%(剩余60%可用于存儲轉(zhuǎn)移內(nèi)容塊)。網(wǎng)絡(luò)中每個鏈路上的傳輸容量在500 Gbit/s～1 Tbit/s范圍內(nèi),其中30%用于傳輸數(shù)據(jù)中心間正常的業(yè)務(wù)(剩余70%可以用于數(shù)據(jù)轉(zhuǎn)移)。假設(shè)數(shù)據(jù)中心存儲的每個內(nèi)容的大小在200～500 GB范圍內(nèi)均勻分布。這里的單個內(nèi)容都是由許多較小的內(nèi)容聚合而成。每個內(nèi)容的重要性因子從1～10分成10個等級,因子越大,重要性越高。在MILP模型中,我們采用了K條最短路徑搜索算法為每個節(jié)點對找到了3條最短路徑作為候選路徑。通過商用軟件AMPL/Gurobi[7](版本5.6.2)求解MILP模型,模型的MIPGAP(Relative MIP Optimality Gap)設(shè)置為1%。啟發(fā)式算法使用JAVA進行仿真。

4.2 整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間

圖3比較了MILP模型與LD算法的整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間。其中,數(shù)據(jù)中心光網(wǎng)絡(luò)采用基于RS(4,2)編碼的CF策略進行內(nèi)容備份。

圖3 整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間

由圖可知,在兩個測試網(wǎng)例的結(jié)果中,MILP模型所需的整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間較短,LD算法的結(jié)果與MILP模型結(jié)果總是非常接近。其次,隨著整個網(wǎng)絡(luò)存儲內(nèi)容總數(shù)的增加,MILP模型和LD算法所需的整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間越來越大。這是因為整個網(wǎng)絡(luò)存儲內(nèi)容總數(shù)的增加將導(dǎo)致需要進行數(shù)據(jù)轉(zhuǎn)移的內(nèi)容增加,從而增加了整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移的時間。最后,在USNET網(wǎng)絡(luò)中,MILP模型和LD算法所需的整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間都少于n6s8網(wǎng)絡(luò)。這是因為USNET網(wǎng)絡(luò)的平均節(jié)點維度高于n6s8網(wǎng)絡(luò),能為轉(zhuǎn)移的數(shù)據(jù)提供更多的可選路徑。

4.3 CF vs CR

本文也比較了CF和CR策略在轉(zhuǎn)移內(nèi)容數(shù)據(jù)總量和數(shù)據(jù)轉(zhuǎn)移時間方面的性能差異。圖4給出了在USNET網(wǎng)絡(luò)中,兩種策略需要轉(zhuǎn)移的內(nèi)容數(shù)據(jù)總量。圖中每個點為基于6個隨機種子仿真結(jié)果的平均值。CF分別采用了RS(2,2)、RS(3,2)和RS(4,2)3種編碼方式,數(shù)據(jù)冗余度分別為100%、67%和50%。CR為每個內(nèi)容都復(fù)制了一個備份(即x=1),數(shù)據(jù)冗余度為100%。

由圖可知,隨著整個網(wǎng)絡(luò)存儲內(nèi)容總數(shù)的增加,兩種策略需要轉(zhuǎn)移的內(nèi)容數(shù)據(jù)總量也不斷增加。這也是由于整個網(wǎng)絡(luò)存儲內(nèi)容總數(shù)的增加將導(dǎo)致需要進行數(shù)據(jù)轉(zhuǎn)移的內(nèi)容增加。我們發(fā)現(xiàn),當(dāng)k值增大時(即數(shù)據(jù)冗余度降低),其需轉(zhuǎn)移的內(nèi)容數(shù)據(jù)總量也將變大。這是因為更低的數(shù)據(jù)冗余度使得內(nèi)容無法恢復(fù)的概率更大,需要進行數(shù)據(jù)轉(zhuǎn)移的內(nèi)容變得更多。在相同數(shù)據(jù)冗余度下(都為100%),CF所需轉(zhuǎn)移的數(shù)據(jù)與CR相比最多節(jié)省了34%。

圖5所示為兩種內(nèi)容備份策略的整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間。CF采用了LD算法,CR采用了文獻[5]中的算法。由圖可知,當(dāng)數(shù)據(jù)冗余度都為100%時,CF數(shù)據(jù)中心光網(wǎng)絡(luò)比CR數(shù)據(jù)中心光網(wǎng)絡(luò)最多節(jié)省42%的數(shù)據(jù)轉(zhuǎn)移時間；當(dāng)數(shù)據(jù)冗余度為67%時,CF數(shù)據(jù)中心光網(wǎng)絡(luò)依然可以比100%數(shù)據(jù)冗余度的CR數(shù)據(jù)中心光網(wǎng)絡(luò)更快完成數(shù)據(jù)轉(zhuǎn)移；當(dāng)數(shù)據(jù)冗余度為50%時,CF數(shù)據(jù)中心光網(wǎng)絡(luò)與CR數(shù)據(jù)中心光網(wǎng)絡(luò)相比,無法總是獲得更低的數(shù)據(jù)轉(zhuǎn)移時間,這與其需要轉(zhuǎn)移的數(shù)據(jù)總量過大有關(guān)。

圖4 CF和CR策略中需要轉(zhuǎn)移的內(nèi)容數(shù)據(jù)總量

圖5 CF和CR策略中整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間

5 結(jié)束語

本文針對CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移問題展開了研究。以最小化整個網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時間為目標(biāo),構(gòu)建了一個MILP模型并提出了一種LD算法。仿真結(jié)果表明,LD算法與MILP模型的最優(yōu)解非常接近。同時,我們也比較了CF和CR策略在災(zāi)前數(shù)據(jù)轉(zhuǎn)移方面的性能。結(jié)果表明,數(shù)據(jù)冗余度都為100%時,采用LD算法的CF數(shù)據(jù)中心光網(wǎng)絡(luò)比CR數(shù)據(jù)中心光網(wǎng)絡(luò)最多節(jié)省42%的數(shù)據(jù)轉(zhuǎn)移時間。