曲明成，吳翔虎，張 銀，廖明宏，楊孝宗，左德承

(1.哈爾濱工業(yè)大學 計算機科學與技術學院，哈爾濱150001，qumingcheng@126.com;2.廈門大學 軟件學院，福建 廈門361005)

現(xiàn)有的針對存儲空間、計算能力和網(wǎng)絡帶寬的資源能力預留其主要解決方案為:通過在資源能力二維坐標空間中將一段時間內(nèi)的資源能力預留抽象為矩形區(qū)域，最為有效的方法為基于時間槽的資源能力預留法［1-4］，本文中稱其為二元法(REC).數(shù)據(jù)網(wǎng)格資源能力預留可以表示成存儲空間與時間的二元組，即＜StorageSpace，Time ＞，該資源能力同樣為矩形區(qū)域，所以StorageSpace與Time 為確定的數(shù)值.如圖1 所示，網(wǎng)格的存儲資源量總數(shù)為M，有兩個資源預留分別為R1(h1，t1)，R2(h2，t2)，在圖1 中分別為兩個矩形區(qū)域，而資源能力的大小為矩形區(qū)域的面積.

圖1 REC 法資源能力預留

REC 法在數(shù)據(jù)網(wǎng)格的資源能力預留中性能較差.比如:歐洲原子能數(shù)據(jù)網(wǎng)格是為原子能實驗特別設計的，其實驗時以10 M/s 的速度產(chǎn)生數(shù)據(jù)，并對其存儲，而后以1 M/s 的速度處理數(shù)據(jù)［5］.而在其他很多時候也存在同樣的問題，比如目前將數(shù)據(jù)網(wǎng)格與計算網(wǎng)格相結合，在計算前從數(shù)據(jù)網(wǎng)格中預留一定的存儲數(shù)據(jù)，將數(shù)據(jù)以一定的速度存儲到預留的空間，待計算條件具備時以一定的速度進行處理，并隨時刪除處理過的數(shù)據(jù)，釋放存儲空間［6］.為提升網(wǎng)絡的下載速度，很多副本部署方法也呈現(xiàn)同樣的特性［7-8］.

針對應用場景和存在的問題，將資源能力的預留表示成四元組R=＜VP，VC，H，t ＞，其中，VP 為數(shù)據(jù)生產(chǎn)速度，VC 為數(shù)據(jù)消耗速度，H 為存儲空間總需求量，t 為起始時間.這樣資源能力的預留將可以表示成圖2(a)，稱這種預留方法為四元法(TR).從圖2(b)中可以看出，如果使用REC法，這兩個資源能力預留是無法被同時接納的.顯然TR 使用的資源能力較REC 小很多，如此必可以提升資源能力的使用率、資源能力預留請求的接納率，同時可以減少資源能力碎片，從而提升數(shù)據(jù)數(shù)據(jù)網(wǎng)格資源能力預留的整體性能.

圖2 TR 資源能力預留與REC 的比較

1 基本階梯法(BTR)

1.1 基本定義

定義1(資源能力空間) 在二維坐標系中，以時間t 為橫坐標，數(shù)據(jù)網(wǎng)格的可用存儲空間h 為縱坐標，稱h=M(存儲空間總量)與h=0(橫坐標軸)圍成的無限空間為資源能力空間.

定義2(資源能力三角形，資源三角形) 令V0，V1分別為一次資源能力預留中數(shù)據(jù)的生產(chǎn)速度和消耗速度，總存儲空間需求為M(總數(shù)據(jù)量)，已知t0，V0，V1，M.則資源能力預留的幾何圖形可以表示為圖3(a)，其中V0，V1分別為三角形兩條邊的斜率，稱這樣的三角形為資源能力三角形.其中，t0為預留起始時刻，t1為達到預留量時刻，t2為空間使用完畢時刻.兩個不與t 坐標軸平行的邊的函數(shù)分別為h1=V0(t-t0)，h2=-V1(t-t2).

定義3(資源能力階梯三角形，階梯三角形) 如圖3(b)所示，將資源三角形以t1為界分割成兩個三角形，將區(qū)間(t0，t1)與(t1，t2)以時間單位r 進行分割，其分割的份數(shù)分別為n1和n2.對于左側三角形每個小區(qū)間的面積Sir =rV0(t1+ir-t0)，而令，右側三角形每個小區(qū)間的面積-rV0(t1+jr-t2)=rV0(t2-jr-t1)，令，令，稱由和構成的區(qū)域為資源能力階梯三角形.

