Transcript Secure Network Routing: Ariadne and Skipchains

Wireless Mesh Networks
Victor Bahl
http://research.microsoft.com/~bahl
Lecture 1
MSR India Summer School on Networking
June 15, 2007
Foreword
• Mobile ad hoc networking and mesh networking is a thriving area of
research. The number of solutions & results are simply too large to
cover in a short lecture.
• This is not a lecture on (1) wireless communications (2) MAC
protocols, (3) PHY Layer techniques and (3) multi-hop routing
protocols.
• This is quick talk about what I know about building mesh networks.
Exhaustive & deep treatment of all existing results is not provided.
• These notes are an attempt to describe the main problems & the
general idea behind some of the promising solutions. At the end of
this lecture you should have a reasonably good understanding of the
state-of-art in mesh networking.
.
Topics not covered in this lecture
Due to lack of time I was not cover several important research results that
you should also be aware of.
Some of these are:
 Modulation and PHY techniques like OFDM, Analog Network Coding etc.
 Adaptive antenna technologies like MIMO, beam forming, etc.
 TCP enhancements (for mesh networking)




Routing protocols (there are hundreds……)
Multicast routing and group communications
Topology control and power management
Standards including IEEE 802.11s,…
 Security and Management
 Directional MACs etc
.
Roadmap
1. Mesh Networking & Applications
2. Basics of Radio Frequency Communications (already covered by Dr. Ramjee)
3. Multi-hop Wireless Networking
–
–
Historical background
Challenges: Mesh networking with 802.11
4. Handling the Challenges
–
Capacity Enhancement & Calculation
MMAC, SSCH, BFS-CA, HMCP, MUP, Network Coding, conflict graphs, ….
–
Routing Protocols & Link Quality Metrics
RFC 2501, RFC 3626, RFC 3684, RFC 3561, RFC 4728, ETX, LQSR, EXoR, HWMP, ETT, WCETT
–
Security & Network Management
5. Mesh Deployments – Discoveries & Innovations
–
MSR’s Mesh, MIT’s RoofNet, IIT’s DGP, Rice’s TFA, UMASS’s DieselNet, UCSB’s Mesh,
Madcity’s Mesh, JHU’s SMesh
6. Mesh Networking Standards
–
IEEE 802.11s (IETF standards covered previously)
7. References
.
Will not
cover,
tutorial notes
available on
request
Mesh Networking & Applications
Wireless Mesh Networking
Definition
A wireless mesh network is a peer-to-peer multi-hop wireless network
in which participant nodes connect with redundant interconnections
and cooperate with one another to route packets.
– Unlike Mobile Ad hoc NETworks (MANETs) where routings node are
mobile, in mesh networks routing nodes are stationary.
– Mesh nodes may form the network's backbone. Other non-routing mobile
nodes ("clients") may connect to the mesh nodes and use the backbone to
communicate with one another over large distances and with nodes on the
Internet
.
Characteristics of a Mesh Network
Mesh Network
–
–
–
–
–
Classic Hub & Spoke Network
Can grow “organically”
Does not require infrastructure support
Is fault tolerant
Requires distributed management
Offers higher capacity (via spatial diversity & power
management), but
• Too many nodes  shared bandwidth may suffer due to interference
• Too few nodes  route maintenance is difficult disconnections possible
– Identity and security management is a challenge
.
The Mesh Networking World
Mesh Node
Mesh
Node
Web
Content
Mesh
Node
Corporate
Data
Communication
Mesh
Node
Games
Mesh
Node
Shopping
Mesh
Node
Media
Internet
Broadband
Neighbourhood
Traditional Last Mile Territory
.
Home Mesh
Scenario 1: Broadband Internet Access
Internet
•
Last Mile
Equipment capital cost
The scale of touching / maintaining so many endpoints
The physics of running cable large distances over unfriendly terrain
Political, social and territorial implications
Wireless mitigates these issues but introduces others
–
–
–
–
•
Middle Mile
Cost of middle and last miles make physical wired infrastructure not an option in
rural areas and many countries
–
–
–
–
•
Backbone
Range
Bandwidth
Spectrum availability
Cost & maintenance issues of new hardware / standards
Mesh networking makes wireless workable
–
–
Range & bandwidth addressed by shorter links
Cost & maintenance addressed by building on commodity standards
.
Scenario 2: A Community Mesh Network
Organic – Participants own the equipment and the network
.
Community Mesh Network Applications
•
•
•
•
•
•
Shared broadband Internet access
Neighborhood watch (e.g. video surveillance)
Shared media content (e.g. neighborhood DVR)
Medical & emergency response
Neighborhood eBay (garage sales, swaps)
Billboards (babysitter/service recommendations, lost cat, newsletter)
 Bits produced locally, gets used locally
 Social interaction
