Bellman動(dòng)態(tài)規(guī)劃的服務(wù)恢復(fù)方法

徐俊波，王慧強(qiáng)，馮光升，呂宏武，田蘇梅

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

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

1 服務(wù)恢復(fù)路徑的規(guī)劃

針對(duì)服務(wù)的復(fù)雜性，使用服務(wù)組合思想來(lái)支持服務(wù)恢復(fù)，通過(guò)采用Bellman動(dòng)態(tài)規(guī)劃算法通過(guò)將整個(gè)問(wèn)題分解成一系列更小問(wèn)題的集合來(lái)籌劃恢復(fù)策略.

1.1 服務(wù)路徑選擇

本文所提出的服務(wù)路徑選擇方法就是在當(dāng)前的所有服務(wù)路徑中選擇一條最優(yōu)的服務(wù)路徑用來(lái)恢復(fù)失效的服務(wù).

通過(guò)分析現(xiàn)有各種類型的網(wǎng)絡(luò)服務(wù)模型，設(shè)定一個(gè)服務(wù)過(guò)程可以被依次轉(zhuǎn)化成N種子服務(wù)過(guò)程.服務(wù)的實(shí)現(xiàn)過(guò)程用關(guān)鍵服務(wù)路徑來(lái)代表，為了方便說(shuō)明，給出以下定義:

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

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

定義3:組合服務(wù)由一個(gè)或多個(gè)組件服務(wù)按邏輯組合而成，提供一個(gè)增值服務(wù)，如網(wǎng)絡(luò)辦公系統(tǒng)或網(wǎng)站服務(wù)等.

定義4:恢復(fù)點(diǎn)設(shè)置就是規(guī)劃實(shí)現(xiàn)服務(wù)恢復(fù)的最優(yōu)服務(wù)路徑.

對(duì)于一個(gè)給定的服務(wù)F，它的服務(wù)路徑是“F1→F2，F(xiàn)3→F4→F5”.F1到F5代表了子服務(wù)的類型，而“，”和“→”分別是功能相似的標(biāo)志和模型的序列.

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

式中:sd是接受者，n是服務(wù)組件的數(shù)目或服務(wù)路徑的跳數(shù).si代表組合服務(wù)中的第i個(gè)服務(wù)組件，它唯一的標(biāo)識(shí)組合服務(wù)需求的功能.

在整個(gè)網(wǎng)絡(luò)中，用Vi表示能提供服務(wù)si的節(jié)點(diǎn)集合.服務(wù)網(wǎng)絡(luò)定義為GS(V，E)，其中節(jié)點(diǎn)集合V和有向邊集合E分別為

顯然，vn+1=vd為目的節(jié)點(diǎn).

在服務(wù)網(wǎng)絡(luò)GS中，組合服務(wù)S的服務(wù)路徑表示為

式中:vi∈Vi，vs和vd分別表示虛擬的源和目的節(jié)點(diǎn).如果不考慮服務(wù)路徑的QoS，服務(wù)網(wǎng)絡(luò)GS中從虛擬的源節(jié)點(diǎn)vs到接受者vd的任何簡(jiǎn)單路徑都是有效的服務(wù)路徑.這些路徑構(gòu)成了一個(gè)抽象的服務(wù)網(wǎng)絡(luò)圖.

1.2 從決策問(wèn)題映射到規(guī)劃問(wèn)題

服務(wù)恢復(fù)決策的問(wèn)題在于如何將它轉(zhuǎn)化成一個(gè)多級(jí)決策問(wèn)題，為了促進(jìn)對(duì)正式的描述和代理的認(rèn)識(shí)，將決策問(wèn)題映射成人工智能中的規(guī)劃問(wèn)題.若采用關(guān)鍵服務(wù)路徑來(lái)描述一個(gè)服務(wù)的恢復(fù)，組件服務(wù)在規(guī)劃中代表行為，被恢復(fù)服務(wù)的等級(jí)代表狀態(tài)，這樣一個(gè)復(fù)雜服務(wù)的恢復(fù)就轉(zhuǎn)化成了一系列分布式資源的結(jié)合.

