3 On-demand routing protocols

On-demand routing protocols do not try to keep their routing tables up-to-date. Instead, a node tries to find a route only when it wants to send a packet. This reduces the traffic needed for routing, but introduces a delay when the first packet is sent to a host.

3.1 Ad-hoc On-demand Distance Vector protocol

AODV, as proposed in [RFC3561] floods route request packets throughout the network to discover a certain host. Although all hosts in the network cache the information in all routing packets, flooding the network to find a host is a resource-intensive process. When the route to a non-existing host is requested, all nodes in the network get a route request packet.

AODV may be useful in networks where there is little traffic, or where connections are relatively static. In a large network where the topology and the connections between hosts change often, AODV induces too much overhead and a long delay before the connection is established.

3.2 Dynamic Source Routing

DSR ([Joh04]) uses source routing, which means that a complete, ordered route is carried in each packet. This makes it easy to control the route from the source node and guarantees loop-free paths.

A node can discover a path to another node by sending a route discovery packet. The node locally broadcasts this packet. Each neighbour appends its own address to a list in the packet and broadcasts it. When it reaches the destination node, a complete path from the source to the destination is available in the packet. The destination node returns this route discovery packet by sending it over the reverse path.

DSR
Figure 3: Route discovery in DSR

At this point, a path between sender and reciever is established. DSR proposes that all nodes cache information in route discovery packets, so that a route discovery is not always needed.

When a part of the link goes down, the node before the broken link informs each node which tries to route packets over the broken link. For example, if the link between C and D in fig. 3 goes down, C will send a route error packet to A. Because B overhears this packet, it will also remove the path through C from its cache.

In the [Joh04], the network size is assumed to be no larger than 200 nodes, with a network diameter of 5 to 10. Bigger networks are not feasible, because flooding is used to discover routes. When network topology changes and new connections are made, the network may collapse under the load of the routing packets.