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

戴慶龍，李建武

(1.中國電子科技集團公司電子科學研究院 綜合電子信息系統研究所，北京 100041；2.中國電子信息產業發展研究院 網絡空間研究所，北京 100846)

?

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

戴慶龍1，李建武2

(1.中國電子科技集團公司電子科學研究院 綜合電子信息系統研究所，北京 100041；2.中國電子信息產業發展研究院 網絡空間研究所，北京 100846)

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

云計算；網絡虛擬化；資源分配；排隊論

0 引言

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

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

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

因此，有必要對云計算中的資源分配性能進行評估。評估分析的結果，可以作為評判資源分配算法優劣和設配采購計劃合理性的基準。

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

文獻[14-15]研究了異構網絡中一種基于網絡虛擬化的無縫組網機制，包括層次模型、業務模型、業務實現和動態帶寬分配，評估了應用網絡虛擬化后的性能改變。提出的組網機制，對云計算研究很有幫助。

Hammad等人提出了基于IP的光網絡架構，利用網絡虛擬化橫跨IP層和光鏈路層。這一架構的設計目標是，提供動態且靈活的云計算業務，以高網絡容量支撐多速率的數據流。這些數據流是由多種多樣的業務要求造成的[16]。

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

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

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

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

1.1 云計算框架

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

圖1 云計算框架

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

1.2 基本模型

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

① 在不重疊的區間，一個任務并不會影響另一個任務，到達的任務數是彼此獨立的；

② 在一個足夠小的區間[t,t+ Δt)中，只有一個任務到達的概率與時間t無關，但是這個區間的大小與Δt呈正比，即：

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

式中，O(Δt)是Δt的高階無窮小，當Δt→0時，到達任務數的出現概率為Pn(0,t)=Pn(t)；

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

(1)

④ 在區間[t,t+ Δt)中，沒有任務到達的概率是：

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

(2)

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

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

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

③ 2個相鄰任務的間隔時間服從負指數分布。

1.3 單級資源分配

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

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

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

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

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

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

(3)

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

圖2 Pn各個狀態之間的轉換關系

Pn的穩態方程為:

(4)

求解得

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

② 當λ≠μ時，令ρ=λ/μ，

(5)

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

圖3 隊列模型的重要指標

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

(6)

② 等待隊列長度：等待隊列中的任務數,它的期望為：

(7)

③ 任務處理時間：任務到達到任務離開的時間,它的期望為：

(8)

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

1.4 多級資源分配

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

(9)

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

2 數值仿真及結果

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

表1 仿真參數

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

圖4 平均隊列長度與平均到達任務數關系

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

圖5 平均隊列長度與任務處理效率關系

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

圖6 平均隊列長度與隊列最大長度關系

從數值仿真可以看出，提出的基于排隊論的資源分配方案能夠對云計算中的資源分配進行客觀、準確的描述，成功地建立了關鍵指標(以平均隊列長度為代表)與各影響因素(如平均到達任務數、任務處理效率和隊列最大長度)之間的關系。

3 結束語

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

[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—)，男，博士，工程師，主要研究方向：網絡虛擬化、云計算、網絡測試等。李建武(1984—)，男，博士，主要研究方向：移動通信、數據分析、網絡安全等。

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

戴慶龍,李建武. 云計算中一種基于排隊論的資源分配方案[J].無線電通信技術,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