Performance issues & improvement on 802.11 MACAn Overlay MAC Layer for 802.11 NetworksMotivationProblem 1: different data ratesProblem 2: unpredictabilityProblem 3: forwarding on behalf of othersProblemsApproachesAdvantages of an overlay approachBigger picture: overlay networkBigger picture: Overlay networkEven bigger picture: virtualizationOverlay MAC Layer (OML) design goalsOverlay MAC Layer (OML): what can it control?Detour: strict priority schedulingDetour: weighted fair queuingOWL main idea: use TDMA-like scheduleQuestionsClock synchronization & slot sizeInterference regionWeighted Slot Allocation: decide winner w/o communicationEvaluation methodologySummary of resultsSimulation resultsSimulation results (cont.)SummaryLimitations1Performance issues & improvement on 802.11 MACreview of 802.11 MACperformance issuesimprovementsidle sensean overlay approach more …2An Overlay MAC Layer for 802.11 NetworksAnanth Rao Ion StoicaUC BerkeleyMobisys 20053MotivationInternet Gateway802.11 hardware provides initial ease of deployability for many applicationsmesh networkslong haul linkslarge Infrastructure Networksthese apps stretching 802.11 beyond its design goals (Wireless LANs)4Problem 1: different data ratesData Rate ThroughputCase IA 11 Mbps 3.09 MbpsB 11 Mbps 3.36 MbpsCase IIA 11 Mbps 0.76 MbpsB 1 Mbps 0.76 MbpsRBA5Problem 2: unpredictability21 3 4 56Problem 3: forwarding on behalf of othersEthernet1/21/61/61/61/31/91/91/9This problem cannot be solved by local scheduling or queue management algorithms like WFQ7802.11 provides no control over resource allocationDefault allocation policy ill-suited for multi-hop networksBad fish problemForwarders get same share as othersProblemsA B C D1M11MA B C DEF8Approachesworkarounds in routing/transport layereasy to deploycannot address some issueschange/replace MAC new protocols, new standardmore powerful, hard to deployoverlay MAC layer (OML)directly on top of 802.11 MACno need to change hardwaredirectly use interfaces exposed by 802.11 cards9Advantages of an overlay approacheasy to deployeasy to modifyimplemented in softwareeasy to modify for diverse requirementstighter integration between MAC and upper layersperformance benefitsutilize information from higher layers10Bigger picture: overlay network11Bigger picture: Overlay networkFocus at the application level12Even bigger picture: virtualizationVirtualization of resources: powerful abstraction in systems engineering:computing examples: virtual memory, virtual devicesvirtual machines: e.g., javaIBM VM os from 1960’s/70’sNetworking examples:connecting local heterogeneous networksIP over ATMoverlay networksVPN13Overlay MAC Layer (OML) design goalsefficientfair or differentiated allocationflexible and low costavoid modifying MAC14Overlay MAC Layer (OML): what can it control?no control in upper layercannot decide when getting a packetno control in MACcannot decide when packet is actually sentcan control only when to send packet to network cardpacket scheduling policy: FIFO, strict priority scheduling, weighted fair queuing15Detour: strict priority schedulingtransmit highest priority queued packet multiple classes, with different prioritiesclass may depend on marking or other header info, e.g. IP source/dest, port numbers, etc..real world example: reservations versus walk-ins 13452time1time3245arrivalsdeparturespacketservice5423116Detour: weighted fair queuingeach class gets weighted amount of service in each cycleequal weight: Round Robin scheduling17OWL main idea: use TDMA-like scheduledivide time into slotsweighted slot allocation (WSA): allocate slots to nodes according to weighted fair queuing policyassigns a weight to each nodeallocate slots proportion to nodes’ weights -> weighted allocationa slot is only assigned to one node in an interference region -> reduce packet loss18Questionsclock synchronization?slot length?interference region?weighted slot allocation how to choose weight? decide a winner w/o communication?19Clock synchronization & slot sizeLoose time synchronizationleader-based slot size: 10 packets of maximum sizelarger than clock synchronization errorlarger than packet transmission timeas small as possible20Interference regionideally node i applies WSA to all nodes that interfere with ihow to determine who interfere with me? assume a node can interfere with all nodes within k-hop distanceonly an approximation, not accuratehow to determine interference relationship is an active research!21Weighted Slot Allocation: decide winner w/o communicationeach node uses pseudo-random function to generate a random numberHi = H(ni, t) 1/wit: time slot, wi: weight of node ni can generate random number for all nodes in the collision domain (e.g., 2-hop neighborhood) the highest number wins22Evaluation methodologySimulation in QualnetImplementation in Atheros Madwifi driver + Click router23Summary of resultsOverhead: OML thruput comparable to native 802.11Reduced contention and retransmissionsFairness: Fairness index for OML network much higherA node’s share = # flows passing thru itLimitations: Impact of mobility; Interference from native 802.11 clients24Simulation resultsSimilar throughput to 802.11Control overhead is small25Simulation results (cont.)Improved fairness over standard 802.11Weight set to number of nodes in output queue26SummaryCoarse-grained scheduling on top of 802.11:alleviate inefficiencies of the MAC protocol in resolving contentionovercome the lack of flexibility of assigning priorities to sendersEnables experiment with new scheduling and bandwidth management algorithms27LimitationsInterference from other 802.11 clientsFace incrementally deployment issuesImpact of mobilityTakes some time for newly joined nodes to get its proportional share How to set weight? How to know of weights of nodes in interference region (weights can be
View Full Document