Mục lục
TULời cảm ơnUT 3
TUDanh mục các từ viết tắtUT 4
TUDanh mục hình vẽUT 5
TUMở đầuUT 7
TUĐặt vấn đềUT 7
TUPhương pháp nghiên cứuUT 7
TUTóm tắt nội dung các chươngUT 8
TUChương 1. Giới thiệu mạng ad-hocUT 9
TU1.1. Khái niệmUT 9
TU1.2. Các ứng dụng của mạng ad-hocUT 10
TU1.3. Đặc điểm của mạng ad-hocUT 11
TU1.4. Một số khái niệm sử dụng trong luận vănUT 13
TUChương 2. Các thuật toán định tuyến trong mạng ad-hocUT 15
TU2.1. Thuật toán định tuyến trướcUT 15
TU2.1.1. Tổng quátUT 15
TU2.1.2. Nguyên tắc hoạt độngUT 16
TU2.1.3. Đánh giáUT 24
TU2.2. Thuật toán định tuyến theo yêu cầuUT 25
TU2.2.1. Tổng quátUT 25
TU2.2.2. Nguyên tắc hoạt độngUT 26
TU2.2.3. Đánh giáUT 35
TU2.3. Thuật toán laiUT 36
TUChương 3. Thuật toán định tuyến theo vùng ZRPUT 37
TU3.1. Giới thiệu chungUT 37
TU3.1.1. Tổng quátUT 37
TU3.1.2. Vùng định tuyếnUT 38
TU3.1.3. Trạm làm việc ngoại biên - trạm làm việc nội vùngUT 39
TU3.2. Nguyên tắc hoạc động của thuật toán ZRPUT 40
TU3.2.1. Định tuyến nội vùngUT 40
TU3.2.2. Định tuyến liên vùngUT 41
đúng thời hạn.
Xin trân trọng cảm ơn thày giáo, TS. Nguyễn Đình Việt, người đã cung cấp và
hướng dẫn cài đặt bộ mô phỏng NS-2, một công c
ụ mô phỏng đã được sử dụng trong
quá trình làm luận văn. Thày cũng đã có những góp ý bổ ích và tạo điều kiện để tác giả
luận văn được cùng làm việc với nhóm do thày hướng dẫn.
Xin cảm ơn sự tạo điều kiện, giúp đỡ, động viên của lãnh đạo và anh chị em trong
Viện Công nghệ Thông tin - Đại học Quốc gia Hà nội, cơ quan nơi tôi đang công tác.
Cảm ơn s
ự động viên giúp đỡ của các bạn cùng lớp cao học K9T3. Các bạn đã cung
cấp một số tài liệu liên quan tới vấn đề mà luận văn nghiên cứu.
Cảm ơn các thày cô giáo và các cán bộ trong trường Đại học Công nghệ - Đại học
Quốc gia Hà nội đã cung cấp các kiến thức khoa học và tạo điều kiện thuận lợi cho tác
giả trong quá trình học tập và thực hiện luận văn cao h
ọc này.
Những nguồn giúp đỡ động viên quý báu kể trên tạo điều kiện và là động lực rất lớn
để tác giả hoàn thành luận văn.
4
Danh mục các từ viết tắt
AODV Ad-hoc On Demand Distance Vector routing protocol – một giao thức
định tuyến cho mạng ad-hoc.
BRP Bordercast Resolution Protocol - giải pháp truy vấn ngoại biên.
CBR Constant Bit Rate – kỹ thuật phát gói tin theo tốc độ cố định.
DSDV Highly Dynamic Destination-Sequenced DistanceVector routing protocol
– một giao thức định tuyến trước dựa vào vectơ khoảng cách.
IARP Intrazone Routing Protocol – thành phần định tuyến nội vùng.
IERP Interzone Routing Protocol – thành phần định tuyến liên vùng.
NPDU Network Protocol Data Unit – gói dữ liệu mạng.
QD Query Detection - Kỹ thuật phát hiện truy vấn đã xử lý.
TUHình 21. Gửi gói tin yêu cầu định tuyến với giải pháp truy vấn ngoại biên BRPUT 46
TUHình 22. Kết thúc truy vấn lặpUT 47
TUHình 23. Kết thúc truy vấn sớmUT 48
TUHình 24. Kỹ thuật phát hiện truy vấn đã xử lýUT 49
TUHình 25. Truy vấn ngoại biên chọn lọcUT 50
TUHình 26. Trạm làm việc nguồn S yêu cầu thông tin định tuyếnUT 52
TUHình 27. Cây truy vấn ngoại biên do S xây dựngUT 53
TUHình 28. Trạm làm việc J tiếp tục quá trình truy vấn định tuyếnUT 53
TUHình 29. Cây truy vấn ngoại biên do J xây dựngUT 54
TUHình 30. Trạm làm việc đích D được tìm thấyUT 54
TUHình 31. Mô hình thử nghiệm xác minh hoạt động của thuật toán định tuyếnUT 56
TUHình 32. Thí nghiệm mô phỏng hoạt động của thuật toán ZRP trên hệ mô phỏng
Qualnet
UT 58
TUHình 33. Số lượng gói tin truyền trên từng trạmUT 59
TUHình 34. Lưu lượng gói tin truyền trên mạng có tính di động caoUT 60
TUHình 35. Thời gian trễ trung bình của các gói tinUT 60
TUHình 36. Số lượng gói tin gửi thành côngUT 61
TUHình 37. Số lượng ít gói tin yêu cầu định tuyến được gửi điUT 61
6
TUHình 38. Thiết lập diện tích và thời gian cho thí nghiệm mô phỏngUT 71
TUHình 39. Lựa chọn thuật toán định tuyếnUT 72
TUHình 40. Thiết đặt kích thước vùng định tuyếnUT 72
TUHình 41. Tự động đặt các trạm làm việcUT 72
TUHình 42. Lựa chọn để đặt các trạm bằng tayUT 72
TUHình 43. Chỉ định file cung cấp thông tin di chuyển của các trạm làm việcUT 73
TUHình 44. Chỉ định file thiết lập kết nối và kết quả sau khi chỉ địnhUT 74
TUHình 45. Nhấn nút run để thực hiện thí nghiệmUT 75
TUHình 46. Sử dụng chức năng Run Batch ExperimentUT 75
ad-hoc.
Luận văn đi sâu tìm hiểu một thuật toán định tuyến cho các thiết bị di động trong
môi trường mạng di động không cấu trúc - thuật toán định tuyến theo vùng Zone
Routing Protocol (ZRP)
Phương pháp nghiên cứu
Nhằm đạt được mục đích nghiên cứu của luận văn, tác giả phải tập hợp và nghiên
cứu các tài liệu đề cập đến các vấn liên quan, đã được công bố trên thế giới; các bản
nháp khuyến nghị của tổ chức IETF; các tài liệu trình bày về mạng không dây và các
giao thức cho mạng không dây.
Do không thể thực hiện thí nghiệm trên hệ thống mạng thực, tác giả sử dụng các hệ
mô phỏ
ng NS-2 và Qualnet (phiên bản thương mại của Glomosim) – là các hệ mô
phỏng mạng đã và đang được các nhà nghiên cứu và nhiều trường đại học trên thế giới
tin cậy sử dụng trong các nghiên cứu khoa học và giảng dạy - để làm thí nghiệm.
8
Luận văn cũng kế thừa các thành quả nghiên cứu đã được công nhận của các trung
tâm nghiên cứu, các trường đại học và các tác giả đã từng nghiên cứu các lĩnh vực liên
quan, sát với đề tài của luận văn.
Tóm tắt nội dung các chương
Luận văn được chia làm 3 chương. Chương 1 nêu lên khái niệm về mạng ad-hoc,
ứng dụng của mạng ad-hoc và các vấn đề cần giải quyết. Để đạt được tính nhất quán
về các thuật ngữ sử dụng trong luận văn, một số thuật ngữ cũng được đưa ra.
Chương 2 giới thiệu các thuật toán định tuyến trước và định tuyến theo yêu cầu
trong mạng ad-hoc, làm cơ sở cho việ
c trình bày thuật toán lai ZRP trong chương 3. Ở
đây, luận văn bày sâu về thuật toán DSDV, một đại diện cho loại thuật toán định tuyến
trước. Tương tự, thuật toán AODV được chọn làm đại diện cho loại thuật toán định
tuyến theo yêu cầu và cũng được trình bày kỹ lưỡng. Ưu, nhược điểm của mỗi loại
thuật toán được nêu ra ở phần đánh giá, cuối mỗi phần trình bày về nguyên tắ
thông qua một thiết bị trung gian gọi là Access Point (chính là các trạm tiếp sóng -
Base Station). Các thiết bị này thường kết nối với nhau và với ph
ần còn lại của mạng
bằng đường truyền hữu tuyến nhưng giao tiếp với các máy tính (có cắm vỉ mạng
không dây) bằng sóng vô tuyến. Cũng có khi các Access Point kết nối vô tuyến với
nhau như trong hình 1. Đó là mạng máy tính không dây thông thường. Hình 1. Mạng máy tính kết nối không dây với 2 access point
Với cách kết nối không dây như trên, các trạm làm việc (máy tính, điện thoại di
động,…) sẽ trao đổi số liệu với nhau thông qua các trạm tiếp sóng. Tức là các gói dữ
liệu gửi giữa các trạm làm việc đều được truyền tới trạm tiếp sóng và trạm tiếp sóng sẽ
chịu trách nhiệm chuyển các gói tin này tới trạm đích được chỉ định. Như vậy, trạm
tiếp sóng đồng thời đ
óng vai trò của bộ định tuyến.
10
Mạng ad-hoc
Trong nhiều trường hợp, điều kiện không cho phép xây dựng hệ thống trạm tiếp
sóng, chẳng hạn khi thiết lập hệ thống liên lạc phục vụ cứu nạn sau thiên tai, hoặc
trong các trận chiến sử dụng công nghệ cao mà các vũ khí, khí tài và ngay cả các chiến
binh cần thường xuyên liên lạc với nhau. Để giải quyết vấn đề, người ta đưa ra giải
pháp xây dựng mạng, trong đó, mỗi trạm làm vi
ệc không dây đồng thời đảm trách cả
chức năng của bộ định tuyến. Các trạm làm việc gửi số liệu cho nhau thông qua các
trạm khác, không cần có các trạm kết nối trung gian (Base Station). Một mạng như vậy
được gọi là Mobile Ad-hoc Network (MANET) hay mạng di động không cấu trúc,
trong luận văn, gọi tắt là mạng ad-hoc.
• Trong các ứng dụng khác (điề
u khiển công nghệp, mạng taxi, mạng kết nối các
tàu thuyền,…)
Hình 3. Ứng dụng rộng rãi của mạng ad-hoc trong cuộc sống
1.3. Đặc điểm của mạng ad-hoc
Mạng ad-hoc có các đặc điểm sau:
• Có cấu trúc động: Do tính di động của tất cả các trạm làm việc trong mạng, sự
thay đổi về cấu trúc mạng xảy ra thường xuyên. Các kết nối giữa các trạm làm
việc có thể hình thành và mất đi nhanh chóng, phụ thuộc vào tốc độ và hướng di
chuyển của các trạm làm việc. Điều này khiến cho việc truyền số liệu giữa các
trạm làm việc g
ặp nhiều khó khăn. Chúng phải thường xuyên định tuyến lại
trong suốt quá trình truyền số liệu và không sử dụng được hướng truyền mặc
định (default route) như đối với mạng hữu tuyến và mạng di động thông
12
thường. Do vậy, vấn đề định tuyến, vốn đã rất phức tạp trong mạng hữu tuyến
và mạng không dây thông thường, nay còn phức tạp hơn rất nhiều trong mạng
ad-hoc.
• Dung lượng đường truyền thấp: Các thiết bị di động kết nối với nhau qua sóng
vô tuyến, do vậy dung lượng đường truyền bị hạn chế, thấp hơn rất nhiều so với
dung lượng truyền trên các
đường truyền hữu tuyến. Khi các trạm làm việc càng
cách xa nhau, tín hiệu vô tuyến càng yếu và do đó dung lượng truyền cũng giảm
dần.
• Mức năng lượng cung cấp cho các trạm làm việc hạn chế: Do tính chất di động
của các trạm làm việc, pin là nguồn cung cấp năng lượng chủ yếu. Do vậy các
thiết bị di động phải được thiết kế (cả phần cứng lẫn phần mề
m) sao cho mức
1.4. Một số khái niệm sử dụng trong luận văn
Trạm làm việc
Trong mạng máy tính, các máy tính được kết nối với nhau để trao đổi thông tin. Các
máy tính là thành phần quan trọng nhất trong mạng máy tính. Nhưng để kết nối các
máy tính này, cần có các thiết bị kết nối mạng như bộ định tuyến, bộ chuyển mạch,…
Để có thể đảm trách được nhiệm vụ đó, chúng cũng phải truyền, nhận, xử lý thông tin
ở một mức độ nào đấy.
Trong mạng truyền thông nói chung, mỗi thiế
t bị như vậy (máy tính, bộ định tuyến,
bộ chuyển mạch,…) được gọi với tên chung là trạm làm việc (node). Tuy nhiên, trong
mạng ad-hoc, có thể coi các trạm làm việc chính là các máy tính vì chúng đảm trách
chức năng của tất cả các thiết bị còn lại. Trong các ứng dụng thực tế của mạng ad-hoc,
trạm làm việc là bất kỳ thiết bị nào có khả năng giao tiếp với các thiết bị mạng khác và
chuyển tiế
p gói tin trong mạng.
Giá trị thước đo định tuyến - bước nhảy
Trong mạng máy tính thường có nhiều đường kết nối giữa hai trạm làm việc. Vì vậy
các bộ định tuyến (router) cần phải chọn đường kết nối nào để việc truyền dữ liệu đạt
hiệu quả cao nhất. Người ta đưa ra khái niệm thước đo định tuyến (metric) để đánh giá
ưu thế của các đường kết nối. Giá trị này có thể là tổng hợp của nhiều y
ếu tố như tốc
độ tối đa của đường truyền, độ trễ truyền tin, tỷ lệ các gói tin bị mất,… nhưng cũng có
thể chỉ dựa vào số bước nhảy (hop count) trong đường kết nối giữa hai trạm làm việc. Hình 4a: Khoảng cách 1 hop Hình 4b: Khoảng cách 2 hop
Hình 4. Giá trị thước đo định tuyến tính theo số bước nhảy
Nếu để đến được trạm làm việc đích, gói tin phải được chuyển qua N+1 bộ định
tuyến khác nhau thì nói hai trạm làm việc cách nhau N bước nhảy, hay đường kết nối
tiếp các gói số liệu tới trạm làm việc đích.
Gói tin yêu cầu định tuyến – gói tin trả lời định tuyến – gói tin định tuyến - xử lý truy
vấn
Trước khi truyền số liệu, trạm làm việc nguồn cần phải tìm được đường đi tới trạm
làm việc đích. Để thực hiện việc này, chúng phát đi các gói tin yêu cầu định tuyến.
Khi một trạm làm việc biết đường đi tới trạm làm việc đích, nó sẽ trả lời trạm làm
việc nguồn bằng gói tin trả lời định tuyến cho biết đườ
ng đi tới trạm làm việc đích.
Gói tin định tuyến được sử dụng để chỉ tất cả các gói tin truyền trên mạng nhằm
mục đích tìm đường từ trạm làm việc nguồn đến tram làm việc đích, bao gồm cả các
gói tin yêu cầu định tuyến, gói tin trả lời định tuyến và các gói tin cập nhật thông tin
định tuyến. Các gói tin định tuyến không chứa số liệu cần truyền.
Nhữ
ng hành động mà một trạm làm việc thực hiện khi nhận được một gói tin yêu
cầu định tuyến (kiểm tra gói tin yêu cầu định tuyến, tìm thông tin định tuyến, chuyển
tiếp gói tin yêu cầu định tuyến…) được gọi chung là xử lý truy vấn.
15
Chương 2. Các thuật toán định tuyến trong mạng ad-hoc
Đã có rất nhiều thuật toán định tuyến dành cho mạng ad-hoc được đề xuất. Mỗi
thuật toán đều có ưu, nhược điểm riêng và được cải tiến dần để hạn chế các nhược
điểm, đồng thời phát huy ưu điểm vốn có. Người ta có thể phân loại các thuật toán
định tuyến dành cho mạng ad-hoc theo các đặc điểm về thời điểm định tuyến
(proactive, reactive), về
tính phân cấp (hierachical), tính sử dụng dữ liệu địa lý
(geographical), tính tiết kiệm năng lượng (power aware), v.v [14].
Xét theo thời điểm định tuyến, ta có hai loại thuật toán định tuyến: định tuyến trước
(proactive routing protocol) và định tuyến theo yêu cầu (reactive routing protocol).
Ngoài ra, nhiều thuật toán kết hợp hai loại trên cũng được đề xuất. Luận văn sẽ trình
2.1.2. Nguyên tắc hoạt động
2.1.2.1. Thuật toán phân phối Bellman-Ford
Thuật toán phân phối Bellman-Ford (còn được gọi là thuật toán vector khoảng cách
- Distance Vector) đã được sử dụng hiệu quả trong một số thuật toán định tuyến cho
mạng hữu tuyến, chẳng hạn RIP (Routing Information Protocol), IGRP (Internet
Gateway Routing Protocol – do Cisco phát triển), RTMP (Routing Table Maintenance
Protocol – do Apple phát triển) và một số thuật toán định tuyến dành cho mạng không
dây, trong đó có DSDV [1], [15].
Trong thuật toán phân phối Bellman-Ford, mỗi trạm làm việc S lưu giữ một bảng
định tuyến, trong đó chỉ rõ để tới được mỗi trạm làm việc đích D trong mạng thì phải
chuyển gói tin số liệu qua trạm làm việc lân cận N nào của S và khoảng cách tương
ứng theo đường đi đó, với khoảng cách là quãng đường ngắn nhất từ S tới D, thường
tính bằng số bước nhảy. N khi đó sẽ là trạm làm việc kế tiếp của S trong đường đi
ngắn nhất t
ừ S tới D nêu trên.
Để cập nhật các thông tin về đường đi ngắn nhất, mỗi trạm làm việc định kỳ trao
đổi thông tin trong bảng định tuyến của nó với các trạm làm việc lân cận. Căn cứ vào
thông tin định tuyến do các trạm làm việc lân cận gửi đến, S sẽ biết được đường đi
ngắn nhất tới mỗi trạm làm việc khác trong mạng, thông qua các trạm làm việc lân
cận. Chẳng h
ạn, với mỗi trạm làm việc D trong mạng, S sẽ chọn một trạm làm việc N
lân cận với S làm trạm kế tiếp trong đường đi tới D, sao cho khoảng cách từ N tới D là
ngắn nhất so với khoảng cách từ các trạm làm việc lân cận còn lại của S tới D. Thông
tin này được lưu lại trong bảng định tuyến của S (là một dòng của bảng định tuyến), và
sau đó sẽ được S trao đổ
i với các trạm làm việc lân cận của nó tại thời điểm trao đổi
thông tin định tuyến định kỳ lần tiếp theo.
Hình 5 dưới đây là một thí dụ minh họa. Trong minh hoạ này, trạm làm việc 1 kết
nối trực tiếp với D (là lân cận của D). Dĩ nhiên, nó biết được đường đi ngắn nhất từ nó
3 4 2
4 4 1
D 2 3
… … …
Lưu ý rằng, trong thuật toán này, bảng định tuyến chỉ lưu một đường đi ngắn nhất
đến mỗi trạm làm việc trong mạng.
Thuật toán phân phối Bellman-Ford có ưu điểm là việc tính toán đơn giản và hiệu
quả, do tính chất phân phối của nó (tất cả các trạm làm việc đều lưu thông tin định
tuyến và việc tính toán tại mỗi trạm làm việc dựa vào thông tin do các trạm làm việc
lân cận cung c
ấp).
18
Tuy nhiên, thuật toán cũng có nhược điểm là sự hội tụ chậm. Tức là khi có sự thay
đổi về thông tin định tuyến, do tính chất định kỳ trong việc trao đổi thông tin nên phải
mất một thời gian, toàn bộ các trạm làm việc trong mạng mới có được thông tin định
tuyến chính xác (đạt trạng thái hội tụ - convergence). Tại một thời điểm nào đó, khi
thông tin định tuyến trên toàn mạng chưa hội tụ có thể
nảy sinh hiện tượng gói tin bị
chuyển vòng quanh trên mạng (routing loop). Hiện tượng này thường xảy ra trong các
mạng có nhiều kết nối không ổn định.
2.1.2.2. Thuật toán định tuyến DSDV
DSDV (Destination Sequence Distance Vector routing protocol) được C. Perkins đề
xuất năm 1994, sử dụng thuật toán vector khoảng cách (hay thuật toán Bellman-Ford)
trình bày ở trên với một số sửa đổi bổ sung nhằm tránh hiện tượng các gói tin bị gửi
vòng quanh (loop) [3], [17]. DSDV đã được tích hợp trong phần mềm mô phỏng NS2.
Trong mạng ad-hoc sử dụng thuật toán định tuyến DSDV, mỗi trạm làm việc sẽ lưu
giữ một bảng định tuyến chứa các thông tin về đường đi tới các tất cả các trạm làm
việc khác mà nó có thể kết nối được. Một bảng định tuyến được thể hiện như trong
tế xây dựng thuật toán, số thứ tự có thể chỉ là một số tự nhiên thông thường mà
không cần kèm thêm các giá trị đánh dấu cho biết tr
ạm làm việc đã đưa ra nó.
Cập nhật thông tin định tuyến
Mỗi trạm làm việc định kỳ truyền đi các thông tin định tuyến tới các trạm làm việc
lân cận theo cách quảng bá. Do tính chất thường xuyên thay đổi về cấu trúc của mạng
ad-hoc, thời gian giữa các lần quảng bá thông tin định tuyến của mỗi trạm làm việc
cần đủ ngắn để các trạm có được thông tin định tuyến chính xác tới mỗi trạm khác
trong mạng.
Để giảm lượng thông tin quảng bá trên mạng, thu
ật toán sử dụng hai cách cập nhật
thông tin định tuyến: cập nhật toàn phần (full dump) và cập nhật tức thời (hay cập nhật
tăng tiến - incremental). Cập nhật toàn phần được sử dụng khi một trạm làm việc
muốn quảng bá toàn bộ bảng định tuyến. Cập nhật tức thời được thực hiện giữa các lần
cập nhật toàn phần, khi có các thay đổi đáng kể và lượ
ng thông tin cần cập nhật là đủ
nhỏ. Các thông tin cập nhật này sẽ ngay lập tức được truyền đi. Chẳng hạn, khi có sự
thay đổi về giá trị thước đo định tuyến của một đường đi thì thay đổi đó được coi là
đáng kể và ngay sau khi thông tin đạt được tính ổn định (được giải thích cụ thể hơn
trong phần trì hoãn quảng bá và thời gian chờ ổn định ở
phần sau), nó phải được
quảng bá ngay để cập nhật cho các trạm làm việc khác trong mạng. Khi thông tin mới
nhận có giá trị thước đo định tuyến giữ nguyên, chỉ có thay đổi về số thứ tự định tuyến
thì sự thay đổi đó không được coi là đáng kể và do vậy thông tin này không cần thiết
phải được quảng bá ngay.
Như đã nói, lượng thông tin cập nhật tức thời phải đủ nhỏ
để có thể chỉ cần sử dụng
một gói dữ liệu của mạng (network protocol data unit - NPDU) trong việc truyền dữ
liệu. Nếu lượng thông tin cập nhật vượt quá một gói dữ liệu, phương thức cập nhật
toàn phần sẽ được sử dụng. Khi đó toàn bộ thông tin trong bảng định tuyến sẽ được
lấy làm thước đo định tuyến thì thông tin về đường đi nào (tới cùng trạm làm việc
đích, có cùng số thứ tự định tuyến) có số bước nhảy ít nhất sẽ được chọn. Giá trị thước
đo định tuyến t
ăng lên nếu quãng đường tới trạm đích phải qua nhiều trạm làm việc.
Nếu tính theo số bước nhảy thì qua mỗi trạm làm việc giá trị thước đo định tuyến sẽ
tăng thêm 1 bước nhảy.
Trì hoãn quảng bá và thời gian chờ ổn định
Đôi khi, một trạm làm việc trong mạng nhận được thông tin có cùng số hiệu định
tuyến, nhưng giá trị thước đo định tuyến lại khác nhau. Trường hợp này thường xảy ra
khi mạng có kích thước lớn và mức độ thường xuyên của việc cập nhật thông tin định
tuyến thấp, hoặc, khi thời gian giữa các lần cập nhật của các trạm làm việc có sự chênh
lệch lớn.
Hình 7 là một thí d
ụ minh họa một mạng ad-hoc, trong đó, F kết nối trực tiếp với
hai nhóm riêng rẽ các trạm làm việc. Số lượng trạm làm việc trong nhóm 2 nhiều hơn
hẳn so với nhóm 1. A cũng kết nối với hai nhóm trên thông quan B và C. Giả sử mỗi
trạm làm việc cập nhật thông tin định tuyến với tần suất thấp (chẳng hạn, khoảng l
lần/15 giây); B biết một đường tới F qua 12 bước nhảy, trong khi C biế
t đường đi tới F
chỉ qua 11 bước nhảy. Thông tin truyền từ B tới A nhanh hơn so với từ C tới A. Khi
đó, A sẽ nhận được thông tin định tuyến đến F do B quảng bá trước khi nhận được
thông tin do C quảng bá. Việc này có thể xảy ra thường xuyên, mỗi khi F đưa ra số thứ
tự định tuyến mới. Một trong những nguyên nhân là số lượng các trạm trong mỗi
nhóm làm việc cũng ảnh hưởng đến th
ời gian nhận được thông tin cập nhật tại A, do
sự lựa chọn lần lượt thông tin đưa vào gói tin cập nhật tức thời, như đã nói trong phần
Cập nhật thông tin định tuyến ở trên. Vậy, thông tin định tuyến tới F mà A nhận được
từ B sẽ không tốt (vì có số bước nhảy lớn hơn) so với thông tin A nhận được sau đó, từ
C.
21
quảng bá thông tin định tuyến có thể được lấy gấp 2 lần thời gian chờ ổn định trung
bình. Gọi khoảng thời gian này là thời gian trì hoãn quảng bá.
Như vậy, khi một trạm làm việc nhận được thông tin định tuyến có số thứ tự lớn
hơn, chứng tỏ thông tin đó mới hơn, nó sẽ dùng thông tin này để lập tức quyết định
đường đi cho gói tin cần được gử
i nhưng chưa vội quảng bá thông tin định tuyến này
ngay. Nói cách khác, thông tin định tuyến dùng để chuyển gói tin không phải lúc nào
22
cũng là thông tin dành để quảng bá. Do đó, mỗi trạm làm việc sẽ lưu hai bảng định
tuyến cho hai mục đích tương ứng.
Hiện tượng mất liên kết
Trong mạng ad-hoc, khi các trạm làm việc di chuyển sẽ gây ra việc mất các liên kết.
Việc mất liên kết có thể được phát hiện nhờ vào giao thức ở lớp 2 (layer 2 protocol)
của mô hình OSI. Hoặc khi các trạm làm việc lân cận không thấy thông tin định tuyến
được tiếp tục gửi quảng bá, chúng cũng sẽ coi là đã xảy ra mất liên kết. Một liên kết bị
mất (break) sẽ được đánh dấu bằng cách đặt giá trị thướ
c đo định tuyến bằng ∞ (là một
giá trị bất kỳ lớn hơn giá trị lớn nhất mà thuật toán quy ước). Khi một trạm làm việc A
phát hiện ra liên kết tới trạm làm việc lân cận B bị mất thì bất kỳ đường đi nào từ A tới
các trạm làm việc khác, mà trạm kế tiếp là B, cũng sẽ bị đánh dấu là mất kết nối, bằng
cách đặt giá tr
ị thước đo định tuyến bằng ∞. Destination Next Hop Hops Seq. No
A A 0 A-846
B B
∞
A-561
23
ứng với mỗi trạm làm việc đích, như đã nói ở trên, rồi mới được quảng bá, dù cũng
được coi là thông tin có chứa thay đổi đáng kể.
Ví dụ trong hình 9 sẽ minh họa thêm hoạt động của mạng ad-hoc sử dụng thuật toán
định tuyến DSDV, trong đó, trạm làm việc C sẽ di chuyển xa khỏi B và đến vùng lân
cận của G và H. Hình 9. Mạng ad-hoc với sự di chuyển của trạm làm việc
Ta chú ý đến trạm làm việc A. Ban đầu, trước khi C di chuyển, bảng định tuyến của
A chứa đầy đủ các thông tin định tuyến tới mọi trạm làm việc trong mạng.
Destination Next Hop Hops Seq. No
C B 2 C-406
B B 1 B-128
D B 2 D-564
A A 0 A-710
F E 2 F-392
E E 1 E-076
G E 2 G-128
H E 3 H-050
Bảng định tuyến trên cho thấy rằng không có hiện tượng mất kết nối, vì số thứ tự
định tuyến của các dòng định tuyến đều mang giá trị chẵn.
Bảng định tuyến dành để quảng bá của trạm làm việc A sẽ như sau:
Destination Hops Seq. No
C 2 C-406
B 1 B-128
Bảng định tuyến dành để quảng bá của A:
Destination Hops Seq. No
A 0 A-820
C 3 C-516
B 1 B-238
D 2 D-674
F 2 F-502
E 1 E-186
G 2 G-238
H 3 H-160
So với bảng định tuyến trước đó, chỉ có thông tin định tuyến tương ứng với trạm
làm việc C có thay đổi về giá trị thước đo định tuyến, còn thông tin định tuyến tương
ứng với các trạm làm việc khác chỉ thay đổi về số thứ tự định tuyến. Thông tin định
tuyến tới trạm làm việc C sẽ được ngay lập tức cập nhật theo phương thức c
ập nhật tức
thời, vì đó là sự xuất hiện trở lại thông tin về đường đi đến trạm mà trước đó được
thông báo là mất kết nối.
2.1.3. Đánh giá
Bằng việc định tuyến trước, mỗi trạm làm việc trong mạng thường xuyên trao đổi
thông tin định tuyến cho nhau nên thông tin định tuyến luôn sẵn sàng. Mỗi khi một
25
trạm làm việc muốn gửi số liệu, nó có thể lấy ngay thông tin định tuyến đã lưu giữ
trong bảng định tuyến để quyết định đường đi cho gói tin.
Tuy nhiên, thuật toán DSDV nói riêng, và các thuật toán định tuyến trước nói
chung, có các nhược điểm sau:
• Trong khi cấu trúc mạng thay đổi thường xuyên thì các thông tin về sự thay đổi
này cần nhiều thời gian để có thể đến được tất cả các trạm làm việc trong m
Thuật toán định tuyến theo yêu cầu (reactive routing protocol hay on-demand
routing protocol) là các thuật toán cho phép trạm làm việc nguồn xác định đường đi
đến trạm làm việc đích chỉ khi có nhu cầu truyền số liệu. Trong số các thuật toán định
tuyến theo yêu cầu, người ta thường kể đến AODV (Ad-hoc On Demand Distance
Vector routing protocol), TORA (Temporally-Ordered Routing Algorithm routing
protocol), DSR (Dynamic Source Routing protocol).
Chúng ta sẽ xem xét một đại diện cho các thuật toán định tuyến theo yêu cầu: thuật
toán định tuyến AODV. Như đã biết, AODV là thuật toán đượ
c C. Perkins phát triển
từ thuật toán DSDV [4], [5], [6], [12], [16].
Copyright: Tài liệu đại học ©