Automating Cross Layer Diagnosis of Enterprise 802 11 Wireless Networks Yu Chung Cheng Department of Computer Science Engineering University of California San Diego 5 13 07 1 Diagnosing distributed systems Simple systems Few components Inputs Output observed Cause of failure usually obvious Distributed systems Many interdependent components Hard to monitor all interactions Cause of failure degradation is non obvious 5 13 07 2 The promise of enterprise 802 11 Blanket AP coverage seamless connectivity 5 13 07 3 5 13 07 4 A familiar story The wireless is being flaky Flaky how Well my connections got dropped earlier and now things seem very sloooow User OK we will take a look Wait wait it s ok now Mmm well let us know if you have any more problems Support 5 13 07 5 Our story new CSE building at UCSD 150k square feet 4 floors basement 500 occupants Building wide WiFi 40 APs 802 11b g Channel 1 6 11 Users complain about wireless performance since we moved in July 2005 Admins and vendors can not solve the issues 5 13 07 6 Why is it hard to figure out Problems can be in anywhere Across layers protocols Even in the same layer 802 11 a b f g h i n s Software incompatibilities vendor variations Transient or persistent time Radio propagates in free space locations Radio spreads across channels frequencies Shared spectrum makes it worse APs bridge wireless and wired worlds infrastructure To diagnose Gather data everywhere Analyze across all layers Need a system to do this job automatically 5 13 07 7 Better world The wireless is being flaky User Your SSH has over 200ms response time in average 8 TCP packet is lost due to the interferences from the microwave oven nearby This problem is logged for sys admins 5 13 07 8 Shaman Goal Develop a system to automatically diagnose problems in wireless networks Pervasive data collection Jigsaw Extensive passive monitoring system Observe all transmissions across locations channels and time Provides a unified synchronized trace of every packet transmission Explicitly model protocols on critical path DHCP 802 11 MAC TCP etc Provides complete delay and loss breakdown For every packet transmission all protocol stages Framework for diagnostic tools Use model outputs to determine root cause of problems Users can query on demand also alert admins 5 13 07 9 Shaman system architecture Do all in real time Wireless monitor Wireless monitor Trace sync merging Protocol modeling Critical path diagnosis Wireless monitor Wired gateway monitor Gather and merge traces from monitors into one global trace 5 13 07 Infer protocol states Identify problems on the critical path 10 Why pervasive monitoring Protocol states are often not directly observable Inferred from packet traces and protocol state machines Packet delay and losses PHY MAC interactions with each other and the environment DHCP req p P rs C H D Capturing all wireless events provide the ground truth to model protocol states Require a global perspective one clock Require high resolution timestamp for 802 11 timing analysis How 5 13 07 11 Jigsaw passive monitor system Overlays existing WiFi network Series of passive monitors Blanket deployment for best coverage Monitor PoE box w 266Mhz P4 128MB ram 2 b g radios 96 monitors 192 radios Monitors are paired in each location 5 13 07 Covering all channels in use Captures all 802 11 activity including PHY CRC errors Stream back to centralized storage 12 Time Trace merging ideal 5 13 07 13 Not all monitors see all packets 5 13 07 14 Time Clock diff us Trace merging reality Time s 5 13 07 15 Challenge 1 sync at 10us precision Why 10us precision Critical evidence for 802 11 layer analysis 802 11 channel access mechanism Carrier sense multiple access CSMA Channel busy wait Channel idle send Timing unit is 10us Precise trace timestamps reveal 802 11 internal states Ex1 if A and B send at same time they could interfere A can t hear B Ex2 if A sends right after B s transmission A can hear B How Create a global clock Monitors timestamp packets w local HW clocks 5 13 07 802 11 HW clocks has 1us granularity Estimate the offset between local and global clock for each monitor 16 Challenge 2 sync across 192 radios 0 To 1 2 3 t1 t2 Goal estimate the offset between local and global clock for each monitor Time route from one monitor to the other Sync across channels Ch 1 monitor does not hear packet sent in ch 6 Dual radios on same monitor slaved to same clock Jigsaw Solving the Puzzle of Enterprise 802 11 Analysis Cheng Bellardo Benko Snoeren Voelker and Savage SIGCOMM 2006 5 13 07 17 Trace merging reality Shaman sync d trace Frame 1 Time Frame 2 Frame 3 Frame 4 Frame 5 5 13 07 18 Part of a sync d trace Traces synchronized User 1 User 2 5 13 07 19 Shaman system architecture Wireless monitor Wireless monitor Trace sync merging Protocol modeling Critical path diagnosis Wireless monitor Wired gateway monitor Gather and merge traces from monitors into one global trace 5 13 07 Infer protocol states Identify problems on the critical path 20 Modeling protocols Now we have fully sync d global traces What protocols must we model Critical path Mobility management Scan associate w AP DHCP ARP Portal page login Data transport protocols TCP 802 11 Mac delay loss 5 13 07 21 Mobility Management Create the illusion of a single AP Proprietary system w site specific policy Most components are simple protocols 1 2 request response transactions Easier to model compared to TCP Very reliable in wired network ARP DHCP DNS Seldom suspected as the culprits in wireless Users expect seamless connectivity People often suspend resume laptops while moving in the office building 5 13 07 22 Mobility overhead in UCSD CSE Major Problem Gratuitous ARPs Scans 5 13 07 23 Protocol Modeling Distribution is not enough Want to diagnose any user s problem by finding the root cause Need to track per packet delay and loss Essential to model e2e protocols like TCP Complex mechanisms to accommodate delay and loss Example slow SSH response high TCP losses most 802 11 retries failed microwave ovens operating nearby 5 13 07 24 The journey of a packet in 802 11 CNN com Wireless gateway AP User Queuing Time Channel busy Exp Backoff Wired packet 802 11 Data 802 11 Ack 5 13 07 Exp Backoff 25 Modeling 802 11 packet delays Emulate AP queue Based on input output events Events observed directly AP Ethernet packet on wires 802 11 data ack on wireless Need to infer when a packet 5 13 07 Reaches head of TxQ Is scheduled to the TxQ Is received by
View Full Document
Unlocking...