Cơ hế multiast lớp ứng dụng đảm bảo hất lượng luồng video

96 Trang 6 DANH MỤC CÁC HÌNH VẼ26TUHình 1.1: Mạng ARPAnet năm 1969U26 T ...1126TUHình 1.2: Unicasting một bộ film đến 10000 người dùng.U26T ...1426TUHình 1.3: Multicasting một bộ film t

- 

-LUẬN VĂN THẠC SỸ KHOA HỌC

CƠ CHẾ MULTICAST LỚP ỨNG DỤNG ĐẢM BẢO

CHẤT LƯỢNG LUỒNG VIDEO

LỜI CAM ĐOAN

Tôi xin cam đoan, đây là luận văn nghiên cứu của riêng tôi Các số liệu, kết quả trong luận văn là trung thực và khách quan

Nguyễn Thị Thu Hà

MỤC LỤC

26TDANH MỤC CÁC HÌNH VẼ26 T 6

26TDANH MUC BẢNG BIỂU26 T 7

26TLỜI GIỚI THIỆU26 T 9

26TLỜI CẢM ƠN26T 10

26TCHƯƠNG 1: MỞ ĐẦU26T 11

26T1.1 Internet: quá khứ, hiện tại, tương lai26T 11

26T1.2 Multicasting lớp mạng (IP)26T 14

26T1.3 Multicasting lớp ứng dụng (AL)26T 17

26T1.4 Cơ sở và mục đích nghiên cứu của luận văn26 T 18

26T1.5 Tổ chức luận văn26T 19

26TCHƯƠNG 2: TỔNG QUAN CÁC GIAO THỨC MULTICAST LỚP ỨNG DỤNG26T 20

26T2.1 Multicast theo lưới (mesh-based) 2126 T 26T2.1.1 Narada 2126T 26T2.1.2 ScatterCast26T 24

26T2.2 Multicast theo cây (tree-based) 2526 T 26T2.2.1 Giao thức cây chuối – BTP (Banana Tree Protocol)26T 25

26T2.2.2 Giao thức HMTP (Host Multicast Tree Protocol)26T 27

26T2.2.3 YOID 2926T 26T2.2.4 ALMI26T 30

26T2.2.5 Overcast26T 31

26T2.2.6 Giao thức điều khiển xây dựng cây overlay – TBCP (Tree Building Control Protocol)26T 32

26T2.2.7 So sánh giao thức dựa theo lưới (mesh based) và dựa theo cây (tree based)26T 33

26T2.3 Multicast ở lớp đỉnh của mạng overlay có cấu trúc P2P26 T 34

26T2.3.1 Multicast theo CAN – MCAN26 T 37

26T2.3.2 SCRIBE 4026T 26T2.3.3 Pastry26T 41

2.3.4 Bayeux 42

26T2.3.5 Giao thức tam điểm Delauny26T 43

26T2.3.6 HyperCast26T 46

26T2.4 Multicast phân cấp26T 48

26T2.4.1 Kudos26 T 48

26T2.4.2 NICE 5026T 26T2.5 Kết luận26 T 52

26T2.5.1 Hiệu quả26T 52

26T2.5.2 Tính mềm dẻo26T 52

26TCHƯƠNG 3: ĐỊNH TUYẾN MULTICAST VÀ PHÂN PHỐI BĂNG THÔNG TRONG CÁC MẠNG OVERLAY26T 54

26T3.1 Cơ sở26T 54

26T3.2 Mục đích thiết kế và xác định bài toán26 T 58

26T3.3 Các thuật toán định tuyến multicast26T 61

26T3.3.1 Thuật toán cây rút gọn (Copact Tree Algorithm)26 T 61

26T3.3.2 Thuật toán cây rút gọn cân bằng (Balanced Compact Tree Algorithm)26T 64

26T3.3.3 Cấp phát bậc cân bằng – BDA (Balanced Degree Allocation)26T 64

26T3.4 Định cỡ băng thông26T 68

26T3.4.1 Định cỡ ranh giới (baseline)26T 68

26T3.4.2 Định cỡ lặp26 T 70

26T3.5 Đánh giá các thuật toán định tuyến26T 71

26T3.5.1 Thiết lập mô phỏng26 T 71

26T3.5.2 So sánh các kỹ thuật xây dựng cây26T 72

26T3.5.3 Đánh giá hiệu suất – Tỉ lệ loại bỏ phiên26 T 76

26T3.5.4 Đánh giá hiệu suất – Đường kính cây26 T 78

26T3.5.5 Độ phức tạp của thuật toán ICT26 T 79

26T3.6 Nguyên lý kết hợp thuật toán CP và CT26T 80

26T3.7 KẾT LUẬN26T 81

26TCHƯƠNG 4: ỨNG DỤNG MULTICAST LỚP ỨNG DỤNG ĐỂ TRUYỀN VoD26T 82

26T4.1 Cơ sở nghiên cứu26 T 82

4.2 Phát biểu bàitoán 84

26T4.3 Giải quyết bài toán26T 85

26T4.3.1 Sắp xếp các client26T 86

26T4.3.2 Các hoạt động giao thức26 T 87

26T4.3.2.1 Giai đoạn nhập mạng26T 87

26T4.3.2.2 Giai đoạn làm việc26T 89

26T4.3.2.3 Giai đoạn rời mạng26T 89

26T4.3.2.4 Các nút mồ côi và khôi phục26 T 90

26T4.3.2.5 Khả năng xác định lỗi của client26 T 91

26T4.3.3 Phân tích – Các kết quả thực nghiệm26T 92

26TKẾT LUẬN26T 96

26TKết quả đạt được và ứng dụng của luận văn26T 96

26THướng phát triển nghiên cứu26T 96

DANH MỤC CÁC HÌNH VẼ

26TUHình 1.1: Mạng ARPAnet năm 1969U26 T 11

26TUHình 1.2: Unicasting một bộ film đến 10000 người dùng.U26T 14

26TUHình 1.3: Multicasting một bộ film tới 10000 người dùngU26T 14

26TUHình 1.4: Mạng overlay và hạ tầng lớp mạng với 5 người dùng cuối (end -user).U26T 18

26TUHình 2.1: Giao thức NaradaU26T 22

26TUHình 2.2: Tối ưu hoá cây BTP: chuyển sang nút cha khácU26T 25

26TUHình 2.3: (a) Vòng lặp trong BTP: chuyển đồng thời, (b) Vòng lặp trong BTP: thông tin lỗi thờiU26 T 27

26TUHình 2.4: Thủ tục gia nhập HMTP .28U26T 26TUHình 2.5: Cơ chế gia nhập TBCP: đánh giá cấu hình nội hạtU26T 33

26TUHình 2.6: Minh hoạ mạng overlay CAN hai chiềuU26 T 37

26TUHình 2.7: Thuật toán chuyển tiếp multicast từ nút gốc trong CANU 26T 40

26TUHình 2.8: Tập nút lá và bảng định tuyến trong mạng Pastry cho NodeID = 12030321U26 T 42

26TUHình 2.9: Định tuyến trong mạng PastryU26T 43

26TUHình 2.10: Tam điểm Delaunay (DelaunayTriangulation)U26T 45

26TUHình 2.11: Thuộc tính đẳng giác cục bộU26 T 45

26TUHình 2.12: Định tuyến compassU26T 45

26TUHình 2.13: Cấu trúc siêu lập thể - hypercubeU 26T 47

26TUHình 2.14: Cây với nút gốc 000 được nhúng trong một siêu lập thể chưa hoàn chỉnhU26T 48

26TUHình 2.15: Phân cấp hai lớp trong KudosU26 T 49

26TUHình 2.16: Cấu trúc phân cấp NICE và tạo cụm (clustering)U26T 50

26TUHình 3.1 Kiến trúc dịch vụ multicast sử dụng mạng OverlayU26T 55

Hình 3.2 Minh hoạ thuật toán cây rút gọn 62

26TUHình 3.3: Thuật toán cây thu gọn cho MDDLU26T 63

26TUHình 3.4: Cấp phát bậc cân bằngU26T 65

26TUHình 3.5: Minh hoạ thuật toán ICT và điều chỉnh bậcU26T 68

26TUHình 3.6: Định cỡ băng thông truy nhập Server [24]U26T 70

26TUHình 3.7: Ba cấu hình mạng Overlay [24]U26T 72

26TUHình 3.8: Độ nhậy về giới hạn đường kính [24]U26T 73

26TUHình 3.9: Độ nhậy đối với vòng điều chỉnh bậc [24]U26T 74

26TUHình 3.10: So sánh tỉ lệ loại bỏ phiên [24]U26T 75

26TUHình 3.11: Hiệu suất trễ end- -to endU26 T 78

26TUHình 3.12: Độ phức tạp của thuật toán ICT [24]U26T 79

26TUHình 3.13: Hiệu suất của thuật toán kết hợp CP và CTU26T 81

26TUHình 4.1: Cấu trúc phân cấp trong ALMU26T 86

26TUHình 4.2: Các nút mô côi và khôi phụcU26 T 91

26TUHình 4.3: Xác suất bị lỗi hàng loạt [26]U26T 94

DANH MUC BẢNG BIỂU 26TUBảng 1.1: Số liệu thống kê sử dụng Internet 03/02/2005U 26T 12

26TUBảng 2.1: So sánh mã nhị phân và mã GrayU26T 46

THUẬT NGỮ VIẾT TẮT

AL Application Layer Lớp ứng dụng

