视频服务节点共享资源池的分布式最优控制

宋 辰,奚宏生

(中国科学技术大学自动化系,合肥230027)

视频服务节点共享资源池的分布式最优控制

宋 辰,奚宏生

(中国科学技术大学自动化系,合肥230027)

针对三网融合背景下的视频服务网,研究实时服务提供设备(RSPE)的节点共享资源池的资源配置,提出一种完全分布式的最优控制解决方案。分别将物理计算资源和RSPE节点视为计算资源的共享池和资源消费者,给出RSPE节点之间的信息传播策略和分布式优化算法,从而实现资源池的分布式最优控制。仿真结果表明,在RSPE节点变化较小的情况下,该方案可保证节点间信息传播过程的收敛性和共享资源的最优资源配置。

三网融合;视频服务网;共享资源池;资源分配;分布式最优控制;受限梯度上升

1 概述

三网融合是以下一代广播电视网(NGB)为主的新一代国家信息基础设施的基本特征［1］。三网融合环境中存在着接入网络、终端设备和用户行为等方面的异构和异质特性,并伴随着海量业务需求。为了向用户提供更高带宽、更快响应的高品质服务,业务一般部署到最接近用户的网络边缘,由边缘服务器面向用户提供服务。中国互联网络信息中心(CNNIC)第29次中国互联网发展报告显示, 2011年网络视频的用户规模较上一年增加14.6%,达到3.25亿人,使用率提升至63.4%［2］。根据美国资讯公司Cisco Systems的预测,2013年全球视频业务将占到通信业务总量的91%,每分钟将有20小时的节目被上传［3］。因此,满足大规模并发视频业务需求并为用户提供高品质的服务是未来三网融合业务面临的新战。

为在保证服务质量(Quality of Service,QoS)的条件下,尽可能提高资源利用率和满足用户需求,本文利用虚拟化技术,通过在一台物理机器上虚拟出多台虚拟机器,或把多台物理机器虚拟化成一台虚拟机器的方式达到提高资源利用率和资源共享率的目的［4-5］。屏蔽网络层复杂的物理特性,将物理资源虚拟化成逻辑资源,在虚拟层上采用控制理论与方法生成一个简化和透明的管控机制,并通过执行系统再部署到物理层。创建虚拟服务节点实时服务提供设备(Real-time Service Provide Equipment,RSPE)为基本服务单位。RSPE节点作为虚拟节点部署在

底层边缘服务器集群之上,为特定用户群提供服务。边缘服务器集群将特定用户群对资源的需求信息和资源的部署信息到RSPE节点上。RSPE节点通过互通互联构成一个多智能体网络层,在该虚拟网络层上采用分布式优化协同控制以实现对资源池的资源调度与部署,在满足QoS的前提下提高资源的利用率。RSPE节点的服务能力是动态可变的,尽可能满足其服务用户的资源需求,但同时根据资源需求大小调整自身服务能力,协同其他RSPE节点共享资源来提高资源利用率。

本文在文献［6］的基础上提出完全分布式系统,以提高系统鲁棒性和容错能力。将边缘服务器集群提供的整体计算资源(存储、CPU、内存、带宽等)视为资源池,边缘服务器集群虚拟化成RSPE节点,把视频服务网内的虚拟RSPE节点视为资源消费者的需求以资源共享的方式参与资源的分配过程［7］,资源分配的关键在于照顾资源消费者的整体资源需求的情况下,尽可能提高资源利用率和共享率,并保证服务质量,在此基础上,提出一种完全分布式的资源最优分配系统——RSPE-DOC。该系统把物理计算资源视为计算资源的共享池,把RSPE节点视为需求,包括RSPE节点之间的信息传播策略和分布式优化算法,从而实现资源池的分布式最优控制。同时本文给出数学和算法模型,并能保证分配结果的最优性和收敛性。

2 背景介绍

