Transcript ppt

15-744: Computer Networking
L-10 Wireless in the Real World
Wireless in the Real World
• Real world deployment patterns
• Mesh networks and deployments
• Assigned reading
• Self-Management in Chaotic Wireless
Deployments
• Architecture and Evaluation of an Unplanned
802.11b Mesh Network
2
Wireless Challenges
• Force us to rethink many assumptions
• Need to share airwaves rather than wire
• Don’t know what hosts are involved
• Host may not be using same link technology
• Mobility
• Other characteristics of wireless
• Noisy  lots of losses
• Slow
• Interaction of multiple transmitters at receiver
• Collisions, capture, interference
• Multipath interference
3
Overview
• 802.11
• Deployment patterns
• Reaction to interference
• Interference mitigation
• Mesh networks
• Architecture
• Measurements
4
Characterizing Current Deployments
• Datasets
• Place Lab: 28,000 APs
• MAC, ESSID, GPS
• Selected US cities
• www.placelab.org
• Wifimaps: 300,000 APs
• MAC, ESSID, Channel, GPS (derived)
• wifimaps.com
• Pittsburgh Wardrive: 667 APs
• MAC, ESSID, Channel, Supported Rates, GPS
5
AP Stats, Degrees: Placelab
(Placelab: 28000 APs, MAC, ESSID, GPS)
#APs Max.
degree
Portland
8683
54
San Diego
7934
76
San
Francisco
3037
85
50 m
1
Boston
2551
2
1
39
6
Degree Distribution: Place Lab
7
Unmanaged Devices
WifiMaps.com
(300,000 APs, MAC, ESSID, Channel)
Channel %age
6
51
11
21
1
14
10
4
• Most users don’t
change default
channel
• Channel selection
must be automated
8
Growing Interference in Unlicensed Bands
• Anecdotal evidence of problems, but how
severe?
• Characterize how 802.11 operates under
interference in practice
Other 802.11
9
• Throughput to decrease
linearly with interference
• There to be lots of options
for 802.11 devices to
tolerate interference
•
•
•
•
•
•
Bit-rate adaptation
Power control
FEC
Packet size variation
Spread-spectrum processing
Transmission and reception
diversity
Throughput (linear)
What do we expect?
Interferer power
(log-scale)
10
Key Questions
• How damaging can a low-power and/or
narrow-band interferer be?
• How can today’s hardware tolerate
interference well?
• What 802.11 options work well, and why?
11
• Effects of interference
more severe in
practice
• Caused by hardware
limitations of
commodity cards,
which theory doesn’t
model
Throughput (linear)
What we see
Interferer power
(log-scale)
12
Experimental Setup
Access
Point
UDP flow
802.11 Interferer
802.11
Client
13
802.11 Receiver Path
PHY
To RF Amplifiers
Amplifier
control
RF
Signal
Analog
signal
ADC
6-bit
samples
Timing
Recovery
PHY
MAC
MAC
AGC
Barker
Correlator
Demodulator
Descrambler
Data
(includes
beacons)
Preamble Detector/
Header CRC-16 Checker
Receiver
SYNC
SFD
CRC
Payload
PHY header
• Extend SINR model to capture these vulnerabilities
• Interested in worst-case natural or adversarial interference
• Have developed range of “attacks” that trigger these vulnerabilities
14
Timing Recovery Interference
• Interferer sends continuous SYNC pattern
• Interferes with packet acquisition (PHY
reception errors)
Moderate
interferer
1000
100
1200
Weak interferer
1000
800
Throughput
Log-scale
600
10
400
Latency
1
Latency
(microseconds)
Throughput (kbps)
10000
200
0.1
0
−∞ -20 -12
-2
0
8
12
15
Interferer Power (dBm)
20
15
Interference Management
• Interference will get worse
• Density/device diversity is increasing
• Unlicensed spectrum is not keeping up
• Spectrum management
• “Channel hopping” 802.11 effective at mitigating some
performance problems [Sigcomm07]
• Coordinated spectrum use – based on RF sensor network
• Transmission power control
• Enable spatial reuse of spectrum by controlling transmit
power
• Must also adapt carrier sense behavior to take advantage
16
Impact of frequency separation
• Even small frequency separation (i.e.,
adjacent 802.11 channel) helps
Throughput (kbps)
10000
15MHz separation
1000
10MHz separation
5MHz separation
(good performance)
Same channel
(poor performance)
100
10
1
0.1
−∞
-20
-12
0
8
12
15
20
Interferer Power (dBm)
17
Transmission Power Control
• Choose transmit power levels to maximize
physical spatial reuse
• Tune MAC to ensure nodes transmit
simultaneously when possible
• Spatial reuse = network capacity / link
capacity
Client2
AP1
AP2
Client1
Spatial Reuse = 1
Concurrent transmissions
increase spatial reuse
AP1
Client2
AP2
Client1
Spatial Reuse = 2
18
Transmission Power Control in Practice
• For simple scenario  easy to
compute optimal transmit power
• May or may not enable simultaneous
transmit
• Protocol builds on iterative pair-wise
optimization
AP1
d12
d22
d11
d21
• Adjusting transmit power 
requires adjusting carrier sense
thresholds
AP2
Client2
Client1
• Echos, Alpha or eliminate carrier sense
• Altrusitic Echos – eliminates starvation
in Echos
19
Details of Power Control
• Hard to do per-packet with many NICs
• Some even might have to re-init (many ms)
• May have to balance power with rate
• Reasonable goal: lowest power for max rate
• But finding ths empirically is hard! Many {power, rate}
combinations, and not always easy to predict how each
will perform
• Alternate goal: lowest power for max needed rate
• But this interacts with other people because you use more
channel time to send the same data. Uh-oh.
• Nice example of the difficulty of local vs. global optimization
20
Rate Adaptation
• General idea:
• Observe channel conditions like SNR (signalto-noise ratio), bit errors, packet errors
• Pick a transmission rate that will get best
goodput
• There are channel conditions when reducing the
bitrate can greatly increase throughput – e.g., if a ½
decrease in bitrate gets you from 90% loss to 10%
loss.
21
Simple rate adaptation scheme
• Watch packet error rate over window (K
packets or T seconds)
• If loss rate > threshhigh (or SNR <, etc)
• Reduce Tx rate
• If loss rate < threshlow
• Increase Tx rate
• Most devices support a discrete set of rates
• 802.11 – 1, 2, 5.5, 11, etc.
22
Challenges in rate adaptation
• Channel conditions change over time
• Loss rates must be measured over a window
• SNR estimates from the hardware are
coarse, and don’t always predict loss rate
• May be some overhead (time, transient
interruptions, etc.) to changing rates
23
Power and Rate Selection Algorithms
• Rate Selection
• Auto Rate Fallback: ARF
• Estimated Rate Fallback: ERF
• Goal: Transmit at minimum necessary power to reach
receiver
• Minimizes interference with other nodes
• Paper: Can double or more capacity, if done right.
• Joint Power and Rate Selection
• Power Auto Rate Fallback: PARF
• Power Estimated Rate Fallback: PERF
• Conservative Algorithms
• Always attempt to achieve highest possible modulation rate
24
Power Control/Rate Control summary
• Complex interactions….
• More power:
• Higher received signal strength
• May enable faster rate (more S in S/N)
• May mean you occupy media for less time
• Interferes with more people
• Less power
• Interfere with fewer people
• Less power + less rate
• Fewer people but for a longer time
• Gets even harder once you consider
• Carrier sense
• Calibration and measurement error
• Mobility
25
Overview
• 802.11
• Deployment patterns
• Reaction to interference
• Interference mitigation
• Mesh networks
• Architecture
• Measurements
26
Community Wireless Network
• Share a few wired Internet connections
• Construction of community networks
• Multi-hop network
• Nodes in chosen locations
• Directional antennas
• Require well-coordination
• Access point
• Clients directly connect
• Access points operates independently
• Do not require much coordination
27
Roofnet
• Goals
• Operate without extensive planning or central
management
• Provide wide coverage and acceptable
performance
• Design decisions
•
•
•
•
Unconstrained node placement
Omni-directional antennas
Multi-hop routing
Optimization of routing for throughput in a slowly
changing network
28
Roofnet Design
• Deployment
• Over an area of about four square kilometers in Cambridge,
Messachusetts
• Most nodes are located in buildings
• 3~4 story apartment buildings
• 8 nodes are in taller buildings
• Each Rooftnet node is hosted by a volunteer user
• Hardware
• PC, omni-directional antenna, hard drive …
• 802.11b card
• RTS/CTS disabled
• Share the same 802.11b channel
• Non-standard “pseudo-IBSS” mode
• Similar to standard 802.11b IBSS (ad hoc)
• Omit beacon and BSSID (network ID)
29
Roofnet Node Map
1 kilometer
30
Roofnet
31
Typical Rooftop View
32
A Roofnet Self-Installation Kit
Antenna ($65)
50 ft. Cable ($40)
8dBi, 20 degree vertical
Low loss (3dB/100ft)
Computer ($340)
Miscellaneous ($75)
533 MHz PC, hard
disk, CDROM
Chimney Mount,
Lightning Arrestor, etc.
802.11b card ($155)
Software (“free”)
Engenius Prism 2.5,
200mW
Our networking
software based on
Click
Total: $685
Takes a user about 45 minutes to install on a flat roof
33
Software and Auto-Configuration
• Linux, routing software, DHCP server, web server …
• Automatically solve a number of problems
• Allocating addresses
• Finding a gateway between Roofnet and the Internet
• Choosing a good multi-hop route to that gateway
• Addressing
• Roofnet carries IP packets inside its own header format and
routing protocol
• Assign addresses automatically
• Only meaningful inside Roofnet, not globally routable
• The address of Roofnet nodes
• Low 24 bits are the low 24 bits of the node’s Ethernet address
• High 8 bits are an unused class-A IP address block
• The address of hosts
• Allocate 192.168.1.x via DHCP and use NAT between the
Ethernet and Roofnet
34
Software and Auto-Configuration
• Gateway and Internet Access
• A small fraction of Roofnet users will share their
wired Internet access links
• Nodes which can reach the Internet
• Advertise itself to Roofnet as an Internet gateway
• Acts as a NAT for connection from Roofnet to the
Internet
• Other nodes
• Select the gateway which has the best route metric
• Roofnet currently has four Internet gateways
35
Evaluation
• Method
• Multi-hop TCP
• 15 second one-way bulk TCP transfer between each pair
of Roofnet nodes
• Single-hop TCP
• The direct radio link between each pair of routes
• Loss matrix
• The loss rate between each pair of nodes using 1500byte broadcasts
• Multi-hop density
• TCP throughput between a fixed set of four nodes
• Varying the number of Roofnet nodes that are
participating in routing
36
Evaluation
• Basic Performance (Multi-hop TCP)
• The routes with low hop-count have much higher
throughput
• Multi-hop routes suffer from inter-hop collisions
37
Evaluation
• Basic Performance (Multi-hop TCP)
• TCP throughput to each node from its chosen
gateway
• Round-trip latencies for 84-byte ping packets to
estimate interactive delay
38
Evaluation
• Link Quality and Distance (Single-hop TCP,
Multi-hop TCP)
• Most available links are between 500m and
1300m and 500 kbits/s
• Srcr
• Use almost all of the links faster than 2 Mbits/s and
ignore majority of the links which are slower than
that
• Fast short hops are the best policy
39
Evaluation
• Link Quality and Distance (Multi-hop TCP, Loss matrix)
• Median delivery probability is 0.8
• 1/4 links have loss rates of 50% or more
• 802.11 detects the losses with its ACK mechanism and
resends the packets
40
Evaluation
• Architectural Alternatives
• Maximize the number of additional nodes with non-zero
throughput to some gateway
• Ties are broken by average throughput
41
Evaluation
• Inter-hop Interference (Multi-hop TCP, Single-hop TCP)
• Concurrent transmissions on different hops of a route collide
and cause packet loss
42
Roofnet Summary
• The network’s architectures favors
•
•
•
•
Ease of deployment
Omni-directional antennas
Self-configuring software
Link-quality-aware multi-hop routing
• Evaluation of network performance
• Average throughput between nodes is 627kbits/s
• Well served by just a few gateways whose position
is determined by convenience
• Multi-hop mesh increases both connectivity and
throughput
43
Roofnet Link Level Measurements
• Analyze cause of packet loss
• Neighbor Abstraction
• Ability to hear control packets or No
Interference
• Strong correlation between BER and S/N
• RoofNet pairs communicate
• At intermediate loss rates
• Temporal Variation
• Spatial Variation
44
Lossy Links are Common
45
Delivery Probabilities are Uniformly
Distributed
46
Delivery vs. SNR
• SNR not a good predictor
47
Is it Bursty Interference?
• May interfere but not impact SNR
measurement
48
Two Different Roofnet Links
• Top is typical of bursty interference, bottom
is not
• Most links are like the bottom
49
Is it Multipath Interference?
• Simulate with channel emulator
50
A Plausible Explanation
• Multi-path can produce intermediate loss
rates
• Appropriate multi-path delay is possible due
to long-links
51
Key Implications
• Lack of a link abstraction!
• Links aren’t on or off… sometimes in-between
• Protocols must take advantage of these
intermediate quality links to perform well
• How unique is this to Roofnet?
• Cards designed for indoor environments used
outdoors
52