服務(wù)結(jié)點(diǎn)連接圖是按網(wǎng)絡(luò)拓?fù)渲蟹?wù)結(jié)點(diǎn)的連接而成的，如圖1所示.R代表被破壞的服務(wù)結(jié)點(diǎn)，當(dāng)它被客戶申請(qǐng)服務(wù)時(shí)，該要求將被傳到路徑選擇處進(jìn)行處理，并在恢復(fù)后對(duì)客戶做出響應(yīng).這樣，即使部分系統(tǒng)被破壞了，客戶仍能及時(shí)的接收到響應(yīng)，同時(shí)，R服務(wù)結(jié)點(diǎn)恢復(fù)的實(shí)現(xiàn)對(duì)客戶來(lái)說(shuō)是透明的.在圖1中的節(jié)點(diǎn)代表信息系統(tǒng)中的服務(wù)提供者，邊表示服務(wù)提供者之間的連接，權(quán)值能按使用者的需要去確定.在一個(gè)服務(wù)結(jié)點(diǎn)連接圖中，被破壞的結(jié)點(diǎn)是源結(jié)點(diǎn)，同時(shí)它也是目標(biāo)結(jié)點(diǎn).“→”指示聯(lián)系的存在且其指向是按照子服務(wù)的過(guò)程序列而定的.

圖1 服務(wù)節(jié)點(diǎn)連接圖Fig.1 Connection graph of service nodes

一個(gè)服務(wù)結(jié)點(diǎn)連接圖是按如下方式構(gòu)造的:

1)如果對(duì)每一個(gè)特定需求的服務(wù)類型，如果在服務(wù)池中都有1個(gè)或多個(gè)可利用的服務(wù)結(jié)點(diǎn)，那么就將每2個(gè)結(jié)點(diǎn)之間進(jìn)行連接，從而來(lái)構(gòu)造服務(wù)結(jié)點(diǎn)連接圖;

2)如果對(duì)于所需的服務(wù)類型沒有相應(yīng)的服務(wù)結(jié)點(diǎn)，那么從需求中刪除這種服務(wù)類型并且使用服務(wù)降級(jí)技術(shù)，然后執(zhí)行步驟1);

3)對(duì)于某些要求的服務(wù)類型，如果沒有可利用的服務(wù)結(jié)點(diǎn)(無(wú)空閑資源)，那么比較當(dāng)前需求與執(zhí)行中占用相同資源的各服務(wù)優(yōu)先權(quán)，如果當(dāng)前需求的優(yōu)先權(quán)更高，則將考慮剝奪低優(yōu)先權(quán)服務(wù)的資源，并且按照步驟1)連接，否則，繼續(xù)等待直到有足夠的可用資源.

如果在關(guān)鍵服務(wù)路徑上有一種合作模式，這種合作模式被視為一種復(fù)雜的組件服務(wù)，如圖2所示.此時(shí)，所有的連接都被要求應(yīng)在其前后結(jié)點(diǎn)與合作結(jié)點(diǎn)之間.

由于效能函數(shù)用來(lái)表示各階段成本的總和，因此為了能夠衡量服務(wù)恢復(fù)的代價(jià)，本文采用帶權(quán)重的效能函數(shù)來(lái)計(jì)算服務(wù)恢復(fù)代價(jià):

式中:Tc代表服務(wù)器本身的性能代價(jià)，包含CPU利用率PCPU、內(nèi)存利用率PRAM等指標(biāo);Ts代表服務(wù)本身的代價(jià)，包含對(duì)服務(wù)響應(yīng)時(shí)間的度量(服務(wù)響應(yīng)時(shí)間tser，預(yù)設(shè)響應(yīng)時(shí)間tthr)以及服務(wù)響應(yīng)率SR等，則Tc、Ts計(jì)算如下:

式中:［］代表求取上確界，預(yù)設(shè)響應(yīng)時(shí)間與系統(tǒng)和服務(wù)相關(guān)，一般是服務(wù)相應(yīng)時(shí)間的平均值.進(jìn)而可以得到W，W是一組比值加和且無(wú)量綱.

對(duì)一個(gè)給定的服務(wù)，按照步驟1)構(gòu)造一個(gè)服務(wù)結(jié)點(diǎn)連接圖，按照步驟2)定義一個(gè)效能函數(shù)，然后恢復(fù)決策問(wèn)題就被轉(zhuǎn)化成了規(guī)劃問(wèn)題.

圖2 復(fù)雜組件服務(wù)Fig.2 Complex components services

2 恢復(fù)算法

Bellman動(dòng)態(tài)規(guī)劃算法可以用來(lái)解決上述規(guī)劃問(wèn)題.服務(wù)恢復(fù)整體上的最優(yōu)戰(zhàn)略可以通過(guò)不帶回滾的遞歸來(lái)實(shí)現(xiàn)，可以保證在規(guī)劃的任何階段都不會(huì)有不適合的決策出現(xiàn)，具本步驟如下:

