一种基于数据驱动的多树方式视频系统设计

焦克莹，李新

(1.驻马店职业技术学院，河南 驻马店 463000;2. 驻马店市第三高级中学，河南 驻马店 463000)

0 引 言

当前，交互式网络电视(IPTV)[1]作为三网合一的典型应用技术，其发展趋势愈来愈加深入，其中多媒体视频业务在网络传输中占据越来越大的数据流量，因此需要一种有效的网络视频广播方式来传输高质量的视频。P2P技术[2]是当前较为流行的一种用于支持网络视频广播系统的技术，在文件下载、网络音频通讯等方面都有着非常重要的应用，但是由于网络多媒体视频业务具有实时性要求高、带宽需求量大、参与者数量多等特点，使得P2P网络视频广播系统存在频道切换慢、源端时延长、播放连续性低与控制开销大等问题。近几年，国内外学者对于采用P2P技术的网络视频广播系统进行了卓有成效的研究[3-4]。根据数据分发方式的不同，传统用于支持视频广播的网络组播技术主要有两种类型[5]：基于树的组播分发方式与基于数据驱动的随机组播分发方式。基于树的组播分发方式是以节目源作为根节点来构建组播分发树(一颗或者多颗)，采用“推”的方法从父节点向各子节点推送视频数据，该分发方式的不足之处在于其波动环境下的健壮性差，其中采用该方式的常见视频广播系统主要有ESM[6]、SplitStream[7]等。基于数据驱动的随机组播分发方式主要是为了解决节点随机失效问题提出的，采用“拉”的方法随机从不同节点中获取视频数据，该分发方式的不足之处在于其随机分发方式无法保证视频服务质量，其中采用该方式的常见视频广播系统主要有CoolStreaming[8]、PPLive[9]等。由于P2P视频广播系统尽管采用基于数据驱动的随机组播分发方式，但是其大部分数据传输路径均保持与某些特定树一致[10]。因此，文中通过结合两种传统的组播分发方式，给出了一种基于数据驱动的多树方式视频系统设计(a design of video system based on Data-Driven MultiTree approach, DDMT)，能够有效保证视频广播系统的健壮性和视频服务质量[1-2]。

1 系统设计

所给DDMT视频系统的基本思想是，首先将视频数据流划分成大小相等的数据段，从节目源开始将这些数据段推送到多颗树的根节点，最终推送到整个网络视频系统覆盖网的全部节点；然后希望收看该视频的用户通过同时加入多颗树，采用“拉”的方法获取所需实时性数据段。在整个网络视频系统覆盖网的全部节点中，除节目源节点以外，其余节点不仅是数据段的接收者，同时也可作为数据段的转发者，且全部节点均可自由加入或退出该网络视频系统。所给DDMT视频系统设计主要包括三个方面内容：1) 基于多树的连接节点管理，该算法应使节点具有自组织性、支持邻近性、可扩展性、可靠性的连接关系。2) 节点关系修复是指在节点主动退出或突然失效的情况下，能够对连接节点关系进行修复，以保证每个节点能够维持稳定的连接节点数量。3) 数据段调度可通过优化以避免数据冗余，同时实现系统的最大效率，目的是保证为用户提供良好的视频服务体验。

1.1 连接节点管理

在所给DDMT视频系统中，每个节点均被赋予128比特的唯一身份标识符，且各节点通过同时加入多颗树以形成网状拓扑结构，以此来管理节点的连接关系。与传统基于树的组播分发方式不同的是，所给DDMT视频系统的树均是双向推送，这是由于每个节点加入多颗树形成的网络结构使得节点即是数据接收者，同时也是数据转发者。所给DDMT视频系统以Pastry[11]为基础，主要通过反向路径转发方法来构造多树结构，每颗树都是以自身的汇聚节点作为根节点，然后加入节点发送一个以汇聚节点为目的节点的申请加入消息，那么由该加入节点到汇聚节点的Pastry路由路径即为该节点加入的树。该节点加入其它树的方法均按照这种方式，即可实现加入多颗树形成网状拓扑结构。图1给出了所给DDMT视频系统中节点的多树连接关系。其中，节点A、B和C表示汇聚节点，其余节点均表示叶子节点[3]。

