论文部分内容阅读
摘要：在实时点播系统中对异步的服务请求的处理，是通过在Peer节点上缓存目标节目部分段的数据，让新节点加入时直接从Peer节点获取数据，可以在很大程度上减少对源服务器带宽资源的占用。基于单棵组播树，本文研究如何对Peer节点进行组织，以适应大规模实时点播系统的应用需求。
关键词：P2P；实时点播；流媒体；对等网络
中图分类号：TP37文献标识码：A文章编号：1009-3044(2008)04-10ppp-0c
P2P Real-time Video on Demand System
LI Jie, LI Yi
(University of Electronic Science and Technology of China, School of Computer and Engineer, Chengdu 610000, China)
Abstract: In real-time video on demand System, in order to process asynchronous service requests, each Peer Node cache part of the whole Media Data. The new rejoining Peer Node gets data from other Peer Node. This method can reduce to a large extent the demand of the source server bandwidth. Multicast tree based on single trees, the paper research how to how to organize Peer nodes, to adapt to large-scale real-time video on demand System application requirements.
Key words: real-time video on demand; Streaming Media; Peer Network
1 引言
由于视频流服务对带宽资源的要求高、服务时间长，使得在Internet上提供实时点播极具挑战性，特别是当某个节目趋向流行时，系统会在短时间内收到大量异步的服务请求，而传统的在服务器端为每个请求单独分配一条流的C/S模式无法容纳大规模的点播请求，因此，如何在一定的部署代价前提下使系统具有高可扩展性也就成为其核心问题。IP组播以其多路复用的方式能够减缓服务器和网络的负载，但众多原因如实现方面的复杂性，拥塞控制、可靠性管理等方面的不足使基于IP组播的实时点播服务在近期内难以得到广泛部署应用。
CDN服务通过在Internet上广泛部署服务节点，把服务内容“推”向网络的“边缘”并把客户请求路由到距客户最近的服务节点，从而减轻服务器的压力和对骨干网络带宽的消耗，但这种方式不仅成本昂贵，月并没有从根本上解决系统可扩展性问题，如当网络中某区域的点播请求数量过大时，部署在该区域的服务节点依然可能成为系统瓶颈。针对实时点播服务，通过在Peer节点上分配一段定长或不定长的数据空间以缓存其所接收到的数据，并为其它请求该数据段的节点提供服务，不但可以满足实时点播中异步模式的服务请求，还可以减轻服务器的负载。一般来说，在P2P实时点播系统的应用研究中面临着如下几个挑战：(1)节点搜索，主要指当节点加入系统时，如何在组播树中快速有效地搜索到合适的父节点，从而缩短节点的加入等待时间；(2)系统容错，P2P模式中的Peer节点不像传统C/S模式中的服务器那样具有高可靠性和可用性，在Peer节点上可能随时发生主动离开或者因软件硬件故障而引起的失效等行为，从而中断其子节点的服务，如何让被中断的节点能够快速有效地进行中断恢复是系统面临的核心问题；(3)协议开销，组播树的建立和维护依赖于控制协议。一般来说，集中式控制协议虽然比较简单但同时也具有单点失效，且当系统规模较大时单个节点也往往难以承担整个系统的协议负载；(4)QoS保证，主要指在Peer节点离开或失效时，如何保证节目的播放质量，如完整性、连续性等。
本文提出了一种P2P环境下的实时点播服务体系，它在系统每个Peer节点上分配一段固定长度的FIFO队列以缓存其最近所接收到的数据，并为其它点播请求该数据段的节点提供服务。该系统具有如下几个特点：(1)采用分布式的控制协议，通过在每个节点上维护有限个其它节点的状态信息，使得当节点加入时能够在短时间内找到合适的父节点，而当节点上发生离开或者失效行为时，子节点能够通过其所维护的状态信息快速准确地找到新的父节点；(2)节点的失效或离开一般不涉及到服务器，从而减轻服务器的负载，系统具有良好的可扩展性；(3)服务被中断的节点在进行中断恢复时，考虑了节点对目标节目接收的完整性；(4)考虑了节点在网络带宽等资源方面所体现出来的异构性。
2 P2P实时点播服务体系及构成
假设目标节目以CBR方式编码和传输，其播放时长为T，目标节目的最小存储和传输单元为数据块，每块的播放时长为一个单位时间，所有数据块按播放先后顺序从1到T予以编号，每个节点上所分配的FIFO缓存队列长度为m。另外，为了系统描述的简单，这里假设节点加入时均从目标节目中第一个数据块开始申请。首先给出描述系统服务体系所需要的几个定义：
定义2.1 系统中共享从源服务器S一个频道所流出数据的Peer节点集合称为一个簇。
定义2.2 簇中直接从源服务器S获取数据的节点称为簇首节点，簇中没有子节点的节点称为簇叶节点。
定义2.3 对于系统中的任一节点，如果该节点上还缓存有目标节目的第一个数据块，则称该节点为开放节点；而对于系统中的任意簇，如果其中至少还包含一个开放节点，则称该簇为开放簇，否则为闭合簇。
显然开放簇能够接受新节点的加入请求，而闭合簇则不能。图1给出了系统在时刻22处的一个运行快照示例，示例中每个节点均能缓存3个数据块。从图1可以看出，节点p1-p7、p8-p13、p14-pl8分别构成了系统中的三个簇，其簇首节点分别为p1、P8、P14前两个簇属于闭合簇，最后一个簇属于开放簇。
图1 实时点播系统在时刻22的运行快照
定义2.4 组播树上沿数据转发路径处于服务器S和pi之间的所有节点(不包括S和pi)称为pi的上游节点，而沿数据转发路径处于pi和簇叶节点之间的所有节点(不包括pi)称为几的下游节点。
定义2.5 对系统中的任意节点pi和pj，如果几在当前时刻缓存了数据块next(pj)，且pi不为pj的父节点，则称pi为pj的候选父节点。
由于在Peer节点上存在离开或失效等动态行为，而当Peer节点作为服务节点时，这些动态行为将导致其子节点服务的中断。考虑系统中节点所缓存的数据块内容一般处于动态更新状态，且在实时点播应用中节点的服务被中断后一般要求从被中断处开始重新获取数据，因此，现有的容错机制如直接从祖父节点或父辈节点恢复获取数据的方式并不能保证节点可以从被中断处恢复所接收的数据，因而这些机制在此都不具有普遍适用性。这里我们提出一种新的容错机制，它在每个节点上保留其候选父节点的状态信息，而当数据服务被中断时节点能够基于这些状态信息快速准确地搜索到新的父节点，从而避免了在整个组播树中进行搜索，不必在每次中断恢复过程中访问源服务器，有效地减轻了源服务器的负载。
3 控制协议
为了维护组播树的逻辑拓扑以及在组播树的节点间正确地转发数据，须在每个节点上维持其父、子节点的有关信息；而为了让服务被中断的节点能够快速进行中断恢复，须在每节点上维持其候选父节点的有关信息；此外，为支持节点的快速加入和中断恢复，对于每个簇首节点，还须维护其簇中部分节点的有关信息。
以节点pi为例，对于其父节点，仅需在pi上记录维护其ip地址、节点状态这两类信息；对于其任一子节点，需在pi上记录维护三类信息：ip地址、节点状态、子节点当前所请求的数据块，后者作为下一时刻向该子节点转发哪个数据块的依据；对于其簇首节点，仅需要维护其ip地址信息；对于其任一候选父节点，除了记录其ip地址外，还需维持其和pi之间的“心跳线”，以确认其当前是否仍处在系统中。
3.1 节点加入
节点(设为pi)在加入系统前，首先向服务器S发送一加入系统的请求消息；S在收到该消息后，分两种情形进行处理：
情形一：如果系统中没有开放簇，则查看其本身是否还有空闲的数据频道：如果有则向Pi返回加入成功的消息并指明其父节点为S，pi在收到该信息后直接加入S，并从S分配获取一新的簇号，置只为空；如果没有则向几返回加入失败的消息，节点加入失败；
情形二：如果系统中还有开放簇，则向所有开放簇的簇首节点转发pi申请加入系统消息；簇首节点在收到该消息后，直接向pi返回簇中所有的开放节点；假设pi所收集到的开放节点集合为A，pi根据预先定义的某种父节点选取原则从A中挑选一父节点，若父节点选取成功(设为pj)，pi直接加入pj；若父节点选取失败，直接申请加入服务器S，其过程类似情形一。对于节点pi和集合A，这里提出三种不同的父节点选取原则：
最快匹配原则：即在A中选择第一个有充足剩余带宽容纳pi加入的节点。这种选择方式不必在A中查询比较每一个节点，从而可以让pi快速加入系统；
最小延迟原则：即在A中选择有充足剩余带宽容纳pi加入，且和pi之间延迟最小的节点。由于组播树建立在应用层，其拓扑结构与物理网络的实际拓扑普遍存在不一致。最小延迟选择方法能在某种程度上减少这种拓扑的不一致，同时也可以减少对骨干网络带宽的消耗；
最小高度原则：即在A中选择有充足剩余带宽容纳pi加入，且其在组播树中高度最小的节点。由于组播树上中间节点的离开或失效行为将直接影响后续子节点对数据的接收。最小高度原则通过选择高度最小的节点作为父节点，能够减小整个组播树的高度，从而减少节点离开或失效对其它节点的影响，提高节目在节点上的平均播放质量。
3.2 节点离开与失效
节点的离开或失效都将引起子节点服务的中断，而为了恢复节点被中断的服务，必须解决两个问题：一是离开或失效节点的检测，二是重新加入时父节点的搜索选择。如果节点为主动离开，则在离开前向其所有的子节点发送LEAVE消息，子节点在收到LEAVE消息后表明其服务将被中断，则由Normal状态转入Disconnected状态。如果节点为失效，由于其在离开系统前无法通知其子节点，因此约定如果节点在规定时间内没有收到任何从其父节点转发而来的数据，则向其父节点发送TEST消息：如果在预定时间内能从其父节点收到WAIT消息反馈，节点转入Suspended状态，否则继续向其父节点发送TEST消息；如果连发三次TEST消息后都不能从其父节点收到WAIT消息反馈，表明其父节点己经失效，子节点转入Disconnected状态；节点一旦从其子节点收到TEST消息，查看本身所处状态，如果为Disconnected或Suspended，则向其反馈WAIT消息，否则向其父节点发送TEST消息，并依此类推。图2给出了节点状态转换图以及相应的转换条件。为了减少节点失效或离开给系统带来的额外开销，规定只有状态为Disconnected的节点才能发起重新加入请求。
图2 节点状态转换图
4 结束语
在Internet上提供大规模的实时点播服务是一项极具挑战性的工作。在P2P网络环境下，本章提出一种基于单棵组播树的实时点播服务体系，它能够以较小的服务器代价实现大规模的实时点播应用。系统中的每个Peer节点均使用定长的FIFO缓存队列来保存其最近所接收到的数据，以便为后续到达的合适节点提供服务。对于组播树的构造和维护，系统使用一种分布式的控制协议，通过在每个节点上维护有限个其它节点的状态信息，使得节点在加入时能快速准确地找到父节点，而当节点上发生离开或者失效等行为时，子节点能够根据其所维护的状态信息快速地找到新的父节点。此外服务被中断的节点在进行中断恢复时，考虑了节点对目标节目接收的完整性。
参考文献：
[1]C.Diot，B.N.Levine，B.Lyles，H.Kassem and D.Balensiefen.Deploymet issues for the IP multicast service and architecture. IEEE Network magazines Special issue on Multicasting，2000,14(l):78-88.
[2]S.Gadde,J.Chase and M.Rabinovich. Web caching and content distribution: a view from the interior. In Proceedings of 5th International Web Caching and Content Delivery Workshop. Lisbon, Portugal: Elsevier Science.
[3]http://ww.akamai.com, Alkamai Website.
[4]http://www.napster.com, Napster Website.
[5]龚海刚, 刘明, 毛莺池, 等. P2P流媒体关键技术的研究进展[J]. 计算机研究与发展, 2005,(12):2033-2040.
[6]周旭, 卢显良, 侯孟书, 等. adPD：一种速度自适应的动态并行下载技术[J]. 计算机科学, 2005,(4):168-170,177.
[7]龚海刚, 刘明, 谢立. P2P流媒体传输的研究进展综述[J]. 计算机科学, 2004,31(9).
收稿日期：2008-01-15
作者简介：李杰（1982-），男，在读硕士研究生，就读于电子科技大学计算机科学与工程学院计算机系统结构专业；李毅，男，博士，电子科技大学教授；研究方向：OS核心、机群技术、对象分布技术、EDA和软计算。
关键词：P2P；实时点播；流媒体；对等网络
中图分类号：TP37文献标识码：A文章编号：1009-3044(2008)04-10ppp-0c
P2P Real-time Video on Demand System
LI Jie, LI Yi
(University of Electronic Science and Technology of China, School of Computer and Engineer, Chengdu 610000, China)
Abstract: In real-time video on demand System, in order to process asynchronous service requests, each Peer Node cache part of the whole Media Data. The new rejoining Peer Node gets data from other Peer Node. This method can reduce to a large extent the demand of the source server bandwidth. Multicast tree based on single trees, the paper research how to how to organize Peer nodes, to adapt to large-scale real-time video on demand System application requirements.
Key words: real-time video on demand; Streaming Media; Peer Network
1 引言
由于视频流服务对带宽资源的要求高、服务时间长，使得在Internet上提供实时点播极具挑战性，特别是当某个节目趋向流行时，系统会在短时间内收到大量异步的服务请求，而传统的在服务器端为每个请求单独分配一条流的C/S模式无法容纳大规模的点播请求，因此，如何在一定的部署代价前提下使系统具有高可扩展性也就成为其核心问题。IP组播以其多路复用的方式能够减缓服务器和网络的负载，但众多原因如实现方面的复杂性，拥塞控制、可靠性管理等方面的不足使基于IP组播的实时点播服务在近期内难以得到广泛部署应用。
CDN服务通过在Internet上广泛部署服务节点，把服务内容“推”向网络的“边缘”并把客户请求路由到距客户最近的服务节点，从而减轻服务器的压力和对骨干网络带宽的消耗，但这种方式不仅成本昂贵，月并没有从根本上解决系统可扩展性问题，如当网络中某区域的点播请求数量过大时，部署在该区域的服务节点依然可能成为系统瓶颈。针对实时点播服务，通过在Peer节点上分配一段定长或不定长的数据空间以缓存其所接收到的数据，并为其它请求该数据段的节点提供服务，不但可以满足实时点播中异步模式的服务请求，还可以减轻服务器的负载。一般来说，在P2P实时点播系统的应用研究中面临着如下几个挑战：(1)节点搜索，主要指当节点加入系统时，如何在组播树中快速有效地搜索到合适的父节点，从而缩短节点的加入等待时间；(2)系统容错，P2P模式中的Peer节点不像传统C/S模式中的服务器那样具有高可靠性和可用性，在Peer节点上可能随时发生主动离开或者因软件硬件故障而引起的失效等行为，从而中断其子节点的服务，如何让被中断的节点能够快速有效地进行中断恢复是系统面临的核心问题；(3)协议开销，组播树的建立和维护依赖于控制协议。一般来说，集中式控制协议虽然比较简单但同时也具有单点失效，且当系统规模较大时单个节点也往往难以承担整个系统的协议负载；(4)QoS保证，主要指在Peer节点离开或失效时，如何保证节目的播放质量，如完整性、连续性等。
本文提出了一种P2P环境下的实时点播服务体系，它在系统每个Peer节点上分配一段固定长度的FIFO队列以缓存其最近所接收到的数据，并为其它点播请求该数据段的节点提供服务。该系统具有如下几个特点：(1)采用分布式的控制协议，通过在每个节点上维护有限个其它节点的状态信息，使得当节点加入时能够在短时间内找到合适的父节点，而当节点上发生离开或者失效行为时，子节点能够通过其所维护的状态信息快速准确地找到新的父节点；(2)节点的失效或离开一般不涉及到服务器，从而减轻服务器的负载，系统具有良好的可扩展性；(3)服务被中断的节点在进行中断恢复时，考虑了节点对目标节目接收的完整性；(4)考虑了节点在网络带宽等资源方面所体现出来的异构性。
2 P2P实时点播服务体系及构成
假设目标节目以CBR方式编码和传输，其播放时长为T，目标节目的最小存储和传输单元为数据块，每块的播放时长为一个单位时间，所有数据块按播放先后顺序从1到T予以编号，每个节点上所分配的FIFO缓存队列长度为m。另外，为了系统描述的简单，这里假设节点加入时均从目标节目中第一个数据块开始申请。首先给出描述系统服务体系所需要的几个定义：
定义2.1 系统中共享从源服务器S一个频道所流出数据的Peer节点集合称为一个簇。
定义2.2 簇中直接从源服务器S获取数据的节点称为簇首节点，簇中没有子节点的节点称为簇叶节点。
定义2.3 对于系统中的任一节点，如果该节点上还缓存有目标节目的第一个数据块，则称该节点为开放节点；而对于系统中的任意簇，如果其中至少还包含一个开放节点，则称该簇为开放簇，否则为闭合簇。
显然开放簇能够接受新节点的加入请求，而闭合簇则不能。图1给出了系统在时刻22处的一个运行快照示例，示例中每个节点均能缓存3个数据块。从图1可以看出，节点p1-p7、p8-p13、p14-pl8分别构成了系统中的三个簇，其簇首节点分别为p1、P8、P14前两个簇属于闭合簇，最后一个簇属于开放簇。
图1 实时点播系统在时刻22的运行快照
定义2.4 组播树上沿数据转发路径处于服务器S和pi之间的所有节点(不包括S和pi)称为pi的上游节点，而沿数据转发路径处于pi和簇叶节点之间的所有节点(不包括pi)称为几的下游节点。
定义2.5 对系统中的任意节点pi和pj，如果几在当前时刻缓存了数据块next(pj)，且pi不为pj的父节点，则称pi为pj的候选父节点。
由于在Peer节点上存在离开或失效等动态行为，而当Peer节点作为服务节点时，这些动态行为将导致其子节点服务的中断。考虑系统中节点所缓存的数据块内容一般处于动态更新状态，且在实时点播应用中节点的服务被中断后一般要求从被中断处开始重新获取数据，因此，现有的容错机制如直接从祖父节点或父辈节点恢复获取数据的方式并不能保证节点可以从被中断处恢复所接收的数据，因而这些机制在此都不具有普遍适用性。这里我们提出一种新的容错机制，它在每个节点上保留其候选父节点的状态信息，而当数据服务被中断时节点能够基于这些状态信息快速准确地搜索到新的父节点，从而避免了在整个组播树中进行搜索，不必在每次中断恢复过程中访问源服务器，有效地减轻了源服务器的负载。
3 控制协议
为了维护组播树的逻辑拓扑以及在组播树的节点间正确地转发数据，须在每个节点上维持其父、子节点的有关信息；而为了让服务被中断的节点能够快速进行中断恢复，须在每节点上维持其候选父节点的有关信息；此外，为支持节点的快速加入和中断恢复，对于每个簇首节点，还须维护其簇中部分节点的有关信息。
以节点pi为例，对于其父节点，仅需在pi上记录维护其ip地址、节点状态这两类信息；对于其任一子节点，需在pi上记录维护三类信息：ip地址、节点状态、子节点当前所请求的数据块，后者作为下一时刻向该子节点转发哪个数据块的依据；对于其簇首节点，仅需要维护其ip地址信息；对于其任一候选父节点，除了记录其ip地址外，还需维持其和pi之间的“心跳线”，以确认其当前是否仍处在系统中。
3.1 节点加入
节点(设为pi)在加入系统前，首先向服务器S发送一加入系统的请求消息；S在收到该消息后，分两种情形进行处理：
情形一：如果系统中没有开放簇，则查看其本身是否还有空闲的数据频道：如果有则向Pi返回加入成功的消息并指明其父节点为S，pi在收到该信息后直接加入S，并从S分配获取一新的簇号，置只为空；如果没有则向几返回加入失败的消息，节点加入失败；
情形二：如果系统中还有开放簇，则向所有开放簇的簇首节点转发pi申请加入系统消息；簇首节点在收到该消息后，直接向pi返回簇中所有的开放节点；假设pi所收集到的开放节点集合为A，pi根据预先定义的某种父节点选取原则从A中挑选一父节点，若父节点选取成功(设为pj)，pi直接加入pj；若父节点选取失败，直接申请加入服务器S，其过程类似情形一。对于节点pi和集合A，这里提出三种不同的父节点选取原则：
最快匹配原则：即在A中选择第一个有充足剩余带宽容纳pi加入的节点。这种选择方式不必在A中查询比较每一个节点，从而可以让pi快速加入系统；
最小延迟原则：即在A中选择有充足剩余带宽容纳pi加入，且和pi之间延迟最小的节点。由于组播树建立在应用层，其拓扑结构与物理网络的实际拓扑普遍存在不一致。最小延迟选择方法能在某种程度上减少这种拓扑的不一致，同时也可以减少对骨干网络带宽的消耗；
最小高度原则：即在A中选择有充足剩余带宽容纳pi加入，且其在组播树中高度最小的节点。由于组播树上中间节点的离开或失效行为将直接影响后续子节点对数据的接收。最小高度原则通过选择高度最小的节点作为父节点，能够减小整个组播树的高度，从而减少节点离开或失效对其它节点的影响，提高节目在节点上的平均播放质量。
3.2 节点离开与失效
节点的离开或失效都将引起子节点服务的中断，而为了恢复节点被中断的服务，必须解决两个问题：一是离开或失效节点的检测，二是重新加入时父节点的搜索选择。如果节点为主动离开，则在离开前向其所有的子节点发送LEAVE消息，子节点在收到LEAVE消息后表明其服务将被中断，则由Normal状态转入Disconnected状态。如果节点为失效，由于其在离开系统前无法通知其子节点，因此约定如果节点在规定时间内没有收到任何从其父节点转发而来的数据，则向其父节点发送TEST消息：如果在预定时间内能从其父节点收到WAIT消息反馈，节点转入Suspended状态，否则继续向其父节点发送TEST消息；如果连发三次TEST消息后都不能从其父节点收到WAIT消息反馈，表明其父节点己经失效，子节点转入Disconnected状态；节点一旦从其子节点收到TEST消息，查看本身所处状态，如果为Disconnected或Suspended，则向其反馈WAIT消息，否则向其父节点发送TEST消息，并依此类推。图2给出了节点状态转换图以及相应的转换条件。为了减少节点失效或离开给系统带来的额外开销，规定只有状态为Disconnected的节点才能发起重新加入请求。
图2 节点状态转换图
4 结束语
在Internet上提供大规模的实时点播服务是一项极具挑战性的工作。在P2P网络环境下，本章提出一种基于单棵组播树的实时点播服务体系，它能够以较小的服务器代价实现大规模的实时点播应用。系统中的每个Peer节点均使用定长的FIFO缓存队列来保存其最近所接收到的数据，以便为后续到达的合适节点提供服务。对于组播树的构造和维护，系统使用一种分布式的控制协议，通过在每个节点上维护有限个其它节点的状态信息，使得节点在加入时能快速准确地找到父节点，而当节点上发生离开或者失效等行为时，子节点能够根据其所维护的状态信息快速地找到新的父节点。此外服务被中断的节点在进行中断恢复时，考虑了节点对目标节目接收的完整性。
参考文献：
[1]C.Diot，B.N.Levine，B.Lyles，H.Kassem and D.Balensiefen.Deploymet issues for the IP multicast service and architecture. IEEE Network magazines Special issue on Multicasting，2000,14(l):78-88.
[2]S.Gadde,J.Chase and M.Rabinovich. Web caching and content distribution: a view from the interior. In Proceedings of 5th International Web Caching and Content Delivery Workshop. Lisbon, Portugal: Elsevier Science.
[3]http://ww.akamai.com, Alkamai Website.
[4]http://www.napster.com, Napster Website.
[5]龚海刚, 刘明, 毛莺池, 等. P2P流媒体关键技术的研究进展[J]. 计算机研究与发展, 2005,(12):2033-2040.
[6]周旭, 卢显良, 侯孟书, 等. adPD：一种速度自适应的动态并行下载技术[J]. 计算机科学, 2005,(4):168-170,177.
[7]龚海刚, 刘明, 谢立. P2P流媒体传输的研究进展综述[J]. 计算机科学, 2004,31(9).
收稿日期：2008-01-15
作者简介：李杰（1982-），男，在读硕士研究生，就读于电子科技大学计算机科学与工程学院计算机系统结构专业；李毅，男，博士，电子科技大学教授；研究方向：OS核心、机群技术、对象分布技术、EDA和软计算。