【作者】 程斌；

【导师】 金海； 张铮；

【作者基本信息】 华中科技大学 ， 计算机系统结构， 2009， 博士

【摘要】 互联网的快速发展使得视频点播正逐渐演变为当前媒体内容传播的主流方式，以低成本提供高扩展高质量的媒体点播服务成为其演变过程中最关键最迫切的需要之一。结合对等网络的高扩展优势实现高性价比的大规模点播系统是满足该需要的有效方式，研究对等点播系统中数据分发的核心技术也因此具有重大现实意义。对等点播系统数据分发的核心技术主要包括节点组织、数据调度和数据放置等三方面的关键问题。现有数据分发技术由于对系统的高动态性特征考虑不足而无法满足点播系统实时性和交互性需求，在此背景下针对数据分发这三方面的关键问题设计和实现新的策略或方法对于构建低成本的大规模对等点播系统尤为重要。传统基于树状结构和网状结构的节点组织方式均不能适应对等点播系统的高动态性特征。针对该问题，一种基于环状结构的节点组织策略RINDY通过维护一组半径呈指数增长的逻辑环结构来管理邻居节点，使得每个客户端节点既有近跳的邻居节点交换媒体数据，又有远跳节点协助拖动后新邻居节点的快速查找，从而实现对等点播系统中邻居节点的快速定位和数据的有效共享。RINDY的协议开销分析和仿真实验的结果显示，基于环状结构的节点组织策略可明显降低源服务器的带宽开销，减少节点加入系统和拖动查询的交互时延，节点之间具有更好的负载均衡性，而且其查询跳数的上限与系统的节点规模无关，取决于媒体文件的总时间长度，相比现有结构具有更好的扩展性。现有对等点播系统数据调度策略着重于通过不同的分发顺序来最大化数据传输率，缺乏对系统实时性和动态特征(如用户拖动和频繁切换节目等)的考虑，其用户体验并不理想且资源共享效率低。从数据请求服务端的带宽分配策略和数据请求发送端的发送时机两方面入手，一种优先级相关的事件驱动型数据调度策略充分考虑了系统中用户的拖动、节点的加入和离开等动态特性，能够自动适应节点带宽的变化并优先服务最紧急的数据请求，从而保证数据到达的实时性，进一步改善用户播放质量。仿真实验结果显示，该策略不仅提高了客户端节点之间的数据利用率，而且明显改善播放的连续性。定点数据预取策略采用与现有预取策略不同的思路来到达降低拖动延迟、改善用户播放体验的目的。该策略并不预测用户未来可能发生的拖动位置，而是将用户拖动点调整到最近的一个等间距分布的数据预取点，避免了用户行为预测的困难，同时也提高了预取数据的利用率。真实系统的测试结果显示，使用定点数据预期策略后，向前或向后拖动操作的平均等待延迟均明显降低。具体而言，延迟小于2秒的向前拖动的比例从原来的35％提高到80％，延迟低于2秒的向后拖动的比例从原来的65％提高到78％。利用GridCast系统部署的真实日志数据，对单文件和多文件数据缓存策略的性能进行了综合评测。日志分析的结论说明多文件数据缓存策略可同时提高系统整体的扩展性和用户播放质量，另外分析也得出一些对系统设计和性能优化具有指导性意义的结论：(1)更高的访问并发度有利于改善用户平均的播放质量；(2)更大的节点数据缓存空间对于提高系统整体扩展性是有限的，而且会恶化节点间负载的不均衡性；(3)解决“节点离开”导致的数据不命中具有最大的可优化空间。结合数据缓存策略的分析结果，一种基于预测的惰性数据复制策略通过预测数据块的访问热度和节点是否离线，将最可能需要的稀缺数据复制到相对稳定的其它节点，从而减少“节点离开”所导致的数据不命中，进一步降低服务器开销。日志数据驱动的仿真实验结果显示，基于预测的惰性数据复制策略可以减少约50％的“节点离开”导致的数据不命中，最终进一步降低15％的源服务器带宽开销，而且随用户规模的增大，其性能改善的幅度将更大。更多还原

【Abstract】 Video-on-Demand (VoD) has emerged as a popular application over the Internet, while being evolving as the main technology to delivery rich content, such as news, sports, and movies. Driven by this requirement, it is becoming more and more important to provide highly scalable VoD streaming services to users at the lowest cost. Taking advantage of the peer-to-peer (P2P) technology for VoD is a potential approach of achieving this goal. This dissertation performs a detailed study on the design, deployment and evaluation of P2P VoD, with a special focus on its data dissemination in terms of peer organization, scheduling algorithms, and data distribution strategies.First of all, a novel ring-assisted overlay network, namely RINDY, is presented to well organize joined peers for efficient content sharing. In RINDY, each peer self-manages a set of concentric rings with power law radii and places all neighbors on these rings according to their playhead distances. More specifically, near neighbors with overlapped buffer windows with current node are placed on the innermost ring as backup data suppliers; while some randomly sampled remote neighbors are placed on the outer rings as routers to nodes with playheads specified by VCR operations. Under this scheme, a peer only needs one hop to join the overlay and at most log (T/w) hops to identify a new group of peers close to the target playback positions specified by random seeks, where T is the total time length of the video and w is the buffer window size of peers.Existing systems and proposals largely utilize scheduling mechanisms that are periodical in nature, referred as time-driven scheduling. This dissertation argues that time-driven scheduling is not efficient for P2P VoD, due to its inadequate resource utilization and inability in quickly adapting to the potential dynamic in such systems. To this end, we propose a priority-aware event-driven scheduling algorithm for P2P VoD systems, in which the scheduler is triggered by events such as peer churn or/and random seeks and the sender turns to first serve those requests with highest priorities through an optimal bandwidth allocation algorithm. The experimental results obtained from extensive simulations show that the priority-aware event-driven scheduling outperforms the time-driven scheduling in terms of both user experience and system scalability, especially during peer churn or when the source server is under-provisioned.An anchor prefetching algorithm is designed to further reduce seek latency. It differs from existing prefetching algorithms in that it adjusts the playback position to the closest anchor, avoiding the difficulty in predicting next playback positions. In the anchor prefetching, seeks can be satisfied instantly if the anchor has been already downloaded. The experimental results from the deployed systems show that the anchor prefetching significantly decreases seek latency. More specifically, forward seeks and backward seeks with less than 2 seconds latency are increased from 35% to 80%, from 65% to 78%, respectively.Based on the trace collected from a live P2P VoD system, namely GridCast, this dissertation analyzes how different caching policies can improve both scalability and user experience, evaluates their limitations, and presents some useful insights for future design and further optimizations. For example, we find that higher concurrencies delivery better content sharing and user experience, that caching leads to globally uneven load distribution, and that chunk misses caused by peer departure remains a major issue and keeps the biggest room for future improvements.From system traces, we identify that departure misses are the major cause of server load. Motivated by this finding, we examine how to use replication to decrease departure misses and thereby further reduce server load. We propose and evaluate a framework for lazy replication in P2P VoD. Lazy replication postpones data replication, trying to make efficient use of bandwidth. In this framework, two predictors are plugged in to create the working replication algorithm. Lazy replication with several predictors is compared with a naive eager replication algorithm. We find that lazy replication is more efficient than eager replication, even when using two simple predictors. With these two simple predictors, lazy replication can decrease server load by 15% from multi-video caching with only a minor increase in network traffic.更多还原