覆蓋網(wǎng)絡中多服務靜態(tài)部署算法

脫立恒， 倪 宏， 李滿天， 劉 學

(1. 中國科學院大學 理學院，北京 100049；2. 中國科學院聲學研究所 國家網(wǎng)絡新媒體工程技術研究中心，北京 100190)

隨著網(wǎng)絡和通信技術的進步和發(fā)展，互聯(lián)網(wǎng)上出現(xiàn)了一大批新型網(wǎng)絡應用，如網(wǎng)絡會議、網(wǎng)絡電視、社交網(wǎng)絡等，相比傳統(tǒng)的網(wǎng)頁沖浪、文件傳輸?shù)葢茫滦蛻玫奶攸c是應用服務器與用戶的交互性更強，內(nèi)容數(shù)據(jù)容量更大，內(nèi)容的實時性要求更高．但現(xiàn)有的網(wǎng)絡基礎架構采用簡單的端到端的設計原則，各路由節(jié)點單純實現(xiàn)數(shù)據(jù)包的存儲和轉發(fā)，雖然在一定程度上這種簡單的設計原則健壯性高、擴展性好、易于實現(xiàn)，但是越來越不能滿足當前新型業(yè)務的發(fā)展需求．

內(nèi)容網(wǎng)絡[1]的研究就是為了解決現(xiàn)有網(wǎng)絡體系架構的不足，它通過在現(xiàn)有的互聯(lián)網(wǎng)上部署服務節(jié)點，使用應用層協(xié)議將這些服務節(jié)點構建成一個存在于IP網(wǎng)絡之上的覆蓋網(wǎng)絡，從而實現(xiàn)為新型應用提供協(xié)同服務．通過將服務部署在覆蓋網(wǎng)的各服務節(jié)點上，可以增加網(wǎng)絡的靈活性，提高應用的響應時間，增強用戶的使用體驗，改善骨干核心網(wǎng)的擁塞問題．覆蓋網(wǎng)絡中的服務部署一直是一個熱點研究問題，國內(nèi)外許多研究者對該問題進行了研究．服務節(jié)點部署屬于選址問題，選址問題模型分為3類：基于確定信息的節(jié)點部署模型[2]，基于概率模型的節(jié)點部署模型[3]和基于博弈論的節(jié)點部署模型[4-5]．Guha等從分層網(wǎng)絡設計出發(fā)，以部署成本和層間路由成本最小化為優(yōu)化目標，提出一種分層服務部署模型[6]．Laoutaris等研究了大規(guī)模內(nèi)容分發(fā)網(wǎng)絡(Content Deliver Network，CDN)的服務節(jié)點部署問題，提出了分布式的無容量約束K中值和無容量約束節(jié)點選址等兩種模型[7]．Cahill等提出了一個針對流媒體服務部署問題的優(yōu)化模型，優(yōu)化目標為用戶到服務器的連接成本和服務器的存儲成本的組合[8]．另外，一些研究者針對云平臺上的虛擬設施部署，同樣給出了多種解決方法[9-11]，云平臺上的虛擬設施同樣是服務部署的實例化．Kecskemeti等提出了一種針對虛擬設備分布的服務部署方法，該方法以降低虛擬設備分布開銷為目標[9]．郭濤等提出了云平臺下一種虛擬機的個性化部署機制，該機制通過時間序列預測機制對宿主機的負載進行預測，進而實現(xiàn)虛擬設施部署[10]．

以上研究都是基于一定的覆蓋網(wǎng)絡拓撲結構或云平臺結構，針對具體應用或虛擬設施的需求，設定不同的優(yōu)化目標模型，其局限性是模型都針對單一服務，沒有考慮多種服務共存的部署問題．陳香蘭等研究了組合服務中的多服務靜態(tài)部署問題[11]，針對基于因特網(wǎng)的服務系統(tǒng)，不考慮節(jié)點間的拓撲結構，提出了基礎服務靜態(tài)部署的最優(yōu)化模型，在保證服務負載均衡分配以及服務請求傳遞的通信流量最小化的約束下，最優(yōu)化服務部署的規(guī)模．但該研究成果只能針對基于Intranet的企業(yè)級應用，應用面狹窄．

