基于排隊(duì)理論的云計(jì)算中心性能分析模型

廖倩文，潘久輝，王開杰

（暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632）

基于排隊(duì)理論的云計(jì)算中心性能分析模型

廖倩文，潘久輝，王開杰

（暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632）

為全面、客觀分析云計(jì)算系統(tǒng)中心的性能，提出一種改進(jìn)的云計(jì)算中心系統(tǒng)分析模型。利用泊松分布描述批量到達(dá)云計(jì)算中心的用戶服務(wù)請求變化特點(diǎn)，建立基于排隊(duì)論的批量到達(dá)系統(tǒng)模型，在概率空間上求解隊(duì)長的穩(wěn)態(tài)概率，采用仿真實(shí)驗(yàn)對阻塞概率、立即服務(wù)概率等性能指標(biāo)進(jìn)行分析。仿真結(jié)果表明，隨著批量到達(dá)請求數(shù)增加，云計(jì)算中心的平均隊(duì)長相應(yīng)增加，降低了系統(tǒng)的阻塞概率。

云計(jì)算系統(tǒng)；性能分析；排隊(duì)論；平均等待隊(duì)長；批量到達(dá)

1 概述

云計(jì)算系統(tǒng)是一種以互聯(lián)網(wǎng)為核心的數(shù)據(jù)處理中心，對存儲(chǔ)、軟件、服務(wù)等資源進(jìn)行統(tǒng)一調(diào)度，構(gòu)成一個(gè)虛擬計(jì)算機(jī)中心，為用戶提供按需服務(wù)的商業(yè)模式［1-2］。由于用戶需求的種數(shù)不斷增加，用戶對云計(jì)算系統(tǒng)中心的服務(wù)質(zhì)量提出更高的要求［3］。云計(jì)算中心是云計(jì)算系統(tǒng)的核心，其性能的優(yōu)劣直接決定了云計(jì)算服務(wù)質(zhì)量的優(yōu)劣，因此對云計(jì)算系統(tǒng)中心的性能進(jìn)行全面、準(zhǔn)確分析具有十分重要的意義［4］。

針對云計(jì)算系統(tǒng)中心的性能分析問題，國內(nèi)外學(xué)者、專家投入了大量的時(shí)間、精力進(jìn)行廣泛的研究，涌現(xiàn)了許多云計(jì)算中心的性能模型［5］。傳統(tǒng)云計(jì)算系統(tǒng)中心性能分析模型采用模擬仿真系統(tǒng)如CloudSim實(shí)現(xiàn)［6］，它們屬于類靜態(tài)分析模型，假設(shè)云計(jì)算系統(tǒng)中心是一種靜態(tài)的工作狀態(tài)，然而，在實(shí)際應(yīng)用中，云計(jì)算系統(tǒng)中心規(guī)模龐大、結(jié)構(gòu)復(fù)雜，具有時(shí)變性和突變性，傳統(tǒng)模型難以建立準(zhǔn)確的性能分析模型［7］。為了解決傳統(tǒng)模型存在的不足，文獻(xiàn)［8］提出了基于數(shù)據(jù)聚集算法的云計(jì)算系統(tǒng)中心分析模型，在考慮服務(wù)質(zhì)量基礎(chǔ)上降低系統(tǒng)能耗；文獻(xiàn)［9］提出了性能受限的云中心異構(gòu)服務(wù)器能耗優(yōu)化模型，解決了云計(jì)算中心資源配置不合理等難題。近些年，隨著排隊(duì)理論的不斷發(fā)展，一些學(xué)者將其引入到云計(jì)算系統(tǒng)中心性能分析中，文獻(xiàn)［10］提出了基于利潤最大化的云計(jì)算系統(tǒng)中心性能分析方法，將多服務(wù)器的云計(jì)算中心優(yōu)化問題看作為一個(gè)M/M/m排隊(duì)問題，根據(jù)利潤最大化得到最優(yōu)優(yōu)化方案；文獻(xiàn)［11］提出了基于M/M/l的排隊(duì)系統(tǒng)云計(jì)算中心性能分析模型，提高了服務(wù)的響應(yīng)時(shí)間，降低了中心的能耗；文獻(xiàn)［12］提出了基于M/G/m/m+r排隊(duì)論的云計(jì)算中心性能分析模型。

