Algorithm design of layered peer-to-peer video on demand streaming networks

Abstract

Peer-to-peer (P2P) video streaming has become a very popular and cost-effective solution to provide video-on-demand (VoD) streaming service to a large group of Internet users. Recent advances of layered video coding are shown to be promising in addressing the problem of receiver heterogeneity in P2P streaming networks. The key idea is to encode a raw video into multiple non-overlapped layers. Peers in the network can enjoy different streaming qualities by subscribing to different number of layers according to their specific network bandwidth. In this thesis, a systematic and comprehensive study of layered P2P VoD streaming networks is conducted.

We first investigate the overlay construction problem that concerns the strategy of forming a logical overlay network for peers to exchange data pieces. We propose a neighbor relationship management algorithm to maintain a stable yet diversified neighbor set to facilitate adding or dropping a video layer, i.e. layer adaptation. Subsequently, an incentive scheme is designed to differentiate neighbors’ contributions at different layers, and a peer is allowed to adjust its number of neighbors according to its average service response time.

We then develop an efficient layer adaptation algorithm for adjusting the number of video layers a peer subscribes to. We use a sliding buffer window for video piece scheduling, and make use of the time difference between the playback point and the starting point of the sliding window to initiate the process of adding or dropping a layer. A probing period is also introduced to ensure the adding decision is indeed correct.

We next focus on designing piece scheduling algorithm for video data exchange among peers. At each peer, a utility function for calculating the relative importance of each missing video data piece is designed. In piece scheduling, a peer prefers a piece with higher utility value. We show that our utility based piece scheduling algorithm yields better video quality than conventional approaches.

Last but not least, we study the request peer selection problem for identifying the most suitable neighbor for a peer to make a piece request. Two algorithms are designed, smallest service response time first (SSF) and closest playback point first (CPF). SSF ensures peers with larger uplink bandwidths to serve more requests, and CPF encourages a newly joined peer to contribute its uplink bandwidth as quickly as possible. We show that there exists a sweet spot by properly combining the two together.

Although our algorithms are presented sequentially in addressing each of the problems above, they do interact with each other. Throughout our study, a comprehensive packet-level simulator is used to closely examine and analyze such interactions. With that, our algorithms are judicially designed and fine-tuned for best performance. To the best of our knowledge, our in-house developed simulator is the most comprehensive packet-level simulator for layered P2P VoD streaming.