RFC 3561
Ad hoc On-Demand Distance Vector (AODV) Routing
RFC 3561: Ad hoc On-Demand Distance Vector (AODV) Routing 💖
okay bestie, this is RFC 3561 and it's giving classic AODV era 🦋 It's an Experimental doc from July 2003, so it's not an Internet standard. It's a proposal the community is invited to poke at. The authors are C. Perkins (Nokia Research Center), E. Belding-Royer (University of California, Santa Barbara), and S. Das (University of Cincinnati). Its header doesn't list anything it obsoletes or updates, so it stands on its own 🧚
Status of this Memo 📜
ok so this memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind 🙈 The authors actually want feedback, so discussion and suggestions for improvement are requested ✨ And distribution of this memo is unlimited, so share it with your whole group chat 💅
Copyright Notice 🎀
the copyright line reads:
Copyright (C) The Internet Society (2003). All Rights Reserved.
Abstract 🌈
the Ad hoc On-Demand Distance Vector (AODV) routing protocol is built for mobile nodes in an ad hoc network 📱 It's giving quick adaptation to dynamic link conditions, low processing and memory overhead, and low network utilization 🔥 It finds unicast routes to destinations inside the ad hoc network too 🦋
the big flex is loop freedom. AODV uses destination sequence numbers to keep loops away at all times, even when routing control messages get delivered in weird, anomalous ways 💀 That dodges the classic distance vector drama of "counting to infinity" 👑
Table of Contents 🗂️
1. Introduction ............................................... 2
2. Overview .................................................. 3
3. AODV Terminology ........................................... 4
4. Applicability Statement .................................... 6
5. Message Formats ............................................ 7
5.1. Route Request (RREQ) Message Format ................... 7
5.2. Route Reply (RREP) Message Format ..................... 8
5.3. Route Error (RERR) Message Format ..................... 10
5.4. Route Reply Acknowledgment (RREP-ACK) Message Format .. 11
6. AODV Operation ............................................. 11
6.1. Maintaining Sequence Numbers .......................... 11
6.2. Route Table Entries and Precursor Lists ............... 13
6.3. Generating Route Requests ............................. 14
6.4. Controlling Dissemination of Route Request Messages ... 15
6.5. Processing and Forwarding Route Requests .............. 16
6.6. Generating Route Replies .............................. 18
6.6.1. Route Reply Generation by the Destination ...... 18
6.6.2. Route Reply Generation by an Intermediate
Node ........................................... 19
6.6.3. Generating Gratuitous RREPs .................... 19
6.7. Receiving and Forwarding Route Replies ................ 20
6.8. Operation over Unidirectional Links ................... 21
6.9. Hello Messages ........................................ 22
6.10 Maintaining Local Connectivity ........................ 23
6.11 Route Error (RERR) Messages, Route Expiry and Route
Deletion .............................................. 24
6.12 Local Repair .......................................... 26
6.13 Actions After Reboot ................................. 27
6.14 Interfaces ............................................ 28
7. AODV and Aggregated Networks ............................... 28
8. Using AODV with Other Networks ............................. 29
9. Extensions ................................................. 30
9.1. Hello Interval Extension Format ....................... 30
10. Configuration Parameters ................................... 31
11. Security Considerations .................................... 33
12. IANA Considerations ........................................ 34
13. IPv6 Considerations ........................................ 34
14. Acknowledgments ............................................ 34
15. Normative References ....................................... 35
16. Informative References ..................................... 35
17. Authors' Addresses ......................................... 36
18. Full Copyright Statement ................................... 371. Introduction ✨
the Ad hoc On-Demand Distance Vector (AODV) algorithm gives you dynamic, self-starting, multihop routing between participating mobile nodes that want to set up and maintain an ad hoc network 🧚 It's so good at getting routes fast for brand-new destinations 🏃♀️💨 And it doesn't make nodes keep routes to destinations that aren't in active communication, which is very minimalist of it 🌸
AODV also handles link breakages and topology changes in a timely manner 💅 It's loop-free, and by dodging the Bellman-Ford "counting to infinity" problem, it converges quickly whenever the ad hoc topology changes (typically when a node moves around) 🔥 When a link breaks, the affected set of nodes gets notified so they can invalidate any routes that used that lost link 😭
one thing that makes AODV iconic is that every route entry carries a destination sequence number 👑 The destination makes that number and includes it with any route information it sends to requesting nodes. Sequence numbers keep loop freedom intact and are simple to program 🫶 So when a requesting node is choosing between two routes to the same destination, it is required to select the one with the greatest sequence number 💜
2. Overview 🌸
okay so the message types AODV defines are Route Requests (RREQs), Route Replies (RREPs), and Route Errors (RERRs) 💌 They come in over UDP, and normal IP header processing applies. For example, the requesting node is expected to use its IP address as the Originator IP address for the messages 🦋 Broadcast messages use the IP limited broadcast address, 255.255.255.255 📣 That means those messages don't get blindly forwarded 🙅♀️
BUT AODV does need certain messages, like RREQ, to be spread widely, maybe across the whole ad hoc network 🌍 How far an RREQ goes is set by the TTL in the IP header. Fragmentation is typically not required 🎀
as long as two endpoints of a connection already have valid routes to each other, AODV basically sits this one out 😌 When a node needs a route to a new destination, it broadcasts a RREQ to go find one 📡 A route can be found when the RREQ reaches either the destination itself, or an intermediate node with a 'fresh enough' route to it 💖 A 'fresh enough' route is a valid route entry for the destination whose sequence number is at least as great as the one in the RREQ 🌈 The route then gets handed back by unicasting a RREP to the origin of the RREQ 💫
every node that receives the request caches a route back to the request's originator. That's the secret sauce: the RREP can be unicast from the destination (or from any intermediate node that can satisfy the request) along a path back to that originator 🧚♀️✨
nodes keep an eye on the link status of next hops in active routes 👀 When a link break in an active route is detected, a RERR message goes out to tell other nodes that the link is gone 💔 The RERR names the destinations (possibly subnets) that can no longer be reached over the broken link 🙈
to make that reporting work, each node keeps a "precursor list" 📋 It holds the IP address of each neighbor that's likely to use this node as a next hop toward each destination. The easiest place to pick up precursor info is while generating an RREP, which by definition has to be sent to a node in a precursor list (see section 6.6) 🫶 And if the RREP has a nonzero prefix length, the originator of the RREQ that solicited the RREP gets included among the precursors for the subnet route. It's not specifically for the particular destination, so no mixing those up bestie 🍓
RREQs can also show up for a multicast IP address. This doc does not specify full processing for those yet 🙃 For example, whoever originates an RREQ for a multicast IP address may have to follow special rules. Still, it matters a LOT that intermediate nodes which aren't set up as originating or destination nodes for IP multicast addresses (and don't have any special multicast processing) can still help multicast work correctly 🔥 For those multicast-unaware nodes, processing for a multicast IP address used as a destination IP address MUST be carried out in the same way as for any other destination IP address 💅
AODV is a routing protocol, so it's all about managing the route table 📚 Route table info has to be kept even for short-lived routes, like the ones made to temporarily store reverse paths back toward nodes that originated RREQs ⏳ AODV uses these fields with each route table entry:
Destination IP AddressDestination Sequence NumberValid Destination Sequence Number flagOther state and routing flags(e.g., valid, invalid, repairable, being repaired)Network InterfaceHop Count(number of hops needed to reach destination)Next HopList of Precursors(described in Section 6.2)Lifetime(expiration or deletion time of the route)
managing the sequence number is crucial for avoiding routing loops 🌀 That holds even when links break and a node can't reach anyone to supply its own sequence number info anymore 😱 A destination becomes unreachable when a link breaks or gets deactivated. When that happens, the route is invalidated by sequence number operations and by marking the route table entry's state as invalid ✨ See section 6.1 for details 📖
3. AODV Terminology ✨
Okay bestie, first things first: this spec uses the usual meanings [1] for capitalized words like MUST and SHOULD 💅 to show how strict each requirement is. It also defines some extra AODV terms that aren't already covered in [3] 📖
active route 🛣️
A route to a destination with a routing table entry marked as valid. Only active routes can be used to forward data packets, so this is the good stuff 💖
broadcast 📢
Broadcasting means sending to the IP Limited Broadcast address, 255.255.255.255. A broadcast packet may not be blindly forwarded, but broadcasting is super useful for spreading AODV messages around the whole ad hoc network 🌐
destination 🎯
An IP address that data packets are headed to. It's the same as "destination node". A node knows it's the destination node for a typical data packet when its address shows up in the right field of the IP header. Routes for destination nodes come from AODV itself, which puts the IP address of the wanted destination node into route discovery messages 🧚
forwarding node 🔁
A node that agrees to forward packets meant for another node, passing them along to a next hop that's closer to the unicast destination. That path has to be set up using routing control messages first ✨
forward route ➡️
A route set up to send data packets from the node that starts a Route Discovery towards the destination it wants 🌸
invalid route 🥀
A route that has expired, shown by an invalid state in its routing table entry. Invalid routes stick around to hold previously valid route info for a long stretch of time. They can't be used to forward data packets, but they're still useful for route repairs and for future RREQ messages 💜
Expired doesn't mean useless, bestie. Invalid routes are kept around on purpose 🫶
originating node 🚀
A node that starts an AODV route discovery message, which other nodes in the ad hoc network then process and maybe retransmit. For example, the node that kicks off a Route Discovery and broadcasts the RREQ message is the originating node of that RREQ 👑
reverse route ⬅️
A route set up to send a reply (RREP) packet back to the originator, coming from the destination or from an intermediate node that has a route to the destination 🦋
sequence number 🔢
A number that only goes up, maintained by each originating node. In AODV routing protocol messages, other nodes use it to figure out how fresh the info from the originating node is 🍓
valid route 🔗
See active route. Same vibes, different name 💅
4. Applicability Statement 🌈
AODV is made for mobile ad hoc networks with anywhere from tens to thousands of mobile nodes 📱 It handles low, moderate, and pretty high mobility rates, plus all kinds of data traffic levels 🚗💨 Here's the catch though: AODV is designed for networks where every node can trust every other node, either because of preconfigured keys or because it's known there are no malicious intruder nodes 🔐 AODV was built to cut down on control traffic and get rid of overhead on data traffic, all to make it scale better and perform better 🎀
5. Message Formats 💌
5.1. Route Request (RREQ) Message Format 📨
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |J|R|G|D|U| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RREQ ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Here's the RREQ layout above, and these are its fields 👀
Type:1🏷️J: Join flag, reserved for multicast 🤝R: Repair flag, reserved for multicast 🔧G: Gratuitous RREP flag. It says whether a gratuitous RREP should be unicast to the node named in the Destination IP Address field (see sections 6.3, 6.6.3) 💫D: Destination only flag. It says only the destination may respond to this RREQ (see section 6.5) 🎯U: Unknown sequence number. It says the destination sequence number is unknown (see section 6.3) ❓Reserved: Sent as 0, ignored on reception 🫥Hop Count: How many hops it took to get from the Originator IP Address to the node handling the request 🐾RREQ ID: A sequence number that uniquely identifies this RREQ, read together with the originating node's IP address 🆔Destination IP Address: The IP address of the destination you want a route to 🎀Destination Sequence Number: The latest sequence number the originator has ever received for any route towards the destination 📈Originator IP Address: The IP address of the node that started the Route Request 🌟Originator Sequence Number: The current sequence number to use in the route entry pointing back to the originator of the route request 🧾
5.2. Route Reply (RREP) Message Format 💬
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |R|A| Reserved |Prefix Sz| Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Now the RREP layout, with its fields 🌷
Type:2🏷️R: Repair flag, used for multicast 🔧A: Acknowledgment required. See sections 5.4 and 6.7 🙋Reserved: Sent as 0, ignored on reception 🫥Prefix Size: If it's nonzero, the 5-bit Prefix Size says the indicated next hop may be used for any nodes sharing the same routing prefix (as defined by the Prefix Size) as the requested destination 🧩Hop Count: How many hops it is from the Originator IP Address to the Destination IP Address. For multicast route requests, this shows the number of hops to the multicast tree member that sent the RREP 🌳Destination IP Address: The IP address of the destination the route is being supplied for 🎯Destination Sequence Number: The destination sequence number tied to the route 🔢Originator IP Address: The IP address of the node that started the RREQ the route is being supplied for 🌟Lifetime: How long, in milliseconds, nodes that receive the RREP treat the route as valid ⏰
Note that the Prefix Size lets a subnet router supply a route for every host in the subnet defined by the routing prefix. That subnet is determined by the subnet router's IP address and the Prefix Size 🏠 To make use of this, the subnet router has to guarantee reachability to all the hosts sharing the indicated subnet prefix. See section 7 for details 🔍 When the prefix size is nonzero, any routing information (and precursor data) MUST be kept with respect to the subnet route, not the individual destination IP address on that subnet 🧠
The 'A' bit is used when the link the RREP is sent over may be unreliable or unidirectional 🛤️ When the RREP message has the 'A' bit set, the receiver of the RREP is expected to send back a RREP-ACK message. See section 6.8 💌
5.3. Route Error (RERR) Message Format 🚨
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |N| Reserved | DestCount |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Destination IP Address (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Destination Sequence Number (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|
| Additional Unreachable Destination IP Addresses (if needed) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Additional Unreachable Destination Sequence Numbers (if needed)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Last but not least, the RERR layout and its fields 💀
Type:3🏷️N: No delete flag. It's set when a node has done a local repair of a link, and upstream nodes should not delete the route 🛠️Reserved: Sent as 0, ignored on reception 🫥DestCount: How many unreachable destinations are in the message. It MUST be at least 1 🔢Unreachable Destination IP Address: The IP address of the destination that became unreachable because of a link break 💔Unreachable Destination Sequence Number: The sequence number in the route table entry for the destination listed in the previous Unreachable Destination IP Address field 📋
The RERR message gets sent whenever a link break makes one or more destinations unreachable from some of the node's neighbors 🧭 See section 6.2 for how to keep the right records for that decision, and section 6.11 for how to build the list of destinations 🗒️
5.4. Route Reply Acknowledgment (RREP-ACK) Message Format 💌
okay bestie, the RREP-ACK is the tiny "got it!" message 🫶 It MUST be sent in response to a RREP message that has the 'A' bit set (check section 5.2 for that). This usually happens when unidirectional links could stop a Route Discovery cycle from finishing, which is a whole vibe we dig into in section 6.8 🙈
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Type 4
Reserved Sent as 0; ignored on reception.So Type is 4 and Reserved gets sent as 0, and receivers just ignore it 💅
6. AODV Operation ⚙️
this section is all about when nodes generate Route Request (RREQ), Route Reply (RREP) and Route Error (RERR) messages for unicast traffic towards a destination, and how the message data gets handled 🦋 to process these messages correctly, you need to keep some state info in the route table entries for the destinations you care about 📚
all AODV messages are sent to port 654 using UDP ✨
6.1. Maintaining Sequence Numbers 🔢
every route table entry at every node MUST include the latest info it has about the sequence number for the IP address of the destination node that entry is for 💖 this is called the "destination sequence number" 👑 it gets updated whenever a node gets new (aka not stale) sequence number info from RREQ, RREP, or RERR messages about that destination. AODV counts on every node owning and maintaining its own destination sequence number so that routes towards that node stay loop-free 🔁 a destination node bumps its own sequence number in two situations:
- Right before a node starts a route discovery, it MUST increment its own sequence number. This stops conflicts with reverse routes already set up towards the originator of a RREQ 🙅♀️
- Right before a destination node sends out a RREP in response to a RREQ, it MUST update its own sequence number to the maximum of its current sequence number and the destination sequence number in the RREQ packet 🌸
when the destination increments its sequence number, it MUST treat that value as an unsigned number 🧚 for rollover, if the sequence number is already the biggest possible 32-bit unsigned integer, 4294967295, then after incrementing it becomes 0. but if the sequence number is 2147483647, which is the biggest positive integer with 2's complement 32-bit math, the next value is 2147483648, the most negative integer in that same system 🌈 how negative numbers are represented doesn't matter for incrementing AODV sequence numbers. comparing two AODV sequence numbers is a different story, which is covered below 💜
to figure out whether info about a destination is stale, the node compares its current sequence number with the one in the incoming AODV message. this comparison MUST be done using signed 32-bit arithmetic, because that's what makes rollover work 🤯 if subtracting the currently stored sequence number from the incoming one gives a result less than zero, then the info about that destination in the AODV message MUST be discarded, since it's older than what the node already has 🗑️
there's one other time a node can change the destination sequence number in one of its route table entries: when a link to the next hop towards that destination is lost or expires 🔗💀 the node figures out which destinations use that next hop by checking its routing table. then, for each of those destinations, it increments the sequence number and marks the route as invalid (see also sections 6.11 and 6.12) 🙃 if an affected destination's route entry is marked invalid and the node gets routing info that's fresh enough (meaning the sequence number is at least equal to the recorded one), the node SHOULD update its route table info using what's in that update ✨
a node can only change the sequence number in a destination's routing table entry if:
- it is itself the destination node, and it offers a new route to itself, or
- it receives an AODV message with new info about the sequence number for a destination node, or
- the path towards the destination node expires or breaks.
6.2. Route Table Entries and Precursor Lists 📚
when a node gets an AODV control packet from a neighbor, or creates or updates a route for a particular destination or subnet, it checks its route table for an entry for that destination 🔍 if there's no entry for it yet, one gets created 🆕 the sequence number either comes from the control packet, or the valid sequence number field is set to false 🙈 the route only gets updated if the new sequence number is either:
- (i) higher than the destination sequence number in the route table, or
- (ii) equal, but the hop count (of the new info) plus one is smaller than the existing hop count in the routing table, or
- (iii) unknown.
the Lifetime field of the routing table entry either comes from the control packet, or gets initialized to ACTIVE_ROUTE_TIMEOUT ⏰ then the route can be used to send any queued data packets and to fulfill any outstanding route requests 🎀
every time a route is used to forward a data packet, the Active Route Lifetime for the source, the destination, and the next hop on the path to the destination gets updated to be no less than the current time plus ACTIVE_ROUTE_TIMEOUT 💅 since the route between each originator and destination pair is expected to be symmetric, the Active Route Lifetime for the previous hop, along the reverse path back to the IP source, also gets updated to be no less than the current time plus ACTIVE_ROUTE_TIMEOUT 🦋 an Active Route's lifetime gets refreshed every time the route is used, whether the destination is a single node or a subnet ✨
for every valid route a node keeps as a routing table entry, the node also keeps a list of precursors that might be forwarding packets on that route 🧚♀️ those precursors get notified by the node if the loss of the next hop link gets detected 💔 the precursor list in a routing table entry has the neighboring nodes that a route reply was generated for or forwarded to 📮
6.3. Generating Route Requests 📣
a node sends out a RREQ when it decides it needs a route to a destination and doesn't have one available 🙋♀️ that can happen if the destination is totally new to the node, or if a previously valid route to it expires or gets marked invalid 💀 the Destination Sequence Number field in the RREQ is the last known destination sequence number for that destination, copied from the Destination Sequence Number field in the routing table 📋 if no sequence number is known, the unknown sequence number flag MUST be set 🚩 the Originator Sequence Number in the RREQ is the node's own sequence number, which gets incremented before it's put into the RREQ 🔼 the RREQ ID field goes up by one from the last RREQ ID the current node used 🔢 each node only keeps one RREQ ID 🫶 and the Hop Count field starts at zero 🌱
before broadcasting the RREQ, the originating node buffers the RREQ ID and the Originator IP address (its own address) for PATH_DISCOVERY_TIME ⏳ that way, when the node gets the same packet again from its neighbors, it won't reprocess and re-forward it 🙅♀️ sneaky loop prevention, iconic 👑
an originating node usually expects to have bidirectional communication with a destination node 🤝 in that case, it's not enough for the originating node to have a route to the destination; the destination also has to have a route back to the originating node 🔄 to make that happen as efficiently as possible, any RREP generated by an intermediate node (as in section 6.6) for delivery to the originating node SHOULD come with some action that tells the destination about a route back to the originator 📣 the originating node picks this mode for the intermediate nodes by setting the 'G' flag. section 6.6.3 has the details on what intermediate nodes do when they get a RREQ with the 'G' flag set 🧚
a node SHOULD NOT originate more than RREQ_RATELIMIT RREQ messages per second 🚦 after broadcasting a RREQ, the node waits for a RREP (or any other control message with current info about a route to the right destination) ⏳ if no route shows up within NET_TRAVERSAL_TIME milliseconds, the node MAY try again by broadcasting another RREQ, up to a maximum of RREQ_RETRIES times at the maximum TTL value 🔁 each new attempt MUST increment and update the RREQ ID 🆔 for each attempt, the TTL field of the IP header is set according to the mechanism in section 6.4, so you control how far the RREQ spreads on each retry 📡
data packets waiting for a route (aka waiting for a RREP after a RREQ has been sent) SHOULD be buffered 📦 the buffer SHOULD be "first-in, first-out" (FIFO) 🥇 if a route discovery has been tried RREQ_RETRIES times at the maximum TTL and still no RREP shows up, all data packets for that destination SHOULD be dropped from the buffer, and a Destination Unreachable message SHOULD be delivered to the application 😭
to ease congestion in a network, repeated route discovery attempts from a source node for a single destination MUST use binary exponential backoff 📉 the first time a source node broadcasts a RREQ, it waits NET_TRAVERSAL_TIME milliseconds for a RREP 🕰️ if none comes back, the source sends a new RREQ 🔁 when working out how long to wait for the RREP after the second RREQ, the source node MUST use binary exponential backoff 🧮 so the wait for the RREP to the second RREQ is 2 * NET_TRAVERSAL_TIME milliseconds ⏱️ if no RREP arrives in that window, another RREQ may be sent, up to RREQ_RETRIES additional attempts after the first RREQ 🙌 for each additional attempt, the wait for the RREP gets multiplied by 2, so the timing follows binary exponential backoff all the way 📈 it's giving careful, it's giving patient 🫶
6.4. Controlling Dissemination of Route Request Messages ✨
okay so, nobody wants RREQs blasting across the entire network for no reason 🙅♀️ which is why the originating node SHOULD use an expanding ring search 🧚 Here's the vibe: it starts with TTL = TTL_START in the RREQ packet's IP header and sets its RREP timeout to RING_TRAVERSAL_TIME milliseconds. RING_TRAVERSAL_TIME gets calculated the way section 10 explains 💅 and the TTL_VALUE used for that calculation is just the TTL field in the IP header.
If the RREQ times out with no RREP coming back, the originator broadcasts it again with the TTL bumped up by TTL_INCREMENT 📈 It keeps going like that until the TTL hits TTL_THRESHOLD. After that, every attempt uses TTL = NET_DIAMETER 🌍 And each time, the RREP timeout is RING_TRAVERSAL_TIME. Wanna make every retry cover the whole ad hoc network? Just set both TTL_START and TTL_INCREMENT to the same value as NET_DIAMETER 🦋
Now the hop count bit, which is lowkey so clever 🧠 The Hop Count stored in an invalid routing table entry is the last known hop count to that destination. So when a new route to that same destination is needed later on (like after a route loss), the TTL in the RREQ IP header starts at the Hop Count plus TTL_INCREMENT 🎀 After each timeout the TTL goes up by TTL_INCREMENT until it reaches TTL_THRESHOLD, and past that point it's TTL = NET_DIAMETER. Once you're at TTL = NET_DIAMETER, the RREP timeout switches to NET_TRAVERSAL_TIME, as section 6.3 specifies 💜
Okay, expired entries need to stick around for a while too 🙈 An expired routing table entry SHOULD NOT be expunged before (current_time + DELETE_PERIOD) (see section 6.11). If you delete it sooner, the soft state for that route (like the last known hop count) is gone forever 😭 A longer expunge time MAY be configured, though 🌸 And any routing table entry that's waiting on a RREP SHOULD NOT be expunged before (current_time + 2 * NET_TRAVERSAL_TIME) 🫶
6.5. Processing and Forwarding Route Requests 🔁
so when a node gets a RREQ, first it creates or updates a route to the previous hop, but without a valid sequence number (see section 6.2) 📍 Then it checks whether it already got a RREQ with the same Originator IP Address and RREQ ID within at least the last PATH_DISCOVERY_TIME. If it did, the node silently discards the new one 🤫 The rest of this subsection is about the RREQs that weren't discarded ✨
First, it increments the hop count value in the RREQ by one, to account for the new hop through the intermediate node ➕ Then the node searches for a reverse route to the Originator IP Address (see section 6.2) using longest-prefix matching 🔍 If it needs to, the route gets created or updated using the Originator Sequence Number from the RREQ. This reverse route is needed later, because the node might get a RREP back to whoever originated the RREQ (identified by the Originator IP Address) 💌 Whenever a reverse route is created or updated, these things happen too:
- the Originator Sequence Number from the RREQ is compared to the corresponding destination sequence number in the route table entry and copied if it's greater than the existing value there
- the valid sequence number field is set to true;
- the next hop in the routing table becomes the node the RREQ came from (that's taken from the source IP address in the IP header, and it's often not the same as the Originator IP Address field in the RREQ message) 🛣️
- the hop count is copied from the Hop Count in the RREQ message;
Also, every time a RREQ comes in, the Lifetime of the reverse route entry for the Originator IP address is set to the maximum of (ExistingLifetime, MinimalLifetime), where:
MinimalLifetime = (current time + 2*NET_TRAVERSAL_TIME -
2*HopCount*NODE_TRAVERSAL_TIME).And the current node can use that reverse route to forward data packets, same as any other route in the routing table 🚀
If a node does not generate a RREP (following the rules in section 6.6), and the incoming IP header has a TTL larger than 1, the node updates the RREQ and broadcasts it to address 255.255.255.255 on each of its configured interfaces (see section 6.14) 📡 To update it, the TTL or hop limit field in the outgoing IP header goes down by one, and the Hop Count field in the RREQ message goes up by one, to account for the new hop through the intermediate node. Lastly, the Destination Sequence number for the requested destination is set to the maximum of the value received in the RREQ message and the destination sequence value the node is currently maintaining for that destination 🧮 But here's the important part: the forwarding node MUST NOT modify its own maintained value for the destination sequence number, even if the incoming RREQ has a bigger value than what it's holding 🙅♀️💅
Otherwise, if a node does generate a RREP, then it discards the RREQ 🗑️ Now, real talk, this is a little plot twist 👀 If intermediate nodes reply to every single RREQ for a particular destination, the destination might end up never receiving any of the discovery messages. Then the destination never learns a route back to the originating node from the RREQs 😬 That could make the destination start its own route discovery (for example, if the originator is trying to set up a TCP session). So, so that the destination does learn routes to the originating node, the originating node SHOULD set the "gratuitous RREP" ('G') flag in the RREQ whenever the destination is likely to need a route back, for any reason 🎁 And if an intermediate node sends back a RREP in response to a RREQ with the 'G' flag set, it MUST also unicast a gratuitous RREP to the destination node (see section 6.6.3) 💖
6.6. Generating Route Replies 📬
A node generates a RREP if either of these is true:
(i) it is itself the destination, or
(ii) it has an active route to the destination, the destination sequence number in the node's existing route table entry for the destination is valid and greater than or equal to the Destination Sequence Number of the RREQ (compared using signed 32-bit arithmetic), and the "destination only" ('D') flag is NOT set. 🙌
When a node generates a RREP message, it copies the Destination IP Address and the Originator Sequence Number from the RREQ message into the matching fields in the RREP message 📋 How the rest gets processed depends on whether the node is the requested destination itself (see section 6.6.1), or just an intermediate node with a fresh enough route to the destination (see section 6.6.2) 🧭
Once it's created, the RREP gets unicast to the next hop toward the originator of the RREQ, as the route table entry for that originator says 💌 As the RREP travels back toward the node that originated the RREQ, the Hop Count field goes up by one at each hop 📈 So by the time the RREP reaches the originator, the Hop Count is the distance, in hops, from the originator to the destination 🦋
6.6.1. Route Reply Generation by the Destination 👑
If the generating node is the destination itself, it MUST increment its own sequence number by one if the sequence number in the RREQ packet is equal to that incremented value 🎀 Otherwise, the destination doesn't change its sequence number before making the RREP message. The destination node puts its (maybe newly incremented) sequence number into the Destination Sequence Number field of the RREP, and puts the value zero in the Hop Count field 🧸
The destination node copies MY_ROUTE_TIMEOUT (see section 10) into the Lifetime field of the RREP ⏳ Each node MAY reconfigure its value for MY_ROUTE_TIMEOUT, within mild constraints (see section 10) 🌈
6.6.2. Route Reply Generation by an Intermediate Node 🧚
If the node generating the RREP isn't the destination, but is an intermediate hop on the path from the originator to the destination, it copies its known sequence number for the destination into the Destination Sequence Number field in the RREP message 🔢
The intermediate node updates the forward route entry by putting the last hop node (the one it got the RREQ from, as shown by the source IP address field in the IP header) into the precursor list for the forward route entry, which is the entry for the Destination IP Address 📝 It also updates its route table entry for the node that originated the RREQ by putting the next hop toward the destination into the precursor list for the reverse route entry. That's the entry for the Originator IP Address field of the RREQ message data 💫
The intermediate node puts its distance in hops from the destination (taken from the hop count in the routing table) into the Count field of the RREP. The Lifetime field of the RREP is worked out by subtracting the current time from the expiration time in its route table entry ⌛
6.6.3. Generating Gratuitous RREPs 🎁
After a node gets a RREQ and responds with a RREP, it discards the RREQ 🗑️ If the RREQ has the 'G' flag set, and the intermediate node returns a RREP to the originating node, it MUST also unicast a gratuitous RREP to the destination node. The gratuitous RREP that goes to the desired destination has these values in its RREP message fields 💅
Hop Count The Hop Count as indicated in the
node's route table entry for the
originator
Destination IP Address The IP address of the node that
originated the RREQ
Destination Sequence Number The Originator Sequence Number from
the RREQ
Originator IP Address The IP address of the Destination
node in the RREQ
Lifetime The remaining lifetime of the route
towards the originator of the RREQ,
as known by the intermediate node.Then the gratuitous RREP gets sent to the next hop along the path to the destination node 🚀 It's sent exactly as if the destination had already issued a RREQ for the originating node, and this RREP was made in response to that (fictitious) RREQ 👻 And the RREP that goes to the originator of the RREQ is the same whether or not the 'G' bit is set 🫶
6.7. Receiving and Forwarding Route Replies 💌
okay so when a node gets a RREP, the first thing it does is search (using longest-prefix matching 🔍) for a route to the previous hop. If it needs to, it makes a route for that previous hop, but without a valid sequence number (see section 6.2). Then it bumps the hop count in the RREP up by one, to count the new hop through the intermediate node. This bumped number is the "New Hop Count" ✨. Next, the forward route for this destination gets created if it doesn't exist yet. If it does exist, the node compares the Destination Sequence Number in the message with its own stored destination sequence number for the Destination IP Address in the RREP. The existing entry only gets updated in these situations:
- (i) the sequence number in the routing table is marked as invalid in the route table entry.
- (ii) the Destination Sequence Number in the RREP is greater than the node's copy of the destination sequence number and the known value is valid, or
- (iii) the sequence numbers are the same, but the route is marked as inactive, or
- (iv) the sequence numbers are the same, and the New Hop Count is smaller than the hop count in the route table entry.
If the route table entry to the destination gets created or updated, then these things happen 🎀:
- the route is marked as active,
- the destination sequence number is marked as valid,
- the next hop in the route entry is set to the node the RREP came from, which is shown by the source IP address field in the IP header,
- the hop count is set to the New Hop Count,
- the expiry time is set to the current time plus the Lifetime in the RREP message,
- and the destination sequence number is the Destination Sequence Number in the RREP message.
The current node can use this route to forward data packets to the destination from then on 🦋.
If the current node is not the node named by the Originator IP Address in the RREP message AND a forward route got created or updated as described above, the node checks its route table entry for the originating node to figure out the next hop for the RREP packet. Then it forwards the RREP toward the originator using that entry. If a node forwards a RREP over a link that's likely to have errors or be unidirectional, the node SHOULD set the 'A' flag. That makes the recipient send back a RREP-ACK message to confirm it got the RREP (see section 6.8). Main character energy, no notes 💅.
Whenever any node transmits a RREP, it adds the next hop node the RREP is forwarded to into the precursor list for the corresponding destination node 🌸. Also, at each node, the (reverse) route used to forward a RREP gets its lifetime changed to the maximum of (existing-lifetime, (current time + ACTIVE_ROUTE_TIMEOUT)). Finally, the precursor list for the next hop toward the destination gets updated to include the next hop toward the source.
6.8. Operation over Unidirectional Links 🚦
okay this one is lowkey tricky 😭. A RREP transmission can fail, especially if the RREQ that triggered it came over a unidirectional link. If no other RREP from the same route discovery attempt reaches the node that originated the RREQ, the originator will try route discovery again after a timeout (see section 6.3). But the same thing can totally happen again with no improvement, so no route ever gets found, even after a bunch of retries. Unless something corrective happens, this can occur even when bidirectional routes between the originator and destination do exist 💀. Link layers that use broadcast transmissions for the RREQ can't detect these unidirectional links at all.
In AODV, any node acts on only the first RREQ with the same RREQ ID and ignores any RREQs after that 🙈. Say the first RREQ arrives along a path with one or more unidirectional link(s). A later RREQ might arrive over a bidirectional path (if those paths exist), but it gets ignored anyway. Rude 💔.
To stop this problem, when a node detects that its transmission of a RREP has failed, it remembers the next hop of the failed RREP in a "blacklist" set 🚫. These failures can be detected through the absence of a link-layer or network-layer acknowledgment (e.g., RREP-ACK). A node ignores all RREQs received from any node in its blacklist set. Nodes get removed from the blacklist set after a BLACKLIST_TIMEOUT period (see section 10). This period should be set to the upper bound of the time it takes to do the allowed number of route request retry attempts described in section 6.3.
Note that the RREP-ACK packet doesn't contain any info about which RREP it's acknowledging 🧐. The RREP-ACK will likely arrive right after the RREP was sent with the 'A' bit. That's expected to be enough to reassure the sender of the RREP that the link is bidirectional right now, without really depending on the specific RREP being acknowledged. Still, that reassurance typically can't be counted on forever 🫶.
6.9. Hello Messages 👋
A node MAY offer connectivity info by broadcasting local Hello messages ✨. A node SHOULD only use Hello messages if it's part of an active route. Every HELLO_INTERVAL milliseconds, the node checks whether it has sent a broadcast (e.g., a RREQ or an appropriate layer 2 message) within the last HELLO_INTERVAL. If it hasn't, it MAY broadcast a RREP with TTL = 1, called a Hello message, with the RREP message fields set as follows:
Destination IP Address The node's IP address.
Destination Sequence Number The node's latest sequence number.
Hop Count 0
Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVALA node MAY figure out connectivity by listening for packets from its neighbors 👂. If, within the past DELETE_PERIOD, it has received a Hello message from a neighbor, and then that neighbor doesn't send any packets (Hello messages or otherwise) for more than ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD assume the link to this neighbor is currently lost. When that happens, the node SHOULD proceed as in Section 6.11 🚨.
Whenever a node gets a Hello message from a neighbor, the node SHOULD make sure it has an active route to that neighbor, and create one if necessary 💜. If a route already exists, the Lifetime for the route should be increased, if necessary, to be at least ALLOWED_HELLO_LOSS * HELLO_INTERVAL. The route to the neighbor, if it exists, MUST subsequently contain the latest Destination Sequence Number from the Hello message. The current node can start using this route to forward data packets right away 🏃♀️. Routes made by Hello messages that aren't used by any other active routes will have empty precursor lists. So if the neighbor moves away and a neighbor timeout happens, they won't trigger a RERR message 🌈.
6.10. Maintaining Local Connectivity 📡
Each forwarding node SHOULD keep track of its continued connectivity to its active next hops 🧚 (meaning the next hops or precursors that have forwarded packets to or from the forwarding node during the last ACTIVE_ROUTE_TIMEOUT). It should also track neighbors that have sent Hello messages during the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL). A node can keep accurate info about its continued connectivity to these active next hops using one or more of the available link or network layer mechanisms, as described below.
- Any suitable link layer notification, such as those provided by IEEE 802.11, can be used to determine connectivity, each time a packet is transmitted to an active next hop. For example, if there's no link layer ACK, or no CTS after sending an RTS, even after the maximum number of retransmission attempts, that means the link to this active next hop is lost 💔.
- If layer-2 notification isn't available, passive acknowledgment SHOULD be used when the next hop is expected to forward the packet. That means listening to the channel for a transmission attempt made by the next hop 👀. If no transmission is detected within NEXT_HOP_WAIT milliseconds, or the next hop is the destination (and so isn't supposed to forward the packet), one of the following methods SHOULD be used to determine connectivity:
- Receiving any packet (including a Hello message) from the next hop.
- A RREQ unicast to the next hop, asking for a route to the next hop.
- An ICMP Echo Request message unicast to the next hop.
If a link to the next hop can't be detected by any of these methods, the forwarding node SHOULD assume the link is lost and take corrective action by following the methods in Section 6.11 🫧.
6.11. Route Error (RERR) Messages, Route Expiry and Route Deletion ❌🧚
okay so route error and link breakage processing basically needs these steps, no cap 💅
- Invalidating existing routes
- Listing affected destinations
- Determining which, if any, neighbors may be affected
- Delivering an appropriate RERR to such neighbors
A Route Error (RERR) message MAY be either broadcast (if there are many precursors), unicast (if there is only 1 precursor), or iteratively unicast to all precursors (if broadcast is inappropriate). 🦋 Even when the RERR message is iteratively unicast to several precursors, it still counts as a single control message for the rest of this explanation. With that in mind, a node SHOULD NOT generate more than RERR_RATELIMIT RERR messages per second. bestie, don't spam the errors 🙈
A node starts processing for a RERR message in three situations:
- (i) if it detects a link break for the next hop of an active route in its routing table while transmitting data (and route repair, if attempted, was unsuccessful), or
- (ii) if it gets a data packet destined to a node for which it does not have an active route and is not repairing (if using local repair), or
- (iii) if it receives a RERR from a neighbor for one or more active routes.
For case (i), the node first makes a list of unreachable destinations. This list has the unreachable neighbor plus any additional destinations (or subnets, see section 7) in the local routing table that use the unreachable neighbor as the next hop. 🌸 If a subnet route turns out to be newly unreachable, its IP destination address gets built by appending zeroes to the subnet prefix shown in the route table entry. This is unambiguous, since the precursor is known to have route table information with a compatible prefix length for that subnet. Iconic logic 👑
For case (ii), there is only one unreachable destination, which is the destination of the data packet that can't be delivered. For case (iii), the list should consist of those destinations in the RERR for which there exists a corresponding entry in the local routing table that has the transmitter of the received RERR as the next hop.
Some of the unreachable destinations in the list could still be used by neighboring nodes, so it may be necessary to send a (new) RERR. ✨ The RERR should contain those destinations that are part of the created list of unreachable destinations and have a non-empty precursor list.
The neighboring node(s) that should receive the RERR are all those that belong to a precursor list of at least one of the unreachable destination(s) in the newly created RERR. If there is only one unique neighbor that needs the RERR, the RERR SHOULD be unicast toward that neighbor. Otherwise the RERR is typically sent to the local broadcast address (Destination IP == 255.255.255.255, TTL == 1), with the unreachable destinations and their corresponding destination sequence numbers included in the packet. The DestCount field of the RERR packet indicates how many unreachable destinations are in the packet. 🎀
Just before transmitting the RERR, some updates get made to the routing table that may affect the destination sequence numbers for the unreachable destinations. For each one of these destinations, the corresponding routing table entry is updated as follows:
- The destination sequence number of this routing entry, if it exists and is valid, is incremented for cases (i) and (ii) above, and copied from the incoming RERR in case (iii) above.
- The entry is invalidated by marking the route entry as invalid.
- The Lifetime field is updated to current time plus
DELETE_PERIOD. Before this time, the entry SHOULD NOT be deleted. 🫶
Lowkey the Lifetime field is doing double duty here 😭 Note that the Lifetime field in the routing table plays a dual role: for an active route it is the expiry time, and for an invalid route it is the deletion time. If a data packet is received for an invalid route, the Lifetime field is updated to current time plus DELETE_PERIOD. The determination of DELETE_PERIOD is discussed in Section 10.
6.12. Local Repair 🔧💖
When a link break in an active route happens, the node upstream of that break MAY choose to repair the link locally, but only if the destination was no farther than MAX_REPAIR_TTL hops away. To repair the link break, the node increments the sequence number for the destination and then broadcasts a RREQ for that destination. The TTL of the RREQ should initially be set to the following value:
max(MIN_REPAIR_TTL, 0.5 * #hops) + LOCAL_ADD_TTL,where #hops is the number of hops to the sender (originator) of the currently undeliverable packet. So local repair attempts will often be invisible to the originating node, and they will always have TTL >= MIN_REPAIR_TTL + LOCAL_ADD_TTL. 🦋 The node starting the repair then waits the discovery period to receive RREPs in response to the RREQ. During local repair, data packets SHOULD be buffered. If, at the end of the discovery period, the repairing node has not received a RREP (or other control message creating or updating the route) for that destination, it goes ahead as described in Section 6.11 by transmitting a RERR message for that destination.
On the other hand, if the node receives one or more RREPs (or other control messages creating or updating the route to the desired destination) during the discovery period, it first compares the hop count of the new route with the value in the hop count field of the invalid route table entry for that destination. If the hop count of the newly determined route is greater than the hop count of the previously known route, the node SHOULD issue a RERR message for the destination, with the 'N' bit set. Then it continues as described in Section 6.7, updating its route table entry for that destination. 💅
A node that receives a RERR message with the 'N' flag set MUST NOT delete the route to that destination. The only action taken should be retransmitting the message, and only if the RERR arrived from the next hop along that route and there are one or more precursor nodes for that route to the destination. When the originating node receives a RERR message with the 'N' flag set, if the message came from its next hop along its route to the destination, then the originating node MAY choose to reinitiate route discovery, as described in Section 6.3. ✨
Local repair of link breaks in routes sometimes results in longer paths to those destinations. 🌈 Repairing the link locally is likely to increase the number of data packets that can be delivered to the destinations, since data packets won't be dropped while the RERR travels to the originating node. Sending a RERR to the originating node after repairing the link locally may let the originator find a fresh route to the destination that's better, based on current node positions. However, it doesn't require the originating node to rebuild the route, since the originator may be done, or nearly done, with the data session. 🙈
When a link breaks along an active route, there are often multiple destinations that become unreachable. The node upstream of the lost link tries an immediate local repair for only the one destination the data packet was traveling toward. Other routes using the same link MUST be marked as invalid, but the node handling the local repair MAY flag each such newly lost route as locally repairable. This local repair flag in the route table MUST be reset when the route times out (e.g., after the route has been not been active for ACTIVE_ROUTE_TIMEOUT). 🍓 Before the timeout occurs, these other routes will be repaired as needed when packets arrive for the other destinations. So these routes are repaired as needed; if a data packet never arrives for the route, then that route won't be repaired. Alternatively, depending on local congestion, the node MAY begin the process of establishing local repairs for the other routes, without waiting for new packets to arrive. By proactively repairing the routes that broke because the link was lost, incoming data packets for those routes won't be subject to the delay of repairing the route and can be forwarded right away. However, repairing the route before a data packet arrives for it runs the risk of repairing routes that are no longer in use. Therefore, depending on the local traffic in the network and whether congestion is being experienced, the node MAY elect to proactively repair the routes before a data packet is received; otherwise, it can wait until a data packet is received and then start the repair of the route. 🧚
6.13. Actions After Reboot 🔄
A node participating in the ad hoc network must take certain actions after reboot, because it might lose all sequence number records for all destinations, including its own sequence number. Meanwhile, there may be neighboring nodes that are still using this node as an active next hop. This can potentially create routing loops. 😱 To prevent that possibility, each node waits for DELETE_PERIOD after reboot before transmitting any route discovery messages. If the node receives a RREQ, RREP, or RERR control packet, it SHOULD create route entries as appropriate given the sequence number information in the control packets, but MUST not forward any control packets. If the node receives a data packet for some other destination, it SHOULD broadcast a RERR as described in subsection 6.11 and MUST reset the waiting timer to expire at current time plus DELETE_PERIOD. 💜
It can be shown [4] that by the time the rebooted node comes out of the waiting phase and becomes an active router again, none of its neighbors will be using it as an active next hop any more. Its own sequence number gets updated once it receives a RREQ from any other node, since the RREQ always carries the maximum destination sequence number seen en route. If no such RREQ arrives, the node MUST initialize its own sequence number to zero. 🌟
6.14. Interfaces 🔌🦋
Because AODV should operate smoothly over wired as well as wireless networks, and because it is likely that AODV will also be used with multiple wireless devices, the particular interface over which packets arrive must be known to AODV whenever a packet is received. This includes the reception of RREQ, RREP, and RERR messages. Whenever a packet is received from a new neighbor, the interface it arrived on is recorded into the route table entry for that neighbor, along with all the other appropriate routing information. Similarly, whenever a route to a new destination is learned, the interface through which the destination can be reached is also recorded into the destination's route table entry. 🎀
When multiple interfaces are available, a node retransmitting a RREQ message rebroadcasts that message on all interfaces that have been configured for operation in the ad hoc network, except those on which it is known that all of the node's neighbors have already received the RREQ. For instance, for some broadcast media (e.g., Ethernet), it may be presumed that all nodes on the same link receive a broadcast message at the same time. When a node needs to transmit a RERR, it SHOULD only transmit it on those interfaces that have neighboring precursor nodes for that route. 👑
7. AODV and Aggregated Networks ✨
okay so AODV was built for mobile nodes whose IP addresses don't have to be related to each other, bestie, because the whole point is making an ad hoc network 🦋. BUT ngl, sometimes a bunch of mobile nodes are literally glued together, sharing one subnet prefix and moving as a squad inside an area where an ad hoc network has formed. A collection like that can be called a "subnet" 🫶. In this situation, one single node in the subnet can advertise reachability for every other node on the subnet, by answering any RREQ asking for a route to a node with the subnet routing prefix with an RREP message. That one node is the "subnet router" 👑. For a subnet router to run AODV for the whole subnet, it has to keep a destination sequence number for the entire subnet 💅. In any RREP the subnet router sends like this, the Prefix Size field MUST be set to the length of the subnet prefix. Everyone else sharing that prefix SHOULD NOT issue RREP messages, and they SHOULD forward RREQ messages to the subnet router instead 🙈.
Processing RREPs that give routes to subnets (aka the ones with a nonzero prefix length) is the exact same as processing host-specific RREPs, so no new drama there 💖. Every node that gets an RREP with prefix size information SHOULD create or update its route table entry for the subnet, including the sequence number from the subnet router and the right precursor info 🧚. Then later on, that node can use what it learned to skip sending RREQs for other nodes on the same subnet. Efficiency is giving ✨.
Now here's the tea 🍓. When a node uses a subnet route, a packet might get routed to an IP address on that subnet that isn't assigned to any existing node in the ad hoc network. When that happens, the subnet router MUST return an ICMP Host Unreachable message to the sending node. Upstream nodes that receive that ICMP message SHOULD record that this particular IP address is unreachable, but they MUST NOT invalidate the route entry for the matching subnet prefix. The subnet route stays alive, periodt 💅.
If several nodes in the subnet advertise reachability to the subnet defined by the subnet prefix, the node with the lowest IP address gets elected as the subnet router, and every other node MUST stop advertising reachability. Lowest IP wins, no cap 👑.
Last thing: the behavior of default routes (routes with routing prefix length 0) is NOT defined in this specification, so we're not touching that 🙈. When routes share prefix bits, selection should be according to longest match first 🌸.
8. Using AODV with Other Networks 🌈
In some setups, an ad hoc network can provide connectivity between external routing domains that don't use AODV at all, which is lowkey iconic 🦋. If the points of contact to those other networks can act as subnet routers (see Section 7) for any relevant networks inside the external routing domains, then the ad hoc network can keep the connection to those external routing domains going 💖. Honestly, the external routing networks can even use the AODV ad hoc network as a transit network. It's giving main character energy 👑.
To make this work, a point of contact to an external network (we'll call it an Infrastructure Router) has to act as the subnet router for every subnet of interest inside the external network that the Infrastructure Router can provide reachability to 🧚. That includes needing to maintain a destination sequence number for that external subnet too 💅.
And if multiple Infrastructure Routers offer reachability to the same external subnet, those Infrastructure Routers have to cooperate 🫶. The way they do that is by means outside the scope of this specification, so it's not our problem here 🙈, but the goal is consistent AODV semantics for ad hoc access to those subnets ✨.
9. Extensions 🎀
okay so in this section we get to define the format of extensions to the RREQ and RREP messages 🔥. All of these extensions go after the message data, and they all look like this:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | type-specific data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+where:
- Type is 1-255 💖
- Length is the length of the type-specific data, NOT counting the Type and Length fields of the extension, measured in bytes 🧚
Extensions with types between 128 and 255 may NOT be skipped. Like, you literally cannot ignore them 🙈. The rules for extensions are going to be spelled out more fully later, and they'll match the rules for handling IPv6 options 💅.
9.1. Hello Interval Extension Format 🦋
Here's the layout for this one:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Hello Interval ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Hello Interval, continued |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type is 1 🌸
- Length is 4 🌸
- Hello Interval is the number of milliseconds between successive transmissions of a Hello message ⏱️
The Hello Interval extension MAY be appended to an RREP message with TTL == 1 🫶. A neighboring receiver can use it to figure out how long to wait for the next RREP messages (aka Hello messages, see section 6.9) ✨.
10. Configuration Parameters 💅
This section gives default values for some important parameters tied to AODV protocol operations, so you've got a starting point 🍓. A particular mobile node might want to change some of them, especially NET_DIAMETER, MY_ROUTE_TIMEOUT, ALLOWED_HELLO_LOSS, RREQ_RETRIES, and maybe HELLO_INTERVAL 🧚. If it changes HELLO_INTERVAL, the node should advertise that value in its Hello messages by tacking a Hello Interval Extension onto the RREP message 🫶. Picking these parameters can change how the protocol performs, so be thoughtful, bestie 🙈. Changing NODE_TRAVERSAL_TIME also changes the node's estimate of NET_TRAVERSAL_TIME, so that's only okay if you really know how the other nodes in the ad hoc network behave 💀. And the configured value for MY_ROUTE_TIMEOUT MUST be at least 2 * PATH_DISCOVERY_TIME 👑.
Here are the defaults:
Parameter Name Value
---------------------- -----
ACTIVE_ROUTE_TIMEOUT 3,000 Milliseconds
ALLOWED_HELLO_LOSS 2
BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME
DELETE_PERIOD see note below
HELLO_INTERVAL 1,000 Milliseconds
LOCAL_ADD_TTL 2
MAX_REPAIR_TTL 0.3 * NET_DIAMETER
MIN_REPAIR_TTL see note below
MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT
NET_DIAMETER 35
NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER
NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10
NODE_TRAVERSAL_TIME 40 milliseconds
PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME
RERR_RATELIMIT 10
RING_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME *
(TTL_VALUE + TIMEOUT_BUFFER)
RREQ_RETRIES 2
RREQ_RATELIMIT 10
TIMEOUT_BUFFER 2
TTL_START 1
TTL_INCREMENT 2
TTL_THRESHOLD 7
TTL_VALUE see note belowThe MIN_REPAIR_TTL should be the last known hop count to the destination 🌸. If Hello messages are used, then the ACTIVE_ROUTE_TIMEOUT parameter value MUST be more than the value (ALLOWED_HELLO_LOSS * HELLO_INTERVAL) 🙈. For a given ACTIVE_ROUTE_TIMEOUT value, this might mean adjusting HELLO_INTERVAL, and then using the Hello Interval Extension in the Hello messages to match ✨.
TTL_VALUE is the value of the TTL field in the IP header while an expanding ring search is happening, and we go deeper on that in section 6.4 🦋. TIMEOUT_BUFFER is configurable, and its purpose is to give the timeout some breathing room 🫶. So if the RREP gets delayed by congestion, a timeout is less likely to fire while the RREP is still on its way back to the source 💖. If you want to skip that buffer, set TIMEOUT_BUFFER = 0 🙈.
DELETE_PERIOD is meant to be an upper bound on how long an upstream node A can keep a neighbor B as its active next hop for destination D, even though B has already invalidated the route to D 💅. After that time, B is allowed to delete the already invalidated route to D 🧚. How big that upper bound is depends a bit on the underlying link layer 🌈. If Hello messages are used to figure out whether links to next hop nodes are still available, then DELETE_PERIOD MUST be at least ALLOWED_HELLO_LOSS * HELLO_INTERVAL 🫶. If link layer feedback is used to detect link loss, DELETE_PERIOD must be at least ACTIVE_ROUTE_TIMEOUT 💅. Now the tricky one 🙈: sometimes hello messages come in from a neighbor but data packets to that neighbor get lost (like from temporary link asymmetry). To cover that, we have to make some more concrete assumptions about the link layer. We assume that asymmetry can't last forever, like beyond a multiple K of HELLO_INTERVAL. Basically, if the link is working and the neighbor isn't sending any other traffic, a node will invariably get at least one out of K subsequent Hello messages from that neighbor. Covering all the possibilities, we get:
DELETE_PERIOD = K * max (ACTIVE_ROUTE_TIMEOUT, HELLO_INTERVAL)
(K = 5 is recommended).NET_DIAMETER measures the maximum possible number of hops between two nodes in the network 🌸. NODE_TRAVERSAL_TIME is a conservative estimate of the average one hop traversal time for packets, and it should include queuing delays, interrupt processing times and transfer times ⏱️. ACTIVE_ROUTE_TIMEOUT SHOULD be set to a longer value (at least 10,000 milliseconds) if link-layer indications are used to detect link breakages, like in the IEEE 802.11 [5] standard 🔥. TTL_START should be set to at least 2 if Hello messages are used for local connectivity information 🧚. Performance of AODV is really sensitive to the values of these constants, and those values often depend on the link layer protocol characteristics, radio technologies and so on 🙈. BLACKLIST_TIMEOUT should be suitably increased if an expanding ring search is used 🦋. In that case, it should be:
{[(TTL_THRESHOLD - TTL_START)/TTL_INCREMENT] + 1 + RREQ_RETRIES} *
NET_TRAVERSAL_TIMEThis accounts for possible extra route discovery attempts, so your blacklist doesn't ghost a node too early 💖.
11. Security Considerations 🔐
Okay bestie, real talk: AODV doesn't specify any special security measures right now 🙈. Routing protocols are literally prime targets for impersonation attacks 💀. When you don't even know who's in the network, spotting an impersonation attack is hard, and preventing one is hard at best. But when the network membership IS known and there's a real danger of these attacks, AODV control messages must be protected with authentication techniques, like unforgeable, cryptographically strong message digests or digital signatures 🔥. AODV doesn't restrict which authentication mechanism you use, but IPsec AH is a solid choice when the nodes share a security association that lets them use AH ✨.
In particular, RREP messages SHOULD be authenticated to avoid creation of spurious routes to a desired destination 😤. Otherwise, an attacker could masquerade as the desired destination and maliciously deny service to it, and/or maliciously inspect and consume traffic meant for it 💀. RERR messages are less dangerous, but they SHOULD be authenticated too, so malicious nodes can't disrupt valid routes between nodes that are communication partners 🙅♀️.
AODV doesn't make any assumption about how addresses get assigned to the mobile nodes, except that they're presumed to have unique IP addresses 🧚. So nothing special needs to be considered about IPsec authentication headers or key exchange mechanisms, beyond what's natural from the general protocol specs 🎀. However, if the mobile nodes in the ad hoc network already have pre-established security associations, it's presumed that those were created partly to authorize processing of AODV control messages 🫶. Given that, the mobile nodes should be able to use the same authentication mechanisms based on their IP addresses that they'd have used otherwise 💅.
12. IANA Considerations 🦋
AODV defines a "Type" field for messages sent to port 654. A new registry has been created for the values of this Type field, and these values have been assigned 📋:
Message Type Value
--------------------------- -----
Route Request (RREQ) 1
Route Reply (RREP) 2
Route Error (RERR) 3
Route-Reply Ack (RREP-ACK) 4AODV control messages can have extensions 🌸. Right now only one extension is defined. A new registry has been created for the Type field of extensions:
Extension Type Value
--------------------------- -----
Hello Interval 1Future values of the Message Type or Extension Type can be allocated using standards action [2] 💖.
13. IPv6 Considerations 🌈
See [6] for detailed operation for IPv6 ✨. The only changes to the protocol are that the address fields are enlarged 💜.
14. Acknowledgments 🫶
Special thanks to Ian Chakeres, UCSB, for his extensive suggestions and contributions to recent revisions 🙌.
We acknowledge with gratitude the work done at University of Pennsylvania within Carl Gunter's group, as well as at Stanford and CMU, to figure out some conditions (especially involving reboots and lost RERRs) under which previous versions of AODV could suffer from routing loops 🔁. Contributors to those efforts include Karthikeyan Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and Davor Obradovic. The idea of a DELETE_PERIOD, where expired routes (and in particular their sequence numbers) to a particular destination must be maintained, was also suggested by them 👑.
We also acknowledge the comments and improvements suggested by Sung-Ju Lee (especially regarding local repair), Mahesh Marina, Erik Nordstrom (who provided text for section 6.11), Yves Prelot, Marc Mosko, Manel Guerrero Zapata, Philippe Jacquet, and Fred Baker 🎉.
15. Normative References 📚
- [1] Bradner, S. "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [2] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
16. Informative References 🧠
- [3] Manner, J., et al., "Mobility Related Terminology", Work in Progress, July 2001.
- [4] Karthikeyan Bhargavan, Carl A. Gunter, and Davor Obradovic. Fault Origin Adjudication. In Proceedings of the Workshop on Formal Methods in Software Practice, Portland, OR, August 2000.
- [5] IEEE 802.11 Committee, AlphaGraphics #35, 10201 N.35th Avenue, Phoenix AZ 85051. Wireless LAN Medium Access Control MAC and Physical Layer PHY Specifications, June 1997. IEEE Standard 802.11-97.
- [6] Perkins, C., Royer, E. and S. Das, "Ad hoc on demand distance vector (AODV) routing for ip version 6", Work in Progress.
17. Authors' Addresses 💌
Charles E. Perkins Communications Systems Laboratory Nokia Research Center 313 Fairchild Drive Mountain View, CA 94303 USA
Phone: +1 650 625 2986 Fax: +1 650 691 2170 (fax) EMail: Charles.Perkins@nokia.com
Elizabeth M. Belding-Royer Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 93106
Phone: +1 805 893 3411 Fax: +1 805 893 8553 EMail: ebelding@cs.ucsb.edu
Samir R. Das Department of Electrical and Computer Engineering & Computer Science University of Cincinnati Cincinnati, OH 45221-0030
Phone: +1 513 556 2594 Fax: +1 513 556 7326 EMail: sdas@ececs.uc.edu
18. Full Copyright Statement ⚖️
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.Acknowledgement 💜
Funding for the RFC Editor function is currently provided by the Internet Society 🎀.
📦 where this page comes from
- ietf: rfc3561 2003-07
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms