頡　斌，楊　揚，曠　毅（北京科技大學 計算機通信工程學院，北京 100083）

基于云基礎設施的服務部署優(yōu)化問題建模*

頡斌，楊揚，曠毅
（北京科技大學 計算機通信工程學院，北京 100083）

目前典型的云基礎設施提供商所提供的虛擬機資源都是有限的規(guī)格類型，當同一個服務部署在不同配置的虛擬機上時，會體現(xiàn)出不同的性能。通過對基于云基礎設施的SaaS層服務部署情況進行研究和分析，提出對服務部署策略進行優(yōu)化的必要性，并將該服務部署優(yōu)化問題抽象為多目標組合優(yōu)化問題，對其進行數(shù)學建模；然后利用排隊論，得出優(yōu)化指標的計算方法，并進行實驗驗證。

云計算；服務部署優(yōu)化；多目標組合優(yōu)化

0　引言

云計算供應商提供了常見的可從Web瀏覽器獲取的在線服務應用，通常用基礎設施即服務（Infrastructure as a Service，IaaS）、平臺即服務（Platform as a Service，PaaS）和軟件即服務（Software as a Service，SaaS）3個層次來表示。

SaaS可基于傳統(tǒng)計算架構提供，也可基于云計算架構提供。在基于云計算架構部署SaaS時，可直接在IaaS層之上部署，也可在PaaS層之上進行部署。IaaS層中的資源，尤其是虛擬機形式的資源，常常是有限的。目前典型的 IaaS提供商所提供的虛擬機資源一般是固定的幾種，SaaS提供商在利用 IaaS層中的資源部署應用時，需要考慮部署應用的虛擬機規(guī)格。

由于不同類型的用戶對 SaaS層的應用服務有不同的服務質量需求，服務提供商需要與不同類型的用戶分別簽訂服務等級協(xié)議，以滿足其需求。此外，要部署的應用通常由多個不同的服務及其工作流組成，構成應用的每個服務可以生成多個服務實例，每個服務實例部署在不同配置的虛擬機上體現(xiàn)出的性能也不同。因此，對于云供應商而言，服務部署是要實施的最重要的任務。

1　服務部署優(yōu)化問題分析

1.1SaaS層服務部署方式

云服務是指服務提供者向服務使用者提供的任何類型的IT功能。云服務的典型類別包括基礎架構、平臺、軟件或業(yè)務流程服務，常用 IaaS、PaaS和 SaaS 3個層次來表示［1］。本文主要研究SaaS層的服務部署，它的部署方式有基于PaaS平臺和基于IaaS平臺兩種，圖1和圖2分別表示了這兩種方案。

若SaaS層應用要以獨立于平臺的方式部署在云上，IaaS一定是最佳選擇。應用開發(fā)者或SaaS提供商可租用IaaS提供商提供的各種虛擬機（Virtual Machine，VM），將應用部署到云環(huán)境中，以 SaaS的形式提供給最終用戶使用［2］。但是，IaaS層中的資源，尤其是虛擬機形式的資源，不同配置規(guī)格提供不同的服務質量，也需要不同的服務價格。

圖1　基于PaaS的SaaS部署架構

圖2　基于IaaS的SaaS部署架構

1.2優(yōu)化問題提出

在SaaS中，服務提供商通過接口將功能和數(shù)據(jù)封裝成應用提供給用戶訪問。應用可以理解成服務的集合。服務可以單獨訪問，也可以組合訪問［3］。因此，一個復雜的應用服務通常是由一組子服務以及這些子服務構成的工作流組成。工作流定義了服務之間的交互方式。

不同的SaaS層用戶對應用服務有不同的服務質量需求。為了滿足不同的服務等級協(xié)議（Service Level A-greement，SLA）［4］，SaaS提供商在部署SaaS層的應用服務時，需要考慮使用由 IaaS提供商提供的哪種 VM配置方案以及每個服務需要多少服務實例，從而為每類用戶優(yōu)化服務部署。由于SLA中需要滿足的性能指標較多且可能沖突，同時可能的服務實例和VM類型的組合也較多，因此部署決策問題實際是一個多目標組合優(yōu)化問題。

2　問題的抽象與建模

