基于MILP的云計算數(shù)據(jù)中心擴(kuò)張策略優(yōu)化模型*

宋俊鋒

(麗水學(xué)院 工程與設(shè)計學(xué)院，浙江 麗水 323000)

?

基于MILP的云計算數(shù)據(jù)中心擴(kuò)張策略優(yōu)化模型*

宋俊鋒*

(麗水學(xué)院 工程與設(shè)計學(xué)院，浙江 麗水 323000)

隨著云計算系統(tǒng)的日益發(fā)展，云服務(wù)提供商需要對大規(guī)模數(shù)據(jù)中心進(jìn)行不斷擴(kuò)張，為此，提出一種基于混合整數(shù)線性規(guī)劃(MILP)的數(shù)據(jù)中心擴(kuò)張策略優(yōu)化模型.綜合考慮了流量負(fù)載、能耗、電力成本、土地成本、稅率、服務(wù)器利用率等多種約束，構(gòu)建MILP模型，在滿足用戶的服務(wù)級別協(xié)議(SLA)下，求解最優(yōu)擴(kuò)張策略，使服務(wù)商利潤最大化.其中，擴(kuò)張策略包括擴(kuò)建現(xiàn)有數(shù)據(jù)中心和在何時何地新建數(shù)據(jù)中心等措施.仿真實驗結(jié)果表明，該模型能夠根據(jù)實際情況獲得最優(yōu)擴(kuò)張策略，提高了利潤.

云計算；數(shù)據(jù)中心擴(kuò)張；混合整數(shù)線性規(guī)劃；優(yōu)化模型；服務(wù)級別協(xié)議

隨著云計算數(shù)據(jù)中心的發(fā)展，企業(yè)不再需要建立和運行自己的服務(wù)器來為用戶提供線上服務(wù)，他們可以以“按使用付費”的方式向云服務(wù)提供商“租用”所需的基礎(chǔ)設(shè)施，以達(dá)到降低成本的目的.云服務(wù)提供商可能擁有分布在不同位置的多個數(shù)據(jù)中心，數(shù)據(jù)中心通常包含成千上萬臺服務(wù)器.隨著需求的增加，即使具有這些龐大的數(shù)據(jù)中心，可能仍然無法提供高質(zhì)量的服務(wù)，即滿足用戶的服務(wù)水平協(xié)議(SLA)[1].這就使得云服務(wù)提供商需要擴(kuò)張云計算中心的規(guī)模，得到一個最優(yōu)的擴(kuò)張策略變得尤為重要，擴(kuò)張策略應(yīng)兼顧提供用戶的服務(wù)質(zhì)量和對服務(wù)提供商的經(jīng)濟(jì)影響[2].

目前，國內(nèi)對于這個問題研究很少，只有國外一些學(xué)者提出一些優(yōu)化方法.例如，[3]提出一種建立數(shù)據(jù)中心最佳位置的選擇策略，其制定了3個目標(biāo)函數(shù)：最小化碳排放，最小化總成本(包括能源、寬帶和稅率)和最小化平均延遲.但是其假設(shè)新建的數(shù)據(jù)中心和其他中心沒有任何關(guān)系，然而，現(xiàn)實中各個數(shù)據(jù)中心是一個整體.[4]考慮了多種因素來選擇數(shù)據(jù)中心的新建位置，包括現(xiàn)有資產(chǎn)、土地成本、運營成本、響應(yīng)時間等等.[5]提出一種最優(yōu)模型，考慮了不同電價的影響，以及負(fù)載、端到端延遲等約束.

本文提出一種用于云計算數(shù)據(jù)中心的擴(kuò)張策略優(yōu)化模型，考慮眾多實際因素并設(shè)定相應(yīng)約束，另外考慮資金貶值的影響，利用混合整數(shù)線性規(guī)劃(Mixed integer-linear programming，MILP)為云服務(wù)提供最優(yōu)的擴(kuò)張策略，在滿足用戶服務(wù)需求的同時最小化擴(kuò)張成本，提高服務(wù)商利潤.實驗結(jié)果表明，本文模型能夠根據(jù)實際情況獲得最優(yōu)擴(kuò)張策略，提高了利潤.

1 擴(kuò)張策略優(yōu)化模型

