chop06

Distributed Channel Management : Distributed Channel Management www.cs.wisc.edu/~arunesh/chop in Uncoordinated Wireless Environments Arunesh Mishra Vivek Shrivastava Dheeraj Agrawal Suman Banerjee Samrat Ganguly University of Wisconsin, Madison


Channel Assignment in Hotspots : Channel Assignment in Hotspots Hotspots are uncoordinated and dense Unpredictable performance Efficient use of 802.11 channels is important Channel Assignment Problem Mapping of channels to APs Can affect performance significantly Hotspot locations in Manhattan


Take Home Message - 1 : Take Home Message - 1 Fairness in throughput among APs is important when assigning channels in hotspots ‘Static’ channel assignment methods cause unfairness in hotspot environments A B D C 3 channels, 4 APs APs on same channel


Take Home Message -2 : Take Home Message -2 Channel Hopping can improve the fairness properties of existing static channel assignment methods APs on same channel


Take Home Message - 3 : Take Home Message - 3 Through careful modeling of interference, it is possible to use partially overlapped channels Refer to our paper in Sigmetrics ’06: “Partially Overlapped Channels Not Considered Harmful” Channel Hopping can take advantage of partially overlapped channels


Take Home Messages : Take Home Messages Fairness: AP-level Fairness is important in hotspots Static channel assignment methods cause unfairness Channel hopping can improve the fairness of existing static channel assignment methods Channel hopping can take advantage of partially overlapped channels for additional fairness and throughput gains


Talk Outline : Talk Outline Fairness in Hotspots Channel Hopping improves fairness Designing MAXchop Evaluation


Proper Usage of 802.11 Channels : Proper Usage of 802.11 Channels Nodes share a single channel Throughput scales with the number of non-overlapping channels 1 channel Throughput 3 Channels 3 channels


Channel Assignment for Hotspots : Channel Assignment for Hotspots Hotspots typically consist of single APs An AP and all its associated clients use one channel Interfering hotspots need to be on a different channel


Channel Assignment for Hotspots : Channel Assignment for Hotspots 2.4 GHz has 3 non-overlapping channels 1, 6 and 11 APs can select such channels by scanning Least Congested Channel Search Channel 1 Channel 6 Channel 11


Channel Assignment for Hotspots : Channel Assignment for Hotspots What if there are more hotspots ? Typical in today’s wireless landscape Channel 1 Channel 6 Channel 11 Channel ?


Fairness is key for Hotspots : Fairness is key for Hotspots Each hotspot wants to maximize throughput for its users


Fairness is key for Hotspots : Fairness is key for Hotspots Thus, a fair division of the wireless bandwidth is important Among APs (and not just users)


Static Methods are unfair ! : Static Methods are unfair ! Only 3 non-overlapping channels in 2.4 GHz band 2.4 GHz ISM Band Ch 1 Ch 6 Ch 11


Static Methods are unfair ! : Static Methods are unfair ! Resulting ‘interference graph’ is dense !


Static Methods are unfair ! : Static Methods are unfair ! Channel assignment essentially becomes graph coloring APs on same channel


Static Methods are unfair ! : Static Methods are unfair ! Even optimal centralized solutions are unfair 1 11 6 6 1 11 6 11 APs on same channel


Talk Outline : Talk Outline Fairness in Hotspots Channel Hopping improves fairness Designing MAXchop Evaluation


Channel Hopping improves Fairness : Channel Hopping improves Fairness Network as a whole ‘cycles’ through multiple different channel assignments Time Time slot


Channel Hopping improves Fairness : Channel Hopping improves Fairness No single AP suffers for long Time


Channel Hopping improves Fairness : Channel Hopping improves Fairness Long term throughput of each AP gets averaged over multiple different channel assignments Time


Channel Hopping improves Fairness : Channel Hopping improves Fairness The potential to improve fairness even over the best static channel assignments Time


Talk Outline : Talk Outline Fairness in Hotspots Channel Hopping improves fairness Designing MAXchop Evaluation


Designing MAXchop : Designing MAXchop


Designing MAXchop : Designing MAXchop Beacon frames contain sequences of channels or hopping sequences Client-AP Channel switch is synchronized with beacons Hopping sequences evolve in a distributed manner Collectively the sequences converge for the network as a whole


Designing MAXchop - Practical Considerations : Designing MAXchop - Practical Considerations Channel Switch overhead 20 ms for Prism cards 5 ms for Atheros 200 us for Intel (not tested) Packet loss during switch Hardware transmit is disabled during switch Data Ack


Talk Outline : Talk Outline Fairness in Hotspots Channel Hopping improves fairness Designing MAXchop Evaluation


Simulation Parameters : Simulation Parameters Hotspot data for the city of San Francisco from wigle.net Partitioned into 12 topologies Two sets of simulations : One sample topology for detailed analysis Statistical properties over the remaining topologies Red dots indicate AP locations San Francisco City


Simulation Parameters : Simulation Parameters NS-2 packet level simulations Augmented with support for bit-level errors Auto-rate fallback Power levels similar to commodity APs Algorithms: Commodity algorithm: Least Congested Channel Search Each AP scans and selects the channel that offers the least amount of congestion Channel Hopping : MAXchop


Simulation – Sample Topology : Simulation – Sample Topology Concentrated dense pockets of 27 APs Representative of hotspot interference in urban areas