ALMI Application Level Multicast Infrastructure Kiến trúc Multicast tầng ứng dụng

ASM Any Source Multicast Multicast với nút nguồn bất kỳ

BGMP Border Gateway Multicast Protocol Giao thức Multicast cho Gateway đường biên BGP Border Gateway Protocol Giao thức Gateway đường biên

BTP Banana Tree Protocol Giao thức cây chuối

CAIDA Cooperative Association for Internet Data Analysis Hiệp hội hợp tác phân tích dữ liệu Internet CAN Content Addressable Network Mạng đánh đánh địa chỉ nội dung

DHT Distributed Hash Table Bảng Hash phân tập

DIS Distributed Interactive Simulations Mô phỏng tương tác phân tập

DT Delaunay Triangulation Tam điểm Delaunay

DVMRP Distance Vector Multicast Routing Protocol Giao thức định tuyến Multicast vectorkhoảng cách

HMTP Host Multicast Tree Protocol Giao thức cây Multicast cho host

HTML Hyper-Text Markup Language Ngôn ngữ đánh dấu siêu văn bản

ICMP Internet Control Message Protocol Giao thức bản tin điều khiển Internet

IGMP Internet Group Membership Protocol Giao thức thành viên nhóm Internet

IP Internet Protocol Giao thức Internet

ISP Internet Service Provider Nhà cung cấp dịch vụ Internet

MBGP Multiprotocol Border Gateway Protocol Giao thức cho các Gateway đường biên sử dụng nhiều loại giao thức.MBone Multicast Backbone Xương sống Multicast

MCAN CAN-based multicast Multicast dựa trên CAN

MSDP Multicast Source Discovery Protocol Giao thức phát hiện nút nguồn multicast MST Minimum Spanning Tree Cây bao trùm

NCP Network Communication Protocol Giao thức truyền thông mạng

NICE NICE is the Internet Cooperative Environment Môi trường hợp tác Internet

p2p Peer to Peer Mạng ngang hàng (điểm – tới – điểm)

pdf Probability density function Hàm phân bố xác suất

PIM- DM Protocol Independent Multicast- Dense Mode Multicast độc lập giáo thức – chế độ đông đúcPIM-SM Protocol Independent Multicast- Sparse Mode Multicast độc lập giao thức chế độ thưa thớt – RFC Request for Comments Công bố chính thức của mạng Internet

RGU Random Graph with uniformly distributed link weights Đồ thị ngẫu nhiên với các trọng số đường liên kết phân bố đều

RP Rendezvous Point Điểm “gặp gỡ”

RPF Reverse Path Forwarding Chuyển tiếp đường lùi

rtt round trip time Thời gian đường vòng

SCX Scattercast Proxies Các proxy trong giao thức Scattercast

SMT Steiner Minimum Tree Cây tối thiểu Steiner

SPT Shortest Path Tree Cây đường đi ngắn nhất

SSM Source Specific Multicast Multicast có nút nguồn là nút gốc

TBCP Tree Building Control Protocol Giao thức xây dựng cây

TCP Transmission Control Protocol Giao thức điều khiển đường truyền

TTL Time to Live Thời gian tồn tại

URT Uniform Recursive Tree Cây đệ quy đồng đều

VLAN Virtual Local Area Network Mạng nội hạt ảo

LỜI GIỚI THIỆU

Trong quá trình triển khai multicast tầng mạng (IP), một hướng tiếp cận mới đã được đề xuất để thực hiện các dịch vụ multicast diện rộng đó là multicast tầng ứng dụng Trong cách tiếp cận này, chức năng multicast được thực hiện ở các host kết cuối thay vì ở các bộ định tuyến Không như multicast lớp mạng, multicast lớp ứng dụng không cần hỗ trợ cơ sở hạ tầng mà vẫn có thể

dễ dàng triển khai trên mạng Internet

Trong luận văn, tác giả đã trình bầy một số các giao thức multicast tầng ứng dụng chính được đề xuất gần đây, phân loại chúng và đánh giá hiệu suất cũng như khả năng áp dụng các giao thức này

Luận văn cũng trình bầy các bài toán định tuyến trong mạng overlay và các bài toán liên quan đến ấn định băng thông cho việc hoạch định mạng

Cuối cùng luận văn trình bầy một giao thức tầng mạng ứng dụng cho các ứng dụng luồng dữ liệu băng thông thấp với số lượng lớn người thu Kỹ thuật này dựa trên một phân cấp điều khiển của các cấu hình siêu lập thể cho các nút mạng ngang hàng

LỜI CẢM ƠN

Đề tài Cơ chế multicast lớp ứng dụng đảm bảo chất lượng luồng video

được tôi lựa chọn làm luận văn tốt nghiệp cao học của mình Trong quá trình tìm hiểu và nghiên cứu, tôi thấy đây là một đề tài còn rất mới và khó Tuy nhiên được sự hướng dẫn, chỉ bảo của thầy cô; sự động viên, giúp đỡ, tạo điều kiện của gia đình, bạn bè và đồng nghiệp, tôi đã hoàn thành bản luận văn này

Nhân đây, tôi xin bày tỏ lòng biết ơn sâu sắc đến TS Nguyễn Hữu Thanh, người đã luôn hướng dẫn, giúp đỡ tôi trong quá trình hoàn thành luận

văn này

bày Tôi cũng xin tỏ lòng biết ơn đến các thầy cô trong Khoa Điện Tử Viễn Thông, các thầy cô tại Trung tâm đào tạo sau đại học trường Đại Học Bách Khoa Hà Nội đã giảng dạy kiến thức và giúp đỡ tôi trong suốt quá trình học tập tại trường

Tôi cũng xin bày tỏ lòng biết ơn sâu sắc tới bố mẹ, gia đình; bạn bè và các đồng nghiệp tại Trung tâm CNTT – Ngân hàng Công Thương đã giúp đỡ, tạo điều kiện cho tôi trong suốt quá trình hoàn thành luận văn này

CHƯƠNG 1: MỞ ĐẦU

1.1 Internet: quá khứ, hiện tại, tương lai

Từ trước đến nay có rất ít các công nghệ ảnh hưởng đến xã hội như Internet Mạng Internet – mạng của các mạng với cấu trúc rất phức tạp gồm các

bộ định tuyến kết nối với nhau có nguồn gốc từ thập kỷ thứ 7 của thế kỷ trước Năm 1963, viễn cảnh của một mạng có thể kết nối các máy tính và con người trên toàn cầu lần đầu tiên được lắp ghép bởi JCR Licklider – trưởng bộ phận

nghiên cứu máy tính thuộc Ban dự án nghiên cứu cao cấp (ARPA) Giữa những

năm 1990, ARPA nhận thấy nhu cầu cần thiết phải kết nối các trường đại học và

các trung tâm nghiên cứu thuộc chính phủ thành một mạng quốc gia để cho phép một số lượng lớn các máy tính có thể trao đổi thông tin và chia sẻ tài nguyên Đến cuối năm 1969, mạng ARPAnet đầu tiên gồm 4 máy tính kết nối

với nhau như hình 1.1 Mạng ARPAnet được xem là cơ sở nền tảng ra đời mạng

Internet

Hình 1.1: Mạng ARPAnet năm 1969

Lúc đầu chỉ có các trường đại học và các tổ chức nghiên cứu tham gia vào mạng này để trao đổi thông tin Tuy nhiên, để có mạng Internet ngày nay

năm 1973, giao thức truyền thông NCP được thay thế bằng một cặp giao thức truyền thông mới TCP/IP Năm 1978, giao thức TCP/IP được chính phủ Mỹ chấp nhận và trở thành chuẩn truyền thông mạng vào năm 1983.

Những năm 1980, càng có nhiều mạng xuất hiện Ngay cả các tổ chức thương mại và giáo dục cũng muốn cùng sử dụng các công nghệ chuyển mạch gói Chính trong giai đoạn này, hệ thống được biết đến với cái tên mạng : Internet như ngày nay Hệ thống này đã vượt qua mục đích ban đầu của nó và trở thành đòn bẩy cho một cuộ cách mạng công nghệ rộng lớn.c

Trước khi mạng Internet có các chức năng như một công cụ thông tin toàn cầu nó còn có những thay đổi phụ khác Đó là vào năm 1989, dự án

“World Wide Web” cùng với ngôn ngữ đánh dấu siêu văn bản HTML được đề

xuất Những năm tiếp theo, các công cụ đơn giản đề nhận và truyền thông tin từ

trang Web dành được nhiều sự quan tâm Mùa xuân năm 1993, một nhóm kỹ sư

tốt nghiệp tại trường Illinois đã sáng tạo ra một trình duyệt – “browser” gọi là Mosaic Sau đó Netscape và Microsoft đã xây dựng các trình duyệt đơn giản đểtìm kiếm thông tin trên Internet

Ngày nay, Internet đã phát triển thành một công nghệ có chi phí thấp và

