Highly Dynamic Destination-Sequenced Distance-Vector Routing

(DSDV) for Mobile Computers

Charles E. Perkins Pravin Bhagwat

IBM, T.J. Watson Research Center Computer Science Department
Hawthorne, NY 10562 University of Maryland
College Park, MD 20742

Abstract users are free to move about at their convenience with-

out being constrained by wires.
An ad-hoc network is the cooperative engagement of
a collection of Mobile Hosts without the required inter- This is a revolutionary development in personal com-
vention of any centralized Access Point. In this paper puting. Battery powered, untethered computers are
we present an innovative design for the operation of such likely to become a pervasive part of our computing in-

ad-hoc networks. The basic idea of the design is to op- frastructure. As people begin to have mobile computers
erate each Mobile Host as a specialized router, which handy, for whatever purposes, sharing information be-
periodically advertises its view of the interconnection tween the computers will become a natural requirement.
topology with other Mobile Hosts within the network. Currently, such sharing is made difficult by the need for
This amounts to a new sort of routing protocol. We users to perform administrative tasks and set up static,
have investigated modifications to the basic Bellman- bidirectional links between their computers. However,
Ford routing mechanisms, as specified by RIP [5], to if the wireless communications systems in the mobile
make it suitable for a dynamic and self-starting network computers support a broadcast mechanism, much more
mechanism as is required by users wishing to utilize ad- flexible and useful ways of sharing information can be
hoc networks. Our modifications address some of the imagined. For instance, any number of people could
previous objections to the use of Bellman-Ford, related conceivably enter a conference room and agree to sup-
to the poor looping properties of such algorithms in the port communications links between themselves, with-
face of broken links and the resulting time dependent out necessarily engaging the services of any pre-existing
nature of the interconnection topology describing the equipment in the room (i.e, without requiring any pre-
links between the Mobile Hosts. Finally, we describe existing communications infrastructure). Thus, one of
the ways in which the basic network-layer routing can our primary motivations is to allow the construction of

be modified to provide MAC-layer support for ad-hoc temporary networks with no wires and no administra-

networks. tive intervention required. In this paper, such a inter-

connection between the mobile computers will be called
an ad-hoc network, in conformance with current. usage
1 Introduction
within the IEEE 802.11 subcommittee [4].
Recently, there has been tremendous growth in the
Ad-hoc networks differ significantly from existing
sales of laptop and portable computers. These smaller
net works. First of all, the topology of interconnections
computers, nevertheless, can be equipped with hun-
may be quite dynamic. Secondly, most users will not
dreds of megabytes of disk storage, high resolution color
wish to perform any administrative actions to set up
displays, pointing devices, and wireless communications
such a network. In order to provide service in the most
adapters. Moreover, since many of these small (in size
general situation, we do not assume that every computer
only) computers operate for hours with battery power,
is within communication range of every other computer.
This lack of complete connectivity would certainly be a
Permission to copy without fee all or part of this material is
reasonable characteristic of, say, a population of mo-
granted provided that the copies are not made or distributed for
direct commercial advantage, the ACM copyright notice and the bile computers in a large room which relied on infrared
title of the publication and its date appear, and notice is given transceivers to effect their data communications.
that copying is by permission of the Association of Computing
Machinery. To copy otherwise, or to republish, requires a fee Currently, there is no method available which enables
and/or specific permission.
mobile computers with wireless data communications
SIGCOMM 94 -8/94 London England UK
@ 1994 ACM 0-89791 -682-4/94/0008..$3.50 equipment to freely roam about while still maintaining

234
connections with each other, unless special assumptions method. Each node maintains a view of the network
are made about the way the computers are situated with topology with a cost for each link. To keep these views
respect to each other. One mobile computer may often consistent, each node periodical y broadcasts the link
be able to exchange data with two other mobile comput- costs of its outgoing links to all other nodes using a
ers which cannot themselves directly exchange data. As protocol such as flooding. As a node receives this in-
a result, computer users in a conference room may be formation, it updates its view of the network topology
unable to predict which of their associates’ computers and applies a shortest-path algorithm to choose its next
could be relied upon to maintain network connection, hop for each destination. Some of the link costs in a
especially as the users moved from place to place within node’s view can be incorrect because of long propaga-
the room. tion delays, partitioned network, etc. Such inconsistent
views of network topologies might lead to formation of
Routing protocols for existing networks have not
routing loops. These loops, however, are short-lived,
been designed specifically to provide the kind of dy-
because they disappear in the time it takes a message
namic, self-starting behavior needed for ad-hoc net-
to traverse the diameter of the network [8].
works. Most protocols exhibit their least desirable be-
havior when presented with a highly dynamic inter-
connection topology. Although we thought that mo-
Distance-Vector In distance-vector algorithms,
bile computers could naturally be modeled as routers,
every node i maintains, for each destination z, a set
it was also clear that existing routing protocols would
of distances {d~j } where j ranges over the neighbors of
place too heavy a computational burden on each mobile
i. Node i treats neighbor k as a next-hop for a packet
computer. Moreover, the convergence characteristics of
destined for x if d~h equals minj {d~i }. The succession
existing routing protocols did not seem good enough
of next hops chosen in this manner lead to x along the
to fit the needs of ad-hoc networks. Lastly, the wire-
shorest path. In order to keep the distance estimates
less medium differs in important ways from wired me-
up-to-date, each node monitors the cost of its outgo-
dia, which would require that we make modifications to
ing links and periodically broadcasts, to each one its
whichever routing protocol we might choose to exper-
neighbors, its current estimate of the shortest distance
iment with. For instance, mobile computers may well
to every other node in the network.
have only a single network interface adapter, whereas
most existing routers have network interfaces to connect The above distance-vector algorithm is the classical

