基于系統響應時間的云服務質量評估模型

楊喆曦 薛華成

1(中國計量大學標準化學院 浙江 杭州 310018)

2(復旦大學管理學院 上海 200433)

基于系統響應時間的云服務質量評估模型

楊喆曦1薛華成2

1(中國計量大學標準化學院 浙江 杭州 310018)

2(復旦大學管理學院 上海 200433)

響應時間是云服務系統的主要質量衡量指標之一，過長的系統響應時間意味著用戶的流失。以隊列等待、服務器處理時間和網絡延遲構成云訪問的總體響應時間，采用嵌入馬爾可夫鏈的方法生成觀察點的馬爾可夫鏈。借助馬爾可夫鏈的無后效特性來模擬云訪問的隨機到達，以此為基礎構建云服務排隊模型，用以評估云服務質量。通過解析仿真的方法驗證了所提出的云服務質量評估模型的有效性。

云計算 響應時間 排隊論 馬爾可夫鏈

0 引 言

云計算服務將大量的軟硬件資源整合起來統一提供給各種類型以不同形式隨機出現的用戶[1]，從這個意義上說對云計算服務系統服務質量(QoS)的研究類似于對排隊服務系統服務質量(服務時間、等待時間、隊列長度等指標)的研究。鑒于云計算對資源的高度集成與對用戶使用的透明性，云計算服務系統是一個單服務臺的服務系統[2]。然而基于云計算的分布式、網格化基石，云計算服務系統又是一個可以具有無限多服務臺的服務系統[3-4]，因此云計算系統的QoS評價與衡量可以集中于對單個服務臺(主機或虛擬機)及其網絡傳輸QoS的評價與衡量。但是服務水平是一個難以量化的抽象指標，而簡單的隊列長度難以有效衡量排隊服務系統的服務質量，采用顧客在系統中的逗留時間或隊列中的等待時間能夠對服務系統質量進行直觀量化，便于進行對比和分析。

1 云服務排隊系統與傳統排隊系統的區別

1.1 虛擬化

虛擬化是云計算的核心技術和主要特征，因此基與云計算的排隊系統也必然是虛擬化的。分布在網絡各地的訪問請求被云服務系統統一進行受理，從云服務系統龐大的硬件資源群中為請求分配特定的軟、硬件資源[5]。因此，云服務系統中所有服務都是在云資源虛擬化的基礎上提供的，訪問所獲取的資源都是虛擬機，受理訪問的服務臺都是虛擬機。

1.2 多源訪問

服務系統的顧客不是傳統的有形客戶或無形電話呼叫，而是Web Application或其他應用程序所發出的訪問請求。這種訪問請求可能是終端用戶觸發的，也可能是由應用程序生成的，因此云服務系統中訪問請求的來源多種多樣[6]。

1.3 并行訪問

傳統的排隊服務系統一個服務臺一次只受理一個顧客的訪問，而鑒于計算機處理的分時并行機制，云計算環境中一個虛擬機也能夠經常同時響應多個訪問請求，這與傳統排隊理論服務規則不一致[7-8]。

1.4 峰、谷訪問

云服務系統部署在云端，供用戶365×7×24進行訪問，對于特定的用戶群，由于工作習慣、業務流程、時區差異等原因存在一定的高峰訪問時間和低谷訪問時間。峰、谷的差異對云服務系統設計和成本控制都具有重要的意義。

1.5 協同處理

為了提高云服務效率，訪問請求通常會被任務分派器進行切割、分塊處理，因此云計算的單個訪問請求往往都是在不同的虛擬機、物理機上單獨處理。然后通過協同、組裝等方式形成完整的處理結果[9]。

1.6 靈活的服務臺設置

信息技術的飛速發展導致的硬件成本飛速下降使得云服務系統的主機設置能夠根據需要以低廉的成本進行動態增減，對所有軟硬件資源進行集成的云平臺也能夠支撐主機的動態增減。同時虛擬機技術的成熟能夠動態申請和銷毀虛擬機，從而使得云服務系統中服務臺因素不是設計者考慮的首要問題[10]。

盡管與傳統的排隊服務系統相比有許多的差異，但這些差異都可以通過適當變通轉換為經典的排隊服務系統模式。因此，云服務排隊系統仍然是一個典型的排隊系統，排隊理論中的相關定理與結論仍然適用。

2 云服務排隊系統主要性能指標

在云計算的服務隊列規則中，不考慮顧客的損失，而一律采取等待的方式。終端客戶通過Web Application 或其他接口向云端提交訪問請求后等待訪問結果的過程就是排隊等待的過程。根據相關研究，客戶等待訪問結果的最大時間通常是4到6秒，超出這個時間客戶將會因極度失望離開，在意味著客戶流失的同時也意味著云服務系統服務水平的低下。

從云客戶的角度而言，自訪問請求被提交開始到得到處理結果的整個等待過程都是客戶等待云服務系統響應的等待時間，以系統中云客戶整體等待時間W代表云服務系統的服務水平。由于云服務系統是一個超級計算機，能夠同時對成千上萬的訪問請求進行及時響應，因此在只有一個數據中心的情況下可以將云服務系統看成n個并行、獨立的服務臺(虛擬機)。服務臺只有在進行了任務分配后才與請求建立了對應的服務關系，否則兩者沒有任何關聯[11]。因此，以所有服務臺中顧客等待時間的均值為整個服務系統整體等待時間，用以代表其云服務的整體服務水平。令云系統服務水平為：

(1)

對云客戶而言，訪問請求一旦提交，后續的工作都是云服務提供商負責的內容。因此訪問提交后的信息傳遞的網絡延遲，隊列等待和請求處理耗時都是顧客等待云服務系統響應的耗時，是云客戶衡量云服務質量優劣的直觀指標，也是企業構建云服務時需要參考和實現的重要目標。根據式(1)的描述，云服務系統服務水平的參數主要包括逗留時間和網絡延遲，而逗留時間又包括隊列等待時間和服務處理時間。

2.1 基于馬尓可夫鏈的等待時間

由于顧客達到和服務時間都具有隨機性，因此基于其上的這些數量指標均為隨機變量。這些指標的瞬態特征對排隊系統的各項特性不具有說服力，通常我們只對統計平穩狀態下的穩態數量指標感興趣。所以在定量分析排隊系統的性能時，通常是指分析系統在平衡狀態下的性能。對云客戶的使用感受而言，除去網絡傳輸耗時，衡量一個云服務系統的質量好壞主要依據其提交訪問請求后得到服務結果的等待時間，即云服務系統的響應時間。

鑒于從云資源管理系統到虛擬機的任務信息傳遞時間已經包括在下文描述的網絡延遲時間中，且無論采用什么樣的排隊模式都不影響這個時間的取值。因此本文對于隊列等待時間的研究可以拋開排隊模式的差異而只研究在任務響應端的虛擬機及其前面排隊等候處理的任務隊列的處理情況。

(2)

雖然在用戶的眼里，云服務系統似乎是一個單服務臺的排隊服務系統，然而以其龐大的服務能力而著稱的云中心實際上擁有無限多虛擬機可以響應用戶的請求。因此，結合排隊論相關定理，對于多服務臺(服務臺個數為k)排隊系統而言，有平均逗留時間計算公式：

(3)

而相應的隊列平均排隊時間計算公式為：

(4)

其中：

(5)

式(3)就是式(1)的一個特殊形式，刻畫的是一個多任務臺的云服務系統對所有抵達請求不加歧視的統一進行處理的情況。

本文采用嵌入馬爾可夫鏈來更貼切模擬訪問請求的到達行為和規律，而不只是簡單的采用Poisson流的方式。馬爾可夫鏈(也叫馬氏鏈)是用來描述離散事件隨機過程最常用的一個模型，由于所具有的無后效性而被廣泛使用。嵌入馬氏鏈技術要求對可觀察的系統狀態進行一些列馬氏點選擇，然后在訪問請求剛好到達之前對這些任務點(包括正在服務中的和隊列中還未被服務的任務)進行編號，如0，1，2，…，這樣我們就得到了一個同質的馬氏鏈。在這個嵌入的馬氏鏈中得到的是每次訪問請求到達前的系統狀態,如圖1所示。

圖1 嵌入馬氏鏈觀察點示意圖

訪問請求的到達仍然假設為服從Poisson分布，每個任務都有一個虛擬機負責進行響應，從而嵌入馬氏鏈的過程如圖2所示。

圖2 嵌入馬氏鏈過程示意圖

圖2中An和An+1表示云服務系統第n個和n+1個訪問請求到達系統的時刻，相應的qn和qn+1分別表示對應到達時刻系統中包括在處理和在等待任務在內的任務數。令vn+1表示從An到An+1時刻系統處理完的任務數，從而有如下等式：

qn+1=qn-vn+1+1

(6)

馬氏鏈的狀態轉換概率可以定義為：

pi,j=Prob[qn+1=j|qn=i]

(7)

式(7)表示i+1-j個請求在兩個成功抵達任務間隔被響應的概率。顯然對于j>i+1時的概率Pi,j=0。

A到達間隔時間的Laplace Stieltjes 變換(LST)為：

(8)

服務時間B的LST為：

(9)

殘存服務時間是從服務時間中任一點(Poisson流的一個達到點)到服務結束的時間間隔，將其表示成B+，已過任務服務時間是自服務開始到任一點的服務時間間隔，將其記作B_。任務在下次請求到達前被完成的基本條件是其處理時間小于請求到達間隔，因此其概率可以寫成：

(10)

當恰好有空閑服務臺時，抵達請求就能立即被受理，這個請求在下一個請求到達前被受理完成的概率Py計算如下：

(11)

而當隊列任務到達非空時，會發生如下幾種情況。如果兩個成功到達間隔中有任務完成，服務臺會從該非空隊列中提取一個新任務。而如果這個新任務依然在下次請求到達前完成，服務臺再從非空隊列中提取新任務，以次類推指導隊列為空或有新請求到達。因此在隊列中有足夠任務提取的情況下，服務臺有k(>0)個任務在下次請求到達前完成的概率根據式(10)和式(11)有：

(12)

在穩態狀態下，設W(x)和W×(s)為服務等待時間W的CDF和LST，從而

(13)

其中π=[π0,π1,π2,…]是穩態概率。

2.2 基于處理器模式的處理時間

IT技術的飛速發展早已使計算機擺脫了單核時代，步入雙核、四核乃至更先進的多處理器時代。這種多處理器的硬件設備也引發了處理器進行任務響應上的策略差異。云計算的虛擬機技術中，在處理器的任務處理方式上有兩種處理策略[7]:空間共享與時間共享。虛擬機的空間共享就是將虛擬機的任務按時間先后來進行執行，虛擬機的時間共享就是把所有虛擬機的請求分配給每個處理器；任務的空間共享就是將多個處理器看作一個處理器，從而將一個任務分配多個處理器上，任務的時間共享就是每個處理器的一個時間片上響應兩個虛擬機的請求。即虛擬機的空間共享就是在任一時刻，只有一個虛擬機能夠運行，從而任務也是逐一被執行；虛擬機的時間共享就是任一時刻，都有多個虛擬機的任務請求被響應，從而任務都被同時響應[12]。因此總共就有4類策略組合方式，對于雙核雙虛擬機的情況，恰好有圖所示的4種策略組合：CPU空間共享-任務空間共享或叫完全空間共享(見圖3)，CPU空間共享-任務時間共享(見圖4)，CPU時間共享-任務空間共享(見圖5)，CPU時間共享-任務時間共享或叫完全時間共享(見圖6)。為了很好地說明這兩種處理策略的異同，以一個雙核CPU的設備為例，假設云計算服務申請了兩個虛擬機也同時接收用戶的服務請求。其中VM1的服務請求由t1～t4組成，VM2的服務請求由t5～t8組成，不同的處理策略在處理器中處理時間分配方式和任務執行順序上存在差異。

圖3 處理器任務處理策略a

圖4 處理器任務處理策略b

圖5 處理器任務處理策略c

圖6 處理器任務處理策略d

設虛擬機共接收到p個云任務(Cloudlet)，每個任務包含r(j)，j=1,2,…,p條執行指令，主機有n個處理單元，每個處理單元的處理長度是cap(i)，i=1,2,…,n，cores(j)表示任務需要的處理器個數，主機處理能力cp表示如下：

(14)

從而在虛擬機的空間共享模式下，虛擬機負責執行的任務j的執行耗費時間ET為：

(15)

任務j的服務等待時間WT為：

(16)

因此空間共享模式下任務j的完成時間表達如下：

FT(j)=WT(j)+ET(j)=

(17)

對于時間共享模式情況下多任務同時處理，因此任務j的服務等待時間為0，任務處理所需耗費的時間ET也表示為式(15)，只不過主機的處理能力cp計算方式有多不同：

