All-IP Routing Protocols

All-IP Routing Protocols
Many of the fundamental characteristics of wired routing protocols can be found in all-IP routing
protocols as well: they use routing tables and metrics to determine optimal paths for packets to travel,
strive for simplicity and low overhead costs, endeavor to be robust and stable, and have some built-in
flexibility for reacting to network changes and problems. However, wireless routing protocols must
also take into consideration certain concerns that are specific to a wireless environment: they must be
even more adaptable to changes in the network topology (moving nodes can find that their shortest
paths to other moving nodes change dramatically), strive even harder to maximize throughput and
minimize delay, and keep the power consumption level of the network as low as possible (since
mobile nodes are typically run off battery power) [525].
Two well-known wired routing protocols are the Routing Information Protocol (RIP) and the
Open Shortest Path First protocol (OSPF). Each has corresponding wireless counterparts: Ad hoc
On-demand Distance Vector (AODV) routing can be thought of as RIP for wireless networks, and
both Dynamic Source Routing (DSR) and the Zone Routing Protocol (ZRP) are roughly analogous
to the OSPF. All of the ideas that have been proposed for wireless routing protocols can be found
within AODV, DSR, and ZRP (when taken as a whole). The Distance-Vector family of protocols
(which includes the Destination-Sequenced Distance Vector Routing protocol) is proactive. AODV
and DSR are reactive protocols, whereas ZRP takes a hybrid approach.
AODV can handle both unicast and multicast routing. As its name implies, it was designed for
use in ad hoc mobile networks and is an on-demand protocol that only constructs routes from source
to destination at the request of a transmitting node. This is done using route request queries and route
reply responses. When a transmitting node does not already have a route to a particular destination, it
broadcasts a route request (RREQ) across the network. When nodes receive this request they update
their information about the transmitting node, create backwards pointers to it in their route tables,
and, if they are not the destination node and have not already established a route to the destination,
rebroadcast the RREQ. If a node is the destination or has already established a route to the destination,
it sends a route reply (RREP) back to the transmitting source node – via any intermediary node that
had forwarded the RREQ. As the RREP returns to the source, the intermediary nodes create forward
pointers to the destination node. When the source node receives the RREP it can begin to transmit
data to the destination node. Such routes are maintained as long as they are “active,” that is, as long
as data packets are using the route within a set timeout period. If the route times out or a link in
the route breaks, the sending node can reinitiate route discovery. Breaks in routes are reported to the
source node in route error (RERR) messages when intermediary nodes perceive them [526].
AODV is the on-demand counterpart to table-based Dynamic State Routing DSDV wireless
routing [526].
DSR is also an on-demand routing protocol, but, unlike the AODV, it does not use hop-by-hop
routing. Instead, it employs packet headers that carry an ordered list of the nodes that constitute
the route from source to destination. With DSR, intermediary nodes do not need to maintain route
information about the various routes that they are a part of (although they do store the routes that
they themselves have established when acting as a transmitting source). To discover a needed route, a
transmitting source node broadcasts a ROUTE REQUEST packet to neighboring nodes. Only nodes
that have not yet seen this ROUTE REQUEST forward it, and when they do so, they update the header
with their own address (in the proper sequence). When either the destination node or a node which has
already established a route to the destination receives the packet, it responds with a ROUTE REPLY with the sequence of nodes in the route taken from the ROUTE REQUEST header. If a route breaks
and the source node learns that its messages are not reaching their destination, route discovery is
reinitiated. DSR does not make use of periodic transmissions of routing information and therefore
nodes consume less power than in other protocols. However, the large headers employed by DSR
make it most efficient in networks of small diameter [525].
ZRP combines the advantages of the proactive (table-driven) protocols like OSPF and the reactive
(on-demand) protocols like DSR and AODV into a hybrid routing protocol for ad hoc wireless
networks. Purely proactive routing works best for networks with a high call rate, and purely reactive
routing works best for networks with high node mobility. The hybrid ZRP is designed to work well
in a network with both of these characteristics; that is, in a network with mobile nodes that frequently
transmit data [528].
ZRP divides a network’s map into zones, roughly centered on individual nodes or small clusters
of nodes. These zones may overlap. The zone radius is an important property for the performance
of ZRP. If a zone radius of one hop is used, routing is purely reactive and broadcasting degenerates
into flood searching. If the radius approaches infinity, routing is reactive. The selection of radius is a
trade-off between the routing efficiency of proactive routing and the increasing traffic for maintaining
the view of the zone [529]. The design of ZRP assumes that the largest part of the traffic is directed
to nearby nodes in an ad hoc network. Therefore, ZRP reduces the proactive scope to a zone centered
on each node. In a limited zone, the proactive maintenance of routing information is easier. Further,
the amount of routing information that is never used is minimized. Still, nodes farther away can be
reached with reactive routing. Since all nodes proactively store local routing information, RREQs
can be more efficiently performed without querying all the network nodes. ZRP refers to the locally
proactive routing component as the Intrazone Routing Protocol (IARP). The globally reactive routing
component is named the Interzone Routing Protocol (IERP) [529]. These are not specific, rigidly
defined protocols because ZRP provides only a framework within which any of a number of welldefined
protocols can be implemented, depending on the circumstances. In order to learn about
its direct neighbors, a node may use the MAC protocols directly. Alternatively, it may require a
Neighbor Discovery Protocol (NDP). Such a NDP typically relies on the transmission of “hello”
beacons by each node. If a node receives a response to such a message, it may note that it has
a direct point-to-point connection with this neighbor. The NDP is free to select nodes on various
criteria, such as signal strength or frequency/delay of beacons. Once the local routing information
has been collected, the node periodically broadcasts discovery messages in order to keep its map of
neighbors up to date.
Communication between the different zones is controlled by the IERP and provides routing
capabilities among peripheral nodes (nodes on the periphery of a zone) only. If a node encounters
a packet with a destination outside its own zone, that is, it does not have a valid route for this
packet, it forwards it to its peripheral nodes, which maintain routing information for the neighboring
zones, so that they can make a decision of where to forward the packet. Through the use of a
bordercast algorithm rather than flooding all peripheral nodes, these queries become more efficient
[527].
Instead of broadcasting packets, ZRP uses a concept called bordercasting, which utilizes the
topology information provided by IARP to direct query request to the border of the zone. The
bordercast packet delivery service is provided by the Bordercast Resolution Protocol (BRP). BRP
uses a map of an extended routing zone to construct bordercast trees for the query packets. Figure 5.4
shows the relationships between the various protocols of ZRP.
Route maintenance is especially important in ad hoc networks, where links are broken and established
as nodes with limited radio coverage move. In purely reactive routing protocols, when routes
containing broken links fail, a new route discovery or route repair must be performed. Until the new
route is available, packets are dropped or delayed. In ZRP, the knowledge of the local topology can
be used for route maintenance. Link failures and suboptimal route segments within one zone can
be bypassed. Incoming packets can be directed around the broken link through an active multihop path. Similarly, the topology can be used to shorten routes; for example, when two nodes have moved
within each other’s radio coverage. For source-routed packets, a relaying node can determine the closest
route to the destination that is also a neighbor. Sometimes, a multihop segment can be replaced
by a single hop. If next-hop forwarding is used, the nodes can make locally optimal decisions by
selecting a shorter path [529].