視頻服務(wù)節(jié)點(diǎn)共享資源池的分布式最優(yōu)控制

宋 辰,奚宏生

(中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系,合肥230027)

視頻服務(wù)節(jié)點(diǎn)共享資源池的分布式最優(yōu)控制

宋 辰,奚宏生

(中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系,合肥230027)

針對(duì)三網(wǎng)融合背景下的視頻服務(wù)網(wǎng),研究實(shí)時(shí)服務(wù)提供設(shè)備(RSPE)的節(jié)點(diǎn)共享資源池的資源配置,提出一種完全分布式的最優(yōu)控制解決方案。分別將物理計(jì)算資源和RSPE節(jié)點(diǎn)視為計(jì)算資源的共享池和資源消費(fèi)者,給出RSPE節(jié)點(diǎn)之間的信息傳播策略和分布式優(yōu)化算法,從而實(shí)現(xiàn)資源池的分布式最優(yōu)控制。仿真結(jié)果表明,在RSPE節(jié)點(diǎn)變化較小的情況下,該方案可保證節(jié)點(diǎn)間信息傳播過(guò)程的收斂性和共享資源的最優(yōu)資源配置。

三網(wǎng)融合;視頻服務(wù)網(wǎng);共享資源池;資源分配;分布式最優(yōu)控制;受限梯度上升

1 概述

三網(wǎng)融合是以下一代廣播電視網(wǎng)(NGB)為主的新一代國(guó)家信息基礎(chǔ)設(shè)施的基本特征［1］。三網(wǎng)融合環(huán)境中存在著接入網(wǎng)絡(luò)、終端設(shè)備和用戶行為等方面的異構(gòu)和異質(zhì)特性,并伴隨著海量業(yè)務(wù)需求。為了向用戶提供更高帶寬、更快響應(yīng)的高品質(zhì)服務(wù),業(yè)務(wù)一般部署到最接近用戶的網(wǎng)絡(luò)邊緣,由邊緣服務(wù)器面向用戶提供服務(wù)。中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)第29次中國(guó)互聯(lián)網(wǎng)發(fā)展報(bào)告顯示, 2011年網(wǎng)絡(luò)視頻的用戶規(guī)模較上一年增加14.6%,達(dá)到3.25億人,使用率提升至63.4%［2］。根據(jù)美國(guó)資訊公司Cisco Systems的預(yù)測(cè),2013年全球視頻業(yè)務(wù)將占到通信業(yè)務(wù)總量的91%,每分鐘將有20小時(shí)的節(jié)目被上傳［3］。因此,滿足大規(guī)模并發(fā)視頻業(yè)務(wù)需求并為用戶提供高品質(zhì)的服務(wù)是未來(lái)三網(wǎng)融合業(yè)務(wù)面臨的新戰(zhàn)。

為在保證服務(wù)質(zhì)量(Quality of Service,QoS)的條件下,盡可能提高資源利用率和滿足用戶需求,本文利用虛擬化技術(shù),通過(guò)在一臺(tái)物理機(jī)器上虛擬出多臺(tái)虛擬機(jī)器,或把多臺(tái)物理機(jī)器虛擬化成一臺(tái)虛擬機(jī)器的方式達(dá)到提高資源利用率和資源共享率的目的［4-5］。屏蔽網(wǎng)絡(luò)層復(fù)雜的物理特性,將物理資源虛擬化成邏輯資源,在虛擬層上采用控制理論與方法生成一個(gè)簡(jiǎn)化和透明的管控機(jī)制,并通過(guò)執(zhí)行系統(tǒng)再部署到物理層。創(chuàng)建虛擬服務(wù)節(jié)點(diǎn)實(shí)時(shí)服務(wù)提供設(shè)備(Real-time Service Provide Equipment,RSPE)為基本服務(wù)單位。RSPE節(jié)點(diǎn)作為虛擬節(jié)點(diǎn)部署在

