基于排隊理論的云計算中心性能分析模型

廖倩文，潘久輝，王開杰

（暨南大學信息科學技術學院，廣州510632）

基于排隊理論的云計算中心性能分析模型

廖倩文，潘久輝，王開杰

（暨南大學信息科學技術學院，廣州510632）

為全面、客觀分析云計算系統中心的性能，提出一種改進的云計算中心系統分析模型。利用泊松分布描述批量到達云計算中心的用戶服務請求變化特點，建立基于排隊論的批量到達系統模型，在概率空間上求解隊長的穩態概率，采用仿真實驗對阻塞概率、立即服務概率等性能指標進行分析。仿真結果表明，隨著批量到達請求數增加，云計算中心的平均隊長相應增加，降低了系統的阻塞概率。

云計算系統；性能分析；排隊論；平均等待隊長；批量到達

1 概述

云計算系統是一種以互聯網為核心的數據處理中心，對存儲、軟件、服務等資源進行統一調度，構成一個虛擬計算機中心，為用戶提供按需服務的商業模式［1-2］。由于用戶需求的種數不斷增加，用戶對云計算系統中心的服務質量提出更高的要求［3］。云計算中心是云計算系統的核心，其性能的優劣直接決定了云計算服務質量的優劣，因此對云計算系統中心的性能進行全面、準確分析具有十分重要的意義［4］。

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

為了更加準確、全面對云計算系統中心性能進行分析，本文提出一種基于排隊理論的批量到達云計算中心性能分析模型。將用戶服務請求過程看作為是一個參數為λ的泊松流，而且每批用戶服務請求數的概率分布已知，從而建立了云計算中心性能分析模型，然后給出系統穩態運行指標的計算方法，最后通過仿真實驗對模型的有效性和優越性進行測試。

2 云計算中心的工作機制和排隊模型

2.1 云計算中心的工作機制

在云計算系統中，通常有大批用戶服務請求進入數據處理中心。由于中心有不同類型的服務臺，一旦有用戶服務需求到來時，云計算中心根據用戶的需求自適應提供不同類型的服務，不同類型服務的價格不一樣，云計算系統中心的工作機制如圖1所示［13］。

圖1 云計算中心的工作機制

2.2 云計算中心的排隊模型

排隊系統是運籌學的重要分支，又稱為隨機服務系統，通過排隊等待中的概率處理最優化設計問題，其成功應用于通信系統、生產管理系統等［14］。排隊系統包括到達過程、排隊規則、服務機制，對于云計算中心性能優化問題，具體假設如下：

（1）用戶服務請求到達云計算系統的中心是隨機的，用戶服務請求批與批之間到達時間的間隔服從參數為λ的泊松流，用戶服務請求所需的服務時間均服從參數μ的負指數分布。

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

（3）云計算中心有m個服務臺（m＜K），每一個服務臺獨立工作，在不同批次到達的用戶服務請求中，服務順序按先到先服務（First Come First Server，FCFS）的規則。

（4）云計算系統中心的容量有限，即系統中心最多可以容納m個用戶服務請求，如果云計算系統中心的容量已滿，那么新到達的用戶服務請求便離去，另尋服務，不然就需要進行排隊等待［15］。

云計算中心的排隊模型如圖2所示。

圖2 云計算中心的排隊模型

3 云計算系統中心的性能分析模型

3.1 馬爾可夫鏈

馬爾可夫過程是指在已知某一隨機過程現在的條件下，“將來”與“過去”是獨立的，馬爾可夫鏈是一個時間與狀態都離散的時間序列。若隨機過程｛X（t），t∈T｝滿足：

（1）狀態空間S為R的馬爾可夫鏈。

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

設I為馬爾可夫鏈｛Xn，n≥0｝的狀態空間，那么條件概率為：

根據每個預測對象的具體情況，將狀態空間劃分成若干區域，每個區域構成一個狀態，設任一狀態記為Ei∈（E1i，E2i］，i=1，2，…，s，s為狀態數目，E1i和E2i分別為第i種狀態的上下界，那么狀態轉移概率矩陣公式為：

得到狀態轉移概率矩陣的計算公式為：

3.2 云計算中心性能分析模型的建立

設X（t）表示t時刻云計算中心的用戶服務請求數），根據排隊論可以知道，云計算中心的狀態空間為E=（0，1，…，m），云計算中心的狀態轉移過程如圖3所示。

圖3 云計算中心的狀態轉移過程

云計算中心的狀態轉移滿足如下規則：

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

（2）任意一個狀態i可以向左達到任意一個狀態i-K，…，i-2，i-1，而右邊狀態中，只有狀態i+1可到狀態i。

（3）以狀態n為分界點，左邊和右邊的狀態i（0＜i＜n）轉移率分別為iμ和nμ。

