Bellman動態規劃的服務恢復方法

徐俊波，王慧強，馮光升，呂宏武，田蘇梅

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

隨著網絡技術的發展和業務種類的擴展，組合服務已經代替了傳統的客戶/服務器模式，成為網絡服務的主體［1-2］.而系統復雜性的增長，使服務路徑上節點的退出和失效日益頻繁和密集，如何使中斷節點快速、有效地恢復，不中斷服務執行過程，盡可能減少服務失敗給用戶帶來的干擾，已成為一項迫切解決的問題［3-4］.但是當前應急響應與災難恢復、系統恢復以及數據庫恢復的相關研究大部分是基于本地或異地的數據備份與恢復技術［5-7］，應急響應決策主要著眼于備份數據的優選與恢復.而服務恢復的主要對象是服務，與傳統方法保證數據的完整和一致性的任務有所不同.為了完成復雜的動態分布式系統的服務組合恢復問題［8-9］，本文提出一種基于Bellman［10］動態規劃的服務恢復方法，以解決服務恢復中面臨的問題.

1 服務恢復路徑的規劃

針對服務的復雜性，使用服務組合思想來支持服務恢復，通過采用Bellman動態規劃算法通過將整個問題分解成一系列更小問題的集合來籌劃恢復策略.

1.1 服務路徑選擇

本文所提出的服務路徑選擇方法就是在當前的所有服務路徑中選擇一條最優的服務路徑用來恢復失效的服務.

通過分析現有各種類型的網絡服務模型，設定一個服務過程可以被依次轉化成N種子服務過程.服務的實現過程用關鍵服務路徑來代表，為了方便說明，給出以下定義:

定義1:元服務是服務分解而成的最小事務，它是能夠向用戶提供的最細粒度的功能，如服務器的CPU、內存、硬盤等.

定義2:組件服務由一個或多個元服務按照結合邏輯組合而成，它提供一個專門的功能，是復雜服務的組成部分，如DNS服務、FTP服務等.

定義3:組合服務由一個或多個組件服務按邏輯組合而成，提供一個增值服務，如網絡辦公系統或網站服務等.

定義4:恢復點設置就是規劃實現服務恢復的最優服務路徑.

對于一個給定的服務F，它的服務路徑是“F1→F2，F3→F4→F5”.F1到F5代表了子服務的類型，而“，”和“→”分別是功能相似的標志和模型的序列.

本文所研究的服務組合是單播形式的，即服務組件是以順序方式連接并在服務路徑上只有一個接收者.其他形式的組合方式，可通過一些方法轉化為順序方式.組合服務S表示為

式中:sd是接受者，n是服務組件的數目或服務路徑的跳數.si代表組合服務中的第i個服務組件，它唯一的標識組合服務需求的功能.

在整個網絡中，用Vi表示能提供服務si的節點集合.服務網絡定義為GS(V，E)，其中節點集合V和有向邊集合E分別為

顯然，vn+1=vd為目的節點.

在服務網絡GS中，組合服務S的服務路徑表示為

式中:vi∈Vi，vs和vd分別表示虛擬的源和目的節點.如果不考慮服務路徑的QoS，服務網絡GS中從虛擬的源節點vs到接受者vd的任何簡單路徑都是有效的服務路徑.這些路徑構成了一個抽象的服務網絡圖.

1.2 從決策問題映射到規劃問題

服務恢復決策的問題在于如何將它轉化成一個多級決策問題，為了促進對正式的描述和代理的認識，將決策問題映射成人工智能中的規劃問題.若采用關鍵服務路徑來描述一個服務的恢復，組件服務在規劃中代表行為，被恢復服務的等級代表狀態，這樣一個復雜服務的恢復就轉化成了一系列分布式資源的結合.

服務結點連接圖是按網絡拓撲中服務結點的連接而成的，如圖1所示.R代表被破壞的服務結點，當它被客戶申請服務時，該要求將被傳到路徑選擇處進行處理，并在恢復后對客戶做出響應.這樣，即使部分系統被破壞了，客戶仍能及時的接收到響應，同時，R服務結點恢復的實現對客戶來說是透明的.在圖1中的節點代表信息系統中的服務提供者，邊表示服務提供者之間的連接，權值能按使用者的需要去確定.在一個服務結點連接圖中，被破壞的結點是源結點，同時它也是目標結點.“→”指示聯系的存在且其指向是按照子服務的過程序列而定的.

圖1 服務節點連接圖Fig.1 Connection graph of service nodes

