熊　鹏

(上海电机学院 电子信息学院, 上海 201306)



高生存伪随机自主服务调度算法

熊鹏

(上海电机学院 电子信息学院, 上海 201306)

摘要高生存性是任何网络计算系统所必须具备的属性。分析了自主服务调度算法的特点，针对服务器群集系统中服务器间服务迁移的不确定性，提出了一种伪随机机制。该机制引入了一个调度序列和基于马尔科夫链的自主竞争机制，实现了服务器的自主调度，同时增加了恶意入侵者入侵服务器群集系统的难度，增强了服务器群集系统的生存率。实验表明，具备伪随机序列的服务迁移自主调度算法性具有更好的抗攻击性能，能够更好地协调安全性和服务连续性间的平衡。

关键词服务迁移; 伪随机; 高生存性

Pseudo Random Autonomous Service Scheduling with High Survivability

XIONGPeng

(School of Electronic Information Engineering, Shanghai Dianji University，Shanghai 201306, China)

AbstractHigh survivability is a necessary ability in any network computing system. The paper analyzes strengths and weaknesses of the existing service migration schedule algorithm. For service migration uncertainty among servers in a server cluster system, a pseudo random mechanism is proposed. By creating a scheduling sequence and introducing autonomous competition algorithm based on Markov Link, the mechanism increases intruding difficulties of malicious intruders, thus increases the survival rate of the server cluster system. Experiments show that the autonomous scheduling services migration algorithm with a pseudo-random sequence has better performance against attacks.

Keywordsservice migration; pseudo random; high survivability

可生存性[1]是任何网络计算系统在面对恶意攻击和功能故障时所必须具备的能力，以便能够及时地恢复系统服务。近年来网络计算机系统高生存率的研究也是网络安全领域的研究热点。考虑到网络系统分层的体系结构，可生存性研究不可避免地受到这一架构影响。对照TCP/IP网络体系结构，可生存性从底层到上层分为物理生存性、网络生存性、数据生存性和服务生存性4层[2]。其中，物理生存性是解决故障问题，主要包括故障检测、硬件冗余备份等；网络生存性是解决路由协议的连接、链路拥塞等问题，包括快速重建路由、控制拥塞等；数据生存性主要通过数据的本地或远程备份、区域网络存储和数据分散算法等来实现；而服务生存性则主要通过服务器冗余、服务迁移和调度机制来实现。和TCP/IP模型一样，上层生存性依赖下层提供的服务。

服务可生存性对整个网络的生存性是不可或缺的[3]。位于最上层的服务可生存性调度主要以在恶意入侵和故障发生的情况下，在提供相同服务的服务器间，如何实现尽可能长时间持续性服务的服务迁移，以及确保服务连续性和可生存性之间达到相互妥协和平衡为主要研究目标。本文在自主服务调度算法的基础上，提出了高生存伪随机自主服务调度算法，引入了伪随机调度序列，使得算法网络存在恶意攻击或出现故障时，具备更好的服务生存性和连续性。模拟实验证明了该算法的有效性。

1自主服务调度算法

自主服务调度算法[4]是多机群集服务调度算法[5]研究方向的一个重要分支。通常用于多机群集系统负载均衡的机制，在服务调度机制中也常被使用。自主服务调度算法位于群集系统中的每台服务器上，服务器彼此竞争，最终胜出的服务器取得存储在名为“分配器”设备上的服务请求，如图1所示。图中，路径1表示服务分配器获取并存储来自于网络的服务请求；路径2和4表示相应服务器竞争分配器的服务请求；竞争结果是由路径2获得请求，并通过路径3向网络提供服务。在此过程中，获得服务请求的服务器将向全网广播该信息，其他服务器则停止竞争，继续等待下一次服务请求。

图1　自主服务调度过程Fig.1　Autonomous service scheduling procedure

服务自主调度算法具有较好的可扩展性，群集系统[7]中服务器数量的增加也较容易实现。但相应地会产生较多的管理信息负荷[8]，如服务器间的负载均衡信息[9]、状态信息[10]等，都要消耗一部分带宽资源。与多机群集服务调度算法中的另一个重要机制——中央控制服务调度[11]相比较，该算法对服务分配器工作要求较低，分配器不会因工作压力产生明显的瓶颈。

2高生存伪随机自主服务调度算法

2.1调度序列

通过移位寄存器来创建一个伪随机序列[12]，同时加入入侵检测序列[13]，在预定的逻辑算法(如异或)运算下获取最终的调度序列，具体过程如图2所示。图中，a1,a2,…,an为伪随机序列。