1)選擇能提供與所需服務(wù)類型相關(guān)聯(lián)的服務(wù)結(jié)點(diǎn).

2)按照網(wǎng)絡(luò)拓?fù)浜完P(guān)鍵服務(wù)路徑，繪制需求的服務(wù)結(jié)點(diǎn)連接圖.

3)按照服務(wù)質(zhì)量參數(shù)定義效能函數(shù)，計(jì)算階段成本，將在步驟2)中的服務(wù)結(jié)點(diǎn)連接圖轉(zhuǎn)化成加權(quán)的服務(wù)結(jié)點(diǎn)連接圖.

4)檢查帶權(quán)的服務(wù)結(jié)點(diǎn)連接圖的連接，判斷它是否能從R連接到R，如果能則轉(zhuǎn)到步驟5)，如果不能則采用服務(wù)降級(jí)技術(shù)并繼續(xù)下一過(guò)程.

5)使用Bellman動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)響應(yīng)路徑選擇，按照問(wèn)題的規(guī)模選擇動(dòng)態(tài)遷移或重建技術(shù).

假設(shè)服務(wù)結(jié)點(diǎn)連接圖和相應(yīng)的權(quán)值已經(jīng)實(shí)現(xiàn)，S和R分別代表服務(wù)結(jié)點(diǎn)連接圖的源和目的結(jié)點(diǎn)，并作為函數(shù)的輸入.在Bellman動(dòng)態(tài)規(guī)劃被遞歸的用于解決這個(gè)圖以后，從S到R的最優(yōu)路徑和它的成本評(píng)估將被作為輸出.Bellman決策函數(shù)(G，W，S，R)返回D和d.算法偽碼描述如下:

輸入:G是一個(gè)服務(wù)結(jié)點(diǎn)連接圖，G=G(V，E); W是權(quán)值，W=(Wij);S是圖G的源結(jié)點(diǎn);R是圖G的目的結(jié)點(diǎn).

輸出:D是從S到R的最優(yōu)路徑;d是從S到R最優(yōu)路徑的估計(jì)成本.

局部變量:D［v］是v的后續(xù)路徑;d［v］是從v到R最優(yōu)路徑的成本評(píng)估。

3 服務(wù)故障恢復(fù)實(shí)驗(yàn)與分析

本實(shí)驗(yàn)構(gòu)建一個(gè)小型的分布式可控信息系統(tǒng)環(huán)境，對(duì)服務(wù)恢復(fù)系統(tǒng)功能及服務(wù)恢復(fù)策略進(jìn)行測(cè)試.如圖3所示.構(gòu)建的信息系統(tǒng)的角色包括服務(wù)請(qǐng)求者、服務(wù)提供者、服務(wù)管理者，分別對(duì)應(yīng)客戶端、應(yīng)局域網(wǎng)內(nèi)的所有服務(wù)器、服務(wù)故障恢復(fù)系統(tǒng).在客戶端A上安裝服務(wù)故障恢復(fù)系統(tǒng)，服務(wù)故障恢復(fù)系統(tǒng)客戶端運(yùn)行在提供服務(wù)的服務(wù)器上，負(fù)責(zé)服務(wù)器性能和服務(wù)參數(shù)的采集并實(shí)時(shí)傳送回到服務(wù)故障恢復(fù)系統(tǒng)的服務(wù)器端;服務(wù)故障恢復(fù)系統(tǒng)服務(wù)器端運(yùn)行在服務(wù)請(qǐng)求者主機(jī)上，對(duì)服務(wù)故障恢復(fù)系統(tǒng)客戶端傳回的信息進(jìn)行處理分析，計(jì)算當(dāng)前服務(wù)器上運(yùn)行服務(wù)的服務(wù)響應(yīng)時(shí)間及服務(wù)響應(yīng)率，并對(duì)服務(wù)器性能參數(shù)和服務(wù)參數(shù)綜合處理以便確定服務(wù)狀態(tài)等級(jí)，依次決定是否采取服務(wù)恢復(fù)技術(shù).

圖3 實(shí)驗(yàn)網(wǎng)絡(luò)示意Fig.3 Experiment network

假設(shè)系統(tǒng)服務(wù)等級(jí)為S，S∈N且0≤S≤100，也就是max{S}=100，min{S}=0;假設(shè)在100≥S≥90，90＞S≥70，70＞S≥50，50＞S≥30，30＞S≥0時(shí)分別產(chǎn)生不同的服務(wù)狀態(tài)預(yù)警，在100≥S≥90情況下，服務(wù)時(shí)效.此時(shí)，服務(wù)故障恢復(fù)系統(tǒng)工作流程圖如圖4所示.

