AODV

           The information in this section concerning the Ad Hoc Ondemand Distance Vector Protocol (AODV). AODV is a reactive protocol that means; the routes are created and maintained only when they are needed. The routing table stores the information about the next hop to the destination and a sequence number which is received from the destination and indicating the freshness of the received information. Also the information about the active neighbors is received throughout the discovery of the destination host. When the corresponding route breaks, then the neighbors can be notified. Mainly 4 types of messages are used in this routing protocol that are

a. Hello

b. RREQ

c. RREP

d. RERR

           

                      The main messages in AODV are received via UDP on port 654. The route discovery is used by broadcasting the RREQ message to the neighbors with the requested destination sequence number, which prevents the old information to be replied to the request and also prevents looping problem, which is essential to the traditional distance vector protocols. The route reply use RREP message that can be only generated by the destination host or the hosts who have the information that the destination host is alive and the connection is fresh. This feature enables that the unidirectional links can be detected. When the breakage of the route is noticed the host sends RERR message to the neighbors. The Hello message is periodically sent for maintaining the route information. All the information about the routes in the network is stored in this table. The routing table has the following entries i.e. DSN, flag, next hop, IP address, State, hop count, the list of precursors, Life time and network interface.

                      The AODV protocol is a flat routing protocol it does not need any central administrative system to handle the routing process. Reactive protocols like AODV tend to reduce the control traffic messages overhead at the cost of increased latency in finding new routes. When the link breakage occurs then the host can try to locally repair the link if the destination is no further than specified amount of hops. In order to repair the link the host increase the destination sequence number and broadcasts the RREQ message to the host. The TTL for the IP header must be calculated, so that locally repair process would not spread throughout the network.

Sequence Numbers:

                 The sequence numbers are the key idea for removing the old and invaluable information from the network. The sequence number act as timestamps and prevent this distance vector protocol from the loop problem The destination sequence number for each possible destination host is stored in the routing table. The destination sequence numbers are updated in the routing table when the host receives the message with the greater sequence number. The host can change the destination sequence number in the routing table if it is offering a new route to itself or if some route expires or simply breaks The host also keeps its own sequence number, which must be incremented only in two different cases: before it sends RREQ message and when the host sends a RREP message responding to the RREQ message. In the second case the sequence number must be incremented to the maximum of the current sequence number and the sequence number in the received RREQ message. The sequence numbers must be treated as unsigned integers so that the possible rollovers can occur, AODV protocol supports the sequence number to be rolled over without any problems.

HELLO MESSAGES:

              Although AODV is a reactive protocol it uses the Hello messages periodically to inform its neighbors that the link to the host is alive. The Hello messages are broadcasted with TTL equals to 1, so that the message will not be forwarded further. When host receives the Hello message it will update the lifetime of the host information in the routing table. If the host does not get information from the host’s neighbor for specified amount of time, then the routing information in the routing table is marked as lost. This action generates needed RRER message to inform other hosts of the link breakage. The routes that were created by the Hello message and were not used for any routing actions should not generate the RERR message when the link breakage occurs.

RREQ, RREP and RREP-ACK:

           The route request message (RREQ) is sent when the host does not know the route to the needed destination host or the existed route is expired. The RREQ message includes the destination sequence number which is the last known sequence number of the destination host entry found in the routing table. If there contains no entry for the destination host, then the unknown sequence number flag must be set. The RREQ message also contains the requesting hosts sequence number, which must be incremented beforehand. The RREQ ID field is incremented by one which is found from the last used RREQ message, which was sent by this host. Also the hop count metric must be set to zero and before sending the RREQ message the RREQ ID and its own address must be saved to the buffer for the specified amount of time, so that it recognize the replies Every intermediate host will generate the RREP message and unicast it to the requesting host. Also the intermediate host must generate the gratuitous RREP to the destination host.

The host can generate the route reply message (RREP) if the destination is the host itself or if the route to the destination is valid and has the same or greater destination sequence number, but only if the D field is not set. D field in the RREQ message indicates that only the destination host can reply to the RREQ message. When generating the RREP message host copies the destination address and the requested host’s sequence number to the corresponding RREP message’s fields. If the receiver is the destination host then its own sequence number is incremented and copied to the destination sequence number field. In addition, the hop count is set to zero and the lifetime field of the RREP message is set to the initial timeout value of the host. If the receiver is the intermediate host, then it just copies destination sequence number from the routing table and adds the host address from where it has received RREQ message to the destination address field. Also the host must add the hop count with the lifetime from the routing table to the RREP. The lifetime is calculated by subtracting the current time and the expiration time from the routing table. When the RREP message is created it is sent using unicast to the next hop in order to be delivered to the requested host[1]. The hop count metric is incremented along the path, so at the end, it corresponds to the actual distance between the hosts.

REPAIR:

           When the link breakage occurs then the host can try to locally repair the link if the destination is no further than specified amount of hops. In order to repair the link the host increase the destination sequence number and broadcasts the RREQ message to the host. The host waits for the RREP messages to its RREQ message for specified amount of time. If the RREP message is not received, then it changes the routing table status for the entry to invalid. If host receives the RREP message then the hop count metric is compared. If the hop metric from the message is greater than the previous one then the RERR with the N field set up is broadcasted. The N field in the RERR message indicates that the host has locally repaired the link and the entry in the table should not be deleted. The received RREP message is handled as original RREP message. The repairing of the link before the data is sent to unavailable host is a proactive repairing. Proactive repairing can be inefficient because the risk of repairing the routes that are not used anymore. So the proactive repairing can be used basing on the local traffic and the workload of the network.