由于圖3是一個有限狀態馬爾可夫過程，其存在平穩分布，根據由概率守恒原理得到穩態方程組：

根據式（5）進行求解，可得到系統穩態概率分布P0，P1，…，Pm，然后可以計算出隊長概率Pi的值。

4 仿真實驗

4.1 仿真環境

為了測試基于排隊論的云計算系統中心性能分析模型的有效性和優越性，在Intel（R）Dual Core（TM）3.0 GHz CPU，4 GB RAM，W indows XP操作系統的計算機上，采用Matlab 2013進行仿真實驗，相關參數如表1所示。

表1 仿真實驗參數設置

4.2 性能評價指標

為了對云計算中心的性能進行客觀和準確評價，本文選擇系統請求總數、阻塞概率、立即服務概率、平均隊長作為模型性能評價指標，它們分別定義如下：

4.3 結果與分析

性能指標分析如下：

（1）系統請求總數

系統請求總數的變化曲線如圖4所示，從圖4可以看出，隨著輸入隊列緩沖區長度增加，當服務節點數m=100時，系統請求總數的增長比較平緩，當m=500時，根本看不出隊列緩沖區大小對系統請求總數的影響。

圖4 系統請求數

（2）阻塞概率

阻塞概率變化曲線如圖5所示。從圖5可以明顯的看出，隨著輸入隊列緩沖區的增加，阻塞概率大幅度下降，在系統阻塞概率小于0.2%條件下，輸入隊列緩沖區長度應該為服務節點數的10%，即當n= 100時，系統輸入隊列緩沖區長度最小值應該10，當增加緩沖區長度時，系統阻塞概率會下降，可以提高了系統的運行效率，但是增加到一定程度時，系統阻塞概率處于穩定狀態。

圖5 阻塞概率

（3）立即服務概率

立即服務概率是指用戶請求服務無須任何排隊等待就可以獲得服務的概率，是評價云計算系統中心服務性能的一個關鍵指標。立即服務概率變化曲線如圖6所示。從圖6可以看出，隨著輸入隊列緩沖區長度增加，立即服務概率下降，這意味著當輸入隊列緩沖區的長度較小時，到達云計算系統中心的請求可以獲得立即服務，不需要進入排隊等待。同時，從圖6（c）看出，服務節點數越多，立即服務概率就越高，系統的性能就越好。

（4）平均隊長的分析

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

圖6 立即服務概率

5 結束語

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

圖7 平均隊長

［1］ 過敏意.綠色計算：內涵及趨勢［J］.計算機工程，2010，36（10）：1-7.

［2］ 王 珊，王會舉，覃雄派，等.架構大數據：挑戰、現狀與展望［J］.計算機學報，2011，34（10）：1742-1747.

［3］ 凍 康，鄭緯民.云計算：系統實例與研究現狀［J］.軟件學報，2009，20（5）：1337-1340.

［4］ 史佩昌，王懷民，蔣 杰，等.面向云計算的網絡化平臺研究與實現［J］.計算機工程與科學，2009，31（z1）：249-252.

［5］ 許 丞，劉 洪，譚 良.Hadoop云平臺的一種新的任務調度和監控機制［J］.計算機科學，2013，40（1）：112-117.

［6］ 李春艷，何一舟，戴 彬.Hadoop平臺的多隊列作業調度優化方法研究［J］.計算機應用研究，2014，31（3）：705-708.

［7］ 王意潔，孫偉東，周 松，等.云計算環境下的分布存儲關鍵技術［J］.軟件學報，2012，23（4）：962-986.

［8］ 徐小龍，楊 庚，李玲娟，等.面向綠色云計算數據中心的動態數據聚集算法［J］.系統工程與電子技術，2012，34（9）：1927-1934.

［9］ 何懷文，傅 瑜，楊 亮，等.性能受限下云中心異構服務器的能耗優化［J］.計算機應用，2009，20（5）：1337-1340.

［10］ 王 巍，羅軍舟，宋愛波.基于動態定價策略的數據中心能耗成本優化［J］.計算機學報，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］ 邱國新，姜海波.批量到達的M（ξ）/G/n/m多服務臺排隊系統研究［J］.甘肅科學學報，2013，25（1）：120-123.

［15］ 何懷文，傅 瑜，楊毅紅，等.基于M/M/n/n+r排隊模型的云計算中心服務性能分析［J］.計算機應用，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

廖倩文，潘久輝，王開杰.基于排隊理論的云計算中心性能分析模型［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

武漢大學軟件工程國家重點實驗室開放基金資助項目（SKLSE2012-09-37）；公安部技術研究計劃基金資助項目（2014 JSYJB048）。

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

2014-12-26

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