為了更加準(zhǔn)確、全面對云計(jì)算系統(tǒng)中心性能進(jìn)行分析，本文提出一種基于排隊(duì)理論的批量到達(dá)云計(jì)算中心性能分析模型。將用戶服務(wù)請求過程看作為是一個(gè)參數(shù)為λ的泊松流，而且每批用戶服務(wù)請求數(shù)的概率分布已知，從而建立了云計(jì)算中心性能分析模型，然后給出系統(tǒng)穩(wěn)態(tài)運(yùn)行指標(biāo)的計(jì)算方法，最后通過仿真實(shí)驗(yàn)對模型的有效性和優(yōu)越性進(jìn)行測試。

2 云計(jì)算中心的工作機(jī)制和排隊(duì)模型

2.1 云計(jì)算中心的工作機(jī)制

在云計(jì)算系統(tǒng)中，通常有大批用戶服務(wù)請求進(jìn)入數(shù)據(jù)處理中心。由于中心有不同類型的服務(wù)臺(tái)，一旦有用戶服務(wù)需求到來時(shí)，云計(jì)算中心根據(jù)用戶的需求自適應(yīng)提供不同類型的服務(wù)，不同類型服務(wù)的價(jià)格不一樣，云計(jì)算系統(tǒng)中心的工作機(jī)制如圖1所示［13］。

圖1 云計(jì)算中心的工作機(jī)制

2.2 云計(jì)算中心的排隊(duì)模型

排隊(duì)系統(tǒng)是運(yùn)籌學(xué)的重要分支，又稱為隨機(jī)服務(wù)系統(tǒng)，通過排隊(duì)等待中的概率處理最優(yōu)化設(shè)計(jì)問題，其成功應(yīng)用于通信系統(tǒng)、生產(chǎn)管理系統(tǒng)等［14］。排隊(duì)系統(tǒng)包括到達(dá)過程、排隊(duì)規(guī)則、服務(wù)機(jī)制，對于云計(jì)算中心性能優(yōu)化問題，具體假設(shè)如下：

（1）用戶服務(wù)請求到達(dá)云計(jì)算系統(tǒng)的中心是隨機(jī)的，用戶服務(wù)請求批與批之間到達(dá)時(shí)間的間隔服從參數(shù)為λ的泊松流，用戶服務(wù)請求所需的服務(wù)時(shí)間均服從參數(shù)μ的負(fù)指數(shù)分布。

（2）每批用戶服務(wù)請求的數(shù)目為一個(gè)隨機(jī)變量ξ，其概率分布為：P（ξ=i）=αi，i=1，2，…，K。

（3）云計(jì)算中心有m個(gè)服務(wù)臺(tái)（m＜K），每一個(gè)服務(wù)臺(tái)獨(dú)立工作，在不同批次到達(dá)的用戶服務(wù)請求中，服務(wù)順序按先到先服務(wù)（First Come First Server，F(xiàn)CFS）的規(guī)則。

（4）云計(jì)算系統(tǒng)中心的容量有限，即系統(tǒng)中心最多可以容納m個(gè)用戶服務(wù)請求，如果云計(jì)算系統(tǒng)中心的容量已滿，那么新到達(dá)的用戶服務(wù)請求便離去，另尋服務(wù)，不然就需要進(jìn)行排隊(duì)等待［15］。

云計(jì)算中心的排隊(duì)模型如圖2所示。

圖2 云計(jì)算中心的排隊(duì)模型

3 云計(jì)算系統(tǒng)中心的性能分析模型

3.1 馬爾可夫鏈

馬爾可夫過程是指在已知某一隨機(jī)過程現(xiàn)在的條件下，“將來”與“過去”是獨(dú)立的，馬爾可夫鏈?zhǔn)且粋€(gè)時(shí)間與狀態(tài)都離散的時(shí)間序列。若隨機(jī)過程｛X（t），t∈T｝滿足：