底層邊緣服務(wù)器集群之上,為特定用戶群提供服務(wù)。邊緣服務(wù)器集群將特定用戶群對(duì)資源的需求信息和資源的部署信息到RSPE節(jié)點(diǎn)上。RSPE節(jié)點(diǎn)通過(guò)互通互聯(lián)構(gòu)成一個(gè)多智能體網(wǎng)絡(luò)層,在該虛擬網(wǎng)絡(luò)層上采用分布式優(yōu)化協(xié)同控制以實(shí)現(xiàn)對(duì)資源池的資源調(diào)度與部署,在滿足QoS的前提下提高資源的利用率。RSPE節(jié)點(diǎn)的服務(wù)能力是動(dòng)態(tài)可變的,盡可能滿足其服務(wù)用戶的資源需求,但同時(shí)根據(jù)資源需求大小調(diào)整自身服務(wù)能力,協(xié)同其他RSPE節(jié)點(diǎn)共享資源來(lái)提高資源利用率。

本文在文獻(xiàn)［6］的基礎(chǔ)上提出完全分布式系統(tǒng),以提高系統(tǒng)魯棒性和容錯(cuò)能力。將邊緣服務(wù)器集群提供的整體計(jì)算資源(存儲(chǔ)、CPU、內(nèi)存、帶寬等)視為資源池,邊緣服務(wù)器集群虛擬化成RSPE節(jié)點(diǎn),把視頻服務(wù)網(wǎng)內(nèi)的虛擬RSPE節(jié)點(diǎn)視為資源消費(fèi)者的需求以資源共享的方式參與資源的分配過(guò)程［7］,資源分配的關(guān)鍵在于照顧資源消費(fèi)者的整體資源需求的情況下,盡可能提高資源利用率和共享率,并保證服務(wù)質(zhì)量,在此基礎(chǔ)上,提出一種完全分布式的資源最優(yōu)分配系統(tǒng)——RSPE-DOC。該系統(tǒng)把物理計(jì)算資源視為計(jì)算資源的共享池,把RSPE節(jié)點(diǎn)視為需求,包括RSPE節(jié)點(diǎn)之間的信息傳播策略和分布式優(yōu)化算法,從而實(shí)現(xiàn)資源池的分布式最優(yōu)控制。同時(shí)本文給出數(shù)學(xué)和算法模型,并能保證分配結(jié)果的最優(yōu)性和收斂性。

2 背景介紹

資源池的建立為計(jì)算資源的協(xié)作共享和用戶并發(fā)訪問(wèn)提供了可能［8］。資源池協(xié)作共享的通常做法是把計(jì)算資源池化,劃分成一系列共享資源份額,分配給資源消費(fèi)者使用。具體的講,資源池中的每一個(gè)資源份額被關(guān)聯(lián)到一個(gè)實(shí)際的資源消費(fèi)者。共享資源池管理調(diào)度的目標(biāo)是,滿足整體資源受限的約束條件下,動(dòng)態(tài)決定最優(yōu)的資源分配方案,并盡量保證資源消費(fèi)者的服務(wù)質(zhì)量。資源池最優(yōu)分配問(wèn)題一般可以被建模成自優(yōu)化問(wèn)題.共享資源池模型可以被映射成很多實(shí)際問(wèn)題。比如計(jì)算中心的最優(yōu)調(diào)度問(wèn)題。在這個(gè)問(wèn)題里,服務(wù)器的集合被劃分成資源份額的集合以供計(jì)算用戶使用。相似的做法在最優(yōu)帶寬控制問(wèn)題中也適用［9］。帶寬作為共享使用的資源被劃分成不同的份額供流量消費(fèi)者使用。這樣流量消費(fèi)者可以共享使用帶寬,在滿足資源容量受限的約束條件下,獲得最優(yōu)的資源分配方案。

資源分配通常被建模成一個(gè)自優(yōu)化的自主計(jì)算系統(tǒng),即該系統(tǒng)可以自動(dòng)地,以最好的可能方式來(lái)分配資源［10］。在這里,“最好”意味著資源分配可以保證最優(yōu)的資源使用情況,并盡量滿足資源消費(fèi)者的資源需求。易知,把尋找這一最優(yōu)分配的過(guò)程建模成優(yōu)化問(wèn)題并求解最終就可以找到最優(yōu)的分配方案。形式上,用x來(lái)表示資源分配向量(資源分配向量x給出每個(gè)資源消費(fèi)者獲得的資源份額),用函數(shù)f(x)表示對(duì)分配向量x所能獲得的資源使用情況和消費(fèi)者個(gè)體需求的綜合評(píng)估,那么優(yōu)化問(wèn)題的優(yōu)化目標(biāo)即為f(x),優(yōu)化的約束條件為資源的整體可用性。優(yōu)化問(wèn)題的解x就是可以最大化f(x)的最優(yōu)資源分配方案。

