流媒体树状结构的研究与优化

摘要：针对当前树状流媒体系统结构由于结构与算法复杂而造成的视频块传输延迟问题，逻辑网络与物理网络拓扑失配等问题，该文提出了一种流媒体树状结构的构建与维护算法doubletree，并且讨论了该结构改进的DHT关键词构建方法，算法分析结果显示doubletree可以获得更高的传输效率与服务质量。

关键词：流媒体；树状；回放；DRPSS；DHT关键词

中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2013）13-3152-03

随着网络和流媒体技术的高速发展，传统的客户端与服务器C/S（Client/Server）网络结构在客户端增多的情况下，由于服务器与客户端的单通道传输结构，往往导致视频传输质量下降，服务器拥塞，甚至服务器瘫痪等问题。所以C/S网络结构已经无法满足流媒体系统中客户端对视频流的请求。为解决服务器瓶颈，网络扩展等问题，P2P技术应运而生。P2P技术是一种对等网络技术，P2P网络结构中没有中心节点，每一个节点既是客户端又是服务器。所以P2P技术可以很好的降低服务器带宽资源和网络拥塞问题，具有较高的扩展性和性价比。

P2P网络拓扑结构大致可分为3种类型： 树状，网状和DHT结构。由于树状结构相对于网状和DHT结构的扩展性好，并且控制开销较小，所以当前很多P2P流媒体系统都是基于树状结构建立的。代表流媒体系统有NICE[[1]]，Bullet[[2]]和oStream[[3]]。NICE通过分层和聚类的方式来组建大规模流媒体组播树，提高了扩展性，但是增加了中间节点的中转压力。Bullet和ostream分别通过节点间的正交协作算法和启发式算法来构建较小链路消耗的流媒体组播树，减低了系统的传输消耗，但是算法的实现较为复杂，增加了系统传输的时间延迟。

本文通过对流媒体树状结构特点的分析，结合splitstream[[4]]流媒体系统的正交树结构思想，提出了中心化流媒体树状结构。通过中心控制节点（根节点）和TT算法对流媒体树状结构进行建立和维护。

1 相关知识

1.1 流媒体树状结构分析

对于树结构的建立和维护，应该考虑一下几个问题。

1）树的规模：树应该尽可能的短，在根节点与叶子节点之间，中间节点应尽可能少。短树结构将会减少由于节点离开和失效，父节点阻塞等原因造成的组播树的崩溃。由于它的短小，每棵树由于将会被平衡，需要可能的繁盛，例如，每个节点的出度将会达到它带宽的上限，但是，由于出度的增大，也会因为其它应用程序竞争带宽而造成流媒体树的崩溃。

2）树的多样性与有效性：组播树应该具有多样性。例如，一个节点的父节点的集合在一棵树中应尽可能不相连。但是，追求多样性将会影响拥有一棵有效的生成树。例如，一棵树的结构很符合覆盖网拓扑结构，网络中的三个节点，一个在北京，一个在广州，一个在香港，如果父节点可以相连，则树结构北京——广州——香港，将会比广州——北京——香港这个具有父子关系的树结构更有效。

3）节点的加入与离开：节点的加入和离开过程应该尽可能的快，这样才能使有兴趣的节点尽快的加入树结构获取视频流，并且拥有最小的干扰，只需一个网络来回的加入和离开过程将会是干扰最小的策略。

4）可扩展性：树的管理算法应该适应大规模节点数量和高速率的节点加入与离开。

以上问题的一些目标是互相矛盾的，因为我们考虑流媒体应用程序是不相关的，所以适当的延迟是可以接受的，又因为恢复力是流媒体结构节点加入和维护的主要目标，所以本文选择创建一棵伴随着快速的加入和离开的多样性的短树。

1.2 建立内部节点不相交树

2 中心控制的树结构和doubletree算法

为了使节点快速的加入和离开，该文使用了中心控制的树管理策略，由一个中心节点管理树的建立和维护，通常设置为树的根节点，根节点一般比普通节点更有资源和更加有用，节点加入和离开操作只需要一或两个网络往返——一次去根节点，一次去新的父节点。

