DART - Dynamic Address Routing: Difference between revisions
| Line 14: | Line 14: | ||
== Address space == |
== Address space == |
||
[[Image:AddressTree.JPG|thumb|300px|The Address Tree of a 3-bit binary address]] The ''Address Tree'' is an abstract visualization from the address space point of view. Its leaves represent peers in a network by their addresses. Its inner nodes represent address subtrees. An address subtree consists of nodes with the same address prefix. The dotted lines in the image indicate physical links (wired or wireless) between participating nodes. Nodes of the same subtree are physically connected. Dotted leaves illustrate currently unused addresses. |
[[Image:AddressTree.JPG|thumb|300px|The Address Tree of a 3-bit binary address]] The ''Address Tree'' is an abstract visualization from the address space point of view. Its leaves represent peers in a network by their addresses. Its inner nodes represent address subtrees. An address subtree consists of nodes with the same address prefix. The dotted lines in the example image indicate physical links (wired or wireless) between participating nodes. Nodes of the same subtree are physically connected. Dotted leaves illustrate currently unused addresses. |
||
Revision as of 15:40, 9 August 2007
The DART-Project was created by Jakob Eriksson, Michalis Faloutsos and Srikanth Krishnamurthy from the University of California, Riverside. Its former name was PeerNet.
Motivation
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
- Zero-configuration
- Minimal restrictions on hardware
Using dynamic addressing and appropriate routing, DART is a promising approach for achieving scalable routing in large ad hoc networks.
Principles
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.
Address space
The Address Tree is an abstract visualization from the address space point of view. Its leaves represent peers in a network by their addresses. Its inner nodes represent address subtrees. An address subtree consists of nodes with the same address prefix. The dotted lines in the example image indicate physical links (wired or wireless) between participating nodes. Nodes of the same subtree are physically connected. Dotted leaves illustrate currently unused addresses.
The Network Topology view represents the connectivity between nodes. A crucial constraint (Prefix Subgraph Constraint) is that all nodes that share a given address prefix form a connected sugraph in the network topology. This implies a coherence between address prefix length and distance between nodes. The longer the address prefix of a subgraph in the address tree, the shorter the expected distance between the nodes that share this prefix.
Another important abstract view is the Sibling view. A address tree of a l-bit address consists of 2 Level-(l-1)-subtrees, 4 Level-(l-2)-subtrees and so on. Leaves are Level-0-subtrees. Each l-bit address has l Level-k-siblings. In the example network the node with address 100 has one Level-0-sibling with the address (prefix) 101 (this sibling is only represented by the node with the same address 101), a Level-1-sibling with the address prefix 11x and Level-2-sibling (0xx).