傳統(tǒng)的優(yōu)化算法所面臨的最大問(wèn)題是:消費(fèi)者的資源需求不是一成不變的,而是會(huì)隨著時(shí)間動(dòng)態(tài)變化［11-12］。靜態(tài)的資源分配無(wú)法保證資源使用的動(dòng)態(tài)最優(yōu)［13］。資源分配也應(yīng)該是隨著時(shí)間動(dòng)態(tài)變化的,本文把這一過(guò)程稱為資源管理過(guò)程。近年來(lái),共享資源池中的資源管理問(wèn)題研究越來(lái)越被重視。集中式資源管理策略是其中一類代表性方法。集中式策略通過(guò)使用中心控制節(jié)點(diǎn)收集所有其他節(jié)點(diǎn)的狀態(tài)信息來(lái)做出資源分配的決策,可以很好地解決資源最優(yōu)分配問(wèn)題。然而,集中式策略最大的問(wèn)題是容錯(cuò)性能不佳:中心節(jié)點(diǎn)一旦出現(xiàn)故障,整個(gè)系統(tǒng)往往都面臨崩潰的可能。一些研究者提出了分層分布式解決方案,系統(tǒng)中配置多個(gè)控制節(jié)點(diǎn),每個(gè)控制節(jié)點(diǎn)管理一定數(shù)額的服務(wù)節(jié)點(diǎn),控制節(jié)點(diǎn)之間互聯(lián)互通協(xié)作工作。分層分布式解決方案一定程度上避免了單個(gè)控制節(jié)點(diǎn)故障對(duì)全局的破壞性影響,但仍然面臨相似的容錯(cuò)性能較差的問(wèn)題。在完全分布式方案中,所有節(jié)點(diǎn)都是平等的,節(jié)點(diǎn)互相合作以完成全局優(yōu)化任務(wù),沒(méi)有任何一個(gè)節(jié)點(diǎn)優(yōu)于其他節(jié)點(diǎn),完全分布式系統(tǒng)具有非常好的容錯(cuò)能力:單節(jié)點(diǎn)故障甚至少量節(jié)點(diǎn)的故障不會(huì)影響全局的最優(yōu)分配過(guò)程。

3 系統(tǒng)建模

本文給出RSPE-DOC解決方案的基本概念。特別地,給出了資源管理過(guò)程問(wèn)題的形式化說(shuō)明。

3.1 多智能體系統(tǒng)模型

本文把物理服務(wù)器集群上部署的RSPE節(jié)點(diǎn)看成一個(gè)多智能體系統(tǒng)(Multi-Agent System),RSPE節(jié)點(diǎn)作為智能體,同時(shí)是底層計(jì)算資源的資源消費(fèi)者,見圖1。

圖1 RSPE虛擬服務(wù)節(jié)點(diǎn)部署示意圖

本文假定智能體以任意拓?fù)浣Y(jié)構(gòu)連接,每個(gè)智能體都可以直接或間接的跟所有其他智能體通信。本文用圖S(t)表示這樣一個(gè)多智能體系統(tǒng),定義如下:

定義令S(t)={V(t),E(t)}為一個(gè)圖,其中,頂點(diǎn)集合V(t)表示時(shí)刻t時(shí)的智能體集合,邊集合E(t)表示時(shí)刻t時(shí)的智能體拓?fù)溥B接。假定S(t)是連通圖,且對(duì)任意的邊{u,v}∈E(t)有u≠v。

定義αi系統(tǒng)中的第i個(gè)智能體,Ni(t)表示智能體αi在時(shí)刻t的鄰居集合,n(t)表示時(shí)刻t系統(tǒng)包含智能體的數(shù)目(也就是n(t)=)。注意到V(t)和E(t)是時(shí)間相關(guān)的,因此,系統(tǒng)智能體的數(shù)目和拓?fù)浣Y(jié)構(gòu)是可以隨著時(shí)間而改變的。

