种动态负载均衡的P2P应用层组播方案)

1、计算机科学2008V<?l. 35fc. 2一种动态负载均衡的P2P应用层组播方案和林龙新周蛊张凌叶昭华南理工大学广东省计算机网络重点实验室 广州510641）擠 要 基于结构化的P2P基础设彪，給出一种动态负載均衡的应用堪组膳方秦 DLBMSa和用Tapestry协哉 的路由刑瓷桂机制.设计了琏迟优化的组務转发掰姑构，象用跟节虽爲制的方选生成多棵不湘交的组曲转規期，棣据 负我的变化动态调节组播特发常戟耳以实现巾栽均箭和降低挥到组成贯节点的端到臨延迟。通址模叔卖验说明了此 方案崔平均控制贞截衣轉到端平均足迟才面的有放性.关摊词 组播，庭用恳组舞，对等岡塔，负嶽均葡A Dynamic Ix

2、iad Balancing P2P Application Layer Multicast SchemeLIN Long-Xin ZHOU Jie ZHANG Lig YE ZhaoGuangdortg Key 1 laboratory of Computer Network» South China Univ. oJ Teth f Guangzhou 510fi41 >Abstract This paper presents DLlSMSt a scalable and dynamir k>ad balancing application layer multicast

3、 scherne built on structured P2P substrate. DLHMS utilizes Tapestry? s routing and data location service to create delay optimized multicast delivery tree, optimizes the end-to-end delay between source and group menbers and achieves load balancing by splitting the DLHMS multicast delivery tree into

4、a set of disjoint multicast delivery trees and adjusting the number of multicast delivery trees dynamically according to the change of load. We compare DLBMS and Bayeux by imuhtLOrif and the results show that DLBMS had the obvious advantage in terms of end-to-end delay and load balancing.Keywords Mu

5、lticast, Application layer multicast + Peer to peer 1華金锁Eh国家刖3计划项目厲00兀坯珂帥計匚国家CNGI项目CNGP04-13-2T）j2005年好唯关阀鞭城璽点竟藏项冒“IPv6樓心路由器研发与产砧化角林龙新 博士研究生,主翌研究方向:应用恳组播.对等悶皓.JQ亦 副救授悌士.张 凌 教授,博士.叶 昭 博士研究生* Inad bahneing* 24 * 24 组桶是Internet中实现群组通信业势的关犍技术.对于 传统IPS!播数抿分组的复制、转发以及群组的背理都由路 由器完成 © 应用层组播（Application

6、Layer Mult2ast* ALM） 则利用« （Overlay Network）技术，在现有的IP啊络上 构建一个虚拟网辂+将组播功能从路由器转移到斓采统.与 】P组播相比.ALM的优势在于:组播服务部署容易可功蛊 适屜网堵条杵的变化，实现报务定制零.近来，对等网络 （PwrtorPwr, P2巧技术在许多领域取得了巨大成功.成为 了网辂研究的焦点*啓P网络具有自组织、扩展性好、容错陡 力强'完全分布式等特性.基于P2P网皓实现组播服务是当 前的研究熬点'出现了众多研究戒果.例如：Ba浮决S Scribe、SplitStream冈.CoolStreamin* 等

7、“这些方案有一 牛共性即在已经存在的结构化或若无结构化的P肿華础设 施之上构建组播迪信业等.本文提出了一种动态负载均衡的 应用层组播方案 <Dynamic Load Ejalancing P2P Multicast Scheme*DLHMS）.它基于Tapestry3协议构建的结梅化 P2P基础网堵,其主要冃的是希笙在P2F协同工作环境中冥 现一些宴时应用"DLBMS利用Tapestry的路由和定谊桃制 来生成延迟优化的组播转发树采用动态选择多个根节点的 方袪把单棵坦播转发拥分割成互不相交的多棵组播转发樨* 井根据负载的变化自动调商组播转发祢数目以实现动态负载 均衡和优牝源到组

