B.A.T.M.A.N.

Last updated
B.A.T.M.A.N.
Developer(s) Freifunk
Initial releasebatmand 0.1 (6 December 2006;17 years ago (2006-12-06))
Stable release
Batman-adv 2024.1 [1] / 5 April 2024;10 days ago (2024-04-05)
Written in C
Operating system Unix-like
Type routing protocol
License GPL
Website www.open-mesh.org

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).

Contents

B.A.T.M.A.N.'s crucial point is the decentralization of knowledge about the best route through the network — no single node has all the data. This technique eliminates the need to spread information about network changes to every node in the network. The individual node only saves information about the "direction" it received data from and sends its data accordingly. The data gets passed from node to node, and packets get individual, dynamically created routes. A network of collective intelligence is created.

In early 2007, the B.A.T.M.A.N. developers started experimenting with the idea of routing on layer 2 (Ethernet layer) instead of layer 3. To differentiate from the layer 3 routing daemon, the suffix "adv" (for: advanced) was chosen. Instead of manipulating routing tables based on information exchanged via UDP/IP, it provides a virtual network interface and transparently transports Ethernet packets on its own. [2] The batman-adv kernel module has been part of the official Linux kernel since 2.6.38. [3]

Operation

B.A.T.M.A.N. has elements of classical routing protocols: It detects other B.A.T.M.A.N. nodes and finds the best way (route) to these. It also keeps track of new nodes and informs its neighbors about their existence.

In static networks, network administrators or technicians decide which computer is reached via which way or cable. As radio networks undergo constant changes and low participation-thresholds are a vital part of the "Freifunk"-networks' foundation, this task has to be automated as much as possible.

On a regular basis, every node sends out a broadcast, thereby informing all its neighbors about its existence. The neighbors then relay this message to their neighbors, and so on. This carries the information to every node in the network. In order to find the best route to a certain node, B.A.T.M.A.N. counts the originator-messages received and logs which neighbor the message came in through.

Like distance-vector protocols, B.A.T.M.A.N. does not try to determine the entire route, but by using the originator-messages, only the packet's first step in the right direction. The data is handed to the next neighbor in that direction, which in turn uses the same mechanism. This process is repeated until the data reaches its destination.

In addition to radio networks, B.A.T.M.A.N. can also be used with common wired cable connections, such as Ethernet.

History

The task was to create a protocol which was to be as easy, as small and as fast as possible. It seemed sensible to split the development in several phases and implement complex functions using an iterative process:

Version one

In the first phase, the routing algorithm was implemented and tested for its practicality and suitability for the task at hand. For the sending and receiving of originator-messages (information about existence), the UDP port 1966 was chosen.

Version two

The version one algorithm made a significant assumption: As soon as a node receives existence data from another node, it assumes it can also send data back. In radio networks however, it may very well be that only one-way communication is possible, i.e., asymmetric links. [4] A mechanism was incorporated into the protocol to allow for this and to solve the arising problems. The mechanism enables the node to determine whether a neighbouring node provides bidirectional communication. Only bidirectional nodes are being considered part of the network, and one-way nodes are no longer fully included.

Version three

The greatest innovation in this version is B.A.T.M.A.N.'s support of multiple network devices. A computer or router running B.A.T.M.A.N. can be deployed in a central location, such as a tall building, and have several wired or wireless network interfaces attached to it. When so deployed, B.A.T.M.A.N. can relay network data in more than one direction without any retransmission delay.

Certain unusual phenomena and special circumstances could appear during the determination of the best route through the network. These have been tackled and counteracted to prevent circular routing (which can prevent data reaching its destination).

A node can inform the network that it provides access to the Internet. Other nodes use this information to evaluate whether there is a connection to the Internet close to them and how much bandwidth is available. They can either use a specific gateway or allow B.A.T.M.A.N. to determine which gateway to use, based on criteria such as connection speed.

Announcing devices not running B.A.T.M.A.N. themselves was also included in this version. Usually, this method is used to connect home networks to mesh-networks. An antenna installation on the roof will connect to the wireless network through B.A.T.M.A.N. and the rest of the building will simply be announced, thus also be reachable.

This version of B.A.T.M.A.N. has been shown to exhibit high levels of stability but slightly slow convergence times in real-world conditions; [5] this is confirmed by theoretical analysis. [6]

BMX6

BatMan-eXperimental (BMX) aims to approximate the real exponent by also sending OGMs (originator messages) multiple times in independent broadcast datagrams. [7] It originated as an independent branch of BATMAN developed by Axel Neumann. [8] An extended version that incorporates securely-entrusted multi-topology routing (SEMTOR) is called BMX7. [9]

IV

[10]

Version four implements an algorithm to better detect quality of transmissions in abnormal link situations. Originator messages are updated to incorporate this data, enabling other nodes to better sense quality of asymmetric connections.

V

[11]

Public persona

In 2017 B.A.T.M.A.N. was written on a whiteboard in the HBO series Silicon Valley (Season 4 Episode 2) where the show's lead character Richard Hendricks appears to include B.A.T.M.A.N. as a component of his "new Internet" concept (the text is visible on the top-right of the whiteboard). [12]

