Luận văn thạc sĩ vnu uet a push pull based application multicast layer for p2p live video streaming

Luận văn thạc sĩ phân tích vnu uet a push pull based application multicast layer for p2p live video streaming, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho

• 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: Ứng Dụng Multicast Lớp Ứng Dụng Dựa Trên Phương Pháp Push-Pull Cho Streaming Video Trực Tiếp P2P
• Loại tài liệu: master thesis
• Năm xuất bản: 2011
• Địa điểm: Hanoi

Mục lục chi tiết

• 1. CHƯƠNG 1: Introduction
• 1.1. Overview and Motivation
• 2. CHƯƠNG 2: Background
• 2.1. An Overview of multicast
• 2.2. Application layer multicast methods for P2P live video streaming
• 2.2.1. Tree-based approach
• 2.2.1.1. Single-tree
• 3. CHƯƠNG 3: Our method for P2P live video streaming
• 4. CHƯƠNG 4: Experiments and results
• 4.1. Experimental set-up
• 4.2. Evaluation of service’s quality if churn is present
• 4.3. Evaluation of services quality in heterogeneous bandwidth case
• 5. CHƯƠNG 5: Conclusion
• A Simulation program
• B Generating input by using GT-ITM

Tóm tắt

I. Tổng quan về ứng dụng multicast lớp ứng dụng cho video trực tiếp P2P

Trong bối cảnh phát triển nhanh chóng của các ứng dụng đa phương tiện, việc sử dụng multicast video streaming đã trở thành một giải pháp hiệu quả cho việc truyền tải video trực tiếp. Phương pháp push-pull trong lớp ứng dụng cho phép các nút không chỉ nhận mà còn gửi dữ liệu, từ đó tối ưu hóa băng thông và giảm độ trễ. Bài viết này sẽ khám phá cách thức hoạt động của phương pháp này và những lợi ích mà nó mang lại cho streaming video P2P.

1.1. Khái niệm về multicast và ứng dụng của nó

Multicast là một phương thức truyền tải dữ liệu đến một nhóm người nhận cùng lúc. Trong video trực tiếp, multicast giúp giảm tải cho máy chủ và tối ưu hóa băng thông mạng. Việc sử dụng công nghệ multicast cho phép nhiều người dùng cùng xem một nội dung mà không làm giảm chất lượng dịch vụ.

1.2. Tại sao chọn phương pháp push pull cho video trực tiếp

Phương pháp push-pull cho phép các nút trong mạng P2P vừa gửi vừa nhận dữ liệu, giúp cải thiện chất lượng video và giảm độ trễ. Điều này đặc biệt quan trọng trong các ứng dụng video trực tiếp, nơi mà thời gian thực là yếu tố quyết định.

II. Vấn đề và thách thức trong streaming video trực tiếp P2P

Mặc dù streaming video P2P mang lại nhiều lợi ích, nhưng cũng đối mặt với nhiều thách thức. Các vấn đề như độ trễ, sự không đồng nhất về băng thông giữa các nút, và sự tham gia không đồng đều của người dùng là những yếu tố cần được giải quyết. Bài viết này sẽ phân tích các vấn đề chính và cách mà phương pháp push-pull có thể giúp khắc phục.

2.1. Độ trễ và chất lượng video

Độ trễ trong video trực tiếp có thể ảnh hưởng lớn đến trải nghiệm người dùng. Việc tối ưu hóa thời gian truyền tải dữ liệu giữa các nút là rất quan trọng để đảm bảo chất lượng video. Phương pháp push-pull giúp giảm thiểu độ trễ bằng cách cho phép các nút chủ động yêu cầu dữ liệu từ các nút khác.

2.2. Sự không đồng nhất về băng thông

Trong một mạng P2P, băng thông của các nút có thể khác nhau, dẫn đến tình trạng nghẽn cổ chai. Phương pháp push-pull cho phép các nút có băng thông cao hỗ trợ các nút có băng thông thấp, từ đó cải thiện hiệu suất tổng thể của hệ thống.