资源池的建立为计算资源的协作共享和用户并发访问提供了可能［8］。资源池协作共享的通常做法是把计算资源池化,划分成一系列共享资源份额,分配给资源消费者使用。具体的讲,资源池中的每一个资源份额被关联到一个实际的资源消费者。共享资源池管理调度的目标是,满足整体资源受限的约束条件下,动态决定最优的资源分配方案,并尽量保证资源消费者的服务质量。资源池最优分配问题一般可以被建模成自优化问题.共享资源池模型可以被映射成很多实际问题。比如计算中心的最优调度问题。在这个问题里,服务器的集合被划分成资源份额的集合以供计算用户使用。相似的做法在最优带宽控制问题中也适用［9］。带宽作为共享使用的资源被划分成不同的份额供流量消费者使用。这样流量消费者可以共享使用带宽,在满足资源容量受限的约束条件下,获得最优的资源分配方案。

资源分配通常被建模成一个自优化的自主计算系统,即该系统可以自动地,以最好的可能方式来分配资源［10］。在这里,“最好”意味着资源分配可以保证最优的资源使用情况,并尽量满足资源消费者的资源需求。易知,把寻找这一最优分配的过程建模成优化问题并求解最终就可以找到最优的分配方案。形式上,用x来表示资源分配向量(资源分配向量x给出每个资源消费者获得的资源份额),用函数f(x)表示对分配向量x所能获得的资源使用情况和消费者个体需求的综合评估,那么优化问题的优化目标即为f(x),优化的约束条件为资源的整体可用性。优化问题的解x就是可以最大化f(x)的最优资源分配方案。

传统的优化算法所面临的最大问题是:消费者的资源需求不是一成不变的,而是会随着时间动态变化［11-12］。静态的资源分配无法保证资源使用的动态最优［13］。资源分配也应该是随着时间动态变化的,本文把这一过程称为资源管理过程。近年来,共享资源池中的资源管理问题研究越来越被重视。集中式资源管理策略是其中一类代表性方法。集中式策略通过使用中心控制节点收集所有其他节点的状态信息来做出资源分配的决策,可以很好地解决资源最优分配问题。然而,集中式策略最大的问题是容错性能不佳:中心节点一旦出现故障,整个系统往往都面临崩溃的可能。一些研究者提出了分层分布式解决方案,系统中配置多个控制节点,每个控制节点管理一定数额的服务节点,控制节点之间互联互通协作工作。分层分布式解决方案一定程度上避免了单个控制节点故障对全局的破坏性影响,但仍然面临相似的容错性能较差的问题。在完全分布式方案中,所有节点都是平等的,节点互相合作以完成全局优化任务,没有任何一个节点优于其他节点,完全分布式系统具有非常好的容错能力:单节点故障甚至少量节点的故障不会影响全局的最优分配过程。

3 系统建模

本文给出RSPE-DOC解决方案的基本概念。特别地,给出了资源管理过程问题的形式化说明。

3.1 多智能体系统模型

本文把物理服务器集群上部署的RSPE节点看成一个多智能体系统(Multi-Agent System),RSPE节点作为智能体,同时是底层计算资源的资源消费者,见图1。

图1 RSPE虚拟服务节点部署示意图

本文假定智能体以任意拓扑结构连接,每个智能体都可以直接或间接的跟所有其他智能体通信。本文用图S(t)表示这样一个多智能体系统,定义如下:

定义令S(t)={V(t),E(t)}为一个图,其中,顶点集合V(t)表示时刻t时的智能体集合,边集合E(t)表示时刻t时的智能体拓扑连接。假定S(t)是连通图,且对任意的边{u,v}∈E(t)有u≠v。

定义αi系统中的第i个智能体,Ni(t)表示智能体αi在时刻t的邻居集合,n(t)表示时刻t系统包含智能体的数目(也就是n(t)=)。注意到V(t)和E(t)是时间相关的,因此,系统智能体的数目和拓扑结构是可以随着时间而改变的。

3.2 自优化问题

为进行资源池的分布式最优控制,有必要引入一种机制可以比较不同资源分配方案的优劣。为此,本文在RSPE-DOC系统中使用效用函数［14］。本文假设每个智能体αi有一个个体效用函数ui(t),给出份额x对智能体αi的个体需求的满足情况。定义整体效用函数U(X)如下:

其中,X={X1,X2,…}是系统的资源分配向量,Xi为分配给智能体ai的资源份额。效用函数把每一种资源分配方案映射到一个实数值,从而允许对资源分配方案进行比较。

