Nowadays there are various routing protocols proposed for the MANET. The most popular ones are DSDV (Destination-Sequenced Distance Vector), TORA (Temporally-Ordered Routing Algorithm), DSR (Dynamic Source Routing) and AODV (Ad-hoc On Demand Distance Vector). These routing protocols can be categorized in different routing operation modes.
2.1.1 Mode of Routing Operations
Proactive vs. Reactive
These two modes concern whether or not nodes in an ad hoc network should keep track of routes to all possible destinations, or instead keep track of only those destinations of immediate interest [8].
Proactive protocols store route information even before it is needed. This kind of protocols has advantage that communications with arbitrary destination experience minimal delay. However it also suffers from the disadvantage that additional control traffic is needed to continually update stale route information. This could significantly increase routing overhead especially for the MANET where the links are often broken.
Reactive protocols, on the contrary, acquire routing information only when it is actually needed. However, the latency of the communication increases tremendously especially when a node communicates to another at the first time.
Source routing vs. Hop-by-hop routing
These two modes concern whether the source node decides the route for a packet to be forwarded to the destination or the intermediate nodes are allowed to decide the next hop until the packet arrives at the destination.
In the source routing protocols, the source node decides the route and puts the route information in the packet header. All the intermediate nodes forward the packet along the route faithfully. This kind of protocols has advantage that the intermediate nodes are not required to maintain the routing information. But it suffers from the disadvantage that the packet size grows because of source routing information carried in each packet.
In the hop-by-hop routing protocols, it is sufficient for the source to know only how to get to the “next hop” and intermediate nodes find their own next-hops until the destination. In contrast to source routing protocols, hop-by-hop routing protocols do not increase packet size but they requires all the intermediate nodes to maintain routing information.
Table 2-1 shows the classification of the routing protocols into the four operation modes we have introduced.
Reactive Proactive
Source routing DSR
Hop-by-hop routing TORA, AODV DSDV
Table 2-1 Categories of routing protocols
Josh Broch et al. has compared the performance of these four routing protocols [11]. The results show that DSR has best throughput performance (above 95%) at all mobility rates and movement speeds. Thus we will use DSR as basic routing protocol in this thesis.
2.1.2 The Dynamic Source Routing Protocol (DSR)
John et al. proposed the dynamic source routing protocol (DSR) [1] which is a routing protocol for use in multi-hop wireless ad hoc networks of mobile nodes. DSR is an on-demand protocol, in which route are only discovered when data need to be transmitted to a node where no route has yet been discovered. The advantage of this on-demand routing protocol is that there are not any periodic routing advertisement and reducing the routing overhead. DSR is also a source routing protocol, allowing multiple routes to any destination and allows each sender to select and control the routes used in routing the packets.
DSR is composed of the two main mechanisms: “Route Discovery” and “Route Maintenance” which are explained below.
2.1 Mobile Ad Hoc Network Routing Protocols 7
Route Discovery
Route Discovery aims at finding routes from a source node to destination. Figure 2-1 illustrates the procedure of Route Discovery. When a source node S wants to send a data packet to some destination node D, it first searches its route cache to find whether there is a route to D. If there is no route to D, then S will initiate a Route Discovery and send out Route Request message which is propagated to all the nodes within its transmission range.
At the mean time, it saves the data packet in its send buffer. The Route Request message contains the addresses of source node and destination node, a unique route request identifier and a route record which records all the intermediate nodes that this route request packet has traveled through. S appends itself to the beginning of the route record when it initiates the message.
S A B D
Route Request S
Route Request S, A
Route Request S, A, B Route Reply
S, A, B, D
Figure 2-1 Route Discovery
When a node receives the Route Request message, it compares the destination address in the message with its own address to judge whether itself is the destination node. If it is not, it will append its own address in the route record and propagate the message to other nodes.
If the node is the destination node, it will send a Route Reply message to the source node and the message contains the source route record which is accumulated when the Route Request message is forwarded along its way to the destination. When the destination sends the Route Reply, if it uses MAC protocols such as IEEE 802.11 that require a bidirectional link, it just reverse the source route record and use it as route to send Route Reply to the source node. Otherwise it should find the route by searching its route cache or sending out a Route Request which piggybacks the Route Reply for the source node.
When the source node receives the Route Reply message, it puts the returned route into its route cache. From then on all the packets destined to the same destination will use this route until it is broken.
Route Maintenance
Since the ad hoc network is dynamic and the topology of the network changes frequently, the existing routes maintained by nodes in their route cache are often broken. After forwarding a packet, a node must attempt to confirm the reachability of the next-hop node. If the node does not receive any confirmation from the next hop during a certain period of time, it will retransmit the packet. If after a maximum number of retransmission
it still does not receive any confirmation, it will think the link to the next hop is broken and will send a Route Error message to the source node.
DSR proposes three acknowledge mechanisms to confirm that data can flow over the link from that node to the next hop:
Link-layer acknowledgement which is provided by MAC layer protocol such as IEEE 802.11.
Passive acknowledgement in which a node hears the next-hop node forwarding the packet and thus confirms the reachability of the link.
Network-layer acknowledgement in which a node sends an explicit acknowledgement request to its next-hop node.
Passive Acknowledgement
Passive Acknowledgement (PACK) is important in CONFIDANT protocol because it is used to detect whether the next hop forwards the packet or drops it. We explain it in detail in this section.
Passive acknowledgement is used with the assumption that:
Network links operates bi- directionally.
The network interface is in the “promiscuous mode”.
When a node taps a new packet in “promiscuous mode” after it originates or forwards a packet, it consider it as an acknowledgement of the first packet if both of following check success [1]:
The Source Address, Destination Address, Protocol, Identification, and Fragment Offset fields in the IP header of the two packets MUST match.
If either packet contains a DSR Source Route header, both packets MUST contain one, and the value in the Segments Left field in the DSR Source Route header of the new packet MUST be less than that in the first packet.
If no matched packet is found during PACK timeout, the node will consider the link between the next hop and itself is broken and will send Route Error message to the source node.
Additional features
DSR has additional features such as replying to route requests using cached routes, caching overheard routing information, packet salvaging and flow state extension and etc.
We will introduce them in section 4.1 and discuss how they will impact the performance of network, how they will interact with CONFIDANT and whether they will be enabled in our simulation.