本文使用混合整數(shù)線性規(guī)劃(MILP)模型[6]求解一個利潤最優(yōu)化問題，為云服務(wù)提供商提供最佳擴(kuò)張策略，以滿足日益增加的需求.求解獲得的策略包括增加數(shù)據(jù)中心的服務(wù)器數(shù)量或新建數(shù)據(jù)中心(包括確定新建數(shù)量、時間、地點和其能力).圖1描述了超大規(guī)模云計算數(shù)據(jù)中心系統(tǒng).

1.1 多約束優(yōu)化模型

本文擴(kuò)張策略優(yōu)化模型的輸入為當(dāng)前數(shù)據(jù)中心的位置、服務(wù)器數(shù)量、成本等多種參數(shù)，然后根據(jù)優(yōu)化模型，選擇新建和/或擴(kuò)大當(dāng)前數(shù)據(jù)中心來最大化云服務(wù)提供商的收入.本文提出一種離散時間模型，其中，時間段被劃分為兩個級別：主要級和次要級.在主要級中，總體時間被劃分為以T為周期的時間段，T可以為十年、一年或一個月等.在次要級中，每個主要時間段被劃分成H個時隙.本文中，T和H分別代表年數(shù)和每年中的小時數(shù).

(1)

(2)

此外，為了保證位置s的數(shù)據(jù)中心在無法處理請求的情況下，不再收到服務(wù)請求，則需滿足約束：

(3)

(4)

令Eusage表示IT設(shè)備功耗占總功耗的比例，并將它作為數(shù)據(jù)中心的功率利用率[8](PUE)的標(biāo)準(zhǔn).令Pidle表示服務(wù)器空閑時的單個服務(wù)器的平均功耗，Ppeak表示處理服務(wù)請求時的單個服務(wù)器的平均功耗.則可以計算出在t年的h小時內(nèi)，候選位置s的功耗，計算公式：

(5)

(6)

式中，μ表示一個小時內(nèi)服務(wù)器可以處理的請求總數(shù).盡管公式(5)和公式(6)都是非線性的，但將公式(6)代入公式(5)即可得到線性公式：

(7)

每個區(qū)域的電網(wǎng)供電量不同，因此，所提出的模型必須確保每小時的總消耗不超過電力總量，約束

(8)

影響服務(wù)質(zhì)量的因素有多個，并且可能會導(dǎo)致違反SLA.時延是其中一個因素，且包含多種類型.在本文所提出的模型中，只關(guān)注傳播時延.令Ds,u為時延約束，確保從用戶u發(fā)送到數(shù)據(jù)中心s的傳播時延不超過SLA允許的最大時延約束：

(9)

為了避免其他方面違反SLA，使用一個常數(shù)上限γmax∈(0,1]限制每個數(shù)據(jù)中心的平均服務(wù)器使用率，即：

(10)

式中，γmax的值取決于服務(wù)質(zhì)量和服務(wù)請求的類型.本文模型中考慮的服務(wù)類型為Web服務(wù)請求，因此，γmax足夠小，以至于可以忽略等待時間.

(11)

數(shù)據(jù)中心的總成本可分為運營成本(OPEX)和資本成本(CAPEX).CAPEX包括土地征用、建造數(shù)據(jù)中心的基礎(chǔ)設(shè)施、電力和數(shù)據(jù)中心帶寬等成本，而OPEX包括電力、稅率、帶寬費用等成本.t年的CAPEX可表示為[9]：

(12)

(13)

(14)

式中，p(x)為服務(wù)請求的等待時間超過SLA允許的最大值的概率，αt是數(shù)據(jù)中心處理單個服務(wù)請求的收費，βt是數(shù)據(jù)中心無法處理單個請求的罰款(例如違反SLA).

1.2 通貨膨脹的影響

2 實驗結(jié)果及分析

本文使用CPLEX與Microsoft Visual Studio構(gòu)建仿真實驗，解決模型的優(yōu)化問題.仿真實驗運行在Windows 7(64位)的虛擬機(jī)上，具有16 GB的RAM和4個處理器.

CPLEX是一種混合整數(shù)線性規(guī)劃問題(MILP)求解器，它基于分支定界算法進(jìn)行整數(shù)規(guī)劃，可通過放松整數(shù)約束獲得有效的次優(yōu)解決方案.在本文所提出的模型中，可以離線為云服務(wù)提供商作出最佳的擴(kuò)張策略決策.

2.1 仿真環(huán)境

