Transcript Mesh Router End Device Connects

Mesh Networking
http://research.microsoft.com/mesh
Victor Bahl
Senior Researcher
Systems and Networking Group
Microsoft Research
Team Introduction
Executive Sponsor
Craig Mundie, CTO & Senior Vice President Microsoft
Microsoft Research
Victor Bahl (Project Lead), Richard Draves, Jitu Padhye, Lili
Qiu, Alec Wolman, Brian Zill
The Venice Incubation
Jeff Erwin (Project Lead), Pierre De Vries, Ian Ferrell, Jason
Ginchereau, Steve Kelly, Alexander Popoff, Karen
Community Network
Community Network Applications
Internet use increased social contact, public participation and size of
social network. (social capital - access to people, information and
resources)
Keith N. Hampton, MIT (author of “Netville Neighborhood
Study”)
URL: http://www.asanet.org/media/neville.html
Shared Broadband Internet Access
Neighborhood watchdog (e.g. video surveillance)
Neighborhood TiVO
Medical & emergency response
Distributed backup
Neighborhood eBay, portals
Bits produced locally, gets used locally
Social interaction
Mesh Formation: Problem
Formulation
Question
How many homes in the
neighborhood have to sign
up before a viable mesh
forms?
Answer depends on
Definition of “viable”
Wireless range
Neighborhood topology
Probability of participation
by a given houshold
Example Scenario
Viable mesh: group of at least 25
houses that form a connected
graph
Topology: A North Seattle
Neighborhood. 8214 houses,
4Km x 4Km
Wireless range: 50, 100, 200 and
1000 meters
Houses decide to join at random,
independent of each other.
We consider 0.1% to 10%
participation rates.
Mesh Formation
5-10% subscription rate
needed for suburban
topologies with documented
wireless ranges
Once a mesh forms, it is
usually well-connected
i.e. number of outliers are few
(most nodes have > 2 neighbors)
Need to investigate other
joining models
Business model
considerations will be
important
Increasing range is key for good mesh connectivity
Suburbia
Upper-middle class
neighbourhood
Houses about 40-120’
apart
21 houses covering 7.8
acres or ~1/3 acre lots
Microwave ovens, cordless
phones, televisions etc.
cause interference
Angled sheetrock and
concrete walls, hills and
trees absorb signal and
create multi-path
reflections
Not a pleasant place to roll
out wireless
One reason why cellular
uses 80’-100’ masts for
their cell towers
0
20 40 60 80 100 120140 160
5 GHz:
Bandwidth is good,
provided you can get a
mesh to form
Published 802.11a ranges
led us to believe we could
achieve the yellow circle
Measured range from the
apartment trial is the red
circle
Range is not sufficient to
bootstrap mesh until
installed % is quite high (in
this diagram ~50%)
0
20 40 60 80 100 120140 160
802.11a in a Multihop Network
Impact of path length on TCP Throughput
12000
TCP Throughput (Kbps)
10000
8000
6000
4000
2000
0
0
1
2
3
4
Path Length (Hops)
5
6
7
Round Trip Delay versus
Node Density
Average RTT
avg_rtt = 0.1*curr_sample + 0.9*avg_rtt
One sample every 0.5 seconds
0.2
0.18
0.16
Average RTT
0.14
0.12
0.1
0.08
0.06
0.04
0.02
0
0
20
40
60
80
100
120
140
160
180
Time
A new 100Kbps CBR connection starts every 10 seconds,
between a new pair of nodes. All nodes hear each other.
Collision between ISM devices
Phone
Panasonic 2.4GHz Spread Spectrum Phone 5m and 1 Wall from receiver
Colliding standards
Courtesy: Mobilian Corp.
Performance worsens when there are large number of
short-range radios in the vicinity
Conclusion
Meshes are viable
existing technologies are inadequate
To make it real
Identify and solve key problems
build and deploy a mesh prototype
Problem Space
Range and Capacity [Talk by Jim K; Poster by John D. & Ranveer C.]
Electronically steerable directional antenna or MIMO for range enhancement
Multiple frequency meshes
Multi-radio hardware for capacity enhancement via greater spectrum utilization
New data channel MAC for higher throughput
Tools for predicting & analyzing network viability & performance
Multihop Routing [Talk by Rich D.; Poster & Demo by Jitu P. & Brian Z.]
L2.5 on-demand source routing. Routes selected based on link quality
Route selection with multiple radios
Security and Fairness
Guard against malicious users (and freeloaders)
EAP-TLS between MeshBoxes, PEAPv2 or EAP-TLS between clients and MeshBoxes
Priority based admission control, Secure traceroute
Self Management & Self Healing [Talk by Lili Q.; Poster by AP]
Desirable: avoid network operator - minimal human intervention
Watchdog mechanism
Data cleaning and liar detection
Online simulation based fault isolation and diagnosis
Problem Space (Cont)
Smart Spectrum Utilization
Spectrum Etiquittes
Agile Radios, cognitive radios
Cognitive software & applications
Analytical Techniques
Information theoretic tools that predict expected capacity with practical
constraints, based on experimental data
Digital Rights Management (DRM)
Broadband access will become popular with expanded digital content.
Increase the value proposition for end-users/subscribers
Ease of use (Plug and play, HCI)
Make the user experience pleasant
QoS protocols over wireless meshes to improve content delivery
Proof of Concept via rapid prototyping and testbed deployments
Scenario: Neighborhood Wireless Meshes
Internet
End Device
ITAP
Connects to a Mesh Router
Standards Compliant
Network Interface
101
Bus Stop
206
Gas Station
(Internet TAP)
Mesh Router / MeshBox
Mesh Router 7
EXIT
90
Mesh Router 5
Routes traffic within the
mesh and to the
neighborhood Internet
Gateway
Serves as access point for
End Devices
Mesh Router 2
Mesh Router
Mesh Router 3
MeshStreet
Zone
Any
Mesh Router 1
Mesh End Device
End Device
(Guest to Router 1)
End Device
Neighborhood Internet Gateway
Gateway between the mesh
nodes and the Internet
Mesh Routing Functionality
Mesh Box
Configuration
Mesh Management Module
Diagnostics Client
and Server DLLs
TCP / IP
S
E
C
U
R
I
T
Y
Link
Monitor
Module
Mesh Connectivity Layer
(MCL)
Multi-hop Routing/Bridging
Radio Selection Metric
Topology Control
Diagnostics Kernel
Module
Data Channel Radio
Miniport Driver
Control Channel
Radio
Miniport driver
Research Results
Spectrum Etiquette
P. Bahl, A. Hassan, P. Vries, Spectrum Etiquettes for Short Range
Wireless Devices Operating in the Unlicensed Band - A
Proposal,,White paper, Spectrum Policy: Property or Commons,
Stanford Law School
Multi Radio Meshes
A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou. A Multi-Radio
Unification Protocol for IEEE 802.11 Wireless Networks. BroadNets
2004 (also Technical Report, MSR-TR-2003-41, June 2003)
Determining Mesh Capacity
K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu. Impact of
Interference on Multi-hop Wireless Network Performance. ACM
Mobicom, San Diego, CA, September 2003
Mesh Self Management
L. Qiu, P. Bahl, A. Rao, and L. Zhou. Fault Detection, Isolation, and
Diagnosis in Multi-hop Wireless Networks. Technical Report, MSRTR-2004-11, December 2003
Research Results (cont.)
Single Radio Mesh Performance
R. Draves, J. Padhye, and B. Zill. Comparison of Routing
Metrics for Static Multi-Hop Wireless Networks. ACM
SIGCOMM 2004 (also Technical Report, MSR-TR-2004-18,
March 2004)
Single Radio Mesh Performance
R. Draves, J. Padhye, and B. Zill. Routing in Multi-radio, Multi-hop
Wireless Mesh Networks, To appear in ACM MobiCom 2004
Multi Radio Mesh Routing & Performance
L. Qiu, P. Bahl, A. Rao, and L. Zhou. Fault Detection, Isolation,
and Diagnosis in Multi-hop Wireless Networks. Technical
Report, MSR-TR-2004-11, December 2003
Capacity Enhancement
Problem
Improve throughput via better utilization of the spectrum
Design Constraints
Require only a single radio per node
Use unmodified IEEE 802.11 protocol
Do not depend on existence of control channel
Assumption
Node is equipped with an omni-direction antenna
- MIMO technology is OK
Multiple orthogonal channels are available
Channel switching time is 80 usecs.
- current speeds 150 microseconds
Capacity Enhancement
In current IEEE 802.11 meshes
1
3
2
5
4
6
Only one of 3 pairs is active @ any given time
With MSR’s SSCH enabled meshes
Ch 1 1
2
1
4
5
4
Ch 2 3
4
5
2
1
6
Ch 3 5
6
3
6
3
2
10 msecs
10 msecs
10 msecs
…
Performance
100 nodes, IEEE 802.11a, 13 channels, every flow is multihop
Total System Throughput
Avg. per node Throughput
4
80
3.5
Throughput (Mbps)
Throughput (Mbps)
70
60
3
2.5
50
40
30
SSCH
2
1.5
IEEE 802.11
20
1
SSCH
10
M802.11
0.5
0
10
20
30
Number of Flows
40
50
0
10
20
30
40
50
Number of Flows
Significant capacity improvement when traffic load is on multiple separate flows
Mesh Diagnosis Visualization
Module
Testbeds
Details
201
23 to 30 nodes
Inexpensive desktops (HP d530 SF)
Two radios in each node
210
220
205
203
NetGear WAG or WAB, Proxim
OriNOCO
Cards can operate in a, b or g mode.
226
204
227
221
Purpose
Approx. 61 m
Verification of the mesh software stack
Routing protocol behavior
Fault diagnosis and mesh
management algorithms
Security and privacy architecture
Range and robustness @ 5 GHz with
different 802.11a hardware
207
206
208
225
211
224
223
209
214
215
Stress Testing
Various methods of loading testbed:
Harpoon traffic generator (University of
Wisconsin)
Peer Metric traffic generator
Ad-hoc use by researchers
217
219
218
216
Approx. 32 m
Redmond Apartment Trials
Deployed by The Venice Team
Road
B
UNIT FF
B
UNIT GG
B
B
UNIT BB
B
A
31
a
FF102
FF203
BB103
a
B
b
A
ControlApt
GG302
b
B
GG202
Parking Lot
BB302
ControlApt
GG302
B
A
32
Bellaire Apts
B
BB201
Carport
A
A
A
HH301
B
Microsoft
Campus
A
A
= MeshBox
UNIT CC
Road
20 Feet
UNIT HH
B
Redmond Apartment Trial
Control Apt GG302
Apt FF201
Mesh Box
Mesh Hall (Kitchen)
Cambridge UK Trial
Deployed by The Venice Team
Working with ehome to create a media
sharing demo in collaboration with ZCast DVB trial
10 node mesh
MSR-Cambridge - 1st
Floor, Mesh box Locations
UK3Gtwy
UK6
UK-MCE20 is the
Kiosk with posters.
= Mesh Box location
= Mesh Box location
UK1 UK8
UK
MCE20
UK2
Near Term Goals
Multi-radio mesh routers
Directional Antenna enabled meshes
Multi spectral meshes
Mesh Connectivity Layer
Self Managing Meshes
Large Scale Testbeds
We hope to take this research to the Point of Irrefutability
Thanks!
http://research.microsoft.com/mesh
SSCH Algorithm & Performance
Every node has a channel hopping schedule
4 pairs of (channel, seed) = (xi, ai)
Hop to a new channel every 35 packets, 1536 bytes/packet
xi  (xi + ai) mod 13
(802.11a has 13 channels)
Parity slot xparity = a1 prevents logical partitioning
When unsynchronized, still overlap ~1/13th of time  can exchange
updated schedules
Synchronize = Change your schedule to match another node’s
Common case in sending is know recipient node’s schedule
propagation of schedule information is more frequent than start of new
flows
if wrong, pay latency penalty
Mesh Security Architecture
Philosophy
Internet
Mesh is open to all, however,
people who contribute resources
to the mesh get priority.
Internet
Gateway
Design Goals
Certificate
Guard against faulty or hacked
Mesh Boxes
Laptop
Certificate
Defend against disruption (e.g.,
denial-of-service attacks) by
malicious End Devices
Protect mesh traffic privacy
Snooper
Server
Neighborhood
File Server
Protect access to network
resources
End Device
Compromised
Mesh Box
Assumptions
Difficult to hack into a Mesh Box
(similar to cable modems)
Regulations handle malicious RF
End Device
Malicious
End Deviceattacks
Interference
Certificate
Basic Framework
Certification
Mesh Routers have built-in
public-key certificates for
authenticating to each other
Mesh Router owners use
them to issue certificates to
End Devices
Mesh Box accepts certificates
issued by any Mesh Box
within range
Access to resources is
controlled based on policy
and End Device certificate
Encryption & Anonymity
Traffic between Mesh Boxes is
encrypted to foil eavesdroppers
Misbehaving Mesh Boxes have
their certificates “blackballed”
Traffic from uncertified End
Devices is prevented from
disrupting certified traffic