脫立恒, 倪 宏, 李滿天, 劉 學(xué)
(1. 中國科學(xué)院大學(xué) 理學(xué)院,北京 100049;2. 中國科學(xué)院聲學(xué)研究所 國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京 100190)
隨著網(wǎng)絡(luò)和通信技術(shù)的進(jìn)步和發(fā)展,互聯(lián)網(wǎng)上出現(xiàn)了一大批新型網(wǎng)絡(luò)應(yīng)用,如網(wǎng)絡(luò)會議、網(wǎng)絡(luò)電視、社交網(wǎng)絡(luò)等,相比傳統(tǒng)的網(wǎng)頁沖浪、文件傳輸?shù)葢?yīng)用,新型應(yīng)用的特點是應(yīng)用服務(wù)器與用戶的交互性更強(qiáng),內(nèi)容數(shù)據(jù)容量更大,內(nèi)容的實時性要求更高.但現(xiàn)有的網(wǎng)絡(luò)基礎(chǔ)架構(gòu)采用簡單的端到端的設(shè)計原則,各路由節(jié)點單純實現(xiàn)數(shù)據(jù)包的存儲和轉(zhuǎn)發(fā),雖然在一定程度上這種簡單的設(shè)計原則健壯性高、擴(kuò)展性好、易于實現(xiàn),但是越來越不能滿足當(dāng)前新型業(yè)務(wù)的發(fā)展需求.
內(nèi)容網(wǎng)絡(luò)[1]的研究就是為了解決現(xiàn)有網(wǎng)絡(luò)體系架構(gòu)的不足,它通過在現(xiàn)有的互聯(lián)網(wǎng)上部署服務(wù)節(jié)點,使用應(yīng)用層協(xié)議將這些服務(wù)節(jié)點構(gòu)建成一個存在于IP網(wǎng)絡(luò)之上的覆蓋網(wǎng)絡(luò),從而實現(xiàn)為新型應(yīng)用提供協(xié)同服務(wù).通過將服務(wù)部署在覆蓋網(wǎng)的各服務(wù)節(jié)點上,可以增加網(wǎng)絡(luò)的靈活性,提高應(yīng)用的響應(yīng)時間,增強(qiáng)用戶的使用體驗,改善骨干核心網(wǎng)的擁塞問題.覆蓋網(wǎng)絡(luò)中的服務(wù)部署一直是一個熱點研究問題,國內(nèi)外許多研究者對該問題進(jìn)行了研究.服務(wù)節(jié)點部署屬于選址問題,選址問題模型分為3類:基于確定信息的節(jié)點部署模型[2],基于概率模型的節(jié)點部署模型[3]和基于博弈論的節(jié)點部署模型[4-5].Guha等從分層網(wǎng)絡(luò)設(shè)計出發(fā),以部署成本和層間路由成本最小化為優(yōu)化目標(biāo),提出一種分層服務(wù)部署模型[6].Laoutaris等研究了大規(guī)模內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Deliver Network,CDN)的服務(wù)節(jié)點部署問題,提出了分布式的無容量約束K中值和無容量約束節(jié)點選址等兩種模型[7].Cahill等提出了一個針對流媒體服務(wù)部署問題的優(yōu)化模型,優(yōu)化目標(biāo)為用戶到服務(wù)器的連接成本和服務(wù)器的存儲成本的組合[8].另外,一些研究者針對云平臺上的虛擬設(shè)施部署,同樣給出了多種解決方法[9-11],云平臺上的虛擬設(shè)施同樣是服務(wù)部署的實例化.Kecskemeti等提出了一種針對虛擬設(shè)備分布的服務(wù)部署方法,該方法以降低虛擬設(shè)備分布開銷為目標(biāo)[9].郭濤等提出了云平臺下一種虛擬機(jī)的個性化部署機(jī)制,該機(jī)制通過時間序列預(yù)測機(jī)制對宿主機(jī)的負(fù)載進(jìn)行預(yù)測,進(jìn)而實現(xiàn)虛擬設(shè)施部署[10].
以上研究都是基于一定的覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或云平臺結(jié)構(gòu),針對具體應(yīng)用或虛擬設(shè)施的需求,設(shè)定不同的優(yōu)化目標(biāo)模型,其局限性是模型都針對單一服務(wù),沒有考慮多種服務(wù)共存的部署問題.陳香蘭等研究了組合服務(wù)中的多服務(wù)靜態(tài)部署問題[11],針對基于因特網(wǎng)的服務(wù)系統(tǒng),不考慮節(jié)點間的拓?fù)浣Y(jié)構(gòu),提出了基礎(chǔ)服務(wù)靜態(tài)部署的最優(yōu)化模型,在保證服務(wù)負(fù)載均衡分配以及服務(wù)請求傳遞的通信流量最小化的約束下,最優(yōu)化服務(wù)部署的規(guī)模.但該研究成果只能針對基于Intranet的企業(yè)級應(yīng)用,應(yīng)用面狹窄.
綜上,筆者考慮的應(yīng)用場景是在廣域網(wǎng)絡(luò)的覆蓋層上的多服務(wù)靜態(tài)部署問題,不同于Intranet環(huán)境的研究,各服務(wù)節(jié)點間的通信時延開銷將大幅影響用戶的應(yīng)用體驗,多服務(wù)的特性也使得它有別于以上討論中涉及的單一服務(wù)部署問題.因此,筆者提出了一種新的多服務(wù)部署模型,綜合考慮了服務(wù)部署規(guī)模和用戶的服務(wù)響應(yīng)時間兩方面的需求,給出了啟發(fā)式的求解算法.
考慮一個廣域網(wǎng)環(huán)境中的覆蓋網(wǎng)絡(luò),令N為網(wǎng)絡(luò)中的服務(wù)節(jié)點數(shù)目,服務(wù)節(jié)點集合L= {l1,l2,…,lN},節(jié)點可能是同構(gòu)的,也可能是異構(gòu)的,節(jié)點間通過底層的物理網(wǎng)絡(luò)互連.系統(tǒng)中每個服務(wù)節(jié)點都可以部署多個服務(wù),并且任意一個服務(wù)都可以完整地在任一節(jié)點上執(zhí)行.設(shè)K為服務(wù)的種類數(shù).服務(wù)集合S= {s1,s2,…,sK},實際服務(wù)部署問題即為生成N個滿足條件的Sj的集合.
(1)
(2)
(3)
由服務(wù)請求分配矩陣,可以得到服務(wù)部署規(guī)模的定義,設(shè)節(jié)點i上的服務(wù)副本的個數(shù)為節(jié)點i的服務(wù)部署規(guī)模,可以由服務(wù)請求分配矩陣得到服務(wù)部署矩陣,即
(7)
整個系統(tǒng)的服務(wù)部署規(guī)模為各節(jié)點服務(wù)規(guī)模之和,可表示為
(8)
顯然,最大的服務(wù)部署規(guī)模為在每一個節(jié)點上部署所有K個服務(wù),即Mmax=KN.
網(wǎng)絡(luò)應(yīng)用服務(wù)系統(tǒng)中響應(yīng)時間是用戶服務(wù)質(zhì)量最重要的參數(shù).服務(wù)響應(yīng)時間通常包括通信延遲和服務(wù)處理延遲,當(dāng)服務(wù)系統(tǒng)存在請求轉(zhuǎn)發(fā)時,服務(wù)響應(yīng)時間還包括請求轉(zhuǎn)發(fā)延遲,這里重點研究請求轉(zhuǎn)發(fā)延遲.假設(shè)任意兩個服務(wù)節(jié)點間的通信延遲用轉(zhuǎn)發(fā)延遲矩陣表示為
(9)
其中,ti,j表示節(jié)點i與節(jié)點j間的通信時延,可以用跳數(shù)表示,也可以用實際時延表示.假設(shè)任意兩個節(jié)點請求,經(jīng)過第3個節(jié)點的轉(zhuǎn)發(fā)后的通信時延均比兩個節(jié)點直接轉(zhuǎn)發(fā)通信時延要大(該條件可由底層物理網(wǎng)絡(luò)路由保證),即滿足
tp(1),p(2)+tp(2),p(3)>tp(1),p(3).
(10)
下面研究在平均請求轉(zhuǎn)發(fā)時間滿足服務(wù)質(zhì)量要求時,如何使服務(wù)部署規(guī)模最小化.假設(shè)服務(wù)系統(tǒng)的平均請求轉(zhuǎn)發(fā)延遲滿足
(11)
其中,T為服務(wù)質(zhì)量要求的最大請求轉(zhuǎn)發(fā)延遲.
(12)
綜合以上定義,在請求轉(zhuǎn)發(fā)延遲限制在一定范圍之內(nèi),同時滿足服務(wù)器的并發(fā)上限要求和最小化服務(wù)部署規(guī)模時,可以定義覆蓋網(wǎng)絡(luò)中的多服務(wù)靜態(tài)部署問題模型(Static Multi-Service deployment Model, SMSPM)為
(13)
定理1 SMSPM問題是非確定性多項式時間(NP)完全問題.
證明 分兩步證明SMSPM問題是NP完全的.先證明SMSPM是NP問題,再證SMSPM是NP難的.
步驟1 SMSPM問題是NP問題.給定一個帶權(quán)重的圖G=V,E,其中,頂點由n個服務(wù)器和m個用戶構(gòu)成.每個服務(wù)器有兩個屬性l和o,l表示服務(wù)器所屬的服務(wù)節(jié)點,o表示服務(wù)器所能提供的服務(wù).每個用戶節(jié)點有兩個屬性分別為i和k,i節(jié)點是該用戶轉(zhuǎn)發(fā)開銷為0的服務(wù)節(jié)點,k代表該用戶請求的服務(wù)類型,將用戶轉(zhuǎn)發(fā)到服務(wù)節(jié)點時,其轉(zhuǎn)發(fā)開銷為.當(dāng)i=l且k=o時,轉(zhuǎn)發(fā)開銷為0;當(dāng)k=o且i≠l時,轉(zhuǎn)發(fā)開銷為ti,j;當(dāng)k≠o時,轉(zhuǎn)發(fā)開銷為∞.每個服務(wù)節(jié)點的請求上限為.假設(shè)Tm是將所有用戶(即請求)指派給服務(wù)節(jié)點后的平均轉(zhuǎn)發(fā)延遲開銷,驗證SMSPM問題是NP完全問題即是在給定的指派中,是否存在平均轉(zhuǎn)發(fā)延遲開銷為Tm的方案.假設(shè)A是“非確定性圖靈機(jī)”,A的輸入為n個服務(wù)器構(gòu)成的集合Sj,m個用戶構(gòu)成的集合U和總開銷T的猜測函數(shù)f.非確定性圖靈機(jī)的工作包括兩步:A非確定性猜測可能的指派方案.函數(shù)f確認(rèn)猜測的指派方案的平均轉(zhuǎn)發(fā)延遲開銷是否為Tm,若驗證成功,則停止;否則,繼續(xù).因此,至少在給定一個用戶到服務(wù)器的指派,驗證該指派方案的平均轉(zhuǎn)發(fā)延遲開銷是否為Tm,即為將所有轉(zhuǎn)發(fā)延遲開銷相加后取平均,時間復(fù)雜度為O(n),驗證過程可以在多項式時間內(nèi)確定.一旦用戶指派方案確定后,服務(wù)的部署問題隨之解決.因此,SMSPM問題是NP問題.
步驟2 SMSPM問題是NP難的.假設(shè)存在可求解SMSPM問題的多項式時間,可將上述問題簡化后用以解決設(shè)施選址問題(Facility Location Problem,F(xiàn)LP)[13-14].FLP將用戶i的帶寬需求設(shè)置為 band(i),每個服務(wù)器設(shè)置帶寬上限,SMSPM將服務(wù)器的并發(fā)上限抽象為FLP的帶寬上限,將用戶i到服務(wù)器的并發(fā)貢獻(xiàn)抽象為FLP的帶寬需求為band(i),即SMSPM問題的 band(i)=1 ,用戶到服務(wù)器的指派僅依賴于并發(fā)限制和轉(zhuǎn)發(fā)延遲兩個限制條件.因為FLP能用SMSPM的多項式時間算法在多項式時間內(nèi)求解.文獻(xiàn)[14]中證明FLP是NP難的,因此,SMSPM問題是NP完全問題.
文中使用啟發(fā)式算法對SMSPM問題進(jìn)行求解,其核心思想是貪婪策略.假設(shè)在初始時,所有節(jié)點均部署所有服務(wù),每次選擇使得總的轉(zhuǎn)發(fā)延遲開銷最小的節(jié)點上的服務(wù)進(jìn)行刪除.步驟如下:
(1) 選中一個節(jié)點,計算刪除其上任意一個服務(wù)所帶來總的轉(zhuǎn)發(fā)延遲開銷增量,選擇最小增量的服務(wù),即為該節(jié)點刪除服務(wù)的最小轉(zhuǎn)發(fā)開銷.
(2) 計算每個節(jié)點的最小轉(zhuǎn)發(fā)延遲開銷,選擇所有節(jié)點中最小轉(zhuǎn)發(fā)延遲開銷的節(jié)點,作為N個節(jié)點中的最小轉(zhuǎn)發(fā)延遲開銷.
(3) 刪除N個節(jié)點中最小轉(zhuǎn)發(fā)開銷的節(jié)點對應(yīng)的服務(wù).
圖1 請求分級轉(zhuǎn)發(fā)
圖2 請求轉(zhuǎn)發(fā)重分配
由于SMSPM模型分別從服務(wù)請求可以多次轉(zhuǎn)發(fā)到不同節(jié)點和服務(wù)請求可以分流轉(zhuǎn)發(fā)到多個節(jié)點等角度對實際問題進(jìn)行抽象,其模型復(fù)雜,使用的啟發(fā)式算法的復(fù)雜度也比較高.首先分析BND算法.BND算法先計算任意一個節(jié)點的請求轉(zhuǎn)發(fā)最小延遲開銷,共要計算N次;繼續(xù)深入,選定1個節(jié)點后,計算該節(jié)點去掉任意一個服務(wù)所帶來的最小延遲開銷,共要計算K次.假如已經(jīng)有其他節(jié)點 (N-1) 向該節(jié)點轉(zhuǎn)發(fā)該服務(wù),則要將該轉(zhuǎn)發(fā)請求轉(zhuǎn)發(fā)到其他節(jié)點上,同樣是N-1 種可能,分配完該部分后,再計算將選定節(jié)點的選定服務(wù)請求轉(zhuǎn)發(fā)到其他節(jié)點上,所以計算任意1個節(jié)點刪除的1個服務(wù)算法復(fù)雜度為O(NK[(N-1)(N-1)+N]),由于每次刪除1個服務(wù),所以最多刪除服務(wù)數(shù)即為NK,所有算法總的復(fù)雜度為O((NK)NK[(N-1)(N-1)+N]),即該算法的算法復(fù)雜度為O(N4K2).BND算法是在多項式時間內(nèi)可解的,但該算法算出的復(fù)雜度是算法的最大上限.實際中,當(dāng)算法開始運行時,由于節(jié)點相互轉(zhuǎn)發(fā)比較少,即公式 (N-1)(N-1) 很小,當(dāng)算法運行到一定節(jié)點時,雖然轉(zhuǎn)發(fā)情況增多,但由于服務(wù)的減少,(N-1)(N-1)、N和K的規(guī)模都在降低.同理,可以分析得到NBND算法的復(fù)雜度為O(N3K2),由于NBND算法省去了轉(zhuǎn)發(fā)的請求重新轉(zhuǎn)發(fā)的步驟,每次轉(zhuǎn)發(fā)1個請求后,再次選擇服務(wù)時,其轉(zhuǎn)發(fā)到其他節(jié)點數(shù)小于N,故實際NBND算法比BND算法的復(fù)雜度低很多.
通過仿真對比了BND算法和NBND算法的運算結(jié)果.文中模擬了N=20,K=30 的服務(wù)系統(tǒng),隨機(jī)生成服務(wù)請求矩陣,每個節(jié)點每種服務(wù)的請求到達(dá)率控制在0~100,隨機(jī)生成轉(zhuǎn)發(fā)延遲矩陣,轉(zhuǎn)發(fā)延遲范圍控制在51~100,假設(shè)所有節(jié)點的最大服務(wù)上限均相同,并且要求初始狀態(tài)時,節(jié)點所有服務(wù)的請求到達(dá)率之和小于服務(wù)器最大服務(wù)上限.系統(tǒng)每運行1次稱為1次運行實例.1次運行實例包括隨機(jī)生成1次服務(wù)請求矩陣,并分別通過BND算法和NBND算法求解服務(wù)部署和請求轉(zhuǎn)發(fā)方案.
圖3 部署規(guī)模對平均轉(zhuǎn)發(fā)延遲開銷的影響
模擬實驗分別比較了兩種啟發(fā)式算法在求解SMSPM問題時的服務(wù)部署規(guī)模、平均轉(zhuǎn)發(fā)延遲開銷變化和算法復(fù)雜度變化.由于算法是從所有節(jié)點部署的所有服務(wù)開始的,當(dāng)每次減少服務(wù)部署規(guī)模時,平均轉(zhuǎn)發(fā)延遲開銷與服務(wù)部署規(guī)模減少量的變化情況如圖3所示.隨著服務(wù)部署規(guī)模減少量的增大,請求轉(zhuǎn)發(fā)延遲的開銷不斷增加.算法開始時,BND算法和NBND算法的平均轉(zhuǎn)發(fā)開銷隨著服務(wù)部署規(guī)模的減少而相同增加轉(zhuǎn)發(fā)延遲,但到達(dá)一定程度時,由于BND算法的回退步驟將之前的轉(zhuǎn)發(fā)請求重新調(diào)整,因此,BND算法的平均轉(zhuǎn)發(fā)開銷比NBND算法的轉(zhuǎn)發(fā)開銷增加速度慢,在達(dá)到目標(biāo)平均轉(zhuǎn)發(fā)開銷時,BND算法的規(guī)模減少量更大,即BND算法使得服務(wù)部署規(guī)模更?。畧D4給出了兩種算法的循環(huán)次數(shù)對比,BND算法的回退算法更加復(fù)雜,隨著服務(wù)部署規(guī)模的減小,其循環(huán)次數(shù)的增加越來越快.文中運行100次運行實例,將兩種算法的服務(wù)部署規(guī)模進(jìn)行了概率統(tǒng)計,概率密度如圖5所示.BND算法的平均服務(wù)部署規(guī)模為246,NBND算法的平均服務(wù)部署規(guī)模為287,兩種算法分別將服務(wù)部署規(guī)模降低了59%和52.2%.
圖4 計算復(fù)雜度對比圖5 服務(wù)部署規(guī)模概率密度分布
研究了覆蓋網(wǎng)絡(luò)中多服務(wù)靜態(tài)部署問題.在服務(wù)部署過程中考慮系統(tǒng)平均轉(zhuǎn)發(fā)時間限制和服務(wù)節(jié)點的最大服務(wù)規(guī)模限制,定義了一種更加全面的問題模型——SMSPM,證明了SMSPM問題屬于NP完全問題.給出了兩種貪婪啟發(fā)式算法BND和NBND,通過兩種算法分別對SMSPM問題進(jìn)行求解,并分析其時間復(fù)雜度.通過仿真,驗證了SMSPM模型的有效性,BND和NBND兩種算法將服務(wù)部署規(guī)模分別降低了59%和52.2%.對于NP完全問題,有多種近似算法,文中給出的啟發(fā)式算法復(fù)雜度較高.接下來的研究工作是設(shè)計更加高效的近似算法.
[1] 尹浩, 袁小群, 林闖, 等. 內(nèi)容網(wǎng)絡(luò)服務(wù)節(jié)點部署理論綜述[J]. 計算機(jī)學(xué)報, 2010, 33(9): 1161-1620.
Yin Hao, Yuan Xiaoqun, Lin Chuang, et al. The Survey of Service Nodes Deployment Theories for Content Networks[J]. Chinese Journal of Computers, 2010, 33(9): 1161-1620.
[2] Goldengorin B, Ghosh D, Sierksma G. Branch and PEG Algorithms for the Simple Plant Location Problem[J]. Computers & Operations Research, 2003, 30(7): 967-981.
[3] Brimberg J, Hansen P, Mladenovic N, et al. Improvement and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem[J]. Operations Research, 2000, 48(3): 444-460.
[4] Rosing K E. An Optimal Method for Solving the (Generalized) Multi-Weber Problem[J]. European Journal of Operational Research, 1992, 58(3): 414-426.
[5] Chekuri C, Chuzhoy J, Lewin-Eytan L, et al. Non-cooperative Multicast and Facility Location Games[C]//Proceedings of the 7th ACM Conference on Electronic Commerce. New York: ACM, 2006: 72-81.
[6] Guha S, Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms[J]. Journal of Algorithms, 1999, 31(1): 228-248.
[7] Laoutaris N, Smaragdakis G, Oikonomou K, et al. Distributed Deployment of Service Facilities in Large-scale Networks[C]//Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 2144-2152.
[8] Cahill A J, Sreenan C J. An Efficient CDN Deployment Algorithm for the Delivery of High-quality TV Content[C]//Proceedings of the 12th Annual ACM International Conference on Multimedia. New York: ACM, 2004: 975-976.
[9] Kecskemeti G, Terstyanszky G, Kacsuk P, et al. An Approach for Virtual Appliance Distribution for Service Deployment[J]. Future Generation Computer Systems, 2011, 27(3): 280-289.
[10] 郭濤, 溫少君, 陳俊杰. 基于個性化的云平臺虛擬機(jī)部署機(jī)制的研究[J]. 太原理工大學(xué)學(xué)報, 2012, 43(2): 125-129.
Guo Tao, Wen Shaojun, Chen Junjie. The Research on Personalized VM Deployment Mechanism in Cloud[J]. Journal of Taiyuan University of Technology, 2012, 43(2): 125-129.
[11] Liu T, Lu T, Wang W, et al. SDMS-O: a Service Deployment Management System for Optimization in Clouds While Guaranteeing Users’ QoS Requirements[J]. Future Generation Computer Systems, 2012, 28(7): 1100-1109.
[12] 陳香蘭, 李曦, 龔育昌. 服務(wù)組合中一種靜態(tài)基礎(chǔ)服務(wù)部署研究[J]. 小型微型計算機(jī)系統(tǒng), 2008, 29(4): 709-714.
Chen Xianglan, Li Xi, Gong Yuchang. Static Service Deployment Algorithm in Service Composition[J]. Journal of Chinese Computer Systems, 2008, 29(4): 709-714.
[13] 史佩昌, 王懷民, 尹剛, 等. 云服務(wù)傳遞網(wǎng)絡(luò)資源動態(tài)分配模型[J]. 計算機(jī)學(xué)報, 2011, 34(12): 2305-2318.
Shi Peichang, Wang Huaimin, Yin Gang, et al. The Dynamic Allocation Model for the Resources of Cloud Services Delivery Network[J]. Chinese Journal of Computers, 2011, 34(12): 2305-2318.
[14] Averbakh I. Complexity of Robust Single Facility Location Problems on Networks with Uncertain Edge Lengths[J]. Discrete Applied Mathematics, 2003, 127(3): 505-522.