云計算中一種基于排隊論的資源分配方案

戴慶龍，李建武

(1.中國電子科技集團(tuán)公司電子科學(xué)研究院 綜合電子信息系統(tǒng)研究所，北京 100041；2.中國電子信息產(chǎn)業(yè)發(fā)展研究院 網(wǎng)絡(luò)空間研究所，北京 100846)

?

云計算中一種基于排隊論的資源分配方案

戴慶龍1，李建武2

(1.中國電子科技集團(tuán)公司電子科學(xué)研究院 綜合電子信息系統(tǒng)研究所，北京 100041；2.中國電子信息產(chǎn)業(yè)發(fā)展研究院 網(wǎng)絡(luò)空間研究所，北京 100846)

為了滿足網(wǎng)絡(luò)不斷發(fā)展條件下對更高資源使用效率的要求，提出了一種基于排隊論的資源分配方案。在這一方案里，云計算中的資源分配被分為單級資源分配和多級資源分配。資源分配的任務(wù)流被抽象為一個隊列模型，實現(xiàn)資源的高效調(diào)度與利用。推導(dǎo)和分析了這一隊列模型的多個性質(zhì)，如到達(dá)任務(wù)數(shù)的性質(zhì)和任務(wù)到達(dá)間隔的性質(zhì)。根據(jù)建立的穩(wěn)態(tài)方程，得到了模型的性能指標(biāo)，如隊列長度、等待隊列長度等。通過數(shù)值仿真，對提出的基于排隊論的資源分配方案進(jìn)行了驗證。

云計算；網(wǎng)絡(luò)虛擬化；資源分配；排隊論

0 引言

云計算是一個技術(shù)集合體，把無處不在、方便、按需的網(wǎng)絡(luò)接入共享的可配置計算資源池(如網(wǎng)絡(luò)、服務(wù)器、存儲、應(yīng)用和業(yè)務(wù))，以最小的管理代價或服務(wù)提供商交互代價，向用戶提供或收回資源[1-3]。在云計算中，網(wǎng)絡(luò)虛擬化的應(yīng)用，使用戶可以專注于業(yè)務(wù)，而不必關(guān)注底層的技術(shù)細(xì)節(jié)[4-5]。云計算業(yè)務(wù)，以一種類似于自來水供應(yīng)或電力供應(yīng)的方式來實現(xiàn)。

網(wǎng)絡(luò)虛擬化，通過把數(shù)據(jù)傳輸和傳輸決策解耦合，允許多個虛擬網(wǎng)絡(luò)在同一物理基礎(chǔ)設(shè)施上共存。在網(wǎng)絡(luò)虛擬化環(huán)境下，每一個虛擬網(wǎng)絡(luò)都是虛擬節(jié)點(diǎn)和虛擬鏈路的集合。本質(zhì)上說，一個虛擬網(wǎng)絡(luò)是底層物理網(wǎng)路資源的一個子集[6]。因此，網(wǎng)絡(luò)虛擬化是靈活、多樣和按需實現(xiàn)的業(yè)務(wù)基礎(chǔ)，也使得網(wǎng)絡(luò)虛擬化的思想被廣泛應(yīng)用于云計算、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化和第五代移動通信網(wǎng)絡(luò)等等[7-9]。

隨著智能移動終端(如手機(jī)、平板電腦等)的普及，用于向用戶提供多種多樣業(yè)務(wù)的數(shù)據(jù)中心得以大規(guī)模建設(shè)。例如，根據(jù)Garter的報告，2016年聯(lián)網(wǎng)的終端設(shè)備達(dá)到了64億臺[10]。另外，物聯(lián)網(wǎng)和工業(yè)4.0的興起，給現(xiàn)有云計算的應(yīng)用帶來了巨大壓力。這些壓力涉及到把數(shù)以億計的事物融合到應(yīng)用了云計算的數(shù)據(jù)中心，及時對這些數(shù)據(jù)進(jìn)行處理，以及虛擬出合適的云資源來承擔(dān)端到端的工業(yè)生命周期的自動運(yùn)轉(zhuǎn)[11-12]。

因此，有必要對云計算中的資源分配性能進(jìn)行評估。評估分析的結(jié)果，可以作為評判資源分配算法優(yōu)劣和設(shè)配采購計劃合理性的基準(zhǔn)。

