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

1、50/50CoolStreaming/DONet: 实时流媒体传输的数据重叠网络作者: Xinyan Zhang, Jiangchuan Liu, Bo Li, Tak-Shing Peter Yum翻译: 默难 ( monnand ). DriftingLeaves ( driftingleaves )原文参见: /zhang05coolstreamingdonet.html本文其他部分参见: /monnand/category/261378.aspx摘要 ( 本节翻译: DriftingLeaves )本文描述了 DONet - - - 一种用于流媒体的数据驱动网络. DONet 的核心操

2、作特不简单 : 每一个结点与一组伙伴周期性地交换数据可用性信息, 从一个或多个伙伴那儿接收自己所没有的数据, 并把自己所拥有的数据提供给需要的伙伴. 我们将着重分析这种数据驱动设计的三种突出特性:(1) 易于实现, 它不需要构建或维护一个复杂的全局结构; (2) 高效,数据的传递方向是依照数据的可用性信息而动态改变的, 而不是被限制在特定的方向上; (3) 健壮, 同意结点的伙伴关系在众多提供者中作出适应变化的快速转换. 这篇文章将会通篇分析 DONet 在有限延迟下的可扩展性, 而且也会考虑到实现 DONet 时所面临的一些实际挑战, 并在此基础上提出一个有效的成员关系和伙伴关系治理算法,

3、以及一个能完成实时且连续播放流内容的智能调度算法.通过 Planetlab 差不多在大范围内评估了 DONet 的性能. 这些实验几乎包括了 Planetlab 的所有有效结点. 实验结果表明 DONet 甚至能够在复杂的网络条件下达到专门好的流质量. 此外, 操纵所带来的额外开销和传输延迟都能够保持在专门低的水平上. 在2004年5月30日, 一个基于Internet 的 DONet 的实现 - - - CoolStreaming v.0.9公布了. 它差不多吸引了超过30000的用户同时在一些高峰时刻创下了4000人同时在线的记录. 这篇论文将会讨论关于 CoolStreaming 设计的

4、关键问题, 同时描述一些这次大范围测试中的有味现象. 具体来讲, 网络范围越大, 被传送的流的质量将会越好.I. 概述 ( 本节翻译: DriftingLeaves )随着宽带接入的普及化, 多媒体服务对用户来讲变得日益重要, 同时差不多成为今天 Internet 流量的重要组成部分. 许多诸如网络电视, 新闻广播的多媒体应用都涉及到把流媒体从源头传送给大量用户的过程. 对这些应用来讲, IP 多播也许是最有效的途径; 然而它的扩展却因为许多现实上的和政治上的因素而受到限制, 例如缺乏动力去安装具有多播能力的路由来承担多播流量. 因此研究者们开始关注应用层上的解决方案 - - - 通过参与者的

5、合作来建立一个在单播通道之外的重叠网络, 这些参与者也被称作重叠网络结点 ( Overlay Node ), 那么在此基础上, 就能够通过结点之间的数据依靠关系, 实现所谓的多播.作为 IP 多播的替代方案, 开始时许多网络构建算法大多使用树结构来实现数据传递. 尽管这种方案能够像 IP 多播一样, 与专用基础路由 ( Dedicated Infrastructure Routers ) 专门好的搭配, 然而却经常会与带有动态结点的应用层网络搭配错误. 而且自主网络结点会轻易地崩溃或离开, 因此树结构是高度易损的. 而这一问题在对带宽和连续性都有专门高要求的流传输中, 显得更加严峻. 同时尽管

6、像网孔和森林如此的复杂结构能部分地解决问题, 但其本身的实现却过于复杂, 而且经常缺乏可扩展性.从另一个角度讲, 把多播功能移植到应用层同样会导致更大的弹性; 具体来讲, 所有的结点都有专门强的缓冲能力同时能够灵活, 智能地决定数据的传输方向. 因此文章中提出了一个以数据为中心的 ( Data-centric ) 设计方案- - - 一个结点总是向那些需要数据的结点传送数据, 而它们之间没有诸如父子关系, 内部外部关系和上行流下行流关系. 换句话讲, 是数据的可用性信息引导着数据的流向, 而不是一个专门的网络结构约束了数据的流向.这种数据中心的设计将会更加适应具有高动态的结点的网络. 尤其是考

7、虑到一个半静态的结构, 不管多么有效, 总是会因为结点的动态而处于次优的状态.基于如此的目标, 本文描述了DONet - - - 一个数据驱动的重叠网络, 而其中的核心操作特不简单: 每一个结点与一组伙伴周期性地交换数据可用性信息, 从一个或多个伙伴那儿接收自己所没有的数据, 并把自己所拥有的数据提供给需要的伙伴. 我们将着重分析这种数据驱动设计的三种突出特性:(1) 易于实现, 它不需要构建并维护一个复杂的全局结构; (2) 高效,数据的传递方向是依照数据的可用性信息而动态改变的, 而不是被限制在特定的方向上; (3) 健壮的, 有弹性的, 同意结点的伙伴关系在众多提供者中作出适应变化的快速

8、转换. 此外, 关于结果的分析显示出了网络半径与网络大小的逻辑关系, 这也讲明了 DONet 能够在有限延迟的情况下进行扩展. 为了实现传输实时流媒体的数据驱动网络, 大量的实际问题需要考虑. 在本文中, 将要讨论 DONet 中的若干关键问题. 包括伙伴关系的建立, 数据可用性信息的编码和交换, 以及视频数据是如何在伙伴间被提供和获得的. 那个地点将要提出一套可扩展的成员关系和伙伴关系的治理算法和一个智能调度算法, 这些方案将会在使用较低操纵开销的情况下, 为中高带宽用户提供高效连续的流传输, 同时平稳地将传输负载分配到正在参与的结点中, 并使结点与异构网络相适应. 通过 Planetlab

9、 差不多在大范围内评估了 DONet 的性能. 这些实验几乎动用了 Planetlab 跨越五大洲的所有可用结点. 实验结果表明 DONet 在流速率和播放连续性上能达到专门高的要求. 此外, 操纵所带来的额外开销和传输延迟都能够保持在专门低的水平上. 依照当前掌握的材料, 全球范围的实验专门少在文献中提及. 为此文章中列出了在实验当中遇到的几个典型问题. 并讨论了阻碍实验结果和可能在今后阻碍 PlanetLab 进展的因素.最后,在2004年5月30日, 一个公开的, 基于Internet 的 DONet 实现 - - - CoolStreaming v.0.9公布了, 它差不多能够播放由一

10、个免费视频服务器所提供的实时体育节目, 那个软件最初只吸引了20个用户, 然而截至本文公布, 超过30000的用户 ( 从独立IP的统计上看 ) 差不多使用过那个流媒体软件, 在一些高峰时刻甚至达到4000多用户同时在线. 先前的统计结果和用户的反馈是十分鼓舞人心的, 这也讲明了两个有味的事实 : 第一, 现在的 Internet 差不多有足够的带宽来支持电视质量的数据流 ( 450 Kbps ); 第二, 数据驱动网络越大, 所传送的数据流质量将会越好. 这两点都再一次讲明了本文所提出的数据驱动重叠网络是用来解决多播视频分配的可靠方案.II. 相关工作 ( 本节翻译: DriftingLea

11、ves )在过去的十年里, 出现过一些基于IP多播视频的重要研究, 能够参考 18. 最近,又提出了许多有关网络多播 ( Overlay Multiply System ) 的系统, 它们大体上分为两类: 基于代理协助 ( Proxy-assisted ) 的和基于 P2P 的. 在传统意义上, 通常事先安排一整套服务或应用层上的代理, 然后在这些锚点 ( Anchor Node ) 的协助下建立起一个高质量的网络1,2,24,26,28. DONets属于第二类, 它不依靠于专用结点 ( Dedicated node ) , 然而能在自组织的自动结点 ( Autonomous Nodes )

12、 的基础之上建立起一个网络. 在这一部分中, 我们将对现行的几种网络流协议作简略介绍, 重点将放在那些完全遵循 p2p 模式的协议上.A. 基于树结构的网络及其扩展像前面所提到的, 许多网络流协议采纳基于IP多播的树状结构. 在网络结点之间构建并维护一个高效的分布式树结构, 是这类系统的关键. 在CoopNet 中, 视频源作为树结构的根, 收集所有结点的信息, 用于树的构造及维护. 因此集中式的算法将会特不有效. 但如此的作法必须依靠于一个功能强大的专用根结点. 同时, 像 SpreadIt10, NICE12和ZIGZAG11, 使用分布式算法通过一系列结点, 实现构建和路由功能. 在大规

13、模网络中, 这些算法采纳层次聚类 ( Hierarchical Clustering ) 的方式来达到最小的延迟 (从树的高度上讲 ) 或边界结点的工作量 (从扇出度 ( Fanout Degree ) 上讲 ) . 然而, 一个树结构中的内部结点会有较大的负载, 因此它的离开或崩溃, 将会在专门大范围内导致后代结点的缓冲区不足. 尽管差不多设计出了一些树结构的修复算法来适应结点的动态变化 12,11,23; 然而树的结构仍会在高动态的网络环境中遭到频繁破坏.还存在许多用来解决树结构负载不均衡或易损性的其他方案. 例如建立以网孔为基础的树结构 ( Narada 及它的扩展 14, Bullet

14、 20) , 维护一个多分布式树结构 ( SplitStream 19), 或者在分层编码 ( PALS 29) 和多重描述编码 ( CoopNet 3) 之间权衡. DONet 通过引入一种简单明了的数据驱动方案, 来弥补这些缺陷. 它并不需要维护一个更复杂的结构, 或者依靠于先进的编码技术, 虽讲后一点也会在那个方案中起到一定作用.B. 以 闲谈 ( Gossip ) 为基础的协议最近, 闲谈 ( 或传染病 ) 算法差不多成为 P2P 系统中信息多播传播的流行解决方案 13, 22. 在一个典型的闲谈算法中, 一个结点将新信息发给一组随机选择的结点; 这些结点会在下一轮中作相似的情况, 直

15、到所有结点都收到信息. 闲谈对象的随机选择, 能使系统加强对随机发生的意外退出的弹性, 同时能够进行非中心式的操作. 与 16 相似, DONet 的成员治理中使用了闲谈协议. DONet 中的数据传输方法也部分受到闲谈概念的阻碍. 但不管如何, 不能将闲谈机制直接用于流传输, 因为随机的传送数据会带来大量的冗余, 而这关于有高带宽需求的流应用来讲更加严峻. DONet 中, 使用了一个有力伙伴的选择算法, 和一个低开销的调度算法, 以便于在大量减少冗余的情况下, 智能地从众多伙伴中接收数据.先前进行的一些有关 P2P 的请求式流传输 ( 例如, 4, 5, 6, 7, 8, 9) 的工作与闲

16、谈机制紧密相关, DONet 也是如此. 在如此的机制中, 视频数据由一些种子结点在有异步需求的结点中传播. 同时, 一个或多个结点, 能够一起为一个新结点提供缓冲数据, 并能随着提供者的增多, 增强系统的能力. DONet 的目标是通过半同步的结点, 达到实时流媒体传输, 这就需要不同的解决方法. 然而, 在实际的Internet 实现中, DONet 的能力有专门大的增强, 这也证明了那些在 P2P 请求式流传输研究中的论证.III. DONet的设计与优化 ( 本节翻译: 默难 ) Fig-1 一个DONet结点的系统架构图Fig-1 是一个 DONet 结点中的系统架构图. 其中有三个