（1）狀態(tài)空間S為R的馬爾可夫鏈。

（2）任n≥1，t1＜t2＜…＜tn，如果式（1）成立，那么稱｛X（t），t∈T｝為馬爾可夫鏈。

設(shè)I為馬爾可夫鏈｛Xn，n≥0｝的狀態(tài)空間，那么條件概率為：

根據(jù)每個(gè)預(yù)測對象的具體情況，將狀態(tài)空間劃分成若干區(qū)域，每個(gè)區(qū)域構(gòu)成一個(gè)狀態(tài)，設(shè)任一狀態(tài)記為Ei∈（E1i，E2i］，i=1，2，…，s，s為狀態(tài)數(shù)目，E1i和E2i分別為第i種狀態(tài)的上下界，那么狀態(tài)轉(zhuǎn)移概率矩陣公式為：

得到狀態(tài)轉(zhuǎn)移概率矩陣的計(jì)算公式為：

3.2 云計(jì)算中心性能分析模型的建立

設(shè)X（t）表示t時(shí)刻云計(jì)算中心的用戶服務(wù)請求數(shù)），根據(jù)排隊(duì)論可以知道，云計(jì)算中心的狀態(tài)空間為E=（0，1，…，m），云計(jì)算中心的狀態(tài)轉(zhuǎn)移過程如圖3所示。

圖3 云計(jì)算中心的狀態(tài)轉(zhuǎn)移過程

云計(jì)算中心的狀態(tài)轉(zhuǎn)移滿足如下規(guī)則：

（1）任意一個(gè)狀態(tài)i向右可以到達(dá)其后狀態(tài)：i+ 1，i+2，…，i+K，向左可以到達(dá)自身的相鄰狀態(tài)i-1。

（2）任意一個(gè)狀態(tài)i可以向左達(dá)到任意一個(gè)狀態(tài)i-K，…，i-2，i-1，而右邊狀態(tài)中，只有狀態(tài)i+1可到狀態(tài)i。

（3）以狀態(tài)n為分界點(diǎn)，左邊和右邊的狀態(tài)i（0＜i＜n）轉(zhuǎn)移率分別為iμ和nμ。

由于圖3是一個(gè)有限狀態(tài)馬爾可夫過程，其存在平穩(wěn)分布，根據(jù)由概率守恒原理得到穩(wěn)態(tài)方程組：

根據(jù)式（5）進(jìn)行求解，可得到系統(tǒng)穩(wěn)態(tài)概率分布P0，P1，…，Pm，然后可以計(jì)算出隊(duì)長概率Pi的值。

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

4.1 仿真環(huán)境

為了測試基于排隊(duì)論的云計(jì)算系統(tǒng)中心性能分析模型的有效性和優(yōu)越性，在Intel（R）Dual Core（TM）3.0 GHz CPU，4 GB RAM，W indows XP操作系統(tǒng)的計(jì)算機(jī)上，采用Matlab 2013進(jìn)行仿真實(shí)驗(yàn)，相關(guān)參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

4.2 性能評價(jià)指標(biāo)

為了對云計(jì)算中心的性能進(jìn)行客觀和準(zhǔn)確評價(jià)，本文選擇系統(tǒng)請求總數(shù)、阻塞概率、立即服務(wù)概率、平均隊(duì)長作為模型性能評價(jià)指標(biāo)，它們分別定義如下：

4.3 結(jié)果與分析

性能指標(biāo)分析如下：

（1）系統(tǒng)請求總數(shù)

系統(tǒng)請求總數(shù)的變化曲線如圖4所示，從圖4可以看出，隨著輸入隊(duì)列緩沖區(qū)長度增加，當(dāng)服務(wù)節(jié)點(diǎn)數(shù)m=100時(shí)，系統(tǒng)請求總數(shù)的增長比較平緩，當(dāng)m=500時(shí)，根本看不出隊(duì)列緩沖區(qū)大小對系統(tǒng)請求總數(shù)的影響。