Khan等人綜述了無線傳感器網(wǎng)絡(luò)虛擬化，給出了現(xiàn)有研究的最新評論和深入討論，研究了無線傳感器網(wǎng)絡(luò)虛擬化的基礎(chǔ)和應(yīng)用場景。在云計算中網(wǎng)絡(luò)傳感器通常被用作前端終端。他們認(rèn)為，網(wǎng)絡(luò)傳感器的推廣應(yīng)用，會給云計算帶來巨大的壓力[13]。

文獻(xiàn)[14-15]研究了異構(gòu)網(wǎng)絡(luò)中一種基于網(wǎng)絡(luò)虛擬化的無縫組網(wǎng)機(jī)制，包括層次模型、業(yè)務(wù)模型、業(yè)務(wù)實現(xiàn)和動態(tài)帶寬分配，評估了應(yīng)用網(wǎng)絡(luò)虛擬化后的性能改變。提出的組網(wǎng)機(jī)制，對云計算研究很有幫助。

Hammad等人提出了基于IP的光網(wǎng)絡(luò)架構(gòu)，利用網(wǎng)絡(luò)虛擬化橫跨IP層和光鏈路層。這一架構(gòu)的設(shè)計目標(biāo)是，提供動態(tài)且靈活的云計算業(yè)務(wù)，以高網(wǎng)絡(luò)容量支撐多速率的數(shù)據(jù)流。這些數(shù)據(jù)流是由多種多樣的業(yè)務(wù)要求造成的[16]。

Khazae等人提出了一種分析模型——任務(wù)服務(wù)時間被滿足通用概率分布，這一模型也給每個節(jié)點(diǎn)的工作流帶來了性能惡化。該分析模型實現(xiàn)了重要性能指標(biāo)的計算[17]。但是，他們的工作并沒有考慮云計算中的多級資源分配。

劃分出來的資源，組裝成的虛擬網(wǎng)絡(luò)，需要映射到傳輸數(shù)據(jù)的物理網(wǎng)絡(luò)之上。為了增大映射方案的選擇范圍，改進(jìn)網(wǎng)絡(luò)性能，Chowdhury等人成功協(xié)同了虛擬節(jié)點(diǎn)映射和虛擬鏈路映射。最初的原始網(wǎng)絡(luò)被看做是一張擴(kuò)增的底層圖，由考慮映射距離的物理網(wǎng)絡(luò)擴(kuò)展而來。虛擬網(wǎng)絡(luò)映射被抽象為一個考慮負(fù)載均衡的最小映射成本混合整數(shù)規(guī)劃問題[18]。

在資源分配的過程中，物理網(wǎng)絡(luò)和分配的資源并不是一成不變的。當(dāng)網(wǎng)絡(luò)發(fā)生變動時，如鏈路失效、業(yè)務(wù)請求變化等，就會進(jìn)行重映射。在這種情況下，重映射的虛擬網(wǎng)絡(luò)實質(zhì)上是一種新增成本。利用增量的重映射機(jī)制，Zhou等人借助原有的已分配資源來承載變動之后的多樣業(yè)務(wù)，這大大降低了成本[19]。

1 基于排隊論的資源分配方案

1.1 云計算框架

云計算框架如圖1所示，底層物理資源由多家基礎(chǔ)設(shè)施提供商(Infrastructure Providers ,InPs)提供，這些物理資源被抽象為虛擬資源，存儲在虛擬資源池中。如果需要實現(xiàn)一個業(yè)務(wù)，云管理者(Cloud Manager)會收到一個資源分配任務(wù)，這個任務(wù)請求承載業(yè)務(wù)所需的資源。云管理者會劃分出一部分資源，組裝成虛擬網(wǎng)絡(luò)，用來承載這一業(yè)務(wù)。在這里，資源請求、資源處理和資源的組裝形成了一個隊列模型。多個虛擬網(wǎng)絡(luò)可以在同一網(wǎng)絡(luò)之上同時共存。

圖1 云計算框架

值得一提的是，在圖1中，VN 1和VN 2由云管理者直接管理，VN 3由子管理者(Sub-Manager)進(jìn)行直接管理，而不是云管理。因此，通過一個隊列的處理，就可以得到VN 1，同理可得VN 2。通過2個隊列的處理，才可以得到VN 3。只需要一個隊列處理的資源分配被稱作單級資源分配。至少需要2個隊列處理的資源分配被稱作多級資源分配。

1.2 基本模型

假設(shè)N(t)是在區(qū)間[0,t)的資源分配任務(wù)數(shù)，Pn(t1,t2)是區(qū)間[t1,t2)中n個任務(wù)到達(dá)的概率，其中t>0，n≥0，因此Pn(t1,t2)=P{N(t2)-N(t1)=n}。任務(wù)到達(dá)時刻服從參數(shù)為λ(λ>0)的泊松分布，λ是一個任務(wù)在某一時刻到達(dá)的可能性，所以：

① 在不重疊的區(qū)間，一個任務(wù)并不會影響另一個任務(wù)，到達(dá)的任務(wù)數(shù)是彼此獨(dú)立的；

② 在一個足夠小的區(qū)間[t,t+ Δt)中，只有一個任務(wù)到達(dá)的概率與時間t無關(guān)，但是這個區(qū)間的大小與Δt呈正比，即：

P1(t,t+Δt)=λ·Δt+O(Δt),

式中，O(Δt)是Δt的高階無窮小，當(dāng)Δt→0時，到達(dá)任務(wù)數(shù)的出現(xiàn)概率為Pn(0,t)=Pn(t)；

③ 在區(qū)間[t,t+ Δt)中，2個或2個以上的任務(wù)同時到達(dá)的概率非常小，可以忽略，即：

(1)

④ 在區(qū)間[t,t+ Δt)中，沒有任務(wù)到達(dá)的概率是：

Ο(Δt)=1-λ·Δt+Ο(Δt)。

(2)

對于N(t)，有以下性質(zhì)：

①N(t)的期望，即E[N(t)]，為λt；

②N(t)的方差，即D[N(t)]，為λt；

③ 2個相鄰任務(wù)的間隔時間服從負(fù)指數(shù)分布。

1.3 單級資源分配

由云管理者處理的任務(wù)被建模為一個隊列模型。其中，任務(wù)間隔服從參數(shù)為1/λ的負(fù)指數(shù)分布，即任務(wù)到達(dá)時間服從參數(shù)為λ的泊松分布，云管理者處理任務(wù)的服務(wù)時間服從參數(shù)μ的負(fù)指數(shù)分布，云管理者的數(shù)量為1，隊列長度的最大值為N個任務(wù)，到達(dá)的服務(wù)數(shù)是正無窮的，即∞，云管理者的服務(wù)原則是先到先處理。

對于該隊列模型，在區(qū)間[t,t+ Δt) ，存在：

① 有一個任務(wù)到達(dá)的概率是λΔt+ O(Δt)，沒有任務(wù)到達(dá)的概率是1-λΔt+ O(Δt)；

② 成功處理掉一個任務(wù)并離開的概率是μΔt+ O(Δt)，沒有業(yè)務(wù)離開的概率是：1-μΔt+O(Δt) ；

③ 有大于等于一個任務(wù)到達(dá)或離開的概率是O(Δt)，可忽略。在時刻t+Δt，存在：

Pn-1(t)λΔt+O(Δt)。

(3)

隨著任務(wù)的增多，隊列模型會趨于穩(wěn)定。在穩(wěn)定的時候，Pn(t)與t無關(guān)，Pn(t)可以簡化為Pn，Pn各個狀態(tài)之間的轉(zhuǎn)換關(guān)系如圖2所示。

圖2 Pn各個狀態(tài)之間的轉(zhuǎn)換關(guān)系

Pn的穩(wěn)態(tài)方程為:

(4)

求解得

① 當(dāng)λ=μ時，P0=P1=…=PN=1/(N+1)；

② 當(dāng)λ≠μ時，令ρ=λ/μ，

(5)

對于隊列模型，有4個重要的指標(biāo)，如圖3所示。

圖3 隊列模型的重要指標(biāo)

① 隊列長度：隊列中的任務(wù)數(shù)，包括等待任務(wù)和處理任務(wù),它的期望為：

(6)

② 等待隊列長度：等待隊列中的任務(wù)數(shù),它的期望為：

(7)

③ 任務(wù)處理時間：任務(wù)到達(dá)到任務(wù)離開的時間,它的期望為：

(8)

④ 任務(wù)等待時間：任務(wù)到達(dá)到離開等待隊列的時間,它的期望為Wq=WS-1/μ。

