Transcript Diapositiva 1

Redes Inalámbricas – Tema 4
Wireless Mesh Networks
Terminology
Study case: Guifi.net
Mesh HW and SW
Elements of mesh routing
IEEE 802.11s
Thanks to Sebastian Büttrich, wire.less.dk
REDES INALÁMBRICAS
Máster de Ingeniería de Computadores-DISCA
2
MIC 2009/2010
REDES INALÁMBRICAS
Mesh topology – a typical scenario
3
MIC 2009/2010
REDES INALÁMBRICAS
Community Networks
 Broadband Internet Access
technology
 Several neighbors may share
their broadband connections
with many other neighbors
 Not run by ISPs
 Possibly in the
disadvantage of the ISPs
Source: research.microsoft.com/mesh/
4
MIC 2009/2010
Overview
Node Types
Wireless routers
Gateways
Printers, servers
Link Types
Intra-mesh wireless links
Stationary client access
Mobile client access
Mobile clients
REDES INALÁMBRICAS
Stationary clients
Internet access links
5
MIC 2009/2010
Advantages of Mesh Networking
 Self-forming
 The wireless mesh network forms automatically once the mesh nodes have been
configured and activated.
 Fault tolerance
 If redundant routes exist in the network, information flow is not interrupted in the rest
of the network when one node fails. The network will dynamically reroute the
information via the next available route.
 Self-healing
 Once restored, a node rejoins the mesh network seamlessly.
 Community ownership
 Ownership of the network is shared, hence the burden of network support does not
rest with a single person.
 Low cost of infrastructure
 Mesh nodes can be built from low cost, common-off-the-shelf equipment.
REDES INALÁMBRICAS
 Incremental cost of network expansion is low
 With the addition of one extra node, at the marginal cost of that node, the reach and
value of the network is increased.
 Ease of deployment
 With little training members of a community can build their own nodes, configure and
deploy them in the community.
Redes Inalámbricas – Tema 4
Wireless Mesh Networks
Terminology
Study case: Guifi.net
Mesh HW and SW
Elements of mesh routing
IEEE 802.11s
Thanks to Sebastian Büttrich, wire.less.dk
REDES INALÁMBRICAS
Máster de Ingeniería de Computadores-DISCA
MIC 2009/2010
Study case: Guifi.net
REDES INALÁMBRICAS
From Ramon Roca talk
at:
MIC 2009/2010
REDES INALÁMBRICAS
What?
Enabling users to become infrastructure providers
 Extending the Internet network neutrality up to the last mile
 Embracing the Openness paradigm:
By peer to peer connection agreements open to all, not restricted to telecoms/
Open standards, software, hardware... Networks!
 Free as in freedom:
No single ownership
Same rules for all
Lowering TCO by being cost oriented/real value instead of price dominance
(How much it costs vs how much user can pay...)
MIC 2009/2010
guifi.net experience
 Started in 2,004 in country-side Catalonia
 Envisioned as a New Generation of Free Networks / Wireless
Communities
 Lead and originally founded by the civil society
 Currently a non-profit NGO (Foundation)
 As of Aug 2,009:
REDES INALÁMBRICAS
 7,500 online nodes
 10,000 kms. of network links
 Sustained growth
MIC 2009/2010
How?
 By building end-user oriented platform to enable the deployment of
neutral networks at the last mile
REDES INALÁMBRICAS
 Same P2P agreement for all
 Web 2.0 style collaborative platform including
IP Provisioning
Network Monitoring (traffic, status...)
GIS applications (maps)
Device Configuration
 Technology agnostic
Low cost wireless intensively used, but not restricted to (now extending to
fiber)
MIC 2009/2010
Example: The node page
Complete menus providing many
features
REDES INALÁMBRICAS
Detailed drill/down information and
maps
Graphs & Network statistics
MIC 2009/2010
REDES INALÁMBRICAS
Example: The node page II
 List of nodes & availability
 Real time
MIC 2009/2010
REDES INALÁMBRICAS
Example: The node page III

Suggested links, check for Line-of-Sight (LoS)
MIC 2009/2010
And now is time for...
 Launching FFTH - FFTF
projects
REDES INALÁMBRICAS
 Fiber From The Farms /
Houses, NOT just “To”...
 Launched in Summer 2,009
 Reuse of existing copper
infrastructure / posts
MIC 2009/2010
Open Spectrum Alliance
 Whitespaces + “smart” technologies = new opportunities for spectrum