3.3 问题形式化

在整体资源受限的情况下,资源管理问题就可以被形式化成:

其中,R(t)是系统在时刻t所能提供的资源总和。在实际问题中,R(t)的值可以被系统管理员设定并传播给系统中每个智能体表示一种单一资源,比如存储、CPU、内存、带宽等,本文假设一个资源管理系统处理一种资源的分配过程。当然,不同类型的资源可以合成一种复合资源——虚拟服务器,在这种情况下,服务器就是需要被分配的资源。

4 RSPE-DOC系统

本节首先给出了如何分布式求解式(2)的数学模型,然后给出了这个数学模型的算法实现,即一个多智能体模型。

4.1 数学模型

RSPE-DOC的数学模型由4个子模型组成:优化模型定义了如何把全局优化问题转化成分布式优化问题,从而可以被每个智能体单独求解;传播模型给出了智能体通信和交换信息的方式;终止模型使智能体可以判断何时可以停止通信;需求模型则最终给出如何把智能体的实际需求转化成优化模型需要的需求参数。

4.1.1 优化模型

为了分解式(2)的优化问题,首先需要给出效用函数的定义。令ui(x)为智能体αi的个体效用函数,ui(x)定义为:

其中,x是分配给智能体αi的资源份额;αi(t)是反映智能体αi在时刻t的资源需求的需求参数。αi(t)越小,智能体αi对资源的需求就越大。采用这个效用函数定义的动机有3个方面:首先,这个定义可以很好地描述需求模型。当份额较小时,效用函数增长很快,表明获得更多的资源份额已不是很重要;其次,定义的效用函数随着资源份额的增大,收敛于1,可以方便地给出智能体资源需求得到满足时的效用阈值;最后,这个效用函数的定义使得把全局优化问题分解成局部的分布式优化问题成为可能。

已知αi(t)一般是可以随着时间改变的［6］,本文做出如下假设。

假设令t′和t″分别为一个资源管理器过程开始和结束的时刻,则对任意智能体ai,任意时刻t′≤t≤t″,有ai(t)=ai(t′)。

这个假设保证在一个资源管理过程中,αi(t)值保持为常数。当然,在资源管理过程中,任何一个智能体都可能会发觉自身的资源需求突然增大或减小。在这种情况下,这个智能体可以通知系统中的其他智能体,一起进入一个新的资源管理过程。本文认为,前一个资源过来过程随即终止,新的资源管理过程随即开始。很多不同的方法可以用来触发新的资源管理过程;在实验中,本文使用了基于时间的事件方法。但这不属于本文的研究范围,本文关注于如何进行分布式的最优资源控制。

给出了效用函数的定义后,本文使用受限梯度上升方法求解得到U(X)的最大值。根据定义:

因此,X处的梯度向量的i分量为:

n=［1,1,…,1］是超平面P的法向向量。最终,本文使用的梯度更新规则是:

为了分布式求解这一全局最优问题,每个智能体都有必要知道其他智能体的需求参数αi。下一节将引入传播模型。

4.1.2 传播模型

传播模型形式化α值的传播过程,以计算lnλ值。RSPE-DOC系统中,本文使用基于PUSH和PULL的同步策略来实现这一过程［3］。每个智能体通过把自己的信息副本推送(push)给邻居节点,并从邻居节点那里拉取(pull)信息副本来同步自己和邻居节点的信息,从而实现所有智能体都获得一致的完整信息。

本文定义智能体传播的消息格式为［ρi,αi(t)］,其中,ρi∈Ν是智能体ai(t)的标识符,ai(t)是其需求参数。本文定义Οi(t)为智能体ai自身和其他所有跟ai通信过的智能体的标识符的集合;Mi(t)为对应的通信过的α值的多值集合。为提高通信过程中的比较效率,本文定义ki(t)为智能体ai所存储的所有局部信息的校验函数［15］:

通过比较2个智能体的校验函数是否相同,即可方便地知道这2个智能体各自存储的局部信息是否已经获得同步。具体地,本文定义差异函数:

其中,&为按位与运算符。易知,对智能体ai而言,所存储的任意信息［ρ,α］,如果2ρ&gij(t)=2ρ成立,那么消息［ρ,α］应该从智能体ai推送到智能体aj;类似的,如果2ρ&gji(t)=2ρ成立,那么消息［ρ,α］应该从智能体aj拉取到智能体ai。这样每一对［ρ,α］值都会被互为邻居的智能体节点同步,最终同步给所有智能体。

4.1.3 终止模型

终止模型使智能体可以通过局部的信息交互来判断何时可以停止传播,这是RSPE-DOC系统重要的组成部分之一,终止模型告诉智能体何时准备好计算lnλ值,进而计算每个智能体自己的最优资源份额Xi。这个过程必须是分布式的,以保证一定的系统容错性。为此,智能体需要维护,并与其邻居节点交换一些额外的信息。本文为智能体ai定义一个指示函数xi(t):

指示函数xi(t)的值反映了系统中有多少信息已经被传播了,较大的xi(t)的值意味着较多的值已经被传播。注意到xi(t)的值只依赖邻居节点指示函数的值,所以xi(t)的计算是完全分布式的。理论上可以证明,任意智能体xi(t)的值最终会收敛于一个相同的常数值。事实上,当t→∞时,xi(t)→∑ai∈V(t)2ρi。这个性质使得xi(t)成为一个可以用来判断系统是否已经稳定的判据。系统稳定的时候就可以停止传播过程了。然而在实际系统中,并不能简单使用xi(t)的值来判断系统是否稳定,因为网络延迟有可能导致xi(t)的值暂时停在某个常数,而让智能体作出误判。为此,本文定义联合差分函数di(t):

即使网络延迟使得di(t)的值暂时停留在某一个值,也不会停留在0。这样一旦di(t)的值趋于0,智能体ai就知道系统已经稳定了。

分布式系统一般都会随着时间改变,即有智能体加入或者离开,所以本文有必要专门讨论这些情况。本文分两类来讨论系统的变化:(1)智能体在资源管理过程之间加入或离开;(2)智能体在资源管理过程之中加入或离开。

在第(1)种情况下,系统的收敛性不会受到影响。因为传播模型不依赖于任何智能体数目相关的全局信息,所以资源管理过程开始之前,系统的任何变化都可以自动被传播模型处理,无需更进一步的设置或者更新。由此,有计划的系统改变不会影响传播过程的收敛,系统也不需要为此重启任何一个部分。

在第(2)种情况下,会导致一些问题。比如,有智能体在某些di(t)为0后加入系统,那么系统将不能进入新的稳定状态;或者,有智能体在资源管理过程中离开系统,那么其α值还将会被继续在系统中传播,最终导致系统不能调整到新的稳定状态。在资源管理过程中,智能体的加入或离开属于非计划的系统改变。本文认为非计划的系统改变在实践中可以尽量控制到最少。所以不失灵活性,本文假设非计划的改变仅发生在两个资源管理过程之间。

最终,本文需要考虑智能体间拓扑结构的改变(这种情况下,智能体数目不变)。因为智能体间的通信仅发生在互为邻居节点之间,所以仅拓扑结构的改变不会影响系统的稳定性,即使这种改变是发生在资源管理过程之中的。

4.1.4 需求模型

正如优化模型中所定义的,αi(t)是反映智能体资

源需求的参数。这个参数的值应由智能体的工作量和实际资源需求共同决定。所以,本文有必要定义需求模型。在视频服务网中,工作量即是当前需要完成传输的视频流中大小和CPU计算时间;实际资源需求主要是指传输当前视频流所需要的带宽总和。具体怎么给出需求模型有多种方法,但这不是本文的研究重点。本文主要关注于分布式的资源最优控制策略。所以,本文认为需求模型是已知的。在实验部分,本文会给出一种简单的表示方法以作示例。

4.2 多智能体模型

本节给出数学模型的算法实现,RSPE-DOC系统中RSPE智能体结构如图2所示。智能体把实际工作量和资源需求传给需求模型,需求模型计算出相应的α值,并传给终止模型,终止模型调用传播模型传播α值,并决定何时停止传播。这时,α值集合Mi(t)传给优化模型。优化模型计算出智能体应得的最优资源份额,传给底层物理系统,并从那里得到分配的计算资源。