1.4 多級資源分配

多級資源分配可以看作是若干個單級資源分配的串并聯(lián)。多級資源分配記作Q=(q0,q1, …qk,A)，其中qj是一個單級資源分配，A是K個單級資源分配的鄰接矩陣。事實上，A是K個隊列組成的樹，以q0為根節(jié)點(diǎn)。因此，對于Q，

(9)

式中，Q_LS為Q的隊列長度期望，Q_Lq為Q的等待隊列長度期望，Q_WS為Q的處理時間期望，Q_Wq為Q的等待時間期望，rank(A) 為矩陣A的秩。

2 數(shù)值仿真及結(jié)果

通過MATLAB數(shù)值仿真，分析提出的基于排隊論的資源分配方案的性能。根據(jù)1.3小節(jié)中的公式，Q_LS、Q_Lq、Q_WS、Q_Wq是相關(guān)的。如果能得到其中一個，其他的也可以推導(dǎo)出來。在仿真當(dāng)中，如果沒有特別提到，用到的參數(shù)如表1所示。

表1 仿真參數(shù)

平均隊列長度(LS)和平均到達(dá)任務(wù)數(shù)(λ)的關(guān)系，如圖4所示。平均隊列長度與平均到達(dá)任務(wù)數(shù)呈正比。對于一個隊列，它的任務(wù)處理能力是固定的。隨著平均到達(dá)任務(wù)數(shù)的增長，已經(jīng)到達(dá)且來不及處理的任務(wù)需要在等待隊列中等待，等待隊列長度的增長導(dǎo)致平均隊列長度的增長。

圖4 平均隊列長度與平均到達(dá)任務(wù)數(shù)關(guān)系

平均隊列長度(LS)和任務(wù)處理效率(μ)的關(guān)系，如圖5所示。平均隊列長度與任務(wù)處理效率成反比。隨著任務(wù)處理效率的增長，平均隊列長度下降。到達(dá)的任務(wù)流式確定的，處理效率越高，等待隊列中剩余的待處理任務(wù)越少，因此，平均隊列長度也會下降。

圖5 平均隊列長度與任務(wù)處理效率關(guān)系

平均隊列長度(LS)和隊列最大長度(N)的關(guān)系，如圖6所示。平均隊列長度近乎線性依賴于隊列長度最大值，由于隊列長度最大值是整個隊列模型的容量。隨著隊列長度最大值的增大，平均隊列長度會增大。

圖6 平均隊列長度與隊列最大長度關(guān)系

從數(shù)值仿真可以看出，提出的基于排隊論的資源分配方案能夠?qū)υ朴嬎阒械馁Y源分配進(jìn)行客觀、準(zhǔn)確的描述，成功地建立了關(guān)鍵指標(biāo)(以平均隊列長度為代表)與各影響因素(如平均到達(dá)任務(wù)數(shù)、任務(wù)處理效率和隊列最大長度)之間的關(guān)系。

3 結(jié)束語

本文提出了云計算中一種基于排隊論的資源分配方案，對云計算的資源分配效率進(jìn)行了建模，可以作為評估資源分配算法優(yōu)劣和設(shè)備采購計劃優(yōu)劣的依據(jù)。同時，通過數(shù)值仿真，對提出的基于排隊論的資源分配方案可行性和有效性進(jìn)行了驗證。

[1] Mell P,Grance T.Sp 800-145. The NIST Definition of Cloud Computing[R],2011.

[2] Buyya R,Yeo C S,Venugopal S,et al. Cloud Computing and Emerging IT Platforms: Vision,Hype,and Reality for Delivering Computing as the 5th Utility[J]. Future Generation Computer Systems,2009,25(6): 599-616.

[3] Zhang Q,Cheng L,Boutaba R,et al. Cloud Computing: State-of-the-art and Research Challenges[J]. Journal of Internet Services and Applications,2010,1(1): 7-18.

[4] Armbrust M,Fox A,Griffith R,et al.A View of Cloud Computing[J].Communications of The ACM,2010,53(4):50-58.

[5] Gangadharan G R.Open Source Solutions for Cloud Computing[J]. Computer,2017,50(1):66-70.

[6] Chowdhury N M M K,Boutaba R. A Survey of Network Virtualization[J]. Computer Networks,2010,54(5):862-876.

