Associativity-based routing

Associative-based routing (commonly known as ABR) is a mobile routing protocol invented for wireless ad hoc networks or also known as ad hoc mobile networks (MANETs) and wireless mesh networks. ABR was invented in 1993, filed a US patent in 1996 and was granted the patent in 1999. ABR was invented by Chai Keong Toh during his PhD. at the University of Cambridge. In the 1990s, our Internet was still largely wired. Toh was working on another Internet – that of a mobile Internet quickly deployable, without infrastructure, self-organized and self-configurable. The challenges in such a network are the mobility of the nodes and the dynamics of the links. Toh’s main argument is that there is no point in choosing a node to route packets if the route is unstable or will soon be broken. Thus, he introduced a new routing metric (known as associativity ticks) and the concept of associativity, that is, the link stability between nodes on TIME and SPACE. Therefore, ABR is born.

In the early 1990s, the Internet is still largely wired. To reach computers at all times, computers must be able to connect wirelessly and automatically. The Internet protocol at the time did not deal with mobility and the formation of a rapidly deployable mobile Internet. The underlying protocols for the Internet were TCP / UDP / IP. These protocols do not support spontaneous network creation and do not handle the dynamics of computer mobility. The assumption was that the final hosts are static hosts, and they do not move. Another assumption was that the network is wired (with copper wires or fiber). Since existing Internet protocols can not support ad hoc mobile computing, a new mobile Internet is needed. This requires a new network layer software that will allow mobile computing at any time and anywhere, while maintaining compatibility with the IP / UDP / TCP protocols already present in the wired Internet. ABR is an on-demand routing protocol, that is, routes are created only as and when needed. This, in contrast, to the existing Internet where routes are immediately available and the routing tables are constantly updated between routers. According to the publications, on-demand routing is chosen because it can reduce the amount of control packet traffic and this is appropriate for a wireless network because the bandwidth is limited.

ABR has three phases. The first phase is the discovery phase of the itinerary. When a user initiates data transmission, the protocol intercepts the request and broadcasts a search packet on the wireless interfaces. As the search packet propagates a node to a node, node identity and stability information is added to the packet. When the packet finally reaches the destination node, it would have received all the information describing the path from the source to the destination. When this happens, the destination then chooses the best route (because there may be more than one path between source and destination) and returns a response to the source node on the chosen path. Note that as the packet moves back from the destination to the source, each intermediate node updates its routing table, which means that it will now know how to route when it receives data from the upstream node. When the source node receives the REPLY message, the route is successfully discovered and established. This process is done in real time and only takes a few milliseconds.

ABR establishes routes that are long-lived or associativity-stable, thus most routes established will seldom experience link breaks; however, if one or more links are broken, their ABR will immediately invoke the RRC – route reconstruction phase. The RRC basically repairs the broken link by having the upstream node (which senses the link break) perform a localized route repair. The localized route repair is performed by carrying out a localized broadcast query that searches for an alternative long-lived partial route to the destination. ABR route maintenance consists of:

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.

In 1998, ABR was successfully implemented 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:

ABR has obtained US Patent 5987011 and Assignee King’s College Cambridge, UK. ABR was later licensed to a US defense company. Ad Hoc tactical mobile networks are flourishing with US defense spending of more than $ 2 billion on programs and research from DARPA, DoD, Air Force, Coast Guard and US Navy. In October 2013, the Storm Disaster Sandy hit the United States and the US Coast Guards used ad hoc mobile network technology to quickly establish networks to facilitate rescue operations. Many lives have been saved. As part of the US-led Operation Enduring Freedom in the wars against Afghanistan, tactical ad hoc mobile communications are used on the battlefield. At the global level, national science and defense organizations in other countries have also invested heavily in research programs related to ad hoc mobile networks. These countries include the United States, United Kingdom, Canada, Sweden, Singapore, Australia, Germany, Norway, France, Switzerland, Taiwan, Japan, Korea, China, Spain, Italy, Denmark, Finland, etc. Many industries have since contributed to the development of ad hoc tactical mobile radios and networking products, including:

Several other mobile ad hoc routing protocols have incorporated the ABR stability concept or have extensions and enhancements to ABR, such as the Adaptive Routing Protocol (SSA) based on signal stability, the Enhanced Associativity Routing protocol. Protocol (EABR). Membership-Based Routing (AEABR), Optimized Associativity Threshold Routing (OABTR), Cluster-Based Associativity Based Routing (CBE-ABR), Associative-Based Clustering (ABCP), Clustering-based Clustering associativity and Query Stride (ABC-QS), associative-based Multi-base Stability Clustering (SBMC), associativity-based AB (EAC) clusters, Fuzzy-based Fuzzy-based associativity-based routing ABR, associativity Tick Rationalization based on averaged associativity (ATA-AR), ABR self-adaptive Q (QTABR), ABR QoS extensions (QoSE-ABR), associative search-based routing TABU (TIG-ABR), associative-based multicast routing (ABAM), based on routing multipath associativity (MABR), and so on. The concept of stability is also applied to wireless sensor networks and vehicular ad-hoc networks (VANETs).

Leave a Comment

Your email address will not be published. Required fields are marked *