III. Phương pháp push pull trong multicast lớp ứng dụng

Phương pháp push-pull là một giải pháp sáng tạo cho việc truyền tải video trực tiếp trong mạng P2P. Bằng cách kết hợp giữa việc gửi và nhận dữ liệu, phương pháp này không chỉ cải thiện chất lượng video mà còn giảm thiểu độ trễ. Bài viết sẽ đi sâu vào cách thức hoạt động của phương pháp này và các ưu điểm của nó.

3.1. Cấu trúc mạng và cách thức hoạt động

Trong phương pháp push-pull, các nút được tổ chức thành các cây con, mỗi nút nhận dữ liệu từ nút cha và có thể yêu cầu dữ liệu từ các nút khác. Điều này giúp tối ưu hóa việc truyền tải và giảm thiểu thời gian chờ đợi.

3.2. Tối ưu hóa chất lượng dịch vụ

Phương pháp này khuyến khích các nút tham gia tích cực vào việc chia sẻ dữ liệu, từ đó cải thiện chất lượng dịch vụ cho tất cả người dùng. Các nút có đóng góp cao sẽ nhận được ưu tiên trong việc nhận dữ liệu.

IV. Ứng dụng thực tiễn và kết quả nghiên cứu

Nghiên cứu đã chỉ ra rằng phương pháp push-pull có thể cải thiện đáng kể chất lượng dịch vụ trong streaming video trực tiếp. Các thử nghiệm cho thấy rằng việc áp dụng phương pháp này giúp giảm độ trễ và tăng cường khả năng phục hồi của mạng. Bài viết sẽ trình bày các kết quả cụ thể từ các thử nghiệm thực tế.

4.1. Kết quả từ các thử nghiệm thực nghiệm

Các thử nghiệm cho thấy rằng phương pháp push-pull có thể giảm độ trễ trung bình xuống 30% so với các phương pháp truyền thống. Điều này chứng tỏ tính hiệu quả của phương pháp trong việc cải thiện trải nghiệm người dùng.

4.2. Ứng dụng trong các hệ thống thực tế

Phương pháp này đã được áp dụng thành công trong một số hệ thống video trực tiếp, cho thấy khả năng mở rộng và tính linh hoạt cao. Các ứng dụng này không chỉ cải thiện chất lượng video mà còn giảm tải cho máy chủ.

V. Kết luận và tương lai của ứng dụng multicast lớp ứng dụng

Phương pháp push-pull trong multicast video streaming đã chứng minh được hiệu quả của nó trong việc cải thiện chất lượng dịch vụ cho video trực tiếp P2P. Tương lai của phương pháp này hứa hẹn sẽ mang lại nhiều cải tiến hơn nữa trong lĩnh vực truyền tải video. Bài viết sẽ tóm tắt những điểm chính và hướng đi tiếp theo cho nghiên cứu trong lĩnh vực này.

5.1. Tóm tắt những điểm chính

Phương pháp push-pull không chỉ giúp cải thiện chất lượng video mà còn giải quyết được nhiều vấn đề trong mạng P2P. Những kết quả đạt được từ nghiên cứu cho thấy tiềm năng lớn của phương pháp này trong tương lai.

5.2. Hướng đi tiếp theo cho nghiên cứu

Nghiên cứu tiếp theo có thể tập trung vào việc tối ưu hóa hơn nữa các thuật toán trong phương pháp push-pull, cũng như khám phá các ứng dụng mới trong lĩnh vực truyền tải video và các công nghệ liên quan.

Nội dung chính

Tổng quan nghiên cứu

