Associativity-Based Routing

Associativity-Based Routing^[1][2][3][4] (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.

Explanation

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 Internet Protocol 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 host are static host, 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 need. This calls for a new network layer software that will enable anytime and anywhere mobile computing, while at the same time, retains 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,^[3] 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.

Route discovery phase

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.

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.

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 invoke the RRC – route reconstruction phase. The RRC basically repairs the broken link by having the upstream node (which sense the link break) doing 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).

Route deletion phase

When a discovered route is no longer needed, a RD (Route Delete) packet will be initiated by the source node so that all intermediate nodes in the route will update their routing table entries and stopped relay data packets associated with this deleted route.

In addition to using RD to delete a route, ABR can also implement a soft state approach where route entries are expired or invalidated after timed out, when there is no traffic activity related to the route over a period of time.

Practicality

In 1998, ABR was successfully implemented^[5][6][7][8] into Linux kernel, in various different branded laptops (IBM Thinkpad, COMPAQ, Toshiba, etc) that are equipped with WaveLAN 802.11a PCMCIA wireless adapters. A working 6-node wide wireless ad hoc network spanning a distance of over 600 meters was achieved and the successful event was published in Mobile Computing Magazine in 1999. Various tests were performed with the network:

• [1] Transmission of up to 100MBytes of data from source to destination over 3-hop route.
• [2] Link breaks and automatic link repairs proven to be working
• [3] Automatic Route Discovery
• [4] Route Delete
• [5] Web Server in Ad Hoc mode – with source being client and destination being the web server
• [6] Transmission of multimedia information (audio^[9] and video)
• [7] TELNET over Ad Hoc
• [8] FTP over Ad Hoc
• [9] HTTP over Ad Hoc

Also, network performance measurements on the following were made:

• [1] End-to-end delay
• [2] TCP throughput
• [3] Packet loss ratio
• [4] Route discovery delay
• [5] Route repair delay

In 2002, TRW Tactical Systems Incorporation implemented^[10] an enhancement of the ABR protocol and successfully implemented on ORiNOCO WaveLAN 802.11b over an X windows system running Linux 5.2 Operating System on DELL laptops. The implementation and field test were done in an outdoor setting in Carson, California over a 6-node ad hoc network. The enhancement made to the protocol include:

• Network layer QoS
• Route precedence
• Route pre-emption

TRW investigators successfully transmitted 10Gbytes of large files, and did tests on route discovery, route repair, and measurements on delays. They recommended the use of Multi-Input Multi-Output (MIMO) spectrum-aware MAC and the consideration of logical clustering to scale to 100,000 or more large scale ad hoc networks.

Patent and applications

ABR was granted a US patent 5987011^[11] and the assignee being King's College Cambridge, UK. ABR was subsequently licensed to a US defense corporation. Tactical Mobile Ad Hoc Networks bloom with US defense spending^[12] over $2 Billion in programs and research by DARPA, DoD, Air Force, Coast Guards, and US Navy.^[13]

In October 2013, the Storm Disaster Sandy hit the USA, and US Coast Guards used mobile ad hoc networking technology to quickly established networks to facilitate rescue operations. Many lives were saved.^[14]

In US Operation Enduring Freedom on wars with Afghanistan, tactical ad hoc mobile communications is used in the battlefield.^[15]

Globally, defense and national science organizations in other countries have also invested heavily on research programs related to mobile ad hoc networks. Such countries include USA, UK,^[16] Canada, Sweden, Singapore, Australia,^[17] Germany, Norway,^[18] France, Switzerland, Taiwan, Japan, Korea, China, Spain, Italy, Denmark, Finland, etc.

Many industries have since contributed to the development of tactical ad hoc mobile radios and networking products, including:

• Harris
• BBN
• Raytheon
• Cisco
• Thales
• MeshDynamics
• Persistent Systems
• Rockwell Collins
• ITT Defense
• XES Inc.,
• Lockheed Martin
• Northrop Grumman
• General Dynamics
• SAIC
• BAE

In 2009, DARAP awarded $155Million^[19] contract to Raytheon to work on mobile ad hoc networking gateway. In 2002, 2012 and 2013, DoD awarded General Dynamics $75Million, $346Million and $475Million^[20] to work on WIN-T Phase 1, Phase 2 and Phase 3 respectively. WIN-T itself is a $6Billion^[21] program. In 2015, US Special Operations has awarded $390Million^[22] contract to Harris to build tactical radios with mobile ad hoc networking capability.

Descendants

Quite a few other mobile ad hoc routing protocols have incorporated ABR's stability concept or have done extensions and enhancement of ABR, such as Signal Stability-based Adaptive Routing Protocol (SSA),^[23] Enhanced Associativity Based Routing Protocol (EABR),^[24] Alternative Enhancement of Associativity-Based Routing (AEABR),^[25] Optimized Associativity Threshold Routing (OABTR),^[26] Cluster Based Enhanced Associativity-Based Routing (CBE-ABR),^[27] Associativity-Based Clustering Protocol (ABCP),^[28] Stability-Based Multihop Clustering (SBMC),^[29] Associativity-Based Energy Aware Clustering (AB-EAC),^[30] Fuzzy Based Trust Associativity-Based Routing (Fuzzy-ABR), Associativity Tick Averaged Associativity-Based Routing (ATA-AR),^[31] Self-adaptive Q-learning based trust ABR (QTABR),^[32] Quality of Service Extensions to ABR (QoSE-ABR),^[33] TABU Search Initiated Associativity-Based Routing (TIG-ABR),^[34] Associativity-based Multicast Routing (ABAM),^[35] Multipath Associativity Based Routing (MABR),^[36] and so on. The stability concept is also applied to wireless sensor networks^[37] and vehicular ad hoc networks (VANETs).^[38]

References