圖4 系統(tǒng)請求數(shù)

（2）阻塞概率

阻塞概率變化曲線如圖5所示。從圖5可以明顯的看出，隨著輸入隊(duì)列緩沖區(qū)的增加，阻塞概率大幅度下降，在系統(tǒng)阻塞概率小于0.2%條件下，輸入隊(duì)列緩沖區(qū)長度應(yīng)該為服務(wù)節(jié)點(diǎn)數(shù)的10%，即當(dāng)n= 100時(shí)，系統(tǒng)輸入隊(duì)列緩沖區(qū)長度最小值應(yīng)該10，當(dāng)增加緩沖區(qū)長度時(shí)，系統(tǒng)阻塞概率會(huì)下降，可以提高了系統(tǒng)的運(yùn)行效率，但是增加到一定程度時(shí)，系統(tǒng)阻塞概率處于穩(wěn)定狀態(tài)。

圖5 阻塞概率

（3）立即服務(wù)概率

立即服務(wù)概率是指用戶請求服務(wù)無須任何排隊(duì)等待就可以獲得服務(wù)的概率，是評價(jià)云計(jì)算系統(tǒng)中心服務(wù)性能的一個(gè)關(guān)鍵指標(biāo)。立即服務(wù)概率變化曲線如圖6所示。從圖6可以看出，隨著輸入隊(duì)列緩沖區(qū)長度增加，立即服務(wù)概率下降，這意味著當(dāng)輸入隊(duì)列緩沖區(qū)的長度較小時(shí)，到達(dá)云計(jì)算系統(tǒng)中心的請求可以獲得立即服務(wù)，不需要進(jìn)入排隊(duì)等待。同時(shí)，從圖6（c）看出，服務(wù)節(jié)點(diǎn)數(shù)越多，立即服務(wù)概率就越高，系統(tǒng)的性能就越好。

（4）平均隊(duì)長的分析

平均隊(duì)長的變化曲線如圖7所示。從圖7可知，隨著批量用戶請求服務(wù)數(shù)的增多，平均隊(duì)長不斷增加，到達(dá)一定的數(shù)量后，又慢慢開始減少，這主要是由于批量用戶請求服務(wù)數(shù)增加，占據(jù)大量的隊(duì)列緩沖區(qū)，后面的用戶請求服務(wù)不能進(jìn)入隊(duì)列緩沖區(qū)而尋服務(wù)，等用戶請求服務(wù)得到滿足后，平均隊(duì)長又逐漸減少。

圖6 立即服務(wù)概率

5 結(jié)束語

為對云計(jì)算系統(tǒng)中心的性能進(jìn)行描述，本文提出基于排隊(duì)論的云計(jì)算中心性能分析模型，仿真結(jié)果表明，當(dāng)批量到達(dá)請求數(shù)增加時(shí)，云中心平均隊(duì)長不斷增加，增加云計(jì)算系統(tǒng)的緩沖區(qū)長度，可降低系統(tǒng)的阻塞概率，而且服務(wù)節(jié)點(diǎn)數(shù)越多，立即服務(wù)概率就越高，實(shí)驗(yàn)結(jié)果可以為云中心的資源配置和參數(shù)調(diào)整提供較好的參考意見，具有一定的實(shí)用價(jià)值。

圖7 平均隊(duì)長

［1］ 過敏意.綠色計(jì)算：內(nèi)涵及趨勢［J］.計(jì)算機(jī)工程，2010，36（10）：1-7.

［2］ 王 珊，王會(huì)舉，覃雄派，等.架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1742-1747.

［3］ 凍 康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀［J］.軟件學(xué)報(bào)，2009，20（5）：1337-1340.

［4］ 史佩昌，王懷民，蔣 杰，等.面向云計(jì)算的網(wǎng)絡(luò)化平臺(tái)研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與科學(xué)，2009，31（z1）：249-252.

［5］ 許 丞，劉 洪，譚 良.Hadoop云平臺(tái)的一種新的任務(wù)調(diào)度和監(jiān)控機(jī)制［J］.計(jì)算機(jī)科學(xué)，2013，40（1）：112-117.

