Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV) for Mobile ComputersCharles E. PerkinsIBM, T.J. Watson Research CenterHawthorne, NY 10562AbstractAn ad-hoc network is the cooperative engagement ofa collection of Mobile Hosts without the required inter-vention of any centralized Access Point. In this paperwe present an innovative design for the operation of suchad-hoc networks. The basic idea of the design is to op-erate each Mobile Host as a specialized router, whichperiodically advertises its view of the interconnectiontopology with other Mobile Hosts within the network.This amounts to a new sort of routing protocol. Wehave investigated modifications to the basic Bellman-Ford routing mechanisms, as specified by RIP [5], tomake it suitable for a dynamic and self-starting networkmechanism as is required by users wishing to utilize ad-hoc networks. Our modifications address some of theprevious objections to the use of Bellman-Ford, relatedto the poor looping properties of such algorithms in theface of broken links and the resulting time dependentnature of the interconnection topology describing thelinks between the Mobile Hosts. Finally, we describethe ways in which the basic network-layer routing canbe modified to provide MAC-layer support for ad-hocnetworks.1 IntroductionRecently, there has been tremendous growth in thesales of laptop and portable computers. These smallercomputers, nevertheless, can be equipped with hun-dreds of megabytes of disk storage, high resolution colordisplays, pointing devices, and wireless communicationsadapters. Moreover, since many of these small (in sizeonly) computers operate for hours with battery power,Permission to copy without fee all or part of this material isgranted provided that the copies are not made or distributed fordirect commercial advantage, the ACM copyright notice and thetitle of the publication and its date appear, and notice is giventhat copying is by permission of the Association of ComputingMachinery. To copy otherwise, or to republish, requires a feeand/or specific permission.SIGCOMM 94 -8/94 London England UK@ 1994 ACM 0-89791 -682-4/94/0008..$3.50Pravin BhagwatComputer Science DepartmentUniversity of MarylandCollege Park, MD 20742users are free to move about at their convenience with-out being constrained by wires.This is a revolutionary development in personal com-puting. Battery powered, untethered computers arelikely to become a pervasive part of our computing in-frastructure. As people begin to have mobile computershandy, for whatever purposes, sharing information be-tween the computers will become a natural requirement.Currently, such sharing is made difficult by the need forusers to perform administrative tasks and set up static,bidirectional links between their computers. However,if the wireless communications systems in the mobilecomputers support a broadcast mechanism, much moreflexible and useful ways of sharing information can beimagined. For instance, any number of people couldconceivably enter a conference room and agree to sup-port communications links between themselves, with-out necessarily engaging the services of any pre-existingequipment in the room (i.e, without requiring any pre-existing communications infrastructure). Thus, one ofour primary motivations is to allow the construction oftemporary networks with no wires and no administra-tive intervention required. In this paper, such a inter-connection between the mobile computers will be calledan ad-hoc network, in conformance with current. usagewithin the IEEE 802.11 subcommittee [4].Ad-hoc networks differ significantly from existingnet works. First of all, the topology of interconnectionsmay be quite dynamic. Secondly, most users will notwish to perform any administrative actions to set upsuch a network. In order to provide service in the mostgeneral situation, we do not assume that every computeris within communication range of every other computer.This lack of complete connectivity would certainly be areasonable characteristic of, say, a population of mo-bile computers in a large room which relied on infraredtransceivers to effect their data communications.Currently, there is no method available which enablesmobile computers with wireless data communicationsequipment to freely roam about while still maintaining234connections with each other, unless special assumptionsare made about the way the computers are situated withrespect to each other. One mobile computer may oftenbe able to exchange data with two other mobile comput-ers which cannot themselves directly exchange data. Asa result, computer users in a conference room may beunable to predict which of their associates’ computerscould be relied upon to maintain network connection,especially as the users moved from place to place withinthe room.Routing protocols for existing networks have notbeen designed specifically to provide the kind of dy-namic, self-starting behavior needed for ad-hoc net-works. Most protocols exhibit their least desirable be-havior when presented with a highly dynamic inter-connection topology. Although we thought that mo-bile computers could naturally be modeled as routers,it was also clear that existing routing protocols wouldplace too heavy a computational burden on each mobilecomputer. Moreover, the convergence characteristics ofexisting routing protocols did not seem good enoughto fit the needs of ad-hoc networks. Lastly, the wire-less medium differs in important ways from wired me-dia, which would require that we make modifications towhichever routing protocol we might choose to exper-iment with. For instance, mobile computers may wellhave only a single network interface adapter, whereasmost existing routers have network interfaces to connecttwo separate networks together, Besides, wireless mediaare of limited and variable range, in distinction to exist-ing wired media. Since we had to make lots of changesanyway, we decided to follow our ad-hoc network modelas far aa we could and ended up with a substantiallynew approach to the classic distance-vector routing.2 Overview of Routing MethodsIn our environment, the problem of routing is essen-tially the distributed version of the shortest path prob-lem [11]. Each node in the network maintains for eachdestination a preferred neighbor. Each data packet con-tains a destination node identifier in its header. Whena node receives a data packet, it forwards the packetto the preferred neighbor for its