網(wǎng)格服務建模分析

1、2006年第 23卷第 10期 微電子學與計算機 1引言在網(wǎng)格環(huán)境下 , 服務動態(tài)地分布在異構(gòu)的廣域網(wǎng)中 , 對服務的透明訪問與管理構(gòu)成了網(wǎng)格研究的 一個重要內(nèi)容 。 各種資源動態(tài)加入網(wǎng)格系統(tǒng) , 它們 可以隨時中止服務 , 從網(wǎng)格中退出 ; 資源是分布在 各種異構(gòu)的系統(tǒng)中 , 故動態(tài)性與異構(gòu)性是網(wǎng)格建模 中的重要考慮因素 。 文獻 1提出了基于協(xié)議的五 層沙漏模型的網(wǎng)格體系結(jié)構(gòu) , 基于此思想 , Globus 項目組開發(fā)了相應的工具包 GT2, GT2中的 MDS2實現(xiàn)了資源的監(jiān)測和發(fā)現(xiàn) 。 隨著網(wǎng)格技術(shù)逐漸向工 業(yè) 標 準 靠 攏 , 文 獻 2提 出 了 以 服 務 為 中 心 的 網(wǎng)

2、 格 體 系 結(jié) 構(gòu) OGSA , Globus 項 目 組 隨 后 推 出 了 基 于OGSA 的工具包 GT4, GT4中的服務的監(jiān)測與發(fā)現(xiàn) 由 MDS4實現(xiàn) 。 雖然 MDS2和 MDS4實現(xiàn)了資源和服務的發(fā)現(xiàn)與監(jiān)測 , 但是關(guān)于服務的性能評價與分 析沒有進行深入研究 。 文獻 35主要研究了網(wǎng)格 環(huán)境下資源管理和調(diào)度模型 , 但是沒有考慮到資源 的動態(tài)性 , 文獻 6研究了資源狀態(tài)變化時 (資源故 障或主動退出虛擬組織 網(wǎng)格服務的建模 , 但是其 研究建立在集中調(diào)度的基礎(chǔ)上 。 基于以上研究工作 , 本文擬討論在網(wǎng)格環(huán)境中 , 分層管理模式下的 服務建模問題 。2集中調(diào)度模型文獻 6將

3、集中調(diào)度下的網(wǎng)格服務建模成強度為 的泊松分布 , 到達虛擬組織的作業(yè)被以概率 q 1,q 2, , q N 分發(fā)到各資源 。 在此基礎(chǔ)上推導出了資源隊列長度有限并且當資源發(fā)生故障時 , 調(diào)度中心在 獲得資源故障信息存在延時的情況下 , 作業(yè)丟包率 的穩(wěn)態(tài)概率 。該模型的優(yōu)點在于 , 可以獲得各個資源的利用 率 , 同時可以通過合理的調(diào)度算法 , 提高資源的利 用率 , Condor-G , Nimrod/G 等系統(tǒng)就可以用 該 模 型 來描述 。 但是存在的問題在于 , 當調(diào)度中心發(fā)生故 障時 , 整個系統(tǒng)將會無法正常工作 。與集中調(diào)度不同的調(diào)度方式是分布式調(diào)度 , 目 前一些 P2P 系統(tǒng)采

4、用了這種調(diào)度方法 , 其具體過程 如下 :當某個資源不能完成提交到其上的作業(yè)請求 時 , 就以廣播的方式向其周圍資源查詢是否能完成 該作業(yè) , 并在該作業(yè)上設置一個有效時間 , 如果發(fā) 現(xiàn)可以滿足該作業(yè)要求的資源時 , 則將該作業(yè)提交 到其上 , 否則 , 這些資源又繼續(xù)在它們周圍的資源 查找 , 直到找到合適的資源或者該作業(yè)的有效時間收稿日期 :2006-05-24基金項目 :中國博士后科學基金項目 (2003034155211工程十五建設項目 (CERS-219899004網(wǎng)格服務建模分析殷 杰王躍宣 吳 澄(清華大學 自動化系 國家 CIMS 工程技術(shù)研究中心 , 北京 100084摘要

5、 :在網(wǎng)格環(huán)境下 , 資源以服務的形式共享 。 針對虛擬組織內(nèi)網(wǎng)格服務的動態(tài)性和廣域性 , 分析了網(wǎng)格服務的特點 , 指出了網(wǎng)格服務建模需要著重考慮的因素 , 并建立了其相應的數(shù)學模型 , 對其進行了初步分析 , 對若干個 小規(guī)模虛擬組織組成的網(wǎng)格系統(tǒng)進行了仿真實驗 , 實驗結(jié)果驗證了模型的合理性 。 關(guān)鍵詞 :網(wǎng)格 , 服務 , 虛擬組織 , 建模 中圖分類號 :TP393.1文獻標識碼 :A文章編號 :1000-7180(2006 10-0015-03Modeling and Analyzing of Grid ServiceYIN Jie, WANG Yue-xuan, WU Cheng

6、(National CIMS Engineering Research Center, Department of Automation, Tsinghua University, Beijing 100084Abstract:In grid, all resources are shared in the form of services. The dynamic characteristic and scalability of grid isintroduced and analyzed, especially the important factors in modeling grid

7、 service. A related mathematical model is giv-en here with preliminary analyses. The experiment in a small scale grid system with several VO, each consists of some resources as the service providers, validates the model provided in this paper. Key words:Grid, Service, Virtual organization, Modeling1

8、5微電子學與計算機 2006年第 23卷第 10期過期為止 。這種調(diào)度方法的優(yōu)點在于不存在單點失效問 題 , 但缺點在于資源組織分散 , 不利于管理 ; 資源的 利用不平衡 ; 當資源動態(tài)變化時 , 必須通知所有的 相關(guān)資源 ; 并且其資源查找方式多為廣播式的 , 占 用大量帶寬 。3混合調(diào)度模型網(wǎng)格上的服務 , 綜合安全與查找效率的平衡 ,可以采用分層管理模式 。 在這種模式下 , 資源組織 成虛擬組織 (VO , VO 又組織成更高層次的 VO , VO 內(nèi)部采用集中調(diào)度的方式 , VO 分布于整個廣域網(wǎng) 內(nèi) , VO 之間信息交互與任務調(diào)度是分布的 。 提交到 虛擬組織上的作業(yè)都是在具體

9、的資源上完成的 , 故 提交到某 VO 上的作業(yè) , 可能被分配到直接歸屬于 該 VO 的資源上 , 也可能分配到其子 VO 上 , 再由子VO 在內(nèi)部再次分配 。 但從提供服務角度看 , 父 VO和子 VO 是平等的 。圖 1是基于分層管理模式下的混合調(diào)度模型 , 它將虛擬組織之間作業(yè)遷移的分布式調(diào)度與虛擬 組織內(nèi)部的集中調(diào)度綜合在一起 。 由于在作業(yè)調(diào)度 上 , 父 VO 與子 VO 是平等的 , 這種平等性在圖 1中 表示為 VO 之間無差異的作業(yè)遷移 。 圖 1中各 VO 之間是協(xié)作的 , 設提交到各 VO 的作業(yè)服從強度為 i (i , 為網(wǎng)格中 VO 的集 合 的泊松分布 , p

10、A L 表示一個提交到 VO A 中作業(yè)由 于各種原因遷移到 VO L 中的概率 。 VO 與其子 VO 的關(guān)系主要體現(xiàn)在 VO 之間的遷移概率的大小上 , 非常明顯 , 一個父 VO 向其子 VO 的作業(yè)遷移概率 要大于其它 VO 。 q i1, q i2, , q iN i (i , 為網(wǎng)格中VO 的集合 ; N i 表示 VO i 內(nèi)的資源數(shù) 表示當一個作 業(yè)到達 VO i 后 , 分配到各資源上的概率 。 q i1, q i2, , q iN i 可以是事先約定的常數(shù) , 也可以是隨著各服務提供者的隊列長度與利用率 , 而動態(tài)進行調(diào)整 。 但需 要滿足式 (1 約束 :T ij =1

11、p ij+N ik =1 q ik=1(i (1式 中 , T i 表 示 VO i 可 以 將 作 業(yè) 轉(zhuǎn) 移 到 其 上 的VO 數(shù) , 表現(xiàn)在圖 1上就是 VO 的出度 (箭頭從該 VO 發(fā)出的虛線的數(shù)量 , 如 VO A 的 T A 是 2, VO L 的 T L 是 1; N i 表示 VO i 內(nèi)的資源數(shù)量 。 從式 (1 可以看 出 , 當對于某 VO , 其出度為零時 , 式 (1 可簡化成 :N ik =1 q ik=1(i (2于是該模型就回歸成了文獻 6的形式 , 也就是 整個網(wǎng)格系統(tǒng)變成了一個個的服務孤島 。下面考慮一種特殊情況 , 當各 VO 的泊松流強 度 相同時

12、, 并且由 p ij 組成的矩陣 P 是對稱矩陣 ,p ij 表示從 VO i 向 VO j 的作業(yè)遷移概率 , 則在滿足此條件下 , 各 VO 的服務隊列可以當作 M/M/1來 處 理 , 文獻 6中的一些結(jié)論也就適用于本模型 。 4仿真研究以下通過實驗 , 來驗證本模型的合理性 。 圖 2給出了當各 VO 的泊松流強度 不相同 , 且 p ij 組成 的矩陣不對稱的網(wǎng)格拓撲結(jié)構(gòu) 。 其中 , VO2是 VO1的子 VO , VO4是 VO3的子 VO 。 圖 3給出了圖 2所 示拓撲結(jié)構(gòu)下 , 各 VO 平均作業(yè)丟失率的實驗值與M/M/1模型下的理論值的對比 , 其中各個資源隊列 的隊列容

13、量為 5。從圖 3可以看出 , 實驗得出的作業(yè)丟失率要低 于理論計算值 , 這是因為部分提交到 VO 上的作業(yè) 部分被遷移到了其它的 VO 上 , 使得實際的 =/162006年第 23卷第 10期 微電子學與計算機與計算時的 有了區(qū)別 。 另外 , 從仿真結(jié)果可以看 出 , 由于協(xié)作關(guān)系的存在 , 使得各個資源的作業(yè)丟 失率均有所減少 。5結(jié)束語從以上實驗結(jié)果看來 , 將網(wǎng)格服務建模成圖 1所示的模型是合理的 , 在性能分析與結(jié)構(gòu)優(yōu)化等方 面是有可能的 。 當然 , 還有許多的研究工作 , 還有待 進一步的深入 :如將作業(yè)調(diào)度到不同資源的策略研 究 、 考慮作業(yè)優(yōu)先級的服務模型研究 、 各資

14、源的服 務隊列有限時 , 隊列長度 、 丟包率與資源穩(wěn)定性的 定性關(guān)系等 。 模型的研究對于應用與優(yōu)化都有較好 的指導意義 , 本文初步提出了網(wǎng)格環(huán)境下 , 服務的 建模與分析工作 , 大量研究工作還有待展開 。 參考文獻 :1I Foster, C Kesselman, S Tuecke. The anatomy of the grid: enabling scalable virtual organizations. International J. Supercomputer Applications, 2001, 15(3:200222 2I Foster, C Kesselman,

15、J Nick, S Tuecke. The physiology of the grid:an open grid services architecture for distribut-ed systems integration. January, 2002. http:/www.Globus. org/research/papers/ogsa.pdf3Cao J, Jarvis S A, Saini S. ARMS:an agent -based re-source management system for Grid computing, Sci. Pro-gram., 2002, 1

16、0(2:1351484Nitzberg B, Schopf J. Current activities in the scheduling and resource management area of the global grid forum, Lect. Notes Comput. Sci., 2002:25375Spooner D P, Jarvis S A, Cao J, et al. Local grid scheduling techniques using performance prediction. IEE proc., Com-put. Digit. Tech., 200

17、3, 150(2:87966Thomas N, Bradley J T, Knottenbelt W J:Stochastic anal-ysis of scheduling strategies in a grid-based resource mod-el, IEE Proceedings-software, 2004, 151(4:232 239作者簡介 :殷 杰 男 , (1980- , 博士研究生 。 研究方向為網(wǎng)格計算 、 語 義網(wǎng)格 、 智能控制等 。制實現(xiàn)代理的遷移 。 系統(tǒng)中不同網(wǎng)絡節(jié)點間的 MA 的發(fā)送和請求 , 即不同節(jié)點上的 MAE 與 MAE 之間 的交互用 RMI

18、實現(xiàn) 。3.4用戶與系統(tǒng)的交互過程(1 用戶登錄 :當用戶需要查詢數(shù)據(jù)時 , 用戶通 過本地 Peer 輸入查詢條件 , 本地 Peer 為用戶生成 相應的 SA , 并將 SA 發(fā)送到網(wǎng)絡上 。 當用戶離線時 , 由于移動代理 SA 自主執(zhí)行的特點 , 系統(tǒng)允許用戶 在發(fā)出查詢請求并派發(fā) SA 之后 , 離開網(wǎng)絡 。 而此時 SA 將脫機繼續(xù)在網(wǎng)絡間執(zhí)行用戶對其賦予的資源 檢索任務 。 (2 代理任務的執(zhí)行 :當 SA 移動到一個 網(wǎng)絡節(jié)點上時 , 先通過該節(jié)點提供的數(shù)據(jù)檢索接口 與 IA 進行交互 , 對該節(jié)點持有的 RDF 數(shù)據(jù)進行檢 索 , 查找相應的數(shù)據(jù) 。 之后 , SA 將自動離開當前宿主 節(jié)點回到網(wǎng)絡上 , 向下一個目標移動 。 (3 獲得查詢 結(jié)果 :用戶可以通過 GUI 查看本地節(jié)點上接收到的 查詢結(jié)果 , 并根據(jù)結(jié)果中對資源的描述選擇自己感 興趣的資源 , 使用本地代理進行下載 。4結(jié)束語該模型采用代理技術(shù)對 P2P 系統(tǒng)中的 RDF 文 檔進行檢索 , 使用 RDQL 作為查詢語言 , 通過圖形 化界面與用戶交互實現(xiàn)資源檢索 , 能提升網(wǎng)絡帶寬 資源利用率和系統(tǒng)效率 , 并具有較好的可擴展性 。參考文獻 :1Crespo A,