(18)

因此時間共享模式下任務j的完成時間表達如下：

(19)

通過前面的對比可以看出，虛擬機的空間共享模式雖然會對用戶服務造成等待感，但是一旦得到云端響應后，會很快處理完。而時間共享模式相對而言能夠及時響應用戶的請求，但是單個任務的處理時間會比較長。事實上，無論哪種模式下虛擬機真正用于響應和處理訪問請求的時間都為ET，只是由于所分配到的資源不同，所耗時間有所不同而已。

2.3 基于網絡拓撲的網絡延遲時間

云計算架構在龐大的計算機網絡之上，擁有眾多的網絡傳輸與通信設備，連接著全球各地的終端客戶，從而網絡拓撲結構成為云服務系統的服務基石。雖然網絡信息傳輸的延遲直接影響著整個服務系統的服務質量，對云服務系統建設者、使用者和管理者而言，網絡實際的物理拓撲結構并不是他們關心的對象，且也不是他們能夠進行改造來減少網絡延遲力所能及的內容[13]。因此多數情況下，網絡延遲時間只是作為云服務網絡的一個外生特性來使用，并在可能的情況下通過路由算法來縮短網絡延遲。通常使用如下所示的延遲矩陣來表示網絡各主要節點在信息傳輸時的延遲狀況：

(20)

其中lij表示信息或數據從網絡節點i到j的傳遞耗時，即在i節點傳輸指令下達后還需要延遲lij毫秒后才能將信息傳達j節點，如圖7所示。該矩陣表示了網絡中r個主要實體之間的數據傳輸延遲信息，如亞、非、歐等世界主要區域，體現為區域入口端和出口端的速度。

圖7 網絡傳輸延遲示意圖

圖7說明了云服務中網絡拓撲造成的數據延遲現象，即網絡拓撲的物理性質導致了云客戶發送與接收信息的延遲，這部分延遲也應該直接計入云服務提供商的服務質量之中。

網絡拓撲結構的描述通常采用BRITE格式將網絡各節點信息全部包含進去。云環境中的節點包括主機、數據中心、云代理等。BRITE中節點信息包括節點編號，矩陣中的行號與列號，出、入度等信息，邊信息包括邊號、開始節點、結束節點、歐式距離、傳遞延時、帶寬等信息。這些信息的納入為網絡各節點延時的計算提供了直接依據。

2.4 基于系統響應時間的云服務排隊模型

(21)

其中lij表示從客戶端到云處理端的網絡延時。可以看出系統響應時間主要有三部分組成：隊列等待時間、服務處理時間和網絡延遲。

3 結 語

關于這個云服務系統服務水平評估模型的數值仿真驗證有兩種方式：隨機仿真法和推理仿真法。隨機仿真法利用蒙特卡羅方法生成符合特定分布特征的隨機數據，借此模仿服務系統的運行狀況，最后將需要考察的服務系統狀態變量所有實例值以均值、方差等統計變量的形式來描述。隨機仿真能夠很好地模擬現實中的哪種不確定性，并且能夠檢驗系統在分布允許情況下的極端點表現，全方位進行服務檢驗。但是正是由于隨機仿真所具有的隨機性，每次仿真所產生的結果都不一樣，只是在統計意義上無限趨近于狀態變量理想值，導致取值誤差。同時隨機仿真必須在足夠次數的仿真情況下才能得到具有說服力的數據，這就要求有足夠的仿真次數，需要耗費大量的時間。

推理仿真法直接使用隨機變量的統計特性來進行推理仿真，而不是去模擬隨機變量的統計特性。這樣的仿真直接采用推導出來的解析公式值進行仿真，得到的是狀態變量的解析值，而不是統計值，消除了隨機性誤差，也極大地減輕了系統的運算工作量。但是由于統計特性在集中表現了絕大部分樣本點信息的同時也會略掉個別極端點的信息，導致對系統的檢驗不完備，無法發現系統針對極端情況可能出現的問題。

由于云計算的仿真需要對大量的硬件資源和大量的用戶訪問進行仿真，計算量非常龐大，如果繼續采用隨機仿真的方法，進行實驗的設備要求很高，時間花費難以想象。因此本文擬采用推理仿真法在后續的研究中對云服務系統進行分析，為此首先需要檢驗推理仿真法結果的有效性。

