Luận văn: Ứng dụng Multicast lớp ứng dụng Push-Pull cho P2P Live Video Streaming - ĐH Công nghệ

Luận văn: Ứng dụng multicast lớp mạng P2P dựa trên cơ chế a push pull cho truyền hình trực tiếp. Nghiên cứu giải pháp hiệu quả cho live streaming.

• Tác giả: Bui Thi Lan Huong
• Người hướng dẫn: Dr. Nguyen Hoai Son
• Trường học: Vietnam National University, Hanoi University of Engineering and Technology
• Chuyên ngành: Computer Science
• Đề tài: A Push-Pull Based Application Layer Multicast For P2P Live Video Streaming
• Loại tài liệu: Master Thesis
• Năm xuất bản: 2011
• Địa điểm: Hanoi

Tóm tắt

I. P2P Live Streaming Tổng Quan và Động Lực Phát Triển 55 ký tự

P2P live streaming ngày càng trở nên phổ biến nhờ sự phát triển nhanh chóng của các ứng dụng đa phương tiện và Internet. Việc truyền tải video trực tiếp đến một lượng lớn người dùng là một nhu cầu cấp thiết. IP Multicast là một giải pháp hiệu quả, nhưng triển khai thực tế còn nhiều hạn chế về mặt chính trị và kỹ thuật. Do đó, các nhà nghiên cứu tập trung vào việc khai thác application-layer multicast (ALM) để phân phối dữ liệu. ALM tận dụng khả năng của các end host vừa là người nhận vừa là người gửi, chuyển tiếp dữ liệu đã nhận đến các host khác. Tuy nhiên, giải pháp này đối mặt với các thách thức như sự tham gia/rời đi liên tục của end host, sự tồn tại của free-rider, sự không đồng nhất về băng thông và yêu cầu thời gian thực, đặc biệt trong các ứng dụng live streaming.

Nhiều giao thức application-layer multicast đã được đề xuất, chia thành hai loại chính: phương pháp dựa trên cây (tree-based approach) và phương pháp dựa trên lưới (mesh-based approach). Các thiết kế dựa trên cây có một cây duy nhất thường gặp các vấn đề về tính công bằng giữa các node bên trong và node lá, cũng như sự cố mất gói tin khi một node bên trong gặp sự cố. Phương pháp dựa trên lưới giảm thiểu tác động của việc node rời đi và băng thông thấp bằng cách lấy dữ liệu cần thiết từ nhiều node lân cận phù hợp. Tuy nhiên, tồn tại sự đánh đổi giữa độ trễ tối thiểu và chi phí hệ thống.

Nghiên cứu này đề xuất một phương pháp push-pull based để giảm độ trễ và cải thiện chất lượng video, giải quyết các hạn chế của các phương pháp application layer multicast hiện tại cho video streaming.

1.1. Ưu Điểm của P2P Live Streaming So với Unicast Broadcast

So với unicast, P2P live streaming giảm tải cho server nguồn bằng cách phân tán việc truyền tải dữ liệu đến các peer khác. Thay vì server phải xử lý từng kết nối riêng lẻ, các peer sẽ chia sẻ gánh nặng này. So với broadcast, P2P live streaming hiệu quả hơn vì chỉ truyền dữ liệu đến những người thực sự muốn xem, tránh lãng phí tài nguyên mạng.

1.2. Hạn Chế Của IP Multicast và Sự Ra Đời Của ALM

IP Multicast là một giải pháp hiệu quả về mặt lý thuyết, nhưng việc triển khai rộng rãi gặp nhiều khó khăn do các vấn đề kỹ thuật và chính trị. ALM ra đời để giải quyết vấn đề này bằng cách triển khai multicast ở tầng ứng dụng, tận dụng khả năng của các end host.

II. Vấn Đề và Thách Thức Trong P2P Live Video Streaming 58 ký tự

Các giao thức P2P live video streaming đối mặt với nhiều thách thức lớn. Thứ nhất, sự tham gia và rời đi liên tục của các peer (node) tạo ra sự xáo trộn (churn) trong mạng, đòi hỏi khả năng phục hồi nhanh chóng. Thứ hai, sự tồn tại của các free-rider (peer chỉ nhận dữ liệu mà không đóng góp băng thông) gây ảnh hưởng đến hiệu suất tổng thể của hệ thống. Thứ ba, sự không đồng nhất về băng thông giữa các peer đòi hỏi các giải pháp linh hoạt có thể thích ứng với các điều kiện mạng khác nhau. Thứ tư, yêu cầu thời gian thực của live streaming đòi hỏi độ trễ thấp và khả năng truyền tải dữ liệu ổn định.

