The efficient scheduling of streaming data delivery in a peer-to-peer (P2P) network is a hard problem due to the Internet’s lack of support for resource allocation and performance guarantees. In particular, the bandwidth resources available to a peer is constantly in flux and the future bandwidth availability is very difficult, if not impossible, to predict accurately. This thesis proposes to tackle this problem from a different angle. We investigate the use of erasure codes to encode the media data and then schedule multiple peers to stream the encoded data simultaneously to a receiver. By exploiting the order-invariant property of erasure codes this approach enables the sending peers to fully utilize their available bandwidth resources and yet does not need to estimate or predict their bandwidth availability. Moreover, we develop distributed scheduling algorithms to juxtapose the data transmissions from multiple peers so that the coding and storage complexities can be kept at practical level in scaling up the system. / 在互聯網中變動的可用頻寬和網路的延遲變異等問題，對點對點網絡上的串流傳輸品質造成嚴重的影響。由於每一個用戶端的網絡傳輸速度都是不穩定，而且是難以預測的，這是很困難去制定一個高效率的傳輸排程。在本論文中，我們從另一個角度去解決這個問題。首先，利用抹除碼把訊息變成足夠數量的區塊，讓多個訊息源可以同時傳送不同部分的區塊給受信者。由於抹除碼擁有糾錯能力，訊息源之間便不再需要任何協調及傳輸排程，提升整體的傳輸速度。另外，我們開發了一個排程算法來演算每一個訊息源的區塊傳送次序，盡可能的節省計算抹除碼時所需的資源，以能夠在具規模的環境中運作。 / Ma, Man Lok. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2014. / Includes bibliographical references (leaves 72-75). / Abstracts also in Chinese. / Title from PDF title page (viewed on 26, September, 2016). / Detailed summary in vernacular field only.

Leung Wai Tak. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 58-60). / Abstracts in English and Chinese. / Acknowledgement --- p.I / Abstract --- p.II / 摘要 --- p.III / Chapter Chapter 1 --- Introduction --- p.1 / Chapter Chapter 2 --- Related Works --- p.5 / Chapter 2.1 --- Previous Works --- p.5 / Chapter 2.2 --- Contributions of this Study --- p.7 / Chapter Chapter 3 --- Architecture --- p.9 / Chapter 3.1 --- Data Placement Policy --- p.10 / Chapter 3.2 --- Retrieval and Transmission Scheduling --- p.13 / Chapter 3.3 --- Fault Tolerance --- p.20 / Chapter Chapter 4 --- Performance Modeling --- p.22 / Chapter 4.1 --- Storage Requirement --- p.22 / Chapter 4.2 --- Network Bandwidth Requirement --- p.23 / Chapter 4.3 --- Buffer Requirement --- p.24 / Chapter 4.4 --- System Response Time --- p.27 / Chapter Chapter 5 --- System Reliability --- p.29 / Chapter 5.1 --- System Failure Model --- p.29 / Chapter 5.2 --- Minimum System Repair Capability --- p.32 / Chapter 5.3 --- Redundancy Configuration --- p.35 / Chapter Chapter 6 --- System Dimensioning --- p.37 / Chapter 6.1 --- Storage Capacity --- p.38 / Chapter 6.2 --- Network Capacity --- p.38 / Chapter 6.3 --- Disk Access Bandwidth --- p.39 / Chapter 6.4 --- Buffer Requirement --- p.41 / Chapter 6.5 --- System Response Time --- p.43 / Chapter Chapter 7 --- Multiple Parity Groups --- p.45 / Chapter 7.1 --- System Failure Model --- p.47 / Chapter 7.2 --- Buffer Requirement --- p.47 / Chapter 7.3 --- System Response Time --- p.49 / Chapter 7.4 --- Redundancy Configuration --- p.49 / Chapter 7.5 --- Scalability --- p.51 / Chapter Chapter 8 --- Conclusions and Future Works --- p.53 / Appendix --- p.55 / Chapter A. --- Derivation of the Artificial Admission Delay --- p.55 / Chapter B. --- Derivation of the Receiver Buffer Requirement --- p.56 / Bibliography --- p.58

由於在線社交網絡的龐大用戶群和口碑效應的病毒式傳播特點，使用少量用戶吸引大量用戶的定向廣告策略在病毒營銷中是非常有效的。公司可以先提供免費商品給在線社交網絡上的小部份用戶，然後依靠這些用戶推薦此產品給他們的好友，從而達到提升產品整體銷售額的目的。在本文中，我們考慮如下在線社交網絡中廣告投放的問題:給定廣告投放資本，比如固定數目的免費產品，公司需要決定在線社交網絡中用戶會最終購買的概率。為了研究此問題，我們把在線社交網絡模擬成擁有或者沒有高聚合係數的無標度圖。我們使用多個影響機制來刻畫如此大規模網絡中的影響傳播，并且使用本地平均場技術來分析這些節點狀態會被影響機制所改變的網絡。我們運行了大量的仿真實驗來驗證我們的理論模型。這些模型能夠為設計在線社交網絡中的有效廣告投放策略提供認識和指導。 / 雖然口碑效應的病毒式傳播能有效地促進產品銷售，但是它同時也為惡意行為提供了機會:不誠實用戶會故意給他們的好友提供錯誤的推薦從而擾亂正常的市場份額分配。為了解決這個問題，我們提出了一個通用的檢測框架，并基於此檢測框架制定了一系列完全分佈式的檢測算法來識別在線社交網絡中的不誠實用戶。我們考慮了不誠實用戶採取基本策略和智能策略兩種情況。我們通過計算假陽性概率，假陰性概率和檢測不誠實用戶所需要的時間的分佈來度量檢測算法的性能。大量的仿真實驗不僅說明了不誠實推薦所造成的影響，也驗證了檢測算法的有效性。我們還應用前面提到的通用檢測框架來解決無線網格網絡(wireless mesh network)和點對點視頻直播網絡(peer-to-peer live streaming network)中的污染攻擊問題。在應用了網絡編碼的無線網格網絡中，污染攻擊是一個很嚴重的安全問題。惡意節點能夠輕易地發動污染攻擊，從而造成污染數據包的病毒式傳播進而消耗網絡資源。前面提到的通用檢測框架也能被用來解決此安全問題。明確地說，我們使用基於時間的校驗碼和批量驗證機制來決定污染數據包的存在與否，然後提出一系列完全分佈式的檢測算法。即使智能攻擊者存在時，此檢測算法仍然有效。這裡智能攻擊者指的是那些為了降低被檢測到的概率從而假裝合法節點傳輸有效數據包的節點。並且，為了解決攻擊者合作注入污染數據包的情形并加速檢測，我們還提出了一個增強的檢測算法。我們也給出了規範的分析來度量檢測算法的性能。最後，仿真實驗和系統原型驗證了我們的理論分析以及檢測算法的有效性。 / 污染攻擊還會對點對點視頻直播網絡基礎設施造成嚴重影響，比如說，它能夠減少網絡中的攻擊問題，我們仍然基於前面提到的通用檢測框架提出了分佈式的檢測算法來識別污染攻擊者。我們也提供了理論分析來度量檢測算法的性能從而證明了算法的有效性。 / Due to the large population in online social networks and the epidemic spreading of word-of-mouth effect, targeted advertisement which use a small fraction of buyers to attract a large population of buyers is very efficient in viral marketing, for example, companies can provide incentives (e.g., via free samples of a product) to a small group of users in an online social network, and these users can provide recommendations to their friends so as to increase the overall sales of the product. In particular, we consider the following advertisement problem in online social networks: given a fixed advertisement investment, e.g., a number of free samples, a company needs to determine the probability that users in the online social network will eventually purchase the product. To address this problem, we model online social networks as scale-free graphs with/without high clustering coefficient. We employ various influence mechanisms that govern the influence spreading in such large scale networks and use the local mean field technique to analyze them wherein states of nodes can be changed by various influence mechanisms. We carry out extensive simulations to validate our models which can provide insight on designing efficient advertising strategies in online social networks. / Although epidemic spreading of word-of-mouth effect can increase the sales of a product efficiently in viral marketing, it also opens doors for “malicious behaviors: dishonest users may intentionally give wrong recommendations to their friends so as to distort the normal sales distribution. To address this problem, we propose a general detection framework and develop a set of fully distributed detection algorithms to discover dishonest users in online social networks by applying the general detection framework. We consider both cases when dishonest users adopt (1) baseline strategy, and (2) intelligent strategy. We quantify the performance of the detection algorithms by deriving probability of false positive, probability of false negative and distribution function of time needed to detect dishonest users. Extensive simulations are carried out to illustrate the impact of dishonest recommendations and the effectiveness of the detection algorithms. / We also apply the general detection framework to address the problem of pollution attack in wireless mesh networks (WMNs) and peer-to-peer (P2P) streaming networks. Epidemic attack is a severe security problem in network-coding enabled wireless mesh networks, and malicious nodes can easily launch such form of attack to create an epidemic spreading of polluted packets and deplete network resources. The general detection framework can also be applied to address such security problem. Specifically, we employ the time-based checksum and batch verification to determine the existence of polluted packets, then propose a set of fully distributed detection algorithms. We also allow the presence of “smart attackers, i.e., they can pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. To address the case when attackers cooperatively inject polluted packets and speed up the detection, an enhanced detection algorithm is also developed. Furthermore, we provide formal analysis to quantify the performance of the detection algorithms. At last, simulations and system prototyping are also carried out to validate the theoretic analysis and show the effectiveness and efficiency of the detection algorithms. / To address the problem of pollution attack in P2P streaming networks, which is known to have a disastrous effect on existing P2P infrastructures, e.g., it can reduce the number of legitimate users by as much as 85%, we also propose distributed detection algorithms to identify pollution attackers by applying the general framework. Moreover, we provide theoretical analysis to quantify the performance of the detection algorithms so as to show their effectiveness and efficiency. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Yongkun. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 148-157). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Influence Modeling in Online Social Networks --- p.7 / Chapter 2.1 --- Scale-free Graphs without High Clustering Coefficient --- p.8 / Chapter 2.1.1 --- Modeling Online Social Networks --- p.8 / Chapter 2.1.2 --- q-influence Model --- p.11 / Chapter 2.1.3 --- m-threshold Influence Model --- p.14 / Chapter 2.1.4 --- Majority Rule Influence Model --- p.16 / Chapter 2.2 --- Scale-free Graphs with High Clustering Coefficient --- p.19 / Chapter 2.3 --- Generalized Influence Models --- p.21 / Chapter 2.3.1 --- Deterministic Influence Model --- p.21 / Chapter 2.3.2 --- Probabilistic Influence Model --- p.25 / Chapter 2.4 --- Multi-state Model --- p.27 / Chapter 2.4.1 --- Example of 3-State Majority Rule --- p.32 / Chapter 3 --- Identifying Dishonest Recommenders in Online Social Networks --- p.35 / Chapter 3.1 --- General Detection Framework --- p.37 / Chapter 3.2 --- Modeling the Behaviors of Users --- p.41 / Chapter 3.2.1 --- Products and Recommendations --- p.41 / Chapter 3.2.2 --- Behaviors of Users --- p.43 / Chapter 3.3 --- Distributed Detection Algorithms --- p.45 / Chapter 3.3.1 --- Identifying Dishonest Recommenders when Baseline Strategy is Adopted --- p.46 / Chapter 3.3.2 --- Identifying Dishonest Recommenders when Intelligent Strategy is Adopted --- p.53 / Chapter 3.3.3 --- Complete Detection Algorithm --- p.57 / Chapter 3.4 --- Cooperative Algorithm to Speed up the Detection --- p.58 / Chapter 3.5 --- Algorithm Dealing with User Churn --- p.61 / Chapter 4 --- Identifying Pollution Attackers in Network Coding Enabled Wireless Mesh Networks --- p.64 / Chapter 4.1 --- Introduction on Wireless Mesh Networks and Pollution Attack --- p.64 / Chapter 4.2 --- Network Coding and Time-based Checksum Batch Verification --- p.66 / Chapter 4.3 --- Basic Detection Algorithms --- p.70 / Chapter 4.3.1 --- Core Idea of the Detection Algorithms --- p.71 / Chapter 4.3.2 --- Attackers with Imitation Probability δ = 0 --- p.74 / Chapter 4.3.3 --- Attackers with Imitation Probability δ > 0 --- p.78 / Chapter 4.3.4 --- Improvement on Probability of False Negative --- p.81 / Chapter 4.4 --- Enhanced Detection Algorithm --- p.82 / Chapter 4.4.1 --- Detection Algorithm --- p.82 / Chapter 4.4.2 --- Performance Analysis --- p.87 / Chapter 4.4.3 --- Detection Acceleration --- p.91 / Chapter 4.5 --- Alternative Detection Algorithms --- p.92 / Chapter 5 --- Identifying Pollution Attackers in Peer-to-Peer Live Streaming Systems --- p.95 / Chapter 5.1 --- Introduction on Peer-to-Peer Streaming Systems and the Problem of Pollution Attack --- p.95 / Chapter 5.2 --- Detection Algorithms --- p.97 / Chapter 5.2.1 --- Imitation Probability δ = 0 --- p.99 / Chapter 5.2.2 --- Imitation Probability δ > 0 --- p.102 / Chapter 5.2.3 --- Improvement on Probability of False Negative --- p.104 / Chapter 6 --- Performance Evaluation --- p.106 / Chapter 6.1 --- Influence Modeling in Online Social Networks --- p.107 / Chapter 6.1.1 --- Online Social Networks without High Clustering Coefficient --- p.107 / Chapter 6.1.2 --- Online Social Networks with High Clustering Coefficient --- p.113 / Chapter 6.1.3 --- Performance Evaluation of the Multi-state Model --- p.116 / Chapter 6.2 --- Performance Evaluation of the Detection Algorithms in Online Social Networks --- p.118 / Chapter 6.2.1 --- Synthesizing Dynamically Evolving Online Social Networks --- p.118 / Chapter 6.2.2 --- Impact of Wrong Recommendations --- p.120 / Chapter 6.2.3 --- Performance Evaluation of the Detection Algorithms --- p.121 / Chapter 6.3 --- Performance Evaluation of the Detection Algorithms in Wireless Mesh Networks --- p.126 / Chapter 6.3.1 --- Performance of the Basic Detection Algorithms --- p.126 / Chapter 6.3.2 --- Results from System Prototype --- p.131 / Chapter 6.3.3 --- Performance of the Enhanced Detection Algorithm --- p.132 / Chapter 6.4 --- Performance Evaluation of the Detection Algorithms in Peer-topeer Streaming Networks --- p.136 / Chapter 6.4.1 --- Performance of the Baseline Algorithm --- p.136 / Chapter 6.4.2 --- Performance of the Randomized Algorithm --- p.138 / Chapter 6.4.3 --- Derive Optimal Uploading Probability --- p.141 / Chapter 7 --- RelatedWork and Conclusion --- p.143