基于式(21)給出的系統響應時間解析值，通過將其與采用同樣假設的隨機仿真結果進行對比的方式來驗證本服務系統評估模型的有效性。采用基于Petri網的Artifex仿真引擎進行云服務離散事件的仿真，在不同數目的虛擬機的情況下比較兩個方針結果中的均值差異，結果如圖8所示。

圖8 仿真結果對比

圖中折線代表的是采用隨機仿真法在不同參數取值下的所有訪問請求的系統響應時間的均值，符號點表示通過解析式仿真得到在馬氏鏈的各觀察點上系統的響應時間。四條線上對應的數字表示仿真的虛擬機的個數。從圖中可以看出，兩種方法得出的響應時間結果是非常接近的，除去隨機仿真法的隨機性誤差，可以認為本文提出的云服務系統的評估模型是有效的，使用解析仿真的方法進行云服務系統的仿真也是可行、有效的。

[1] Du N H,Huang H L,Li L F. Can online trading survive bad-mouthing? An experimental investigation[J].Decision Support Systems,2013,56(6):419-426.

[2] Su Q,Chen L.A method for discovering clusters of e-commerce interest patterns using click-stream data[J].Electronic Commerce Research & Applications,2015,14(1):1-13.

[3] Su Q,Huang J J,Zhao X D.An information propagation model considering incomplete reading behavior in microblog[J].Physica A Statistical Mechanics & Its Applications,2015,419(2):55-63.

[4] Lin C H, Liu D, Pang W, et al.Sherlock:A Semi-automatic Framework for Quiz Generation Using a Hybrid Semantic Similarity Measure[J].Cognitive Computation,2015,7(6):667-679.

[5] Ghosh R, Longo F. Scalable Analytics for IaaS Cloud Availability[J].IEEE Transactions on Cloud Computing, 2014,2(1):57-70.

[6] 趙娉婷.云計算環境下服務信任度評估技術的研究[D].北京:北京交通大學,2014.

[7] Calheiros R N, Ranjan R, Beloglazov A,et al. CloudSim: a toolkit for modeling and simulation of cloud computing envi-ronments and evaluation of resources provisioning algorithms[J].Software: Practice & Experience, 2011,41(1):23-50.

[8] Gotelli N J, Wener U. Statistical challenges in null model analysis[J]. Oikos,2012,121(2):171-180.

[9] 馬滿福,王梅.云環境下基于服務等級協議的信任評估模型[J].計算機應用,2015,35(6):1567-1572.

[10] 車建華.虛擬計算系統性能和可用性評測方法研究[D].杭州:浙江大學,2010.

[11] Vani B, Priya R C M. A Survey on the Security Issues in Cloud Computing[J]. International Journal of P2P Network Trends and Technology, 2014(11):16-19.

[12] Jesús Montes, Alberto Sánchez, Bunjamin Memishi, et al.GMonE: A complete approach to cloud monitoring[J]. Future Generation Computer Systems, 2013,29(8):2026-2040.

[13] Chard K, Caton S, Rana O, et al. Social Clouds: A Retrospective[J]. IEEE Cloud Computing, 2015, 2(6):30-40.

CLOUDSERVICEQUALITYEVALUATIONMODELBASEDONSYSTEMRESPONSETIME

Yang Zhexi1Xue Huacheng2

1(CollegeofStandardization,ChinaJiliangUniversity,Hangzhou310018,Zhejiang,China)2(SchoolofManagement,FudanUniversity,Shanghai200433,China)

The response time is one of the key quality indexes of cloud service system, which means that the longer of system response time, the more of losing customers. Queuing waiting, server processing time and network delay constitute the overall response time of cloud service access, and the Markov chain of observation points is generated by embedded Markov chain. The random arrival of cloud access is simulated by the non-aftereffect property of Markov chain, and the queuing model of cloud service is constructed to evaluate the quality of cloud service. At the same time, the validity of the proposed cloud service quality evaluation model is verified by analytic simulation.

Cloud computing Response time Queuing theory Markov chain

TP393

A

10.3969/j.issn.1000-386x.2017.10.007

2016-12-14。浙江省科技計劃重點項目(2016C25G2080022);杭州市哲學社會科學規劃課題(2015JD30);浙江省教育廳項目(Y201432184)。楊喆曦，講師，主研領域：均衡優化，信息化管理，標準化。薛華成，教授。