一個服務結點連接圖是按如下方式構造的:

1)如果對每一個特定需求的服務類型，如果在服務池中都有1個或多個可利用的服務結點，那么就將每2個結點之間進行連接，從而來構造服務結點連接圖;

2)如果對于所需的服務類型沒有相應的服務結點，那么從需求中刪除這種服務類型并且使用服務降級技術，然后執行步驟1);

3)對于某些要求的服務類型，如果沒有可利用的服務結點(無空閑資源)，那么比較當前需求與執行中占用相同資源的各服務優先權，如果當前需求的優先權更高，則將考慮剝奪低優先權服務的資源，并且按照步驟1)連接，否則，繼續等待直到有足夠的可用資源.

如果在關鍵服務路徑上有一種合作模式，這種合作模式被視為一種復雜的組件服務，如圖2所示.此時，所有的連接都被要求應在其前后結點與合作結點之間.

由于效能函數用來表示各階段成本的總和，因此為了能夠衡量服務恢復的代價，本文采用帶權重的效能函數來計算服務恢復代價:

式中:Tc代表服務器本身的性能代價，包含CPU利用率PCPU、內存利用率PRAM等指標;Ts代表服務本身的代價，包含對服務響應時間的度量(服務響應時間tser，預設響應時間tthr)以及服務響應率SR等，則Tc、Ts計算如下:

式中:［］代表求取上確界，預設響應時間與系統和服務相關，一般是服務相應時間的平均值.進而可以得到W，W是一組比值加和且無量綱.

對一個給定的服務，按照步驟1)構造一個服務結點連接圖，按照步驟2)定義一個效能函數，然后恢復決策問題就被轉化成了規劃問題.

圖2 復雜組件服務Fig.2 Complex components services

2 恢復算法

Bellman動態規劃算法可以用來解決上述規劃問題.服務恢復整體上的最優戰略可以通過不帶回滾的遞歸來實現，可以保證在規劃的任何階段都不會有不適合的決策出現，具本步驟如下:

1)選擇能提供與所需服務類型相關聯的服務結點.

2)按照網絡拓撲和關鍵服務路徑，繪制需求的服務結點連接圖.

3)按照服務質量參數定義效能函數，計算階段成本，將在步驟2)中的服務結點連接圖轉化成加權的服務結點連接圖.

4)檢查帶權的服務結點連接圖的連接，判斷它是否能從R連接到R，如果能則轉到步驟5)，如果不能則采用服務降級技術并繼續下一過程.

5)使用Bellman動態規劃實現最優響應路徑選擇，按照問題的規模選擇動態遷移或重建技術.

假設服務結點連接圖和相應的權值已經實現，S和R分別代表服務結點連接圖的源和目的結點，并作為函數的輸入.在Bellman動態規劃被遞歸的用于解決這個圖以后，從S到R的最優路徑和它的成本評估將被作為輸出.Bellman決策函數(G，W，S，R)返回D和d.算法偽碼描述如下:

輸入:G是一個服務結點連接圖，G=G(V，E); W是權值，W=(Wij);S是圖G的源結點;R是圖G的目的結點.

輸出:D是從S到R的最優路徑;d是從S到R最優路徑的估計成本.

局部變量:D［v］是v的后續路徑;d［v］是從v到R最優路徑的成本評估。

3 服務故障恢復實驗與分析

本實驗構建一個小型的分布式可控信息系統環境，對服務恢復系統功能及服務恢復策略進行測試.如圖3所示.構建的信息系統的角色包括服務請求者、服務提供者、服務管理者，分別對應客戶端、應局域網內的所有服務器、服務故障恢復系統.在客戶端A上安裝服務故障恢復系統，服務故障恢復系統客戶端運行在提供服務的服務器上，負責服務器性能和服務參數的采集并實時傳送回到服務故障恢復系統的服務器端;服務故障恢復系統服務器端運行在服務請求者主機上，對服務故障恢復系統客戶端傳回的信息進行處理分析，計算當前服務器上運行服務的服務響應時間及服務響應率，并對服務器性能參數和服務參數綜合處理以便確定服務狀態等級，依次決定是否采取服務恢復技術.

圖3 實驗網絡示意Fig.3 Experiment network

假設系統服務等級為S，S∈N且0≤S≤100，也就是max{S}=100，min{S}=0;假設在100≥S≥90，90＞S≥70，70＞S≥50，50＞S≥30，30＞S≥0時分別產生不同的服務狀態預警，在100≥S≥90情況下，服務時效.此時，服務故障恢復系統工作流程圖如圖4所示.

