Ad Hoc On-Demand Distance Vector (AODV)
An ad hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. AODV is a novel algorithm for the operation of such ad hoc networks. Each mobile host operates as a specialized router, and routes are obtained as needed (i.e., on demand with little or no reliance on periodic advertisements). The AODV routing algorithm is quite suitable for a dynamic self-starting networkas required by users wishing to utilize ad hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements.
AODV uses symmetric links between neighboring nodes. It does not attempt to follow paths between nodes when one of the nodes cannot hear the other one. Nodes do not lie on active paths; they neither maintain any routing information nor participate in any periodic routing table exchanges. Further, a node does not have to discover and maintain a route to another node until the two need to communicate unless the former node is offering its services as an intermediate forwarding station to maintain connectivity between two other nodes. When the local connectivity of the mobile node is of interest, each mobile node can become aware of the other nodes in its neighborhood by the use of several techniques, including local (not systemwide) broadcasts known as Hello messages. The routing tables of the nodes within the neighborhood are organized to optimize response
time to local movements and provide quick response time for requests for establishment of new routes.
The algorithm’s primary objectives are as follows:
1.To broadcast discovery packets only when necessary.
2.To distinguish between local connectivity management neighborhood detection and general topology maintenance.
3.To disseminate information about changes in local connectivity to those neighboring mobile nodes that are likely to need the information.
AODV uses a broadcast route discovery mechanism as is also used with modifications in the DSR algorithm. Instead of source routing, however, AODV relies on dynamically establishing route table entries at intermediate nodes. This difference pays off in networks with many nodes where a larger overhead is incurred by carrying source routes in each data packet.
To maintain the most recent routing information between nodes, we borrow the concept of destination sequence numbers from DSDV. Unlike in DSDV, however, each ad hoc node maintains a monotonically increasing sequence number counter which is used to supersede stale cached routes. The combination of these techniques yields an algorithm that uses bandwidth efficiently by minimizing the network load for control, and data traffic is responsive to changes in topology and ensures loop-free routing.
Path Discovery
The path discovery process is initiated whenever a source node needs to communicate with another node for which it has no routing information in its table. Every node maintains two separate counters: a node sequence number and a broadcast ID. The source node initiates path discovery by broadcasting a Route REQuest (RREQ) packet to its neighbors.
The RREQ contains the following fields:
<source_addr source sequence# broadcast id dest_addr dest sequence# hop cnt>
The pair <source_addr, broadcast_id> uniquely identifies an RREQ. broadcast_id is incremented whenever the source issues a new RREQ. Each neighbor either satisfies the RREQ by sending a Route REPly (RREP) back to the source, or broadcasts the RREQ to its own neighbors after increasing the hop_cnt. Notice that a node may receive multiple copies of the same route broadcast packet from various neighbors. When an intermediate node receives an RREQ, if it has already received an RREQ with the same broadcast_id and source address, it drops the redundant RREQ and
does not rebroadcast it. If a node cannot satisfy the RREQ, it keeps track of the following information to implement the reverse-path setup as well as the forwardpath setup that will accompany the transmission of the eventual RREP.
Destination IP address
Source IP address
Broadcast ID
Expiration time for reverse-path route entry
Source node’s sequence number
The RREQ contains the following fields:
<source_addr source sequence# broadcast id dest_addr dest sequence# hop cnt>
The pair <source_addr, broadcast_id> uniquely identifies an RREQ. broadcast_id is incremented whenever the source issues a new RREQ. Each neighbor either satisfies the RREQ by sending a Route REPly (RREP) back to the source, or broadcasts the RREQ to its own neighbors after increasing the hop_cnt. Notice that a node may receive multiple copies of the same route broadcast packet from various neighbors. When an intermediate node receives an RREQ, if it has already received an RREQ with the same broadcast_id and source address, it drops the redundant RREQ and
does not rebroadcast it. If a node cannot satisfy the RREQ, it keeps track of the following information to implement the reverse-path setup as well as the forwardpath setup that will accompany the transmission of the eventual RREP.
Destination IP address
Source IP address
Broadcast ID
Expiration time for reverse-path route entry
Source node’s sequence number
Reverse-Path Setup
There are two sequence numbers (in addition to the broadcast_id) included in anRREQ: the source sequence number and the last destination sequence number known to the source. The source sequence number is used to maintain freshness information about the reverse route to the source, and the destination sequence number specifies how fresh a route to the destination must be before it can be
accepted by the source. As the RREQ travels from a source to various destinations, it automatically sets up the reverse path from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of the RREQ. These reverse-path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.
accepted by the source. As the RREQ travels from a source to various destinations, it automatically sets up the reverse path from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of the RREQ. These reverse-path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.
Forward-Path Setup
Eventually, an RREQ will arrive at a node (possibly the destination itself) that possesses a current route to the destination. The receiving node first checks that the RREQ was received over a bidirectional link. If an intermediate node has a route entry for the desired destination, it determines whether the route is current by comparing the destination sequence number in its own route entry to the destination sequence number in the RREQ. If the RREQ’s sequence number for the destination is greater than that recorded by the intermediate node, the intermediate node must not use its recorded route to respond to the RREQ. Instead, the intermediate node rebroadcasts the RREQ. The intermediate node can reply only when it has a route with a sequence number that is greater than or equal to that contained in the RREQ. If it does have a current route to the destination and if
the RREQ has not been processed previously, the node then unicasts a route reply packet (RREP) back to its neighbor from which it received the RREQ.
the RREQ has not been processed previously, the node then unicasts a route reply packet (RREP) back to its neighbor from which it received the RREQ.
An RREP contains the following information:
<source_addr, dest_addr, dest_sequence #, hop_cnt, lifetime>
By the time a broadcast packet arrives at a node that can supply a route to the destination,
a reverse path has been established to the source of the RREQ. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination. The forward path setup as the RREP travels from the destination D to the source node S. Nodes that are not along the path determined by the RREP will time out after ACTIVE_ROUTE_TIMEOUT (3000 milliseconds) and will delete the reverse pointers.
A node receiving an RREP propagates the first RREP for a given source node toward that source. If it receives further RREPs, it updates its routing information and propagates the RREP only if the RREP contains either a greater destination sequence number than the previous RREP or the same destination sequence number with a smaller hop count. It suppresses all other RREPs it receives. This decreases the number of RREPs propagating toward the source while also ensuring the quickest and most up-to-date routing information. The source node can begin data transmission as soon as the first RREP is received and can later update its routing information if it learns of a better route.
<source_addr, dest_addr, dest_sequence #, hop_cnt, lifetime>
By the time a broadcast packet arrives at a node that can supply a route to the destination,
a reverse path has been established to the source of the RREQ. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination. The forward path setup as the RREP travels from the destination D to the source node S. Nodes that are not along the path determined by the RREP will time out after ACTIVE_ROUTE_TIMEOUT (3000 milliseconds) and will delete the reverse pointers.
A node receiving an RREP propagates the first RREP for a given source node toward that source. If it receives further RREPs, it updates its routing information and propagates the RREP only if the RREP contains either a greater destination sequence number than the previous RREP or the same destination sequence number with a smaller hop count. It suppresses all other RREPs it receives. This decreases the number of RREPs propagating toward the source while also ensuring the quickest and most up-to-date routing information. The source node can begin data transmission as soon as the first RREP is received and can later update its routing information if it learns of a better route.
Route Table Management
In addition to the source and destination sequence numbers, other useful information
is also stored in the route table entries and is called the “soft state” associated with the entry. Associated with reverse-path routing entries is a timer called the “route request expiration timer.” The purpose of this timer is to purge reverse-path routing entries from those nodes that do not lie on the path from the source to the destination. The expiration time depends upon the size of the ad hoc network. Another important parameter associated with routing entries is the route-cachingtimeout,
or the time after which the route is considered to be invalid. In each routing table entry, the address of active neighbors through which packets for the given destination are received is also maintained. A neighbor is considered active for that destination if it originates or relays at least one packet for that destination within themost recent active timeout period. This information is maintained so that all active source nodes can be notified when a link along a path to the destination breaks. A route entry is considered active if it is in use by any active neighbors. The path from a source to a destination, which is followed by packets along active route entries, is called an “active path.” Note that, as with DSDV, all routes in the route table are tagged with destination sequence numbers, which guarantee that no routing loops can form, even under extreme conditions of out-of-order packet delivery and high node mobility. A mobile node maintains a route table entry for each destination of interest. Each route table entry contains the following information:
Destination
Next hop
Number of hops (metric)
Sequence number for the destination
Active neighbors for this route
Expiration time for the route table entry
Each time a route entry is used to transmit data from a source toward a destination,
the timeout for the entry is reset to the current time plus the active route
timeout. If a new route is offered to a mobile node, the mobile node compares the
destination sequence number of the new route to the destination sequence numberfor
the current
route. The route with the greater sequence number is chosen. If the
sequence numbers are the same, then the new route is selected only if it has a
smaller metric (a fewer numbers of hops) to the destination.
is also stored in the route table entries and is called the “soft state” associated with the entry. Associated with reverse-path routing entries is a timer called the “route request expiration timer.” The purpose of this timer is to purge reverse-path routing entries from those nodes that do not lie on the path from the source to the destination. The expiration time depends upon the size of the ad hoc network. Another important parameter associated with routing entries is the route-cachingtimeout,
or the time after which the route is considered to be invalid. In each routing table entry, the address of active neighbors through which packets for the given destination are received is also maintained. A neighbor is considered active for that destination if it originates or relays at least one packet for that destination within themost recent active timeout period. This information is maintained so that all active source nodes can be notified when a link along a path to the destination breaks. A route entry is considered active if it is in use by any active neighbors. The path from a source to a destination, which is followed by packets along active route entries, is called an “active path.” Note that, as with DSDV, all routes in the route table are tagged with destination sequence numbers, which guarantee that no routing loops can form, even under extreme conditions of out-of-order packet delivery and high node mobility. A mobile node maintains a route table entry for each destination of interest. Each route table entry contains the following information:
Destination
Next hop
Number of hops (metric)
Sequence number for the destination
Active neighbors for this route
Expiration time for the route table entry
Each time a route entry is used to transmit data from a source toward a destination,
the timeout for the entry is reset to the current time plus the active route
timeout. If a new route is offered to a mobile node, the mobile node compares the
destination sequence number of the new route to the destination sequence numberfor
the current
route. The route with the greater sequence number is chosen. If the
sequence numbers are the same, then the new route is selected only if it has a
smaller metric (a fewer numbers of hops) to the destination.
Path Maintenance
Movement of nodes not lying along an active path does not affect the routing to
that path’s destination. If the source node moves during an active session, it can
reinitiate the route discovery procedure to establish a new route to the destination.
When either the destination or some intermediate node moves, a special RREP is sent
to the affected source nodes. Periodic Hello messages can be used to ensure symmetric
links, as well as to detect link failures. Alternatively, and with far less latency, such
failures could be detected by using Link-Layer ACKnowledgments (LLACKs). A link
failure is also indicated if attempts to forward a packet to the next hop fail.
that path’s destination. If the source node moves during an active session, it can
reinitiate the route discovery procedure to establish a new route to the destination.
When either the destination or some intermediate node moves, a special RREP is sent
to the affected source nodes. Periodic Hello messages can be used to ensure symmetric
links, as well as to detect link failures. Alternatively, and with far less latency, such
failures could be detected by using Link-Layer ACKnowledgments (LLACKs). A link
failure is also indicated if attempts to forward a packet to the next hop fail.
Once the next hop becomes unreachable, the node upstream of the break
propagates an unsolicited RREP with a fresh sequence number, that is, a sequence
numberthat is one greater than the previously known sequence number and hop
count of all active upstream neighbors. Those nodes subsequently relay that messageto
their active neighbors and so on. This process continues until all active source
nodes are notified; it terminates because AODV maintains only loop-free routes,
and there are only a finite number of nodes in the ad hoc network.
Upon receiving notification of a broken link, source nodes can restart the discovery
process if they still require a route to the destination. To determine whether
a route is still needed, a node may check whether the route has been used recently
as well as inspect upper-level protocol control blocks to see whether connections
remain open using the indicated destination. If the source node or any other node
along the previous route decides it would like to rebuild the route to the destination,
it sends out an RREQ with a destination sequence number of one greater than
the previously known sequence number to ensure that it builds a new viable route,
and that no nodes reply if they still regard the previous route as valid.
propagates an unsolicited RREP with a fresh sequence number, that is, a sequence
numberthat is one greater than the previously known sequence number and hop
count of all active upstream neighbors. Those nodes subsequently relay that messageto
their active neighbors and so on. This process continues until all active source
nodes are notified; it terminates because AODV maintains only loop-free routes,
and there are only a finite number of nodes in the ad hoc network.
Upon receiving notification of a broken link, source nodes can restart the discovery
process if they still require a route to the destination. To determine whether
a route is still needed, a node may check whether the route has been used recently
as well as inspect upper-level protocol control blocks to see whether connections
remain open using the indicated destination. If the source node or any other node
along the previous route decides it would like to rebuild the route to the destination,
it sends out an RREQ with a destination sequence number of one greater than
the previously known sequence number to ensure that it builds a new viable route,
and that no nodes reply if they still regard the previous route as valid.
Local Connectivity Management
Nodes learn of their neighbors in one of two ways. Whenever a node receives a broadcast from a neighbor, it updates its local connectivity information to ensure that it includes this neighbor. In the event that a node has not sent any packets to all of its active downstream neighbors within a Hello interval, it broadcasts to its neighbors a Hello message, a special unsolicited RREP containing its identity and sequence number. The node’s sequence number is not changed for Hello message
transmissions. This Hello message is prevented from being rebroadcast outside the
neighborhood of the node because it contains a Time-To-Live (TTL) value of one. Neighbors that receive this packet update their local connectivity information to the node. Receiving a broadcast or a Hello message from a new neighbor or failing to receive allowed Hello loss consecutive Hello messages from a node previously in the neighborhood is an indication that the local connectivity has changed. Failing to receive Hello messages from inactive neighbors does not trigger any protocol
action. If Hello messages are not received from the next hop along an active path, the active neighbors using that next hop are sent notification of link failure. We have determined that the optimal value for allowed Hello loss is two. The local connectivity management with Hello messages can also be used to ensure that only nodes with bidirectional connectivity are considered to be neighbors. For this purpose,each Hello sent by a node lists the nodes from which it has heard. Each
node checks to make sure that it uses only routes to neighbors that have heard the node’s Hello message. To save local bandwidth, such checking should be performed only if explicitly configured into the nodes.
transmissions. This Hello message is prevented from being rebroadcast outside the
neighborhood of the node because it contains a Time-To-Live (TTL) value of one. Neighbors that receive this packet update their local connectivity information to the node. Receiving a broadcast or a Hello message from a new neighbor or failing to receive allowed Hello loss consecutive Hello messages from a node previously in the neighborhood is an indication that the local connectivity has changed. Failing to receive Hello messages from inactive neighbors does not trigger any protocol
action. If Hello messages are not received from the next hop along an active path, the active neighbors using that next hop are sent notification of link failure. We have determined that the optimal value for allowed Hello loss is two. The local connectivity management with Hello messages can also be used to ensure that only nodes with bidirectional connectivity are considered to be neighbors. For this purpose,each Hello sent by a node lists the nodes from which it has heard. Each
node checks to make sure that it uses only routes to neighbors that have heard the node’s Hello message. To save local bandwidth, such checking should be performed only if explicitly configured into the nodes.
No comments:
Post a Comment