efficiency
REDES INALÁMBRICAS
 The Open Spectrum Alliance is united by the goal of realizing the potential social
and economic benefits of this underutilized natural resource by promoting
innovative public policies.
Redes Inalámbricas – Tema 4
Wireless Mesh Networks
Terminology
Study case: Guifi.net
Mesh HW and SW
Elements of mesh routing
IEEE 802.11s
Thanks to Sebastian Büttrich, wire.less.dk
REDES INALÁMBRICAS
Máster de Ingeniería de Computadores-DISCA
17
MIC 2009/2010
REDES INALÁMBRICAS
Mesh hardware
 Ranges from (almost no-cost) refurbished computers over modified
home user Access points for 50€ to mid-price embedded boards to
carrier grade equipment for several thousand €
 Challenge: to balance total cost of ownership, quality, requirements –
as with all other network hardware.
 Market is in dynamic development
 Open platforms and standards enable open development
18
MIC 2009/2010
REDES INALÁMBRICAS
Mesh hardware: Meshnode by Saxnet
 Debian GNU Linux 2.6er Kernel
 Processor AMD Geode LX x86
 WLAN Standards 802.11
a/b/c/g/i/f
 Security WPA2 (AES), WEP
64/128/156, 802.1x, Firewall,
MAC Filter, HTTPS, Port
Forward
 Management
Web GUI,
root access over SSH2, SNMP
V3 (read), Network
Management System
 Services PPPoE (DSL & 3G) ,
DHCP server, SSH, HTTP,
DynDNS
 Built into a waterproof outdoor
enclosure.
19
MIC 2009/2010
Mesh Hardware: Commercial & proprietary
 Tropos
 BelAir
 Strix
 And:
REDES INALÁMBRICAS




Nortel
Nokia
Cisco
…
20
MIC 2009/2010
REDES INALÁMBRICAS
Mesh hardware: Linksys WRT54G
 Not originally meant as a mesh device
 Due to low price and GPL firmware, one of the most interesting and
versatile low budget options
 Many firmware distributions available: OpenWRT, EWRT, Batbox,
Sveasoft, FreifunkFirmware, and many more
 Hardware specs: RAM / Flash / CPU speed
WRT54G v2
16
4
200 MHz
WRT54GS
32
8
200 MHz
 Processor: Broadcom
 Price: circa 60€ (WRT54G)
21
MIC 2009/2010
Mesh software packages
 Zebra/Quagga
 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
 Meshlinux by elektra




@ http://zolder.scii.nl/~elektra/
Based on Slackware, circa 50 MB ISO
Targetted at reuse of (older) laptops
Mesh protocols included: MobileMesh, OLSR, BGP, OSPF, RIP, AODV
REDES INALÁMBRICAS
 CUWiN (the Champaign-Urbana Community Wireless Network)
 @ http://www.cuwin.net/
 Various mesh protocols included: HSLS, ETX, …
22
MIC 2009/2010
Mesh software packages: OpenWRT
 OpenWrt is a linux distribution for the Linksys WRT54G, a minimal
firmware with support for add-on packages, custom tunable
 http://openwrt.org/
REDES INALÁMBRICAS
 It includes other chipsets, manufacturers and device types, including
Netgear, D-Link, Asus routers and many others.
 Readonly core provides: network initalization (ethernet and wireless),
firewalling, dhcp client / server, caching dns server, telnet server and
busybox environment
 ssh and web interfaces available via ipkg
 Many more packages, e.g. asterisk
 Mesh protocols: OLSR, AODV, ....
23
MIC 2009/2010
Mesh software packages: OpeWRT derivatives
 Many other forware s are available that derive in vaious percentages
from the original OpenWRT. The most important are:
REDES INALÁMBRICAS
 Freifunk
@ http://start.freifunk.net/
Uses OLSR
 DD-WRT
@ http://www.dd-wrt.com/
Commercial
 Sveasoft
@ http://sveasoft.com/
Talisman/Mesh Firmware
Redes Inalámbricas – Tema 4
Wireless Mesh Networks
Terminology
Study case: Guifi.net
Mesh HW and SW
Elements of mesh routing
IEEE 802.11s
Thanks to Sebastian Büttrich, wire.less.dk
REDES INALÁMBRICAS
Máster de Ingeniería de Computadores-DISCA
25
MIC 2009/2010
REDES INALÁMBRICAS
Wireless Mesh Networking Principles
 Communication between mesh nodes are typically based on
