揭水平,李泳成

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

0 引 言

數(shù)據(jù)中心光網(wǎng)絡(luò)中每個(gè)數(shù)據(jù)中心都存儲(chǔ)了用戶大量的重要數(shù)據(jù),一旦受到自然或人為災(zāi)難(例如地震、臺(tá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)容備份策略能確保單個(gè)數(shù)據(jù)中心發(fā)生故障后數(shù)據(jù)中心光網(wǎng)絡(luò)中存儲(chǔ)的數(shù)據(jù)被恢復(fù)[3]。然而,發(fā)生大范圍災(zāi)難時(shí),多個(gè)數(shù)據(jù)中心同時(shí)毀壞,內(nèi)容備份無法保證所有內(nèi)容都被恢復(fù),必須轉(zhuǎn)移災(zāi)難區(qū)域內(nèi)存儲(chǔ)的部分?jǐn)?shù)據(jù)[4]。由于數(shù)據(jù)中心中存儲(chǔ)了海量數(shù)據(jù),其需要轉(zhuǎn)移的數(shù)據(jù)量為TB級(jí)甚至PB級(jí)。因此,如何對(duì)多個(gè)數(shù)據(jù)中心的大量數(shù)據(jù)在短時(shí)間內(nèi)進(jìn)行快速數(shù)據(jù)轉(zhuǎn)移是一個(gè)具有挑戰(zhàn)性的問題。Ferdousi等人雖然針對(duì)CR數(shù)據(jù)中心光網(wǎng)絡(luò)提出了一種數(shù)據(jù)轉(zhuǎn)移算法[5],但目前并沒有針對(duì)更為復(fù)雜的CF數(shù)據(jù)中心光網(wǎng)絡(luò)數(shù)據(jù)快速轉(zhuǎn)移問題的相關(guān)研究。

本文對(duì)CF數(shù)據(jù)中心光網(wǎng)絡(luò)災(zāi)前數(shù)據(jù)轉(zhuǎn)移問題展開研究,首次針對(duì)該問題進(jìn)行了問題描述,構(gòu)建了混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)模型且為大規(guī)模網(wǎng)絡(luò)也提出了一種高效的最小時(shí)延(Least Delay,LD)快速數(shù)據(jù)轉(zhuǎn)移算法(簡稱LD算法)。仿真結(jié)果表明,LD算法性能與MILP模型接近,證明了其高效性。其次,本文也首次從災(zāi)前數(shù)據(jù)轉(zhuǎn)移性能的角度評(píng)估了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)移時(shí)間。

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

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

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

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

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

1.2 問題描述

給定一個(gè)數(shù)據(jù)中心光網(wǎng)絡(luò)G(N,L,D,C)。其中,N為節(jié)點(diǎn)的集合；L為鏈路的集合；D為數(shù)據(jù)中心的集合；C為存儲(chǔ)內(nèi)容的集合；αc為內(nèi)容c的重要性權(quán)重。假設(shè)一個(gè)大范圍災(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)移時(shí)間。

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

2 MILP模型

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

集合:

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

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

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

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

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

Pd節(jié)點(diǎn)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可用存儲(chǔ)資源。

Δ 一個(gè)極大值。

變量:

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

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

約束條件:

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

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

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

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

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

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

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

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

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

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

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

3 LD算法

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

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

遍歷各個(gè)數(shù)據(jù)中心存儲(chǔ)的所有內(nèi)容,一旦某個(gè)內(nèi)容在災(zāi)難區(qū)域內(nèi)存儲(chǔ)的內(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)移路徑的選擇

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

End for

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

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

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

4.1 測試條件

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

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

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

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

由圖可知,在兩個(gè)測試網(wǎng)例的結(jié)果中,MILP模型所需的整個(gè)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時(shí)間較短,LD算法的結(jié)果與MILP模型結(jié)果總是非常接近。其次,隨著整個(gè)網(wǎng)絡(luò)存儲(chǔ)內(nèi)容總數(shù)的增加,MILP模型和LD算法所需的整個(gè)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時(shí)間越來越大。這是因?yàn)檎麄€(gè)網(wǎng)絡(luò)存儲(chǔ)內(nèi)容總數(shù)的增加將導(dǎo)致需要進(jìn)行數(shù)據(jù)轉(zhuǎn)移的內(nèi)容增加,從而增加了整個(gè)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移的時(shí)間。最后,在USNET網(wǎng)絡(luò)中,MILP模型和LD算法所需的整個(gè)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)移時(shí)間都少于n6s8網(wǎng)絡(luò)。這是因?yàn)閁SNET網(wǎng)絡(luò)的平均節(jié)點(diǎn)維度高于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)移時(shí)間方面的性能差異。圖4給出了在USNET網(wǎng)絡(luò)中,兩種策略需要轉(zhuǎn)移的內(nèi)容數(shù)據(jù)總量。圖中每個(gè)點(diǎn)為基于6個(gè)隨機(jī)種子仿真結(jié)果的平均值。CF分別采用了RS(2,2)、RS(3,2)和RS(4,2)3種編碼方式,數(shù)據(jù)冗余度分別為100%、67%和50%。CR為每個(gè)內(nèi)容都復(fù)制了一個(gè)備份(即x=1),數(shù)據(jù)冗余度為100%。

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

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

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

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

5 結(jié)束語

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