Luận văn Nghiên cứu các giao thức định tuyến điều khiển theo yêu cầu trên mạng Manet

khỏe: Trao đổi thông tin đa phương tiện giữa bệnh nhân và các cơ sở chăm sóc sức khỏe sẽ rất có ích trong những tình huống khẩn cấp. Một bệnh nhân được đưa đến bệnh viện bằng xe cấp cứu có thể sử dụng mạng ad hoc để cung cấp các thông tin về tình trạng bệnh nhân. Điều này sẽ rất có ích trong việc chuẩn bị một kế hoạch điều trị cho bệnh nhân đang được đưa đến bệnh viện hoặc trước khi đưa đến bệnh viện. Kết luận chương 1: Mạng không dây ngày nay đã phát triển rất mạnh mẽ, hàng loạt các thiết bị di động khai thác mạng không dây ra đời, mạng không dây có tính linh động rất cao và được ứng dụng trong hầu hết các lĩnh vực của cuộc sống. Vì vậy, mạng không dây có thể được xem như một công nghệ tiên tiến, một bước phát triển vượt bậc của hệ thống mạng máy tính. Nội dung của chương 1 đã tìm hiểu cơ bản về mạng không dây, với những mô hình và công nghệ, các ứng dụng, đồng thời phân tích các đặc điểm về mặc kỹ thuật, những khuyết điểm còn tồn tại của mô hình mạng không dây nói chung và mạng MANET nói riêng. Để tìm hiểu rõ hơn, chúng tôi sẽ tiếp tục đi sâu nghiên cứu các giao thức định tuyến ở chương 2. CHƯƠNG 2 NGHIÊN CỨU CÁC GIAO THỨC ĐỊNH TUYẾN ĐIỀU KHIỂN THEO YÊU CẦU TRÊN MẠNG MANET Trong mạng máy tính để định đường đi trong quá trình truyền dữ liệu người ta thường dùng các bộ định tuyến. Hay định tuyến là cách thức mà các bộ định tuyến, các máy tính hoặc các thiết bị mạng sử dụng để tìm đường trong việc phát các gói tin tới địa chỉ đích trên mạng, đảm bảo tìm đường đi tốt nhất từ lớp mạng này sang lớp mạng khác để đưa dữ liệu đến được đích mong muốn. Định tuyến trong hệ thống mạng: Thông thường, tiến trình định tuyến thường chỉ hướng đi dựa vào bảng định tuyến được tổ chức trong bộ nhớ của router, đó là bảng chứa những lộ trình tốt nhất đến các đích khác nhau trên mạng. Vì vậy, việc xây dựng bảng định tuyến trở nên vô cùng quan trọng trong việc định tuyến trên các hệ thống mạng. Để thực hiện được việc chuyển các gói dữ liệu đến mạng đích một cách chính xác, các router phải nhớ thông tin về đường đi tới các mạng khác. Nếu router chạy định tuyến động thì router sẽ tự động nhớ những thông tin này từ các router khác. Còn nếu router chạy định tuyến tĩnh thì người quản trị mạng phải cấu hình các thông tin đến các mạng khác cho các router. Một số thuật toán định tuyến cơ bản trong mạng: Một phương pháp khá đơn giản và hiệu quả để thực hiện việc định tuyến trong hầu hết các hệ thống mạng truyền thông là việc sử dụng các bộ định tuyến để phát hiện và lựa chọn đường đi hợp lý cho gói dữ liệu đến đích thông qua các thuật toán định tuyến như: thuật toán vectơ khoảng cách (Distance Vector) và thuật toán trạng thái kết nối (Link State) [5], [11] Thuật toán Vectơ khoảng cách (Distance Vector): Phương pháp này được thực hiện bằng cách truyền định kỳ các bản sao của bảng định tuyến từ router này sang router khác. Mỗi router nhận được bảng định tuyến của những router láng giềng kết nối trực tiếp với nó. Dựa vào thông tin cung cấp bởi các router láng giềng, thuật toán vectơ khoảng cách sẽ lựa chọn đường đi tốt nhất. Việc tính toán đường đi trong thuật toán định tuyến theo vectơ khoảng cách dựa vào thuật toán Bellman-Ford. Thuật toán Bellmen-Ford thường được áp dụng trong giao thức định tuyến tĩnh RIP để xây dựng bảng định tuyến. Thuật toán này cũng tương tự như thuật toán Dijlkstra nhưng nó không áp dụng phương pháp tham lam trong việc chọn ra đỉnh v có trọng nhỏ nhất lân cận với đỉnh u đang xét. Thuật toán Bellman Ford tính toán đường đi ngắn nhất từ nguồn tới đích được mô tả như sau: Input: Đồ thị (G, w, s); Bellman-Ford-More(G, w, s) Bước 1: Khởi tạo nút nguồn s Bước 2: for i = 1 to V[G] –1 do for mỗi cạnh (u, v) Î E[G] do if d( v) > d(u) + w then {d(u), d(v) là chi phí được tính từ nút gốc đến các đỉnh u, v} d(v) : = d(u) + w; Bước 3: for mỗi cạnh (u,v) Î E[G] do if d[u] + w(u, v) < d[v] then return False; else return True; Output: Cây đường đi ngắn nhất từ nút s đến các nút khác, kết quả hàm là true nếu không có đỉnh nào mà đường đi đến nó có giá trị lớn hơn tổng đường đi đến nút kề đứng trước nó với trọng số trên cạnh nối hai đỉnh u và v, ngược lại hàm trả về giá trị là false. Sử dụng các giao thức định tuyến theo vectơ khoảng cách thường tốn ít tài nguyên của hệ thống. Tuy nhiên, tốc độ đồng bộ giữa các router lại chậm và thông số được sử dụng để chọn đường đi có thể không phù hợp với những hệ thống mạng lớn. Thuật toán trạng thái kết nối (Link State): Trạng thái liên kết là một mô tả đặc điểm các mối liên kết từ bộ định này tới các bộ định tuyến lân cận. Các đặc điểm này bao gồm: địa chỉ IP, mặt nạ, kiểu mạng kết nối, và các bộ định tuyến kết nối mạng đó. Giao thức định tuyến trạng thái liên kết được thực hiện dựa trên các bản tin thông báo trạng thái liên kết (LSA), mỗi bộ định tuyến xây dựng cho mình một cơ sở dữ liệu trạng thái riêng dựa vào nội dung của các bản tin này. Do đó các bộ định tuyến biết rõ và chinh xác thông tin topo về mạng và thực hiện truyền dẫn các gói tin từ nút nguồn đến nút đích trong mạng dễ dàng. Gói thông báo trạng thái liên kết (LSA: Link State Advertisment) là các gói tin nhỏ chứa thông tin định tuyến được truyền qua lại giữa các bộ định tuyến, được làm tràn trên mạng theo định kỳ hay khi có thay đổi thông tin của một bộ định tuyến nào đó trong mạng. Cơ sở dữ liệu trạng thái liên kết (LSDB: Link State Database) được tạo và cập nhật từ thông tin của các bản tin thông báo LSA. Thuật toán trạng thái liên kết được dùng để xây dựng và tính toán đường đi ngắn nhất từ nút nguồn đến tất cả các nút đích trong mạng. Thuật toán Dijkstra được áp dụng trong giao thức định tuyến trạng thái liên kết được thực hiện qua các bước sau: Input: Đồ thị (G, w, s); Dijkstra(G, w, s) Bước 1: Khởi tạo nút nguồn s; Bước 2: S : = {}; {Cuối cùng S sẽ chứa các đỉnh có trọng số đường đi ngắn nhất từ s} Bước 3: Khởi tạo hàng đợi ưu tiên Q : = V[G] {Q chứa các đỉnh trong đồ thị G} Bước 4: While Q {} do u : = EXTRACT_MIN(Q) {Chọn ra đỉnh v trong Q lân cận đỉnh u có trọng số cạnh (u,v) nhỏ nhất gán cho u} Bước 5: S : = S È {u} ; Q : = Q \ {u} Bước 6: for mỗi đỉnh v Î Adj[u] do {v các đỉnh liền kề với u} if d( v) > d(u) + w then {d(u), d(v) là chi phí được tính từ nút gốc đến các đỉnh u, v} d(v) : = d(u) + w; {quay lại Bước 4} Output: Cây đường đi ngắn nhất từ đỉnh s đến các nút trong mạng. Sử dụng giao thức định tuyến trạng thái liên kết sẽ dẫn đến một số nhược điểm: Router sử dụng định tuyến theo trạng thái kết nối sẽ phải cần nhiều bộ nhớ hơn và hoạt động xử lý nhiều hơn là sử dụng định tuyến theo vectơ khoảng cách. Router phải có đủ bộ nhớ để lưu cơ sở dữ liệu về cấu trúc mạng, bảng định tuyến. Khi khởi động việc định tuyến, tất cả các router phải gửi gói LSA cho tất cả các router khác, khi đó băng thông đường truyền sẽ bị chiếm dụng làm cho băng thông dành cho đường truyền dữ liệu của người dùng bị giảm xuống. Tuy nhiên, sau khi các router đã thu thập đủ thông tin để xây dựng cơ sở dữ liệu về cấu trúc mạng thì băng thông đường truyền không bị chiếm dụng nữa. Phân loại các giao thức định tuyến trong mạng MANET Mạng MANET (Mobile Ad hoc Network) là mạng không dây đặc biệt gồm tập hợp các thiết bị di động, giao tiếp không dây, có khả năng truyền thông trực tiếp với nhau hoặc thông qua các nút trung gian làm nhiệm vụ chuyển tiếp. Các nút mạng vừa đóng vai trò như thiết bị truyền thông vừa đóng vai trò như thiết bị định tuyến. Với nguyên tắc hoạt động như vậy, nó không bị phụ thuộc vào cơ sở hạ tầng mạng cố định nên có tính linh động cao, đơn giản trong việc lắp đặt, chi phí triển khai và bảo trì thấp. Như vậy, khi sử dụng các giao thức định tuyến thông thường dựa trên các giải thuật Distance-Vector hoặc Link-State trong mạng Ad Hoc sẽ dẫn đến một số vấn đề phát sinh: [6] Tiêu tốn băng thông mạng và năng lượng nguồn nuôi cho các cập nhật định kỳ: Hầu hết các thiết bị di động trong mạng Ad Hoc sẽ hoạt động dựa trên nguồn pin, việc truyền hoặc nhận gói tin sẽ tiêu tốn đáng kể đến nguồn năng lượng này. Ở các mạng thông thường, việc kết nối các bộ định tuyến nhìn chung là không thay đổi về vị trí, chính vì thế ít xảy ra việc thay đổi cấu hình tôpô mạng nên việc hội tụ mạng là ít xảy ra.Tuy nhiên, trong mạng Ad Hoc, các nút luôn thay đổi vị trí dẫn đến cấu hình tôpô mạng thay đổi, nên đòi hỏi cần phải có sự hội tụ của mạng cho các tuyến mới một cách nhanh chóng. Để thực hiện được việc này, các giao thức định tuyến phải liên tục gửi cập nhật định tuyến, dẫn đến việc tiêu tốn khá nhiều băng thông và năng lượng. Các đường đi dư thừa được tích lũy một cách không cần thiết: Trong môi trường mạng Ad Hoc, có rất nhiều đường đi từ nút nguồn đến nút đích và những đường đi này sẽ được cập nhật tự động vào bảng định tuyến trong các thiết bị định tuyến (thiết bị di động), dẫn đến việc dư thừa đường đi trong bảng định tuyến. Các giao thức định tuyến trong mạng Ad Hoc được chia thành 3 loại: Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol), Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol) và Giao thức định tuyến kết hợp (Hybrid Routing Protocol). Ad hoc Routing Protocols Table-Driven On-Demand Hybrid Flat Hierarchical DSDV WRP GSR OLSR DREAM MMWN CGSR HSR LANMAR HOLSR START Flat Hierarchical DSR TORA AODV LAR SSA MSR CBRP Flat Hierarchical ZRP SHARP ZHLS SLURP DST HARP Hình 2.1. Phân loại các giao thức định tuyến trong mạng Ad Hoc Giao thức định tuyến theo bảng ghi (Table-Driven Routing Protocol): Giao thức định tuyến theo bảng ghi còn được gọi là giao thức chủ ứng (Proactive). Theo giao thức này, bất kỳ một nút trong mạng đều luôn duy trì trong bảng định tuyến của nó thông tin định tuyến đến tất cả các nút khác trong mạng. Thông tin định tuyến được phát broadcast trên mạng theo một khoảng thời gian quy định để giúp cho bảng định tuyến luôn cập nhật những thông tin mới nhất. Chính vì vậy, một nút nguồn có thể lấy thông tin định tuyến ngay lập tức khi cần thiết. Tuy nhiên, với những mạng mà các node di chuyển nhiều hoặc các liên kết giữa các node bị đứt thì cần phải có cơ chế tìm kiếm hoặc sửa đổi thông tin của nút bị đứt trong bảng định tuyến, nhưng nếu các liên kết đó không sử dụng thì sẽ trở nên lãng phí tài nguyên, ảnh hưởng đến các băng thông của mạng. Chính vì thế giao thức định tuyến theo bảng ghi chỉ áp dụng trong các mô hình mạng MANET mà các nút ít di chuyển. Các giao thức hoạt động theo kiểu giao thức định tuyến theo bảng ghi như: Giao thức DSDV (Destination Sequenced Distance Vector), Giao thức WRP (Wireless Routing Protocol), Giao thức GSR (Global State Routing)… Giao thức định tuyến điều khiển theo yêu cầu (On-Demand Routing Protocol): Một phương pháp khác với phương pháp định tuyến điều khiển theo bảng ghi đó là định tuyến điều khiển theo yêu cầu còn được gọi là giao thức phản ứng (Reactive). Theo phương pháp này, các con đường đi sẽ được tạo ra nếu như có nhu cầu. Khi một nút yêu cầu một tuyến đến đích, nó phải khởi đầu một quá trình khám phá tuyến để tìm đường đi đến đích (Route Discovery). Quá trình này chỉ hoàn tất khi đã tìm ra một tuyến sẵn sàng hoặc tất cả các tuyến khả thi đều đã được kiểm tra. Khi một tuyến đã được khám phá và thiết lập, nó được duy trì thông số định tuyến (route maintenance) bởi một số dạng thủ tục cho đến khi hoặc là tuyến đó không thể truy nhập được từ nút nguồn hoặc là không cần thiết đến nó nữa. Với các cơ chế đó, các giao thức định tuyến điều khiển theo yêu cầu không phát broadcast đến các nút lân cân về các thay đổi của bảng định tuyến theo thời gian, nên tiết kiệm được tài nguyên mạng. Vì vậy, loại giao thức này có thể sử dụng trong các mạng MANET phức tạp, các node di chuyển nhiều. Một số giao thức định tuyến điều khiển theo yêu cầu tiêu biểu như: Giao thứ CBRP (Cluster Based Routing Protocol), Giao thức AODV (Ad hoc On Demand Distance Vector), Giao thức DSR (Dynamic Source Routing), Giao thức TORA (Temporally Ordered Routing Algorihm)… Giao thức định tuyến kết hợp (Hybrid Routing Protocol): Trong giao thức định tuyến này có kết hợp cả hai cơ chế giao thức định tuyến chủ ứng (Proactive) và giao thức định tuyến phản ứng (Reactive). Giao thức này phù hợp với những mạng quy mô, kích thước lớn, mật độ các nút mạng dày đặc. Trong giao thức định tuyến này, mạng được chia thành các vùng (zone). Mỗi node duy trì cả thông tin về kiến trúc mạng trong vùng của nó và thông tin về các vùng láng giềng. Đều đó có nghĩa là giao thức Hybrid sử dụng giao thức định tuyến phản ứng (Reactive) giữa các zone và giao thức định tuyến chủ ứng (Proactive) cho các node mạng trong cùng zone. Do đó, đường đi đến nỗi node trong cùng một zone được lập mà không cần phải định tuyến ra ngoài zone, trong khi đó các tiến trình khám phá đường và duy trì đường thì được sử dụng để tìm kiếm và duy trì đường đi giữa các zone với nhau. Các giao thức định tuyến tiêu biểu sử dụng kiểu Hybrid: Giao thức ZPR (Zone Routing Protocol), Giao thức ZHLS (Zone-based Hierarchical Link State Routing Protocol)… Giao thức định tuyến điều khiển theo yêu cầu trên mạng MANET: Như chúng ta đã biết, việc định tuyến trên các hệ thống mạng là khá quan trọng, quá trình định tuyến có thể xảy ra trước khi hệ thống có nhu cầu truyền dữ liệu hoặc trong khi hệ thống truyền dữ liệu. Các phương thức này cũng là một trong những yếu tố ảnh hưởng đến sự hoạt động của toàn bộ hệ thống mạng. Định tuyến điều khiển theo yêu cầu là một trong những phương thức định tuyến cơ bản trong hệ thống mạng không dây đặc biệt là hệ thống mạng MANET. Theo phương thức này, việc định tuyến chỉ xảy ra khi hệ thống có nhu cầu truyền dữ liệu. Có rất nhiều giao thức định tuyến sử dụng theo phương thức này. Trong luận văn này, chúng tôi phân tích hai giao thức định tuyến được sử dụng phổ biến nhất hiện nay: giao thức DSR và giao thức AODV. Giao thức DSR (Dynamic Source Routing): DSR (Dynamic Source Routing) là giao thức định tuyến đơn giản và hiệu quả được thiết kế riêng cho mạng MANET. DSR cho phép mạng tự động tổ chức và cấu hình mà không cần đến sự can thiệp của người quản trị hoặc cơ sở hạ tầng sẵn có của mạng. Giao thức DSR là giao thức định tuyến phản ứng (Reactive) sử dụng cơ chế định tuyến nguồn (source routing), nghĩa là bên gửi sẽ biết toàn bộ thông tin về đường đi đến đích. Phần Header của gói dữ liệu sẽ lưu trữ thứ tự các nút mà gói tin cần phải đi qua để đạt tới đích. Do vậy, các nút trung gian chỉ cần giữ liên lạc với các nút hàng xóm của nó để chuyển tiếp các gói tin. Tại mỗi một nút trong mạng luôn duy trì một bộ nhớ đệm (Router Cache), đây là cấu trúc dữ liệu lưu trữ các con đường đã biết. Khi có đường đi tồn tại trong Router Cache, các gói tin sẽ nhận thông tin về đường đi và thực hiện việc truyền tin trên con đường đã chọn. Ngược lại, khi không tồn tại đường đi trong Router Cache hoặc có tồn tại đường đi nhưng không còn hiệu lực, DSR sẽ thực hiện cơ chế phát hiện đường (Route Discovery) bằng cách gởi các gói tin quảng bá Route Request đến các nút lân cận trên toàn bộ mạng. Các nút trung gian nhận được gói tin quảng bá sẽ kiểm tra đường đi trong Route Cache. Khi đường đi được tìm thấy, gói tin Route Reply sẽ chứa thứ tự các chặng tới đích và được truyền trở lại nguồn. Như vậy, hoạt động của giao thức DSR bao gồm hai cơ chế chính: cơ chế tạo thông tin định tuyến (Route Discovery) và cơ chế duy trì thông tin định tuyến (Route Maintanance) [5], [6] Cơ chế tạo thông tin định tuyến (Route Discovery): Route Discovery cho phép các node trong mạng Ad Hoc tìm kiếm đường đi đến đích một cách tự động thông qua các node trung gian. Tiến trình tạo thông tin định tuyến sẽ phát gói tin Route Request (RREQ) đến các node lân cận của nó trong mạng. Ngoài các trường bình thường như: địa chỉ nguồn, địa chỉ đích, đường dẫn…, thông tin trong gói RREQ còn chứa một số request ID là một số được tạo ra bởi node nguồn và là số không trùng nhau. Khi một node nhận gói RREQ thì nó sẽ tiến hành kiểm tra thông tin trong RREQ như sau: Phát RREQ đến các node hàng xóm Trước đó node chưa nhận RREQ? Hủy gói RREQ N Node không có đường đi đến đích trong Route Cache? Y Node không là node đích? Y Phản hồi RREP về nguồn Y - Cập nhật thông tin về nguồn trong Router cache - Cập nhật lại đường dẫn cho gói RREQ N Kết thúc tiến trình khám phá đường Thêm vào Router cache của node Nối đường đi trong RREQ và đường đi đã có trong Router cache, cập nhật vào RREQ N Bắt đầu tiến trình khám phá đường tại nguồn Kết thúc tiến trình xử lý gói RREQ đã nhận Lưu đồ 2.1. Cơ chế xử lý khám phá đường tại node của DSR Bước 1: Thông qua trường request ID, nó sẽ kiểm tra xem đã nhận gói tin này hay chưa? Nếu đã tồn tại thì nó sẽ loại bỏ gói tin đó và không xử lí gì thêm. Ngược lại thì qua bước 2. Bước 2: Nó kiểm tra trong Route Cache của nó có đường đi đến node đích mà còn hiệu lực hay không? Nếu có đường đi đến đích thì nó sẽ phản hồi lại cho node nguồn bằng gói Route Reply (RREP) chứa thông tin về đường đi đến đích và kết thúc tiến trình. Ngược lại thì qua bước 3. Bước 3: Nó kiểm tra địa chỉ đích cần tìm có trùng với điạ chỉ của nó hay không? Nếu trùng thì nó gởi lại cho node nguồn gói Route Reply (RREP) chứa thông tin về đường đi đến đích và kết thúc tiến trình. Ngược lại thì nó sẽ phát broadcast gói tin RREQ đến các node láng giềng của nó. Các nút láng giềng sau khi nhận gói tin RREQ sẽ thực hiện việc kiểm tra thông tin (quay về bước 1) Như vậy, quá trình này cứ tiếp tục cho đến khi node nguồn nhận được thông tin về đường đi đến đích hoặc thông tin rằng không thể định tuyến đến đích. Gói Route Reply (RREP) được gởi đến nguồn bằng cơ chế phát Unicast với Source Route là đảo ngược Source Route trong gói RREQ. Ví dụ: Xét mô hình mạng Ad Hoc với mô hình truyền thông như hình 2.5. Nút S cần truyền dữ liệu đến nút D. S E A F B K G H I S D J Hình 2.2. Mô hình mạng Ad Hoc gồm 12 nút Giả thuyết 1: Trong Route Cache của các nút hiện tại là rỗng. Nút S sẽ phát gói tin Router Request (RREQ) đến các nút lân cận của nó (Hình 2.5.1) Hình 2.2.1. Nút S phát gói tin RREQ đến các nút lân cận A, E, F Nút A, E, F sẽ kiểm tra mình có phải là đích hay không? Nếu không sẽ kiểm tra trong Route Cache về đường đi đến đích. Theo giả thuyết ban đầu thì trong Route Cache sẽ không có thông tin về đường đi đến đích. Do đó, nút E, F, A sẽ cập nhật thông tin về đường đi về nguồn vào Route Cache thông qua gói tin RREQ, đồng thời sẽ phát gói tin RREQ đến các nút lân cận của nó. Bảng 2.1. Thông tin lưu trữ trong Route Cache tại thời điểm 1 Nút A, E, F sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.2) Hình 2.2.2. Nút A, F phát gói tin RREQ đến các nút F, B, A, K, G Tại thời điểm này tại A và F đều nhận gói tin RREQ (vì A là nút láng giềng của F và ngược lại). Do đó, hai gói tin này sẽ bị hủy vì đã tồn tại trước đó. Đồng thời, quá trình tìm kiếm đường đi vẫn chưa hoàn thành vì chưa đạt đến đích. Vì vậy, các nút lân cận sẽ lưu trữ thông tin về đường đi đến nguồn trong Route Cache và tiếp tục gửi gói tin RREQ đến các nút lân cận của nó. Bảng 2.2. Thông tin lưu trữ trong Route Cache tại thời điểm 2 Nút B, K, G sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.3) Hình 2.2.3. Nút B, K, G phát gói tin RREQ đến các nút C, G, H, K Tại thời điểm này, nút H cùng nhận gói RREQ từ 2 nút K và G. Trong trường hợp này, gói tin nào đến sau sẽ bị loại bỏ. Giả sử gói tin gửi từ K đến sau, vì thế giao thức DSR sẽ loại bỏ gói tin này. Tiến trình khám phá đường đi vẫn tiếp tục thực hiện. Bảng 2.3. Thông tin lưu trữ trong Route Cache tại thời điểm 3 Nút H, C sẽ phát gói tin RREQ đến các nút lân cận của nó (Hình 2.5.4) Hình 2.2.4. Nút H, C phát gói tin RREQ đến các nút láng giềng I, D, J Bảng 2.4. Thông tin lưu trữ trong Route Cache tại thời điểm 4 Tại thời điểm này, D nhận được gói RREQ và kiểm tra biết được mình chính là đích nên tiến trình khám phá đường đến đích dừng. Giao thức DRS sẽ thực hiện các công việc sau: D sẽ phát gói tin phản hồi Route Reply (RREP) về nguồn thông qua đường đã tìm được. Nút I vẫn tiếp tục phát gói RREQ để tìm đường đến D. Tuy nhiên, khi tìm thấy D thì gói tin RREQ sẽ lập tức bị hủy vì D đã nhận gói tin này trước đó, đồng thời D gửi gói tin RREP về nguồn S thông qua đường này. Nút J vẫn tiếp tục phát gói RREQ để tìm đến D. Tuy nhiên, trong trường hợp này nút I không tìm thấy và sẽ gửi gói RREP về nguồn. Trong khi các gói tin RREP được gửi về nguồn, Route Cache sẽ tiếp tục lưu trữ đường đi ngược lại từ đích. Sau khi nút nguồn S nhận được gói tin phản hồi RREP, S sẽ biết được được đường đi đến đích và tiến hành gửi dữ liệu theo con đường này. Hình 2.2.5. Nút D phát gói tin RREP về nút S theo đường đã khám phá Như vậy, trong trường hợp này sẽ có 2 con đường đi từ nút S đến nút D đó là: S,A,B,C,D và S,F,G,H,I,D. Giao thức DSR sẽ sử dụng một trong hai con đường này để truyền dữ liệu từ nút S đến nút D. Trong quá trình truyền dữ liệu nếu đường thứ nhất đang sử dụng bị hỏng thì giao thức sẽ sử dụng đường thứ hai và ngược lại. Trong trường hợp cả hai đường bị hỏng thì tiến trình khám phá đường (Router Discovery) sẽ tự động thực hiện lại. Giả thuyết 2: Trong Route Cache của các nút là không rỗng. Giả sử Route Cache của nút B đã lưu trữ đường đi đến D. Tiến trình khám phá đường đi vẫn thực hiện bình thường như giả thuyết 1. Tuy nhiên, khi đến B giao thức DSR sẽ kiểm tra trong Route Cache và phát hiện được đường đi đến D chính là đích, nên tiến trình khám phá đường sẽ dừng và nút B sẽ gửi gói tin phản hồi RREP về nguồn thông qua đường đi đã xác định. Cơ chế duy trì thông tin định tuyến (Route Maintanance): Route Maintanance cho phép các nút trong hệ thống mạng tự động bảo trì thông tin định tuyến trong Route Cache. Trong giao thức định tuyến DSR, các node khi chuyển gói tin trên mạng đều phải có nhiệm vụ xác nhận rằng các gói tin đó đã chuyển đến node kế tiếp hay chưa (thông qua sự phản hồi thông tin của node nhận) ? Trong một trường hợp nào đó mà node đó phát hiện rằng gói tin không thể truyền đến node kế tiếp. Nó sẽ gởi gói Route Error (RERR) cho node nguồn để thông báo tình trạng hiện thời của liên kết và điạ chỉ của node kế tiếp mà không thể chuyển đi. Khi node nguồn nhận được gói RERR, nó sẽ xóa con đường đi mà liên kết bị hỏng trong Route cache và tìm một đường đi khác mà nó biết trong route cache hoặc sẽ khởi động một tiến trình route discovery mới nếu như không tồn tại đường đi thích hợp trong Route cache. Hình 2.3. Minh họa cơ chế duy trì thông tin định tuyến Giao thức AODV (Ad hoc On Demand Distance Vector): Giao thức định tuyến AODV là một trong những giao thức định tuyến theo cơ chế phản ứng trong hệ thống mạng MANET. Tương tự như giao thức DSR, AODV cũng phát gói tin broadcast để yêu cầu tìm đường khi có nhu cầu. Tuy nhiên điểm khác biệt cơ bản đối với giao thức DSR là AODV sử dụng nhiều cơ chế khác để duy trì thông tin bảng định tuyến, chẳng hạn như nó sử dụng bảng định tuyến truyền thống để lưu trữ thông tin định tuyến với mỗi entry cho một địa chỉ đích. [3] Không sử dụng cơ chế Source Routing và cũng không cần biết thông tin về các node láng giềng của nó, AODV dựa trên các entry của bảng định tuyến để phát gói tin RREP về node nguồn và node nguồn dùng thông tin đó để gởi dữ liệu đến đích. Để đảm bảo rằng thông tin trong bảng định tuyến là mới nhất thì AODV sử dụng kỹ thuật Sequence Number (kỹ thuật này dùng để nhận ra các con đường đi không còn giá trị trong quá trình cập nhật bảng định tuyến) để loại bỏ những đường đi không còn giá trị trong bảng định tuyến. Mỗi node sẽ có một bộ tăng số Sequence Number riêng cho nó. [5] Tương tự như cơ chế hoạt động của DSR, quá trình định tuyến của AODV cũng bao gồm 2 cơ chế chính: cơ chế tạo thông tin định tuyến và cơ chế duy trì thông tin định tuyến. Cơ chế tạo thông tin định tuyến (Route Discovery): Cơ chế tạo thông tin định tuyến sẽ được thiết lập khi một nút nguồn có nhu cầu trao đổi thông tin với một nút khác trong hệ thống mạng. Trong hệ thống mạng MANET hoạt động theo giao thức AODV, mỗi nút trong hệ thống mạng luôn duy trì 2 bộ đếm: Bộ đếm Sequence Number và Bộ đếm REQ_ID. Cặp thông tin là định danh duy nhất cho một gói tin RREQ. Cặp thông tin này sẽ bị thay đổi giá trị khi: [5] Đối với Sequence Number: Trước khi một node khởi động tiến trình route discovery, đều này nhằm chống sự xung đột với các gói tin RREP trước đó. Khi nhận được một gói tin RREP gửi từ nút đích để trả lời gói tin RREQ, nó sẽ cập nhật lại giá trị Sequence number lớn nhất của một trong 2 giá trị: Sequence number hiện hành mà nó lưu giữ đối với Sequence number trong gói RREQ Đối với REQ_ID: Khi có một sự thay đổi trong toàn bộ các nút lân cận của nó dẫn đến sẽ có một số tuyến đường trong bảng định tuyến sẽ không còn hiệu lực. Số REQ_ID sẽ được tăng lên khi node khởi động một tiến trình route discovery mới. Hình 2.4. Các trườn