Transcript Real-Time Compilation Technologies and Instruction Parallelism

Lecture 4
Wireless Medium Access Control
Prof. Shamik Sengupta
Office 4210 N
[email protected]
http://jjcweb.jjay.cuny.edu/ssengupta/
Fall 2010
Medium Access Control (MAC)
Base Station
Forward link
Reverse link
Mobile Station
Mobile Station
Mobile Station
Mobile Station
Earlier MAC Protocols: A quick overview

Channel Partitioning: TDMA, FDMA
– divide channel into “pieces” (time slots, frequency)
– allocate piece to node for exclusive use
A
B
f0
CB ACB ACB ACB A
C
Time

Channel Partitioning: adv., disadv.
– Share channel efficiently at
high load
– inefficient at low load: delay in
channel access, 1/N
bandwidth allocated even if
only 1 active node!
C
C
B
B
A
f2
A
f1
f0
Time
Earlier MAC Protocols: A quick overview

Packet Radio (PR) Access Technique:
– Users attempt to access a single channel in an uncoordinated or
random manner

Random Access: Aloha, Slotted Aloha
– allow collisions
– “recover” from collisions

Random access MAC protocols
– efficient at low load: single node can fully utilize channel
– high load: collision overhead
Pure (unslotted) ALOHA
 Devised by Norman Abramson and his colleagues
– University of Hawaii
 Simple, no synchronization
 when frame first arrives
– transmit immediately
 collision probability increases:
– frame sent at t0 collides with other frames sent in [t0-1,t0+1]
Pure Aloha efficiency
What is the efficiency?
Slotted ALOHA
Assumptions:
 all frames same size
 time divided into equal
size slots (time to
transmit 1 frame)
 nodes start to transmit
only slot beginning
 nodes are synchronized
 if 2 or more nodes
transmit in slot, all nodes
detect collision
Operation:
 when node obtains fresh
frame, transmits in next slot
– if no collision: node can
send new frame in next
slot
– if collision: node
retransmits frame in
each subsequent slot
with prob. p until
success
Slotted ALOHA
Pros
 single active node can
continuously transmit at
full rate of channel
 highly decentralized:
only slots in nodes
need to be in sync
 simple
Cons
 collisions, wasting slots
 idle slots
 nodes may be able to
detect collision in less
than time to transmit
packet
 clock synchronization
Slotted Aloha efficiency
Efficiency : 37%
At best: channel
used for useful
transmissions 37%
of time!
!
5: DataLink Layer
5-9
Why Aloha protocols were disadvantageous?
 Aloha protocols do not listen to the channel before
transmission
– Do not exploit info about other users
 Listening to the channel if any user is transmitting is
key to the efficient wireless access
– This was the basic of CSMA protocols
– Carrier Sense Multiple Access Protocol
Carrier Sense Multiple Access (CSMA) Protocol

Two imp parameters in CSMA
– Detection delay
– Propagation delay

Detection delay
– A function of the receiver hardware
– Time reqd for a terminal to sense whether or not the channel is idle

Propagation delay
– Relative measure of how fast a packet travels from one station to
another station (BS or AP)
– Systems must be built taking this parameter significantly in account
– High propagation delay impact efficiency
– E.g., two extreme transmitting users may get into collision again and
again due to high propagation delay
Variations of CSMA

1-persistent CSMA
– Listens to the channel, if idle transmit

p-persistent CSMA
– Listens to the channel, if idle, transmit with prob p in the first slot
or (1-p) in the next slot

CSMA/CD
– Further improvement over earlier CSMA
– Not only listens to channel before transmissions but also during
transmissions
– If collision is detected, transmissions are aborted immediately
– Saves valuable resources from wastage
– Combines “listen before talk” and “listen while talk”
– Happens in Ethernet (because of full-duplex radios)
CSMA in wireless

The concept of CSMA/CD is interesting
– How about applying it in wireless medium access control?

Problems in wireless networks
– signal strength decreases proportional to the square of the distance
– the sender would apply CS and CD, but the collisions happen at the
receiver
– a sender cannot “hear” the collision at the same time of
transmission, because transmission power suppresses receiving
power
– i.e., CD does not work
– furthermore, CS might not work if, e.g., a terminal is “hidden”

