即時點對點視訊串流系統容量之研究

On the Capacity of Live P2P Video Streaming System

劉炳傳(Pin-Chuan Liu) ； 易志偉(Chih-Wei Yi)

《電腦與通訊》 142期 (2011/12) Pp. 37-44

https://doi.org/10.29917/CCLTJ.201112.0006

摘要

每個系統在佈建後能達到的服務容量一直是系統商最重視的問題。點對點（P2P）視訊串流系統的容量受到系統諸多動態變因影響，例如：每個節點的上下傳頻寬、點對點網路拓樸形成方法、影音延遲限制、影音串流位元傳輸率大小…等。在本篇論文中，我們研究樹狀拓樸的點對點視訊串流系統並且證明找到最佳化樹狀拓樸以達到最大系統容量是NP-hard問題；接著我們說明頻寬與視訊延遲將造成系統容量的限制；最後我們提出一個適合在動態環境下使用的點對點網路生成演算法，並且以模擬結果證明我們提出的演算法能同時考慮節點上傳頻寬與視訊延遲，進而達成較佳的頻寬使用率與系統容量。

關鍵字

非決定性多項式時間難題 ； 系統容量 ； 點對點視訊串流 ； 樹狀拓樸

並列摘要

People always want to know achievable service capacity while deploying new systems. The capacity of P2P streaming systems changes due to dynamic system composition. Different formation parameters, like uplink/downlink bandwidth of each peer and server, overlay network topology, video delay constraint, video stream bit-rate, etc, can result in different system capacity. In this paper, we focus on tree-based P2P streaming systems and deal with the routing and peer selection strategies. We prove that finding the routing tree to maximize system capacity is NP-hard. A distributed heuristic which considers both on peer uplink bandwidth and video delay constraints is proposed. Simulation results show that the proposed heuristic achieves larger system capacity.

並列關鍵字

Non-Deterministic Polynomial-Time hard ； NP-hard ； System Capacity ； P2P Video Streaming ； Tree Topology