總結前文分析，可將云計算環(huán)境中的服務部署優(yōu)化問題的基本模型概括為：IaaS提供商給定一組不同配置和價格的虛擬機，SaaS提供商利用這些虛擬機資源部署應用。應用由一組服務及其工作流組成。SaaS提供商需要找到一種部署應用的方案，實現(xiàn)在滿足不同類型的用戶的服務質量需求的情況下，最小化部署費用。

應用中每個服務可生成任意多個服務實例，同一個虛擬機上也可以部署多個不同的服務實例，因此，服務實例與虛擬機的組合結果是無限的。優(yōu)化目標包括延遲、吞吐量和費用，它們無法統(tǒng)一為一個量綱，并存在相互制約關系。

由此可見，云計算環(huán)境中的服務部署優(yōu)化問題是一個典型的多目標組合優(yōu)化問題，問題初始化變量包括服務實例、虛擬機類型以及優(yōu)化指標，可做如下數(shù)學描述：

其中，S代表組成應用的所有服務集合，si對應服務 i；V為云環(huán)境中由IaaS提供商提供的所有虛擬機類型集合，vi對應虛擬機類型i；O代表可優(yōu)化的 SLA中的指標，如延遲、吞吐量、費用等，每個指標都有對應的邊界值，使其在實際問題中有現(xiàn)實意義，這里用 gi（o）≥Ki表示。

S和V中的元素可以任意組合，數(shù)學表述如下：

其中，式（7）表示一個 r（rk）代表某個服務實例（si）部署到某種虛擬機（vj）。R為服務部署的具體方案。式（10）表示一個部署方案R必須保證所有服務實例都被部署。式（11）說明一個部署方案R中，某些服務實例可能被部署多次。圖3表示了某部署問題中，某種部署方案Ri的生成方式。

圖3　部署方案生成示例

由于R所占用的虛擬機種類及數(shù)量會隨集合值的不同而不同，因此，不同R會對應一組不同的O值。R所包含元素的組合方式有很多種，因此服務部署方案，也就是問題的數(shù)學解集RX（式（12））的元素有無窮多個，其中元素Ri代表了一種具體的部署方案，根據(jù) Ri占用的虛擬機資源可得到 Oi，Oi包含了所有要優(yōu)化的目標值，所有 Oi組成的集合定義為 OX，即式（13）。

服務部署優(yōu)化的問題對應于其數(shù)學模型上的求解為在RX中的眾多元素中找到合適的Ri值，使得其對應的Oi值能最好地滿足 SLA中規(guī)定的各項指標，該 Ri即為優(yōu)化服務部署方案。

3　優(yōu)化指標計算及驗證

3.1云環(huán)境中的 SLA

SLA是服務提供者和服務需求者之間定義的關于服務的具體水平的正式協(xié)議，包括服務描述、服務等級參數(shù)、保證以及所有違例情況的行動和補救措施［5］。SaaS應用中的SLA主要關注的是與 SaaS應用的服務質量相關的性能參數(shù)，例如響應時間、吞吐量、可靠性、易用性、可擴展性和操作便捷性等［6］。為了簡化問題，本文選取響應時間、吞吐量和費用3個目標進行優(yōu)化。

3.2服務實例的吞吐量和延遲

設μ是平均單位服務速率，它是平均請求處理時間的倒數(shù)?；讦?，當一個服務實例在多種不同請求到達率下運行在一個具有多種VM配置的部署方案上，可利用排隊論來評估服務實例的吞吐量和延遲。

服務請求的到達可將其表示為一個泊松分布。λ是平均請求到達率，即單位時間內對一個服務實例的請求的平均數(shù)量。

對一個確定的服務實例而言，它對每個請求的服務處理時間一般是固定的，因此將服務實例建模為一個M/D/1排隊，即泊松到達、確定服務時間和單服務窗口。

M/D/1排隊系統(tǒng)的服務時間Tn是定長分布。據(jù)Little公式，可得顧客平均排隊等待時間為［7］：

服務的處理時間與排隊等待時間相比，通?？珊雎圆挥嫞虼?，延遲時間等于排隊等待時間。把式（14）中，可得延遲時間為：

既然μ已知，當λ給定時，Wq就可以計算出來。當λ＞μ時，所有n個CPU核的使用率都超過了100%，此時的服務實例吞吐量就是μ；而當 λ≤μ時，服務實例的吞吐量即為λ。

3.3端到端的QoS值

