点对点网络是今年兴起的一个热门研究课题。 点对点网络有非常好的文件分发能力, 在传统的服务器客模式下, 服务器需要为每位客建立独立的链接。随着用的增加服务器的能力很快会变成瓶颈。点对点网络的优势在于能够通过下载相同内容的客共享交换内容, 从而利用每位客的上传带宽.基于这个特点,即使没有服务器的帮助, 只要客都无私的共享自己的内容, 点对点网络可以以非常高的效率分发大文件。 目前已经有很对研究成果是关于点对点网络的体系结构设计和网络协议设计。但随着文件大小和数量的快速增长, 客除了贡献带宽还会贡献一块硬盘来缓存一些自己并不感兴趣的内容来增加客间互相帮助的概率。尤其是视频点播应用的兴起给点对点网络的内容传输带来了新的挑战。例如如何能保证所有客流畅的点播视频,以及如何优化每个客缓存的内容来最小化服务器带宽需求。在本篇论文中, 我们将集中讨论点对点视频点播系统并解决以下问题: / 我们的目的是节省服务器带宽。一个最基本的问题是客节点的最优缓存替换策略问题。首先我们定义了完美请求调度策略,在这个调度策略的基础上提出RLB 缓存替换策略从而得到最小化服务器带宽。 / 第二个问题是不同的请求调度策略和最优的缓存替换策略之间是如何相互影响的。我们提出了FSBD 模型。通过研究每个客能发出的请求数目,我们恩能够比较不同的缓存替换策略和不同的调度策略之间的关系。 / 最后一个问题,我们研究了点对点视频点播系统在电影数量远远多于客数量的极端情况。在这种情况下, 由于客只能贡献非常少量的硬盘来缓存电影, 提供电影的覆盖和提高视频点播系统的吞吐量是一个互相矛盾的问题。两者不能同时达到最优。 / 除了以上的理论分析, 我们通过模拟试验来验证理论模型的正确性。 此外我们还提出了非常简单有效的分布式缓存替换策略用于实际系统的实现。相信以上的研究工作对于点对点视频系统的设计和实现有重要的帮助。 / Peer-to-Peer (P2P) systems become a hot research topic in recent years because of their excellent ability for content distribution. In traditional Client/Server(C/S) mode, the server must serve each user directly. The server capacity is the bottleneck when user population becomes large. The power of P2P network is to encourage peers to share common content with each other to offload server. The P2P systems distribute content very efficiently if all peers help others selflessly with minimal support from the server. There are many works dedicated to the architecture and protocol design for P2P systems. These works study how to organize peers to exchange content efficiently. As content size and content population are growing very fast today, P2P networks are used to support Video on Demand (VoD) streaming service. For VoD streaming, besides bandwidth, the peers are required to contribute storage to cache some content that they may not be interested in. The new challenges include how to guarantee that all peers can play video smoothly and how to cache the content at different peers to minimize server load . In this thesis, we study the following problems in a P2P VoD streaming system: / What the optimal movie replication strategy to minimize server load is. To study this problem, we first make an assumption to simplify the P2P service model. We assume that all peers follow a Perfect Fair Sharing (PFS) scheduling strategy. Based on this setup, we proposed Random Load Balance (RLB) algorithm to achieve minimum server load. We derive analytical bounds on the achieved server load. / Next, We observe that different P2P scheduling strategies lead to different “optimal replication strategies. Our second setup is to relax the assumption of perfect fair sharing scheduling by proposing a Fair Sharing with Bounded Degree (FSBD) model, parameterized by the maximum number of peers that can be used to serve a single request. PFS is a special case of FSBD. We compare different replication strategies for different in-degree bounds and see how and why different replication strategies are favored depending on the in-degree. / For the last problem, we let the movie population become large and assume that there is some skewness in movie popularity. Then peers can’t reduce server load and provide availability of all movies at the same time. In other words, peers must be selective in replicating sufficiently popular movies. It is a tradeoff between coverage of movies and streaming throughput provided by the P2P system. / Besides analysis, we also use simulation to validate our models. As a robust solution under different P2P service models, we proposed a simple adaptive movie replication algorithm with computation efficiency. Our study leads to several fundamental insights for the design of P2P VoD systems in practice. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Zhou, Yipeng. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 162-170). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.i / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.2 / Chapter 1.2 --- P2P VoD Streaming System --- p.6 / Chapter 1.3 --- Contribution --- p.11 / Chapter 1.4 --- Organization --- p.12 / Chapter 2 --- Model --- p.14 / Chapter 2.1 --- Assumptions and Notations --- p.15 / Chapter 2.2 --- User Behavior Model --- p.19 / Chapter 2.3 --- Movie Popularity --- p.22 / Chapter 2.4 --- Optimizing Server Load --- p.25 / Chapter 3 --- Analysis --- p.30 / Chapter 3.1 --- Request Scheduling Strategy --- p.31 / Chapter 3.2 --- Fixed Bandwidth Allocation --- p.33 / Chapter 3.2.1 --- FBA with Homogeneous Peers --- p.33 / Chapter 3.2.2 --- FBA with Heterogeneous Peers --- p.37 / Chapter 3.3 --- Perfect Fair Sharing --- p.37 / Chapter 3.3.1 --- PFS with Homogeneous Peers --- p.41 / Chapter 3.3.2 --- PFS with Heterogeneous Peers --- p.48 / Chapter 3.4 --- Fair Sharing with Fixed Degree --- p.50 / Chapter 3.5 --- FBA v.s. PFS v.s. FSFD --- p.53 / Chapter 3.6 --- Fair Sharing with Bounded Degree --- p.55 / Chapter 4 --- Adaptive Movie Replication Algorithms --- p.62 / Chapter 4.1 --- Adaptive RLB Algorithm --- p.63 / Chapter 4.2 --- Distributed Adaptive Replication Algorithm --- p.66 / Chapter 4.2.1 --- Other Algorithms --- p.70 / Chapter 5 --- Simulation --- p.73 / Chapter 5.1 --- Simulation Setting --- p.74 / Chapter 5.2 --- Simulation for PFS --- p.76 / Chapter 5.2.1 --- Stationary demand and static replication assignment --- p.77 / Chapter 5.2.2 --- Evaluate adaptive replication algorithms --- p.81 / Chapter 5.2.3 --- Performance analysis and discussion --- p.85 / Chapter 5.2.4 --- Copy Distribution of ARLB --- p.89 / Chapter 5.3 --- Simulation for FBA, FSFD and FSBD --- p.91 / Chapter 5.3.1 --- Model Validation --- p.91 / Chapter 5.3.2 --- Test of DAR Algorithm --- p.93 / Chapter 5.3.3 --- Robustness Validation --- p.96 / Chapter 6 --- Division of Labor --- p.102 / Chapter 6.1 --- Background: models and algorithms --- p.103 / Chapter 6.2 --- Availability versus Throughput --- p.106 / Chapter 6.2.1 --- ATD and its Drawbacks --- p.107 / Chapter 6.2.2 --- Coverage Assured Replication --- p.110 / Chapter 6.2.3 --- Automatic Division of Labor --- p.113 / Chapter 6.3 --- Optimal Coverage --- p.115 / Chapter 6.3.1 --- Save Most Popular Movies for P2P --- p.115 / Chapter 6.3.2 --- The Value of Optimal K --- p.118 / Chapter 6.3.3 --- Performance with or without CA --- p.121 / Chapter 6.4 --- Sensitivity --- p.122 / Chapter 6.4.1 --- θ versus K* --- p.122 / Chapter 6.4.2 --- The Effect of Popularity Skewness:θ --- p.123 / Chapter 6.4.3 --- System Parameters versus K* --- p.124 / Chapter 6.4.4 --- The Effect of System Parameters --- p.126 / Chapter 7 --- Related Work --- p.131 / Chapter 8 --- Conclusion --- p.141 / Chapter A --- Equation Derivation --- p.144 / Bibliography --- p.162
Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328403 |
Date | January 2012 |
Contributors | Zhou, Yipeng, Chinese University of Hong Kong Graduate School. Division of Information Engineering. |
Source Sets | The Chinese University of Hong Kong |
Language | English, Chinese |
Detected Language | English |
Type | Text, bibliography |
Format | electronic resource, electronic resource, remote, 1 online resource (iv, x, 170 leaves) : ill. (some col.) |
Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0019 seconds