How Mesh Networking Works
Networks
Networks are systems that enable devices (such as desktop or laptop computers, mobile devices, servers, or routers) to communicate with one another. Each device in a network is called a node.
Nodes in a network are linked together by any of a variety of media, such as cables (for wired networks) or radio waves (for wireless networks). Networks can transmit data along paths, from device to device, so that two computers that are not directly linked can still communicate. This is called routing.
Devices communicate using protocols, or rules for the formatting and transmission of data. The protocols used on the Internet, and most modern networks, are packet-switching protocols. A packet is the basic unit of data transmission on such networks.
Traditional Network Design
Most networks use dedicated routers, usually connected by physical cables, to transmit communications between computers that are not directly connected.
For example, the backbone of the Internet is comprised of core routers, usually connected by fiber optic cables, that allow communication between computers around the world. Local area networks (LANs) use routers to manage communications between a small number of computers, such as in a home or office. These networks are often wireless networks that operate over the IEEE 802.11 protocols, otherwise known as WiFi.
Wireless Networks in Infrastructure Mode
The following sections are adapted from Chapter 3 of Wireless Networking in the Developing World, a free e-book licensed under Creative Commons.
Most WiFi networks operate in infrastructure mode – they consist of an access point somewhere (with a radio operating in master mode), attached to a DSL line or other large scale wired network. In such a hotspot the access point usually acts as a master station that is distributing Internet access to its clients, which operate in managed mode. This topology is similar to a mobile phone (GSM) service. Mobile phones connect to a base station – without the presence of such a base station mobiles can’t communicate with each other. If you make a joke call to a friend that is sitting on the other side of the table, your phone sends data to the base station of your provider that may be a mile away – the base station then sends data back to the phone of your friend.
WiFi cards in managed mode can’t communicate directly, either. Clients – for example, two laptops on the same table – have to use the access point as a relay. Any traffic between clients connected to an access point has to be sent twice. If client A and C communicate, client A sends data to the access point B, and then the access point will retransmit the data to client C. A single transmission may have a speed of 600 kByte/sec (thats about the maximum speed you could achieve with 802.11b) in our example – thus, because the data has to be repeated by the access point before it reaches its target, the effective speed between both clients will be only 300 kByte/sec.
In ad-hoc mode there is no hierarchical master-client relationship. Nodes can communicate directly as long as they are within the range of their wireless interfaces. Thus, in our example both computers could achieve full speed when operating ad-hoc, under ideal circumstances.
The disadvantage to ad-hoc mode is that clients do not repeat traffic destined for other clients. In the access point example, if two clients A and C can’t directly “see” each other with their wireless interfaces, they still can communicate as long as the AP is in the wireless range of both clients.
Ad-hoc nodes do not repeat by default, but they can effectively do the same if routing is applied. Mesh networks are based on the strategy that every mesh-enabled node acts as a relay to extend coverage of the wireless network. The more nodes, the better the radio coverage and range of the mesh cloud.
There is one big tradeoff that must be mentioned at this point. If the device only uses one radio interface, the available bandwidth is significantly reduced every time traffic is repeated by intermediate nodes on the way from A to B. Also, there will be interference in transmission due to nodes sharing the same channel. Thus, cheap ad-hoc mesh networks can provide good radio coverage on the last mile(s) of a community wireless network at the cost of speed– especially if the density of nodes and transmit power is high.
If an ad-hoc network consists of only a few nodes that are up and running at all time, don’t move and always have stable radio links – a long list of ifs – it is possible to write individual routing tables for all nodes by hand.
Unfortunately, those conditions are rarely met in the real world. Nodes can fail, WiFi enabled devices roam around, and interference can make radio links unusable at any time. And no one wants to update several routing tables by hand if one node is added to the network. By using routing protocols that automatically maintain individual routing tables in all nodes involved, we can avoid these issues. Popular routing protocols from the wired world (such as OSPF) do not work well in such an environment because they are not designed to deal with lossy links or rapidly changing topology.
Mesh routing with olsrd
The Optimized Link State Routing Daemon – olsrd – from olsr.org is a routing application developed for routing in wireless networks. We will concentrate on this routing software for several reasons. It is a open-source project that supports Mac OS X, Windows 98, 2000, XP, Linux, FreeBSD, OpenBSD and Chapter 3: Network Design 57NetBSD. Olsrd is available for access points that run Linux like the Linksys WRT54G, Asus Wl500g, AccessCube or Pocket PCs running Familiar Linux, and ships standard on Metrix kits running Pyramid. Olsrd can handle multiple interfaces and is extensible with plug-ins. It supports IPv6 and it is actively developed and used by community networks all over the world.
Note that there are several implementations of Optimized Link State Routing, which began as an IETF-draft written at INRIA France. The implementation from olsr.org started as a master thesis of Andreas Toennesen at UniK University. Based on practical experience of the free networking community, the routing daemon was modified. Olsrd now differs significantly from the original draft because it includes a mechanism called Link Quality Extension that measures the packet loss between nodes and calculates routes according to this information. This extension breaks compatibility to routing daemons that follow the INRIA draft. The olsrd available from olsr.org can be configured to behave according to the IETF draft that lacks this feature – but there is no reason to disable Link Quality Extension unless compliance with other implementations is required.
Theory
After olsrd is running for a while, a node knows about the existence of every other node in the mesh cloud and which nodes may be used to route traffic to them. Each node maintains a routing table covering the whole mesh cloud. This approach to mesh routing is called proactive routing. In contrast, reactive routing algorithms seek routes only when it is necessary to send data to a specific node.
There are pros and cons to proactive routing, and there are many other ideas about how to do mesh routing that may be worth mentioning. The biggest advantage of proactive routing is that you know who is out there and you don’t have to wait until a route is found. Higher protocol traffic overhead and more CPU load are among the disadvantages. In Berlin, the Freifunk community is operating a mesh cloud where olsrd has to manage more than 100 interfaces. The average CPU load caused by olsrd on a Linksys WRT54G running at 200 MHz is about 30% in the Berlin mesh. There is clearly a limit to what extent a proactive protocol can scale – depending on how many interfaces are involved and how often the routing tables are updated. Maintaining routes in a mesh cloud with static nodes takes less effort than a mesh with nodes that are constantly in motion, since the routing table has to be updated less often. Mechanism
A node running olsrd is constantly broadcasting ‘Hello’ messages at a given interval so neighbors can detect it’s presence. Every node computes a statistic how many ‘Hellos’ have been lost or received from each neighbor – 58 Chapter 3: Network Designthereby gaining information about the topology and link quality of nodes in the neighborhood. The gained topology information is broadcasted as topology control messages (TC messages) and forwarded by neighbors that olsrd has chosen to be multipoint relays.
The concept of multipoint relays is a new idea in proactive routing that came up with the OLSR draft. If every node rebroadcasts topology information that it has received, unnecessary overhead can be generated. Such transmissions are redundant if a node has many neighbors. Thus, an olsrd node decides which neighbors are favorable multipoint relays that should forward its topology control messages. Note that multipoint relays are only chosen for the purpose of forwarding TC messages. Payload is routed considering all available nodes.
Two other message types exist in OLSR that announce information: whether a node offers a gateway to other networks (HNA messages) or has multiple interfaces (MID messages). There is not much to say about what this messages do apart from the fact that they exist. HNA messages make olsrd very convenient when connecting to the Internet with a mobile device. When a mesh node roams around it will detect gateways into other networks and always choose the gateway that it has the best route to. However, olsrd is by no means bullet proof. If a node announces that it is an Internet gateway – which it isn’t because it never was or it is just offline at the moment – the other nodes will nevertheless trust this information. The pseudo-gateway is a black hole. To overcome this problem, a dynamic gateway plugin was written. The plugin will automatically detect at the gateway if it is actually connected and whether the link is still up. If not, olsrd ceases to send false HNA messages. It is highly recommended to build and use this plugin instead of statically enabling HNA messages.