Associativity-based routing

From HandWiki

Associativity-based routing[1][2][3][4] (commonly known as ABR) is a mobile routing protocol invented for wireless ad hoc networks, also known as mobile ad hoc networks (MANETs) and wireless mesh networks. ABR was invented in 1993, filed for a U.S. patent in 1996, and granted the patent in 1999. ABR was invented by Chai Keong Toh while doing his Ph.D. at Cambridge University.

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 chooses the best route (because there may be more than one path from the source to the destination) and sends 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 node 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

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:

  • (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 stop 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 the 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 500MBytes of data from source to destination over a 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
  6. Impact of packet size on throughput
  7. Impact of beaconing interval on throughput and remaining battery life

An enhanced version of the protocol was implemented in the field[10] by defense contractor TRW Inc. in 2002. The enhancement made to the protocol include: (a) network-layer QoS additions and (b) route precedence capabilities.

Patent and work extensions

ABR was granted a US patent 5987011[11] and the assignee being King's College, Cambridge, UK.

A few other mobile ad hoc routing protocols have incorporated ABR's stability concept or have done extensions of the ABR protocol, including:

  • Signal Stability-based Adaptive Routing Protocol (SSA)[12]
  • Enhanced Associativity Based Routing Protocol (EABR)[citation needed]
  • Alternative Enhancement of Associativity-Based Routing (AEABR)[13]
  • Optimized Associativity Threshold Routing (OABTR)[14]
  • Associativity-Based Clustering Protocol (ABCP),[15]
  • Fuzzy Based Trust Associativity-Based Routing (Fuzzy-ABR)
  • Associativity Tick Averaged Associativity-Based Routing (ATA-AR),[16]
  • Self-adaptive Q-learning based trust ABR (QTABR)[17]
  • Quality of Service Extensions to ABR (QoSE-ABR)[18]
  • Associativity-based Multicast Routing (ABAM)[19]
  • Multipath Associativity Based Routing (MABR)[20]
  • Associativity routing for Wireless Sensor Networks [21]
  • Associative Vehicular Ad Hoc Networks (VANETs) [22]

References

  1. ↑ Toh, Chai-Keong (March 1997). "Associativity-based routing for ad hoc mobile networks". Wireless Personal Communications 4 (2): 103–139. doi:10.1023/A:1008812928561. https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:d1gkVwhDpl0C. 
  2. ↑ Toh, Chai-Keong (March 1996). "A novel distributed routing protocol to support ad-hoc mobile computing". https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:2osOgNQ5qMEC. 
  3. ↑ Toh, Chai-Keong (December 2001). Ad Hoc Mobile Wireless Networks. Prentice Hall. ISBN 978-0-13-007817-9. 
  4. ↑ Long-lived ad-hoc routing based on the concept of Associativity, IETF Draft 1999, https://www.ietf.org/proceedings/46/I-D/draft-ietf-manet-longlived-adhoc-routing-00.txt 
  5. ↑ "Mobile Computing Magazine Interview Article - First practical ad hoc wireless network implementation outdoors, 1999, http://init.unizar.es/images/MobiCompMag1999.pdf 
  6. ↑ Toh, C.-K.; Lin, G.; Delwar, M. (2000), "Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks", Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks, Proceedings of 9th International Conference on Computer Communications and Networks, 2000., pp. 20–27, doi:10.1109/ICCCN.2000.885465, ISBN 978-0-7803-6494-3 
  7. ↑ Evaluating the communication performance of an ad hoc wireless network, IEEE Transactions on Wireless Communications, 2000, https://scholar.google.com/citations?view_op=view_citation&hl=en&user=YTwSsH4AAAAJ&citation_for_view=YTwSsH4AAAAJ:WF5omc3nYNoC 
  8. ↑ Toh, C.-K.; Chen, Richard; Delwar, Minar; Allen, Donald (2000), "Experimenting with an Ad Hoc wireless network, ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, Dec. 2000", ACM SIGMETRICS Performance Evaluation Review 28 (3): 21–29, doi:10.1145/377616.377622 
  9. ↑ Transporting Audio over Wireless Ad Hoc Networks, Proc. International Conference on Personal, Indoor And Mobile Radio Communications, Pimrc, 2003, v. 1, p. 772-777, https://hub.hku.hk/bitstream/10722/46490/1/92280.pdf?accept=1 
  10. ↑ "Next-Generation Tactical Ad Hoc Mobile Wireless Networks". TRW Technology Review Journal. 2004. https://drive.google.com/file/d/1LJotUZzeYZxHUg1F8YMm2zS5OdNKgguQ/view. 
  11. ↑ A Routing Method for Ad Hoc Mobile Networks, US Patent 5987011, granted 1996, filed 1994., https://www.google.com/patents/US5987011 
  12. ↑ Dube, Rohit; Rais, Cynthia D.; Wang, Kuang-Yeh; Tripathi, Satish K. (1996), Signal stability based adaptive routing (SSA) for ad-hoc mobile networks, http://dl.acm.org/citation.cfm?id=241244 
  13. ↑ Alternative Enhancement of Associativity-Based Routing, 2009, doi:10.1007/978-3-642-11817-3_7 
  14. ↑ Optimized Associativity Threshold Routing 
  15. ↑ Associativity-Based Clustering Protocol for Mobile Ad Hoc Networks, https://jan.newmarch.name/conferences/ccnc05/DATA/1-N03-04.PDF 
  16. ↑ Associativity Tick Averaged Associativity-Based Routing for Realtime Mobile Networks, http://www.emo.org.tr/ekler/8a07694d909694a_ek.pdf 
  17. ↑ Vijaya Kumar, A.; Jeyapal, A. (2014), "Self-Adaptive Trust Based ABR Protocol for MANETs Using Q-Learning", The Scientific World Journal 2014: 452362, doi:10.1155/2014/452362, PMID 25254243 
  18. ↑ Murad, Ayman Mansour; Al-Mahadeen, Bassam; Murad, Nuha Mansour (2008), "Adding Quality of Service Extensions to the Associativity Based Routing Protocol for Mobile Ad Hoc Networks (MANET)", 2008 IEEE Asia-Pacific Services Computing Conference, Apscc '08, pp. 631–637, doi:10.1109/APSCC.2008.234, ISBN 9780769534732, http://dl.acm.org/citation.cfm?id=1487990 
  19. ↑ ABAM: On-Demand Associativity-Based Multicast, https://www.researchgate.net/publication/3874369 
  20. ↑ Carthy, P.M.; Grigoras, D. (2005), "Multipath Associativity Based Routing", Second Annual Conference on Wireless On-demand Network Systems and Services, pp. 60–69, doi:10.1109/WONS.2005.24, ISBN 0769522904, http://dl.acm.org/citation.cfm?id=1044034 
  21. ↑ Eltarras, Ramy; Eltoweissy, Mohamed (2011), "Associative routing for wireless sensor networks", Computer Communications 34 (18): 2162–2173, doi:10.1016/j.comcom.2011.01.010 
  22. ↑ Yu, Hyun; Ahn, Sanghyun; Yoo, Joon (2013), "A Stable Routing Protocol for Vehicles in Urban Environments", International Journal of Distributed Sensor Networks 9 (11): 759261, doi:10.1155/2013/759261 



Retrieved from "https://handwiki.org/wiki/index.php?title=Associativity-based_routing&oldid=3371549"