• Distributed backup
Internet use increased social contact, public participation and size of social
network. (social capital - access to people, information and resources)
Prof. Keith N. Hampton (author of “Netville Neighborhood Study”)
URL: http://www.asanet.org/media/neville.html
.
Scenario 3: Home Mesh
Services
Entertainment
Entertainment
E-Business, Services
Pre-Recorded Content
Personal Media
Broadband
•
•
•
Extend Access Point (AP) coverage
Better spectrum (re)use  greater capacity
Automatic discovery, plug-and-play networked home devices:
– AV equipment (Cameras, TV, DVD, DVR, satellite/cable)
– Phones (Cellular and POTS)
– Traditionally disassociated smart devices (PDAs, AutoPC)
– Home infrastructure items (Light switches, HVAC controls)
.
Scenario 4: Blanket City-wide Wireless Coverage
Philadelphia picks Earthlink for City Wireless, TechNew World, October 5, 2005
San Francisco Keeps Pushing City Wide WiFi, CNET News.com, August 17, 2005
“San Francisco Mayor Gavin Newsom wants to make Wi-Fi coverage in the city as ubiquitous as the fog that blankets
its neighborhoods.”
Wi-Fi Hits the Hinterlands, BusinessWeek Online, July 5, 2004
“Who needs DSL or cable? New “mesh” technology is turning entire small towns into broadband hot spots”, Rio Rancho
N.M., population 60,000, 500 routers covering 103 miles2
NYC wireless network will be unprecedented, Computerworld, June 18, 2004
“New York City plans to build a public safety wireless network of unprecedented scale and scope, with a capacity to
provide tens of thousands of mobile users”
Rural Areas need Internet too! Newsweek, June 7, 2004 Issue
“EZ Wireless built the country's largest regional wireless broadband network, a 600-square-mile Wi-Fi
blanket, and activated it this February”, Hermiston, Oregon, population 13,200, 35 routers with 75
antennas covering 600 miles2
Mesh Casts Its Net, Unstrung, January 23, 2004
“Providing 57 miles2 of wireless coverage for public safety personnel in Garland Texas”
PCCW takes Wireless Broadband to London, The Register, September 2, 2005
“Prices for the service in UK start from £10 / month for 256 Kbps to £18 /month for 1 Mbps”
Anacapa and Firetide Bring Free Wireless Internet to La Semaine Italienne in Paris, France ,
Business Wire, 24 May, 2005
Bell Canada and Nortel Networks launch Project Chapleau,
designed to evaluate broadband in rural Canada, Optical Networks Daily, 18 July 2005
.
Scenario 5: All-Wireless Office
• Older buildings
• No wires
• For small offices (~100 PCs) • No switches
• No APs
– Rapid deployment
– Low cost
– Short-term offices
• Not a replacement for wire
.
Scenario 6: Spontaneous “Mesh”
Definition
A temporary ad-hoc multihop wireless network for exchanging voice, video or
data, for collaboration in a locally distributed environment, when no permanent
infrastructure or central control is present. Usually between portable wireless
devices.
1. Peer Calling & Party Lines
– P2P calling within local groups – conferences, events, school campus,…
2. Public Safety
Fire and rescue teams need ad-hoc
communication at incident sites
.
3. Real Time Advisory
Drivers need traffic information and
advisories generated in real time
Grass Roots Mesh Deployments
Academia
– The Roofnet Project (MIT, USA) - http://pdos.csail.mit.edu/roofnet/doku.php
802.11 mesh network for broadband IA in cities
– The CITRIS TIER Project (UC Berkeley, USA) - http://tier.cs.berkeley.edu/
Technology and Infrastructure for emerging regions
– The Digital Gangetic Plains Project (IIT Kanpur, India) - http://www.iitk.ac.in/mladgp
802.11-based low-cost Networking for rural India
– The TFA Project (Rice University, USA) - http://taps.rice.edu/index.html
Technology for All Project
– ….
Community Mesh Networks
– Community Network Movement - http://www.scn.org/commnet/
– Seattle Wireless - http://www.seattlewireless.net/
– Champaign-Urbana Community Wireless Network - http://www.cuwireless.net/
– Kingsbridge Link, U.K. - http://www.kingsbridgelink.co.uk/
– ….
.
Industry Breakdown
Infrastructure Based
Infrastructure-less
Internet
UNIVERSITY
Internet
101
Bus Stop
206
Poletop Radio
Gas Station
(Internet TAP)
Mesh Router 7
EXIT
90
Mesh Router 5
Mesh Router 2
Mesh Router 3
MeshStreet
Zone
Any
SkyPilot, QualNet (Flarion),
Motorola (Canopy) IRoamAD, Vivato,
Arraycomm, Malibu Networks,
BeamReach Networks, NextNet
Wireless, Navini Networks, etc.
Mesh Router 1
Mesh End Device
End Device
(Guest to Router 1)
Meshnetworks Inc.,Radiant Networks,
Invisible Networks, FHP, Green Packet Inc.,
LocustWorld, etc.
Architecture effects design decisions on
Capacity management, fairness, addressing & routing, mobility
management, energy management, service levels, integration with the
Internet, etc.
.
Industry Deployment Scenarios
http://www.unstrung.com/insider/
March 2005, Source: Unstrung Insider
.
What about WiMAX?
IEEE 802.16d for developing/rural use (.16e targets mobile scenarios)
– Still needs market momentum around hardware optimisation: size, power,
efficiency and most important—cost
WiMAX as a last-mile solution?
– In low-density areas, WiMAX requires high-power towers or lots of
towers: (=> cost goes up)
– In NLOS environments, range impacts bandwidth through reduced
modulation
– WiMAX CPE expensive in next 3-5 years (~ $150-250)
WiMAX feeding a mesh can be a good solution
– Mesh extends WiMAX tower reach
– Mesh simplifies the financials by greatly reducing equipment cost
– Mesh is robust and deal with network vagaries
.
WiMAX + Mesh
WiFi Meshes can add value to WiMAX in several ways:
– Reduce CPE costs
– Extend range of WiMAX tower without compromising speed
– Replace high-price WiMAX towers with cheaper mesh nodes
WiMAX
Only
WiMAX
with
Mesh
16
QAM
8PSK QPSK
FSK
A
.
16
QAM
16
QAM
16
QAM
16
QAM
A
Multi-Hop Wireless Networking
Historical Perspective
Packet Radio Network (PRNET), 1972-1982
•
Band: 1718.4-1840 MHz; Power: 5 W; Range: 10 km; Speed:100-400 Kbps, Addressing: Flat;
Routing: Distance Vector; Scale: 50+
Survivable Adaptive Networks (SURAN), 1983-1992
•
Band: 1718.4-1840 MHz; Power: 5 W; Range: 10 Km; Speed: 100-400 kbps, Addressing:
Hierarchical; Routing: Distance Vector; Scale: 1000+ (Low cost packet radio)
Global Mobile Information Systems (GLOMO), 1995-2000
•
e.g. NTDR, Band: 225-450 MHz; Power: 20 W; Range: 11-20 Km; Speed: 300 kbps,
Addressing: Flat; Routing: Link-state / 2-level clusters; Scale: 400+
IETF Mobile Ad Hoc Networks (MANET) Working Group, 1997 –
•
RFC 2501 (Eval), RFC 3561 (AODV), RFC 3626 (OLSR), RFC 3684 (TBRPF), Drafts – DSR,
DYMO, Multicast, OLSRv2
PRNET Van
MSR Mesh Networking Project (2002 – 2005)
IEEE 802.11s Working Group, 2004 .
Challenge:
Mesh Networking with IEEE 802.11
The MAC Problem – Packets in Flight Example
RTS
RTS
RTS
RTS
1
2
3
RTS
4
5
6
7
8
9
10
CTS
CTS
Backoff window doubles 
2 packets in flight! Only 4 out of 11 nodes are active….
.
11
Throughput: Internet Gateway Example
Internet
RTS
RTS
RTS
CTS
Backoff window doubles
.
Backoff window doubles
The Scheduling Problem
Conflict graph
A
B
A
A
B
B
D
D
A
C
B
D
C
E
D
E
1
Choice 1
Choice 2
D
 yes
A
B
0
1
1
D
C
D
A
B
A
D
D
 yes
B
A
C
A
B
E
E
B
D
D
B
C
A
B
A
E
If future traffic is not known, which one do you schedule first?
.
The Fairness Problem
A
1
B
C
2
D
Jinyang-MobiCom-2001
Information Asymmetry
– A & C do not have the same information
 C knows about flow 1 (knows how to contend)
 A does not know about flow 2
– Flow 2 always succeeds, Flow 1 suffers
 When RTS/CTS is used
– A’s packets are not acknowledged by B
» A times out & doubles it’s contention window
 When RTS/CTS is not used
– A’s packet collide at B, but Flow 2 is succesful
» A times out & double it’s contention window
– Downstream links suffer
.
Gambiroza-MoiCom-2004
The Fairness Problem (2)
ITAP
Camp-DC-2005
•
Location closest to gateway gets the more packets
•
Nodes farthest from the gateway get very little bandwidth and can get starved
•
Possible solution: Rate control on each node with fairness in mind
– Need topology & traffic information to calculate fair amount
– Global vs. distributed solution
.
The Fairness Problem (3)
MAC attempts to provide fairness at packet level not flow level
Capture phenomena
 Winner of competing flows has a higher chance of winning contention again
Different levels of interference at different links (different neighborhood)
 Highly interfered flows can be drowned
Nandagopal-MobiCom-2000
Qiu-MSRTR-2003
A
C
B
F1
F2
O
P
D
F3
Q
E
F
F4
R
G
F5
S
T
U
Flow1
Flow2
Flow3
Flow4
Flow5
2.5 Mbps
0.23 Mbps
2.09 Mbps
0.17 Mbps
2.55 Mbps
Active area of research
- MACAW, WFQ, DFS, Balanced MAC, EBF-MAC, PFCR, ….
.
The Path Length Problem
Experimental Setup
Impact of path length on throughput
• 23 node testbed
10000
9000
One IEEE 802.11a radio per node
(NetGear card)
• Randomly selected 100 senderreceiver pairs (out of 23x22 =
506)
8000
Throughput (Kbps)
•
7000
6000
5000
4000
3000
2000
1000
0
• 3-minute TCP transfer, only one
connection at a time
.
0
1
2
3
4
5
6
Byte-Averaged Path Length (Hops)
If a connection takes multiple paths over lifetime,
lengths are byte-averaged
Total 506 points.
Robert Morris’s Rooftnet MSR Mesh Summit 2004 Presentation
The Collision Problem
Actual Roofnet b/w is often much lower
Multi-hop collisions cut b/w by about 2x
Expected multi-hop b/w based on single-hop b/w
The Node Density Problem
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.
.
The Power Control Problem
Tight power control reduces interference and increases throughput
D
B
A
C
– A & B do not detect RTS/CTS exchange between C & D
– B does not detect data transmission from D to C
– B’s transmission to A results in packet collision at C
.
The Power Control Problem (2)
Tight power control reduces interference & increases overall throughput
A
D
B
C
But it also disconnects the network. So what’s the “right” power control
algorithm?
A
D
B
C
.
The Capacity of Mesh Nodes
What is the maximum achievable capacity of a mesh network with N nodes?
Gupta-IEEEIT-2000
Optimal Case
Average Case
– Nodes are optimally
located, destinations are
optimally located
– Randomly located nodes and
destinations
– Traffic pattern are random
– Traffic patterns are fixed
– Optimally spatio-temporal
scheduling, routes, ranges
for each transmission
– As
n
each node obtains
 1  bits/sec

O
 n


.
– Each node chooses same
range
– Each n   node obtains

1  bits/sec
O
 n log n 


