Associativity-Based Routing

Associativity-Based Routing (commonly known as ABR) is a mobile routing protocol invented for wireless ad hoc networks or also known as Mobile Ad Hoc Networks (MANETs) and Wireless Mesh Network. 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, infrastructureless, self-organizing, self-configuring 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 a new routing metric (known as associativity ticks) and the concept of associativity, i.e., link stability among nodes over TIME and SPACE. Hence, ABR was born.

In the early 1990s, the Internet is still largely wired. To achieve anytime anywhere computing, computers must be able to connect to each other wirelessly and automatically. The at that time did not address mobility, and the formation of an rapidly deployable mobile Internet. The underlying protocols for Internet were TCP/UDP/IP. Those protocols do not support spontaneous network creation, and do not handle dynamics due to mobility of computers. The assumption was end hosts are static hosts, and they do not move. Another assumption was the network is wired (with copper wires or fiber).

Since existing Internet protocols cannot support ad hoc mobile computing, a new mobile Internet is needed. This calls for a new network layer software that will enable anytime and anywhere mobile computing, while at the same time, retaining compatibility with IP/UDP/TCP protocols already present in the wired Internet. 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 among routers. According to the publications, on-demand routing is chosen because it can reduce the amount of control packet traffic and this is suitable for a wireless network because bandwidth is limited.

ABR has three phases. The first phase is the 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.

...
Wikipedia