點對點視頻點播是架構于互網上的熱門應用，旨在提供高質視頻服務。應用點對點技術的優勢在於，系統可用用戶資源以滿足其他用戶的觀賞需求，從而提高系統可擴展性并低運營成本。在該系統中存在以下關鍵設計因素。其一，在給定用戶資源時，如何以分佈式和動態性方法有效用這些資源；其二，考慮用戶自私性，如何激他們貢獻本地資源。 / 點對點視頻點播系統具有高動態性，非同步性及質性；相比文件共享系統還需大帶寬支持。這些特性使得解決以上技術問題充滿挑戰，因而激發我們的研究。我們試圖回答以下問題： / 如何確定存儲空間對各視頻的最佳分配比，從而最小化服務器負擔？ / 如何設計高效激機制使用戶於貢獻他們的本地資源？ / 我們首先關注最佳複製策。我們回答（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

点对点网络是今年兴起的一个热门研究课题。 点对点网络有非常好的文件分发能力， 在传统的服务器客模式下， 服务器需要为每位客建立独立的链接。随着用的增加服务器的能力很快会变成瓶颈。点对点网络的优势在于能够通过下载相同内容的客共享交换内容， 从而利用每位客的上传带宽.基于这个特点,即使没有服务器的帮助， 只要客都无私的共享自己的内容， 点对点网络可以以非常高的效率分发大文件。 目前已经有很对研究成果是关于点对点网络的体系结构设计和网络协议设计。但随着文件大小和数量的快速增长， 客除了贡献带宽还会贡献一块硬盘来缓存一些自己并不感兴趣的内容来增加客间互相帮助的概率。尤其是视频点播应用的兴起给点对点网络的内容传输带来了新的挑战。例如如何能保证所有客流畅的点播视频，以及如何优化每个客缓存的内容来最小化服务器带宽需求。在本篇论文中， 我们将集中讨论点对点视频点播系统并解决以下问题： / 我们的目的是节省服务器带宽。一个最基本的问题是客节点的最优缓存替换策略问题。首先我们定义了完美请求调度策略，在这个调度策略的基础上提出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

