宋俊鋒

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

?

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

宋俊鋒*

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

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

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

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

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

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

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

本文使用混合整數(shù)線性規(guī)劃(MILP)模型[6]求解一個(gè)利潤(rùn)最優(yōu)化問(wèn)題，為云服務(wù)提供商提供最佳擴(kuò)張策略，以滿足日益增加的需求.求解獲得的策略包括增加數(shù)據(jù)中心的服務(wù)器數(shù)量或新建數(shù)據(jù)中心(包括確定新建數(shù)量、時(shí)間、地點(diǎn)和其能力).圖1描述了超大規(guī)模云計(jì)算數(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ù)中心來(lái)最大化云服務(wù)提供商的收入.本文提出一種離散時(shí)間模型，其中，時(shí)間段被劃分為兩個(gè)級(jí)別：主要級(jí)和次要級(jí).在主要級(jí)中，總體時(shí)間被劃分為以T為周期的時(shí)間段，T可以為十年、一年或一個(gè)月等.在次要級(jí)中，每個(gè)主要時(shí)間段被劃分成H個(gè)時(shí)隙.本文中，T和H分別代表年數(shù)和每年中的小時(shí)數(shù).

(1)

(2)

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

(3)

(4)

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

(5)

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

(13)

(14)

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

1.2 通貨膨脹的影響

2 實(shí)驗(yàn)結(jié)果及分析

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

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

2.1 仿真環(huán)境

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

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

表1 不同時(shí)間段的PUE平均值

Tab.1 The average PUE under different time period

季節(jié)月份平均溫度對(duì)應(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í)驗(yàn)中假設(shè)來(lái)自所有用戶位置的服務(wù)請(qǐng)求總數(shù)為(1.5～2)百萬(wàn)次點(diǎn)擊/秒.每臺(tái)服務(wù)器每秒可處理一個(gè)請(qǐng)求，即μ=3 600.令服務(wù)器使用率上限γmax=0.8.對(duì)于電力價(jià)格，考慮三個(gè)不同時(shí)間段：低峰、平段和高峰值，具體電價(jià)為基于國(guó)內(nèi)工業(yè)用電的平均價(jià)格設(shè)定，分別為：0.3、0.6和1.0元/千瓦時(shí).

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

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

[2] 朱超. 基于虛擬化技術(shù)構(gòu)建高校分布式云計(jì)算數(shù)據(jù)中心[J]. 武漢工程大學(xué)學(xué)報(bào), 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é)報(bào), 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] 羅亮, 吳文峻, 張飛. 面向云計(jì)算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學(xué)報(bào), 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ī)劃項(xiàng)目(2014SCG386)；浙江省教育技術(shù)研究規(guī)劃課題(JB055)

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

TP393

A

1000-5900(2015)04-0105-06