Abstract-In this paper, we show that the use of dynamic addressing can enahle ralahle routing in ad hoc networks. It ic well known that the current ad linc protocol suites do not scale to wnrk efficiently in networks of more then n few hundred nodes. Most current ad hoc routing architectures use Rat static addresing and thus. need to keep track of each node individually, Creating a massive averhead prnhleni as the network grows. Could dynamic addressing alleviate this prohlem? To bogin to answer this question. we provide an initial design of a routing layer hawd on dynamic addressing, and evaluute its performance. Each node has a unique permunent identifier and B transient routing address. which indicates its location in the network at any given time. The main challenge is dynamic address allocation in the face of node niohility. We prnpmse mechanisms to implement dynamic addresing efficiently. Our initial evaluation suggests that dynamic addressing is a proniisisg apprnach for achieving scalahle muting in mrguntnle ad hoc networks. ' Scalability is a critical requireincnt i n the use and deployment of ad hoc networks. ii we \ w i t this technoloey to reach its full potential. Ad hoc netwmkiiig ~ccliiiolo:y is receiving , a lot of interest but it has ye( to nature. This is similar to the early stages of the Internet. where very few could predict its explosive growth. A difference is that in the Internet. scalability wds. from the very beginning. a design constraint. Ad hoc networks research seems to have downplayed the importance of scalability. In fact. current ad hoc architectures do not scale well beyond a iew hundred nodes. How can we make ad hoc networks scale to thousands. or even millions of nodes? We find this question fundamental if we want ad hoc technology to be successful in the consumer marketplace. Already. non-military technology and applications seem to point towards fkture networks with: a) ad hoc pockets of connectivity [I]. b) consumer-owned networks [?I 131 141. and c) sensor-net technologies [51. All of these applications will place increased scalability demands on ad hoc routing Most current research in ad hoc networks focus more on performance and power-consumption related issues in relatively small networks. and less o n scalability. The current routing protocols and. architectures work well only up to a few hundred nodes. We believe the main reason behind the ' protocols. . lack of scalability is that these protocols rely on flat and static addressing. With scalahility as a partial goal. some efforts have been made in the direction of hierarchical routing and clustering [6] [7] [SI. These approaches do hold promise. hut they do not seem to be actively pursued. It appears to us as if these protocols would work well in scenarios with group mobility [9], which is also a common assumption among cluster based routing protocols. Is dynamic addressing a feasible way of achieving scalable ad hoc routing'? This is the question that we address in this work. Dynamic addressing simplifies routing but introduces two new problems: address allocation. and address lookup. Here. we focus on the address allocation part; earlier work describes a' general idea of how address lookup e m be efficiently handled [IO]. AS a guideline. we identify a set of properties that a scalable and efficient solution must have: Localization cf ovrrheafl: a local change should affect only the immediate neighborhood, thus limiting the overall overhead incurred due to the change. . Lighhwight. rlecPnrrali.-Pd protocols: we would like to avoid concentrating responsibility at any individual node. and we want to keep the necessary state to be maintained at each node as small as possible. -Zero-coii~~i~ration: we want to completely remnve the need for manual configuration beyond what can be done at the time of manufacture. In this paper. we evaluate dynamic addressing and show that it is a prom,ising first step toward achieving scalability in the order of millions of nodes in ad hoc routing. First. we develop a dynamic addressing scheme.' which has thc , necessary properties mentioned above. Our scheme separates node identity from node address. and uses the address to indicate the node's current location in the network. Second. we study the performance of a new routing protocol. based on dynamic addressing. through analysis and simulations. In more detail. our work leads to the following results. Our address allocation scheme uses the address space efficiently on topologies of randomly and uniformly disuihuted nodes. empirically resulting in average routing
The feasibility of routing based on dynamic addresses is examined in REF .
Scalable ad hoc routing: the case for dynamic addressing
IEEE INFOCOM 2004
IEEE INFOCOM 2004
Computer Science