Made available in DSpace on 2015-03-05T13:58:26Z (GMT). No. of bitstreams: 0 Previous issue date: 13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Apesar de ser uma das principais aplicações da Internet na atualidade, o compartilhamento de arquivos P2P tem sido fortemente prejudicado por ataques de poluição de conteúdo. Esta dissertação propõe e analisa uma classe de métodos de contenção de poluição cujo princípio básico é a limitação do número instantâneo de downloads de acordo com a reputação de versões. Inicialmente, o método é proposto e avaliado em termos de um ambiente idealizado, mostrando sua eficiência na contenção de poluição e baixa sobrecarga induzida quando o título não é poluído. A seguir, valendo-se de modelos clássicos para projeto de redes P2P, são propostos e comparados métodos de contenção distribuída / Despite currently one of the main Internet applications, P2P file sharing has been hampered by content pollution attacks. This work proposes and analyzes a class of contention methods to reduce the dissemination of polluted content whose basic principle is to limit the amount of instantaneous downloads according to its reputation. The method is firstly proposed and evaluated in terms of an idealized environment. The evaluation shows the eficiency of the contention method and the low overhead induced when the content is not polluted. Then, inspired by classic P2P designs, we propose and compare distributed contention methods

Made available in DSpace on 2015-03-05T13:58:27Z (GMT). No. of bitstreams: 0 Previous issue date: 16 / Bolsa para curso e programa de Pós Graduação / BitTorrent é a tecnologia de compartilhamento de arquivos mais popular atualmente na Internet e responsável por fração significativa do tráfego nela existente. Considerando sua importância e adoção em larga escala, a arquitetura BitTorrent precisa ser robusta e resistente a pares maliciosos. Esta dissertação constitui a primeira investigação em termos de vulnerabilidades do BitTorrent, apresentando quatro contribuições principais: (a) auxilia no entendimento do BitTorrent; (b) identifica vulnerabilidades e descreve ataques e contramedidas possíveis à arquitetura; (c) descreve um modelo de simulação discreto, que permite mapear o comportamento do protocolo BitTorrent; e (d) avalia, via simulação, o impacto de dois dos ataques identificados, Mentira de Peças e Eclipse. Os resultados mostram que BitTorrent é suscetível a ataques em que pares maliciosos mentem a posse de peças e tornam-nas mais raras, fazendo com que downloads em geral sejam atrasados em até 50%. Em ataques Eclipse, com uma proporção em torno de / BitTorrent is the most popular file sharing technology and associated with a significant fraction of the Internet traffic. Considering its importance and large scale adoption, the BitTorrent architecture should be robust and resistant to malicious peers. This dissertation is the first investigation in terms of vulnerabilities against BitTorrent architecture, providing four important contributions: (a) it helps to increase the understanding of the BitTorrent protocol; (b) it identifies vulnerabilities and describes feasible attacks and countermeasures to the BitTorrent architecture; (c) it presents a discrete event simulation model which maps the behaviour of the protocol; and (d) it evaluates, through simulation, the impact of two proposed attacks, namely Piece Lying and Eclipse. Results show what BitTorrent is vulnerable to cheating peers that lie about having pieces, in order to make them rarer, causing an increase of about 50% in downloading times. Eclipse attacks can cause even more damage, as analysis

