CMPE 257 Wireless and Mobile Networking SET 3f Medium Access Control Protocols Winter 2004 UCSC CMPE252 1 MAC Protocol Topics Fair medium access and fair scheduling queueing MACAW Topology independent fair queuing Spring 2005 CMPE257 UCSC 2 The Fairness Problem Unequal opportunity to access the channel Severe throughput degradation Causes Binary exponential backoff BEB Location dependent contention Node B Node A Node C Node D Example Flow CD will capture the channel Spring 2005 CMPE257 UCSC 3 Prior Work on Fairness Max min fairness Reduce the ratio between max throughput and min throughput of flows Backoff or dynamic adjustment of channel access Fair queuing FQ approach Adapt wireline FQ disciplines to ad hoc networks Flow contention graph as a useful abstraction Flows are tagged as either leading or lagging and then backoff window is adjusted accordingly Spring 2005 CMPE257 UCSC 4 MACAW BDSZ94 One of the earliest work on throughput and fairness enhancement Note Packet sensing not carrier sensing is used Per node and per stream fairness Maintain backoff windows for different streams also appears in IEEE 802 11e Backoff copy and MILD backoff Multiplicative increase linear decrease to address the fairness problem Spring 2005 CMPE257 UCSC 5 Topology Independent Fair Queuing Design Goals LL00 LL05 QoS Support for Advanced Applications in Ad Hoc Wireless Networks Fair Allocation of Channel Bandwidth Maximal Channel Utilization under Fairness Constraint Communication Intensive Applications Limited bandwidth Wireless Channel Distributed Spring 2005 Packet Scheduling Design CMPE257 UCSC 6 Outline Issues in Ad Hoc Wireless Fair Queueing Fair Queueing Model for Packet Scheduling An Idealized Centralized Algorithm A Distributed Implementation Performance Evaluation Conclusion and Future Work Spring 2005 CMPE257 UCSC 7 Network Model A Single Shared Physical Channel Collision Receiver in Transmission Range of More than One Transmitting Node Flow Stream of Packets from Source to Destination Sender Receiver Flow ID CSMA CA MAC Framework Spring 2005 CMPE257 UCSC 8 Spatial Reuse Design Issues Location Dependent Contention F3 Channel Reuse F1 X F2 Spatial Collision Spring 2005 CMPE257 UCSC 9 Design Issues F3 F1 F4 F2 No Spatial Reuse Contention Spring 2005 CMPE257 UCSC 10 Flow Contending Graph F3 F1 F3 F1 F4 F4 F2 F2 Spring 2005 Node Graph Flow Graph CMPE257 UCSC 11 Design Issues cont d Inherent Conflict between Achieving Fairness Maximizing Channel Utilization F1 F3 F1 F4 F2 F5 F3 F4 F5 F2 Node Graph Flow Graph To Maximize Channel Utilization Schedule F3 F5 Number always MIS Schedule the Maximal of Flows in Flow Graph Starve F1 F2 F4 Spring 2005 CMPE257 UCSC 12 Design Issues cont d Distributed Nature of Packet Scheduling in Ad Hoc Wireless Networks Unlike Wireline or Packet Cellular Networks NO Single Logical Entity for Scheduling NO Direct Access to All Contending Flow Info Provide QoS at Finest Time Scale Packet Level Spring 2005 CMPE257 UCSC 13 Solution Space Maximize Channel Utilization Always Schedule Largest Number of Nonconflicting Flows Starvation of Certain Flows Ensure Fairness Maximize Spatial Channel Reuse Subject to Fairness Constraint Spring 2005 CMPE257 UCSC 14 Enable Spatial Channel Reuse F1 F4 F2 F3 FQ Tagging F1 1 F2 1 F3 1 F4 1 F1 2 F2 2 F3 2 F4 2 Wireline FQ 0 1 2 3 4 5 6 7 F1 1 F2 1 F3 1 F4 1 F1 2 F2 2 F3 2 F4 2 Spring 2005 CMPE257 UCSC 15 Look Ahead Window F1 F4 F2 F3 FQ Tagging F1 1 F2 1 F3 1 F4 1 F1 2 F2 2 F3 2 F4 2 Wireline FQ 0 1 2 3 4 5 6 7 F1 1 F2 1 F3 1 F4 1 F1 2 F2 2 F3 2 F4 2 Lookahead window 4 bits FQ with F1 1 F2 1 F1 2 F2 2 Lookahead F3 1 F4 1 F3 2 F4 2 Spring 2005 CMPE257 UCSC 16 Minimum Graph Coloring Maximizing Spatial Reuse within a Look Ahead Window is a Minimum Coloring Problem F3 F3 F4 F1 F5 F0 Contending Graph F5 F0 F2 F2 Spring 2005 Flow F4 F1 CMPE257 UCSC 17 Dynamic Graph Coloring Look Ahead Window Moves Forward Balance Two Design Goals Transmit Current Window of Bits ASAP Move Window Ahead AFAP Spring 2005 CMPE257 UCSC 18 An Adaptive Algorithm Two Key Components A Basic Scheduling Loop Adaptive Dynamic Coloring Spring 2005 CMPE257 UCSC 19 Basic Scheduling Loop WFQ to Assign Flow Tags V t Smallest Finish Tag A Lookahead Window of V t V t Spring 2005 Bits Partition Flows into Disjoint Sets Schedule the Set with Least Tagged Flow Move Window Forward to Next Least Tagged Flow CMPE257 UCSC 20 Adaptive Dynamic Coloring As Lookahead Window Moves from V t 1 V t 1 to V t V t Retain Disjoint Sets of Unserved Packets in V t 1 V t 1 Merge Newly Joined Packets Create New Set if No Merge Possible Retain All Disjoint Sets until t 1 Spring 2005 CMPE257 UCSC 21 Properties of Central Algorithms Number of Disjoint Sets Non increase Adaptively Reduce Total Number of Disjoint Sets Move the Window Forward Fairness Guarantee Spatial Channel Reuse Throughput Delay Bounds Spring 2005 CMPE257 UCSC 22 Distributed Implementation Approximate Central Algorithm A Backoff Based Approach Within CSMA CA MAC Framework Approximate WFQ with Modified WRR Backoff based Implementation of Largest degree First LF Coloring Algorithm Backoff based Implementation of Adaptive Algorithms Spring 2005 CMPE257 UCSC 23 An Example Adaptive Dynamic Coloring 3 F3 4 F4 F1 5 F0 2 2 F5 Partition Flows into Disjoint Sets F2 2 Spring 2005 CMPE257 UCSC 24 An Example Largest Degree First Set Backof Flow Degree F0 3 F3 F1 4 F4 F1 5 F0 2 F2 2 1 F2 2 F5 4 3 F3 F4 F5 Spring 2005 4 CMPE257 UCSC 2 4 Time 25 An Example FQ Tagging F1 1 F4 1 F3 1 F2 1 F5 1 F0 1 F1 2 F4 2 Wireline FQ 1 0 2 3 4 5 6 7 F1 1 F5 1 F0 F3 F1 F4 F1 F2 4 3 F3 F4 F5 Spring 2005 1 F2 F5 F0 4 CMPE257 UCSC 2 4 Time 26 An Example FQ Tagging Wireline FQ F4 1 F3 1 F2 1 1 0 2 3 F0 1 F1 2 F4 2 4 5 6 7 F1 1 F4 1 F5 1 F0 1 F0 F3 F1 F4 F1 F2 4 3 F3 F4 F5 Spring 2005 1 F2 F5 F0 4 CMPE257 UCSC 2 4 Time 27 An Example FQ Tagging Wireline FQ F3 1 F2 1 1 0 2 F1 1 F4 1 F2 1 F5 1 F0 1 F3 1 7 4 1 4 3 F3 F4 F5 Spring 2005 6 F2 F5 F2 5 F1 F4 F0 4 F0 F3 F1 3 F1 2 F4 2 CMPE257 UCSC 2 4 Time 28 Other Issues Detailed MAC Layer Design CSMA CA Paradigm Global Flow Information i e Flow Weights Propagation Conflict free Multicast Tree Spring 2005 CMPE257 UCSC 29 Simulation Example F9 F6 F0 F8 F5 F1 F7 F3 F16 F12 F13 F2 F4 F10 17 flows 15 source nodes Simulation slots 100 000 Poisson MMPP Traffic F14 F11 F15 Spring 2005 CMPE257 UCSC 30 Simulation Example Normalized Throughput Normalized …