圖4 服務(wù)故障恢復(fù)系統(tǒng)工作流程Fig.4 Work flow chart of service recovery system

3.1 性能對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)內(nèi)容為基于TCP服務(wù)對(duì)系統(tǒng)進(jìn)行測(cè)試，具體的TCP服務(wù)為C/S結(jié)構(gòu)的聊天室.對(duì)正在提供服務(wù)的服務(wù)器進(jìn)行攻擊使得服務(wù)失效，應(yīng)用服務(wù)故障恢復(fù)系統(tǒng)對(duì)服務(wù)請(qǐng)求者透明恢復(fù)服務(wù).實(shí)驗(yàn)步驟如下所示:

1)將服務(wù)故障恢復(fù)系統(tǒng)的服務(wù)器端布置在聊天室客戶端A主機(jī)上，將服務(wù)故障恢復(fù)系統(tǒng)的客戶端分別安裝在聊天室的服務(wù)器端服務(wù)器1、2、3主機(jī)上.

2)開啟系統(tǒng)服務(wù)器端和系統(tǒng)客戶端，采集所有聊天室服務(wù)器的性能信息，測(cè)試系統(tǒng)的所有功能實(shí)現(xiàn)是否正常.

3)聊天室默認(rèn)服務(wù)器端為服務(wù)器2，當(dāng)將該服務(wù)器關(guān)閉以致服務(wù)失效，此時(shí)分別采用服務(wù)故障恢復(fù)系統(tǒng)提供的服務(wù)路徑和傳統(tǒng)上的服務(wù)備份路徑［6］2種方法進(jìn)行服務(wù)恢復(fù)，對(duì)比服務(wù)器性能、服務(wù)質(zhì)量和服務(wù)恢復(fù)時(shí)間.

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

由此可以看出此時(shí)服務(wù)器一的性能要比服務(wù)器三更加高效.

圖5 服務(wù)器性能對(duì)比Fig.5 Server performance comparison

圖6 服務(wù)性能信息Fig.6 Information of service performance

3.2 恢復(fù)路徑選擇實(shí)驗(yàn)

利用MATLAB仿真郵件服務(wù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并對(duì)該拓?fù)浣Y(jié)構(gòu)應(yīng)用Bellman動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最優(yōu)服務(wù)恢復(fù)路徑的選擇及應(yīng)用服務(wù)備份路徑方法選出服務(wù)路徑.對(duì)于目前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，選擇如下測(cè)試場(chǎng)景.服務(wù)提供者個(gè)數(shù):10，服務(wù)類型:4種，服務(wù)節(jié)點(diǎn)個(gè)數(shù):12.利用MATLAB仿真該可控信息系統(tǒng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖7所示.節(jié)點(diǎn)1和12分別代表服務(wù)初始節(jié)點(diǎn)、完成服務(wù)的目標(biāo)節(jié)點(diǎn).節(jié)點(diǎn)2和3代表可執(zhí)行第1種服務(wù)的服務(wù)器;節(jié)點(diǎn)4、5和6代表可執(zhí)行第2種服務(wù)的服務(wù)器;節(jié)點(diǎn)7、8和9代表可執(zhí)行第3種服務(wù)的服務(wù)器;節(jié)點(diǎn)10和11代表可執(zhí)行第4種服務(wù)的服務(wù)器.根據(jù)圖7，郵件服務(wù)S的一條服務(wù)路徑為S={1→2→5→7→10→12}.

圖7 網(wǎng)絡(luò)拓?fù)鋱DFig.7 Network topology

使用1.2節(jié)的效用函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，其中令w1和w2權(quán)重相等，即w1=0.5，w2=0.5;Tc代表服務(wù)器本身的性能代價(jià);Ts代表郵件服務(wù)的代價(jià)，如傳輸時(shí)間t，服務(wù)響應(yīng)率SR等，Ts=t+SR.相關(guān)參數(shù)如表1所示.規(guī)定傳輸時(shí)間為1 s，規(guī)定計(jì)算所得W值越小服務(wù)等級(jí)越高，W值用來(lái)表示邊的權(quán)值.

實(shí)驗(yàn)步驟如下所示:

1)針對(duì)設(shè)計(jì)的網(wǎng)絡(luò)拓?fù)溥x出當(dāng)前最優(yōu)的服務(wù)路徑，在針對(duì)該服務(wù)路徑中某一鏈路進(jìn)行攻擊.