綜上，筆者考慮的應用場景是在廣域網(wǎng)絡的覆蓋層上的多服務靜態(tài)部署問題，不同于Intranet環(huán)境的研究，各服務節(jié)點間的通信時延開銷將大幅影響用戶的應用體驗，多服務的特性也使得它有別于以上討論中涉及的單一服務部署問題．因此，筆者提出了一種新的多服務部署模型，綜合考慮了服務部署規(guī)模和用戶的服務響應時間兩方面的需求，給出了啟發(fā)式的求解算法．

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

1.1 部署模型描述

考慮一個廣域網(wǎng)環(huán)境中的覆蓋網(wǎng)絡，令N為網(wǎng)絡中的服務節(jié)點數(shù)目，服務節(jié)點集合L= {l1，l2，…，lN}，節(jié)點可能是同構的，也可能是異構的，節(jié)點間通過底層的物理網(wǎng)絡互連．系統(tǒng)中每個服務節(jié)點都可以部署多個服務，并且任意一個服務都可以完整地在任一節(jié)點上執(zhí)行．設K為服務的種類數(shù)．服務集合S= {s1，s2，…，sK}，實際服務部署問題即為生成N個滿足條件的Sj的集合．

(1)

(2)

(3)

由服務請求分配矩陣，可以得到服務部署規(guī)模的定義，設節(jié)點i上的服務副本的個數(shù)為節(jié)點i的服務部署規(guī)模，可以由服務請求分配矩陣得到服務部署矩陣，即

(7)

整個系統(tǒng)的服務部署規(guī)模為各節(jié)點服務規(guī)模之和，可表示為

(8)

顯然，最大的服務部署規(guī)模為在每一個節(jié)點上部署所有K個服務，即Mmax=KN．

1.2 資源限制

網(wǎng)絡應用服務系統(tǒng)中響應時間是用戶服務質(zhì)量最重要的參數(shù)．服務響應時間通常包括通信延遲和服務處理延遲，當服務系統(tǒng)存在請求轉發(fā)時，服務響應時間還包括請求轉發(fā)延遲，這里重點研究請求轉發(fā)延遲．假設任意兩個服務節(jié)點間的通信延遲用轉發(fā)延遲矩陣表示為

(9)

其中，ti，j表示節(jié)點i與節(jié)點j間的通信時延，可以用跳數(shù)表示，也可以用實際時延表示．假設任意兩個節(jié)點請求，經(jīng)過第3個節(jié)點的轉發(fā)后的通信時延均比兩個節(jié)點直接轉發(fā)通信時延要大(該條件可由底層物理網(wǎng)絡路由保證)，即滿足

tp(1)，p(2)+tp(2)，p(3)>tp(1)，p(3)．

(10)

下面研究在平均請求轉發(fā)時間滿足服務質(zhì)量要求時，如何使服務部署規(guī)模最小化．假設服務系統(tǒng)的平均請求轉發(fā)延遲滿足

(11)

其中，T為服務質(zhì)量要求的最大請求轉發(fā)延遲．

(12)

1.3 問題描述

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

(13)

1.4 SMSPM模型分析

定理1 SMSPM問題是非確定性多項式時間(NP)完全問題．

證明 分兩步證明SMSPM問題是NP完全的．先證明SMSPM是NP問題，再證SMSPM是NP難的．

