Đồ án Đánh giá thông lượng của các giao thức định tuyến trong mạng Ad hoc

OPTIMIZED LINK STATE ROUTING(OLSR) OLSR là giao thức định tuyến theo bảng và là một sự tối ưu của giao thức trạng thái liên kết cổ điển, hoàn toàn thích hợp cho mạng di động Ad hoc. OLSR tối thiểu hóa tiêu đề định tuyến bằng cách chỉ sử dụng các nút được chọn để phát tràn lan lưu lượng điều khiển, được gọi là Chuyển tiếp đa điểm MPR (Multipoint Relay). Kỹ thuật này giảm đáng kể số lượng yêu cầu truyền lại để phát tràn lan một bản tin tới tất cả các nút trong mạng. Bầu chọn Multipoint relay Hình 2.3 Quá trình phát tràn lan bản tin quảng bá MPR là để tối thiểu hóa overhead khi phát tràn lan bản tin trong mạng bằng cách giảm số lần truyền lại trong cùng một vùng. Mỗi nút trong mạng lựa chọn một tập hợp các nút hàng xóm trực tiếp của nó để làm MPR. Hàng xóm của nút A mà không nằm trong tập hợp MPR của A có thể nhận và xử lý các bản tin quảng bá nhưng không thể truyền các bản tin quảng bá nhận được từ A. Mỗi nút lựa chọn tập hợp MPR từ những hàng xóm trực tiếp (one-hop) của nó. Tập hợp MPR của nút A, kí hiệu là MPR(A), là tập con của tập hợp các hàng xóm trực tiếp của A, phải thỏa mãn những điều kiện sau: mỗi nút trong hàng xóm hai bước (two-hop) của A phải có một liên kết trực tiếp đến MPR(A). Tập hợp MPR càng nhỏ thì tiêu đề lưu lượng điều khiển của giao thức định tuyến càng nhỏ. Mỗi nút phải duy trì thông tin về tập hợp hàng xóm mà chúng chọn làm MPR. Tập hợp này gọi là “MPR selector set” của một nút. Hình 2.4 Bầu chọn MPR Trong OLSR, mỗi nút truyền bản tin Hello định kỳ (ví dụ một giây một bản tin) trên mỗi giao diện của nút. Mục đích chính của bản tin Hello cho phép mỗi nút có thể khám phá tuyến trực tiếp tới hàng xóm của nó. Bản tin Hello được quảng bá từng chặng một (hop-by-hop) và phải không được truyền trước đó. Bản tin Hello bao gồm tên của nút khởi tạo, hàng xóm trực tiếp mà nút khởi tạo truyền bản tin khám phá, và các nút mà nút khởi tạo chọn làm MPRs. Khi một nút nghe thấy bản tin Hello, nó kiểm tra liệu bản tin đó có phải được phát sinh từ hàng xóm mới hay không, và nếu đúng, nút sẽ cập nhật vào danh sách hàng xóm trực tiếp của nút. Bản tin Hello rất quan trọng trong việc hỗ trợ khái niệm MPR. Mỗi nút kiểm tra bản tin Hello nhận được từ hàng xóm của nó để xem nó liệu có được lựa chọn làm MPR của bất kỳ hàng xóm nào không. Nếu vậy, nút sẽ phát tràn lan các cập nhật định tuyến được phát sinh từ các hàng xóm mà đã chọn nó là MPR. Mỗi nút cũng có thể khám phá liệu các nút có là hàng xóm hai bước từ bản tin Hello, bởi vì danh sách các hàng xóm hai bước đã được liệt kê trong bản tin Hello của nút hàng xóm trực tiếp của nó. Mỗi nút lựa chọn MPR trên cơ sở hàng xóm hai bước, do vậy mỗi hàng xóm hai bước phải nhận được bản tin MPR. Truyền bá bản tin điều khiển topo (Topology control) Bản tin điều khiển topo được truyền đi với mục đích cung cấp cho mỗi nút trong mạng các thông tin liên kết trạng thái đầy đủ để cho phép tính toán được tuyến đường. Tính toán tuyến Thông tin trạng thái liên kết đưa ra được thực hiện thông qua trao đổi định kỳ các bản tin, cũng giống như cấu hình giao diện của các nút, bảng định tuyến của mỗi nút có thể được tính toán. DYNAMIC SOURCE ROUTING (DSR) Giao thức định tuyến nguồn động DSR là giao thức định tuyến đơn giản và hiệu quả. Giao thức này được thiết kế để sử dụng trong các mạng Ad hoc vô tuyến đa chặng có tốc độ di chuyển cao của các nút. Các nút này phối hợp với nhau để chuyển tiếp các gói tin. Do vậy gói tin có thể được chuyển đến các nút không nằm trong vùng phủ sóng của chính nút đó. Khi các nút trong mạng di chuyển, tham gia hoặc rời khỏi mạng thì toàn bộ các thủ tục định tuyến được xác định và duy trì một cách tự động bởi giao thức định tuyến DSR. DSR bao gồm 2 cơ chế cơ bản: Khám phá tuyến (Route Discovery) và Duy trì tuyến (Route Maintenance). Khám phá tuyến và Duy trì tuyến hoạt động hoàn toàn theo yêu cầu. Định tuyến nguồn DSR phát hiện và sử dụng các tuyến nguồn. Nút gửi tin sẽ phải nắm đươc toàn bộ thông tin về trình tự sắp xếp của các chặng (vị trí các nút) của mạng tới một nút đích. Mỗi gói tin được định tuyến sẽ mang thông tin về danh sách các chặng này trong tiêu đề. Ưu điểm quan trọng của thủ tục định tuyến nguồn là các nút trung gian không cần phải duy trì việc cập nhật thông tin định tuyến khi chuyển tiếp các gói tin bởi vì bản thân các gói đã mang thông tin quyết định việc định tuyến (danh sách đầy đủ các nút theo trình tự mà gói phải đi qua). Việc tập hợp thông tin về topo mạng tại nút nguồn của mỗi gói cho phép nút nguồn phân phát các gói tin một cách hiệu quả trong mạng. Điều này rất thích hợp với việc quản lý tài nguyên trong mạng Ad hoc. Giao thức định tuyến dựa trên các tuyến nguồn còn có thêm 2 lợi ích. Thứ nhất, giao thức có thể chứng minh được một cách đơn giản tính không lặp vòng bởi vì tuyến nguồn được sử dụng để điều khiển định tuyến các gói. Thứ hai, mỗi tuyến nguồn là một bản kê sẵn về một đường truyền cụ thể, tin cậy để truyền các thông tin qua mạng. DSR sử dụng các tuyến nguồn và mỗi gói được định tuyến dựa trên một tuyến nguồn khám phá được, tuy nhiên những cải thiện gần đây đối với DSR đã cho phép hầu hết các gói tin không phải mang theo phần tiêu đề chứa thông tin đầy đủ về tuyến nguồn. Khám phá tuyến Khám phá tuyến được thực hiện bằng cách phát tràn lan yêu cầu qua mạng để tìm kiếm một tuyến tới đích nào đó. Trong dạng đơn giản nhất, nút nguồn A muốn khám phá một tuyến tới nút đích D thì A sẽ phát quảng bá gói tin Yêu cầu tuyến RREQ và gói này tiếp tục được quảng bá bởi các nút trung gian cho đến khi nó đến được nút đích D. Trong cơ chế này, nhiều tối ưu hóa được sử dụng để giới hạn tần số và phạm vi của các Khám phá tuyến. Khi một nút S muốn gửi một gói tin đến D, đầu tiên nó sẽ đặt vào phần tiêu đề của gói tin đó một tuyến nguồn trong đó chỉ ra thứ tự của các chặng mà gói tin sẽ phải đi qua. Thông thường, nút S sẽ đạt được một tuyến nguồn thích hợp thông qua việc tìm kiếm trong Bộ nhớ tuyến của nó các tuyến đã biết trước đây. Tuy nhiên nếu không tìm thấy tuyến nào trong Bộ nhớ tuyến, nó sẽ khởi tạo thủ tục Tìm kiếm tuyến động để tìm ra một tuyến nguồn tới D. Trong trường hợp này ta gọi nút S là nút nguồn còn nút D là nút đích trong thủ tục Khám phá tuyến. Trước khi khởi tạo một gói tin RREQ, nút nguồn chọn một nhận dạng yêu cầu (Request_id) đặt trong gói tin RREQ. Cặp là duy nhất. ^ "A" ^ "A,B" ^ "A,B,C" ^ "A,B,C,D" | id=2 | id=2 | id=2 | id=2 +-----+ +-----+ +-----+ +-----+ +-----+ | A |---->| B |---->| C |---->| D |---->| E | +-----+ +-----+ +-----+ +-----+ +-----+ | | | | v v v v Hình 2.5 Khám phá tuyến trong DSR Hình 2.5 minh họa quá trình Khám phá tuyến đơn giản, nút A cố gắng khám phá tuyến tới nút E. Để khởi đầu Khám phá tuyến, A truyền một tin báo RREQ. Mỗi tin báo RREQ nhận dạng nút nguồn và đích của Khám phá tuyến. Nhận dạng yêu cầu được xác định bởi nút nguồn của Yêu cầu. Một RREQ bao gồm một bản ghi danh sách địa chỉ của từng nút trung gian mà tin báo RREQ đã đi qua. Giá trị ban đầu của bản ghi tuyến là một danh sách trống. Khi một nút nhận được bản tin RREQ này (ví dụ như nút B trong ví dụ), nếu nó là đích của Khám phá tuyến, nó sẽ gửi lại bản tin Trả lời tuyến RREP tới khởi tạo của Khám phá tuyến, chuyển bản copy của bản ghi tuyến được cộng dồn từ RREQ; khi nút nguồn nhận được RREP, nó cất giữ tuyến này trong Bộ nhớ tuyến để sử dụng khi gửi các gói tin tiếp theo tới đích này. Mặt khác, nếu một nút nhận RREQ mà đã nhận được một bản tin RREQ khác từ nút nguồn, mang theo những nhận dạng yêu cầu và địa chỉ đích giống nhau hoặc nếu địa chỉ riêng của nút này đã nằm trong báo cáo tuyến của RREQ, nó sẽ từ chối Yêu cầu. Nếu không, nút này sẽ gắn địa chỉ riêng của nó vào bản ghi tuyến trong bản tin RREQ và tiếp tục quảng bá nó. Trong ví dụ, nút B sẽ quảng bá bản tin RREQ, nó sẽ được nhận ở nút C, nút C và nút D cũng vậy, nó sẽ broadcast Yêu cầu, kết quả là copy của Yêu cầu sẽ được nhận bởi nút E. Trong việc bản tin RREP trở lại nút nguồn trong thủ tục Khám phá tuyến, chẳng hạn nút E trả lời nút A trong hình 2.5, nút E sẽ kiểm tra Bộ nhớ tuyến của nó xem liệu có một tuyến ngược về nút A, và nếu tìm được nó sẽ sử dụng tuyến này làm tuyến nguồn để phân phát các gói tin bao gồm cả gói RREP. Nếu không tìm được một tuyến ngược trở lại A, E có thể thực hiện thủ tục Khám phá tuyến từ nó tới A. Để tránh khả năng quay lại vô hạn có thể của các Khám phá tuyến, nó sẽ chèn bản tin RREP vào chính bản tin RREQ của nó đối với nút A. Sử dụng cơ chế này nó cũng có khả năng cõng theo các gói dữ liệu nhỏ khác ví dụ như gói TCP SYN trên một bản tin RREQ. Nút E còn có thể đảo vị trí sắp xếp của các chặng trong bản ghi tuyến và sử dụng tuyến đã đảo vị trí này như một tuyến nguồn đối với các gói tin mang bản tin RREP của chính nó. Khi khởi tạo một Khám phá tuyến, nút đang gửi sẽ giữ lại bản sao của gói tin ban đầu trong bộ nhớ đệm nội bộ (Send Buffer) gọi là bộ đệm gửi. Ngoài ra Send Buffer còn chứa các bản sao của các gói tin không truyền đi được do chưa tìm ra một tuyến nguồn tới đích. Mỗi gói trong Send Buffer được gán cho một nhãn thời gian chỉ ra thời gian chúng tồn tại trong Buffer và gói tin sẽ bị loại bỏ sau khi thời gian lưu lại trong Send Buffer quá hạn; để Send Buffer không bị tràn, kĩ thuật FIFO hoặc kĩ thuật tương đương khác có thể được sử dụng để truyền các gói tin đó đi trược khi chúng hết hạn. Trong trường hợp gói tin còn lưu lại trong Send Buffer mà chưa truyền đi được thì thỉnh thoảng nút mạng lại thiết lập mới thủ tục Khám phá tuyến tùy theo địa chỉ đích của các gói. Tuy nhiên, tần suất khởi tạo các Khám phá tuyến mới cần phải được giới hạn do có thể xảy ra trường hợp đích của thủ tục khởi tạo tuyến đã thay đổi và không thể tới được. Trên thực tế, do giới hạn về phạm vi truyền dẫn vô tuyến và sự di chuyển của các nút trong mạng nên nhiều khi cấu trúc mạng bị phân mảnh, nghĩa là không có thứ tự sắp xếp của các chặng mà qua đó gói tin được chuyển tiếp tới đích. Kiều phân mảnh như vậy có thể hiếm gặp hoặc phổ biến tùy thuộc vào kiểu di chuyển và mật độ của các nút trong mạng. Trong trường hợp với mỗi gói tin, một thủ tục Khám phá tuyến được khởi tạo thì một số lớn các gói RREQ không hữu ích được truyền từ nút này tới tất cả các nút khác trong mạng. Để giảm phần phụ trội tiêu đề do các Khám phá tuyến trên người ta phải giới hạn tần suất khởi tạo các Khám phá tuyến từ một nút bất kì đến cùng một đích. Nút chỉ được phép khởi tạo Khám phá tuyến mới sau khi đợi hết khoảng thời gian tối thiểu cần thiết để có thể thiết lập thủ tục Khám phá tuyến mới. Từ kết quả của việc kiểm tra bản sao các tuyến nguồn ghi được, thuật toán Khám phá tuyến đã ngăn chặn được việc lặp các RREQ trong mạng. Đó là một thuộc tính hiệu chỉnh quan trọng và là nguyên nhân tạo ra thuộc tính không lặp vòng của DSR. Sử dụng các nhận dạng yêu cầu là một tối ưu đơn giản khi đó các RREQ ban đầu trải rộng hướng ra phía ngoài so với nút nguồn và rút bớt số các gói RREQ bao quanh bộ khởi tạo. Duy trì tuyến Khi gửi hoặc chuyển tiếp một gói tin tới đích D nào đó sử dụng tuyến nguồn, mỗi nút sẽ có nhiệm vụ giám sát và khẳng định rằng gói tin đó đã đến được chặng tiếp theo trên tuyến nguồn hay chưa; gói tin sẽ được truyền lại (sau một số lần cho phép) cho tới khi nút này nhận được khẳng định rằng nó đã đến được nút tiếp theo.Ví dụ trường hợp được minh họa trong hình 2.6 dưới đây: nút A gửi một gói tin tới E sử dụng một tuyến nguồn thông qua các nút trung gian B, C và D. Trong trường hợp này nút A chịu trách nhiệm về việc nhận gói tin ở nút B, nút B chịu trách nhiệm việc nhận gói tin ở nút C, nút C lại chịu trách nhiệm về việc nhận gói tin ở nút D,… và cứ như thế đến nút cuối cùng nút D phải chịu trách nhiệm về việc nhận gói tin ở nút E. Trong nhiều trường hợp khẳng định việc nhận gói tin không ảnh hưởng gì đối với giao thức DSR do thực tế đây là một phần của các thủ tục lớp MAC. Hình 2.6 Duy trì tuyến, nút C không thể chuyển tiếp từ A đến E qua liên kết tới bước nhảy tiếp theo D của nó Nếu cơ chế này không tồn tại và sẵn có ở các nút thì khi đó nút gửi tin sẽ dùng một bít thông tin trong phần tiêu đề của gói tin để yêu cầu một phúc đáp từ nút tiếp theo thông qua phần mềm đặc biệt trong DSR. Thông thường phúc đáp qua phần mềm này được truyền trực tiếp tới nút gửi tin. Tuy nhiên nếu đường liên kết giữa hai nút là liên kết đơn hướng thì phúc đáp này có thể phải đi qua rất nhiều chặng khác nhau để quay lại nút gửi tin Nếu gói tin được truyền lại qua một số chặng và vượt quá số lần cực đại cho phép mà vẫn chưa nhận được khẳng định từ nút tiếp theo, nút này sẽ gửi bản tin báo lỗi tuyến RERR quay trở lại nút đã gửi bản tin ban đầu để xác minh tuyến bị lỗi từ nút nào. Ví dụ trong hình 2.6 trên : nếu nút C không thể truyền tin đến nút D tiếp theo, C sẽ gửi bản tin RERR về nút A và tường trình rằng tuyến từ C đến D bị đứt. Khi đó A sẽ xóa đường liên kết bị lỗi này khỏi bộ nhớ tuyến của nó. Việc truyền lại bản tin ban đầu bây giờ là nhiệm vụ và chức năng của các thủ tục lớp cao hơn như TCP. Trong trường hợp phải gửi lại gói tin tới chính đích E và nếu trong bộ nhớ tuyến của nút A có một tuyến khác tới E (ví dụ từ các bản tin trả lời tuyến từ các thủ tục khám phá tuyến trước đó hoặc là từ việc nghe lỏm được các thông tin định tuyến từ các gói tin khác) thì nó sẽ gửi ngay gói tin sử dụng tuyến mới đó. Nếu không nó sẽ thực hiện một thủ tục khám phá tuyến mới tới đích E nói trên AD HOC ON- DEMAND DISTANCE VECTOR ROUTING (AODV) AODV cho phép định tuyến nhiều bước giữa các nút mạng để thiết lập và duy trì mạng Ad hoc. AODV dựa trên thuật toán vector khoảng cách nhưng thuộc loại định tuyến theo yêu cầu, nó chỉ yêu cầu đường định tuyến khi cần thiết. Thuật toán định tuyến AODV khá phù hợp cho cấu hình mạng động. AODV đưa ra các tuyến không bị lặp ngay cả khi nó đang sửa các liên kết lỗi. Bởi vì giao thức này không yêu cầu quảng bá tuyến định kỳ trên toàn mạng, nên yêu cầu toàn bộ băng thông có sẵn cho một nút di động thực chất là thấp hơn so với các giao thức khác, những giao thức yêu cầu quảng bá. AODV sử dụng liên kết đối xứng giữa các hàng xóm. Gói tin không đi theo tuyến đường giữa các nút khi một trong những nút đó không nghe được từ các nút khác. Những nút không nằm trên các tuyến đường hoạt động; chúng sẽ không duy trì bất cứ thông tin định tuyến nào cũng như không tham gia vào bất kỳ sự trao đổi bảng định tuyến định kỳ nào. Hơn nữa, một nút không phải khám phá và duy trì một tuyến tới nút khác cho tới khi hai nút cần giao tiếp với nhau, trừ khi nút đó đóng vai trò như một trạm chuyển tiếp trung gian để duy trì kết nối giữa hai nút khác . Khi một kết nối cục bộ của nút di động được thiết lập, mỗi nút có thể nhận thấy các nút khác trong vùng lân cận của nó bằng một vài kĩ thuật, bao gồm quảng bá cục bộ các bản tin Hello. Bảng định tuyến của các nút trong vùng lân cận được tạo ra để tối ưu thời gian đáp ứng tới với sự di chuyển cục bộ và cung cấp thời gian đáp ứng nhanh cho các yêu cầu thiết lập tuyến mới. Mục tiêu chính của thuật toán AODV: Gửi broadcast các gói tin khám phá tuyến khi cần thiết. Phân biệt giữa phát hiện-quản lý kết nối cục bộ trong vùng lân cận với duy trì topo mạng chung. Quảng bá thông tin về sự thay đổi kết nối cục bộ tới các nút hàng xóm mà thực sự cần thông tin. AODV sử dụng một cơ chế Khám phá tuyến với sự cải biến của thuật toán DSR. Thay vì định tuyến nguồn, AODV tin tưởng vào sự thiết lập động các entry trong Bảng định tuyến ở các nút trung gian. AODV sử dụng số thứ tự ở nút mạng đích để giúp cho tuyến đường luôn cập nhật và không hình thành đường định tuyến khép kín. Hơn nữa, AODV cũng hỗ trợ định tuyến multicast và giải quyết được vấn đề đếm vô hạn trong thuật toán Bellman Ford. Khám phá tuyến Quá trình Khám phá tuyến được khởi tạo bất cứ khi nào một nút nguồn muốn giao tiếp với các nút mạng khác nhưng nó lại không có thông tin định tuyến trong Bảng định tuyến của nó. Mỗi nút duy trì hai bộ đếm: số thứ tự nút và broadcast ID. Nút nguồn khởi tạo Khám phá tuyến bằng cách quảng bá gói tin RREQ tới hàng xóm của nó. RREQ chứa các trường sau: Trong đó: source _addr: địa chỉ nguồn source sequence: số thứ tự nguồn broadcast_id: định danh của RREQ dest_addr: địa chỉ đích dest sequence: số thứ tự đích hop_cnt : số chặng Cặp được xác định duy nhất với mỗi bản tin RREQ. broadcast_id được tăng lên khi nút nguồn khởi tạo một RREQ mới. Mỗi nút hàng xóm khi nhận được bản tin RREQ sẽ gửi lại một bản tin RREP tới nút nguồn nếu nó biết một tuyến tới đích, hoặc tiếp tục quảng bá bản tin RREQ tới nút hàng xóm sau khi tăng hop_cnt. Chú ý rằng mỗi nút có thể nhận được nhiều bản sao của cùng một RREQ từ các hàng xóm. Khi một nút trung gian nhận được một RREQ, nếu nó đã nhận RREQ với cùng broadcast_id và địa chỉ đích, nó sẽ loại bỏ RREQ đó và không chuyển tiếp gói tin đó nữa. Nếu một nút không thể đáp ứng được RREQ, nó sẽ theo dõi các thông tin sau để thiết lập tuyến đường ngược cũng như thiết lập tuyến đường thuận để dành cho việc truyền gói tin RREP. Địa chỉ IP đích Địa chỉ IP nguồn Broadcast ID Thời gian hết hạn của entry tuyến đường ngược Số thứ tự của nút nguồn Thiết lập tuyến đường ngược Có hai số thứ tự được chứa trong một bản tin RREQ: số thứ tự nguồn và số thứ tự đích cuối cùng được biết bởi nguồn. Số thứ tự nguồn được sử dụng để duy trì thông tin mới về tuyến đường ngược tới nguồn, và số thứ tự đích chỉ ra rằng tuyến đường tới đích phải mới như thế nào để nó có thể được chấp nhận bởi nguồn. Khi bản tin RREQ được gửi từ nút nguồn tới các nút đích khác nhau, nó sẽ tự động thiết lập các tuyến đường ngược từ tất cả các nút đó tới nút nguồn. Để thiết lập tuyến đường ngược, mỗi nút phải ghi lại địa chỉ của hàng xóm mà từ đó nó nhận được bản sao đầu tiên của RREQ. Các entry tuyến đường ngược được duy trì trong khoảng thời gian vừa đủ để bản tin RREQ có thể truyền trên mạng và trả lời lại tới nút gửi. Hình 2.7 Thiết lập tuyến đường đi ngược Thiết lập tuyến đường thuận Cuối cùng, bản tin RREQ sẽ đến được một nút biết được tuyến tới nút đích. Đầu tiên, nút nhận được bản tin RREQ sẽ kiểm tra để chắc chắn rằng bản tin RREQ đã được nhận trên một liên kết hai chiều. Nếu một nút trung gian có một entry tuyến tới đích yêu cầu, nó so sánh số thứ tự đích trong entry tuyến của chính nó với số thứ tự đích trong bản tin RREQ để xác định xem tuyến đó có dùng được hay không. Nếu số thứ tự đích trong bản tin RREQ lớn hơn, nút trung gian sẽ không sử dụng tuyến trong bảng entry tuyến của nó để đáp ứng RREQ. Khi đó, nút trung gian sẽ tiếp tục quảng bá RREQ. Các nút trung gian chỉ trả lời khi số thứ tự đích trong bảng entry của nó lớn hơn so với trong bản tin RREQ. Nếu nút trung gian có một tuyến hiện hành tới nút đích và nếu bản tin RREQ này chưa được nhận trước đó, nút sẽ gửi unicast một bản tin RREP tới hàng xóm mà từ đó nó nhận được RREQ. Một bản tin RREP chứa các thông tin sau: Trong khi một gói tin quảng bá tới một nút có tuyến tới đích, một tuyến đường ngược được thiết lập tới nút nguồn của gói tin RREQ. Khi RREP trở lại nút nguồn, mỗi nút dọc theo tuyến đường thiết lập một con trỏ thuận tới nút mà từ đó RREP đến, cập nhật thông tin timeout cho các entry tới nút nguồn và nút đích, ghi lại số thứ tự đích mới nhất cho tuyến được yêu cầu. Thiết lập tuyến đường thuận khi RREP từ nút đích D tới nút nguồn S. Nút không nằm trên tuyến được xác định bởi RREP sẽ hết hạn sau ACTIVE_ROUTE_TIMEOUT (3000ms) và sẽ xóa con trỏ ngược. Một nút nhận RREP sẽ truyền RREP đầu tiên về nút nguồn. Nếu một nút nhận nhiều hơn một RREP, nó sẽ cập nhật thông tin định tuyến của nó và truyền RREP chỉ khi RREP có số thứ tự đích lớn hơn hoặc bằng RREP trước đó với một số chặng nhỏ hơn. Nó sẽ loại bỏ hết các RREP khác mà nó nhận được. Điều này giảm số lượng bản tin RREP truyền tới nút nguồn đồng thời đảm bảo rằng thông tin định tuyến là nhanh và mới nhất. Nút nguồn có thể truyền dữ liệu ngay sau khi nhận được RREP đầu tiên và sau đó có thể cập nhật thông tin định tuyến nếu nó học được một tuyến mới tốt hơn. Hình 2. 8 Thiết lập tuyến đường thuận Quản lý bảng định tuyến Gắn liền với các entry tuyến đường ngược là một bộ đếm thời gian, được gọi là “bộ đếm thời gian hết hạn RREQ”. Mục đích của bộ đếm thời gian này là để thanh lọc những entry tuyến đường ngược từ những nút không nằm trên tuyến đường từ nguồn tới đích. Thời gian hết hạn phụ thuộc vào kích thước của mạng Ad hoc. Một thông số quan trọng khác gắn với entry định tuyến là thời gian timeout của các tuyến đang được lưu giữ, hay thời gian mà sau đó tuyến đường này coi như hết hiệu lực. Trong mỗi entry Bảng định tuyến, địa chỉ của nút hàng xóm mà gói tin đi qua để đến đích cũng được duy trì. Một nút được coi là hoạt động đối với đích đó khi nó tạo ra hay chuyển tiếp ít nhất một gói tin tới đích đó trong khoảng thời gian timeout . Thông tin này được duy trì để tất cả các nút nguồn có thể được thông báo khi có một liên kết bị đứt. Mỗi nút duy trì một entry cho mỗi đích cần đến. Mỗi entry chứa các thông tin sau: Đích Next hop Số chặng Số thứ tự đích Các hàng xóm còn hoạt động cho đích đó Thời gian hết hạn cho entry bảng định tuyến Mỗi khi một entry tuyến được dùng để truyền gói tin dữ liệu từ nguồn tới đích, timeout cho entry đó sẽ được reset tới thời gian hiện tại cộng thêm timeout. Nếu một tuyến mới được yêu cầu cho một nút di động, các nút di động so sánh số thứ tự đích của tuyến mới với tuyến hiện tại. Nếu số thứ tự tuyến mới cao hơn, nó sẽ được chọn, nếu bằng nhau thì tuyến mới sẽ được chọn khi có metric nhỏ hơn (số chặng ít hơn) tới đích. Cập nhật đường định tuyến Khi một nút mạng phát hiện đường định tuyến đến nút bên cạnh không hoạt động, nó sẽ xóa trong bảng định tuyến và gửi một bản tin Liên kết hỏng RERR. AODV sử dụng danh sách nút mạng bên cạnh còn hoạt động để ghi nhớ nút mạng đang sử dụng đường định tuyến trong bảng định tuyến. Nút mạng nhận được bản tin này cũng sẽ lặp lại quá trình gửi bản tin. Cuối cùng bản tin cũng đến được gửi đến tất cả nút mạng có liên quan, từ đó chúng có thể dừng việc gửi thông tin hoặc yêu cầu đường định tuyến mới thông qua bản tin RREQ. DYNAMIC MANET ON- DEMAND (DYMO) DYMO là giao thức định tuyến theo bảng mới nhất, hiện vẫn đang được phát triển bới MANET trong IETF. DYMO có thể coi là sự kết hợp của AODV và DSR. Mục tiêu của nó là thiết kế đơn giản, giảm thiểu yêu cầu hệ thống , đơn giản hóa việc thực thi giao thức. Một mặt, DYMO cũng sử dụng số thứ tự để đàm bảo tránh lặp tuyến, mặt khác, DYMO đưa ra các đặc tính mới như là thực hiện tính toán tuyến đường. Bên cạnh thông tin tuyến đường về một mục tiêu được yêu cầu, một nút cũng nhận được thông tin về tất cả các nút trung gian nằm trên một tuyến đường mới khám phá được. Đây là một khác biệt cơ bản giữa DYMO và AODV, trong đó thì AODV chỉ tạo ra entry bảng định tuyến cho nút đích và nút next-hop, còn DYMO thì lưu trữ tuyến đường cho mỗi nút trung gian. Điều này được thể hiên qua hình 2.9. Hình 2.9: Sự khác nhau giữa AODV và DYMO Khi sử dụng AODV, một nút A chỉ biết đường tới B và D sau khi Yêu cầu tuyến được đáp ứng. Trong DYMO, nút A cũng biết cả đường tới C. DYMO có thể thiết lập và duy trì các tuyến đường unicast trong các kịch bản mạng IPv4 và IPv6 bằng cách sử dụng cơ chế sau: Nhằm phát hiện một tuyến mới đến một nút đích, một nút gửi một bản tin Yêu cầu tuyến RREQ tới tất cả hàng xóm trong phạm vị truyền sóng của nó. Điều này cũng nhận được bằng cách gửi bản tin tới 1 địa chỉ multicast cục bộ riêng. Khi một nút trung gian nhận được một RREQ nó thiết lập tuyến đường tới tất cả các nút mà gói tin đã đi qua. Sau đó nút sẽ gắn địa chỉ của chính nó vào bản tin và truyền bản tin tới tất cả các nút lân cận. Bằng cách này thì RREQ được quảng bả một cách hiệu quả trên mạng và cuối cùng là đến đích của nó. Đich đáp ứng RREQ bằng cách gửi unicast một bản tin Trả lời RREP trở về nút mà nó mà từ đó nó nhận được RREQ. Cũng như trong quá trình quảng bá RREQ, nút này lại gắn địa chỉ của nó và ghi chú tất cả các thông tin định tuyến có trong RREP. Cùng với thông tin định tuyến đã có được trước đó khi chuyển tiếp RREQ tương ứng, nút trung gian có khả năng gửi RREP trở về nút nguồn của RREQ. Nút này cũng sẽ biết được tuyến đường tới nút đích được yêu cầu, cũng như là đường tới mọi nút trung gian, và ngược lại. Một nút trung gian cũng có thể tạo ra RREP nếu như nó biết tuyến đường tới đích. Để phản ứng tốt với mạng có mức độ di chuyển cao, các liên kết trên tuyến đường đã biết được có thể được theo dõi, bằng cách sử dụng giao thức nhận biết hàng xóm (Neighboehood Discovery Protocol) hoặc kiểm tra phản hồi nhận được ở tầng data link. Một hệ thống cũng có thể lựa chọn không bật tính năng theo dõi, đơn giản chỉ xóa các tuyến không còn hoạt động. Khi một nút phát hiện liên kết lỗi, nó sẽ gửi một bản tin RERR để thông báo có tất cả các nút lân cận, thông báo cho chúng biết về tất cả các tuyến đị đứt. TỔNG KẾT Qua việc nghiên cứu một số giao thức trong mạng Ad hoc ta có thể thấy rằng chưa có giao thức nào có đầy đủ các tính năng và không thể khẳng định giao thức nào là tối ưu cho mạng Ad hoc. Tuy nhiên, chức năng chính của các giao thức là tìm được đường đi tới đích, không phải đường ngắn nh