Các phương pháp tiếp cận hiện tại, như dựa trên cây (tree-based) và dựa trên lưới (mesh-based), có những ưu và nhược điểm riêng. Phương pháp dựa trên cây dễ quản lý nhưng dễ bị ảnh hưởng bởi sự cố node và không đảm bảo tính công bằng. Phương pháp dựa trên lưới linh hoạt hơn nhưng phức tạp hơn và có thể gây ra tình trạng nghẽn mạng. Do đó, cần có một giải pháp kết hợp các ưu điểm của cả hai phương pháp và giải quyết các thách thức còn tồn tại. Việc tối ưu hóa multicast trong môi trường P2P là rất quan trọng để đạt được hiệu suất cao và trải nghiệm người dùng tốt.

2.1. Ảnh Hưởng Của Node Churn Đến Chất Lượng Streaming

Việc một node rời mạng đột ngột có thể gây ra gián đoạn cho các node khác đang nhận dữ liệu từ nó. Cần có các cơ chế phục hồi nhanh chóng để giảm thiểu tác động của node churn.

2.2. Vấn Đề Free rider và Giải Pháp Khuyến Khích Chia Sẻ Băng Thông

Các free-rider chỉ nhận dữ liệu mà không đóng góp băng thông, gây bất công cho các node khác. Cần có các cơ chế khuyến khích chia sẻ băng thông để đảm bảo tính công bằng và hiệu suất tổng thể của hệ thống.

III. Phương Pháp Push Pull Giải Pháp Tối Ưu Cho P2P Live Streaming 60 ký tự

Phương pháp push-pull kết hợp ưu điểm của cả phương pháp dựa trên cây (push) và phương pháp dựa trên lưới (pull) để tối ưu hóa P2P live streaming. Trong giai đoạn push, dữ liệu được truyền tải theo cấu trúc cây, đảm bảo rằng mỗi node nhận được ít nhất một phần của video. Trong giai đoạn pull, các node chủ động yêu cầu các phần dữ liệu còn thiếu từ các node lân cận khác, cải thiện chất lượng video và giảm độ trễ.

Phương pháp này cho phép hệ thống thích ứng linh hoạt với sự thay đổi về băng thông và sự cố node. Các node có thể lựa chọn các node lân cận phù hợp để yêu cầu dữ liệu, giảm thiểu tác động của việc mất kết nối hoặc băng thông thấp. Ngoài ra, phương pháp push-pull khuyến khích các node đóng góp băng thông bằng cách ưu tiên các node đóng góp nhiều hơn trong việc phân phối dữ liệu. Việc tối ưu hóa multicast trong cả giai đoạn push và pull giúp đạt được hiệu suất cao và trải nghiệm người dùng tốt.

3.1. Cơ Chế Hoạt Động Của Giai Đoạn Push Phân Phối Dữ Liệu Cơ Bản

Giai đoạn push đảm bảo rằng mỗi node nhận được ít nhất một phần của video, tạo nền tảng cho việc xây dựng video hoàn chỉnh. Cấu trúc cây giúp phân phối dữ liệu hiệu quả và có tổ chức.

3.2. Cơ Chế Hoạt Động Của Giai Đoạn Pull Bổ Sung Dữ Liệu và Giảm Độ Trễ

Giai đoạn pull cho phép các node chủ động yêu cầu các phần dữ liệu còn thiếu, cải thiện chất lượng video và giảm độ trễ. Việc lựa chọn node lân cận phù hợp giúp tối ưu hóa quá trình truyền tải dữ liệu.

IV. Kiến Trúc Mạng Lưới P2P và Xây Dựng Overlay Network 57 ký tự

Việc xây dựng một P2P overlay network hiệu quả là rất quan trọng để tối ưu hóa multicast trong P2P live streaming. Kiến trúc mạng lưới cần đảm bảo tính linh hoạt, khả năng mở rộng và khả năng phục hồi. Các node cần được tổ chức một cách hợp lý để giảm độ trễ và tăng hiệu suất truyền tải dữ liệu.

Trong phương pháp push-pull, kiến trúc mạng lưới bao gồm các cây phân phối dữ liệu (cho giai đoạn push) và các kết nối lân cận (cho giai đoạn pull). Các cây phân phối dữ liệu cần được cân bằng để đảm bảo tính công bằng và giảm độ trễ. Các kết nối lân cận cần được thiết lập một cách thông minh để tối ưu hóa việc lựa chọn node để yêu cầu dữ liệu. Việc xây dựng P2P overlay network cần xem xét các yếu tố như băng thông, độ trễ và sự ổn định của kết nối để đạt được hiệu suất cao và trải nghiệm người dùng tốt.

4.1. Xây Dựng Cây Phân Phối Dữ Liệu Cân Bằng Balanced Tree