The Capacity Calculation Problem
Gupta and Kumar 2000
– Theorem for stationary ad hoc nodes in the worst case traffic scenario
Determines asymptotic, pessimistic bounds on performance
– Every node in the mesh is active (either transmitting or receiving)
Does not answer:
– What is the capacity of a mesh which is using multiple channels,
directional antennas, tight power control?
.
What is the Real Capacity of a Chain?
…but the radio’s interferance range is > radios communication range
Source
1
Destination
2
3
4
5
6
With Ideal MAC, Chain Utilization = 1/3
With interferences, Chain Utilization = 1/4
Jinyang-MobiCom-2001
….but this is achievable only with optimum scheduling and optimum offered load!,
…with random scheduling and random load, utilization ~ 1/7 !
.
Routing Problem: Which to Choose?
Unicast Ad Hoc Multi-hop Routing Protocols
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
ABR (Associativity-Based Routing Protocol)
AODV (Ad Hoc On Demand Distance Vector)
ARA (Ant-based Routing Algorithm)
BSR (Backup Source Routing)
CBRP (Cluster Based Routing Protocol)
CEDAR (Core Extraction Distributed Ad hoc Routing)
CHAMP (CacHing And MultiPath routing Protocol)
CSGR (Cluster Gateway Switch Routing)
DART (Dynamic Address Routing)
DBF (Distributed Bellman-Ford)
DDR (Distributed Dynamic Routing)
DNVR (Dynamic Nix-Vector Routing)
DSDV (Dynamic Destination-Seq. Dist. Vector)
DSR (Dynamic Source Routing)
DSRFLOW (Flow State in the DSR)
DYMO (Dynamic Manet On-Demand)
FORP (Flow Oriented Routing Protocol)
FSR (Fisheye State Routing)
GB (Gafni-Bertsekas)
GLS(Grid) (Geographic Location Service)
GPSAL (GPS Ant-Like)
GSR (Global State Routing)
Guesswork
HARP (Hybrid Ad hoc Routing Protocol)
HSLS (Hazy Sighted Link State)
HSR (Hierarchical State Routing)
HSR (Host Specific Routing)
IARP (Intrazone Routing Protocol)
IERP (Interzone Routing Protocol)
.
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
LANMAR (LANdMARk Routing Protocol)
LAR (Location-Aided Routing)
LBR (Link life Based Routing)
LCA (Linked Cluster Architecture)
LMR (Lightweight Mobile Routing)
LQSR (Link Quality Source Routing)
LUNAR (Lightweight Underlay Network Ad hoc
Routing)
MMRP (Mobile Mesh Routing Protocol)
MOR (Multipoint On-demand Routing)
MPRDV (Multi Point Relay Distance Vector)
OLSR (Optimized Link State Routing)
OORP (OrderOne Routing Protocol)
DREAM (Distance Routing Effect Algorithm for
Mobility)
PLBR (Preferred Link Based Routing)
RDMAR (Relative-Distance Micro-discover Ad hoc
Routing)
Scar (DSR and ETX based)
SSR (Signal Stability Routing)
STAR (Source Tree Adaptive Routing)
TBRPF (Topology dissemination Based on ReversePath Forwarding)
TORA (Temporally-Ordered Routing Algorithm)
WRP (Wireless Routing Protocol)
ZHLS (Zone-Based Hierarchical Link State)
ZRP (Zone Routing Protocol)
….
The Path Selection Problem
Several link quality metrics to select from
– Hop count
–
–
–
–
–
Round trip time
Packet pair
Expected data transmission count incl. retransmission
Weighted cumulative expected transmission time
Signal strength stability
–
–
–
–
Energy related
Link error rate
Air Time
…
Which to select? We still don’t have a interference-aware metric! We still
don’t know how to measure interference…..
.
Baseline comparison of Metrics
Single Radio Mesh
Experimental Setup
Median path length:
HOP: 2, ETX: 3.01, RTT: 3.43, PktPair: 3.46
• 23 node testbed
1600
One IEEE 802.11a radio per node
(NetGear card)
• Randomly selected 100
sender-receiver pairs (out of
23x22 = 506)
• 3-minute TCP transfer, only
one connection at a time
1400
Median Throughput (Kbps)
•
1200
1000
800
600
400
200
0
HOP
ETX
RTT
PktPair
ETX performs the best
Draves-MobiCom-2004
.
Baseline Comparison of Metrics
Two Radio Mesh
Draves-SIGCOMM-2004
Experimental Setup
Median path length:
HOP: 2, ETX: 2.4, WCETT: 3
• 23 node testbed
Median Throughput of 100 transfers
• 3-minute TCP transfer
• Two scenarios:
– Baseline (Single radio):
 802.11a NetGear cards
– Two radios
 802.11a NetGear cards
 802.11g Proxim cards
.
3500
2989.5
3000
Throughput (Kbps)
• Randomly selected 100
sender-receiver pairs (out of
23x22 = 506)
Single Radio
Two Radios
2500
2000
1601
1379
1500
1508
1155
844
1000
500
0
WCETT
ETX
Shortest Path
WCETT utilizes 2nd radio better
than ETX or shortest path
But with different traffic pattern….
226
Trace Capture
• 1 workstations connected via Ethernet
• Traces captured during 1-month period
227
Erickson-MobiSys-2006
225
219
EL32
Trace Replayed
• Testbed of 22 mesh computers in office environment
• 2 IEEE 802.11a/b/g cards per computer
215
217
220
218
216
214
211
210
209
UP
DN
208
207
204
205
~ 76 m
206
203
202
~ 32 m
Similar performance
.
201
The Multicast Problem
A multicast group is defined with a unique group identifier.
Nodes may leave or join the group anytime
 In wired networks physical network topology is static
 In ad hoc multi-hop wireless networks physical topology can change often
– Need to Integrate with unicast routing protocols
Many proposals [Tree-based, Mesh-based, Location-based] which one
to use?
- ABAM (On-Demand Associatively-Based Multicast)
- FGMP (Forwarding Group Multicast Protocol)
- ADMIR (Adaptive Demand-Driven Multicast Routing)
- LAM (Lightweight Adaptive Multicast)
- AMRIS (Ad hoc Multicast Routing utilizing Increased id-numberS)
- MAODV (Multicast AODV)
- DCMP (Dynamic Core Based Multicast Routing)
- MCEDAR (Multicast CEDAR)
- AMRoute (Adhoc Multicast Routing)
- MZR (Multicast Zone Routing)
- CAMO (Core-Assisted Mesh Protocol)
- ODMRP (On-Deman Multicast Routing Protocol)
- CBM (Content Based Multicast)
- SPBM (Scalable Position-Based Multicast)
- DDM (Differential Destination Multicast)
- SRMP (Source Routing-based Multicast Protocol)
- DSR-MB (Simple Protocol for Multicast and Broadcast using DSR) - …
-…
.
The Interference Detection Problem
When two systems operate on overlapping frequencies, there exists a
potential for harmful interference between them
– Performance degradation on both systems
Conflict graph is determined by the “Interference Graph”
To determine the Interference Graph, require
– Knowledge of packet transmission from nodes that are not “visible”
– Knowledge of physical location of nodes within the network
– Knowledge of whether or not multiple transmissions increase ot decrease
interference?
Interference Graph can change
– as rapidly as the environment
– when a node leaves or join the network
.
The Transport Layer Problem
• Majority of the Internet traffic is TCP
• Packet losses & delays in wireless can occur due to
– Environmental fluctuations resulting link failures
– Stochastic link performance due to rapidly changing error rates
– CSMA/CA assumes loss is due to congestion and back-off’s
• TCP assumes packet losses are due to congestion
– Times out when no ACK is received
– Invokes slow start, when instead the best response would be to retransmit
lost packets quickly
• RTT calculation can change as rapidly as the environment (link)
changes
Can we solve this problem without changing the end-to-end semantics?
.
The Security Problem
Two type of attackers:
– External malicious node (no crypto keys)
– Compromised node (attacker captures legitimate node and reads out all
cryptographic information)
Attacks
– Selfish behavior, do not forward other node’s packets
– Denial of Service (DoS)
 Jamming
 Resource consumption attack
 Routing disruption (e.g. Wormhole attack)
 Inject malicious routing information