图2　调度序列的创建Fig.2　 Creation of scheduling sequence

图2中，当输出的伪随机序列为“1”时，将触发算法进行服务迁移，由此避免从事服务的服务器长时间暴露在恶意攻击下，这样能有效地降低服务器受攻击的概率，提高系统的安全；同时，根据入侵检测的情况，入侵检测序列本身也能触发服务进行迁移。因此，在伪随机序列和入侵检测序列的双重保护下，群集系统能有效地应对检测到和未检测到的恶意攻击行为，系统中的服务器也因暴露时间有限，而避免遭受大规模破坏。

2.2调度算法

本文设计的高生存伪随机调度算法的具体执行步骤如下：

伪随机调度算法

Pseudo-random Scheduling()

变量(variables)：c: 群集系统某区域中服务器的总量，其集合为Z；

i: 完成初始化的服务器数量(0≤i≤c)，其集合表示为R；

Timer: 时间计数器。单个服务器被指定提供服务的最长时间。

初始化(Initialization):

(重新)启动服务器，并加载本地启动信息，并获取私钥，对文件及目录完整性进行验证。

算法主体(Main Loop)

While(i>0)

{

∥存在一个来自于服务分配器的服务请求

服务器Pi获得该请求；

Set Timer;∥设置时间计数器初始值；

i=i-1;

delete serverPifrom the setR;∥从集合R中删除服务器Pi；

if ((Timer1 timeout) OR (the output of scheduling sequence is “1”))

{

if(R≠∅)

{

通过预定的竞争机制，服务将迁移到集合R中的另一台服务器Pj上；同时Pj在整个系统内广播这一信息，集合R中的其他服务器收到此广播后将继续等待新的服务请求；

}

if(R=∅)

{

服务将被挂起，直到集合R中有新的服务器存在，然后服务将被迁移到新服务器上;

}

服务器Pi进行初始化；

if(如果服务器Pi结束初始化)

{

i=i+1；

服务器Pi加入集合R;

}

}

}

算法的执行代码被设计保存在每台服务器的只读存储器中，以便服务器启动时读取。算法中，变量被设计存储在群集系统中的共享存储区域，保证了不同服务器能读取到相同的变量值。

服务器一旦重启，假设所有安全隐患都将被清除，在伪随机调度算法下，所有服务器能够为整个系统提供安全服务。算法执行过程中，存在两种触发服务进行迁移的条件： ① 输出的调度序列为1；② 时间计数器超时。一旦两者中有其一成立，服务器将停止当前服务，进入初始化状态；初始化结束后，服务器将再次提供服务。

可生存性是本文设计的伪随机调度算法最重要的实现目标。若考虑更多的指标因素，如服务的连续性，当集合R为空，且时间计数器超时，此时工作服务器将持续为系统提供长时间的服务，故服务器会因暴露时间过长也增加其遭受攻击或入侵的风险。因此，可以通过为处于挂起状态的服务设置一个计时器来避免挂起的某项服务过长时间。

2.3基于马尔科夫链的自主竞争机制

不同于请求调度算法[10]的中央控制服务调度机制，在本文设计的高生存伪随机调度算法中，所有服务器都将参与服务提供权的竞争，一旦服务需要迁移，系统中那些处于准备服务状态中的服务器(即算法中集合R中的服务器)彼此竞争提供服务的权利；无需考虑负载均衡问题，只要使得上次规定的最长时间内表现最好(如被攻击次数最少)的服务器赢得竞争即可，这种选择机制可称为基于马尔科夫链的自主竞争机制。

2.4服务器状态转移

本文设计的高生存伪随机自主调度算法共定义了4种服务器状态： 服务状态、初始状态、准备服务状态、挂起状态。系统中任何一台服务器在某一时刻只能处于其中一种状态。服务状态，即服务器当前正在提供服务，此时该服务器称之为执行服务器；初始状态，此时服务器处于离线状态，它可能正在执行重启、自检和安全性检测或认证(如文档或目录的完整性等)等任务；准备服务状态，服务器已完成了先前的初始化，可随时参与服务请求的竞争；挂起状态服务器暂停了服务调度直到有新的服务器处于待服务状态。服务器状态间的相互转移路径如图3所示。

图3　服务器状态转移Fig.3　Server state transition diagram

