VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY BUI THI LAN HUONG A PUSH-PULL BASED APPLICATION LAYER MULTICAST FOR P2P LIVE VIDEO STREAMING Major: Computer Science Code : 60 48 01 MASTER THESIS Hanoi – 2011 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY BUI THI LAN HUONG A PUSH-PULL BASED APPLICATION MULTICAST LAYER FOR P2P LIVE VIDEO STREAMING BRANCH: INFORMATION TECHNOLOGY MAJOR: COMPUTER SCIENCE CODE: 60 48 01 MASTER THESIS SUPERVISOR: DR. NGUYEN HOAI SON Hanoi – 2011 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table of Contents 1 Introduction 1 1.1 Overview and Motivation .1 An Overview of multicast .2 Application layer multicast .2 Application layer multicast methods for P2P live video streaming .1 Tree-based approach .2 Mesh-based approach. 12 3 Our method for P2P live video streaming 16 3. 24 4 Experiments and results 26 4.1 Experimental set-up .1 Evaluation of services quality if no churn.
29 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com vi TABLE OF CONTENTS 4.2 Evaluation of service’s quality if churn is present .3 Evaluation of services quality in heterogeneous bandwidth case 33 5 Conclusion 36 A Simulation program 38 A. 40 B Generating input by using GT-ITM 41 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Figures 2.1 Using unicast, broadcast and multicast for video streaming .2 An example of IP multicast .3 An example of ALM .4 Single multicast tree with 10 nodes .5 An example of multi-tree based streaming .6 An example of mesh-based video streaming method .1 Pushing connections and pulling connection of a node .2 Example of changing position of high-bandwidth node .3 Example of diffusion phase with k = 3 .4 Example of swarming phase, node pulls missing data .5 Example of replacement of node failure .1 An example of real networks topology [NTks] .2 CDF of average variance between the arrival times of different parts in PRIME and in our method .3 CDF of average parts delay and average segment delay from source to node in PRIME and in our method .4 CDF of missing parts ratio of node in our method when there is leave and join nodes .5 CDF of average variance between the arrival times of different parts in our method when there is leave and join nodes .6 CDF of average parts delay and average segment delay from source to node in our method when there are leave and join nodes .7 CDF of missing parts ratio of our method when participating nodes have different bandwidth. 33 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com viii LIST OF FIGURES 4.8 CDF of average parts delay from source to node when participating nodes have different bandwidth .9 CDF of average segment delay from source to node when participating nodes have different bandwidth. 35 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Tables 2.1 Conceptual comparison between IP Multicast and ALM [HASG07] .1 Algorithm of selecting node reply pull request.
23 ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Abbreviations P2P Peer to Peer MDC Multiple Description Coding ALM Application Layer Multicast ESM End System Multicast x LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 1 Introduction 1.1 Overview and Motivation With the rapid growth of multimedia applications and the Internet, stream- ing video over the Internet is becoming more and more attractive to users. This is especially the case for live video streaming. Live video streaming applications often require transmitting streaming data to a large number of users. IP Multicast [DC90] is probably the most efficient solution for this requirement.
However, the deployment of IP multicast remains restricted due to many practical and political issues [HASG07]. Researchers thus have shifted focus to exploiting application-layer multicast (ALM) for data delivery. ALM utilizes the ability of end hosts that act not only as receivers but also as senders. They can forward their received data to other hosts.
However, this solution is challenged by the dynamic join/leave of end hosts, the existence of free-riders, the heterogeneous of node bandwidth and the real-time constraint, especially in live streaming applications. Many application-layer multicast protocols have been proposed recently. Cur- rent application-layer multicast protocols can be divided into two classes: tree-based approach and mesh-based approach. The tree-based approach, organize participat- ing peers into multicast tree for data delivery ([CDK+ 03], [PWC03], [PKT+ 05], [WXL10], [RD01], [CDKR02], [BBMB+ 10], [LLR09], [THD04]).
However, for tree- based designs with only one single tree, two major problems can be seen. Firstly, it is unfair between interior nodes and leaf nodes when leaf nodes do not contribute to the system. Secondly, the leave/failure of any interior node may cause packet outage in all its descendant nodes. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Introduction To deal with these problems, in SplitStream [CDK+ 03], nodes are structured into multiple diverse trees such that an interior node in this tree will be a leaf node of all other trees. Video streams are split into several smaller sub-streams using Mul- tiple Description Coding [AW01] or layered video [LPA98] and each sub-streams data is delivered by one tree. However, SplitStream requires all nodes to have equal bandwidth. Otherwise, its performance will be degraded.
Some recent tree-based research ([BBMB+ 10], [LLR09]) overcomes the disadvantage of Splitstream by op- timizing the construction of multi trees even when nodes have different bandwidth. However, multi-tree based approach still has a disadvantage of long buffering time due to the variation in arrival times of different sub-streams data. Another problem that all multi-tree-based designs have to face is the cost of maintaining and recov- ering multicast trees when there is a node churn (there is node join and leave in the system). Recently, mesh-based P2P streaming approach ([MR10], [MRW07], [VYF06], [ZXBY05], [ZLZY05], [LPA98], [CdSLMM11], [HCC10], [CJW11], [LKHT10]) has attracted a lot of attention since it can minimize the impact of node churn and low bandwidth of a neighbour node by pulling necessary data from a number of appro- priate neighbour nodes.
Each node independently selects some nodes as neighbours and pulls data from them based on an assumption that neighbour nodes may have necessary video data. However, there is a trade-off between minimum delay by send- ing pull request and overhead of whole system ([VYF06], [ZLZY05]). Furthermore, there are may exist content bottleneck due to the lack of data at the pulled nodes. PRIME [MR10] improves bandwidth bottleneck and content bottleneck by com- bining a method of pushing data via multiple sub-trees and a method of pulling data from nodes in different sub-trees.
However, PRIME did not show clearly how is built the overlay network in the case that the bandwidth degree constraint does not sat- isfied and decentralized. [CdSLMM11], [CJW11] proposed some different strategies to select connections but all these strategies are built based on the fact that the bootstrap node must store the whole information about all nodes in the network, which leads to low scalability. [LKHT10] shows how to build a decentralized overlay network but with the cost of increased computation complexity. In addition, these strategies does not address problems such as long buffering time, node churn or free-riders.
Realizing this drawback in current application layer multicast methods for video streaming, we aim to propose a push-pull based method for lower delay and better LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Our contribution 3 video quality.2 Our contribution In this thesis, we design a large-scale decentralized P2P streaming mechanism that combines pushing and pulling method. Nodes are organized in separate sub-trees such that a node, except the source node, belongs to only one sub-tree. Each node also has links to other nodes of other sub-trees.
Each sub-stream is delivered through a sub-tree based on a push mechanism. Each node will receive from its parent at least one sub-stream in the pushing phase to ensure the availability. Then, a node pulls other sub-streams from other nodes to improve the quality of service. In our work, we tackle several problems such as how to reduce buffering time of nodes, how to encourage nodes to contribute resources and how to deal with node churn.
The contribution of our work includes: 1. Optimizing packet delivery in pulling phase to reduce buffering time of nodes. We consider that the playing time of each node depends on the arrival time of the latest part of a segment. Therefore, in our method, each node will try to establish pulling connections with nodes in the level above or in the same level.
Here, the level of a node is defined as the path length from a source node to the node. Therefore, the time gap between arrival times of pushing data and pulling data is reduced. Ensuring the fairness between nodes and encouraging nodes to contribute more to the network. In our work, a tit-for-tat policy is designed such that nodes with more contribution will be given higher priority to receive data.
Hence, they can get better quality of service such as shorter buffering time or more received data. To enhance the tit-for-tat policy, we construct a balanced tree to ensure that nodes belonging to different sub-trees can provide data to each other. Recovering from node failure when there are nodes failed. We keep the number of nodes affected by a node failure to be small, and minimize the amount of time to recover from node failure.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ensuring scalability: Our mechanism is fully large-scale decentralized. It does not require any node to keep global information about the network. We conduct simulations to evaluate performance of our proposed system.
The simulation results show that our proposed system can improve the quality of service for live video streaming, handle node churn well and ensure the tit-for-tat policy.3 Thesis organization The rest of this thesis is structured as follows: Chapter 2 presents some background in this area. The description issues in- cludes a review of previous and current work in live video streaming. Chapter 3 describes the proposed push-pull based method for P2P live video streaming and explain how our method satisfies the problem that mentioned above. Chapter 4 describes how we set-up our simulation experiments and presents our results and comparisons with other approaches.
Chapter 5 present our conclusion and gives future research directions based on the results obtained so far. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 2 Background In this chapter, we present the basic concepts of this thesis. Firstly, we in- troduce a briefly overview of multicast and why multicast is the choice for video streaming application and a comparison between IP Multicast and application layer multicast (ALM). Secondly, we discuss about current ALM solutions for P2P live video streaming.1 An Overview of multicast In live video streaming applications, a source sends the same video stream to end hosts.
For example, the same video stream is sent to many viewers in IPTV appli- cation. Multicast is the most suitable mechanism for video streaming application in comparison with other communication mechanisms such as unicast and broadcast [HASG07]. Multicast is mechanism that allows sender to send data to a group of receivers [Dee92]. The group of receivers is named as host group or multicast group.1 shows multicast, unicast and broad cast methods for video streaming application.
Unicast allows a source to send data to a single host. Video streaming application must use multiple unicast connections. Therefore, the number of viewer is limited by the bandwidth of source node. In broadcast approach (Fig.
1b), data is sent from source to all end hosts. In this mechanism, node that does not want to receive data still receives data. It causes a waste of network resources. In multicast approach (Fig.
1c), data is transmitted to a set of receivers. After receiving data, a receiver can copy and forward this data to another receiver.