基于性能测量的分布式CDN负载均衡策略

2007年5月

应用科学学报

JOURNALOFAPPLIEDSCIENCES

Vol.25No.3

May2007

文章编号:025528297(2007)0320247205

基于性能测量的分布式CDN负载均衡策略

张国敏, 陈 鸣, 丁 科, 王 娜

3.理工大学理学院,江苏南京211101)

摘 要:为了能够使CDN根据网络和服务器的性能变化实现真正的全局负载均衡,并使其摆脱服务器的单点故障对全局的影响.文中借鉴P2P网络在分布式文件共享及定位等方面的巨大成功,取消CDN中心,使各PoP节点成为对等实体,从而提出了完全分布式CDN(DCDN,distributedCDN)模型.重点研究了负载均衡和服务定位等关键技术,提出了基于网络测量和服务性能测量的MBPP算法.从而在提高CDN的扩展性和健壮性的同时,能够更加精确定位最佳服务提供点.试验表明,基于MBPP算法的负载均衡策略以较低的通信开销和运算复杂度实现了真正的全局实时动态负载均衡.

关键词:分布式内容分发网络;集群式服务提供节点;负载均衡中图分类号:TP393.07 文献标志码:A

1

1

2

3

(1.理工大学指挥自动化学院,江苏南京210007;2.全军网格研究中心,江苏南京210007;

LoadBalancingPolicyofDistributedCDNModelBasedonPerformanceMeasurement

ZHANGGuo2min, CHENMing, DINGKe, WANGNa

1

1

2

3

(1.InstituteofCommandAutomation,PLAUniversityofScienceandTechnology,Nanjing210007,China;2.PLAResearchCenterforMilitaryGridTechnology,Nanjing210007,China;3InstituteofSciences,

PLAUniversityofScienceandTechnology,Nanjing211101,China)

Abstract:InordertomakeCDNimplementrealgloballoadbalancingbasedonnetworkandserverperformancevarianceandavoidinfluenceofsinglepointfailureinserver,byborrowingthesuccessfulP2Ptechniquesfordistributedfilesharingandlocating,wedesignapuredistributedCDNmodelthathasnocentralnode.ThusallPoPnodesarepeerstoeachother.Keytechniquessuchasloadbalancingandservicelocatingarethenstudiedindetail.AMBPPalgorithmbasedonthenetworkandserviceperformancemeasurementisproposed.ScalabilityandrobustnessofCDNareimproved,andthebestserviceprovidingpointcanbelocatedmoreprecisely.Experimentsshowthat,basedonMBPP,globalreal2timedynamicloadbalancewithsmallcommunicationoverheadandcomputingcomplexitycanbeachieved.Keywords:distributedCDN;cluster2PoP;loadbalancing 当前网络中音频和视频应用的增长非常迅速,在给运营商带来丰厚利润的同时也带来了新的挑战.主干网数据流巨大,服务器端瓶颈等都会影响服务的质量.因此将流媒体信息有效地分发是当前面临的重要问题和挑战.内容分发网络(contentdeliverynetwork,CDN)

[1]

求重定向等技术,将信息资源推向网络边缘,使得用户可以从/最近最好0的服务器快速访问到所需的内容,从而大大提高终端用户的访问速度.

在传统CDN系统中,负载均衡和服务重定向大都由中心服务器负责,所有用户的请求都首先发送给中心服务器.由于用户数的增多和CDN规模的不

[2]

采用缓存、复制、负载均衡和客户请

收稿日期:2006205204; 修订日期:2006210223

基金项目:国家自然科学基金(90304016);国家/8630高技术研究发展计划(2003AA143040)资助项目

作者简介:张国敏,博士生,研究方向:网络管理和分布式计算,E2mail:zhang-gmwn@163.com;陈 鸣,教授,博导,研究方向:网络测量、网

络管理和网络体系结构,E2mail:mingchenjy@163.com248 应 用 科 学 学 报第25卷

断扩大,采用一个中心和多个PoP(providerofpoint)点的两层结构的CDN,在扩展性、可靠性和服务性能上已不能适应当前要求.为了能够摆脱集中控制,避免中心服务器的单点故障对全局的影响,更重要的是实现真正的全局均衡负载和内容分布,有许多科研人员采用P2P改造CDN.

DOH是以P2P结构进行Web服务器协作的

[4][5]

CDN,采用DKS(distributedk2narysearch)和DHT(distributedhashtable)构造了可扩展的查询定位环境,从而可以共享负载,提高了整个系统的性能、可扩展性、可用性和稳定性.且DOH能够在异构的硬件环境和地理上分散的区域上运行.CoralCDN是由广泛部署的Web代理和名字服务器组成的P2P结构CDN,能够为用户提供高性能的Web站点和较大的吞吐量.只要在正常URL后面加上简短的特定字符串,就可以通过CoralCDN的对等结构DNS层透明选择,将Web请求重定向到负载最轻的caching代理上,从而避免热点服务器因重载而不可用.

[7]

相对于前两者,CobWeb则更注重资源的优化使用问题.它在缩短用户访问时间和保持带宽可用方面,保持了性能与耗费的折中.CobWeb利用结构化的方式组织系统,不但继承了DHT的可靠性和扩展性,还对正常拓扑下和性能过载情况下负载均衡协调考虑.并使用Pastry作为样例覆盖网络进行了分析.此外,还有几所机构也在这方面进行了深入研[9,10]究.

本文也借鉴P2P网络在分布式文件共享及定位等方面的基础上,通过取消CDN中心使各PoP节点成为对等实体,从而提出了完全分布式CDN(DCDN,distributedCDN)模型.相对于前述研究工作的重点在文件复制和查找上,而在动态负载均衡研究相对不够深入.CobWeb在这方面作了些工作,但是没有把网络性能与服务器性能这两个重要因素结合起来.本文针对以上不足,重点研究了负载均衡和服务定位等关键技术,提出了基于网络测量和服务性能测量的MBPP(measurement2basedping2pong)算法,使CDN系统的灵活性、健壮性、动态能力等都有明显改进.

[8]

[6]

[3]

[2]

CDN,DCDN取消了中心的管理服务器和媒体服务器,将系统管理功能和媒体管理功能放在了各个PoP节点上,形成了完全分布式的体系结构.DCDN

没有取消Web服务器,主要是因为在不改变用户端的情况下,方便用户浏览媒体资源;而且Web服务器是的,不会影响系统管理和内容管理的分布式结构,也不参与动态负载分配,全网的动态负载分配由各个PoP节点协调完成.

DCDN工作过程可以分为以下几个阶段:首先用户登录到Web服务器上,根据请求者的IP地址查找本地对应关系表,定位到相应的邻近PoP节点.由于Web服务器不负责内容管理和全局动态负载分配,因此通过简单的热备份就可以保证可靠性;其次,在用户请求定位到PoP节点后,由PoP节点负责处理请求,不但要负责本地内容存储和管理,以及本地动态负载分配外,还要负责在全局范围内的对等PoP节点间进行动态负载均衡、内容分发、查找和管理.通过一系列的查找和比较,PoP节点将用户的请求定位到能够提供服务的最佳设备上;最后由选中PoP节点负责返回给用户服务设备的地址,从而建立连接传输数据.

因为取消了中心的媒体服务器,所有的内容管理功能都是由PoP节点相互协调完成.当内容提供商ICP向CDN提供媒体信息时,通过Web服务器指定到就近的PoP节点,将媒体信息存储到该节点,并将媒体信息记录在Web数据库中.

当用户发出请求,Web服务器会定位到本地PoP节点.此时,PoP节点如果没有请求的媒体资源,就开始采用查找算法定位能够提供媒体信息的PoP节点.这显然是P2P网络中的查找问题,很直接的方法是洪泛法,但是比较浪费骨干链路的带宽,与CDN的设计宗旨不符.在这里我们采用比较成熟且非常有效的

[11]

Chord算法,该算法通过Hash函数将资源平均分布在所有的参与节点中,它能够保证在O(lgN)步内找到相应内容,其中N为参与的节点数,并能够应对系统的动态变化(如图1所示).当通过异地PoP节点向本地用户传输媒体数据时,本地PoP节点会将其记录下来,存储在本地的存储设备上.

1 DCDN模型

DCDN由一个Web服务器和若干分布于网络边缘的PoP节点组成,如图1所示.相对于传统两级2 全局负载均衡策略

定位服务节点除了考虑内容因素外,还要考虑全局的负载均衡.在DCDN中,全局的动态负载均衡 第3期张国敏,等:基于性能测量的分布式CDN负载均衡策略249

图1 DCDN的体系结构和内容定位

Fig.1 ArchitectureofDCDNandcontentlocatingscenario

是由各个PoP节点相互协调来完成.各个PoP节点必须收集网络性能信息和PoP节点的服务性能信息,这是进行动态负载均衡的基础.

为了避免性能信息的两两传输带来的流量负担,也避免无序刷新引起的混乱,在DCDN中对基于

[12]

权标环的容错ping2pong算法进行修改,提出基于网络测量和服务性能测量的MBPP算法.通过测量网络链路性能信息和PoP节点服务性能信息,在每一个节点形成全局服务性能视图.L表示域间链路性能信息的集合,S表示服务性能的集合,因此全局性能视图为:

T=iG(L,S) I为PoP节点的集合II

为了后面描述的方便,我们将性能信息表示为F(x)函数:F(x)=Lx(,sj),定义域Ri={3li,lj4,sj}iII,jII,上式的变量为节点di与节点dj之间的链路性能和对端服务器sj的性能.ft为函数F(x)的一个实例值,也即一条用户服务连接.F(x)值的获取是算法的关键,其主要思想是:(1)

主干链路性能对服务的影响大大超过域内链路;链路性能可以采用递归抽样测量的方法获得sample-linkij;(2)链路性能perf-linkij变化是一个过程,采用自学习算法平滑剧烈变化(A为学习因子);(3)服务器性能Perfi对服务的影响超过链路性能,因此占有更大的权重;(4)负载均衡时本地优先,尽量提高本地性能权重以避免主干网流量;(5)链路性能和服务性能分别赋予不同权重,综合性能参数进行均衡servi=L#perf-linkij+K#perfi(L和K为各自所赋权重,经验值比例设置为1B3).

MBPP算法的工作过程如下:当该PoP节点拿到

权标ping,此时已收到传来的所有节点服务性能数据,首先用自己的当前性能数据刷新该列表,然后向下一点传输所有的性能数据,最后将权标ping传给下一节点,pong用来检测ping的丢失.用分布式程序设计语言DCDL

P(i:0..n-1)J=

[receive(t1,nbt1,F(t1))fromp((i-1)modn) updateserv(i)inperfList;y[mi=t1

y[nbt1:=(nbt1+1)modn); send(perflist)toP((i+1)modn); send(ping,nbping)toP((i+1)modn); send(pong,nbpong)toP((i-1)modn); ]

miXnbping y[mi:=nbping;

send(perfList)toP((i+1)modn); send(ping,nbping)toP((i+1)modn); ]

receive(pong,nbpong)formP((i+1)modn) y[mi=nbpong

y[send(ping,nbping)toP((i+1)modn);

send(pong,nbpong)toP((i-1)modn); ]

miXnbpongy[mi:=nbpong;

[13]

将算法描述如下:

send(pong,nbpong)toP((i-1)modn);

250 ]

meet(ping,pong)atpi

应 用 科 学 学 报第25卷

大量价格低廉的PC组成的海量存储系统存储.PoP管理服务器只负责将客户端的服务请求重定向到相应的主机上,由指定主机来实现与用户的点到点传

[14]

输.这种方式相对于RAID有明显的优势,不通过一个服务器与用户建立通信,这样减轻了服务的瓶颈.但是相应地增加了实现的难度,即一个PoP节点只有一个IP地址,而许多PC都会与用户建立连接.这里的数据传输可以由单一主机完成,但是交互信息还需要网关服务器和内容管理服务器的参与.网关服务器接收用户传来的交互信息后首先交付给内容管理服务器,由内容管理服务器识别交互主机,再与其进行通信.

3.1 内容的接收与缓存

PoP节点要加入DCDN,首先必须拥有认证种子,只有完成一次ping循环并得到当前所有PoP节点认证后才能加入.当加入到DCDN后,就可以与其他PoP节点交互内容资源.内容资源包括静态的和动态的,静态内容指文档、HTML网页、图片、视P音频媒体等资源;动态资源主要指系统运行过程中生成的一些音视频片段文件等.

PoP节点接收内容资源的方式有两种:一种是被动传输,一种是统计传输.被动传输是指当用户点击相应的内容资源时,如果临近PoP节点上没有存储该内容信息,而是由其他PoP节点向用户提供服务,此时会通知接入点的PoP节点接收存储该资源.统计传输是指通过代理缓存服务、透明代理缓存服务等方式来改善用户的响应时间,内容管理服务器根据制定的缓存策略(存储用户点击率最高的信息或根据对信息的分析选择是近期的热点信息)定期更新自己的内容.对于近期的热点资源将主动分发到全网的各个PoP节点,从而更有利于负载分散到边缘的原则,也加快了用户访问的响应速度.

PoP节点的网关服务器接收到媒体信息后,交付给内容管理服务器,由其通过目录服务记录所存储的内容信息.存储设备对于媒体数据的删除原则是根据用户访问媒体数据进行统计的,在一定时间内访问数量少于设定值的媒体数据将被删除.3.2 状态监控和性能监测

图2 PoP节点的结构及内容定位

y[send(ping,nbping)toP((i+1)modn); send(pong,nbpong)toP((i-1)modn); ] ]

main2programJ=[nbping:=1;nbpong:=-1;

mi:=0,0[i[n-1;+P(i:0..n-1)]

对链路性能的测量采用时延这一单一指标,对网络的侵扰最小,获取迅速实时性强.而网络其他性能的导出在PoP节点本地计算,对网络和其他服务器没有影响.而且在本地进行运算也很容易做到一致和收敛.在MBPP算法中,传输数据量只有性能列表,消息复杂与节点数目是一阶线性关系.采用MBPP算法使DCDN的可靠性也得到了提高.如果某一个PoP节点出现故障,MBPP会很快在全局范围内传播其故障信息(链路性能或服务器性能),全局负载均衡时就将此节点排除在外,由其他PoP节点来提供服务,解决了单点故障问题.

3 集群式PoP节点

DCDN中的PoP节点在物理上采用集群方式构成,在逻辑上一般是由PoP网关服务器、内容管理服务器和存储设备组成,如图2所示.PoP节点除了全局内容管理和负载均衡外,还要负责接收其他PoP节点转发过来的媒体资源,存储在本地的存储设备上,并建立资源的目录信息,进行维护和管理.当收到用户的请求时,在性能允许的情况下定位媒体资源,建立与用户的直接通信传输数据.

Fig.2 ArchitectureofPoPandcontentlocationg

scenarionode

网关服务器负责与外部节点建立通信,由于一个PoP节点只有一个IP地址,因此交互的报文只能由网关服务器接收.网关服务器也负责进行网络性能监测,主要测量PoP节点到邻近PoP节点的链路性能(RTT)和与用户之间的链路性能(时延抖动和 PoP点节点采用集群的方式后,媒体信息是由 第3期张国敏,等:基于性能测量的分布式CDN负载均衡策略251

应用层测量).网关服务器一方面将这些测量到的性能数据作为自己负载分配和内容定位的依据;另一方面作为F(x)值在MBPP算法中转发,从而形成全局性能视图.内容服务器负责监控内部的存储部件的状态,并评估各个设备的服务性能,当出现服务不能被满足时,及时更新监控的本地设备状态,并通告PoP节点的服务阈值和服务状态.3.3 本地负载均衡

本地负载均衡主要是采用动态负载均衡方式,具体过程如图2所示.当用户的请求(1)被指定到该PoP节点(2)后,PoP网关服务器将请求信息交付给内容管理服务器处理(3).内容管理服务器根据本身的目录信息查找请求内容的存储位置,如果存在该媒体信息的多个副本,则根据内容管理服务器监控的设备服务状态信息选择最佳的设备(4).

但是用户返回的交互信息不会直接传给服务设备,而是按PoP节点的唯一IP发给网关服务器(6),由其转发给内容服务器处理(7).内容服务器上由于负责分发请求并监视设备使用状态,因此保存了存储设备的连接的详细信息.所以内容服务器可以根据这些连接信息确定将收到的用户返回交互信息交给哪个存储设备的哪个应用进程(8).

[J].IEEEInternetComputing,2001,5(4):66-75.[2]NIJ,

DANNYH.

Large2scalecooperativecachingand

application2levelmulticastinmultimediacontentdeliverynetworks[J].IEEEComm,2005,43(5):98-105[3]JERNBERJ,VLASSOVV,GHODSIA,HARIDIS.DOH:a

content2deliverypeer2to2peernetwork[C]PPEuropean

ConferenceonParallelComputing,Germany,2006.[4]GHODSIA.Distributedk2arysystem:algorithmsfordistributedhashtable[D].StockholmSweder,KTH2RoyolInstituteof

technology,2006:23-28.

[5]GUMMADIKP,GUMMADIR,GRIBBLES,RATNASAMYS,

SHENRERS,STONICAI.TheimpactofDHTroutinggeometry

onresilienceandproximity[C]PPProcofthe2003ACMSIGCOMM,Karlsruhe,2003.8.

[6]FREEDMANMJ,FREUDENTHALE,MAZIERESD.Democratizing

contentpublicationwithcoral[C]PPProcofthe1stSymponNetworkedSystemsDesignandImplementation(NSDI),SanFrancisco,2004.

[7]SONGYJ,VENUGOPALANR,SIREREG.Optimalresource

utilizationincontentdistributionnetworks[EBPOL].http:PPwww.cs.cornell.ednPpeoplePegsPpoperslcobweb.pdfCornellUniversity,2005.

[8]ROWSTORNA,DRUSCHELP.Pastry:scalable,decentralized

objectlocationandroutingforlarge2scalepeer2to2peersystems[C]PPProcofIFIPPACMInternationalConferenceonDistr2ibutedSystemsPlatforms,Heidelberg,2001.

[9]ZHAOB,HUANGL,STRIBLINGJ,RHEAS,JOSEPHA,KUBJATOWICZJ.Tapestry:aresilientglobal2scaleoverlayfor

servicedeployment[J].IEEEJournalonSelectedAreasinCommunications,2004,22(1):41-53.[10]RATNASAMYS,FRANCISP,HADLEYM,KARPR.Ascalable

content2addressablenetwork[C]PPProcofACMSIGCOMM,SanDiego,CA,Aug.2001.

[11]STOICAI,MORRISR,KARGERD,KAOSHOEKF,BALAKRISHNAN

H.Chord:ascalablepeer2to2peerlookupserviceforInternetapplications[C]PPProcoftheACMSIGCOMM,2001.

[12]JOHNSONKL,CARRJF,DAYMS,KAOSHOEKF.The

measuredperformanceofcontentdistributionnetworks[C]PPProceedingsofthe5thInternationalWebCachingWorkshopandContentDeliveryWorkshop,2000:5.

[13]WUJie.Distributedsystemdesign[M].FloridaAtlanticUniversity:CRCPressLLC,1999:74.[14]PATTERSOND,GIBSONG,KATZR.ACaseforredundant

arraysofinexpensivedisks(RAID)[C]PPProcoftheACMSIGMOD,1988.

4 结 语

DCDN是在研发的Grid2CDN项目基础上,通过进一步的理论分析和优化而提出的.Grid2CDN实现了集群式PoP节点,并能采用被动接收、主动请求和

热点更新等方式复制资源,也实现了本地负载均衡.但是全局负载均衡采用的是集中式管理.本文在此基础上,提出并阐述了DCDN模型,设计实现了分布式节点的全局负载均衡策略.试验表明,相对于CobWeb和CoralCDN的负载均衡方法,由于MBPP能够获取全局网络及服务器性能信息,因此可以更加准确、实时地定位最佳服务提供点,并且通信开销很低.而且使DCDN具有良好的扩展性和可靠性.下一步主要对协议性能进行深入分析,进一步优化算法,并提高负载均衡的可靠性.参考文献:

[1]CRANORC,GREENM,KALMANEKC,SHURD,SIBALS.

Enhancedstreamingservicesinacontentdistributionnetwork

(编辑:曹培华)