服务负载均衡

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
5,May2006,pp.
10681077http://www.
jos.
org.
cnDOI:10.
1360/jos171068Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
服务组合中一种自适应的负载均衡算法李文中1,2+,郭胜1,2,许平1,2,陆桑璐1,2,陈道蓄1,21(计算机软件新技术国家重点实验室(南京大学),江苏南京210093)2(南京大学计算机科学与技术系,江苏南京210093)AnAdaptiveLoadBalancingAlgorithmforServiceCompositionLIWen-Zhong1,2+,GUOSheng1,2,XUPing1,2,LUSang-Lu1,2,CHENDao-Xu1,21(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210093,China)2(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)+Correspondingauthor:Phn:+86-25-83597284,E-mail:lwz@dislab.
nju.
edu.
cn,http://www.
nju.
edu.
cnLiWZ,GuoS,XuP,LuSL,ChenDX.
Anadaptiveloadbalancingalgorithmforservicecomposition.
JournalofSoftware,2006,17(5):10681077.
http://www.
jos.
org.
cn/1000-9825/17/1068.
htmAbstract:ServiceCompositionenablesanewwaytocreatenewservicesbyassemblingindependentservicecomponents.
Oneoftheimportantgoalsinservicecompositionisloadbalancingacrossservicereplicas.
Inthispaper,anoveladaptivedistributedloadcapacitybased(LCB)algorithmispresentedtosolvetheloadbalancingprobleminservicecomposition.
LCBalgorithmusesserviceroutingmechanismtosearchservicesandtransfertheapplicationdata.
Byself-adaptivelycalculatingtheloadcapacity(LC)metric,LCBalgorithmcanchooseareasonableservicepath.
LCmetricreflectstheworkloadoftheservicenode,andisadaptivelyadjustedaccordingtothevariationsoftheserver'sload.
Comparedwiththepreviousresearches,LCBalgorithmneedn'ttheglobaltopologyinformationandloadinformation.
Itismuchsuitablefordynamicservicecompositionindistributedsystems.
SimulationsshowthatLCBalgorithmperformswellintermsofloadbalancingacrosstheservicereplicas.
Keywords:servicecomposition;loadbalancing;serviceoverlaynetwork;servicerouting;qualityofservice摘要:服务组合可以整合网络上现有的多种异构服务,形成新的服务.
针对服务组合中服务路径的选择和负载均衡问题,提出了一种自适应的分布式负载均衡算法——LCB(loadcapacitybasedalgorithm)算法.
LCB算法使用服务路由来查找服务和转发数据,使用负载容率(loadcapacity,简称LC)测度来进行服务副本的选择,从而建立一条适当的组合服务路径.
LC测度是对服务器负载的估算,它根据服务器的负载波动信息不断地进行自适应的调整,从而实现多个服务副本之间的负载均衡.
与现有的服务组合负载均衡算法相比,LCB算法不需要知道服务器的最大负载量和当前负载信息,而且具有更好的可扩展性,更适用于分布式环境下动态服务副本的组合.
模拟实验表明,LCB算法具有良好的负载均衡效果.
SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60402027(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.
2004AA112090(国家高技术研究发展计划(863));theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.
2002CB312002(国家重点基础研究发展规划(973));theNaturalScienceFoundationofJiangsuProvinceofChinaunderGrantNo.
BK2005411(江苏省自然科学基金)Received2005-09-04;Accepted2005-10-11李文中等:服务组合中一种自适应的负载均衡算法1069关键词:服务组合;负载均衡;服务覆盖网;服务路由;服务质量中图法分类号:TP393文献标识码:AWeb服务是一种新兴的分布式Web应用模式,是Web上数据和信息集成的有效机制.
当前,Internet上正出现越来越多的规模巨大且内容丰富的服务,需要有一种新的机制来整合和集成这些服务.
在Web服务的研究中,服务组合(servicecomposition)是一个极具挑战性的问题[1].
服务组合可以集成现有的简单服务,组合形成复杂服务,快速而又灵活地构建功能强大的新应用,对于网络资源的重用和协同具有重要意义[2].
首先,现实中的应用一般很复杂,为了分散和简化应用逻辑,提高服务可用性,单个Web服务不可能做得很复杂.
因此,复杂服务需要组合多个简单的Web服务.
其次,目前已经存在丰富多样的异构Web服务,为了将这些分散的服务有机地组织成新的系统,需要进行服务组合.
再次,各种异构的硬件设备(如PC,PDA等)和网络服务访问方式(如有线、无线等)不断涌现,为了实现随时随地的普适计算(pervasivecomputing),同一种服务要求以多种版本投递给用户[3],传统的信息存储站点、商业站点、网络服务和搜索引擎需要以一种新的方式结合起来,提供新的服务,也要由服务组合来完成.
1问题描述我们研究在服务覆盖网(serviceoverlaynetwork)中的服务组合问题.
服务覆盖网是由服务节点构成的覆盖网络,服务提供者可以在服务节点上部署相应的服务.
在服务覆盖网中,每类服务都可以有多个实例或称为服务副本,它们提供相同或不同级别的服务质量,可以实现覆盖网络中负载均衡并提供有弹性的容错[4].
服务组合通过选择一组所需的实例,在服务覆盖网中形成路径,构成复杂的新应用.
如何选择服务路径是服务组合中一个具有挑战性的问题[5].
出于负载均衡以及保证服务可用性的需求,服务提供者会在不同的网络节点上部署和管理多个服务副本.
因此,一个组合服务可以由多条服务路径来实现.
服务路径由服务组件和组件之间的网络构成.
服务组件实现了组合服务的功能,因此,组合服务的性能严重依赖于组合过程中所选择的各服务组件的副本.
为了提高服务质量,在建立服务路径时,要避免某些服务副本负载过重而另一些服务副本负载很轻的情况.
在服务副本之间实现负载均衡是服务组合的一个重要目标.

图1是一个服务覆盖网.
图中显示了4种服务及其副本的部署情况.
用户可以向服务覆盖网中任意一个节点提出服务组合请求,该节点叫做出口节点(exitnode).
在图1中,用户请求组合服务0和服务2,图中建立了一条服务路径,该路径经过了服务0和服务2两种服务组件,为用户提供新的服务.
服务路径中允许存在非操作服务(no-opservice).
一个节点如果作为非操作服务节点,它只作数据的转发,不进行任何处理.
数据沿着服务路径传输,最后到达出口节点,传递给用户.
服务组合要解决的问题是根据用户的服务请求,寻找一条服务路径满足用户请求,同时,要使每种服务的各服务副本上的负载尽可能地分布均衡.
Service0Service1Service2Service3No-OpserviceServicepathServiceoverlaynetworkExitnodeClientFig.
1Servicecomposition:Anexample图1服务组合的例子1070JournalofSoftware软件学报Vol.
17,No.
5,May20062相关工作近年来,国内外对Web服务器选择的负载均衡问题进行了广泛研究[68].
但是,服务组合的负载均衡问题具有新的特点:首先,服务器负载均衡只需选择一台服务器提供服务,而服务组合需要选择一组服务副本,服务之间存在某种次序和依赖关系,形成服务路径;其次,服务实例的选择必须是动态的,因为组合服务往往是持续一段时间的软实时应用(比如多媒体流),这一点与接受短时间会话请求(如Web页面访问)的Web服务器不同.
目前,关于服务组合的研究主要有SAHARA项目[9],CANS[10],QUEST[11],SpiderNet[12]等.
要在服务覆盖网中找出一条合适的服务路径,就是要找出一条通过特定节点,并以某种测度衡量的、代价最小的路径.
目前,人们对Web副本站点的选择和机群的负载均衡问题[7,8]进行了深入的研究.
但是,服务组合问题要对一组服务进行动态选择,原有的负载均衡算法并不能完全适用于服务组合的情况.
QUEST框架提出了一种在服务覆盖网中寻找满足多种QoS约束的服务路径的方法[11],但它主要考虑的是不同服务路径上的QoS约束和路径之间的负载均衡问题,并不一定能保证各服务副本的负载均衡.
在可编程网络的研究中,文献[13]提出了一种构建通过特定中间节点的路径的算法.
该算法从初始覆盖网络拓扑图派生出一个多层转换图,然后在这个转换图上使用Dijkstra最短路径算法,求出经过某些特定节点的最短路径.
文献[14]提出了利用状态转换图来选择符合网络带宽约束的服务路径的方法.
在此基础上,Raman等人提出了使用LIAC(least-inverse-available-capacity)测度来构建服务路径的方法[5](简称为LIAC算法).
LIAC算法的基本思想是:对于用户请求组合的k个服务,将覆盖网络图复制k+1次,并在用户所请求的服务之间添加垂直边,形成多层转换图;然后,根据服务器的最大负载和当前负载信息,在垂直边上设置权重.
这样,只需使用Dijkstra算法在这个带权多层转换图上寻找一条从顶层到底层的最短路径,就是服务负载最轻的一条路径.
但是,LIAC算法具有以下缺点:(1)多层转换图需要将覆盖网络图复制k+1次,存储空间开销和计算时间开销比较大;(2)LIAC算法需要知道服务覆盖网的全局拓扑结构、每台服务器的当前负载和最大负载值,在实际网络环境中,这些信息是难以准确测定的;(3)每个服务器需要维护全局的网络拓扑和负载信息,一个服务器加入或退出系统,需要重新进行计算,开销较大.
总之,LIAC实际上是一种集中式的负载均衡算法,并不适用于大规模网络中服务节点动态加入和退出的情况.
3LCB:一种分布式自适应服务组合负载均衡算法针对上述LIAC算法的缺点,我们提出一种分布式的自适应服务组合负载均衡算法——基于负载容率的负载均衡(loadcapacitybasedalgorithm,简称LCB)算法.
它借鉴IP路由的思想,使用分布式的服务路由表来进行服务的查找和数据的转发,同时根据各服务节点的负载波动情况,自适应地选择服务副本,达到良好的负载均衡效果.
LCB算法需要使用两张表:服务路由表和负载容率(loadcapacity,简称LC)表.
服务路由表用于服务的查找和数据转发,LC表则用于为服务副本的选择提供决策.
下面,首先介绍如何在服务覆盖网中构建分布式的服务路由,然后详细介绍LCB负载均衡算法.
3.
1分布式服务路由的建立在服务覆盖网中,为了实现服务的组合和服务之间的数据转发,每个服务节点要维护一张服务路由表.
服务路由表的作用是记录服务之间的最短路径以及该路径上进行数据转发的服务节点.
服务路由类似于Internet上的IP路由.
通过服务路由,一个服务节点可以选择一个邻居服务节点将数据转发到目标节点.

服务覆盖网可以用一个无向连通图来表示,图中每一个顶点表示一个服务.
服务路由问题本质上是要求出图中任意两个节点之间的最短路径问题.
在经典的图论中,可以使用Dijkstra算法和Floyd算法来计算图中任意两顶点的最短路径,但它们是集中式的算法,不能用于建立分布式路由.
Toueg基于Floyd算法提出了一种简单的分布式路由算法[15],可用于建立网络中各服务器的路由.
此外,还有许多改进的分布式路由算法,如Merlin-Segall算法[15]、Chandy-Misra算法[16].
李文中等:服务组合中一种自适应的负载均衡算法1071我们介绍如何用Chandy-Misra分布式路由算法来建立服务路由.
假设服务覆盖网中部署有N个服务节点,每个服务节点要维护一张长度为N的服务路由表.
服务路由表的每一项包含该服务节点到其他节点的最短路径的长度和转发邻居的信息.
对于节点u,用Ru表示它的服务路由表.
Ru[i].
hops表示服务节点u到节点i的最短路径的长度(用转发的跳数来表示),Ru[i].
next表示服务节点u到节点i的转发邻居,u到i的数据都经过该邻居节点转发.
设V为服务覆盖网中所有服务节点的集合,Neighu为节点u的所有邻居节点的集合.
使用Chandy-Misra算法计算到达目的节点v0的服务路由的过程如下:Initialization:beginforallv∈VdoIfv=uthenbeginRu[v].
hops:=0;Ru[v].
next:=nullendelsebeginRu[v].
hops:=∞;Ru[v].
next:=nullendendFornodev0only:beginforallω∈Neighudosendmessage(v0,0)toω;endProcessingamessage(v0,d)fromneighborωbyu:beginreceivemessage(v0,d)fromω;ifd+1max_lcthenbeginmax_lc:=LCu(x);S:=xendendifS=nullexit3.
使用式(2)~式(4)更新节点u的LC表:LCu(S):=MAX(0,MIN(1,(1α*s)*LCu(S)));/*s为节点S的负载波动率*/4.
查询服务路由表,将客户的其他服务请求转发给S所在的服务器,由S选择下一个服务副本,最终形成服务路径Req:=(S2,…,Sk);request_forward(u,S,Req);李文中等:服务组合中一种自适应的负载均衡算法1073LCB算法克服了上面提到的LIAC算法的一些缺点:(1)在LIAC算法中,构建多层转换图需要将覆盖网络图复制k+1次,再用Dijkstra算法寻找最短路径.
LCB算法只需对覆盖网络图应用服务路由算法,存储空间开销和计算时间开销都比LIAC算法小得多.
(2)在LIAC算法中,构造多层转换图需要知道服务覆盖网的全局拓扑结构,LIAC测度的计算则需要知道各服务节点的当前负载和最大负载值,但是,服务器的最大负载量往往难以预先估算,而且服务器的当前负载也是难以测定的.
LCB算法只需要知道服务节点的负载波动情况,也就是服务器在一段时间内结束的服务数量,这对于服务器来说是可以准确测量的.
(3)在LIAC算法中,一个服务器加入或退出系统,会导致整个多层转换图的拓扑结构发生改变,需要重新计算,开销较大.
LCB算法使用分布式的服务路由,一个节点的状态发生改变,只需对分布式路由表的部分项进行修改,并重新计算LC表中该节点的测度值即可.
(4)LIAC实质上是一种集中式的负载均衡算法,而LBC是一种分布式的负载均衡算法,更适用于大规模网络环境下服务节点动态加入和退出的情况.
4模拟实验4.
1实验的建立我们通过模拟实验来验证LCB算法的负载均衡性能.
我们使用网络仿真工具GT-ITM[17]生成物理网络拓扑,并在生成的物理网络上随机选择100个节点作为服务覆盖网的节点,在这些节点之间定义了117条链接.
我们设置了10个不同的服务S0~S9,每个服务有4个副本数.
我们在服务覆盖网的100个节点上随机选择40个节点来部署这些服务副本.
每个节点的最大负载量设为1500.
假设每使用一次服务副本消耗1个单位的负载.
我们设置每个会话的持续时间为70s~90s,会话请求的到达速率设为20次/秒.
每个会话随机包含2个服务.
一次实验处理10000个会话.
每个会话到达后,可以使用不同的方式选择出口节点.
根据不同的实验目的,我们将使用随机和非随机两种方式选择出口节点.
4.
2LCB算法的负载均衡效果假设用户的请求是随机地向服务覆盖网的100个节点发送的,我们令波动因子α=0.
1,在上述实验环境下,运行LCB算法.
表1显示了当10000个会话全部建立后,每种服务的4个服务副本所接入的会话总数.
从表中可以看出,每种服务的4个副本所接入的负载总量相差不太大,表明使用LCB算法,各服务副本在一个时间段内所接入的负载总量是均衡的.
Table1Loaddistributionacrossservicereplicas表1服务副本的负载分布ReplicanumberS0S1S2S3S4S5S6S7S8S90452493503476474473502496491473152753654051048851353951649351024965105014854774994935045455063487501513533470448492511505519为了研究各服务副本的负载随时间变化的情况,我们的实验每隔15秒测量一次各服务副本的负载量.
我们通过实验比较LCB算法和LIAC算法的性能.
图2和图3显示了分别使用这两种算法时,一个服务S0的4个副本的负载量随时间变化的曲线(其他服务的副本负载变化情况也类似).
图中4条曲线相互越靠近,表明分布在4个服务副本上的负载越均衡.
从图3可见,在很多情况下,4条曲线的点几乎重合在一起,这表明LIAC算法具有良好的负载均衡效果.
图2的4条曲线则相互分得开一些,表明LCB算法的负载均衡效果不如LIAC算法.
造成这种差异的原因是,LIAC算法使用了全局的准实时负载信息,进行集中式的计算,因此大部分时间服务副本的负载分布很均衡,但LIAC算法是集中式的,计算开销比较大,而且算法所需的信息在真实网络环境中也很难获取.
LCB算法是一种分布式的算法,它使用的LC测度是一个根据服务器负载波动估算的测度,并不是真正的服务器负载信息.
同时,LC测度是自适应调整的,当几个服务副本之间的负载差异比较大时,LC值会自动调整,使各副本的负载趋于均匀.
从图2可见,虽然在有些点,4条曲线的距离比较大,但通过LC测度的调整会逐渐趋于1074JournalofSoftware软件学报Vol.
17,No.
5,May200612010080604020Replica0Replica1Replica2Replica3Workload靠近.
在实际的网络应用环境中,并不要求各服务副本的负载在任何时刻都严格保持均衡,各服务副本之间的载只要相差在一定的范围内,都是可以接受的.
从图2来看,大部分情况下4个服务副本之间的负载相差不超过20.
因此,LCB算法可以适用于真实网络环境中的服务组合应用.
1590165240315390465120100806040200WorkloadReplica0Replica1Replica2Replica3Time(s)01590165240315390465Time(s)负Fig.
2LoadvariationwithLCBalgorithm(α=0.
1)图2LCB算法负载变化(α=0.
1)Fig.
3LoadvariationwithLIACalgorithm图3LIAC算法负载变化4.
3波动因子α对负载均衡的影响图2显示了α=0.
1时LCB算法的负载均衡效果.
事实上,波动因子α的取值对负载均衡有着重要的影响,适当地选取α的值可以获得更好的负载均衡效果.
因此,我们需要研究波动因子α的变化与负载均衡的关系.

为了衡量负载均衡的效果,我们引入负载距离LD来表示4条负载曲线之间相互靠近的程度.
在任一时刻,LD定义为4条负载曲线上各点两两距离的总和.
4条负载曲线相互越靠近,LD越小,表明负载越均衡.
假设σ为负载观测点的集合,sum为观测点的总数.
设P为一个观测点,则在P点处观测到4个服务副本的负载值L0,L1,L2,L3.
在P点处的负载距离LDp定义为∑∑=+==2031iijjiPLLLD(5)我们用平均负载距离来衡量整体的负载均衡效果.
平均负载距离定义为在所有观测点上的负载距离的平均值.
平均负载距离的计算公式为sumLDLDPP∑∈=σ(6)为了考察波动因子α对平均负载距离LD的影响,我们让α取值0.
1,0.
2,…,0.
9,对每个α,计算相应的平均负载距离,可以画成如图4所示的关系曲线.
可见,曲线在α=0.
3和α=0.
6附近各有一个极小值.
这表明α取值在0.
3或0.
6附近时,整体的负载均衡效果最好.
在后面的实验中,我们令α的取值为0.
3.
Fig.
4Averageloaddistancevariationwithfluctuatingfactorα图4平均负载距离随波动因子α的变化4.
4LCB算法对于非均匀用户访问的负载均衡效果前面讨论了用户访问均匀分布在各服务器的负载均衡情况.
但在实际中,用户对各服务器的访问请求往往不是均匀的.
研究表明,用户对Web页面的访问服从Zipf-like分布[18],即大部分用户请求集中在小部分的"热点"Averageloaddistanceα7674727068666462600.
10.
20.
30.
40.
50.
60.
70.
80.
9李文中等:服务组合中一种自适应的负载均衡算法1075数据上.
因此,有必要研究当用户请求符合Zipf-like分布时,使用LCB算法的负载均衡效果.
为了产生符合Zipf-like分布的用户访问序列,我们假设为用户请求的对象总数,i表示第i个热门的对象的ID,P(i)表示该对象被请求的概率,则iiP=)(,其中111==∑ii.
在实验中,我们令=100,产生10000个符合Zipf-like分布的用户访问序列.
取α=0.
3,重做第4.
2节的实验,可以得到如图5所示的负载曲线图.
由图可见,4条负载曲线比较接近,各服务副本的负载在大部分时间相差不超过20.
这说明,对于非均匀的用户访问请求,虽然大部分访问请求集中在小部分节点上,但是使用LCB算法,通过对LC测度的自适应调整,仍然可以使负载均衡地分布在服务的各副本上.
Fig.
5Loadvariationwithunevenuservisits(α=0.
3)WorkloadTime(s)1590165240315390465120100806040200Replica0Replica1Replica2Replica3图5非均匀用户访问的负载变化(α=0.
3)4.
5服务路径长度的影响在以上讨论中,LC测度完全是根据负载波动信息进行负载均衡的,并没有考虑服务路径的长度.
因此,有可能根据LC测度选择出来的服务路径虽然可以保证各服务副本的负载相对均匀,但很长,这样,服务组合要经过服务覆盖网的多跳,造成客户访问的延时较长,同时会浪费网络的带宽资源,使网络的整体服务质量下降.

为了研究LCB算法中服务路径长度对性能的影响,我们分别使用LC测度和最短路径测度来进行服务路径选择,图6给出了使用这两种测度选择出来的服务路径长度的累积分布(cumulativedistributionfunction,简称CDF)图.
从图中两条曲线的比较可见,当使用最短路径测度时,80%的服务路径长度在10跳之内;而当使用LC测度时,只有不到40%的服务路径在10跳之内.
由于LC测度没有考虑服务路径长度因素,故选择出来的服务路径长度并不理想.
Cumulativepercentage1008060402000510152025303540ShortestpathLC-Based我们希望在保证负载均衡的同时选择较短的服务路径,以减少用户访问延迟.
因此,我们考虑对LCB算法进行改进,在负载容率LC中加入路径长度的影响.
假设用两个节点之间的跳数(hops)来表示两节点之间的路径长度,我们改进的副本选择原则是,当两个服务副本的负载比较接近时,选择服务路径较短的一个副本为用户提供服务.
这样,LC的更新公式可以改写如下:PathlengthFig.
6PathlengthCDFs,withα=0.
3图6路径长度累积分布函数图(α=0.
3)+=hopsLCfLC1)1(βα(7)其中,β是路径因子,它表示路径长度因素对于服务路径选择的影响.
β越大,表明路径长度的影响越大,越趋近于最短路径.
但β的值不能选得太大,β越大,负载波动的相对影响越小,这样,LC测度也就越不能反映服务副本的负载状况,从而造成负载不均衡的程度增大.
图7显示了随着β的增大,平均负载距离的变化情况.
可见,β越大,平均负载距离越大,造成各服务副本之间1076JournalofSoftware软件学报Vol.
17,No.
5,May2006Shortestpathβ=0β=0.
05β=0.
1β=0.
1510080604020mulativepercentage300250200150100erageloaddistanceβ=0.
200510152025303540PathlengthCu50000.
10.
20.
30.
40.
5βAv的负载越不均匀.
为了保证负载均衡,β的取值不能过大.
例如,我们希望服务的任意两个副本之间的负载距离不超过20,那么平均负载距离LD应控制在小于120的范围内.
由图可见,β取值应在0~0.
2之间.
为了研究β的取值对于所选择的服务路径长度的影响,我们让β分别取值0,0.
05,0.
1,0.
15,0.
2,研究这几种情况下使用LCB算法建立的服务路径长度,并与最短路径进行比较.
图10显示了这几种情况下服务路径的CDF图.
可见,随着β的增大,CDF曲线越来越接近于最短服务路径.
但是,从负载均衡的角度,我们希望β尽可能小,这样负载会更均衡.
两者要取得折衷.
从图8可以看出,当β>0.
1时,β取值为0.
1,0.
15,0.
2这3条CDF曲线已经比较接近,表明当β>0.
1时,β的增大对于缩短服务路径长度的影响已经很小.
因此,我们认为β的值取为0.
1比较适当,这时可以获得较短的服务路径,同时保证负载比较均衡.
Fig.
7Averageloaddistancevariationwithpathfactorβ(α=0.
3)图7平均负载距离随路径因子β的变化(α=0.
3)Fig.
8ComparisonofpathlengthCDFsunderdifferentβvalue(α=0.
3)图8路径长度累积分布函数对不同β取值的比较(α=0.
3)5总结服务路径的选择和负载均衡是服务组合研究的一个重要问题.
我们提出了一种自适应的服务组合负载均衡算法LCB算法,它使用负载容率(LC)测度来衡量各服务副本的负载状况,根据LC测度来选择一条合适的服务路径,可以获得较好的负载均衡效果.
与现有的服务组合负载均衡算法相比,LCB算法的创新之处在于:(1)基于多层转换图的算法时间和空间开销较大,LCB算法提出使用服务路由来查找服务和转发数据,服务路由表可以由服务覆盖网的各节点进行分布式计算,计算的时间和空间开销都少得多.
(2)现有服务组合负载均衡算法大部分需要知道服务器的最大负载和当前负载量信息,而这些数值是很难准确测量的,LCB算法需要的信息量更少.
LCB算法提出根据负载波动来进行服务副本的选择,负载波动的值是很容易准确计算的.
(3)基于多层转换图的算法需要服务覆盖网的全局信息,本质上是一种集中式算法.
LCB算法是一种分布式的负载均衡算法,当服务节点发生改变时,只需对服务路由表和LC表的部分数据进行更新,可扩展性更好.
因此,LCB算法更适用于分布式环境下动态服务副本的组合.
References:[1]YangJ,PapazoglouM.
Webcomponent:Asubstrateforwebservicereuseandcomposition.
In:PidduckAB,MylopoulosJ,WooCC,OzsuMT,eds.
Proc.
ofthe14thConf.
onAdvancedInformationSystemsEngineering(CaiSE2002).
LNCS2348,Toronto:Springer-Verlag,2002.
2136.
[2]YueK,WangXL,ZhouAY.
UnderlyingtechniquesforWebservices:Asurvey.
JournalofSoftware,2004,15(3):428442(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/15/428.
htm[3]SatyanarayananM.
Pervasivecomputing:Visionandchallenges.
IEEEPersonalCommunications,2001,6(8):1017.
[4]GuX,NahrstedtK.
DynamicQoS-Awaremultimediaserviceconfigurationinubiquitouscomputingenvironments.
In:Proc.
ofthe22ndInt'lConf.
onDistributedComputingSystems(ICDCS2002).
Vienna:IEEEComputerSociety,2002.
311318.
[5]RamanB,KatzRH.
Loadbalancingandstabilityissuesinalgorithmsforservicecomposition.
In:Proc.
ofthe22ndAnnualJointConf.
oftheIEEEComputerandCommunicationsSocieties(INFOCOM2003).
SanFranciso:IEEECommunicationsSociety,2003.
14771487.
李文中等:服务组合中一种自适应的负载均衡算法1077[6]CardelliniV,ColajanniM,YuPS.
DynamicloadbalancingonWeb-serversystems.
IEEEInternetComputing,1999,3(3):2839.
[7]ShanZ,LinC,MarinescuDC,YangY,ModelingandperformanceanalysisofQoS-awareloadbalancingofweb-serverclusters.
ComputerNetworks,2002,40(2):235256.
[8]GuoCC,YanPL.
Adynamicload-balancingalgorithmforheterogeneousWebservercluster.
ChineseJournalofComputers,2005,28(2):179184(inChinesewithEnglishabstract).
[9]RamanB,AgarwalS,ChenY,CaesarM,CuiWD,JohanssonP,LaiK,KavianT,MachirajuS,MaoZM,PorterG,RoscoeT,SeshadriM,ShihJ,SklowerK,SubramanianL,SuzukiT,ZhuangS,JosephAD,KatzRH,StoicaI.
TheSAHARAmodelforservicecompositionacrossmultipleproviders.
In:MatternF,NaghshinehM,eds.
Proc.
oftheInt'lConf.
onPervasiveComputing(Pervasive2002).
LNCS2414,Zürich:Springer-Verlag,2002.
114.
[10]FuX,ShiW,AkkermanA,KaramchetiV.
CANS:Compassable,adaptivenetworkservicesinfrastructure.
In:AndersonT,ed.
Proc.
ofthe3rdUSENIXSymp.
onInternetTechnologiesandSystems.
SanFrancisco:USENIX,2001.
135146.
[11]GuX,NahrstedtK,ChangRN,WardC.
QoS-Assuredservicecompositioninmanagedserviceoverlaynetworks.
In:Proc.
ofthe23rdInt'lConf.
onDistributedComputingSystems(ICDCS2003).
Providence:IEEEComputerSociety,2003.
194203.
[12]GuX,NahrstedtK,YuB.
SpiderNet:Anintegratedpeer-to-peerservicecompositionframework.
In:Proc.
oftheInt'lSymp.
onHigh-PerformanceDistributedComputing(HPDC-13).
Honolulu:IEEEComputerSociety,2004.
110119.
[13]ChoiS,TurnerJ,WolfT.
Configuringsessionsinprogrammablenetworks.
ComputerNetworks,2003,41(2):269284.
[14]MaQ,SteenkisteP.
Onpathselectionfortrafficwithbandwidthguarantees.
In:Proc.
oftheInt'lConf.
onNetworkProtocols(ICNP'97).
Atlanta:IEEEComputerSociety,1997.
191202.
[15]TelG.
IntroductiontoDistributedAlgorithms.
2nded.
,Beijing:ChinaMachinePress,2004.
6192(inChinese).
[16]ChandyKM,MisraJ.
Distributedcomputationongraphs:Shortestpathalgorithms.
CommunicationsoftheACM,1982,25(11):833837.
[17]ZeguraEW,CalvertK,BhattacharjeeS.
HowtomodelanInternetwork.
In:Proc.
ofthe15thAnnualJointConf.
oftheIEEEComputerandCommunicationsSocieties(INFOCOM'96).
SanFrancisco:IEEECommunicationsSociety,1996.
594602.
[18]BreslauL,CaoP,FanL,PhillipsG,ShenkerS.
WebcachingandZipf-Likedistributions:Evidenceandimplications.
In:Proc.
ofthe18thAnnualJointConf.
oftheIEEEComputerandCommunicationsSocieties(INFOCOM'99).
NewYork:IEEECommunicationsSociety,1999.
126134.
附中文参考文献:[2]岳昆,王晓玲,周傲英.
Web服务核心支撑技术:研究综述.
软件学报,2004,15(3):428442.
http://www.
jos.
org.
cn/1000-9825/15/428.
htm[8]郭成城,晏蒲柳.
一种异构Web服务器集群动态负载均衡算法.
计算机学报,2005,28(2):179184.
[15]TelG,著;霍红卫,译.
分布式算法导论.
第2版.
北京:中国:机械工业出版社,2004.
6192.