Hu-MobiCom-2002
Ongoing Research
–
Possible solutions: SEAD, Ariadne, SRP, CONFIDANT, …
Bucheggar-MobiHoc-2002
.
The Spectrum Etiquette Problem
Local behavior affects Global Performance!
Doesn’t care
Node D
Node E
100 meters
Node A
Node B
200 meters
Node C
200 meters
120
Packets get dropped!
Normalized Percentage
100
80
60
40
20
0
.
Base
One TCP
10% Drop rate
Consequently we…..
Must Increase Range and Capacity
Single radio meshes built on 802.11 technologies are not good enough. We must extend
the range of radios; we must understand the achievable capacity in an ideal wireless
mesh and we must build technology to approach this capacity?
Must Improve Routing Performance
Routing protocols based on shortest-hop are sub-optimal. We must build a routing
protocol that adapts quickly to topology changes, incorporates wireless interference and
link quality.
Must Provide Security and Fairness
Is it possible to ensure fairness and privacy for end-users and security for the network?
We must ensure that no mesh nodes starves and that the mesh guards itself against
malicious users.
Must Provide Self Management
An “organic network” should be both self-organizing and self managing? To what extent
can we remove the human out of the loop?
.
Must Develop a Resilient Framework for Applications
In a environmentally hostile environment, we must provide a framework for applications to
work robustly.
.
Handling the Challenges
.
Strategies for increasing Capacity
Strategy 1: Use all available channels
–
Avoid spectrum waste
Strategy 2: Improve modulation, reception, and coding
–
Today ~ 2.5 bits/Hz (.11g), Soon ~ 4.5 bits / Hz (.11n)
–
Network coding
Strategy 3: Improve spatial reuse by reducing interference
–
Fine grain transmit power control
–
(Steerable) directional antennas and directional MACs
Strategy 4: Navigate around harmful interference
–
Interference aware least cost routing
.
Will not
cover
Strategy 1: Multi-Channel Communications
Goal
Assign n non-interfering channels to n pair of nodes such that n packet
transmissions can occur simultaneously.
Knobs
Single
Channel
Single Radio
Multiple Radio
Multiple Channels
Today
☺
X
☺
.
Single Radio – Multiple Channels (SR-MC)
Distributed: Use a modified RTS/CTS sequence to negotiate channels
– Problem
 How does the sender know which channel the receiver is listening on?
– Solutions
 Receive on all channels simultaneously
– Simplest solution but too costly - will not consider here
 Use a dedicated rendezvous channel
 Use a synchronized hopping protocol
 Provide multiple rendezvous opportunities
Centralized: Compute channel assignments using global knowledge
Scope of Coverage
We will cover schemes that work on commodity radios only
.
Packets-in-Flight Example Revisited
Negotiating Channel with RTS / CTS
RTS (C1,C3,C7)
C2
1
RTS (C3,C5,C7,C11)
C1
2
3
C2
4
CTS (C1, C7)
5
6
C11
7
8
C1
9
CTS (C11)
10 nodes are active, 5 packets in flight, 150% improvement!
.
10
11
Note: Hidden Terminal – Multi-Channel Case
Let C1 be the rendezvous channel
γ can hear traffic on C1 only, doesn’t hear the CTS from β consequently doesn’t
know anything about traffic on C6 (δ is too far to hear anything from β)
α
γ
β
C1
C1
C11
C1
RTS
(C 6)
CTS
RTS
C1
C6
C6
CTS
Collision
Possible solution: Use multiple radios
.
Data
C6
C6
on
Data
(C 6)
on C
6
C6
Data on C6
Time
δ
So-MobiHoc-2004
Implementation Option for SR-MC
Buffer packets, switch between channels
Chandra-INFOCOM-2004
Channel switching speed:
Today - 5 milliseconds
Possible - 80 microseconds
Application Layer
User-level
Kernel-level
TCP/IP, Network Stack
802.11 Device Driver
Switching logic
Packets for C1
Packets for C11
Firmware
802.11 hardware
Packets for C6
Multi-Channel Medium Access Control (MMAC)
Idea: Periodically rendezvous on a fixed channel to decide the next channel
• Divide time into beacon intervals
• Divide a beacon interval into two phase
So-MobiHoc-2004
– Negotiation Phase: All nodes switch to a pre-defined common channel
and negotiate the channel to use
– Transfer Phase: Once a channel is selected, the source & receiver switch
to this channel and data transfer occurs during this phase
Issues
• Requires tight clock synchronization
• Packets to multiple destinations can incur high delays
• Congestion on the common channel
• Common channel goes bad, everything goes bad
• Not able to handle broadcasts
.
Slotted Seeded Channel Hopping (SSCH)
•
•
Divide time into slots
At each slot hop to a different channel
–
•
•
Bahl-MobiCom-2004
Nodes hop across channels to distribute traffic
Senders and receivers probabilistically meet & exchange schedules
Senders loosely synchronize hopping schedule to receivers
Characteristics

Distributed: every node makes independent choices

Optimistic: exploits common case that nodes know each others’
channel hopping schedules

Traffic-driven: nodes repeatedly overlap when they have packets to
exchange
.
SSCH Rendezvous
Divide time into slots: switch channels at beginning of a slot
New Channel = (Old Channel + seed) mod (Number of Channels)
seed is from 1 to (Number of Channels - 1)
(1 + 2) mod 3 = 0
Seed = 2
Seed = 1
1
0
2
1
0
2
1
0
0
1
2
0
1
2
0
1
3 channels
E.g. for 802.11b
Ch 1 maps to 0
Ch 6 maps to 1
Ch 11 maps to 2
(0 + 1) mod 3 = 1
• Enables bandwidth utilization across all channels
• Does not need control channel rendezvous
.
SSCH Syncing Seeds
• Each node broadcasts (channel, seed) once every slot
• If B has to send packets to A, it adjusts its (channel, seed)
Seed 2
2
2
2
2
2
2
2
2
2
1
0
2
1
0
2
1
0
3 channels
B wants to start a flow with A
Seed
1
2
0
2
1
0
2
1
0
1
1
2
2
2
2
2
2
2
Follow A: Change next (channel, seed) to (2, 2)
Stale (channel, seed) info simply results in delayed syncing
.
Using all Available Channels with SSCH
In current IEEE 802.11 meshes
1
3
2
5
4
6
Only one of 3 pairs is active @ any given time
With proper use of channels
Ch 1 1
2
1
4
5
4
Ch 6 3
4
5
2
1
6
Ch 11 5
6
3
6
3
2
10 msecs
.
10 msecs
10 msecs
…
SSCH Performance
100 nodes, IEEE 802.11a, 13 channels, every flow is multihop
Total System Throughput
Avg. per node Throughput
4
80
Throughput (Mbps)
60
SSCH
50
40
30
SSCH
Throughput (Mbps)
3.5
70
3
2.5
2
SSCH
1.5
IEEE 802.11
20
IEEE 802.11a
10
1
SSCH
0.5
0
10
20
30
40
Number of Flows
50
M802.11
IEEE 802.11a
0
10
20
30
40
50
Number of Flows
Significant capacity improvement when traffic load is on multiple separate flows
.
How many Channels can we really use?
Banerjee-SIGMETRICS-2006
2.4 GHz ISM band use in 802.11b
Ch 1
Ch 6
Ch 11
• IEEE 802.11{b,g} partitions the allocated 83.5 MHz
spectrum into 11 channels
– Only channels 1, 6 and 11 are mutually non-overlapping
• But…using only the orthogonal channels may waste
spectrum
.
Overlapped Channels do work!
Link A, Channel 1
Distance
(X-axis)
Link B, Channel Y
UDP Throughput (Mbps)
6
ChSep = 5
ChSep = 2
ChSep = 1
5
4
ChSep = 0
3
0
10
20
30
40
50
Distance (meters)
LEGEND
• Minimum distance between links for different choices
of channel
Non-overlapping channels, A = 1, B = 6
5
separation
Partially Overlapped Channels, A = 1, B = 3
2
Partially
Overlapped
Channels,
A
=
1,
B
=
2
1
• For every channel separation there is a minimal distance
0
Same channel, A = 1, B = 1
• Model-based algorithmic approach for channel assignment in wireless
Channel Separation
mesh networks
.
60
Notes on Single Radio – Multiple Channels
•
Single radio solutions can be applied to multi-radios nodes since in most
cases the number of channels is greater than the number of radios in the
node.
•
Compared to multi-radio solutions, single radio solutions are power efficient –
but power is not the primary concern in most mesh networks
•
Single radio solutions are less costly than multi-radio solutions but radios are
fairly inexpensive
•
Switching speeds and mute-deaf-time is a problem in single radio solutions
but switching speeds are being reduced dramatically
•
When distance between nodes is large, need not restrict operation to nonoverlapping channels only
…so now lets look at multi-radio solutions
.
Single Node Multiple Radio - Interference Study
Question:
Do two radios operating on non-overlapping channel interfere?
Experimental setup:
HOP 1
A
TCP
B
6” separation between B & C radios
C
TCP
HOP 2
.
D
802.11a/g Interference Results
40.00
35
Hop 2
Netgear: A to B Hop
TCP Throughput (Mb/Sec)
30
Throughput (Mb/sec)
Netgear: C to D Hop
25
20
15
10
5
35.00
Hop 1
30.00
25.00
20.00
15.00
10.00
5.00
0.00
0
64,64
60,64
Channels
56,64
52,64
Same channel or channel
separation of 4 causes
46% - 49% reduction in overall
throughput
Hop1 = A, Hop2 = G
Hop1 = G, Hop2 = A
802.11a link causes a 22%
reduction in overall throughput,
and a 63% reduction in
throughput on the 802.11g link.
Surprise: 802.11g does not affect 802.11a
Implications
• Interference even when radios are placed 6” apart is significant
• Significant RF hardware shielding work is needed
.
Single Node Multiple Radios
Channel 1
Channel 11
t1
Source
Mesh Box
Destination
Let’s assume we can build “mesh-boxes” with enough separation /
shielding between radios that performance does not suffer.
Then interesting problem to consider
(1) How should we assign channels to each interface?
 Don’t want to cause network partitions
