脫立恒， 倪 宏， 李滿天， 劉 學(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ā)式的求解算法．

1 多服務(wù)靜態(tài)部署模型

1.1 部署模型描述

考慮一個廣域網(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．

1.2 資源限制

網(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)

1.3 問題描述

綜合以上定義，在請求轉(zhuǎn)發(fā)延遲限制在一定范圍之內(nèi)，同時滿足服務(wù)器的并發(fā)上限要求和最小化服務(wù)部署規(guī)模時，可以定義覆蓋網(wǎng)絡(luò)中的多服務(wù)靜態(tài)部署問題模型(Static Multi-Service deployment Model， SMSPM)為

(13)

1.4 SMSPM模型分析

定理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完全問題．

2 啟發(fā)式算法

2.1 算法思想

文中使用啟發(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ā)重分配

2.2 算法復(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ù)雜度低很多．

3 實驗仿真分析

通過仿真對比了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ī)模概率密度分布

4 結(jié) 束 語

研究了覆蓋網(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.