Low cost routing in Mobile Ad-hoc Networks: is it achievable?
Roberto B ALDONI Roberto B ERALDI
baldoni, beraldi
@dis.uniroma1.it Dipartimento di Informatica e Sistemistica
Universit`a di Roma “La Sapienza”,Via Salaria 113, Roma, Italy
Abstract
Cache schemes that adopt timeout (i.e. lifetime) for re- moving stale information have its correct estimation as ba- sic assumption. An incorrect value for the timeout highly reduces the effect of the cache scheme or, even worst, pro- duces a severe performance degradation rather than an im- provement. However, lifetime estimation in mobile ad-hoc networks is difficult to assure due to the rapid ad random changes in the network topology as well as to dependency on the path length.
In this paper we discuss the general issue of caching in the context of mobile environments as a means to achieve efficient routing protocols. We propose a class of cache schemes that adopt active topology monitoring to determine when cached routes become stale. The scheme requires ex- plicit support from the routing protocol. We present an im- plementation of the scheme when using a ZRP-like routing protocol and present some preliminary performance results.
Keywords: MANET, Routing protocols, wireless net- works, caching, performance evaluation.
1. Introduction
A mobile ad-hoc network (MANET) [5] is a set of func- tionally equivalent mobile hosts, hereafter also referred to as nodes, which must be able to communicate while mov- ing without using any kind of wired backbone. A graph G=(V,E) can be used to model MANETs. Elements belong- ing to the vertex set V correspond to mobiles and edges be- longing to set of edge E correspond to wireless links in the network. Due to mobility, new wireless links are contin- uously created and existing one are deleted; thus G is time variant. The issue of routing stems from the observation that well known algorithms derived from graph theory, which ef- ficiently calculate paths in G, are not suitable when G varies with time.
Routing protocols for MANETs can be divided into two classes, proactive protocols and reactive protocols. A sur-
vey can be found in [14]. Proactive protocols are based on the long experience in fixed networks. They use pre- computation of paths between all pairs of nodes in G which are then stored at each node and immediately available for use. Examples of such routing protocols are those based on the distributed Bellman-Ford (DBF) algorithm [2], known as Distance Vector protocols, and on the Dijkstra’s shortest path algorithm or Link State protocols (like Open Shortest Path First, OSPF). Destination-Sequenced Distance Vector (DSDV)[12], Optimized Link State Protocol (OLSR) [8], Global State Routing (GSR) [15] are examples of proactive protocols proposed for the MANET environments. The main drawbacks of proactive protocols are: (i) scalability;
(ii) slow convergence to correctly track changes in network topology; (iii) battery drain due to protocol management even in absence of user traffic.
In reactive protocols the computation of a path is per- formed on-demand only when it is required for sending a message. Computation is based on a query-reply cycle that adopts flooding of query packets. Then, the routing infor- mation is either piggybacked on the message containing the application payload (source routing) or stored at the inter- mediate nodes. Examples of such protocols are Dynamic Source Routing (DSR) [6], Ad hoc On-demand Distance Vector (AODV) [13], Temporally Ordered Routing Algo- rithm (TORA) [11]. In principle, reactive protocols require a new route discovery for each transmission of packets. This makes the scheme very expensive since the discovery pro- cedure involves all nodes in the network. In addition, flood- ing the network with route request packets can lead to the
”broadcast storm problem” [10].
To combine the benefits of the two approaches while reducing their drawbacks hybrid protocols were also pro- posed and represent an attractive solution. In the Zone Rout- ing Protocol (ZRP) [4] a proactive algorithm runs insides
”zones” comprising nodes at distances of K hops or less.
Let
be the distance in number of hops between the
nodes
and
. If
then a route from
to
is immediately available, otherwise a discover procedure is
triggered. In order to minimize control traffic [3]
has to
be set to a value as small as 2 or 3, so the probability that
is high and thus a discovery procedure is often triggered.
In order to reduce the cost of reactive protocols the num- ber of route discoveries has to be reduced by means of caching [9, 7]. The main concern of a cache scheme is how to guarantee cache consistency, i.e. how can it be as- sured that routes stored in the cache reflect the current net- work topology? Using out-of-date cached routes produces, in fact, a severe performance degradation rather than im- provement. For example, [9] reported that in the Dynamic Source Routing (DSR) protocol up to 41% of route replies sent based on data cache contained broken routes. Remov- ing stale information from caches is thus a critical issue.
In this paper we discuss the general issue of caching in the context of mobile environments and point-out that low- cost routing can be achived by means of a well designed caching scheme. To this end, caching should be strongly integrated into the routing protocol, rather than used simply as a means to improve reactive protocols. We thus propose a class of cache schemes that adopt active topology moni- toring to detect when cached routes become stale. Tracking network topology changes requires explicit support from the routing protocol, but limited to information stored into the cache. This leads to a hybrid proactive/reactive routing pro- tocol that does not use any timer-based mechanism. We test the cache scheme by using a ZRP-like protocol implementa- tion, dubbed C-ZRP, and present some performance results.
The paper is organized as follows: section 2 intriduces caching, section 3 describes the proposed cache scheme and its implementation. In section 4 simulation results are pre- sented. Finally, conclusions are given.
2. Caching in routing protocols
A cache scheme is characterized by the following two mechanisms:
write policy, set of rules to decide when writing infor- mation into the cache;
deletion policy, set of rules for deciding when to re- move an entry from the cache.
The design of a policy must account for the amount of knowledge about network topology that the policy exploits and the degree of cooperation among nodes. Knowledge about network topology is gained by a node either directly, by using specific messages (i.e. hello) or indirectly, by ob- serving (a) user data traffic (for example to confirm that a path is still valid) (b) protocol specific traffic (i.e. error route messages). Moreover, a node can either act indepen- dently from the others (isolated policy) or cooperate with other nodes (coordinated policy).
A write policy is aggressive if it aims to extract as much information as possible related to the network topology. For example [9] a node can ”snoop” on the unprocessed portion of the source route and add to its cache the route from itself to the final destination listed in the source route. Also, by running the network interface in promiscuous mode a node can scan any packet it hears for useful routes.
Deletion policy is actually the critical part of a cache scheme. Two kinds of errors can occur:
Late Deletion Error, a cached route is not removed when it is no longer valid;
Early Deletion Error, a cached route is removed when it is still valid.
Late deletion errors can result in a severe performance degradation, especially if an aggressive write policy is used.
As noted by [9] stale routes, if used, may start polluting other caches. On the other hand, if in order to avoid late deletion errors, the removal from cache is accomplished too early the effectiveness of the scheme is reduced. A route discovery has, in fact, to be triggered from a node S even if a valid path to the destination node D has been recently learned by S, which is exactly the reason why caching is in- troduced. This reduces the effect of the cache scheme whose goal is to decrease the number of route discoveries and thus the protocol overhead.
In the simplest deletion policy the time when an entry will be deleted is set when it is created. The decision to delete a cache is taken by each node independently from the others so that the policy is isolated.
A delete policy is adaptive if it tries to determine a suit- able lifetime after which the entry is deleted. The cor- rect estimation of timeout is however difficult due to the general mobility pattern, as well as its dependency on the path length. To outline the weakness of timer-based mech- anisms, let us consider Figure 1. In this Figure, an arrow from a node
to
means that
sends packets to
and that those nodes are directly visible each other. Node
acts as server and nodes
,
and
as clients 1 .
Assume that nodes
,
,
cached the route to
. Fur- ther let us suppose that the link (
,
) breaks but lifetimes of cached routes at clients have not expired. If clients send messages to
, each of them discovers the breakage inde- pendently only when trying to use the broken path (as in DSR). For example, when node
sends a message to
it receives an error route from
. Despite this advertisement, both nodes
and
still use the broken path to reach
. To avoid such a situation node
should communicate to all nodes
,
,
the breakage of the path. In this case, deletions from cache are coordinated among nodes in the network and
1 Currently, client-server is a typical interaction between nodes in a mo-
bile environment.
b
c
d e
a
Figure 1. Hot-spot traffic pattern.
act proactively. This strategy is adopted in AODV together with a timer-based state to determine when removing an en- try in the routing table. Again, estimation of timeout can become a critical point.
In order to guarantee that cached routes are neither re- moved prematurely nor remain in the cache if no longer valid, timer-based delete policy have to be avoided. We sug- gest to monitor the network topology explicitly, but limited to information stored in the cache. This requires the use of some degree of cooperation among nodes. The resulting routing protocol is thus hybrid since it uses both the reactive and proactive approaches.
In order to realize the above framework, we introduce the notion of a cache-leader node. A node
is called cache- leader node if it writes information to the cache only if it can monitor the validity of the information. Once
be- comes cache-leader, it broadcasts cached paths to a set of nodes
at a distance no more than R hops. A node
receiving this advertisement writes the path into its cache, setting
as the ”next-hop” node. The node
is dubbed a cache-passive node. A cache-leader sends an explicit delete message to nodes in Z(B) as soon as it deletes an entry from its cache. Passive-cache nodes must always have a path to the cache-leader node that advertised routes. As soon
cannot reach a cache-leader
, it deletes cached routes that have
as next-hop node. Thus, deletion of an entry from a passive-cache node
is triggered either by a message from the cache-leader node or when the distance between
and
exceeds R. If
this mechanism is similar to the one used by AODV. The cache-leader corresponds to nodes that lie on active paths while cache-passive nodes do no exist.
Our solution is however more general, since it comprises AODV as a special case, and does not use timeouts. When
, a monitor function, limited to the area
, has to be added to the protocol.
The proposed scheme can be fairly mapped into a ZRP- like framework, where
corresponds to the
’s zone and monitoring is accomplished by the IARP (IntrAzone Routing Protocol). Such an implementation will be referred to as C-ZRP. As an alternative, monitoring could be started on-demand only when useful to track topology changes. In
the following section we first describe ZRP and then discuss the implementation of C-ZRP in details.
3. An implementation of the caching scheme
ZRP [4] is a hybrid routing protocol that provides routing service by using two different approaches, a proactive In- trAzone Routing Protocol (IARP) and a reactive IntErzone Routing Protocol (IERP). Central for such a protocol is the notion of zone, defined for each node as the set of nodes at a distance not greater than
hops (
is called the zone’s radius).
A IARP route is immediately available at node
for nodes belonging to its routing zone. A IERP route is ob- tained reactively for those nodes located beyond the sender node’s routing zone.
If a node
wishes to send a message to the node
it first checks if a IARP route is available. If such is the case, no further actions are taken, otherwise the source invokes the IERP in order to discover a route. The route discov- ery procedure is based on a controlled flooding of messages and exploits the underlying zone structure to optimize the query process. This is accomplished by sending the query message only to those nodes located at distance
from the querying node (called the border nodes) instead of to all the nodes of its zone (this multicast transmission is called bordercast) and by using suitable mechanisms (Loopback Termination, Query Detection,..) to stop redundant query threads.
On receiving a query message a border node can either reply to the source if a route to the destination is provided by the local IARP (i.e. the destination is within the border node’s routing zone 2 ) or bordercasts the message again.
3.1 C-ZRP
In C-ZRP each node
uses three local data structures, called the Internal Zone routing Table (IZT), External Zone routing Table (EZT), and InterZone Paths (IZP) table.
An entry of IZT is a triple (
), where
is the des- tination node,
is the next-hop node (located in the
’s transmission range), and
is the path cost in number of hops (i.e. the distance).
Similarly, a row of EZT is a triple (
), where
is the destination node,
is the ”next-hop” node (
belongs to the
’s routing zone and is not restricted to be in its trans- mission range), and
is the cost in number of routing zones.
An interzone path from
to
is formed by a sequence of nodes
in which node
2 The query can extended up to the destination in order to let the desti-
nation acquire a route back to the sender.
B
1B
2B
2, ) S (ID,
B
3B
4b a 2 c a 2 a a 1
e b 2 p b 3 t b 4 D b 5
a a 1
h h 1 S a 2 c a 2 g f 2 l h 2 e h 2 f f 1
p e 2 t e 3 D e 4
h h 1
p m 2 n m 2 l h 2 m m 1
b h 2
S b 2 t p 2 D p 3
m m 1 q q 1 e m 2 t q 2
S p 4 b p 3 e p 2 a
c
f g
h
i m
n
r D b=
e= p=
q
t=
S
Node S Node B1 Node B2
IZT
EZT IZT
EZT IZT
EZT
IZT
S e 3 b e 2 D t 2 EZT
Node B3
D r 2 r r 1 q q 1 p q 2 IZT
EZT
r r 1 IZT
p t 2 e t 3 t r 2
S t 5 b t 4 EZT
Node B4 Node D
o k
IZP=(ID,S,B2) IZP=(ID,B1,B3) IZP=(ID,B2,B4) IZP=(ID,B3,D) Interzone Node
Figure 2. An example of values of data struc- tures used in C-ZRP,
=2.
is a node within
’s routing zone and external to
’s routing zone.
A single interzone path from
to
is created during a route request/reply cycle by (i) allowing the destination
to send only one reply for a given request and (ii) by electing a node as a member of the path only if it forwards the request and the corresponding reply. This mechanism is similar to the one used in [13]. An entry in the IZP table is a triple (
), where
is the interzone path identifier
3 while
and
are two nodes belonging to the
’s routing zone, which we refer to as companion nodes.
A node
(
) belonging to an interzone path is called an interzone node and stores a triple in its IZP with
and
. An example of values of the above data structures is given in Figure 2.
The following consistency relations are always guaran- teed 4
(
)
EZT
(
)
IZT (
)
IZP
(
),(
)
IZT When a node
leaves the
’s routing zone, the IARP deletes: the entry (
) from IZT; all the entries (
) from EZT; all the entries (
) and (
) from IZP.
When a node
has a new message
to send to a node
, it first checks if either IZT or EZT have an entry for
. If such is not the case a route discovery is triggered. Even- tually, a node
is selected as the next-hop node towards
and the message
is sent to it, with the destination field
.
On receiving
a node
checks the destination
. If
then the message is delivered to the upper
3 This identifier is unique in the network and can be obtained by using the sequence number of a request issued by a node and the node identifier.
4 The character - means any.
B
1B
2B
3B
4Query
D S
B
2B
3B
4S B1 2 B4 B3 2 D B3 3
B
1B
2B
3B
4B
1(a)
T=[(ID,B1,1,B1), (ID,S,2,B1)]
AV=[S] AV=[S,B1] AV=[S,B1,B2]
D S
Reply AV=[D]
RN=[(S,2),(B1,1),(B3,1),(B4,2),(D,3)]
EZT
Active node AV=[D,B4]
AP=[(ID,B4,B3,B2)] AV=[D,B4,B3]
S D
DeletePath
UN=[B2,B1,S] UN=[B2,B1,S]
UN=[B3,B4,D]
UN=[B3,B4,D]
EZT S B1 2
(b)
(c)
DeletePath
IZT=[(ID,B1,B3)]
Figure 3. An example of interzone path cre- ation and deletion.
layer. Otherwise
forwards the message according to the following algorithm
forward(
);
if(
)
IZT then ucast(
) to
;
elseif(
£)
EZT then Let (
£)
IZT;
ucast(
) to
;
3.1.1 Path management
In the following we discuss how entries are added to and deleted from EZT and IZP.
Interzone Path creation. When
triggers a new route discovery for a node
, it bordercasts a query message to all its border nodes. The message contains a unique identifier
and a route accumulation vector
, initialized with
.
[I]When a border node
receives a query message:
1. It adds its own identification into the accumulation vector. As an example, if the node
corresponds to node
in the interzone path, then
. 2. If
belongs to the
’s routing zone, then the latter
unicasts the query message to
. Otherwise it exe- cutes a bordercast in its zone 5 .
5 Any method adopted in the base ZRP can be used to block multiple
[II] When the destination node
receives a query mes- sage with identifier
for the first time it:
1. Stores the following tuples
in EZT
2. Prepares a list of Reachable Nodes,
!
=[
],
. 3. Sets
.
4. Sends a reply message to
. The message contains the
vector accumulated in the query message.
[III]When a border node
receives a reply message:
Let consider the node
corresponds to node
: 1. If
then stores the triple (
) in the IZP table.
2. Stores the following sets of tuples in EZT:
" "
,
,
". 3. prepares a list of Reachable Nodes:
!
=[
,
" "],
"
.
4. If
then forwards the reply message to the node
.
Figure 3.b shows the state at node
after it received the reply message.
1. The node becomes a member of an interzone path (it stores the triple (
) in the IZP table).
2. Adds the entries (
),(
),(
) in EZT.
3. Prepares the list of reachable nodes
!
. 4. Forwards the reply to
.
Let us finally remark that when a node
becomes a member of an interzone path from
to
(
) due to a route request/reply request generated from
, it becomes actually a member of all the interzone paths from
to
with
#,
.
Interzone Path deletion. An interzone path is broken at node
when
(or
) is no longer in the
’s routing zone. In this case, the node executes the following actions:
redundant queries.
1. Prepares a list of unreach-
able nodes
$!=[
] (
$!=[
]) 6 . 2. clears the entries (
) from EZT.
3. checks for the companion node
(or
) in the IZP table.
4. sends a Delete Path message containing
$!and the path identifier
to the companion node.
5. clears the entry from IZP after the successful transmis- sion of the message.
Let us consider an interzone path is broken, say between
and
. Not all the routing information gathered dur- ing the creation of the interzone path is lost. From the point of view of a node
(with
) all the routing in- formation concerning interzone paths from
½
to
½
(with
#
,
and
#
) is still valid. Similarly, from the point of view of a node
¼
(with
¼
) all the routing information concerning interzone paths from
¾to
¾(with
#,
and
#
¼
) is still valid. Figure 3.c shows the case when the ”link” between
and
is broken (i.e. their distance becomes higher than
). Two in- terzone subpaths are generated. In the figure the
’s EZT data structure is shown.
When an interzone node receives a Delete Path mes- sage from
it deletes the entries stored in
$!list from EZT and forwards the message to the
’s companion node.
Note that if the node has some another route to some of the nodes indicated in the
$!list, then the node can copy in the outgoing message only those nodes for which no routes are available. Forwarding continues until node
(
) is reached.
3.1.2 Cache management
So far, we have described how a node
belonging to a path from
to
acquires route information about all the other nodes of that interzone path.
can then act as cache-leader node (see previous section) within its zone with respect to route information acquired by handling the path from
to
.
Injecting and maintaining external routes. A node stores information about the interzone path it belongs to in the EZT data structure and creates the
!list. It then broadcasts
!inside its zone 7 . We call such a message the inject message.
6 If the node has a some other path to a node
than
is not included in the list.
7 One possible way is to use a limited broadcast with the Time To Live
field set to the zone’s radius
.
B
2B
3B B
41
D
S B
2B
1B
3B
4
B
2S D
Y UN=[(B3,B4,D)]
Delete
B1 B2 1 Y’s EZT D B2 3 B4 B2 2 B3 B2 1 B1 B2 1 S B2 2 Y’s EZT Y
Inject RN=[(S,2),(B1,1),(B3,1),(B4,2),(D,3)]
Y’s routing zone
’s routing zone
S B2 2
(a)(b)
Figure 4. An example of injection and deletion of external routes.
Figure 4.a shows node
injecting the external routes to nodes
into its zone. Note that
has two routes to node
since such a node is in the
’ rout- ing zone. On receiving an inject message carrying the reachable node list
!from a node
, a node
creates a set of entries
(
! !into EZT,
, where
!is the first component (des- tination identifier) of the pair stored at
!and
!the other one.
When a node
detects a new neighbor node
it sends all the triples of the EZT to it. If the next-hop node of a triple belongs to the
’s routing zone, then
adds it in its EZT. Note that the next-hop node remains unchanged.
Deleting external routes. When a node
either detects a path breakage or receives a Delete Path message it broadcasts a Delete Routes message into its zone containing the list of unreachable nodes
$!, created by the node or carried by the Delete Path message respectively. When an internal node receives a Delete Routes message it deletes all the matching entries from EZT. Figure 4.b shows the delete mechanism on node
. A node
also deletes the entries (
) from EZT when node
leaves the
’s routing zone. In this way the consistency relation is satisfied.
4. Preliminary performance results
In this section we present some preliminary numerical results obtained by simulating the system for a period of
1000 sec. Each node moves in a 1500 x 1500 m
square region according to a random waypoint model [1]: the node alternates between a pause state and a moving state, i.e. it remains stationary for a fixed time interval, called the Pause Time (
%&), and then it moves to a random destination point in the region at a constant speed
m/s.
%&is given as a percentage of the simulation period. Node movement and traffic generation are mutually independent. Traffic activ- ity is modeled as Constant Bit Rate (CBR) sources. Only a subset of nodes (the sending subset) can generate traffic di- rected to a fixed subset (the destination subset). The sending and destination subset are disjoint and are composed by the same number
of nodes. Each node of the sending subset generates
'=512-byte packets at a rate
(=4 message/s over a
)=2 Mbps digital channel. A packet is destined to any randomly selected node belonging to destination subset.
We assume a fairly ideal behavior of the underlying com- munication system so that the observed results are only due to the protocol characteristics and do not depend on any par- ticular traffic load (i.e. congestion) or environment (i.e. sig- nal propagation) condition. In this way we attempt to re- move all effects not directly due to the algorithm itself. A unicast or broadcast message is successfully received by the target node, provided it is in the sender transmission range
m. Deferring time due to transmissions of adja- cent nodes and the time required to acquire the media are assumed negligible, so that a packet is received
&ms after its transmission. Similarly, the assumed transmission time of the shorter routing message is
&ms.
Figure 5 shows the percentage of times a sending node
used a route to the destination
from its routing tables, either IZT or EZT, as a function of
%&for
and
. As expected, such a value increases with
%&. In fact, the higher
%&the lower the mobility and thus the higher the time interval a route remains in the tables. In this way, the probability that the entry will be used to send a message to
increases. For
%&the network is static and thus paths are learned once either via route discovery or via an inject message. Since these information are always valid the hit rate approaches 100%.
Protocol Overhead Route requests ZRP (
%&=80%) 327431 2709 C-ZRP (
%&=80%) 68903 330
ZRP (
%&=20%) 806904 6229 C-ZRP (
%&=20%) 421954 2199
Table 1: Protocol overhead.
The protocol overhead is measured by the total number
of packets observed during a simulation which are not sent
on behalf of any user application. The overhead is due to (i)
the interzone path maintenance procedures; (ii) the trans-
mission of inject and delete messages; (iii) the discovery
70 75 80 85 90 95 100
0 10 20 30 40 50 60 70 80 90 100
Routing table hit rate
Pause Time (%)
Base, A=5 Cache, A=5 Base, A=25 Cache, A=25
Figure 5. Routing table hit rate.
procedure. Table 1 lists the protocol overhead and the to- tal number of route requests observed during a simulation when
for
%&and
.
Even with frequent changes in the network topology (i.e.
%&