Một cây phân phối dữ liệu cân bằng đảm bảo rằng các node ở các nhánh khác nhau nhận được dữ liệu với độ trễ tương đương, giảm thiểu tình trạng nghẽn mạng và cải thiện tính công bằng.

4.2. Thiết Lập Kết Nối Lân Cận Thông Minh Cho Giai Đoạn Pull

Việc lựa chọn node lân cận phù hợp để yêu cầu dữ liệu là rất quan trọng để giảm độ trễ và tăng hiệu suất truyền tải dữ liệu. Các yếu tố như băng thông, độ trễ và sự ổn định của kết nối cần được xem xét.

V. Chính Sách Công Bằng và Khuyến Khích Đóng Góp 52 ký tự

Để đảm bảo tính bền vững của hệ thống P2P live streaming, cần có một chính sách công bằng và khuyến khích đóng góp. Các node đóng góp nhiều băng thông hơn cần được ưu tiên trong việc phân phối dữ liệu và nhận được chất lượng video tốt hơn.

Một cơ chế tit-for-tat có thể được sử dụng để khuyến khích các node chia sẻ băng thông. Các node chia sẻ băng thông sẽ nhận được điểm thưởng và được ưu tiên trong việc lựa chọn node để yêu cầu dữ liệu. Các node không chia sẻ băng thông sẽ bị phạt và có thể bị hạn chế trong việc truy cập dữ liệu. Chính sách công bằng và khuyến khích đóng góp giúp tạo ra một hệ thống P2P live streaming công bằng, hiệu quả và bền vững. Việc chia sẻ băng thông P2P cần được khuyến khích để đạt được hiệu suất cao và trải nghiệm người dùng tốt.

5.1. Cơ Chế Tit for tat Để Thưởng Cho Các Node Đóng Góp

Cơ chế tit-for-tat giúp khuyến khích các node chia sẻ băng thông bằng cách thưởng cho những node đóng góp nhiều hơn.

5.2. Xử Lý Các Node Free rider và Đảm Bảo Công Bằng

Cần có các cơ chế để xử lý các free-rider và đảm bảo rằng các node đóng góp nhận được lợi ích tương xứng.

VI. Kết Luận và Hướng Phát Triển P2P Live Streaming Tối Ưu 59 ký tự

P2P live streaming là một lĩnh vực đầy tiềm năng, nhưng vẫn còn nhiều thách thức cần giải quyết. Phương pháp push-pull kết hợp với tối ưu hóa multicast là một hướng đi đầy hứa hẹn để đạt được hiệu suất cao và trải nghiệm người dùng tốt.

Trong tương lai, cần tập trung vào việc phát triển các thuật toán tối ưu hóa P2P overlay network, cải thiện khả năng phục hồi của hệ thống và xây dựng các chính sách công bằng và khuyến khích đóng góp. Nghiên cứu về các giao thức P2P live streaming độ trễ thấp và các giải pháp P2P bandwidth sharing cũng rất quan trọng để đáp ứng nhu cầu ngày càng tăng của người dùng. Việc phát triển P2P streaming platform cần được đẩy mạnh để tạo ra một hệ sinh thái P2P live streaming phong phú và đa dạng.

6.1. Các Hướng Nghiên Cứu Mới Trong P2P Live Streaming

Các hướng nghiên cứu mới bao gồm các thuật toán tối ưu hóa P2P overlay network, cải thiện khả năng phục hồi của hệ thống và xây dựng các chính sách công bằng và khuyến khích đóng góp.

6.2. Tương Lai Của P2P Streaming Platform và Ứng Dụng Thực Tế

Việc phát triển P2P streaming platform cần được đẩy mạnh để tạo ra một hệ sinh thái P2P live streaming phong phú và đa dạng, với nhiều ứng dụng thực tế trong các lĩnh vực như esports, game và sự kiện trực tiếp.

Trích đoạn nội dung tài liệu

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 TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : [e-mail] List of Tables 2.1 Conceptual comparison between IP Multicast and ALM [HASG07] .1 Algorithm of selecting node reply pull request.

23 ix TIEU LUAN MOI download : [e-mail] List of Abbreviations P2P Peer to Peer MDC Multiple Description Coding ALM Application Layer Multicast ESM End System Multicast x TIEU LUAN MOI download : [e-mail] 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 TIEU LUAN MOI download : skknchat@gmail.

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 TIEU LUAN MOI download : skknchat@gmail. 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.

TIEU LUAN MOI download : skknchat@gmail. 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. TIEU LUAN MOI download : [e-mail] 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. There- fore, multicast approach reduces the dependence of system on ability of source node 5 TIEU LUAN MOI download : skknchat@gmail.