由于云環(huán)境中的一個應用是由一組服務及其工作流組成的，因此，在計算出應用中各個服務實例的延遲、吞吐量、費用等優(yōu)化指標值之后，還需要計算整個應用的總優(yōu)化指標值，即端到端的QoS（Quality of Service）值。

組成應用的各服務之間存在串聯(lián)、并聯(lián)和分支等多種情況，對同一個服務而言，也可能是一個或多個服務實例同時提供服務。因此，在計算端到端的 QoS值時，需分別考慮這些情況。

3.4仿真實驗驗證

本文用MATLAB等工具對前述理論計算公式進行了實驗驗證。

圖4為在單服務實例情況下，當服務速率μ分別為15 req/s、24 req/s、32 req/s時，在不同請求到達率下的平均延遲曲線圖?？梢钥闯?，當用戶請求到達率λ小于服務速率μ時，測量值與理論值曲線的吻合度較高，誤差較??；當λ接近μ時，據(jù)式（15）可知，延遲值將趨近無限大；當λ＞μ時，理論值公式不再適用，因此與圖4所示實際值誤差較大。綜上所述，當λ＜μ時，該排隊模型和計算公式能夠較為精確地表示單服務實例的延遲值。

圖4　單服務實例平均排隊延遲圖

這里也對端到端的QoS值進行了驗證。假設服務1、2、3和4的服務速率分別是 μ1=24 req/s，μ2=15 req/s，μ3=32 req/s，μ4=32 req/s，圖 5為該應用在不同請求到達率下的端到端延遲值?？梢钥闯?，前述理論計算方法能夠較為精確地表示端到端的延遲值。

圖5　端到端的平均延遲曲線

4　結論

本文通過對云計算環(huán)境中的服務部署情況的詳細分析，提出了在基于云基礎設施對 SaaS層服務進行部署時進行優(yōu)化的必要性。通過抽象和數(shù)學建模，將問題表示成一個多目標組合優(yōu)化問題。最后利用排隊論得出了SLA中的優(yōu)化指標計算方法，并通過仿真實驗進行了驗證。

下一步研究中，可利用此優(yōu)化模型，將實際情況與已有多目標優(yōu)化算法結合，設計出適用于本研究課題的優(yōu)化算法，并通過仿真實驗對算法的有效性進行驗證。

［1］徐星，周劍雄，王明哲.基于模型仿真的云計算 PaaS構建模式選擇［J］.微電子學與計算機，2014（6）：91-96.

［2］曹偉杰，賀建民，孫志丹.IaaS模式下虛擬機部署機制研究［J］.計算機技術與發(fā)展，2012，22（10）：105-108.

［3］張曉娟，易明巍.基于云計算與SOA的企業(yè)集成架構及實現(xiàn)［J］.計算機系統(tǒng)應用，2011，20（9）：1-6.

［4］馮國富，唐明偉，劉林源，等.基于服務級別協(xié)議的云資源分配［J］.計算機科學，2014，41（4）：36-39.

［5］張健.云計算服務等級協(xié)議（SLA）研究［J］.電信網技術，2012（2）：16-21.

［6］程旭.基于SLA的 SaaS應用性能管理機制研究 ［D］.濟南：山東大學，2010.

［7］陸傳賚.排隊論［M］.北京：北京郵電大學出版社，2009.

Service deployment optimization problem modeling based on cloud infrastructure

Xie Bin，Yang Yang，Kuang Yi
（School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China）

The typical cloud infrastructure providers only provide limited types of specifications of virtual machine resources. When the same service is deployed on a different configuration of the virtual machine，it will reflect the different performance.Based on the research and analysis of the service deployment in SaaS，this paper puts forward the need to optimize the service deployment strategies，and abstracts it to a multi-objective combinatorial optimization problem，then models it in mathematical way.

cloud computing；service deployment optimization；multi-objective combinatorial optimization

TP393

A

1674-7720（2015）02-0063-04

國家自然科學基金（61272508）

（2014-09-17）

頡斌（1970-），男，碩士，講師，主要研究方向：計算機網絡，圖像處理與模式識別。

楊揚（1955-），男，博士，教授，主要研究方向：計算機網絡，圖像處理與模式識別。

曠毅（1988-），男，碩士，工程師，主要研究方向：計算機網絡。