See also

Related Research Articles

A virtual private network (VPN) is a mechanism for creating a secure connection between a computing device and a computer network, or between two networks, using an insecure communication medium such as the public Internet.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

<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">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.

<span class="mw-page-title-main">RapidIO</span> High-speed interconnect technology

The RapidIO architecture is a high-performance packet-switched electrical connection technology. It supports messaging, read/write and cache coherency semantics. Based on industry-standard electrical specifications such as those for Ethernet, RapidIO can be used as a chip-to-chip, board-to-board, and chassis-to-chassis interconnect.

<span class="mw-page-title-main">Wireless network interface controller</span> Hardware component that connects a computer to a wireless computer network

A wireless network interface controller (WNIC) is a network interface controller which connects to a wireless network, such as Wi-Fi, Bluetooth, or LTE (4G) or 5G rather than a wired network, such as an Ethernet network. A WNIC, just like other NICs, works on the layers 1 and 2 of the OSI model and uses an antenna to communicate via radio waves.

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.

The Neighbor Discovery Protocol (NDP), or simply Neighbor Discovery (ND), is a protocol of the Internet protocol suite used with Internet Protocol Version 6 (IPv6). It operates at the internet layer of the Internet model, and is responsible for gathering various information required for network communication, including the configuration of local connections and the domain name servers and gateways.

<span class="mw-page-title-main">Flooding (computer networking)</span> Simple routing algorithm sending incoming packets to all other links than the sender

Flooding is used in computer network routing algorithms in which every incoming packet is sent through every outgoing link except the one it arrived on.

<span class="mw-page-title-main">Computer network</span> Network that allows computers to share resources and communicate with each other

A computer network is a set of computers sharing resources located on or provided by network nodes. Computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are made up of telecommunication network technologies based on physically wired, optical, and wireless radio-frequency methods that may be arranged in a variety of network topologies.

Transparent Inter Process Communication (TIPC) is an inter-process communication (IPC) service in Linux designed for cluster-wide operation. It is sometimes presented as Cluster Domain Sockets, in contrast to the well-known Unix Domain Socket service; the latter working only on a single kernel.

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.

Extremely Opportunistic Routing (ExOR) is a combination of routing protocol and media access control for a wireless ad hoc network, invented by Sanjit Biswas and Robert Morris of the MIT Artificial Intelligence Laboratory, and described in a 2005 paper. A very similar opportunistic routing scheme was also independently proposed by Zhenzhen Ye and Yingbo Hua from University of California, Riverside and presented in a paper in 2005. Previously open source, ExOR was available in 2005 but is no longer obtainable. The broadcast and retransmission strategies used by the algorithm were already described in the literature. ExOR is valuable because it can operate available digital radios to use some previously impractical algorithmic optimizations.

In wired computer networking, including the Internet, a hop occurs when a packet is passed from one network segment to the next. Data packets pass through routers as they travel between source and destination. The hop count refers to the number of network devices through which data passes from source to destination.

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.

Associativity-based routing 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.

References

  1. ↑ "B.A.T.M.A.N. home page". Updated as required
  2. ↑ "batman-adv — The Linux Kernel documentation". www.kernel.org. Retrieved 2019-04-14.
  3. ↑ "Linux 2 6 38". Linux Kernel Newbies.
  4. ↑ On Supporting Link Asymmetry in Mobile Ad Hoc Networks - Kim, Toh, Choi, IEEE GLOBECOM 2001., vol. 5, November 2001, pp. 2798–2803 vol.5, doi:10.1109/GLOCOM.2001.965940, S2CID   16396581
  5. ↑ M. Abolhasan; B. Hagelstein; J. C.-P. Wang (2009). "Real-world performance of current proactive multi-hop mesh protocols". 2009 15th Asia-Pacific Conference on Communications. pp. 44–47. doi:10.1109/APCC.2009.5375690. ISBN   978-1-4244-4784-8. S2CID   15462784.
  6. ↑ J. Chroboczek. "A few comments on the BATMAN routing protocol".
  7. ↑ Axel Neumann. "A few comments on the BATMAN routing protocol".
  8. ↑ Daneels, Glenn (2012–2013). Analysis of the BMX6 routing protocol. Department Mathematics-Computer Science, Faculty of Science, University of Antwerp.
  9. ↑ Neumann, Axel; Navarro, Leandro; Cerdà-Alabern, Llorenç (2018-10-01). "Enabling individually entrusted routing security for open and decentralized community networks". Ad Hoc Networks. 79: 20–42. doi:10.1016/j.adhoc.2018.06.014. hdl: 2117/119276 . ISSN   1570-8705. S2CID   61155814.
  10. ↑ "BATMAN IV - batman-adv - Open Mesh". www.open-mesh.org. Retrieved 2022-01-23.
  11. ↑ "BATMAN V - batman-adv - Open Mesh". open-mesh.org.
  12. ↑ Sven Eckelmann (May 3, 2017). "Silicon Valley Season 4 trailer links". Archived from the original on Dec 23, 2019.


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.