Automatic incremental routing using multiple roots

We present Multi-root Automatic Incremental Routing (MAIR), an efficient routing approach for mobile ad hoc networks (MANET). MAIR has a low routing stretch (ratio of selected path to shortest path length) and provides multiple paths to each destination. Every node is assigned multiple prefix labels with respect to multiple roots in the network. The roots are distributed in the network such that the paths calculated from each of the root labels are as disjoint as possible from each other. The labels of a node are stored distributively in hash tables at “anchor nodes” across the network. Data packets are routed using the distributed hash table (DHT) lookup and longest prefix match with neighbor labels. This eliminates the need to maintain large routing tables in the nodes, which substantially reduces the routing state at each node. A region of interest (ROI) is formed around each active source-destination pair using the node labels. The nodes in the ROI maintain the most recent mapping of the node identifier of a destination to its labels. This reduces the route establishment delay for the nodes inside ROI as the need for DHT lookup is reduced.