3.2 自優(yōu)化問(wèn)題

為進(jìn)行資源池的分布式最優(yōu)控制,有必要引入一種機(jī)制可以比較不同資源分配方案的優(yōu)劣。為此,本文在RSPE-DOC系統(tǒng)中使用效用函數(shù)［14］。本文假設(shè)每個(gè)智能體αi有一個(gè)個(gè)體效用函數(shù)ui(t),給出份額x對(duì)智能體αi的個(gè)體需求的滿足情況。定義整體效用函數(shù)U(X)如下:

其中,X={X1,X2,…}是系統(tǒng)的資源分配向量,Xi為分配給智能體ai的資源份額。效用函數(shù)把每一種資源分配方案映射到一個(gè)實(shí)數(shù)值,從而允許對(duì)資源分配方案進(jìn)行比較。

3.3 問(wèn)題形式化

在整體資源受限的情況下,資源管理問(wèn)題就可以被形式化成:

其中,R(t)是系統(tǒng)在時(shí)刻t所能提供的資源總和。在實(shí)際問(wèn)題中,R(t)的值可以被系統(tǒng)管理員設(shè)定并傳播給系統(tǒng)中每個(gè)智能體表示一種單一資源,比如存儲(chǔ)、CPU、內(nèi)存、帶寬等,本文假設(shè)一個(gè)資源管理系統(tǒng)處理一種資源的分配過(guò)程。當(dāng)然,不同類型的資源可以合成一種復(fù)合資源——虛擬服務(wù)器,在這種情況下,服務(wù)器就是需要被分配的資源。

4 RSPE-DOC系統(tǒng)

本節(jié)首先給出了如何分布式求解式(2)的數(shù)學(xué)模型,然后給出了這個(gè)數(shù)學(xué)模型的算法實(shí)現(xiàn),即一個(gè)多智能體模型。

4.1 數(shù)學(xué)模型

RSPE-DOC的數(shù)學(xué)模型由4個(gè)子模型組成:優(yōu)化模型定義了如何把全局優(yōu)化問(wèn)題轉(zhuǎn)化成分布式優(yōu)化問(wèn)題,從而可以被每個(gè)智能體單獨(dú)求解;傳播模型給出了智能體通信和交換信息的方式;終止模型使智能體可以判斷何時(shí)可以停止通信;需求模型則最終給出如何把智能體的實(shí)際需求轉(zhuǎn)化成優(yōu)化模型需要的需求參數(shù)。

4.1.1 優(yōu)化模型

為了分解式(2)的優(yōu)化問(wèn)題,首先需要給出效用函數(shù)的定義。令ui(x)為智能體αi的個(gè)體效用函數(shù),ui(x)定義為:

其中,x是分配給智能體αi的資源份額;αi(t)是反映智能體αi在時(shí)刻t的資源需求的需求參數(shù)。αi(t)越小,智能體αi對(duì)資源的需求就越大。采用這個(gè)效用函數(shù)定義的動(dòng)機(jī)有3個(gè)方面:首先,這個(gè)定義可以很好地描述需求模型。當(dāng)份額較小時(shí),效用函數(shù)增長(zhǎng)很快,表明獲得更多的資源份額已不是很重要;其次,定義的效用函數(shù)隨著資源份額的增大,收斂于1,可以方便地給出智能體資源需求得到滿足時(shí)的效用閾值;最后,這個(gè)效用函數(shù)的定義使得把全局優(yōu)化問(wèn)題分解成局部的分布式優(yōu)化問(wèn)題成為可能。

已知αi(t)一般是可以隨著時(shí)間改變的［6］,本文做出如下假設(shè)。

假設(shè)令t′和t″分別為一個(gè)資源管理器過(guò)程開始和結(jié)束的時(shí)刻,則對(duì)任意智能體ai,任意時(shí)刻t′≤t≤t″,有ai(t)=ai(t′)。