17、重要模块: (1) 成员治理模块 ( Membership Manager ). 负责维护网络中一部分结点的相关信息; (2) 伙伴治理模块 ( Partnership Manager ). 负责与网络中的其他结点建立并维护伙伴关系 ( 译者注: 原文中的Member一词此处被翻译为成员; Partner被译为伙伴. 二者区不为: 网络中的一个结点被称为那个网络中的成员; 网络中两个直接相连的结点互为伙伴. ); (3) 调度器 ( Scheduler ). 负责视频数据传输过程的调度工作. 一个 DONet 结点的角色相关于视频流中的每一个分段 ( Segment ), 既能够是分段的接收者

18、 ( Receiver ), 也能够是提供者 ( Supplier ), 或二者皆是. 结点角色的确定会依照分段的可用性信息 ( Segments Availability Information ), 动态地调整. 分段的可用性信息会在结点及其伙伴之间周期性地传递. ( 译者注: 原文中使用的是 periodically exchanged between the node and its partners. 翻译为周期性地在结点及其伙伴间传递. 然而译者认为, 这种传递并非是严格地周期性动作, 即, 两次信息交换之间的时刻间隔不一定是个常数. 因此, 此处翻译为周期性地 大概欠妥 ) 然而

19、最初提供资源的结点 ( Source Node ) 是个例外 它的角色永久是分段的提供者. 在此, 这种结点被称为源结点 ( Origin Node ). 它能够是一个专用于提供视频服务的服务器, 也能够是网络中一个运行了视频服务程序的计算机.本节中, 将讨论模块间的交互以及设计问题. 并给出了当前的一些解决方案. 它们分不被应用于基于PlanetLab的和基于因特网的实现中. A. 结点的加入和成员的治理每个 DONet 结点都有自己的一个唯一标识符 ( Unique Identifier ) 比如能够是它的IP地址 同时维护着一个缓存, 用来存储 DONet 网络中一部分活跃成员的标识符

20、( 以下称该缓存为mCache ). 在一个简单的结点添加算法中, 一个新加入的结点首先去和源结点联系. 源结点会随机地从自己的 mCache 中选择出一个代理结点 ( Deputy Node ), 并将新加入的结点连接重定向到那个代理结点上. 新结点会从代理结点上获得一个成员的列表, 把其中的成员视为候选伙伴. 之后, 与这些候选伙伴建立连接, 由此确定了自己在网络中的伙伴关系. 总体来讲, 这一添加过程是可行的. 因为源结点会在整个流的传输过程中始终存在, 同时它的标识符/地址是众所周知的. 重定向的过程使得新结点能够更加均匀地选择伙伴 ( 译者注: 此处原文为 The redirecti

21、on enables more uniform partner selections for newly joined nodes. 该句的翻译有些过分生硬. 需再斟酌 ), 同时专门大程度上减少了源结点的负载. 本节的最后, 会对那个添加算法的改进进行一些深入探讨. 实践中, 此处遇到的一个关键问题是: 如何建立并更新 mCache. 为了适应网络的动态变化, 每个结点周期性地产生一个成员信息 ( Membership Message ) 用以声明自己的存在; 每个信息包含四项: . 其中, seq_num 表示该信息的序号; id 表示结点的标识符; num_partner 表示结点当前拥

22、有的伙伴数量; time_to_live 表示本条信息剩余的生存时刻. DONet网络中, 成员信息的传递使用了 Scalable Gossip Membership 协议, 即SCAM. 关于那个协议的具体细节, 参考 21. 此处, 仅强调它所具有的三条重要性质: 可扩展 ( Scalable ), 轻量级 ( Light-weight )同时每个结点仅掌握部分信息 ( Uniform Partial View at Each Node ). 当结点收到一个新的成员信息时, 它会在 mCache 中找到对应 id 的成员信息记录, 假如seq_num大于记录中的seq_num, 则更新此条

23、记录. 假如没有找到对应 id 的记录, 则在 mCache 中添加一条记录存储该成员信息. mCache 中, 每条成员信息记录包含五项: . 前四项与成员信息中对应项的意义相同, 是从收到的成员信息中拷贝来的. 第五项记录了最后一次更新该记录的本地时刻.以下两种事件同样可能引起 mCache 中记录的更新: (1) 在会话 ( gossip ) 过程中, 某条记录立即被传递给其他结点; (2) 一个代理结点立即把某条记录传递给新加入的结点. 在这两种情况下, 结点会把相应记录的 time_to_live 减去 current_local_time - last_update_time .

24、假如计算结果小于等于零, 则该条记录会被删除, 同时可不能被传递, 也可不能被加入到伙伴列表. 否则, 关于第二种情况, 代理结点会把该条记录中的num_partner项加一.B. 缓存映像的表示和交换Fig-2 DONet 中的伙伴关系实例 ( A为源结点 )Fig-2 是 DONet 中伙伴关系的一个例子. 如前所述, 在 DONet 网络中, 伙伴关系和数据传输方向都不是固定的. 一个视频流被分解为多个定长的分段. 结点缓存中各个分段的可用性信息被表示为一个缓存映像 ( Buffer Map, BM ). 每个结点会和它的伙伴不断地交换各自的BM. 之后, 通过调度算法, 确定从哪个伙伴

25、处接收哪个分段.关于实时的多媒体流来讲, DONet 结点中的媒体播放过程是一个半同步 ( semi-synchronized) 的过程 ( 译者注: 半同步 一词大概有些前后矛盾. 从字面上看, 翻译为半步 更佳. 然而为了便于理解, 这种矮高粱 似的词汇依旧保留了下来). 分析的结果表明, DONet 中分段传输的平均延时被限制在了一定范围之内. 实验的结果更近一步指出了, 结点之间的拖延专门少高于一分钟. 假设每个分段包含了一秒钟的视频信息, 一个具有 120 个分段长度的滑动窗口便能够有效地构成一个缓存, 而滑动窗口以外的分组则不在结点的考虑范围之内. 如此, 在实现中, 便能够使用1

26、20比特来表示一个BM. 假如其中的某位被置一, 则表明该比特对应的分段有效, 即, 该分段差不多被存储在了缓存中; 反之, 若某比特被置零, 则表明该比特对应的分段无效. 滑动窗口中第一个分段的序号 ( seq_num ) 存储在额外的两个字节中. 关于一个特不长的视频节目来讲, 那个序号可能会由于溢出而被归零 ( 如此的视频节目至少应该大于24小时 ).C. 调度算法 给定了一个结点和它伙伴的BM信息, 调度算法则能够用来确定从哪个伙伴处获得所需的分段. 关于一个同构 ( Homogenous ), 静态 ( Static )的网络, 循环鲁棒 ( Round-robin ) 式的调度便足

27、以. 然而关于一个动态 ( Dynamically ) 同时异构 ( Heterogeneous ) 的网络来讲, 更加智能的算法就显得尤为重要了. 一个调度的结果会受到两个约束条件的阻碍: 每个分段的截止时刻 ( Deadline ), 以及与各个伙伴间的传输带宽. 第一个约束条件表明, 超过截止时刻到达的分段数量应该操纵在最小. 那个问题实际上是 并行计算机调度问题 ( Parallel Machine Scheduling ) 的一个变种, 属于NP类问题 25. 因此专门难找到一个最优解. 从实际角度动身, 调度算法必须能够快速地适应高度动态的网络环境. 因此, 我们采取了一种简单且能

28、够快速响应的启发式 ( Heuristic ) 算法.那个启发式算法中, 首先计算出资源的潜在提供者 ( Potential Supplier ) 的数量 ( 即, 拥有所需分段的伙伴的数量 ). 因为一个分段假如对应着较少的潜在提供者, 那么将意味着那个分段会专门难在截止时刻之前到达. 算法会从仅有一个潜在提供者的分组开始确定某一分组的提供者. 之后是对应有两个潜在提供者的分组, 以此类推. 假如一个分组对应着多个潜在提供者, 那么具有最高带宽同时具有更长可用时刻的提供者会被选中. Fig-3 列出了那个算法的伪码. 关于每个结点, 都将会执行该算法. 它的时刻复杂度为 O( W * B *

29、 M ). 在具体的实现中, 每次执行仅需15ms. 计算的额外开销并不高. 因此, 它能够比较频繁地运行, 从而更新调度策略. Fig-3 每个DONet结点调度算法的伪码( 译者注: 个人认为, 该伪码包含部分打印错误:自Scheduling: 一行起, 向下四行, 有: Tj,i. 个人认为应该改为: tj,i第一个if语句中的for循环, 包含一个循环操纵条件, 原文为: jk. 个人认为应该改为 ji再向下五行, 原文为 suppliern. 个人认为应该改为 supplieri最后一个for循环, 包含一个循环操纵条件, 原文为: jk. 个人认为应该改为 ji以上纯属个人臆断,

30、一切仍以原文为准 )结点通过调度算法的计算获得调度策略, 把需要从同一个伙伴处获得哪些分段的信息存储在一个类似 BM 的位序列中. 之后, 将那个位序列发送给相应的伙伴. 该伙伴会把位序列中所对应的分段通过一个实时的传输协议发送给结点. DONet 并不依靠于某个特定的协议. 和其他系统一样, 目前所采纳的是 TFRC ( TCP-Friendly Rate Control ) 协议 31. BM 信息和调度策略信息能够随数据一并传输. 如此能够快速更新同时减少额外开销.源结点在此始终作为资源提供者. 同时所有的分段都存储在它的缓存中. 为了防止源结点过载, 那个地点给出了一个适应度较高的调度

31、算法. 假如需要, 它还能够通过对外公布保留的缓存映射来操纵负载. 例如, 一个源结点拥有 M 个伙伴, 那么它能够把传递给第 k 个伙伴的 BM 设置为:这确实是讲, 只有第 ( i mod M ) 个伙伴才会从源结点处获得第 i 个分段. 其他的分段则来自不的伙伴. D. 错误的恢复和伙伴的筛选在 DONet 网络中, 一个结点能够在事先声明后退出, 或由于崩溃而意外退出. 这两种情况都能够在TFRC空转一段时刻或者BM信息传递过程中被检测出来. 结点同时离开的概率专门小, 受到离开结点阻碍的结点会立即做出反应 依照剩下伙伴的 BM 信息重构调度策略. 除了那个恢复机制以外, 下面提出的操

32、作也同样用于增强系统的恢复能力. 声明后退出: 立即退出的结点会提交一个退出消息. 那个信息的格式与成员信息一样, 只是num_partner这一项被设为-1.意外退出: 一个结点的意外退出会被它的伙伴检测到. 那个伙伴会代替退出的结点来公布退出消息. 退出消息的传递方式与成员信息的传递方式一样. 假如结点是意外退出的, 冗余的退出消息也许会被退出结点的多个伙伴公布. 然而只有第一个收到的退出消息会被同意接着在网络上传播, 其他的相同信息传播则会被抑制. 每个收到消息的结点会删除各自 mCache 中对应于退出结点的记录.最后, 每个结点会定期地从它的 mCache 中随机选择出结点并与之建立

33、伙伴关系. 这一操作的目的有两个: 第一, 它使得每个结点能够在一些伙伴退出的情况下, 维护一定数量的伙伴; 第二, 它使得结点能够查找到更高质量的伙伴. 在实现中, 一个结点 i 评估它的伙伴结点 j, 使用函数 max si,j, sj,i. 其中, si,j 表示单位时刻内, 结点 i 收到来自结点 j 的分段的平均数量. 直觉上看, 一个具有更大上传带宽和更多可用分段的伙伴会获得更高的评估分数. 由于一个结点既能够是资源提供者, 也能够是接收者, 因此需要计算两个方向上的最大值. 在查找到新的伙伴后, 为了保持伙伴数量的稳定, 伙伴列表中具有最低分数的伙伴将会被抛弃. 伙伴的数量, M

