Associativity-based routing

Introduction

Associativity-Based Routing (commonly known as ABR) is a mobile routing protocol invented for wireless ad hoc networks. ABR was invented in 1993, filed for a USA patent in 1996, and granted the patent in 1999. ABR was invented by Chai Keong Toh while doing his Ph.D. at Cambridge University. In the 1990s, our Internet is still largely wired. Toh was working on a different Internet - that of a rapidly deployable, self-organizing, self-configuration mobile Internet. The challenges in such a network is mobility of nodes and link dynamics.

Toh's prime argument is that there is no point in choosing a node to route packets if the route is unstable or going to be broken soon. So, he introduced the concept of associativity, i.e., link stability among nodes over TIME and SPACE. Hence, ABR was born.

Explanation

ABR is an on-demand routing protocol, i.e., routes are created only as and when needed. This, in contrast, to the existing Internet where routes are immediately available and routing tables are constantly updated. According to the publications, on-demand routing is chosen because it can reduce the amount of traffic and bandwidth is particularly limited in a wireless network.

ABR Route Discovery Phase

ABR has 3 phases. The first phase is Route Discovery Phase. When a user initiates to transmit data, the protocol will intercept the request and broadcast a search packet over the wireless interfaces. As the search packet propagates node to node, node identity and stability information are appended to the packet. When the packet eventually reaches the destination node, it would have received all the information describing the path from source to destination. When that happens, the destination then chose the best route (because there may be more than one path from the source to the destination) and send a REPLY back to the source node, over the chosen path.

Note that when the packet transits backwards from destination to the source, each intermediate nodes will update their routing table, signifying that it will now know how to route when it receives data from the upstream node. When the source node receives the REPLY, the route is successfully discovered and established. This process is done in real-time and only takes a few milli-seconds.

ABR Route Reconstruction Phase

Because ABR chooses route that are long-lived or associativity-stable, most route so established will seldom experience link breaks. However, if one or more links are broken, there ABR will immediately respond and invoked the RRC - route reconstruction phase. The RRC basically repair the broken link will having the upstream node (which sense the link break) to do a localized route repair. The localized route repair is in the form of localized broadcast query, in the search for an alternative long-lived partial route to the destination.

ABR route maintenance consists of: (a) partial route discovery, (b) invalid route erasure, (c) valid route update, and (d) new route discovery (worse case).

==AR Route