8、应员节点的端到端延迟. TapestryTapestry是一种着名的基于分布戌哈希（Distributed Hash Table, DHT）方法的P2P协议，可用于形成FEP网络 其有良好的节点路由和资源定位性能.在Tapestry中*节点 代表P2P网堵中的对等主机资源对象代表网络中共皐的资 源"每牛节点和资源对象都对应一个唯一的标识分别为 Nodeld和0&利打氐 Nodeld和O&j啟£加属于樹同的命名空 间何表示为澎如心-评宀啊严的伽的数字序列，通过茸种 均匀的分布式哈希算沐如SHA1）生帆 其中沖代表序列 的怏度曲为b位二进制数表示的整数*瓦込 0

9、-1, 称为基（ha5e），川=（才P为Tapestry的葩名空间大小，称 生为N如d的电位后纲仃鼻1）.Tapestry的路由机制（Tapestry中每牛节点A都有-个 本地路由晩射表.路由晚射表包含K列（从第0列开始）.每 列有严个记录，每个记录为节点A的个邻居节点E的相 关宿息3的N如心的IP地址答鳥第j列的第*个记余 1 e卷宅L1）所代表邻居节点的N血L以片+ ju/yiiMJ）为后缀*武中为A的j拉后撮耳 1”当/=时用叙訂皿以“产为后毀.在Tapestry中.节点之 何的路曲通过后缀匹配的方式实现.路由过程中，第血3 "跳节点的Nodeld和目标节点的NMd至少有长度为

10、j 的后孃是棚同的，通过査询第j跳节点路由映射表的第j+l 列的邻居节点信息找到后皺的第j+1 f数字和目标节点 N皿k相同的邻居节点作为第j+1跳节点°進种路由机制 保证经过最大叽N跳之后任何节点都能够被找到.Tapestry的畫源发布和定位机制=在Tapestry中*每个 资湄对煞都和一个或多个称为“定位権”的节点相关联.为了在P2P网堀中发布贾源对象0存ITO的服务器S通过1丁 期try辭由机制以定位根为目标节点发布“位置消息S此消 息包含（Objectldruerldy映射。从S到宦位根的路往上 除S之外的所有节点都保存此映射信息，在资源对象査询 和定位过程中査向节点向目标资

11、嫌对象关联的定谊根节点 路由査询消息*如果此賂轻中的一个中闾节点洽好含有该资 源对象的位置信息那么査询消息将被直接转发到对应的服 务器岔否则，将 歩步靠近定位抿。査和消息到达定位根 节点可确保找到其位置信息+从而准确定位且标资源对象.2 DLBMS播树和动态负载均衡策略DLBME超一种渭指定应用层组播建血在Tapestry之 上.在会话骨理方面釆用和Rayeux同样的方法：在DIJ3MS 中-一个组播会话用二元组SessianNar. UID 唯一标识. 组播源将此二元组转化为160比特的（Jbjectid （即 Grpld） 创建一个以此Objectld为名宇的文件其中包含 组播会话的相关信

12、息。它被看成是Tapestry的资源对象， 组播源通过Tastry的资源发布机制把谏资源对靈发布到 对应的定位根*2.1 1MJWWS组播转童铜盹源指定的ALM方案中源到组成员节点的转发路径 的枚度在某种程度上按定了礁到组虑员节点的延迟,对于实 时应用，尽可能便组播转发树的探度在满足度釣柬的条井下 趙小越好"现有的P2P组播方案，数据转发树中包含了大量 的非组成B节点,而这些节点的存在增加了源到组成员节点 的数据传输延迟并且因为这些节点不皑组成员节点*在对等 网络中*这些节点随时都可能离开网给,这样会影响组播转发 树结构的稳定.因此.DLBN1S所构建的组播转发树不再包 含非组成员转

13、炭节点。在DI.BMS的组播转发树中*节点需 聲裸存的主要狀态信息有；该节点在组播转发树中所处的逻 辑“层气源处于最髙层，即第0层几谏节点的孩子节点信息 该节点的父亲节点信息。组成员节点的加人（JOIN it程伴 随着组播转发树的生城算法如下： 谡定源节点为5S是组播转发列的提.节点M（设捷 N如直为弧-诧宀如创要求加人组播组° M根据Ground通过Tapestry的资源对象定位机制 获得S的屮地址倍怠.直接向&境送JOIN请求消息° $报 据肖身花坦播转发树所处的逻辑"层"值来确定初始后墩对比 序列（层值为齢那么初始后繼对比序列为处叭T的為人

