01Introduction
We previously wrote an article about the Freifunk network project in Germany, which, apart from its open and free attributes, also provides a very typical application scenario for wireless Mesh. I have always wanted to emphasize two aspects: one is that the concept of Wi-Fi Mesh encompasses many scenarios, and it is not limited to the home use of EasyMesh, which can severely restrict the understanding of Wi-Fi technology. On the other hand, the evolution of Wi-Fi technology is entirely driven by demand and business needs, representing a design with internet attributes, as Wi-Fi can be considered a crucial cornerstone of the current internet.
02RFC 3626: Traditional OLSR
Initially, Freifunk hoped to adopt Mobilemesh. Mobilemesh was a project supported by DARPA in the year 2000, which at that time was based on the minimum hop count to select routes. However, a routing algorithm based solely on hop count is inevitably limited in performance, and many link-state routing algorithms were already being promoted at that time, so Freifunk focused on the OLSR project.The OLSR project is based on RFC3626 and was originally designed as a routing scheme for mobile ad hoc networks (MANET). The routing protocols in MANET networks, which are typical of IoT scenarios, differ significantly from those in wired networks in two aspects: first, the topology of MANET is more dynamic and flexible. Secondly, the terminals in mobile scenarios often lack stable power supply, making energy efficiency a crucial part. A classic example is AODV, which establishes connections on demand, meaning that routing information is not maintained in real-time but is updated only when there is a need to transmit data packets.Compared to AODV, OLSR proposes to establish an active routing mechanism that allows every node in the network to maintain a routing table to reach other nodes at any time, thereby reducing latency during data transmission. Additionally, to avoid excessive flooding of routing information in the network and considering the broadcast nature of wireless networks, OLSR introduces the Multi-Point Relays (MPR) technology, which selects certain core nodes responsible for forwarding routing information, thus reducing bandwidth overhead.
As shown in the figure above, standard OLSR discovers neighbors and performs bidirectional link detection by having nodes periodically send Hello messages (the Hello packets contain node IDs, known neighbor lists, and link states). Nodes construct a “neighbor table” and a “2-hop neighbor table” through Hello messages and select the minimum number of nodes that can cover all 2-hop neighbors as MPRs. The selection of MPRs can reduce redundant forwarding and ensure network connectivity. When MPRs are selected, they are broadcasted. MPR nodes send TC (Topology Control) messages, which are used to construct the overall network topology and synchronize the topology connection status of all nodes. TC packets are propagated through the MPR network to all nodes. Additionally, there are HNA packets (Host and Network Association) used to announce the external networks (e.g., internet gateways) that nodes are connected to, allowing nodes in the ad hoc network to access the internet.Thus, the basic operational logic of OLSR is: 1) establish neighbor and 2-hop tables through Hello messages; 2) select MPRs; 3) MPR nodes periodically send TC messages, and all nodes construct the overall network graph based on TC topology information; 4) run Dijkstra’s shortest path algorithm to update the routing table and determine the next hop for each destination node; 5) routing convergence, and the network begins to operate.
03Improved OLSR: Openmesh OLSR
However, the OLSR based on RFC3626 is still too theoretical in many aspects, leading to numerous issues during actual deployment. The most severe problem is that the MPR selection strategy tends to favor distant nodes, thereby reducing the number of MPR nodes, but the nodes selected are often unstable in the topological relationship, requiring frequent replacements, which leads to repeated negotiations and reconstruction of topological information. The problem of topology desynchronization can further cause routing loops. Moreover, the routing selection is still based on the minimum hop count acting as link state, which is too simplistic, and the issue of dynamic gateway switching can also lead to continuous network interruptions.Therefore, Freifunk made thorough changes to the standard OLSR framework (referencing The OLSR.ORG story), which is referred to as openmesh OLSR. The main changes are: 1) disabling all optimization mechanisms of OLSR, leaving only a simple, multi-interface supporting active link state routing protocol; 2) introducing the LQ/ETX mechanism, which establishes routing relationships based on the statistical information from Hello packets, reflecting the actual link quality; 3) implementing the Fish-Eye mechanism, which prevents MPR nodes from frequently updating the entire network, allowing only nearby nodes to refresh.
LQ/ETX MechanismThe LQ/ETX mechanism was initially introduced in OLSR and later continued to be used in protocols like B.A.T.M.A.N. for wireless ad hoc networks. Its essence is to replace the traditional “hop count” metric, providing a better measure of link quality and reflecting the reliability and performance of wireless links. LQ (Link Quality): a metric that reflects the reliability of communication between nodes. ETX (Expected Transmission Count): the average number of transmissions required to successfully send a data packet (including retransmissions).In fact, ETX is a specific calculation method for the LQ metric, where df (forward delivery ratio) represents the success rate of forward transmission, and dr (reverse delivery ratio) represents the success rate of reverse acknowledgment. The transmission success rate can be obtained by statistically analyzing the transmission status of probe packets over a period. For example, in openmesh OLSR, nodes continuously send small probe packets (like Hello packets). By recording the ratio of packets sent and received between nodes and neighbors, the ETX metric is calculated based on the success rate within a time window. During routing selection, paths with the minimum total ETX value are prioritized over the shortest hop count.Fish-Eye MechanismThe Fish-Eye mechanism sets the TTL (Time To Live) field in the TC packets of OLSR to limit the message propagation range. However, the traditional OLSR has a propagation range that includes all nodes, resulting in significant network overhead. In openmesh OLSR, multiple TTL settings (1, 2, 3, 255) are used, and messages are sent in a sequence (i.e., TTL 255, TTL 3, TTL 2, TTL 1, TTL 2, TTL 1, TTL 1, TTL 3, TTL 2, TTL 1, TTL 2, TTL 1, TTL 1, simply put, this sequence is 255, 3, 2, 1, 2, 1, 1, 3, 2, 1, 2, 1, 1, which can be optimized and modified in the program).
If we consider the TC packet update cycle to be 0.5 seconds, then one-hop neighbors receive updates approximately every 0.5 seconds, two-hop neighbors about every 0.9 seconds, three-hop neighbors about every 2.2 seconds, and more distant nodes about every 6.5 seconds.
After using the improved Openmesh OLSR, Freifunk can initially establish such network connections. For example, it can stably operate in a network scale of about 10 hops, and with Dijkstra’s parameter restrictions, even low-end CPUs can support networks with over a hundred nodes. However, under high load, there are still occasional routing loops of 3-10 seconds, and the dynamic gateway switching issue remains unresolved.
04B.A.T.M.A.N: Better Approach To Mobile Ad-Hoc Networking
This is because the fundamental issue has not been resolved; OLSR has an inherent flaw where each node maintains all paths, but in reality, nodes only need to decide which neighbor to send to. In a wireless environment, global synchronization is impossible, and broadcasting messages during topology changes will lead to loss. The burden of maintaining a global topology in link-state routing is too heavy. Thus, a new protocol was born that allows nodes to autonomously select gateways: B.A.T.M.A.N: Better Approach To Mobile Ad-Hoc Networking.B.A.T.M.A.N. does not calculate the routing table for the entire network on each device. Each router using B.A.T.M.A.N. periodically broadcasts messages (called “Originator Messages”) to announce its presence to neighbors, who then continue to broadcast this message to their neighbors. Upon receiving an OGM, neighbors record which node the packet came from and through which link, and continue to forward it in the next round of broadcasts. Each OGM carries a link quality assessment value TQ (Transmission Quality), which indicates the quality of link transmission. Nodes count the number of received and lost OGMs to calculate the stability of the signal. Based on the accumulated TQ values over multiple hops, nodes determine which neighbor path is optimal. In this way, all nodes in the network can be aware of which B.A.T.M.A.N. routers exist. Each router only records which neighbors can reach other routers in its routing table, without calculating the complete path to the target. Therefore, B.A.T.M.A.N. does not compute a global topology but only selects the “best next hop,” allowing each node to know only which neighbor to reach the target.When the network topology changes (nodes join/leave or links degrade), the statistics from OGMs are updated over time, and nodes automatically adjust routing based on the latest TQ values. Because there is no centralized control or global topology recalculation, the network has a high degree of self-healing capability, adapting to frequent node movements.
B.A.T.M.A.N. initially operated at OSI layer 3 as a routing protocol, using UDP for optimal path selection and routing table updates. Later, due to its usefulness as a component in OpenWRT, the updated B.A.T.M.A.N. advanced (abbreviated as batman-adv) directly operates at OSI layer 2, ensuring it works directly at the Wi-Fi level (essentially as a component of the mesh). This makes the entire mesh network appear as a distributed switch at the upper layer: data flows are encapsulated and forwarded to the target as if the target node were directly adjacent.To enhance data throughput, B.A.T.M.A.N. advanced has been implemented as a Linux kernel module and has been part of the mainline Linux kernel since 2011, and it continues to be developed. B.A.T.M.A.N. advanced is widely used in the construction of WLAN Mesh networks, in addition to Germany’s Freifunk, it has also built Altermundi in Argentina and guifi.net in Catalonia, Spain. Additionally, the Village Telco project utilizes an implementation called “B.A.T.M.A.N. Daemon” to build low-cost community telephone networks, with the corresponding routers referred to as “Mesh Potato”; another project, Serval Project, uses Mesh networks to enable VoIP calls between smartphones.
Finally, we can summarize with a table, which is directly generated by AI and summarizes quite well, so it is included here.
About this article
This series of articles is reprinted from the author’s Zhihu column on Wi-Fi archaeology. This article focuses on expanding the understanding of the Mesh concept and technology. Therefore, it is shared on the public account for everyone’s reference.
If you like it,please follow us
and give us alike
andcheck it out for the best view.