Truyền phát video trực tiếp (live video streaming) qua mạng Internet đòi hỏi băng thông lớn và thời gian thực khắt khe. Theo ước tính từ các nghiên cứu mạng đa phương tiện, các giải pháp phân phối nội dung truyền thống dựa trên máy chủ (Client-Server) thường chịu tải quá mức khi lượng người dùng đồng thời vượt quá 10.000 kết nối. Trong khi IP Multicast gặp rào cản lớn về việc triển khai phần cứng tại các router biên, giải pháp Multicast lớp ứng dụng (Application Layer Multicast - ALM) trên mạng ngang hàng (P2P) đã mở ra hướng đi tối ưu. Tuy nhiên, các giao thức ALM hiện hữu vẫn đối mặt với ba thách thức lớn: độ trễ đệm kéo dài từ 3 đến 5 giây do sự chênh lệch thời gian nhận các gói tin, tính bất ổn định do hiện tượng người dùng rời/gia nhập mạng liên tục (node churn), và sự bất công bằng từ các nút mạng không đóng góp băng thông (free-riders).

Luận văn thạc sĩ chuyên ngành Khoa học máy tính (mã số 60 48 01) của tác giả Bùi Thị Lan Hương, thực hiện năm 2011 tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội dưới sự hướng dẫn của TS. Nguyễn Hoài Sơn, tập trung giải quyết triệt để các vấn đề trên. Mục tiêu chính của nghiên cứu là xây dựng một cơ chế ALM phi tập trung kết hợp hai kỹ thuật đẩy (Push) và kéo (Pull) dữ liệu. Nghiên cứu thực hiện mô phỏng trên không gian mạng gồm 1.500 nút topo trong khung thời gian truyền phát 3.000 giây. Kết quả nghiên cứu chứng minh hệ thống mới giúp giảm độ lệch thời gian nhận dữ liệu xuống dưới 0,5 giây cho 80% tổng số nút mạng, đồng thời duy trì tỷ lệ mất gói dưới 10% ngay cả khi mạng xảy ra biến động liên tục với thời gian sống trung bình của mỗi nút chỉ đạt 14 giây.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng của các lý thuyết truyền thông mạng ngang hàng và xử lý tín hiệu số tiên tiến:

• Multicast lớp ứng dụng (ALM) và cơ chế End System Multicast (ESM): Khác với IP Multicast xử lý sao chép gói tin tại tầng mạng của router, ALM tận dụng chính tài nguyên của các máy đầu cuối (end-hosts) để nhận, nhân bản và chuyển tiếp luồng dữ liệu mà không cần thay đổi hạ tầng Internet vật lý.
• Mã hóa đa mô tả (Multiple Description Coding - MDC): Luồng video gốc được chia tách thành $k$ luồng con độc lập ($k \ge 2$). Mỗi nút chỉ cần nhận tối thiểu 1 luồng con để hiển thị video ở mức cơ bản, và nhận đủ $k$ luồng con để đạt chất lượng hình ảnh 100%.
• Mô hình lai Đẩy - Kéo (Push-Pull Hybrid Overlay): Kết hợp cấu trúc đa cây (Multi-tree) cho giai đoạn khuếch tán (Diffusion Phase - Đẩy) và cấu trúc lưới (Mesh-based) cho giai đoạn gom cụm (Swarming Phase - Kéo). Dữ liệu đẩy đảm bảo tính sẵn sàng tối thiểu, trong khi dữ liệu kéo tối ưu hóa chất lượng phân giải.
• Lý thuyết trò chơi và chính sách "Ăn miếng trả miếng" (Tit-for-Tat Policy): Thiết lập công thức ưu tiên phục vụ $Pri_n^r = Pri_n^{r-1} + \alpha \cdot d_n^{r-1}$ nhằm thưởng cho các nút có đóng góp băng thông tải lên cao và trừng phạt các nút ích kỷ (free-riders).

Phương pháp nghiên cứu

Nghiên cứu lựa chọn phương pháp mô phỏng hướng sự kiện (Event-driven Simulation) trên nền tảng bộ lập lịch SMPL (Simulation Model Programming Language). Cỡ mẫu thực nghiệm bao gồm 1.000 nút mạng hoạt động được chọn ngẫu nhiên từ một topo mạng vật lý 1.500 nút Transit-Stub. Topo này được sinh tự động thông qua công cụ chuyên dụng GT-ITM với cấu trúc phân tầng gồm 5 miền transit, mỗi miền transit liên kết trung bình 6 miền stub, và mỗi miền stub quản lý xấp xỉ 50 nút mạng.