這個(gè)假設(shè)保證在一個(gè)資源管理過(guò)程中,αi(t)值保持為常數(shù)。當(dāng)然,在資源管理過(guò)程中,任何一個(gè)智能體都可能會(huì)發(fā)覺(jué)自身的資源需求突然增大或減小。在這種情況下,這個(gè)智能體可以通知系統(tǒng)中的其他智能體,一起進(jìn)入一個(gè)新的資源管理過(guò)程。本文認(rèn)為,前一個(gè)資源過(guò)來(lái)過(guò)程隨即終止,新的資源管理過(guò)程隨即開始。很多不同的方法可以用來(lái)觸發(fā)新的資源管理過(guò)程;在實(shí)驗(yàn)中,本文使用了基于時(shí)間的事件方法。但這不屬于本文的研究范圍,本文關(guān)注于如何進(jìn)行分布式的最優(yōu)資源控制。

給出了效用函數(shù)的定義后,本文使用受限梯度上升方法求解得到U(X)的最大值。根據(jù)定義:

因此,X處的梯度向量的i分量為:

n=［1,1,…,1］是超平面P的法向向量。最終,本文使用的梯度更新規(guī)則是:

為了分布式求解這一全局最優(yōu)問(wèn)題,每個(gè)智能體都有必要知道其他智能體的需求參數(shù)αi。下一節(jié)將引入傳播模型。

4.1.2 傳播模型

傳播模型形式化α值的傳播過(guò)程,以計(jì)算lnλ值。RSPE-DOC系統(tǒng)中,本文使用基于PUSH和PULL的同步策略來(lái)實(shí)現(xiàn)這一過(guò)程［3］。每個(gè)智能體通過(guò)把自己的信息副本推送(push)給鄰居節(jié)點(diǎn),并從鄰居節(jié)點(diǎn)那里拉取(pull)信息副本來(lái)同步自己和鄰居節(jié)點(diǎn)的信息,從而實(shí)現(xiàn)所有智能體都獲得一致的完整信息。

本文定義智能體傳播的消息格式為［ρi,αi(t)］,其中,ρi∈Ν是智能體ai(t)的標(biāo)識(shí)符,ai(t)是其需求參數(shù)。本文定義Οi(t)為智能體ai自身和其他所有跟ai通信過(guò)的智能體的標(biāo)識(shí)符的集合;Mi(t)為對(duì)應(yīng)的通信過(guò)的α值的多值集合。為提高通信過(guò)程中的比較效率,本文定義ki(t)為智能體ai所存儲(chǔ)的所有局部信息的校驗(yàn)函數(shù)［15］:

通過(guò)比較2個(gè)智能體的校驗(yàn)函數(shù)是否相同,即可方便地知道這2個(gè)智能體各自存儲(chǔ)的局部信息是否已經(jīng)獲得同步。具體地,本文定義差異函數(shù):

其中,&為按位與運(yùn)算符。易知,對(duì)智能體ai而言,所存儲(chǔ)的任意信息［ρ,α］,如果2ρ&gij(t)=2ρ成立,那么消息［ρ,α］應(yīng)該從智能體ai推送到智能體aj;類似的,如果2ρ&gji(t)=2ρ成立,那么消息［ρ,α］應(yīng)該從智能體aj拉取到智能體ai。這樣每一對(duì)［ρ,α］值都會(huì)被互為鄰居的智能體節(jié)點(diǎn)同步,最終同步給所有智能體。

4.1.3 終止模型

終止模型使智能體可以通過(guò)局部的信息交互來(lái)判斷何時(shí)可以停止傳播,這是RSPE-DOC系統(tǒng)重要的組成部分之一,終止模型告訴智能體何時(shí)準(zhǔn)備好計(jì)算lnλ值,進(jìn)而計(jì)算每個(gè)智能體自己的最優(yōu)資源份額Xi。這個(gè)過(guò)程必須是分布式的,以保證一定的系統(tǒng)容錯(cuò)性。為此,智能體需要維護(hù),并與其鄰居節(jié)點(diǎn)交換一些額外的信息。本文為智能體ai定義一個(gè)指示函數(shù)xi(t):