(2) Which interface should we send the packet on?
 State-of-art metrics (hop count, ETX, SRTT, packet-pair) are not
suitable for multiple radio / node. As they do not leverage channel,
range, data rate diversity.
.
Multiple Radios - Multiple Channels
Options to consider
Static Assignment
One channel / radio for all time
 Suboptimal use of spectrum
 Some routes may be suboptimal
Dynamic Assignment (all SR-MC strategies apply)
Channels assigned to match traffic patterns and/or to reduce interference
 Interference patterns can change,
network may get disconnected
Hybrid Assignment
One channel to one radio for all time, for all other radios, channels are
assigned dynamically to match traffic patterns and/or reduce interference
.
Static Assignment (1)
2 radios / node
Draves-MobiCom-2004
All nodes use common set of channels
A
11
1
B
11
1
C
11
1
11
1
1
D
E
11
.
11
F
Suboptimal use of
spectrum
Static Assignment (2)
2 radios / node, 4 channels
Raniwala-Infocom-2005
Different nodes use different channels
A
52
56
52
B
52
60
C
60
Some routes may
be suboptimal
(e.g. B->F)
D
60
E
.
64
F
Dynamic Assignment
N radios / node; M channels; N < M
Interfaces can switch channels as needed
A
B
C
Coordination may be
needed before each
transmission
D
E
• MMAC
• SSCH
• BFS-CA
F
See section on single radio – multiple channels
.
Hybrid Assignment
Hybrid Multichannel Control Protocol (HMCP)
• Each node has two interfaces (1 fixed, 1 switch-able)
– Connectivity is maintained + all channels used
Kyasanur-WCM-2006
• Every node picks a channel as it’s fixed channel
– Different nodes use different fixed channels
• Sender tunes it’s “switchable” interface to receiver’s fixed channel to
send packets
– Once a “connection” is made, there may not be a reason to switch
channels again for that particular flow.
.
HMCP Channel Selection
Challenge: Nodes in a neighborhood should use different fixed channels
Fixed Channel Selection
– On startup pick a random fixed channel
– Periodically send a “hello” pkt. containing fixed channel & 1-hop neighbors
info. on all channels (using the switchable interface)
– Maintain a NeighborTable containing fixed channels being used by
neighbors
– Select the channel with fewest nodes as a candidate
 Use 2-hop neighbor information
– Change fixed channel to candidate channel probabilistically to avoid
oscillations
Issues
– High overhead for broadcast packets
.
Adya-BroadNets-2004
Which Interface should we send the packet on?
A Simple Approach: For every transmission select the interface with the
“best” channel & transmit on it
 Multi-Radio Unification Protocol (MUP)
Pros:
- Locally optimizes use of available spectrum
- Does not require changes to routing protocols or application-level software
- Interoperates with legacy hardware
- Does not require global topology information
Cons:
– For one-hop ad hoc – works great. For meshes need metrics that combine
link selection metrics into a path selection metric (will see)
.
MultiRadio Unification Protocol (MUP)
Illustration of Channel Switching
Goal
Allow nodes with multiple radios to locally
optimize use of available spectrum and
hence increase capacity
Ch. 0
0
MUP Enabled
1
Operation
• Set the network interface cards on different
frequency channels
Ch. 1
• Periodically monitor channel / Link
quality on each interface
• Select the interface with the “best” channel
and transmit packets
Does not require global topology
information
Adya-BroadNets-2004
.
MUP in a Neighborhood
252 houses in a Seattle neighborhood
(Green Lake Area)
Mesh formation among 35
randomly selected houses
Web surfer
40-50% reduction in delay
compared to a one-radio network
.
ITAP
Routes via RFC 3561 (AODV)
Why MUP is not enough?
MUP is a link metric not a path metric. Routing protocols that use MUP do not
– Leverage channel diversity
 A two hop path with hops on different channels is better than a path with both
hops are on the same channel.
– Leverage range and data rate diversity
 A path with two 6 Mbps hops is better than a path with a single 1 Mbps hop. MUP
will take the 1Mbps path.
 …..but a path with four 6 Mbps hops is worse than a path with a single 2 Mbps
hop. MUP and metrics like ETX may take the four-hop path, depending on delay
& loss rate.
Note: Striping protocols are not enough
–
–
–
Packet-level striping results is packet reordering, and hence poor TCP throughput
Flow-level striping requires a routing algorithm!
MUP may work, but only if radios have identical range.
Bottom Line: Need a routing protocol / metric that takes bandwidth, loss rate, and channel diversity into
account.
.
…about routing in mesh networks
The Routing Problem
Why not simply use traditional routing protocols
(RIP/OSPF/etc)?
• Network topologies are dynamic due to router mobility & environmental
fluctuations
– Dynamic topology may prevent routing protocol convergence
• Many links are redundant (routing updates can be large)
• Periodic updates may waste bandwidth & batteries
• Computed routes may not work due to unidirectional links
• Wireless makes routing protocols easy to attack
• Link quality, spectrum utilization and interferences are uniquely important
for path selection
.
Desirable Qualitative Properties
•
•
•
•
•
•
•
Distributed operation
Loop-freedom
Corson-RFC2501-1999
Demand-based operation
Proactive operation
Attack resistant & Secure
“Sleep” period operation (friendly to power management)
Unidirectional link support / asymmetric link support
Implementation
– Layer 3 - traditional “network layer” / IP layer
 Interoperable internetworking capability and consistency over a heterogeneous networking
infrastructure.
– Layer 2.5
 Agnostic of IPv4 or IPv6 issues and can incorporate link quality measures more easily
 Capable of handling multiple wireless & wired networking technologies
