點對點視頻點播是架構于互網上的熱門應用，旨在提供高質視頻服務。應用點對點技術的優勢在於，系統可用用戶資源以滿足其他用戶的觀賞需求，從而提高系統可擴展性并低運營成本。在該系統中存在以下關鍵設計因素。其一，在給定用戶資源時，如何以分佈式和動態性方法有效用這些資源；其二，考慮用戶自私性，如何激他們貢獻本地資源。 / 點對點視頻點播系統具有高動態性，非同步性及質性；相比文件共享系統還需大帶寬支持。這些特性使得解決以上技術問題充滿挑戰，因而激發我們的研究。我們試圖回答以下問題： / 如何確定存儲空間對各視頻的最佳分配比，從而最小化服務器負擔？ / 如何設計高效激機制使用戶於貢獻他們的本地資源？ / 我們首先關注最佳複製策。我們回答（1）在給定視頻條件下，如何確定視頻最佳複製比；（2）如何通過分佈式動態算法獲得這樣的最佳複製比。我們將視頻複製技術表達為最優化問題，显示傳統比複製法并非最優，而最優比應正比于文中定義的“欠缺帶寬。我們通過“被動替換算法與“主動推送算法以達到最優複製比，顯示我們的算法可使得服務器負擔大幅下以及服務質素顯著提高。 / 我們而後關注激機制設計。系統運營商需激用戶貢獻上載帶寬以傳輸據，以及本地存儲空間以存儲視頻。我們分解這個設計問題，并為它們逐一設計基於獎賞的激機制。（1）上載帶寬激。用戶根據貢獻帶寬受到獎賞。我們用博弈模型分析運營商與用戶之間的交互。我們推導出博弈均衡，分析系統高效性并研究多重博弈設定下的長期交互特性。（2）分佈存儲激。用戶根據緩存視頻受到獎賞。我們以優化模型刻畫視頻最佳獎賞價格。我們在漸進系統中推導出最優獎賞價格，然後將結果推廣至多種系統環境。 / 總而言之，該文從學建模、博弈分析、算法設計與性能評估等諸多角，解決點對點視頻點播系統中的資源獲取與分配策。 / Peer-to-Peer Video-on-Demand (P2P-VoD) is a popular Internet application which aims to provide a high quality video service to users. The advantage of using the P2P technology is that the system can utilize peers’ resources so as to satisfy other peers’ viewing requirement, thereby improving the system scalability and reducing the operating cost. There are two key design issues in P2P-VoDs. First, given the distributed resources of peers, what is the most efficient manner to utilize them in a distributed and dynamic fashion. Second, given the selfish nature of peers, how to incentivize the peers to contribute their local resources. / A P2P-VoD system is highly dynamic, asynchronous and heterogenous in nature. In addition, it requires a much higher bandwidth resource as compared with file sharing applications. These features make it challenging to solve the above technical problems, and hence motivate our work. In particular, we aim to answer: / How to determine the optimal ratios of storage space that should be assigned to each video, such that the content server’s workload can be minimized? / How to design effective and efficient incentive mechanisms so as to stimulate the peers to contribute their local resources? / We first focus on the optimal replication strategy. In particular, we answer (a) what is the optimal replication ratio of a video in terms of its popularity, and (b) how to achieve these optimal ratios in a distributed and dynamic fashion. We formulate the video replication as an optimization problem, and show that the conventional wisdom of using the proportional replication strategy is “sub-optimal“. The optimal replication ratios should be proportional to the “deficit bandwidth which we define in the thesis. We utilize “passive replacement policy“ and “active push policy“ to achieve the optimal replication ratios and show how to greatly reduce server’s workload and improve streaming quality via our distributed algorithms. / We next focus on incentive mechanisms design. The content providers need to incentivize the peers to contribute their upload capacity to delivery data, and local storage space to cache the videos. We decompose the problems and design reward-based incentive mechanisms for them respectively. (a) Incentivizing upload capacity. Each peer is rewarded based on its dedicated upload bandwidth. We analyze the interaction between a content provider and the peers using game theory. We derive a unique equilibrium, analyze the system efficiency and study the long term interactions under a repeated game setting. (b) Incentivizing distributed caching. Each peer is rewarded based on the videos they cache. We characterizes the optimal reward price using optimization. In particular, we first derive the optimal prices to obtain the desired amount of replicas in an asymptotic system, and then extend our results to adapt to various system environments. / To summarize, this thesis addresses the resource acquisition and allocation problems in P2P-VoD systems via mathematical modeling, game analysis, algorithms design and performance evaluations. / 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. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Wu, Weijie. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 129-138). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.v / Contents --- p.ix / List of Figures --- p.xiii / List of Tables --- p.xv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Peer-to-Peer Networks --- p.2 / Chapter 1.1.1 --- Classification of P2P Networks --- p.2 / Chapter 1.1.2 --- Applications of P2P Services --- p.4 / Chapter 1.2 --- P2P Video-on-Demand Systems --- p.4 / Chapter 1.2.1 --- General Architecture --- p.4 / Chapter 1.2.2 --- Key Advantages of P2P-VoDs --- p.6 / Chapter 1.3 --- Motivation --- p.7 / Chapter 1.4 --- Challenges --- p.8 / Chapter 1.5 --- Contributions --- p.10 / Chapter 1.6 --- A General System Model on P2P-VoDs --- p.12 / Chapter 1.7 --- Thesis Structure and Organization --- p.15 / Chapter 2 --- Optimal Replication Strategies in P2P-VoD Systems --- p.17 / Chapter 2.1 --- Chapter Overview --- p.17 / Chapter 2.2 --- Mathematical Model --- p.19 / Chapter 2.2.1 --- Basic System Assumptions and Peer Scheduling Policy --- p.19 / Chapter 2.2.2 --- Server’s Workload --- p.22 / Chapter 2.2.3 --- Discussion on Peer Operations --- p.26 / Chapter 2.2.4 --- Impact of Replication on Reducing the Server’s Workload --- p.27 / Chapter 2.3 --- Optimal Replication Ratios to Minimize Server’s Workload --- p.30 / Chapter 2.3.1 --- Operation Modes --- p.30 / Chapter 2.3.2 --- Characteristics of Deficit Bandwidth --- p.31 / Chapter 2.3.3 --- Characterizing the Optimal Replication Strategy --- p.34 / Chapter 2.3.4 --- Discussion on Heterogeneous Video Playback Rates --- p.36 / Chapter 2.4 --- Algorithms to Control Replication Ratios --- p.38 / Chapter 2.4.1 --- Passive Adjustment via Replacement Algorithm --- p.39 / Chapter 2.4.2 --- Active Adjustment via Push Strategy --- p.40 / Chapter 2.5 --- Performance Evaluation --- p.43 / Chapter 2.5.1 --- Performance of Replacement Algorithm --- p.43 / Chapter 2.5.2 --- Performance of Push Algorithm --- p.49 / Chapter 2.6 --- Chapter Summary --- p.51 / Chapter 3 --- Incentivizing Upload Capacity in P2P-VoD Systems --- p.53 / Chapter 3.1 --- Chapter Overview --- p.53 / Chapter 3.2 --- Peers’ Viewing Behavior and Reward-based Scheme --- p.55 / Chapter 3.2.1 --- Peers’ Viewing Behavior --- p.55 / Chapter 3.2.2 --- Reward-based Incentive Scheme --- p.57 / Chapter 3.3 --- Peers’ Contribution and Content Provider’s Cost --- p.58 / Chapter 3.3.1 --- Distribution of Peers in Different Video Segments --- p.58 / Chapter 3.3.2 --- Content Provider’s Upload Cost --- p.61 / Chapter 3.4 --- Game Theoretic Analysis on Incentive Scheme --- p.62 / Chapter 3.4.1 --- Stackelberg Game Model --- p.63 / Chapter 3.4.2 --- Existence and Uniqueness of Stackelberg Equilibrium --- p.64 / Chapter 3.4.3 --- Efficiency of Stackelberg Equilibrium --- p.67 / Chapter 3.4.4 --- General Reward Scheme --- p.72 / Chapter 3.4.5 --- Repeated Game Model --- p.73 / Chapter 3.5 --- Performance Evaluation --- p.77 / Chapter 3.6 --- Discussion on Practical Issues --- p.82 / Chapter 3.6.1 --- System Heterogeneity --- p.82 / Chapter 3.6.2 --- P2P-VoD System with Caching --- p.83 / Chapter 3.6.3 --- Cheating Prevention Guarantee --- p.84 / Chapter 3.7 --- Chapter Summary --- p.84 / Chapter 4 --- Incentivizing Distributed Caching in P2P-VoD Systems --- p.86 / Chapter 4.1 --- Chapter Overview --- p.86 / Chapter 4.2 --- Mathematical Model --- p.88 / Chapter 4.2.1 --- Preliminaries --- p.88 / Chapter 4.2.2 --- Peers’ Caching Behaviors --- p.91 / Chapter 4.2.3 --- Cache state distribution of peers of type m --- p.93 / Chapter 4.2.4 --- Cache State of the System --- p.95 / Chapter 4.2.5 --- Design Objectives of Pricing Schemes --- p.96 / Chapter 4.3 --- Asymptotic Analysis --- p.98 / Chapter 4.3.1 --- Cache State of Peers --- p.99 / Chapter 4.3.2 --- Conservative Pricing Problem --- p.102 / Chapter 4.3.3 --- Strategic Pricing Problem --- p.105 / Chapter 4.4 --- Generalizations and Extensions --- p.106 / Chapter 4.4.1 --- Viewing-Caching Decoupling --- p.107 / Chapter 4.4.2 --- General Sensitivity Model --- p.108 / Chapter 4.4.3 --- Non-Asymptotic System --- p.111 / Chapter 4.4.4 --- Pricing before Reaching the Steady State --- p.113 / Chapter 4.5 --- Performance Evaluation --- p.115 / Chapter 4.6 --- Chapter Summary --- p.119 / Chapter 5 --- Related Work --- p.120 / Chapter 5.1 --- Related Work on Replication Strategy --- p.120 / Chapter 5.2 --- Related Work on Incentive Mechanisms Design --- p.122 / Chapter 6 --- Conclusion and FutureWork --- p.125 / Chapter 6.1 --- Conclusion --- p.125 / Chapter 6.2 --- Future work --- p.126 / Chapter 6.2.1 --- Extensions for Various Practical Issues --- p.126 / Chapter 6.2.2 --- Incentive and Resource Allocation in Other Applications --- p.127 / Bibliography --- p.129
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328162 |
| Date | January 2012 |
| Contributors | Wu, Weijie, Chinese University of Hong Kong Graduate School. Division of Computer Science and 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 (xv, 138 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.0034 seconds