步驟1 SMSPM問題是NP問題．給定一個帶權重的圖G=V，E，其中，頂點由n個服務器和m個用戶構成．每個服務器有兩個屬性l和o，l表示服務器所屬的服務節(jié)點，o表示服務器所能提供的服務．每個用戶節(jié)點有兩個屬性分別為i和k，i節(jié)點是該用戶轉發(fā)開銷為0的服務節(jié)點，k代表該用戶請求的服務類型，將用戶轉發(fā)到服務節(jié)點時，其轉發(fā)開銷為．當i=l且k=o時，轉發(fā)開銷為0；當k=o且i≠l時，轉發(fā)開銷為ti，j；當k≠o時，轉發(fā)開銷為∞．每個服務節(jié)點的請求上限為．假設Tm是將所有用戶(即請求)指派給服務節(jié)點后的平均轉發(fā)延遲開銷，驗證SMSPM問題是NP完全問題即是在給定的指派中，是否存在平均轉發(fā)延遲開銷為Tm的方案．假設A是“非確定性圖靈機”，A的輸入為n個服務器構成的集合Sj，m個用戶構成的集合U和總開銷T的猜測函數(shù)f．非確定性圖靈機的工作包括兩步：A非確定性猜測可能的指派方案．函數(shù)f確認猜測的指派方案的平均轉發(fā)延遲開銷是否為Tm，若驗證成功，則停止；否則，繼續(xù)．因此，至少在給定一個用戶到服務器的指派，驗證該指派方案的平均轉發(fā)延遲開銷是否為Tm，即為將所有轉發(fā)延遲開銷相加后取平均，時間復雜度為O(n)，驗證過程可以在多項式時間內(nèi)確定．一旦用戶指派方案確定后，服務的部署問題隨之解決．因此，SMSPM問題是NP問題．

步驟2 SMSPM問題是NP難的．假設存在可求解SMSPM問題的多項式時間，可將上述問題簡化后用以解決設施選址問題(Facility Location Problem，F(xiàn)LP)[13-14]．FLP將用戶i的帶寬需求設置為 band(i)，每個服務器設置帶寬上限，SMSPM將服務器的并發(fā)上限抽象為FLP的帶寬上限，將用戶i到服務器的并發(fā)貢獻抽象為FLP的帶寬需求為band(i)，即SMSPM問題的 band(i)=1 ，用戶到服務器的指派僅依賴于并發(fā)限制和轉發(fā)延遲兩個限制條件．因為FLP能用SMSPM的多項式時間算法在多項式時間內(nèi)求解．文獻[14]中證明FLP是NP難的，因此，SMSPM問題是NP完全問題．

2 啟發(fā)式算法

2.1 算法思想

文中使用啟發(fā)式算法對SMSPM問題進行求解，其核心思想是貪婪策略．假設在初始時，所有節(jié)點均部署所有服務，每次選擇使得總的轉發(fā)延遲開銷最小的節(jié)點上的服務進行刪除．步驟如下:

(1) 選中一個節(jié)點，計算刪除其上任意一個服務所帶來總的轉發(fā)延遲開銷增量，選擇最小增量的服務，即為該節(jié)點刪除服務的最小轉發(fā)開銷．

(2) 計算每個節(jié)點的最小轉發(fā)延遲開銷，選擇所有節(jié)點中最小轉發(fā)延遲開銷的節(jié)點，作為N個節(jié)點中的最小轉發(fā)延遲開銷．

(3) 刪除N個節(jié)點中最小轉發(fā)開銷的節(jié)點對應的服務．

圖1 請求分級轉發(fā)

圖2 請求轉發(fā)重分配

2.2 算法復雜度分析

由于SMSPM模型分別從服務請求可以多次轉發(fā)到不同節(jié)點和服務請求可以分流轉發(fā)到多個節(jié)點等角度對實際問題進行抽象，其模型復雜，使用的啟發(fā)式算法的復雜度也比較高．首先分析BND算法．BND算法先計算任意一個節(jié)點的請求轉發(fā)最小延遲開銷，共要計算N次；繼續(xù)深入，選定1個節(jié)點后，計算該節(jié)點去掉任意一個服務所帶來的最小延遲開銷，共要計算K次．假如已經(jīng)有其他節(jié)點 (N-1) 向該節(jié)點轉發(fā)該服務，則要將該轉發(fā)請求轉發(fā)到其他節(jié)點上，同樣是N-1 種可能，分配完該部分后，再計算將選定節(jié)點的選定服務請求轉發(fā)到其他節(jié)點上，所以計算任意1個節(jié)點刪除的1個服務算法復雜度為O(NK[(N-1)(N-1)+N])，由于每次刪除1個服務，所以最多刪除服務數(shù)即為NK，所有算法總的復雜度為O((NK)NK[(N-1)(N-1)+N])，即該算法的算法復雜度為O(N4K2)．BND算法是在多項式時間內(nèi)可解的，但該算法算出的復雜度是算法的最大上限．實際中，當算法開始運行時，由于節(jié)點相互轉發(fā)比較少，即公式 (N-1)(N-1) 很小，當算法運行到一定節(jié)點時，雖然轉發(fā)情況增多，但由于服務的減少，(N-1)(N-1)、N和K的規(guī)模都在降低．同理，可以分析得到NBND算法的復雜度為O(N3K2)，由于NBND算法省去了轉發(fā)的請求重新轉發(fā)的步驟，每次轉發(fā)1個請求后，再次選擇服務時，其轉發(fā)到其他節(jié)點數(shù)小于N，故實際NBND算法比BND算法的復雜度低很多．