.
Routing and Addressing
Many choices, which is the best one?
– Flat addressing - Each node runs the routing protocol; node’s address is
independent of its location (e.g. PRNET, TORA, DSR, AODV,..)
– Clustering – Only cluster heads run routing protocol; addressing is flat
and independent of node’s location (NTDR, CEDAR,..)
– Hierarchical – Only cluster heads run routing protocol, a node’s form
subnets, each node acquire’s address of its subnet (SURAN).
Many protocols to consider
– See next
Multiple path routing
– Many choices: MSDR, AOMDV, AODV-BR, APR, SMR, ROAM, ….
.
Bucketizing Routing Protocols
Proactive (periodic)
– Each node maintains route to each other network node (Global state)
–
–
–
–
–
Routes are determined independent of traffic
All topology changes propagated to all nodes
Periodic routing advertisements (neighbor discovery is beacon based)
Generally longer route convergence time
Examples: Distance vector and link state (DSDV, OLSR, TBRPF)
Reactive (on-demand)
– Actions driven by data packet requiring delivery
– Source builds route only when needed by “flooding” (Route Discovery)
– Maintain only active routes (Route Maintenance)
– Pro: Typically less overhead, better scaling properties
– Cons: Route acquisition latency
– Examples: DSR, AODV
Conventional Wisdom
Ad Hoc Networking Protocols
Proactive
Reactive
• Proactive protocols perform best in networks with low to moderate
mobility, few nodes and many data sessions
– E.g. OLSR (RFC 3626), TBRPF (RFC 3684)
• Reactive protocols perform best in resource-limited, dynamic networks
where nodes are mobile. Tradeoff routing overhead for start-up delay
– E.g. AODV (RFC 3561), DSR (IETF Draft)
Popular Taxonomy
Multihop Routing Protocols
Proactive
Reactive
Hybrid
.
Hierarchical
Geographical
Power Aware
Mapping Protocols to Taxonomy
Multihop Routing
Protocols
Proactive
Reactive
CSGR
DBF
DSDV
Guesswork
HSLS
HSR
IARP
LCA
MMRP
OLSR
STAR
TBRPF
WRP
Hybrid
ARA
ABR
AODV
BSR
CHAMP
DSR
DSRFLOW
DNVR
DYMO
FORP
GB
IERP
LBR
LMR
LQSR
LUNAR
MOR
MPRDV
RDMAR
SrcRR
SSR
TORA
PLBR
.
ZRP
Hierarchical
Geographical
CBRP
CEDAR
DART
DDR
FSR
GSR
HARP
HSR
HSR
LANMAR
OORP
Power
Aware
DREAM
GLS(Grid)
LAR
GPRS
GPSL
ZHLS
ISAIAH
PARO
EADSR
PAMAS
Link / Path Selection Metrics
Min. hop count results in lower-quality links
Incorporate metric into routing protocols
Path Selection Metrics
• Link Metric: Assign a weight to each link
– Prefer high bandwidth, low-loss links
– RTT, Packet Pair, ETX
Metrics such as shortest path, RTT, Packet Pair, ETX etc. do not leverage
channel, range, data rate diversity
• Path Metric: Combine metrics of links on path
– Prefer short, channel-diverse paths
– WCETT
.
Expected Transmission Count (ETX)
Link Selection Metric for Single Radio Meshes
• Each node periodically
broadcasts a probe
• The probe carries information
about probes received from
neighbors
• Each node can calculate loss
rate on forward (Pf) and reverse
(Pr) link to each neighbor
• Selects the path with least total
ETX
ETX 
1
(1  Pf) * (1  Pr)
.
Advantages
Couto-MobiCom-2003
– Explicitly takes loss rate into
account
– Implicitly takes interference
between successive hops into
account
– Low overhead
Disadvantages
– PHY-layer loss rate of broadcast
probe packets is not the same as
PHY-layer loss rate of data packets
 Broadcast probe packets are
smaller
 Broadcast packets are sent at
lower data rate
– Does not take data rate or link load
into account
Expected Transmission Time (ETT)
Link Selection Metric for Single Radio Meshes
Given:
–
–
–
–
Loss rate p
Bandwidth B
Mean packet size S
Min backoff window CWmin
Takes bandwidth and loss rate of the link into account
ETT  ETxmit  ETbackoff
where,
ETxmit 
S
B(1  p)
i 7
f(p)  1   2 (i 1) p i
i 0
ETbackoff 
CWmin f(p)
2(1  p)
Weighted Cumulated ETT (Combine link ETTs)
Link Selection Metric for Multi-Radio Meshes
Given a n hop path, where each hop can be on any one of k channels,
and two tuning parameters, a and b:
Path throughput is dominated by the max
of the sum of ETTs of path links on the
same channel
Sum of ETTs of all links on the path
- Favors short paths

a *  ETT   b * max
WCETT 
n
i 1
i
1 j  k
X
j

ab
where
X 
j
Draves-MobiCom-2004
 ETT
