Transcript Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis

Jigsaw: Solving the Puzzle of
Enterprise 802.11 Analysis
Yu-Chung Cheng
John Bellardo, Peter Benko, Alex C. Snoeren,
Geoff Voelker, Stefan Savage
Enterprise 802.11?
Easy. Blanket the building with 802.11 APs
for 100% coverage
2
A familiar story...
“The wireless is being flaky.”
“Flaky how?”
“Well, my connections got dropped
earlier and now things seem very
sloooow.”
“OK, we will take a look”
Employee
“Wait, wait … it’s ok now”
“Mmm… well let us know if you
have any more problems.”
Now what?
Support
3
What are the problems?










Contention with nearby wireless devices?
Bad AP channel assignments?
Microwave ovens?
Congestions in the Internet?
Bad interaction between TCP and 802.11?
Rogue access points?
Poor choice of APs (weak signal)?
Incompatible user software/hardware?
802.11 DoS attack?!
…
Need to monitor the wireless network
across time, locations, channels, and
protocol layers
4
How to monitor 802.11?
Measurement
Limitations
AP traces
Only packets that AP sees
1 passive sniffer
Limited coverage
N passive sniffers
in 1 channel
Limited frequency (roaming, broadband
interference, AP channel assignments)
N passive sniffers
of all channels
Need synchronized traces
5
Jigsaw
 Measure real large wireless networks

Collect every possible information
•
•

PHY/Link/IP/TCP/App layer trace
Collect every single wireless packet
Need many sniffers for 100% coverage
 Provide global view of wireless
networks across time, locations,
channels, and protocol layers
6
New CSE building at UCSD
 150k square feet
 4 floors
 >500 occupants
 150 faculty/staff
 350 students
 Building-wide WiFi
 39 access points
 802.11b/g
• Channel 1, 6, 11


10 - 90 active clients
anytime
Daily traffic ~5 GB
7
UCSD passive monitor
system
 Overlays existing WiFi
network


Series of passive sniffers
Blanket deployment over 4
floors
 39 sensor pods (156
radios)



4 radios per pod, cover all
channels in use
Captures all 802.11
activities
• Including CRC/PHY events
Stream back over wired
network to a centralized
storage
8
Jigsaw design
Traces
synchronization
and unification
L2 state
reconstruction
TCP flow
reconstruction
9
Synchronization
 Create a virtual global
clock
To keep unification working
 Critical evidence for analysis
TSF diff of two sniffers
• If A and B are transmitting
at the same time they could
interfere
• If A starts transmitting
after B has started then A
can’t hear B
 Require fine time-scales
(10-50us)
NTP is >100 usec accuracy
 802.11 HW clocks (TSF)
have 100PPM stability
TSF diff (us)

Time (s)

10
Traces synchronization and
unification
 Sniffers label packets w/ local timestamp (TSF)
 Need a global clock
 Estimate the offset between TSF and the global clock
for each sniffer
11
Trace unification (ideal)
Time
12
Trace unification (reality)
Jigsaw
unified
trace
JFrame 1
Time
JFrame 2
JFrame 3
JFrame 4
JFrame 5
13
Challenge: sync at large-scale
1
2
3
4
To
∆t1
∆t2
 How to bootstrap?


Goal: estimate the offset between TSF and the global
clock for each sniffer
Time reference from one sniffer to the other
 Sync across channels

Dual radios on same sniffer slaved to same clock
 Manage TSF clock skews

Continuously re-adjust offsets when unifying frames
14
Jigsaw in action
 Jigsaw unifies 156
traces into one
global trace
 Covers 99% of AP
frames, 96% of
client frames
Starts
Jan 24,2006
(Tuesday)
Duration
24 hr
Total APs
107 (39 CSE)
CSE Clients
1026
Active CSE
clients anytime
10 - 90
Total Events
2,700M
PHY/CRC Errors
48%
Valid Frames
52%
JFrames
530M
Events per
Jframe
2.97
15
CRC
errors
PHY
errors
L2-ACK
Beacon
Synchronized
Valid
packets
16
Jigsaw syncs 99% frames < 20us
 Measure sync. quality
by max dispersion
per Jframe
 20 us is important
threshold



802.11 back-off time is
20 us
802.11 inter frame time
is 50 us
Sufficient to infer many
802.11 events
17
Hidden terminal problems
 How much packet is lost due to hiddenterminal?
?
sender
receiver
hidden terminal
 Infer transmission failure by absence of ACK
 Estimate conditional probability of loss given
simultaneous transmission by some hiddenterminal
18
Hidden Terminal Problems
 10% of sender-receiver pairs have over
10% losses due to hidden terminals
19
Trace analysis
TCP loss rate in wireless vs. in Internet
802.11 b/g interactions
Microwave Ovens
ARP Broadcast Storms
20
Moving forward
 Developed “Jigsaw” that allows



24x7 monitor system in UCSD CSE w/
156 sniffers
Global fine-grained view of large wireless
network (time, locations, channels)
Jigsaw software will be available shortly
 Ongoing work


Root cause diagnoses of end-to-end
performance in wireless networks
Standard wireless problem analysis
• Ex. Exposed terminal problems
21
Q&A
Live traffic monitoring and more information at
http://wireless.ucsdsys.net
22