Multimedia Training Kit

Mesh Networks

agenda

Mesh topology

Motivations & expectations

Mesh routing protocols

Mesh hardware

Mesh oriented software, distros etc

Some cases

Issues in mesh networking

Mesh topology - definition

Full Mesh Topology:

Mesh topology - definition

A mesh network is a network that employs one of two connection arrangements,
full mesh topology or partial mesh topology.
In the full mesh topology, each node is connected directly to each of the others. In the partial mesh topology, nodes are connected to only some, not all, of the other nodes."

MANET – common definition

MANET – a self-configuring network of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary topology.

* source: http://wikipedia.org

Mesh topology –
a typical scenario

Reality is not regular

Low-cost (potentially)

Distributed ownership models

Gradual deployment of infrastructure

Simple: Self-configuring

Robust

Low power requirements pr. unit

Why Mesh?

Mesh routing protocols: elements of mesh routing

Node discovery

Border discovery

Link metrics

Route calculation

IP address management

Uplink/backhaul management

... and more

Mesh routing protocols: Types

Pro-active (Table-driven)
Proactive checking of Link state and updating of routing tables – high complexity and CPU load, high performance

Reactive (On-demand)
Reacting on detection problems (non-working routes) – less demanding on CPU

Lines between types not strict

More types exist

Routing Protocols:
Pro-active (Table-driven)

OLSR (Optimized Link State Routing Protocol)OLSR-EXT, QOLSR

TBRPF (Topology Broadcast based on Reverse-Path Forwarding routing protocol)

HSLS (Hazy Sighted Link State routing protocol)

MMRP (Mobile Mesh Routing Protocol), short: MobileMesh

OSPF (Open Shortest Path First)

Routing Protocols:
Reactive (On-demand)

AODV

Mesh routing protocols: AODV

The Ad hoc On Demand Distance Vector (AODV) protocol is a routing protocol designed for mobile ad hoc networks. ...enables dynamic, self-starting, multihop routing between computers.

The protocol is in the process of being standardized at the IETF and currently is an experimental RFC

The AODV@IETF project is made possible through the joint collaboration of the MOMENT and NMSL laboratories at UC Santa Barbara and Intel R&D.

Routing Protocols: MMRP

Mobile Mesh protocol contains three separate protocols, each addressing a specific function
1. Link Discovery – a Simple “Hello” Protocol
2. Routing - Link State Packet Protocol
3. Border Discovery - Enables external tunnels

Developed by Mitre (with military interest involved)

The Mobile Mesh software is covered by the GNU General Public License (Version 2)

Comment: Good starting point for ad hoc linux laptop fun ....
a how-to is at: http://www.oreillynet.com/pub/a/wireless/2004/01/22/wirelessmesh.html

Routing Protocols: OSPF

Open Shortest Path First (OSPF) developed by the Interior Gateway Protocol (IGP) working group of the IETF , based on the SPF algorithm

OSPF specification is in the public domain, published as RFC1247.

Calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables included in LSAs.

OSPF routers accumulate link-state information, use the SPF algorithm to calculate shortest paths

As a link-state routing protocol, OSPF contrasts (and competes) with RIP and IGRP, which are distance-vector routing protocols. Routers running the distance-vector algorithm send all or a portion of their routing tables in routing-update messages to their neighbors.

Routing Protocols: OLSR

Optimized Link State Routing protocol. RFC3626.

OLSR is a routing protocol for mobile ad-hoc networks. The protocol is pro-active, table driven and utilizes a technique called multipoint relaying (MPR) for message flooding. Currently the implementation compiles on GNU/Linux, Windows, OS X, FreeBSD and NetBSD systems.

OLSRD is ment to be a well structured and well coded implementation that should be easy to maintain, expand and port to other platforms. The implementation is RFC3626 compliant with respect to both core and auxiliary functioning.

One of the most promising and stable prorocols

Used by a.o. the US navy in ship networks and behind-enemy-line drop-off autonomous units (verify!). Now that IS proof :)

Routing Metrics

Metric calculation deals with the cost assigned to a certain route

In principle, the routing protocol is independent from the metrics calculation – it just needs to know how 'good' the route is, not where that value comes from

Yet sensible metrics are the core of wireless ad hoc networking

Routing Metrics

Hop Count

RTT: Round Trip Time

PktPair: pe-hop Packet-pair Delay

ETX: Expected Transmission Count

Metrics: ETX

Estimates number of retransmissions needed for sending unicast package by measuring packet-loss of broadcast packets sent to each neighbour.

Reasonable overhead because broadcast packets are used

No self-interference because delay is not measured

Does not measure under realistic conditions because broadcast packets are small, and are sent at low data rate.

Favours high-capacity, reliable links.

Mesh hardware & software

Mesh hardware:
Metrix Mark I

OLSR preinstalled

low power consumption (ca. 10W)

100Mbps ethernet

power over ethernet (802.3af standard)

up to 2 (4,6) WLAN (802.11a/b/g) interfaces

133MHz AMD processor

64MB flash, 64MB RAM

Circa USD 275

Mesh hardware:
Meshnode

OLSR preinstalled

low power consumption (ca. 7W)

power over ethernet (802.3af standard)

Die-Cast Aluminum, protection class NEMA-67/IP-67

up to 2 WLAN (802.11a/b/g) interfaces

266MHz Geode processor