本文以河南省為例，為了確保滿足公式(8)的限制，針對不同市的情況，將電力的最大可用功率設(shè)定為100MW/h.數(shù)據(jù)中心候選位置如圖2所示.

在確定數(shù)據(jù)中心集合S后，接下來確定其他輸入?yún)?shù).數(shù)據(jù)中心最大和最小服務(wù)器數(shù)量mmax和mmin分別設(shè)置為5 000和50 000.本文設(shè)置工作功耗(Ppeak)和空閑功耗(Pidle)分別為140W和84W.通常將功率利用率(PUE)設(shè)置為固定值1.3，本文中考慮外界溫度變化對PUE的影響，如圖3所示.考慮春夏秋冬四季的溫度，為方便計算，所有溫度均為這一時段的均值.溫度數(shù)據(jù)從一些文獻(xiàn)獲取，詳情見表1.

表1 不同時間段的PUE平均值

Tab.1 The average PUE under different time period

季節(jié)月份平均溫度對應(yīng)PUE值春3/4/515℃1.18夏6/7/825℃1.57秋9/10/1116℃1.18冬12/1/27℃1.10

關(guān)于流量負(fù)載，實驗中假設(shè)來自所有用戶位置的服務(wù)請求總數(shù)為(1.5～2)百萬次點擊/秒.每臺服務(wù)器每秒可處理一個請求，即μ=3 600.令服務(wù)器使用率上限γmax=0.8.對于電力價格，考慮三個不同時間段：低峰、平段和高峰值，具體電價為基于國內(nèi)工業(yè)用電的平均價格設(shè)定，分別為：0.3、0.6和1.0元/千瓦時.

2.2 優(yōu)化模型仿真結(jié)果

本節(jié)將進(jìn)行兩個實驗，以評估所提出的擴(kuò)張策略的優(yōu)化模型的性能.

在第一個實驗中，在12個數(shù)據(jù)中心位置上運行該模型5年時間.其中一半是現(xiàn)存的數(shù)據(jù)中心，另一半待建設(shè).假設(shè)單個數(shù)據(jù)中心中放置的服務(wù)器數(shù)量在5 000和50 000臺之間.CAPEX取決于兩個方面：建設(shè)成本和服務(wù)器成本.假設(shè)每臺服務(wù)器成本為1萬元.對于建設(shè)成本，根據(jù)各個市的情況，假設(shè)云服務(wù)提供商第一年的CAPEX初始投資為5億元，隨后幾年的建設(shè)成本由之后所得的利潤提供.

表2給出了根據(jù)優(yōu)化模型計算，得出的5年內(nèi)每個數(shù)據(jù)中心服務(wù)器的數(shù)量.該表顯示服務(wù)器的數(shù)量隨著時間的推移和流量載荷的增加而增加.在開始時，只有一個現(xiàn)存的數(shù)據(jù)中心(DC1)負(fù)載較低，而其他5個負(fù)載較高.在第二年，DC1保持低負(fù)載(可能由于高運營成本或高延遲)，而高負(fù)載的數(shù)據(jù)中心幾乎達(dá)到滿負(fù)荷.此外，新建了3個數(shù)據(jù)中心.在接下來的幾年保持同樣的趨勢.低運營成本和低時延數(shù)據(jù)中心通過增加服務(wù)器的數(shù)量進(jìn)行擴(kuò)張，直到它們達(dá)到滿負(fù)載.如果無法處理新產(chǎn)生的流量，那么就得新建數(shù)據(jù)中心.實驗的最后一年，云服務(wù)提供商在所有候選位置上建立數(shù)據(jù)中心來處理大量的服務(wù)請求.

表2 在5年中，每個數(shù)據(jù)中心的服務(wù)器數(shù)量

在第二個實驗中，使用固定PUE值和變化PUE值、固定電價和分時段電價，建立4個案例，其中固定值設(shè)定為一個周期內(nèi)變化值的平均值.案例1：固定PUE和固定電價.案例2：固定PUE和分時段電價.案例3：變化PUE和固定電價.案例4：變化PUE和分時段電價.

圖4顯示了四種情況下所產(chǎn)生的年利潤，每年實際獲得利潤的顯著增加.從圖4可以看出，合理利用不同的PUE值對年利潤具有很大影響，相比于固定PUE值平均增加13%.另外，利用分時段電價可以進(jìn)一步提高年利潤(平均提高2%).同時，利用變化PUE和分時段電價能夠平均增加14%的年利潤.

