Associativity-based routing

Last updated

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.

Contents

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:

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:

Related Research Articles

<span class="mw-page-title-main">Wireless mesh network</span> Radio nodes organized in a mesh topology

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.

<span class="mw-page-title-main">Mesh networking</span> Network with multiple links between nodes

A mesh network is a local area network topology in which the infrastructure nodes connect directly, dynamically and non-hierarchically to as many other nodes as possible and cooperate with one another to efficiently route data to and from clients.

<span class="mw-page-title-main">Optimized Link State Routing Protocol</span> IP routing protocol optimized for mobile ad hoc networks

The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

Ad hoc On-Demand Distance Vector (AODV) Routing is a routing protocol for mobile ad hoc networks (MANETs) and other wireless ad hoc networks. It was jointly developed by Charles Perkins and Elizabeth Royer and was first published in the ACM 2nd IEEE Workshop on Mobile Computing Systems and Applications in February 1999.

Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing table at each intermediate device.

<span class="mw-page-title-main">Freifunk</span>

Freifunk is a non-commercial open grassroots initiative to support free computer networks in the German region. Freifunk is part of the international movement for a wireless community network. The initiative counts about 400 local communities with over 41,000 access points. Among them, Münster, Aachen, Munich, Hanover, Stuttgart, and Uelzen are the biggest communities, with more than 1,000 access points each.

Delay-tolerant networking (DTN) is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity. Examples of such networks are those operating in mobile or extreme terrestrial environments, or planned networks in space.

Vehicular ad hoc networks (VANETs) are created by applying the principles of mobile ad hoc networks (MANETs) – the spontaneous creation of a wireless network of mobile devices – to the domain of vehicles. VANETs were first mentioned and introduced in 2001 under "car-to-car ad-hoc mobile communication and networking" applications, where networks can be formed and information can be relayed among cars. It was shown that vehicle-to-vehicle and vehicle-to-roadside communications architectures will co-exist in VANETs to provide road safety, navigation, and other roadside services. VANETs are a key part of the intelligent transportation systems (ITS) framework. Sometimes, VANETs are referred as Intelligent Transportation Networks. They are understood as having evolved into a broader "Internet of vehicles". which itself is expected to ultimately evolve into an "Internet of autonomous vehicles".

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

<span class="mw-page-title-main">B.A.T.M.A.N.</span> Routing protocol for multi-hop mobile ad hoc networks

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR) as OLSR did not meet the performance requirements of large-scale mesh deployments.

Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad hoc networks (MANETs).

Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.

In multi-hop networks, Adaptive Quality of Service routing protocols have become increasingly popular and have numerous applications. One application in which it may be useful is in Mobile ad hoc networking (MANET).

In mobility management, the random waypoint model is a random model for the movement of mobile users, and how their location, velocity and acceleration change over time. Mobility models are used for simulation purposes when new network protocols are evaluated. The random waypoint model was first proposed by Johnson and Maltz. It is one of the most popular mobility models to evaluate mobile ad hoc network (MANET) routing protocols, because of its simplicity and wide availability.

Scalable Source Routing (SSR) is a routing protocol for unstructured networks such as mobile ad hoc networks, mesh networks, or sensor networks. It combines source routing with routing along a virtual ring, and is based on the idea of "pushing Chord into the underlay".

IEEE 802.11s is a wireless local area network (WLAN) standard and an IEEE 802.11 amendment for mesh networking, defining how wireless devices can interconnect to create a wireless LAN mesh network, which may be used for relatively fixed topologies and wireless ad hoc networks. The IEEE 802.11s task group drew upon volunteers from university and industry to provide specifications and possible design solutions for wireless mesh networking. As a standard, the document was iterated and revised many times prior to finalization.

A mobile wireless sensor network (MWSN) can simply be defined as a wireless sensor network (WSN) in which the sensor nodes are mobile. MWSNs are a smaller, emerging field of research in contrast to their well-established predecessor. MWSNs are much more versatile than static sensor networks as they can be deployed in any scenario and cope with rapid topology changes. However, many of their applications are similar, such as environment monitoring or surveillance. Commonly, the nodes consist of a radio transceiver and a microcontroller powered by a battery, as well as some kind of sensor for detecting light, heat, humidity, temperature, etc.

<span class="mw-page-title-main">Chai Keong Toh</span> Singaporean computer scientist

Chai Keong Toh is a Singaporean computer scientist, engineer, industry director, former VP/CTO and university professor. He is currently a Senior Fellow at the University of California Berkeley, USA. He was formerly Assistant Chief Executive of Infocomm Development Authority (IDA) Singapore. He has performed research on wireless ad hoc networks, mobile computing, Internet Protocols, and multimedia for over two decades. Toh's current research is focused on Internet-of-Things (IoT), architectures, platforms, and applications behind the development of smart cities.

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. S2CID   14335563.
  2. ↑ Toh, Chai-Keong (March 1996). A novel distributed routing protocol to support ad-hoc mobile computing. Proceedings of the IEEE Fifteenth Annual International Phoenix Conference on Computers and Communications.
  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
  5. ↑ "Mobile Computing Magazine Interview Article - First practical ad hoc wireless network implementation outdoors, 1999 (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, S2CID   26834795
  7. ↑ Evaluating the communication performance of an ad hoc wireless network, IEEE Transactions on Wireless Communications, 2000
  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, S2CID   1486812
  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 (PDF)
  10. ↑ "Next-Generation Tactical Ad Hoc Mobile Wireless Networks". TRW Technology Review Journal. 2004.
  11. ↑ A Routing Method for Ad Hoc Mobile Networks, US Patent 5987011, granted 1996, filed 1994.
  12. ↑ Dube, Rohit; Rais, Cynthia D.; Wang, Kuang-Yeh; Tripathi, Satish K. (1996), Signal stability based adaptive routing (SSA) for ad-hoc mobile networks
  13. ↑ Alternative Enhancement of Associativity-Based Routing, 2009, doi:10.1007/978-3-642-11817-3_7, S2CID   8920485
  14. ↑ Optimized Associativity Threshold Routing, CiteSeerX   10.1.1.79.8653
  15. ↑ Associativity-Based Clustering Protocol for Mobile Ad Hoc Networks (PDF)
  16. ↑ Associativity Tick Averaged Associativity-Based Routing for Realtime Mobile Networks (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 , PMC   4164804 , 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, S2CID   7026878
  19. ↑ ABAM: On-Demand Associativity-Based Multicast
  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, S2CID   12523282
  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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.