Wireless MAC use variants of CSMA
– CSMA/CA (collision avoidance protocol)
– Does not make collision zero, just tries to reduce it
– Very popular in IEEE 802.11 (WLAN)
IEEE802.11
infrastructure
network
AP
AP
ad-hoc network
wired network
AP: Access Point
AP
802.11 infrastructure mode
Station (STA)
802.11 LAN
802.x LAN
– terminal with access mechanisms
to the wireless medium and radio
contact to the access point
Basic Service Set (BSS)
STA1
BSS1
Portal
Access
Point
Distribution System
– station integrated into the wireless
LAN and the distribution system
– bridge to other (wired) networks
Distribution System
BSS2
STA2
Access Point
Portal
Access
Point
ESS
– group of stations using the same
radio frequency
802.11 LAN
STA3
– interconnection network to form
one logical network (ESS:
Extended Service Set) based
on several BSS
802.11: ad-hoc mode

802.11 LAN
STA1
STA3
BSS1
– Station (STA):
terminal with access
mechanisms to the wireless
medium
– Basic Service Set (BSS):
group of stations in range and
using the same radio
frequency
STA2
BSS2
STA5
STA4
Direct communication within a
limited range
802.11 LAN
IEEE standard 802.11
fixed terminal
mobile terminal
server
infrastructure network
access point
application
application
TCP
TCP
IP
IP
LLC
LLC
LLC
802.11 MAC
802.11 MAC 802.3 MAC
802.3 MAC
802.11 PHY
802.11 PHY 802.3 PHY
802.3 PHY
How does the medium access work in WLAN?
Contention
Based
Distributed Coordination Function (DCF)

Contention
Free
Point Coordination Function (PCF)
Access methods
– DCF CSMA/CA (mandatory)
– collision avoidance via exponential backoff
– Minimum distance (IFS) between consecutive packets
– ACK packet for acknowledgements (not for broadcasts)
– DCF with RTS/CTS (optional)
– Distributed Foundation Wireless MAC
– avoids hidden terminal problem
– PCF (optional)
– access point polls terminals according to a list
802.11 – MAC

Priorities
– defined through different inter frame spaces
– SIFS (Short Inter Frame Spacing)
– highest priority, for ACK, CTS, polling response
– PIFS (PCF IFS)
– medium priority, for time-bounded service using PCF
– DIFS (DCF, Distributed Coordination Function IFS)
– lowest priority, for asynchronous data service, competing stations
DIFS
DIFS
medium busy
PIFS
SIFS
direct access if
medium is free  DIFS
contention
next frame
t
WLAN CSMA/CA access method
DIFS
DIFS
medium busy
direct access if
medium is free  DIFS


t
slot time
starts sensing the medium (Carrier Sense)
If the medium is free for the duration of an Inter-Frame Space (IFS),
the station can start sending (IFS depends on service type)
If the medium is busy, the station has to wait for a free IFS, then the
station must additionally wait a random back-off time
–

next frame
Station ready to send
–

contention window
(randomized back-off
mechanism)
collision avoidance, multiple of slot-time
If another station occupies the medium during the back-off time of the
station, the back-off timer freezes
WLAN access scheme details

Sending unicast packets
– station has to wait for DIFS before sending data
– receivers acknowledge at once (after waiting for SIFS) if the packet was
received correctly (CRC)
– automatic retransmission of data packets in case of transmission errors
DIFS
sender
data
SIFS
receiver
ACK
DIFS
other
stations
waiting time
data
t
contention
Contention for channel

When the other stations find the channel idle, they would like
to transmit their own packets
– Contention for channel

If all the waiting stations attempt at once, this will surely result
in collision
– Some CA scheme is necessary
– Backoff intervals can be used to reduce collision probability
Backoff Interval

When transmitting a packet, choose a backoff interval in the
range [0,cw]
– cw is contention window

Count down the backoff interval when medium is idle
– Count-down is suspended if medium becomes busy

When backoff interval reaches 0, transmit packet
B1 = 25
B1 = 5
wait
data
data
B2 = 20
Assume cw = 31
wait
B2 = 15
B2 = 10
B1 and B2 are backoff intervals
at nodes 1 and 2
Backoff Interval

The time spent counting down backoff intervals is a part of
MAC overhead
– Choosing a large cw leads to large backoff intervals and can
result in larger overhead
– Choosing a small cw leads to a larger number of collisions (when
two nodes count down to 0 simultaneously)

