Tóm tắt Luận văn Nghiên cứu một số thuật toán lập lịch tối ưu trên mạng ngang hàng (P2P)

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN THỊ THÙY ANH NGHIÊN CỨU MỘT SỐ THUẬT TOÁN LẬP LỊCH TỐI ƯU TRÊN MẠNG NGANG HÀNG (P2P) Chuyên ngành: HỆ THỐNG THÔNG TIN Mã số: 60.48.01.04 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS VŨ VĂN THỎA Phản biện 1: Phản biện 2: .. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện công ngện công nghệ Bưu Chính Viễn Thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm .......... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU Ngày nay, cùng với mức độ phổ biến của máy tính cá nhân và mạng viễn thông, internet đã thực sự phát triển và có tác động tích cực vào đời sống xã hội và của mỗi con người. Dựa trên internet, người sử dụng có khả năng chia sẻ những tài nguyên lớn một cách nhanh chóng và hiệu quả. Mạng ngang hàng (P2P) với nhiều đặc tính phù hợp cho các hệ thống phân tán và cho các ứng dụng, ngày càng thu hút được nhiều chú ý của người sử dụng và giới nghiên cứu trên thế giới về các lĩnh vực: tô pô mạng, định tuyến, giao thức, lập lịch, triển khai các dịch vụ ứng dụng, ... Bài toán lập lịch trong mạng ngang hàng tập trung chủ yếu vào vấn đề lựa chọn cơ chế kéo/đẩy dữ liệu hợp lý giữa các nút (peer) trong mạng. Việc sử dụng thuật toán lập lịch cụ thể trong mạng ngang hàng có ảnh hưởng rất lớn đến các tham số hiệu năng của hệ thống mạng như: trễ (Delay), tỷ lệ mất gói (Packet Loss), băng thông (Bandwidth), Đã có nhiều tác giả quan tâm nghiên cứu và đề xuất nhiều thuật toán lập lịch tối ưu. Do đó, học viên chọn đề tài “Nghiên cứu một số thuật toán lập lịch tối ưu trên mạng ngang hàng (P2P)” cho luận văn tốt nghiệp thạc sĩ. Căn cứ mục tiêu và yêu cầu nghiên cứu, đề tài được bố cục gồm các phần sau: 2 MỞ ĐẦU CHƯƠNG 1: TỔNG QUAN VỀ MẠNG NGANG HÀNG. Trong chương này luận văn tiến hành khảo sát những vấn đề chung về mạng ngang hàng và vấn đề lập lịch trong mạng ngang hàng. CHƯƠNG 2: CÁC THUẬT TOÁN LẬP LỊCH TỐI ƯU TRONG MẠNG NGANG HÀNG. Chương 2 sẽ trình bày một số thuật toán lập lịch tối ưu trong mạng ngang hàng cho một số mạng phổ biến hiện nay như sau: - Mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM). - Mạng chồng phủ truyền tải dữ liệu DON (Data-driven Overlay Networks). - Mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System). CHƯƠNG 3: ĐÁNH GIÁ HIỆU NĂNG CÁC THUẬT TOÁN LẬP LỊCH TỐI ƯU TRÊN MẠNG NGANG HÀNG. Chương 3 sẽ trình bày đánh giá các thuật toán lập lịch tối ưu trên mạng ngang hàng đã được nghiên cứu trong chương 2. KẾT LUẬN TÀI LIỆU THAM KHẢO. 3 CHƯƠNG 1: TỔNG QUAN VỀ MẠNG NGANG HÀNG 1.1 Giới thiệu mạng ngang hàng 1.1.1 Khái niệm Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy khách, nói cách khác, tất cả các máy tham gia đều bình đẳng, mỗi máy là một nút mạng (còn gọi là peer) đóng vai trò đồng thời là máy khách và máy chủ đối với các máy khác trong mạng. 1.1.2 Đặc điểm chung của mạng ngang hàng Mạng ngang hàng có thể xem như tập hợp của các máy tính đơn lẻ được liên kết với nhau và cùng đóng góp tài nguyên (bao gồm dung lượng ổ cứng, băng thông và khả năng tính toán). Sức mạnh của mạng tăng khi số nút tham gia mạng tăng. Một ưu thế khác của mạng ngang hàng so với mô hình client/server truyền thống đó chính là tính chất phân tán. Điều này đảm bảo được tính bền vững của mạng khi có một (hoặc một vài nút) gặp phải sự cố. Đảm bảo tính sẵn sàng cao, chi phí xây dựng thấp. 1.1.3 Ứng dụng của mạng ngang hàng 1.1.3.1 Chia sẻ tài liệu 4 1.1.3.2 Ứng dụng phân tán tính toán 1.1.3.3 Ứng dụng hợp tác 1.1.3.4 Ứng dụng lớp nền 1.2 Phân loại mạng ngang hàng Mạng ngang hàng có thể phân loại theo tiêu chí mục đích sử dụng hoặc tiêu chí mức độ phân tán (hay tập trung) và cấu trúc của mạng. Theo tiêu chí mục đích sử dụng có thể kể ra một số mạng ngang hàng như: - Mạng chia sẻ file (file sharing) - Mạng điện thoại VoIP (telephony) - Mạng đa phương tiện media streaming (audio, video) - Diễn đàn thảo luận (Discussion forums) Theo tiêu chí mức độ phân tán và cấu trúc của mạng có thể kể ra một số mạng ngang hàng như: - Mạng ngang hàng không cấu trúc (unstructured) bao gồm: + Mạng ngang hàng tập trung (Cetralized) + Mạng ngang hàng thuần túy (Pure) + Mạng ngang hàng lai (Hybrid) - Mạng ngang hàng có cấu trúc (structured) 5 Trong mục này sẽ trình bày phân loại mạng ngang hàng theo tiêu chí mức độ phân tán và cấu trúc của mạng. 1.2.1. Mạng ngang hàng không cấu trúc 1.2.1.1 Mạng ngang hàng tập trung Đặc trưng của mạng kiểu này là vẫn dựa vào một máy chủ tìm kiếm trung tâm. Máy chủ trung tâm có vai trò như một server. Hoạt động của mạng ngang hàng tập trung bao gồm: - Trao đổi thông tin giữa peer và máy chủ tìm kiếm trung tâm - Trao đổi dữ liệu giữa các peer với nhau. Mạng ngang hàng tập trung có các ưu, nhược điểm sau đây. Ưu điểm: - Hệ thống mạng dễ xây dựng; - Tốc độ tìm kiếm dữ liệu nhanh, hiệu quả. Nhược điểm: - Hệ thống mạng không có tính bảo mật cao, dễ bị tấn công; - cần có trung tâm quản trị - Không bảo vệ được bản quyền nội dung. - Có hiện tượng nút cổ chai tại máy chủ nên khả năng mở rộng mạng bị hạn chế. 6 1.2.1.2 Mạng ngang hàng thuần túy Trong mạng ngang hang thuần túy các peer giao tiếp trực tiếp với peer khác trong mạng mà không cần các máy chủ trung tâm riêng biệt nào. Các peer thiết lập kết nối với nhau ngẫu nhiên. Trong mạng ngang hàng thuần túy, quá trình tìm kiếm dữ liệu sử dụng phương pháp phát tràn (Flooding). Mạng ngang hàng thuần túy có các ưu, nhược điểm sau đây. Ưu điểm: - Hệ thống mạng dễ xây dựng; - Khắc phục hiện tượng nút cổ chai; - Đảm bảo tính phân tán hoàn toàn: Các node tham gia mạng và rời khỏi mạng một cách tùy ý mà không ảnh hưởng đến cấu trúc của mạng. Nhược điểm: - Tốn băng thông: Các node có khả năng khác nhau(CPU power, bandwidth, storage) đều có thể phải chịu tải(load) như nhau. - Quá trình tìm kiếm dữ liệu phức tạp. 1.2.1.3 Mạng ngang hàng lai Mạng ngang hàng lai có các ưu điểm sau đây. 7 - Hạn chế việc flooding các query, làm giảm lưu lượng trong mạng, nhưng vẫn tránh được hiện tượng nút cổ chai (do có nhiều Super peers). - Khắc phục được nhược điểm về sự khác nhau về CPU power, bandwidthở mạng ngang hàng thuần túy, các Super peer sẽ chịu tải chính, các node khác chịu tải nhẹ. 1.2.2 Mạng ngang hàng có cấu trúc Để khắc phục nhược điểm của mạng ngang hàng không cấu trúc mạng ngang hàng có cấu trúc đã ra đời sử dụng bảng băm phân tán (Distributed Hash Table-DHT). Đặc điểm của DHT có thể tóm tắt như sau: - Phân tán: DHT là tập hợp các node mà không cần bất kỳ một máy trung tâm nào. - Chống lỗi: hệ thống hoạt động được trong trường hợp các nút liên tục ra, vào hoặc bị lỗi. - Khả năng mở rộng: hệ thống hoạt động ổn định khi có số lượng lớn các nút tham gia. Mạng ngang hàng có cấu trúc có các ưu, nhược điểm sau đây. Ưu điểm: Khả năng mở rộng mạng với mô hình mạng có cấu trúc được nâng cao rõ rệt. 8 Nhược điểm: Việc quản lý cấu trúc của topo mạng gặp khó khăn, đặc biệt trong trường hợp tỷ lệ vào/ra mạng của các nút cao. Vấn đề cân bằng tải trong mạng này cũng là một khó khăn. 1.3 Lập lịch trong mạng ngang hàng 1.3.1 Giới thiệu Vấn đề lập lịch trong mạng ngang hàng đóng vai trò rất quan trọng vì nó trực tiếp điều phối việc các gói tin được truyền đi và phân phối giữa các peer như thế nào. Quá trình này ảnh hưởng trực tiếp đến hiệu năng của hệ thống P2P. Một lịch trình phân phối dữ liệu kém có thể làm cho thời gian tải dữ liệu về lâu hơn rất nhiều. Trong khi đó, một lịch trình tốt có thể rút ngắn thời gian hoàn thành và tối ưu việc sử dụng các nguồn tài nguyên mạng. 1.3.2 Mô hình lập lịch đẩy (Push) 1.3.3 Mô hình lập lịch kéo (Pull) 1.3.4 Mô hình lai kết hợp đẩy/ kéo (Push/ Pull) Trong mô hình kết hợp Push/ Pull, mỗi nút mạng là độc lập và không đồng bộ với nguồn hoặc với các peer khác. 1.4 Kết chương Trong chương này luận văn đã khảo sát những vấn đề chung về mạng ngang hàng và vấn đề lập lịch trong mạng ngang hàng. Mặc dù vẫn còn những vấn đề về bảo mật, về bản quyền của những nội dung được trao đổi, nhưng với những ưu thế và lợi ích mà mạng 9 ngang hàng đem lại, mạng ngang hàng cần phải được tiếp tục nghiên cứu và phát triển. Trên cơ sở các nội dung nghiên cứu trong chương 1, chương 2 sẽ nghiên cứu một số thuật toán lập lịch tối ưu trong các mạng ngang hàng phổ biến. 10 CHƯƠNG 2: CÁC THUẬT TOÁN LẬP LỊCH TỐI ƯU TRONG MẠNG NGANG HÀNG Vấn đề lập lịch tối ưu trong mạng ngang hàng đóng vai trò rất quan trọng đến việc nâng cao hiệu năng của mạng. Trong chương 2 sẽ trình bày một số thuật toán lập lịch tối ưu trong mạng ngang hàng cho một số mạng phổ biến hiện nay như sau: - Mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM). - Mạng chồng phủ truyền tải dữ liệu DON (Data-driven Overlay Networks). - Mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System). 2.1 Lập lịch tối ưu trong mạng hình lưới không cấu trúc kết nối hoàn toàn 2.1.1 Mô hình mạng Trong mục này ta xét hệ thống P2P live streaming không có cấu trúc, bao gồm N peer được mô hình hóa bởi mạng ngang hàng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM). Hệ thống được mô hình hóa như là một nguồn P0 và tập S= {P1, , PN} gồm N peer Pi nhận luồng dữ liệu từ nguồn. Nguồn tạo ra luồng dữ liệu, được chia ra thành Mc chunk. Mỗi peer Pi nhận chunk Cj từ các peer khác và sau đó gửi chúng đi với tốc độ s(Pi). 11 Nguồn gửi các chunk với tốc độ s(source). Tập các chunk vừa được Pi nhận tại thời điểm t được kí hiệu là C(Pi, t). 2.1.2 Lập lịch peer tối ưu Cơ sở lựa chọn peer tối ưu đó là: peer đích được lựa chọn phải có thể ngay lập tức tham gia vào quá trình phân bổ chunk. Khảo sát lập lịch peer “Earliest Latest” ELp. Hình 2.1: Thuật toán lập lịch peer Elp 2.1.3 Lập lịch chunk tối ưu Lập lịch cho chunk có thể có nhiều dang. Ở đây luận văn chỉ khảo sát hai thuật toán lập lịch RUc (Random Useful Chunk) và Dl (DeadLine Chunk). 2.1.4 Lập lịch tối ưu chunk/peer kết hợp Ở đây luận văn sẽ khảo sát hai thuật toán lập lịch chunk/peer kết hợp là LUc/ELp và Dl/ELp. Trong mục này ta sẽ chứng minh hai thuật toán lập lịch LUc/ELp và Dl/ELp là tối ưu. 12 2.2 Lập lịch tối ưu cho mạng DON (Data-driven Overlay Networks) 2.2.1 Giới thiệu chung Giới thiệu chung về mạng DON, cách thiết lập mạng DON. 2.2.2 Mô hình lập lịch tối ưu Trong mạng DON, các phương tiện truyền thông được phân chia thành các block và được lưu trữ tại các peer. Tất cả các nút thông báo định kỳ sự có mặt của các block tại nút đó cho các peer láng giềng với một vector bit được gọi là “bản đồ bộ đệm”. Sau đó các nút sẽ yêu cầu các block mà nó không có từ các peer láng giềng. Hình 2.3: Mô hình lập lịch block trong DON Mục đích của lập lịch này là tối đa hóa các ưu tiên của tất cả các block được yêu cầu trong các lớp chồng phủ với những hạn chế băng thông khác nhau. 13 2.2.3 Các thuật toán tìm phương án lập lịch tối ưu 2.2.3.1 Thuật toán đơn hình Trình bày thuật toán đơn hình. 2.2.3.2 Thuật toán tìm luồng với chi phí nhỏ nhất Trình bày thuật toán tìm luồng với chi phí nhỏ nhất. 2.2.3.3 Thuật toán phân phối Heuristic Trình bày thuật toán phân phối Heuristic. 2.3 Lập lịch tối ưu cho mạng truyền tải video trực tiếp 2.3.1 Mô hình hóa Mô tả và mô hình hóa một phiên trực tuyến trên một mạng chồng phủ như một đồ thị có hướng G = {V, E}, trong đó V là tập các đỉnh đại diện cho các nút peer và E là tập các cạnh lớp phủ đại diện cho các liên kết lớp phủ. 2.3.2 Bài toán cực tiểu hóa trễ trung bình end-to-end trong P2P live streaming Trình bày bài toán cực tiểu hóa trễ trung bình end-to-end trong P2P live streaming (Minimizing Average End-to-End Delay in P2P Live Streaming Systems - MADPS) đưa ra một phương án lập lịch dòng cực tiểu hóa trễ trung bình end-to-end sao cho tất cả các peer nhận đều là các peer được phục vụ đầy đủ. 14 2.3.3 Thuật toán xấp xỉ giải bài toán MADPS Trình bày thuật toán xấp xỉ để giải bài toán MADPS. 2.4 Kết chương Chương 2 dã nghiên cứu một số thuật toán lập lịch tối ưu cho ba mô hình mạng cụ thể. - Đối với mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM) luận văn đã khảo sát các thuật toán lập lịch tối ưu cho chunk, peer và chunk/peer phối hợp là LUc/ELp và Dl/ELp. - Đối với mạng chồng phủ truyền tải dữ liệu DON (Data- driven Overlay Networks) đã khảo sát ba thuật toán lập lịch tối ưu là phương pháp đơn hình cho bài toán quy hoạch tuyến tính, phương pháp tìm luồng với chi phí nhỏ nhất và thuật toán phân phối Heuristic. - Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System) đã trình bày thuật toán xấp xỉ để giải quyết bài toán MADPS. 15 CHƯƠNG 3 ĐÁNH GIÁ CÁC THUẬT TOÁN LẬP LỊCH TỐI ƯU TRÊN MẠNG NGANG HÀNG Chương 3 sẽ trình bày đánh giá các thuật toán lập lịch tối ưu trên mạng ngang hàng đã được nghiên cứu trong chương 2. Quá trình đánh giá các thuật toán lập lịch tối ưu trên mạng ngang hàng phức tạp. Do đó, trong chương này luận văn sẽ hạn chế tập trung khảo sát các vấn đề sau: - Đối với mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM) sẽ mô phỏng đánh giá hiệu năng trễ (Delay) của hai thuật toán chunk/peer phối hợp là LUc/ELp và DLc/ELp. - Đối với mạng chồng phủ truyền tải dữ liệu DON (Data- driven Overlay Networks) sẽ mô phỏng đánh giá tốc độ trung bình chia sẻ các block trong mạng. - Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System) sẽ đánh giá chi tiết thuật toán lập lịch tối ưu bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời gian thực hiện chương trình. 16 3.1 Mô phỏng đánh giá hiệu năng thuật toán lập lịch tối ưu trong mạng hình lưới không cấu trúc kết nối hoàn toàn 3.1.1 Đặt bài toán Xét mạng P2P hình lưới không cấu trúc kết nối hoàn toàn gồm N nút (peer), không kể nút nguồn. Kí hiệu trễ toàn mạng cho tới khi tất cả các nút nhận được đầy đủ dữ liệu cần thiết theo yêu cầu trong trường hợp xấu nhất là F. Theo công thức (2.1) trong mục 2.1, thuật toán lập lịch là tối ưu nếu F = 2log N   + 1. Trong mục này, ta sẽ mô phỏng đánh giá hiệu năng của hai thuật toán lập lịch kết hợp LUc/ELp và DLc/ELp như là một hàm của số các nút mạng N: F = f(N) 3.1.2 Nội dung mô phỏng (1) Công cụ mô phỏng: Trong luận văn sử dụng công cụ mô phỏng P2PTVSim ([10]) trên nền WindowXP. (2) Kịch bản mô phỏng: - Mô hình mạng: Mạng được tạo ngẫu nhiên theo số peer N (trừ peer nguồn) như là một đồ thị đầy đủ. N sẽ nhận các giá trị khác nhau. - Băng thông Upload tại các Peer là như nhau. 17 - Độ tin cậy thống kê các kết quả là 90% với ý nghĩa là tính trễ phân bổ sau khi tất cả các peer đều đã nhận được 90% số lượng các chunk đã gửi từ nguồn. 3.1.3 Kết quả và đánh giá Hình 3.1: Kết quả mô phỏng cho FM - Kết quả mô phỏng chứng tỏ hai thuật toán lập lịch LUc/ELp và DLc/ELp là các thuật toán lập lịch tối ưu. - Tuy nhiên, giá trị của thuật toán lập lịch tối ưu LUc/ELp gần với kết quả lý thuyết hơn là DLc/ELp. 3.2 Mô phỏng đánh giá hiệu năng thuật toán lập lịch tối ưu trong mạng DON 3.2.1 Đặt bài toán Xét mạng chồng phủ truyền tải dữ liệu DON (Data-driven Overlay Networks) gồm N nút. Ta định nghĩa tốc độ phân bổ R(i) các block tại mỗi nút i là tỷ số giữa số lượng các block nút i nhận được trước hoặc tại thời điểm kết thúc playback và số lượng các block đã phát. 18 Tốc độ phân bổ trung bình R(tb) là: R(tb) = ( ) i R R i   (3.1) Như vậy giá trị R(tb) như là một hàm của tốc độ dòng trong mạng DON. Trong mục này ta sẽ mô phỏng đánh giá R(tb) bằng phương pháp giải bài toán trong mục 2.2 là phương pháp đơn hình. Giả thiết là mạng DON không có các nút cổ chai. 3.2.2 Kết quả và đánh giá Hình 3.2: Kết quả mô phỏng R(tb) cho DON - Kết quả mô phỏng chứng tỏ phương pháp đơn hình cho nghiệm tối ưu toàn cục. Kết quả này tốt hơn kết quả tính nghiệm xấp xỉ trong [4]. - Tuy nhiên, phương pháp đơn chạy chậm hơn phương pháp trong [4] và không thể sử dụng khi số nút lớn và kết nối phức tạp. Trong luận văn chỉ mô phỏng mạng DON với số nút 50, còn [4] với số nút là 500. 19 3.3 Đánh giá thuật toán lập lịch tối ưu cho mạng truyền tải video trực tiếp 3.3.1 Phân tích thuật toán Trong phần này chúng ta tiến hành chứng minh và phân tích thuật toán iStream-APX bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời gian thực hiện chương trình. 3.3.2 Ước lượng độ phức tạp thời gian của thuật toán Trong phần này chúng ta phân tích các ràng buộc về thời gian chạy. 3.4 Kết chương Trong chương 3 đã thực hiện mô phỏng đánh giá hiệu năng của các thuật toán lập lịch tối ưu cho ba mô hình mạng sau đây. - Đối với mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM) đã mô phỏng đánh giá hiệu năng trễ (Delay) F trong trường hợp xấu nhất của hai thuật toán chunk/peer phối hợp là LUc/ELp và DLc/ELp. - Đối với mạng chồng phủ truyền tải dữ liệu DON (Data- driven Overlay Networks) đã mô phỏng đánh giá tốc độ trung bình R(tb) chia sẻ các block trong mạng tương ứng các tốc độ dòng khác nhau sử dụng phương pháp đơn hình. - Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System) đã phân tích, đánh giá chi tiết thuật toán lập lịch 20 tối ưu bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời gian thực hiện chương trình. Các kết quả đánh giá mô phỏng là phù hợp với lý thuyết và mở ra khả năng ứng dụng các thuật toán lập lịch tối ưu trong các dịch vụ thực tế. 21 KẾT LUẬN Luận văn đã đạt được các kết quả chính sau đây: Luận văn đã khảo sát những vấn đề chung về mạng ngang hàng, và vấn đề lập lịch cho mạng ngang hàng. Một số thuật toán lập lịch tối ưu đã được nghiên cứu và thực hiện đánh giá hiệu năng cho ba mô hình mạng cụ thể là: - Đối với mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM) luận văn đã khảo sát các thuật toán lập lịch tối ưu cho chunk, peer và chunk/peer phối hợp là LUc/ELp và DLc/ELp. Sau đó đã tiến hành mô phỏng đánh giá hiệu năng trễ (Delay) F trong trường hợp xấu nhất của hai thuật toán chunk/peer phối hợp là LUc/ELp và DLc/ELp. - Đối với mạng chồng phủ truyền tải dữ liệu DON (Data-driven Overlay Networks) luận văn đã khảo sát ba thuật toán lập lịch tối ưu là phương pháp đơn hình cho bài toán quy hoạch tuyến tính, phương pháp tìm luồng với chi phí nhỏ nhất và thuật toán phân phối Heuristic. Luận văn đã mô phỏng đánh giá tốc độ trung bình R(tb) chia sẻ các block trong mạng tương ứng các tốc độ dòng khác nhau. - Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live Streaming System) đã trình bày thuật toán xấp xỉ để giải quyết bài toán MADPS. Luận văn cũng đã phân tích, đánh giá chi tiết thuật toán lập lịch tối ưu bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời gian thực hiện chương trình.