圖3 資源能力三角形與階梯三角形

定義4(資源能力使用率) 定義一段時間內(nèi)所接納的資源能力預留的總和與該段時間時間內(nèi)資源能力空間大小的比值為資源能力使用率(U).令某個階梯三角形的大小為，REC 法資源能力大小為.其對應的為某段時間內(nèi)的資源能力空間大小.

1.2 公式推導

為了能夠有效地計算某個資源能力預留請求是否可以被接納，理想的情況下是資源能力空間在資源能力預留時刻處有足夠的空間可以容納下資源能力三角形(REC 法為矩形).給出ST，SR，UT，UR的求解過程，求解時參考圖3 進行幾何推導.

令時間單位長度為r，將t1-t0分成n1=份，則，并假設區(qū)間(t0，t1)，(t1，t2)之間有整數(shù)個單位時間間隔.t1，t2的求解為

由式(1)可以得出SR為

為了求解ST，需先求出S1′，S1″，由式(1)推出:，由此可以推出:

由定義4 和式(2)，式(4)得出

2 閾值階梯法(VTR)

由于網(wǎng)絡速度的動態(tài)變化，基本階梯法的資源能力預留存在一定的局限性(要求網(wǎng)絡速度平穩(wěn))，因此應為生產(chǎn)與消耗速度引入一定的速度變化區(qū)間.

定義5(可靠閾值ε) 生產(chǎn)與消耗速度實際中會存在偏差，在基本階梯法中引入速度偏差，即生產(chǎn)與消耗速度分別位于區(qū)間(V0-ε，V0+ε)與(V1-ε，V1+ε)中，稱ε 為可靠閾值.

定義6(閾值梯形) 在基本階梯法中引入可靠閾值后，即相當于在圖3(a)的幾何圖形上將非平行t 軸的兩條三角形邊的斜率分別±ε，而后形成的圖形為一個梯形，如圖4 中的由t0，t2，A，B 4 個點構成的圖形，稱其為閾值梯形.

圖4 閾值梯形圖

閾值梯形的面積為資源能力預留的數(shù)量，令其為ST′，其面積可以分解為3 部分，如圖5(a)，即三角形Δt0T1A(Sa)，矩形T1T1′AB(Sb)，三角形ΔT1′T2B(Sc).將3 個區(qū)域重新組合成圖5(b)，并對新的大三角形按照基本階梯法進行處理，同時根據(jù)圖4 進行推導:

根據(jù)式(4)和圖5(b)可以得出ST′=(Sa+Sc)+Sb，由此推出:

圖5 閾值梯形分解圖

定理1 由于為在基本解題法中引入可靠閾值后致使資源能力預留時間增加了Δt2=T2-t2，當V0-V1+ε ＞0 時，如果對REC 法進行t2可靠閾值擴展，其資源能力SR′增加量SR＞ST=ST′-ST.

證明:

因為V0-V1+ε ＞0，所以ΔST-ΔSR＞0，證畢.

定理1 說明，在時間增加相同的情況下針對REC 法進行可靠擴展的代價要大于閾值階梯法.

由式(2)，式(5)推出:

由式(7)，式(8)推出:

3 仿真實驗

令資源能力空間具有2 500 個時間單位，資源最大數(shù)量為4 000，在一次測試中，針對該段資源能力空間隨機的產(chǎn)生不同數(shù)量的資源能力預留請求.判斷某請求是否可以被接納的條件為:該請求的任意一個hi都能被其所對應的時間單位內(nèi)的資源能力空間所接納.實驗中將測試REC 法與BRTVTR 法的資源能力預留請求的接納率、資源的使用率，并對其進行對比分析.同時模擬速度動態(tài)變化，以檢測不同的ε 對已預留的資源能力使用失效的影響.

3.1 基本階梯法性能測試

在一定的資源能力空間中，對REC 法與BTR法接納率與資源能力使用率進行比較.從圖6 可以看出隨著請求數(shù)的增加兩種方法的接納率都成下降趨勢，但是BTR 法接納率明顯較REC 法的高.而從圖7 中可以看出，在接納率相同時BTR法的資源能力使用率明顯高于BTR 法.

