一種IaaS服務中的雙時間尺度用戶動態競價和資源管理算法的製作方法
2023-04-24 04:41:51
本發明屬於雲計算技術領域，特別涉及一種IaaS服務中的雙時間尺度用戶動態競價和資源管理算法。
背景技術：
亞馬遜提供三種租賃服務實例：預留型實例、按需型實例和現貨型實例。預留型實例的單價較低，但是雲用戶必須與雲提供商籤訂較長時間的租賃協議(通常在1-3年)。按需型實例以較小的時間粒度(以小時為單位)被動態分配給用戶，可用來應對工作負載的激增。現貨型實例的價格是隨著資源的供需關係不斷變化的，只要雲用戶給出的價格高於亞馬遜給出的價格，則用戶可一直租賃該伺服器。一般情況下，雲用戶選擇預留型實例處理基本的資源需求，當工作負載出現大幅波動時，用戶可選用按需型實例和現貨型實例。如何為雲用戶設計一個動態競價與資源分配算法，以降低其資源租用成本，是一個亟待解決的問題。
技術實現要素：
為了克服上述現有技術的缺點，本發明的目的在於提供一種IaaS服務中的雙時間尺度用戶動態競價和資源管理算法，旨在為雲用戶提供一種動態資源競價與管理機制，降低雲用戶使用亞馬遜IaaS服務的資源租賃成本，該機制在兩個時間尺度上進行操作：在粗時間尺度下，動態決定競價與租賃伺服器的數量，同時進行任務調度；在細時間尺度下，對伺服器進行分配。
為了實現上述目的，本發明採用的技術方案是：
一種IaaS服務中的雙時間尺度用戶動態競價和資源管理算法，包括：
構建伺服器端模型：假設雲提供商運營了n個位於不同地理位置的數據中心，每個數據中心包含若干虛擬機伺服器資源，雲用戶對這些數據中心發起伺服器租賃請求，假設虛擬機的配置全都是相同的，即相同的作業系統和硬體配置；數據中心中具有檢查點機制和數據遷移技術，保證中斷的任務可以在用戶使用權被終止後在其他伺服器繼續處理；
構建數據中心模型：假設任務共有k種類型，雲用戶通過代理與數據中心j建立聯繫，代理負責緩存到達的任務，並輔助雲用戶進行資源管理決策，令代理j與數據中心j的隊列分別為Qij與qij，下標i代表第i類任務，在t時刻，各種類型的任務到達代理j對應的Qij隊列，代理j決定這些任務到數據中心隊列qij的分配方式；
控制決策與系統動態演變：以降低伺服器的租賃成本為目標，在雙時間尺度進行雲用戶控制決策：在細粒度上的時間尺度為時間槽，在粗粒度上的時間尺度為幀，一個幀包含數個時間槽，幀的長度由用戶指定；
動態資源競價與分配：以最小化用戶租賃按需型和現貨型實例的平均費用為目標，進行動態資源分配。
所述伺服器端模型中，令為t時刻數據中心j中現貨型實例的價格，假設有界，其中最大值為所述數據中心模型中，t時刻，有aij(t)個i類任務到達代理j，aij(t)服從任意有界隨機分布，其有界性假設為0≤aij(t)≤amax，amax為任務到達的上界。
所述控制決策與系統動態演變過程中：假設現貨型實例的價格每個時間槽更新一次，則雲用戶控制決策的架構表示為：
代理j在每一幀決定數據中心j的以下參數：
1)租用按需型伺服器的數量；
2)bj(t)，現貨型實例的競價；
3)若出價成功，應該租賃的現貨型伺服器的數量；
每一幀下，到達的任務進入代理j的隊列後，代理j為任務決定任務的路由策略rijj』，即任務由Qij到qij』的路由方式，Qij隊列動態更新模型為
每一時間槽下，雲用戶決定虛擬伺服器分配策略yij(t)，即分配給數據中心j的第i類任務的伺服器數量，隊列qij動態更新模型為
其中si是i類任務的服務速率。
所述控制決策的約束定義如下：
首先定義任務路由策略的可行域，即
rijj'(t)∈R
R包含實際問題中的約束條件，其次，虛擬伺服器分配策略必須滿足
上式意味著被分配的伺服器數量與租用的伺服器總數相同；
最後，對於上述約束條件，有如下有界性約束
0≤bj(t)≤bmax,
0≤yij(t)si≤ymax。
所述動態資源競價與分配中，將動態資源競價與分配問題定義為約束條件為：
rijj'(t)∈R，
0≤bj(t)≤bmax，
0≤yij(t)si≤ymax，
其中，目標函數的前半部分是按需型實例的租賃費用，後半部分是現貨型實例的租賃費用，是一個示性函數，標誌是否出現了現貨型實例價格高於用戶競價的事件，該函數定義為
本發明可採用基於李雅普諾夫優化理論的方法，求解動態資源競價與分配問題，李雅普諾夫函數的定義為
令Q(t)＝{Qij(t)}，q(t)＝{qij(t)}，i＝1,...,k,j＝1,...,n，且θ(t)＝{Q(t),q(t)}；
定義T個時間槽的李雅普諾夫偏移ΔT(t)＝E{L(t+T)-L(t)|θ(t)}；
李雅普諾夫優化技術並不直接求解動態資源競價與分配問題，而是試圖最小化偏移懲罰目標函數的上界。
所述偏移懲罰目標函數的上界通過如下方式求解：
命題1：當t＝mT，m∈Z+時，確定一個非負值V和可行的控制決策bj(t)，和rijj'(t)，有
其中
或者：
命題2：當t＝mT，m∈Z+時，確定一個非負值V和可行的控制決策bj(t)，和rijj'(t)，有
其中
本發明可通過如下算法實現動態資源競價與分配：
1)競價與伺服器分配
在時刻t＝mT，每一個代理j需求解
約束條件為：
0≤bj(t)≤bmax，
0≤yij(t)si≤ymax，
在[t,t+T-1]期間，如果代理j出價bj(t)成功，那麼它將獲取臺按需型伺服器和臺現貨型伺服器；如果出價失敗，代理j不會得到現貨型伺服器。
2)任務路由
在時刻t＝mT，代理j需求解
約束條件為：
rijj'(t)∈R，
從隊列Qij調度rijj'(t)個任務到隊列qij；
3)伺服器分配
每一時間槽τ∈[t,t+T-1]，代理j通過下式決定分配給隊列qij的虛擬伺服器數量yij(τ)
約束條件為：
0≤yij(t)si≤ymax，
4)隊列更新
每個時間槽隊列按照式和更新。
與現有技術相比，本發明為雲用戶提供了一種動態資源競價與管理機制，可降低雲用戶使用亞馬遜IaaS服務的資源租賃成本。
附圖說明
圖1是本發明數據中心系統框架示意圖。
圖2是本發明雙時間尺度決策框架示意圖。
具體實施方式
下面結合附圖和實施例詳細說明本發明的實施方式。
1.符號說明：本發明模型中所用到的符號如表1所示。
表1本發明所用到的符號及其描述
2.構建伺服器端模型，包括以下幾個部分：
A.假設雲提供商運營了n個位於不同地理位置的數據中心，每個數據中心包含若干虛擬機伺服器資源。雲用戶對這些數據中心發起伺服器租賃請求。假設虛擬機的配置全都是相同的，即相同的作業系統和硬體配置。亞馬遜對於現貨型實例的收費方式如下：
2.1用戶向雲提供商發出伺服器租賃請求，包括競價價格和租賃的伺服器數量。
2.2若提供商的現貨型實例的當前價格低於用戶的競價，則用戶獲得這些伺服器的使用權。
2.3若當前現貨型實例價格高於用戶的競價，提供商在不通知用戶的情況下終止其使用權。
2.4若現貨型實例價格低於用戶的競價，那麼雲提供商將按照當前現貨型實例的價格作為收取用戶的實際價格。
2.5若用戶的使用權被雲提供商終止，且不滿一小時，則雲提供商不收取用戶最後一小時的費用。反之，用戶需向提供商繳納所有費用。
2.6若用戶主動終止現貨型實例的使用，則不足一小時按一小時收費。
B.數據中心中具有檢查點機制和數據遷移技術，保證中斷的任務可以在用戶使用權被終止後在其他伺服器繼續處理。令為t時刻數據中心j中現貨型實例的價格，假設有界，其中最大值為
3.構建數據中心模型，包括以下幾個部分：
A.數據中心模型如附圖1所示，系統可以處理例如大數據分析和MapReduce等容時(Delay-tolerant)任務。假設任務共有k種類型。雲用戶通過代理(Broker)與數據中心j建立聯繫。代理負責緩存到達的任務，並輔助雲用戶進行資源管理決策。令代理j與數據中心j的隊列分別為Qij與qij。下標i代表第i類任務。在t時刻，各種類型的任務到達代理j對應的Qij隊列。代理j決定這些任務到數據中心隊列qij的分配方式。
B.t時刻，有aij(t)個i類任務到達代理j，aij(t)可服從任意有界隨機分布，其有界性假設為0≤aij(t)≤amax。
4.控制決策與系統動態演變
A.雲用戶控制決策的目標在於降低伺服器的租賃成本。由於預留型實例的伺服器數在合同期限內無法動態變化(合同期限比決策時間間隔大幾個數量級)，因此假設已被預先決定。如附圖2所示，用戶在雙時間尺度進行控制決策：在細粒度上的時間尺度為時間槽(slot)，在粗粒度上的時間尺度為幀(frame)。一個幀包含數個時間槽，幀的長度由用戶指定，一般可設置為一小時。假設現貨型實例的價格每個時間槽更新一次，則雲用戶控制決策的架構可以表示為：
代理j在每一幀決定數據中心j的以下參數：1)租用按需型伺服器的數量。2)bj(t)，現貨型實例的競價。3)若出價成功，應該租賃的現貨型伺服器的數量。
每一幀下，到達的任務進入代理j的隊列後，代理j為任務決定任務的路由策略rijj』，即任務由Qij到qij』的路由方式。因此，Qij隊列動態更新模型為
每一時間槽下，雲用戶決定虛擬伺服器分配策略yij(t)，即分配給數據中心j的第i類任務的伺服器數量。因此，隊列qij動態更新模型為
其中si是i類任務的服務速率。
B.控制決策的約束定義如下：
首先定義任務路由策略的可行域，即
rijj'(t)∈R (3)
R包含實際問題中的約束條件。其次，虛擬伺服器分配策略必須滿足
上式意味著被分配的伺服器數量與租用的伺服器總數相同。最後，對於上述約束條件，有如下有界性約束
0≤bj(t)≤bmax, (7)
0≤yij(t)si≤ymax。 (9)
5.動態資源競價與分配問題
A.動態資源分配問題的目標是最小化用戶租賃按需型和現貨型實例的平均費用，定義為
約束條件：(3)，(4)，(5)，(6)，(7)，(8)，(9)。
目標函數的前半部分是按需型實例的租賃費用，後半部分是現貨型實例的租賃費用。是一個示性函數，標誌是否出現了現貨型實例價格高於用戶競價的事件，該函數定義為
式(11)為隊列穩定性約束，保證了有限的平均排隊等待時間。
本發明採用基於李雅普諾夫優化理論的方法，求解動態資源競價與分配問題。
1.李雅普諾夫優化技術
A.李雅普諾夫函數的定義為
令Q(t)＝{Qij(t)}，q(t)＝{qij(t)}，i＝1,...,k,j＝1,...,n，且θ(t)＝{Q(t),q(t)}。
B.定義T個時間槽的李雅普諾夫偏移
ΔT(t)＝E{L(t+T)-L(t)|θ(t)}。
C.李雅普諾夫優化技術並不直接求解動態資源競價與分配問題，而是試圖最小化如下偏移懲罰目標函數的上界
2.偏移懲罰目標函數的上界
A.命題1：當t＝mT，m∈Z+時，確定一個非負值V和可行的控制決策bj(t)，和rijj'(t)，有
其中
命題1給出了偏移懲罰目標函數的上界。然而，對式(14)的右半部分進行優化較為困難，原因在於隊列Qij(τ)與qij(τ)的狀態是未知的。同時，在τ∈[t+1,...t+T-1]時，任務請求到達也是未知的。
B.為了解決以上問題，本發明將式(14)中的上界進行鬆弛處理，得到放大的上界，如命題2所示。
命題2：當t＝mT，m∈Z+時，確定一個非負值V和可行的控制決策bj(t)，和rijj'(t)，有
其中
3.動態資源競價與分配算法
動態資源競價與分配算法如下所示：
3.1競價與伺服器分配。在時刻t＝mT，每一個代理j需求解
約束條件為(4)，(5)，(6)，(7)，(9)。在[t,t+T-1]期間，如果代理j出價bj(t)成功，那麼它將獲取臺按需型伺服器和臺現貨型伺服器。如果出價失敗，代理j不會得到現貨型伺服器。
3.2任務路由。在時刻t＝mT，代理j需求解
約束條件為(3)和(8)，從隊列Qij調度rijj'(t)個任務到隊列qij。
3.3伺服器分配。每一時間槽τ∈[t,t+T-1]，代理j通過下式決定分配給隊列qij的虛擬伺服器數量yij(τ)
約束條件為(4)和(9)。
3.4隊列更新。每個時間槽隊列按照式(17)和(18)更新。
動態資源競價與分配算法是一種結構簡單的分布式算法，包含任務調度問題(17)和伺服器分配問題(18)。每個代理單獨決定本地的控制決策，代理之間需要共享的唯一信息是隊列長度。