图2 RSPE-DOC系统中的RSPE智能体结构

5 实验验证

在实验中,资源池能提供的最大带宽。本文定义αi(t)的计算公式为:其中,H=0.99。这样,当智能体ai实际分配的份额x=bi(t)时,ui(x)=H;当x＞bi(t)时,ui(x)＞H。在这个定义下,当智能体的需求得到满足时,其个体效用函数的值非常接近于1;另外,继续追加份额,也不妨碍效用函数的值继续增大。

5.1 资源分配实验

为验证资源分配的最优性,本文假设底层物理资源池之上部署6个虚拟RSPE节点,每个节点在资源管理过程开始之前随机确定其带宽需求。这里是为了验证算法的最优性,所以少量的智能体数目已经可以达到目的。本文共进行了2组实验:在第1组实验里,智能体提出的平均整体需求基本上与系统最大服务能力持平,系统处于正常负载状态;在第2组实验里,智能体提出的评价整体需求远大于系统最大服务能力,系统处于过载工作状态。2组实验中6个智能体对应的泊松分布λ值如表1所示。在第1组实验中,66个智能体平均带宽需求之和为1 000 MB/s;在第2组实验中,6个智能体平均带宽需求之和为2 000 MB/s。

表1 智能体带宽需求满足的泊松分布参数

本文共进行了100次独立重复实验。观察到平均的整体效用函数U(x)分别约为5.95±0.000 79和5.48±0.003 10。注意到,U(x)可能取得的最大值为6,U(x)越接近于6,智能体资源需求获得满足的情况越好,整体服务质量也就越高。实验结果显示,在系统正常负载状态下,优化模型找到的解对应的整体效用函数的值非常接近于1;在系统过载状态下,智能体的资源需求不可能全部得到满足,优化模型找到的解对应的整体效用函数的值达不到最大值6(但事实上通过测试可以判定该解仍然是此过载状态下的最优解)。

5.2 传播实验

为验证传播模块,本文定义一个周期(cycle)为智能体跟邻居节点的一次同步过程,并假设所有智能体按相同时间信号运行。对1～100范围内不同的智能体数目,分别重复测试6次,记录每次实验中传播模块终止所需要的周期数和单个智能体为完成同步所需要的CPU计算时间。实验中系统结构图

中节点的度大小设定为5。实验结果见图3。可以看出,传播过程需要的周期数与智能体数目成对数关系,证明RSPE-DOC系统具有很好的可扩展性;单个智能体传播过程所需要的计算时间跟智能体数目成指数关系,但所需CPU计算时间非常少。可以看出,RSPE-DOC系统的反应时间非常快,能满足实时性要求。

图3 传播模型实验结果

5.3 收敛性实验

本文使用xi(t)值和di(t)值随周期数的变化情况来验证系统的收敛性。实验时,智能体数目设定为100,系统结构拓扑图中节点的度设定为5。本文记录了每个智能体的xi(t)值和di(t)值,实验结果见图4。可以看出,xi(t)值和di(t)值分别都可以正确地收敛到一个常数值和0。

图4 收敛性实验结果

6 结束语

本文介绍了RSPE-DOC系统——一个完全分布式的视频服务网资源池自适应最优控制方案。RSPE-DOC系统把每个RSPE节点视为资源消费者,使用智能体代理资源消费者向底层物理资源池提出资源请求,智能体之间以任意拓扑结构联系,智能体通过同步需求信息把全局优化问题分解成分布式优化问题,从而最终确定每个智能体的最优资源份额,以保证服务质量,并提高资源利用率。实验结果表明,RSPE-DOC系统可以保证系统在不同负载状态下的资源最优分配,传播过程可以很快终止,传播所需CPU计算时间较少,并且系统可以正确收敛。RSPE-DOC系统假设RSPE节点的增加或删除只发生在资源管理过程间,下一步工作将考虑放宽该限制,以提高RSPE-DOC系统的实时性,进一步扩大适用范围。

［1]张 彬,李俊杰.我国三网融合业务发展研究［J］.信息系统工程,2010,(12):101-106.

［2]中国互联网络信息中心.第29次中国互联网络发展状况统计报告［Z］.2012.