依赖根节点意味着系统不再是自组织的，但这只是对控制传输的，对于数据传输其仍然是自扩展的。为了避免根节点造成的系统瓶颈问题，本设计将其扩展为一个根节点簇，然后随机指定客户端去连接其中一个根节点。由于整个根节点簇带宽的增大，它将导致更短，更有效的分布树。

2.1 树的中心管理

根节点具有树的所有管理机能，当一个节点要加入时，节点将联系根节点，根节点将会发送给新加入节点一个指定的父节点的信息。然后，新节点联系其指定节点作为父节点接收数据流。当一个节点正常离开时，它将通知根节点，然后根节点将会为离开节点的子节点找到一个新的父节点，并且通知双方互相的存在。

如果是节点异常离开，节点监视器将监视节点的丢包率，如果丢包数量达到一定的上线，节点将会检查其父节点是否也处于这种情况，如果父节点也处于此情况，则等待父节点处理此问题，如果父节点没有此问题，或父节点失效，则节点将连接根节点获取另一个父节点。

2.2 DoubleTree算法

当一个新节点加入时，我们首先决定这个节点是作为中间节点或是叶子节点加入一棵树中，TT算法采用与SplitStream相同的机制，即一个节点只在一棵树中为内部节点，而在其他树中均为叶子节点。TT算法首先找出在一棵树中中间节点最少的树，然后将新节点作为其中间节点加入此树，这样做的目的是使中间节点的节点数在每课树中是平衡的。

一个新节点作为中间节点加入树中时，首先找到根节点，根节点通过搜索其信息结合分配给新节点一个拥有多余带宽的一个中间节点，或者有一个孩子节点为中间节点的节点。如果一个有多余带宽的节点找到了，我们就将其作为新节点的父节点。否则，我们将指定一个一个孩子节点为中间节点的节点作为新节点的父节点，然后为这个孩子节点重新找一个父节点。这样做的目的是使树的上层拥有足够的中间节点，这些节点可以支持子节点。

2.3有效性

3 算法分析

本文的doubletree算法利用根节点作为控制节点建立组播树并对其进行维护，中间节点和叶子节点的加入和离开在算法中的时间复杂度只有O（1）. 而根节点对信息集合的搜索的时间复杂度也只有O（N）. 大大减少了网络延迟度。随着节点数目的增加，使得数据块稳定数目大幅增加，又因为通过改进的pastry关键词进行搜索，获得物理距离最近的视频块提供者，所以数据块的丢失率大幅减小。

4 总结

本文提出了一种基于P2P的中心控制的组播树建构算法，并通过对pastry关键词的设计使网络拓扑结构更符合物理拓扑结构。最后，对doubletree算法进行了算法分析。分析结果表明该结构降低了搜索延迟，提高了路由效率，并且流媒体的服务质量也得到了大幅提高。

参考文献：

[1] Baner Jee S， Bhattachar Jee B， Kommareddy C. Scalable application layer multicast [J ]. ACM SIGCOMM Computer Communication Review， 2002， 32 （4）： 205-217.

[2] Dejan Kostic， Adolfo Rodriguez， Jeannie R Albrecht， et al. High bandwidth data dissemination using an overlay mesh[C]. In： Proc 19th ACM Symposium on Operating System Principles， October 2003. 282-297.

[3] Y.Cui， B.Li， K.Nahrstedt.oStream：asynchronous treaming multicast in application-layer overlay networks[J]. Selected Areas in Communications. IEEE Journal， 2004， vol.22， no.1.

[4]Miguel Castro， Peter Druschel. SplitStream：High-bandwidth content distribution in cooperative enviroments[C].In：Proc 19th ACM Symp on Operating System Principles， October 2003.

[5] Antony Rowstron， Peter Druschel. Pastry： Scalable， decentralized object location and routing for large-scale peer-to-peer systems[C]. Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms （Middleware 2001）. Heidelberg， Germany， November 2001.