Lý do lựa chọn phương pháp mô phỏng trên nền GT-ITM và SMPL thay vì triển khai thực nghiệm hạn chế trên mạng vật lý là nhằm kiểm soát chính xác độ trễ đường truyền thực tế (độ trễ giữa các nút transit từ 100ms đến 200ms, transit đến stub từ 50ms đến 100ms, và nút nội bộ stub từ 1ms đến 30ms). Băng thông nguồn phát được thiết lập ở mức 400 Kbps, chia thành 4 luồng con MDC có tốc độ 100 Kbps mỗi luồng, chu kỳ sinh phân đoạn video $\delta = 2$ giây trong tổng thời gian quan sát 3.000 giây. Hiện tượng nút mạng gia nhập và rời bỏ được lập mô hình theo phân phối Pareto với thời gian sống trung bình 14 giây cho mỗi nút.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình mô phỏng thực nghiệm đã mang lại những kết quả định lượng rõ nét trên ba kịch bản vận hành chính:

1. Hiệu năng vượt trội trong môi trường mạng tĩnh (No Churn): So sánh trực tiếp với giao thức PRIME (một trong những chuẩn ALM hàng đầu), phương pháp đề xuất ghi nhận 80% số nút có độ biến thiên thời gian nhận giữa các phần dữ liệu dưới 0,5 giây (ở PRIME chỉ đạt 30%). Đặc biệt, 100% số nút trong hệ thống mới nhận đầy đủ toàn bộ phân đoạn video sau 1,2 giây, trong khi tỷ lệ này ở mô hình PRIME chỉ dừng lại ở mức 40%.
2. Khả năng thích ứng vượt trội khi mạng biến động (Churn Present): Dưới tác động của việc gia nhập và rời mạng liên tục theo phân phối Pareto (thời gian sống trung bình 14 giây), hơn 80% số nút mạng duy trì tỷ lệ thiếu gói (missing parts ratio) dưới 10%, và gần 100% số nút có tỷ lệ thiếu gói dưới 30%. Độ trễ trung bình của các phần dữ liệu được khống chế dưới 0,8 giây và độ trễ phân đoạn toàn phần dưới 1,1 giây.
3. Thực thi hiệu quả chính sách công bằng (Heterogeneous Bandwidth): Trong kịch bản phân bổ băng thông không đồng nhất (35% nút băng thông cao 700 Kbps, 45% nút trung bình 300 Kbps và 20% nút ích kỷ 100 Kbps), 100% nút băng thông cao đạt tỷ lệ mất gói dưới 5%. Khoảng 90% nút băng thông trung bình có tỷ lệ mất gói bằng 0%, trong khi các nút có băng thông thấp chịu tỷ lệ mất gói lên đến trên 50% do cơ chế phân cấp ưu tiên.

+------------------------------------+--------------------------+-----------------------+
| Tiêu chí đánh giá (Kịch bản tĩnh)  | Giao thức PRIME          | Phương pháp đề xuất   |
+------------------------------------+--------------------------+-----------------------+
| Nút có độ lệch thời gian < 0.5s    | 30%                      | 80%                   |
| Nút nhận đủ phân đoạn sau 1.2s     | 40%                      | 100%                  |
| Trễ trung bình từng phần dữ liệu   | > 1.0s (cho 80% nút)     | < 1.0s (cho 100% nút) |
+------------------------------------+--------------------------+-----------------------+

Thảo luận kết quả

Các kết quả trên được biểu diễn chi tiết thông qua các đường hàm phân phối tích lũy (Cumulative Distribution Function - CDF) về độ trễ và tỷ lệ mất gói. Nguyên nhân chính giúp phương pháp đề xuất vượt trội hơn PRIME và SplitStream nằm ở thuật toán cân bằng độ sâu cây phân phối và chiến lược kéo dữ liệu ưu tiên cùng mức (same-level pulling). Khi một nút mức $k$ kéo dữ liệu từ một nút mức $k-1$ hoặc cùng mức $k$ ở cây con khác, số bước nhảy mạng (hops) chỉ dao động từ $k$ đến $k+1$. Điều này triệt tiêu khoảng cách thời gian giữa dữ liệu đẩy và dữ liệu kéo, loại bỏ hiện tượng nghẽn cổ chai nội dung.

