聯(lián)合成本優(yōu)化和隊列穩(wěn)定的數(shù)據(jù)中心調(diào)度算法

孫佑明

(巢湖學(xué)院 信息工程學(xué)院，安徽 巢湖 238000)

假設(shè)數(shù)據(jù)中心[1-2]是由一個中央控制器和N個服務(wù)器組成，每個服務(wù)器n有三種基本狀態(tài)：活動狀態(tài)，此時服務(wù)器n可用于服務(wù)請求并產(chǎn)生成本en；睡眠狀態(tài)，此時服務(wù)器處于低成本的休眠狀態(tài)，不提供任何服務(wù)請求；啟動狀態(tài)，此時服務(wù)器處于從空閑到活動狀態(tài)的過渡期.通過選擇特定的睡眠模式和睡眠時間，處于活動狀態(tài)的服務(wù)器可以在任意時刻過渡到睡眠狀態(tài).例如，深度睡眠模式可以關(guān)閉更多的電子設(shè)備，從而節(jié)省更多的成本；但從深度睡眠狀態(tài)過渡到活動狀態(tài)需要更長的時間.每個服務(wù)器分別決定何時轉(zhuǎn)換和使用什么睡眠模式，每個服務(wù)器的轉(zhuǎn)換時間是異步的.中央控制器將請求調(diào)度至服務(wù)器，也可能拒絕請求.

1 問題建模

在每個時刻t∈{0,1,2,…}，新請求的到達(dá)率是λ(t)，其中：λ(t)∈Λ.Rn(t)表示服務(wù)器n接收到的請求數(shù)量，d(t)是被服務(wù)器n拒絕的請求數(shù)量，而c(t)∈C是每一個被拒絕請求的成本.Rn(t)和d(t)之間需要滿足如下的關(guān)系：

(1)

(2)

每個服務(wù)器n都維護(hù)一個請求隊列Qn(t)，Qn(t)的計算如下：

Qn(t+1)=max{Qn(t)+Rn(t)-μn(t)Hn(t),0}

(3)

Hn(t)是一個指示變量.若Hn(t)=1，則服務(wù)器n在時刻t處于活動狀態(tài)；否則，Hn(t)=0.μn(t)是一個隨機變量，表示時刻t請求的服務(wù)率，其平均值為μn.每個隊列初始化為Qn(0)=0.

(4)

其中，In[f]是服務(wù)器處于睡眠狀態(tài)的時間，τn[f]是服務(wù)器處于啟動狀態(tài)的時間.

本文的目標(biāo)是最小化調(diào)度過程的總成本，同時保持系統(tǒng)的穩(wěn)定，該優(yōu)化問題如下所示：

(5)

(6)

其中，第一個約束條件要求平均服務(wù)率不能小于請求的平均達(dá)到率，這樣一來隊列就不會堆積，系統(tǒng)才能趨于穩(wěn)定狀態(tài).接下來的目標(biāo)是設(shè)計一種算法，該算法中每個服務(wù)器都可以獨立地、分布式地進(jìn)行調(diào)度，無需獲取其他服務(wù)器的工作負(fù)載或調(diào)度決策，并能夠依概率接近最優(yōu).

2 實時在線調(diào)度算法

(7)

對于每一個時刻t，通過求解以下的優(yōu)化問題，我們能得到Rn(t)和d(t)：

(8)

此時，有

(9)

(10)

(11)

其中，B0=(Rmax+μmax)μmax/2.如果服務(wù)器選擇轉(zhuǎn)換成活動狀態(tài)(即αn[f]=active)，那么就有

(12)

如果服務(wù)器轉(zhuǎn)換為睡眠狀態(tài)，則有

(13)

然后，服務(wù)器計算確定性優(yōu)化問題(14)的最小值.對于αn∈Ln，對公式(14)關(guān)于In[f]求導(dǎo)，以得到最小解.然后將該最小解與式(12)的值進(jìn)行比較，若式(12)的值小于最小解，則服務(wù)器進(jìn)入活動狀態(tài)；否則，服務(wù)器選擇進(jìn)入睡眠狀態(tài).

(14)

3 仿真實驗

在本節(jié)中，我們將通過大量的仿真實驗來驗證算法的性能.本文的算法達(dá)到了Ο(1/V)接近最優(yōu).我們將本文算法與其他幾種啟發(fā)式算法進(jìn)行了比較，結(jié)果表明，該算法確實具有較低的時延和較低的功耗.

圖1 平均成本與V值的關(guān)系

在第一部分的仿真實驗中，我們使用了一個較小規(guī)模的數(shù)據(jù)中心模型.服務(wù)器的數(shù)量N=5，請求率λ(t)服從[10,30]的均勻分布，拒絕成本c(t)服從[1,6]的均勻分布，Rmax=40.仿真實驗的運行時間是10 000個時刻.圖1展示了隨著權(quán)衡參數(shù)V變大，時間平均成本逐漸接近最優(yōu)值.當(dāng)V值很小的時候，成本曲線迅速下降；當(dāng)V值變大時，成本曲線變得平坦.這說明了本文算法以Ο(1/V)接近最優(yōu).

在第二部分的仿真實驗中，我們采用真實數(shù)據(jù)中心流量[4-5]作為實驗數(shù)據(jù)集.實驗的總時間為1 500 s.圖2和圖3分別是隨著V值的變大，系統(tǒng)平均功耗和隊列長度的變化.由結(jié)果可以看出，V值對平均功耗沒有太大的影響，但是隊列長度卻受V值影響.接下來，我們將本文算法與其他策略進(jìn)行比較，圖4和圖5分別是平均功耗和隊列長度的實驗結(jié)果.在實驗的開始部分，所有算法都表現(xiàn)良好.但在后半部分，隨著流量增加，主動算法的隊列長度劇烈增加.由于啟動時間長，被動算法中處于活動狀態(tài)的服務(wù)器數(shù)量無法適應(yīng)不斷增加的流量，因此隊列長度也會增加.本文提出的算法在穩(wěn)定隊列的同時最小化了功耗，因此在性能上超過了主動算法和被動算法.

圖2 不同V值下平均能耗隨時間的變化

圖3 不同V值下隊列長度隨時間的變化

圖4 不同算法下平均能耗隨時間的變化

圖5 不同算法下隊列長度隨時間的變化

4 結(jié)語

本文提出了一種高效的分布式異步控制算法，以降低數(shù)據(jù)中心的成本.該算法在穩(wěn)定請求隊列的同時，實現(xiàn)了接近最優(yōu)的開銷.在仿真實驗部分，我們使用真實的數(shù)據(jù)中心流量驗證本文算法.未來的研究工作在于加強對本文算法的理論分析，從理論上進(jìn)一步證明算法的性能.