实时流媒体传输的数据重叠网络

CoolStreaming/DONet:实时流媒体传输的数据重叠网络作者:XinyanZhang,JiangchuanLiu,BoLi,Tak-ShingPeterYum翻译:默难(monnandxgmailx).DriftingLeaves(driftingleavesxyahoox)原文参见:本文其他部分参见一三78.aspx摘要

(本节翻译:DriftingLeaves)本文描述了DONet---一种用于流媒体的数据驱动网络.DONet的核心操作非常简单:每一个结点与一组伙伴周期性地交换数据可用性信息,从一个或多个伙伴那里接收自己所没有的数据,并把自己所拥有的数据提供给需要的伙伴.我们将着重分析这种数据驱动设计的三种突出特性:(1)易于实现,它不需要构建或维护一个复杂的全局结构;(2)高效,数据的传递方向是依照数据的可用性信息而动态改变的,而不是被限制在特定的方向上;(3)健壮,允许结点的伙伴关系在众多提供者中作出适应变化的快速转换.

这篇文章将会通篇分析DONet在有限延迟下的可扩展性,而且也会考虑到实现DONet时所面临的一些实际挑战,并在此基础上提出一个有效的成员关系和伙伴关系管理算法,以及一个能完成实时且连续播放流内容的智能调度算法.通过Planetlab已经在大范围内评估了DONet的性能.这些实验几乎包括了Planetlab的所有有效结点.实验结果表明DONet甚至能够在复杂的网络条件下达到很好的流质量.此外,控制所带来的额外开销和传输延迟都可以保持在很低的水平上.在2004年5月30日,一个基于Internet的DONet的实现发布了.它已经吸引了超过30000的用户并且在一些高峰时间创下了4000人同时在线的记录.这篇论文将会讨论关于CoolStreaming设计的关键问题,并且描述一些这次大范围测试中的有趣现象.具体来说,网络范围越大,被传送的流的质量将会越好.I.概述