14、S 先杳看M Nodeld的如值.井检査自己的孩予节点列表中 是否Nodeld的第1个数字和相同的节点.如果没有. S就将M作为其孩子节点.并将M作为组播转发树层1中 阳域的代衣节点燃后回境成功的JOIN响应消息JOIN过 程结束.否则S向M回复車新启动JOIN过程的消息，苴中 包含Nodeld的第1个数字和為相同的S的孩子节点C的 相关信息.M继续向匚发送JO】N请求消息*C将查看M的 Nodeld的伽值来进行董似操柞° 如上的JOIN过程晟多经过n次迭代,M最聲会被放 置到组播转发树的一个合适位置.例如，在一个Tapestry网络中，设:base等于2 *节点的 No血坯表示为敢

15、血甌心W怕,1.假设节点时0为源节点 000,101.100,001为组戚员.按照如上算法先后加人到组播 组口戢石形成的组播转发树如圈I所示。图2基本树分割产生的组播森林图】中，E为源，稱圆表示节点带箭头的连线夜示树的 边，边上曲数字表示节点加人的次序，L0表示第0层，表 示第I层*第1圧包含节点00。和101,其中带F划线的0、1 表示不同的域级000作为树中第1层“旷域的代表节点J01 作为第I层域的代表节点口源的不同子树中包含的节点 的有相同后嬢.DLBMS组播转发树的毘大深度小于等于灵树所包含的节点只冇源$和组感员节点，不再包 含非组成员转发节点.由于每节点的孩子数最大为h赵. 因此节

16、点的鼠大出度不超过尿组播树中相邻节点通过定 期交互消息来保持联矗.当节点离开的时恢它需要向茸相邻 节点发送LEAVE消息引发相应过程来维持树结构的稳定, 具怵细节在此不再叙述.2.2 DLBMS动态负戟均衡策略在DLBMS中组播转发树的根节点需要处理所有组成 员的加人请求并转发所有数据分组”这将是大规檯扩展的瓶 颈井易造成单点失舷.为此+ DLHMS采用动恋树分割的方 法来泊除这种影响-基本思路如下I 把DLBMS产生的单棵组播转发牺分割成互不相交 的多个部分.每部分对应棵新的DLBMS组播转发树，这些 组播转发树组成组播森林*每棵树的很节点是Tapestry网 络中的非组成员节点.源把需嬰组

17、播的资源对象冥制到每棵 组播转发树的根节点.不同的根节点负贵自己所崔的组播转 发树的控制信息虹理和数据分组分发" 组播过程中组成员是动卷变化的，可能会造施节点在 同一棵组播转发樹的某牛分支聚集的情况。DLEMS把椭足 一定集集条件的分支分离出新的组播转发树，从而进一步优 化源到组成员节点的传输延迟和降低根节点的平均控制负 權节点之间以网状（mesh）结构组织在一底，菠此都拥 用一份相同的賣源对象和状态信息副本“通过信息交换以确 保此网狀结构的稳定.DLBMS树分割策略分为两步：第一 涉为基本树分割+第二步为动态榊分割.基本树分割算法崔DLBMS单树中+源赵即根节点）的所有孩子廿点的

18、曲记的他项互不相同.除根节点外，其它节点餓自然地彼 划分感多个不相交的分支°耙这些分支所包含的节点组成的 集合定义为民严卮严，创一山甞二屁出 包含的节 点的Nodeld 相同的刊值.基本树分割算法如下*游S从本地路由映射表的第0列中选取Nodeld利S 的1搅后蠻不同的出一】个节点怡与这器一 1个严节点组 成个初始根节点.* 24 | 维普资讯 $把要组播的资源对象O复制到其余的护一1个根 节点* 所有根节点通过Tapestry提供的资源对象发布机制 向Tapcstiy网蜡中境布对象CL 组曲员逋过Tapestry的賂由和定位机制找到和自已 的N如d具有相同如值的根节点，然后运用DL

19、BMS的 JOIN过程把自己加人到相应的组播转发钳中.图2给出了基本拥分割算法主成的2*棵组播转境树图 中图2中捕圆代表节点+椭圆内的数字代表该 节点的Nod沁蕊色背景的节点是根节点.根据DLBMS的JOIN过程,DLBMS产生的毎棵组播转 发树的根結点只有一个孩子节点*这一性质在讨论根节点失 效时起重要作用.动态树分割组成员节点的动态变化会琏咸在同一棵组播树屮出现节 点局部聚集的情况即在树的某些分支组成员节点相对軽集. 而另外一些分支又很稀疏.如果把摘足一定密集程僮的分支 单独分离出来组成新的姐播树可以进一步优化源列组成员 节点的传输延迟同时降低根廿点处理控制信息的幵销.LXUI 3卜rm3