là cánh cửa dồi dào thông tin, tri thức và đang từng phút từng giây thay đổi thế giới Người ta hoàn toàn có thể sử dụng Internet tại nhà, công sở, trường học, thư viện và cả các quán café Bảng 1.1 dưới đây dẫn chứng số liệu thống kê sự thâm nhập của Internet (nguồn http://www.internetworldstats.com/stats.htm)

Bảng 1.1: Số liệu thống kê sử dụng Internet 03/02/2005

Làm thế nào các máy tính của mạng Internet trao đổi với nhau? Chúng trao đổi với nhau bằng các gói tin mang các thông tin cần trao đổi Mạng Internet như chúng ta biết ngày nay là dựa trên kiểu truyền thông unicast (point – – point) to Trong phương pháp unicast, gói tin được truyền qua mạng từ điểm nguồn đến điểm đích theo từng bước truyền (hop – by – hop) Nghĩa là

mỗi bộ định tuyến trên đường đi từ nguồn đến đích chọn bộ định tuyến kế tiếp cho một gói tin biết trước sao cho số bước truyền là nhỏ nhất Phương pháp này được thực hiện bằng thuật toán đường đi ngắn nhất Hầu hết các ứng dụng IP

truyền thống như duyệt Web, e-mai đều sử dụng unicast Bất cứ khi nào người

dùng chỉ cần duyệt các trang Web khác nhau, nhận các bản tin cụ thể thì chỉ cần unicast

Những năm gần đây, chúng ta đã chứng kiến sự phát triển của các ứng dụng đa phương tiện với sự tham gia đồng thời của một số người dùng Những

ứng dụng gồm các kiểu truyền: một – nhiều, nhiều nhiều Các ứng dụng một – – nhiều (one – – many) to chỉ có một người gửi nhiều người nhận đồng thời Các ứng dụng này gồm: phân phối audio/video theo lịch, push media, phân bổ file

và caching Trong các ứng dụng nhiều nhiều – (many – – many) to , có hơn 2 người nhận đồng thời cũng là người gửi Một số ứng dụng của kiểu truyền này là: hội nghị truyền hình, xử lý đồng thời, mô phỏng tương tác phân tập (DIS – distributed interactive simulations), game tương tác nhiều người chơi, đào tạo

từ xa, …

Hầu hết các ứng dùng này không thể chạy trên mạng Internet ngày nay

do nó cần băng thông rộng Để minh hoạ điều này, chúng ta giả định một máy

server cung cấp video muốn truyền một bộ film theo kiểu unicast đến 10000 người xem (hình 1.2) Máy chủ này cần 10000 kết nối điểm – điểm riêng biệt

và gửi 10000 bản copy của bộ film trên mạng Phương pháp như vậy là rất lãng phí dung lượng mạng Hơn nữa, nó cũng làm lãng phí dung lượng của máy chủ

Hình 1.2: Unicasting một bộ film đến 1000 0 người dùng

1.2 Multicasting lớp mạng (IP)

Hình 1.3: Multicasting một bộ film tới 1000 0 người dùng

Nhờ sử dụng truyền thông multicast mà việc triển khai các ứng dụng đa phương tiện đã dễ dàng đi rất nhiều Khi trên đường truyền có sự chồng chéo của các gói tin cùng nội dung thì chỉ một bản sao của gói tin được gửi trên mạng qua đường truyền đó Nếu các đường chuyển hướng, các gói tin sẽ được sao chép trong bộ định tuyến và gửi đến các đường liên kết (link) thích hợp

Như hình 1.3 minh hoạ, mỗi gói tin được sao chép trong mạng chỉ khi cần

Lợi ích của việc sử dụng multicast là gấp đôi Multicast giảm tải cho

server do server chỉ phải gửi duy nhất một gói tin trên mỗi đường liên kết thay

vì gừi nhiều gói tin tới các người nhận khác nhau Ngoài ra, nó còn giảm tải tổng do chỉ có duy nhất một bản copy của gói tin được truyền bất cứ nơi đâu có thể Điều này giảm đáng kể tiêu hao băng thông toàn màng như minh hoạ trong hình 1.2 và 1.3

Mô hình multicast chuẩn được đưa ra bởi Steven Deering vào năm 1988

Mô hình multicast lớp mạng (IP) mà Deering đề xuất dựa trên một khái niệm nhóm: các host mà tham gia một ứng dụng cụ thể gọi là nhóm multicast Mỗi

nhóm multicast được nhận dạng bởi một địa chỉ multicast đặc biệt lớp D Để

nhận dữ liệu từ một nhóm multicast, các host phải tham gia vào nhóm bằng cách liên hệ với bộ định tuyến mà nó gắn với, sử dụng giao thức quản lý nhóm Internet phiên bản 3 (IGMPv3) Mỗi lần một host tham gia vào một nhóm, nó

nhận được tất cả dữ liệu được gửi tới địa chỉ nhóm không kể địa chỉ gốc của nút gửi Các host có thể gửi tới một nhóm multicast mà không cần trở thành

một nút nhận; đó là các host mà được gọi là các nút gửi không phải là thành viên

Trong multicast lớp IP, khi một thành viên muốn gia nhập hay rời khỏi nhóm, nó thông tin tới bộ định tuyến multicast được chỉ định trong cùng

subnet, sau đó các bộ định tuyến multicast tham gia sẽ thay đổi thông tin thành

viên nhóm và sử dụng các giao thức định tuyến multicast để thiết lập các cây phân phối dữ liệu

Mô hình nhóm multicast lớp IP là một mô hình dịch vụ mở Không có cơ chế nào hạn chế các host hoặc người dùng trong việc tạo ra một nhóm multicast, nhận dữ liệu từ một nhóm, hoặc gửi dữ liệu cho một nhóm Nhiều người gửi có thể chia sẻ cùng địa chỉ multicast Những người gửi không thể dự trữ địa chỉ hoặc ngăn lại các nút gửi khác chọn cùng địa chỉ Khái niệm thành viên nhóm là khái niệm chỉ khả năng đi đến của nút nhận và không có ý định cung cấp bất kỳ quyền truy nhập nào Như vậy rất khó quản lý một nhóm multicast lớp IP.

- Bài toán định tuyến multicast làm thế nào tìm được một đường đi tối ưu (đường đi ngắn nhất) phức tạp hơn unicast Để thực hiện multicast, tất cả các nút thuộc nhóm multicast phải được kết nối với nhau bằng một cây (server

được kết nối với tất cả các user từ 1 – 10000 trong hình 1.3) Một cây như vậy

gợi là cây multicast và được minh hoạ như hình 1.3 Các gói tin multicast được chuyển đi theo cây đó từ nút gửi đến tất cả thành viên của nhóm multicast

Một số cách tiếp cận đã được chấp nhận để xác định cây multicast Cách đơn giản nhất để xây dựng một cây định tuyến là cứ lúc nào thêm một nút tham gia thì sử dụng thuật toán đường đi ngắn nhất Các nút mới tham gia được kết nối theo đường đi ngắn nhất tới nút gần nhất trong cây Trong khi cây đường

đ gắn hất i n n giữa nút nguồn và mỗi nút đích đảm bảo rằng các gói tin multicast

sẽ được phân phối nhanh nhất có thể, thì cũng không cần phải đem lại kết quả

là một cây tiết kiệm được tài nguyên mạng Cách tiếp cận thứ hai là xây dựng một cây đơn để phân bổ lưu lượng từ tất cả nút gửi trong nhớm, không kể vị trí của nút gửi, và tối ưu trọng số tổng của cây Do đó nó tối ưu được việc sử dụng tài nguyên mạng Bài toán tìm cây trọng số nhỏ nhất được biết đến là bải toán

rộng rãi của nó (bảo mật, cấp phát địa chỉ mềm dẻo, ổn định, hạ tầng, quản lý) Trong những năm qua, những vấn đề trên đã được nghiên cứu và có m số giải ột pháp đã được đề xuất đó là multicast lớp ứng dụng Ở đây các nút thực tạo thành các mạng ảo và các cấu trúc phân phát multicast được xây dựng trên mạng ảo này, các gói dữ liệu được tái tạo ở các nút tham gia và được phân phát trên các đường hầm

1.3 Multicasting lớp ứng dụng (AL)

Phương pháp hiệu quả nhất để cung cấp dịch vụ multicast là thực hiện nó trong lớp mạng như đã nói ở phần trên Tuy nhiên, sự triển khai chậm của multicast lớp IP và nhu cầu ngày càng tăng các ứng dụng đa người dùng đã thúc đẩy sự ra đời multicast lớp ứng dụng (AL) Ở multicast lớp ứng dụng, việc

sao chép gói tin và định tuyến được xử lý bởi các host kết cuối (end-host) thay

vì ở các bộ định tuyến mạng như trong trường hợp multicast lớp IP Các host kết cuối tạo thành một mạng overlay, trong đó mỗi link của mạng overlay tương ứng với một đường unicast trực tiếp giữa hai thành viên nhóm Tất cả các gói dữ liệu được gửi như các gói unicast và được chuyển tiếp từ một thành viên trong mạng overlay đến thành viên khác theo một số qui tắc định sẵn Khái niệm multicasting lớp ứng dụng được minh hoạ trong hình 1.4 Cây multicast được minh hoạ bằng các đường nét đậm Các gói tin theo các đường unicast ở mạng hạ tầng được minh hoạ bằng các đường mũi tên

Như trong hình 1.4 chúng ta thấy, multicast lớp ứng dụng không yêu cầu

hỗ trợ hoặc thay đổi về cơ sở hạ tầng Phương pháp này cho phép khả năng triển khai nhanh và thông suốt của các ứng dụng multicast Phương pháp này cũng cho thấy nếu multicast lớp ứng dụng được triển khai rộng khắp, nó có thể nâng cao khả năng tạo ra các ứng dụng multicast và thúc đẩy sự triển khai multicast lớp IP

Hình 1.4: Mạng overlay và hạ tầng lớp mạng với 5 người dùng cuối (end - user)

1.4 Cơ sở và mục đích nghiên cứu của luận văn

Multicast lớp ứng dụng ra đời như là giải pháp tình thế cho các vấn đề triển khai multicast lớp mạng (IP) So với multicast lớp IP, multicast lớp ứng dụng có độ phức tạp thấp hơn nhưng cũng phải trả giá về hiệu quả bởi các gói tin trong multicast lớp ứng dụng có thể đi trên cùng một đường kết nối (link)

một số lần (hình 1.4) Multicast lớp ứng dụng chỉ có ý nghĩa khi nó vượt trội so với unicast Do vậy cần phải đánh giá được multicast lớp ứng dụng hiệu quả như thế nào? Tất cả các thuật toán multicast lớp ứng dụng được đề xuất phải hiệu quả hơn unicast Trong hầu hết các trường hợp, các thuật toán khác nhau khó có thể so sánh với nhau ở cùng các điều kiện như nhau, nhưng hiểu được hiệu suất (performance) của từng giao thức multicast sẽ giúp chúng ta tối ưu và

cải tiến được chúng

Một vấn đề quan trọng khác trong việc định tuyến lớp ứng dụng đó là chất lượng phối hợp giữa mạng overlay và cấu trúc mạng hạ tầng Bởi các nút

cuối không lấy thông tin topo có sẵn ở các bộ định tuyến nên khi kết nối chúng với nhau thành mạng overlay, chúng thường không có thông tin cấu trúc hình học của mạng Điều này dẫn đến tình trạng là hai nút lân cận trong mạng overlay có thể cách nhau bởi rất nhiều bước truyền (hop) ở lớp mạng (IP) và do

đó tạo ra trễ cao và lưu lượng không cần thiết Hiệu suất của mạng overlay (nhìn từ khía cạnh độ trễ và số bản tin lặp không cần thiết) có thể được cải thiện nếu kết nối giữa các nút ở mạng overlay đồng dạng với kết nối ở mạng hạ tầng

Với những cơ sở như trên, mục đích của luận văn là: đánh giá hiệu quả của các thuật toán multicast lớp ứng dụng; đánh giá ảnh hưởng cấu trúc hình học (topology) đến hiệu quả của các thuật toán multicast lớp ứng dụng; ứng dụng multicast lớp ứng dụng truyền luồng dữ liệu đa phương tiện (VoD, video streaming,…) trên mạng

1.5 Tổ chức luận văn

Luận văn gồm 4 chương:

Chương 1: Mở đầu – Giới thiệu và mô tả về các phương pháp truyền thông multicast cũng như cở sở và mục đích nghiên cứu của luận văn

Chương 2: Tổng quan các giao thức multicast lớp ứng dụng Trình bầy – phân loại và tổng quan 17 giao thức multicast lớp ứng dụng, đánh giá khả năng mềm dẻo và hiệu quả của các giao thức

Chương 3: Trình bầy về định tuyến multicast mạng và phân phối băng thông trong các mạng overlay Trong chương này, chúng ta trình bầy một số thuật toán định tuyến multicast điển hình cho mạng overlay và tập trung vào việc tối ưu băng thông giao diện tại các nút dịch vụ multicast

Chương 4: Trình bầy một hướng ứng dụng ulticast lớp ứng dụng trong mtruyền video theo yêu cầu (VoD)

Phần kết luận nêu kết quả đạt được, ứng dụng của luận văn đồng thời đưa ra hướng nghiên cứu tương lai của tác giả

CHƯƠNG 2: TỔ NG QUAN CÁC GIAO THỨC

MULTICAST LỚP ỨNG DỤNG

Multicast ở lớp ứng dụng (AL) với các đặc tính như: thành viên nhóm

(membership), lặp gói tin và định tuyến multicast được thực hiện ở các máy

chủ kết cuối (end-host) chứ không phải là tại các bộ định tuyến mạng (network router) Máy chủ kết cuối thường không sẵn có thông tin định tuyến cho bộ

định tuyến, thay vào đó chúng dựa vào các bản tin đo đạc end- -end to để nhận định mạng và dựa vào đó để xây dựng cây phân phối multicast giữa các máy chủ kết cuối

Tất cả các giao thức multicast lớp ứng dụng tổ chức các thành viên nhóm thành hai loại kiến trúc liên mạng (topology): topo điều khiển (control topology) và topo dữ liệu (data topology) Các thành viên ngang hàng nhau

trong topo điều khiển thì trao đổi định kỳ các bản tin làm mới (refresh message) đề nhận dạng và kiểm soát lại sự rời nhóm (mà không thông báo) của

thành viên nhóm Topo dữ liệu thường là một tập con của topo điều khiển và có chức năng xác định đường đi để một gói tin multicast được truyền đi trong mạng overlay Trong thực tế, topo dữ liệu có cấu trúc dạng cây còn topo điều

khiển là để đảm bảo sự kết nối chặt chẽ giữa các thành viên với nhau Với ý nghĩa như vậy, topo điều khiển được gọi là lưới (mesh) còn topo dữ liệu được gọi là một cây (tree)

Các phương pháp multicast lớp ứng dụng được phân loại theo nhiều cách khác nhau Một tiêu chí đó là dựa trên nút mạng overlay được lựa chọn như thế

nào Theo tiêu chí này, hai giao thức có thể được phân loại thành: cách tiếp cận với các nút (no de) cố định và cách tiếp cận với các nút động Trong cách tiếp cận với nút cố định, các nút tạo thành cây multicast và được đặt một cách chiến lược trên mạng Internet tổng thể Ưu điểm của cách này là do sử dụng các nút

cố định nên cây multicast hoạt động ổn định Tuy nhiên dịch vụ multicast sẽ

không linh động và vẫn cần sự hỗ trợ từ phía nhà cung cấp dịch vụ Internet

(Internet Service Provider - ISP Ngoài ra, những nút cố định này có thể tạo )

thành hiện tượng nút cổ chai (bottleneck) Trong khi đó với cách tiếp cận dựa

trên nút động, các thành viên của nhóm tự tổ chức thành một cây multicast và

tự cải tiến một cách định kỳ Một tiêu chí phân loại khác nữa đó là dựa vào thuật toán xây dựng mạng overlay là tập trung (centralized) hay phân tập

(distributed)

Phần dưới đây chúng ta đề cập cách tiếp cận phân loại các giao thức multicast lớp AL dựa trên kiểu topo được tạo thành để truyền thông giữa các

máy chủ kết cuối (end-host) Theo tiêu chí này, chúng ta có thể phân thành 4

loại chính: kiểu lưới (mesh based) , kiểu cây (tree based) , kiểu multicast ở lớp trên cùng của mạng overlay có cấu trúc ngang hàng ( peer- - to peer ) , và kiểu multicast phân cấp Phần dưới sẽ trình bầy chi tiết từng loại.

Trong cách tiếp cận kiểu lưới, các nhóm nút trước tiên tự tổ chức thành một mạng lưới (messh topology) sao cho mỗi cặp nút có nhiều đường đi đến

nhau Tiếp theo, tạo cây với nút gốc là nút bất kỳ bằng cách chạy một vài cơ chế định tuyến multicast phổ biến như DVMRP[9] Chúng ta sẽ đi vào mô tả chi tiết Narada [10], giao thức điển hình nhất của phân loại này và Scattercast

[11]

2.1.1 Narada [10]

Mỗi thành viên trong nhóm hay mỗi nút trong mạng lưới giữ cho mình danh sách về trạng thái của tất cả các thành viên khác trong nhóm Một thành viên mới muốn gia nhập vào một nhóm nào đó thì trước hết cần có được danh sách các thành viên hiện thời của nhóm Nó sẽ nhận danh sách này từ nút được

ấn định như điểm “gặp gỡ” (Rendezvous point) với sự trợ giúp của giao thức BOOTP BOOTP ( là một giao thứ Internet c thể cung cấp thông tin cấu hc ó ình

mạng cho các tr m làm vi c không có a c ng hay các tr m làm vi c khác nếu ạ ệ đĩ ứ ạ ệ

cần thiết trong mạng c c bộụ Khi m t tr m làm vi c kh i đ ng, nó gởi thông ộ ạ ệ ở ộđiệp BOOTP lên m ng M t máạ ộ y dịch vụ BOOTP nhận thông điệp n y, lấà y thông tin cấu hình cho má íy t nh được thiết kế đ , v ởi lại n cho m y t nh ó à g ó á íLưu ý là hệ thống kh i đ ng không có a ch IP khi g i thông đi p ở ộ đị ỉ ở ệ BOOTP) Thành viên chỉ gia nhập thành công khi nó nhận được bản tin chấp nhận từ ít nhất là một thành viên nút Thành viên mới bắt đầu trao đổi các bản tin làm mới định kỳ với các nút lân cận (neighbor) trong lưới, cập nhật bảng thông tin

của các nút này Thông tin này tiếp tục được lan rộng hơn cho đến khi tất cả các thành viên của nhóm đều nhận được

Nếu một thành viên muốn rời nhóm, nó sẽ gửi bản tin rời nhóm tới tất cả các thành viên khác lân cận nó và dần dần gửi tới toàn nhóm

Cây phân phối dữ liệu multicast của giao thức Narada là kiểu cây mà bất kỳ

nút nào cũng được xem như là nút gốc (source-based) Cây phân phối này được

tính toán bởi các nút của mạng lưới bằng giao thức véctơ khoảng cách khác thay đổi Cây này được hình thành từ những đường đi ngắn nhất (shortest path)

của từng nút nhận với nút nguồn (giao thức DVMRP[9] C) ây dữ liệu dạng này được minh hoạ như ở Hình 2.1(a)

Hình 2 : 1 Giao thức Narada [10]

Một trong những mục tiêu thiết kế chính của giao thức Narada này là

tính bền vững (robustness) Trong trường hợp lỗi, ví dụ nút 2, khi đó nút 1,3,7

sẽ truy vấn nút 2 do chúng không nhận được ất kỳ bản làm mới nàob nào từ nút này Khi không có tín hiệu trả lời, nút 2 được xem như “đã chết” và các nút còn lại trong mạng lưới sẽ nhanh chóng được thông báo thông tin này Hậu quả sẽ

nghiêm trọng hơn khi nút 3 và 7 cùng bị lỗi, như chỉ ra ở hình 2.1(b) Các nút khác sẽ phát hiện ra sự chia cắt này bằng việc không thấy sự cập nhật thông tin

từ hai nút 3 và 7 đến các thành viên khác Mỗi thành viên sẽ giữ danh sách các nút thành viên mà nó không nhận được thông tin gì Mỗi thực thể trong danh sách sẽ được duy trì trong danh sách đó một khoảng thời gian nhất định Một cách định kỳ và với khả năng chắc chắn, mỗi nút mà đã phát hiện ra sự phân cách sẽ lựa chọn và thăm dò một trong số các nút có trong danh sách Nếu nó nhận được hồi đáp nó sẽ cố gắng tạo thêm đường liên kết tới nút đó và sửa chữa lại sự phân cách Nếu không như thế, nút được thăm dò sẽ coi như đã chết Giá trị của khả năng này phải được lựa chọn một cách cẩn thận để sao cho ngay cả khi có một số nút thành viên cùng cố gắng sửa chữa lại sự phân cách đồng thời thì cũng chỉ một số lượng nhỏ đường liên kết mới được tạo thêm

Do một vài nguyên nhân, mạng lưới xây dựng có thể không tối ưu: (1) sự lựa chọn các nút lân cận ban đầu là ngẫu nhiên, (2)các đường liên kết được tạo

ra trong quá trình sửa chữa sự phân cách chỉ cần thiết nhất thời nhưng sau đó trở nên không cần thiết, (3) quá trình tham gia/ rời bỏ mạng là động, (4) các trạng thái động của mạng hạ tầng Do các đường dẫn dữ liệu trong giao thức Narada là các cây bao trùm (spanning tree Giả – i thu t cây bao trùm Được ậ

dùng trong c c môi trường liên mạá ng để dò tìm và tách c c mẫu giao thông á

bằng c ch vô hiệu h a mộ ốá ó t s liên k t cế ụ thể Giao thức IEEE 801.2-D STP (spanning tree protocol) ngăn cấm vòng l p trong các c u d phòặ ầ ự ng bằng cách

d phòự ng cầu thứ ấp Nếu cầ ầ c u đ u tiên bị ắt, cầu thứ ấp sẽ thay thế của t c ) mạng lưới Do đó, Narada cho phép sự chọn lọc định kỳ mạng lưới bằng việc thêm hoặc ngắt một số kết nối Từng nút ước lượng giá trị và tính hữu dụng của các đường liên kết hiện có một cách định kỳ cũng như ước lượng giá trị và tính hữu dụng từ một đường liên kết tới một nút khác bất kỳ mà không phải là nút lân cận Trong ví dụ minh hoả ở hình 2.1(c), nút 9 muốn gia nhập hệ thống, nó chọn ngẫu nhiên 2 nút để tạo kết nối (ví dụ nút 1 và nút 8), trong hình vẽ này

(hop) khi nút 9 muốn giao tiếp với nút 6 và đây là đường liên kết hữu ích, còn

liên kết không hữu ích giữa 1 và 8 có thể được ngắt ra khỏi mạng lưới

2.1.2 ScatterCast [11]

ScatterCast [11] thuộc nhóm giao thức dựa trên các nút cố định: kiến trúc của nó bao gồm các ScatterCast Proxies (SCXs) dành riêng được đặt một cách chiến lược tại các nhóm dịch vụ Internet, thường là tại các điểm hiện diện POP

(point of perenc) của nhà cung cấp dịch vụ Internet (ISP)

Các proxy này (SCXs) sử dụng một giao thức gọi là Gossamer để tự tổ chức phân tập thành một cấu trúc lưới ỗi phiên multicast M sẽ tạo ra một mạng lưới mới Các nút mong muốn gia nhập, trước tiên phải bắt tay với một cụm dịch vụ (services cluster) gần nhất và gửi yêu cầu tới một SCX Cụm này sẽ thiết lập một SCX (nếu chưa có) và thông báo địa chỉ IP của mình tới nút mới Ngoài ra, nó sẽ gửi địa chỉ multicast cục bộ cốt để các thành viên mới có thể thông tin với một SCX khác thông qua địa chỉ unicast hoặc multicast cục bộnếu có thể Tương tự như Narada, các SCXs chạy giao thức véctơ khoảng cách

ở tầng trên cùng của mạng lưới để xây dựng một cây phân phối nguồn-gốc

(source- rooted có nút gốc là nút bất kỳ Trong quá trình tạo cây, có 2 yêu – )

cầu cần phải xem xét: bậc (dgree) của SCX là giới hạn do dải thông của nó và

độ trễ giữa nút nguồn và đích SCX là nhỏ nhất

Để cải thiện mạng lưới một cách định kỳ, các SCX dò từng proxy khác

và ước lượng giá trị (chi phí) của các đường liên kết tiềm năng so với giá trị của các đường liên kết đã tồn tại Giá trị của một đường được tính toán bằng tổng giá trị các đường tới tất cả các SCX nguồn Nếu giá trị của đường mới thấp hơn giá trị đường liên kết hiện tại thì đường hiện tại sẽ bị thay thế

Những sự phân cách trong mạng lưới sẽ được phát hiện và khắc phục bằng việc sử dụng điểm “hẹn” (Rendezvous) tập trung Một trong số các điểm như thế này sẽ được lựa chọn ngẫu nhiên để gửi bản tin làm mới (refresh message) trên mạng lưới Nếu bất kỳ một nút SCX nào dừng việc nhận những

bản tin này, nó sẽ bắt tay với điểm RP (Rendezvous point) đặc biệt và kết nối

lại mạng lưới Mặc dù vấn đề khắc phục lỗi phân cách được đơn giản hoá bằng việc sử dụng điểm tập trung, nhưng nó sẽ không khắc phục được trong trường hợp tất cả các điểm này thất bại

2.2 Multicast theo cây (tree-based)

Các giao thức thuộc nhóm này trực tiếp xây dựng lên cây phân phối dữ liệu một cách phân tập khác hẳn, với các giao thức dựa trên mạng lưới – các cây được xây dựng kiểu chia sẻ nhóm (group-shared) Các nút được tổ chức

bằng việc lựa chọn nút cha (parent) của mình trong cây Việc lựa chọn này là

cốt yếu cho hiệu suất và hiệu quả của cây Để nâng cao mạng overlay, một số giao thức trong nhóm này xây dựng một mạng lưới sau đó Các nút thành viên của nhóm kết nối với nhau trong một cây phát hiện ra một số thành viên khác

mà không phải là lân cận của mình trong cây thì thiết lập thêm các đường điều khiển tới các thành viên đó Các giao thức loại này khác nhau về thuật toán xây dựng cây

2.2.1 Giao thức cây chuối – BTP (Banana Tree Protocol) [27]

BTP có lẽ là giao thức đơn giản nhất của các giao thức lớp dựa theo cây

Hình 2.2: Tối ưu hoá cây BTP: chuyển sang nút cha khác

Một nút muốn gia nhập nhóm thu thập các thông tin từ một vài nút đã tồn tại trong nhóm bằng việc sử dụng cơ chế Bootstrap và chọn một trong số các nút

này làm nút cha của mình Nếu nút này là nút đầu tiên trong nhóm thì nó trở

thành nút gốc Cây được tối ưu hoá dần dần bằng việc thỉnh thoảng dịch chuyển sang nút cha khác. Sự thay đổi nút cha để giảm giá trị cây (tree cost)

hoặc độ trễ (latency) Việc dịch chuyển này có thể tới một nút anh em (lân cận, ngang hàng) hoặc nút ông bà nhưng không phải tuỳ tiện tới một nút bất kỳ như nút con cháu, để tránh tạo các vòng lặp Mỗi nút nhận danh sách các nút anh chị từ nút cha và kiểm tra kết nối đến để tìm ra một anh em gần hơn so với nút cha Trong trường hợp một nút anh em được tìm thấy, nút cần dịch sẽ gửi một yêu cầu dịch chuyển tới nút tìm thấy đó (Hình 2.2) Tại cùng thời điểm, sự thay đổi nút cha này ngăn bất kỳ nút anh em nào khác dịch chuyển tới nó, mặt khác vòng lặp và phân cách có thể hình thành như mô tả Hình 2.3(a) Ngoài ra, cũng phải đảm bảo rằng nút mà nó sắp chuyển đến vẫn là nút anh em của nó, để hạn chế tình trạng như trong trường hợp mô tả ở hình 2.3(b) Nút 1 và 3 là ví dụ đầu tiên là các nút anh em của nút 2 Tuy nhiên, do sự thay đổi về nút cha của chúng, thì không còn thêm trường hợp nào nữa tại thời điểm nút 2 quyết định thay đổi nút cha Do đó, tại thời điểm chuyển, nút chuyển phải lấy được thông tin về nút cha hiện thời

Hình 2.3: (a) Vòng lặp trong BTP: chuyển đồng thời, (b) Vòng lặp trong BTP: thông tin

lỗi thời

2.2.2 Giao thức HMTP (Host Multicast Tree Protocol) [28]

Trong giao thức HMTP một cây chia sẻ nhóm (group-shared) được xây

dựng Cây được xây dựng sao cho tối thiểu hoá các giá trị (chi phí) của đường liên kết và bậc tại mỗi nút được bảo đảm Cơ sở tối ưu là thời gian đi vòng từ thành viên này đến thành viên khác – rtt (round- trip time) Ngoài ra gần đây

người ta còn đề xuất cơ sở thứ hai trong tương lai đó là băng thông

(bandwidth) HMTP cũng không tạo ra một lưới điều khiển

Thủ tục gia nhập được mô tả tại Hình 2.4 Một thành viên muốn ra nhập

để bắt tay với nút gốc R và coi nó như nút cha, nút gốc R có danh sách các nút

con của mình (nút 1,2,3), dựa trên giá trị rtt (round- trip time) nó tìm các nút

-gần nhất tới nó giữa nút cha tiềm năng và các nút con của mình Nếu nút -gần nhất là nút cha tiềm năng, thành viên mới sẽ gửi yêu cầu gia nhập tới nút này (như nút R) Một nút cha tiềm năng chấp nhận thành viên mới này là con của

mình thì nó sẽ cung cấp số lượng các nút con nhỏ hơn Mặt khác, nút con gần nhất với nút cha tiềm năng sẽ trở thành một nút cha tiềm năng mới (nút 3) và toàn bộ quá trình được lặp lại như trên: thành viên mới thu thập danh sách các nút con của nút cha tiềm năng (trong ví dụ chỉ có nút 4) và tìm kiếm nút gần nhất giữa nút cha tiềm năng này với các nút con khác Bằng cách này các nút phía dưới của topo mạng sẽ được nhóm (clustered) lại với nhau

Hình 2.4: Thủ tục gia nhập HMTP

Cấu trúc cây này được duy trì bởi sự trao đổi định kỳ các bản tin làm mới

(refresh messages) của các nút cha đến các nút con Khi một nút muốn rời khỏi

cây, nó thông tin với nút cha và các nút con của mình, nút cha của nút muốn rời cây này sau đó sẽ xoá đơn thuần thông tin về nút đó trong danh sách các nút con của mình Các nút con của nút muốn rời cây này phải tìm kiếm nút cha mới Việc tìm kiêm một nút cha mới được thực hiện như cách gia nhập vào thủ tục (như trên)

Thủ tục phát hiện ngăn cách là tương tự như thủ tục rời cây của thành viên Sự vắng mặt của các bản tin làm mới chỉ ra cho các nút cha và các nút con việc các nút nào đó bị lỗi, do đó ngăn cách được phát hiện Khi phát hiện lỗi, nút cha của nút bị lỗi sẽ cập nhật thông tin về danh sách các nút con Các nút con sẽ kết nối lại với cây bằng cách cố gắng kết nối tới một số nút trong các đường dẫn gốc của mình

Tính động của mạng hạ tầng và mối quan hệ hội viên nhóm có thể làm giảm chất lượng của cây theo thời gian Cây có thể được cải tiến bởi các thành viên thay đổi nút cha Một thành viên thường bắt đầu một thủ tục gia nhập lai không phải từ nút gốc mà từ một nút được lựa chon ngẫu nhiên khác trong đường dẫn gốc của nó Ngoài ra, để tìm kiếm các nhánh khác cho một nút cha tiềm năng tốt hơn, một nút có thể chọn một nút tối ưu con cho một nút cha (không phải là nút gần nó nhất) Nếu tìm thấy một nút cha tốt hơn, nút sẽ chuyển sang nút cha đó.

Trong HMTP, không áp dụng thuật toán hạn chế vòng lặp (loop) Thay

vào đó thực hiện phát hiện và phân giải vòng lặp Một thành viên trong vòng lặp phát hiện ra vòng bằng cách tìm thấy chính nó trong đường dẫn gốc lặpKhi vòng lặp được phát hiện, thành viên trong vòng lặp sẽ rời nút cha hiện thời

và gia nhập vào cây và tìm kiếm một nút cha từ nút gốc trở đi

2.2.3 YOID [12]

YOID (Your Own Internet Distribution) [12] có thể là giao thức đầu tiên

trong nhóm giao thức cây Yoid xây dựng một cây chia ẻ nhóm, ở đó dữ liệu sđược phổ biến cho tất cả các thành viên Tuy nhiên để tăng tính bền vững và ổn định, Yoid cũng xây dựng lên topo lưới điều khiển Các liên kết lưới thêm vào này được sự dụng để khôi phục sự phân cách cây

Khi một thành viên muốn gia nhập nhóm, nó liên hệ với một “điểm hẹn”– RP ( Rendezvous Point mà không nhất thiết phải là thành viên của nhóm RP )

này sẽ cung cấp cho thành viên mới một danh sách các thành viên hiện tại một cách ngẫu nhiên Trong trường hợp nút ra nhập này là thành viên đầu tiên của nhóm thì nó sẽ trở thành nút gốc Nếu không như vậy, nó sẽ lựa chọn một trong

số các thành viên trong danh sách làm nút cha của mình

Cơ chế xây dựng cây đơn giản này có thể dẫn đến một cấu trúc vòng lặp

và hiệu suất tồi Để tránh điều này, Yoid triển khai một cơ chế tránh vòng lặp đơn giản là: một nút sẽ từ chối yêu cầu gia nhập của các nút có trong danh sách

nút gốc Luật này sẽ ngăn hầu hết các vòng lặp nhưng không phải tất cả Nế u một vòng lặp xuất hiện nó sẽ được phát hiện theo cùng một cách là một nút tự tìm kiếm mình trong đường dẫn gốc có được từ nút cha của nó Để tránh tạo ra một cây mới một cách vội vàng khi một số nút đồng thời kết nối đến các nút

cha mới, thông tin được thêm vào đường dẫn gốc gọi là nhãn chuyển đổi (switchstamp) Mỗi lần một nút thay đổi nút cha, trong bản tin thông tin về

đường dẫn gốc đầu tiên nó nhận được từ nút cha mới, nhãn chuyển đổi của nút

đó được thiết lập ở mức cao hơn bất kỳ một nút nào trên đường dẫn gốc Trong một vòng lặp, một nút trong vòng với chỉ số nhãn chuyển đổi cao nhất sẽ chấm dứt vòng lặp bằng việc thay đổi nút cha

2.2.4 ALMI [13]

Giao thức ALMI [13] có thể là một trong những đề xuất đầu tiên về multicast tầng ứng dụng Nó thuộc cách tiếp cận nhóm tập trung Nhờ đặc tính tập trung, ALMI là giao thức ổn định duy nhất thích hợp các nhóm cỡ nhỏ (một vài chục nút) và các ứng dụng kiểu nhiều đến – – nhiều (many – – to many)

Trong giao thức ALMI, một phiên (hoặc nhóm) bao gồm bộ điều khiển phiên và các thành viên chính thức của phiên Bộ điều khiển phiên chịu trách nhiệm tính toán MST (Minimum Spanning Tree) bao trùm tất cả các nút trong

nhóm Cây này được sử dụng để phân phối dữ liệu ứng dụng ộ trễ Đ (latency)

giữa các thành viên được dùng làm cơ sở tối ưu Mỗi thành viên giám sát độ trễ của một tập các thành viên khác Bộ điều khiển nhận thông tin cập nhật từ các thành viên chứa thông tin độ trễ (latency data) và dựa vào thông tin này, cây sẽ định kỳ tính toán lại Sau đó, bộ điều khiển rao đổi vớit từng thành viên về nút cha và các nút con mới Các thành viên gia nhập vào một nhóm multicast trước hết liên lạc và gửi yêu cầu tới bộ điều khiển Bộ điều khiển sẽ trả lại nhận dạng

về nút cha để thành viên mới khởi tạo liên kết, và danh sách các nút con để chấp nhận yêu cầu kết nối

Cách tiếp cận này làm đơn giản hoá những khó khăn về định tuyến, do

đó cây sẽ không còn vòng lặp Tuy nhiên vòng lặp và phân cách cũng xuất hiện Một lý do cho sự xuất hiện này là thông tin cập nhật từ các thành viên bị trễ hoặc bị mất Một nguyên nhân khác có thể là sự phổ biến số lượng các phiên bản khác nhau của MST tới các thành viên Điều này có thế khắc phục bằng cách ấn định một số xác định mỗi phiên bản MST Các thành viên sẽ duy trì một cache (bản copy) của các số phiên bản khác nhau trong các bảng định tuyến và chỉ định tuyến các gói tin với các số phiên bản cây đã được chứa trong cache Nếu một gói tin mà phiên bản cây mới hơn được nhận, nút nhận sẽ đăng

ký lại với bộ điều khiển để nhận MST mới

2.2.5 Overcast [14]

Overcast [14] được thiết kế như một sự phối hợp multicast nguồn đơn với dải thông và không coi trễ là cơ sở tối ưu, và do đó nó không được dùngcho các ứng dụng tương tác Mục tiêu của cơ chế xây dựng cây là tối đa dải thông từ tất cả các nút tới gốc Giao thức này đặt thành viên mới xa nút gốc nhất có thể (trong một quá trình lặp) mà không làm giảm dải thông Một thành viên muốn gia nhập bắt đầu quá trình bằng việc liên lạc với gốc – nút cha tiềm năng Trong mỗi vòng lặp của quá trình, mỗi thành viên ước tính dải thông trực tiếp tới các nút cha tiềm năng thông qua các nút con của các nút cha tiềm năng

đó Dải thông được ước tính bằng cách đo thời gian tải 10Kb dữ liệu Nếu dải thông qua bất ký một nút con của nút cha tiềm năng này lớn hơn hoặc bằng dải thông trực tiếp tới gốc thì nút con liên quan đó sẽ trở thành nút cha tiềm năng

và một quá trình lặp mới lại bắt đầu Trái lại, nút cha tiềm năng trở thành nút cha của thành viên mới Khi có một vài nút con của nút cha tiềm năng mà thoả mãn tiêu chí về băng thông, nút con gần nhất (số bước truyền) tới nút mới (có được thông qua traceroute) được lựa chọn làm nút cha tiềm năng

Đôi khi các nút thành viên xác định dải thông tới các nút anh em, cha

mẹ, ông bà và chuyển đổi nút cha dựa trên kết quả ước tính

Mỗi thành viên gửi bản tin làm mới định kỳ cho nút cha của mình, nếu một nút cha không liên lạc được với nút con trong một thời gian nhất định thì nút cha đó coi như nút con và các thông tin liên quan đến nó đã “chết”

2.2.6 Giao thức điều khiển xây dựng cây overlay – TBCP [15] Tree Building Control Protocol)

TBCP [15] xây dựng các cây mà bắt buộc các nút trong cây đó xác định sẵn số nút con sẵn sàng hỗ trợ

Hình 2.5 mô tả thủ tục gia nhập trong giao thức TBCP Một nút mà là nút gửi chính (main sen der) của nhóm sẽ được lựa chọn làm nút gốc Tương tự như HMTP và Overcast, thành viên mới (nút 4) đầu tiên sẽ liên lạc với nút gốc (R) và nhận một danh sách các nút con của nó (1,2,3) Nút mới sẽ đo khoảng

cách (rrt) tới nút gốc và các nút con Sau đó nó gửi thông tin đo được về nút

gốc, nút gốc sẽ ước lượng tất cả các cấu hình có thể cho nút mới (hình 2.5) rồi

sẽ lựa chọn một mô hình tối ưu Nếu một nút được chấp nhận như là nút con của nút gốc (hình 5a) thì thủ tục gia nhập kết thúc 2 Ngoài ra, nếu nút mới 4 (hình 2.5b) hoặc bất kỳ nút con hiện tại nào của nút gốc (1,3) phải định hướng lại, nút đó sẽ bắt đầu lại quá trình nhập mạng nhưng bắt đầu từ nút nó định hướng đến

Hình 2.5: Cơ chế gia nhập TBCP: đánh giá cấu hình nội hạt

Đôi khi ngay cả các nút hiện có cũng có thể thực hiện thủ tục gia nhập để thay đổi chúng trong cây, do đó nâng cao hiệu suất của cây Hiệu suất của cây

có thể được cải thiện bằng cách sắp xếp phân cấp các thành viên vào trong các domain, mà mỗi domain này có nút gốc riêng của minh

Giao thức này không sử dụng cơ chế khôi phục lỗi

2.2.7 So sánh giao thức dựa theo lưới (mesh based) và dựa theo cây (tree based)

Phần này chúng ta sẽ tổng kết ưu điểm, nhược điểm của cả haikiểu giao thức: dựa theo lưới(messh based) và dựa theo cây (tree based)

Ưu điểm đầu tiên của các giao thức dựa theo lưới là tính bền vững vượt trội của chúng Xác suất mạng overlay bị phân tách do nút bị lỗi hoặc sự rời mạng đột ngột của nút là rất thấp do các mạng overlay này có các kết nối đa

đường hoặc có dự phòng Hơn nữa, do tồn tại nhiều đường dẫn nên không cần phải khôi phục lại một đường dẫn bị lỗi (như trong trường hợp của một mạng overlay kiểu cây) Một ưu điểm khác đó là các giao thức theo lưới sử dụng các thuật toán xây dựng cây đã có Cuối cùng, do trong lưới các cây có nút gốc cũng là nút nguồn nên các giao thức của nhóm này sẽ hỗ trợ các ứng dựng đa nút nguồn (many- -many) to

