Associativity-based routing: Difference between revisions

Revision as of 15:21, 27 November 2016

Revision as of 00:44, 28 November 2016

Line 1:

'''Associativity-Based Routing'''<ref>{{citation |title="Associativity-based routing for ad hoc mobile networks" |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:d1gkVwhDpl0C}}</ref><ref>{{citation |title="A novel distributed routing protocol to support ad-hoc mobile computing" |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:2osOgNQ5qMEC}}</ref><ref name="auto">[[Chai Keong Toh]] Ad Hoc Mobile Wireless Networks, Prentice Hall Publishers, 2002. ISBN 978-0-13-007817-9</ref><ref>{{citation |title="Long-lived ad-hoc routing based on the concept of Associativity" |url=https://scholar.google.com/citationsview_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:YsMSGLbcyi4C}}</ref> (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, 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.

Line 18:

This, in contrast, to the existing Internet where routes are immediately available and routing tables are constantly updated among routers. According to the publications,<ref name="auto"/> 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 Route Discoverydiscovery Phasephase==

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.

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.

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 Reconstructionreconstruction Phasephase==

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

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.

Line 47 ⟶ 37:

*(d) new route discovery (worse case).

==AR Route Deletiondeletion Phasephase==

When a discovered route is no longer needed, a RD (Route Delete) packet will be initiated by the source node

Line 57 ⟶ 47:

period of time.

==ABR Practicality==

In 1998, ABR was successfully implemented<ref>{{citation |title="Mobile Computing Magazine Interview Article, 1999 |url=http://init.unizar.es/images/MobiCompMag1999.pdf}}</ref><ref>{{citation |title="Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks" |url=https://www.semanticscholar.org/paper/Implementation-and-evaluation-of-an-adaptive-Toh-Lin/422dbbb6a624855a4636bed56c65e0d1278f9e6a}}</ref><ref>{{citation |title="Evaluating the communication performance of an ad hoc wireless network" |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:WF5omc3nYNoC}}</ref><ref>{{citation |title="Experimenting with an Ad Hoc wireless network " |url=http://dl.acm.org/citation.cfm?id=377622}}</ref> into Linux kernel, in various different branded laptops (IBM Thinkpad,

Line 67 ⟶ 57:

*[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<ref>{{citation |title="Transporting Audio over Wireless Ad Hoc Networks" |url=https://hub.hku.hk/bitstream/10722/46490/1/92280.pdf?accept=1}}</ref> and video)

*[7] [[TELNET]] over Ad Hoc

Line 95 ⟶ 85:

clustering to scale to 100,000 or more large scale ad hoc networks.

==ABR Patent &and Applicationsapplications==

ABR was granted a US patent 5987011<ref>{{citation |title="A Routing Method for Ad Hoc Mobile Networks" |url=https://www.google.com/patents/US5987011}}</ref> and the assignee being [[King's College Cambridge]], UK. ABR was subsequently licensed to a US defense corporation.

Line 136 ⟶ 126:

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

==ABR 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'''),<ref>{{citation |title="Signal stability based adaptive routing (SSA) for ad-hoc mobile networks"|url=http://dl.acm.org/citation.cfm?id=241244}}</ref> Enhanced Associativity Based Routing Protocol ('''EABR'''),<ref>{{citation |title="Enhanced Associativity Based Routing Protocol"|url=http://thescipub.com/PDF/jcssp.2006.853.858.pdf}}</ref> Alternative Enhancement of Associativity-Based Routing ('''AEABR'''),<ref>{{citation |title="Alternative Enhancement of Associativity-Based Routing"|url=http://link.springer.com/chapter/10.1007%2F978-3-642-11817-3_7#page-1

}}</ref> Optimized Associativity Threshold Routing ('''OABTR'''),<ref>{{citation |title="Optimized Associativity Threshold Routing"|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8653&rep=rep1&type=pdf}}</ref> Cluster Based Enhanced Associativity-Based Routing ('''CBE-ABR'''),<ref>{{citation |title="CBE-ABR: A Cluster Based Enhanced Routing Protocol for Ad Hoc Mobile Networks" |url=http://airccse.org/journal/cnc/1009s5.pdf}}</ref> Associativity-Based Clustering Protocol ('''ABCP'''),<ref>{{citation |title="Associativity-Based Clustering Protocol for Mobile Ad Hoc Networks" |url=https://jan.newmarch.name/conferences/ccnc05/DATA/1-N03-04.PDF}}</ref>, Stability-Based Multihop Clustering ('''SBMC''')<ref>{{cite |title="Stability-Based Multi-Hop Clustering Protocol" |url=http://s3.amazonaws.com/academia.edu.documents/43823278/Stability-based_multi-hop_clustering_pro20160317-32218-jdn2wu.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1480260646&Signature=p5yhUuqrcgQ5iZAIeUQmmgN%2BPGs%3D&response-content-disposition=inline%3B%20filename%3DStability-Based_Multi-Hop_Clustering_Pro.pdf}}</ref>, Associativity-Based Energy Aware Clustering ('''AB-EAC''')<ref>{{cite |title="An Associativity Based Energy Aware Clustering Technique for Mobile Ad Hoc Networks" |url=http://link.springer.com/chapter/10.1007/978-3-642-14493-6_37}}</ref>, Fuzzy Based Trust Associativity-Based Routing ('''Fuzzy-ABR'''), Associativity Tick Averaged Associativity-Based Routing ('''ATA-AR'''),<ref>{{citation |title="Associativity Tick Averaged Associativity-Based Routing for Realtime Mobile Networks" |url=http://www.emo.org.tr/ekler/8a07694d909694a_ek.pdf}}</ref> Self-adaptive Q-learning based trust ABR ('''QTABR'''),<ref>{{citation |title="Self-Adaptive Trust Based ABR Protocol for MANETs Using Q-Learning" |url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4164804/}}</ref> Quality of Service Extensions to ABR ('''QoSE-ABR'''),<ref>{{citation |title="Adding Quality of Service Extensions to the Associativity Based Routing Protocol for Mobile Ad Hoc Networks"|url=http://dl.acm.org/citation.cfm?id=1487990}}</ref> TABU Search Initiated Associativity-Based Routing ('''TIG-ABR'''),<ref>{{citation |title="Improved Associativity Based Routing for Multi Hop Networks Using TABU Initialized Genetic Algorithm" |url=http://www.ripublication.com/ijaer16/ijaerv11n7_28.pdf}}</ref> Associativity-based Multicast Routing ('''ABAM'''),<ref>{{citation |title="ABAM: On-Demand Associativity-Based Multicast" |url=https://www.researchgate.net/publication/3874369_ABAM_On-Demand_Associativity-Based_Multicast_Routing_for_Ad_Hoc_Mobile_Networks}}</ref> Multipath Associativity Based Routing ('''MABR'''),<ref>{{citation |title="Multipath Associativity Based Routing"|url=http://dl.acm.org/citation.cfm?id=1044034}}</ref> and so on. The stability concept is also applied to [[wireless sensors network]]<ref>{{citation |title="Associative routing for wireless sensor networks" |url=http://www.sciencedirect.com/science/article/pii/S0140366411000326}}</ref> and VANETs -– [[Vehicular Ad Hoc Network]].<ref>{{citation |title="A Stable Routing Protocol for Vehicles in Urban Environments" |url=http://dsn.sagepub.com/content/9/11/759261.full}}</ref>

==References==