20、(b)井割呛 | ijft 1+".-w图3动态树分割过程设在DLBM5的组播繰林甲某棵组播转发拥节点的分布 情况如图肌訪所示，组成员节点丸量聚集在节点如所在 的子轲中。若把M00所在的子树从组播转发鞫中分离出来7 组成新的组播转发树（如图3（b）所示几就可以进一步降低根 节点平均控制负载和源到组成员节点的传输延迟*配違参数maroonunibcr代表组播瘵林容许包含的 组播转发轴的躍大数目。max, member number 示每棵组 播转发树所包含的最大节点散乩只有当组播森林中组播转 发树数目小于nux_r0Ot_numrP某棵组播转发树所包含的 组成员节点数目大于mqx_xn

21、cmbcr_number且谏组播转播转 绘树某个廿点的出度大于等于给定的临界值时启动动态 树分割算法.算法描述如下： 组嵐员加入到某棵殂播转发树后，相关廿点检査自己 的出度，当出度大于等于毋时它向对应恨节点发送消息，其 中包含节点Nodeld所琏的层、出度、所辖成员数等參数，供 树分割算法进行分割决策口 如皋当前俎播转发树满足前述的动蠡梢分割条件，根 节点选择出度大于等于俎且“层”值最小的节点所在的分支 进行分割，称这样的节点为“分削节点二 根节点向分割节点F发送TREEPARTlTONReq 消息，要求F选择新的组播转发树的根。 设F的层值为仁P从本地路由映射表中选取和官已 的位后緞相同的非

22、组成员且非根节点作为新的组播转发树 的根，井把此节点的相关倍息通过TREE PARTITION,Rsp 消息发送给当前的根节点. 当前根节点自己或者依靠已存在的其他帳节点把需 要组播的资源对象宜制到新的根冇点上，新的根节点把蠹源 对象发布厠Tapestry网络* 把P所衽的子树迁移刪新的根节点上.图3是 个动态树分割的例子.动态树分割后，设分割 节点P的层值为仁当新的组成员M加人到被分割出来的组 播转发树时.其JO】W过程中M和根节点的后缀对比序列的 长度等于匚如前所述的基本树分割和动鑫树分割产生的组播森林的 每棵组聲转发樽的根节点只有一个孩子+这些根节点之间组 织底网伏结构，彼此郁拥用-份相

23、同的资源对象和狀态信息 副琲.每个根节点都保存“报节点网”的信息并目把这些信 慝定期通知给各口的崔子节点"根节点尖效处理组播转岌树的根节点是Tapestry网堆中的节点，这些根 节点可能会矢效（如粮节点退出Tapestry网第人乖节给出 处理根节点矢效的机制，具体策略为； 失效幅节点检测:通过相节点网”宦期检测根节点的 存活情况，或通过组成员汇报的方式来枪测根节点是否失效。 临时替代根冇点；当某个根节点失效时，越孩子节点 银据自身保存的“根节点网片信息'先措定厨外一个有妓的报 节点作为梵貸节点，即“临时替代根节点J以避免由于根笔点 失效而导致的组播会话中斷. 新组播转发树的构

24、造;临时替代根节点把失效根节点 的菽子节点作为动态树分割算虑中的分割节点.按照动蛊树 片割的算隆选择一个新的根节点以替代失效根节点'并重新 构逍组播转发树*图4给出一牛根苗点xxxO失效后的处理过程，节点 sk为临时替代根节点，yyyO为新构造的组播转发树的根 节鼠%? n卡点喪效刷g “节应心久效坨默刁氐“了$的雀“成丹卢图4根节点换复3性能评价3.1评价摩为了VFfft DLBMS的有牧性，就以下曲个性能鑫数将其 分别与Bayeux A案进行比较t 根节"点的平均控制负载（Root Average Control Load* RACL）.在组破员加人组播组过程申，毎根节点