Ip Tak Shun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 95-101). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Media Streaming --- p.1 / Chapter 1.1.2 --- Incentive Mechanism --- p.2 / Chapter 1.2 --- Cooperative and Incentive-based Proxy-and-Client Caching --- p.4 / Chapter 1.2.1 --- Cooperative Proxy-and-Client Caching --- p.4 / Chapter 1.2.2 --- Revenue-Rewarding Mechanism --- p.5 / Chapter 1.3 --- Thesis Contribution --- p.6 / Chapter 1.4 --- Thesis Organization --- p.7 / Chapter 2 --- Related Work --- p.9 / Chapter 2.1 --- Media Streaming --- p.9 / Chapter 2.2 --- Incentive Mechanism --- p.11 / Chapter 2.3 --- Resource Pricing --- p.14 / Chapter 3 --- Cooperative Proxy-and-Client Caching --- p.16 / Chapter 3.1 --- Overview of the COPACC System --- p.16 / Chapter 3.2 --- Optimal Cache Allocation (CAP) --- p.21 / Chapter 3.2.1 --- Single Proxy with Client Caching --- p.21 / Chapter 3.2.2 --- Multiple Proxies with Client Caching --- p.24 / Chapter 3.2.3 --- Cost Function with Suffix Multicast --- p.26 / Chapter 3.3 --- Cooperative Proxy-Client Caching Protocol --- p.28 / Chapter 3.3.1 --- Cache Allocation and Organization --- p.29 / Chapter 3.3.2 --- Cache Lookup and Retrieval --- p.30 / Chapter 3.3.3 --- Client Access and Integrity Verification --- p.30 / Chapter 3.4 --- Performance Evaluation --- p.33 / Chapter 3.4.1 --- Effectiveness of Cooperative Proxy and Client Caching --- p.34 / Chapter 3.4.2 --- Robustness --- p.37 / Chapter 3.4.3 --- Scalability and Control Overhead --- p.38 / Chapter 3.4.4 --- Sensitivity to Network Topologies --- p.40 / Chapter 4 --- Revenue-Rewarding Mechanism --- p.43 / Chapter 4.1 --- System Model --- p.44 / Chapter 4.1.1 --- System Overview --- p.44 / Chapter 4.1.2 --- System Formulation --- p.47 / Chapter 4.2 --- Resource Allocation Game --- p.50 / Chapter 4.2.1 --- Non-Cooperative Game --- p.50 / Chapter 4.2.2 --- Profit Maximizing Game --- p.52 / Chapter 4.2.3 --- Utility Maximizing Game --- p.61 / Chapter 4.3 --- Performance Evaluation --- p.74 / Chapter 4.3.1 --- Convergence --- p.76 / Chapter 4.3.2 --- Participation Incentive --- p.77 / Chapter 4.3.3 --- Cost effectiveness --- p.85 / Chapter 5 --- Conclusion --- p.87 / Chapter A --- NP-Hardness of the CAP problem --- p.90 / Chapter B --- Optimality of the Greedy Algorithm --- p.92 / Bibliography --- p.95

Li Fengjun. / Thesis submitted in: July 2004. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 83-84). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.v / Table of Contents --- p.vi / List of Figures --- p.viii / List of Tables --- p.ix / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivations of this work --- p.1 / Chapter 1.2 --- Network Fairness Issue --- p.3 / Chapter 1.3 --- Our Contribution --- p.4 / Chapter 1.4 --- Organization of the Thesis --- p.5 / Chapter Chapter 2 --- Background of Fairness Index --- p.7 / Chapter 2.1 --- The Model --- p.7 / Chapter 2.2 --- Definitions of Fairness Index --- p.9 / Chapter 2.3 --- General Existence and Uniqueness Properties of Perfectly Fair Solution --- p.12 / Chapter 2.4 --- Properties in Specific Network Topologies --- p.16 / Chapter 2.4.1 --- Uniform Routing Networks --- p.16 / Chapter 2.4.2 --- Single Routing Node Networks --- p.20 / Chapter Chapter 3 --- Extension of the Fairness Index --- p.22 / Chapter 3.1 --- A Single Routing Node Network Example --- p.22 / Chapter 3.2 --- The Max-Min Fairness Index --- p.27 / Chapter 3.3 --- Von Neumann Equilibrium Index --- p.29 / Chapter Chapter 4 --- Distributed Low Bit Rate Algorithm --- p.36 / Chapter 4.1 --- Distributed Controller --- p.36 / Chapter 4.2 --- Convergence of the Low Bit Rate Distributed Algorithm --- p.39 / Chapter 4.3 --- Experiment Results --- p.49 / Chapter 4.4 --- Heuristic Iterative Algorithm --- p.53 / Chapter Chapter 5 --- Fairness Index Based Routing --- p.57 / Chapter 5.1 --- Routing Protocol Basics --- p.58 / Chapter 5.1.1 --- Static Routing and Dynamic Routing --- p.58 / Chapter 5.1.2 --- Routing Metrics --- p.59 / Chapter 5.1.3 --- Distance Vector and Link State --- p.60 / Chapter 5.1.4 --- Shortest Path Routing Algorithm --- p.62 / Chapter 5.2 --- Minimum Delay Routing --- p.63 / Chapter 5.3 --- Fairness Index Based Routing --- p.66 / Chapter 5.3.1 --- Problem Formulation --- p.66 / Chapter 5.3.2 --- Cost Function --- p.69 / Chapter 5.3.3 --- Implementing Fairness Index Based Routing --- p.71 / Chapter 5.3.4 --- Experiment and Analysis --- p.73 / Bibliography --- p.82

