Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

A Quick Guide to AODV Routing Luke Klein-Berndt Wireless Communications Technol

A Quick Guide to AODV Routing Luke Klein-Berndt Wireless Communications Technologies Group National Institute of Standards and Technology Node 4 Node 1 Node 2 Node 3 A Quick Guide to AODV Routing 2 Node 4 Node 5 Node 1 Node 2 Node 3 Message Node 1 wants to send a message to Node 3. Unfortunately it is unsure of the route to get there AODV is a method of routing messages between mobile computers. It allows these mobile computers, or nodes, to pass messages through their neighbors to nodes with which they cannot directly communicate. AODV does this by discovering the routes along which messages can be passed. AODV makes sure these routes do not contain loops and tries to find the shortest route possible. AODV is also able to handle changes in routes and can create new routes if there is an error. The diagram to the left shows a set up of four nodes on a wireless network. The circles illustrate the range of communication for each node. Because of the limited range, each node can only communicate with the nodes next to it. A Quick Guide to AODV Routing 3 Nodes you can communicate with directly are considered to be Neighbors. A node keeps track of its Neighbors by listening for a HELLO message that each node broadcast at set intervals. When one node needs to send a message to another node that is not its Neighbor it broadcasts a Route Request (RREQ) message. The RREQ message contains several key bits of information: the source, the destination, the lifespan of the message and a Sequence Number which serves as a unique ID. In the example, Node 1 wishes to send a message to Node 3. Node 1’s Neighbors are Nodes 2 + 4. Since Node 1 can not directly communicate with Node 3, Node 1 sends out a RREQ. The RREQ is heard by Node 4 and Node 2. Node 4 Node 1 Node 2 RREQ RREQ Node 1 A packet of data Dest: Node 3 Route Request Packet Dest: Node 3 Src: Node 1 Lifespane: 3 ID: 0 Neighbors Node 2 Node 6 Since Node 3 is not a Neighboring node, Node 1 has to discover a route. It does this by generating a Route Request and broadcasting it. A Quick Guide to AODV Routing 4 When Node 1’s Neighbors receive the RREQ message they have two choices; if they know a route to the destination or if they are the destination they can send a Route Reply (RREP) message back to Node 1, otherwise they will rebroadcast the RREQ to their set of Neighbors. The message keeps getting rebroadcast until its lifespan is up. If Node 1 does not receive a reply in a set amount of time, it will rebroadcast the request except this time the RREQ message will have a longer lifespan and a new ID number. All of the Nodes use the Sequence Number in the RREQ to insure that they do not rebroadcast a RREQ In the example, Node 2 has a route to Node 3 and replies to the RREQ by sending out a RREP. Node 4 on the other hand does not have a route to Node 3 so it rebroadcasts the RREQ. Node 4 Node 5 Node 1 Node 2 RREP Node 3 RREQ RREQ Node 6 does not have a route to Node 3 so it rebroadcasts the RREQ message Node 3 recieves a Route Reply and adds a Route to Node 1 which goes through Node 2 Node 2 has a route to Node 3 it send a Route reply to Node 1. It also send a Route reply to Node 3 so it will know how to contact Node 1. Node 2 Neighbors Node 1 Node 3 Route Reply Packet Dest: Node 1 Src: Node 3 Hop Count: 2 ID: 136 Route Reply Packet Dest: Node 3 Src: Node 1 Hop Count: 2 ID: 136 To Node 3 To Node 1 A Quick Guide to AODV Routing 5 Node 4 Node 1 Node 2 Node 3 RREP RREP RREP Route Reply Packet Dest: Node 3 Src: Node 4 Hop Count: 3 Seq #: 136 Seq #: 136 Node Data Routing List Node Next Hop Seq # Hop Cnt 4 4 78 1 3 2 128 2 2 2 114 1 Seq #: 128 < 136 When Node 1 forwards the RREP it also compares it with the route it has in its Routing List. Since the RREP has a higher Sequence number it is newer than the on in the Routing list. Because of this, Node 1 updates it list with the new route Sequence numbers serve as time stamps. They allow nodes to compare how “fresh” their information on other nodes is. Every time a node sends out any type of message it increase its own Sequence number. Each node records the Sequence number of all the other nodes it talks to. A higher Sequence numbers signifies a fresher route. This it is possible for other nodes to figure out which one has more accurate information. In the example, Node 1 is forwarding a RREP to Node 4. It notices that the route in the RREP has a better Sequence number than the route in it’s Routing List. Node 1 then replaces the route it currently has with the route in the Route Reply Sequence Numbers A Quick Guide to AODV Routing 6 Error Messages The Route Error Message (RERR) allows AODV to adjust routes when Nodes move around. Whenever a Node receives RERR it looks at the Routing Table and removes all the routes that contain the bad Nodes. The diagrams to the left illustrate the three circumstances under which a Node would broadcast a RERR to its neighbors. In the first scenario the Node receives a Data packet that it is supposed to forward but it does not have a route to the destination. The real problem is not that the Node does not have a route; the problem is that some other node thinks that the correct Route to the Destination is through that Node. In the second scenario the Node receives a RERR that cause at least one of its Route to become invalidated. If it happens, the Node would then send out a RERR with all the new Nodes which are now unreachable In the third scenario the Node detects that it cannot communicate with one of its Neighbors. When this happens it looks at the route table for Route that use the Neighbor for a next hop and marks them as invalid. Then it sends out a RERR with the Neighbor and the invalid routes Node 4 Routing Table Node Next Hop Seq # Hop Cnt 4 4 78 1 3 4 128 2 Route Error Node 3 The Node recieves a Route Error message for a Node which is in its Routing Table Node 4 Data Packet Dest: Node 3 Src: Node 1 Data: 010101 ? The Route to the destination of the Packet is unkown! Node 4 Node 5 A link break is detected with the Node's neighbors Routing Table Node Next Hop Seq # Hop Cnt 4 4 78 1 3 5 128 2 5 5 114 1 1. 2. 3. A Quick Guide to AODV Routing 7 AODV Characteristics: • Will find routes only as needed • Use of Sequence numbers to track accuracy of information • Only keeps track of next hop for a route instead of the entire route • Use of periodic HELLO messages to track Neighbors References: • IETF Manet Working Group AODV Draft http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-08.txt uploads/Ingenierie_Lourd/ aodv-guide.pdf