hop i is on channel j
i
Sum of ETTs of all links on the path that are on the same channel
Select the path with min WCETT
Takes bandwidth, loss rate and channel diversity into account
Path Length and Throughput
Eriksson-MobiSys-2006
Which metric is best? (“Wireless Office Study”)
WCETT
Experimental Setup
ETX
HOP
3.5
•
•
23 node testbed
Randomly selected 100 senderreceiver pairs (out of 23x22 = 506)
3-minute TCP transfer (transmit as
many bytes as possible in 2
minutes, followed by 1 minute of
silence)
For 1 or 2 hop the choice of
metric doesn’t matter
2.5
2
1.5
1
0.5
0
A
C
D
E
F
Testbed Configuration
WCETT
ETX
HOP
4000
Throughput (Kbps)
•
Hop Length
3
3500
3000
2500
2000
1500
1000
500
0
A
C
D
E
Testbed Configuration
.
F
Summarizing
• Many routing protocols to choose from
• Protocols that take link quality into account show most promise
• A link quality metric that incorporates interference is still needed
• Adaptive protocols that change behavior in different environments
might be best
.
Additional Areas of Research
Active Areas of Research
–
–
–
–
–
–
–
–
–
–
–
–
Analytical tools for calculating mesh capacity
Flow-level and packet-level fairness
Network management & automatic diagnosis of faults
Network coding for capacity improvement
Routing with directional antennas / routing for network coding
Supporting VoIP & video traffic over meshes
Inexpensive software steerable directional antennas
Smart medium access control
Meshing with cognitive radios
Multi-spectral meshes
Delay tolerant meshing
Usage scenarios
.
Complete tutorial notes available on my web site:
http://research.microsoft.com/~bahl
Thanks!
For prior work & updates, check out:
http://research.microsoft.com/nrg/
Q/A
References
Papers are categorized under subject area. Duplication is possible because
some papers include more than one problem/solution pair. This is not a
exhaustive list. List is not exhausted (was prepared at least 2 years ago)
References - Testbeds
UMASS’s DieselNet
•
•
•
•
•
•
•
[Zhao-MASS-2006] Wenrui Zhao, Yang Chen, Mostafa Ammar, Mark Corner, Brian N. Levine, and
Ellen Zegura. Capacity Enhancement using Throwboxes in DTNs, IEEE Intl Conf on Mobile Ad hoc
and Sensor Systems (MASS), Oct 2006.
[Partan-WUWNet-2006] Jim Partan, Jim Kurose, Brian N. Levine, A Survey of Practical Issues in
Underwater Networks. ACM Intl Wkshp on Underwater Networks (WUWNet), September 2006
[Jun-ACHANTS-2006] Hyewon Jun, Mostafa Ammar, Mark Corner, Ellen Zegura. Hierarchical
Power Management in Disruption Tolerant Networks with Traffic-Aware Optimization, ACM
CHANTS. September, 2006.
[Burgess-INFOCOM-2006] John Burgess, Brian Gallagher, David Jensen, and Brian N. Levine.
MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks, IEEE INFOCOM, April 2006.
[Burns-ICRA-2006] Brendan Burns, Oliver Brock, and Brian N. Levine. Autonomous Enhancement
of Disruption Tolerant Networks, IEEE Intl Conf on Robotics and Automation (ICRA), May 2006.
[Burns-INFCOMM-2005] Brendan Burns, Oliver Brock, and B.N. Levine. MV routing and capacity
building in disruption tolerant networks., IEEE INFOCOM, March 2005.
[Hanna-ICNP-2003] Kat Hanna, Brian N. Levine, and R. Manmatha. Mobile Distributed Information
Retrieval For Highly Partitioned Networks, IEEE ICNP, November 2003.
.
References - Testbeds
IITK’s Digital Gangetic Plains
•
[Chebrolu-MobiCom-2006] Kameswari Chebrolu, Bhaskaran Raman, and Sayandeep Sen, LongDistance 802.11b Links: Performance Measurements and Experience, 12th Annual International
Conference on Mobile Computing and Networking (MOBICOM), Sep 2006, Los Angeles, USA.
•
[Raman-MobiCom-2005] Bhaskaran Raman and Kameswari Chebrolu, Design and Evaluation of a
new MAC Protocol for Long-Distance 802.11 Mesh Networks, 11th Annual International Conference
on Mobile Computing and Networking (MOBICOM), Aug/Sep 2005, Cologne, Germany.
•
[Bhagwat-HotNets-2003] Pravin Bhagwat, Bhaskaran Raman, and Dheeraj Sanghi, Turning 802.11
Inside-Out, Second Workshop on Hot Topics in Networks (HotNets-II), 20-21 Nov 2003, Cambridge,
MA, USA.
MIT’s RoofNet
•
•
•
•
[Briket-MobiCom-2005] John Bicket, Daniel Aguayo, Sanjit Biswas, and Robert Morris, Architecture
and Evaluation of an Unplanned 802.11b Mesh Network, ACM MobiCom 2005.
[Biswas-SIGCOMM-2005] Sanjit Biswas and Robert Morris, Opportunistic Routing in Multi-Hop
Wireless Networks, ACM SIGCOMM 2005
[Aguayo-SIGCOMM-2004] Daniel Aguayo, John Bicket, Sanjit Biswas, Glenn Judd, Robert Morris,
Link-level Measurements from an 802.11b Mesh Network, SIGCOMM 2004, Aug 2004
[Couto-MobiCom-2003] Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris, A
High-Throughput Path Metric for Multi-Hop Wireless Routing, ACM Mobicom 2003
.
References - Testbeds
MSR’s Mesh Network
•
•
•
•
•
•
•
•
•
[Qiu-CCR-2006] Lili Qiu, Paramvir Bahl, Ananth Rao, Lidong Zou, “Troubleshooting Wireless
Meshes”, ACM Computer Communications Review 2006
[Eriksson-MobiSys-2006] Jacob Eriksson, Sharad Agarwal, Paramvir. Bahl, Jitendra Padhye,
Feasibility Study of Mesh Networks for All-Wireless Offices, ACM/USENIX MobiSys, Uppsala,
Sweden, June 2006
[Kyasanpur-Broadnets-2005] Pradeep Kyasanur, Jitendra Padhye, Paramvir Bahl, On the Efficacy
of Separating Control and Data into Different Frequency Bands, IEEE BroadNets 2005 , Boston,
Massachusetts, USA (October 2005)
[Padhye-IMC-2005] Jitendra Padhye, Sharad Agarwal, Venkata Padmanabhan, lili Qiu, A. Rao,
Brian Zill, “Estimation of Link Interference in Static Multi-hop Wireless Networks”, ACM Internet
Measurement Conference 2005, October 2005
[Kuga-NRSM-2004] Y Kuga, J. Cha, J. A. Ritcey, James Kajiya, Mechanically Steerable Antennas
Using Dielectric Phase Shifters,
IEEE AP-S International Symposium and USNC/URSI National Radio Science Meeting, June 2004
[Qiu-ICNP-2004] Lili Qiu, Ranveer Chandra, Kamal Jain, M. Mahdian, Optimizing the Placement of
Integration Points in Multi-hop Wireless Networks, IEEE ICNP 2004.
[Draves-MobiCom-2004] Richard Draves, Jitendra Padhye, Brian Zill, Routing in Multi-radio, Multihop Wireless Mesh Networks, ACM MobiCom, Philadelphia, PA, September 2004.
[Bahl-MobiCom-2004] Paramvir Bahl, Ranveer Chandra, John Dunagan, SSCH: Slotted Seeded
Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks, ACM
MobiCom, Philadelphia, PA, September 2004.
[Draves-SIGCOMM-2004] Richard Draves, Jitendra Padhye, Brian Zill, Comparison of Routing
Metrics for Static Multi-Hop Wireless Networks, ACM SIGCOMM, Portland, OR, August 2004.
.
References - Testbeds
MSR’s Mesh Network
•
•
[Qiu-MSRTR-2003] Lili Qiu, Paramvir Bahl, A. Rao, Lidong Zhou, Fault Detection, Isolation, and
Diagnosis in Multi-hop Wireless Networks, Microsoft Research Technical Report, TR-2004-11
[Jain-MobiCom-2003] 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
Rice’s TFA
•
[Camp-MobiSys-2006] Joseph Camp, J. Robinson, C. Steger, Edward Knightly, "Measurement Driven
Deployment of a Two-Tier Urban Mesh Access Network," in Proceedings of ACM MobiSys 2006,
Uppsala, Sweden, June 2006.
•
[Camp-DC-2005] Joseph Camp, Edward Knightly, W. Reed, "Developing and Deploying Multihop
Wireless Networks for Low-Income Communities," in Proceedings of Digital Communities 2005, Napoli,
Italy, June 2005.
JHU’s SMESH
•
[Amir-MobiSys-2006] Yair Amir, Claudiu Danilov, Michael Hilsdale, Raluca Musaloiu-Elefteri, Nilo
Rivera, “Fast Handoff for Seamless Wireless Mesh Networks”, ACM/USENIX MobiSys 2006, June
2006
.
References - Testbeds
Purdue’s Mesh
•
•
[Das-JSAC-2006] Saumitra M. Das, Himabindu Pucha, Dimitrios Koutsonikolas, Y. Charlie Hu,
Dimitrios Peroulis, “DMesh: Incorporating Practical Directional Antennas in Multi-Channel Wireless
Mesh Networks”, IEEE Journal on Selected Areas in Communications (JSAC 06) special issue on
Multi-Hop Wireless Mesh Networks, 2006.
[Das-mobicom_wintech-2006] Saumitra M. Das, Dimitrios Koutsonikolas, Y. Charlie Hu, Dimitrios
Peroulis, “Characterizing Multi-Way Interference In Wireless Mesh Networks”, ACM MobiCom
International Workshop on Wireless Network Testbeds, Experimental evaluation and
Characterization (MobiCom WiNTECH 06), Los Angeles, CA, September 29, 2006.
.
References - Fairness
•
•
[Nandagopal-MobiCom-2000] Thyagarajan Nandagopal, Tae-Eun Kim, Xia Gao, Vadhuvar
Bharghavan, “Achieving MAC Layer Fairness in Wireless Packet Networks,” ACM MobiCom 2000,
August 2000
[Luo-MobiCom-2000] Haiyun Luo, Songwu Lu, Vadhuvar Bharghavan, “A New Model for Packet
Scheduling in Multihop Wireless Networks”, ACM MobiCom 2000, August 2000
References – Capacity / Channelization
•
•
•
•
•
•
•
[MSBA-SIGMETRICS-2006] Arunesh Mishra, Vivek Shrivastava, Suman Banerjee, William Arbaugh,
Partially-overlapped Channels not Considered Harmful, ACM SIGMETRICS, June 2006.
[Ramachandran-Infocom-2006] K. Ramachandran, E. Belding, K. Almeroth, M. Buddhikot,
“Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks”, IEEE Infocom,
Barcelona, Spain, April 2006
[Kyasanur-WCM-2006] Pradeep Kyasanur, Jungmin So, Chandrakanth Chereddi, and Nitin H.
Vaidya, "Multi-Channel Mesh Networks: Challenges and Protocols", IEEE Wireless Communications,
April 2006
[Kyasanur-BroadNets-2005] Pradeep Kyasanur, Jitendra Padhye, and Paramvir Bahl, "On the
Efficacy of Separating Control and Data into Different Frequency Bands", in IEEE Broadnets, Boston,
MA, October 2005
[Raniwala-Infocom-2005] Ashish Raniwala and Tzi-cker Chiueh, “Architecture and Algorithms for an
IEEE 802.11-based Multi-Channel Wireless Mesh Network”, IEEE INFOCOM, 2005
Alicherry-MobiCom-2005] Mansoor Alicherry, Randeep Bhatia, Li Li, “Joint Channel Assignment
and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks”, ACM MobiCom
2005, September 2005
[Kodialam-MobiCom-2005] Muralidharan Kodialam, Thyaga Nandagopal, “Characterizing the
Capacity Region in Multi-Radio, Multi-Channel Wireless Mesh Networks”, ACM MobiCom 2005,
September 2005
.
References – Capacity / Channelization
•
•
•
•
•
•
•
•
[Kyasanur-MobiCom-2005] Pradeep Kyasanur, Nitin Vaidya, Capacity of Multi-Channel Wireless
Networks: Impact of Number of Channels and Interfaces”, ACM MobiCom 2005, September 2005
[Adya-BroadNets-2004] Atul Adya, Paramvir Bahl, Jitendra Padhye, Alec Wolman, and Lidong
Zhou, “A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks”, IEEE BroadNets
2004.
[Bahl-MobiCom-2004] Paramvir Bahl, Ranveer Chandra, John Dunagan, “SSCH: Slotted Seeded
Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks”, ACM
MobiCom, Philadelphia, PA, September 2004
[So-MobiHoc-2004], Jungmin So, Nitin Vaidya, “Multi-Channel MAC for Ad Hoc Networks: Handling
Multi-Channel Hidden Terminals Using A Single Transceiver”, ACM MobiHoc 2004, Tokyo, Japan,
May 2004
[Jain-MobiCom-2003] Kamal Jain, Jitendra Padhye, Venkata Padmanabhan, and Lili Qiu, “Impact of
Interference on Multi-hop Wireless Network Performance”, ACM MobiCom, San Diego, CA,
September 2003
[Jinyang-MobiCom-2001] Jinyang Li, Charles Blake, Douglas S. J. De Couto, Hu Imm Lee, and
Robert Morris, Capacity of Ad Hoc Wireless Networks, ACM MobiCom '01), Rome, Italy, July 2001
[Gupta-IEEEIT-2000] Piyush Gupta, P. R. Kumar, “Capacity of Wireless Networks”, IEEE
Transactions on Information Theory, March 2000.
[Wu-ISPAN-2000] S.L. Wu, C.Y. Lin, Y.C. Tseng, J.P. Sheu, “A New Multi-Channel MAC Protocol
with On-Demand Channel Assignment for Mobile Ad Hoc Networks”, International Symposium on
Parallel Architectures, Algorithms and Networks (I-SPAN), 2000
.
References - Routing
IETF Standards
•
•
•
•
•
[Corson-RFC2501-1999] Scott Corson, Joseph Macket, “Mobile Ad hoc Networking (MANET): Routing
Protocol Performance Issues and Evaluation Considerations”, IETF RFC 2501, January 1999
[Perkins-RFC3561-2003] Charlie Perkins, Elizabeth Beilding-Royer, Samir Das, “Ad Hoc On Demand
Distance Vector (AODV) Routing”, IETF RFC 3561, July 2003
[Clausen-RFC3626-2003] T. Clausen, P. Jacquet, “Optimized Link State Routing Protocol (OLSR)”,
IETF RFC 3626, October 2003
[Ogier-RFC3684-2004] R. Ogier, Fred Templin, Mark Lewis, “Topology Dissemination Based on
Reverse-Path Forwarding (TBRPF)”, IETF RFC 3684, February 2004
[Johnson-RFC4728-2007] D. Johnson, Y. Hu, D. Maltz, “The Dynamic Source Routing Protocol (DSR)
for Mobile Ad Hoc Networks for IPv4”, IETF RFC 4728, February 2007
Papers & Drafts
•
•
•
•
[Biswas-SIGCOMM-2005] Sanjit Biswas and Robert Morris, Opportunistic Routing in Multi-Hop
Wireless Networks, ACM SIGCOMM 2005
[Draves-SIGCOMM-2004] Richard Draves, Jitendra Padhye, Brian Zill, Comparison of Routing Metrics
for Static Multi-Hop Wireless Networks, ACM SIGCOMM, Portland, OR, August 2004.
[Johnson-Draft-2004] David B. Johnson, David A. Maltz, Yih-Chun Hu, “The Dynamic Source Routing
Protocol for Mobile Ad Hoc Networks (DSR)”, IETF Draft, July 2004
[Ni-MobiCom-1999] S. Ni, Y. Tseng, Y. Chen, J. Chen, “The Broadcast Storm Problem in a Mobile Ad
Hoc Network,” ACM MobiCom ’99, Seattle, Washington, August 1999
.
References - Routing
Papers & Drafts
•
•
•
•
[Alicherry-MobiCom-2005] Mansoor Alicherry, Randeep Bhatia, Li Li, “Joint Channel Assignment
and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks”, ACM MobiCom
2005, September 2005
[Couto-HotNets-2002] Douglas De Couto, Daniel Aguayo, Benjamin Chambers, Robert Morris,
“Performance of Multihop Wireless Networks: Shortest Path is Not Enough”, First Workshop on Hot
Topics in Networks (HotNets-I), October 2002
[Broch-MobiCom-1998] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta
Jetcheva. “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocol”,.
ACM MobiCom'98, Oct. 1998.
[Perkins-CCR-1994] Charlie Perkins and Pravin Bhagwat, “Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers,”, Computer Communications Review 24(4),
Oct. 1994
.
References – Security & Management
•
•
•
•
•
•
•
•
•
•
•
[Qiu-CCR-2006] Lili Qiu, Paramvir Bahl, Ananth Rao, Lidong Zou, “Troubleshooting Wireless
Meshes”, ACM Computer Communications Review 2006
[Badonnei-JNM-2005] Remi Badonnel, Radu State, Olivier Festor “Management of Mobile Ad Hoc
Networks: Information Model and Probe-based Architecture”, International Journal of Network
Management, Vol. 15, Issue 5, September 2005
[Kyasanur-TMC-2005] Pradeep Kyasanur, Nitin Vaidya, “Selfish MAC Layer Misbehavior in
Wireless Networks”, IEEE Transactions on Mobile Computing, Vol. 4, Issue 4, September 2005
[Hu-Infocom-2003] Yih-Chun Hu, Adrian Perrig, David B. Johnson, “Packet Leashes: A Defense
Against Wormhole Attacks in Wireless Ad Hoc Networks,”, IEEE INFOCOM 2003
[Qiu-MSRTR-2003] Lili Qiu, Paramvir Bahl, A. Rao, Lidong Zhou, Fault Detection, Isolation, and
Diagnosis in Multi-hop Wireless Networks, Microsoft Research Technical Report, TR-2004-11
[Shen-Milcom-2002] C.-C. Shen, C. Jaikaeo, C. Srisathapornphat, Z. Huang, “The GUERILLA
Management Architecture for Ad Hoc networks”, IEEE MILCOM 2002, Oct. 2002
[Hu-MobiCom-2002] Yih-Chun Hu, Adrian Perrig, David B. Johnson, “Ariadne: A Aecure OnDemand Routing Protocol for Ad Hoc Networks”, ACM MobiCom 2002, Atlanta, GA
[Bucheggar-MobiHoc-2002] S. Buchegger, J. Y. Le Boudec, “Performance Analysis of the
CONFIDANT Protocol”, ACM MobiHoc 2002
[Marti-MobiCom-2000] Sergio Marti, T. J. Giuli, Kevin Lai, Mary Baker, “Mitigating Routing
Misbehavior in Mobile Ad Hoc Networks”, ACM MobiCom 2000, Boston, MA
[Zhang-MobiCom-2000] Yongguang Zhang , Wenke Lww, “Intrusion Detection in Wireless Ad Hoc
Networks”, ACM MobiCom 2000, Boston, MA
[Chen-JSAC-1999] Wenli Chen, Nitin Jain, Suresh Singh, “ANMP: Ad Hoc Network Management
Protocol”, IEEE Journal on Selected Areas in Communications, Volume 17 Number 8, August 1999
.
References - General
Network Management
•
[Badonnel-JTS-2005] Remi Badonnel, Radu State, Olivier Festor, “Self-Organized Monitoring of Ad
Hoc Networks”, Journal of Telecommunications Systems, Vol. 30, No. 1-3, 2005
General
•
•
•
•
•
[Andel-Computer-2006] Todd R. Andel, Alec Yasinsac, “On the Credibility of MANET Simulations”,
IEEE Computer Magazine, pp. 48-54, 2006
[IEEE-Mesh-2006] Joint SEE-Mesh/Wi-Mesh Proposal to 802.11 TGs Overview”, IEEE 802.1106/0329r2, March 6, 2006
[Karn-CNC-1997] Phil Karn, “MACA – A New Channel Access Method for Packet Radio”, in
Proceedings of AARL/CRRL Amateur Radio 9th Computer Networking Conference, Sept. 1997
[Powers-Proc-1995] R. A. Powers. “Batteries for Low Power Electronics”, Proceedings of the IEEE,,
April 1995
[Tobagi-Comm-1975] F. A. Tobag, L. Klienrock, “Packet Switching in Radio Channels: Part II – The
hidden Terminal Problem in a Carrier Sense Multiple-Access Modes and Busy-Tone Solution”, IEEE
Transaction Communications, Vol. COM-23, no. 12, 1975
.