Nhược điểm chủ yếu của cách tiếp cận theo lưới là tải thông tin mào đầu điều khiển cao (do các thành viên cần phải giữ thông tin trạng thái của tất cả các thành viên khác) Mỗi khi thành viên gia nhập hoặc rời mạng, tất cả các thành viên nhóm phải được thông báo dẫn đến phải có mào đầu điều khiển Mặc dù đây chỉ là một lựa chọn thiết kế, dùng mào đầu để có tính chắc chắn ổn định hơn, điều này cũng giới hạn các thuật toán chỉ được phép hỗ trộ các nhóm multicast nhỏ Các cơ chế theo lưới cũng gánh chịu sự mất gói tin cao hơn do chúng chạy theo một thuật toán xây dựng cây Điều này có thể dẫn đến sự chuyển đổi trạng thái do không phải tất cả các bảng định tuyến của các nút được giám sát và như vậy gói tin có thể sẽ bị mất

Ưu điểm chính của các giao thức theo cây là chúng dễ mở rộng hơn so với giao thức dựa theo lưới do mỗi host chỉ phải trao đổi với một số nhỏ các (host khác) Điểm yếu chính của chúng là tính dễ bị phân tách Các mạng overlay cây thường dễ bị phân tách hơn do lỗi của bất kỳ nút nào cũng có thể dẫn đên đứt đoạn truyền thông và phân tách cây