Abstract In this thesis, we consider the performance evaluation of peer-to-peer (P2P)streaming over wireless networks. Traditionally, P2P streaming has been implemented and analyzed extensively in wire line networks. As more and more devices are connected to the internet through wireless, however, it is critical to understand how wireless channel variability affects the performance of P2P systems. Weformulate the P2P streaming system as a queuing network, and analyze its performance based onthe large deviation principle. We are interested in characterizing the buffer underow probability, where users run of out content and cannot receive smooth video playback. As explicit analysis is very dicult with a nite number of users, we focus on characterizing the performance bounds when the number of users goes to innity, assuming that playback rate and buffer size both grow linearly with the number of users N. We show that the upper bound of buffer underow probability decays exponentially in N. We also compare the decay rate of bound in different channel models, and show that the Markov modulated channel leads to a faster decay rate than the I.I.D. model with the same expected channel capacities. / Leung, Kam Wong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 50-52). / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.2 / Chapter 1.1.1 --- Video Streaming --- p.2 / Chapter 1.1.2 --- Large Deviations Theory --- p.4 / Chapter 1.2 --- Related Works --- p.6 / Chapter 2 --- System Model and Assumptions --- p.9 / Chapter 2.1 --- System Model --- p.9 / Chapter 2.2 --- Assumptions --- p.11 / Chapter 2.3 --- Queuing Model --- p.12 / Chapter 3 --- Performance of Large Network --- p.16 / Chapter 3.1 --- Large Deviation Principle --- p.16 / Chapter 3.2 --- Time I.I.D. Channel Model --- p.23 / Chapter 3.3 --- Markov Modulated Channel --- p.29 / Chapter 3.4 --- Performance Comparison of Channel Model: Time I.I.D. Model vs Markov Modulated Model --- p.31 / Chapter 4 --- Simulation Result and Analysis. --- p.35 / Chapter 4.1 --- Simulation Settings --- p.35 / Chapter 4.2 --- The Performance Bounds of Different Playback Rates --- p.36 / Chapter 4.3 --- The Performance Bounds for Different Channel Transition Matrix --- p.37 / Chapter 5 --- Conclusion --- p.40 / Chapter A --- Appendix --- p.42 / Chapter A.1 --- Convexity of decay rate function for time I.I.D Model --- p.42 / Chapter A.2 --- Condition for the Chernoff Bound hold --- p.44 / Chapter A.3 --- Convergence of the Decay Rate Function --- p.44 / Chapter A.4 --- Moment Generating Function of Markov Modulated Sources --- p.46 / Chapter A.5 --- Limiting Probability Distribution of Capacity of Markov Channel --- p.47 / Chapter A.6 --- Computation: Capacity p.d.f of Two States Markov Modulated Channel --- p.48 / Bibliography --- p.50