Ad Hoc On-Demand Distance Vector

Slides: Download
Thời gian: 14:00 ngày 2 tháng 11 năm 2019
Địa điểm: Phòng V10.02
Thời lượng: 1 tiết

Chú ý: Tập trung từ 13:00 tại phòng nào trống nhà V10. Khi đi nhớ ăn mặc gọn gàng, mang theo bút vở, tài liệu để làm bài tập. Cảm ơn các em! ;)

Ad hoc on-demand distance vector (AODV) là một thuật toán định tuyến theo yêu cầu (on-demand) thuần túy. Các nút (node) không nằm trên một đường truyền cụ thể thì không bảo trì thông tin định tuyến và cũng không tham gia vào các trao đổi bảng định tuyến. Do đó, số lượng các gói tin quảng bá (broadcasts) cần thiết để tạo ra các tuyến đường (routes) theo yêu cầu thông qua AODV được giảm thiểu thay vì thực hiện truyền tin theo chế độ quảng bá để duy trì thông tin định tuyến hoàn chỉnh như trong DSDV. Nhờ đó lưu lượng các gói tin có chức năng định tuyến trong mạng được giảm thiểu.
Khi một nút nguồn (source) cần gửi một thông điệp (message) đến một nút đích mà không có một tuyến đường nào có hiệu lực, nút nguồn bắt đầu một quá trình khám phá tuyến đường (route discovery) đến đích. Nút nguồn gửi đi một gói tin yêu cầu tuyến đường (route request), viết tắt là RREQ, đến tất cả các nút lân cận (neighbors) của nó. Các nút nhận được gói tin RREQ sau đó chuyển tiếp yêu cầu đến tất cả các nút lân cận, và cứ như vậy, đến khi nút đích (destination) hoặc nút trung gian (intermediate) với thông tin tuyến đường đủ mới nhận được thông điệp. Hình 7.3.6 minh họa sự lan truyền của gói tin quảng bá RREQs đi qua mạng từ nút nguồn A đến nút đích E.

Hình 7.3.6: Sự lan truyền của gói tin yêu cầu tuyến RREQ

Cũng giống như giải thuật định tuyến DSDV, số thứ tự (sequence number) của đích được dùng để đảm bảo rằng tất cả các tuyến không tạo ra vòng lặp và chứa thông tin tuyến mới gần đây. Mỗi nút có một số thứ tự riêng và một định danh quảng bá (broadcast ID), sẽ được tăng lên mỗi khi nút bắt đầu gửi đi một yêu cầu tuyến RREQ. Định danh quảng bá, cùng với địa chỉ IP của nút, định dạng duy nhất mỗi gói tin RREQ. Các thông tin định dạng nút nguồn bao gồm trong gói tin RREQ:

-         Số thứ tự của nút

-         Số định danh quảng bá

-         Số thứ tự gần đây nhất của nút đích

Các nút trung gian trả lời gói tin RREQ chỉ nếu chúng có một tuyến đến đích với số thứ tự lớn hơn hoặc tối thiếu là bằng với số thứ tự bên trong gói tin RREQ. Để tối ưu hóa hiệu xuất của tuyến, các nút trung gian lưu trữ địa chỉ của các nút lân cận khi chúng nhận được lần đầu gói tin quảng bá RREQ. Điều này thiết lập thông tin đường đi ngược lại về nút nguồn (reverse path). Tất cả những gói tin RREQ cùng số thứ tự nhận được sau đó đều bị hủy bỏ. Hình 7.3.7 mô tả đường đi ngược lại về nút nguồn được cập nhật trên các bảng định tuyến.

Hình 7.3.7: Đường đi ngược về nguồn – reverse path

Một khi gói tin RREQ đến được đích hoặc một nút trung gian có thông tin tuyến đường đủ mới đến đích, nút trung gian hoặc nút đích đó gửi một thông điệp trả lời (route reply), viết tắt là RREP, trở lại cho nút lân cận mà nó nhận được bản đầu tiên của gói tin RREQ. Hình 7.3.8 minh họa đường đi của gói tin phản hồi RREP.

Hình 7.3.8: Đường đi của gói tin RREP

Bởi gói tin RREP đi ngược trở lại trên đường ngược về đã được thiết lập trước đây, các nút trên tuyến đường có thể thiết lập thông tin đường tuyến hướng về phía nút đích (forward path) khi các nút nhận được gói tin RREP. Các thông tin định tuyến hướng về phía nút đích sẽ tạo ra đường đi hiệu lực từ nút nguồn đến nút đích. Các gói tin RREP tiếp tục đi trở lại dọc theo đường ngược (reverse path) cho đến khi đến nút nguồn. Nhờ đó AODV có thể hỗ trợ đường truyền hai chiều (symmetric links). Hình 7.3.9 mô tả đường đi hướng về phía nút đích (forward path) xuất phát từ nút nguồn được thể hiện trong các bảng định tuyến.

Hình 7.3.9: Đường đi từ nguồn đến đích – forward path

Một bộ định thời cho tuyến (route timer) được liên kết với mỗi bảng ghi định tuyến. Bộ định thời này tác động đến việc xóa bảng ghi tuyến nếu tuyến đó không được dùng trong một khoản thời gian cụ thể (specified lifetime).

Khi một nút nguồn di chuyển, nó có thể khởi động lại quá trình khám phá tuyến để tìm ra tuyến đường mới đến nút đích. Nếu các nút dọc theo tuyến đường di chuyển, các nút liền kề ghi chú sự di chuyển và lan truyền một thông báo liên kết hỏng (link failure), và cứ thế cho đến khi nút nguồn nhận được thông báo. Một thông báo hỏng đường truyền về cơ bản là một gói tin RREP với trọng số vô cực.

Nút nguồn lúc bấy giờ có thể chọn khởi động lại quá trình khám phá tuyến nếu một tuyến đến nút đích vẫn được yêu cầu. Một giao thức khác theo sau trong quá trình bảo trì tuyến là thông điệp HELLO, định kỳ gửi đi theo cách thức quảng bá bởi một nút để thông báo cho các nút lân cận sự hiện diện của nó. Thông điệp HELLO bảo đảm các liên kết cục bộ. Các nút lắng nghe sự truyền lại gói dữ liệu để đảm bảo rằng các bước tiếp theo vẫn trong phạm vi có thể truyền được. Nếu một sự truyền lại như vậy không được nghe thấy, một vài kỹ thuật có thể được dùng để tái tạo lại tuyến đường cho gói tin. Một phương thức như vậy là sự đảm bảo của thông điệp HELLO để xác định nút tiếp theo có nằm trong phạm vi truyền thông hay không. Các thông điệp HELLO có thể cũng liệt kê các nút khác mà một nút có thể lắng nghe được, từ đó chuyển tiếp nhiều thông tin hơn về kết nối mạng.

Hình 7.3.10: Gói tin route error

Khi một kết nối đã bị đứt và gói tin không thể truyền được đến đích, các nút truyền gói tin route error, viết tắt là RERR, ngược trở lại nút nguồn. Nếu nút nguồn vẫn cần đường truyền đến đích, nó sẽ khởi động trở lại quá trình khám phát tuyến đường đến đích. Hình 7.3.10 minh hoạt một kết nối đã bị hỏng và gói tin RERR được gửi ngược về nút nguồn.