圖4 服務故障恢復系統工作流程Fig.4 Work flow chart of service recovery system

3.1 性能對比實驗

實驗內容為基于TCP服務對系統進行測試，具體的TCP服務為C/S結構的聊天室.對正在提供服務的服務器進行攻擊使得服務失效，應用服務故障恢復系統對服務請求者透明恢復服務.實驗步驟如下所示:

1)將服務故障恢復系統的服務器端布置在聊天室客戶端A主機上，將服務故障恢復系統的客戶端分別安裝在聊天室的服務器端服務器1、2、3主機上.

2)開啟系統服務器端和系統客戶端，采集所有聊天室服務器的性能信息，測試系統的所有功能實現是否正常.

3)聊天室默認服務器端為服務器2，當將該服務器關閉以致服務失效，此時分別采用服務故障恢復系統提供的服務路徑和傳統上的服務備份路徑［6］2種方法進行服務恢復，對比服務器性能、服務質量和服務恢復時間.

圖5中左側為應用Bellman動態規劃恢復策略選出的服務器1，右側是應用服務備份路徑方法選出的服務器3.明顯看出服務器一的CPU利用率和內存利用率低于服務器3，峰值降低了20%以上.而且流量曲線中服務器3流入流量很大流出流量卻很小，說明此時該服務器的服務請求者非常多但是服務器應答處理卻很低，表明服務器很繁忙且效率很低，但是服務器1的流入流量很少而且對服務請求者的應答處理卻很高.服務的性能信息對比，如圖6所示.左側為應用Bellman動態規劃恢復策略選出的服務器1，右側是應用服務備份路徑方法選出的服務器3.由圖看見服務響應率提高了30%左右，而服務響應時間的平均值明顯降低.

由此可以看出此時服務器一的性能要比服務器三更加高效.

圖5 服務器性能對比Fig.5 Server performance comparison

圖6 服務性能信息Fig.6 Information of service performance

3.2 恢復路徑選擇實驗

利用MATLAB仿真郵件服務網絡的拓撲結構，并對該拓撲結構應用Bellman動態規劃算法實現最優服務恢復路徑的選擇及應用服務備份路徑方法選出服務路徑.對于目前的網絡拓撲結構，選擇如下測試場景.服務提供者個數:10，服務類型:4種，服務節點個數:12.利用MATLAB仿真該可控信息系統網絡拓撲結構，如圖7所示.節點1和12分別代表服務初始節點、完成服務的目標節點.節點2和3代表可執行第1種服務的服務器;節點4、5和6代表可執行第2種服務的服務器;節點7、8和9代表可執行第3種服務的服務器;節點10和11代表可執行第4種服務的服務器.根據圖7，郵件服務S的一條服務路徑為S={1→2→5→7→10→12}.

圖7 網絡拓撲圖Fig.7 Network topology

使用1.2節的效用函數作為評價標準，其中令w1和w2權重相等，即w1=0.5，w2=0.5;Tc代表服務器本身的性能代價;Ts代表郵件服務的代價，如傳輸時間t，服務響應率SR等，Ts=t+SR.相關參數如表1所示.規定傳輸時間為1 s，規定計算所得W值越小服務等級越高，W值用來表示邊的權值.

實驗步驟如下所示:

1)針對設計的網絡拓撲選出當前最優的服務路徑，在針對該服務路徑中某一鏈路進行攻擊.

2)對攻擊后的網絡拓撲應用Bellman動態規劃算法，選出最優服務恢復路徑.

3)對被攻擊的網絡拓撲應用備用路徑恢復算法，選出最優服務恢復路徑.

表1 評價指標參數Table 1 Evaluation parameter

對于正常運行的服務S來說，正在提供服務S的路徑當前一定是最優的，如圖8所示.其服務路徑為:S=S{1→2→4→7→11→12}，權值為13.

這時如果對服務路徑上的2→4段進行攻擊，服務S就會失效，如圖9所示.

圖8 正常運行下的服務路徑Fig.8 Service path under normal running

圖9 受到攻擊后的服務路徑Fig.9 Service path after attack

此時如果采用服務備份路徑恢復的方法，那么恢復后的服務路徑為:S=S{1→2→5→7→11→12}，權值為17，如圖10所示.而如果采用Bellman動態規劃算法作為服務恢復策略，此時成功恢復后的服務路徑為S=S{1→3→4→7→11→12}，權值為13，如圖11所示.