指示函數(shù)xi(t)的值反映了系統(tǒng)中有多少信息已經(jīng)被傳播了,較大的xi(t)的值意味著較多的值已經(jīng)被傳播。注意到xi(t)的值只依賴鄰居節(jié)點(diǎn)指示函數(shù)的值,所以xi(t)的計(jì)算是完全分布式的。理論上可以證明,任意智能體xi(t)的值最終會(huì)收斂于一個(gè)相同的常數(shù)值。事實(shí)上,當(dāng)t→∞時(shí),xi(t)→∑ai∈V(t)2ρi。這個(gè)性質(zhì)使得xi(t)成為一個(gè)可以用來(lái)判斷系統(tǒng)是否已經(jīng)穩(wěn)定的判據(jù)。系統(tǒng)穩(wěn)定的時(shí)候就可以停止傳播過(guò)程了。然而在實(shí)際系統(tǒng)中,并不能簡(jiǎn)單使用xi(t)的值來(lái)判斷系統(tǒng)是否穩(wěn)定,因?yàn)榫W(wǎng)絡(luò)延遲有可能導(dǎo)致xi(t)的值暫時(shí)停在某個(gè)常數(shù),而讓智能體作出誤判。為此,本文定義聯(lián)合差分函數(shù)di(t):

即使網(wǎng)絡(luò)延遲使得di(t)的值暫時(shí)停留在某一個(gè)值,也不會(huì)停留在0。這樣一旦di(t)的值趨于0,智能體ai就知道系統(tǒng)已經(jīng)穩(wěn)定了。

分布式系統(tǒng)一般都會(huì)隨著時(shí)間改變,即有智能體加入或者離開,所以本文有必要專門討論這些情況。本文分兩類來(lái)討論系統(tǒng)的變化:(1)智能體在資源管理過(guò)程之間加入或離開;(2)智能體在資源管理過(guò)程之中加入或離開。

在第(1)種情況下,系統(tǒng)的收斂性不會(huì)受到影響。因?yàn)閭鞑ツＰ筒灰蕾囉谌魏沃悄荏w數(shù)目相關(guān)的全局信息,所以資源管理過(guò)程開始之前,系統(tǒng)的任何變化都可以自動(dòng)被傳播模型處理,無(wú)需更進(jìn)一步的設(shè)置或者更新。由此,有計(jì)劃的系統(tǒng)改變不會(huì)影響傳播過(guò)程的收斂,系統(tǒng)也不需要為此重啟任何一個(gè)部分。

在第(2)種情況下,會(huì)導(dǎo)致一些問(wèn)題。比如,有智能體在某些di(t)為0后加入系統(tǒng),那么系統(tǒng)將不能進(jìn)入新的穩(wěn)定狀態(tài);或者,有智能體在資源管理過(guò)程中離開系統(tǒng),那么其α值還將會(huì)被繼續(xù)在系統(tǒng)中傳播,最終導(dǎo)致系統(tǒng)不能調(diào)整到新的穩(wěn)定狀態(tài)。在資源管理過(guò)程中,智能體的加入或離開屬于非計(jì)劃的系統(tǒng)改變。本文認(rèn)為非計(jì)劃的系統(tǒng)改變?cè)趯?shí)踐中可以盡量控制到最少。所以不失靈活性,本文假設(shè)非計(jì)劃的改變僅發(fā)生在兩個(gè)資源管理過(guò)程之間。

最終,本文需要考慮智能體間拓?fù)浣Y(jié)構(gòu)的改變(這種情況下,智能體數(shù)目不變)。因?yàn)橹悄荏w間的通信僅發(fā)生在互為鄰居節(jié)點(diǎn)之間,所以僅拓?fù)浣Y(jié)構(gòu)的改變不會(huì)影響系統(tǒng)的穩(wěn)定性,即使這種改變是發(fā)生在資源管理過(guò)程之中的。

4.1.4 需求模型

正如優(yōu)化模型中所定義的,αi(t)是反映智能體資

源需求的參數(shù)。這個(gè)參數(shù)的值應(yīng)由智能體的工作量和實(shí)際資源需求共同決定。所以,本文有必要定義需求模型。在視頻服務(wù)網(wǎng)中,工作量即是當(dāng)前需要完成傳輸?shù)囊曨l流中大小和CPU計(jì)算時(shí)間;實(shí)際資源需求主要是指?jìng)鬏敭?dāng)前視頻流所需要的帶寬總和。具體怎么給出需求模型有多種方法,但這不是本文的研究重點(diǎn)。本文主要關(guān)注于分布式的資源最優(yōu)控制策略。所以,本文認(rèn)為需求模型是已知的。在實(shí)驗(yàn)部分,本文會(huì)給出一種簡(jiǎn)單的表示方法以作示例。