图1 所给DDMT视频系统中节点的多树连接关系

由图1可以看出，每个节点同时加入了多个树，且每个节点均有多个父节点与叶子节点。但是为了降低开销以及保证数据段有足够资源扩散，因此一个节点连接节点的数量是有限制的，这就需要连接节点管理算法来实现多树构建过程中某一节点的出度限制。所给DDMT视频系统的连接节点管理策略如下所示：

(1)当一个汇聚节点探测其连接的节点数量已经达到出度限制时，则该节点在其加入的多颗树中查找资源消耗最多的树；

(2)该汇聚节点根据邻近性参数，在所查找到的树中选择出距离最远的叶子节点并进行丢弃，同时向各叶子节点发送丢弃消息，该消息还包含该节点拥有的叶子节点列表以及各叶子节点距离自身的延迟；

(3)各叶子节点收到该消息后，执行如下步骤：

①叶子节点计算其自身与所接收的叶子节点列表中各节点的延迟；

②该叶子节点计算其自身到汇聚节点的总延迟；

③该叶子节点向能够提供最小总延迟的节点发送加入消息，即可使其到达汇聚节点的总延迟最小。

1.2 节点关系修复

当存在节点主动退出或者突然失效的情况时，需要对节点间的连接关系进行修复。如果是节点主动退出的情况，则该节点会主动向其所连接节点发送退出消息；如果是节点突然失效的情况，则该节点会因在一定时间内未与汇聚节点进行信息交互而被探测到[4-6]。在出现上述节点主动退出或突然失效情况下，所给DDMT视频系统的连接节点关系修复策略如下所示：

(1)如果主动退出或突然失效的节点是父节点，那么该节点的子节点可通过调用Pastry路由向汇聚节点发送消息，同时发现一个新的父节点作为其连接节点，以此修复节点的连接关系；

(2)如果主动退出或突然失效的节点在其加入的全部树中均为叶子节点，那么该节点在其加入的全部树中的父节点可通过构建新树来发现新的节点。

1.3 数据段优化调度

如果要实现一个节点如何决定其需从连接节点所获得的数据段，则需要一个有效的调度算法，且该算法需满足两个必要的限制条件：1) 每个数据段的提交时限；2) 每个连接节点的带宽大小。所给DDMT视频系统在综合考虑传播时延大小、数据段数、带宽大小与候选节点数量的情况下，给出了一种简单、时延小、播放连续性高的数据段调度策略，其具体过程描述如下所示：

(1)优先调度即将需要播放的数据段，即该数据段即将到达播放提交时限时需优先调度；

(2)由于提供者较少的数据段要比提供者较多的数据段更易获取，所以应优先调度提供者较少的数据段(尤其是仅有一个提供者的数据段应最优先调度)，即候选节点越少的数据段越应优先调度；

(3)当从某个连接节点同时请求获取多个可用数据段时，首先计算所有数据段总延时的平均值，优先调度平均延时最小的候选节点中的数据段，以实现在相同时间获取最多数据段[7]。

2 性能分析

2.1 可扩展性分析

(1)

从式(1)可以看出，所给DDMT视频系统中节目源节点到各节点的平均跳数复杂度是O(logN)，由此表明所给DDMT视频系统具有良好的可扩展性，其节点规模可以扩展到非常大的程度。

2.2 时延分析

假设所给DDMT视频系统中节点的分布为一个圆且其半径为r，则两节点间的时延为其实际物理距离。由于在所给DDMT视频系统中的节点均是通过在多颗树中选择距离其最近的节点来“拉”取所需的数据段，所以所给DDMT视频系统中的第i跳时延不大于Pastry路由路径的第i跳时延。则可知所给DDMT视频系统中的第i跳时延D1(i)，如式(2)所示：

D1(i)=r·cos-1(1-2t(i+1)+1/N)

(2)

其中，由于经典的CoolStreaming视频系统是基于数据驱动机制、采用网状拓扑结构的网络视频系统，相互间的连接节点是随机的，所以其每一跳的时延近似于两点间的平均距离，则CoolStreaming视频系统中每一跳时延D2(i)，如式(3)所示：

D2(i)=π·r/2

(3)

由式(2)和(3)可以看出，D1(i)