Wi-Fi radios (IEEE 802.11 a/b/g) attached to directional or omnidirectional antennas.
 All radios are set to ad-hoc mode (not client mode or infrastructure
(access point) mode).
 Each node in the WMN has the same ESSID (name) and BSSID
(number) - the BSSID should be fixed to prevent partitioning of the
wireless network.
 All nodes in the WMN will operate on the same channel (frequency).
 In an ideal WMN, each node should be able to “see” at least two other
nodes in the WMN. This allows full fail-over in case any node goes out
of commission (e.g. due to a hardware failure or power failure).
 A mesh routing protocol, like OLSR, will route IP traffic between the
wireless interfaces of the mesh nodes.
26
MIC 2009/2010
Important Considerations
 Various obstructions may interfere with the signals and should be
considered:
REDES INALÁMBRICAS
 Trees and plants – water on leaves negatively impact on signal strength
 Construction materials – metal objects like roofs or reinforcing in concrete walls
affect the signal strength.
 Electronics are susceptible to lightning damage and lightning
protection should be considered, especially for outdoor installations of
Wi-Fi equipment.
 Each country has a regulatory body that regulates the use of wireless
equipment. Check with your local regulator.
 There is a trade-off between the cost of planning and building of a
network well at the start of the project and the cost of maintaining a
badly designed network. It is worth the effort to plan thoroughly, get
the appropriate equipment and to create redundant routes in the
wireless mesh network wherever possible.
27
MIC 2009/2010
Important Considerations: channel allocation
 Channel allocation for the backbone and mesh network
 Adding a backbone effectively adds another wireless network that has to work
independent from the other mesh network. The “normal” mesh network will
therefore work at channel 6 and the backbone at channel 11. This will ensure that
the two networks do not interfere with each other.
 Channel allocation for home / office users
REDES INALÁMBRICAS
 A third wireless network is possible within this framework; a hotspot. A hotspot is
usually required at home or the office when one wants to create a local wireless
network to connect laptops and other wireless equipment. The hotspot will require
a wireless access point (Linksys) to be connected to the mesh node. The two
Linksys boxes are connected together back-to-back with an LAN cable (via the
Ethernet switch ports).
28
MIC 2009/2010
REDES INALÁMBRICAS
Select the network topology type
Simple mesh network plot
Clustered mesh with backbone
29
MIC 2009/2010
Plan the IP address allocation
 Addresses are allocated according to RFC 1918 which provides details
of the private address space.
 The IP addressing scheme should ensure unique addresses for each
node and PC on the network.
 The first thing one has to choose is an available subnet.
 According to RFC 1918, the subnets available for private
IP networks that will not be connected to the internet are:
REDES INALÁMBRICAS

10. 0.0.0  172. 16.0.0  192.168.0.0 -
10.255.255.255
172. 31.255.255
192.168.255.255
(10/8 prefix)
(172.16/12 prefix)
(192.168/16 prefix)
 Once the subnet has been selected, one can assign IP numbers to
mesh nodes and PCs randomly.
 It is much better to choose a method of assigning IP numbers and to
stick to it very rigorously.
30
MIC 2009/2010
A Method of assigning IP numbers (wireless interface):
a proposal
 Backbone node:
Or sometimes (x-1)…
 Wireless interface: 10.0.1.x/24 where 1 ≤ x < 255
 Ethernet interface: 10.3.x.y/24 where 1 ≤ y < 255
 “Normal” mesh node:
 Wireless interface: 10.1.1.a/24 where 1 ≤ a < 255
 Ethernet interface: 10.2.a.b/24 where 1 ≤ b < 255.
Note that “mesh” nodes will be in the lower range, but other PCs and laptops
connected to a node will be numbered from 100 according to the DHCP
settings.
REDES INALÁMBRICAS
 Access Point (Hotspots):
 One would connect a wireless access back-to-back to a “normal”
mesh node. The subnet assigned to the wireless LAN or hotspot will therefore be
the same as with an Ethernet LAN connected to the mesh node.
 NOTE
 The 10.0.1.x/24 notation translates to:
IP address:
10. 0. 1.x where 1 ≤ x < 255, and
subnet mask: 255.255.255.0
31
MIC 2009/2010
REDES INALÁMBRICAS
Example layout of a wireless mesh network
32
MIC 2009/2010
Routing Protocols
 Proactive:
 OLSR (Optimized Link State
Protocol)
 B.A.T.M.A.N. (Better
Approach to Mobile Ad-Hoc
Networking)
 Reactive:
REDES INALÁMBRICAS
 AODV (Ad-hoc on Demand
Distance Vector)
 SrcRR (MIT Roofnet)
 Hybrid:
 HSLS (Hazy Sighted Link
State Routing, CuWin)
 These are just some of the
most relevant protocols in
our context ... there are
many other protocols!
 TBRPF (Topology Broadcast
based on Reverse-Path
Forwarding routing protocol)
 MMRP (Mobile Mesh Routing
Protocol), short: MobileMesh
 OSPF (Open Shortest Path
First)
33
MIC 2009/2010
REDES INALÁMBRICAS
Mesh routing protocols: 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
34
MIC 2009/2010
Link Quality Metrics
 Per-hop Round Trip Time (RTT)
 Per-hop Packet-Pair (PktPair)
 Expected transmissions (ETX)
 Minimum-hop routing (HOP)
REDES INALÁMBRICAS
Binary link quality
35
MIC 2009/2010
Metric 1: Per-hop RTT
 Node periodically pings each of its neighbors
 Unicast probe/probe-reply pair
 RTT samples are averaged using TCP-like low-pass filter
 Exponential smoothing
REDES INALÁMBRICAS
 Path with least sum of RTTs is selected
36
MIC 2009/2010
Metric 1: Per-hop RTT
 Advantages
 Easy to implement
 Accounts for link load and bandwidth
 Also accounts for link loss rate
802.11 retransmits lost packets up to 7 times
Lossy links will have higher RTT
 Disadvantages
REDES INALÁMBRICAS
 Expensive
 Self-interference due to queuing
37
MIC 2009/2010
Metric 2: Per-hop Packet-Pair
 Node periodically sends two back-to-back probes to each neighbor
 First probe is small, second is large
 Neighbor measures delay between the arrival of the two probes;
reports back to the sender
 Sender averages delay samples using low-pass filter
REDES INALÁMBRICAS
 Path with least sum of delays is selected
38
MIC 2009/2010
Metric 2: Per-hop Packet-Pair
 Advantages
 Self-interference due to queuing is not a problem
 Implicitly takes load, bandwidth and loss rate into account
 Disadvantages
REDES INALÁMBRICAS
 More expensive than RTT
39
MIC 2009/2010
Metric 3: Expected Transmissions (ETX)
 Estimate number of times a packet has to be retransmitted on each
hop
 Each node periodically broadcasts a probe
 802.11 does not retransmit broadcast packets
 Probe carries information about probes received from neighbors
 Node can calculate loss rate on forward (Pf) and reverse (Pr) link to
each neighbor
REDES INALÁMBRICAS
ETX 
1
(1  P ) * (1  P )
f
 Select the path with least total ETX
r
40
MIC 2009/2010
Metric 3: Expected Transmissions
 Advantages
 Low overhead
 Explicitly takes loss rate into account
 Disadvantages
REDES INALÁMBRICAS
 Loss rate of broadcast probe packets is not the same as loss rate of data packets
Probe packets are smaller than data packets
Broadcast packets are sent at lower data rate
 Does not take data rate or link load into account
41
REDES INALÁMBRICAS
Approx. 32 m
MIC 2009/2010
Mesh Testbed
Approx. 61 m
23 Laptops running Windows XP.
802.11a cards: mix of Proxim and Netgear.
Diameter: 6-7 hops.
42
Lower Bandwdith (Mbps)
MIC 2009/2010
Link bandwidths in the testbed
30
• Cards use Autorate
25
•Total node pairs:
23x22/2 = 253
20
• 90 pairs have non-zero
bandwidth in both directions.
15
10
5
REDES INALÁMBRICAS
0
0
5
10
15
20
25
Higher Bandwidth (Mbps)
30
Bandwidths vary significantly; lot of asymmetry.
43
MIC 2009/2010
Experiment 1
 3-Minute TCP transfer between each node pair
 23 x 22 = 506 pairs
 1 transfer at a time
 Long transfers essential for consistent results
 For each transfer, record:
REDES INALÁMBRICAS
 Throughput
 Number of paths
Path may change during transfer
 Average path length
Weighted by fraction of packets along each path
44
MIC 2009/2010
Median Throughput
1600
Median Throughput (Kbps)
1400
1200
1000
800
600
400
REDES INALÁMBRICAS
200
0
HOP
ETX
RTT
ETX performs best. RTT performs worst.
PktPair
45
MIC 2009/2010
Impact on Path Lengths
8
Path Length with HOP
7
6
5
4
3
2
REDES INALÁMBRICAS
1
0
0
1
2
3
4
5
6
7
Path Length with ETX
Path length is generally higher under ETX.
8
46
MIC 2009/2010
Throughput vs path length
Throughput (Kbps)
ETX
12000
10000
8000
6000
4000
2000
0
0
1
2
3
4
5
6
7
8
Average Path Length (Hops)
PktPair
Throughput (Kbps)
REDES INALÁMBRICAS
12000
10000
8000
6000
4000
2000
0
0
1
2
3
4
5
6
7
8
Average Pathlength (Hops)
PktPair suffers from self-interference only on multi-hop paths.
Redes Inalámbricas – Tema 4
Wireless Mesh Networks
Terminology
Study case: Guifi.net
Mesh HW and SW
Elements of mesh routing
IEEE 802.11s
REDES INALÁMBRICAS
Máster de Ingeniería de Computadores-DISCA
48
MIC 2009/2010
The standard 802.11s: history
 The Mesh Standard 802.11s is currently under development and
unapproved.
 The development started in September 2003 and a Call for Proposals
was issued in May 2005.
 The 15 proposals received by the IEEE were submitted to vote in July
2005.
REDES INALÁMBRICAS
 All the ideas have been merged into two different proposals, called “See-Mesh”
and “Wi-Mesh”.
 Wi-Mesh (sponsored by Nortel, Accton, Thomson, Philips, InterDigital, MITRE,
NextHop and Comnets) has been merged to See-Mesh (sponsored by Intel, Nokia,
Motorola, Texas Instruments and NTT DoCoMo) in January 2006.
 The TGs goal for the March 2010 IEEE 802.11 meeting is to resolve all
outstanding comments, produce Draft 5.0, and recirculate.
49
MIC 2009/2010
REDES INALÁMBRICAS
The standard 802.11s and D1.00
 802.11s is an extension of the traditional 802.11 protocol for WLAN
communication and adds MESH functionality (routing) at Link layer
(Level 2).
 802.11s (MESH) is transparent for higher levels.
 802.11s Device Classes:
 Stations (STA): Non-mesh capable station
 Mesh Points (MP): Mesh capable station
 Mesh AP (MAP): MP + AP
 Mesh Portal (MPP): Entry/exit to wired network. Support transparent
bridging, address learning, and bridge-to-bridge communication (spanning
tree etc).
 Root Portal: MPP configured for topology building. Elected to become the
root of the default forwarding tree
50
MIC 2009/2010
REDES INALÁMBRICAS
Joining the Mesh
 Each MP should have more
than one Radio Interface →
more than one channel is
joined
 Each channel belongs to a
“Unified Channel Graph”,
connecting more than two
stations
 Each MP has a table with a
priority list for every active
channel
Unified Channel
Graph
MP1
MP2
MP4
MP3
51
MIC 2009/2010
REDES INALÁMBRICAS
Steps in joining a Mesh
1. MP1 “feels” some mesh frames in the air
2. MP1 tries to read the Mesh ID, the MWLAN Capability Element and
the Profile (eg. Link State)
3. If MP1 can support the connection (in terms of protocol and profile),
it sends to “Candidate Neighbours” some frames to join the mesh
4. Start of authentication
5. If authentication is succesfully completed, MP1 is connected to the
mesh
52
MIC 2009/2010
Authentication and Privacy
 No central authority or hierarchy
 Security about
 Authentication to the Mesh Network
 Confidentiality and integrity of private data
 Protection from DoS attacks
REDES INALÁMBRICAS
 Open issues
 A possible choice for having a secured authentication, provide a secure key
distribution and to prevent unauthorized connections could be the modification of
the 802.11i protocol, specifically designed for the traditional 802.11 security.
 An option is to use a centralized server for primary authentication. Once the
authentication ends successfully, the Supplicant (new MP) and the Authenticator
(a MP connected to the Mesh network) can start an handshake and then establish
a secure connection.
 Need to extend traditional 802.11i techniques for having fast-reconnect (still under
discussion as of today)
53
MIC 2009/2010
REDES INALÁMBRICAS
Routing techniques
 D1.00 defines one “Mandatory Protocol” for the Path Selection (Hybrid
wireless mesh protocol (HWMP), inspired by AODV and Tree-based
routing), but any vendor of 802.11s could define any other protocol
 An optional protocol (Radio Aware OLSR) is described in the 802.11s
draft
 MWLAN Capability Element is used to inform new nodes of which
protocol is in use