Since the number of nodes attempting to transmit
simultaneously may change with time, some mechanism to
manage contention is needed
– IEEE 802.11 DCF: contention window cw is chosen dynamically
depending on collision occurrence
– Follows Binary exponential backoff algorithm
Binary Exponential Backoff (BEB) in DCF
 Even before the first collision, nodes follow BEB
 Initial backoff interval (before 1st collision)
– [0,7]
 If still packets collide, double the collision interval
– [0,15], [0,31] and so on…
 Express this binary exponential backoff interval as a
function of collision number
Numerical example #1
 Two nodes, A and C both waiting for a busy
channel to be idle so that they can proceed with
their first transmission. After the channel becomes
idle, what is the probability of A and C colliding in
their first transmissions?
Numerical example #2
 Two nodes, X and Y intend to transmit frames of 10
and 5 timeslots. Initially after waiting for DIFS, X
and Y both generate random backoff number, rX
and rY as 2. In the next stage, X generates rX =1
and Y generates rY =3. What will be the time (slots)
taken to complete both transmissions and receive
acks?
– Assume, SIFS=1 timeslot, DIFS=2 timeslots
Avoiding collisions (more)
idea: allow sender to “reserve” channel rather than random access of
data frames: avoid collisions of long data frames



sender first transmits small request-to-send (RTS) packets to BS
using CSMA
– RTSs may still collide with each other (but they’re short)
BS broadcasts clear-to-send CTS in response to RTS
CTS heard by all nodes
– sender transmits data frame
– other stations defer transmissions
avoid data frame collisions completely
using small reservation packets!
Collision Avoidance: RTS-CTS exchange
B
A
AP
reservation collision
DATA (A)
defer
time
802.11 access scheme details – RTS/CTS

Sending unicast packets
– station can send RTS with reservation parameter after waiting for DIFS
(reservation determines amount of time the data packet needs the medium)
– ack via CTS after SIFS by receiver (if ready to receive)
– sender can now send data at once, acknowledgement via ACK
– other stations store reservations distributed via RTS and CTS
DIFS
sender
RTS
data
SIFS
receiver
other
stations
CTS
SIFS
SIFS
NAV (RTS)
NAV (CTS)
defer access
ACK
DIFS
data
t
contention
802.11 Steps – RTS/CTS
 All backlogged nodes choose a random number, R
 Each node counts down R
– Continue carrier sensing while counting down
– Once carrier busy, freeze countdown
 Whoever reaches ZERO transmits RTS
– Neighbors freeze countdown, decode RTS
– RTS contains (CTS + DATA + ACK) duration = T_comm
– Neighbors set NAV = T_comm
– Remains silent for NAV time
31
802.11 Steps – RTS/CTS
 Receiver replies with CTS
– Also contains (DATA + ACK) duration.
– Neighbors update NAV again
 Tx sends DATA, Rx acknowledges with ACK
– After ACK, everyone initiates remaining countdown
– Tx chooses new R = rand (0, CW)
 If RTS or DATA collides (i.e., no CTS/ACK returns)
– Indicates collision
– RTS chooses new random no. following BEB
32
Numerical example #3
 Two nodes, X and Y intend to transmit frames of 10
and 5 timeslots. Initially after waiting for DIFS, X
and Y both generate random backoff number, rX
and rY as 2. In the next stage, X generates rX =1
and Y generates rY =3. What will be the time (slots)
taken to complete both transmissions and receive
acks?
– Assume, SIFS=1 timeslot, DIFS=2 timeslots
– RTS threshold = 8.
Another special access – with Fragmentation
DIFS
sender
RTS
frag1
SIFS
receiver
CTS
SIFS
frag2
SIFS
ACK1
SIFS
SIFS
ACK2
NAV (RTS)
NAV (CTS)
other
stations
NAV (frag1)
NAV (ACK1)
DIFS
contention
data
t
Point Coordination Function
t0 t1
medium busy PIFS
point
coordinator
wireless
stations
stations‘
NAV
SuperFrame
SIFS
D1
SIFS
SIFS
D2
SIFS
U1
U2
NAV
Point Coordination Function
t2
point
coordinator
wireless
stations
stations‘
NAV
D3
PIFS
SIFS
D4
t3
t4
CFend
SIFS
U4
NAV
contention free period
contention
period
t