64-256MB CF-card, 128MB RAM

From circa EUR 450

Mesh hardware:
Linksys WRT54G

Not originally meant as a mesh device

Due to low price and GPLed firmware, one of the most interesting and versatile low budget options

Many firmware distros available: OpenWRT, EWRT, Batbox, Sveasoft (comment!), FreifunkFirmware, and many more

Hardware specs:	RAM / Flash / CPU speed
WRT54G v2	16	4	200 MHz
WRT54GS	32	8	200 MHz	Processor: BCM4712KPB

Price: circa EUR 60 (WRT54G) / 70 (WRT54GS)

Mesh hardware: Locustworld MeshAP

500mhz processor, 128mb ram, on board WiFi, 32mb compact flash drive.

No moving parts!

£250 each or £220 in orders of 10+

Mesh hardware: any old laptop

Any old laptop or stationary PC can serve as a mesh node

Targetted sw packages for this, e.g. Pebble Linux, MeshLinux, basically any Linux distro

Many arguments pro/contra using refurbished hardware, incl power consumption

Mesh software packages: olsrd

by Andreas Tønnesen

Implementation of OLSR with ETX

Runs on windows, Mac OSX, Linux and freeBSD

Mesh software packages: MeshLinux

By Elektra, Berlin/Germany

Based on slackware, circa 50 MB ISO

Targetted at reuse of (older) laptops

Mesh protocols included: MobileMesh, OLSR, BGP, OSPF, RIP, AODV

Mesh software packages: Zebra/Quagga

By Kunihiro Ishiguro

GNU Zebra is free software that manages TCP/IP based routing protocols. Part of the GNU Project, distributed under the GNU GPL

Mesh protocols included: BGP-4 (RFC1771, A Border Gateway Protocol 4), RIPv1, RIPv2, OSPFv2, IPv6 ready.

Fork: Quagga adds RIPv3, OSPFv3

Mesh software packages: CUWin

By Champaign-Urbana community project, USA

“The software the Champaign-Urbana Community Wireless Network (CUWiN) project releases is a complete operating system for wireless, meshing nodes. We start with a stock NetBSD distribution and add wireless drivers, routing code, and specialized systems which allow the nodes to work in harmony to route traffic for each other.”

Uses HSLS, OSPF, ETX

Mesh software packages: FreifunkFirmware

By Freifunk group, Berlin/Germany

Based off OpenWRT

The Freifunk Firmware can be installed on either a Linksys WRT54g (version 1.0 to 2.2), a WRT54gs (version 1.0 and 1.1), a WAP54g (version 2.0 only) or a compatible device to set up a typical OLSR node quickly and easily.

Mesh cases

Just a couple of examples (chosen almost at random)

Mesh cases: OLSRFreifunk, Berlin, Germany

Berlin, Germany, Freifunk

Mesh cases: MIT Rooftop

Mesh cases: Dharamsala

Using Linksys WRT54G with OpenWRT firmware

Using OLSR with ETX

Connecting non-profit organizations

Developed by Dharamsala Information Technology Group and David Ben-Yahel

Mesh cases: Dharamsala

Mesh cases: Tropos.com
Chaska, Minnesota

Quoting their website:
.... delivering metro-scale Wi-Fi mesh network products and services, with more than 125 customers and 40 resellers in eight countries around the world at the end of 2004. .... fastest, lowest cost and simplest way to deliver true wireless broadband (>1 Mbps) over large geographic areas using low-cost standard Wi-Fi clients ..

Proprietary MetroMeshTM routing software &
Predictive Wireless Routing Protocol PWRP TM

Chaska, Minnesota: Municipal network claims:
circa 250 nodes
covering 16 sqm
with 36 backhaul points

Issues in mesh networking

Throughput

Latency

Scalability

Security

IP distribution

Issues in mesh networking

Discussion is controversial and sometimes very biased, based on personal agenda

Expectations and benchmark differ wildly ... Enterprise level QoS implies other challenges than basic rural connectivity

Simply many things that haven't been tried yet (scale, stability, ...) and cannot be answered in lab.

Issues: Throughput

Issue of throughput in all multi-hop networks

Scales: with 1/n or 1/n2 or 1/n1/2?

For 802.11 MAC,
determined by half duplex
quality of radios ... in that case:
throughput ~ c/na with a = 1...2

Mesh idea not tied
to 802.11 MAC in principle

Issues: Latency

Latency obviously has to grow with number of hops

Effects of latency dependent on application

Example VoIP: latency can be felt from 170ms on, but sometimes walkie talkie with 5 s delay is better than nothing

Issues: Scalability

Mesh has not been tested in real life with more than a few dozen nodes:
MIT roofnet:	40-50
Berlin OLSR:	circa 80?

Commercial implementations (200 nodes? 10,000 nodes?) often do not share experiences .

Lab is not real life!

Issues: Security

Ad hoc networks per definition need to talk to clients before they know them
--> inherent security challenge

DoS issues

Issues: IP distribution

IP distribution in mesh networks far from trivial

DHCP in private IP ranges is fine, but what happens, when mesh1 meets mesh2?

Possible Solution: Zeroconf/Bonjour

Long-term solution: IPv6 and MobileIP

Mesh networks

Thank you for listening!

Questions?

mmtk_wireless_mesh_networks

Onno W. Purbo

2004-04-07T04:18:07