two separate networks together, Besides, wireless media Distributed Bellman-Ford (DBF) algorithm [2]. Com-

are of limited and variable range, in distinction to exist- pared to link-state method, it is computationally more

ing wired media. Since we had to make lots of changes efficient, easier to implement and requires much less

anyway, we decided to follow our ad-hoc network model storage space, However, it is well known that this algo-

as far aa we could and ended up with a substantially rithm can cause the formation of both short-lived and

new approach to the classic distance-vector routing. long-lived loops [3]. The primary cause for formation
of routing loops is that nodes choose their next-hops in

2 Overview of Routing Methods a completely distributed fashion based on information

which can possibly be stale and, therefore, incorrect.
In our environment, the problem of routing is essen- Almost all proposed modifications to DBF algorithm
tially the distributed version of the shortest path prob- [6, 7, 9] eliminate the looping problem by forcing all
lem [11]. Each node in the network maintains for each nodes in the network to participate in some form of in-
destination a preferred neighbor. Each data packet con- ternodal coordination protocol. Such internodal coordi-
tains a destination node identifier in its header. When nation mechanisms might be effective when topological
a node receives a data packet, it forwards the packet changes are rare. However, within an ad-hoc mobile en-
to the preferred neighbor for its destination. The for- vironment enforcing any such internodal coordination
warding process continues until the packet reaches its mechanism will be difficult due to the rapidly changing
destination. The manner in which routing tables are topology of the underlying routing network.
constructed, maintained and updated differs from one
Simplicity is one of the primary attributes which
routing method to another. Popular routing methods,
makes any routing protocol preferred over others for
however, attempt to achieve the common objective of
implement ation within operational networks. RIP [5]
routing packets along the optimal path. The next-hop
is a classical example. Despite the counting-to-infinity
routing methods can be categorized into two primary
problem it has proven to be very successful within small
classes: link-state and distance-vector.
size internetworks. The usefulness of RIP within ad-hoc
environment, however, is limited as it was not designed
Link-State The link-state approach is closer to the to handle rapid topological changes. Furthermore, the
centralized version of the shortest path computation techniques of split-horizon and poisoned-reverse [5] are

235
 not useful within the wireless environment due to the tween arrival of the jkt and the arrival of the best route
broadcast nature of the transmission medium. Our de- for each particular destination. Based on this data, a
sign goal therefore has been to design a routing method decision may be made to delay advertising routes which
for ad-hoc networks which preserves the simplicity of are about to change soon, thus damping fluctuations
RIP, yet at the same time avoids the looping problem. of the route tables. The advertisement of routes which
Our approach is to tag each route table entry with a may not have stabilized yet is delayed in order to reduce
sequence number so that nodes can quickly distinguish the number of rebroadcasts of possible route entries that
stale routes from the new ones and thus avoid formation normally arrive with the same sequence number.
of routing loops.
The DSDV protocol requires each mobile station to
advertise, to each of its current neighbors, its own rout-
3 Destination-Sequenced Distance Vec-
ing table (for instance, by broadcasting its entries). The
tor (DSDV) Protocol entries in this list may change fairly dynamically over
time, so the advertisement must be made often enough
Our proposed routing method allows a collection of
to ensure that every mobile computer can almost al-
mobile computers, which may not be close to any base
ways locate every other mobile computer of the collec-
station and can exchange data along changing and arbi-
tion. In addition, each mobile computer agrees to relay
trary paths of interconnection, to afford all computers
data packets to other computers upon request. This
among their number a (possibly multi-hop) path along
agreement places a premium on the ability to deter-
which data can be exchanged. In addition, our solution
mine the shortest number of hops for a route to a desti-
must remain compatible with operation in cases where
nation; we would like to avoid unnecessarily disturbing
a base station is available. By the methods outlined in
mobile hosts if they are in sleep mode. In this way a mo-
this paper, not only will routing be seen to solve the
bile computer may exchange data with any other mobile
problems associated with ad-hoc networks, but in ad-
computer in the group even if the target of the data is
dition we will describe ways to perform such routing
not within range for direct communication. If the noti-
functions at Layer 2, which traditionally has not been
fication of which other mobile computers are accessible
utilized as a protocol level for routing,
from any particular computer in the collection is done
Packets are transmitted between the stations of the at layer 2, then DSDV will work with whatever higher
network by using routing tables which are stored at layer (e.g., Network Layer) protocol might be in use.
each station oft he network. Each routing table, at each
All the computers interoperating to create data paths
of the stations, lists all available destinations, and the
between themselves broadcast the necessary data pe-
number of hops to each. Each route table entry is tagged
riodically, say once every few seconds. In a wireless
with a sequence number which is originated by the des-
medium, it is important to keep in mind that broad-
tination station. To maintain the consistency of routing
casts are limited in range by the physical characteris-
tables in a dynamically varying topology, each station
tics of the medium. This is different than the situation
periodically transmits updates, and transmits updates
with wired media, which usually have a much more well-
immediately when significant new information is avail-
defined range of reception. The data broadcast by each
able. Since we do not assume that the mobile hosts
mobile computer will contain its new sequence number
are maintaining any sort of time synchronizat ion, we
and the following information for each new route:
also make no assumption about the phase relationship
of the update periods between the mobile hosts. These
packets indicate which stations are accessible from each ● The destination’s address;

station and the number of hops necessary to reach these

● The number of hops required to reach the destina-
accessible stat ions, as is often done in dist ante-vector
tion; and
routing algorithms. It is not the purpose of this paper to
propose any new metrics for route selection other than
. The sequence number of the information received
the freshness of the sequence numbers associated with
regarding that dest inat ion, as originally stamped
the route; cost or other metrics might easily replace the by the destination;
number of hops in other implementations. The packets
may be transmitted containing either layer 2 (MAC)
The transmitted routing tables will also contain the
addresses or layer 3 (network) addresses.
hardware address, and (if appropriate) the network ad-
Routing information is advertised by broadcasting or dress, of the mobile computer transmitting them, within
multicasting the packets which are transmitted period- the headers of the packet. The routing table will also
ically and incrementally as topological changes are de- include a sequence number created by the transmitter.
tected – for instance, when stations move within the Routes with more recent sequence numbers are always
network. Data is also kept about the length of time be- preferred as the basis for making forwarding decisions,

236
but not necessarily advertised. Of the paths with the casts oft he routing information packets. In order to re-
same sequence number, those with the smallest metric duce the amount of information carried in these packets,
will be used. By the natural way in which the routing two types will be defined. One will carry all the avail-
tables are propagated, the sequence number is sent to all able routing information, called a “full dump”. The
mobile computers which may each decide to maintain a other type will carry only information changed since
routing entry for that originating mobile computer. the last full dump, called an “incremental”. By design,
an incremental routing update should fit in one net-
Routes received in broadcasts are also advertised by
work protocol data unit (NPDU). The full dump will
the receiver when it subsequently broadcasts its routing
most likely require multiple NPDUS, even for relatively
information; the receiver adds an increment to the met-
small populations of Mobile Hosts. Full dumps can be
ric before advertising the route, since incoming pack-
transmitted relatively infrequently when no movement
ets will require one more hop to reach the destination
of Mobile Hosts is occurring, When movement becomes
(namely, the hop from the transmitter to the receiver).
frequent, and the size of an incremental approaches the
Again, we do not explicitly consider here the changes
size of a NPDU, then a full dump can be scheduled (so
required to use metrics which do not use the hop count
that the next incremental will be smaller). It is expected
to _the destination.
that mobile nodes will implement some means for de-
One of the most important parameters to be chosen is termining which route changes are significant enough to
the time between broadcasting the routing information be sent out with each incremental advertisement. For
packets. However, when any new or substantially modi- instance, when a stabilized route shows a different met-
fied route information is received by a Mobile Host, the ric for some destination, that would likely constitute
new information will be retransmitted soon (subject to a significant change that needed to be advertised after
constraints imposed for damping route fluctuations), ef- stabilization. If a new sequence number for a route is
fecting the most rapid possible dissemination of routing received, but the metric stays the same, that would be
information among all the cooperating Mobile Hosts. unlikely to be considered as a significant change.
This quick re-broadcast introduces a new requirement
When a Mobile Host receives new routing informa-
for our protocols to converge as soon as possible. It
tion (usually in an incremental packet as just described),
would be calamitous if the movement of a Mobile Host
that information is compared to the information al-
caused a storm of broadcasts, degrading the availability
ready available from previous routing information pack-
of the wireless medium.
ets. Any route with a more recent sequence number
Mobile Hosts cause broken links as they move from is used. Routes with older sequence numbers are dis-
place to place, The broken link may be detected by carded. A route with a sequence number equal to an
the layer-2 protocol, or it may instead be inferred if no existing route is chosen if it has a “better” metric, and
broadcasts have been received for a while from a for- the existing route discarded, or stored as less prefer-
mer neighbor. A broken link is described by a metric of able. The metrics for routes chosen from the newly
00 (i.e., any value greater than the maximum allowed received broadcast information are each incremented
metric). When a link to a next hop has broken, any by one hop. Newly recorded routes are scheduled for
route through that next hop is immediately assigned an immediate advertisement to the current Mobile Host’s
00 metric and assigned an updated sequence number. neighbors. Routes which show an improved metric are
Since this qualifies as a substantial route change, such scheduled for advertisement at a time which depends
modified routes are immediately disclosed in a broad- on the average settling time for routes to the particular
cast rout ing information packet. Building information destination under consideration.
to describe broken links is the only situation when the
Timing skews between the various Mobile Hosts are
sequence number is generated by any Mobile Host other
expected. The broadcasts of routing information by the
than the destination Mobile Host. Sequence numbers
Mobile Hosts are to be regarded as somewhat asyn-
defined by the originating Mobile Hosts are defined to
chronous events, even though some regularity is ex-
be even numbers, and sequence numbers generated to
pected. In such a population of independently trans-
indicate cm metrics are odd numbers. In this way any
mitting agents, some fluctuation could develop using the
‘) real” sequence numbers will supersede an m metric.
above procedures for updating routes. It could turn out
When a node receives an co metric, and it has a later
that a particular Mobile Host would receive new routing
sequence number with a finite metric, it triggers a route
information in a pattern which causes it to consistently
update broadcast to disseminate the important news
change routes from one next hop to another, even when
about that destination.
the destination Mobile Host has not moved. This hap-
In a very large population of Mobile Hosts, adjust- pens because there are two ways for new routes to be
ments will likely be made in the time between broad- chosen; they might have a later sequence number, or

237
they might have a better metric. A Mobile Host could vertise which Layer 3 protocols it supports, and each
conceivably always receive two routes to the same des- Mobile Host advertising reachability to that destina-
tination, with a newer sequence number, one after an- tion would include along, with the advertisement, the
other (via different neighbors), but always get the route information about the Layer 3 protocols supported at
with the worse metric first. Unless care is taken, this that destination. This information would only have to
will lead to a continuing burst of new route transmittals be transmitted when it changes, which occurs rarely.
upon every new sequence number from that destination. Changes would be transmitted as part of each incremen-
Each new metric is propagated to every Mobile Host in tal dump. Since each Mobile Host could support several
the neighborhood, which propagates to their neighbors Layer 3 protocols (and many will), this list would have
and so on. to be variable in length.

One solution is to delay the advertisement of such Extending Base Station Coverage
routes, when a Mobile Host can determine that a route
Mobile computers will frequently be used in conjunc-
with a better metric is likely to show up soon. The
tion with base stations, which allow them to exchange
route with the later sequence number must be available
data with other computers connected to the wired net-
for use, but it does not have to be advertised imme-
work. By participating in the DSDV protocol, base
diately unless it is a route to a destination which was
stations can extend their coverage beyond the range
previously unreachable. Thus, there will be two rout-
imposed by their wireless transmitters. When a base
ing tables kept at each Mobile Host; one for use with
station participates in DSDV, it is shown as a default
forwarding packets, and another to be advertised via
route in the tables transmitted by a mobile station. In
incremental routing information packets. To determine
this way, mobile stations within range of a base station
the probability of imminent arrival of routing informa-
can cooperate to effectively extend the range of the base
tion showing a better metric, the Mobile Host has to
station to serve other stations outside the range of the
keep a history of the weighted average time that routes
base station, as long as those other mobile stations are
to a particular destination fluctuate until the route with
close to some other mobile station that is within range.
the best metric is received. We hope that such a pro-
cedure will allow us to predict how long to wait before
advertising new routes. 4 Examples of DSDV in operation

Operating DSDV at Layer 2

respond
The

protocol
use network
addresses
to the
is operated.
layer
layer
stored
at
That
addresses
in the
which
routing
this
is, operation
for the
ad-hoc

next
tables

hop
will
networking
at Layer
and
cor-

