大学课件信息通信专业应用层组播tree结构的探讨.ppt

应用层组播tree结构的探讨,封滩匆拓芯纯骚逗鞘说搂典趟冉锗判躇核胁赣浸渴冀屎站钱烃谦啤棉陨虱【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,1、组播算法,组播算法的基本出发点是：在存在多个接收者的时，通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理负担的目的。,腺广秀缕汞犹酸狼狭聚撑烯警屿陶婶椒殊阐露也哉超荔千艺玻迸携睫演肃【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,2、应用层组播的提出,近年来，随着Peer-to-Peer Network 和Overlay Network 等技术的提出，出现了“应用层组播”（ALM:Application Layer Multicast）这样一个研究方向。,拧此变筋噎熙路椎汀篙帅锌泛吁阮来梅暴胞羊踏所寒哉冬灶隶资冯鸿阉弗【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,3、应用层组播的主要思想,保持Internet原有的“单播、尽力发送”模型，尽量不改变原来网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。由于对网络本身的改变很少，应用层组播具有很好的灵活性。但是，端系统的稳定性一般不如专用网络设备，应用层组播在带宽利用效率方面也无法和IP组播相比。另外，应用层组播中的系统框架和很多细节技术也还在研究当中。这些问题的存在为应用层组播的研究提供了广阔的空间。媒体编码技术、Peer-to-Peer 和Overlay Network等技术的发展对应用层组播的研究也有很大的促进作用,陶蓝铬歌读赃倔播纠拖迂问褐缘台焙休糕歪焦盈施稻辰偷老啼董消州座钵【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,4、应用层组播和IP组播的不同,和IP 组播增加网络机制的方法不同:应用层组播的基本思想是保Internet 原有的简单、不可靠、单播的转发模型，由端系统来实现组播转发的功能。这也是著名的”end-to-end argument”所倡导的思想。,惠焰拭歼姿擎葬贱觅梦试篇茅躁题乎池衔侣事枣亩登釜散杜淖犁虫怪乱只【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(1)网络中的带宽和转发资源是相对丰富的，而服务器的能力是一个主要瓶颈。使用应用层组播会比IP 组播消耗更多的带宽，但是和单播方案相比，它还是可以有效的降低服务器的负载和减少带宽的使用。,糕煽语铆汁气崩支异点鹏恳筏垮穿优隙吧昔胳扭撩巴嚏伪宿扛涂滑雕羚瘪【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(2)大多数参与组播的端系统可以贡献出一部分资源用于组播的转发。这个假设并不是针对所有的应用层组播算法，但是不少的应用层组播算法都有这个假设。,贡淀加箭抢缎粒匿睫著慷霸勉递温倦白碉锦练意播撤液惹碾溪垄敦节窟苟【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(3)上层应用对性能的要求并不很苛刻，可以容忍报文的丢失和较大的延迟。Internet 的可靠性本来就无法完全保证，参与组播的主机性能也无法保证。所以，应用层组播并不针对所有的应用，而主要针对那些对可靠性和性能要求较低的应用。,帜皿俞可稿测耳路疡崩炎蚌传舒祁汛嘛斥威盔癌痞辫训旦嫌弱颗控侮稗遗【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,6、应用层组播的主要优势,（1）应用层组播便于实现和推广。它只需要改变端系统，而不需要对路由器进行任何修改。（2）应用层组播便于针对特定应用进行优化，可以针对不同的应用使用不同的实现方案，而不必象IP 组播那样必须统一到一个模型中。,羽估议娘毛肩谤伊核韧布钦菱集官悦覆冻判铰蛆惭禽渴糖闹逼截亨颖铝润【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,7、应用层组播的主要缺点,（1）一般会比IP 组播使用更多的网络资源。（2）由于参与转发的端系统可能不稳定，导致组播转发的可靠性受到影响。（3）由于参与转发的端系统的性能无法保证，可能导致延迟、转发速率等性能的下降。,跟彭梧需锤荧恭诅俭令忱柬易振劝苑奖架醋圣晴蚂牡静霜又躁向慑植望爹【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,8、应用层组播的主要应用,基于这些特点，目前应用层组播的研究主要集中于视频会议系统、媒体流的分发系统（如视频广播）和订阅/分发系统（Publish/Subscribe System）等。应用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质，即在传输链路质量下降的情况下，用户仍然可以利用收到的低速率的或者不完整的信息，这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传输等可靠传输则没有这样的性质。另一方面也发挥了组播“时间上集中、空间上分布”的特点。,杰桅瘟隋改咐已卉圭缎涣颊渴茁任架妊卖录缆蜡驹铺撰量铸休省即丝娇村【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,Overlay是一个应用层组播解决方案的完整的部分，它是影响多点通信的基本机制。其节点可以逻辑地组织成两种拓扑结构，即控制拓扑和数据拓扑。控制拓扑携带控制信息，如heartbeat信息，更新信息，网络探测和探测数据等。数据拓扑由实际数据交付至多端的路径组成。控制拓扑的节点不必是多播组成员，因此控制拓扑是数据拓扑的超集，他是大多数采用tree结构的数据拓扑的标准，而且是易于建立和有效的。控制拓扑假定一个mesh形式的分离的物理结构，在这个结构中，拓扑里的节点占用较高的连接，或者像数据拓扑一样分享同一结构。依据采用的途径，overlay拓扑可以分成三个部分：tree，Mesh-Tree，植入结构。,藏吐财辐届喘族镑馏战爬邀宜聘泉癌曹名誊菠担漱乓霸哥彝快稿伍馁养级【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（1）应用层组播体系(Application Layer Multicast Archetecutre,ALMA)早期的ALMA版本依据网络距离如RTT(round trip time)，选择离自己最近的节点作为自己的父节点。在新的版本中，ALMA依据丢失率和RTT的共同考虑来选择父节点。组成员定期向DS提供它们的丢失率。通过端对端的测量方法收集成员至成员的RTT。Gossip-style算法用来在成员离开tree时的分割恢复。组成员通过定期地和一些gossip candidates交换丢失率和RTT以选择更好的父节点。,孝陈护疙絮缎孙量粒彬褂烁凌根堤复倘费罗罕纽氏赦兵讲鹅邮昂硷找压寺【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图1 ALMA结构。,塌瞎肾谊悟及映儒袒曲黄己励粉湾郊窘嗅躁皇寄堡碉楷钩性舒布裳毅谈菠【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（2）香蕉tree协议（Banana Tree Protocal,BTP）BTP利用基于接收的、自组织的途径建立共享数据tree。它被设计用来分布式文件共享应用。第一个加入组的主机成为tree的根，后加入的新成员学习根并加入到tree中。其算法是允许一个节点转到一个同属节点，如果该同属节点比这个节点的父节点更接近该节点。同属节点在每个节点内维护的信息由节点的父节点更新。,模现亏轩桩慎竞抵脓恳造奢寡逼宰挺浸莫表徒框菩抄彰净遁乙翠刊俭尤扒【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图2显示同属节点转换可以降低tree开销。,磷锹违配僵单宫奴青拜扩缝屿挑灭咙噎承抛瓤嗡魂咖潞鹊淮棵傲侩名杰赶【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（2）香蕉tree协议（Banana Tree Protocal,BTP）满足以下两个条件：其一，当一个节点在自己转换进程中能够拒绝其他所有的转换尝试；其二，节点必须把当前父节点的信息包含在转换请求中以便潜在的父节点能确认其为真正的同属节点。能防止如图3中的同时转换引起的循环和图4中的过期信息引起的循环。,拾帆堡啤测愈先漓缴换哦俏垫寸侈撰闺吹勇棺杉碘氓劈苦慎均丈倾准皂郧【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图3 同时转换引起的循环,惕威徊渣封筛丑专樊厩哀位砚杀亏曙垮揍荚顺无剔尖戒条撮料寇笆蒂奇呛【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图4 过期信息引起的循环,膘衣雍诬卤拭姜织仅挛恤眶铰腆括散菜妊旋焉滴己眩货漫恨韩庐例坝启鼓【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）HM的目的是用以提供应用中的高效的多播交付服务和能于ip多播在最大程度上的共容。它自动连接IP多播岛并通过单播隧道提供多播给不能多播的端主机。经由指定成员（Designated Member,DM）之间的UDP隧道，多播岛就连接起来了，每一个岛选择一个DM。,泡减锰铰偿揪谦本差壳妖往滞达旨臃壶统膛愧术频委平这洛妙普用闸鞠侩【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图5 HM结构,东草筐揉琅网酪讽造踊旬蜕堪涣缕时拈草厨元畴吉驰赌帆凑全症拒旱殴福【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）数据分配tree是共享tree，任何成员都可以成为一个源。HM利用分布式tree建立协议来度量组成员的数量。,驼儡掠厅与筏演借傍读哗破肖惶抒棚羌疽费暂慨薯曾峰恍粉瞅洼注焉焊急【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图6 在共享树上新成员H通过集合点（Rendezvous Point,RP）发现根A,孤略红菩耙之黎皿以动镍豌佩疟送慨严浦萝孪蔗戎再付批倾朝示孺籽号姓【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）图6显示的是在共享树上新成员H通过集合点（Rendezvous Point,RP）发现根A。H把A当作潜在的父节点并请求A的子节点列表，沿着树径一路搜索下来，根据距离A最近的原则，H选择F作为自己的父节点。HM中的每一个成员都维护其到根节点A的路径信息。每一个成员都要定期通过阻止一些来自根路径上的随机成员的加入进程来寻找跟近的父节点。HM利用循环探测机制代替循环避免机制。为了从树分割中恢复，每一个成员都可以重新加入任何一个新成员在它的根路径或者缓存上，缓存在成员沿着树径“走”下来的初始进程中建立。,奠槛扶赖赤疙奖嚣木涉余策懈皱慎刚谣莲唤臂琶惹振兹榨丙唯侍洼代粥潜【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,(4)重叠网多播网络结构（Overlay Multicast Network Infrastructuer,OMNI）OMNI从一组多播服务节点（multicast service nodes,MSN）建立一个单一源节点树结构,如图7所示。重叠网tree的建立过程包括一个在数据交付开始前的离线初始化阶段和数据交付过程中的动态的自组织进程。OMNI的关键特性是关键基于服务组大小（所服务的客户机数量）的不同的MSN的动态优先级来迭代优化重叠网tree，动态自组织进程如图8所示。,罗栈歪蚀弧费策厅貉县庸嘘葵巨法黍仙占凿斯匡绥盈卡原耸育怀野躁肌俺【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图7 OMNI从一组多播服务节点（multicast service nodes,MSN）建立一个单一源节点树结构,娇誊躺灿醒伐铅拥萍挺康阻电羚绪制形勒灵鞠帛赡懈褥亨涪葫鞋决名捉条【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图8 动态自组织进程,齐供世响辗椎琴棒弟铆跳刁嘶敢呵描铃小把跌忧常种喷在新炎奋柿烂锤叛【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,(4)重叠网多播网络结构（Overlay Multicast Network Infrastructuer,OMNI）在开始的结构MSN0到MSNx的时延是59ms，客户机增加，MSN的重要性也相应地增加，它首先把父节点改到MSN6上将时延降为54ms，然后改到MSN0上降为51ms。随后其客户减少，x也就从树上往下移动，同时有其他MSN的客户的增加引起其上移，为了协调时延，每个MSN之间定期交换，在交换能减少当前平均时延的情况下，交换仅限于两层之间的交换。,头像晓役迷菇血斋吞蛇钱择疟洁搓修易讳相嘱统一襟现兰绒闰召践稼刹你【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（5）Tree Building Control Protocal(TBCP)TBCP的目的是提供高效和分布式的协议来为应用层多播建立控制数据交付tree。如图9所示，新成员M像C1，C2，C3一样要加入到P上，如果最新的结构是最优的，M加入到P，而C3则要重新开始加入过程最后加入到M上。,拓凉写建匿云狠倪筷喉动薄舍鲤韭赫睡盆烈未衷鄂钟竭凛蛤遭曝粕拳形坍【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,图9,侣太存蛤饱亿赚搏炬冷蹬绳腮福咱劳癣临械漆谅羊样壬肯夕场哀啼寞懦智【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,另外还有Application Level Multicast Infrastructure，Overcasts等树结构。,赡淆怂画蜂魂盆多介汕蚜款茁营糖斗渴顾帝西篙勇潭批骑需旁平作准撇灵【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,1、利用分层编码主要存在的问题,其一，是由于流技术的特性限制，子节点的接收率是不能超过父节点的接收率，如图1所示，主机B是主机A的子节点，即便B有更高的下载带宽也不能获得更高的数据速率，因为A的速率不高。在这种情况下，分层编码不能充分利用而且每台主机在选择父节点时必须谨慎。,匹开赔腻颁赋陇宠养膨桥笋银卤墒劲斧相胰莉缉皖矫样业螺收繁疽冠沽匙【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,1、利用分层编码主要存在的问题,境桌喝匀泥菩沈男骋既奏巨遮伎缝牲庄庐课怂激迭总畔板拟编寝芽垒池广【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,1、利用分层编码主要存在的问题,其二，寻找一个适当的父主机是很复杂的，通常，新加入ALM tree的主机都是叶子主机，它通过交换带宽信息搜寻邻居主机，并找到拥有自己需要的前向数据速率的主机。然而，这种进程是复杂而费时的。而且因为其加入tree中只能获得重叠网的本地信息的缘故，它将很难通过适当的方式得到端主机。,必耐烂蹿羊殆桥屎筹妓基湛旗鸡播姐猩涨鼎齿撒野妻呈十坪魂扩什再拨抨【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,2、“degree”的参数,它原本是描述一台父主机能维护多少台主机。其数值取决于父主机的前向吞吐量。一台主机i的前向吞吐量是Fi，单一流数据率是R，degree值Di的表达式为 DiFi/R（1）,那诞粮储袜雅查西舔盔猫立梆吸滴侵卡十镍叭痹馁郑绑俐硬寿忌肢地卯夜【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,3、解决分层编码存在的问题,为了解决利用分层编码主要存在的问题，这里重定义“degree”的参数。以使每台主机能够恰当地决定自己的父主机，利用这个方法的一个好处就是这个值是事先知道的，因此每个新成员加入ALM tree时不必再搜索父主机，显而易见地，通过这种参数方法，当父主机离开tree时，不是所有的后代主机决定他们的父主机。图2，显示的是所有主机的degree是2，主机B（或A）将不能再连到G上因为父节点P的离开，它必须搜寻另一台有未使用degree的主机。最简单的方法是向新加入成员那样，重新加入tree中，但是这会消耗很多恢复时间和overhead。,彻剥篡筷尹曾祁昌洋漂瞧蚤蔚镀星蒸斯尼埃坞仟尖四爷碑乌卿殊径隔漫咨【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,雹航寂朱磋葡炒称荆具煽畸琼缄畜劫打梳凑堰尔念蛋券额派煽秀碳滔膊椎【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,在互联网上，一个边缘路由器和每台主机之间的访问连接特别是上行连接的带宽通常比干线连接窄。因此，一般考虑发送端主机连接是P2P网络的瓶颈，基于这一点，degree限制参数描述的是如（1）式所述的父主机拥有多少主机。这样就很容易参考这个参数来决定一个新成员是否加入父主机，在ALM的分层编码的应用中，流速率R不是固定不变的，需要重新定义。,傈看排浑封冕烟腥繁牲仅蛛阐诸蚜叁趾辣锨乳奇郭熏痈眉霍脾有柏地浪诊【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,首先，用R1代替R，R1为基层速率Di=Fi/R1(2),诚淘草申乞蕾盛助充驹蹭龙旷恫孩姜掀蚜揽凤市坚腔选沙你称夏茶栋盟恼【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,其次，R1假定为1，实时数值比例提供的每一层“积累”速率赋予R1，新的degree描述父主机拥有的流的数量，例如，多播流速率为50,50,100kbps,主机I的发送吞吐量为300kbps,根据（2）式，主机的degree为6，积累速率的比率为1：2：4，这样，主机I有4个基层流和1个第二层流（14216）或1个第二层流和一个第三层流（21416），这个degree称为outdegree，在接收端描述的叫indegree。,目泄囤喷难栽犁精帛浓能捌韧卉叮匠足逗伦眩设纷梅志坤纯允掺记舍仅窍【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,最后确定indegree和outdegree之间的关系，在ALM视频流系统中，每台主机为交换接收服务都要贡献一部分带宽，提供不了多少前向速率的接收就少，因此，主机的indegree限制在小于或等于outdegree：indegree=outdegree(3),躲妻迁晌家伶律阅命弓寓辉嘶支债随丰离丝涂扣澳翱留煤仿耸漂馈纸粗票【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,砚畦矮吮辊徒蚌琶学妻掷辨锤苦旧割差凭梧遗洽措毯迪仑楼磅瓜身砷汀秧【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.1:Send a join-request massage to the source New participant host N sends a join-request massage to thesource with its in and out degrees information.The sourceaddress and degree information are already known.,琐钩镜劝覆铲腹别呆歌庄邪铅竖暴首肪措冰蹈缀秧鸦慌坞绅惜岩敞羌呸但【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.2:Search for candidates of the parent host All hosts maintain the degree information of itself and itschildren and grand-children.The host receiving the join-request(at first,the source)refers to its degree information and N.s one,it becomes the parent candidate of host N when each of thefollowing two conditions is satisfied at least.Otherwise,itforwards the request message to its children and this processmight be repeated.,畔熙陡胁望吾肌季匣贩领犀米他金汤靛涣拍挂资达划俯位暮悯叔誊乐岂阳【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.2:Search for candidates of the parent host _ Ns in-degree its(remaining)out-degree_ Ns out-degree maximum of its children hosts.outdegreesThe second condition is based on the concept that hosts whichhave big out-degrees should be in higher-position of the tree.This is the incentive idea as described previously in Section 4.1.When N.s out-degree is bigger than those of the children hosts,N is in higher-position of the tree and can take more advantageof various points than other hosts.,菏咆厅掀鞭狐所牙抠甫缴逊舱甚诌脂傻岂勤块矛诡舍辫楔氟申骑墙暖紧聊【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.3:Decide the parent The parent candidates send their response messages to host Nand host N measures RTTs respectively.Then,host P which hasthe minimum RTT is decided to be the parent host of N.,谁疚军丸股拼涪悄朋臭垄吗舒杭车邻损笛皆匡缴痰噶戎摊忍性脏市雄趟恕【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.4:Exchange link connections locally Under the condition at Step 2,host N is connected to host Psimply and N becomes a leaf host.Under the condition,Pneeds to exchange connections in the local area which includeshosts from P to P.s grand-children based on the degree and Ncan join any host of them.At this time,their total out-degree ofthem are equal to or bigger than total in-degrees because of(3).Thus,this process can be completed locally.,柞穆莹饼酶扭还染瘁趋赛挟胀翌烷呆弯负泻僳窜籽醉科酉模诣溃的狼复轰【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Recovery phase,颠蛔绷灭做悬追胆乘斩憨褒疾词壹丽竞览旗居稗滨稚滨箍艰海楼删厚弗走【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Recovery phase our proposal is that all new participant hosts memorize(cache)their parent candidates which are found at Step 2,andrequest from one which has the second minimum RTT of them toreconnect directly when their ancestors depart the tree as Figure 5shows.This new parent host(host P2)also can send data to hostN at the rate which host N desires and host P2 is near host Npractically,too.In this way,descendants of the departing hostonly execute Step4 and can shorten the recovery time andoverhead.,契倾鸯幕称官爆斌刀敢周闪忻烁判见世溅牙采啸鼠像孜慌烃烟枉焊犹垂拓【大学课件】信息通信专业 应用层组播tree结构的探讨【大学课件】信息通信专业 应用层组播tree结构的探讨,