［6］ 李春艷，何一舟，戴 彬.Hadoop平臺(tái)的多隊(duì)列作業(yè)調(diào)度優(yōu)化方法研究［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（3）：705-708.

［7］ 王意潔，孫偉東，周 松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)［J］.軟件學(xué)報(bào)，2012，23（4）：962-986.

［8］ 徐小龍，楊 庚，李玲娟，等.面向綠色云計(jì)算數(shù)據(jù)中心的動(dòng)態(tài)數(shù)據(jù)聚集算法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（9）：1927-1934.

［9］ 何懷文，傅 瑜，楊 亮，等.性能受限下云中心異構(gòu)服務(wù)器的能耗優(yōu)化［J］.計(jì)算機(jī)應(yīng)用，2009，20（5）：1337-1340.

［10］ 王 巍，羅軍舟，宋愛波.基于動(dòng)態(tài)定價(jià)策略的數(shù)據(jù)中心能耗成本優(yōu)化［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：599-612.

［11］ Khazaei H，M isic J，M isic V B.Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems［J］.IEEE Transactions on Parallel and Distributed System s，2012，23（5）：936-943.

［12］ Guo Liheng，Yan Tao，Zhao Shuguang，et al.dynamic Performance Optimization for Cloud Computing Using M/M/m Queuing System［J］.Journal of Applied Mathematics，2014，24（12）：2429-2438.

［13］ Khazaei H，Misic J，Misic V B.Performance of Cloud Centers with High Degree of Virtualization Under Batch Task Arrivals［J］.Parallel and Distributed System s，2013，24（12）：2429-2438.

［14］ 邱國新，姜海波.批量到達(dá)的M（ξ）/G/n/m多服務(wù)臺(tái)排隊(duì)系統(tǒng)研究［J］.甘肅科學(xué)學(xué)報(bào)，2013，25（1）：120-123.

［15］ 何懷文，傅 瑜，楊毅紅，等.基于M/M/n/n+r排隊(duì)模型的云計(jì)算中心服務(wù)性能分析［J］.計(jì)算機(jī)應(yīng)用，2014，34（7）：1843-1847.

編輯 索書志

Per form ance Analysis Model of C loud Computing Center Based on Queuing Theory

LIAO Qianwen，PAN Jiuhui，WANG Kaijie
（College of Information Science and Technology，Jinan University，Guangzhou 510632，China）

In order to com prehensively and objectively analyse the performance for cloud computing system s center，this paper presents a performance analysis model of cloud Computing center based on queuing theory.The characteristics of the user service request which reaches the center are described and a the system model for batch arrivals by using queuing theory is established，and the length of steady-state probability is solved in probability space.Finally，the simulation experiments are carried out to test the performance by using blocking probability，immediate service probability，etc. Simulation results show that，With the increase of the number of batch arrival request，average length of cloud Computing center increases，and increasing the buffer length can reduce the blocking probability.

cloud computing system；performance analysis；queuing theory；mean waiting queue size；batch arrivals

廖倩文，潘久輝，王開杰.基于排隊(duì)理論的云計(jì)算中心性能分析模型［J］.計(jì)算機(jī)工程，2015，41（9）：51-55.

英文引用格式：Liao Qianwen，Pan Jiuhui，Wang Kaijie.Performance Analysis Model of Cloud Computing Center Based on Queuing Theory［J］.Computer Engineering，2015，41（9）：51-55.

1000-3428（2015）09-0051-05

A

TP393

10.3969/j.issn.1000-3428.2015.09.009

武漢大學(xué)軟件工程國家重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目（SKLSE2012-09-37）；公安部技術(shù)研究計(jì)劃基金資助項(xiàng)目（2014 JSYJB048）。

廖倩文（1989-），男，碩士研究生，主研方向：信息集成，數(shù)據(jù)質(zhì)量管理；潘久輝，教授、博士生導(dǎo)師；王開杰，碩士研究生。

2014-12-26

2015-02-11 E-m ail：liaoqianw en_77@163.com