毕业论文外文翻译-高质量的视频点播使用P2P分类是否可行.doc

本科毕业设计外文文献及译文文献、资料题目：Is High-Quality VoD Feasible using P2P Swarming文献、资料来源：网络文献、资料发表（出版）日期：2007.5 院 （部）： 计算机科学与技术学院专 业： 软件工程班 级： 姓 名： 学 号： 指导教师： 翻译日期： 2015.2.26山东建筑大学毕业设计外文文献及译文 外文文献： Is high-Quality VoD Feasible using P2P Swarming Peer-to-peer (P2P) systems have been immensely successful for large scale content distribution. Current peer-to-peer applications generate a large percentage of the traffic over the Internet and, more relevant to this paper, a large fraction of that traffic relates to distributing video content 30. However, with current systems, the users need to download the complete file, and as a result suffer long delays before they can watch the video. Recently systems such as CoolStreaming and others 15, 32, 38 have been very successful in delivering live media content to a large number of users using mesh peer-to-peer technology. However, it has been an open question whether similar P2P technologies can be used to provide a VoD service. A P2P VoD service is more challenging to design than a P2P live streaming system because the system should allow users arriving at arbitrary times to watch (arbitrary parts of) the video, in addition to providing low start up delays. The fact that different users may be watching different parts of the video at any time can greatly impact the efficiency of a swarming protocol. The lack of synchronization among users reduces the block sharing opportunities and increases the complexity of the block transmission algorithms. Peer-to-peer networks promise to provide scalable distribution solutions without infrastructure support. There are two fundamental approaches to building P2P systems: (a) tree-based (push) where trees (or, forests of trees) are usually constructed for dissemination of data 7, 11, 24, and (b) mesh-based (pull) where peers exchange random blocks 18, 26. Mesh-based systems do not enforce a structure on the overlay topology and, instead, promise high (swarming) efficiency by allowing peers to exchange random blocks with each other. As a result, mesh-based systems have lower protocol overhead, are much easier to design, are more resilient to high rates of churn, and hence are more popular. However, while mesh P2P systems have proved to be efficient for bulk file dissemination, it is still an open question how efficient they can be in providing VoD. The difficulty lies in the fact that users need to receive blocks “sequentially” (and not in random order) in order to watch the movie while downloading, and, unlike streaming systems, the users may be interested in different parts of the movie, and may compete for system resources. The goal then is to design a P2P system which meets the VoD requirements, while maintaining a high utilization of the system resources. In this paper, we study algorithms that provide the users with a high-quality VoD service while ensuring a high utilization of the system resources. We evaluate our algorithms using both extensive simulations and real experiments. under different user arrival departure patterns (heterogeneous user capacities etc. are not addressed in detail due to space constraints). The main results of this paper can be summarized as follows: (a) Naive, greedy scheduling algorithms provide bad VoD swarming throughputs. Applying Network Coding 1, 16, 17 over small time-windows of the video (e.g. a segment with a few seconds worth of video frames) reduces the risks of uploading duplicate content and minimizes the variance in the performance of each node, thus, improving the overall efficiency of the system. (b) While Network Coding solves the scheduling problem within a segment, scheduling across segments (spanning the entire video file) requires algorithms that avoid under-represented video portions. Such algorithms are feasible and can provide good system throughput while downloading blocks “pseudo-sequentially”. (c) The performance of the system, which translates to high utilization of system resources and also good user experience, depends critically on creating proper mesh topologies using efficient peermatching algorithms. Such peer-matching algorithms should take into account both the content at each peer, as well as their bandwidth. (d) We show that by combining network coding, segment scheduling, and peer-matching algorithms we can design P2P systems that can provide a “play as you download” experience. We show that with the proposed system the playback rate that the system can support is close to the peers maximum bandwidth with some small start-up delay (i.e. initial buffering). The rest of the paper is organized as follows. Section 2 discusses related work. Section 3 gives a brief outline of our system. Section 4 describes our evaluation methodology, as well as, the simulator and the prototype we have used to evaluate the system. Section 5 argues that naive extensions to current P2P swarming systems and shows are inadequate to support VoD. In particular, to support VoD over mesh P2P technology we need efficient block and segment scheduling algorithms; they are described in Section 6 and Section 7 respectively. Topology management is described in Section 8. The adaptation of our algorithms in the presence of clients with heterogeneous capacities is discussed in Section 9. Video streaming over the Internet has been on of the most prolific research areas for over a decade, see 5, 9, 21, 36 and the references therein. Most related to this work are the research efforts for designing video distribution systems that can support a large number of users. Multicasting has been proposed to provide a scalable video streaming service, even in the presence of non-homogeneous receivers 25, 27, 31. Multicasting is a natural paradigm for live video streaming. It has been also extended for supporting near- Video-on-Demand services. The simplest approach is to periodically start a new broadcast scheme 2. More elaborate schemes propose to divide the video into segments and distribute each segment in different multicast channels 21, 22, 34. The main disadvantage of such systems is that there is no support for native multicasting in the Internet today. Even though native multicasting is not available, there have been many proposals to use overlay multicast distribution for live streaming events 8, 14, 19, 23, 33, 37. Observe that such systems support live media streaming and not near-Video-on-Demand. Moreover, there is extra network overhead and complexity for maintaining the overlay topology. It is an open question whether such overlay multicasting approaches can be extended to support near-VoD, maybe by using similar approaches as in 22, 34. Inspired by the success of unstructured P2P networks, the authors in 28, 38 propose to use mesh-P2P networks for live video streaming. Similarly to our approach, 28, 38 use mesh-based P2P networks and, hence, have low overhead for topology maintenance, but, unlike our approach, support live video streaming instead of nVoD. More relevant to our work are the BASS 13 and BiToS 35 systems. BASS extends the current BitTorrent system 12 to provide a near-Video-on-Demand service 13. BASS assumes that there is a streaming server, that all nodes connect to the streaming server, but, all nodes use the P2P network to help each other and alleviate the load from the server. Even though BASS reduces the load at the server by a significant amount, the design of the system is still server oriented, and, hence, the bandwidth requirements at the server increase linearly with the number of users. In this work we assume that peers rely only on the P2P network to retrieve the content; hence, in our approach it is important to understand the performance of the various block propagation algorithms. Since in our approach we depend on a dynamic and fluctuating P2P network, we use deeper buffering compared to BASS. The BiToS system is also based on BitTorrent 35. The main idea is to divide the missing blocks into two sets, “high priority set” and “remaining piece set”, and request with higher probability blocks from the high priority set. While the emphasis is on careful scheduling of the video blocks in BiToS, the use of network coding obviates this problem in our system. Also, we note that BiToS does not identify the issues with topology management (and instead uses the standard BitTorrent algorithms).We assume a large number of users (referred to also as clients, nodes, or peers) interested in some video content, which initially exists on a special peer that we call server. Users are free to arrive at any point in time and want to watch the video from the beginning (seek, and fast-forward functionalities are out of the scope of this paper). In other words, we assume linear viewing, but we allow the users to join at arbitrary times. The resources (especially network bandwidth) of the server are limited, and hence users contribute their own resources to the system. Users organize themselves in an unstructured overlay mesh which resembles a random graph. A client joins the system by contacting a central tracker (whose address is obtained by an independent bootstrap mechanism). This tracker gives the client a subset of nodes already in the system. The client then contacts each of these nodes, and incorporates itself into the overlay mesh. Thus, each node is oblivious of the other nodes in the system except for a small subset, which we designate as its neighborhood. Each node can exchange content, as well as control messages, only with its immediate neighbors. When a node loses a neighbor (for example, a neighbor crashes) or wishes to increase its download rate, it can request additional neighbors. Note that we assume fail-stop behavior from the clients, i.e., they either function correctly or they cease to be a part of the system. In particular, they are not actively malicious; this is out of the scope of this paper. We assume that the clients themselves are resource-constrained (esp. network bandwidth). Thus, the download and the upload rates of a client are limited by its capacity. We consider scenarios where clients have asymmetric links, i.e., their upload and download capacities are different. The file is divided into a number of blocks. A number of consecutive blocks may be grouped into segments to improve efficiency. The system is media codec agnostic, hence, we do not rely on media format knowledge to recover from errors and packet losses; as a result, an important constraint of our system is that all blocks needs to be received without errors by the clients. Clients have enough storage capacity to keep a copy of all the blocks downloaded up to that point in time. Blocks can only be played if they are received in order and they are only available for other peers to download while the user is watching the video content or shortly after he is done. In our system, we have considered various arrival patterns, but focussed on flash-crowd events where most users arrive close in time after the video is published, and the file initially resides at a single location with limited upload capacity. We note that typically, in steady-state, it is possible to find a few nodes that have downloaded the entire content and can act as servers; the resulting increase in serving capacity in steady state eases the problem of content scheduling. Hence, we have focussed on flash-crowd arrival patterns because this configuration exercises the system the most. We have used extensive simulations and measurements using a prototype to understand the factors that affect the performance of VoD over P2P networks, and to evaluate the performance of our algorithms. The simulator models important performance factors, such as access capacities, block scheduling algorithms, and allows us to experiment with large networks; it is described in Sec. 4.1. The implementation gives us a more detailed insight into the operation of the system; it is described in Sec. 4.2. In Sec. 4.3, we describe the performance metrics we have used for our study. The simulator takes as input the size of the video file in units of blocks (typically 250 in our simulations), the number of nodes (typically 500), their capacities, and the times at which nodes join/depart the system. The simulator operates in discrete intervals of time called rounds. A clients upload/download capacity is given as the number of blocks that the client can transmit/receive in one round (typically 1). Each node connects to a small number of neighbors (typically 6-8). The topology changes during the simulation as a result of node arrivals and departures, and as the nodes try to find new neighbors to increase their download rates. At every round, each node contacts its neighbors to identify those that have useful blocks. Then, there is a random matching of peers that can exchange content. All block transfers, both between peers and from the server, happen simultaneously, and then the system moves to the next round. Note that while our simulator does not model realistic P2P networks in all their details (e.g. does not model network delays, locality properties etc.), it does capture some of the important propertiesof mesh-based P2P networks. Hence, we feel that many of our results are applicable to the design of real mesh-based systems. We have developed a prototype to validate our results in a realistic setting. The system resembles typical P2P systems 16 and consists of three types of participants: peers, a tracker, and a logger. Content is seeded into the system by a special peer called server. The tracker enables peer discovery and peer matching. The active peers periodically report to the tracker (e.g. information about their content, rates etc.), and the tracker provides a subset of the active peers to nodes that have too few neighbors. The logger is an aggregation point for peer and tracker trace messages. Every peer in the system reports detailed statistics to the logger; using those statistics we are able to perform an in-depth evaluation of the various system parameters. We rate-limit the upload and download capacities of the peers using a token bucket based algorithm. Each peer maintains 6-8 connections to other peers. Peers periodically connect to other peers at random and drop connections in an attempt to find better neighbors and increase their download rates. When testing network encoded transfers, we perform the encoding and decoding operations over a Galois Field GF(216); we also experiment with unencoded transfers. In most of our experiments, the file is divided into 100 original blocks (we have also experimented with larger number of blocks obtaining similar results). In this paper, we will use our implementation to study small scale scenarios, which will highlight the design principles and interactions that need to