覆蓋網絡中多服務靜態部署算法

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

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

隨著網絡和通信技術的進步和發展，互聯網上出現了一大批新型網絡應用，如網絡會議、網絡電視、社交網絡等，相比傳統的網頁沖浪、文件傳輸等應用，新型應用的特點是應用服務器與用戶的交互性更強，內容數據容量更大，內容的實時性要求更高．但現有的網絡基礎架構采用簡單的端到端的設計原則，各路由節點單純實現數據包的存儲和轉發，雖然在一定程度上這種簡單的設計原則健壯性高、擴展性好、易于實現，但是越來越不能滿足當前新型業務的發展需求．

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

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

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

1 多服務靜態部署模型

1.1 部署模型描述

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

(1)

(2)

(3)

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

(7)

整個系統的服務部署規模為各節點服務規模之和，可表示為

(8)

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

1.2 資源限制

網絡應用服務系統中響應時間是用戶服務質量最重要的參數．服務響應時間通常包括通信延遲和服務處理延遲，當服務系統存在請求轉發時，服務響應時間還包括請求轉發延遲，這里重點研究請求轉發延遲．假設任意兩個服務節點間的通信延遲用轉發延遲矩陣表示為

(9)

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

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

(10)

下面研究在平均請求轉發時間滿足服務質量要求時，如何使服務部署規模最小化．假設服務系統的平均請求轉發延遲滿足

(11)

其中，T為服務質量要求的最大請求轉發延遲．

(12)

1.3 問題描述

綜合以上定義，在請求轉發延遲限制在一定范圍之內，同時滿足服務器的并發上限要求和最小化服務部署規模時，可以定義覆蓋網絡中的多服務靜態部署問題模型(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表示服務器所屬的服務節點，o表示服務器所能提供的服務．每個用戶節點有兩個屬性分別為i和k，i節點是該用戶轉發開銷為0的服務節點，k代表該用戶請求的服務類型，將用戶轉發到服務節點時，其轉發開銷為．當i=l且k=o時，轉發開銷為0；當k=o且i≠l時，轉發開銷為ti，j；當k≠o時，轉發開銷為∞．每個服務節點的請求上限為．假設Tm是將所有用戶(即請求)指派給服務節點后的平均轉發延遲開銷，驗證SMSPM問題是NP完全問題即是在給定的指派中，是否存在平均轉發延遲開銷為Tm的方案．假設A是“非確定性圖靈機”，A的輸入為n個服務器構成的集合Sj，m個用戶構成的集合U和總開銷T的猜測函數f．非確定性圖靈機的工作包括兩步：A非確定性猜測可能的指派方案．函數f確認猜測的指派方案的平均轉發延遲開銷是否為Tm，若驗證成功，則停止；否則，繼續．因此，至少在給定一個用戶到服務器的指派，驗證該指派方案的平均轉發延遲開銷是否為Tm，即為將所有轉發延遲開銷相加后取平均，時間復雜度為O(n)，驗證過程可以在多項式時間內確定．一旦用戶指派方案確定后，服務的部署問題隨之解決．因此，SMSPM問題是NP問題．

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

2 啟發式算法

2.1 算法思想

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

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

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

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

圖1 請求分級轉發

圖2 請求轉發重分配

2.2 算法復雜度分析

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

3 實驗仿真分析

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

圖3 部署規模對平均轉發延遲開銷的影響

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

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

4 結 束 語

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

[1] 尹浩, 袁小群, 林闖, 等. 內容網絡服務節點部署理論綜述[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] 陳香蘭, 李曦, 龔育昌. 服務組合中一種靜態基礎服務部署研究[J]. 小型微型計算機系統, 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] 史佩昌, 王懷民, 尹剛, 等. 云服務傳遞網絡資源動態分配模型[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.