EE206A Lecture #5 Sharing the Wireless Link: Part II
Mani Srivastava mbs@ee.ucla.edu University of California at Los Angeles Electrical Engineering Department
Copyright 2002 Mani Srivastava
Reading List for This Lecture
MANDATORY READING: [Bharghavan94] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, "MACAW: A Media Access Protocol for Wireless LAN's," ACM SIGCOMM, 1994. [Brenner97] Pablo Brenner. A Technical Tutorial on the IEEE 802.11 Protocol. Breezecom, 1997. http://nesl.ee.ucla.edu/pw/ee206a/802_11tut_breezecom97.pdf RECOMMENDED READING: [IEEE 802.11] IEEE 802.11 Tutorial. Available in pdf (in five parts) at http://grouper.ieee.org/groups/802/11/main.html#Tutorial OTHER READING: [IEEE802.11 Standard] http://standards.ieee.org/reading/ieee/std/lanman/ In particular, IEEE 802.11 Standard specification, 1999, Chapter 9.
Copyright 2002 Mani Srivastava
Packet-Oriented Wireless Multiple Access
Sharing of Time-Frequency Space
Slotted-time vs. Non-slotted time
Static (Fixed) Assignment
e.g. Time-division & Frequency-division
Demand-based Assignment Contention-based Conflict-free Random Access
e.g. ALOHA, PRMA Carrier-sensing e.g. Token-passing & Polling
Connection Oriented Scheduled Access
e.g. DQRUMA
Packet Oriented
Copyright 2002 Mani Srivastava
Controlled Random Access
2
Contention-based Multiple Access
Many transmitters access a channel with no or minimal coordination Transmission in bursts of data Collisions may happen: need ACK or NACK with retransmission - delays induced - lower spectral efficiency
Three categories: random access, scheduled access, hybrid access
Transmitter # 1
Packet B
Packet C
Transmitter # 2
Packet A
One Packet Time () Vulnerable Period (2)
Time
Copyright 2002 Mani Srivastava
What is so special about the wireless case?
e.g. Ethernet uses contention-based medium access... Following attributes make contention-based multiple access interesting with wireless: - carrier sensing is much costlier in wireless 20-30 s - cant listen while transmitting therefore cannot detect collisions - what matters is the collision at a receiver ... but the transmitter cant sense the channel at the receiver! - effects of spatial distribution of wireless nodes hidden terminal problem exposed terminal problem near-far problem (capture effect)
Nevertheless, the first contention-based scheme (ALOHA) was for wireless
4
Copyright 2002 Mani Srivastava
Pure ALOHA and Slotted ALOHA
Pure ALOHA (random access channel) - channel accessed as soon as message ready - wait for ACK on same or separate channel - if collision (time-out or NACK), retransmit after a random back-off - more collisions as number of users increases
Slotted ALOHA - time is divided into equal time slots of length > - transmitters are synchronized, and only transmit at beginning of slot - vulnerable period reduced to from 2 - maximum channel utilization (1/e =.3679) is x2 of pure ALOHA (1/2e =.1839) under Poisson traffic
retransmission Pure ALOHA retransmission
collision
Slotted ALOHA Copyright 2002 Mani Srivastava 5
Performance of ALOHA - the Usual Approach
total offered traffic G = -----------------------------------------------------------------maximum possible data rate channel throughput S = -----------------------------------------------------------------maximum possible data rate ... may be > 1 ... will be 1 and includes retransmissions
Assume that G represents the mean number of packet arrivals during a packet transmission time interval in a Poisson packet traffic model, i.e. k G P ( k packets generated in a packet transmission time ) = P ( k ) = G e --------------k! Then, for Pure ALOHA, S = GP ( no collision during 2 x packet transmission time ) = Ge 2G Maximum value of S occurs for G = 0.5 , and is S max = 1 ( 2e ) = 0.184 . A packet is retransmitted with a probability 1 e 2G Mean # of times a packet is retransmitted N is 1 ( 1 ( 1 e 2G ) ) = e 2G So that, the delay throughput characteristic is S = ln(N) ( 2N ) Similarly, for Slotted ALOHA S = Ge G with maximum value of S at G = 1.0 , is 0.368. The delay-throughput relation is S = ln(N) N
Copyright 2002 Mani Srivastava 6
Performance of ALOHA - Graphically
0.4 0.35 0.3 0.25 Slotted ALOHA 10 9 8 7 6 0.2 0.15 0.1 0.05 0 0 1 2 3 4 5 6 7 8 9 10 Pure ALOHA Pure ALOHA Slotted ALOHA
5 4 3 2 1 0 0.05 0.1
0.15
0.2
0.25
0.3
0.35
0.4
G = offered load, S = channel utilization, N = mean # of retransmissions Stability problem once the operating point wanders to the right side - increase in G leads to reduction in S which leads to further increase in G ... - backoff algorithm becomes important to ensure stability
Copyright 2002 Mani Srivastava
Carrier Sense Multiple Access (CSMA) Protocols
Listen before transmit scheme - ALOHA protocols transmit blindly - CSMA listens for carrier before transmitting, transmit only if channel idle
Detection delay - time needed for terminal receiver to sense whether or not channel is idle Propagation delay - relative measure of how fast the packet travels - effects performance because another transmitter may sense an idle channel and begin to send data if the packet does not reach it
Several variations of CSMA 1-persistent: on channel idle, transmit with probability 1 non-persistent: on collision, wait a random time before retransmitting (used in WLANs where packet transmit interval >> propagation delay) p-persistent: on idle, transmit with prob. p in first slot and 1-p on next slot CSMA/CD: listen-while-talk - monitor transmission & abort on collision (in wireless need to interrupt transmission to sense the channel)
Copyright 2002 Mani Srivastava
Review: 1-Persistent CSMA
while (1) { while (channel_sense()==BUSY) continue; send_packet(); if (waitfor(ACK,time_threshold)==TIMEOUT) { waitfor(random_time); continue; } else break; }
Better than ALOHA due to channel sensing, but... - collisions are not eliminated - performance depends on propagation delay - multiple waiting users may transmit on busy-to-free transition
Comes in a slotted version too
Copyright 2002 Mani Srivastava
Review: Nonpersistent CSMA
while (1) { while (channel_sense()==BUSY) waitfor(random_time_1); send_packet(); if (waitfor(ACK,time_threshold)==TIMEOUT) { waitfor(random_time); continue; } else break; }
Does not continuously sense the channel - waits a random time before sensing again Waiting time eliminates most of collisions on busy-to-free transition - maximum throughput of 80% or higher under typical delays - but causes performance when only few users
Comes in a slotted version too
Copyright 2002 Mani Srivastava
10
Review: p-Persistent CSMA
transmitted=0; while (!transmitted) { while (channel_slot_sense()==BUSY) continue; do { if (uniform_rv(0,1)<p) { send_packet(); if (waitfor(ACK,time_threshold)==TIMEOUT) { waitfor(random_time); } else transmitted=1; break; } } while (channel_slot_sense()==IDLE); }
Generalization of 1-persistent CSMA, for slotted channels - slot length == maximum propagation delay - parameter p needs to be chosen carefully - for low-to-medium delays, throughput is between slotted & unslotted non-persistent CSMA - for long propagation delays, it works the best
Copyright 2002 Mani Srivastava
11
CSMA with Collision Detection/Avoidance
CSMA/CD: enhancement to slotted or unslotted CSMA schemes Node monitors its own transmission - if collision detected, transmission is aborted without waiting for a NACK backoff and retransmission procedure started - a jamming signal may be sent to get everybody else to abort too
Problem: does not work with RF wireless - cannot easily sense the channel while transmitting MHs signal will dominate need different receiving and transmitting antenna patterns
But, does work well with infrared wireless... directional receivers Wireless networks stick with the ACK/NACK approach - popularly called CSMA/CA - but, not really a strictly defined scheme... many variants some implement as CSMA + exponential backoff + ACK some use DSMA or even reservation
Copyright 2002 Mani Srivastava
12
Data Sense Multiple Access (DSMA)
Variation of CSMA - also called Inhibit Sense Multiple Access Basestation transmits a busy/idle message on a forward control channel Mobile listens on the forward control channel for the busy/idle message Mobile transmits on the reverse channel only if busy/idle message indicates that the reverse channel is free Back-off and retransmit if collision occurs nevertheless Used in CDPD (cellular digital packet data)
Reverse link: contention with back-off
Forward link: idle/busy signal
Copyright 2002 Mani Srivastava
13
Problems in Contention-based Wireless Multiple Access
Near-far effect - characterized by capture ratio of the receiver - strongest (nearby) transmitter can capture the intended receiver - weaker (far away) transmitters get ignored by the receiver - depends on receiver and modulation used - fairness problem Hidden terminal problem - terminal hidden from the transmitter may disrupt the receiver - makes carrier sensing ineffective - A cannot detect collisions at B due to transmissions from C - solve by using RTS/CTS control frames to reserve medium (AppleTalk)
RTS range CTS range
A
RTS CTS Data
B
CTS
A
ACK
C hidden terminal
Copyright 2002 Mani Srivastava
14
More on RTS/CTS
RTS/CTS serve to reserve the medium - RTS contains length of proposed transmission - CTS also contains length of proposed transmission - MHs overhearing RTS defer all transmissions until after CTS would have finished (including receiver turnaround time) - MHs overhearing CTS defer for length of data packet transmission - RTS and CTS are short... their collisions dont hurt that much - retransmissions happen only if no CTS is received in response to RTS e.g. MACA (Phil Karn) in Packet Radio - uses binary exponential backoff for retransmission (backoff increased exponentially up to BOmax on failure, reset to BOmin success)
Binary exponential backoff (BEB) has problems - does not provide fairness if every MH generates enough traffic to consume the channel - after collisions, the less-backed-off mobile wins eventually all but one MH are backed-off to BOmax
Copyright 2002 Mani Srivastava
15
Exposed Terminal Problem
As range Bs range
Cs range
D A B C exposed terminal
C will sense channel busy, and defer, but doesnt need to - the C to D transmission can take place but is delayed
Copyright 2002 Mani Srivastava
16
Enhancements to MACA: MACAW
Fixing the backoff 1. MHs exchange values of their back-off counters BO - carried in packet headers, and copied by MHs that are listening problem: mobiles need to be up all the time! - but, a single number is bad idea... congestion not homogeneous regions may have different levels of congestion 2. multiplicative backoff on failure, and decrease by 1 on success MACAs exponential backoff on failure, and reset on success resulted in large variations, and unfair conditions
Fixing the signalling: RTS-CTS-DS-DATA-ACK and RRTS 1. Adding ACK helps in faster recovery MACA relied on transport layer for retransmissions 2. DS sent before sending DATA - tells other MHs that RTS-CTS was successful - defer until after ACK - avoids doing carrier sensing... DS is like a virtual carrier - helps at exposed terminals... no need to do futile RTS and backoff 3. RRTS (Request for RTS) - a MH receiving a RTS to which it cannot, it later sends RRTS - useful at MHs that are deferring, for example, due overhearing a CTS
Copyright 2002 Mani Srivastava
17
IEEE 802.11 MAC
Support for multiple PHYs - single and multiple channel PHYs - PHYs with different Medium Sense characteristics - available PHY layers: original 802.11: 900M and 2.4G ISM band DSSS & FHSS, IR @ 1 and 2 Mbps 802.11b: 2.4 GHz DSSS @ 5.5 & 11 Mbps 802.11a: 5 GHz OFDM @ 6-54 Mbps Efficient medium sharing without overlap restrictions - multiple networks in same area and channel space - Distributed Coordination Function: using CSMA /CA - based on carrier sense mechanism called Clear Channel Assessment (CCA) Robust against interferers (e.g. co-channel interference, microwave + other non 802.11 interferers) - CSMA/CA+ACK for unicast frames with MAC level retransmission Protection against Hidden Terminal problem: Virtual Carrier Sense - via parameterized use of RTS/CTS frames with duration information Provision for Time Bounded Services via Point Coordination Function
18
Copyright 2002 Mani Srivastava
IEEE 802.11 MAC (contd.)
ad hoc network
distribution system
infrastructure network
Two Configurations: ad hoc & distribution system connecting access points Roaming: mobile-controlled hand-offs with registration at new basestation Power management Authentication and privacy
Copyright 2002 Mani Srivastava
19
Packet Structure for 802.11 (DSSS)
SYNC 128bits
SFD 16 bits
SIGNAL 8 bits
SERVICE 8 bits
LENGTH 16 bits
CRC 16 bits
PLCP Preamble 144 bits
PLCP Header 48 bits
192 s
MPDU
1 DBSK Barker 2 DQPSK Barker 5.5 or 11 Mbps CCK
PPDU
Preamble and Header always at 1Mb/s DBPSK
Copyright 2002 Mani Srivastava
20
Packet Fields
SYNC - 128 scrambled 1 bits - used for: gain setting, energy detection, antenna selection, frequency offset compensation SFD (Start Frame Delimiter) - 16 bit (0xF3A0), used for bit synchronization Signal field - rate indication: 0x0A (1 Mbps DBPSK), 0x14 (2 Mbps DQPSK), etc. Service field - reserved for future use, 0x00 indicates 802.11 compliance Length field - indicates numbers of octets to be transmitted in MPDU - used for end of frame detection, MPDU CRC sync CRC field - CCITT CRC-16 - protects signal, service, and length field All bits are scrambled to whiten the spectrum - scrambling polynomial G(z) = z^-7 + z^-4 + 1
Copyright 2002 Mani Srivastava 21
IEEE 802.11 MAC (contd.)
CSMA/CA: direct access if medium free for > DIFS, else defer & back-off
DIFS DIFS PIFS DATA SIFS defer access
source other
contention window
DATA select slot & decrement back-off as long as idle
CSMA/CA + ACK: receiver sends ACK immediately if CRC okay - if no ACK, retransmit frame after a random back-off
DIFS
source receiver other
contention window DATA SIFS ACK DIFS defer access DATA select slot & decrement back-off as long as idle
RTS/CTS with duration: distribute medium reservation information - also used in the defer decision (virtual carrier sensing)
Copyright 2002 Mani Srivastava
22
IEEE 802.11 MAC (contd.)
Timing parameters dictate access priority - SIFS = short interframe space - PIFS = PCF interframe space - DIFS = DCF interframe space
Backoff time is decremented only when channel is idle - frozen when channel is busy - resumed after busy-to-free transition only after DIFS
Backoff timer is chosen = int(CW[] * random()) * slot_time - CW is an integer between CWmin=7 and CWmax=255 CW assignment - for every fresh frame, CW is CWmin - on each unsuccessful transmission, CW is incremented until CWmax
Due to spatial effects, performance at all MH is not the same
Copyright 2002 Mani Srivastava
23
Fragmentation
DIFS PIFS
Other Src Dest
SIFS RTS
SIFS NAV (RTS) NAV (CTS) NAV (Fragment 0) NAV (ACK 0) Backoff-Window
Fragment 0
Fragment 1
CTS
ACK 0
ACK 1
Burst of Fragments which are individually acknowledged. - For Unicast frames only. Random backoff and retransmission of failing fragment when no ACK is returned. Duration information in data fragments and Ack frames used by medium reservation mechanism.
24
Copyright 2002 Mani Srivastava
MAC Frame Formats
MAC Header format differs per Type: - Control Frames (several fields are omitted) - Management Frames - Data Frames
Bytes: 2
Frame Control
2
Duration ID
2
Sequence Control
6 Addr 4
0-2312 Frame Body
4 CRC
Addr 1 Addr 2 Addr 3 802.11 MAC Header
Bits: 2 Protocol Version
2 Type
4 SubType
1 To DS
1 From DS
1 More Frag
1 Retry
1 Pwr Mgt
1 More Data
1 WEP
1 Rsvd
Frame Control Field
Copyright 2002 Mani Srivastava
25
Address Field Description
Addr 1 = All stations filter on this address. Addr 2 = Transmitter Address (TA) Identifies transmitter to address the ACK frame to. Addr 3 = Dependent on To and From DS bits. Addr 4 = Only needed to identify the original source of WDS (Wireless Distribution System) frames.
Copyright 2002 Mani Srivastava
26
Reversing the Collision Avoidance Handshake
Reversing the collision avoidance handshake - most collision avoidance protocols (MACA, MACAW, 802.11, FAMA) are sender-initiated - another scheme: receiver-initiated with correct collision avoidance
Design issues - carrier sensing or not - polling dependent or independent of polling nodes data rate - polling to one, some, or all neighbors - polling with extra request for transmission, or not
Three schemes - RIMA-SP - RIMA-DP - RIMA-BP
Copyright 2002 Mani Srivastava
27
Multiple Access Collision Avoidance by Invitation (MACA-BI)
A
RTR (BA)
) RTR (DC A) DATA (B
RTR (DC)
DATA (BA )
C) DATA (D
Data Collision !
After sensing the channel, a polling node sends a RTR packet (Request To Receive) to one other node The polled node responds by sending a DATA packet
Copyright 2002 Mani Srivastava
28
Receiver Initiated Multiple Access with Simple Polling (RIMA-SP)
B
RTR (BA)
) RTR (DC
C
RTR (DC)
C) DATA (D
Polling and polled node sense the channel for a period after sending/receiving the RTR If a polled node senses the channel busy, it does not transmit the data
Copyright 2002 Mani Srivastava
29
Receiver Initiated Multiple Access with Simple Polling (RIMA-SP)
A B
RTR (BA)
) RTR (DC A) DATA (B
DATA (BA )
RTR (DC) NTR (DC)
Polling and polled node sense the channel for a period after sending/receiving the RTR If a polling node senses the channel busy, it sends a NTR packet Transmission Request) Collision avoidance if maximum transmission delay (No
Copyright 2002 Mani Srivastava
30
Receiver Initiated Multiple Access with Dual-Purpose Polling (RIMA-DP)
A B (has data)
RTR (BA)
A
RTR (BA)
CTS (AB)
B (has no data)
A) DATA (B
DATA (AB )
DATA (AB )
Dual purpose of RTR: request for data from polled node and transmission request of the polling node New control packet CTS: polled node has no data Collision avoidance conditions specify and CTS size
Copyright 2002 Mani Srivastava
31
Receiver Initiated Multiple Access with Broadcast Polling (RIMA-BP)
(only B has data) C
RTR (?A)
(B and C have data) B C
RTR (?A)
A
RTR (?A)
RTS (BA)
A
RTR (?A)
RTS (BA)
RTS (CA)
NTR (CA)
NTR (BA)
) DATA (BA
Broadcast polling New control packet RTS: to avoid users sending data at the same time Collision avoidance conditions specify
Copyright 2002 Mani Srivastava
32
Limitations of Random Access & Static Assignment
Static Assignment Dictatorship Model QoS Bandwidth allocation Connection Oriented Rigid guarantees Periodic & negotiated: - ask for what you need - pay for what you get - based on a contract Low Low High - no collisions Inefficient Poor Random Access Anarchy Connectionless No guarantees Statistical & shared: - grab as much as you want - live with what you get - based on courtesy High High Low - collisions under heavy load Efficient Good Fast Channel resources locked even if collision is destined What we want? Democracy Connectionless + virtual connections Flexible QoS Statistical, shared, negotiated, periodic
Delay Jitter Capacity Bursty traffic Support for variable b/w traffic
Low Low Low Efficient Good Fast Channel resources not locked needlessly 33
Response to changes in b/ Slow w requirements Key Problem Channel resources locked even if no traffic
Copyright 2002 Mani Srivastava
Approaches to Wireless Multiple Access
Sharing of Time-Frequency Space
Slotted-time vs. Non-slotted time
Static (Fixed) Assignment
e.g. Time-division & Frequency-division
Demand-based Assignment Contention-based Conflict-free Random Access
e.g. ALOHA, PRMA Carrier-sensing e.g. Token-passing & Polling
Connection Oriented Scheduled Access
e.g. DQRUMA
Next Topic
Copyright 2002 Mani Srivastava
Packet Oriented
Controlled Random Access
34
Controlled Random Access
Exercise more control over the access method than random access - avoid inefficiencies of uncontrolled access with collisions
... but, not the rigid control of fixed channel assignment - avoid inefficiencies of static resource allocation
Some approaches: 1. Token passing 2. Polling 3. Auctioning 4. Reservation-based with distributed control 5. Reservation-based with centralized control - scheduled access
Copyright 2002 Mani Srivastava
35
Polling Techniques
Controller periodically polls MHs to see if they have data to transmit - BS may be the controller - polling done according to a polling list
MH transmits if it has something to transmit, otherwise NACK (or no reply) Controller then polls the next MH in the list Constraints on efficient polling: - roundtrip delay must be small - overhead due to polling messages is low - user population is not large and bursty
Performance degrades as number of (bursty) users increases New MH needs to register to participate in polling But, centralized control provides robustness - even in presence of fading and dynamic channel characteristics Not widely used... but used in 802.11
36
Copyright 2002 Mani Srivastava
Point Coordination Function in 802.11
Time Bounded / Async
Contention Free Service (optional)
Async
Contention Service
PCF
DCF
(CSMA/CA)
PHY
802.11 Contention Free Service uses Point Coordination Function (PCF) on a CSMA/CA Distributed Coordination Function (DCF) foundation - PCF is optional - PCF can provide lower jitter to support Time Bounded Services - mix asynchronous data, voice etc. - PCF resides in AP
Contention free PCF co-exists with contention based DCF
37
Copyright 2002 Mani Srivastava
Contention Free Operation in 802.11
CFP repetition interval
contention free period
CFP repetition interval
Async traffic defer
PCF (optional)
DCF
contention period
CF-Burst
Reset NAV NAV
PCF defer
Alternating Contention Free and Contention operation under PCF control Net Allocation Vector (NAV) prevents Contention traffic until reset by last PCF transfer - so variable length Contention Free period per interval - NAV acts as virtual carrier sense, and distributed by RTS/CTS in DCF
Both PCF and DCF defer to each other causing PCF Burst start variations
38
Copyright 2002 Mani Srivastava
PCF Burst
CFP repetition interval contention free burst
PIFS PIFS PIFS PIFS PIFS
D1 U1
SIFS
D2 U2
SIFS
D3
No Up
D4 D4
SIFS CF_End
contention period Dx = BS Frame Ux = MH Frame
Reset NAV
min contention period
CF-burst by Polling bit in CF-Down frame Immediate response by MH on a CF_Poll MH maintain NAV to protect CF-traffic Responses can be variable length Reset NAV by last (CF_End) frame from BS (access point in 802.11) ACK Previous Frame bit in Header
39
Copyright 2002 Mani Srivastava
Scheduled Access: Centralized & Reservation-based
Also called Demand Assigned Multiple Access Central agent that acts as a slot scheduler Senders request reservations for future time slots - reservations done using random access such as ALOHA (conflict) - or, by piggy backing on data packets (conflict free)
Central agent assigns a slot - scheduling may be done slot-by-slot or on a frame basis - may also have permanently reserved TDMA-like slots
Data transmission in the assigned slot is done without contention Assumption is that data packets >> reservation request packets Overhead of reservation and acknowledgment messages Trades higher throughput (up to 80% utilization) for higher latency
Copyright 2002 Mani Srivastava
40
Generic Scheduled Access Schemes
request, allocation app n
MAC MAC PHY
admission control scheduling
app 2
MH2
app 1 app n
MAC PHY
PHY BS central coordinator
app 2
MH1
app 1
Design issues - service models and parameters - per flow (VC) vs. per-MH allocations (joint MAC & multiplexing?) - admission control policy (schedulability) - bandwidth allocation policy (scheduling) - peer to peer vs. MH-BS communication - request mechanism, frame structure
Much research on these protocols: QoS, wireless ATM, low power
41
Copyright 2002 Mani Srivastava
Ideal Multi Access Scheme
BS has perfect knowledge of all MHs with no overheads - BS always knows the status of every packet queue No random access for requests is needed - no access delay - only service delay
Optimum in: - energy efficiency no collision, transmitter & receivers wake up only when need be! - system throughput no needless idle time, no collision
But, ability to meet QoS (e.g. latency) depends on: - scheduling algorithm - and, schedulability analysis at admission control time
Alas, no perfect scheduled access scheme...
42
Copyright 2002 Mani Srivastava
IBMs Hybrid MAC (Natarajan 1992)
TA G AH A BS to MH
- broadcast
network id BS id next hop frequency time left in current hop list of receiving MHs TA, TB, & TC
TB BH B MH to BS
- contention-free - scheduled access
TC CH C MH to BS
- contention-based - slotted ALOHA - new MH registration requests - bandwidth reservation requests - singleton data packets - ACKs from BS
transmit schedule <MH, Slot>*
Features/constraints: - MSBH data flow - TA & TB adjusted on a frame-by-frame basis - but, TA+TB+TC is fixed TC has a lower bound TC_MIN = 20% - MH needs to register with a BS - two service types: isochronous (CBR) & non-isochronous (UBR) isochronous implies repeating every frame until cancelled - assumes a fixed bitpipe channel model (all slots are good) - no scheduling algorithm specified
Copyright 2002 Mani Srivastava
43
NECs Wireless ATM MAC (Xie 1995, Biswas 1996)
Copyright 2002 Mani Srivastava
44
NECs Wireless ATM MAC (contd.)
Multiservices dynamic TDM/TDMA protocol with QoS control Support for ABR - dynamic allocation CBR - fixed allocation VBR - fixed + shared allocation Slotted ALOHA for mobile to basestation control packets
Copyright 2002 Mani Srivastava
45
Bluetooth
Support both voice (synchronous connection oriented) and data (asynchonous connectionless) Use small and low-power radio transceiver in ISM band Frequency hop, time-division duplex with one packet per slot Channel shared by a master unit and multiple slave units - called Piconet - hop frequency selection based on master unit
Copyright 2002 Mani Srivastava
46
Frequency-hop / Time-division Duplex Channel
Copyright 2002 Mani Srivastava
47
Bluetooth Baseband
Packet may occupy 1, 3, or 5 slots Segmentation and reassembly to handle large data packets Link level fast unnumbered ARQ Link level FEC - header protected by 1/3 rate FEC - data optionally protected by 2/3 rate FEC
Two types of links - Synchronous Connection Oriented (SCO) for voice point-to-point, established by reservation of duplex slots at regular intervals - Asynchronous Connectionless (ACL) for packet data point-to-multipoint between master and all its slaves
Copyright 2002 Mani Srivastava
48
The Bluetooth Protocol Stack
Copyright 2002 Mani Srivastava
49
LMP and L2CAP
Link Manager Protocol (LMP) - manages connection state - enforces fairness among slaves - power management, and other management tasks
Logical Link Control & Adaptation Protocol (L2CAP) - higher level protocol multiplexing baseband doesnt support any type field identifying the higher layer protocol - packet segmentation and reassembly (SAR) - conveys QoS information - permits higher level protocols and applications to transmit and receive L2CAP data packets up to 64 kB in length
Copyright 2002 Mani Srivastava
50
MAC Scheduling
MAC scheduling because - multiple piconet slaves active - slave has multiple data connections
Scheduling approaches - simple master-driven round robin scheduling - Other scheduling, e.g. in [Das01] at Infocom 2001
Copyright 2002 Mani Srivastava
51
Does QoS-oriented MAC Make Sense?
Radio channel allocation and sharing is done under harsh conditions fading, noise, transmit power control, error control
Channel dynamics may make it hard to talk about QoS e.g. fading can be several 10s of ms at pedestrian speeds cant really talk about delay guarantees better than that e.g. what to do if a slot belonging to a constant bit rate stream is lost? retransmit? discard? e.g. what to do if total channel goodput is reduced due to interference? drop some users? renegotiate with everybody?
Question: is it meaningful to do reservation or scheduled access at fine time granularity in a wireless link? - might, therefore, a simpler random access MAC (which do give throughput and delay assurances in a long term average sense) work as well?
Copyright 2002 Mani Srivastava
52
Power Management in MAC: 802.11 Approach
Mobile nodes in power saving mode switch off their radios for some period - sender nodes meanwhile buffer the frames
Nodes are synchronized to wake up at the same time when the sender announces buffered frames - nodes with frames for them in the announcement stay up until frame is delivered - timing synchronization function (TSF)
Easy to do in PCF, but hard to do in DCF - centralized vs distributed buffering & TSF
Copyright 2002 Mani Srivastava
53
Power Management in the PCF Mode
TIM-Interval DTIM interval
Time-axis
TIM TIM Busy Medium DTIM Broadcast TIM TIM DTIM Broadcast
AP activity
PS Station
AP generates time-stamped beacons & transmits them every beacon interval (~100 ms) - beacon transmission is deferred if channel busy - nodes wake up before the end of beacon interval and stay up until beacon is received - nodes adjust their local timers to the timestamp Beacon carries a traffic-indication map (TIM) - all unicast packets for nodes in sleep mode at announced in the TIM - mobile nodes with entries in TIM request packets from AP Broadcast packets are announced by a delivery TIM (DTIM) and send immediately afterwards - DTIM interval is a multiple of TIM interval
Copyright 2002 Mani Srivastava 54
Power Management in the DCF Mode
Timers are adjusted in a distributed fashion - every node generates beacons - all nodes compete to transfer the beacon using DCF - the first node to transmit the beacon is the winner - other nodes cancel their beacons & adjust timers
Packets for sleeping nodes are buffered by the sender until the end of beacon interval - announced using ad hoc TIMs (ATIMs) sent via DCF transmitted in an ATIM window (~ 4 ms) after the beacon acked by the receiver receiver stays up and waits for the packet
Copyright 2002 Mani Srivastava
55
Power Saving in MAC via Directories or Schedules
Scheduling access via a schedule or a directory - 802.11s TIM is like a directory - this concept also used in pagers - also suggested in the literature for application level
Several TDMA-based MAC protocols around this idea - frame with directory or schedule carrying beacon in the first slot - mobile nodes wake up only in the right slots
Copyright 2002 Mani Srivastava
56