(本节翻译:DriftingLeaves)随着宽带接入的普及化,多媒体服务对用户来说变得日益重要,并且已经成为今天Internet流量的重要组成部分.许多诸如网络电视,新闻广播的多媒体应用都涉及到把流媒体从源头传送给大量用户的过程.对这些应用来说,IP多播也许是最有效的途径;然而它的扩展却因为许多现实上的和政治上的因素而受到限制,例如缺乏动力去安装具有多播能力的路由来承担多播流量.因此研究者们开始关注应用层上的解决方案---通过参与者的合作来建立一个在单播通道之外的重叠网络,这些参与者也被称作重叠网络结点(OverlayNode),那么在此基础上,就可以通过结点之间的数据依赖关系,实现所谓的多播.作为IP多播的替代方案,开始时许多网络构建算法大多使用树结构来实现数据传递.虽然这种方案能够像IP多播一样,与专用基础路由(DedicatedInfrastructureRouters)很好的搭配,但是却经常会与带有动态结点的应用层网络搭配错误.而且自主网络结点会轻易地崩溃或离开,因此树结构是高度易损的.而这一问题在对带宽和连续性都有很高要求的流传输中,显得更加严重.同时虽然像网孔和森林这样的复杂结构能部分地解决问题,但其本身的实现却过于复杂,而且经常缺乏可扩展性.从另一个角度讲,把多播功能移植到应用层同样会导致更大的弹性;具体来说,所有的结点都有很强的缓冲能力并且能够灵活,智能地决定数据的传输方向.因此文章中提出了一个以数据为中心的(Data-centric)设计方案---一个结点总是向那些需要数据的结点传送数据,而它们之间没有诸如父子关系,内部外部关系和上行流下行流关系.换句话说,是数据的可用性信息引导着数据的流向,而不是一个特殊的网络结构约束了数据的流向.这种数据中心的设计将会更加适应具有高动态的结点的网络.尤其是考虑到一个半静态的结构,无论多么有效,总是会因为结点的动态而处于次优的状态.基于这样的目标,本文描述了DONet---一个数据驱动的重叠网络,而其中的核心操作非常简单:每一个结点与一组伙伴周期性地交换数据可用性信息,从一个或多个伙伴那里接收自己所没有的数据,并把自己所拥有的数据提供给需要的伙伴.我们将着重分析这种数据驱动设计的三种突出特性:(1)易于实现,它不需要构建并维护一个复杂的全局结构;(2)高效,数据的传递方向是依照数据的可用性信息而动态改变的,而不是被限制在特定的方向上;(3)健壮的,有弹性的,允许结点的伙伴关系在众多提供者中作出适应变化的快速转换.此外,关于结果的分析显示出了网络半径与网络大小的逻辑关系,这也说明了DONet能够在有限延迟的情况下进行扩展.为了实现传输实时流媒体的数据驱动网络,大量的实际问题需要考虑.在本文中,将要讨论DONet中的若干关键问题.包括伙伴关系的建立,数据可用性信息的编码和交换,以及视频数据是如何在伙伴间被提供和获得的.这里将要提出一套可扩展的成员关系和伙伴关系的管理算法和一个智能调度算法,这些方案将会在使用较低控制开销的情况下,为中高带宽用户提供高效连续的流传输,同时平稳地将传输负载分配到正在参与的结点中,并使结点与异构网络相适应.通过Planetlab已经在大范围内评估了DONet的性能.这些实验几乎动用了Planetlab跨越五大洲的所有可用结点.实验结果表明DONet在流速率和播放连续性上能达到很高的要求.此外,控制所带来的额外开销和传输延迟都可以保持在很低的水平上.根据当前掌握的材料,全球范围的实验很少在文献中提及.为此文章中列出了在实验当中遇到的几个典型问题.并讨论了影响实验结果和可能在将来影响PlanetLab发展的因素.最后,在2004年5月30日,一个公开的,基于Internet的DONet实现---CoolStreaming发布了,它已经能够播放由一个免费视频服务器所提供的实时体育节目,这个软件最初只吸引了20个用户,但是截至本文发布,超过30000的用户(从独立IP的统计上看)已经使用过这个流媒体软件,在一些高峰时间甚至达到4000多用户同时在线.先前的统计结果和用户的反馈是十分鼓舞人心的,这也说明了两个有趣的事实:第一,现在的Internet已经有足够的带宽来支持电视质量的数据流(450Kbps);第二,数据驱动网络越大,所传送的数据流质量将会越好.这两点都再一次说明了本文所提出的数据驱动重叠网络是用来解决多播视频分配的可靠方案.遭II聋.啄相关画工作雅强(辟盖本节丑翻译鞋:药Dr脑if宰ti劈ng谣Le刑av详es胡)推在过职去的宁十年而里像,傲出现纯过一乒些基缝于禁IP册多播茶视频师的重吼要研秧究硬,纳可以丰参考礼[律一八软].慰橡最近隙,纹又提跨出了所许多举有关纳网络缝多播漂(百O误ve冶rl技ay尼M早ul逝ti杀pl申y张Sy歪st俩em借)倘诉的系类统斧,矛它们婚大体院上分蓄为两吹类扇:格基于韵代理遗协助听(唱P户ro塑xy造-a倒ss浅is蚁te符d惜)谁的和恋基于猫P误2P楚错的易.众在传辣统意酬义上惊,册通常开事先敲安排亩一整岂套服魄务或玩应用房层上骗的代社理蔬,强然后窝在这菜些锚型点月(封A是nc庙ho岩r牧N符od拣e柳)宽的协谷助下探建立碎起一状个高饥质量稿的网济络粒[1唐],蜜[2吊],宁[2柜4]田,[尸26趋],隔[2驻8]功.芒DO证Ne魔ts求属于猪第二伍类柏,再它不竖依赖贼于专忽用结升点兆(午D秧ed李ic翠at电ed身n间od帜e业)迈,割但是算能在全自组寿织的塑自动哭结点碍(潜A婶ut逮on钟om竿ou删s泉No脏de增s室)贪的基垃础之积上建错立起品一个碌网络环.纹在这村一部掏分中锡,盗我们贿将对守现行姻的几臭种网盏络流俘协议赖作简验略介聋绍裕,标重点由将放骨在那睛些完嫌全遵咬循轮p粥2p酿腔模式焦的协输议上眨.士A.热革基于阅树结嗽构的矛网络幼及其陆扩展别像前狂面所就提到唉的固,娘许多尘网络请流协闪议采想用基院于皱IP苹多播劣的树议状结暴构觉.师在网救络结造点之身间构头建并巡维护斯一个姓高效衔的分恼布佛式树铺结构俯,闷是这担类系你统的胸关键主.肤在听Co潜op邀Ne析t畏中钩,睁视频误源作围为树扑结构敞的根挺,卷收集荷所有觉结点陷的信练息欣,胖用于贤树的涌构造业及维捉护析.及因此倒集中肉式的锄算法泻将会跌非常盛有效扫.样但这独样的济作法叮必须傲依赖朴于一赢个功裁能强相大的榆专用摄根结干点孔.昼同时锯,踪像妹S营pr母ea箭dI密t[据10数],棚N欠IC掌E[面12耐]伶和价ZI泥GZ犯AG扔[1摄1]警,弟使用恒分布糊式算牧法通诵过一卧系列位结点片,娃实现想构建射和路过由功畏能史.性在大遵规模御网络煎中提,赞这些荷算法晶采用布层次氏聚类关(桑H苦ie贝ra保rc房hi移ca息l守Cl厅us颜te佳ri店ng饺)之馅的方猛式来谷达到菊最小墓的延处迟衡(师从树量的高诉度上害讲痛)等菜或边仆界结丰点的岗工作静量罗(锦从扇绞出丙度警(纱F呀an假ou停t训De倚gr嗓ee患)颂烦上讲唱)树.飞晃但是氏,壁一个泼树结扑构中连的内券部结尤点会锅有较案大的玻负载奇,诊因此阅它的粥离开申或崩元溃仿,斜将会许在很情大范雷围内断导致裕后代狮结点反的缓命冲区阳不足拦.轻虽然牲已经吩设计见出了述一些读树结处构的燥修复肢算法从来适汽应结位点的兽动态庆变化蹈[艳12杜],网[1露1]卡,[内23用];迈镇但是贷树的昌结构彻仍会吊在高醒动态景的网奶络环迷境中读遭到搜频繁擦破坏涛.捞还存哥在许尿多用筒来解帖决树内结构安负载点不均记衡或舟易损碑性的扰其他爷方案馒.肺例如古建立朗以网搏孔为窃基础捡的树萝结构视(和N城ar避ad嫁a党及它密的扩发展绒[衣14姻],如B踏ul神le均t椅[2还0]山)赔,怠维护漂一个怕多分兼布式割树结就构属(雀S已pl源it掉St恋r午ea悠m附[1边9]锄),由六或者和在分寒层编渗码沾(阁P筒AL啦S长[2尸9]饿)券和多潮重描妻述编钟码荷(启C爆oo测pN冲et差[见3]亩)持之间鬼权衡帝.田DO颤Ne佣t歼通过薪引入次一种倍简单惯明了格的数重据驱念动方肆案瘦,播来弥腔补这岭些缺楼陷老.贞它并迹不需建要维款护一脆个更君复杂蝶的结言构启,姑或者湾依赖疾于先赖进的把编码鸭技术事,省虽说疾后一节点也誉会在列这个斯方案磁中起鱼到一奶定作对用嗓.瓣B.状放以谣闲谈熔(汁G低os棉si圾p荣)咱为基疮础的转协议心最近灰,翁闲谈哈(正护或传姿染病授)志艳算法宅已经嘉成为料P喉2P盆燃系统疑中信毅息多观播传魂播的疾流行刚解决杨方案厨[妻一三哀],咳[鸡22专].负突在一免个典铃型的慰闲谈样算法结中擦,究一个读结点绩将新照信息毛发给悦一组拳随机键选择尽的结售点管;很这些撒结点椒会在测下一电轮中练作相炸似的旁事情梳,积直到期所有馅结点壁都收庙到信衔息锦.抚闲谈左对象写的随知机选猪择么,管能使犁系统信加强判对随忘机发会生的最意外疑退出闸的弹托性困,轻并且晨能够淡进行户非中窑心式码的操移作枪.表与捏[截16口]似相似介,伍DO驰Ne故t热的成闲员管拢理中潮使用京了闲远谈协菊议寒.汽DO孟Ne曲t碎中的镇数据妥传输姜方法棋也部塑分受犬到闲姥谈概貌念的析影响厨.果但无屈论如析何扩,坑不能俱将闲姨谈机厦制直唱接用姓于流日传输谋,防因为舞随机塞的传吓送数复据会估带来通大量饰的冗觉余戚,轨而这陶对于挎有高赏带宽洒需求绘的流醉应用谋来说样更加连严重进.期DO进Ne坊t皮中微,鸦使用牧了一村个有就力伙圾伴的灿选择举算法刻,劝和一认个低矿开销骗的调植度算至法兆,语以便绞于在统大量拳减少荐冗门余的职情况螺下逼,透智能渣地从银众多哲伙伴丢中接伯收数澡据邮.锹先前治进行看的一醒些有屑关肆P窄2P经犯的请雄求式们流传豪输霜(道盈例如许,男[4窗],残[径5]屠,皇[6仔],畏[破7]层,炊[8呈],展[格9]丝)首的工承作与池闲谈盖机制矩紧密旺相关嫂,刺DO掩Ne叶t兼也是侮如此信.僻在这忌样的慨机制乒中旧,著视频冰数据滔由一贵些种宵子结德点在诸有异滩步需谦求的艇结点义中传洗播清.电同时柴,宋一个斗或多求个结猾点繁,浆能够错一起承为一兽个新熊结点片提供停缓冲似数据瓣,拐并能性随着奉提供熄者的擦增多窑,妄增强注系统框的能害力么.脱DO扬Ne更t角的目只标是舱通过扣半同物步的诸结点便,灶达到笼实时年流媒丛体传幻输挡,固这就驳需要办不同拖的解赞决方备法历.旦然而令,外在实伏际的榆In巷te伶rn厨et丧蔬实现膨中号,救DO拘Ne棵t文的能才力有呢很大副的增柔强云,育这也胆证明波了那甩些在登P红2P挺阵请求颗式流特传输燥研究鹅中的释论证绑.坝II盛I.腥D嚷ON沿et钥的设唯计与恨优化密(游飞本节破翻译棋:蕉默难两)惹丽Fi钢g-拨1玻一个适DO妈Ne缠t瘦结点仰的系鸭统架俗构图呀Fi滋g-匙1配是一坊个贵D挡ON阿et庙地结点及中的惩系统勾架构适图断.丽其中斜有三搜个重眨要模旅块呜:顺(1形)睡成员尝管理满模块坡(疗M它em纸be光rs腰hi百p像Ma幕na亚ge悦r不).球针负责残维护宋网络锹中一苗部分欣结点比的相哨关信番息浇;吨(2连)店伙伴裙管理落模块脖(穴P躺ar罗tn笋er滔sh馅ip静M较an拐ag柄er胁)肆.浮负责武与网删络中咬的其躺他结舟点建现立并刷维护衡伙伴恩关系朵(更失译者遗注丑:兴原文辅中的狼``晓Me疗mb藏er窃''各一词闹此处尖被翻臂译为强``振成员遥''邻;首``俊Pa秧rt扛ne券r'错'您被译播为睡``瓣伙伴老''款.肚二者疗区别凯为叙:钳网络淡中的尾一个跑结点楼被称絮为这镇个网工络中薄的成认员尽;警网络练中两游个直华接相封连的守结点吵互为锦伙伴洋.粒);梅(祖3)固螺调度泰器虽(结S弃ch踪ed晓ul秆er京)损.装负责乞视频千数据旦传输亮过程泻的调升度工旺作筋.撞一个来D跃ON贸et虎姻结点炉的角衔色相督对于烦视频隐流中旦的每绍一个谎分段纯(蜂S命eg兵me蠢nt昌)厨,大既可贯以是辆分段凳的接忙收者第(裤R截ec式ei洪ve评r御),过迟也可祥以是碍提供撑者族(垒Su疾pp渐li唉er黑)乐,亮或二尸者皆悉是瑞.鞭结点准角色察的确茅定会多根据撕分段串的可嫌用性损信息柿(代S召eg仍me鸦nt映's茫A摆va桌il某ab虽il伐it输y飞In防fo茄rm洒at减io财n枣),饮炊动态亩地调尊整签.彼分段殊的可缴用性帆信息衬会在耽结点葵及其蛮伙伴章之间艘周期熄性地腿传递爷.贵(蒜译者曲注侍:需原文究中使架用的竟是佳`克`p锻er哪io套di差ca匹ll痕y驳ex弦ch厅an上ge拒d慧be范tw党ee芽n亮th断e内no数de旱a吵nd扩i集ts扫p秀ar闲tn东er核s'就'.阻滋翻译处为抱``箩周期桂性地依在结端点及抽其伙牌伴间船传递衡''找.予但是唱译者启认为痒,至这种坊传递踪并非梁是严柴格地备周期湾性动检作传,胜即蒙,逆两次谢信息疏交换查之间沟的时症间间失隔不笼一定食是个继常数显.御因此关,彻此处杰翻译姓为馆``熔周期沫性地狼''验涉似乎饥欠妥过)测盟但是耐最初备提供孩资源圆的结寸点育(炊S骄ou她rc悄e旷No南de慕)倾菠是个肥例外撑-温--肚祸它的曾角色找永远赢是分缩段的城提供爽者贺.摧在此建,猜这种侵结点仔被称誓为欢``利源结葵点汇''荣(怨O淹ri换gi已n虾No坡de例)杂.准它可稼以是窃一个务专用金于提哭供视抖频服挣务的占服务停器旨,浪也可队以是奖网络光中一凝个运挽行了理视频霜服务倾程序爹的计陡算机莫.疫本节躁中泽,吼将讨侍论模合块间锦的交预互以编及设溉计问喉题蔑.习并给嗓出了纽当前滋的一知些解肺决方隶案陆.嫁它们辜分别释被应什用于限基于圾Pl剑an绕et晨La复b岗的和至基于貌因特吼网的醉实现料中愧.须A.伸斩结点嚼的加卸入和乐成员最的管疫理诵每个使D病ON神et趁乘结点册都有雄自己贴的一任个唯叔一标缸识符懂(胖U乒ni蕉qu牺e亿Id车en扔ti葡fi者er漂)厘-度--低芬比如搅可以联是它粮的摘IP挖地址秒-智--顷牲并且猪维护肢着一凤个缓猾存俯,狼用来诚存储覆D衫ON第et泉烫网络蓄中一盟部分蝴活跃符成员术的标深识符受(数楼以下牧称该豪缓存储为珍mC做ac隶he誉)网.提在一寿个简省单的行结点女添加脾算法栽中彩,市一个答新加份入的抓结点喘首先尊去和巷源结申点联朗系选.防源结遗点会巧随机坝地聋从自冷己的蚀m胖Ca院ch题e葬中挑算选出奏一个晴代理衰结点晴(串D会ep框ut者y虎No右de随)植,汽并将挤新加请入的泳结点版连接裳重定鼠向到柴这个帖代理朱结点赤上恰.撑新结女点会侦从代六理结钢点上秆获得塑一个幸成员胜的列股表伶,猴把其颂中的多成员惯视为枪候选绢伙伴不.羞之后宗,杰与这广些候杏选伙布伴建茄立连工接蜂,巷由此序确定汪了自环己在梯网络倡中的位伙伴潮关系干.茄总体掩来说狭,冲这一庆添加伸过程箱是可伪行的不.默因为门源结床点会双在整饿个流炉的传然输过恒程中躬始终横存在揉,疑并且突它的傻标识姑符链/没地址扑是众借所周佛知的书.缴重定役向的家过程粗使得新新结竹点可蜂以更骆加均削匀地玉选择迷伙伴摩(她博译者蛙注西:勿此处马原文粉为辆`铲`尼Th婚e伴re僚di苍re滋ct服io率n烦en抵ab卸le臣s芬m渔or筑e泳un出if浩or丹m前pa吧rt痒ne唱r毛se鹊le插ct鸽io傅ns语f熄or昏n讨ew店ly快j猪oi旦ne本d摄no诱de驰s'泄'.策约该句搁的翻珠译有鲁些过薯分生科硬笋.难需再霞斟酌注)寄,匆同时才很大寒程度愧上减茅少了葱源结欺点的币负载最.险本节搏的最乐后为,暴会对奸这个连添加参算法叹的改犯进进幻行一赌些深徒入探钉讨损.顺实践料中醋,峡此处衡遇到非的一醒个关羊键问端题是穗:月如何浊建立云并更旅新乒m蠢Ca吨ch绍e.僻吸为了卖适应那网络龟的动颠态变压化纲,定每个死结点农周期你性地捉产生宜一个姓成员摸信息舞(屡M续em掀be悠rs索hi寄p鹿Me沾ss户ag惊e抢)浸用以杠声明阳自己奶的存锈在挠;瓦每个起信息过包含届四项选:梨<s企eq梳_n熔um领,酸id雨,反nu遗m_惕pa描rt照ne旺r,出t为im暗e_嚼to偿_l盼iv值e>绸.接其中迟,小se尚q_榆nu出m罢表示借该信攻息的齐序号洗;蜓id如鄙表示旋结点烈的标桥识符是;进nu扎m_奥pa型rt疮ne宰r格表示予结点块当前泽拥有丑的伙听伴数惭量请;块ti菌me根_t嫌o_忧li帝ve阴亚表示制本条榆信息医剩余肝的生码存时要间学.杯DO残Ne遮t足网络战中夺,窝成员胡信息删的传进递使社用了照S书ca歼la薯bl咽e荣Go某ss跟ip伶M透em进be级rs迷hi曾p赛协议奔,感即卵SC崭AM脸.墨关于要这个巩协议厘的具乳体细恰节常,阴参考宣[罚21妨].最辽此处牌,贤仅强邪调它是所具村有的成三条增重要嚷性质忌:弊可扩恢展践(骗S盼ca蔬la被bl桑e幸),绪去轻量拐级加(严L妈ig崖ht纤-w倘ei卷gh挤t衣)闭并且朱每个口结点斗仅蠢掌握棒部分钻信息开(农U冈ni葱fo公rm左P著ar抱ti各al哥V休ie穴w羞at停E祥ac栏h喂No行de筝)页.深当结种点收承到一旨个新脱的成从员信凭息时牺,槐它会薄在型m脏Ca订ch纹e净中找攀到对抗应输i钞d膜的成岭员信撤息记级录脂,紫如果臣se选q_姻nu敞m子大于磨记录秒中的脂se愤q_磁nu询m,污利则更烟新此洽条记干录方.角如果征没有赤找到蔬对应豆i列d系的记要录趴,辜则在悦m指Ca薄ch袍e摔中添乘加一始条记欣录存荷储该佩成员请信息夺.肯mC浮ac荷he宏某中娱,南每条桶成员涛信息曲记录侦包含柜五项透:幼<s步eq坑_n胜um左,疑id栋,网nu取m_吃pa运rt朴ne乖r,令t资im醋e_迟to描_l侨iv胁e,傻l俩as相t_朵up淹da远te寿_t歌im脆e>司.锄前四流项与主成贝员信乞息中岗对应命项的继意义伶相同惕,六是从云收到絮的成奶员信寇息中贝拷贝悟来的锡.使第五拌项记续录了醋最后尤一次珍更新递该记共录的香本地恩时间池.画以下索两种挺事件钩同样版可能兔引起奖m岗Ca珍ch壮e慌中记崭录的贝更新科:魄(1割)依在会泡话主(菊g积os溜si屿p晶)词过程绵中制,剑某条纸记录嘴即将带被传揪递给研其他巡结点仇;狡(2口)窄一个目代理她结点会即将咳把某冶条记务录传颈递给债新加品入的袖结点普.眠在这疾两种或情况最下孝,罢结点斧会把冬相应荐记录岂的茫t础im推e_盗to偿_l饮iv监e披减去奖c任ur隆re项nt弓_l情oc粮al嘉_t扮im间e困-呀la某st贡_u蝴pd字at乏e_菠ti脚me刮.雄得如果观计算岔结果挣小于绢等于阔零匆,归则该辆条记班录会顷被删小除击,梯并且徐不会乡被传益递苗,正也不伪会被川加入坡到伙桃伴列物表粮.童否则弃,职对于维第二毒种情灶况息,唉代理饱结点拒会把棚该条葡记录叨中的妻nu筋m_办pa愿rt扁ne碌r笋项加师一状.势B.没朗缓存躲映像专的表屠示和净交换伞Fi诱g-桂2全DO汪Ne剥t务中的映伙伴督关系舍实例横(僻A担为源敏结点层)阅Fi泰g-巨2兼是佩D垮ON支et宽胸中伙孩伴关妥系的侵一个彩例子豆.滋如前伴所述键,燥在鉴D肚ON顶et校殿网蹈络中膀,霞伙伴提关系盈和数业据传贼输方探向都掏不是增固定预的咱.勿一个队视频昂流被摄分解肾为多膨个定笑长的捐分段回.夫结点恰缓存浪中各街个分胁段的牺可用勉性信披息被抵表示茎为一芦个缓共存映称像仙(上B苍uf辉fe丈r饮Ma欢p,雀B完M仆).斧计每个却结点暖会和备它的拔伙伴迅不断唉地交陡换各圈自的疤BM业.精之后址,给通过络调度贤算法短,昏确定镜从哪糠个伙巴伴处津接收迎哪个腐分段惕.讲对于备实时检的多扮媒体标流来叉说德,酿DO糊Ne晴t划结点蒸中的弯媒体辰播放以过程探是一右个半烛同步巡(径s挨em牢i-休sy员nc湿hr赖on潮iz捏ed讨)胖的过言程朴(戏规译者散注越:醋``吵半同惜步傲''吴寒一词贡似乎忌有些样前后殖矛盾诞.警从字捆面上朵看宜,旱翻译梅为贿``遭半步糊''优烘更佳殃.约但是湾为了弄便于婚理解并,句这种彩``涛矮高端粱杠''饿蓝似的缸词汇腰还是溜保留瞧了下段来但).规慈分析尿的结节果表赔明葡,感DO萍Ne版t摆中分摄段传吼输的千平均闸延时程被限旋制在效了一敏定范芦围之析内昨.俱实验咳的结仗果更缸近一景步指虎出了午,永结点称之间屋的迟柱延很众少高默于一结分钟栏.级假设谦每个险分段帮包含甩了一悦秒钟笛的视运频信粘息弦,尤一个藏具有数1晒20律草个分垫段长袜度的更滑动跪窗口明便可很以有蔽效地畅构成抄一个黎缓存虏,付而滑末动窗套口以能外的午分组肢则不距在结枪点的早考虑兆范围娱之内士.崖如此段,窝在实轿现中炎,舌便可顽以使籍用研12常0秘比特乌来表强示一广个趣BM全.宪如果辫其中假的某民位被册置一和,坏则表乌明该枝比特童对应并的分险段有廉效予,形即打,俩该分狱段已男经被释存储美在了分缓存慎中归;拌反之丑,衔若某局比特圣被置僚零律,抗则演表明蚊该比盲特对虎应的求分段朵无效急.蝴滑动拣窗口图中第站一个劲分段极的序酱号认(米s丈eq猫_n雕um叔)极筹存储堤在额赛外的事两个踢字节忘中造.择对于剃一个诚非常赞长的夸视频房节目挤来说槽,呀这个拒序号晶可能昨会由禁于溢骂出而距被归证零穗(呆冈这样铅的视谅频节乌目至焰少应测该大誉于离24症小时肤)险.德C.蚕沫调度晕算法讲给定雄了一各个结债点和伸它伙狂伴的跟BM鬼信息虑,蓄调度穿算法沙则可份以用香来确泽定从控哪个准伙伴诱处获编得所肤需的洲分段节.牢对于宣一个购同构桌(铲H比om捆og淋en众ou齐s抚),枪皆静态挥(帝S床ta糟ti藏c挥)衔的网采络埋,为循环滥鲁棒线(套R稍ou左nd尿-r哥ob巡in侵)忘悔式的励调度检便足韵以听.兵但是拉对于把一个辩动态终(桌D污yn原am叫ic壳al婚ly熄)匠并且计异构催(奥H够et炮er医og作en疏eo劈us明)景斜的网哨络来联说剂,膊更加娃智能剥的算序法就抄显得扫尤为化重要柜了宪.辽一个闪调度宏的结件果会冻受到统两个杀约束输条件专的影字响激:源每个扰分段扰的截缠止时篮间司(侦D即ea宴dl越in仔e洽),像妻以及零与各烧个伙狐伴间脂的传黎输带垃宽毛.厨第一屯个约察束条封件表址明季,坟超过肝截止刃时间泰到达傲的分列段数读量应淹该控跌制在观最小双.墙这个色问题甚实际目上是执`捐`六并行觉计算叙机调洁度问顺题渣'江'(贯P割ar招al兼le旁l凡Ma学ch劈in催e汪Sc禽he爬du棵li画ng吓)轧变的一遣个变钓种咱,壶属于末NP蛛类问涝题掠[线25仇].国泡因此立很难浸找到斤一个烧最优喉解福.稿从实扰际角孔度出健发向,教调度疲算法器必须镜能够主快速堪地适院应高笔度动泡态的蕉网络钳环境汤.宣因此响,辫我们画采取喝了一恼种简啦单且近能够色快速务响应特的启楚发式你(赚H吐eu松ri影st姨ic艺)亏击算法嫁.殖这个疼启发恨式算荣法中书,螺首先嫁计算课出资墨源的铸潜在疤提供扰者察(蚊P鞋ot申en揪ti搭al震S搬up化pl悉ie生r刑)效的数益量洪(滤智即夜,板拥有咏所需之分段响的伙重伴的少数量勺)管.得因为麦一个尸分段江如果饰对应鼠着较解少的穷潜在锣提供县者援,揭那么巨将意母味着丸这个篮分段百会很判难在弱截止既时间所之前棉到达迅.嗽算法鼓会从虎仅有菜一个怖潜在很提供释者的屡分组偏开始瑞确定喘某一辞分组膛的提港供者多.亿之后颈是对冤应有乡两个细潜在彩提供番者的案分组婆,区以此搅类推疮.妙如果或一个祸分组蒸对应够着多贼个潜旬在提隔供者呢,卷那么益具有络最高纽带宽纽并且懂具有顾更长驻可用董时间曲的提惠供者便会被封选中徐.姐Fi沸g-讯3狐列出垂了这博个算贡法的谋伪码枕.器对于集每个夺结点筒,现都将灶会执莫行该匹算法惨.择它的秧时间皱复杂忙度为目O权(释W瓜*破B置*鬼M知).情松在具挠体的舌实现可中曲,纱每次席执行赚仅需色一五器ms贝.湾计算站的额赵外开夺销并幻不高污.驴因此冷,怨它可洽以比渣较频置繁地葡运行侮,盈从而衬更新不调度牢策略慧.课Fi蛙g-搂3消每杨个圈DO睡Ne黎t衰结点葵调度涛算法箭的伪涛码贞(帮译者洒注窜:喉个人宣认为解,兄该伪貌码包乔含部影分打针印错优误吓:姥自造Sc词he写du痒li情ng施:宏一行与起淡,绒向下晚四行愈,占有寺:夸T[鞠j,际i]解.兔个人精认为挪应该莲改为污:桥t[客j,蹦i]早第一迷个丛if吴语句温中的寸fo山r锐循环丰,燕包含横一个役循环谎控制馆条件齿,访原文殃为烟:合j>罪k.奥奸个人员认为鹅应该件改为永j煎>i响再向趋下五结行海,险原文他为心s停up阳pl迟ie精r[鹿n]秒.毫个人这认为长应该新改为潮s像up虹pl鹅ie里r[倘i]央最后更一个柏fo测r哑循环萄,栋包含把一个挨循环朵控制典条件席,好原文忆为得:笛j>榨k.饮解个人祝认为喉应该状改为夸j椅>i续以上魂纯属桥个人鄙臆断宣,回一切散仍以冶原文鹅为准胆)榨结点煌通过谣调度巩算法戴的计姓算获绸得调巴度策晋略毫,夜把需逗要从熊同一禾个伙滑伴处傻获得骆哪些润分段辉的信引息存叶储在谅一个篇类似久B保M江的位诵序列朋中胸.书之后辈,窑将这旬个位箱序列协发送钻给相菌应的钢伙伴催.糟该伙继伴会旁把位杆序列鲁中所者对应生的分岔段通诱过一户个实牙时的控传输惨协议泥发送伪给结晕点月.剑DO染Ne造t睛并不衫依赖赴于某虚个特筐定的勇协议第.难和其找他系席统一腹样酸,串目前沾所采买用的坊是掩T做FR点C祖(讯TC丑P-颜Fr善ie苹nd歇ly轮R竖at缓e多Co越nt促ro造l章)评协议讽[滔31垃].聪B证M碰信息阵和调拨度策饺略信签息可帖以随给数据饥一并锡传输亡.散这样筋可以与快速团更新顷并且行减少乘额外雨开销不.穗源结洲点在双此始姥终作老为资智源提遇供者早.址并且错所有嗓的分父段都道存储劣在它溪的缓即存中河.俯为了歇防止扬源结片点过收载惯,杠这里尘给出竿了一叉个适龄应度兄较高蠢的调蓬度算付法似.贴如果漆需要梅,夸它还扑可以城通过寇对外未公布行保留凭的缓羽存映扛射来徒控制起负载咽.巴例如易,桥一个习源结仍点拥搁有帽M舞材个伙阳伴俯,统那么络它可献以把纷传递配给第由k蠢冤个伙券伴的徐B靠M烫设置臂为疲:逗这就例是说扶,布只有慢第棉(凝i扶m寺od流M晴)暑游个伙家伴才街会从遣源结漏点处场获得庄第巷i躲骂个分灭段歪.忙其他删的分格段则伏来自震别的钳伙伴抹.循D.研弊错误度的恢斜复和运伙伴坝的筛企选储在平D葡ON鱼et画槽网络续中联,收一个狸结点融可以煌在事沸先声方明后脏退出阀,膀或由绵于崩申溃而家意外定退出火.撕这两器种情帮况都笋可以节在导TF肚RC恳空转为一段艰时间党或者菠BM乡信息闲传递庆过程屯中被双检测子出来显.熊结点梢同时节离开床的概攻率很颗小婆,垦受到投离开盈结点漠影响奶的结叮点会毯立即慨做出明反应踏-肃--卷毅根据求剩下偶伙伴解的虚B吧M边信息直重构蜓调度交策略添.骨除了宾这个访恢复兽机制劫以外酱,际下面裹提出蒜的操刃作也午同样线用于糠增强耕系统逮的恢掩复能铲力支.更声明督后退孙出今:系即将刑退出经的科结点哄会提隶交一相个退雪出消冶息颜.涉这个浮信息市的格即式与端成员等信息迷一样资,地只是陆nu朝m_妙pa桑rt肾ne鞋r简这一属项被捷设为哈-1台.把意外植退出温:摄一个录结点圾的意沈外退仆出会己被它增的伙听伴检贺测到食.谈这个幼伙伴它会代货替退亩出的捐结点爪来发歌布退放出消庆息尿.陕退出简消息岸的传来递方绩式与专成员链信息少的传篮递方晴式一南样驶.坛如果竿结点食是意毒外退如出的涌,佣冗余分的退仇出消杆息也害许会蚂被退奉出结元点的岁多个岗伙伴绞发布乳.北但是集只有忠第一幼个收狸到的竿退出各消息夜会被残允许爸继续某在网右络上弹传播更,汁其他贴的相呆同信榜息传暮播则厨会被桂抑制冲.夏每个凭收到叮消息尺的结金点会洋删除浆各自芽m泄Ca钉ch写e痕中对友应于柔退出酷结点药的记治录隶.胳最后扒,愁每个灾结点顶会定视期地歼从它炕的昆m眯C则ac塑he怕俊中随粉机选队择出浸结点透并与送之建尚立伙辟伴关仓系哲.喘这一徐操作签的目毛的有歪两个仿:菠第一铃,司它使谊得每蔽个结岗点可耗以在励一些匆伙伴蓄退出讲的情笨况下贼,动维护施一定香数量驳的伙他伴采;屑第二枯,轮它使使得结擦点可好以寻音找到键更高狸质量执的伙昏伴问.缺在实题现中个,昨一个芹结点羞i麦逃评估毁它的担伙伴弯结点万j蹈,狮使用姨函数姑m疑ax寿{锻si之,j扔,烤sj定,i危}.企游其中祸,遣si建,j邪锯表示窑单位闪时间絮内辆,岔结点止i丹猜收到衬来自抱结点任j牙禾的分翁段的度平均进数量盖.归直觉嫩上看开,饺一个跳具有选更大巨上传纵带宽块和更仅多可送用分踢段的幻伙伴浇会获祥得更榨高的沾评估当分数阁.导由于吹一个留结点季既可醋以是偏资源喝提供逃者冬,嘱也可离以是坝接收梢者紫,集因此泻需要丘计算认两个快方向慈上的般最大仅值橡.滨在寻炎找到才新的巷伙伴均后尊,但为了糟保持够伙伴谣数量找的稳于定怠,钥伙伴屯列表帅中具铸有最搅低分母数的布伙住伴将共会被挖抛弃炸.沾伙伴冶的数罗量管,嫌M夺,繁是一章个很异重要锐的设扣计参券数巨.类它的逝影响徒将会危在之坑后的越理论宰分析声和实防验中包做具搁体介己绍躺.袭IV丙.播网络萝半径培的分弄析奇抚灾(流本节绿翻译歇:烂默难钱)矛本节电将会统对路DO传Ne鹊t旅网络界的半伴径进甜行分话析那.筐所谓快网络祥半径启,怜指的排是一粗个分或段在阿传递胳过程拢中控,摇从源统结点绍到所按有的杏目的推结点翼的平庸均距扑离设.浑和大昂多数抚文献虹[1钞1]碍,奔[计12火],曲[贷27绝]良相同唇,咱距离泼的单持位是京经过亡网络津中结育点的涂跳数垮.搅这在果一定旁程度鸽上反穗应了测端拢到端蓬的传榴输延屠迟讨.错这里屿用到啦的分填析模北型是密经过遣简化晨的闷,随结果咸显示坛网络弄半径伏与网春络大塔小之干间成魂对数涝关系腊.层这说衬明胆,榜DO茂Ne统t倡网络护中的婶端到构端延誉迟是蝴较小搂的信,惜足以遭用来刘传输挎实时围的流诸媒体呢.似在为DO裕Ne血t友网络荷中饰,啄分段念可用君性信奴息的引传递蛛路径浅,美可以案用一匠棵广流度优嘉先搜套索接(脸BF拘S,获B苏re刷ad枝th地-F箱ir党st然S输ea狐rc益h)筑虏的树毫结构疲来表欲示割.筹源结铅点是钢树的号根结存点留,圣处于悔第应0研层零.匆第怨k豆层的圾结点雕与源河结点捡之间赔相隔祸k询跳亩.现DO睬Ne舍t足的结萌点不模会维示护一黑个明场确的大结构惯,屈因此阔,剩每个啦结点猫可以伟在这日个齐BF祸S炒树中况出现削多次寿.份为了记描述北方便夜,仰把熄BF茫S忠树中魄的结筛点称狮为糠s-道结点父(饮s-纱no协de饲)挤.缓根据馒广度想优先殃搜索暂的规联则轻,逮s-控结点温按照腥在搜组索时提被访感问的井顺序角进行镰编号怒.布这样降,丹根结混点的担编号剩为贸1.播榜对于锐编号资为乳t豆的获s-黑结点仍,膝它所浅对应贯的闪DO狼Ne点t配结点螺被表收示为绣pt望(幸查译者嫌注疲:培根据害下面语(t崇)阶函数缸的定答义板,译此处捕应为居).围认假设淋伙伴愁之间狱的带胸宽大随约相芽等裁,家并且墨一个涉分段包到达棚一个舰结点恨的过结程流,必是自叮根结和点出仰发赖,念按照含广度婆优先扶的算骆法搜邻索树旋结构巧,变直到谋该结凑点第告一次扯出现前.随Fi直g-隔4泊显示痛了古Fi待g-本2魄的究DO嗽Ne颈t隐网络院的单BF萄S拘树结竹构俘(肚只列肠举了竞三个属层次趴).误Fi辅g-明4梨一棵舍广度陈优先奥搜索杨的数映.篇黑色值的结兵点表跨示安(t芬)第等于吨1嫩的结瓦点唉.意即第朋一次播出现从的结传点毕.事白色愁结点梯表示卷(t勒)版等于岛零的鸟结点贪.件定义恭一个嫌辅助挠函数丰(t杂):悼贤也就越是说艘,稠只有鼻在各s骨-难结点追t澡缎第一誉次在支树结盛构中功出现成时丧,泉函数么值才驶为吓1寒.吨由于掘成员赵关系婶和伙见伴关打系协砖议是管采用脖随机逮的伙子伴选扭择方访式瘦,备用普N茫过表示范网络怠中的薪结点糖数量超,旺因此缓则有拜:滔这里唯,变f(镜t)认核表示皂编号委为男1堤鞭至歉t男融的开s咐-厦结点婆中言,倘包含骨的思D盘ON怠et焰楚结点恭的数惠量弦.混由此障则有奴:阳f(种t)碑-告f矩(t樱-1母)滥=泽(t压).廊叶对截(代1)茫令式两台遍同辨时求梨期望佛,乔则有类:易由此仍推导抬出蓬:村因为再f伪(1和)徒=敞1,羞我根据畅等式旺(兵3)辱弯可以苦推导娇出潮:室这一幸关系奋给出辩了鱼D追ON习et能奔结点安数目单关于棍s闻-锐结点鬼编号是的函投数颗.扔令称t巾k虹表示位第筐k控箭层中尝最后欲一个镰s泼-脊结点验的编烫号查,菌那么黑D傍ON昏et极快网络途中其耽他结么点与伪源结搬点之销间的镰平均音距离方,贷即网成络半吉径伯,围则为酱:竭注意键到忌,妻当众k纹抖趋近丸于无捎穷时派,滔有仍:式.车对于风一个披连通待的网彩络来咳说真,逗可得春:通考虑愚一种盗稳定霞的状三态紧:僻每个捡D泽ON柏et叮倍结点池均拥悄有水M妨笼个伙信伴悔.云那么魔对应剩的归B序FS口汉树中毯,忧除了咐根结扇点拥秒有隆M各糊棵子秋树外挂,贴每个五非叶捎子结歉点都歉拥有鸦M晚-1埋潜棵子晚树规.功那么挖可以系导出睬:僻将饲(弊6)蹄闹式中嗓的连鱼加分胞解为巴两部派分粮:倡一部页分是约从语k丰=汉0技拦到棍k财=中l预og院M-朝1渡N;券次另一驳部分本是从状k誓=战1数+秋l据og袭扰M-兵1乓N模到正麦无穷赵.扩那么朽有往:绢当商M本闲大于狼等于链3经施时裂,喂有丸(添M-子1)缎k骑>沈=劣(M理-1训)k今.曾则压e霉M-油1^按k逝<紧=寒e尝-(架M-能1)膊k拖.凤由此写导出将:或由此艰,泛源结寺点到乐网络辟中任腐意结如点的缸平均赌距离构则为奉O蜻(l质og芳N)微.棉从式抖(览4)每纽和式否(诞8)壁店可以互看出兔,滴从源目结点映出发洪,邮在咏k浪梅跳之痛内可轻以到姻达的舌结点枝的比遮例为迁.柔也就胡是说攻,枪对于自包含翠5辉00浅个结聪点的塔D歇ON歌et壶贝网络兵,谋设通M吹=盯4碎,果那么公,估大约姨9涛5%叹拖的结井点可评以在痒6繁奔跳之多内到腥达条.V.

基于全球范围的性能评估

(本节翻译:A-C由DriftingLeaves翻译;D和E由默难翻译)关于DONet的原型,已经进行过多方面实验.这一部分中,将会首先说明在PlanetLab[30]环境下,实验系统是如何设计.其次会列出一些典型的结果.最后,本文会指出在实验中所遇到的一些典型问题,并讨论它们对实验结果的影响.Fig-5结点地理分布的快照A.

实验系统的设计这些实验几乎动用了PlanetLab的所有可用结点,

而结点的总量在实验期间(2004年5月到2004年6月),达到了200个到300个.每一个结点都运行一个程序原型,扮演DONet结点的角色.源结点被设置在美国(,IP:2),而借助远程登录,通过在香港(.hk,IP:一三7.一八9.97.一八)的结点控制整个系统,它也就是所谓的监控结点(MonitoringNode).实际上这也是亚洲第一个接入PlanetLab的结点(从2003年1月开始).Fig-5展示了一个在5月进行的实验所动用结点的地理分布快照.对于这样一个大范围分布的实验台,如何有效地控制结点和收集报告,将会是一个挑战,因为无论是启动或升级程序,还是收集实验结果,所有的结点都将会集中地完成登录,上传或下载操作.所以设计一个自动控制系统是很必要的.而同时实验系统应该具有高度的可扩展性,以便加入新的结点和性质.有趣的是,借助PlanetLab所提供的工具,以上目的也可以通过使用重叠网络来达到.下面将简要描述实验系统的模块,Fig-6描述了这一模块的构成.

Fig-6实验系统的模块结构图DONet模块:DONet是使用Python---也就是Planet的编程语言,来实现的.在这一模块中,对于并行事件的处理是采用具有非阻塞模式套接字的事件队列来完成的,而不是多线程.正因为程序是单线程的,可以避免许多在多线程编程下的复杂问题,因此程序的调试和实现会更加简单,这也会使得原型的设计变得快捷.控制台和自动机模块:控制台通过交互命令来便控制整个系统.这些命令会是诸如加入,离开DONet或改变参数.而Python的突出性质是能够动态地执行指令.那么,新的特性和功能就能够在避免重写和重新装入整个程序的情况下加入.在控制台中,同时设计了自动机的模块,它能够自动地开始实验并执行一系列在队列中事先定义好的指令.这样不仅能完成精确的时间控制,还能够减轻长时间实验(许多实验经常会持续5个小时)的监控工作.指令分发和报告收集模块:由监控结点直接连接到每一个结点来分发指令和收集报告,这样的设计是不具有可扩展性的.而使用另一个网络来实现命令的分发将会很好地缓和这个问题.在实际中,每一个指令都有唯一的序号;一个结点接收到命令后,会把它转发给一列自己已知的结点,而这列结点就是先前在DONet模块的mCache中获取的那一列.由于指令在数量上是有限的,并且对于延迟敏感,采用泛洪式的方式来广播指令是一个合理的选择.这样的作法同时会有助于建立一个,用于收集报告的逆向树结构.在这个结构中,有关丢失和路径长度等信息能在一些交叉结点(JuncionNode)处分类合并,然后再传回监控结点.综上所述,就能在不让监控结点过重负载的情况下完成在线统计.在能自动控制系统的情况下,创造一个稳定的(使用持续结点)或动态的(使用动态加入,离开或异常退出的结点)环境并不困难.下面将通过列举一组有代表性的结果来说明DONet在这两种环境中的性能,并且指出一些关键的影响因素.

B.

稳定环境下的性能在第一组实验当中,所有的结点都将会在一段初始化时段(1分钟左右)内加入,并在某个流的播放时间内(120分钟,一部电影的典型长度)保持可用.默认的流速率是500Kbps,每个分段都包含长度为一秒钟的流.每个结点会维持一个含有60个分段的划动窗口,或者说是长度为60秒的数据流,并会在接受到第一个分段10秒钟后开始播放.控制开销:成员关系管理使用了轻量级的gossip协议,DONet中的大多数控制信息是用来交换数据可用性信息的.因此伙伴数量成为决定控制开销的关键因素.Fig-7将控制流量描述为平均伙伴数量的函数.开销自然会随着伙伴数量的增长而变大,但是相比于视频流量,

甚至在伙伴超过5,6个情况下(控制流量少于总流量的2%),控制流量也是次要的.这个结果也给人一种直观的印象---每个分段的可用性信息仅由1比特表示.Fig-7在不同网络规模下控制负载关于伙伴数量的函数.(控制负载=每个结点控制流量/每个结点视频流量).Fig-8连续性信息关于伙伴数量的函数.播放连续性:维持播放的连续性是流应用的首要目标.为了评估连续性,这里定义了连续性指标,它表示能在播放的截止时间前到达的分段数量与分段总量的比值.Fig-8将连续性指标表示为伙伴数量M的函数.连续性会随着M的增长而加大,因为每个结点都会有更多的资源提供者以供选择.但是在伙伴超过4个之后,这种增长将变得不再明显.在Fig-9中将连续性指标表示为流速率的函数,可以看到,即使在高速率下,伙伴数量为4时仍然会达到很好的效果.考虑到控制开销会随着伙伴数量的增长而加大,M=4在实际中将会是一个很好的选择,这一点在下面的实验中也同样适用.Fig-9连续性信息关于流速率的函数.网络规模=200结点.可扩展性:从Fig-7中可以看出每个结点的控制开销几乎与网络规模无关,这是因为数据的可用性信息(BM)只在本地交换.同样,相比于较小的网络,连续性指标在大规模网络中也没有太大的变化.实际上,后文将会说明,随着网络规模的增大,合作的程度将会增加,这往往会导致更好的播放连续性.一句话,DONet无论在网络规模上还是流速率上都具有可扩展性.C.

动态环境下的性能下面将要检测DONet在有结点动态加入,离开或意外退出时的性能.大多数的参数设置与前一组实验相同,只是在这里,每个结点会按照ON/OFF模型来改变它的状态:在ON时段,结点会在网络中保持活跃,而在OFF时段,结点会离开(或意外退出).ON和OFF都在平均为T的时间内呈指数分部.Fgi-10在不同网络规模下控制流量关于ON/OFF平均周期的函数Fig-10将不同网络规模下的控制流量表示为ON/OFF周期的函数.可以看到,控制流量会随着ON/OFF周期的缩短(例如,动态结点执行更多动作)而有轻微的增长.这些附加的控制流量主要是由离开或意外退出的声明引起的,但是像前面所提到的,相对于总体流量,这只是次要部分.Fig-11在不同网络规模下连续性指标关于ON/OFF平均周期的函数Fig-11描述了连续性指标在不同ON/OFF周期下的变化.更短的ON/OFF周期肯定会导致更低的连续性指标,但是下降不是很明显.在使用DONet内部一些恢复机制的情况下,即使在高动态的网络,DONet的连续性指标仍然是可以接受的(在1分钟之内找到新的资源结点).D.

与基于树结构网络的比较本节将把DONet与传统的树结构网络进行一个比较.公平起见,树中的每个结点的度被限制在三个以内.这就是说,除了源结点可以拥有四棵子树以外,其他非叶子结点最多只能拥有三棵子树(加上一个父结点,则总度数为4.这与DONet中每个结点的度数相同).

然而,考虑到异构能力和带宽的约束,让每个结点都支持三个子树似乎并不现实.在这种情况下,一些子树将被移到更底的层次,直到约束条件解除.同时,会使用一种树修复算法,使得在结点异常退出的时候,把一些下游结点移到上游.首先比较的是端到端的延迟(end-to-enddelay).由于PlanetLab中结点的时钟并非完全同步,所以准确地计算出每个分段的端到端延迟并非是件易事.因此,使用了一种更简单的方法来衡量延迟---计算跳数(hop-count)的方法.利用这种方法的衡量结果被显示在Fig-一三中.尽管树结构经常被认为可以实现最短的延迟,但测试结果显示,无论是在稳定的还是动态的网络中,基于树结构的网络都表现的不那么尽如人意.如前所述,这是由于上传带宽的限制可以在很大程度上增加树的高度.Fig-12显示了本次实验中的树结构.结点总数是231,但是树的高度却是19---而一颗231个结点的满平衡三叉树的高度却只有五层.Fig-12一个包含231个结点的基于树结构的网络Fig-一三DONet和基于树结构的网络中的平均跳数延迟.Fig-14在连续性指标方面,DONet网络和基于树结构的网络的比较.(Y轴:连续性指标;X轴:ON/OFF周期;网络大小分别为50和200个结点)Fig-一五在一段时间内,DONet和基于树结构的网络中的连续性指标的采样(采样自从第10分钟起至第20分钟)如Fig-14所示,在连续性指标方面,采用树的拓扑结构远不如DONet网络.特别是在较大的动态网络中.这是因为树结构的网络对于非叶子结点的异常退出非常敏感.从Fig-12中可以看到,有些非叶子结点在树结构中起到了至关重要的作用.比如根结点的最右边那个子结点,它仅仅拥有一颗子树---它或者它的子结点的异常退出,都可以导致下游结点的缓冲区不足,而这就意味着网络中会有大约3/4的结点受到影响.为了更进一步指出树结构的易损性,Fig-一五显示了在一段时间内,200个结点的网络中的连续性指标.显然,在连续性指标方面,树结构的网络不仅比DONet网络的低,而且还表现出了很大的波动性.比如,在800至900秒区间,连续性指标严重下跌,甚至低于了0.4.根据当时的记录显示,这是根结点的一个子结点离开所导致的.而这种情况在DONet中则很少见.因为结点的负载被平等地分担开,并且传输的路径是根据数据的可用性动态确定的.值得注意的是,哪怕树结构是满且平衡的,它在动态网络中依然比DONet网络更加易损.为此,对于由结点离开或崩溃而导致的播放间断,作一个简单的分析,为了方便描述,将结点的离开或崩溃统称为结点失效(Nodefailure).假设失效的概率为Pf.引入另一个变量P0,表示一个相关结点(在树结构中指失效节点的一个子结点,在DONet中指它的一个伙伴)在t时间内无法找到新的资源提供者的概率.Ps表示一个结点可以在它的相关结点提出请求后便马上提供上传的概率.P0和Ps的值都依赖于网络维护的算法,和网络/结点的性能.比如修复算法,缓冲区大小,上传带宽等.在实际中,假设树结构中的绝大部分非叶子结点都给M-1个子结点提供服务,那么Ps可以适当高一些,比如等于0.5.在DONet网络中,每个结点拥有M个伙伴.假设只能有一个结点可能替换失效节点成为资源提供者,那么一个非失效节点在delta_t时间内找不到新的资源提供者的概率为:那么,出现流间断的结点数量的期望是:上述的结果显然是低估了.因为我们忽略了一个事实:活跃的伙伴结点可以协同工作为一个结点提供资源.这已经在之前的调度算法中提及了.同样,在树结构的网络中,出现流间断的结点数量的期望是(推导的细节参见附录):这里,h表示一颗满且平衡的树的高度.Fig-16在t

时间内,出现流间断结点的比例的期望Fig-16在数值上显示了两个网络的性能.这显示了,哪怕树是满且平衡的,DONet网络依然可以在播放的连续性上表现得更好些.在大规模,并且结点失效概率较高的网络中,差距则更为明显.值得注意的是,由于在网络层次上DONet与基于树结构的结点没有差别,因此,基于DONet圆算法做的结萍点可舟以与耗基于返树结捕构算影法的泼结点香协同湾工作侦,芝而运仰算的淡复杂姥度方兵面谜,捞DO您Ne微t爽显然没更加描简便被.归E.厅信岭总结吴及展害望蓄总体该说来屑,封DO逼Ne慎t嘱的性和能足坟以用石于实孙时的榨流媒径体传律输复.跟它在先控制斧上的硬额外渗开销信非常信低隐,题大约反仅相很当于致视频场流量瘦的骨1%剖,网并且抬这一愚比值丧不会零随着万网络表的扩朴大而雨增长小.秀和基世于树思结构谢的网淹络相赏比状,辉DO广Ne急t尖的播奖放连捎续性洞更佳如,沉特别绢是在祸一种蔑高度围动态膝的网拿络环怀境中除.什并且宵端到旨端延棒迟也沟比树遥结构被的网姜络要阻小抽.少实践盛中也仓表明逢,蛙实现详一个遍D们ON骄et联迅的原讽型并糠不难凶.吉这即乒是由意于它避本身海的简料单性拌,完也因揭为前P趴la窃ne扯tL刑ab矮捆提供忧的出构色支累持给.莲毕竟拖,挤Pl捆an望et振La腿b宋计划榨依然队在发目展中哀并且级还未朋成熟滔.肌在此厚讨论踏一些想有代门表性锣的观秧点以井及由科此得驰到的恢启示糠.痕可扩斧展性界(游S岛ca累la那bi驼li开ty择)固:慢命令哀分发宽和报麦告收誉集系雅统的开实现捷,电使得红D搏ON役et匀场可以租运行衫于更逮多的门结点卖之上揉.豪如今继限制另它规除模的促仅仅循是骗P市la阴ne沙tL夏ab谋毒中的饺结点号数量昨.驶而且脊,爹如岭F含ig成-7折东所示汽,锡大多灵数的培P货la叠ne咽tL艺ab欺堪结点暖都分夫布于覆北美他和欧属洲洪.竹这仅完仅能街反映灵出当应今部迈分因同特网非的情稀况繁.幸为了丽创造毛一个式更接举近于销因特雪网的旧网络阅环境厕,虏我们与期待狗着有刃更多格其他督国家新结点株的加赖入廉.砍可再隆现性盟(扇R响ep智ro骡du遭ci朱bi裹li把t浙y菌):超算与前巧人在粮这种剥非完非全控望制榴(枯n缘ot偿-f阵ul脊ly务-c绿on赤tr驻ol丙le供d亏)俊的环敢境下岗所遇际到的辣问题殖相同遥,语基于借P洗la竿ne幻tL退ab竞选的实棋验同喉样面阿临着熟可再踢现性碍的问剂题抗.及但是冰不管晓怎么免样聋,钩Pl洽an探et限La沟b好网络茅在几伸个小略时之雷内是如可以准保持妨相对罢稳定玩的预.献所以数这个喇问题静并没遗有那岗么严惯重寺,保并且宽连续戏的几慌次实子验在黎总体朵上是存具有孤可比孙性的屿.疑可描抚述性明(墨R态ep孩re宋se日nt姨ab弦il面it笋y扔):更P医la薄ne斩tL痒ab救粮的稳症定性牵在一煌定程棵度上足是由祖于网毁络中费的应添用较届少徐,主因此嗽额外弱的流垦量较摔少湿.园实验剃尽量钱模拟梢了当遥前因扮特网习的环忘境障,梁因此斜有意盏地加晨入了轿一些蛋额外迷流量丝,舒并且蚂抑制扫了注军入速红率以跨防超伏出了霞规定锹带宽裁.挺另一婆点需阀要考筝虑的嘱就是黑源结能点的熊为止选.块在本之次实栏验中撒,天选择器的源巷结点录几本介都在浓美国祥,导因为功大多嫂数指P钩la盆ne袋tL脉ab忙夫结点尊都在唱那里非.伙同时仆也使兵用了明香港众的结堤点汉,侍尽管暂与其然他结凭点相统隔较纵远瞧,裕但由雪于香忽港与煌美国糟/检欧洲岛之间歉的连炭接较万通畅罩,藏因此脸得到静的结乏果也痒类似拢.晒现在挨正在喜联系豪更多酬的位能于其遍他大抽洲的中结点极,谱以它压们为孩源结搏点拦,哑用于更更深爹入的盈实验颗.VI.CoolStreaming:DONet的实现和它的扩展

(本节翻译:DriftingLeaves)在DONet的基础上,一个基于Internet的实现---CoolStreaming在2004年5月30日发布了第一个公开版(v.0.9).CoolStreamingv.0.9包含了2000行Python源代码,这个版本源于以PlanetLab为基础的实验原型,并且在实验完成的两星期之内就发布了.这也再一次说明了DONet的简单.它目前支持RealVideo和WindowsMedia格式,不过只要用户安装了支持其他视频格式的播放器,就可以实现其他格式视频的播放.此外,它的实现与平台无关.无论是Unix,Windows,或者其他的操作系统,只要是支持Python和所播放的视频格式,均可以使用它.像其他的Internet应用一样,CoolStreaming能否成功依赖于它所传送的内容.然而,又不像传统的用户/服务器模型,重叠网络没有一个拥有丰富资源,并由其所有者完成升级的专用结点.此外,它还会涉及到许多诸如版权问题,以及关于它们的深入研究,但这些超出了本文所研究的范围.更重要的是,我们没有意图,也没有能力成为内容提供者.那么,有一个实际且快速的解决方案:使DONet(CoolStreaming)成为内容提供者和用户之间的能力放大器(CapacityAmplifier).换句话说,它会最终成为网络基础设施的一部分.到现在为止,CoolStreaming已经用来播放实时体育节目(450Kb