Marja-Leena Lehmus
Electrical Engineering
Helsinki University of Technology
marja-leena.lehmus@sonera.com
3 Mechanisms of routing protocols
3.1 Conventional routing protocols
4 Evaluation of ad hoc protocol
5 Description of two manet protocols
5.1 Ad hoc on demand distance vector (AODV) protocol
5.2 Source Tree Adaptive Routing (STAR) Protocol
Mobile ad hoc networking (manet) was first seen as a vital application in military environment. Nowadays also other industrial and commercial applications for manet are identified. Examples of these are moving vehicles (e.g. aeroplanes), areas without network coverage and emergency situations. In the future also the developing technology of 'wearable' computing and communication may provide applications for manet technology. The manet networks may operate in isolation or have gateways to and interface with a fixed network. Thus mesh-based mobile networks can provide robust and inexpensive alternatives or enhancements to cell-based mobile network infrastructures.
There is a current and future need of dynamic ad hoc networking technology. The emerging field of mobile and nomadic computing is currently emphasising on mobile IP operation, but also highly-adaptive mobile networking technology is required to effectively manage multihop, ad hoc network clusters which can operate autonomously or, more than likely, be attached at some point(s) to fixed Internet.
The goal of manet, to extend the mobility into the realm of autonomous mobile wireless domains, is accomplished by incorporating routing functionality into mobile nodes, so that the nodes are capable of acting both as routers and hosts. The work to standardise the routing capability in this environment is done in Mobile Ad hoc Networking (MANET), which is a working group of IETF. Several routing protocols for ad hoc networks are introduced and specified by this group as Internet Drafts.
This paper describes the requirements of manet protocols. Two manet protocols are introduced and analysed how the manet requirements are fulfilled in these protocols. The paper starts by presenting the special characteristics of manet networks, which set the underlying assumptions and performance concerns for protocol design. The dynamic and wireless environment of manet networks set demands for the manet protocols that do not need to be considered in normal fixed Internet routing protocols.
Chapter 3 contains an introduction to the principle mechanisms of routing protocols. Distance vector and link state algorithms are introduced likewise the table-driven and on-demand algorithms.
Chapter 4 takes a look at the metrics to evaluate the performance of a manet protocol and presents arguments that have been stated how a specific protocol supports these metrics.
Chapter 5 describes two ad hoc routing protocols - AODV [2] and STAR
[3] - which are based on different routing mechanisms. AODV (Ad hoc on-demand
distance vector) is, as already stated in the name, an on-demand protocol
using distance vector, while STAR (Source Tree Adaptive Routing) is a table-driven
protocol, which exploits link-state information. The implementation of
the characteristics described in chapter 4 are reviewed in these two protocols.
The dynamic topology is caused from the freedom of nodes to move arbitrarily. Thus the network topology may change randomly and rapidly at unpredictable times, and may consist of both bidirectional and unidirectional links.
The bandwidth-constrained links are caused by the limits of the air interface. Furthermore, fading, noise and other interference at the air interface decrease the limited capacity available at the allocated frequency rate. The capacity limitation problem will never completely be overcome since while the transmission speed on the air interface is slowly increasing, the capacity demands of multimedia transmission increases faster.
The third characteristic, energy-constrained operation, is an essential issue in manet network where most, if not all, nodes rely on batteries. For such nodes energy conservation is a critical system design aspect.
The last characteristic, limited security, is a consequence from the fact that mobile networks in general are more vulnerable to eavesdropping, spoofing and denial-of-service attacks than fixed-cable networks. These characteristics create the set of additional underlying assumptions and performance concerns that need to be taken into account during the design of routing protocols for wireless ad hoc networks compared to the routing protocols in fixed-cable networks.
In addition to these four characteristics some networks may be relatively
large. The need for scalability is not unique to manets. However, in light
of the preceding characteristics, the mechanisms required to achieve scalability
likely are.
In distance vector routing each router contains in the routing table the distance to all available routers, where the distance is measured in hops. The table is formed by computing the shortest path to each host from the information received from the other routers broadcasting messages. The messages are sent by request, periodically every 30 seconds and additionally each time there is change of metric in the routing table.
The disadvantage of RIP is the long time required to stabilise after a failure of a router or a link. The time is measured in minutes. During this settling time routing loops can occur.
In a link-state protocol router does not exchange the distances with is neighbours, instead a network topology information is used to make routing decisions. Each router actively tests the status of its link to each of its neighbours and sends this information to its other neighbours, which then propagate it throughout the autonomous system. Each router takes this information and builds a complete routing table.
There are several advantages in OSPF compared to RIP. For example OSPF
can calculate a separate set of routes for each IP-type of service, which
means that there can be multiple routing table entries, one for each IP
type-of-service. Additionally a link-state protocol stabilises always quicker
than distance vector protocol after a failure of router or a link.
In an on-demand routing protocol, routers maintain routing information for only those destinations that they need to contact as a source or relay of information. The basic approach consists of allowing a router that does not know how to reach a destination to send a flood-search message to obtain the path information it needs. An example of on-demand ad hoc routing protocol is AODV (Ad Hoc on-demand distance vector) protocol, which is introduced in chapter 5. On-demand routing protocols differ on the specific mechanisms used to disseminate flood-search packets and their responses, cache the information heard from other nodes' searches, determine the cost of a link, and determine the existence of a neighbour.
In a table-driven algorithm, each router maintains path information
for each known destination in the network and updates its routing- table
entries as needed. An example of table-driven ad hoc routing protocol is
STAR (Source Tree Adaptive Routing protocol) protocol, which is also introduced
in chapter 5.
The most straightforward and comparable metrics to measure the performance of a protocol are the quantitative metrics. These include e.g. end-to-end data throughput and delay, route acquisition time, percentage out of order delivery and efficiency. Such measurements are done to all protocols at some point of protocol design and thus comparison of the results between different protocols is easy. Good comparisons of different protocols based on they quantitative metrics simulation environments can be found in documents [6] and [7]. All separate measurement results of different protocols are not however comparable since the networking context may vary in the measurements. Essential parameters that should be noted in the performance measurements of protocols are e.g. network size, network connectivity, topological rate of change, link capacity, fraction of unidirectional links, traffic patterns, mobility and fraction and frequency of sleeping nodes.
Other clear metrics to measure the ad hoc network protocol performances is to evaluate the qualitative properties of the protocols. Properties that all ad hoc network protocols should have include distributed operation, loop-freedom, demand-based operation, proactive operation, security, sleep period operation, unidirectional link support and they should be free from the counting to infinity problem. These properties are already more difficult to measure. To be able to truly verify properties like loop freedom and counting to infinity one would need a thorough or even formal description on the protocol. However, the effect to protocols that these two properties and some others mentioned earlier have is analysed in higher level in the following.
Routing loops and counting to infinity are seen by some parties [5] as the most demanding problem needed to be solved in the ad hoc network protocols. A routing table loop [5] is a path specified in the nodes routing tables at a particular point in time, such that the path visits the same node more than once before reaching the intended destination. A node counts to infinity [5] when it increments its distance to a destination until it reaches a predefined maximum distance value. These problems have been tried to solve a number of times e.g. by increasing the amount of information exchanged among nodes, or by making nodes to hold down the updating of their routing tables for some period on time after detecting distance increases. However, these approaches do not solve these problems satisfactorily since at the same time they increase the control data on the limited bandwidth, which decreases the overall efficiency of the network. It should be noted that link-state algorithms are free from the counting to infinity problem, but they do not, however, eliminate the creation of temporary routing loops. Whether link states or distance vectors are used, the existence of routing table loops, even temporarily, is a detriment to the overall performance of an internet.
While the overall performance of the network can be increased by deleting the loops and counting to infinity cases, also the minimisation of the controlling data increases the network performance. Thus the communication overhead incurred by the protocol could be named as a key issue in verifying a good routing protocol for ad hoc networks. Minimising the control traffic frees up more bandwidth for data, since their share the same communication bandwidth.
A very interesting approach is taken in STAR [3] protocol where the
control traffic is minimised by the argument, that the computing of the
optimum paths to all destinations at the expense of considerable routing-update
traffic is not practical in networks with untethered nodes and dynamic
topologies. Thus the used paths in STAR are not always optimum routes to
destinations, but the way that routing table is updated is bandwidth and
battery saving. It is argued in [3] that to date, the debate on whether
a table-driven or an on-demand routing approach is best for wireless networks
has assumed that table-driven routing necessarily has to provide optimum
(e.g., shortest-path) routing, when in fact on-demand routing protocols
cannot ensure optimum paths.
The algorithm allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain route information to destinations that are not in active communication. It determines both unicast and multicast routes, so that the multicast group memberships are free to change during the lifetime of the network.
The implementation of the protocol is based on five message types, which are Route Request (RREQ), Route Reply (RREP), Route Error (RERR), Multicast Activation (MACT) and Group Hello (GRPH). The message types are handled by UDP, and normal IP header processing applies. As long as the endpoints of a communication connection have valid routes to each other, AODV is not used. The role of AODV is therefore on the establishment of the routes. Connections to unknown nodes are formed by broadcasting RREQ message. A route is determined when the message reaches either the destination endpoint or an intermediate node with 'fresh enough' route to the destination. A route is 'fresh enough' if the route information is unexpired and the destination sequence number is equal to or greater than in the RREQ message. The route is made available by unicasting a RREP message to the source of the RREQ. After the source receives the RREP it may start using the route by sending packets to the destination though the neighbour node defined in the RREP.
Nodes monitor the link status of next hops in active routes. When a link break is detected, a RERR message is used to notify other nodes that the loss of the link has occurred. The RERR message indicates which destinations are now unreachable due to the loss of the link.
RREQ messages are also used to join a multicast group indicating it by a join flag. In this case nodes forwarding RREP message save the route information as multicast route, which is used if the route is selected to be added to the tree. If the root is chosen for addition to the multicast tree, it will be activated by a MACT message.
The last message type, Group Hello, is used by multicast group leader to inform the group members on changes in the multicast tree. These include changes in the multicast tree route and a change of group leader.
To evaluate the 'goodness' of AODV, the RFC [2] lists at the introduction all the salient characteristics of manet networks which the protocol conforms with; dynamic link conditions, low processing and memory overhead and low network utilisation. These match very closely to dynamic topology, bandwidth-constrained links and energy-constrained operation. From the metrics to measure the operation of the protocol, loop-freeness is mentioned as is also the counting to infinity problem. Both of these are solved by using sequence numbering. Routing loops could occur at multicasting when several available paths are found to a new node to join the multicast group. This is solved by selecting always the path with the biggest sequence number or when they are equal, the path with less hops.
Another risk when routing loops could be formed is during a reconnection of two multicast trees. This is solved by stating that the reconnection is started by the multicast group leader with the lower IP address by sending a RREQ message to the group leader with greater IP address. Any node in the other multicast group receiving the RREQ message must forward the messages upstream to the group leader of the multicast group.
After a reboot a node has lost its prior sequence number as well as its last known prior sequence numbers for various other destinations. However, there may be neighbouring nodes which are using this node as an active next hop. To prevent routing loops after a reboot due to stale routing information, the node must wait a predefined time during which it does not respond to any routing packets. After the waiting time when a node receives a RREQ from any other node, its sequence number gets updated.
The monitoring of active link conditions is implemented using the network capacity efficiently. There is no specific messages send to check the link conditions but the link is considered damaged when there is no response after a data packet was forwarded to an active next hop. The response could be an acknowledgement received in the link level or a passive acknowledgement, meaning that a node does not hear the next hop making any transmission attempts.
But there are also shortcomings in AODV. At least two arguments [6]
can be stated that the network capacity is not used economically. Firstly,
in the absence of source routing and promiscuous listening, AODV can gather
only very limited amount of routing information. In particular, route learning
is limited only to the source of any routing packets being forwarded. This
usually causes AODV to rely on a route discovery flood more often than
protocols utilizing these features, which may carry a significant network
overhead. Secondly, the routing table entries which are not used recently
are expired. This is done to ensure fresh routing information. It is possible
to expire valid routes, if unused beyond an expire time. Also, determination
of a suitable expire time is difficult, as sending rates for sources as
well as node mobility may differ widely and can change dynamically.
Depending on the bandwidth available in ad hoc network, the ORA (optimum routing approach) or LORA (least overhead routing approach) approach can be used to updating the routing information. The basic concept of ORA is to find the optimum path respect to defined metric. The metric could be different for each type of service. But since in STAR only one type of service exits, the update criteria has been defined to be any change in the source tree. The basic concepts of LORA are for the routers to use the paths found after a flood search as long as the paths are valid, even thought the paths are not optimum and to maintain path information for only those destinations with which the router needs to communicate. Under LORA, a router running STAR sends updates to its neighbours when it looses its paths to one or more destinations, when it detects a new destination, or when it detects that local changes to its source tree can potentially create long term routing loops. STAR is a first table-driven routing protocol that implements LORA.
The basic update unit used in STAR to communicate changes to source trees is the link-state update (LSU). An LSU reports the characteristics of a link. In a link from a router u to a router or destination v, the router u is the head node. Only the head node of a link is allowed to report changes on the parameters of that link. LSUs are validated by a sequence number, which is set by the head node. A node has only one valid sequence number which is used for each of its link. This means that a sequence number of consecutive LSUs of a link can be incremented by more than one. The same LSU is not retransmitted on the link, since link-state information never ages out.
How update messages are exchanged in STAR depends on the routing approach used (ORA or LORA) and the service provided by the link layer. The router supporting LORA send update messages according to the following four rules:
LORA 1 Router finds a new destination, or any of its neighbours report
a new destination.
LORA 2 At least one destination becomes unreachable to router or any
of its neighbours.
LORA 3.1 A path implied in the source tree of router leads to a loop.
LORA 3.2 The new successor chosen to a given destination has an address
larger than the address of the router.
LORA 3.3 The reported distance from the new chosen successor n to
a destination j is longer than the reported distance from the previous
successor to the same destination. However, if the link (i, j)
fails and n is a neighbour of j, no update message is needed regarding
j
or
any destination whose path from i involves j.
LORA 4 A data packet is received from a neighbour who, according to
its source tree, is in the path to the destination specified in the data
packet. This rule is needed to eliminate permanent looping under
unreliable broadcasting.
LORA1-3 are sufficient rules to ensure loopless paths for every router to all destinations, without the routers having to send updates periodically.
A fourth LORA rule is needed to prevent permanent looping, which could occur due to unreliable update message broadcasting. When there is no retransmission of update messages, it could occur that every neighbour does not receive each message. This could generate permanent loops as described in the following two-node loop example. When router A sends an update message to the neighbour router B, specifying that A is using B to get to destination D, and B does not receive it, B could start using A to reach D.
If ORA is to be supported in STAR, the only rule needed to send update messages consists of a router sending an update message every time its source tree changes.
The major work to design STAR protocol is done in the University of California. It seems to have less interest by other research groups than AODV and it is thus yet difficult to find clear proofs on the evaluations of the performance measurements of STAR protocol.
In the Internet Draft [3] STAR is advertised to be the first example of a table-driven routing protocol that is as efficient as an on-demand routing protocol by exploiting link-state information and allowing paths taken to destinations to deviate from the optimum in order to save bandwidth. Clearly it can be said that the limitation of the amount of update messages saves bandwidth.
Loop freeness is accomplished in STAR by sequence numbering and by the
defined four LORA rules for sending update messages.
To have a better and more thorough evaluation of a manet protocol, the protocol would need to be compared to another protocol with same basic routing mechanisms. Quantitative metrics can be analysed through simulations and the results can be compared to any protocol type. But the 'goodness' of the qualitative metrics of a protocol can only be evaluated when compared to another protocol preferably with same routing mechanism. The evaluation of protocols is also always very subjective to the networking context which may give advantages to one protocol over another one, since it is clear than some protocols are better suited for certain type of networking context than others.
Mobile network is often an extension to a fixed network so mobile users
expect to get the same services as in fixed network. Thus a salient requirement
for manet protocols is to provide reasonably good quality network compared
to fixed networks in order to ad hoc networks to be accepted in public
use.
| [1] | Stevens, R. "TCP/IP Illustrated, Volume 1"Addison-Wesley 1998. |
| [2] | Perkins, C., Royer, E., and Das, S. "Ad Hoc On-Demand vector (AODV)
Routing ", Internet-draft, 22.10.1999, p.38.
< http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-05.txt > |
| [3] | Garcia-Luna-Aceves, J., Spohn, M., and Beyer, D. "Source Tree Adaptive
Routing (STAR) Protocol", Internet-draft, 22.10.1999, p.26.
< http://www.ietf.org/internet-drafts/draft-ietf-manet-star-00.txt > |
| [4] | [RFC 2501] Corson, and S., Macker, J "Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation Considerations" RFC
2501, January 1999, p.12.
< http://www.ietf.org/rfc/rfc2501.txt> |
| [5] | .Garcia-Luna-Aceves, J. "Loop-Free routing using diffusing computations", IEEE/ACM Transactions on networking, Vol. 1, No.1, February 1993. |
| [6] | Das, S., Perkins, C., and Royer, E. "Performance Comparison of Two
On-demand Routing Protocols for Ad Hoc Networks", Infocom 2000.
< http://www.ececs.uc.edu/~mmarina/aodv/ > |
| [7] | Boppana, R., Marina, M. and Konduru, S. "An Analysis of Routing techniques for Mobile and Ad Hoc Networks", HiPC '99 Mobile Computing Session. |