34、 , 是一个专门重要的设计参数. 它的阻碍将会在之后的理论分析和实验中做具体介绍. IV. 网络半径的分析 ( 本节翻译: 默难 )本节将会对 DONet 网络的半径进行分析. 所谓网络半径, 指的是一个分段在传递过程中, 从源结点到所有的目的结点的平均距离. 和大多数文献 11 , 12, 27 相同, 距离的单位是通过网络中结点的跳数. 这在一定程度上反应了端到端的传输延迟. 那个地点用到的分析模型是通过简化的, 结果显示网络半径与网络大小之间成对数关系. 这讲明 , DONet 网络中的端到端延迟是较小的, 足以用来传输实时的流媒体.在 DONet 网络中, 分段可用性信息的传递路径,

35、能够用一棵广度优先搜索 ( BFS, Breadth-First Search) 的树结构来表示. 源结点是树的根结点, 处于第 0 层. 第 k 层的结点与源结点之间相隔 k 跳. DONet 的结点可不能维护一个明确的结构, 因此, 每个结点能够在那个 BFS 树中出现多次.为了描述方便, 把 BFS 树中的结点称为 s-结点 ( s-node ). 依照广度优先搜索的规则, s-结点按照在搜索时被访问的顺序进行编号. 如此, 根结点的编号为 1. 关于编号为 t 的 s-结点, 它所对应的 DONet 结点被表示为 pt ( 译者注: 依照下面(t) 函数的定义, 此处应为 ). 假设伙

36、伴之间的带宽大约相等, 同时一个分段到达一个结点的过程, 是自根结点动身, 按照广度优先的算法搜索树结构, 直到该结点第一次出现. Fig-4 显示了 Fig-2 的 DONet 网络的 BFS 树结构 ( 只列举了三个层次).Fig-4 一棵广度优先搜索的数. 黑色的结点表示(t)等于1的结点. 即第一次出现的结点. 白色结点表示(t)等于零的结点.定义一个辅助函数 (t): 也确实是讲, 只有在 s-结点 t 第一次在树结构中出现时, 函数值才为 1. 由于成员关系和伙伴关系协议是采纳随机的伙伴选择方式, 用 N 表示网络中的结点数量, 因此则有:那个地点, f(t) 表示编号为 1 至

37、t 的 s-结点中, 包含的 DONet 结点的数量. 由此则有: f(t) - f(t-1) = (t). 对 (1) 式两遍同时求期望, 则有:由此推导出:因为 f(1) = 1, 依照等式 (3) 能够推导出:这一关系给出了 DONet 结点数目关于 s-结点编号的函数. 令tk表示第 k 层中最后一个 s-结点的编号, 那么 DONet 网络中其他结点与源结点之间的平均距离, 即网络半径, 则为:注意到, 当 k 趋近于无穷时, 有: . 关于一个连通的网络来讲, 可得:考虑一种稳定的状态: 每个 DONet 结点均拥有 M 个伙伴. 那么对应的 BFS 树中, 除了根结点拥有 M 棵

38、子树外, 每个非叶子结点都拥有 M-1 棵子树. 那么能够导出:将 (6) 式中的连加分解为两部分: 一部分是从 k = 0 到 k = logM-1N; 另一部分是从 k = 1 + log M-1N 到正无穷. 那么有:当 M 大于等于 3 时, 有 (M-1)k = (M-1)k. 则 eM-1k = 450 Kbps )事实上, 超过80%的 CoolStreaming 用户表示 ( 通过 e-mail 或在线统计 ) 能够在总体上稳定地播放视频. 这也证明了一个推测: 是视频服务器有限的处理能力和上传带宽限制了 Internet 上流服务的进展, 而不一定是主干网络. 像 DONet/CoolStreaming 如此以重叠网络为基础的流传播方式, 将是一个可靠的解决方案. 2.数据驱动网络越大, 所传送的数据流质量将会越好在公布了第一个版本之后, 我们并没有提供要紧的升级服务. 而有味的是, 随着用户的增加, 统计结果和用户反馈反而比初期的更好. 从 Fig-17 中也可看出, 随着结点数量的增加, 连续性指标在总体上会变好 - - - 在大多数时刻达到0.95以