Bài giảng Các giao thức định tuyến: Giao thức định tuyến mạng MANET

Chia sẻ: Cố Dạ Bạch | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

6
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Các giao thức định tuyến: Giao thức định tuyến mạng MANET. Chương này cung cấp cho học viên những nội dung gồm: mạng MANET; thách thức trong định tuyến cho mạng MANET; các giao thức định tuyến trong mạng MANET; routing protocols; reactive routing – định tuyến nguồn;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Các giao thức định tuyến: Giao thức định tuyến mạng MANET

Giao thức định tuyến mạng MANET
Mạng MANET l Mobile Adhoc Network. l Gồm các thiết bị di động, kết nối không dây l Multi-hop routing
Thách thức trong định tuyến cho mạng MANET l Cần định tuyến động ¡ Topo thay đổi rất thường xuyên l Cần giữ lượng thông tin điều khiển định tuyến tối thiểu ¡ Wireless à băng thông thấp ¡ Mobile à năng lượng thấp ¡ Cần giảm thiểu số lượng các gói tin điều khiển định tuyến ¡ Cần giảm thiểu lượng thông tin trạng thái lưu tại mỗi nút.
Các giao thức định tuyến trong mạng MANET l Topology based routing ¡  Proactive approach, e.g., DSDV. ¡  Reactive approach, e.g., DSR, AODV, TORA. ¡  Hybrid approach, e.g., Cluster, ZRP. l  Position based routing ¡  Location Services: l DREAM, Quorum-based, GLS, Home zone etc. ¡  Forwarding Strategy: l Greedy, GPSR, RDF, Hierarchical, etc.
Routing Protocols l  Reactive (On-demand) protocols ¡ Khám phá đường đi khi cần ¡ Quá trình tìm kiếm được khởi tạo từ nguồn l  Proactive protocols ¡ Tìm kiếm đường đi ngắn nhất theo các giao thức định tuyến phân tán truyền thống ¡ Cần các quá trình cập nhật thông tin định tuyến thường xuyên. Lượng thông tin điều khiển định tuyến lớn l  Vấn đề cân đối giữa 2 phương pháp ¡ Thông lượng để cập nhật trạng thái vs. thông lượng để khám phá đường đi ¡ Định tuyến dữ liệu theo các tuyến đường cũ vs. trễ khi khám phá đường đi.
Reactive (on-demand) routing: l Định tuyến khi cần Ưu điểm: 0 ¡ Không tạo trước một cấu trúc query(0) reply(0) định tuyến nào (bảng định query(0) tuyến) 1 ¡ Không cần các cập nhật định kỳ query(0) 3 ¡ Thích nghi với sự thay đổi reply(0) động của mạng query(0) 2 query(0) Nhược điểm: l  Overhead do phát tán thông tin 4 khám phá lớn query(0) reply(0) query(0) ¡ Độ trễ đến thời điểm tìm được 5 đường đi lớn.
Reactive Routing – Định tuyến nguồn l  Nguồn sẽ phát tán (kiểu ngập lụt) trong mạng bản tin route request khi có yêu cầu về đường đi đến một đích. ¡ Phát tán xuất phát từ nguồn ¡ Ngập lụt = mọi nút trong mạng đều nhận được yêu cầu 1 lần l  Đích trả lời bằng cách gửi bản tin route reply ¡ Trả lời bằng cách sử dụng đường đi xác định bởi route request ¡ Thiết lập đường chuyển dữ liệu l  2 giao thức đặc trưng: DSR and AODV
Dynamic Source Routing (DSR) l Quá trình hợp tác giữa các nút l Hoạt động trên bán kính mạng nhỏ (5-10 hops) l Hoạt động trên các liên kết 1 chiều và 2 chiều
Route Discovery RREQ FORMAT B Initiator ID A-B-D-G A-B-D-G G Initiator seq# A-B-D-G A-B Target ID A D A-B-D Partial route A A-C-E A E H A-B-C A-C-E Route Request (RREQ) A-C-E C A-C A-B-C F Route Reply (RREP)
Route Discovery: ở nguồn A A need to send to G Lookup Cache for route A to G Start Route no Route Discovery Buffer found packet ? Protocol yes Continue normal wait yes Write route in processing packet header Packet Route in Discovery buffer Send finished ? no packet to done next-hop
Route Discovery: Ở nút trung gian in Accept route recently Discard request yes seen route packet requests request list? no Host’s address yes Discard already in route patrial request route Append no myAddr to no partial route myAddr =target yes Store in list Send route reply packet Broadcast packet done
DSR - Route Discovery l  Route Reply chứa thông tin đường đi tìm được được gửi bởi đích l  Mỗi nút chứa một Route Cache chứa các bản ghi đường đi mà nút này học được (nhận được) trong quá trình hoạt động l  Toàn bộ đường đi sẽ được đưa vào header của gói tin cần vận chuyển (khác AODV).
Duy trì đường đi l  Đường đi được duy trì chỉ khi nó vẫn đang được sử dụng l  Phát hiện lỗi: ¡ Kiếm soát tính hợp lệ của các đường đi đang có bằng cách nghe thụ động các quá trình truyền dữ liệu của các nút hàng xóm ¡ Nhờ cơ chế ACK của tầng thấp hơn. l  Khi phát hiện có vấn đề, gửi bản tin Route Error về nguồn để thực hiện một quá trình khám phá đường đi mới.
Duy trì đường đi B RERR RERR G D G A Route Cache (A) G: A, B, D, G H G: A, C, E, H, G E F: B, C, F C F
Tóm tắt về DSR " Hoàn toàn on-demand, nói chung không gây overhead " Loop-free " source routing " Hỗ trợ cả liên kết unidirectional và bidirectional. " Có độ trễ truyền/jitters gây ra do on-demand routing " Đòi hỏi không gian lưu trữ đường đi trong caches
AODV Routing Protocol S E F A C G D B l  AODV = Ad Hoc On-demand Distance Vector l  Nguồn gửi ngập lụt route request đi toàn mạng. l  Đích D l  Tuyến đường ngược về nguồn được xác định khi một nút nhận được route request. l  Mỗi nút chỉ forward gói tin request 1 lần (pure flooding).
AODV Route Discovery S E F A C G D B l  Reverse paths được tạo khi một nút nhận được một gói route request.
AODV Route Discovery S E F A C G D B l  Reverse paths được tạo khi một nút nhận được một gói route request.
AODV Route Discovery S E F A C G D B l Route reply được chuyển ngược lại dựa trên reverse path.
AODV Route Discovery S E F A C G D B l Route reply được chuyển ngược về nguồn sử dụng reverse path … do đó tạo lập forward path l Forward path được dùng để vận chuyển dữ liệu từ nguồn đến đích sau này. l Các nút trung gian lưu bảng định tuyến có next hop trong forward path hướng đến đich (khác DSR)