25、需要处理的 控制消息的平均数日. 平均相对延迟损耗（Average Rehtiw Delay Penalty, ARDP儿鱒到每亍组成员节点的相对传输廷迟损耗RD巧时 的平均在应用层组播中，漁到一个组成园节点的组播通 信延迟通常要大于它们之间的单播砸迟.RDP描述源到组 成员节点的实际传输延迟和它们之间的单播延迟的比值3,2仿鼻实验设计参考相关P2P和应用层组福仿真器源代码，用C+语 言设计实现了一牛可仿宜Baycux和DLBMS协议的离散事 件模拟仿真器°用GTTME网络拓扑发生器产生由20000 牛节点组成的Trit-Stub类型的髓机网络拓扑"节点的单 播路由按照最短

26、路径算法设f仁Tapestry网的命名空间大小 为16384 （卩hbasc为4°从20000个节点申随机选取）6384 个节点件为丁apcstiy节点&实有效性测试.根据不同组播转发树的 数目测试DLBM3左RMX和ARDP等方面的有效性.为 保证可以分割岀足聊多的组播转发树*设定组播组的规模为 4000个组成员.max-mernber-nuinber的値为80,节点出度临 界值個为氐 通过调节墨数max_txx>t_number来限定每次产 生的根节点数冃（组播姐规模和m值的选取棵证町以产生足 够多的分割节点人实艶二t DLBMS參树、Rayeux以及DI.BMS单

27、树在 RACL和ARDF等方面的性能比较*纲播组规模的最小值 为200.以朗0的步长連如最大值3000,设置max. mot ”.number 值为 201 max_meniber_number 值为 20G，节点出度 临界值忍为九玄3实验结躍与分析图5 DLBMS有效性实验卡4t話毎離慣曲隈當A遇圈6 RACL对比实验*.hlms *w-Afrap图了 ARDP对比兵验实驰一测试结果如图5所示'横坐标表示测试中根节点 数目，左侧纵塑标表示RACL的值，右儁纵坐标我示ARDP 的值.当根节点数目为1时，即为DLBMS单棵组播转炭树 的悄形（当根节点数目为鎳即氐强）时*为DIMS的基本树

28、 分割情羽；当根节点数目大于4时为DIJ3MS动态树分割情 形.实验表明在组捲组规模确定的情况下圈着根节点数目 的增加+ RACL明显降低* ARDP也逐步降低'这表明DLBMS 在负载分担和优化延迟方面是有皱的.实验二中对于RACL的对比测试结果如图6所示.橫 醴标优表组播组的规模纵塞标表示RACL的值*实验表 聘DLBMS在组播组规棋较小的悄况下组嵐员数小于 1500）,它和Bsyeux静态多根方案每个抿节点所桑担的控制 负载基本接近"这是因为此时D35还外于基本树分割状 态*所产生的分担根节点数目和同*当组播组规模 逐新增大时*Dl,BhlS毎个根节点平均控制值裁耍開显

29、低于 曲严u独这超因为此时动态树分割算送发挥柞用由于 DLBMS 形只有一棵组播转发树，因哉其在RACE方 面性能垠豊。实验二中/VRDF的对比测试结果如图了所示. 对于ARDF,DLBMS优于DI.BMS单树并明显优于Ba尸 euH*堵束语 基于rapStry基础架构给出动态负载均衡的 应用层组播方案一 DLBMH不同于其他的P2P组播方案， DLBMS利用了 Tapestry协饮特性构建了不再包含非组曲员 节点的薙迟优化的组補转发树,通过动态选择Tapestry网络 中的非组成员节点作为组播转发树的报节点、根据组播组规 摸的变化悄况自动调整组播转发树的数口来实现控制负載的 动态平衡和忧化源到组成员节点的端到趙延迟仿真结果表 明了它的冇效性.所给方案适合于在P2P环境中开脛对延 迟有较高要事的组播应用.崔P2P网堵中引入组播技术将 对改善当前P2P环境下一感业务進成的网络拥塞疳一定帮 助.下一步的工作垂点足把节点的转炭能力和带宽条杵进行 综合薄虑*以构造更有敬更鲁棒的组播转发结构井转化为濟 统在实际网蜡中验证.参考文献1 Zhuang SQ Zhao BY, Joseph A DP et al. Bayeux； An architectur