圖6 不同資源能力請求REC 與BTR 接納率比較

3.2 閾值階梯法性能測試

在一定的資源能力空間中，當ε =0 時，對REC 法與VTR 法接納率與資源能力使用率進行比較.從圖8 可以看出隨著資源能力預留請求數(shù)的增加兩種方法的接納率都成下降趨勢，但是VTR 法接納率明顯較REC 法的高.而從圖9 中可以看出，在接納率相同時VTR 法的資源能力使用率明顯高于BTR 法.

圖7 相同接納率REC 與BTR 資源能力使用率比較

圖8 不同資源能力請求REC 與VTR 接納率比較

圖9 相同接納率REC 與VTR 資源能力使用率比較

3.3 綜合比較與預留失效檢測

令ε=0、5、10，觀測請求量與接納率的變化曲線，從圖10 中可以看出較小的ε 產(chǎn)生較高的接納率.令生產(chǎn)與消耗速度分別在(0.8 V，1.2 V)之間隨機的變化.在整個資源能力空間中，如果某個時間單位的實際資源能力需求量超出網(wǎng)格的資源總量那么算作一次失效，搜索請求量為600 時的失效時間單位數(shù)，并將總數(shù)與總的資源能力空間時間單位數(shù)進行比值，得出失效單位數(shù)f.針對不同ε 取值分別進行10 次實驗，取平均值，繪出柱形圖如圖11 所示，從圖11 中可以看到，當ε=4 時，f 已經(jīng)為0，效果較好.

圖10 ε 對VTR 接納率的影響

圖11 ε 對VTR 預留失效的影響

3.4 實驗小結

①采用BTR 與VTR 方法進行資源能力預留較傳統(tǒng)的REC 法有更好的性能;②隨著ε 的增加VTR 的性能逐漸降低;③在ε 達到合理的數(shù)值時預留失效可以降低為0;④采用合理的ε 值，可以大幅的提升資源能力預留請求的接納率和資源能力的使用率，并可以降低或消除預留失效.

4 結 論

1)提出了基本階梯法和閾值階梯法很好的實現(xiàn)了四元法預留策略，而閾值階梯法更能適應傳輸速度動態(tài)變化的網(wǎng)絡特性.

2)從實驗可以看出:與二元法相比四元法能夠有效降低資源能力碎片，提升存儲空間的使用率，進而提高資源能力預留的接納率和網(wǎng)格系統(tǒng)的整體吞吐量.

［1］BURCHARD L O.On the performance of computer networks with advance reservation mechanisms［C］//Proceedings of the 11thIEEE Intl.Conference on Networks(ICON’03).Washington:IEEE Computer Society，2003:449-454.

［2］HU Chunming，HUAI Jinpeng，WO Tianyu.Flexible resource reservation using slack time for service grid［C］//Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS′06).Washington:IEEE Computer Society，2006:327-334.

［3］胡春明，懷進鵬，沃天宇.一種基于松弛時間的服務網(wǎng)格資源能力預留機制［J］.計算機研究與發(fā)展，2007，44(1):20-28.

［4］XIAO Peng，HU Zhigang，LI Xi，et al.A novel statistic-based relaxed grid resource reservation strategy［C］//Proceedings of the 9th International Conference for Young Computer Scientists.Washington:IEEE Computer Society，2008:703-707.

［5］Large Scale System Configuration Workshop.CERN and the DataGrid Project［EB/OL］.http://homepages.inf.ed.ac.uk/group/lssconf/files2001/datagrid-edinburgh.pdf.

［6］MCCLATCHEY R，ANJUM A，STOCKINGER H，et al.Data intensive and network aware (diana)grid scheduling［J］.Journal of Grid Computing，2007，5(1):43-64.

［7］SHI Ke.A replication and cache based distributed metadata management system for data grid［C］//Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing.Washington:IEEE Computer Society，2007:20-25.

［8］YUAN Yulai，WU Yongwei，YANG Guangwen，et al.Dynamic data replication based on local optimization principle in data grid［C］//The 6th International Conference on Grid and Cooperative Computing(GCC 2007).Washington:IEEE Computer Society，2007:815-822.