［3]Cisco Systems Inc..2010 Annual Report［Z］.2010.

［4]Michael A,Fox A,GRIFFITH R.A View of Cloud Computing［J］.Communications of the ACM,2010, 53(4):50-58.

［5]Gmach D,Rolia J,Cherkasova L,et al.Resource Pool Management:Reactive Versus Proactive or Let’s Be Friends［J］.ComputerNetworks,2009,53(17), 2905-2922.

［6]Loureiro E,NixonP,DobsonS.Decentralizedand Optimal Control of Shared Resource Pools［J］.ACM Transactions on Autonomous and Adaptive Systems, 2012,7(1).

［7]Kephart J O,Das R.Achieving Self-management via Utility Functions［J］.IEEE Internet Computing,2007, 11(1):40-48.

［8]Rolia J,CherkasovaL,ArlittM,etal.Supporting Application Quality of Service in Shared Resource Pools［J］.Communications of the ACM,2006,49(3): 55-60.

［9]Raghavan B,Vishwanath K,Ramabhadran S,et al.Cloud Control with Distributed Rate Limiting［J］.ACM SIGCOMM Computer Communication Review,2007, 37(4):337-348.

［10]Kephart J O,Chess D M.The Vision of Autonomic Computing［J］.Computer,2003,36(1):41-50.

［11]Guitart J,Carrera D,Beltran V,et al.Dynamic CPU Provisioning for Self-managed Secure Web Applications in SMP Hosting Platforms［J］.Computer Networks, 2008,52(7):1390-1409.

［12]Gmach D,Rolia J,Cherkasova L,et al.An Integrated ApproachToresourcePoolManagement:Policies, Efficiency andQualitymetrics［C］//Proceedingsof IEEE International Conference on Dependable Systems and Networks.［S.l.］:IEEE Press,2008:326-335.

［13]Padala P,Shin K G,Zhu X,et al.Adaptive Control of VirtualizedresourcesinUtilityComputingEnvironments［J］.ACM SIGOPS Operating Systems Review, 2007,41(3):289-302.

［14]Johansson B,Adam C,Johansson M,et al.Distributed Resource Allocation Strategies for Achieving Quality of Service in Server Clusters［C］//Proceedings of the 45th IEEE Conference on Decision and Control.［S.l.］: IEEE Press,2006:1990-1995.

［15]Demers A,GreeneD,HauserC,etal.Epidemic Algorithms for Replicated Database Maintenance［C］// Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing.［S.l.］:ACM Press,1987:1-12.

编辑 金胡考

Distributed Optimal Control in Shared Resource Pools of Video Service Nodes

SONG Chen,XI Hongsheng
(Department of Automation,University of Science and Technology of China,Hefei 230037,China)

Aiming at the domain of video service network in tri-network convergence,this paper focuses on the problem of optimal resource allocation of Real-time Service Provide Equipment(RSPE)nodes in shared resource pools.This paper proposes a fully distributed optimal control solution,named RSPE-DOC.RSPE-DOC treats underlying physical servers as a shared resource pool,and RSPE nodes as resource consumers.RSPE-DOC implements the information exchanging strategy and distributed optimization method among RSPE nodes,leading to a distributed optimal control framework.Experimental results indicate that RSPE-DOC is able to ensure the convergence of dissemination process and find the optimal resource allocation,when the RSPE nodes are not changed substantially in resource management process.

tri-network convergence;video service network;shared resource pools;resource assignment;distributed optimal control;constrained gradient ascent

宋 辰,奚宏生.视频服务节点共享资源池的分布式最优控制［J］.计算机工程,2015,41(3):71-76.

英文引用格式:Song Chen,Xi Hongsheng.Distributed Optimal Control in Shared Resource Pools of Video Service Nodes［J］.Computer Engineering,2015,41(3):71-76.

1000-3428(2015)03-0071-06

:A

:TP393

10.3969/j.issn.1000-3428.2015.03.013

国家自然科学基金资助重点项目(61233003)。

宋 辰(1987-),女,硕士研究生,主研方向:网络传播系统与控制;奚宏生,教授、博士生导师。

:2014-03-11修回日期:2014-04-28E-mail:sclucky@mail.ustc.edu.cn