图中，路径1表示满足服务迁移，但待服务器集合为空，服务器挂起服务进程，继续服务直到待服务器集非空；路径2表示服务迁移发生，工作服务器转入初始化状态；路径3表示输出序列为“1”或计时器超时，服务发生迁移，工作服务器进入初始化状态；路径4意味着初始化过程结束，服务器转入准备服务状态；而路径5表示服务器通过竞争获取了提供服务的权利。需要说明的是，当某个服务器处于挂起状态时，它接下来的状态只能是初始化状态，这是由算法更注重高生存性、而服务的连续性而决定的。

3模拟实验

实验通过Linux系统的虚拟服务器[14]构建了一个简单的服务器群集系统来验证本文设计的高生存伪随机自主调度算法的性能。系统中的所有服务器都运行相同的服务程序，如DNS服务。服务器双倍速率Redhat由PC机承担，基本配置为2.4GHz CPU，512MB双倍速率内存，80GB IDE(Integrated Drive Electronics)硬盘等。操作系统为Redhat Linux 9.0，内核版本为2.4.20。服务请求用户向服务器群集发送服务请求，实验设定任一时刻只能有一台服务器提供服务。算法采用传输控制协议(Transmission Control Protocl, TCP)连接迁移方案[15]来执行具体的服务迁移。

将人为加入间隔时间为120s的入侵检测序列作为实际检测结果；伪随机序列发生器使用63位寄存器，反馈函数为

bn= b1+b2+bn-1

该发生器能产生一个总长为9.22337×1018(即263-1位)寄存器周期的序列。序列初始化时全为“0”。设定高生存伪随机自主调度算法序列间隔时间为120s，时间计数器的值为250s，实验持续时间为60min(3600s)[16]。

实验1假定实验群集系统采用3台服务器A、B、C；无伪随机序列，人为添加入侵检测序列{000001101001010101101100111110}，间隔时间120s，第1位(bit)在实验开始120s后发出。需要指出的是，当输出序列中有1个“1”时，服务开始迁移；连续输出5个“0”时，用时120×5=600s，而时间计数器为250s，故将出现2次服务迁移；2个连续“0”也能导致服务迁移；因此，本实验服务共将进行19次迁移。表1给出了服务迁移的顺序及对应的时间间隔。

表1　服务迁移顺序及时间间隔(无伪随机序列参与)

为计算本次实验系统的服务效率，利用实验的总耗时和迁移耗时来计算服务的持续时间。实验中，共进行了19次服务迁移，耗时141.9s，实验总耗时3600s，故实验的总服务时间ts=3600-141.9=3458.1s，则系统的服务效率为

(1)

式中，ts为平均服务时间；tm为平均迁移时间。

对表1进行统计，服务器A服务迁移了7次，服务器B服务迁移了6次，服务器C服务迁移了6次，而总服务时间被分割为20份，则单个服务器平均暴露时间为

te=3458.1/20=172.9(s)

(2)

实验2加入伪随机序列{01000111101010-110110000001000101000111010000010011000111-1110}，其间隔时间为60s。伪随机序列在实验开始60s后发送第1位(bit)；检测序列与实验1相同，间隔时间为120s，以便两次实验能够相互对照。实验开始，将输出如下调度序列： {01000111-101111110110000101010101000111010101010011-0101111110}，间隔时间为60s。当输出序列中有“1”时，服务迁移；连续输出4个“0”将导致时间计数器超时，从而将出现2次服务迁移，故实验2的服务迁移总次数为35次，具体如表2所示。

表2　服务迁移顺序及间隔时间(加入伪随机序列)

因此，服务迁移总耗时252.9s，总服务时间ts=3600-252.9=3347.1s则服务效率为

C2=3347.1/3600=92.98%

(3)

单个服务器服务的平均暴露时间为

Te=3347.1/36=93.0s

(4)

和单纯由检测序列组成的调度序列相比，显然加入了伪随机序列的调度序列使服务器的暴露时间更短，即连续服务时间更短，而相应地提高了提供服务的服务器本身的安全性能。因此，整个服务器群集的安全性也将更强。

保持输出调度序列不变，调整伪随机序列的输出周期，从而改变服务迁移的频率。当伪随机序列输出周期分别为10s，60s，90s，120s，300s，600s、900s时，实验给出了伪随机序列输出频率和服务连续性以及和服务器曝露时间的关系，如图4、5所示。

图4　服务连续性和伪随机序列周期相关性Fig.4　　　The relation between the pseudo-random sequence　　　period and the service continuity

图5　服务器暴露时间和伪随机序列周期相关性Fig.5　　　The relation between the pseudo-random sequence　　　period and The server exposure time