3 實驗仿真分析

通過仿真對比了BND算法和NBND算法的運算結果．文中模擬了N=20，K=30 的服務系統(tǒng)，隨機生成服務請求矩陣，每個節(jié)點每種服務的請求到達率控制在0～100，隨機生成轉發(fā)延遲矩陣，轉發(fā)延遲范圍控制在51～100，假設所有節(jié)點的最大服務上限均相同，并且要求初始狀態(tài)時，節(jié)點所有服務的請求到達率之和小于服務器最大服務上限．系統(tǒng)每運行1次稱為1次運行實例．1次運行實例包括隨機生成1次服務請求矩陣，并分別通過BND算法和NBND算法求解服務部署和請求轉發(fā)方案．

圖3 部署規(guī)模對平均轉發(fā)延遲開銷的影響

模擬實驗分別比較了兩種啟發(fā)式算法在求解SMSPM問題時的服務部署規(guī)模、平均轉發(fā)延遲開銷變化和算法復雜度變化．由于算法是從所有節(jié)點部署的所有服務開始的，當每次減少服務部署規(guī)模時，平均轉發(fā)延遲開銷與服務部署規(guī)模減少量的變化情況如圖3所示．隨著服務部署規(guī)模減少量的增大，請求轉發(fā)延遲的開銷不斷增加．算法開始時，BND算法和NBND算法的平均轉發(fā)開銷隨著服務部署規(guī)模的減少而相同增加轉發(fā)延遲，但到達一定程度時，由于BND算法的回退步驟將之前的轉發(fā)請求重新調(diào)整，因此，BND算法的平均轉發(fā)開銷比NBND算法的轉發(fā)開銷增加速度慢，在達到目標平均轉發(fā)開銷時，BND算法的規(guī)模減少量更大，即BND算法使得服務部署規(guī)模更?。畧D4給出了兩種算法的循環(huán)次數(shù)對比，BND算法的回退算法更加復雜，隨著服務部署規(guī)模的減小，其循環(huán)次數(shù)的增加越來越快．文中運行100次運行實例，將兩種算法的服務部署規(guī)模進行了概率統(tǒng)計，概率密度如圖5所示．BND算法的平均服務部署規(guī)模為246，NBND算法的平均服務部署規(guī)模為287，兩種算法分別將服務部署規(guī)模降低了59%和52.2%．

圖4 計算復雜度對比圖5 服務部署規(guī)模概率密度分布

4 結 束 語

研究了覆蓋網(wǎng)絡中多服務靜態(tài)部署問題．在服務部署過程中考慮系統(tǒng)平均轉發(fā)時間限制和服務節(jié)點的最大服務規(guī)模限制，定義了一種更加全面的問題模型——SMSPM，證明了SMSPM問題屬于NP完全問題．給出了兩種貪婪啟發(fā)式算法BND和NBND，通過兩種算法分別對SMSPM問題進行求解，并分析其時間復雜度．通過仿真，驗證了SMSPM模型的有效性，BND和NBND兩種算法將服務部署規(guī)模分別降低了59%和52.2%．對于NP完全問題，有多種近似算法，文中給出的啟發(fā)式算法復雜度較高．接下來的研究工作是設計更加高效的近似算法．

[1] 尹浩, 袁小群, 林闖, 等. 內(nèi)容網(wǎng)絡服務節(jié)點部署理論綜述[J]. 計算機學報, 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]. 太原理工大學學報, 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] 陳香蘭, 李曦, 龔育昌. 服務組合中一種靜態(tài)基礎服務部署研究[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ǎng)絡資源動態(tài)分配模型[J]. 計算機學報, 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.