CoolStreaming/DONet: 一个用于实时流媒体传输的数据驱动型重叠网络 ( 第三节 )

III. DONet的设计与优化

Fig-1 一个DONet结点的系统架构图

Fig-1 是一个 DONet 结点中的系统架构图. 其中有三个重要模块: (1) 成员管理模块 ( Membership Manager ). 负责维护网络中一部分结点的相关信息; (2) 伙伴管理模块 ( Partnership Manager ). 负责与网络中的其他结点建立并维护伙伴关系 ( 译者注: 原文中的``Member''一词此处被翻译为``成员''; ``Partner''被译为``伙伴''. 二者区别为: 网络中的一个结点被称为这个网络中的成员; 网络中两个直接相连的结点互为伙伴. ); (3) 调度器 ( Scheduler ). 负责视频数据传输过程的调度工作. 一个 DONet 结点的角色相对于视频流中的每一个分段 ( Segment ), 既可以是分段的接收者 ( Receiver ), 也可以是提供者 ( Supplier ), 或二者皆是. 结点角色的确定会根据分段的可用性信息 ( Segment's Availability Information ), 动态地调整. 分段的可用性信息会在结点及其伙伴之间周期性地传递. ( 译者注: 原文中使用的是 ``periodically exchanged between the node and its partners''. 翻译为``周期性地在结点及其伙伴间传递''. 但是译者认为, 这种传递并非是严格地周期性动作, 即, 两次信息交换之间的时间间隔不一定是个常数. 因此, 此处翻译为``周期性地'' 似乎欠妥 ) 但是最初提供资源的结点 ( Source Node ) 是个例外 --- 它的角色永远是分段的提供者. 在此, 这种结点被称为``源结点'' ( Origin Node ). 它可以是一个专用于提供视频服务的服务器, 也可以是网络中一个运行了视频服务程序的计算机.

本节中, 将讨论模块间的交互以及设计问题. 并给出了当前的一些解决方案. 它们分别被应用于基于PlanetLab的和基于因特网的实现中.

A. 结点的加入和成员的管理

每个 DONet 结点都有自己的一个唯一标识符 ( Unique Identifier ) --- 比如可以是它的IP地址 --- 并且维护着一个缓存, 用来存储 DONet 网络中一部分活跃成员的标识符 ( 以下称该缓存为mCache ). 在一个简单的结点添加算法中, 一个新加入的结点首先去和源结点联系. 源结点会随机地从自己的 mCache 中挑选出一个代理结点 ( Deputy Node ), 并将新加入的结点连接重定向到这个代理结点上. 新结点会从代理结点上获得一个成员的列表, 把其中的成员视为候选伙伴. 之后, 与这些候选伙伴建立连接, 由此确定了自己在网络中的伙伴关系.

总体来说, 这一添加过程是可行的. 因为源结点会在整个流的传输过程中始终存在, 并且它的标识符/地址是众所周知的. 重定向的过程使得新结点可以更加均匀地选择伙伴 ( 译者注: 此处原文为 `` The redirection enables more uniform partner selections for newly joined nodes''. 该句的翻译有些过分生硬. 需再斟酌 ), 同时很大程度上减少了源结点的负载. 本节的最后, 会对这个添加算法的改进进行一些深入探讨.

实践中, 此处遇到的一个关键问题是: 如何建立并更新 mCache. 为了适应网络的动态变化, 每个结点周期性地产生一个成员信息 ( Membership Message ) 用以声明自己的存在; 每个信息包含四项: <seq_num, id, num_partner, time_to_live>. 其中, seq_num 表示该信息的序号; id 表示结点的标识符; num_partner 表示结点当前拥有的伙伴数量; time_to_live 表示本条信息剩余的生存时间. DONet网络中, 成员信息的传递使用了 Scalable Gossip Membership 协议, 即SCAM. 关于这个协议的具体细节, 参考 [21]. 此处, 仅强调它所具有的三条重要性质: 可扩展 ( Scalable ), 轻量级 ( Light-weight )并且每个结点仅掌握部分信息 ( Uniform Partial View at Each Node ). 当结点收到一个新的成员信息时, 它会在 mCache 中找到对应 id 的成员信息记录, 如果seq_num大于记录中的seq_num, 则更新此条记录. 如果没有找到对应 id 的记录, 则在 mCache 中添加一条记录存储该成员信息. mCache 中, 每条成员信息记录包含五项: <seq_num, id, num_partner, time_to_live, last_update_time>. 前四项与成员信息中对应项的意义相同, 是从收到的成员信息中拷贝来的. 第五项记录了最后一次更新该记录的本地时间.

以下两种事件同样可能引起 mCache 中记录的更新: (1) 在会话 ( gossip ) 过程中, 某条记录即将被传递给其他结点; (2) 一个代理结点即将把某条记录传递给新加入的结点. 在这两种情况下, 结点会把相应记录的 time_to_live 减去 current_local_time - last_update_time . 如果计算结果小于等于零, 则该条记录会被删除, 并且不会被传递, 也不会被加入到伙伴列表. 否则, 对于第二种情况, 代理结点会把该条记录中的num_partner项加一.

B. 缓存映像的表示和交换

Fig-2 DONet 中的伙伴关系实例 ( A为源结点 )

Fig-2 是 DONet 中伙伴关系的一个例子. 如前所述, 在 DONet 网络中, 伙伴关系和数据传输方向都不是固定的. 一个视频流被分解为多个定长的分段. 结点缓存中各个分段的可用性信息被表示为一个缓存映像 ( Buffer Map, BM ). 每个结点会和它的伙伴不断地交换各自的BM. 之后, 通过调度算法, 确定从哪个伙伴处接收哪个分段.

对于实时的多媒体流来说, DONet 结点中的媒体播放过程是一个半同步 ( semi-synchronized) 的过程 ( 译者注: ``半同步'' 一词似乎有些前后矛盾. 从字面上看, 翻译为``半步'' 更佳. 但是为了便于理解, 这种``矮高粱'' 似的词汇还是保留了下来). 分析的结果表明, DONet 中分段传输的平均延时被限制在了一定范围之内. 实验的结果更近一步指出了, 结点之间的迟延很少高于一分钟. 假设每个分段包含了一秒钟的视频信息, 一个具有 120 个分段长度的滑动窗口便可以有效地构成一个缓存, 而滑动窗口以外的分组则不在结点的考虑范围之内. 如此, 在实现中, 便可以使用120比特来表示一个BM. 如果其中的某位被置一, 则表明该比特对应的分段有效, 即, 该分段已经被存储在了缓存中; 反之, 若某比特被置零, 则表明该比特对应的分段无效. 滑动窗口中第一个分段的序号 ( seq_num ) 存储在额外的两个字节中. 对于一个非常长的视频节目来说, 这个序号可能会由于溢出而被归零 ( 这样的视频节目至少应该大于24小时 ).

C. 调度算法

给定了一个结点和它伙伴的BM信息, 调度算法则可以用来确定从哪个伙伴处获得所需的分段. 对于一个同构 ( Homogenous ), 静态 ( Static )的网络, 循环鲁棒 ( Round-robin ) 式的调度便足以. 但是对于一个动态 ( Dynamically ) 并且异构 ( Heterogeneous ) 的网络来说, 更加智能的算法就显得尤为重要了. 一个调度的结果会受到两个约束条件的影响: 每个分段的截止时间 ( Deadline ), 以及与各个伙伴间的传输带宽. 第一个约束条件表明, 超过截止时间到达的分段数量应该控制在最小. 这个问题实际上是 `` 并行计算机调度问题 ''( Parallel Machine Scheduling ) 的一个变种, 属于NP类问题 [25]. 因此很难找到一个最优解. 从实际角度出发, 调度算法必须能够快速地适应高度动态的网络环境. 因此, 我们采取了一种简单且能够快速响应的启发式 ( Heuristic ) 算法.

这个启发式算法中, 首先计算出资源的潜在提供者 ( Potential Supplier ) 的数量 ( 即, 拥有所需分段的伙伴的数量 ). 因为一个分段如果对应着较少的潜在提供者, 那么将意味着这个分段会很难在截止时间之前到达. 算法会从仅有一个潜在提供者的分组开始确定某一分组的提供者. 之后是对应有两个潜在提供者的分组, 以此类推. 如果一个分组对应着多个潜在提供者, 那么具有最高带宽并且具有更长可用时间的提供者会被选中. Fig-3 列出了这个算法的伪码. 对于每个结点, 都将会执行该算法. 它的时间复杂度为 O( W * B * M ). 在具体的实现中, 每次执行仅需15ms. 计算的额外开销并不高. 因此, 它可以比较频繁地运行, 从而更新调度策略.

( 译者注: 个人认为这个伪码有些打字错误:

自Scheduling: 起向下第四行, 有T[j,i], 个人认为应该为 t[j,i]

再向下8行, 一个for语句中包含控制条件为j > k; 个人认为应该是 j > i

再向下13行, else语句中, 有一个supplier[n] <- null; 个人认为应该为supplier[i] <- null

最后一个end for n语句向上五行, 有一个for语句, 其中的控制条件为: j > k; 个人认为应该是 j > i

以上纯属个人臆断. 一切仍以原稿为准 )

结点通过调度算法的计算获得调度策略, 把需要从同一个伙伴处获得哪些分段的信息存储在一个类似 BM 的位序列中. 之后, 将这个位序列发送给相应的伙伴. 该伙伴会把位序列中所对应的分段通过一个实时的传输协议发送给结点. DONet 并不依赖于某个特定的协议. 和其他系统一样, 目前所采用的是 TFRC ( TCP-Friendly Rate Control ) 协议 [31]. BM 信息和调度策略信息可以随数据一并传输. 这样可以快速更新并且减少额外开销.

源结点在此始终作为资源提供者. 并且所有的分段都存储在它的缓存中. 为了防止源结点过载, 这里给出了一个适应度较高的调度算法. 如果需要, 它还可以通过对外公布保留的缓存映射来控制负载. 例如, 一个源结点拥有 M 个伙伴, 那么它可以把传递给第 k 个伙伴的 BM 设置为:

这就是说, 只有第 ( i mod M ) 个伙伴才会从源结点处获得第 i 个分段. 其他的分段则来自别的伙伴.

D. 错误的恢复和伙伴的精简

在 DONet 网络中, 一个结点可以在事先声明后退出, 或由于崩溃而意外退出. 这两种情况都可以在TFRC空转一段时间或者BM信息传递过程中被检测出来. 结点同时离开的概率很小, 受到离开结点影响的结点会立即做出反应 --- 根据剩下伙伴的 BM 信息重构调度策略. 除了这个恢复机制以外, 下面提出的操作也同样用于增强系统的恢复能力.

声明后退出: 即将退出的结点会提交一个退出消息. 这个信息的格式与成员信息一样, 只是num_partner这一项被设为-1.

意外退出: 一个结点的意外退出会被它的伙伴检测到. 这个伙伴会代替退出的结点来发布退出消息.

退出消息的传递方式与成员信息的传递方式一样. 如果结点是意外退出的, 冗余的退出消息也许会被退出结点的多个伙伴发布. 但是只有第一个收到的退出消息会被允许继续在网络上传播, 其他的相同信息传播则会被抑制. 每个收到消息的结点会删除各自 mCache 中对应于退出结点的记录.

最后, 每个结点会定期地从它的 mCache 中随机选择出结点并与之建立伙伴关系. 这一操作的目的有两个: 第一, 它使得每个结点可以在一些伙伴退出的情况下, 维护一定数量的伙伴; 第二, 它使得结点可以寻找到更高质量的伙伴. 在实现中, 一个结点 i 评估它的伙伴结点 j, 使用函数 max{ s_{i,j}, s_{j,i}}. 其中, s_{i,j} 表示单位时间内, 结点 i 收到来自结点 j 的分段的平均数量. 直觉上看, 一个具有更大上传带宽和更多可用分段的伙伴会获得更高的评估分数. 由于一个结点既可以是资源提供者, 也可以是接收者, 因此需要计算两个方向上的最大值. 在寻找到新的伙伴后, 为了保持伙伴数量的稳定, 伙伴列表中具有最低分数的伙伴将会被抛弃. 伙伴的数量, M , 是一个很重要的设计参数. 它的影响将会在之后的理论分析和实验中做具体介绍.