圖10 基于服務備份路徑恢復算法的服務路徑選擇Fig.10 Service route choice based on backup path restoration algorithm

圖11 基于Bellman動態規劃算法的服務路徑選擇Fig.11 Service route choice based on Bellman dynamic programming

利用理論分析的方法對Bellman動態規劃服務恢復策略算法進行復雜度分析.所給問題的規模描述為:給定一個分布式信息系統中，恢復一個失效的服務，假設這個服務平均包含M種類型的子服務，提供一定功能類型的有效服務的服務節點數N.

這個策略算法的空間復雜度和時間復雜度主要包括這2個部分:一個是邏輯層網絡自組織過程中所花費的空間和時間成本，該成本為O(MN2);另一部分成本來自于完成Bellman動態規劃算法過程所花費的成本O(MN2)，所以整個算法的復雜度就約為O(2MN2).而傳統的備份服務路徑屬于盲目的搜索，復雜度大約為O(NM).顯而易見，Bellman動態恢復服務恢復策略更有效，同時，隨著Internet和網絡服務的發展，服務的子服務集成規模將迅速的增長，更高的M和N值將使得該算法的重要性有效的提高.策略技術性能對比如圖12所示.

圖12 策略技術性能對比Fig.12 Strategic technology performance comparison

仿真實驗體現出了算法的合理性和有效性.當采用備份服務恢復路徑方法時，成功恢復后的路徑權值總和為17，但是采用Bellman動態規劃算法的服務恢復策略，服務恢復成功的服務路徑權值為13，相較而言，該算法產生的路徑是最優的而服務恢復成功率也是最高的.

4 結束語

本文提出了一種基于Bellman動態規劃的服務恢復方法.通過與傳統的服務備份路徑方法對比，實驗結果顯示:1)在性能方面本文方法的CPU負載、內存利用率和輸入輸出均有較大改善;2)在恢復路徑選區方面選擇的路徑權值更小，開銷得到了有效控制，且時間復雜度由原有指數時間降為多項式時間.下一步將結合恢復過程的特點對Bellman動態規劃算法進一步改進，以提高求解的效率.

［1］代鈺，楊雷，張斌，等.支持組合服務選取的QoS模型及優化求解［J］.計算機學報，2006(7):1167-1178.

DAI Yu，YANG Lei，ZHANG Bin，et al.QoS for composite web services and optimizing［J］.Chinese Journal of Computers，2006，29(7):1167-1178.

［2］葉世陽，魏峻，李磊，等.支持服務關聯的組合服務選擇方法研究［J］.計算機學報，2008(8):1383-1397.

YE Shiyang，WEI Jun，LI Lei，et al.Service-correlation aware service selection for composite service［J］.Chinese Journal of Computers，2008，31(8):1383-1397.

［3］VAN RENESSE R，MINSKY Y，HAYDEN M.A gossipstyle failure detection service［C］//The 2009 IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing.NY，USA.2009:55-70.

［4］MOVSICHOFF B，LAGOA C，CHE H.End-to-end optimal algorithms for integrated QoS，traffic engineering，and failure recovery［J］.IEEE/ACM Transactions on Networking (TON)，2007，15(4):813-823.

［5］李旭，謝長生，楊靖，等.一種改進的塊級連續數據保護機制［J］.計算機研究與發展，2009(5):762-769.

LI Xu，XIE Changsheng，YANG Jing，et al.An improved block-level continuous data protection mechanism［J］.Journal of Computer Research and Development，2009，46(5): 762-769.

［6］REDMAN W，BUGBEE M，DOBBS S，et al.A robust high speed serial PHY architecture with feed-forward correction clock and data recovery［J］.IEEE Journal of Solid-State Circuits，2009，44(7):1914-1926.

［7］BEUTEL J，GRUBER S，HASLER A，et al.PermaDAQ:a scientific instrument for precision sensing and data recovery in environmental extremes［C］//The 2009 International Conference on Information Processing in Sensor Networks.San Francisco，USA.2009:265-276.

［8］JIANG S，XUE Y，SCHMIDT C.Minimum disruption service composition and recovery in mobile ad hoc networks［J］.Computer Network，2009，53(10):1649-1665.

［9］CHANG D W，HSIEH C E，CHEN Y P，et al.Virtual machine support for zero-loss internet service recovery and upgrade［J］.Software-Practice＆ Experience，2007，37 (13):1349-1376.

［10］ANTOS A，SZEPESVARI C，MUNOS R.Learning nearoptimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path［J］.Machine Learning，2008，71(1):89-129.