3 仿真试验

仿真试验采用PeerSim模拟器[12]，主要用于评估在稳定环境下与波动环境下，所给DDMT视频系统的切换时延、源端时延、播放连续性以及控制开销/波动开销四个方面性能，并与经典的网络视频系统CoolStreaming与Tree进行性能比较。假定仿真试验前所有主机节点均已加入网络视频系统中。其中，路由器节点的数目为100个，主机节点的数目为1200个，路由器节点之间的平均时延是216 ms，主机节点到连接路由器节点的时延是1 ms，视频流持续时间是0.2×106ms，节目源节点在0时刻开始发送数据段，所得最终仿真试验结果均是统计10次仿真试验结果的平均值。

3.1 稳定环境下的仿真

稳定环境下是指在仿真过程中没有节点主动退出或者突然失效的情况，全部节点均保持加入状态。仿真参数设置如下：视频的编码速率为0.3 Mbps，主机节点的带宽大小为1 Mbps，一个节点的平均连接节点数目为8个，数据段的大小为0.08×106bit，缓冲区中视频缓冲时间为32 s，每个节点的视频播放开始时间均在视频缓冲6s后。则下面分别给出随着网络视频系统中节点数量的变化，所给DDMT、Tree以及CoolStreaming三种网络视频系统方案在切换时延(图2)、源端时延(图3)、播放连续性(图4)与控制开销(图5)方面的性能比较。

图2 三种方案随节点数量变化的切换时延比较

图3 三种方案随节点数量变化的源端时延比较

图4 三种方案随节点数量变化的播放连续性比较

图5 三种方案随节点数量变化的控制开销比较

由图2可以看出，在节点数量相同的情况下，所给DDMT视频系统所需的切换时延均更小。在节点数量为1200个时，所给DDMT视频系统的切换时延分别比Tree和CoolStreaming低了70.37%和65.22%。由图3可以看出，在节点数量相同的情况下，所给DDMT视频系统的源端时延同样也都更小。在节点数量为1200个时，所给DDMT视频系统的源端时延分别比Tree和CoolStreaming低了43.75%和70%。由图4可以看出，在节点数量相同的情况下，所给DDMT视频系统的播放连续性要优于Tree和CoolStreaming。在节点数量为1200个时，Tree视频系统的播放连续性为43%，CoolStreaming视频系统的播放连续性为88%，而所给DDMT视频系统则可达到98%。由图5可以看出，在节点数量相同的情况下，所给DDMT视频系统的控制开销要低于Tree和CoolStreaming。在节点数量为1200个时，Tree视频系统的控制开销为1.29%，CoolStreaming视频系统的播放连续性为1.33%，而所给DDMT视频系统则仅有1.24%。由上述仿真结果可知，在稳定环境下，所给DDMT视频系统的整体性能优于Tree和CoolStreaming[8-11]。

3.2 波动环境下的仿真

波动环境下是指在仿真过程中有节点主动退出或者突然失效的情况，此时视频网络中需要进行节点关系修复，将会产生一定的波动开销以稳定视频网络中数据段的传输。仿真参数设置与稳定环境下的参数设置相同。则下面分别给出随着网络视频系统中失效节点比例的变化，所给DDMT、Tree以及CoolStreaming三种网络视频系统方案在切换时延(图6)、源端时延(图7)、播放连续性(图8)与波动开销(图9)方面的性能比较。

图6 三种方案随失效节点比例变化的切换时延比较

图7 三种方案随失效节点比例变化的源端时延比较

图8 三种方案随失效节点比例变化的播放连续性比较

图9 三种方案随失效节点比例变化的控制开销比较