3 結(jié)束語

隨著超大規(guī)模數(shù)據(jù)中心的發(fā)展，針對降低數(shù)據(jù)中心運營成本的研究仍處于起步階段.本文提出一種為云服務(wù)提供商作出最佳擴(kuò)張策略的決策模型.本文模型中考慮許多因素，如電力成本、帶寬成本、稅率、功耗和服務(wù)器利用率等.本文研究可以在各個方向擴(kuò)展，以減少數(shù)據(jù)中心的能量成本和功率密度.未來工作中，將考慮服務(wù)器整合，將任務(wù)分配給當(dāng)前任務(wù)最少的服務(wù)器，關(guān)閉未使用的服務(wù)器，實現(xiàn)動態(tài)的啟動和停止服務(wù)器，進(jìn)一步節(jié)約成本.

[1] 鄧維, 劉方明, 金海,等. 云計算數(shù)據(jù)中心的新能源應(yīng)用:研究現(xiàn)狀與趨勢[J]. 計算機(jī)學(xué)報, 2013, 36(3):582-598.

[2] 朱超. 基于虛擬化技術(shù)構(gòu)建高校分布式云計算數(shù)據(jù)中心[J]. 武漢工程大學(xué)學(xué)報, 2011, 33(4):100-102.

[3] CARROLL R, BALASUBRAMANIAM S, BOTVICH D, et al. Dynamic optimization solution for green service migration in data centres[C]// Communications (ICC), 2011 IEEE International Conference on IEEE, 2011:1-6.

[4] ZHANG Y, WANG Y, WANG X. Capping the electricity cost of cloud-scale data centers with impacts on power markets[C]//Proceedings of the 20th International ACM Symposium on High-Performance Parallel and Distributed Computing, 2011:271-272.

[5] LI J, LI Z, REN K, et al. Towards optimal electric demand management for internet data centers[J]. Smart Grid IEEE Transactions on, 2012, 3(1):183-192.

[6] 陳彬, 鮑東暉, 蘇恭超,等. 基于路徑的整數(shù)線性規(guī)劃方法在阻塞IP over WDM網(wǎng)絡(luò)中能耗優(yōu)化的應(yīng)用[J]. 電子與信息學(xué)報, 2015, 37(3):715-720.

[7] HEDDEGHEM W V, VEREECKEN W, COLLE D, et al. Distributed computing for carbon footprint reduction by exploiting low-footprint energy availability[J]. Future Generation Computer Systems, 2012, 28(2):405-414.

[8] 羅亮, 吳文峻, 張飛. 面向云計算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學(xué)報, 2014, 25(7):1 371-1 387.

[9] BERRAL J L, GOIRI I, NGUYEN T D,et al. Building green cloud services at low cost[C]// Distributed Computing Systems (ICDCS), 2014 IEEE 34th International Conference on IEEE, 2014:449-460.

[10] SHUJA J, BILAL K, MADANI S A, et al. Survey of techniques and architectures for designing energy-efficient data centers[J]. IEEE Systems Journal,2014,99:1-13.

責(zé)任編輯：龍順潮

Optimizing Expansion Strategies Based on MILP for Cloud Computing Data Centers

SONGJun-feng*

(College of Engineering and Design, Lishui College, Lishui 323000 China)

With the increasing development of cloud computing systems, the large-scale data center is need to expand by cloud service providers, therefore, an optimizing expansion strategies based on mixed integer-linear programming(MILP) for cloud computing data centers is proposed. The energy consumption, electricity costs, land costs, tax rate, server utilization and many kinds of constraint are considered to build MILP model, under meet the user service level agreement (SLA), solving the optimal expansion strategy to maximize the profits of service providers. The expansion strategy includes the expansion of the existing data center or / and when and where to build new data centers. The simulation results show that the model can obtain the optimal expansion strategy according to the actual situation, and improve the profit.

cloud computing; expansion of data centers; mixed integer-linear programming; optimization model;service level agreement

2015-05-22

浙江省教育科學(xué)規(guī)劃項目(2014SCG386)；浙江省教育技術(shù)研究規(guī)劃課題(JB055)

宋俊鋒(1984- )，男，浙江 縉云人，工程師. E-mail:songjfjls@126.com

TP393

A

1000-5900(2015)04-0105-06