由图可见，随着伪随机序列输出频率的提高(输出周期缩短)，服务迁移率显著提高，随之而来的服务器的暴露时间缩短，安全性得到增强，但相应的服务连续性会变差。实际应用中，检测序列来自于外部的实际检测结果，算法只能控制伪随机序列的输出周期，通过调整伪随机序列的输出频率，群集系统就能实现服务连续性和安全性之间平衡；而且服务迁移的成本也能得到有效控制。

4结语

在分析自主服务调度算法的基础上，本文提出的高生存伪随机自主调度算法通过引入伪随机序列和入侵检测序列，在预定的竞争机制下，实现了服务在服务器间分发和自主迁移。考虑到现实应用中的网络入侵的普遍存在，而服务器本身又是网络入侵和恶意攻击的主要目标，算法实现了对未知或未检测到的入侵行为有效抵抗，从而增加了恶意入侵服务器集群系统的难度。实验证明，伪随机自主调度算法在有效平衡服务连续性的前提下，可有效地提高整个服务器系统的生存能力。

参考文献

[1]ELLISON R J，FISHER D A，LINGER R C，et al.Survivable network systems: An Emerging discipline.Technical Report CMU/SEI-97-TR-013[R].Pittsburgh，PA: Software Engineering Institute，1997.

[2]ORDA A，YASSOUR B.Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas[C]∥Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，NY，USA: ACM，2005: 426-437.

[3]BLACKMON S，NGUYEN J.Storage：High-availability file server with heartbeat[J].System Administrators，2001，10(9)： 24-32.

[4]XIE Tao，QIN Xiao.Stochastic scheduling with availability constraints in heterogeneous clusters[C]∥IEEE International Conference on Cluster Computing.Barclona：IEEE，2013: 1-10.

[5]RABBAT R，MCNEAL T，BURKE T.A high-availability clustering architecture with data integrity guarantees[C]∥Proceeding of the 2001 IEEE International Conference on Cluster Computing. Newport Beach，CA，USA：IEEE，2001: 178-182.

[6]WOO A，CULLER D.A transmission control scheme for media access in sensor networks[C]∥Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.New York，NY，USA：ACM，2001: 221-235.

[7]HUANG Y, SOOD A.Self-cleansing systems for intrusion containment[J].Workshop on Self-Healing Adaptive and Self-Managed Systems，2002: 5.

[8]HUANG Y，SOOD A, BHASKAR R K.Countering web defacing attacks with system self- cleansing[C]∥Proceedings of 7th Conference on Word Multiconference on Systemics，Cybernetics and Informatics.Orlando，Florida:[s.n]，2003，12-16.

[9]HUANG Y，ARSENAULT D，SOOD A.SCIT-DNS：Critical infrastructure protection through secure DNS server dynamic updates[J].Journal of High Speed Networks，2006(1): 5-19.

[10]HUANG Y，ARSENAULT D，SOOD A.Securing DNS services through system self cleansing and hardware enhancements[C]∥Proceeding First International Conference on Availability, Reliability，and Security.Washington，DC，USA：IEEE，2006: 132-139.

[11]TAO Jie，JU Jiubin.A task scheduling algorithm for parallel logic programming systems[C]∥Proceedings of the Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region，Volume 1.Beijng：IEEE，2000： 266-271.

[12]HUANG Y，ARSENAULT D，SOOD A.Incorruptible system self-cleansing for intrusion Tolerance[C]∥25th IEEE International Performance，Computing and Communications Conference.Phoenix，AZ：IEEE，2006： 496.

[13]胡兰雨，高振明，朱维红，等.基于PN码导频的FMT信道估计方法[J].山东大学学报(理学版)，2006，41(1)： 120-124.

[14]LVS.What is virtud server?[EB/OL].(2008-02-26)[2015-09-01].http:∥linuxvir tualserver.org/what is.html.

[15]SNOEREN A C，ANDERSEN D G，BALAKRISHNAN H.Fine-grained failover using connection migration[C]∥Proceedings of the 3rd Conference on USENIX Symposium on Internet Technologies and Systems Vol.3.San Francisco，California，USA：USENIX Association Berkeley，2001： 19.

[16]HUANG Y，ARSENAULT D，SOOD A.Closing cluster attack windows through server redundancy and rotations[C]∥Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid.Singapore： IEEE，2006: 12-21.

文献标识码A

中图分类号TP 393.04

文章编号2095 - 0020(2016)01 -0032 - 06

作者简介：熊鹏(1978-)，男，副教授，博士，主要研究方向为无线网络协议、网络安全等，E-mail:xiongp@sdju.edu.cn

基金项目：国家自然科学基金项目资助(11261037)；上海电机学院重点学科资助(XKJ0701)

收稿日期：2015-12-25