[7] Liang C,Yu F R,Zhang X,et al. Information-centric Network Function Virtualization over 5G Mobile Wireless Networks[J]. IEEE Network,2015,29(3): 68-74.

[8] Zhang X,Zhu Q. Information-centric Network Virtualization for QoS Provisioning over Software Defined Wireless Networks[C]∥IEEE MILCOM,2016: 1028-1033.

[9] Duan Q,Ansari N,Toy M,et al.Software-defined Network Virtualization: an Architectural Framework for Integrating SDN and NFV for Service Provisioning in Future Networks[J]. IEEE Network,2016,30(5):10-16.

[10]Georgakopoulos D,Jayaraman P P,Fazia M,et al. Internet of Things and Edge Cloud Computing Roadmap for Manufacturing[J]. IEEE Cloud Computing,2016,3(4): 66-73.

[11]Fernando N,Loke S W,Rahayu W,et al.Mobile Cloud Computing: A Survey[J]. Future Generation Computer Systems,2013,29(1): 84-106.

[12]Guo Y,Zhu H,Yang L,et al.Service-oriented Network Virtualization Architecture for Internet of Things[J]. China Communications,2016,13(9):163-172.

[13]Khan I,Belqasmi F,Glitho R,et al.Wireless Sensor Network Virtualization: A Survey[J]. IEEE Communications Surveys and Tutorials,2016,18(1): 553-576.

[14]Dai Q,Shou G,Hu Y,et al.A General Model for Hybrid Fiber-Wireless (FiWi) Access Network Virtualization[C]∥IEEE International Conference on Communications,2013: 858-862.

[15]Dai Q,Zou J,Shou G,et al.Network Virtualization Based Seamless Networking Scheme for Fiber-Wireless (FiWi) Networks[J]. China Communications,2014,11(5):1-16.

[16]Hammad A,Nejabati R,Simeonidou D,et al.Cross-layer Optimization of Network Resource Virtualization in IP over O-OFDM Networks[J]. IEEE/OSA Journal of Optical Communications and Networking,2016,8(10): 765-776.

[17]Khazaei H,Misic J,Misic V B,et al. Performance of Cloud Centers with High Degree of Virtualization under Batch Task Arrivals[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2429-2438.

[18]Chowdhury M,Rahman M R,Boutaba R,et al.Vineyard: Virtual Network Embedding Algorithms with Coordinated Node and Link Mapping[J]. IEEE/ACM Transactions on Networking,2012,20(1):206-219.

[19]Zhou Y,Yang X,Li Y,et al. Incremental Re-Embedding Scheme for Evolving Virtual Network Requests[J]. IEEE Communications Letters,2013,17(5):1016-1019.

A Queueing Theory-based Resource Allocation Scheme in Cloud Computing Environment

DAI Qing-long1,LI Jian-wu2

(1. Institute of Electronic Technology of CETC,Beijing 100041,China; 2. Institute of Cyber Space of CCID,Beijing 100846,China)

In order to meet higher resource usage requirement in network development,this paper proposes a queueing theory-based resource allocation scheme based on. In this scheme,the resource allocation in cloud computing is classified as single-stage resource allocation and multi-stage resource allocation. The resource allocation task flow is modeled as a queue model. The properties of task flow are deduced and analyzed,including arrived task number and task arrival interval. The performances,such as queue length,waiting queue length and etc.,are solved according to established stable equations. At last,through numerical simulation,the performances of the proposed queueing theory-based resource allocation scheme are validated.

cloud computing; network virtualization; queueing theory; resource allocation

2017-05-23

戴慶龍(1988—)，男，博士，工程師，主要研究方向：網(wǎng)絡(luò)虛擬化、云計算、網(wǎng)絡(luò)測試等。李建武(1984—)，男，博士，主要研究方向：移動通信、數(shù)據(jù)分析、網(wǎng)絡(luò)安全等。

10. 3969/j.issn. 1003-3114. 2017.05.11

戴慶龍,李建武. 云計算中一種基于排隊論的資源分配方案[J].無線電通信技術(shù),2017,43(5):47-51.

[ DAI Qinglong,LI Jianwu. A Queueing Theory-based Resource Allocation Scheme in Cloud Computing Environment [J]. Radio Communications Technology,2017,43(5):47-51.]

TP274

A

1003-3114(2017)05-47-5