AODV Route Discovery
Time Out Time Out
: RREQ : RREP :Valid Route
Route Maintenance
• Periodic Hello message to detect continued presence of neighbours • When a link break is detected
AODV route table entry
• • • • • • • • • Destination IP Address Destination Sequence Number Vaild Destination Sequence Number flag （有效） Network Interface（网络接口模式。设成混搭模式） Hop Count (number of hops needed to reach destination) Next Hop List of Precursors Lifetime (expiration or deletion time of the route) Other State and routing flag (e.g. valid, invalid, repairable, being repaired)
– Node sends a RERR containing list of unreachable destinations due to link break – Receiving nodes forwards RERR to precursors of unreachable destinations
A destination node increments its own sequence number in two circumstances:
• before a node originates a route discovery • before a destination node originates a RREP in response to a RREQ（序号+1）
The route is only updated if the new sequence number
• higher than the destination sequence number in the route table • the sequence numbers are equal, but the hop count is smaller than the existing hop count in the routing table • the sequence number is unknown
• RREP (route reply) is unicast back
– From destination if necessary – From intermediate node if that node has a recent route
AODV Messages
• • • • Route request (RREQ) Route reply (RREP Route error (RERR) Hello messages
• Before sending or forwarding RERR
– Update destination sequence number in routing table entry – Invalidated entry
AODV Local Route Repair
Data packet be buffered
Ad-hoc Networking Example
• Suppose MH1 moves away from MH2 towards MH7, and has active sessions with MH3 and MH6. The following actions occur:
• MH2 notices that its link to MH1 is broken • MH2 checks its routing table, and finds that its link to MH1 was actively in use by MH3 and MH4. • MH2 unicasts an ∞-metric route update, with an incremented destination sequence number, to MH3 and MH4. MH3 may subsequently issue a new route request for MH1. • MH4 also notes that its route to MH1 was actively in use, and forwards the ∞-metric route update to MH6. • MH6 may subsequently issue a new route request for MH1.
Route Reply (RREP) Message Format
Route Error (RERR) Message Format
Link Breakage
• Nodes remember active routes • Next hop breaks -> neighbors using that route are notified • Notification is a RREP with: - metric = ∞ - dest_seqno = previous + 1 and is sent to each active neighbor
A node may change the sequence number in the routing table entry
• it is itself the destination node, and offers a new route to itself • it receives an AODV message with new information about the sequence number for a destination node • the path towards the destination node expires or breaks
B
A
K
D N
Inclusion
• AODV has the following features:
- Nodes store only the routes that are needed - Need for broadcast is minimized - Reduces memory requirements and needless duplications - Quick response to link breakage in active routes - Loop-free routes maintained by use of destination sequence numbers - Scalable to large populations of nte Discovery
• RREQ (route request) is broadcast
– Reverse path is set up along the way – RREQ message contains < bcast_id; dest_ip; dest_seqno;src_ip; src_seqno; hop_count >
Ad hoc On Demand Vector routing (AODV路由协议)
• AODV是基于距离矢量算法的路由协议。AODV只在路由表 中保持需要的路由，通常每一个目的节点保存一条路由，每 条路由信息都有生存期，若超时则该项路由信息无效。 AODV采用每个目的节点中保存的序列号来保持路由信息的 有效性，所有的路由分组都保存序列号。 • Route is set up only when requested • Nodes not along active paths not required to maintain route information • Avoids the Bellman-Ford “counting to infinity” problem • Link breakages notification only to affected nodes • Multicasting（多播路由算法） • Key Feature: Use of Destination sequence Number（目的 节点序列号） • Loop freedom（路由回环）
完整性
n • 它的路由表中通往目节点D的链路为 ( n , n )， j 为 n 的邻节点，可知链路 ( n , n )一定存在，即 i (n , n ) (n , n ) (n , n ) （ j ） 所以 n i 是节点 n j到目的节点D路由中记录的 下一跳节点。是由 i 的任意性，我们得到在 邻节不变的情况下，AODV通过记录到目的 节点的下一跳节点的IP地址，在Ad hoc网络 中可以形成一条完整的路由。
• Example
RREQ S E F C G H I K D N J
B
A
RREQ <S, 11, 1, D, 0, 1> [D, S, 1, time, 11] S E F C G H I Reverse pointer J
B
A
K
D N
Forward pointer RREP <S, D, 12, 3, lifetime> S E F C G H I timeout J