DART - Dynamic Address Routing
The DART-Project was created by Jakob Eriksson, Michalis Faloutsos and Srikanth Krishnamurthy from the University of California, Riverside. Its former name was PeerNet.
How large can an ad-hoc network be? Current ad hoc routing architectures do not scale well and work inefficiently in networks of more than a few hundred nodes. Those routing protocols use static addressing which leads to a massive overhead problem in mobile networks as the number of nodes grows. The main idea behind DART is to seperate node's address and identity. DART satisfies the following properties which can be seen as guideline for a scalable and efficient solution:
- Localization of overhead
- Lightweight, decentralized protocols
- Minimal restrictions on hardware
Using dynamic addressing and appropriate routing, DART is a promising approach for achieving scalable routing in large ad hoc networks.
Identity & Address
The identity of a peer is a static number which is globally unique and stays the same throughout the lifetime of the node. The address of a node is represented by a k-bit number. It is dynamic and changes with node movement. Moreover, the address has a topological meaning since its current value reflects the node's location. The "address-disparate-identity" paradigma is totally opposed to traditional network protocols as IP.
Assuming a balanced address tree, on average a routing table consists of O(logn) entries (n = number of nodes). A peer propagates its routing entries to its neighbors by periodic updates.
An important question is how to find a node's current address. One promising approach is to use a distributed node lookup table shared by all nodes to store the <identifier, address> pairs. A node that stores the address of node Y is called Y's anchor node. A globally, a priori known hash function h(x) calculates the address of the anchor node for the peer with identifier x. According to this hash function h(x) new nodes propagate their addresses to their anchor nodes, which in turn propagate them to requesting peers. If the address returned by h(x) is unoccupied, then the address with the least edit distance is chosen and its corresponding peer becomes the anchor node.
Dynamic Address Allocation
When a node joins the network, it needs to gain a legitimate address. Listening to the periodic routing updates of its neighbors, the new node looks for the neighbor with the largest unoccupied address block and picks an address from that block. Obviously the Prefix Subgraph Constraint is satisfied. But what happens, if to mutual invisible nodes join the network and pick out address with the same prefix? In that case, the Prefix Subgraph Constraint is violated. Through periodic routing updates their adresses are propagated into the network. The first node that receives the conflicting information to that address subtree, compares the identifiers of the subtrees and drops the subtree with the higher ID. Listening to its neighbors updates the node with the invalid address learns about the conflict and chooses a new address. Large address space is used to prevent refusing new node's request because of address congestion. Furthermore, address tree balancing is a technique to migrate nodes from highly congested adress spaces to less one without violating the Prefix Subgraph Constraint. Eventually high degree of congestion can lead to address space expansion.
- DART: Dynamic Address RouTing for Scalable Ad Hoc and Mesh Networks (by Eriksson, Faloutsos, Krishnamurthy)
- PeerNet: Pushing Peer-To-Peer Down the Stack (by Eriksson, Faloutsos, Krishnamurthy)