4.2 多智能體模型

本節(jié)給出數(shù)學(xué)模型的算法實(shí)現(xiàn),RSPE-DOC系統(tǒng)中RSPE智能體結(jié)構(gòu)如圖2所示。智能體把實(shí)際工作量和資源需求傳給需求模型,需求模型計(jì)算出相應(yīng)的α值,并傳給終止模型,終止模型調(diào)用傳播模型傳播α值,并決定何時(shí)停止傳播。這時(shí),α值集合Mi(t)傳給優(yōu)化模型。優(yōu)化模型計(jì)算出智能體應(yīng)得的最優(yōu)資源份額,傳給底層物理系統(tǒng),并從那里得到分配的計(jì)算資源。

圖2 RSPE-DOC系統(tǒng)中的RSPE智能體結(jié)構(gòu)

5 實(shí)驗(yàn)驗(yàn)證

在實(shí)驗(yàn)中,資源池能提供的最大帶寬。本文定義αi(t)的計(jì)算公式為:其中,H=0.99。這樣,當(dāng)智能體ai實(shí)際分配的份額x=bi(t)時(shí),ui(x)=H;當(dāng)x＞bi(t)時(shí),ui(x)＞H。在這個(gè)定義下,當(dāng)智能體的需求得到滿足時(shí),其個(gè)體效用函數(shù)的值非常接近于1;另外,繼續(xù)追加份額,也不妨礙效用函數(shù)的值繼續(xù)增大。

5.1 資源分配實(shí)驗(yàn)

為驗(yàn)證資源分配的最優(yōu)性,本文假設(shè)底層物理資源池之上部署6個(gè)虛擬RSPE節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)在資源管理過(guò)程開始之前隨機(jī)確定其帶寬需求。這里是為了驗(yàn)證算法的最優(yōu)性,所以少量的智能體數(shù)目已經(jīng)可以達(dá)到目的。本文共進(jìn)行了2組實(shí)驗(yàn):在第1組實(shí)驗(yàn)里,智能體提出的平均整體需求基本上與系統(tǒng)最大服務(wù)能力持平,系統(tǒng)處于正常負(fù)載狀態(tài);在第2組實(shí)驗(yàn)里,智能體提出的評(píng)價(jià)整體需求遠(yuǎn)大于系統(tǒng)最大服務(wù)能力,系統(tǒng)處于過(guò)載工作狀態(tài)。2組實(shí)驗(yàn)中6個(gè)智能體對(duì)應(yīng)的泊松分布λ值如表1所示。在第1組實(shí)驗(yàn)中,66個(gè)智能體平均帶寬需求之和為1 000 MB/s;在第2組實(shí)驗(yàn)中,6個(gè)智能體平均帶寬需求之和為2 000 MB/s。

表1 智能體帶寬需求滿足的泊松分布參數(shù)

本文共進(jìn)行了100次獨(dú)立重復(fù)實(shí)驗(yàn)。觀察到平均的整體效用函數(shù)U(x)分別約為5.95±0.000 79和5.48±0.003 10。注意到,U(x)可能取得的最大值為6,U(x)越接近于6,智能體資源需求獲得滿足的情況越好,整體服務(wù)質(zhì)量也就越高。實(shí)驗(yàn)結(jié)果顯示,在系統(tǒng)正常負(fù)載狀態(tài)下,優(yōu)化模型找到的解對(duì)應(yīng)的整體效用函數(shù)的值非常接近于1;在系統(tǒng)過(guò)載狀態(tài)下,智能體的資源需求不可能全部得到滿足,優(yōu)化模型找到的解對(duì)應(yīng)的整體效用函數(shù)的值達(dá)不到最大值6(但事實(shí)上通過(guò)測(cè)試可以判定該解仍然是此過(guò)載狀態(tài)下的最優(yōu)解)。

5.2 傳播實(shí)驗(yàn)

為驗(yàn)證傳播模塊,本文定義一個(gè)周期(cycle)為智能體跟鄰居節(jié)點(diǎn)的一次同步過(guò)程,并假設(shè)所有智能體按相同時(shí)間信號(hào)運(yùn)行。對(duì)1～100范圍內(nèi)不同的智能體數(shù)目,分別重復(fù)測(cè)試6次,記錄每次實(shí)驗(yàn)中傳播模塊終止所需要的周期數(shù)和單個(gè)智能體為完成同步所需要的CPU計(jì)算時(shí)間。實(shí)驗(yàn)中系統(tǒng)結(jié)構(gòu)圖

中節(jié)點(diǎn)的度大小設(shè)定為5。實(shí)驗(yàn)結(jié)果見圖3。可以看出,傳播過(guò)程需要的周期數(shù)與智能體數(shù)目成對(duì)數(shù)關(guān)系,證明RSPE-DOC系統(tǒng)具有很好的可擴(kuò)展性;單個(gè)智能體傳播過(guò)程所需要的計(jì)算時(shí)間跟智能體數(shù)目成指數(shù)關(guān)系,但所需CPU計(jì)算時(shí)間非常少。可以看出,RSPE-DOC系統(tǒng)的反應(yīng)時(shí)間非常快,能滿足實(shí)時(shí)性要求。

圖3 傳播模型實(shí)驗(yàn)結(jié)果

5.3 收斂性實(shí)驗(yàn)

本文使用xi(t)值和di(t)值隨周期數(shù)的變化情況來(lái)驗(yàn)證系統(tǒng)的收斂性。實(shí)驗(yàn)時(shí),智能體數(shù)目設(shè)定為100,系統(tǒng)結(jié)構(gòu)拓?fù)鋱D中節(jié)點(diǎn)的度設(shè)定為5。本文記錄了每個(gè)智能體的xi(t)值和di(t)值,實(shí)驗(yàn)結(jié)果見圖4。可以看出,xi(t)值和di(t)值分別都可以正確地收斂到一個(gè)常數(shù)值和0。

圖4 收斂性實(shí)驗(yàn)結(jié)果

6 結(jié)束語(yǔ)

本文介紹了RSPE-DOC系統(tǒng)——一個(gè)完全分布式的視頻服務(wù)網(wǎng)資源池自適應(yīng)最優(yōu)控制方案。RSPE-DOC系統(tǒng)把每個(gè)RSPE節(jié)點(diǎn)視為資源消費(fèi)者,使用智能體代理資源消費(fèi)者向底層物理資源池提出資源請(qǐng)求,智能體之間以任意拓?fù)浣Y(jié)構(gòu)聯(lián)系,智能體通過(guò)同步需求信息把全局優(yōu)化問(wèn)題分解成分布式優(yōu)化問(wèn)題,從而最終確定每個(gè)智能體的最優(yōu)資源份額,以保證服務(wù)質(zhì)量,并提高資源利用率。實(shí)驗(yàn)結(jié)果表明,RSPE-DOC系統(tǒng)可以保證系統(tǒng)在不同負(fù)載狀態(tài)下的資源最優(yōu)分配,傳播過(guò)程可以很快終止,傳播所需CPU計(jì)算時(shí)間較少,并且系統(tǒng)可以正確收斂。RSPE-DOC系統(tǒng)假設(shè)RSPE節(jié)點(diǎn)的增加或刪除只發(fā)生在資源管理過(guò)程間,下一步工作將考慮放寬該限制,以提高RSPE-DOC系統(tǒng)的實(shí)時(shí)性,進(jìn)一步擴(kuò)大適用范圍。

［1]張 彬,李俊杰.我國(guó)三網(wǎng)融合業(yè)務(wù)發(fā)展研究［J］.信息系統(tǒng)工程,2010,(12):101-106.

［2]中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心.第29次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告［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

宋 辰,奚宏生.視頻服務(wù)節(jié)點(diǎn)共享資源池的分布式最優(yōu)控制［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金資助重點(diǎn)項(xiàng)目(61233003)。

宋 辰(1987-),女,碩士研究生,主研方向:網(wǎng)絡(luò)傳播系統(tǒng)與控制;奚宏生,教授、博士生導(dǎo)師。

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