2)對(duì)攻擊后的網(wǎng)絡(luò)拓?fù)鋺?yīng)用Bellman動(dòng)態(tài)規(guī)劃算法，選出最優(yōu)服務(wù)恢復(fù)路徑.

3)對(duì)被攻擊的網(wǎng)絡(luò)拓?fù)鋺?yīng)用備用路徑恢復(fù)算法，選出最優(yōu)服務(wù)恢復(fù)路徑.

表1 評(píng)價(jià)指標(biāo)參數(shù)Table 1 Evaluation parameter

對(duì)于正常運(yùn)行的服務(wù)S來(lái)說(shuō)，正在提供服務(wù)S的路徑當(dāng)前一定是最優(yōu)的，如圖8所示.其服務(wù)路徑為:S=S{1→2→4→7→11→12}，權(quán)值為13.

這時(shí)如果對(duì)服務(wù)路徑上的2→4段進(jìn)行攻擊，服務(wù)S就會(huì)失效，如圖9所示.

圖8 正常運(yùn)行下的服務(wù)路徑Fig.8 Service path under normal running

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

此時(shí)如果采用服務(wù)備份路徑恢復(fù)的方法，那么恢復(fù)后的服務(wù)路徑為:S=S{1→2→5→7→11→12}，權(quán)值為17，如圖10所示.而如果采用Bellman動(dòng)態(tài)規(guī)劃算法作為服務(wù)恢復(fù)策略，此時(shí)成功恢復(fù)后的服務(wù)路徑為S=S{1→3→4→7→11→12}，權(quán)值為13，如圖11所示.

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

圖11 基于Bellman動(dòng)態(tài)規(guī)劃算法的服務(wù)路徑選擇Fig.11 Service route choice based on Bellman dynamic programming

利用理論分析的方法對(duì)Bellman動(dòng)態(tài)規(guī)劃服務(wù)恢復(fù)策略算法進(jìn)行復(fù)雜度分析.所給問(wèn)題的規(guī)模描述為:給定一個(gè)分布式信息系統(tǒng)中，恢復(fù)一個(gè)失效的服務(wù)，假設(shè)這個(gè)服務(wù)平均包含M種類型的子服務(wù)，提供一定功能類型的有效服務(wù)的服務(wù)節(jié)點(diǎn)數(shù)N.

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

圖12 策略技術(shù)性能對(duì)比Fig.12 Strategic technology performance comparison

仿真實(shí)驗(yàn)體現(xiàn)出了算法的合理性和有效性.當(dāng)采用備份服務(wù)恢復(fù)路徑方法時(shí)，成功恢復(fù)后的路徑權(quán)值總和為17，但是采用Bellman動(dòng)態(tài)規(guī)劃算法的服務(wù)恢復(fù)策略，服務(wù)恢復(fù)成功的服務(wù)路徑權(quán)值為13，相較而言，該算法產(chǎn)生的路徑是最優(yōu)的而服務(wù)恢復(fù)成功率也是最高的.

4 結(jié)束語(yǔ)

本文提出了一種基于Bellman動(dòng)態(tài)規(guī)劃的服務(wù)恢復(fù)方法.通過(guò)與傳統(tǒng)的服務(wù)備份路徑方法對(duì)比，實(shí)驗(yàn)結(jié)果顯示:1)在性能方面本文方法的CPU負(fù)載、內(nèi)存利用率和輸入輸出均有較大改善;2)在恢復(fù)路徑選區(qū)方面選擇的路徑權(quán)值更小，開銷得到了有效控制，且時(shí)間復(fù)雜度由原有指數(shù)時(shí)間降為多項(xiàng)式時(shí)間.下一步將結(jié)合恢復(fù)過(guò)程的特點(diǎn)對(duì)Bellman動(dòng)態(tài)規(guī)劃算法進(jìn)一步改進(jìn)，以提高求解的效率.

［1］代鈺，楊雷，張斌，等.支持組合服務(wù)選取的QoS模型及優(yōu)化求解［J］.計(jì)算機(jī)學(xué)報(bào)，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］葉世陽(yáng)，魏峻，李磊，等.支持服務(wù)關(guān)聯(lián)的組合服務(wù)選擇方法研究［J］.計(jì)算機(jī)學(xué)報(bào)，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］李旭，謝長(zhǎng)生，楊靖，等.一種改進(jìn)的塊級(jí)連續(xù)數(shù)據(jù)保護(hù)機(jī)制［J］.計(jì)算機(jī)研究與發(fā)展，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.