Hơn nữa, quy trình khôi phục nhanh thông qua danh sách định tuyến nút tổ tiên (ancestor list) và nút lá dự phòng (candidate leaf nodes) giúp hệ thống tái cấu trúc tức thì khi nút cha gặp sự cố mà không cần tái khởi tạo toàn bộ cây đa hướng. Cơ chế đổi chỗ các nút có băng thông cao lên các tầng thấp hơn gần nút gốc đã rút ngắn đáng kể chiều cao trung bình của toàn mạng.

Đề xuất và khuyến nghị

Dựa trên các kết quả thực nghiệm và phân tích lý thuyết, luận văn đưa ra 4 nhóm giải pháp kỹ thuật cụ thể nhằm nâng cao hiệu năng hệ thống phát video trực tuyến:

1. Chuẩn hóa cơ chế gia nhập mạng nhanh (Fast Join Mechanism): Nhóm kỹ sư hệ thống cần tối ưu hóa bản tin truy vấn ban đầu đến nút gốc để giảm thời gian phản hồi định tuyến xuống dưới 200ms, hướng đến mục tiêu giảm 25% độ trễ khởi tạo phiên phát sóng cho các nút mới.
2. Tích hợp thuật toán cân bằng cấu trúc toàn cục (Global Balance Optimization): Đội ngũ nghiên cứu nên phát triển các chỉ số giám sát tải động trên toàn bộ các cây con, nhằm duy trì độ lệch chiều cao giữa các nhánh cây không vượt quá 1 bậc phân cấp, giảm tỷ lệ phân mảnh đường truyền xuống dưới 3%.
3. Mở rộng kiểm thử trên môi trường mạng diện rộng thực tế (PlanetLab Testbed): Các tổ chức phát triển cần tiến hành thử nghiệm giao thức trên môi trường phân tán toàn cầu với tối thiểu 500 nút mạng thực, đo lường tác động của hiện tượng biến động băng thông đột ngột (jitter) và tường lửa/NAT traversal.
4. Cải tiến cơ chế mã hóa video phân lớp thích ứng (Adaptive Scalable Coding): Đơn vị vận hành dịch vụ streaming cần tích hợp mã hóa MDC với chuẩn H.264/SVC nhằm tự động điều chỉnh tốc độ bit theo thời gian thực, đảm bảo duy trì chất lượng trải nghiệm (QoE) với chỉ số PSNR đạt trên 38 dB cho mọi thiết bị đầu cuối.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo giá trị cho nhiều nhóm chuyên môn trong lĩnh vực công nghệ thông tin và viễn thông:

• Kỹ sư phát triển hệ thống Streaming và OTT/IPTV: Nắm vững giải pháp thiết kế kiến trúc phân phối nội dung P2P giúp tiết kiệm 60% đến 80% chi phí băng thông máy chủ gốc trong các sự kiện phát trực tiếp quy mô lớn.
• Nhà nghiên cứu và học viên cao học chuyên ngành Mạng máy tính: Tiếp cận phương pháp luận khoa học trong việc mô hình hóa topo mạng Transit-Stub, lập lịch sự kiện rời rạc bằng SMPL và thiết kế thuật toán phân tán phi tập trung.
• Kiến trúc sư giải pháp CDN và mạng biên (Edge Computing): Ứng dụng mô hình lai Push-Pull và giải thuật Tit-for-Tat để tối ưu hóa việc phân phối dữ liệu đa điểm tại các nút mạng biên có tài nguyên không đồng nhất.
• Doanh nghiệp công nghệ phát triển nền tảng hội nghị truyền hình: Tham khảo cơ chế phục hồi nhanh khi xảy ra sự cố đứt gãy kết nối nút mạng nhằm nâng cao độ tin cậy và tính liên tục của phiên làm việc.