Simulation Results – Sample Topology : Simulation Results – Sample Topology UDP Throughput, full throttle. 20 % improvement in aggregate throughput UDP Throughput Least Congested Channel Search (LCCS) MAXchop


Simulation Results – Statistical Properties : Simulation Results – Statistical Properties Twelve topologies chosen from wigle.net Representative of the dense and variable deployment patterns


Simulation Results – Statistical Properties : Simulation Results – Statistical Properties UDP traffic, full throttle Randomized Compaction (RaC) [Infocom ’06] Centralized, assumes full coordination and roaming Acts as an upper bound


Simulation Results – Statistical Properties : Simulation Results – Statistical Properties RaC optimizes for max-min fair throughput MAXchop does ‘nearly’ as well as RaC


Experiments : Experiments Implementation Standard Linux platform User-level daemon does channel switching Study performance of TCP/UDP traffic Experiment topology designed to mimic dense hotspots


Experiment Results – UDP traffic : Experiment Results – UDP traffic With partially overlapped channels, MAXchop improves both fairness and throughput See ‘Partially Overlapped Channels Not Considered Harmful’, Sigmetrics 06. MAXchop MAXchop Manual LCCS Non-overlapped channels Partially overlapped channels


Key Insights : Key Insights Fairness is important for hotspots All static channel assignment schemes will be unfair Because of the dense nature of the hotspots Even optimally computed ones Channel hopping improves fairness Uses any existing channel assignment method Channel hopping can take advantage of partially overlapped channels


Your Questions : Your Questions Thank you for listening !


Fairness is key for Hotspots : Fairness is key for Hotspots Uncoordinated deployment Hotspots typically consist of single APs Each hotspot wants to maximize throughput for its users Thus, fair division of the wireless bandwidth is key


Fairness is key for Hotspots : Fairness is key for Hotspots Uncoordinated deployment Hotspots typically consist of single APs Each hotspot wants to maximize throughput for its users Thus, fair division of the wireless bandwidth is key


Fairness is key for Hotspots : Fairness is key for Hotspots Uncoordinated deployment Hotspots typically consist of single APs Each hotspot wants to maximize throughput for its users Thus, fair division of the wireless bandwidth is key


What is Channel Assignment : What is Channel Assignment SCAN : APs sense other interfering APs SELECT : They select the best channel based on congestion information for each channel Same as distributed graph coloring This distributed algorithm is close to the best


But Fairness is an important goal : But Fairness is an important goal Each AP represents an independent user Users need a fair division of the system’s resources


Static channel assignments are unfair ! : Static channel assignments are unfair ! Four clique, three channels (2.4 GHz band) Two APs inevitably suffer in all static assignments of channels 2 2


What do I mean by “static” : What do I mean by “static” Assignments that don’t change rapidly Includes dynamic assignment methods which utilize one logical channel assignment for a long time (such as 60 seconds or more )


What can Channel Hopping do ? : What can Channel Hopping do ?


Novel use of channel hopping : Novel use of channel hopping Fairness is an undiscovered property of channel hopping Allows the network to timeshare between different global channel assignments in a distributed manner


Novel use of channel hopping : Novel use of channel hopping


Design Considerations for MAXchop : Design Considerations for MAXchop Communicate hopping sequences through beacon messages Randomized in nature Interfering APs synchronize through beacons


Packet-level Simulations : Packet-level Simulations Allows us to study statistical properties of using channel hopping Topologies derived from real-world AP locations – wigle.net Users are uniformly distributed among APs NS-2 simulator Augmented with bit-error model, rate adaptation, and partially overlapped channels.


Practical Issues – Channel Switch Overhead : Practical Issues – Channel Switch Overhead Overhead


Practical Issues – Effect on TCP : Practical Issues – Effect on TCP


Design of Experiments : Design of Experiments


Experiment Results : Experiment Results


Proposed Solution : Proposed Solution Our solution is based on a loose market mechanism without any specific rules being imposed on the peers In p2p streaming, if the peers do not forward bandwidth to their peer community, then all the peers will try to join the publisher directly


Fairness is key for Hotspots : Fairness is key for Hotspots Uncoordinated deployment Hotspots typically consist of single APs Each hotspot wants to maximize throughput for its users Thus, fair division of the wireless bandwidth is key


Fairness is key for Hotspots : Fairness is key for Hotspots Hotspots typically consist of single APs


Fairness is key for Hotspots : Fairness is key for Hotspots Uncoordinated deployment


Fairness is key for Hotspots : Fairness is key for Hotspots Thus, a fair division of the wireless bandwidth is important


Today’s Wi-Fi Hotspots : Today’s Wi-Fi Hotspots Homes, cafes, restaurants Uncoordinated High and variable densities Unpredictable performance Efficient use of 802.11 channels is important


Simulation Results – Sample Topology : Simulation Results – Sample Topology TCP traffic, full throttle. 15 % improvement in aggregate throughput Least Congested Channel Search (LCCS) MAXchop TCP Throughput


Experiment Results – TCP traffic : Experiment Results – TCP traffic Similar results 20 ms channel switching overhead TCP throughput suffers negligibly due to channel switching MAXchop MAXchop LCCS LCCS Non-overlapped channels Partially overlapped channels


Interesting Questions : Interesting Questions Fundamental limits of channel hopping ? New definition of optimal fairness How much fairness can it improve Can it reduce fairness ? Game theoretic extensions What if certain APs can collaborate ? Implementation hurdles What design considerations does this bring for the RF engineer ?