Những năm trước đây, các hệ thống chia sẻ file được sử dụng phổ biến

Hệ thống mạng ngang hàng P2P có được sự quan tâm vì hai khía cạnh cơ bản Thứ nhất, trên quan điểm người sử dụng, sử dụng máy tính trên mạng P2P có tiềm năng lớn do nó giảm sự cần thiết phải sử dụng những server đầu cuối đắt tiền mà lại thường phải xử lý những tác vụ phức tạp Xu hướng hiện tại trong việc xây dựng các hệ thống P2P bao gồm việc cung cấp một mạng overlay độc

lập ứng dụng như một nền tảng mà ở mức trên cùng của nó các ứng dụng diện rộng được xây dựng.

Hai kiểu giải pháp cơ sở hạ tầng cho các mạng overlay được phân biệt là: không có cấu trúc (unstructured) và có cấu trúc (structured) Các nút trong lớp

overlay không có cấu trúc được tổ chức trong một đồ thị ngẫu nhiên: một user mới tham gia vào hệ thống overlay bằng cách tự liên kết với một nút bất kỳ (theo lựa chọn ngẫu nhiên) Dữ liệu lưu trữ trong các nút overlay được truy vấnhoặc theo kiểu tràn ngập (flooding) hoặc theo đường đi ngẫu nhiên trên đồ thị

Điều này là kém hiệu quả do một tập con các nút được truy vấn cho một nội dung không được phân phối rộng rãi Bất chấp các nỗ lực để cải thiện cho overlay không có cấu trúc, thì overlay có cấu trúc vẫn ra đời

Overlay có cấu trúc được xây dựng trên một mô hình được kiểm soát Trong những hệ thống này, mỗi mục dữ liệu và mỗi thành viên được ấn định một mã nhận dạng logic duy nhất Dựa trên mã nhận dạng thành viên, một thành viên mới gia nhập bằng cách gắn vào một thành viên cũ tạo nên đồ thị có câu trúc Nhưng không chỉ là thay thế các thành viên mới mà còn thay thế cả

các mục dữ liệu Những hệ thống này dựa vào các bảng DHT (distributesd hash tables) để ánh xạ từ khoá (nhận dạng của các mục dữ liệu) vào nút lưu trữ khoá

và mục dữ liệu đó Điều này cho phép tìm kiếm hiệu quả cho các truy vấn

chính xác, nhờ đó một mục dữ liệu (data item) có thể tìm thấy trong O(logN)

bước truyền (hop) Ngoài ra, tổng O(logN) của các nút lân cận cũng được duy

trì theo từng nút

Một vài nghiên cứu gần đây chỉ ra rằng tỉ lệ các nút gia nhập và rời khỏi mạngcũng như tính hỗn tạp của người dùng là rất cao Nhiều ý kiến trái ngược cho rằng mô hình overlay không có cấu trúc có thể xử lý như một môi trường hiệu quả hơn Hơn nữa, chúng cung cấp tìm kiếm hiệu quả hơn đối với các yêu cầu phức tạp của các mục dữ liệu so với các đối tác có cấu trúc Một hệ thống lai ghép sẽ được thiết kế để xây dựng lên một biểu đồ có cấu trúc, tuy nhiên các

không có cấu trúc Các kết quả minh họa dựa trên các mẫu thực chỉ ra rằng hệ thống lai ghép có thể hỗ trợ các yêu cầu phức tạp với một bản tin mào đầu nhỏ hơn trong khi cung cấp các tỉ lệ thành công yêu cầu cao hơn và thời gian đáp ứng thấp hơn hệ thống dựa trên biểu đồ không có cấu trúc.

Overlay có cấu trúc có thể được sử dụng cho multicast lớp ứng dụng (AL) AL multicast được xây dựng tại lớp trên cùng của overlay có cấu trúc như là một ứng dụng Rất nhiều các đề xuất như vậy đã ra đời Tất cả các đề xuất này đều có một điểm chung đó là đối với mỗi một nút một địa chỉ logic từ không gian trừu tượng được ấn định Tiếp theo, các cây phân bổ được nhúng vào trong các mạng overlay, và không cần giao thức định tuyến Điều này cho phép các nguyên lý như thế mở rộng lên các mạng có kích thước lớn (hàng

nghìn nút), mà không bị hạn chế đối với các ứng dụng nguồn đơn source), đây cũng là ưu điểm của các nguyên lý này

(single-Trở ngại chính là hiệu suất suy giảm so với các giao thức của hai nhóm đầu tiên Hiệu suất thấp là hậu quả của sự bất cập không tối ưu giữa mạng overlay và mạng nền cơ sở Cụ thể là người dùng cuối không có thông tin topo sẵn có cho các bộ định tuyến mạng Do vậy khi kết nối các nút với nhau tạo thành mạng overlay, chúng thường không quan tâm đến topo cơ sở như thế nào Trong trường hợp này hai nút lân cận nhau trong mạng overlay có thể được tách biệt bởi nhiều bước truyền trên lớp IP Do đó thậm chí nếu tối ưu số bước truyền lớp ứng dụng, một đường đi giữa nút nguồn và đích trên mạng overlay có thể gồm một số lượng lớn các bước truyền ở lớp IP

Thông thường, có 3 cách tiếp cận có thể tích hợp thông tin kiến trúc mạng vào overlay đó là: Định tuyến gần, Ấn định số hiệu nhận dạng nút

(nodeID) dựa trên kiến trúc mạng và Lựa chọn lân cận gần Phần dưới đây sẽ

giải thích cụ thể hơn Tuy nhiên, để đạt được sự tương đồng của mạng overlay với mạng lớp dưới IP để tìm đường tối ưu vẫn là một bài toán khó, và việc tích hợp thông tin kiến trúc mạng vào mạng overlay vẫn phải thực hiện từng phần

2.3.1 Multicast theo CAN – MCAN [16]

Mạng overlay CA N

Nguyên lý multicast này [16] khai thác mạng overlay có cấu trúc CAN Các nút trong mạng CAN được nhận dạng trong một không gian toạ độ

Cartesian d chiều Mỗi nút trong mạng CAN nắm giữ một vùng riêng (xem

hình 2.6) được xác định bởi các toạ độ của nó Bảng định tuyến trong mỗi nút chứa địa chỉ IP và toạ độ vùng của nút lân cận (hai nút được gọi là lân cận nhau nếu vùng của chúng chồng chéo nhau tất cả ngoại trừ một chiều) Điều này có nghĩa là mỗi nút duy trì bảng định tuyến với O(d) thực thể và làm cho bảng

định tuyến độc lập với kích cỡ mạng Sự định tuyến của bản tin được thực hiện theo kiểu: gói tin được truyền đến nút lân cận với toạ độ gần nhất với toạ độ của nút đích

Hình 2.6: Minh hoạ mạng overlay CAN hai chiều

Mạng overlay được hình thành theo cách sau: mỗi nút muốn tham gia trước tiên phải tìm được một nút đã tham gia vào mạng CAN bằng cách sử dụng cơ chế tự mồi (bootstrap) Tiếp đến, nó chọn ngẫu nhiên một điểm với toạ

(x,y) trong không gian CAN Thông qua nút tự mồi, n gửi một bản tin yêu cầó u tham gia cho một nút chiếm giữ vùng chứa toạ độ (x,y) Vùng chứa toạ độ (x,y)

được chia làm 2 nửa: một nửa giữ bởi nút đang nắm giữ vùng, và nửa còn lại được cấp phát cho nút mới Tiếp đến, cả hai nút cập nhật bảng định tuyến của chúng và thông báo sự thay đổi cho các nút lân cận để cùng cập nhật bảng định

tuyến của chúng Khi một nút rời mạng, nó chuyển vùng nó nắm giữ cho một nút ở lân cận của nó.

Thông tin kiến trúc mạng trong mạng overlay CAN

Mạng overlay CAN cấp phát các nút cho các vùng một cách ngẫu nhiên nên không có mối liên hệ giữa toạ độ các nút và kiến trúc mạng cơ sở Do vậy, các nút lân cận trên một mạng CAN không nhất thiết phải gần nhau về mặt vật

lý trong mạng Internet Do vậy việc định tuyến sẽ không hiệu quả Kỹ thuật thông tin kiến trúc mạng mà được thực hiện trong CAN được tạo ra ấn định nhận dạng nút theo kiến trúc mạng Trong cách tiếp cận này, thông tin kiến trúc mạng được tích hợp trong cấu trúc overlay: các nút mà gần nhau trong mạng lớp dưới (mạng hạ tầng) sẽ được lân cận với nhau trong mạng overlay Người thiết kế CAN đã đề xuất việc thay thế kiến trúc mạng lớp dưới dựa trên mốc ranh giới (landmark based) khi tạo ra CAN Trong cách tiếp cận này, mỗi nút

khảo sát một tập các cơ chế mốc ranh giới, đánh giá khoảng cách mạng bằng cách đo thời gian đường đi vòng (rtt) và sắp xếp giá trị rtt theo thứ tự tăng dần

Không gian CAN được chia thành các khối và chọn ngẫu nhiên một nút giữa các nút, nút chia sẽ được chọn một cách ngẫu nhiên trong khu vực khối Những khối này là các cụm nút với cùng thứ tự mốc ranh giới Do vậy, các nút gần nhau về mặt hình học thường có cùng trật tự và sẽ được đặt otr ng cùng phần không gian của CAN

Thuật toán chuyển tiếp trong cơ chế multicast dựa trên CAN (MCAN)

Mạng overlay CAN có thể dễ dàng khai thác cho việc multicasting Nếu chúng ta giả sử các nút CAN hoặc tập con của chúng tạo thành nhóm multicast, thì cách đơn gián nhất để đạt được multicasting có thể là truyền tất cả các bản tin đến tất cả các nút tham gia Do vậy thuật toán làm tràn lụt tạo ra một số lượng lớn các gói tin sao chép, một thuật toán chuyển tiếp hiệu quả hơn đã được đưa ra [16] Hơn nữa, thuật toán được cải tiến đã tạo ra một lượng các gói tin sao chép Thuật toán này chúng ta sẽ mô tả ở dưới và có thể gọi là MCAN1

Thuật toán chuyển tiếp (MCAN1)

Quy tắc chuyển tiếp gốc: Điểm nguồn tạo ra một bản tin mới chuyển tiếp bản tin này đến tất cả các điểm lân cận của nó (hình 2.7(a))

Qui tắc chuyển tiếp chung: Nếu một nút nhận một bản tin dọc theo trục y, thì

nó sẽ chuyển tiếp bản tin theo trục y theo hướng ra khỏi nút gốc để đến các lân cận theo cả hướng trục x (trong hình 2.7(b), nút H chuyển tiếp bản tin đến nút I,

J, K và G) Trái lại, nếu một nút nhận bản tin dọc theo trục x, nó sẽ chỉ chuyển

tiếp bản tin đến các lân cận dọc theo trục x, theo hướng đi ra khỏi nút nguồn (nút C trong hình 2.7(b))

Qui tắc nửa đường: Một nút không chuyển tiếp một bản tin dọc theo một

hướng xác định nếu bản tin đã được truyền một nửa đường đi qua không gian

từ toạ độ nút gốc theo hướng này Qui tắc truyền nửa đường được minh hoạ trong hình 2.7(c) (G và H sẽ không được truyền đến K, A sẽ không được truyền

đến N, …) Quy tắc này bảo vệ việc truyền tràn lụt do có sự lặp vòng trong không gian

Quy tắc giấu kín : Một nút giấu kín số tuần tự các bản tin nhận và không chuyển tiếp cùng một bản tin quá hai lần

Quy tắc lọc góc: Qui tắc này được xây dựng dựa trên thực tế là mỗi nút đều biết toạ độ vùng của các nút lân cận nó Một nút chỉ chuyển tiếp bản tin đến các lân cận của nó nếu vùng của nó có liên lạc với một góc của nút lân cận Một góc của một nút được xác định theo cách sau: giả sử nút X nhận bản tin theo

một trục xác định Giả sử thêm là nó có đường biên với nút Y theo trục vuông góc (theo hướng ngược với hướng nó nhận bản tin) Góc CRYR của Y sẽ là toạ độ

thấp nhất của Y theo hướng (trực giao) này Hình 7(d), C2 RMR là góc của nút M, còn CRFR là góc của nút F Do vậy, nút M và Fchỉ nhận được bản tin lần lượt từ nút J và D do vùng của J và D có liên hệ với các góc của M và F

Hình 2.7: Thuật toán chuyển tiếp multicast từ nút gốc trong CAN

cả nhóm Mỗi nhóm có một mã nhận dạng duy nhất ( group ID và nút gốc của )

cây Cây được tạo bởi tổ hợp các đường đi Pastry từ mỗi thành viên nhóm đến nút gốc của cây Một nút muốn gửi một bản tin đến cả nhóm thì phải chuyển đến nút gốc trước Từ nút gốc bản tin multicast được phân bố đến cả cây multicast