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.