由图6可以看出，在失效节点比例相同的情况下，所给DDMT视频系统所需的切换时延均更小。在失效节点比例为8%时，所给DDMT视频系统的切换时延分别比Tree和CoolStreaming低了71.43%和59.73%。由图7可以看出，在失效节点比例相同的情况下，所给DDMT视频系统的源端时延同样也都更小。在失效节点比例为8%时，所给DDMT视频系统的源端时延分别比Tree和CoolStreaming低了60.61%和56.38%。由图8可以看出，虽然随着失效节点比例增大，所给DDMT视频系统的播放连续性降低，但在失效节点比例相同的情况下，所给DDMT视频系统的播放连续性仍然要优于Tree和CoolStreaming。在失效节点比例为8%时，Tree视频系统的播放连续性为20%，CoolStreaming视频系统的播放连续性为59%，而所给DDMT视频系统则可达到79%。由图9可以看出，随着失效节点比例增大，所给DDMT视频系统的波动开销也逐渐增加，但增加的幅度要小于Tree和CoolStreaming。在失效节点比例达到4%之后，所给DDMT视频系统的波动开销低于Tree和CoolStreaming。在失效节点比例为8%时，Tree视频系统的控制开销为1.25%，CoolStreaming视频系统的播放连续性为1.43%，而所给DDMT视频系统则仅有0.88%。由上述仿真结果可知，在波动环境下，所给DDMT视频系统的整体性能同样要优于Tree和CoolStreaming[12]。

4 结 语

随着当前对于多媒体视频业务的需求愈来愈大，需要低切换时延、低源端时延、低控制开销和高播放连续性的视频广播系统。P2P视频网络技术是当前一种流行的视频广播系统，它是基于数据驱动方式进行数据传输的，其拓扑结构为网状结构，但其大部分传输路径与特定树保持一致，所以文中结合基于数据驱动方式和基于树的方式，给出了一种基于数据驱动的多树方式视频系统设计，分别给出了连接节点管理策略、节点关系修复策略和数据段调度优化策略。通过性能分析可知，所给DDMT视频系统设计具有较好的可扩展性和较低的切换时延。仿真结果表明，与经典的Tree和CoolStreaming视频系统相比，所给DDMT视频系统更低的切换时延、更低的源端时延、更高的播放连续性以及更小控制开销，是一种有较好用户体验的网络视频广播系统，具有较好的理论研究实际应用价值。

[1] THAM M L, CHOW C O, XU Y H, et al. Seam handover between unicast and multicast multimedia streams[J].Journal of Zhejiang University-Science C (Computers & Electronics)，2014, 15(10)：929-942.

[2] CHEN Z,FENG G, LU Y, et al. Improving playback quality of peer-to-peer live streaming systems by joint scheduling and distributed hash table based compensation[J]. China Communications, 2013,(6): 127-145.

[3] 李润知，张茜，林予松.对等流媒体数据调度优化算法[J].计算机工程与设计，2014，35(7): 2447-2452.

[4] CHE Y Z, CHIEW K, HONG X Y,et al. EDA: an enhanced dual-active algorithm for location privacy preservation in mobile P2P networks.Journal of Zhejiang University-Science C (Computers & Electronics)，2013, 14(5): 356-373.

[5] XIA H L, WANG N, ZENG Z M.Neighbor peer selection scheme based on effective capacity for mobile peer-to-peer streaming[J].China Communications, 2013,(5): 89-98.

[6] CHU Y, RAO S G, SESHAN S, et al. A case for end system multicast[C]//In Proceedings of ACM International Conference on Measurement and Modeling of Computer Systems, Santa Clara: ACM，2000: 1-12.

[7] CASTRO M, DRUSCHEL P, KERMARREC A M, et al. SplitStream: high-bandwidth multicast in cooperative environment[C]//In Proceedings of the ACM Symposium on Operating Systems Principles, New York: ACM，2003: 298-313.

[8] 龚尚福，朱建雷，冯健.一种基于复杂网络的P2P流媒体拓扑构建算法[J].计算机应用研究，2013，30(4): 1149-1151.

[9] 蒋海明，张剑英，赵二涛，等.PPLive网络电视通信机制研究[J].电视技术，2009，34(12): 61-63.

[10] POUWELSE J,GARBACKI P, EPEMA D, et al. The bittorrent P2P file-sharing system: measurements and analysis[C]//In Proceedings of International Workshop on Peer-to-Peer Systems, Ithaca: IEEE，2005: 205-216.

[11] 刘世朋，邓亚平.一种改进的Pastry路由机制[J].计算机工程与应用，2010，46(21): 103-105.

[12] 常国峰，索岩.单码流场景下P2P流媒体直播数据调度方法[J].电视技术，2013，37(15): 93-95.