云计算中一种基于排队论的资源分配方案

戴庆龙，李建武

(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