Mesh Networking with OLSR
Rob Flickenger
Types of links
Wireless networks can be arranged in one of these three logical configurations:
- Point-to-Point
- Point-to-Multipoint
- Multipoint-to-Multipoint
Point-to-Point
The simplest connection is the point-to-point link.
Point-to-Multipoint
When more than one connection communicates with a central point, this is a
point-to-multipoint network.
Multipoint-to-Multipoint
When any node of a network may communicate with any other, this is a
multipoint-to-multipoint network (also referred to as an
ad-hoc or mesh network)
The Mesh
Mesh networks are conceptually beautiful.
Benefits of mesh networking
Mesh networking can solve several difficult networking problems:
- The network is self-forming
- The network is also self-healing
- Simple node configuration
- All nodes are (more or less) equal
Problems with mesh networking
Mesh networks are not perfect.
- Complex routing can make debugging difficult
- Single radio = reduced bandwidth
- All nodes must be trusted
- Algorithms and implementations are in rapid development
The Mess
CSMA is a nightmare on large ad-hoc networks.
Mesh Algorithms: AODV
AODV: Ad-hoc On Demand Distance Vector
AODV is an on-demand reactive algorithm, meaning that it builds routes between nodes
only as desired by source nodes. It maintains these routes as long as they
are needed by the sources.
Most popular implementation is LocustWorld
Mesh Algorithms: AODV
The advantage of AODV is that it creates no extra traffic for communication
along existing links. Also, distance vector routing is simple, and doesn't
require much memory or calculation. However AODV requires more time to
establish a connection, and the initial communication to establish a route
is heavier than some other approaches.
More information: http://moment.cs.ucsb.edu/AODV/aodv.html
Mesh Algorithms: HSLS
HSLS: Hazy Sighted Link State
HSLS uses both proactive and reactive link-state routing to minimize network
updates. Routing updates are limited in both space and time. HSLS is
designed to scale well to networks containing more than one
thousand nodes.
Mesh Algorithms: HSLS
The most popular implementation of HSLS is CUWiN.
- Highly decentralized routing information and updates
- Complete NetBSD distribution
- Radios operate in proprietary ad-hoc mode
More information: http://cuwireless.net/
Mesh Algorithms: SrcRR
SrcRR: A High-Throughput Routing Protocol for 802.11 Mesh Networks
SrcRR is a reactive ad-hoc networking protocol developed at M.I.T.
The Roofnet implementation of SrcRR is a complete Linux distribution that implements
ad-hoc and AP mode simultaneously using a single radio card.
More information: http://pdos.csail.mit.edu/roofnet/design/
Mesh Algorithms: 802.11s
802.11s: Amendment to IEEE 802.11
802.11s integrates mesh networking at the MAC layer to make small mesh
networks.
- Extension to WDS
- Can create a network of up to 32 nodes
- Uses 802.11i security extensions
- Standard is due to be ratified in 2008
More information: http://grouper.ieee.org/groups/802/11/Reports/tgs_update.htm
Mesh Algorithms: OLSR
OLSR: Optimized Link State Routing
OLSR is a proactive routing protocol defined by RFC 3626.
It uses a technique called
multipoint relaying for efficient message flooding.
Implementations are available for
GNU/Linux, Windows, OS X, FreeBSD, OpenBSD and NetBSD.
- Implementation is Layer 1 agnostic
- Link updates are continuous
- Established IEEE standard
OLSR + ETX = olsr.org
olsr.org's implementation of OLSR
implements the ETX extension (not part of the IEEE standard).
ETX assigns a metric to each link, which is an estimate of the number of
times a packet will be transmitted before it is received and
acknowledged. An ETX metric of 1.0 represents a perfect link.
dot_draw plugin
OLSR: Other features
- Realtime topology display
- Dynamic Internet gateway (dyn_gw)
- Dynamic DNS throughout the mesh
- Scales to a few hundred nodes
Credits
Portions of this talk were adapted from Wireless Networking in the
Developing World, http://wndw.net/