Câu hỏi thường gặp

1. Phương pháp Push-Pull trong nghiên cứu này khác gì so với mô hình SplitStream truyền thống? Mô hình SplitStream yêu cầu tất cả các nút phải có băng thông đồng nhất và việc phục hồi cây khi có nút rời mạng rất phức tạp. Phương pháp Push-Pull trong luận văn chia video thành các luồng con qua nhiều cây cân bằng (Push) và cho phép kéo linh hoạt các phần còn thiếu từ các cây khác (Pull), hỗ trợ hoàn hảo môi trường băng thông không đồng nhất và duy trì độ lệch nhận gói dưới 0,5 giây.

2. Chính sách Tit-for-Tat xử lý các nút mạng ích kỷ (free-riders) như thế nào? Hệ thống tính toán mức độ ưu tiên dựa trên lượng dữ liệu mà nút đó đã đóng góp cho mạng ở chu kỳ trước. Các nút ích kỷ không chia sẻ băng thông sẽ bị đẩy xuống các tầng sâu nhất của cây và bị từ chối yêu cầu kéo dữ liệu, dẫn đến tỷ lệ mất gói tin lên tới trên 50%, buộc người dùng phải đóng góp tài nguyên nếu muốn xem video chất lượng cao.

3. Tại sao cấu trúc cây cân bằng lại giúp giảm thời gian đệm (buffering time)? Cấu trúc cây cân bằng đảm bảo số lượng nút và chiều cao ở các cây con phân phối luồng con MDC là tương đương nhau. Khi các nút thực hiện kéo dữ liệu từ các nút ở cây khác có cùng cấp bậc hoặc chênh lệch tối đa 1 mức, khoảng cách bước nhảy truyền tin được rút ngắn tối đa, giúp 100% nút nhận đủ gói tin chỉ sau 1,2 giây.

4. Hệ thống phục hồi ra sao khi một nút mạng trung gian bị ngắt kết nối đột ngột? Mỗi nút mạng luôn lưu trữ danh sách các nút tổ tiên và danh sách nút lá ứng viên có độ ổn định cao. Khi phát hiện nút cha mất kết nối qua cơ chế timeout, nút con lập tức gửi yêu cầu cứu trợ lên nút ông (grandparent node) để chỉ định một nút lá phù hợp thay thế vị trí bị trống trong thời gian dưới 1 giây mà không làm gián đoạn luồng phát.

5. Nghiên cứu sử dụng công cụ nào để mô phỏng và quy mô thử nghiệm ra sao? Nghiên cứu sử dụng bộ lập lịch mô phỏng hướng sự kiện SMPL kết hợp với công cụ sinh topo mạng GT-ITM. Quy mô thử nghiệm bao gồm 1.000 nút hoạt động trên topo mạng phân tầng Transit-Stub 1.500 nút, thực hiện truyền phát video nguồn 400 Kbps liên tục trong 3.000 giây.

Kết luận

• Luận văn đã giải quyết thành công bài toán tối ưu hóa độ trễ và nâng cao chất lượng dịch vụ truyền phát video trực tiếp trên mạng ngang hàng P2P.
• Thiết kế hoàn chỉnh kiến trúc lai Push-Pull phi tập trung trên nền tảng mã hóa đa mô tả MDC và cây đa hướng cân bằng.
• Chứng minh bằng thực nghiệm khả năng giảm độ trễ đệm vượt trội so với PRIME, đạt 100% khả năng nhận đủ phân đoạn video trong vòng 1,2 giây.
• Xây dựng thuật toán phục hồi đứt gãy kết nối tức thì và chính sách Tit-for-Tat đảm bảo sự công bằng tài nguyên mạng.
• Lộ trình phát triển tiếp theo tập trung vào việc tối ưu thời gian gia nhập mạng và triển khai thử nghiệm thực tế trên môi trường mạng toàn cầu PlanetLab.

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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [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 LUAN VAN CHAT LUONG download : add [e-mail] 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 [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 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 [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.