3 will
des-
Qy@(#@> MH

tination addresses, and operation at Layer 2 will use

Layer 2 Media Access Control (MAC) addresses.
\
M HI M H,
Using MAC addresses for the forwarding table does
o o -.. ........ ,.
-...
introduce a new requirement, however. The difficulty .... --- (MH1 .
‘G....a
is that Layer 3 network protocols provide communica- ..... .....* 3
-----
..... .........
tion based on network addresses, and a way must be ....... .. ........ .... . ...... .....- .. ........-

provided to resolve these Layer 3 addresses into MAC

addresses. Otherwise, a multiplicity of different address Figure 1: Movement in an ad-hoc network
resolution mechanisms would be put into place, and a
corresponding loss of bandwidth in the wireless medium Consider J41fA in Figure 1. Table 1 shows a possible
would be observed whenever the resolution mechanisms structure of the forwarding table which is maintained
were utilized. This could be substantial since such at ikfH4. Suppose the addressl. of each Mobile Host is
mechanisms would require broadcasts and retransmit- represented as MHi Suppose further that all sequence
ted broadcasts by every Mobile Host in the ad-hoc net- numbers are denoted SNNN_MHi, where MHi spec-
work. Thus, unless special care is taken, every address ifies the computer that created the sequence number
resolution might look like a glitch in the normal oper- and SNNN is a sequence number value. Also suppose
ation of the network, which may well be noticeable to that there are entries for all other Mobile Hosts, with se-
any active users. quence numbers SNNN.MHi, before MH1 moves away
from MH2. The install time field helps determine when
The solution proposed here, for operation at Layer 2,
is to include Layer 3 protocol information along with the 1If DSDV is operated at level 2 then MHi denotes the MAC
Layer 2 information. Each destination host would ad- address, otherwise it denotes a level 3 address

238
 Destination NextHop Metric Sequence number Install Flags Stable.data
MHI MHZ 2 S406_MH1 TOO1.MH4 Ptrl-MH1
MH2 MHZ 1 S128_MHz TO01.MH4 Ptrl-MH2
MH3 MHZ 2 S564_MH3 TOO1-MH4 Ptrl-MH3
MH4 MH4 o S71O-MH4 TOO1-MH4 Ptrl-MH4
MH5 MH6 2 S392_MH5 TO02-MH4 Ptrl.MH5
MH6 MHfj 1 S076_MHtj TO01-MH4 ptrl-MHG
MH7 MH,5 2 S128_MHT TO02-MH4 Ptrl_Mlf7
MH&-1 MH6 3 so50_MH13 TO02-MH4 Ptrl-MHa

Table 1: Structure of the MH4 forwarding table

to delete stale routes. With our protocol, the deletion tion updates until the next full dump occurs. When
of stale routes should rarely occur, since the detection MH1 moved into the vicinity of MH5 and MH7, it
of link breakages should propagate through the ad-hoc triggered an immediate incremental routing informa-
network immediately. Nevertheless, we expect to con- tion update which was then broadcast to MH6. MH6,
tinue to monitor for the existence of stale routes and having, determined that significant new routing infor-
take appropriate action. mation had been received, also triggered an immediate
update which carried along the new routing informa-
From table 1, one could surmise, for instance, that
tion for MH1. MH4, upon receiving this information,
all the computers became available to MH4 at about
would then broadcast it at every interval until the next
the same time, since its install-time for most of them is
full routing information dump. At MH4, the incremen-
about the same. One could also surmise that none of the
tal advertised routing update would have the form as
links between the computers were broken, because all of
shown in table 4.
the sequence number fields have times with even digits
in the units place. Ptrl-MHi would all be pointers In this advertisement, the information for MH4
to null structures, because there are not any routes in comes first, since it is doing the advertisement. The
Figure 1 which are likely to be superseded or compete information for MH1 comes next, not because it has a
with other possible routes to any particular destination. lower address, but because MH1 k the only one which
has any significant route changes affecting it. As a gen-
Table 2 shows the structure of the advertised route
eral rule, routes with changed metrics are first included
table of MH4.
in each incremental packet. The remaining space is used
to include those routes whose sequence numbers have
changed.
Destination Metric Sequence number
MH1 2 S406_MHl In this example, one node has changed its routing in-
MHZ 1 S128-MHz formation, since it is in a new location. All nodes have
MH3 2 S564_MHs transmitted new sequence numbers recently. If there
MH4 o S71O-MH4 were too many updated sequence numbers to fit in a
MH5 2 S392-MH5 single packet, only the ones which fit would be trans-
MH6 1 S076-MH6 mitted. These would be selected with a view to fairly
MH7 2 S128-MH7 transmitting them in their turn over several incremental
MH8 3 so50-MH13 update intervals. There is no such required format for
the transmission of full routing information packets. As
Table 2: Advertised route table by MH4
many packets are used as are needed, and all available
information is transmitted. The frequency of transmit-
ting full updates would be reduced if the volume of data
Now suppose that MH1 moves into the general vicin- began to consume a significant fraction of the available
ity of MH5 and MH7, and away from the others (es- capacity of the medium.
pecially MH2). The new internal forwarding tables at
MH4 might then appear as shown in table 3. Damping Fluctuations

Only the entry for MH1 shows a new metric, but in The following describes how the settling time table is
the intervening time, many new sequence number en- used to prevent fluctuations of routing table entry ad-
tries have been received. The first entry thus must be vertisements. The general problem arises because route
advertised in subsequent incremental routing informa- updates are selected according to the following criteria:

239
 Destination NextHop Metric Sequence number Install Flags Stable.data

I
MHI MH6 3 S516.MHI T810-MH4 M Ptrl-MHl
MHZ MH2 1 S238.MH2 TOO1.MH4 Ptrl-MH2
MH3 MH2 2 s674_MH3 TOO1-MH4 Ptrl-MH3
MH4 MH4 0 S820.MH4 TOO1-MH4 Ptrl-MH4
MH5 MH6 2 S502-.MH5 TO02.MH4 Ptrl-MH5
MH6 MH6 1 s186_MH6 TOO1-MH4 ptrl-MHe
MH7 MH6 2 S238-.MH7 T002-MH4 Ptrl-MH7
MH8 MH6 3 s160_MH.g T002-MH4 ptrl-MHs

Table 3: MH4 forwarding table (updated)

pose that MH4 receives the higher metric next hop first,
Destination Metric Sequence number and soon after gets another next hop with a lower met-
MH4 o S820-MH4 ric but the same sequence number. This could happen
MH1 3 S516_MHl when there are a lot of Mobile Hosts, transmitting their
MHZ 1 S238_MHz updates not quite regularly. Alternatively, if the Mo-
MH3 2 s674_MH3 bile Hosts are acting independently and with markedly
MH5 2 S502_MHS different transmission intervals, the situation could oc-
MHfj 1 S186.-MH6 cur with correspondingly fewer hosts. Suppose, in any
MH7 2 S238-MH7 event, in Figure 2 that there are enough Mobile Hosts to
MH8 3 s160_MH8 cause the problem, in two separate collections of Mobile
Hosts both connected to a common destination MH9,
Table 4: MH4 advertised table (updated)
but with no other Mobile Hosts in common. Suppose
further that all Mobile Hosts are transmitting updates
approximately every 15 seconds, that Mobile Host MH2

● Routes are always preferred if the sequence num- has a route to MH9 with 12 hops, and Mobile Host

bers are newer; MH6 has a route to MH9 with 11 hops, Moreover, sup-
pose that the routing information update from MHZ
● Otherwise, routes are preferred if the sequence arrives at MH4 approximate ely 10 seconds before the
numbers are the same and yet the metric is bet- rout ing information update from MH6. This will occur
ter (lower). every time that a new sequence number is issued from
Mobile Host MH9. In fact, the time differential can be
drastic if any Mobile Host in collection II begins to is-
MH ~
-., sue its sequence number updates in multiple incremental
... %.
....’ ...
...
..... .... update intervals, as would happen, for instance, when
....” %.
....
-. there are too many hosts with new sequence number
updates for them all to fit within a single incremental
packet update. In general, the larger the number of
Mobile Host
Collection I I
hops, the more drastic differentials between delivery of
the updates can be expected in Figure 2.

@g The settling time data is stored in a table with the

following fields, keyed by the first field:
MH2 MH6
------- ....
.... ..-.,
...-” ● Destination address
....
.... ....””
.-.. MH ‘. ● Last settling time
4

Figure 2: Receiving fluctuating routes ● Average settling time

To see the problem, suppose that two routes with The settling time is calculated by maintaining a run-
identical sequence numbers are received by a Mobile ning, weighted average over the most recent updates of
Host, but in the wrong order. In other words, sup- the routes, for each destination.

240
 Suppose a new routing information update arrives more stale rout ing entries, but would also allow for more
at MH4. The sequence number in the new entry is transmission errors. Transmission errors are likely to
the same as the sequence number in the currently used occur when a CSMA-type broadcast medium is used,
entry, and the newer entry has a worse (i.e., higher) as may well be the case for many wireless implementa-
metric. Then MH4 must use the new entry in making tions. When the link breaks, an cm metric route should
subsequent forwarding decisions. However, MH4 does be advertised for it, as well as for the routes that depend
not have to advertise the new route immediately and on it.
can consult its route settling time table to decide how
There are additional data fields, other than those
long to wait before advertising it. The average settling
stated above, which might be transmitted as part of
time is used for this determination. For instance, MH4
each entry in the routing tables which are broadcast by
may decide to delay (average.settling_time x 2) before
each participating computer (mobile or base station).
advertising a route.
These fields may depend, for instance, on higher level
This can be quite beneficial, because if the possi- protocols or other protocols depending on the operation
bly unstable route were advertised immediately, the ef- of layer 2. For instance, to enable correct ARP opera-
fects would ripple through the network, and this bad tion, each routing table entry must also contain an asso-
effect would probably be repeated every time Mobile ciation between the Internet Protocol (1P) address and
Host MHg’s sequence number updates rippled through the MAC address of the destination. This would also
the ad-hoc network. On the other hand, if a link via enable an intermediate computer, when serving a rout-
Mobile Host MHIj truly does break, the advertisement ing function for its neighbors, to also issue proxy ARP
of a route via MH2 should proceed immediately. To replies instead of routing ARP broadcasts around. How-
achieve this when there is a history of fluctuations at ever, if packet forwarding is based on MAC addresses,
Mobile Host MH4, the link breakage should be detected hopefully such techniques will be unnecessary. And, if
fast enough so that an intermediate host in Collection II forwarding is done based on 1P addresses, no ARP is
finds out the problem and begins a triggered incremen- strictly necessary, as long as neighboring nodes keep
tal update showing an oo metric for the path along the track of associations gleaned from route table broad-
way to Mobile Host M Hg. Rout es with an 00 metric are casts. Note also that layer 3 operation violates the nor-
required by this protocol to be advertised immediately, mal subnet model of operation, since even if two Mobile
without delay. Hosts share the same subnet address there is no guar-
antee they will be directly connected – in other words,
In order to bias the damping mechanism in favor of
within range of each other. This is compatible with the
recent events, the most recent measurement of the set-
model of operation offered by the mobile-IP working
tling time of a particular route must be counted with
group of the IETF [12, 10].
a higher weighting factor than are less recent measure-
ments. And, importantly, a parameter must be selected The new routing algorithm was particularly devel-
which indicates how long a route has to remain stable oped for enabling the creation of ad-hoc networks, which
before it is counted as truly stable. This amounts to are most specifically targeted for the operation of mo-
specifying a maximum value for the settling time for bile computers. However, the routing algorithm itself,
the destination in the settling time table. Any route and the operation of an ad-hoc network, can be bene-
more stable than this maximum value will cause a trig- ficially used in situations which do not include mobile
gered update if it is ever replaced by another route with computers. For instance, the routing algorithm could be
a different next hop or metric. applied in any situation where reduced memory require-
ments are desired (compared to link-state routing algo-
When a new routing update is received from a neigh-
rithms). The operation of an ad-hoc network could be
bor, during the same time that the updates are applied
applied to wired as well as wireless mobile computers. In
to the table, processing also occurs to delete stale en-
general, then, we provide a new destination-sequenced
tries. Stale entries are defined to be those for which
routing algorithm, and this algorithm is supplemented
no update has been applied within the last few update
by a technique for damping fluctuations.
periods. Each neighbor is expected to send regular up-
dates; when no updates are received for a while, the
receiver may make the determination that the corre- 5 Properties of the DSDV Protocol
sponding computer is no longer a neighbor. When that
At all instants, the DSDV protocol guarantees loop-
occurs, any route using that computer as a next hop
free paths to each destination. To see why this property
should be deleted, including the route indicating that
holds, consider a collection of IV mobile hosts forming
computer as the actual (formerly neighboring) destina-
an instance of an ad-hoc style network. Further assume
tion. Increasing the number of update periods that may
that the system is in steady-state, i.e. routing tables
transpire before entries are determined would result in
of all nodes have already converged to the actual short-

241
est paths. At this instant, the next node indicators to 6 Comparison with other Methods
each destination induce a tree rooted at that destina-
tion. Thus, routing tables of all nodes in the network
The table 5 presents a quick summary of some of the
can be collectively visualized as forming IV trees, one
main features of a few chosen routing protocols. The
rooted at each destination. In the following discussion,
chosen set, although small, is representative of a vari-
we’ll focus our attention on one specific destination x
ety of routing techniques most commonly employed in
and follow the changes occurring on the directed graph
operational data networks. Except for the link-state
G(a) defined by nodes i and arcs (i, p; ) where p: de-
approach, all routing methods shown in the table are
notes the next-hop for destination x at node i. Oper-
a variant of the basic distance-vector approach. The
ation of DSDV algorithm ensures that at every instant
comparison criteria reflects some of the most desirable
G(z) is loop-free, or rather, it is a set of disjoint di-
features that a routing algorithm should possess for it
rected trees. Each such tree is rooted either at z or at
be useful in a dynamic ad-hoc style environment. In
a node whose next-hop is nil. Since this property holds
wireless medium, communication bandwidth is the most
with respect to each destination z, all paths induced by
precious and scarce resource. The formation of any kind
routing tables of DSDV algorithm are indeed loop free
of routing loops, therefore, is highly undesirable. In
at all instants.
case of infrared LANS which employ pure CSMA pro-

Potentially a loop may form each time node i changes tocol, looping packets can not only consume the com-

its next-hop. This can happen in two cases. First, when munication bandwidth but they can further degrade the

node i detects that the link to its next-hop is broken, the performance by causing more collisions in the medium.
node resets p? to nil. Clearly, this action cannot form A common technique employed for loop-prevention is
a loop involving 2. The second scenario occurs when what we call internodal- coordination whereby strong
node i receives, from one of its neighbors k, a route constraints on the ordering of the updates among nodes
to z, with sequence number s; and metric m, which is is imposed. The resulting internode protocols tend to be
selected to replace the current route it has through p:. complex. Furthermore, their update coordination may
Let s: denote the value of the sequence number stored restrict a node’s ability to obtain alternate paths quickly
at node i and d: denote the distance estimate from i to in an environment where topology changes are relatively
z just prior to receiving route from k. i will change its frequent. The last criteria used for comparison is the
next-hop from p; to k only if either of the following two space requirement of the routing method. Nodes in
happens. an ad-hoc network may be battery powered lap-tops,
or even hand-held notebooks, which do not have the

1. the new route contains a newer sequence number, kind of memory that NSFNET dedicated routers are

i.e., s; > s: expected to have. Therefore, economy of space is of

import ante.
2. the sequence number s:,. is same as S$, but the new
The primary concern with using a Distributed Bell-
route offers a shorter path to z, i.e, m < diz
man Ford algorithm in ad-hoc environment is its suscep-
tibility towards forming routing loops and counting-to-
In the first case, by choosing k as its new next-hop
infinity problem. RIP [5], which is very similar to DBF
node i cannot close a loop. This can be easily deduced
algorithm, also suffers from the same problem. Unlike
from the following observation. A node i propagates se-
DBF, RIP only keeps track of the best route to each
quence number s: to its neighbors only after receiving
destination, which results in some space saving at no
it from its current next-hop. Therefore, at all times the
extra performance hit. RIP also employs techniques
sequence number value stored at the next-hop is always
known as split-horizon and poisoned-reverse to avoid a
greater or equal to the value stored at i. Starting from
ping-pong style of looping, but these techniques are not
node i, if we follow the chain of next-hop pointers, the
powerful enough to avoid loops involving more than two
sequence number values stored at visited nodes would
hops. The primary cause of loop formation in BF style
form a nondecreasing sequence. Now suppose node i
algorithms is that nodes make uncoordinated modifica-
forms a loop by choosing k as its next-hop. This would
tions to their routing tables based on some information
imply that St s s:. But this contradicts our initial
which could be incorrect. This problem is alleviated
assumption that s: > s?. Hence, loop-formation can-
by employing an internodal coordination mechanism as
not occur if nodes use newer sequence numbers to pick
proposed by Merlin and Segall in [9]. A similar tech-
routes.
nique, but with better convergence results, is developed
The loop-free property holds in the second scenario by Jaffe and Moss in [6]. However, we do not know of
due to the theorem proved in [6], which states that in any operational routing protocols which employ these
presence of static or decreasing link weights distance- complex coordination methods to achieve loop-freedom,
vector algorithms always maintain loop-free paths. which leads us to the conclusion that from a practical

242
 Routing Method Looping Internodal Space

1
Coordination Complexity
Bellman Ford [2] s/1 O(nd)
Link State [8] s O(n2)
Loop-free BF [3] s O(nd)
RIP [5] s/1 O(n)
Merlin Segall [9] loop free Required O(nd)

2!LJ
Jaffe Moss [6] loop free Required
DSDV -- loop free .

s - short term loop, 1- long term loop

n - number of nodes, d - maximum degree of a node

Table 5: Comparison of various routing methods

point of view the usefulness of such complex methods is o Full update period
diminished.
o Settling time applied to triggered updates
Link-state [8] algorithms are also free of the counting-
i!o-infinity problem. However, they need to maintain Note that the measurement of the convergence times
the up-to-date version of the entire network topology may depend heavily on many interesting parameters,
at every node, which may constitute excessive storage such as the average velocity of the mobile hosts, update
and communication overhead in a highly dynamic net- periods, size of the mobile host population, geographical
work. Besides, link-state algorithms proposed or imple- placement of mobile hosts, existence of base stations,
mented to date do not eliminate the creation of tempo- and average processing loads at the mobile computers.
rary routing-loops.

It is evident that within ad-hoc environment design

8 Summary
tradeoffs and the constraints under which a routing Providing convenient connectivity for mobile com-
method has to operate are quite different. The pro- puters in ad-hoc computers is a challenge that is only
posed DSDV approach offers a very attractive combi- now being met. We have presented an innovative ap-
nation of desirable features. Its memory requirement is proach, DSDV, which models the mobile computers as
very moderate O(n). It guarantees loop-free paths at all routers, which are cooperating to forward packets as
instants, and it does so without requiring nodes to par- needed to each other. We make good use of the prop-
ticipate in any complex update coordination protocol. erties of the wireless broadcast medium. Our approach
The worst case convergence behavior of the DSDV pro- can be utilized at either the network layer (layer 3), or
tocol is certainly non-optimal but, in the average case, below the network layer but still above the MAC layer
it is expected that convergence will be quite rapid. We software in layer 2. In the latter case certain additional
are in the process of conducting simulation studies to information should be included along with the routing
verify this claim. tables for the most convenient and efficient operation.
The information in the routing tables is similar to what
7 Current Status and Future Work is found in routing tables with today’s distance vec-
tor (Bellman-Ford) algorithms, but includes a sequence
We have implemented a preliminary version of this
number, as well as settling-time data useful for damping
protocol for use with mobile computers in our lab. Cur-
out fluctuations in route table updates.
rently we are making necessary modifications to the
MARS simulator [1] for use in creating the appropria- All sequence numbers are generated by the destina-
tion simulation environment for our needs. We hope to tion computer in each route table entry, except for the
discover good operational values via simulation for the cases when a link has been broken; the latter case is de-
following quantities: scribed by an co metric and a sequence number which
cannot be correctly generated by any destination com-
puter. We have specified that co metric route entries
● Average convergence times
have sequence numbers which are odd numbers, and
sequence numbers generated by each destination com-
● Incremental update period
puter is an even number. By the natural operation of
● Settling time averaging method the protocol, the sequence numbers chosen to represent

243
broken links will be superseded by real routes propa- routing protocol without bouncing effect. In ACM
gated from the newly located destination as soon as SIGCOMM ’89, pages 224-237, September 1989.
possible. Anynewly propagated routes will necessarily
[4] Wim Diepstraten, Greg Ennis, and Phil Be-
use a sequence number greater than what was used for
langer. DF WMAC - Distributed Foundation Wire-
the broken link since the latter sequence number is cho-
less Medium Access Control. IEEE Document
sen to be one more than the last valid route’s sequence
P802.11-93/190, Nov 1993.
number. This allows real route data to quickly super-
sede temporary link outages when a mobile computer
[5] C. Hedrick. Routing Information Protocol. RFC
moves from one place to another. 1058, June 1988.

We have borrowed the existing mechanism of trig-

[6] J. M. Jaffe and F.H. Moss. A responsive dis-
gered updates to make sure that pertinent route table
tributed routing algorithm for computer networks.
changes can be propagated throughout the population
IEEE Transactions on Communications, COM-
of mobile hosts as quickly as possible whenever any
30(7):1758-1762, July 1982.
topology changes are noticed. This includes movement
from place to place, as well as the disappearance of a [7] J. J. Garcia Luna-Aceves. A unified approach
mobile host from the interconnect topology (perhaps as to loop-free routing using distance vectors or link
a result of turning off its power). states. In ACM SIGCOMM, pages 2 12–223, 1989.

In order to combat problems arising with large pop-

[8] J. M. McQuillan, 1. Richer, and E. C. Rosen.
ulations of mobile hosts, which can cause route updates
The new routing algorithm for the ARPANET.
to be received in an order delaying the best metrics until IEEE Transactions on Communications, COM-
after poorer metric routes are received, we have sepa- 28(5):711-719, May 1980.
rated the route tables into two distinct structures. The
actual routing is done according to information kept [9] P. M. Merlin and A. Segall. A failsafe distributed
in the internal route table, but this information is not routing protocol. IEEE ‘llansadions on Commu-
always advertised immediately upon receipt. We have nications, COM-27(9):1280–1287, September 1979.
defined a mechanism whereby routes are not advertised
[10] Charles Perkins. Mobile 1P as seen by the IETF.
until it is likely, based upon past history, that they are
Connezions, pages 2-20, Mar 1994.
stable. This measurement of the settling time for each
route is be biased towards the most recent measure-
[11] M. Schwartz and T.E. Stern. Routing tech-
ments for the purposes of computing an average.
niques used in computer communication networks.

We have found that mobile computers, modeled IEEE Transactions on Communications, COM-
as routers, can effectively cooperate to build ad-hoc 28(4):539-552, April 1980.

networks. We hope to explore further the necessary

[12] Bill Simpson. draft-ietf-mobileip-protocol-03.txt.
application-level support needed to automatically en-
Draft RFC - work in progress, May 1994.
able use of the network-layer route capabilities to pro-
vide simple access to conferencing and workplace tools
for collaboration and information sharing.

9 Acknowledgment

We thank the reviewers for their many valuable com-

ments; also, thanks to Arvind Krishna and Josh Knight
for their suggestions and improvements.

References

[1] C. Alaettino~l~, K. Dussa-Zieger, 1. Matta, A. U.

Shankar, and O. Gudmundsson. Introducing mars,
a routing testbed. ACM C’omputer Communication
Review, 1992.

[2] D. Bertsekas and R. Gallager. Data IVetwonks,

pages 297–333. Prentice-Hall, Inc., 1987.

[3] C. Cheng, R. Riley, S. P. R. Kumar, and J. J.

Garcia-Luna-Aceves. A loop-free Bellman-Ford

244