RFC 4728
The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4
Title Block 🎀
okay bestie, this is RFC 4728 and it's called The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4 ✨
- Written by: D. Johnson (Rice University), Y. Hu (UIUC), and D. Maltz (Microsoft Research) 👑
- Stream: Network Working Group 🌸
- Category: Experimental 🧪
- Date: February 2007 📅
- Obsoletes / Updates: the title block doesn't list anything, so this RFC isn't replacing or patching any older RFC 💅
Status of This Memo 📣
this memo defines an Experimental Protocol for the Internet community 🧪. it does not specify an Internet standard of any kind, so don't treat it like one 🙈
they're literally asking for discussion and suggestions for improvement 🫶 and distribution of this memo is unlimited 🌈.
Copyright Notice ©
Copyright (C) The IETF Trust (2007). 💜
Abstract 💜
okay so the Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol made specifically for multi-hop wireless ad hoc networks full of mobile nodes 📱✨. it lets the network be completely self-organizing and self-configuring, so you don't need any existing network infrastructure or administration. no router babysitter needed 💅
the protocol is built from two main mechanisms, "Route Discovery" and "Route Maintenance", which work together so nodes can find and keep routes to arbitrary destinations in the ad hoc network 🦋. everything happens entirely on demand, so the routing packet overhead of DSR scales automatically to only what's needed to react to changes in the routes that are actually in use. iconic efficiency 👑
DSR allows multiple routes to any destination, and each sender can select and control the routes used to route its packets. this is useful for things like load balancing or extra robustness 🔥. other perks include easily guaranteed loop-free routing, operation in networks with unidirectional links, use of only "soft state" in routing, and very rapid recovery when routes in the network change 🌈.
DSR is designed mainly for mobile ad hoc networks of up to about two hundred nodes, and it's built to work well even with very high rates of mobility 🏃♀️💨. this document specifies how DSR routes unicast IPv4 packets. main character energy 🎀
Table of Contents 📑
1. Introduction ....................................................5
2. Assumptions .....................................................7
3. DSR Protocol Overview ...........................................9
3.1. Basic DSR Route Discovery .................................10
3.2. Basic DSR Route Maintenance ...............................12
3.3. Additional Route Discovery Features .......................14
3.3.1. Caching Overheard Routing Information ..............14
3.3.2. Replying to Route Requests Using Cached Routes .....15
3.3.3. Route Request Hop Limits ...........................16
3.4. Additional Route Maintenance Features .....................17
3.4.1. Packet Salvaging ...................................17
3.4.2. Queued Packets Destined over a Broken Link .........18
3.4.3. Automatic Route Shortening .........................19
3.4.4. Increased Spreading of Route Error Messages ........20
3.5. Optional DSR Flow State Extension .........................20
3.5.1. Flow Establishment .................................21
3.5.2. Receiving and Forwarding Establishment Packets .....22
3.5.3. Sending Packets along Established Flows ............22
3.5.4. Receiving and Forwarding Packets Sent along
Established Flows ..................................23
3.5.5. Processing Route Errors ............................24
3.5.6. Interaction with Automatic Route Shortening ........24
3.5.7. Loop Detection .....................................25
3.5.8. Acknowledgement Destination ........................25
3.5.9. Crash Recovery .....................................25
3.5.10. Rate Limiting .....................................25
3.5.11. Interaction with Packet Salvaging .................26
4. Conceptual Data Structures .....................................26
4.1. Route Cache ...............................................26
4.2. Send Buffer ...............................................30
4.3. Route Request Table .......................................30
4.4. Gratuitous Route Reply Table ..............................31
4.5. Network Interface Queue and Maintenance Buffer ............32
4.6. Blacklist .................................................33
5. Additional Conceptual Data Structures for Flow State
Extension ......................................................34
5.1. Flow Table ................................................34
5.2. Automatic Route Shortening Table ..........................35
5.3. Default Flow ID Table .....................................36
6. DSR Options Header Format ......................................36
6.1. Fixed Portion of DSR Options Header .......................37
6.2. Route Request Option ......................................40
6.3. Route Reply Option ........................................42
6.4. Route Error Option ........................................44
6.4.1. Node Unreachable Type-Specific Information .........46
6.4.2. Flow State Not Supported Type-Specific
Information ........................................46
6.4.3. Option Not Supported Type-Specific Information .....46
6.5. Acknowledgement Request Option ............................46
6.6. Acknowledgement Option ....................................47
6.7. DSR Source Route Option ...................................48
6.8. Pad1 Option ...............................................50
6.9. PadN Option ...............................................50
7. Additional Header Formats and Options for Flow State
Extension ......................................................51
7.1. DSR Flow State Header .....................................52
7.2. New Options and Extensions in DSR Options Header ..........52
7.2.1. Timeout Option .....................................52
7.2.2. Destination and Flow ID Option .....................53
7.3. New Error Types for Route Error Option ....................54
7.3.1. Unknown Flow Type-Specific Information .............54
7.3.2. Default Flow Unknown Type-Specific Information .....55
7.4. New Acknowledgement Request Option Extension ..............55
7.4.1. Previous Hop Address Extension .....................55
8. Detailed Operation .............................................56
8.1. General Packet Processing .................................56
8.1.1. Originating a Packet ...............................56
8.1.2. Adding a DSR Options Header to a Packet ............57
8.1.3. Adding a DSR Source Route Option to a Packet .......57
8.1.4. Processing a Received Packet .......................58
8.1.5. Processing a Received DSR Source Route Option ......60
8.1.6. Handling an Unknown DSR Option .....................63
8.2. Route Discovery Processing ................................64
8.2.1. Originating a Route Request ........................65
8.2.2. Processing a Received Route Request Option .........66
8.2.3. Generating a Route Reply Using the Route Cache .....68
8.2.4. Originating a Route Reply ..........................71
8.2.5. Preventing Route Reply Storms ......................72
8.2.6. Processing a Received Route Reply Option ...........74
8.3. Route Maintenance Processing ..............................74
8.3.1. Using Link-Layer Acknowledgements ..................75
8.3.2. Using Passive Acknowledgements .....................76
8.3.3. Using Network-Layer Acknowledgements ...............77
8.3.4. Originating a Route Error ..........................80
8.3.5. Processing a Received Route Error Option ...........81
8.3.6. Salvaging a Packet .................................82
8.4. Multiple Network Interface Support ........................84
8.5. IP Fragmentation and Reassembly ...........................84
8.6. Flow State Processing .....................................85
8.6.1. Originating a Packet ...............................85
8.6.2. Inserting a DSR Flow State Header ..................88
8.6.3. Receiving a Packet .................................88
8.6.4. Forwarding a Packet Using Flow IDs .................93
8.6.5. Promiscuously Receiving a Packet ...................93
8.6.6. Operation Where the Layer below DSR
Decreases the IP TTL ...............................94
8.6.7. Salvage Interactions with DSR ......................94
9. Protocol Constants and Configuration Variables .................95
10. IANA Considerations ...........................................96
11. Security Considerations .......................................96
Appendix A. Link-MaxLife Cache Description ........................97
Appendix B. Location of DSR in the ISO Network Reference Model ....99
Appendix C. Implementation and Evaluation Status .................100
Acknowledgements .................................................101
Normative References .............................................102
Informative References ...........................................1021. Introduction ✨
Okay so, the Dynamic Source Routing protocol (DSR) [JOHNSON94, JOHNSON96a] is a simple and efficient routing protocol built specifically for multi-hop wireless ad hoc networks of mobile nodes. 🦋 With DSR, the network is completely self-organizing and self-configuring, so it needs no existing network infrastructure or administration. Nodes cooperate to forward packets for each other, which lets them communicate over multiple "hops" with nodes that aren't directly within wireless transmission range of one another. 📡 As nodes move around, join, or leave the network, and as wireless conditions like sources of interference shift, DSR automatically figures out and maintains all the routing. The number or sequence of intermediate hops needed to reach any destination can change at any time, so the network topology can get pretty rich and rapidly changing. 🌈
In designing DSR, the goal was to make a routing protocol with very low overhead that could still react super quickly to changes in the network. 💖 DSR provides highly reactive service so that data packets still get delivered successfully even when nodes move or other network conditions change. ✨
The DSR protocol is made of two main mechanisms that work together to discover and maintain source routes in the ad hoc network. 🎀
- Route Discovery is the mechanism by which a node S that wants to send a packet to a destination node D gets a source route to D. Route Discovery is only used when S tries to send a packet to D and doesn't already know a route to D. 🔍
- Route Maintenance is the mechanism by which node S can tell, while using a source route to D, whether the network topology has changed so much that it can no longer use its route to D, because a link along the route stopped working. 🛠️ When Route Maintenance says a source route is broken, S can try any other route it happens to know to D, or it can invoke Route Discovery again to find a new route for subsequent packets to D. Route Maintenance for a route is only used when S is actually sending packets to D. 💅
In DSR, Route Discovery and Route Maintenance each operate entirely "on demand". 🙈 Unlike other protocols, DSR requires no periodic packets of any kind at any layer within the network. It doesn't use any periodic routing advertisement, link status sensing, or neighbor detection packets, and it doesn't rely on these functions from any underlying protocols in the network. 💀 This totally on-demand behavior and lack of periodic activity means the number of overhead packets caused by DSR can scale all the way down to zero, when all nodes are roughly stationary relative to each other and all the routes needed for current communication have already been discovered. 😭 As nodes start moving more, or communication patterns change, the routing packet overhead of DSR automatically scales to only what's needed to track the routes currently in use. Network topology changes that don't affect routes in use get ignored and don't make the protocol react at all. 🧚
All state maintained by DSR is "soft state" [CLARK88], which is giving main character energy. 👑 Losing any state won't interfere with the correct operation of the protocol. All state is discovered as needed, and it can easily and quickly be rediscovered after a failure without a significant impact on the protocol. 🌸 Using only soft state makes the routing protocol super robust to problems like dropped or delayed routing packets or node failures. Specifically, a node in DSR that fails and reboots can rejoin the network right away after rebooting. If the failed node was forwarding packets for other nodes as an intermediate hop along one or more routes, it can also resume that forwarding quickly after rebooting, with no or minimal interruption to the routing protocol. 🫶
For a single Route Discovery (plus routing information from other packets it overhears), a node may learn and cache multiple routes to any destination. 🍓 Supporting multiple routes makes reacting to routing changes way more rapid, since a node with multiple routes to a destination can try another cached route if the one it's been using fails. Caching multiple routes also avoids the overhead of doing a brand new Route Discovery every time a route in use breaks. 🌈 The sender of a packet selects and controls the route used for its own packets. Together with support for multiple routes, this also allows features like load balancing to be defined. Plus, all routes used are easily guaranteed to be loop-free, since the sender can avoid duplicate hops in the routes it selects. 👑
The operation of both Route Discovery and Route Maintenance in DSR is designed to support unidirectional links and asymmetric routes. As noted in Section 2, in wireless networks a link between two nodes may not work equally well in both directions, due to differing transmit power levels or sources of interference. 🦋
It's possible to interface a DSR network with other networks that sit outside it. 🌐 Those external networks may be the Internet, for example, or they may be other ad hoc networks routed with a routing protocol other than DSR. They may also be other DSR networks that get treated as external networks in order to improve scalability. The complete handling of such external networks is beyond the scope of this document. However, this document specifies a minimal set of requirements and features necessary to let nodes that only implement this specification interoperate correctly with nodes implementing interfaces to such external networks. 💜
This document specifies how DSR works for routing unicast IPv4 packets in multi-hop wireless ad hoc networks. 🎀 Advanced, optional features like Quality of Service (QoS) support and efficient multicast routing, plus operation of DSR with IPv6 [RFC2460], will be covered in other documents. The DSR specification in this document provides a compatible base that these features can be added onto, either independently or by integrating with the DSR operation specified here. As described in Appendix C, the design of DSR has been extensively studied through detailed simulations and testbed implementation and demonstration. ✨ This document encourages additional implementation and experimentation with the protocol. 🧪
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 🌸
2. Assumptions ✨
okay bestie, let's talk about the vibes DSR is built on 🫶. As described here, DSR is made mainly for mobile ad hoc networks of up to about two hundred nodes, and it's designed to work well even when everything is moving at super high speeds 🏃♀️💨. Scaling it to much bigger networks is a whole different story, and that's outside the scope of this doc 🌸.
We assume in this doc that every node wanting to talk to other nodes in the ad hoc network is down to participate fully in the protocols. No ghosting allowed 🙈. Specifically, each node in the ad hoc network SHOULD also be willing to forward packets for other nodes in the network 💅.
The diameter of an ad hoc network is the minimum number of hops it takes for a packet to get from one extreme edge of the network to the opposite extreme 🗺️. We assume this diameter will often be small (like, maybe 5 or 10 hops), but it may often be greater than 1 🦋.
Packets can get lost or corrupted on the wireless network, which is so relatable 😭. We assume a node that gets a corrupted packet can detect the error, like through a standard link-layer checksum or Cyclic Redundancy Check (CRC), and then discard the packet 🗑️.
Nodes within the ad hoc network MAY move at any time without notice and MAY even move continuously 🏃💨. We do assume the speed they move at is moderate compared to the packet transmission latency and wireless transmission range of the underlying network hardware in use. DSR can handle very rapid rates of arbitrary node mobility, but we assume nodes don't move so fast that flooding every single data packet becomes the only possible routing protocol 🤯💖.
Here's a fun one: many network interfaces, including most current LAN hardware for broadcast media like wireless, can run in "promiscuous" receive mode 👀. In this mode, the hardware delivers every received packet to the network driver software, without filtering based on link-layer destination address. We don't require this facility, but some of our optimizations can take advantage of it ✨. Promiscuous mode does add software overhead on the CPU, but we believe wireless network speeds and capacity are more of the inherent limiting factors to performance, both now and in future systems 🧚. We also believe parts of the protocol are suitable for running directly within a programmable network interface unit, so the CPU doesn't have to pick up that overhead [JOHNSON96a] 💅. Promiscuous mode may also bump up the power consumption of the network interface hardware, depending on how the receiver hardware is designed. In those cases, DSR can easily run without the optimizations that depend on promiscuous receive mode, or it can be programmed to only switch the interface into promiscuous mode every so often 🔋. Using promiscuous receive mode is entirely optional 🫶.
Wireless communication between any pair of nodes may not always work equally well in both directions 📡. This can happen because of things like transmit power levels or sources of interference around the two nodes [BANTZ94, LAUER95]. So wireless communication between each pair of nodes will often be bidirectional, but sometimes the wireless link between two nodes may only be unidirectional 🙃. That means one node can successfully send packets to the other while no communication is possible in the reverse direction. Some Medium Access Control (MAC) protocols, though, like MACA [KARN90], MACAW [BHARGHAVAN94], or IEEE 802.11 [IEEE80211], limit unicast data packet transmission to bidirectional links 🔁. They do this because of the required bidirectional exchange of request to send (RTS) and clear to send (CTS) packets in these protocols, and because of the link-layer acknowledgement feature in IEEE 802.11. When DSR runs on top of MAC protocols like these, it can take advantage of extra optimizations, like being able to reverse a source route to get a route back to the origin of the original route 🔄💜.
The IP address used by a node running the DSR protocol MAY be assigned by any mechanism 🎀. Examples include static assignment, or Dynamic Host Configuration Protocol (DHCP) [RFC2131] for dynamic assignment. The method of that assignment is outside the scope of this specification, though 🙈.
A routing protocol like DSR picks a next-hop for each packet and gives you the IP address of that next-hop 📦. When the packet is actually transmitted, though, the lower-layer protocol often needs a separate, MAC-layer address for that next-hop node. DSR uses the Address Resolution Protocol (ARP) [RFC826] to translate next-hop IP addresses into next-hop MAC addresses 🔍. A node MAY also add an entry to its ARP cache based on any received packet, as long as the IP address and MAC address of the transmitting node are available in that packet 🧠. For example, the IP address of the transmitting node is present in a Route Request option (in the Address list being accumulated), and in any packets containing a source route. Adding entries to the ARP cache this way avoids the overhead of ARP in most cases 💖.
3. DSR Protocol Overview 🌈
this section gives you the tea on how DSR actually works 🍵. The basic version of DSR uses explicit "source routing," which means each data packet sent carries the complete, ordered list of nodes it will pass through, right in its header 📜. This is so iconic, because the sender gets to select and control the routes used for its own packets 👑. It also supports multiple routes to any destination (for example, for load balancing), and it gives you a simple guarantee that the routes used are loop-free 🔥. Another perk: by including the source route in the header of each data packet, other nodes that forward or overhear these packets can easily cache that routing information for later use 🧚✨.
Here's the roadmap. Section 3.1 covers this basic operation of Route Discovery, and Section 3.2 covers basic Route Maintenance 🗺️. Sections 3.3 and 3.4 describe extra features of these two parts of DSR's operation 💅. Then Section 3.5 describes an optional, compatible extension to DSR called "flow state" 🦋. It lets most packets get routed without an explicit source route header in the packet, and the fundamental properties of DSR's operation are still preserved 💜.
3.1. Basic DSR Route Discovery 🦋
Okay so bestie, picture this: a source node is sending a brand new packet to some destination node. It stuffs a "source route" into the packet header, which is basically the list of hops the packet has to bounce through on its way to the destination 🗺️ Usually the sender checks its "Route Cache" for routes it already learned. If nothing's in there, it kicks off the Route Discovery protocol to find a fresh route. The source is called the "initiator" and the destination is called the "target" of that Route Discovery 💅
Let's say node A wants to find a route to node E. Here's how the Route Discovery would go down:
^ "A" ^ "A,B" ^ "A,B,C" ^ "A,B,C,D"
| id=2 | id=2 | id=2 | id=2
+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+
| | | |
v v v vTo start things off, node A sends out a "Route Request" as one single local broadcast packet 📡 Basically everyone within wireless range of A (roughly all of them) hears it, including node B in this example. Each Route Request names the initiator and the target, and it carries a unique request identification, which the initiator picks. In our example that ID is 2 🎀 Each Route Request also has a route record listing the address of every intermediate node this particular copy has been forwarded through. The initiator sets that route record to an empty list, so in this example it starts out listing only node A.
When another node gets the Route Request (like node B here), there are two possibilities. If that node is the target, it sends a "Route Reply" back to the initiator, copying over the accumulated route record from the Request. Then, when the initiator gets that Route Reply, it caches the route in its Route Cache so it can use it for sending later packets to that destination 🌸
If the node is not the target, things get a little more picky. It discards the Request if it has recently seen another Route Request from this same initiator with the same request identification and target address. It also discards the Request if its own address is already in the route record. (A node counts a Request as "recently seen" if it still has info about that Request in its Route Request Table, which gets covered in Section 4.3 ✨) If neither of those is true, the node adds its own address to the route record and passes the Request along by sending it as a local broadcast, keeping the same request identification. So in this example, node B broadcasts the Request, which node C receives. Nodes C and D then each broadcast it in turn, and node E ends up getting a copy 🧚
Now for the reply trip. When node E sends the Route Reply back to node A, E will usually check its own Route Cache for a route back to A. If it finds one, it uses that as the source route for the packet carrying the Route Reply. If it doesn't find one, E SHOULD start its own Route Discovery for target node A. To keep that from spiraling into an endless chain of Route Discoveries, E MUST piggyback this Route Reply onto the packet carrying its own Route Request for A 🔁 Other small data packets can ride along the same way too, like a TCP SYN packet [RFC793] on a Route Request.
Here's another option. Node E could just reverse the order of hops in the route record it's trying to send back, and use that reversed list as the source route for the Route Reply packet itself. For MAC protocols like IEEE 802.11 that need a bidirectional frame exchange for unicast packets [IEEE80211], the discovered source route MUST be reversed this way when returning the Route Reply. Why? Because reversing it tests that the discovered route really is bidirectional before the initiator starts using it 🙌 It also saves the overhead of a possible second Route Discovery. Iconic, honestly.
Next up is the Send Buffer 📦 When a node starts a Route Discovery, it saves a copy of the original packet that triggered the discovery in a local buffer. The Send Buffer holds a copy of every packet this node can't transmit yet because it doesn't have a source route to that packet's destination. Each packet in there is tied to the time it went into the buffer, and it gets tossed out once it has sat in the buffer for some timeout period, SendBufferTimeout. If the buffer is at risk of overflowing, a FIFO or other replacement strategy MAY also be used to evict packets before they expire 🫶
While a packet is sitting in the Send Buffer, the node SHOULD now and then start a new Route Discovery for that packet's destination address. But the node MUST limit how often it starts new Route Discoveries for the same address (more on that in Section 4.3), because the destination might not be reachable right now 🙈 Due to limited wireless range and nodes moving around, the network can sometimes get partitioned. That means there's no sequence of nodes that could forward a packet to the destination at that moment. How often partitions happen depends on how the nodes move and how dense the network is. They could be rare or super common.
Here's the thing: if every packet a node sent in a partitioned network kicked off a new Route Discovery, you'd get a huge pile of pointless Route Request packets flooding the part of the ad hoc network reachable from that node 😭 To cut down on that overhead, a node SHOULD use an exponential back-off algorithm to limit how fast it starts new Route Discoveries for the same target, doubling the timeout between each successive discovery for that target. If the node tries to send more data packets to that same destination faster than this limit allows, those extra packets SHOULD sit in the Send Buffer until a Route Reply gives a route to that destination. The node MUST NOT start a new Route Discovery until the minimum allowed interval for this target has passed. This cap on how often Route Discoveries can happen for one target is pretty similar to what Internet nodes already do to limit how fast ARP Requests go out for any single target IP address [RFC1122] 💜
3.2. Basic DSR Route Maintenance 🌈
Every node that sends or forwards a packet using a source route is responsible for making sure data can actually flow over the link from itself to the next hop 💖 For example, in the picture below, node A has sent a packet to node E using a source route through intermediate nodes B, C, and D:
+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |-->? | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+So in this case, node A is responsible for the link from A to B, node B is responsible for the link from B to C, node C is responsible for the link from C to D, and node D is responsible for the link from D to E 🎀
An acknowledgement is how you confirm a link can carry data, and in wireless networks these often come for free ✨ Sometimes it's a standard part of the MAC protocol already, like the link-layer acknowledgement frame in IEEE 802.11 [IEEE80211]. Other times it's a "passive acknowledgement" [JUBIN87], where for example B confirms that C got the packet by overhearing C forward it on to D. Lowkey genius 🧠
If there's no built-in acknowledgement mechanism, the sending node can explicitly ask the next node on the route to send back a DSR-specific software acknowledgement. That software acknowledgement normally goes straight back to the sender. But if the link between those two nodes is unidirectional (Section 4.6), the software acknowledgement could take a different, multi-hop path instead 🔄
After getting an acknowledgement from some neighbor, a node MAY choose to stop requiring acknowledgements from that neighbor for a brief period, unless the network interface connecting the node to that neighbor always gets an acknowledgement back for unicast traffic 🦋
When a software acknowledgement is being used, the acknowledgement request SHOULD be retransmitted up to a maximum number of times. A retransmitted acknowledgement request can go out as its own separate packet, get piggybacked onto a retransmission of the original data packet, or get piggybacked onto any packet headed to the same next hop that doesn't already contain a software acknowledgement 📬
Now the sad part 💀 If the maximum number of retransmissions has happened and still no acknowledgement arrives, the sender treats the link to that next hop as currently "broken". It SHOULD remove that link from its Route Cache, and it SHOULD send a "Route Error" to each node that has sent a packet over that link since the last acknowledgement was received. Using the picture above as an example: if C doesn't get an acknowledgement from D after a number of requests, it sends a Route Error to A, plus any other node that may have used the link from C to D since C last heard an acknowledgement from D. Node A then removes that broken link from its cache. Any retransmission of the original packet can be handled by upper layer protocols like TCP, if needed. If A wants to send that retransmission or other packets to the same destination E, and it has another route to E in its Route Cache (maybe from extra Route Replies from its earlier Route Discovery, or from overhearing enough routing info in other packets), it can use the new route right away. Otherwise, it SHOULD start a new Route Discovery for this target, subject to the back-off described in Section 3.1 🥺
3.3. Additional Route Discovery Features 💅
3.3.1. Caching Overheard Routing Information ✨
okay bestie, so any node that is forwarding or even just overhearing a packet SHOULD add all the usable routing info from that packet into its own Route Cache 🧚. How useful that info is depends on the directionality of the physical medium (Section 2) AND on the MAC protocol being used 💅. There are three distinct cases, and they're all kind of iconic in their own way:
- Links are frequently only able to operate unidirectionally (not bidirectionally), and the MAC protocol can send unicast packets over unidirectional links. 🦋
- Links only occasionally operate unidirectionally (not bidirectionally), but that one-way situation is not permanent. Almost all links are physically bidirectional, and the MAC protocol can send unicast packets over unidirectional links. 🌸
- The MAC protocol can't send unicast packets over unidirectional links, so only bidirectional links can be used for unicast. For example, the IEEE 802.11 Distributed Coordination Function (DCF) MAC protocol [IEEE80211] can only send a unicast packet over a bidirectional link, since it requires the return of a link-level acknowledgement packet from the receiver and also optionally requires a bidirectional exchange of an RTS and CTS packet between the transmitter and receiver nodes. 💀
In the first case, the source route used in a data packet, the accumulated route record in a Route Request, or the route being returned in a Route Reply SHOULD all be cached by any node in the "forward" direction. Any node SHOULD cache this info from any such packet it receives, whether the packet was addressed to that node, sent to a broadcast (or multicast) MAC address, or overheard while the node's network interface is in promiscuous mode. However, the "reverse" direction of the links in those packet headers SHOULD NOT be cached 🙈.
Here's an example. Node A is using a source route to talk to node E:
+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+As node C forwards a data packet along the route from A to E, it SHOULD add to its cache the presence of the "forward" direction links it learns from the headers of these packets, from itself to D and from D to E. Node C SHOULD NOT, in this case, cache the "reverse" direction of the links in these packet headers, from itself back to B and from B to A, since those links might be unidirectional 🥺.
In the second case, where links may occasionally operate unidirectionally, the links described above SHOULD be cached in both directions. Furthermore, in this case, if node X overhears (e.g., through promiscuous mode) a packet transmitted by node C that is using a source route from node A to E, node X SHOULD cache all of these links as well, including the link from C to X over which it overheard the packet 👑.
In the final case, where the MAC protocol requires physical bidirectionality for unicast operation, links from a source route SHOULD be cached in both directions, except when the packet also contains a Route Reply. In that situation, only the links already traversed in this source route SHOULD be cached. However, the links not yet traversed in this route SHOULD NOT be cached 🫶.
3.3.2. Replying to Route Requests Using Cached Routes
okay so when a node gets a Route Request for a target it isn't, it searches its own Route Cache for a route to that target 🔍. If it finds one, the node usually returns a Route Reply to the initiator itself instead of forwarding the Route Request ✨. In that Route Reply, this node sets the route record to list the sequence of hops this copy of the Route Request went through to get to it, concatenated with the source route to the target from its own Route Cache.
BUT (and this is a big but 😭), before sending a Route Reply that was generated from its Route Cache like this, a node MUST verify that the resulting route, after the concatenation, has no duplicate nodes in the route record. Here's a case where a Route Request for target E reaches node F, and F already has a route to E in its Route Cache:
+-----+ +-----+ +-----+ +-----+
| A |---->| B |- >| D |---->| E |
+-----+ +-----+ \ / +-----+ +-----+
\ /
\ +-----+ /
>| C |-
+-----+
| ^
v |
Route Request +-----+
Route: A - B - C - F | F | Cache: C - D - E
+-----+Concatenating the accumulated route record from the Route Request with F's cached route would include a duplicate node, since the route goes from C to F and then back to C 🌀.
Node F could try to edit the route to get rid of the duplicate, giving a route from A to B to C to D and on to E. But then node F wouldn't be on the route it returned in its own Route Reply 🙃. DSR Route Discovery prohibits node F from returning a Route Reply like that from its cache. This prohibition makes it more likely that the route is valid, since node F should have received a Route Error if the route had stopped working earlier. It also means a future Route Error traveling along the route is very likely to pass through any node that sent the Route Reply for it (including node F), which helps stale data get cleared out of caches, like the one at F, in a timely manner 🧹. Otherwise, the next Route Discovery started by A might get contaminated by a Route Reply from F with the same stale route. If node F doesn't return a Route Reply because of this restriction on answering from its Route Cache, it propagates the Route Request normally 💖.
3.3.3. Route Request Hop Limits
Every Route Request message has a "hop limit" that can be used to limit how many intermediate nodes are allowed to forward that copy of the Route Request 🎀. This hop limit is carried in the Time-to-Live (TTL) field of the IP header of the packet that holds the Route Request. Each time the Request is forwarded, this limit goes down, and the Request packet is discarded if the limit reaches zero before the target is found. This hop limit can be used to build all kinds of algorithms for controlling how far a Route Request spreads during a Route Discovery attempt 🌈.
For example, a node MAY use this hop limit to build a "non-propagating" Route Request as the first phase of a Route Discovery. A node using this technique sends its first Route Request for some target with a hop limit of 1, so any node that gets that first transmission won't forward the Request by re-broadcasting it. This is called a "non-propagating" Route Request, and it's a cheap way to check whether the target is currently a neighbor of the initiator, or whether a neighbor has a route to the target cached (basically using the neighbors' Route Caches as an extension of the initiator's own) 🧚. If no Route Reply arrives after a short timeout, the node sends a "propagating" Route Request for the target, with a hop limit set by the DiscoveryHopLimit configuration variable (DiscoveryHopLimit).
As another example, a node MAY use this hop limit to run an "expanding ring" search for the target [JOHNSON96a]. A node using this technique first sends a non-propagating Route Request as described above. If no Route Reply comes back for it, the node sends another Route Request with a hop limit of 2. For each Route Request sent, if no Route Reply comes back, the node doubles the hop limit used on the previous attempt, so it explores farther and farther for the target without letting the Route Request spread across the whole network 🦋. However, this expanding ring approach could increase the average latency of Route Discovery, since several Discovery attempts and timeouts may be needed before a route to the target is found ⏳.
3.4. Additional Route Maintenance Features
3.4.1. Packet Salvaging
When an intermediate node forwarding a packet notices through Route Maintenance that the next hop on that packet's route is broken, and the node has another route to the packet's destination in its Route Cache, the node SHOULD "salvage" the packet instead of throwing it away 🛟. To salvage a packet, the node replaces the original source route on the packet with a route from its Route Cache. Then it forwards the packet to the next node listed along this source route. For example, in the situation from the example in Section 3.2, if node C has another route cached to node E, it can salvage the packet by swapping in this new route from its own Route Cache, rather than discarding the packet 💅.
When a packet gets salvaged, the packet keeps a count of how many times it has been salvaged, so one packet can't get salvaged endlessly 🔁. Otherwise, since the TTL is only decremented once by each node, a single node could salvage a packet an unlimited number of times. Even if we chose to require the TTL to be decremented on each salvage attempt, salvaging is an expensive operation, so it's worth bounding the maximum number of salvages for a packet separately from the maximum number of hops it can travel 😤.
As described in Section 3.2, an intermediate node in a case like this one, which notices through Route Maintenance that the next hop on the route for a packet it's forwarding is broken, SHOULD also return a Route Error to the packet's original sender, naming the link the packet couldn't be forwarded over 📣. If the node sends this Route Error, it SHOULD originate the Route Error before salvaging the packet ✨.
3.4.2. Queued Packets Destined over a Broken Link 💔
Okay so picture this 🧚: a middle node is forwarding a packet, and through Route Maintenance it finds out that the next-hop link for that packet is totally broken 😭. Along with handling that packet the way Route Maintenance already says to, the node SHOULD also handle the other pending packets it has queued that are headed over this same new broken link. Specifically, it SHOULD dig through its Network Interface Queue and Maintenance Buffer (Section 4.5) for packets whose next-hop link is this new broken link. For each one still queued at this node, it SHOULD process that packet like this 💅:
- Remove the packet from the node's Network Interface Queue and Maintenance Buffer. 🗑️
- Originate a Route Error for this packet to the original sender of the packet, using the procedure described in Section 8.3.4, as if the node had already reached the maximum number of retransmission attempts for that packet for Route Maintenance. However, when it's sending these Route Errors for queued packets because of one single new broken link, the node SHOULD send no more than one Route Error to each original sender of any of these packets. (No spam, bestie 💌)
- If the node has another route to the packet's IP Destination Address in its Route Cache, the node SHOULD salvage the packet as described in Section 8.3.6. Otherwise, the node SHOULD discard the packet. 🧹
3.4.3. Automatic Route Shortening ✂️
Source routes that are already in use MAY get automatically shortened if one or more intermediate nodes in the route stop being necessary. It's kinda like passive acknowledgements [JUBIN87], and honestly that's giving clever 🪄. Here's the tea: if a node overhears a packet carrying a source route (for example, by running its network interface in promiscuous receive mode 👀), it checks the unexpended portion of that source route. If this node is NOT the intended next-hop destination for the packet but IS named later in the unexpended portion of the packet's source route, then it can infer that the intermediate nodes before itself in the source route are no longer needed in the route.
For example, the figure below shows node D overhearing a data packet being transmitted from B to C, for later forwarding to D and to E 🦋:
+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C | | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+
\ ^
\ /
---------------------In this case, this node (node D) SHOULD return a "gratuitous" Route Reply to the original sender of the packet (node A) 🔥. The Route Reply gives the shorter route as the concatenation of the portion of the original source route up through the node that transmitted the overheard packet (node B), plus the suffix of the original source route beginning with the node returning the gratuitous Route Reply (node D). So in this example, the route in the gratuitous Route Reply sent from D to A gives the new route as the sequence of hops from A to B to D to E. Main character shortcut energy ✨.
When deciding whether to return a gratuitous Route Reply in this way, a node MAY factor in more info than just the fact that it overheard the packet 🧐. For example, the node MAY decide to return the gratuitous Route Reply only when the overheard packet comes in with a signal strength or signal-to-noise ratio above some specific threshold. Also, each node maintains a Gratuitous Route Reply Table, as described in Section 4.4, so it can limit how often it originates gratuitous Route Replies for the same returned route. Not spamming the same route, iconic 🙌.
3.4.4. Increased Spreading of Route Error Messages 📣
When a source node receives a Route Error for a data packet that it originated, it passes that Route Error on to its neighbors by piggybacking it on its next Route Request 📬. This way, stale info in the caches of nodes around this source node won't generate Route Replies that contain the same invalid link the source node got the Route Error for. Stale routes getting cancelled out, periodt 💅.
Let's look at an example from Section 3.2. Node A learns from the Route Error message from C that the link from C to D is currently broken. So it removes this link from its own Route Cache and starts a new Route Discovery (if it has no other route to E in its Route Cache) 🔍. On the Route Request packet that starts this Route Discovery, node A piggybacks a copy of this Route Error. That makes the Route Error spread well to other nodes, and it guarantees that any Route Reply node A receives (including those from other nodes' Route Caches) in response to this Route Request won't contain a route that assumes this broken link still exists 🫶.
3.5. Optional DSR Flow State Extension 🌊
This section describes an optional, compatible extension to the DSR protocol, called "flow state," that lets most packets get routed without an explicit source route header in the packet 🎀. The flow state extension cuts the protocol's overhead even further, and it still keeps the fundamental properties of DSR's operation. Once a sending node has found a source route (for example, through DSR's Route Discovery mechanism), the flow state mechanism lets that sending node set up hop-by-hop forwarding state within the network, based on that source route. Each node along the route can then forward the packet to the next hop using its own local knowledge of the flow the packet is being routed along.
Flow state gets set up dynamically by the first packet using a source route, and then it can route later packets along that same flow without a source route header in them. The state at each hop along a flow is "soft state," so it automatically expires when it's no longer needed, and it can be quickly recreated when necessary ⏳. DSR's basic operation is based on an explicit source route in the header of every routed packet. The flow state extension keeps that basic operation but takes the explicit source route out of the packets, which makes it a form of "implicit source routing" 🧚♀️✨.
3.5.1. Flow Establishment 🛠️
A source node sending packets to some destination node MAY use the DSR flow state extension described here to establish a route to that destination as a flow. A "flow" is a route from the source to the destination, represented by hop-by-hop forwarding state within the nodes along the route. Each flow is uniquely identified by a combination of the source node address, the destination node address, and a flow identifier (flow ID) chosen by the source node 🆔.
Each flow ID is a 16-bit unsigned integer. Comparison between different flow IDs MUST be performed modulo 2**16. For example, using an implementation in the C programming language, a flow ID value (a) is greater than another flow ID value (b) if ((short)((a) - (b)) > 0), as long as a C language "short" data type is implemented as a 16-bit signed integer 🤓.
A DSR Flow State header in a packet identifies the flow ID to be followed in forwarding that packet. From a given source to some destination, any number of different flows MAY exist and be in use, for example, following different sequences of hops to reach the destination 🌈. One of these flows MAY be considered the "default" flow from that source to that destination. If a node receives a packet with neither a DSR Options header specifying the route to be taken (with a Source Route option in the DSR Options header) nor a DSR Flow State header specifying the flow ID to be followed, the packet is forwarded along the default flow for the source and destination addresses specified in the packet's IP header 🚦.
When establishing a new flow, the source node generates a nonzero 16-bit flow ID that's greater than any unexpired flow IDs for this (source, destination) pair. If the source wants this flow to become the default flow, the low bit of the flow ID MUST be set (the flow ID is an odd number). Otherwise, the low bit MUST NOT be set (the flow ID is an even number) 🔢.
The source node establishing the new flow then transmits a packet containing a DSR Options header with a Source Route option. To establish the flow, the source node also MUST include in the packet a DSR Flow State header, with the Flow ID field set to the chosen flow ID for the new flow. It MUST also include a Timeout option in the DSR Options header, giving the lifetime after which state information about this flow is to expire ⏰. This packet will usually be a normal data packet sent from this sender to the destination (for example, the first packet sent after discovering the new route), but it's also treated as a "flow establishment" packet 🎉.
The source node records this flow in its Flow Table for future use. It sets the TTL in this Flow Table entry to the value used in the TTL field in the packet's IP header, and it sets the Lifetime in this entry to the lifetime specified in the Timeout option in the DSR Options header. The TTL field is used for Default Flow Forwarding, as described in Sections 3.5.3 and 3.5.4 📋.
Any further packets sent with this flow ID before the timeout that also contain a DSR Options header with a Source Route option MUST use this same source route in the Source Route option 🔁.
3.5.2. Receiving and Forwarding Establishment Packets 🛤️
Packets intended to establish a flow, as described in Section 3.5.1, contain a DSR Options header with a Source Route option, and they're forwarded along the indicated route. A node implementing the DSR flow state extension, when it receives and forwards one of these DSR packets, also keeps some state in its own Flow Table. That way it can forward future packets sent along this flow with only the flow ID specified 🧠. Specifically, if the packet also contains a DSR Flow State header, this packet SHOULD cause an entry to be established for this flow in the Flow Table of each node along the packet's route 🗺️.
The Hop Count field of the DSR Flow State header is also stored in the Flow Table, and so is the lifetime specified in the Timeout option in the DSR Options header 📝.
If the Flow ID is odd and there is no flow in the Flow Table with a Flow ID greater than the received Flow ID, the node sets the default Flow ID for this (IP Source Address, IP Destination Address) pair to the received Flow ID, and the TTL of the packet is recorded 🏁.
The Flow ID option is removed before final delivery of the packet 🎁.
3.5.3. Sending Packets along Established Flows ✨
Okay so once a flow is set up like we covered in Section 3.5.1, a packet goes out that plants state in every node along the route 🌸. This state is soft, which means the protocol has ways to recover if it goes missing 🫶. BUT those recovery tricks can slow things down for packets riding flows whose state got forgotten 😭. So it's desirable to act differently depending on whether the sender is pretty sure the flow state actually exists in every node on the route 💅. We say a flow's state is "established end-to-end" when the Flow Tables of all nodes on the route have forwarding info for that flow ✨. You can't know for sure without sending packets, but implementations can make reasonable assumptions about how long state sticks around and how likely it is that every node saw the establishment packet 🧚.
A source that wants to send along an established flow checks whether the flow state is established end-to-end 🔍. If it isn't, a DSR Options header with a Source Route option carrying this flow's route gets added to the packet 🎀. The source SHOULD set the Flow ID field of the DSR Flow State header either to the flow ID previously tied to this flow's route, or to zero 💖. If it puts any other value in Flow ID, it MUST follow the processing steps in Section 3.5.1 for establishing a new flow ID 🔥. If it puts in a nonzero value, it MUST include a Timeout option whose value is not greater than the timeout left in the node's Flow Table. And if its TTL isn't equal to the one in the Flow Table, the flow MUST NOT be used as a default flow in the future 💀.
Once flow state is established end-to-end for non-default flows, a source adds a DSR Flow State header to each packet it wants to send on that flow, with Flow ID set to that flow's ID 🦋. A Source Route option SHOULD NOT be added to the packet. Though if one does get added, the steps for processing flows not established end-to-end MUST be followed 🙈.
Once flow state is established end-to-end for default flows, sources whose packets have an IP TTL equal to the TTL value in the local Flow Table entry for this flow just transmit the packet to the next hop 🚀. In this case a DSR Flow State header SHOULD NOT be added, and a DSR Options header likewise SHOULD NOT be added. Though if one is, the steps for sending along non-default flows MUST be followed 🌈. If the IP TTL isn't equal to the TTL value in the local Flow Table, the steps for processing a non-default flow MUST be followed 💜.
3.5.4. Receiving and Forwarding Packets Sent along Established Flows
Packets with a DSR Options header carrying both a nonzero Flow ID and a Source Route option get handled in Section 3.5.2 ✨. A Flow ID of zero gets ignored. This section only covers packets with no Source Route option 🌷.
If a node gets a packet with a Flow ID in the DSR Options header that points to an unexpired flow in its Flow Table, it bumps the Hop Count in the DSR Options header and forwards the packet to the next hop listed in the Flow Table 🏃♀️.
If a node gets a packet with a Flow ID for a flow that isn't in its Flow Table right now, it sends back a Route Error of type UNKNOWN_FLOW, with Error Destination and IP Destination addresses copied from the IP Source of the packet that set off the error 😱. This error packet SHOULD be MAC-destined to the node the packet came from. If it can't confirm reachability of the previous node using Route Maintenance, it MUST send the error as described in Section 8.1.1. The node sending the error SHOULD try to salvage the packet that triggered the Route Error. If it does salvage it, it MUST zero the Flow ID in the packet 🛠️.
If a node gets a packet with no DSR Options header and no DSR Flow State header, it checks the Default Flow Table 🔎. If there's a matching entry, it forwards to the next hop in the Flow Table for the default flow. Otherwise it sends back a Route Error of type DEFAULT_FLOW_UNKNOWN, with Error Destination and IP Destination addresses copied from the IP Source Address of the triggering packet. This error packet SHOULD be MAC-destined to the node it came from. If this node can't confirm reachability of the previous node using Route Maintenance, it MUST send the error as described in Section 8.1.1. The node sending the error SHOULD try to salvage the packet that triggered the Route Error. If it does salvage it, it MUST zero the Flow ID in the packet 🌟.
3.5.5. Processing Route Errors
When a node gets a Route Error of type UNKNOWN_FLOW, it marks that flow to show it has not been established end-to-end 🚩. When a node gets a Route Error of type DEFAULT_FLOW_UNKNOWN, it marks the default flow to show it has not been established end-to-end 💅.
3.5.6. Interaction with Automatic Route Shortening
Since a full source route doesn't ride along in every packet, packets using the flow state extension need a different way to do automatic route shortening 🌊. So instead, nodes listen in on packets promiscuously 👂. If a node sees a packet whose (IP Source, IP Destination, Flow ID) is in its Flow Table, but the MAC-layer (next hop) destination address isn't this node, it figures out whether the sender was upstream or downstream by looking at the Hop Count field in the DSR Flow State header. If the Hop Count is less than the expected Hop Count at this node (that is, the expected Hop Count field in the Flow Table described in Section 5.1), the node assumes the packet came from upstream. It then adds an entry for the packet to its Automatic Route Shortening Table, possibly kicking out an earlier entry 📝. When the packet is later sent to that node for forwarding, the node checks its Automatic Route Shortening Table, sees it has already received the packet, and returns a gratuitous Route Reply to the source of the packet 🎁.
3.5.7. Loop Detection
If a node gets a packet for forwarding with a TTL lower than expected while default flow forwarding is in use, it sends a Route Error of type DEFAULT_FLOW_UNKNOWN back to the IP source 🔁. It can attempt delivery of the packet by normal salvaging, subject to the constraints described in Section 8.6.7 🛟.
3.5.8. Acknowledgement Destination
With Flow State packets, the previous hop isn't necessarily known 🤷♀️. So nodes that have lost flow state can work out the previous hop, and the address of the previous hop can optionally be stored in the Acknowledgement Request. This extension SHOULD NOT be used when a Source Route option is present. It MAY be used when flow state routing is used without a Source Route option, and it SHOULD be used before Route Maintenance determines that the next-hop destination is unreachable 🙌.
3.5.9. Crash Recovery
Every node has a maximum Timeout value it can possibly generate 🕰️. That can be based on the biggest number that fits in a timeout option (2**16 - 1 seconds), or it can be lower, set in system software. When a node crashes, it doesn't establish new flows for a period equal to this maximum Timeout value. That way it doesn't collide with its old Flow IDs 💫.
3.5.10. Rate Limiting
Flow IDs can be assigned with a counter 🔢. Specifically, we keep the "Current Flow ID". When a new default Flow ID needs assigning: if the Current Flow ID is odd, the Current Flow ID is assigned as the Flow ID and then incremented by one. If it's even, one plus the Current Flow ID is assigned as the Flow ID, and the Current Flow ID is incremented by two 🧮.
If Flow IDs are assigned this way, one algorithm for avoiding duplicate, unexpired Flow IDs is to rate limit new Flow IDs to an average rate of n assignments per second, where n is 2**15 divided by the maximum Timeout value 🚦. This can be averaged over any period not exceeding the maximum Timeout value ⏱️.
3.5.11. Interaction with Packet Salvaging
Salvaging gets modified to zero the Flow ID field in the packet 🧹. Also, anytime this document mentions the Salvage field in the Source Route option in a DSR Options header, packets without a Source Route option are considered to have the value zero in the Salvage field 💖.
4. Conceptual Data Structures ✨
This document describes how DSR works in terms of a bunch of conceptual data structures 🧠. This section describes each one and gives an overview of how it's used in the protocol. In an implementation of the protocol, these data structures MUST be implemented in a manner consistent with the external behavior described in this document, but the choice of implementation is otherwise unconstrained 🎀. Additional conceptual data structures are required for the optional flow state extensions to DSR. Those get described in Section 5 🌈.
4.1. Route Cache 🗺️
Okay bestie, every node implementing DSR MUST maintain a Route Cache 💖, which holds the routing info that node needs. A node adds to its Route Cache whenever it learns about a new link between nodes in the ad hoc network. For example, it might learn about a new link from a Route Request, a Route Reply, or a DSR source route inside a packet it receives. And it removes info when it finds out a link has broken, like from a Route Error, or when the link-layer retransmission mechanism reports that it couldn't forward a packet to its next-hop destination 💀.
Anytime a node adds new information to its Route Cache, the node SHOULD check each packet in its own Send Buffer (Section 4.2) to see whether a route to that packet's IP Destination Address now exists in the node's Route Cache, including the info that was just added ✨. If it does, the packet SHOULD then be sent using that route and removed from the Send Buffer. Main character energy 👑.
Now the external networks tea 🫖. DSR networks can be interfaced with other networks outside the DSR network. Those external networks may, for example, be the Internet, or they may be other ad hoc networks routed with a routing protocol other than DSR. They may also be other DSR networks that are treated as external networks in order to improve scalability 🌸. Full handling of all that is beyond the scope of this document. BUT this document does specify a minimal set of requirements and features so that nodes implementing only this specification can still interoperate correctly with nodes that have interfaces to those external networks 🦋. That minimal set involves the First Hop External (F) and Last Hop External (L) bits in a DSR Source Route option (Section 6.7) and a Route Reply option (Section 6.3) in a packet's DSR Options header (Section 6). It also includes adding an External flag bit to each link in the Route Cache, copied from the First Hop External (F) and Last Hop External (L) bits in the DSR Source Route option or Route Reply option that the link was learned from 🧚.
The Route Cache SHOULD support storing more than one route to each destination 🍓. When searching the Route Cache for a route to some destination node, the cache is searched by destination node address. The following properties describe this searching function:
- Each implementation of DSR at any node MAY choose any appropriate strategy and algorithm for searching its Route Cache and selecting a "best" route to the destination from among those found 🔍. For example, a node MAY choose to select the shortest route to the destination (the shortest sequence of hops), or it MAY use an alternate metric to select the route from the Cache.
- However, if there are multiple cached routes to a destination, the selection of routes when searching the Route Cache SHOULD prefer routes that do not have the External flag set on any link. This preference selects routes that lead directly to the target node over routes that try to reach the target via any external networks connected to the DSR ad hoc network 🙅♀️.
- In addition, any route selected when searching the Route Cache MUST NOT have the External bit set for any links other than possibly the first link, the last link, or both. The External bit MUST NOT be set for any intermediate hops in the route selected 🚫.
An implementation of a Route Cache MAY provide a fixed capacity for the cache, or the cache size MAY be variable 📏. The following properties describe how available space in a node's Route Cache is managed:
- Each implementation of DSR at each node MAY choose any appropriate policy for managing the entries in its Route Cache, such as what to do when limited cache capacity forces a choice about which entries to keep 🗑️. For example, a node MAY chose a "least recently used" (LRU) cache replacement policy, in which the entry last used longest ago is discarded from the cache when space is needed for some new entry being added.
- However, the Route Cache replacement policy SHOULD allow routes to be categorized by "preference", where routes with a higher preference are less likely to be removed from the cache 💅. For example, a node could prefer routes it initiated a Route Discovery for over routes it learned from promiscuous snooping on other packets. In particular, a node SHOULD prefer routes that it is presently using over those it is not using 💜.
Any suitable data structure organization, consistent with this specification, MAY be used to implement the Route Cache in any node 🧩. Two types of organization are possible, for example:
- In DSR, the route returned in each Route Reply received by the initiator of a Route Discovery (or learned from the header of overhead packets, as described in Section 8.1.4) represents a complete path, meaning a sequence of links leading to the destination node. By caching each of these paths separately, a "path cache" organization for the Route Cache can be formed 🛤️. A path cache is very simple to implement and easily guarantees that all routes are loop-free, since each individual route from a Route Reply, Route Request, or packet is loop-free. To search a path cache, the sending node can simply search its Route Cache for any path (or prefix of a path) that leads to the intended destination node.
This type of organization for the Route Cache in DSR has been extensively studied through simulation [BROCH98, HU00, JOHANSSON99, MALTZ99a] and through implementation of DSR in a mobile outdoor testbed under significant workload [MALTZ99b, MALTZ00, MALTZ01] 🏆.
- Alternatively, a "link cache" organization could be used for the Route Cache. Here, each individual link (hop) in the routes returned in Route Reply packets (or otherwise learned from the header of overhead packets) is added to a unified graph data structure representing this node's current view of the network topology 🕸️. To search a link cache, the sending node must use a more complex graph search algorithm, such as the well-known Dijkstra's shortest-path algorithm, to find the current best path through the graph to the destination node. That algorithm is harder to implement and may require significantly more CPU time to execute 🥵.
But a link cache is more powerful than a path cache at effectively using all of the potential information a node might learn about the state of the network 🧠. In particular, links learned from different Route Discoveries, or from the header of any overheard packets, can be merged together to form new routes in the network. That isn't possible in a path cache because each individual path is kept separate.
This type of organization for the Route Cache in DSR, including the effect of a range of implementation choices, has been studied through detailed simulation [HU00] 🔬.
The choice of data structure organization for the Route Cache in any DSR implementation is a local matter for each node, and it affects only performance. Any reasonable choice of organization for the Route Cache does not affect either correctness or interoperability 🫶.
Each entry in the Route Cache SHOULD have a timeout associated with it, so that the entry can be deleted if it isn't used within some time ⏰. The particular algorithm and data structure used to implement the Route Cache SHOULD be considered when choosing the timeout for entries. The configuration variable RouteCacheTimeout defined in Section 9 specifies the timeout applied to entries in the Route Cache, although it is also possible to use an adaptive policy for choosing timeout values instead of a single timeout setting for all entries. For example, the Link-MaxLife cache design (below) uses an adaptive timeout algorithm and does not use the RouteCacheTimeout configuration variable 🌈.
As guidance to implementers, Appendix A describes a type of link cache known as "Link-MaxLife" that has been shown to outperform other types of link caches and path caches studied in detailed simulation [HU00] 👑. Link-MaxLife is an adaptive link cache in which each link has a timeout that the caching node determines dynamically, based on its observed past behavior of the two nodes at the ends of the link. Also, when selecting a route for a packet being sent to some destination, Link-MaxLife chooses, among cached routes of equal length (number of hops) to that destination, the route with the longest expected lifetime (the highest minimum timeout of any link in the route) ⭐. Use of the Link-MaxLife design for the Route Cache is recommended in implementations of DSR 💅✨.
4.2. Send Buffer 📦
The Send Buffer of a node implementing DSR is a queue of packets that the node can't send yet, because it doesn't have a source route to each packet's destination 😭. Each packet in the Send Buffer is logically associated with the time it was placed into the buffer. It SHOULD be removed from the Send Buffer and silently discarded after a period of SendBufferTimeout from when it was first placed in the buffer ⏳. If necessary, a FIFO strategy SHOULD be used to evict packets before they time out, so the buffer doesn't overflow 🫣.
Subject to the rate limiting defined in Section 4.3, a Route Discovery SHOULD be initiated as often as allowed for the destination address of any packets residing in the Send Buffer 🚀.
4.3. Route Request Table 🧠✨
okay bestie, so the Route Request Table is basically a node's memory of the Route Requests it recently started or passed along 📝 it's indexed by IP address, and it's giving organized 💅
The Route Request Table on a node keeps track of these things for every node it has started a Route Request toward 🎯
- The Time-to-Live (TTL) field from the IP header of the Route Request for the last Route Discovery this node started for that target node. This number lets the node run different algorithms to control how far its Route Request spreads on each Discovery it starts for a target 🌸 Two possible algorithms for using the TTL field are described in Section 3.3.3, so go check those out 🦋
- The time this node last started a Route Request for that target node ⏰
- The number of Route Discoveries in a row this node has started for that target since it got a valid Route Reply giving a route to that target node 🔁
- The remaining amount of time before which this node MAY next attempt a Route Discovery for that target node. When the node starts a new Route Discovery for this target, this field in the entry gets set to the timeout for that Discovery. After that timeout, the node MAY start a new Discovery for that target 💜 Until a valid Route Reply comes back for this target node address, a node MUST use a back-off algorithm to figure out this timeout for each Discovery it starts for this target using the same Time-to-Live (TTL) value in the IP header of the Route Request packet 😭 The gap between these back-to-back Discovery starts SHOULD grow by doubling the timeout each time a new one starts 📈
The Route Request Table on a node also keeps track of these things about initiator nodes that sent this node a Route Request 👀
- A FIFO cache of
RequestTableIdsentries, holding the Identification value and target address from the most recent Route Requests this node got from that initiator node 🗂️
Nodes SHOULD use an LRU policy to manage the entries in their Route Request Table 🧹
Okay, this part is lowkey important 🚨 The number of Identification values to keep in each Route Request Table entry, RequestTableIds, MUST NOT be unlimited 🙅♀️ Why? Because in the worst case, a node crashes and reboots, and the first RequestTableIds Route Discoveries it starts after rebooting could look like duplicates to the other nodes in the network 💀 Also, a node SHOULD base its initial Identification value, the one it uses for Route Discoveries after rebooting, on a battery backed-up clock or some other persistent memory device, if it has one 🔋 That helps avoid any possible delay in finding new routes after rebooting 🚀 If there's no such source for the initial Identification value, a node that just rebooted SHOULD base its initial Identification value on a random number 🎲
4.4. Gratuitous Route Reply Table 🎁
The Gratuitous Route Reply Table of a node implementing DSR keeps track of "gratuitous" Route Replies this node sent as part of automatic route shortening ✂️ Remember from Section 3.4.3: a node sends a gratuitous Route Reply when it overhears a packet some node sent, where the overhearing node wasn't the intended next hop but is named later in the unexpended hops of that packet's source route 👂 The overhearing node sends the gratuitous Route Reply to the original sender of the packet, listing the shorter route (the hops of the source route "skipped over" by this packet don't get included) 🛤️ A node uses this table to limit how often it sends gratuitous Route Replies to the same original sender, for the same node it overheard a packet from that triggered the reply 🚦
Each entry in the Gratuitous Route Reply Table of a node has these fields 📋
- The address of the node this node sent a gratuitous Route Reply to 📬
- The address of the node this node overheard the packet from, the one that triggered that gratuitous Route Reply 👂
- The remaining time before this entry in the Gratuitous Route Reply Table expires and SHOULD be deleted by the node ⏳ When a node makes a new entry in its Gratuitous Route Reply Table, the timeout for that entry SHOULD be set to the value
GratReplyHoldoff🕰️
When a node overhears a packet that would trigger a gratuitous Route Reply, and a matching entry already exists in the node's Gratuitous Route Reply Table, then the node SHOULD NOT send a gratuitous Route Reply for that packet 🙅♀️ Otherwise, if no matching entry exists, the node SHOULD make a new entry in its Gratuitous Route Reply Table to record that gratuitous Route Reply, with a timeout value of GratReplyHoldoff 📝✨
4.5. Network Interface Queue and Maintenance Buffer 📦
Depending on stuff like how the operating system and protocol stack are organized, the network interface device driver, and the network interface hardware, a packet being sent could get queued in a bunch of different ways 🌀 For example, outgoing packets from the network protocol stack might get queued at the operating system or link layer before the network interface sends them 📤 The network interface might also have its own retransmission mechanism for packets, like what happens in IEEE 802.11 [IEEE80211] 📡 The DSR protocol, as part of Route Maintenance, needs limited buffering of packets that were already sent but whose next-hop reachability hasn't been figured out yet 🧐 DSR's behavior is defined here using two conceptual data structures that, together, cover this queuing behavior 💖
The Network Interface Queue of a node implementing DSR is an output queue of packets from the network protocol stack that are waiting to be sent by the network interface 🚪 For example, in the 4.4BSD Unix network protocol stack implementation, this queue for a network interface is represented as a struct ifqueue [WRIGHT95] 💾 This queue holds packets while the network interface is busy sending another packet 🙌
The Maintenance Buffer of a node implementing DSR is a queue of packets this node sent that are waiting for next-hop reachability confirmation as part of Route Maintenance 🫧 For each packet in the Maintenance Buffer, a node keeps track of how many retransmissions happened and the time of the last retransmission 🔢 Packets get added to the Maintenance Buffer after the first transmission attempt is made 🚀 The Maintenance Buffer MAY be of limited size. If the buffer doesn't have room for a new packet when one is being added, the new packet SHOULD be silently discarded 🤫 If no confirmation comes back after MaxMaintRexmt attempts to confirm next-hop reachability of some node, then all packets in this node's Maintenance Buffer with that next-hop destination SHOULD be removed from the Maintenance Buffer 🗑️ In this case, the node also SHOULD originate a Route Error for this packet to each original source of a packet removed this way (Section 8.3), and SHOULD salvage each packet removed this way (Section 8.3.6) if it has another route to that packet's IP Destination Address in its Route Cache 🛟 The definition of MaxMaintRexmt conceptually includes any retransmissions that might be attempted for a packet at the link layer or in the network interface hardware 🔁 The timeout value to use for each transmission attempt for an acknowledgement request depends on the type of acknowledgement mechanism Route Maintenance uses for that attempt, as described in Section 8.3 🎀
4.6. Blacklist 🖤
When a node using the DSR protocol is connected through a network interface that requires physically bidirectional links for unicast transmission, the node MUST maintain a blacklist 🚫 The blacklist is a table, indexed by neighbor node address, that shows the link between this node and the specified neighbor node might not be bidirectional 🙈 A node adds another node's address to this list when it believes broadcast packets from that other node reach this node, but unicast transmission between the two nodes isn't possible 📡 For example, if a node forwarding a Route Reply finds out that the next hop is unreachable, it puts that next hop on its blacklist 💀
Once a node finds out it can communicate bidirectionally with one of the nodes on the blacklist, it SHOULD remove that node from the blacklist 🎉 For example, if node A has node B on its blacklist, but after sending a Route Request, node A hears B forward the Route Request with a route record showing the broadcast from A to B worked, then A SHOULD remove the entry for node B from its blacklist 🙌
A node MUST associate a state with each node on its blacklist, saying whether the unidirectionality of the link to that node is "questionable" or "probable" 🧠 Each time the unreachability is positively determined, the node SHOULD set the state to "probable" 🚨 After the unreachability hasn't been positively determined for some amount of time, the state SHOULD go back to "questionable" 🌤️ A node MAY expire entries for nodes from its blacklist after a reasonable amount of time 🗓️
5. Additional Conceptual Data Structures for Flow State Extension 🌈✨
This section defines more conceptual data structures used by the optional "flow state" extension to DSR 🧩 In an implementation of the protocol, these data structures MUST be implemented in a way that's consistent with the external behavior described in this document 💅 The choice of implementation is otherwise totally unconstrained, so do your thing 🦋
5.1. Flow Table
okay bestie, a node doing the flow state extension MUST implement a Flow Table 💖 or some other data structure that acts the same from the outside. A node that is NOT doing the extension SHOULD NOT implement one. no cap, that's the whole vibe 🎀
The Flow Table keeps track of flows that this node has recently sent or forwarded packets for ✨ It's indexed by a triple of (IP Source Address, IP Destination Address, Flow ID), where Flow ID is a 16-bit number the source picks (see Section 3.5.1). Each entry holds these fields:
- The MAC address of the next-hop node along this flow.
- Which outgoing network interface on this node gets used to send packets along this flow.
- The MAC address of the previous-hop node along this flow.
- Which network interface on this node packets from that previous-hop node come in on.
- A timeout after which this entry in the Flow Table MUST be deleted ⏰
- The expected value of the Hop Count field in the DSR Flow State header for packets received for forwarding along this flow (for use with packets containing a DSR Flow State header).
- Whether or not this flow can be used as a default flow for packets originated by this node 👑 (the Flow ID of a default flow MUST be odd).
- The entry SHOULD record the complete source route for the flow. (Nodes not recording the complete source route cannot participate in Automatic Route Shortening 😭)
- The entry MAY contain a field recording the time this entry was last used.
The entry MUST be deleted when its timeout expires. bye bye, old flow 👋
5.2. Automatic Route Shortening Table
A node implementing the flow state extension SHOULD implement an Automatic Route Shortening Table 🦋 or some other data structure that acts the same from the outside. A node NOT implementing the flow state extension SHOULD NOT implement an Automatic Route Shortening Table.
This table keeps info about received packets that might be good candidates for Automatic Route Shortening 👀 It's indexed by the same triple (IP Source Address, IP Destination Address, Flow ID). Each entry is a list of (packet identifier, Hop Count) pairs for that flow. The packet identifier can be any unique identifier for the received packet. For example, for IPv4 packets, this combo of fields from the IP header MAY be used as a unique identifier: Source Address, Destination Address, Identification, Protocol, Fragment Offset, and Total Length 🍓
The Hop Count in each list item is copied from the Hop Count field in the DSR Flow State header of the received packet that created that table entry. Any packet identifier SHOULD appear at most once in an entry's list, and that list item SHOULD record the minimum Hop Count value received for that packet. Also, if the DSR implementation can see the wireless signal strength or signal-to-noise ratio a packet was received at, the node MAY, for example, remember instead the minimum Hop Count value for which that packet's signal strength or signal-to-noise ratio went over some threshold 📶
Space in the Automatic Route Shortening Table MAY be dynamically managed by any local algorithm at the node 🧠 For example, to keep memory use in check, any existing entry MAY be deleted at any time, and the number of packets listed in each entry MAY be limited. BUT when reclaiming space, nodes SHOULD favor keeping info about more flows over info about more packets per entry, as long as at least a small number of packets (e.g., 3) can still be kept in each entry 💅
5.3. Default Flow ID Table
A node implementing the flow state extension MUST implement a Default Flow Table 💜 or some other data structure that acts the same from the outside. A node NOT implementing the flow state extension SHOULD NOT implement a Default Flow Table.
For each (IP Source Address, IP Destination Address) pair that a node forwards packets for, the node MUST record:
- The largest odd Flow ID value seen.
- The time at which all the corresponding flows forwarded by this node expire.
- The current default Flow ID.
- A flag saying whether or not the current default Flow ID is valid.
If a node deletes this record for an (IP Source Address, IP Destination Address) pair, it MUST also delete all Flow Table entries for that pair. Nodes MUST delete table entries once all of that pair's flows forwarded by this node have expired. it's giving clean-up crew 🧹✨
6. DSR Options Header Format 🧚
The Dynamic Source Routing protocol uses a special header that carries control info and can be added to any existing IP packet 🎀 This DSR Options header has a small, fixed-size, 4-octet portion, followed by a sequence of zero or more DSR options carrying optional info. Where the sequence of DSR options ends is implied by the total length of the DSR Options header.
For IPv4, the DSR Options header MUST immediately follow the IP header in the packet. (If a Hop-by-Hop Options extension header, as defined in IPv6 [RFC2460], becomes defined for IPv4, the DSR Options header MUST immediately follow the Hop-by-Hop Options extension header, if one is present in the packet, and MUST otherwise immediately follow the IP header.)
To add a DSR Options header to a packet, you insert it right after the packet's IP header, before any following header like a traditional (e.g., TCP or UDP) transport layer header 💅 Specifically, the Protocol field in the IP header is used to say that a DSR Options header follows the IP header, and the Next Header field in the DSR Options header is used to say what type of protocol header (such as a transport layer header) comes after the DSR Options header.
If any headers follow the DSR Options header in a packet, the total length of the DSR Options header (and therefore the total, combined length of all DSR options present) MUST be a multiple of 4 octets. This requirement keeps those following headers aligned in the packet 📐
6.1. Fixed Portion of DSR Options Header
The fixed portion of the DSR Options header carries info that MUST be present in any DSR Options header 🫶 It has this 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Header |F| Reserved | Payload Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Options .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Here's what each field does:
Next Header : 8-bit selector. Identifies the type of header immediately following the DSR Options header. It uses the same values as the IPv4 Protocol field [RFC1700]. If no header follows, then Next Header MUST have the value 59, "No Next Header" [RFC2460].
Flow State Header (F) : Flag bit. MUST be set to 0. This bit is set in a DSR Flow State header (Section 7.1) and clear in a DSR Options header.
Reserved : MUST be sent as 0 and ignored on reception.
Payload Length : The length of the DSR Options header, excluding the 4-octet fixed portion. The value of the Payload Length field defines the total length of all options carried in the DSR Options header.
Options : Variable-length field. Its length is specified by the Payload Length field in this DSR Options header. It contains one or more pieces of optional info (DSR options), encoded in type-length-value (TLV) format (except for the Pad1 option described in Section 6.8).
The placement of DSR options following the fixed portion of the DSR Options header MAY be padded for alignment. However, because ad hoc networks typically have limited wireless bandwidth, this padding is not required, and receiving nodes MUST NOT expect options within a DSR Options header to be aligned 🙈
Each DSR option gets a unique Option Type code. The most significant 3 bits (that is, Option Type & 0xE0) let a node that doesn't implement processing for this Option Type behave in the closest-to-correct way for that type 🔥
- The most significant bit in the Option Type value (that is,
Option Type & 0x80) says whether a node receiving this Option Type, when it doesn't implement processing for it, SHOULD respond to that DSR option with a Route Error of typeOPTION_NOT_SUPPORTED, except that such a Route Error SHOULD never be sent in response to a packet containing a Route Request option. - The two bits after that (that is,
Option Type & 0x60) are a two-bit field showing how such a node that doesn't support this Option Type MUST process the packet:
00 = Ignore Option
01 = Remove Option
10 = Mark Option
11 = Drop PacketWhen these 2 bits are 00 (that is, Option Type & 0x60 == 0), a node not implementing processing for that Option Type MUST use the Opt Data Len field to skip over the option and keep processing. When these 2 bits are 01 (that is, Option Type & 0x60 == 0x20), a node not implementing processing for that Option Type MUST use the Opt Data Len field to remove the option from the packet and continue processing as if the option had never been included in the received packet. When these 2 bits are 10 (that is, Option Type & 0x60 == 0x40), a node not implementing processing for that Option Type MUST set the most significant bit following the Opt Data Len field, MUST ignore the contents of the option using the Opt Data Len field, and MUST continue processing the packet. Finally, when these 2 bits are 11 (that is, Option Type & 0x60 == 0x60), a node not implementing processing for that Option Type MUST drop the packet 💀
The following types of DSR options are defined in this document for use within a DSR Options header:
- Route Request option (Section 6.2)
- Route Reply option (Section 6.3)
- Route Error option (Section 6.4)
- Acknowledgement Request option (Section 6.5)
- Acknowledgement option (Section 6.6)
- DSR Source Route option (Section 6.7)
- Pad1 option (Section 6.8)
- PadN option (Section 6.9)
In addition, Section 7 specifies further DSR options for use with the optional DSR flow state extension 🌈
6.2. Route Request Option ✨
okay so the Route Request option lives inside a DSR Options header and looks 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Target Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+IP fields: 💖
- Source Address
- It's a MUST: put the address of the node originating this packet here. Intermediate nodes that retransmit the packet to propagate the Route Request MUST NOT change this field. Hands off! 🙅
- Destination Address
- This one MUST be set to the IP limited broadcast address (255.255.255.255). 📣
- Hop Limit (TTL)
- This MAY be varied from 1 to 255, for example, to implement non-propagating Route Requests and Route Request expanding-ring searches (Section 3.3.3). Super flexible, it's giving 🌈
Route Request fields: 🧚
- Option Type
- The value is
1. Nodes that don't understand this option will just ignore it, no drama 🫶
- The value is
- Opt Data Len
- This is an 8-bit unsigned integer, the length of the option in octets, not counting the Option Type and Opt Data Len fields themselves. It MUST be set equal to
(4 * n) + 6, where n is the number of addresses in the Route Request Option. Math check passed ✨
- This is an 8-bit unsigned integer, the length of the option in octets, not counting the Option Type and Opt Data Len fields themselves. It MUST be set equal to
- Identification
- This is a unique value made up by the initiator (the original sender) of the Route Request. Every new Route Request gets a brand-new Identification value, for example one pulled from a sequence number counter covering all the Route Requests that node has started. 🔢
- This value lets a receiving node figure out whether it has recently seen a copy of this Route Request. If this Identification value (for this IP Source address and Target Address) is found in the receiving node's Route Request Table (in the cache of Identification values in the entry there for this initiating node), that receiving node MUST discard the Route Request. Bye bye, duplicate 💀
- When a Route Request gets propagated, this field MUST be copied from the received copy of the Route Request being propagated. Copy and paste, but make it iconic 📋
- Target Address
- The address of the node that is the target of the Route Request. The main character of this whole search 👑
- Address[1..n]
- Address[i] is the IPv4 address of the i-th node recorded in the Route Request option. The address in the Source Address field of the IP header is the address of the initiator of the Route Discovery, and it MUST NOT be listed in the Address[i] fields. So Address[1] is the IPv4 address of the first node on the path after the initiator. Don't double-list the OG sender, periodt 💅
- The number of addresses in this field is given by the Opt Data Len field in the option (n = (Opt Data Len - 6) / 4). Each node that propagates the Route Request adds its own address to this list and bumps the Opt Data Len value up by 4 octets. A little growing list, so cute 🌸
The Route Request option MUST NOT appear more than once within a DSR Options header. One Route Request per header, bestie, no stacking 🙈
6.3. Route Reply Option 🦋
the Route Reply option in a DSR Options header is encoded like this, and honestly it's so pretty 🥹
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |L| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+IP fields: 💌
- Source Address
- This is set to the address of the node sending the Route Reply. If a node is replying from its Route Cache (Section 3.3.2) or sending a gratuitous Route Reply (Section 3.4.3), this address can be different from the address that was the target of the Route Discovery. Plot twist energy 🎭
- Destination Address
- This MUST be set to the address of the source node of the route being returned. It's copied from the Source Address field of the Route Request that generated the Route Reply or, for a gratuitous Route Reply, copied from the Source Address field of the data packet that triggered the gratuitous Reply. 🎯
Route Reply fields: 🧁
- Option Type
- The value is
2. Nodes that don't understand this option will ignore it 🫠
- The value is
- Opt Data Len
- This is an 8-bit unsigned integer, the length of the option in octets, not counting the Option Type and Opt Data Len fields. It MUST be set equal to
(4 * n) + 1, where n is the number of addresses in the Route Reply Option. ✔️
- This is an 8-bit unsigned integer, the length of the option in octets, not counting the Option Type and Opt Data Len fields. It MUST be set equal to
- Last Hop External (L)
- Set this to indicate that the last hop given by the Route Reply (the link from Address[n-1] to Address[n]) is actually an arbitrary path in a network outside the DSR network. The exact route outside the DSR network isn't represented in the Route Reply. 🌍
- Nodes that cache this hop in their Route Cache MUST flag the cached hop with the External flag. Such hops MUST NOT be returned in a cached Route Reply generated from this Route Cache entry. When picking routes from the Route Cache to route a packet being sent, you SHOULD prefer routes that contain no hops flagged as External. Choose the clean routes, bestie ✨
- Reserved
- This MUST be sent as 0 and ignored on reception. 0️⃣
- Address[1..n]
- This is the source route being returned by the Route Reply. The route is a sequence of hops, starting at the source node named in the Destination Address field of the IP header of the packet carrying the Route Reply, going through each of the Address[i] nodes in the order listed in the Route Reply, and ending at the node indicated by Address[n]. 🗺️
- The number of addresses in the Address[1..n] field is given by the Opt Data Len field in the option (n = (Opt Data Len - 1) / 4). 🔢
A Route Reply option MAY appear one or more times within a DSR Options header. Multiple replies? Totally allowed 💜
6.4. Route Error Option 💀
okay the Route Error option in a DSR Options header is encoded like this, and it's kinda the drama queen of the bunch 😭
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Error Type |Reservd|Salvage|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Type-Specific Information .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Option Type
- The value is
3. Nodes that don't understand this option will ignore it 🙃
- The value is
- Opt Data Len
- This is an 8-bit unsigned integer, the length of the option in octets, not counting the Option Type and Opt Data Len fields.
- For the current definition of the Route Error option, this field MUST be set to 10, plus the size of any Type-Specific Information present in the Route Error. Further extensions to the Route Error option format may also be included after the Type-Specific Information portion of the option, and their presence will be indicated by the Opt Data Len field. When Opt Data Len is greater than what's needed for the fixed portion of the Route Error plus the necessary Type-Specific Information (as indicated by the Option Type value in the option), the leftover octets are read as extensions. Right now, no such extensions have been defined, so this is all still theoretical 🔮
- Error Type
- This is the type of error encountered. Currently these type values are defined:
1 = NODE_UNREACHABLE
2 = FLOW_STATE_NOT_SUPPORTED
3 = OPTION_NOT_SUPPORTED- Other values of the Error Type field are reserved for future use. Future-proofing, iconic 🔭
- Reservd
- Reserved. This MUST be sent as 0 and ignored on reception. 🤫
- Salvage
- This is a 4-bit unsigned integer, copied from the Salvage field in the DSR Source Route option of the packet that triggered the Route Error. 🛟
- The "total salvage count" of the Route Error option is worked out from the value in this option's Salvage field, plus the Salvage fields of all the Route Error options before it in the packet. Each such Route Error option adds one, plus its own Salvage value, to the total. Counting is serious business 🧮
- Error Source Address
- The address of the node that originated the Route Error. For example, the node that tried to forward a packet and discovered the link failure. 🚨
- Error Destination Address
- The address of the node the Route Error MUST be delivered to. For example, when Error Type is set to NODE_UNREACHABLE, this field is set to the address of the node that generated the routing information claiming that the hop from the Error Source Address to the Unreachable Node Address (given in the Type-Specific Information) was a valid hop. That's the one who gets the apology 💌
- Type-Specific Information
- Information specific to the Error Type of this Route Error message. 🧩
A Route Error option MAY appear one or more times within a DSR Options header. Errors can stack, no shame 🫶
6.4.1. Node Unreachable Type-Specific Information ✨
okay so when the Route Error is NODE_UNREACHABLE, the Type-Specific Information field is laid out 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Unreachable Node Address 💖
This is the IP address of the node that got marked as unreachable. It's the next-hop neighbor that the node with address Error Source Address was trying to send the packet to. Main character energy, honestly 💅
6.4.2. Flow State Not Supported Type-Specific Information 🌸
when the Route Error is FLOW_STATE_NOT_SUPPORTED, the Type-Specific Information field is empty. nothing to see here, just vibes 🫶
6.4.3. Option Not Supported Type-Specific Information 🎀
when the Route Error is OPTION_NOT_SUPPORTED, the Type-Specific Information field looks like this 🧚
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|Unsupported Opt|
+-+-+-+-+-+-+-+-+Unsupported Opt ✨
This is the Option Type of the option that set off the Route Error. Bestie, it's giving detective work 🔥
6.5. Acknowledgement Request Option 🍓
okay so the Acknowledgement Request option in a DSR Options header is encoded 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 🌈
The value is 160. Nodes that don't understand this option will remove it and send back a Route Error.
Opt Data Len 🦋
An 8-bit unsigned integer. It's the length of the option in octets, not counting the Option Type and Opt Data Len fields.
Identification 💅
This gets set to a unique value. The node receiving the packet over this hop copies it into the Identification field of the Acknowledgement option it sends back.
An Acknowledgement Request option MUST NOT appear more than once within a DSR Options header. bestie, one per header, no exceptions 🙅♀️💀
6.6. Acknowledgement Option 🫧
so the Acknowledgement option in a DSR Options header is encoded 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 🍓
The value is 32. Nodes that don't understand this option will just remove it.
Opt Data Len 🌈
An 8-bit unsigned integer. It's the length of the option in octets, not counting the Option Type and Opt Data Len fields.
Identification 🧚
This gets copied from the Identification field of the Acknowledgement Request option in the packet being acknowledged. the matching energy is immaculate ✨
ACK Source Address 💖
The address of the node that's sending the acknowledgement.
ACK Destination Address 🎀
The address of the node the acknowledgement is supposed to reach.
An Acknowledgement option MAY appear one or more times within a DSR Options header. you can stack these as much as you need 💜
6.7. DSR Source Route Option 🗺️
okay the DSR Source Route option in a DSR Options header is encoded 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 💅
The value is 96. Nodes that don't understand this option will drop the packet. no mercy 💀
Opt Data Len 🦋
An 8-bit unsigned integer. It's the length of the option in octets, not counting the Option Type and Opt Data Len fields. For the format of the DSR Source Route option defined here, this field MUST be set to the value (n * 4) + 2, where n is the number of addresses present in the Address[i] fields.
First Hop External (F) 🌸
Set this to say the first hop in the DSR Source Route option is really an arbitrary path in a network outside the DSR network. The exact route outside the DSR network isn't represented in the option. Nodes caching this hop in their Route Cache MUST flag the cached hop with the External flag. Hops like that MUST NOT be returned in a Route Reply generated from that Route Cache entry. When choosing routes from the Route Cache to route a packet being sent, selection SHOULD prefer routes that contain no hops flagged as External. lowkey a whole vibe 🫶
Last Hop External (L) 🧚
Set this to say the last hop in the DSR Source Route option is really an arbitrary path in a network outside the DSR network. The exact route outside the DSR network isn't represented in the option. Nodes caching this hop in their Route Cache MUST flag the cached hop with the External flag. Hops like that MUST NOT be returned in a Route Reply generated from that Route Cache entry. When choosing routes from the Route Cache to route a packet being sent, selection SHOULD prefer routes that contain no hops flagged as External. same energy as the first hop, just at the end 🌈
Reserved 🍓
This MUST be sent as 0 and ignored on reception. 🤫
Salvage 💜
A 4-bit unsigned integer. It counts how many times this packet has been salvaged as a part of DSR routing (Section 3.4.1). ✨
Segments Left (Segs Left) 🎀
The number of route segments remaining. In other words, how many explicitly listed intermediate nodes are still left to visit before the final destination 🗺️
Address[1..n] 👑
This is the sequence of addresses in the source route. When routing and forwarding the packet, the source route gets processed as described in Sections 8.1.3 and 8.1.5. The number of addresses in the Address[1..n] field is shown by the Opt Data Len field in the option (n = (Opt Data Len - 2) / 4). 🦋
When forwarding a packet along a DSR source route using a DSR Source Route option in the packet's DSR Options header, the Destination Address field in the packet's IP header is always set to the address of the packet's ultimate destination. A node that receives a packet containing a DSR Options header with a DSR Source Route option MUST examine the indicated source route to figure out whether it's the intended next-hop node for the packet and how to forward it, as defined in Sections 8.1.4 and 8.1.5. read the source route, get the job done 💅✨
6.8. Pad1 Option 🫧
the Pad1 option in a DSR Options header is encoded like this 🌸
+-+-+-+-+-+-+-+-+
| Option Type |
+-+-+-+-+-+-+-+-+Option Type 💖
The value is 224. Nodes that don't understand this option will drop the packet and send back a Route Error.
A Pad1 option MAY be included in the Options field of a DSR Options header to line up the options that come after it. But that alignment isn't required, and a node receiving a packet containing a DSR Options header MUST NOT expect it. 🫶
If any headers follow the DSR Options header in a packet, the total length of the DSR Options header MUST be a multiple of 4 octets. The total length is indicated by the Payload Length field in the DSR Options header. In this case, when building a DSR Options header in a packet, enough Pad1 or PadN options MUST be included in the Options field of the DSR Options header to make the total length a multiple of 4 octets. the math has to add up, bestie 🧮
If more than one consecutive octet of padding is going into the Options field of a DSR Options header, the PadN option described next SHOULD be used instead of multiple Pad1 options. 🎀
Quick note: the Pad1 option is a special case. It doesn't have an Opt Data Len or Option Data field. just the type, that's it 🧚
6.9. PadN Option 🌈
the PadN option in a DSR Options header is encoded like this 💜
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
| Option Type | Opt Data Len | Option Data
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -Option Type 🍓
The value is 0. Nodes that don't understand this option will ignore it.
Opt Data Len ✨
An 8-bit unsigned integer. It's the length of the option in octets, not counting the Option Type and Opt Data Len fields. It also tells you the size of the Option Data field.
Option Data 🦋
A bunch of zero-valued octets, equal in number to the Opt Data Len.
A PadN option MAY be included in the Options field of a DSR Options header to line up the options that come after it. That alignment isn't required, and a node receiving a packet containing a DSR Options header MUST NOT expect it. 🌸
If any headers follow the DSR Options header in a packet, the total length of the DSR Options header, which is indicated by the Payload Length field in the DSR Options header, MUST be a multiple of 4 octets. In this case, when building a DSR Options header in a packet, enough Pad1 or PadN options MUST be included in the Options field of the DSR Options header to make the total length a multiple of 4 octets. same rule, same padding, we love consistency 💅
7. Additional Header Formats and Options for Flow State Extension 🌊
okay so the optional DSR flow state extension needs a brand new header type, the DSR Flow State header 🧚
Also, the DSR flow state extension adds these options to the DSR Options header defined in Section 6:
- Timeout option (Section 7.2.1) ⏰
- Destination and Flow ID option (Section 7.2.2) 🆔
Two new Error Type values are also defined for use in the Route Error option in a DSR Options header:
UNKNOWN_FLOW🫣DEFAULT_FLOW_UNKNOWN🙈
Finally, there's an extension to the Acknowledgement Request option in a DSR Options header:
- Previous Hop Address 💜
This section defines each of these new header, option, or extension formats. let's get into it, bestie 💖✨
7.1. DSR Flow State Header ✨
okay so the DSR Flow State header is a tiny 4-byte header 🎀 that you can optionally use to carry the flow ID and hop count for a packet riding along a DSR flow. how do you tell it apart from the fixed DSR Options header (Section 6.1)? the Flow State Header (F) bit is set to 1 in the Flow State header and stays at 0 in the fixed DSR Options header 🦋
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Header |F| Hop Count | Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Next Header 💅 This is an 8-bit selector that tells you what kind of header comes right after the DSR Flow State header. it uses the same values as the IPv4 Protocol field [RFC1700].
Flow State Header (F) 🌸 This is a flag bit. it MUST be set to 1. the bit is set in a DSR Flow State header and clear in a DSR Options header (Section 6.1).
Hop Count 🧚 This is a 7-bit unsigned integer. it's the number of hops this packet has been forwarded through.
Flow Identification 💜 This is the flow ID for this flow, as described in Section 3.5.1.
7.2. New Options and Extensions in DSR Options Header 🎀
7.2.1. Timeout Option ⏳
okay the Timeout option is defined for use in a DSR Options header 💖 it tells you how much time is left before the flow ID the packet is being sent along expires.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Timeout |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 🦋 The value is 128. nodes that don't understand this option will ignore it and return a Route Error.
Opt Data Len 🍓 This is an 8-bit unsigned integer. it's the length of the option in octets, not counting the Option Type and Opt Data Len fields.
When no extensions are present, the Opt Data Len of a Timeout option is 2. further extensions to DSR may add more data to a Timeout option, and you can tell they're there because the Opt Data Len is greater than 2. currently, no such extensions have been defined 🙈
Timeout ⭐ This is the number of seconds for which this flow stays valid.
the Timeout option MUST NOT appear more than once within a DSR Options header. one is the limit, bestie 💅
7.2.2. Destination and Flow ID Option 🧚♀️
the Destination and Flow ID option is defined for use in a DSR Options header 🫶 it lets you send a packet to an intermediate host along one flow, so it can be forwarded to the final destination along a different flow. this option is what makes aggregating the state of multiple flows possible ✨
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | New Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| New IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 👑 The value is 129. nodes that don't understand this option will ignore it and return a Route Error.
Opt Data Len 🌈 This is an 8-bit unsigned integer. it's the length of the option in octets, not counting the Option Type and Opt Data Len fields.
When no extensions are present, the Opt Data Len of a Destination and Flow ID option is 6. further extensions to DSR may add more data to a Destination and Flow ID option, and those are indicated by an Opt Data Len greater than 6. currently, no such extensions have been defined 💀
New Flow Identifier 🌸 This tells you the next identifier to store in the Flow ID field of the DSR Options header.
New IP Destination Address 🍓 This tells you the next address to store in the Destination Address field of the IP header.
the Destination and Flow ID option MAY appear one or more times within a DSR Options header 🎀
7.3. New Error Types for Route Error Option 🚨
7.3.1. Unknown Flow Type-Specific Information 🔥
okay so a new Error Type value of 129 (UNKNOWN_FLOW) is defined for use in a Route Error option in a DSR Options header 💖 the Type-Specific Information for errors of this type is encoded 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flow ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Original IP Destination Address 🦋 This is the IP Destination Address of the packet that caused the error.
Flow ID 💜 This is the Flow ID contained in the DSR Flow ID option that caused the error.
7.3.2. Default Flow Unknown Type-Specific Information 🌈
a new Error Type value of 130 (DEFAULT_FLOW_UNKNOWN) is defined for use in a Route Error option in a DSR Options header ⭐ its Type-Specific Information is encoded as follows:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Original IP Destination Address 🧚 This is the IP Destination Address of the packet that caused the error.
7.4. New Acknowledgement Request Option Extension 🫶
7.4.1. Previous Hop Address Extension 🎀
when the Opt Data Len field of an Acknowledgement Request option in a DSR Options header is greater than or equal to 6, the ACK Request Source Address field is present 👀 the option is then formatted 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Packet Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Request Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Option Type 💖 The value is 160. nodes that don't understand this option will remove the option and return a Route Error.
Opt Data Len 🌸 This is an 8-bit unsigned integer. it's the length of the option in octets, not counting the Option Type and Opt Data Len fields.
When no extensions are presents, the Opt Data Len of an Acknowledgement Request option is 2. further extensions to DSR may add more data to an Acknowledgement Request option, and those are indicated by an Opt Data Len greater than 2.
currently, one such extension has been defined 🦋 if the Opt Data Len is at least 6, then an ACK Request Source Address is present.
Packet Identifier 🍓 The Packet Identifier field is set to a unique number. it's copied into the Identification field of the DSR Acknowledgement option when the node receiving the packet returns it over this hop.
ACK Request Source Address 💜 This is the address of the node requesting the DSR Acknowledgement.
8. Detailed Operation 🔍
8.1. General Packet Processing ⚡
8.1.1. Originating a Packet 📦
okay bestie, when a node using DSR routing originates any packet, it MUST perform the following sequence of steps 💅
- Search the node's Route Cache for a route to the address given in the IP Destination Address field in the packet's header.
- If no such route is found in the Route Cache, then perform Route Discovery for the Destination Address, as described in Section 8.2. starting a Route Discovery for this target node address means the node either adds a Route Request option in a DSR Options header to this existing packet, or saves this existing packet to its Send Buffer and starts the Route Discovery by sending a separate packet containing such a Route Request option. if the node chooses to start the Route Discovery by adding the Route Request option to this existing packet, it will replace the IP Destination Address field with the IP "limited broadcast" address (255.255.255.255) [RFC1122], and copy the original IP Destination Address to the Target Address field of the new Route Request option added to the packet, as described in Section 8.2.1.
- If the packet now does not contain a Route Request option, then this node must have a route to the Destination Address of the packet. if the node has more than one route to this Destination Address, the node selects one to use for this packet. if the length of this route is greater than 1 hop, or if the node decides to request a DSR network-layer acknowledgement from the first-hop node in that route, then insert a DSR Options header into the packet, as described in Section 8.1.2, and insert a DSR Source Route option, as described in Section 8.1.3. the source route in the packet is initialized from the selected route to the Destination Address of the packet.
- Transmit the packet to the first-hop node address given in the selected source route, using Route Maintenance to determine the reachability of the next hop, as described in Section 8.3.
8.1.2. Adding a DSR Options Header to a Packet 🎁
a node originating a packet adds a DSR Options header to the packet, if necessary, to carry information needed by the routing protocol 🫶 a packet MUST NOT contain more than one DSR Options header. a DSR Options header gets added to a packet by following this sequence of steps (these steps assume that the packet contains no other headers that MUST be located in the packet before the DSR Options header):
- Insert a DSR Options header after the IP header but before any other header that may be present.
- Set the Next Header field of the DSR Options header to the Protocol number field of the packet's IP header.
- Set the Protocol field of the packet's IP header to the protocol number assigned for DSR (48).
8.1.3. Adding a DSR Source Route Option to a Packet ✨
okay so when a node originates a packet, it adds a DSR Source Route option to the packet, but only if it's actually needed 🫶 The whole point is to carry the source route from this originating node to the packet's final destination address. 💅 Here's the step-by-step, the node builds the option and tweaks the IP packet like this:
- The node creates a DSR Source Route option, as described in Section 6.7, and appends it to the DSR Options header in the packet. (A DSR Options header is added, as described in Section 8.1.2, if not already present.) 🎀
- The number of
Address[i]fields to include in the DSR Source Route option (n) is the number of intermediate nodes in the source route for the packet (i.e., excluding the address of the originating node and the final destination address of the packet). TheSegments Leftfield in the DSR Source Route option is initialized equal ton. 🧚 - The addresses within the source route for the packet are copied into sequential
Address[i]fields in the DSR Source Route option, fori = 1, 2, ..., n. 🍓 - The First Hop External (F) bit in the DSR Source Route option is copied from the External bit flagging the first hop in the source route for the packet, as indicated in the Route Cache. 🌸
- The Last Hop External (L) bit in the DSR Source Route option is copied from the External bit flagging the last hop in the source route for the packet, as indicated in the Route Cache. 🦋
- The
Salvagefield in the DSR Source Route option is initialized to0. 💜
8.1.4. Processing a Received Packet 🌈
okay this part is SO important bestie 😭 When a node receives any packet (whether it's being forwarded, overheard, or is the final destination), if that packet has a DSR Options header, the node MUST process every option in that header, in the order they appear there. Here's how each one gets handled:
- If the DSR Options header has a Route Request option, the node SHOULD pull the source route out of the Route Request and add that routing info to its Route Cache, subject to the conditions in Section 3.3.1. ✨ The routing info from the Route Request is this sequence of hop addresses:
initiator, Address[1], Address[2], ..., Address[n]where initiator is the value of the Source Address field in the IP header of the packet carrying the Route Request (the address of the initiator of the Route Discovery), and each Address[i] is a node the Route Request has passed through, in turn, during this Route Discovery. The value n here is the number of addresses recorded in the Route Request option, or (Opt Data Len - 6) / 4. 🔥
After possibly updating its Route Cache based on the Route Request option, the node MUST then process the Route Request option as described in Section 8.2.2. 👑
- If the DSR Options header has a Route Reply option, the node SHOULD pull the source route out of the Route Reply and add that routing info to its Route Cache, subject to the conditions in Section 3.3.1. 💅 The source route from the Route Reply is this sequence of hop addresses:
initiator, Address[1], Address[2], ..., Address[n]where initiator is the value of the Destination Address field in the IP header of the packet carrying the Route Reply (the address of the initiator of the Route Discovery), and each Address[i] is a node the source route passes through, in turn, on the way to the target of the Route Discovery. Address[n] is the address of the target. 🦋
If the Last Hop External (L) bit is set in the Route Reply, the node MUST flag the last hop from the Route Reply (the link from Address[n-1] to Address[n]) in its Route Cache as External. 🙈 The value n here is the number of addresses in the source route being returned in the Route Reply option, or (Opt Data Len - 1) / 4.
After possibly updating its Route Cache based on the Route Reply option, then if the packet's IP Destination Address matches one of this node's IP addresses, the node MUST then process the Route Reply option as described in Section 8.2.6. 🫶
- If the DSR Options header has a Route Error option, the node MUST process the Route Error option as described in Section 8.3.5. 💀
- If the DSR Options header has an Acknowledgement Request option, the node MUST process the Acknowledgement Request option as described in Section 8.3.3. 🧚
- If the DSR Options header has an Acknowledgement option, then, subject to the conditions in Section 3.3.1, the node SHOULD add the single link from the node identified by the ACK Source Address field to the node identified by the ACK Destination Address field to its Route Cache. 🌸
After possibly updating its Route Cache based on the routing info in the Acknowledgement option, the node MUST then process the Acknowledgement option as described in Section 8.3.3. 👑
- If the DSR Options header has a DSR Source Route option, the node SHOULD pull the source route out of the DSR Source Route option and add that routing info to its Route Cache, subject to the conditions in Section 3.3.1. 🍓 If the
Salvagefield in the DSR Source Route option is zero, then the routing info from the DSR Source Route is this sequence of hop addresses:
source, Address[1], Address[2], ..., Address[n], destinationOtherwise (i.e., if Salvage is nonzero), the routing info from the DSR Source Route is this sequence of hop addresses:
Address[1], Address[2], ..., Address[n], destinationwhere source is the value of the Source Address field in the IP header of the packet carrying the DSR Source Route option (the original sender of the packet), each Address[i] is the value in the Address[i] field in the DSR Source Route option, and destination is the value of the Destination Address field in the packet's IP header (the last-hop address of the source route). The value n here is the number of addresses in the source route in the DSR Source Route option, or (Opt Data Len - 2) / 4. 💜
After possibly updating its Route Cache based on the routing info in the DSR Source Route option, the node MUST then process the DSR Source Route option as described in Section 8.1.5. 🌈
- Any Pad1 or PadN options in the DSR Options header are ignored. 🎀
- Finally, if the Destination Address in the packet's IP header matches one of this receiving node's own IP address(es), remove the DSR Options header and all the included DSR options in the header, and pass the rest of the packet to the network layer. 🦋✨
8.1.5. Processing a Received DSR Source Route Option ✨
okay bestie, so whenever a node gets a packet with a DSR Source Route option 🦋 (whether it's forwarding it, overhearing it, or it's the final destination), that node SHOULD examine the packet to see if it's a chance for automatic route shortening 💅 (see Section 3.4.3). Here's the tea: if this node isn't the intended next-hop but its address shows up later in the unexpended part of the source route, then the packet is basically handing you an opportunity 🎀. The intermediate nodes between the node that overheard the packet and this node aren't needed anymore in the source route. ✂️ In that case, this node SHOULD perform the following steps as part of automatic route shortening:
- The node searches its Gratuitous Route Reply Table for an entry describing a gratuitous Route Reply it sent earlier, where both the original sender (of the packet that triggered that Route Reply) and the transmitting node (the one it overheard that packet from) match the node addresses for this new packet. If it finds one, the node SHOULD NOT perform automatic route shortening in response to this receipt of this packet. 🙅♀️
- Otherwise, the node creates an entry for this overheard packet in its Gratuitous Route Reply Table. The timeout for this new entry SHOULD be initialized to the value
GratReplyHoldoff⏳. Once that timeout expires, the node SHOULD delete the entry. 🧹 - After making the new entry, the node originates a gratuitous Route Reply to the IP Source Address of the overheard packet, as described in Section 3.4.3. 💌
Ngl this part is so iconic 😭: if the MAC protocol in use isn't capable of sending unicast packets over unidirectional links (see Section 3.3.1), then the node MUST use a source route for this Route Reply. That route is made by reversing the sequence of hops the triggering packet took to reach and get overheard by this node. The reversed route basically tests the hops for bidirectionality 🔁, so the gratuitous Route Reply can't reach the initiator of the Route Discovery unless every hop it crosses is bidirectional. no cap, that's genius.
- Discard the overheard packet, since it got here before its normal trip along the source route would have brought it to this node. Another copy will normally show up here as the source route says, so tossing this early copy (the one that triggered the Route Reply) stops the duplication that would've happened otherwise. 🚫
If the packet isn't discarded as part of automatic route shortening above, then the node MUST process the Source Route option using these steps 📋:
- If the value of the
Segments Leftfield in the DSR Source Route option equals0, then remove the DSR Source Route option from the DSR Options header. - Else, let
nequal(Opt Data Len - 2) / 4. This is the number of addresses in the DSR Source Route option. - If the value of the
Segments Leftfield is greater thann, then send an ICMP Parameter Problem, Code 0, message [RFC792] to the IP Source Address, pointing to theSegments Leftfield, and discard the packet. Do not process the DSR Source Route option any further. 🙈 - Else, decrement the value of the
Segments Leftfield by 1. LetiequalnminusSegments Left. This is the index of the next address to be visited in the Address vector. 🧚 - If
Address[i]or the IP Destination Address is a multicast address, then discard the packet. Do not process the DSR Source Route option any further. - If this node has more than one network interface and
Address[i]is the address of one of this node's network interfaces, then that signals a change in the network interface to use for forwarding the packet, as described in Section 8.4. In this case, decrement the value of theSegments Leftfield by 1 to skip over that address (the one that indicated the interface change), and go back to the first step above (checking the value of theSegments Leftfield) to keep processing this Source Route option. In further processing of this Source Route option, the indicated new network interface MUST be used in forwarding the packet. 🔀 - If the MTU of the link this node would transmit over to forward the packet to the node
Address[i]is less than the size of the packet, the node MUST either discard the packet and send an ICMP Packet Too Big message to the packet's Source Address [RFC792], or fragment it as specified in Section 8.5. 🧩 - Forward the packet to the IP address in the
Address[i]field of the IP header, following normal IP forwarding procedures, including checking and decrementing the Time-to-Live (TTL) field in the packet's IP header [RFC791, RFC1122]. During this forwarding, the next-hop node (identified byAddress[i]) MUST be treated as a direct neighbor node. The transmission to that next node MUST be done in a single IP forwarding hop, without Route Discovery and without searching the Route Cache. 🚀 - While forwarding the packet, perform Route Maintenance for the packet's next hop by verifying that the next-hop node is reachable, as described in Section 8.3. 🫶
Multicast addresses MUST NOT appear in a DSR Source Route option, or in the IP Destination Address field of a packet carrying a DSR Source Route option in a DSR Options header. absolutely not, bestie 🙅♀️💀
8.1.6. Handling an Unknown DSR Option
okay so nodes implementing DSR MUST handle all the options specified in this document, except the ones for the optional flow state extension (Section 7) 🌸. BUT future extensions to DSR might add option types that this version of the spec doesn't understand 👀. In DSR, the Option Type code actually encodes the required behavior for nodes that don't implement that type of option, and those behaviors live in the most significant 3 bits of the Option Type 🔥.
If the most significant bit of the Option Type is set (that is, Option Type & 0x80 is nonzero), and the packet does NOT contain a Route Request option, a node SHOULD return a Route Error to the IP Source Address, following the steps in Section 8.3.4. The only difference is the Error Type MUST be set to OPTION_NOT_SUPPORTED, and the Unsupported Opt field MUST be set to the Option Type that triggered the Route Error. 💅
Whether or not a Route Error gets sent for that DSR option, the node also MUST examine the next 2 most significant bits (that is, Option Type & 0x60) 🔍:
- When these 2 bits are
00(that is,Option Type & 0x60 == 0), a node that doesn't implement processing for that Option Type MUST use theOpt Data Lenfield to skip over the option and keep processing. 🦘 - When these 2 bits are
01(that is,Option Type & 0x60 == 0x20), a node that doesn't implement processing for that Option Type MUST use theOpt Data Lenfield to remove the option from the packet and keep processing as if the option had never been included in the received packet. 🗑️ - When these 2 bits are
10(that is,Option Type & 0x60 == 0x40), a node that doesn't implement processing for that Option Type MUST set the most significant bit following theOpt Data Lenfield. On top of that, the node MUST then ignore and skip over the contents of the option using theOpt Data Lenfield, and MUST continue processing the packet. 🙋♀️ - Finally, when these 2 bits are
11(that is,Option Type & 0x60 == 0x60), a node that doesn't implement processing for that Option Type MUST drop the packet. 💀
8.2. Route Discovery Processing 🗺️
okay so Route Discovery is the mechanism a node S uses when it wants to send a packet to a destination node D and needs a source route to D 🧭. Route Discovery SHOULD be used only when S tries to send a packet to D and doesn't already know a route to D. The node that starts a Route Discovery is called the "initiator" 🎤, and the destination it's looking for is called the "target" 🎯.
Route Discovery is totally on-demand ✨. A node starts one based on its own origination of new packets for some destination address it doesn't currently have a route to. It does NOT depend on any periodic or background exchange of routing information, or on neighbor node detection at any layer of the network protocol stack at any node. So chill, no constant background chatter 🌈.
The Route Discovery procedure uses two types of messages, a Route Request (Section 6.2) and a Route Reply (Section 6.3), to actively search the ad hoc network for a route to the desired target 🔎. These DSR messages MAY be carried in any type of IP packet, through use of the DSR Options header described in Section 6 🎀.
Except as discussed in Section 8.3.5, a Route Discovery for a destination address SHOULD NOT be initiated unless the initiating node has a packet in its Send Buffer that needs delivery to that destination 📦. A Route Discovery for a given target node MUST NOT be initiated unless it's permitted by the rate-limiting information in the Route Request Table 🚦. After each Route Discovery attempt, the interval between successive Route Discoveries for this target SHOULD be doubled, up to a maximum of MaxRequestPeriod, until a valid Route Reply comes back for this target 📈💖.
8.2.1. Originating a Route Request ✨
Okay bestie, so when a node wants to start a Route Discovery for some target, it makes and sets up a Route Request option inside a DSR Options header in an IP packet 🎀. This MAY be a separate IP packet that only carries this Route Request option, or the node MAY tuck the option into some existing packet it already needs to send to the target node (like the IP packet this node originated that made it start Route Discovery for that packet's destination address 🫶). The Route Request option MUST be included in a DSR Options header in the packet. To set it up, the node runs through this sequence of steps:
- The
Option Typein the option MUST be set to the value2. - The
Opt Data Lenfield in the option MUST be set to the value6. When it's first initiated, the whole Route Request option is 8 octets, butOpt Data Lendoesn't count theOption TypeandOpt Data Lenfields themselves 🧚 - The
Identificationfield in the option MUST be set to a new value, different from the one used for other Route Requests this node recently initiated for this same target address. For example, each node MAY maintain a single counter value for generating a newIdentificationvalue for each Route Request it initiates 🔢 - The
Target Addressfield in the option MUST be set to the IP address that is the target of this Route Discovery 🎯
The Source Address in the IP header of this packet MUST be the node's own IP address. The Destination Address in the IP header of this packet MUST be the IP "limited broadcast" address (255.255.255.255) 📣
A node MUST maintain, in its Route Request Table, information about the Route Requests it initiates. When it starts a new Route Request, the node MUST use the information recorded in the Route Request Table entry for that Route Request's target, and it MUST update that information in the table entry for the next Route Request initiated for this target. In particular:
- The Route Request Table entry for a target node records the
Time-to-Live (TTL)field used in the IP header of the Route Request for the last Route Discovery this node initiated for that target node. This value lets the node run a bunch of different algorithms to control how far its Route Request spreads on each Route Discovery for a target. As examples, two possible algorithms for this use of the TTL field are described in Section 3.3.3 🌈 - The Route Request Table entry for a target node records the number of consecutive Route Requests initiated for this target since the node received a valid Route Reply giving a route to that target node. It also records the remaining amount of time before which this node MAY next attempt a Route Discovery for that target node ⏳
A node MUST use these values to run a back-off algorithm, which limits how fast this node starts new Route Discoveries for the same target address. In particular, until a valid Route Reply is received for this target node address, the timeout between consecutive Route Discovery initiations for this target node with the same hop limit SHOULD increase by doubling the timeout value on each new initiation 📈
The behavior of a node processing a packet with a DSR Options header that has both a DSR Source Route option and a Route Request option is unspecified 🤷♀️ Packets SHOULD NOT contain both a DSR Source Route option and a Route Request option.
Packets containing a Route Request option SHOULD NOT include an Acknowledgement Request option, SHOULD NOT expect link-layer acknowledgement or passive acknowledgement, and SHOULD NOT be retransmitted. The retransmission of packets containing a Route Request option is controlled solely by the logic described in this section 💅
8.2.2. Processing a Received Route Request Option ✨
When a node receives a packet containing a Route Request option, that node MUST process the option using this sequence of steps:
- If the
Target Addressfield in the Route Request matches this node's own IP address, the node SHOULD return a Route Reply to the initiator of this Route Request (theSource Addressin the IP header of the packet), as described in Section 8.2.4 🎉 The source route for this Reply is the sequence of hop addresses:
initiator, Address[1], Address[2], ..., Address[n], targetHere, initiator is the address of the initiator of this Route Request, each Address[i] is an address from the Route Request, and target is the target of the Route Request (the Target Address field in the Route Request). The value n is the number of addresses recorded in the Route Request, or (Opt Data Len - 6) / 4 🧮
The node then MUST replace the Destination Address field in the Route Request packet's IP header with the value in the Target Address field in the Route Request option, and continue processing the rest of the Route Request packet normally. The node MUST NOT process the Route Request option further, and MUST NOT retransmit the Route Request to propagate it to other nodes as part of the Route Discovery 🛑
- Else, the node MUST examine the route recorded in the Route Request option (the IP
Source Addressfield and the sequence ofAddress[i]fields) to determine if this node's own IP address already appears in this list of addresses. If so, the node MUST discard the entire packet carrying the Route Request option 🙅♀️ - Else, if the Route Request was received through a network interface that requires physically bidirectional links for unicast transmission, the node MUST check if the Route Request was last forwarded by a node on its blacklist (Section 4.6). If such an entry is found in the blacklist, and the state of the unidirectional link is "probable", then the Request MUST be silently discarded 🫥
- Else, if the Route Request was received through a network interface that requires physically bidirectional links for unicast transmission, the node MUST check if the Route Request was last forwarded by a node on its blacklist. If such an entry is found in the blacklist, and the state of the unidirectional link is "questionable", then the node MUST create and unicast a Route Request packet to that previous node, setting the IP Time-To-Live (TTL) to
1to prevent the Request from being propagated. If the node receives a Route Reply in response to the new Request, it MUST remove the blacklist entry for that node, and SHOULD continue processing. If the node does not receive a Route Reply within some reasonable amount of time, the node MUST silently discard the Route Request packet 🕵️♀️ - Else, the node MUST search its Route Request Table for an entry for the initiator of this Route Request (the IP
Source Addressfield). If such an entry is found in the table, the node MUST search the cache ofIdentificationvalues of recently received Route Requests in that table entry, to determine if the cache has an entry matching theIdentificationvalue and target node address in this Route Request. If such an (Identification, target address) entry is found in this cache, in this entry in the Route Request Table, then the node MUST discard the entire packet carrying the Route Request option 🔁 - Else, this node SHOULD further process the Route Request according to the following sequence of steps:
- Add an entry for this Route Request in its cache of (
Identification, target address) values of recently received Route Requests 📝 - Conceptually create a copy of this entire packet, and perform the following steps on the copy of the packet 👯♀️
- Append this node's own IP address to the list of
Address[i]values in the Route Request, and increase the value of theOpt Data Lenfield in the Route Request by 4 (the size of an IP address). However, if the node has multiple network interfaces, this step MUST be modified by the special processing specified in Section 8.4 🔧 - This node SHOULD search its own Route Cache for a route (from itself, as if it were the source of a packet) to the target of this Route Request. If such a route is found in its Route Cache, then this node SHOULD follow the procedure outlined in Section 8.2.3 to return a "cached Route Reply" to the initiator of this Route Request, if permitted by the restrictions specified there 💌
- If the node does not return a cached Route Reply, then this node SHOULD transmit this copy of the packet as a link-layer broadcast, with a short jitter delay before the broadcast is sent. The jitter period SHOULD be chosen as a random period, uniformly distributed between 0 and
BroadcastJitter🦋
- Add an entry for this Route Request in its cache of (
8.2.3. Generating a Route Reply Using the Route Cache ✨
okay so, like we covered in Section 3.3.2 🦋, a node processing a received Route Request can totally skip passing it along toward the target if it already has a route from itself to that target in its Route Cache. 💅 A Route Reply made from the node's own cached route to the target is called a "cached Route Reply", and it's giving major efficiency because it cuts way down on Route Request flooding across the whole network 🌊. The general processing of a received Route Request is in Section 8.2.2. This section covers the extra stuff that MUST be true before a cached Route Reply can be made and sent back, plus how to actually return it. 🫶
Before a node can even think about a cached Route Reply for a received Route Request, it MUST have a route from itself to the target of that Route Request in its Route Cache. 🎀 But wait, there's more! Before making that cached Route Reply, the node MUST verify that there are no duplicate addresses in the route accumulated in the Route Request together with the route from this node's Route Cache. Specifically, there MUST be no duplicates among these addresses:
- The IP Source Address of the packet containing the Route Request,
- The
Address[i]fields in the Route Request, and - The nodes listed in the route obtained from this node's Route Cache, excluding the address of this node itself (this node itself is the common point between the route accumulated in the Route Request and the route obtained from the Route Cache).
If any duplicates show up among those, the node MUST NOT send a cached Route Reply using that Route Cache route 🙅 (but it's possible this node has a different route in its Route Cache that passes the no-duplicates check, and then it can send a cached Route Reply based on that one instead). The node SHOULD keep processing the Route Request as described in Section 8.2.2 if it doesn't send a cached Route Reply.
If the Route Request and the route from the Route Cache pass that check, the node SHOULD build and return a cached Route Reply like this:
- The source route for this Route Reply is the sequence of hop addresses
initiator, Address[1], Address[2], ..., Address[n], c-routewhere initiator is the address of the initiator of this Route Request, each Address[i] is an address from the Route Request, and c-route is the sequence of hop addresses in the source route to this target node, obtained from the node's Route Cache. When appending this cached route to the source route for the reply, the address of this node itself MUST be excluded, since it's already listed as Address[n].
- Send a Route Reply to the initiator of the Route Request, using the procedure defined in Section 8.2.4. The initiator of the Route Request is indicated in the
Source Addressfield in the packet's IP header.
Before sending the cached Route Reply, though, the node MAY delay the Reply to help prevent a possible Route Reply "storm", as described in Section 8.2.5. 🌸
If the node returns a cached Route Reply like this, then the node MUST NOT propagate the Route Request further (aka the node MUST NOT rebroadcast the Route Request) 🙈. Instead, if the packet contains no other DSR options and no payload after the DSR Options header (e.g., the Route Request isn't piggybacked on a TCP or UDP packet), the node SHOULD simply discard the packet. Otherwise (if the packet contains other DSR options or any payload after the DSR Options header), the node SHOULD forward the packet along the cached route to the target of the Route Request. If the node does that, it MUST use these steps:
- Copy the Target Address from the Route Request option in the DSR Options header to the
Destination Addressfield in the packet's IP header. - Remove the Route Request option from the DSR Options header in the packet, and add a DSR Source Route option to the packet's DSR Options header.
- In the DSR Source Route option, set the
Address[i]fields to represent the source route found in this node's Route Cache to the original target of the Route Discovery (the new IP Destination Address of the packet). Specifically, the node copies the hop addresses of the source route into sequentialAddress[i]fields in the DSR Source Route option, fori = 1, 2, ..., n.Address[1], here, is the address of this node itself (the first address in the source route found from this node to the original target of the Route Discovery). The value n, here, is the number of hop addresses in this source route, excluding the destination of the packet (which is instead already represented in theDestination Addressfield in the packet's IP header). - Initialize the
Segments Leftfield in the DSR Source Route option to n as defined above. - The First Hop External (
F) bit in the DSR Source Route option MUST be set to 0. - The Last Hop External (
L) bit in the DSR Source Route option is copied from the External bit flagging the last hop in the source route for the packet, as indicated in the Route Cache. - The
Salvagefield in the DSR Source Route option MUST be initialized to some nonzero value. The particular nonzero value used SHOULD beMAX_SALVAGE_COUNT. By initializing this field to a nonzero value, nodes forwarding or overhearing this packet will not consider a link to exist between the IP Source Address of the packet and theAddress[1]address in the DSR Source Route option (e.g., they will not attempt to add this to their Route Cache as a link). By choosingMAX_SALVAGE_COUNTas the nonzero value to which the node initializes this field, nodes furthermore will not attempt to salvage this packet. - Transmit the packet to the next-hop node on the new source route in the packet, using the forwarding procedure described in Section 8.1.5.
8.2.4. Originating a Route Reply ✨
A node originates a Route Reply to reply to a received and processed Route Request, following the procedures in Sections 8.2.2 and 8.2.3. The Route Reply rides inside a Route Reply option (Section 6.3). The Route Reply option MAY be sent back to the initiator of the Route Request in a separate IP packet, used only to carry this Route Reply option, or it MAY be tucked into any other IP packet being sent to this address. 📦
The Route Reply option MUST be included in a DSR Options header in the packet returned to the initiator. To set up the Route Reply option, the node runs through this sequence of steps:
- The
Option Typein the option MUST be set to the value 3. - The
Opt Data Lenfield in the option MUST be set to the value(n * 4) + 3, where n is the number of addresses in the source route being returned (excluding the Route Discovery initiator node's address). - If this node is the target of the Route Request, the Last Hop External (
L) bit in the option MUST be initialized to 0. - The
Reservedfield in the option MUST be initialized to 0. - The Route Request Identifier MUST be initialized to the
Identifierfield of the Route Request to which this Route Reply is sent in response. - The sequence of hop addresses in the source route are copied into the
Address[i]fields of the option.Address[1]MUST be set to the first-hop address of the route after the initiator of the Route Discovery,Address[n]MUST be set to the last-hop address of the source route (the address of the target node), and each otherAddress[i]MUST be set to the next address in sequence in the source route being returned.
The Destination Address field in the IP header of the packet carrying the Route Reply option MUST be set to the address of the initiator of the Route Discovery (i.e., for a Route Reply being returned in response to some Route Request, the IP Source Address of the Route Request). 🎯
After creating and initializing the Route Reply option and the IP packet containing it, send the Route Reply. When sending the Route Reply from this node (but not from nodes forwarding it), this node SHOULD delay the Reply by a small jitter period chosen randomly between 0 and BroadcastJitter. ⏳
When returning any Route Reply in the case where the MAC protocol in use in the network isn't able to transmit unicast packets over unidirectional links, the source route used for routing the Route Reply packet MUST be obtained by reversing the sequence of hops in the Route Request packet (the source route that's then returned in the Route Reply). This restriction lets the Route Reply test this sequence of hops for bidirectionality, so the Route Reply won't be received by the initiator of the Route Discovery unless each of the hops it goes over (and so each of the hops in the source route being returned in the Reply) is bidirectional. 🔁
If sending a Route Reply to the initiator of the Route Request requires performing a Route Discovery, the Route Reply option MUST be piggybacked on the packet that contains the Route Request. This piggybacking prevents a recursive dependency, where the target of the new Route Request (which was itself the initiator of the original Route Request) would otherwise have to do another Route Request just to return its Route Reply. 🔄
If sending the Route Reply to the initiator of the Route Request does not require performing a Route Discovery, a node SHOULD send a unicast Route Reply in response to every Route Request it receives for which it is the target node. 💖
8.2.5. Preventing Route Reply Storms ✨
Okay so, being able to reply to a Route Request from what's in your Route Cache (see Sections 3.3.2 and 8.2.3) is super helpful, but it can cause a Route Reply "storm" in some cases 😭. If a node broadcasts a Route Request for a target, and its neighbors all have a route to that target cached, every one of those neighbors might try to send a Route Reply. That's wasted bandwidth and maybe more network collisions in the area 💀
Here's the vibe 👀 Nodes B, C, D, E, and F all catch A's Route Request for target G, and each one has its own cached route to G:
+-----+ +-----+
| D |< >| C |
+-----+ \ / +-----+
Cache: C - B - G \ / Cache: B - G
\ +-----+ /
-| A |-
+-----+\ +-----+ +-----+
| | \--->| B | | G |
/ \ +-----+ +-----+
/ \ Cache: G
v v
+-----+ +-----+
| E | | F |
+-----+ +-----+
Cache: F - B - G Cache: B - GNormally, they'd all reply from their own caches at about the same time, since they all got the broadcast at about the same time 😩 That's a lot of Replies bumping into each other, which can cause local congestion in the wireless network and packet collisions among some or all of them if the MAC protocol doesn't have enough collision avoidance for these packets. Plus, the replies will often show routes of different lengths, like in this example 🫠
To tone it down, a node that can put its network interface into promiscuous receive mode MAY delay its own Route Reply for a short bit, listening in to see if the initiating node starts using a shorter route first 👂 Specifically, this node MAY delay its Route Reply for a random period:
d = H * (h - 1 + r)where h is the length in number of network hops for the route to be returned in this node's Route Reply, r is a random floating point number between 0 and 1, and H is a small constant delay (at least twice the maximum wireless link propagation delay) to be introduced per hop.
This delay basically randomizes when each node sends its Route Reply 🎲 Anyone with a route shorter than h sends their Reply before this node, and anyone with a route longer than h sends theirs after it.
During the delay period, this node promiscuously receives all packets, looking for data packets from the initiator of this Route Discovery that are headed to the target. If one of those data packets uses a source route of length less than or equal to h, this node may infer that the initiator has already received a Route Reply with an equally good or better route. In that case, this node SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for this Route Discovery 🙅♀️
8.2.6. Processing a Received Route Reply Option 🔁
Section 8.1.4 covers the general processing for a received packet, including adding routing info from options in the packet's DSR Options header to the receiving node's Route Cache 📚
If the received packet has a Route Reply, no extra special processing is needed for that option beyond what's described there. As Section 4.1 explains, anytime a node adds new info to its Route Cache (including the info from this Route Reply option), the node SHOULD check each packet in its own Send Buffer (Section 4.2) to see if a route to that packet's IP Destination Address now exists in its Route Cache, including the info it just added. If so, the packet SHOULD then be sent using that route and removed from the Send Buffer. That general procedure handles all the processing a received Route Reply option needs ✨
When you're using a MAC protocol that requires bidirectional links for unicast transmission, a unidirectional link may get discovered during propagation of the Route Request 😬 Then, when the Route Reply goes back over the reverse path, a forwarding node may find that its next-hop is unreachable. In that case, it MUST add the next-hop address to its blacklist (Section 4.6).
8.3. Route Maintenance Processing 🛠️
Route Maintenance is how a source node S figures out, while using a source route to some destination node D, if the network topology has changed so much that it can't use its route to D anymore because a link along it stopped working 🕵️♀️ When Route Maintenance says a source route is broken, S can try any other route it happens to know to D, or invoke Route Discovery again to find a new route for later packets to D. Route Maintenance for that route only happens while S is actually sending packets to D.
Specifically, when forwarding a packet, a node MUST attempt to confirm the reachability of the next-hop node, unless such confirmation was received in the last MaintHoldoffTime period. Individual implementations MAY choose to bypass that confirmation for some limited number of packets, as long as all those packets fall within MaintHoldoffTime since the last confirmation. If no confirmation arrives after the retransmission of MaxMaintRexmt acknowledgement requests (counted after the initial transmission of the packet, and conceptually including all retransmissions provided by the MAC layer), the node decides that the link to this next-hop node of the source route is "broken" 💔
This confirmation from the next-hop node can be done with a link-layer acknowledgement (Section 8.3.1), a "passive acknowledgement" (Section 8.3.2), or a network-layer acknowledgement (Section 8.3.3). The retransmission timing depends on which type of acknowledgement mechanism is used. When not using link-layer acknowledgements for Route Maintenance, nodes SHOULD use passive acknowledgements when possible, but SHOULD try requesting a network-layer acknowledgement one or more times before deciding the link has failed and originating a Route Error to the original sender of the packet, as described in Section 8.3.4 🥺
In deciding whether or not to send a Route Error in response to attempting to forward a packet from some sender over a broken link, a node MUST limit the number of consecutive packets from a single sender that it attempts to forward over this same broken link for which it chooses not to return a Route Error. This requirement MAY be satisfied by returning a Route Error for each packet the node attempts to forward over a broken link.
8.3.1. Using Link-Layer Acknowledgements 📡
If the MAC protocol in use gives feedback on whether a data packet was delivered successfully (like the link-layer acknowledgement frame defined by IEEE 802.11 [IEEE80211] does for unicast packets), then you don't need the DSR Acknowledgement Request and Acknowledgement options at all 🙌 If that link-layer feedback is available, it SHOULD be used instead of any other acknowledgement mechanism for Route Maintenance, and the node SHOULD NOT use either passive acknowledgements or network-layer acknowledgements for Route Maintenance.
When you're using link-layer acknowledgements for Route Maintenance, the retransmission timing and the timing for scheduling retransmission attempts are generally controlled by whichever link layer implementation the network uses 🧠 For example, in IEEE 802.11, the link-layer acknowledgement comes back after a unicast packet as part of the basic access method of the IEEE 802.11 Distributed Coordination Function (DCF) MAC protocol. The MAC protocol implementation controls when that acknowledgement is expected to arrive and when the next retransmission attempt (if needed) happens ⏱️
When a node receives a link-layer acknowledgement for any packet in its Maintenance Buffer, that node SHOULD remove that packet from its Maintenance Buffer, as well as any other packets in its Maintenance Buffer with the same next-hop destination 🧹💖
8.3.2. Using Passive Acknowledgements ✨
Okay bestie, so when link-layer acks aren't available but passive acks [JUBIN87] are, passive acks SHOULD be used for Route Maintenance whenever you're originating or forwarding a packet over any hop except the last one (the hop leading to the IP Destination Address node of the packet). 🦋 Especially if your node can switch its network interface into "promiscuous" receive mode and the links carrying data packets generally work in both directions, passive acks SHOULD totally be your move 💅
A node MUST NOT attempt to use passive acknowledgements for Route Maintenance for a packet originated or forwarded over its last hop (the hop leading to the IP Destination Address node of the packet). Why? Because the receiving node won't be forwarding the packet, so there's no passive ack for this node to overhear 🙈 Beyond that one rule, a node MAY use a bunch of different strategies for passive acks in Route Maintenance of a packet it originates or forwards. Two strategies are possible, for example:
- Each time a node receives a packet to be forwarded to a node other than the final destination (the IP Destination Address of the packet), that node sends the original transmission of that packet without requesting a network-layer acknowledgement for it. If no passive acknowledgement is received within
PassiveAckTimeoutafter this transmission, the node retransmits the packet, again without requesting a network-layer acknowledgement for it. The samePassiveAckTimeouttimeout value is used for each such attempt. If no acknowledgement has been received after a total ofTryPassiveAcksretransmissions of the packet, network-layer acknowledgements (as described in Section 8.3.3) are requested for all remaining attempts for that packet. 🔥 - Each node maintains a table of possible next-hop destination nodes, noting whether or not passive acknowledgements can typically be expected from transmission to that node, and the expected latency and jitter of a passive acknowledgement from that node. Each time a node receives a packet to be forwarded to a node other than the IP Destination Address, the node checks its table of next-hop destination nodes to determine whether to use a passive acknowledgement or a network-layer acknowledgement for that transmission to that node. The timeout for this packet can also be derived from this table. A node using this method SHOULD prefer using passive acknowledgements to network-layer acknowledgements. 👑
When a node originates or forwards a packet and uses passive acks for it, the node counts a later receipt of a new packet (for example, with promiscuous receive mode enabled on its network interface) as an acknowledgement of this first packet, but only if both of the following two tests succeed. Iykyk, it's giving strict matching energy 🧚
- The
Source Address,Destination Address,Protocol,Identification, andFragment Offsetfields in the IP header of the two packets MUST match [RFC791]. - If either packet contains a DSR Source Route header, both packets MUST contain one, and the value in the
Segments Leftfield in the DSR Source Route header of the new packet MUST be less than that in the first packet.
When a node hears such a passive acknowledgement for any packet in its Maintenance Buffer, that node SHOULD remove from its Maintenance Buffer that packet, as well as any other packets in its Maintenance Buffer with the same next-hop destination. 🫶
8.3.3. Using Network-Layer Acknowledgements 🎀
When a node originates or forwards a packet and has no other mechanism of acknowledgement available to determine reachability of the next-hop node in the source route for Route Maintenance, that node SHOULD request a network-layer acknowledgement from that next-hop node. To do so, the node inserts an Acknowledgement Request option in the DSR Options header in the packet. The Identification field in that Acknowledgement Request option MUST be set to a value unique over all packets recently transmitted by this node to the same next-hop node. 🌸
When a node receives a packet containing an Acknowledgement Request option, that node performs the following tests on the packet:
- If the indicated next-hop node address for this packet does not match any of this node's own IP addresses, then this node MUST NOT process the Acknowledgement Request option. The indicated next-hop node address is the next
Address[i]field in the DSR Source Route option in the DSR Options header in the packet, or the IP Destination Address in the packet if the packet does not contain a DSR Source Route option or theSegments Leftthere is zero. - If the packet contains an Acknowledgement option, then this node MUST NOT process the Acknowledgement Request option.
If neither of the tests above fails, then this node MUST process the Acknowledgement Request option by sending an Acknowledgement option to the previous-hop node. To do so, the node performs the following sequence of steps, bestie, so pay attention 💅
- Create a packet and set the IP
Protocolfield to the protocol number assigned for DSR (48). - Set the IP Source Address field in this packet to the IP address of this node, copied from the source route in the DSR Source Route option in that packet (or from the IP Destination Address field of the packet, if the packet does not contain a DSR Source Route option).
- Set the IP Destination Address field in this packet to the IP address of the previous-hop node, copied from the source route in the DSR Source Route option in that packet (or from the IP Source Address field of the packet, if the packet does not contain a DSR Source Route option).
- Add a DSR Options header to the packet. Set the
Next Headerfield in the DSR Options header to the value59, "No Next Header" [RFC2460]. - Add an Acknowledgement option to the DSR Options header in the packet. Set the Acknowledgement option's
Option Typefield to6and theOpt Data Lenfield to10. - Copy the
Identificationfield from the received Acknowledgement Request option into theIdentificationfield in the Acknowledgement option. - Set the
ACK Source Addressfield in the Acknowledgement option to be the IP Source Address of this new packet (set above to be the IP address of this node). - Set the
ACK Destination Addressfield in the Acknowledgement option to be the IP Destination Address of this new packet (set above to be the IP address of the previous-hop node). - Send the packet as described in Section 8.1.1.
Packets containing an Acknowledgement option SHOULD NOT be placed in the Maintenance Buffer. 🙅♀️
When a node receives a packet with both an Acknowledgement option and an Acknowledgement Request option, if that node is not the destination of the Acknowledgement option (the IP Destination Address of the packet), then the Acknowledgement Request option MUST be ignored. Otherwise (that node is the destination of the Acknowledgement option), that node MUST process the Acknowledgement Request option by returning an Acknowledgement option according to the following sequence of steps. ✨
- Create a packet and set the IP
Protocolfield to the protocol number assigned for DSR (48). - Set the IP Source Address field in this packet to the IP address of this node, copied from the source route in the DSR Source Route option in that packet (or from the IP Destination Address field of the packet, if the packet does not contain a DSR Source Route option).
- Set the IP Destination Address field in this packet to the IP address of the node originating the Acknowledgement option.
- Add a DSR Options header to the packet, and set the DSR Options header's
Next Headerfield to the value59, "No Next Header" [RFC2460]. - Add an Acknowledgement option to the DSR Options header in this packet. Set the Acknowledgement option's
Option Typefield to6and theOpt Data Lenfield to10. - Copy the
Identificationfield from the received Acknowledgement Request option into theIdentificationfield in the Acknowledgement option. - Set the
ACK Source Addressfield in the option to the IP Source Address of this new packet (set above to be the IP address of this node). - Set the
ACK Destination Addressfield in the option to the IP Destination Address of this new packet (set above to be the IP address of the node originating the Acknowledgement option). - Send the packet directly to the destination. The IP Destination Address MUST be treated as a direct neighbor node: the transmission to that node MUST be done in a single IP forwarding hop, without Route Discovery and without searching the Route Cache. In addition, this packet MUST NOT contain a DSR Acknowledgement Request, MUST NOT be retransmitted for Route Maintenance, and MUST NOT expect a link-layer acknowledgement or passive acknowledgement.
When using network-layer acknowledgements for Route Maintenance, a node SHOULD use an adaptive algorithm in determining the retransmission timeout for each transmission attempt of an acknowledgement request. For example, a node SHOULD maintain a separate round-trip time (RTT) estimate for each node to which it has recently attempted to transmit packets, and it SHOULD use this RTT estimate in setting the timeout for each retransmission attempt for Route Maintenance. The TCP RTT estimation algorithm has been shown to work well for this purpose in implementation and testbed experiments with DSR [MALTZ99b, MALTZ01]. 🦋
8.3.4. Originating a Route Error ✨
okay so this is the moment a node is like "bestie, I literally cannot reach my next hop 💀" 😭 When a node is unable to verify reachability of a next-hop node after reaching a maximum number of retransmission attempts, it SHOULD send a Route Error to the IP Source Address of the packet. When sending a Route Error for a packet containing either a Route Error option or an Acknowledgement option, a node SHOULD add these existing options to its Route Error, subject to the limit described below.
A node transmitting a Route Error MUST perform the following steps: 💅
- Create an IP packet and set the
IP Protocolfield to the protocol number assigned for DSR (48). Set theSource Addressfield in this packet's IP header to the address of this node. 🎀 - If the
Salvagefield in the DSR Source Route option in the packet triggering the Route Error is zero, then copy theSource Addressfield of the packet triggering the Route Error into theDestination Addressfield in the new packet's IP header; otherwise, copy theAddress[1]field from the DSR Source Route option of the packet triggering the Route Error into theDestination Addressfield in the new packet's IP header 🧚 - Insert a DSR Options header into the new packet. 🦋
- Add a Route Error Option to the new packet, setting the Error Type to
NODE_UNREACHABLE, the Salvage value to the Salvage value from the DSR Source Route option of the packet triggering the Route Error, and the Unreachable Node Address field to the address of the next-hop node from the original source route. Set theError Source Addressfield to this node's IP address, and theError Destinationfield to the new packet's IP Destination Address. 🔥 - If the packet triggering the Route Error contains any Route Error or Acknowledgement options, the node MAY append to its Route Error each of these options, with the following constraints: 👑
- The node MUST NOT include any Route Error option from the packet triggering the new Route Error, for which the total Salvage count (Section 6.4) of that included Route Error would be greater than
MAX_SALVAGE_COUNTin the new packet. 🙈 - If any Route Error option from the packet triggering the new Route Error is not included in the packet, the node MUST NOT include any following Route Error or Acknowledgement options from the packet triggering the new Route Error. 🫶
- Any appended options from the packet triggering the Route Error MUST follow the new Route Error in the packet. 🌸
- In appending these options to the new Route Error, the order of these options from the packet triggering the Route Error MUST be preserved. 🍓
- The node MUST NOT include any Route Error option from the packet triggering the new Route Error, for which the total Salvage count (Section 6.4) of that included Route Error would be greater than
- Send the packet as described in Section 8.1.1. 🚀
8.3.5. Processing a Received Route Error Option 🩷
when a node gets a packet with a Route Error option, that node MUST process the Route Error option according to the following sequence of steps. no skipping, periodt 💅
- The node MUST remove from its Route Cache the link from the node identified by the
Error Source Addressfield to the node identified by theUnreachable Node Addressfield (if this link is present in its Route Cache). If the node implements its Route Cache as a link cache, as described in Section 4.1, only this single link is removed; if the node implements its Route Cache as a path cache, however, all routes (paths) that use this link are either truncated before the link or removed completely. 🗑️ - If the option following the Route Error is an Acknowledgement or Route Error option sent by this node (that is, with Acknowledgement or Error Source Address equal to this node's address), copy the DSR options following the current Route Error into a new packet with IP Source Address equal to this node's own IP address and IP Destination Address equal to the Acknowledgement or Error Destination Address. Transmit this packet as described in Section 8.1.1, with the Salvage count in the DSR Source Route option set to the Salvage value of the Route Error. 💌
In addition, after processing the Route Error as described above, the node MAY initiate a new Route Discovery for any destination node for which it then has no route in its Route Cache as a result of processing this Route Error, if the node has indication that a route to that destination is needed. For example, if the node has an open TCP connection to some destination node, then if the processing of this Route Error removed the only route to that destination from this node's Route Cache, then this node MAY initiate a new Route Discovery for that destination node. Any node, however, MUST limit the rate at which it initiates new Route Discoveries for any single destination address, and any new Route Discovery initiated in this way as part of processing this Route Error MUST conform as a part of this limit. 🦋 main character rate-limiting, no cap 🧢
8.3.6. Salvaging a Packet 🛟
okay this one is so iconic 😭 When an intermediate node forwarding a packet detects through Route Maintenance that the next-hop link along the route for that packet is broken (Section 8.3), if the node has another route to the packet's IP Destination Address in its Route Cache, the node SHOULD "salvage" the packet rather than discard it. To do so using the route found in its Route Cache, this node processes the packet as follows:
- If the MAC protocol in use in the network is not capable of transmitting unicast packets over unidirectional links, as discussed in Section 3.3.1, then if this packet contains a Route Reply option, remove and discard the Route Reply option in the packet; if the DSR Options header in the packet then contains no DSR options or only a DSR Source Route Option, remove the DSR Options header from the packet. If the resulting packet then contains only an IP header (e.g., no transport layer header or payload), the node SHOULD NOT salvage the packet and instead SHOULD discard the entire packet. 🥀
- Modify the existing DSR Source Route option in the packet so that the
Address[i]fields represent the source route found in this node's Route Cache to this packet's IP Destination Address. Specifically, the node copies the hop addresses of the source route into sequentialAddress[i]fields in the DSR Source Route option, for i = 1, 2, ..., n.Address[1], here, is the address of the salvaging node itself (the first address in the source route found from this node to the IP Destination Address of the packet). The value n, here, is the number of hop addresses in this source route, excluding the destination of the packet (which is instead already represented in the Destination Address field in the packet's IP header). 🗺️ - Initialize the
Segments Leftfield in the DSR Source Route option to n as defined above. 🔢 - The First Hop External (F) bit in the DSR Source Route option MUST be set to 0. 🙅♀️
- The Last Hop External (L) bit in the DSR Source Route option is copied from the External bit flagging the last hop in the source route for the packet, as indicated in the Route Cache. 📌
- The
Salvagefield in the DSR Source Route option is set to 1 plus the value of theSalvagefield in the DSR Source Route option of the packet that caused the error. ➕ - Transmit the packet to the next-hop node on the new source route in the packet, using the forwarding procedure described in Section 8.1.5. 🚀
As described in Section 8.3.4, the node in this case also SHOULD return a Route Error to the original sender of the packet. If the node chooses to salvage the packet, it SHOULD do so after originating the Route Error. 💖
When returning any Route Reply in the case in which the MAC protocol in use in the network is not capable of transmitting unicast packets over unidirectional links, the source route used for routing the Route Reply packet MUST be obtained by reversing the sequence of hops in the Route Request packet (the source route that is then returned in the Route Reply). This restriction on returning a Route Reply and on salvaging a packet that contains a Route Reply option enables the Route Reply to test this sequence of hops for bidirectionality, preventing the Route Reply from being received by the initiator of the Route Discovery unless each of the hops over which the Route Reply is returned (and thus each of the hops in the source route being returned in the Reply) is bidirectional. 🔍 the bidirectionality check is giving detective energy 🕵️♀️
8.4. Multiple Network Interface Support 📡
A node using DSR MAY have multiple network interfaces that support DSR ad hoc network routing. This section describes special packet processing at such nodes. 🧩
A node with multiple network interfaces that support DSR ad hoc network routing MUST have some policy for determining which Route Request packets are forwarded using which network interfaces. For example, a node MAY choose to forward all Route Requests over all network interfaces. 🌈
When a node with multiple network interfaces that support DSR propagates a Route Request on a network interface other than the one on which it received the Route Request, it MUST in this special case modify the Address list in the Route Request as follows: 🪄
- Append the node's IP address for the incoming network interface. 📥
- Append the node's IP address for the outgoing network interface. 📤
When a node forwards a packet containing a source route, it MUST assume that the next-hop node is reachable on the incoming network interface, unless the next hop is the address of one of this node's network interfaces, in which case this node MUST skip over this address in the source route and process the packet in the same way as if it had just received it from that network interface, as described in Section 8.1.5. 🦋
If a node that previously had multiple network interfaces that support DSR receives a packet sent with a source route specifying a change to a network interface, as described above, that is no longer available, it MAY send a Route Error to the source of the packet without attempting to forward the packet on the incoming network interface, unless the network uses an autoconfiguration mechanism that may have allowed another node to acquire the now unused address of the unavailable network interface. 🫠
8.5. IP Fragmentation and Reassembly 🧩
When a node using DSR wishes to fragment a packet that contains a DSR header not containing a Route Request option, it MUST perform the following sequence of steps: ✂️
- Remove the DSR Options header from the packet. 🗑️
- Fragment the packet using normal IP fragmentation processing [RFC791]. However, when determining the size of each fragment to create from the original packet, the fragment size MUST be reduced by the size of the DSR Options header from the original packet. 📏
- IP-in-IP encapsulate each fragment [RFC2003]. The IP Destination address of the outer (encapsulating) packet MUST be set equal to the IP Destination address of the original packet. 📦
- Add the DSR Options header from the original packet to each resulting encapsulating packet. If a Source Route header is present in the DSR Options header, increment the
Salvagefield. ➕
When a node using the DSR protocol receives an IP-in-IP encapsulated packet destined to itself, it SHOULD decapsulate the packet [RFC2003] and then process the inner packet according to standard IP reassembly processing [RFC791]. 🎁✨
8.6. Flow State Processing ✨
okay so a node that's running the optional DSR flow state extension MUST follow these extra processing steps 💖
8.6.1. Originating a Packet 🦋
when a node is originating any packet that's gonna get routed using flow state, a node using DSR flow state MUST do the following:
- If the route to be used for this packet has never had a DSR flow state established along it (or the existing flow state has expired):
- Generate a 16-bit Flow ID larger than any unexpired Flow IDs used by this node for this destination. Odd Flow IDs MUST be chosen for "default" flows; even Flow IDs MUST be chosen for non-default flows. 🌸
- Add a DSR Options header, as described in Section 8.1.2. 🎀
- Add a DSR Flow State header, as described in Section 8.6.2. 🎀
- Initialize the Hop Count field in the DSR Flow State header to 0. 🧚
- Set the Flow ID field in the DSR Flow State header to the Flow ID generated in the first step. ✨
- Add a Timeout option to the DSR Options header. ⏰
- Add a Source Route option after the Timeout option with the route to be used, as described in Section 8.1.3. 🗺️
- The source node SHOULD record this flow in its Flow Table. 📒
- If this flow is recorded in the Flow Table, the TTL in this Flow Table entry MUST be set to be the TTL of this flow establishment packet. 💅
- If this flow is recorded in the Flow Table, the timeout in this Flow Table entry MUST be set to a value no less than the value specified in the Timeout option. 🫶
- If the route to be used for this packet has had DSR flow state established along it, but has not been established end-to-end:
- Add a DSR Options header, as described in Section 8.1.2. 🎀
- Add a DSR Flow State header, as described in Section 8.6.2. 🎀
- Initialize the Hop Count field in the DSR Flow State header to 0. 🧚
- The Flow ID field of the DSR Flow State header SHOULD be the Flow ID previously used for this route. If it is not, the steps for sending packets along never-before-established routes above MUST be followed in place of these. 🔁
- Add a Timeout option to the DSR Options header, setting the Timeout to a value not greater than the timeout remaining for this flow in the Flow Table. ⏳
- Add a Source Route option after the Timeout option with the route to be used, as described in Section 8.1.3. 🗺️
- If the IP TTL is not equal to the TTL specified in the Flow Table, the source node MUST set a flag to indicate that this flow cannot be used as default. 🚩
- If the route the node wishes to use for this packet has been established as a flow end-to-end and is not the default flow:
- Add a DSR Flow State header, as described in Section 8.6.2. 🎀
- Initialize the Hop Count field in the DSR Flow State header to 0. 🧚
- The Flow ID field of the DSR Flow State header SHOULD be set to the Flow ID previously used for this route. If it is not, the steps for sending packets along never-before-established routes above MUST be followed in place of these. 🔁
- If the next hop requires a network-layer acknowledgement for Route Maintenance, add a DSR Options header, as described in Section 8.1.2, and an Acknowledgement Request option, as described in Section 8.3.3. 📬
- A DSR Options header SHOULD NOT be added to a packet, unless it is added to carry an Acknowledgement Request option, in which case:
- A Source Route option in the DSR Options header SHOULD NOT be added. 🙈
- If a Source Route option in the DSR Options header is added, the steps for sending packets along flows not yet established end-to-end MUST be followed in place of these. 🔁
- A Timeout option SHOULD NOT be added. 🙈
- If a Timeout option is added, it MUST specify a timeout not greater than the timeout remaining for this flow in the Flow Table. ⏳
- If the route the node wishes to use for this packet has been established as a flow end-to-end and is the current default flow:
- If the IP TTL is not equal to the TTL specified in the Flow Table, the source node MUST follow the steps above for sending a packet along a non-default flow that has been established end-to-end in place of these steps. 😭
- If the next hop requires a network-layer acknowledgement for Route Maintenance, the sending node MUST add a DSR Options header and an Acknowledgement Request option, as described in Section 8.3.3. The sending node MUST NOT add any additional options to this header. 🙅♀️
- A DSR Options header SHOULD NOT be added, except as specified in the previous step. If one is added in a way inconsistent with the previous step, the source node MUST follow the steps above for sending a packet along a non-default flow that has been established end-to-end in place of these steps. 💀
8.6.2. Inserting a DSR Flow State Header 💜
a node originating a packet adds a DSR Flow State header to the packet, if necessary, to carry information needed by the routing protocol. A packet MUST NOT contain more than one DSR Flow State header. to add one, you do this exact sequence of steps:
- Insert a DSR Flow State header after the IP header and any Hop-by-Hop Options header that may already be in the packet, but before any other header that may be present. 🧁
- Set the Next Header field of the DSR Flow State header to the Next Header field of the previous header (either an IP header or a Hop-by-Hop Options header). 🍓
- Set the Flow (F) bit in the DSR Flow State header to 1. 🌈
- Set the Protocol field of the IP header to the protocol number assigned for DSR (48). 👑
8.6.3. Receiving a Packet ✨
okay bestie, this part is all about what a node does when a packet lands on it 📬🫶 This section only covers packets that are sent to this node as the next hop, meaning the MAC-layer destination address is this node's MAC address 💌 For everything else, the process described in Sections 8.6.5 should be followed 🦋
A flow counts as being in the Flow Table if the triple (IP Source Address, IP Destination Address, Flow ID) has an unexpired entry in this node's Flow Table. so it's giving "it's on the list and still fresh" 🧚✨
When a node using DSR flow state receives a packet, it MUST follow the following steps for processing: 💅🔥
- If a DSR Flow State header is present, increment the Hop Count field.
- In addition, if a DSR Flow State header is present, then if the triple
(IP Source Address, IP Destination Address, Flow ID)is in this node's Automatic Route Shortening Table and the packet is listed in the entry, then the node MAY send a gratuitous Route Reply as described in Section 4.4, subject to the rate limiting specified therein 🌸 This gratuitous Route Reply gives the route by which the packet originally reached this node. Specifically, the node sending the gratuitous Route Reply builds the route to return in the Route Reply like this 👇- Let
k = (packet Hop Count) - (table Hop Count), where packet Hop Count is the value of the Hop Count field in this received packet, and table Hop Count is the Hop Count value stored for this packet in the corresponding entry in this node's Automatic Route Shortening Table. (this is the math part, bestie 🧮) - Copy the complete source route for this flow from the corresponding entry in the node's Flow Table.
- Remove from this route the k hops immediately preceding this node in the route, since these are the hops "skipped over" by the packet as recorded in the Automatic Route Shortening Table entry. 🙈
- Let
- Process each of the DSR options within the DSR Options header in order:
- On receiving a Pad1 or PadN option, skip over the option.
- On receiving a Route Request for which this node is the destination, remove the option and return a Route Reply as specified in Section 8.2.2. 💖
- On receiving a broadcast Route Request that this node has not previously seen for which this node is not the destination, append this node's incoming interface address to the Route Request, continue propagating the Route Request as specified in Section 8.2.2, pass the payload, if any, to the network layer, and stop processing.
- On receiving a Route Request that this node has previously seen for which this node is not the destination, discard the packet and stop processing.
- On receiving any Route Request, add appropriate links to the Route Cache, as specified in Section 8.2.2. 🗺️
- On receiving a Route Reply for which this node is the initiator, remove the Route Reply from the packet and process it as specified in Section 8.2.6. 🎀
- On receiving any Route Reply, add appropriate links to the Route Cache, as specified in Section 8.2.6.
- On receiving any Route Error of type
NODE_UNREACHABLE, remove appropriate links to the Route Cache, as specified in Section 8.3.5. - On receiving a Route Error of type
NODE_UNREACHABLEthat this node is the Error Destination Address of, remove the Route Error from the packet and process it as specified in Section 8.3.5. It also MUST stop originating packets along any flows using the link from Error Source Address to Unreachable Node, and it MAY remove from its Flow Table any flows using the link from Error Source Address to Unreachable Node. this one is serious, bestie 🚨 the stop-originating part is a MUST - On receiving a Route Error of type
UNKNOWN_FLOWthat this node is not the Error Destination Address of, the node checks if the Route Error corresponds to a flow in its Flow Table. If it does not, the node silently discards the Route Error; otherwise, it forwards the packet to the expected previous hop of the corresponding flow. If Route Maintenance cannot confirm the reachability of the previous hop, the node checks if the network interface requires bidirectional links for operation. If it does, the node silently discards the Route Error; otherwise, it sends the Error as if it were originating it, as described in Section 8.1.1. 🧠 - On receiving a Route Error of type
UNKNOWN_FLOWthat this node is the Error Destination Address of, remove the Route Error from the packet and mark the flow specified by the triple (Error Destination Address, Original IP Destination Address, Flow ID) as not having been established end-to-end. 🥀 - On receiving a Route Error of type
DEFAULT_FLOW_UNKNOWNthat this node is not the Error Destination Address of, the node checks if the Route Error corresponds to a flow in its Default Flow Table. If it does not, the node silently discards the Route Error; otherwise, it forwards the packet to the expected previous hop of the corresponding flow. If Route Maintenance cannot confirm the reachability of the previous hop, the node checks if the network interface requires bidirectional links for operation. If it does, the node silently discards the Route Error; otherwise, it sends the Error as if it were originating it, as described in Section 8.1.1. - On receiving a Route Error of type
DEFAULT_FLOW_UNKNOWNthat this node is the Error Destination Address of, remove the Route Error from the packet and mark the default flow between the Error Destination Address and the Original IP Destination Address as not having been established end-to-end. - On receiving an Acknowledgement Request option, the receiving node removes the Acknowledgement Request option and replies to the previous hop with an Acknowledgement option. If the previous hop cannot be determined, the Acknowledgement Request option is discarded, and processing continues. 📩
- On receiving an Acknowledgement option, the receiving node removes the Acknowledgement option and processes it.
- On receiving any Acknowledgement option, add the appropriate link to the Route Cache, as specified in Section 8.1.4.
- On receiving any Source Route option, add appropriate links to the Route Cache, as specified in Section 8.1.4. ✨
- On receiving a Source Route option, if no DSR Flow State header is present, if the flow this packet is being sent along is in the Flow Table, or if no Timeout option preceded the Source Route option in this DSR Options header, process it as specified in Section 8.1.4. Stop processing this packet unless the last address in the Source Route option is an address of this node.
- On receiving a Source Route option in a packet with a DSR Flow State header, if the Flow ID specified in the DSR Flow State header is not in the Flow Table, add the flow to the Flow Table, setting the Timeout value to a value not greater than the Timeout field of the Timeout option in this header. If no Timeout option preceded the Source Route option in this header, the flow MUST NOT be added to the Flow Table. so no timeout, no flow. no cap, that's the rule 🫶
If the Flow ID is odd and larger than any unexpired, odd Flow IDs for this (IP Source Address, IP Destination Address), it is set to be default in the Default Flow ID Table.
Then process the Route option as specified in Section 8.1.4. Stop processing this packet unless the last address in the Source Route option is an address of this node. 🌈
- On receiving a Timeout option, check if this packet contains a DSR Flow State header. If this packet does not contain a DSR Flow State header, discard the DSR option. Otherwise, record the Timeout value in the option for future reference. The value recorded SHOULD be discarded when the node has finished processing this DSR Options header. If the flow that this packet is being sent along is in the Flow Table, it MAY set the flow to time out no more than Timeout seconds in the future. ⏰
- On receiving a Destination and Flow ID option, if the IP Destination Address is not an address of this node, forward the packet according to the Flow ID, as described in Section 8.6.4, and stop processing this packet. 🦋
- On receiving a Destination and Flow ID option, if the IP Destination Address is an address of this node, set the IP Destination Address to the New IP Destination Address specified in the option and set the Flow ID to the New Flow Identifier. Then remove the Destination and Flow ID option from the packet and continue processing. 💫
- If the IP Destination Address is an address of this node, remove the DSR Options header, if any, pass the packet up the network stack, and stop processing. 🎉
- If there is still a DSR Options header containing no options, remove the DSR Options header.
- If there is still a DSR Flow State header, forward the packet according to the Flow ID, as described in Section 8.6.4. 🚀
- If there is neither a DSR Options header nor a DSR Flow State header, but there is an entry in the Default Flow Table for the (IP Source Address, IP Destination Address) pair:
- If the IP TTL is not equal to the TTL expected in the Flow Table, insert a DSR Flow State header, setting the Hop Count equal to the Hop Count of this node, and the Flow ID equal to the default Flow ID found in the Default Flow Table, and forward this packet according to the Flow ID, as described in Section 8.6.4.
- Otherwise, follow the steps for forwarding the packet using Flow IDs described in Section 8.6.4, but taking the Flow ID to be the default Flow ID found in the Default Flow Table. 🍓
- If there is no DSR Options header and no DSR Flow State header and no default flow can be found, the node returns a Route Error of type
DEFAULT_FLOW_UNKNOWNto the IP Source Address, specifying the IP Destination Address as the Original IP Destination in the type-specific field. 💀
8.6.4. Forwarding a Packet Using Flow IDs 🧚♀️
To forward a packet using Flow IDs, a node MUST follow the following sequence of steps: 💖
- If the triple
(IP Source Address, IP Destination Address, Flow ID)is not in the Flow Table, return a Route Error of typeUNKNOWN_FLOW. 🙃 - If a network-layer acknowledgement is required for Route Maintenance for the next hop, the node MUST include an Acknowledgement Request option as specified in Section 8.3.3. If no DSR Options header is in the packet in which the Acknowledgement Request option is to be added, it MUST be included, as described in Section 8.1.2, except that it MUST be added after the DSR Flow State header, if one is present. the MUSTs are doing a lot of work in this bullet 👑
- Attempt to transmit this packet to the next hop as specified in the Flow Table, performing Route Maintenance to detect broken routes. 🦋
8.6.5. Promiscuously Receiving a Packet 👀
Okay so this part is only for packets whose MAC destinations are some other processing node 🙈. If the packet is actually addressed to you, just follow the process from Section 8.6.3, bestie 💅.
When a node using DSR flow state promiscuously overhears a packet, it SHOULD follow these steps for processing ✨:
- If the packet has a DSR Flow State header, and the triple (IP Source Address, IP Destination Address, Flow ID) is in the Flow Table, and the Hop Count is less than the Hop Count in that flow's entry, the node MAY retain the packet in the Automatic Route Shortening Table 🦋. If it can be determined that this Flow ID has been recently used, the node SHOULD retain the packet in the Automatic Route Shortening Table 🫶.
- If the packet has neither a DSR Flow State header nor a Source Route option, and a Default Flow ID can be found in the Default Flow Table for the (IP Source Address, IP Destination Address), and the IP TTL is greater than the TTL in the Flow Table for the default flow, the node MAY retain the packet in the Automatic Route Shortening Table 🌸. If it can be determined that this Flow ID has been used recently, the node SHOULD retain the packet in the Automatic Route Shortening Table 💜.
8.6.6. Operation Where the Layer below DSR Decreases the IP TTL Non-uniformly 🌈
Some nodes may use an IP tunnel as a DSR hop 🚇. If different packets sent along this IP tunnel can take different routes, the reduction in IP TTL across this link may be different for different packets. Honestly, this is where things get messy 💀. It prevents the Automatic Route Shortening and Loop Detection functionality from working properly when used in conjunction with default routes.
Nodes forwarding packets without a Source Route option onto a link with unpredictable TTL changes MUST ensure that a DSR Flow State header is present, indicating the correct Hop Count and Flow ID 🔥.
8.6.7. Salvage Interactions with DSR 🧚
Nodes salvaging packets MUST remove the DSR Flow State header, if present 🙌.
Anytime this document refers to the Salvage field in the Source Route option, packets without a Source Route option are considered to have the value zero in the Salvage field ✨.
9. Protocol Constants and Configuration Variables 👑
Any DSR implementation MUST support the following configuration variables and MUST support a mechanism enabling the value of these variables to be modified by system management 🎀. The specific variable names are used for demonstration purposes only, and an implementation is not required to use these names for the configuration variables, so long as the external behavior of the implementation is consistent with that described in this document 💖.
For each configuration variable below, the default value is specified to simplify configuration. In particular, the default values given below are chosen for a DSR network running over 2 Mbps IEEE 802.11 network interfaces using the Distributed Coordination Function (DCF) MAC protocol with RTS and CTS [IEEE80211, BROCH98] 🛜.
DiscoveryHopLimit 255 hops
BroadcastJitter 10 milliseconds
RouteCacheTimeout 300 seconds
SendBufferTimeout 30 seconds
RequestTableSize 64 nodes
RequestTableIds 16 identifiers
MaxRequestRexmt 16 retransmissions
MaxRequestPeriod 10 seconds
RequestPeriod 500 milliseconds
NonpropRequestTimeout 30 milliseconds
RexmtBufferSize 50 packets
MaintHoldoffTime 250 milliseconds
MaxMaintRexmt 2 retransmissions
TryPassiveAcks 1 attempt
PassiveAckTimeout 100 milliseconds
GratReplyHoldoff 1 secondIn addition, the following protocol constant MUST be supported by any implementation of the DSR protocol 🫶:
MAX_SALVAGE_COUNT 15 salvages10. IANA Considerations 🦋
This document specifies the DSR Options header and DSR Flow State header, for which the IP protocol number 48 has been assigned. A single IP protocol number can be used for both header types, since they can be distinguished by the Flow State Header (F) bit in each header ✨.
In addition, this document proposes use of the value "No Next Header" (originally defined for use in IPv6 [RFC2460]) within an IPv4 packet, to indicate that no further header follows a DSR Options header 💅.
Finally, this document introduces a number of DSR options for use in the DSR Options header, and additional new DSR options may be defined in the future. Each of these options requires a unique Option Type value, the most significant 3 bits (that is, Option Type & 0xE0) encoded as defined in Section 6.1. It is necessary only that each Option Type value be unique, not that they be unique in the remaining 5 bits of the value after these 3 most significant bits 🧚.
Two registries (DSR Protocol Options and DSR Protocol Route Error Types) have been created and contain the initial registrations. Assignment of new values for DSR options will be by Expert Review [RFC2434], with the authors of this document serving as the Designated Experts 👑.
11. Security Considerations 🔥
This document does not specifically address security concerns. This document does assume that all nodes participating in the DSR protocol do so in good faith and without malicious intent to corrupt the routing ability of the network 🥹.
Okay, bestie, this part is serious. Security is not optional just because the spec is cute 🚨.
Depending on the threat model, a number of different mechanisms can be used to secure DSR. For example, in an environment where node compromise is unrealistic and where all the nodes participating in the DSR protocol share a common goal that motivates their participation in the protocol, the communications between the nodes can be encrypted at the physical channel or link layer to prevent attack by outsiders. Cryptographic approaches, such as that provided by Ariadne [HU02] or Secure Routing Protocol (SRP) [PAPADIMITRATOS02], can resist stronger attacks 🔐.
Appendix A. Link-MaxLife Cache Description 📚
As guidance to implementers of DSR, the description below outlines the operation of a possible implementation of a Route Cache for DSR that has been shown to outperform other caches studied in detailed simulations. Use of this design for the Route Cache is recommended in implementations of DSR 🌟.
This cache, called "Link-MaxLife" [HU00], is a link cache, in that each individual link (hop) in the routes returned in Route Reply packets (or otherwise learned from the header of overhead packets) is added to a unified graph data structure of this node's current view of the network topology, as described in Section 4.1. To search for a route in this cache to some destination node, the sending node uses a graph search algorithm, such as the well-known Dijkstra's shortest-path algorithm, to find the current best path through the graph to the destination node 🗺️.
The Link-MaxLife form of link cache is adaptive in that each link in the cache has a timeout that is determined dynamically by the caching node according to its observed past behavior of the two nodes at the ends of the link. In addition, when selecting a route for a packet being sent to some destination, among cached routes of equal length (number of hops) to that destination, Link-MaxLife selects the route with the longest expected lifetime (highest minimum timeout of any link in the route) 🦋.
Specifically, in Link-MaxLife, a link's timeout in the Route Cache is chosen according to a "Stability Table" maintained by the caching node. Each entry in a node's Stability Table records the address of another node and a factor representing the perceived "stability" of this node. The stability of each other node in a node's Stability Table is initialized to InitStability. When a link from the Route Cache is used in routing a packet originated or salvaged by that node, the stability metric for each of the two endpoint nodes of that link is incremented by the amount of time since that link was last used, multiplied by StabilityIncrFactor (StabilityIncrFactor >= 1). When a link is observed to break and the link is thus removed from the Route Cache, the stability metric for each of the two endpoint nodes of that link is multiplied by StabilityDecrFactor (StabilityDecrFactor < 1) 🌈.
When a node adds a new link to its Route Cache, the node assigns a lifetime for that link in the Cache equal to the stability of the less "stable" of the two endpoint nodes for the link, except that a link is not allowed to be given a lifetime less than MinLifetime. When a link is used in a route chosen for a packet originated or salvaged by this node, the link's lifetime is set to be at least UseExtends into the future. If the lifetime of that link in the Route Cache is already further into the future, the lifetime remains unchanged ⏳.
When a node using Link-MaxLife selects a route from its Route Cache for a packet being originated or salvaged by this node, it selects the shortest-length route that has the longest expected lifetime (highest minimum timeout of any link in the route), as opposed to simply selecting an arbitrary route of shortest length 🏆.
The following configuration variables are used in the description of Link-MaxLife above. The specific variable names are used for demonstration purposes only, and an implementation is not required to use these names for these configuration variables. For each configuration variable below, the default value is specified to simplify configuration. In particular, the default values given below are chosen for a DSR network where nodes move at relative velocities between 12 and 25 seconds per wireless transmission radius 🏃♀️.
InitStability 25 seconds
StabilityIncrFactor 4
StabilityDecrFactor 0.5
MinLifetime 1 second
UseExtends 120 secondsAppendix B. Location of DSR in the ISO Network Reference Model 🧚
okay so bestie, when they were designing DSR they had to decide which layer of the protocol hierarchy ad hoc network routing should live in 🦋 they seriously considered two options: routing at the link layer (ISO layer 2) and routing at the network layer (ISO layer 3). they originally went with the link layer, and honestly the reasons are iconic 💅
- pragmatically, running DSR at the link layer maximizes the number of mobile nodes that can join ad hoc networks 📱 it can route just as happily between IPv4 [RFC791], IPv6 [RFC2460], and IPX [TURNER90] nodes. no one gets left out 🫶
- historically [JOHNSON94, JOHNSON96a], DSR grew out of them daydreaming about a multi-hop, propagating version of the Internet's Address Resolution Protocol (ARP) [RFC826], plus the routing mechanism used in IEEE 802 source routing bridges [PERLMAN92]. both of those are layer 2 protocols, so it's giving layer 2 origin story 🌸
- technically, DSR was designed to be simple enough to be implemented directly in the firmware inside wireless network interface cards [JOHNSON94, JOHNSON96a], way down below the layer 3 software in a mobile node 🔥 they saw huge potential here for DSR running inside a cloud of mobile nodes around a fixed base station, where DSR would quietly extend the coverage range out to those nodes 🌈 mobile nodes that otherwise couldn't reach the base station because of things like distance, fading, or local interference sources could still get there through their peers. the peers become the bridge, and that's so main character of them ✨
ultimately, though, they decided to specify and implement [MALTZ99b] DSR as a layer 3 protocol 💖 why? because layer 3 is the only layer where they could realistically support nodes with multiple network interfaces of different types forming an ad hoc network. the layer 2 dream had to take a backseat 🥲
Appendix C. Implementation and Evaluation Status 🍓
so the initial design of DSR, including its basic Route Discovery and Route Maintenance mechanisms, was first published in December 1994 [JOHNSON94] 🎀 then significant additional design details and initial simulation results dropped in early 1996 [JOHNSON96a] 💜
after that, DSR got studied to death (in the best way) through more detailed simulations 🤓 they implemented DSR in the ns-2 network simulator [NS-2, BROCH98] and ran extensive ns-2 simulations of DSR (e.g., [BROCH98, MALTZ99a]). they also evaluated the different caching strategies in this document [HU00] ✨
they implemented DSR under the FreeBSD 2.2.7 operating system running on Intel x86 platforms too 💻 FreeBSD [FREEBSD] is built on a bunch of free software, including 4.4 BSD Lite from the University of California, Berkeley. for the environments they used it in, this implementation is functionally equivalent to the version of DSR specified in this document 🫶
during the 7 months from August 1998 to February 1999, they designed and built a full-scale physical testbed to evaluate ad hoc network performance in the field 🌍 it was an actively mobile ad hoc network running under realistic communication workloads, and the whole thing is giving serious research energy 🔥 the last week of February and first week of March 1999 featured demos of the testbed for a bunch of sponsors and partners, including Lucent Technologies, Bell Atlantic, and the Defense Advanced Research Projects Agency (DARPA) 👑 a complete description of the testbed is available [MALTZ99b, MALTZ00, MALTZ01].
then they ported this implementation to FreeBSD 3.3 🦋 and added a preliminary version of Quality of Service (QoS) support for DSR 💅 a demo of this modified version was presented in July 2000. these QoS features are NOT included in this document. they'll be added later in a separate document on top of the base protocol specified here 👀
DSR has also been implemented under Linux by Alex Song at the University of Queensland, Australia [SONG01] 🐧 that version supports the Intel x86 PC platform and the Compaq iPAQ 📱
the Network and Telecommunications Research Group at Trinity College, Dublin, has implemented a version of DSR on Windows CE 🪟
Microsoft Research implemented a version of DSR on Windows XP and used it in testbeds of over 15 nodes 🌈 several machines use that implementation as their primary means of accessing the Internet. bestie, that's a real-life, everyday-use situation 😭
several other independent groups have also used DSR as a platform for their own research, or as a basis of comparison between ad hoc network routing protocols 🧠
a preliminary version of the optional DSR flow state extension was implemented in FreeBSD 3.3 🌸 a demo of this modified version was presented in July 2000. the DSR flow state extension has also been extensively evaluated using simulation [HU01] 💖
Acknowledgements 🫶
the protocol described in this document was designed and developed within the Monarch Project, a long-term research project at Rice University (previously at Carnegie Mellon University) 🎓 it's developing adaptive networking protocols and protocol interfaces to allow truly seamless wireless and mobile node networking [JOHNSON96b, MONARCH] ✨
the authors want to acknowledge the substantial contributions of Josh Broch in helping to design, simulate, and implement the DSR protocol. thank you for everything, Josh 💜 they also thank him for his contributions to earlier versions of this document.
they'd also like to acknowledge Robert V. Barron at Carnegie Mellon University for his help. Bob ported the DSR implementation from FreeBSD 2.2.7 into FreeBSD 3.3 👑
many valuable suggestions came from participants in the IETF process 🌟 they particularly want to acknowledge Fred Baker, who gave extensive feedback on a previous version of this document 🙌 and the working group chairs, for their suggestions on previous versions of the document too 💅
Normative References 📚
[RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.
[RFC792] Postel, J., "Internet Control Message Protocol", STD 5, RFC 792, September 1981.
[RFC826] Plummer, David C., "Ethernet Address Resolution Protocol: Or converting network protocol addresses to 48.bit Ethernet address for transmission on Ethernet hardware", STD 37, RFC 826, November 1982.
[RFC1122] Braden, R., "Requirements for Internet Hosts - Communication Layers", STD 3, RFC 1122, October 1989.
[RFC1700] Reynolds, J. and J. Postel, "Assigned Numbers", STD 2, RFC 1700, October 1994. See also http://www.iana.org/numbers.html.
[RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, October 1996. RFC 2003, October 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
Informative References ✨
okay so here's the big reading list, bestie 📚🧚 every one of these is a real source the spec leans on, so they all stay.
- [BANTZ94] David F. Bantz and Frederic J. Bauchot. Wireless LAN Design Alternatives. IEEE Network, 8(2):43-53, March/April 1994.
- [BHARGHAVAN94] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia Zhang. MACAW: A Media Access Protocol for Wireless LAN's. In Proceedings of the ACM SIGCOMM '94 Conference, pages 212-225. ACM, August 1994.
- [BROCH98] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pages 85-97. ACM/IEEE, October 1998.
- [CLARK88] David D. Clark. The Design Philosophy of the DARPA Internet Protocols. In Proceedings of the ACM SIGCOMM '88 Conference, pages 106-114. ACM, August 1988.
- [FREEBSD] The FreeBSD Project. Project web page available at
http://www.freebsd.org/. - [HU00] Yih-Chun Hu and David B. Johnson. Caching Strategies in On-Demand Routing Protocols for Wireless Ad Hoc Networks. In Proceedings of the Sixth Annual ACM International Conference on Mobile Computing and Networking. ACM, August 2000.
- [HU01] Yih-Chun Hu and David B. Johnson. Implicit Source Routing in On-Demand Ad Hoc Network Routing. In Proceedings of the Second Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), pages 1-10, October 2001.
- [HU02] Yih-Chun Hu, Adrian Perrig, and David B. Johnson. Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks. In Proceedings of the Eighth Annual International Conference on Mobile Computing and Networking (MobiCom 2002), pages 12-23, September 2002.
- [IEEE80211] IEEE Computer Society LAN MAN Standards Committee. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std 802.11-1997. The Institute of Electrical and Electronics Engineers, New York, New York, 1997.
- [JOHANSSON99] Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, and Mikael Degermark. Scenario-based Performance Analysis of Routing Protocols for Mobile Ad-hoc Networks. In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pages 195-206. ACM/IEEE, August 1999.
- [JOHNSON94] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158-163. IEEE Computer Society, December 1994.
- [JOHNSON96a] David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
- [JOHNSON96b] David B. Johnson and David A. Maltz. Protocols for Adaptive Wireless and Mobile Networking. IEEE Personal Communications, 3(1):34-42, February 1996.
- [JUBIN87] John Jubin and Janet D. Tornow. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 75(1):21-32, January 1987.
- [KARN90] Phil Karn. MACA---A New Channel Access Method for Packet Radio. In ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pages 134-140. American Radio Relay League, September 1990.
- [LAUER95] Gregory S. Lauer. Packet-Radio Routing. In Routing in Communications Networks, edited by Martha E. Steenstrup, chapter 11, pages 351-396. Prentice-Hall, Englewood Cliffs, New Jersey, 1995.
- [MALTZ99a] David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. Johnson. The Effects of On-Demand Behavior in Routing Protocols for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on Selected Areas of Communications, 17(8):1439-1453, August 1999.
- [MALTZ99b] David A. Maltz, Josh Broch, and David B. Johnson. Experiences Designing and Building a Multi-Hop Wireless Ad Hoc Network Testbed. Technical Report CMU-CS-99-116, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, March 1999.
- [MALTZ00] David A. Maltz, Josh Broch, and David B. Johnson. Quantitative Lessons From a Full-Scale Multi-Hop Wireless Ad Hoc Network Testbed. In Proceedings of the IEEE Wireless Communications and Networking Conference. IEEE, September 2000.
- [MALTZ01] David A. Maltz, Josh Broch, and David B. Johnson. Lessons From a Full-Scale MultiHop Wireless Ad Hoc Network Testbed. IEEE Personal Communications, 8(1):8-15, February 2001.
- [MONARCH] Rice University Monarch Project. Monarch Project Home Page. Available at
http://www.monarch.cs.rice.edu/. - [NS-2] The Network Simulator -- ns-2. Project web page available at
http://www.isi.edu/nsnam/ns/. - [PAPADIMITRATOS02] Panagiotis Papadimitratos and Zygmunt J. Haas. Secure Routing for Mobile Ad Hoc Networks. In SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), January 2002.
- [PERLMAN92] Radia Perlman. Interconnections: Bridges and Routers. Addison-Wesley, Reading, Massachusetts, 1992.
- [RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.
- [RFC2131] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, March 1997.
- [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998.
- [SONG01] Alex Song. picoNet II: A Wireless Ad Hoc Network for Mobile Handheld Devices. Submitted for the degree of Bachelor of Engineering (Honours) in the division of Electrical Engineering, Department of Information Technology and Electrical Engineering, University of Queensland, Australia, October 2001. Available at
http://piconet.sourceforge.net/thesis/index.html. - [TURNER90] Paul Turner. NetWare Communications Processes. NetWare Application Notes, Novell Research, pages 25-91, September 1990.
- [WRIGHT95] Gary R. Wright and W. Richard Stevens. TCP/IP Illustrated, Volume 2: The Implementation. Addison-Wesley, Reading, Massachusetts, 1995.
Authors' Addresses 🎀
these are the humans who built it, so here's where you can find them 💖
David B. Johnson
Rice University
Computer Science Department, MS 132
6100 Main Street
Houston, TX 77005-1892
USA
Phone: +1 713 348-3063
Fax: +1 713 348-5930
EMail: dbj@cs.rice.edu
David A. Maltz
Microsoft Research
One Microsoft Way
Redmond, WA 98052
USA
Phone: +1 425 706-7785
Fax: +1 425 936-7329
EMail: dmaltz@microsoft.com
Yih-Chun Hu
University of Illinois at Urbana-Champaign
Coordinated Science Lab
1308 West Main St, MC 228
Urbana, IL 61801
USA
Phone: +1 217 333-4220
EMail: yihchun@uiuc.eduFull Copyright Statement 💅
so the legal bit: the IETF Trust holds the copyright for 2007 🔥
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
Intellectual Property 🦋
the IETF doesn't say whether any patents or rights around this tech are valid or how wide they reach, and it doesn't claim to have checked for any either 🙈 the IETF takes no position on the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or on whether any license under such rights might or might not be available, and it makes no representation that it has made any independent effort to identify any such rights. Info on how rights work for RFC documents lives in BCP 78 and BCP 79.
copies of IPR disclosures sent to the IETF Secretariat, any assurances of licenses that will be available, and the results of any attempt to get a general license or permission to use these proprietary rights for implementers or users of this spec can be found in the IETF's online IPR repository at http://www.ietf.org/ipr.
the IETF also invites anyone to flag any copyrights, patents, patent applications, or other proprietary rights that might cover technology needed to implement this standard. send that info to the IETF at ietf-ipr@ietf.org 💜
Acknowledgement 🫶
the RFC Editor function is currently funded by the Internet Society 🌈
📦 where this page comes from
- ietf: rfc4728 2007-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms