Định tuyến đa phát dựa trên bảo trì tối ưu cây khung trong các mạng tự hợp di động

  • 107 trang
  • file .pdf
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNGĐẠI HỌC CÔNG NGHỆ
NGUYỄN TRUNG HẢI
ĐỊNH TUYẾN ĐA PHÁT DỰA TRÊN
BẢO TRÌ TỐI ƯU CÂY KHUNG
TRONG CÁC MẠNG TỰ HỢP DI ĐỘNG
LUẬN VĂN THẠC SĨ
Hà Nội - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNGĐẠI HỌC CÔNG NGHỆ
NGUYỄN TRUNG HẢI
ĐỊNH TUYẾN ĐA PHÁT DỰA TRÊN
BẢO TRÌ TỐI ƯU CÂY KHUNG
TRONG CÁC MẠNG TỰ HỢP DI ĐỘNG
LUẬN VĂN THẠC SĨ
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số : 60.48.15
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS NGUYỄN ĐẠI THỌ
Hà Nội - 2010
i
MỤC LỤC
LỜI CAM ĐOAN ............................................................................................... i
LỜI CẢM ƠN ..................................................................................................... i
MỤC LỤC .......................................................................................................... i
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ...................................... 1
DANH MỤC CÁC BẢNG BIỂU ....................................................................... 2
DANH MỤC HÌNH VẼ ..................................................................................... 3
CHƢƠNG 1 - GIỚI THIỆU CHUNG ................................................................ 5
1.1 Mở đầu ................................................................................................... 5
1.2 Vấn đề nghiên cứu .................................................................................. 6
1.3 Phƣơng pháp luận ................................................................................... 7
1.4 Tổ chức luận văn .................................................................................... 8
CHƢƠNG 2 - ĐA PHÁT TRONG MẠNG MANET ......................................... 9
2.1 Giới thiệu ............................................................................................... 9
2.2 Mạng tự hợp di động và các vấn đề khi thiết kế giao thức đa phát ........ 11
2.3 Phân loại các giao thức định tuyến đa phát ........................................... 14
2.4 Multicast Ad hoc On-demand Distance Vector – MAODV .................. 16
2.5 On-Demand Multicast Routing Protocol - ODMRP.............................. 18
2.6 Giao thức PUMA và ROMANT ........................................................... 19
2.7 Kết luận ................................................................................................ 22
CHƢƠNG 3 - XÂY DỰNG VÀ BẢO TRÌ TỐI ƢU CÂY KHUNG TRONG
MẠNG ĐỘNG ................................................................................................. 23
3.1 Mở đầu ................................................................................................. 23
3.2 Phát biểu bài toán ................................................................................. 23
ii
3.3 Giải thuật GHS-83 ................................................................................ 24
3.4 Giải thuật bảo trì cây khung trong mạng động ...................................... 32
3.5 Kết luận ................................................................................................ 46
CHƢƠNG 4 - CẢI TIẾN GIẢI THUẬT BẢO TRÌ TỐI ƢU CÂY KHUNG
TRONG MẠNG ĐỘNG .................................................................................. 47
4.1 Đặt vấn đề ............................................................................................ 47
4.2 Tƣ tƣởng giải thuật OMST cải tiến ....................................................... 48
4.3 Chi tiết giải thuật OMST cải tiến .......................................................... 51
4.4 Ví dụ minh họa ..................................................................................... 56
4.5 Chứng minh tính đúng đắn của giải thuật OMST cải tiến ..................... 61
4.6 Độ phức tạp thông báo của giải thuật OMST cải tiến............................ 62
4.7 Đơn giản hóa cài đặt danh sách “cây ảo” .............................................. 63
4.8 Cải tiến cách thức xây dựng “cây ảo” trong mạng MANET ................. 65
CHƢƠNG 5 - XÂY DỰNG VÀ BẢO TRÌ TỐI ƢU CÂY KHUNG ĐA PHÁT
TRONG MẠNG MANET ................................................................................ 67
5.1 Đặt vấn đề ............................................................................................ 67
5.2 Tƣ tƣởng của giải pháp ......................................................................... 67
5.3 Giải thuật chi tiết .................................................................................. 72
5.4 Ví dụ minh họa ..................................................................................... 80
5.5 Chứng minh tính đúng đắn ................................................................... 86
5.6 Độ phức tạp thông báo.......................................................................... 86
CHƢƠNG 6 - ĐÁNH GIÁ GIẢI PHÁP MỚI .................................................. 87
6.1 Môi trƣờng mô phỏng và các tham số .................................................. 87
6.2 Chứng minh tính đúng đắn của giải thuật ............................................. 88
6.3 Đánh giá hiệu quả truyền phát thành công ............................................ 90
6.4 Đánh giá độ trễ trung bình truyền thông ............................................... 94
iii
6.5 Đánh giá tỉ lệ phụ tải ............................................................................ 95
6.6 Đánh giá trung bình số gói tin điều khiển ............................................. 96
6.6 Nhận xét ............................................................................................... 98
CHƢƠNG 6: KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU TIẾP THEO ............ 99
6.1 Kết luận ................................................................................................ 99
6.2 Hƣớng nghiên cứu tiếp theo................................................................ 100
TÀI LIỆU THAM KHẢO .............................................................................. 101
1
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
MANET Mobile adhoc network Mạng tự hợp di động
NS-2 Network Simulator 2 Bộ công cụ giả lập mạng phiên
bản 2
NAM Network Animator Công cụ hình hóa mô phỏng
mạng
IP Internet Protocol Giao thức định tuyến cho mạng
Internet
HTTP Hyper Text Transfer Giao thức truyền văn bản siêu
Protocol liên kết
SMTP Simple Mail Transfer Giao thức gửi mail đơn giản
Protocol
FTP File Transfer Protocol Giao thức truyền file
ARP Address Resolution Giao thức phân giải địa chỉ
Protocol
MZRP Multicast Zone Routing Giao thức định tuyến đa phát theo
Prototol vùng
MAODV Multicast Adhoc On- Giao thức định tuyến đa phát theo
demand Distance Vector yêu cầu dựa theo vector khoảng
cách
AMRIS Ad hoc Multicast Routing Giao thức định tuyến đa phát
protocol utilizing Increasing bằng các sử dụng chỉ số ID tăng
id-numberS dần
ODMRP On-Demand Multicast Giao thức định tuyến đa phát theo
Routing Protocol yêu cầu
CAMP Core Assisted Multicast Giao thức định tuyến đa phát dựa
Protocol theo gốc
RREQ Route Request Yêu cầu định tuyến
MST Minimum Spanning Tree Cây khung nhỏ nhất
OMST Optimal Maintenance of Bảo trì tối ƣu cây khung
Spanning Tree
PDR Packet Delivery Ratio Tỉ lệ truyền thành công
STM Spanning Tree for Cây khung đa phát
Multicast
PUMA Protocol for Unified Giao thức cho đa phát hợp nhất
Multicasting through dựa vào các bản tin thông báo
Annoucements
ROMANT Robust Multicasting in Đa phát hiệu quả trong mạng tự
Adhoc Networks using Trees hợp sử dụng cây
2
DANH MỤC CÁC BẢNG BIỂU
Bảng 1: Thực hiện giải thuật OMST ................................................................. 38
Bảng 2: Thủ tục LOCAL-UPDATE ................................................................. 40
Bảng 3: Thủ tục FIND ...................................................................................... 42
Bảng 4: Thủ tục CHANGE_ROOT .................................................................. 43
Bảng 5: Thủ tục MERGE ................................................................................. 44
Bảng 6: Thực hiện giải thuật OMST cải tiến .................................................... 51
Bảng 7: Thủ tục UPDATE ............................................................................... 52
Bảng 8: Thủ tục UPDATED ............................................................................. 53
Bảng 9: Thủ tục FIND ...................................................................................... 54
Bảng 10: Thủ tục FOUND ............................................................................... 55
Bảng 11: Thủ tục SET_DATALINK ................................................................ 77
Bảng 12: Thủ tục CANCEL_DATALINK ....................................................... 78
Bảng 13: Cấu hình môi trƣờng giả lập .............................................................. 87
3
DANH MỤC HÌNH VẼ
Hình 1: Đơn phát (trái), phát tỏa (giữa) và đa phát (phải) ................................... 9
Hình 2: Đa phát mạng chồng (trái) và đa phát tầng mạng (phải) ....................... 10
Hình 3: Một mạng tự hợp di động đơn giản ...................................................... 11
Hình 4: Phân loại các giao thức định tuyến đa phát .......................................... 14
Hình 5: Phân loại định tuyến theo hình trạng mạng .......................................... 15
Hình 6: Phân loại định tuyến đa phát theo cơ chế bảo trì hình trạng ................. 16
Hình 7: Hoạt động giao thức MAODV ............................................................. 17
Hình 8: Giao thức ODMRP .............................................................................. 19
Hình 9: Khởi tạo lƣới trong mạng bằng giao thức PUMA ................................ 21
Hình 10: Khởi tạo cây chia sẻ trong giao thức ROMANT ................................ 21
Hình 11: Minh họa chứng minh định lí 3.1 ....................................................... 25
Hình 12: “Rừng ảo” lƣu tại nút u ...................................................................... 34
Hình 13: Mảnh A chọn liên kết ngoài có trọng số 2.......................................... 36
Hình 14: Mảnh B chọn liên kết ngoài có trọng số 1 (mới đƣợc thêm vào) ........ 36
Hình 15: Gửi thông báo thêm cạnh u-t cho nút right ......................................... 41
Hình 16: Gửi thông báo thêm cạnh u-t và xóa cạnh u-s .................................... 41
Hình 17: Danh cách cây ảo tại nút 6 ................................................................. 41
Hình 18: Danh cách cây ảo tại nút 6 ................................................................. 50
Hình 19: Đồ thị vô hƣớng trƣớc khi kết hợp ..................................................... 56
Hình 20: Hình trạng mạng sau khi mảnh MST kết hợp với nút 2 thông qua nút 1
......................................................................................................................... 57
Hình 21: Cây khung dựng đƣợc sau khi kết thúc .............................................. 58
Hình 22: Liên kết 3-4 bị đứt gãy....................................................................... 59
Hình 23: Hình trạng mạng sau khi kết hợp trở lại ............................................. 60
Hình 24: Minh họa chứng minh định lí 4.2 ....................................................... 62
Hình 25: Giá trị node_map tƣơng ứng với “cây ảo” ......................................... 64
Hình 26: Mô tả các khái niệm trong cây khung đa phát .................................... 69
4
Hình 27: Các loại liên kết với nút hàng xóm .................................................... 70
Hình 28: Trƣớc và sau khi thực hiện thủ tục SET_DATALINK ....................... 78
Hình 29: Xóa bỏ các liên kết Data_Link không cần thiết .................................. 79
Hình 30: Hình trạng mạng cần xây dựng cây khung đa phát ............................. 80
Hình 31: Hình trạng cây MST sau khi nút 0 mở rộng với nút 3 ........................ 81
Hình 32: Hình trạng cây khung sau khi nút 0 kết hợp với nút 4 ........................ 83
Hình 33: Cây khung STM sau khi kết hợp với nút 2 ......................................... 84
Hình 34: Cây STM hoàn chỉnh ......................................................................... 85
Hình 35: Quá trình kết hợp các mảnh ............................................................... 88
Hình 36: Quá trình kết hợp thành công ............................................................. 89
Hình 37: Cây khung bị đứt gãy liên kết ............................................................ 89
Hình 38: Cây khung đƣợc bảo trì thành công ................................................... 90
Hình 39: Biểu đồ tỉ lệ truyền thành công theo thời gian .................................... 91
Hình 40: Biểu đồ tỉ lệ truyền thành công theo tốc độ nút .................................. 92
Hình 41: Biểu đồ tỉ lệ truyền thành công theo số nút phát ................................ 93
Hình 42: Biểu đồ độ trễ trung bình theo tốc độ nút và số lƣợng nút tham gia ... 94
Hình 43: Biểu đồ độ trễ theo số nút phát .......................................................... 94
Hình 44: Biểu đồ tỉ lệ phụ tải theo thời gian và số nút tham gia........................ 95
Hình 45: Biểu đồ tỉ lệ phụ tải theo tốc độ nút và số nút phát ............................. 96
Hình 46: Biểu đồ trung bình thông điệp điều khiển theo thời gian và số nút ..... 97
5
CHƢƠNG 1 - GIỚI THIỆU CHUNG
1.1 Mở đầu
Với sự phát triển không ngừng của các thiết bị máy tính cá nhân xách tay
và các thiết bị truyền dữ liệu không dây với giá thành ngày càng rẻ, truyền thông
không dây giữa những ngƣời dùng di động đang càng ngày càng trở nên phổ
biến, với mức nhu cầu truyền nhận dữ liệu càng cao, nhƣ truyền dữ liệu đa
phƣơng tiện, dữ liệu hội nghị truyền hình… Do tính chất di động của các thiết
bị, đôi khi việc thiết lập mạng truyền không cần sự giúp đỡ của các thiết bị hạ
tầng cơ sở cố định, nhƣ các trạm phát cơ sở (base station) hoặc điểm truy cập
(access point). Thay vào đó, ngƣời dùng có thể thiết lập các mạng không dây di
động ngang hàng của riêng họ. Những mạng này đƣợc gọi là mạng tự hợp di
động (mobile ad hoc network- MANET).
Năm 2003, Chlamtac, Conti và Liu [1] đã đƣa ra khái niệm chính thức về
mạng MANET, là mạng động tạm thời đƣợc thiết lập bằng một tập hợp các nút
mạng không dây di động tự trị mà không cần bất kì sự hỗ trợ về cơ sở hạ tầng
mạng cố định cũng nhƣ hỗ trợ về quản lí tập trung. Các nút mạng tự do di
chuyển một cách ngẫu nhiên và tự tổ chức chính nó bằng một số qui luật chung,
do đó, hình trạng mạng có thể thay đổi một cách đột ngột và không thể đoán
trƣớc. Hơn nữa, các thiết bị không dây di động có sự hạn chế về không gian
truyền, năng lƣợng và năng lực vi xử lí, làm cho toàn bộ mạng MANET có các
đặc tính rất tự nhiên nhƣ mạng động, băng thông thấp, tỉ lệ mất gói cao, giới hạn
năng lƣợng… (theo Kaliaperumal và Jeyakumar [2]) . Do đó, vấn đề lựa chọn
thiết kế giao thức truyền thông trong mạng MANET đóng vai trò cốt lõi để đảm
bảo chất lƣợng dịch vụ mạng.
Mạng MANET càng ngày càng có nhiều ứng dụng thực tế, nhƣ hội nghị
nhóm, các ứng dụng khẩn cấp nhƣ cứu hộ, chia sẻ dữ liệu lớn. Đặc biệt trong
các ứng dụng chia sẻ dữ liệu, một nút mạng có thể chia sẻ dữ liệu cho rất nhiều
nút lân cận cùng lúc, do bản chất truyền đa hƣớng của sóng không dây. Tính
chất này làm cho các ứng dụng chia sẻ dữ liệu và truyền thông kiểu phát tỏa
(broadcast) và đa phát (multicast) đƣợc quan tâm nghiên cứu và phát triển nhiều
hơn. Trong đó, truyền thông đa phát có cách thức thực thi khó khăn và tốn chi
phí nhiều hơn so với phát tràn, do phải có cơ chế điều khiển để không truyền dữ
6
liệu tràn lan gây lãng phí băng thông mạng, mà chỉ truyền cho một số thành viên
thuộc cùng nhóm truyền thông.
Vì thế, nghiên cứu về đa phát và các giao thức định tuyến đa phát trong
mạng MANET là một trong những hƣớng nghiên cứu thu hút đƣợc nhiều sự
quan tâm. Có nhiều các ý tƣởng, giao thức và cách thức tiếp cận khác nhau đƣợc
đƣa ra, nhƣng hiện nay vẫn chƣa có một chuẩn chính thức đƣợc công nhận rộng
rãi về mặt học thuật lẫn ứng dụng công nghiệp. Luận văn này hƣớng đến nghiên
cứu vấn đề một vấn đề quan trọng của định tuyến đa phát trong mạng MANET:
duy trì và bảo toàn hình trạng mạng với chi phí tối thiểu, đảm bảo kết nối đƣợc
liên tục và chất lƣợng, bằng hƣớng tiếp cận ứng dụng các kết quả nghiên cứu
mới nhất trong lĩnh vực tính toán phân tán áp dụng cho mạng MANET, từ đó
xây dựng nên một giao thức định tuyến đa phát mới, đáp ứng đƣợc yêu cầu của
một giao thức định tuyến đa phát với kết quả tối ƣu về một số thông số đƣợc
trình bày ở các phần sau.
1.2 Vấn đề nghiên cứu
Trong định tuyến đa phát, việc duy trì và bảo toàn hình trạng mạng nhằm
đảm bảo sự truyền thông đƣợc liên tục và bảo đảm chất lƣợng dịch vụ là một
vấn đề then chốt đƣợc hầu hết các nghiên cứu quan tâm đến. Có nhiều tƣ tƣởng
và hƣớng tiếp cận khác nhau đƣợc đặt ra để giải quyết vấn đề này. Một trong
những hƣớng tiếp cận cơ bản và có tính nền tảng là dựa theo lý thuyết đồ thị,
trong đó xem xét mạng MANET là một đồ thị có trọng số vô hƣớng và mạng
truyền dữ liệu là một cây nối tất cả các nút trong đồ thị. Do từng tính chất của
mạng MANET mà yêu cầu xây dựng cây có sự khác biệt, một số mạng chỉ
truyền thông đa phát theo kiểu môt-nhiều, trong đó một nút gửi và nhiều nút
nhận, lúc đó cây xây dựng hƣớng vào nút gửi (mô hình Source Based Tree); một
số mạng khác xem toàn bộ các nút trong cây là bình đẳng (mô hình Shared Tree)
và truyền thông theo kiểu nhiều-nhiều.
Luận văn đặt ra vấn đề nghiên cứu truyền thông nhiều-nhiều, do các ứng
dụng nhƣ hội nghị truyền hình, trong đó mọi thành viên đều có thể phát biểu và
truyền dữ liệu, càng ngày càng trở nên phổ biến hơn, thay vì chỉ có một nguồn
gửi dữ liệu duy nhất. Theo lí thuyết đồ thị, bài toán trở thành xây dựng và bảo trì
cây khung nhỏ nhất, lúc đó, chi phí về truyền dữ liệu sẽ đƣợc tối ƣu nhất. Tuy
nhiên, cây khung dùng trong định tuyến đa phát (từ đây gọi là cây khung không
đầy đủ hay cây khung đa phát) không giống hoàn toàn với cây khung nhỏ nhất
thuần túy, lí do là chỉ có một số nút mạng thuộc nhóm đa phát để gửi nhận dữ
7
liệu, một số nút khác chỉ đóng vai trò định tuyến và chuyển tiếp gói tin chứ
không trực tiếp nhận dữ liệu, nếu áp dụng nguyên bản tƣ tƣởng cây khung nối
tất cả các nút mạng lại với nhau, thì sẽ không tối ƣu về chi phí đƣờng truyền nếu
chuyển tiếp gói tin cho những nút không thuộc nhóm đa phát. Do đó cần đƣa ra
một giải pháp tiên tiến hơn để giải quyết vấn đề trên.
Một số nghiên cứu cũng đặt ra vấn đề tƣơng tự, tuy nhiên hiệu suất của
giao thức vẫn chƣa tối ƣu, chi phí phụ tải cho điều khiển mạng lớn. Luận văn
đƣa ra một hƣớng tiếp cận hoàn toàn mới, áp dụng các thành tựu mới nhất trong
lĩnh vực tính toán phân toán để đƣa ra giao thức xây dựng và bảo trì cây khung
đa phát với chi phí tối thiểu hóa, cây khung đa phát đƣợc bảo trì là cây khung
xấp xỉ nhỏ nhất có thể đƣợc.
1.3 Phƣơng pháp luận
Luận văn đƣợc thực hiện dựa trên các thành quả mới nhất trong lĩnh vực
tính toán phân tán[11][12], trong đó giảm thiểu chi phí bảo trì hình trạng mạng
từ giá trị O(E) với E là số cạnh của đồ thị sang O(V) với V là số đỉnh, trong một
mạng dày đặc giá trị O(E) đạt xấp xỉ O(V)2; giá trị O(V) là giá trị tối ƣu nhất có
thể có đƣợc đối với một mạng có V nút. Kết quả này đƣợc ứng dụng trong
nghiên cứu xây dựng và bảo trì cây khung trong mạng động nhằm tối thiểu hóa
chi phí điều khiển mạng, từ đó đƣa ra các thành quả mới trong xây dựng và bảo
trì cây khung đa phát cũng với chi phí tối thiểu hóa. Kết quả độ phức tạp đƣợc
chứng minh về mặt lí thuyết bằng toán học, đồng thời so sánh đánh giá hiệu
năng thực nghiệm với các giao thức tƣơng tự. Từ xây dựng một giải thuật toán
học thành một giao thức thực tế, luận văn cũng giải quyết rất nhiều vấn đề liên
quan đến bài toán đồng bộ xử lí tính toán và khắc phục lỗi. Để xây dựng giao
thức mạng thực tế, luận văn đi vào tìm hiểu chi tiết tƣ tƣởng và phƣơng thức
hoạt động của nhiều giao thức đa phát trên mạng MANET tƣơng tự, từ đó định
hình nên các bƣớc giao tiếp chính của giao thức mới. Từ đó, giao thức đƣợc cài
đặt trên bộ công cụ mô phỏng mạng NS-2[3], cung cấp kết quả thực thi trên NS-
2 để làm số liệu so sánh đánh giá hiệu năng thực nghiệm với các giao thức phổ
biến tƣơng tự nhƣ MAODV[9] và PUMA[13], để chứng minh tính ƣu việt về tỉ
lệ phát thành công gói tin, độ trễ thấp không hề thua kém các giao thức khác,
thậm chí có những thông số ƣu việt hơn, trong khi chi phí điều khiển giao thức
lại thấp hơn rất nhiều. Cuối cùng các kết luận và một số phƣơng hƣớng cải tiến
giao thức đƣợc đƣa ra để hoàn thiện hơn giải pháp.
8
1.4 Tổ chức luận văn
Luận văn đƣợc bố cục theo các chƣơng chính sau:
- Chƣơng 1: Giới thiệu: Cung cấp tổng quan về luận văn, từ vấn đề cần đặt
ra, đến hƣớng tiếp cận, cách thức tổ chức giải quyết vấn đề.
- Chƣơng 2: Trình bày chi tiết về đa phát và đa phát trong mạng MANET.
- Chƣơng 3: Trình bày sâu về bài toán xây dựng và bảo trì tối ƣu cây khung
trong mạng động.
- Chƣơng 4: Cải tiến giải thuật xây dựng và bảo trì tối ƣu cây khung trong
mạng động
- Chƣơng 5: Đề xuất giải pháp mới cho vấn đề cây khung đa phát trong
mạng MANET.
- Chƣơng 6: Các kết quả đạt đƣợc: Cài đặt, so sánh và đánh giá giải pháp
mới.
- Chƣơng 7: Kết luận và các hƣớng nghiên cứu tiếp theo.
9
CHƢƠNG 2 - ĐA PHÁT TRONG MẠNG MANET
2.1 Giới thiệu
Trong mạng máy tính nói chung và mạng IP nói riêng, dữ liệu có thể đƣợc
truyền phát bằng ba cách khác nhau: đơn phát, phát tỏa và đa phát. Đơn phát là
kiểu truyền thông đơn giản và phổ biến nhất, tạo ra liên kết dữ liệu một-một
giữa hai thực thể mạng đơn. Rất nhiều các ứng dụng hiện nay nhƣ HTTP,
SMTP, FTP… dựa trên định tuyến đơn phát. Phát tỏa là cơ chế phát từ một thực
thể mạng cho toàn bộ các thực thể khác cùng thuộc mạng đó, tạo ra liên kết kiểu
một-tất cả. Các ứng dụng trên mạng diện rộng thƣờng khó áp dụng cơ chế phát
tỏa, thay vào đó, các ứng dụng ở mức cục bộ hóa, nhƣ ARP (Address Resolution
Protocol) sử dụng cơ chế phát tỏa.
Đa phát là khái niệm có thể xem nhƣ nằm giữa đơn phát và phát tỏa, trong
đó một thực thể mạng đơn có thể gửi dữ liệu cho nhiều (nhƣng không phải tất
cả) các thực thể mạng khác, tạo ra liên kết dữ liệu một-nhiều hoặc nhiều-nhiều.
Ứng dụng đa phát trở nên phổ biến hơn trong mạng máy tính xuất phát từ yêu
cầu thực tế ngày càng nhiều, ví dụ việc phân phối cùng một nội dung (bản cập
nhật phần mềm, hội nghị từ xa, cung cấp dịch vụ nội dung số..), đặc biệt là các
dữ liệu đa phƣơng tiện có dung lƣợng lớn, làm cho vấn đềtối ƣu hóa các giao
thức định tuyến để đảm bảo chất lƣợng dịch vụ tốt nhất trở thành vấn đề then
chốt trong nghiên cứu và triển khai các hệ thống truyền dữ liệu dựa trên đa phát.
Hình 1: Đơn phát (trái), phát tỏa (giữa) và đa phát (phải)
10
Cơ chế đa phát có thể đƣợc cài đặt thông qua các cơ chế khác nhau, trong
đó có hai cơ chế phổ biến: đa phát ở tầng mạng và đa phát ở tầng dứng dụng (đa
phát mạng chồng – overlay multicast).
Đa phát mạng chồng [4] cho phép ảo hóa các kết nối đơn phát ở tầng mạng,
gửi các gói tin dữ liệu từ một thực thể mạng qua các thực thể khác bằng các kết
nối đơn phát độc lập. Đa phát mạng chồng có ƣu điểm là có thể cài đặt ở tầng
ứng dụng mà không cần có sự thay đổi ở các thiết bị định tuyếnởtầng mạng, bù
lại hiện tƣợnglặp các gói dữ liệu trên dùng một liên kết đơn làm tăng chi phí
truyền phát.
Do các đặc điểm này, các nghiên cứu về đa phát ở tầng mạng nhận đƣợc
nhiều sự chú ý hơn. Trong cơ chế này, một gói dữ liệu (hoặc bản sao của nó) sẽ
đƣợc gửi duy nhất một lần đến các router lân cận cho tới khi nào gói dữ liệu cần
đƣợc sao thành các bản và gửi đến các router tiếp theo để đến đƣợc các thực thể
đích. Một cách trực quan, cơ chế định tuyến này mang lại hiệu năng mạng cao
hơn, tuy nó yêu cầu các router trung gian phải hỗ trợ định tuyến. Do có ƣu thế
về hiệu năng, luận văn này chỉ tập trung vào các vấn đề liên quan đến đa phát
tầng mạng.
Hình 2: Đa phát mạng chồng (trái) và đa phát tầng mạng (phải)
Với cơ chế này, vấn đề định tuyến là vấn đề cốt lõi nhất, và cũng là trọng
tâm của luận văn này. Các vấn đề khác của đa phát không liên quan đến định
tuyến, nhƣ việc đánh địa chỉ, đã đƣợc trình bày chi tiết ở [4] và sẽ không đƣợc
trình bày lại ở đây.
Trong định tuyến tầng mạng, sẽ có các router chịu trách nhiệm chuyển phát
cùng một gói dữ liệu đến nhiều router kế tiếp, nhƣ hình 2. Trong mạng có dây,
11
thực tế các gói dữ liệu đi theo các đƣờng liên kết chặng khác nhau là độc lập,
làm tăng chi phí gửi gói tin tỉ lệ thuận với số router liền kề cần phải chuyển phát.
Với sự phát triển của ngành viễn thông và mạng không dây, cơ chế định
tuyến nhƣ trên trở nên tự nhiên hơn, trong đó các router giao tiếp bằng sóng
không dây, và một router chỉ cần phát đi (phát tỏa sóng mang) một gói dữ liệu
duy nhất là tất cả các router liền kề nằm trong vùng phủ của router này đều có
thể nhận đƣợc. Tiện ích này khiến cho các nghiên cứu về định tuyến đa phát
hƣớng nhiều đến mạng không dây.Các giao thức cài đặt trong định tuyến đa phát
mạng không dây so với mạng có dây, chủ yếu tập trung vào vấn đề đáp ứng tính
di động của mạng. Các vấn đề trong chƣơng này sẽ trình bày tập trung vào định
tuyến tầng mạng cho mạng không dây, tuy nhiên các khái niệm, sự phân loại và
tƣ tƣởng thuật toán hầu hết giống mạng có dây và có thể áp dụng đƣợc.
2.2 Mạng tự hợp di động và các vấn đề khi thiết kế giao thức đa phát
Mạng tự hợp di động hay thƣờng gọi là mạng Mobile Ad-hoc Network
(MANET). Mô hình này gồm hai hay nhiều thiết bị không dây di động kết nối
với nhau theo mô hình mạng ngang hàng (peer-to-peer) và các nút có vai trò nhƣ
nhau, và có thể kết nối với nhau một cách tùy ý và không cần đến cơ sở hạ tầng
của các mạng trƣớc đó. Các nút trong mạng này còn đóng vai trò nhƣ là các
router có khả năng tìm kiếm, duy trì và định tuyến các gói dữ liệu cho các
node nằm trong vùng phát sóng của nó. Các node trong mạng di chuyển
tùy ý nên kiến trúc của mạng luôn luôn thay đổi. Mô hình mạng MANET
đƣợc sử dụng nhiều trong những trƣờng hợp khẩn cấp: Hoạt động tìm
kiếm và cứu hộ, quân sự, …
Hình 3: Một mạng tự hợp di động đơn giản
Trong định tuyến đa phát, gói tin từ một nút gửi thƣờng phải đƣợc gửi đến
nhiều nút nhận và tạo nên một nhóm đa phát. Tất cả các nút có thể đồng thời gửi
dữ liệu, và bất kỳ nút nào cũng có thể tham gia và rời khởi nhóm một cách tùy ý.
12
Trong các mạng tự hợp di động với các nhƣợc điểm đã nêu ở phần trên, định
tuyến đa phát trở thành vấn đề rất phức tạp.
Những năm gần đây, nhiều giao thức định tuyến đa phát cho các mạng tự
hợp di động đã đƣợc phát triển, một số thì dựa trên cơ chế thụ động , các đƣờng
đi đƣợc khám phá khi có nhu cầu; một số khác lại dựa trên cơ chế chủ động nhƣ
định kỳ gửi phát tràn hoặc định kỳ cập nhất bảng định tuyến.
Những đặc tính riêng biệt của mạng MANET làm cho việc thiết kế giao
thức định tuyến multicast có những vấn đề riêng . Những giao thức này cần phải
tính toán đến rất nhiều trƣờng hợp, ví dụ, hình trạng mạng thay đổi động, khả
năng các node có giới hạn (do hầu hết là các node mobile), ít tài nguyên về năng
lƣợng, tỉ lệ lỗi truyền cao, vấn đề định tuyến đa chặng, và vấn đề xử lí thông
điệp ở thiết bị đầu cuối. Do đó, yêu cầu đặt ra với các giao thức định tuyến hiện
tại (và cả các giao thức định tuyến sau này) nên đƣợc cân nhắc đến tất cả các
yếu tố sau[5,6,7,8]:
- Hình trạng mạng, khả năng di động và khả năng bền bỉ: Trong mạng
MANET, các nút mạng di chuyển tự do đến bất kì đâu, vào bất kì lúc nào
và với các tốc độ khác nhau. Sự di chuyển ngẫu nhiên và liên tục của các
nút mạng dẫn đến một cấu hình mạng động, đặc biệt trong môi trƣờng
mạng có tính di động cao. Giao thức định tuyến multicast cần phải đủ bền
bỉ để phản hồi một cách nhanh chóng với sự di động của các nút mạng và
đáp ứng các thay đổi hình trạng để tránh việc mất mát các gói tin dữ liệu
trong suốt phiên multicast, việc mất mát dữ liệu này tạo ra tỉ lệ truyền gói
tín thấp (Packet delivery ratio: số gói tin không lặp nhận đƣợc ở các điểm
nhận so với số gói tin đƣợc mong chờ sẽ nhận đƣợc ở điểm nhận). Điều
này rất quan trọng trong thiết kế tối thiểu hóa các phụ phí cho gói tin điều
khiển mạng khi khởi tạo và duy trì hình trạng mạng cho multicast, đặc
biệt quan trọng trong môi trƣờng động với năng lực giới hạn (về băng
thông, năng lƣợng…)
- Năng lực và sự tiện lợi: Không nhƣ các mạng có dây, mạng MANET
đƣợc mô tả là có năng lực giới hạn đƣợc gây ra bởi nhiễu sóng và giao
thoa trong môi trƣờng truyền không dây và fading đa chặng. Các giao
thức định tuyến multicast đƣợc gọi là tiện lợi nếu nó cung cấp một số
lƣợng gói tin điều khiển vừa đủ, tỉ lệ tƣơng quan với số gói tin dữ liệu
truyền tới các điểm đến tham gia mạng; ngoài ra, các phƣơng thức để cải
13
tiến và năng cao năng lực hiện có của mạng cũng đƣợc cân nhắc để làm
tiện lợi hơn giao thức hiện có.
- Mức tiêu thụ năng lƣợng: Việc truyền phát gói tin tỉ lệ thuận với tỉ lệ tiêu
thụ năng lƣợng. Sự hạn chế tiêu thụ năng lƣợng là vấn đề cân quan tâm
trọng mang MANET, vì các nút trong mạng hầu hết hoạt động dựa và
nguồn pin có sức mạnh giới hạn. Các kĩ thuật tiết kiệm năng lƣợng đƣợc
sử dụng để tối thiểu hóa mức tiêu thụ năng lƣợng cũng đƣợc nghiên cứu,
nhƣ tối thiểu hóa số nút tham gia vào việc khởi tạo kết nối mạng
multicast, tối thiểu hóa số gói tin điều khiển…
- Chất lƣợng dịch vụ và quản lí tài nguyên: Cung cấp dịch vụ đảm bảo chất
lƣợng dịch vụ (Quality of Services) là một trong những thách thức lớn
nhất khi thiết kế giao thức multicast. Giao thức định tuyến multicast cần
có khả năng phục vụ theo từng tiêu chí chất lƣợng dịch vụ khác nhau nhƣ
năng lực mạng, độ trễ, mất gói tin… Rất khó để có thể đáp ứng tất cả các
yêu cầu QoS cùng lúc do các đặc thù của mạng MANET. Thậm chí cả khi
đáp ứng đƣợc, giao thức cũng sẽ rất phức tạp (nhiều bảng định tuyến, phụ
phí điều khiển lớn, tiêu thị nhiều năng lƣợng), điều này ảnh hƣởng tới
năng lực có giới hạn của mạng. Do đó, cân nhắc giữa chi phí và hiệu quả
thu đƣợc trong mạng MANET là điều cần quan tâm.
- An ninh và tin cậy: An ninh trọng MANET là điều sống còn trong
multicast bởi vì đặc tính phát tràn của mạng (có thể bị nghe lén ở giữa), và
đặc tính thiếu cơ sở hạ tầng cố định để quản lí trung tâm. Điều này làm
cho mạng MANET dễ bị tổn thƣơng bởi các hình thức nghe lén, giả
mạo… Các giao thức định tuyến cần cân nhắc vấn đề này, đặc biệt quan
trọng trong các ứng dụng nhƣ của quân đội, cứu hộ. Tin cậy là một yếu tố
quan trọng khác trong multicast, đặc biệt đối với tầng ứng dụng chạy trên
mạng này, nó trở nên khó khăn để cung cấp một dịch vụ truyền phát tin
cậy cho tầng ứng dụng nếu cấu hình mạng thay đổi liên tục. Một giao thức
multicast đáng tin cậy cần phải có câu trả lời rõ ràng cho cả ba câu hỏi: Ai
có vai trò tìm ra lỗi? Làm thế nào để báo hiệu lỗi cho toàn mạng? Làm thế
nào để truyền lại gói tin đã mất?
- Khả năng mở rộng: Một giao thức định tuyến multicast cần có khả năng
cung cấp một mức dịch vụ chấp nhận đƣợc trong mạng có số nút mạng
lớn. Để đảm bảo điều này, các đặc tính riêng biệt của mạng nhƣ năng lực
14
giới hạn, tính di động ngẫu nhiên, cần đƣợc tính đến khi giải quyết vấn đề
mở rộng mạng.
2.3 Phân loại các giao thức định tuyến đa phát
Có nhiều cách để phân loại các giao thức định tuyến đa phát, tùy theo triết
lí về mục đích xây dựng giao thức định tuyến. Hình 4 mô tả khái quát các cách
thức phân loại giao thức định tuyến.
Hình 4: Phân loại các giao thức định tuyến đa phát
Có một số cách phân loại khá phổ biến sau:
1/ Phân loại theo hình trạng mạng: Dựa theo hình trạng mà các nốt mạng
liên kết với nhau tạo thành. Có hai nhánh chính phân chia theo hình trạng: Hình
trạng dựa theo cây, và hình trạng dựa theo lƣới. Triết lí xây dựng cây liên kết
các nốt mạng xuất phát từ mạng có dây, theo nghĩa, chỉ có đƣờng đi ngắn nhất
trở thành tuyến nối các cặp gửi-nhận dữ liệu.
Cây liên kết đa phát trong mạng phân tán đƣợc xây dựng thành hai nhánh:
cây dựa theo nguồn và cây chia sẻ chung. Trong cây đa phát dựa theo nguồn,
mỗi nguồn phát hình thành một cây riêng, nhƣ các giao thức MZRP, BEMRP.
Trong khi đó, với cây đa phát dựa treo cây chia sẻ chung, mọi thực thể mạng chỉ
15
xây dựng duy nhất một cây nối chúng với nhau. Tƣ tƣởng này đƣợc áp dụng ở
rất nhiều các giao thức mạng, nhƣ MAODV, AMRIS, LAM…
Khác với quan điểm về cây, trong đó mỗi cặp thực thể chỉ có duy nhất một
liên kết, mạng đa phát dựa theo lƣới cho phép có nhiều đƣờng nối giữa cặp gửi-
nhận. Có rất nhiều giao thức áp dụng tƣ tƣởng này, nhƣ ODMRP, CAMP…
Hình 5: Phân loại định tuyến theo hình trạng mạng
Ngoài ra, còn có một số kiểu phân theo hình trạng mạng khác nhƣ: Lai
ghép giữa cây và lƣới (Hybrid), mạng không lƣu hình trạng (stateless), nhƣng ít
phổ biến hơn.
2/ Phân loại theo cách thức bảo trì kết nối: Do mạng MANET có thể thay
đổi do tính di động, nên cần thiết phải có cơ chế bảo trì kết nối mạng. Theo sự
phân loại này, có hai tƣ tƣởng chính: Bảo trì cứng (Hard-State) hoặc bảo trì
mềm (Soft-State).
Trong cơ chế bảo trì mềm, các thành viên của nhóm đa phát và các liên kết
đƣợc định kì làm mới (chủ động - proactive) bằng cách phát tràn gói tin điều
khiển, trong khi đó, với cơ chế bảo trì cứng, các liên kết bị đứt có thể tái cấu
hình bằng cách gửi các gói tin điều khiển yêu cầu tạo kết nối mới chỉ khi nào
phát hiện có liên kết bị đứt gãy (phản hồi - reactive). Rõ ràng, cơ chế cập nhật
chủ động các liên kết sẽ ít tránh gây ra mất mát gói tin hơn, dẫn đến tỉ lệ truyền
thành công cao hơn. Một số giao thức thuộc hai nhóm bảo trì kết nối đƣợc liệt
kê nhƣ hình dƣới.