Transcript Wireless LAN

Special Topics
on
Wireless Ad-hoc Networks
Lecture 12: Wireless 802.11
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Computer Network
1
Covered topic


How wireless LAN, 802.11 works
References







Chapter 3 of the book
“Wireless Medium Access control protocols” a survey
“MACAW: A Media Access Protocol for Wireless LAN’s”
SSCH: Slotted Seeded Channel Hopping for Capacity …
ECHOS: Enhanced Capacity 802.11 Hotspots
Idle Sense: An Optimal Access Method for High
Throughput and Fairness in Rate Diverse Wireless LANS
A wireless MAC protocol Using Implicit Pipelining
Univ. of Tehran
Computer Network
2
Outlines





Why wireless LAN
802.11
802.11 MAC
Some improvement
Performance Analysis.
Univ. of Tehran
Computer Network
3
Why wireless networks?




Mobility: to support mobile applications
Costs: reductions in infrastructure and
operating costs: no cabling or cable
replacement
Special situations: No cabling is possible
or it is very expensive.
Reduce downtime: Moisture or hazards
may cut connections.
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
4
Why wireless networks? (cont)



Rapidly growing market attests to public
need for mobility and uninterrupted
access
Consumers are used to the flexibility
and will demand instantaneous,
uninterrupted, fast access regardless of
the application.
Consumers and businesses are willing
to pay for it
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
5
The Two Hottest Trends in
Telecommunications Networks
700
600
Millions
Mobile Telephone
Users
500
400
Internet Users
300
200
100
0
1993 1994 1995 1996 1997 1998 1999 2000 2001
Year
Source: Ericsson Radio Systems, Inc.
Wireless Ad hoc/Sensor Networks
Growth of Home wireless
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
7
Why is it so popular?




Flexible
Low cost
Easy to deploy
Support mobility
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
8
Applications ?




Ubiquitous, Pervasive computing or nomadic
access.
Ad hoc networking: Where it is difficult or
impossible to set infrastructure.
LAN extensions: Robots or industrial
equipment communicate each others. Sensor
network where elements are two many and
they can not be wired!.
Sensor Networks: for monitoring, controlling,
e Univ. of Tehran
9
Wireless Ad hoc/Sensor Networks
What is special on wireless?

Channel characteristics




Resource limitation




Half-Duplex
Location dependency
Very noisy channel, fading effects, etc.,
Bandwidth
Frequency
Battery, power.
Wireless problems are usually optimization
problems.
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
10
What is special on wireless?






Mobility in the network elements
Very diverse applications/devices.
Connectivity and coverage (internetworking)
is a problem.
Maintaining quality of service over very
unreliable links
Security (privacy, authentication,...) is very
serious here. Broadcast media.
Cost efficiency
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
11
Big issues!


Integration with existing data networks
sounds very difficult.
It is not always possible to apply wired
networks design methods/principles here.
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
12
Problems



Host mobility is not considered in the initial
Internet design.
There is a hierarchal design in Internet. How
Ad hoc wireless networks can be handled
A layered design. Layer should be
independent of each other. It is not work at
all in wireless



TCP
Battery shortages;
Etc,.
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
13
High availbility requirements


No QoS assumed from below
Reasonable but non-zero loss rates

What’s minimum recovery time?


But conservative assumptions end-to-end


1 RTT
TCP RTO - min(1s)!
Interconnect independent networks

Federation makes things hard:


My network is good. Is yours? Is the one in the middle?
Scale

Routing convergence times, etc.
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
14
Growing Application Diversity
Collision Avoidance:
Car Networks
Mesh Networks
Wired Internet
Access
Point
Sensor
Relay Node
Ad-Hoc/Sensor
Univ. of Tehran
Networks
Wireless Home
Wireless Ad hoc/Sensor Networks Multimedia
15
Challenge: Diversity
Wireless
Edge
Network
INTERNET
INTERNET
Wireless
Edge
Network
2005


2010
New architectures must accommodate rapidly
evolving technology
Must accommodate different optimization goals

Power, coverage, capacity, price
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
16
Spectrum Scarcity

Interference and unpredictable behavior


Need better management/diagnosis tools
Lack of isolation between deployments

Cross-domain and cross-technology
Why is my
802.11 not
working?
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
17
Other Challenges



Performance: Nothing is really work well
Security: It is a broadcast media
Cross layer interception

TCP performance
Univ. of Tehran
Wireless Ad hoc/Sensor Networks
18
Ideal Wireless Area network?

Wish List






High speed (Efficiency)
Low cost
No use/minimal use of the mobile equipment
battery
Can work in the presence of other WLANs
(Heterogeneity)
Easy to install and use
Etc
Univ. of Tehran
Computer Network
19
Wireless LAN Design Goals

Wireless LAN Design Goals




Portable product: Different countries have
different regulations concerning RF band
usage.
Low power consumption
License free operation
Multiple networks should co-exist
Univ. of Tehran
Computer Network
20
Wireless LAN Design
Alternatives

Design Choices





Physical Layer: diffused Infrared (IR) or Radio
Frequency (RF)?
Radio Technology: Direct-Sequence or FrequencyHopping?
Which frequency range to use?
Which MAC protocol to use.
Peer-Peer architecture or Base-Station approach?
Univ. of Tehran
Computer Network
21
Wireless Standards
Univ. of Tehran
Computer Network
22
Distance vs. Data Rate
Univ. of Tehran
Computer Network
23
WiFi






Almost all wireless LANs now are IEEE 802.11
based
Competing technologies, e.g., HiperLAN can’t
compete on volume and cost
802.11 is also known as WiFi = “Wireless Fidelity”
Fidelity = Compatibility between wireless
equipment from different manufacturers
WiFi Alliance is a non-profit organization that does
the compatibility testing (WiFi.org)
Univ. of Tehran
Computer Network
24
Architectures


Distributed wireless Networks: also called
Ad-hoc networks
Centralized wireless Networks: also called
last hop networks. They are extension to
wired networks.
Univ. of Tehran
Computer Network
25
Centralized Wlan
Ad Hoc
Laptop
Server
Laptop
DS
Access Point
Access Point
Pager
PDA
Univ. of Tehran
Laptop
Computer Network
Laptop
26
IEEE 802.11 Topology




Independent basic service set (IBSS) networks (Ad-hoc)
Basic service set (BSS), associated node with an AP
Extended service set (ESS) BSS networks
Distribution system (DS) as an element that
interconnects BSSs within the ESS via APs.
Univ. of Tehran
Computer Network
27
Starting an IBSS




One station is configured to be “initiating
station,” and is given a service set ID (SSID);
Starter sends beacons;
Other stations in the IBSS will search the
medium for a service set with SSID that
matches their desired SSID and act on the
beacons and obtain the information needed
to communicate;
There can be more stations configured as
“starter.”
Univ. of Tehran
Computer Network
28
ESS topology

connectivity between multiple BSSs, They use a
common DS
Univ. of Tehran
Computer Network
29
Base-Station Approach
Advantages over Peer-Peer





No hidden terminal: base station hears all
mobile terminals, are relays their information
to ever mobile terminal in cell.
Higher transmission range
Easy expansion
Better approach to security
Problem?


Point of failure,
Feasibility?
Univ. of Tehran
Computer Network
30
802.11 Logical Architecture
•PLCP: Physical Layer Convergence Procedure
•PMD: Physical Medium Dependent
•MAC provides asynchronous, connectionless service
•Single MAC and one of multiple PHYs like DSSS, OFDM, IR
and FHSS.
Univ. of Tehran
Computer Network
31
802.11 MAC Frame Format
Bytes
32
Preamble
34~2346
6
MPDU
PLCP
header
MAC Header
Frame Duration Addr 1 Addr 2 Addr 3 Sequence Address 4 User
Control
Control
Data
Bytes 2
2
6
6
2
6
6
CRC
4
Encrypted to WEP
Bits 2
Protocol
Version
2
4
1
1
Type Sub type To From
DS DS
Univ. of Tehran
1
Last
Retry Power
Fragment
Mgt
Computer Network
EP RSVD
32
802.11 MAC Frame Format

Address Fields contains






Source address
Destination address
AP address
Transmitting station address
DS = Distribution System
User Data, up to 2304 bytes long
Univ. of Tehran
Computer Network
33
Special Frames: ACK, RTS,
CTS
bytes

Acknowledgement
2
2
6
Frame
Receiver
Duration
Control
Address
ACK
4
CRC
bytes

Request To SendRTS
2
2
6
6
Frame
Receiver Transmitter
Duration
Control
Address Address
bytes

Clear To Send
CTS
2
2
6
Frame
Receiver
Duration
Control
Address
4
CRC
4
CRC
802.11 Features




Power management: NICs to switch to
lower-power standby modes periodically
when not transmitting, reducing the drain
on the battery. Put to sleep, etc.
Bandwidth: To compress data
Security:
Addressing: destination address does not
always correspond to location.
Univ. of Tehran
Computer Network
35
Power Management



Battery life of mobile computers/PDAs are
very short. Need to save
The additional usage for wireless should
be minimal
Wireless stations have three states



Sleep
Awake
Transmit
Univ. of Tehran
Computer Network
36
Power Management, Cont…




AP knows the power management of each
node
AP buffers packets to the sleeping nodes
AP send Traffic Delivery Information Message
(TDIM) that contains the list of nodes that
will receive data in that frame, how much
data and when?
The node is awake only when it is sending
data, receiving data or listening to TDIM.
Univ. of Tehran
Computer Network
37
IEEE 802.11 LLC Layer


Provides three type of service for
exchanging data between (mobile) devices
connected to the same LAN
 Acknowledged connectionless
 Un-acknowledged connectionless, useful
for broadcasting or multicasting.
 Connection oriented
Higher layers expect error free transmission
Univ. of Tehran
Computer Network
38
Frame type and subtypes

Three type of frames





Management
Control
Asynchronous data
Each type has subtypes
Control



RTS
CTS
ACK
Univ. of Tehran
Computer Network
39
Frame type and subtypes,
Cont..

Management






Association request/ response
Re-association request/ response: transfer
from AP to another.
Probe request/ response
privacy request/ response: encrypting
content
Authentication: to establish identity
Beacon (Time stamp, beacon interval,
channels sync info, etc.)
Univ. of Tehran
Computer Network
40
Frame type and subtypes,
Cont..

Management…


TIM (Traffic Indication Map) indicates traffic
to a dozing node
dissociation
Univ. of Tehran
Computer Network
41
802.11 Management
Operations




Scanning
Association/Reassociation
Time synchronization
Power management
Univ. of Tehran
Computer Network
42
Scanning in 802.11


Goal: find networks in the area
Passive scanning



Not require transmission
Move to each channel, and listen for Beacon
frames
Active scanning


Require transmission
Move to each channel, and send Probe
Request frames to solicit Probe Responses
from a network
Univ. of Tehran
Computer Network
43
Time Synchronization in
802.11

Timing synchronization function (TSF)




AP controls timing in infrastructure networks
All stations maintain a local timer
TSF keeps timer from all stations in sync
Periodic Beacons convey timing



Beacons are sent at well known intervals
Timestamp from Beacons used to calibrate
local clocks
Local TSF timer mitigates loss of Beacons
Univ. of Tehran
Computer Network
44
Authentication

Three levels of authentication
 Open: AP does not challenge the identity of
the node.
 Password: upon association, the AP
demands a password from the node.
 Public Key: Each node has a public key.
Upon association, the AP sends an
encrypted message using the nodes public
key. The node needs to respond correctly
using it private key.
Univ. of Tehran
Computer Network
45
Inter Frame Spacing




SIFS = Short inter frame space =
dependent on PHY
PIFS = point coordination function (PCF)
inter frame space = SIFS + slot time
DIFS = distributed coordination function
(DCF) inter frame space = PIFS + slot time
The back-off timer is expressed in terms of
number of time slots.
Univ. of Tehran
Computer Network
46
802.11 Frame Priorities
Busy
DIFS
PIFS
SIFS
content
window
Frame transmission
Time

Short interframe space (SIFS)


PCF interframe space (PIFS)


For highest priority frames (e.g., RTS/CTS, ACK)
Used by PCF during contention free operation
DCF interframe space (DIFS)

Minimum medium idle time for contention-based
services
Univ. of Tehran
Computer Network
47
SIFS/DIFS
SIFS makes RTS/CTS/Data/ACK atomic
Example: Slot Time = 1, CW = 5, DIFS=3, PIFS=2,
SIFS=1,
Univ. of Tehran
Computer Network
48
Priorities in 802.11
CTS and ACK have priority over RTS
After channel becomes idle
 If a node wants to send CTS/ACK, it
transmits SIFS duration after channel goes
idle
 If a node wants to send RTS, it waits for
DIFS > SIFS

Univ. of Tehran
Computer Network
49
SIFS and DIFS
DATA1
ACK1
SIFS DIFS
Univ. of Tehran
backoff
RTS
SIFS
Computer Network
50
Energy Conservation


Since many mobile hosts are operated by
batteries, MAC protocols which conserve
energy are of interest
Two approaches to reduce energy
consumption


Power save: Turn off wireless interface when
desirable
Power control: Reduce transmit power
Univ. of Tehran
Computer Network
51
Power Control with 802.11

Transmit RTS/CTS/DATA/ACK at least
power level needed to communicate
with the receiver
A


B
C
D
A/B do not receive RTS/CTS from C/D.
Also do not sense D’s data transmission
B’s transmission to A at high power
interferes with reception of ACK at C
Univ. of Tehran
Computer Network
52
A Plausible Solution

RTS/CTS at highest power, and DATA/ACK at smallest
necessary power level
Data sensed
A
B
C
D
Data
Interference range



RTS
Ack
A cannot sense C’s data transmission, and may transmit DATA
to some other host
This DATA will interfere at C
This situation unlikely if DATA transmitted at highest power
level

Interference
range Network
Univ. of Tehran range ~ sensingComputer
53
02.11 Activities IEEE








802.11c: Bridge Operation (Completed. Added to IEEE 802.1D)
802.11d: Global Harmonization (PHYs for other countries.
Published as IEEE Std 802.11d-2001)
802.11e: Quality of Service. IEEE Std 802.11e-2005
802.11f: Inter-Access Point Protocol (Published as IEEE Std Std
802.11F-2003)
802.11h: Dynamic Frequency Selection and transmit power
control to satisfy 5GHz band operation in Europe. Published as IEEE Std
802.11h-2003
802.11i: MAC Enhancements for Enhanced Security. Published
as IEEE Std 802.11i-2004
802.11j: 4.9-5 GHz operation in Japan. IEEE Std 802.11j-2004
802.11k: Radio Resource Measurement interface to higher
layers. Active.
Univ. of Tehran
Computer Network
54
02.11 Activities IEEE










802.11m: Maintenance. Correct editorial and technical issues in
802.11a/b/d/g/h. Active.
802.11n: Enhancements for higher throughput (100+ Mbps).
Active.
802.11p: Inter-vehicle and vehicle-road side communication at
5.8GHz. Active.
802.11r: Fast Roaming. Started July 2003. Active.
802.11s: ESS Mesh Networks. Active.
802.11T: Wireless Performance Metrics. Active.
802.11u: Inter-working with External Networks. Active.
802.11v: Wireless Network Management enhancements for
interface to upper layers. Extension to 80211.k. Active.
Study Group ADS: Management frame security. Active
Standing Committee Wireless Next Generation WNG:
Globalization jointly w ETSI-BRAN and MMAC. Active.
Univ. of Tehran
Computer Network
55
802.11n








Trend: HDTV and flat screens are taking off Media Center
Extenders from Linksys and other vendors
Application: HDTV and streaming video (over longer
distances than permitted by 802.15.3 WPANs)
11n = Next Generation of 802.11
At least 100 Mbps at MAC user layer ⇒ 200+ Mbps at PHY ⇒
4x to 5x faster than 11a/g
(802.11a/g have 54 Mbps over the air and 25 Mbps to user)
Pre-11n products already available
Task Group n (TGn) setup: Sept 2003
Expected Completion: March 2007
v. of Tehran
Computer Network
56
802.11n




Uses multiple input multiple output antenna (MIMO)
Data rate and range are enhanced by using spatial
multiplexing (N antenna pairs) plus antenna
diversity occupies one WLAN channel, and in
compliance with 802.11
Backwards compatible with 802.11 a,b,g
One access point supports both standard WLAN and
MIMO devices
v. of Tehran
Computer Network
57
MAC: A Simple Classification
Wireless
MAC
Centralized
Distributed
On Demand MACs, Polling
Guaranteed
or
controlled
access
Random
access
Our focus
SDMA, FDMA, TDMA, Polling
Univ. of Tehran
Computer Network
58
Reservation/Polling MAC
Protocol






Works only with AP
Fair and slow. First-in-First-Out
Wireless station send a request.
All requests are queued.
Wireless stations are polled in the same
order that the requests have arrive.
All data reception is acknowledged.
Univ. of Tehran
Computer Network
59
IEEE 802.11 Wireless MAC

Distributed and centralized MAC
components




Distributed Coordination Function (DCF)
Point Coordination Function (PCF)
DCF suitable for multi-hop and ad hoc
networking
DCF is a Carrier Sense Multiple
Access/Collision Avoidance (CSMA/CA)
protocol
Univ. of Tehran
Computer Network
60
IEEE 802.11 DCF

Uses RTS-CTS exchange to avoid hidden terminal
problem



Any node overhearing a CTS cannot transmit for the
duration of the transfer
Uses ACK to achieve reliability
Any node receiving the RTS cannot transmit for the
duration of the transfer


To prevent collision with ACK when it arrives at the
sender
When B is sending data to C, node A will keep quite
A
Univ. of Tehran
B
Computer Network
C
61
Hidden Terminal Problem




Node B can communicate with A and C both
A and C cannot hear each other
When A transmits to B, C cannot detect the
transmission using the carrier sense
mechanism
If C transmits, collision will occur at node B
A
Univ. of Tehran
B
Computer Network
C
62
MACA Solution for Hidden
Terminal Problem




In order everybody to avoid send we need to
reserved the media.
Reservation can be done by handshaking first,
sending data and finally acknowledgement.
To be fair to others, reservation is done for one
packet delivery.
During reservation other nodes stay silent


To do this, sender includes during in handshaking and
others record it in their Network Allocation Vector (NAV)
Upon ending transmission, everybody can contend
to the media to send.
Univ. of Tehran
Computer Network
63
MACA Solution for Hidden
Terminal Problem [Karn90]


When node A wants to send a packet to node B,
node A first sends a Request-to-Send (RTS) to A
On receiving RTS, node A responds by sending
Clear-to-Send (CTS), provided node A is able to
receive the packet
A

B
C
When a node (such as C) overhears a CTS, it keeps
quiet for the duration of the transfer

Transfer duration is included in RTS and CTS both
Univ. of Tehran
Computer Network
64
IEEE 802.11
RTS = Request-to-Send
RTS
A
B
Univ. of Tehran
C
D
E
Computer Network
F
65
IEEE 802.11
RTS = Request-to-Send
RTS
A
B
C
D
E
F
NAV = 10
NAV = remaining duration to keep quiet
Univ. of Tehran
Computer Network
66
IEEE 802.11
CTS = Clear-to-Send
CTS
A
B
Univ. of Tehran
C
D
E
Computer Network
F
67
IEEE 802.11
•DATA packet follows CTS. Successful data reception
acknowledged using ACK.
CTS = Clear-to-Send
CTS
A
B
C
D
E
F
NAV = 8
Univ. of Tehran
Computer Network
68
IEEE 802.11
DATA
A
B
Univ. of Tehran
C
D
E
Computer Network
F
69
IEEE 802.11
Reserved area
ACK
A
Univ. of Tehran
B
C
D
Computer Network
E
F
70
IEEE 802.11
Carrier sense
range
Interference
range
DATA
A
B
C
D
E
F
Transmit range
Univ. of Tehran
Computer Network
71
Backoff Interval

To give everybody a chance, each node for
transmitting a packet, choose a backoff
interval in the range [0,cw]


Count down the backoff interval when
medium is idle


cw is contention window
Count-down is suspended if medium becomes
busy
When backoff interval reaches 0, transmit
RTS
Univ. of Tehran
Computer Network
72
DCF Example
B1 = 25
B1 = 5
wait
data
data
B2 = 20
cw = 31
Univ. of Tehran
wait
B2 = 15
B2 = 10
B1 and B2 are backoff intervals
at nodes 1 and 2
Computer Network
73
Backoff Interval





backoff intervals is a part of MAC overhead
large cw leads to large backoff and larger
overhead
small cw leads to a larger number of
collisions
A lot of work has been to reduce this
overhead but still no a solid sloution.
IEEE 802.11 DCF: contention window cw is
chosen dynamically depending on collision
74
Univ. of Tehran
Computer Network
occurrence
Binary Exponential Backoff in
DCF

When a node fails to receive CTS in
response to its RTS, it increases the
contention window


When a node successfully completes a data
transfer, it restores cw to Cwmin


cw is doubled (up to an upper bound)
cw follows a sawtooth curve
802.11 has large room for improvement
Random
backoff
Univ. of Tehran
RTS/CTS
Data Transmission/ACK
Computer Network
75
Inter Frame Spacing




SIFS = Short inter frame space =
dependent on PHY
PIFS = point coordination function (PCF)
inter frame space = SIFS + slot time
DIFS = distributed coordination function
(DCF) inter frame space = PIFS + slot time
The back-off timer is expressed in terms of
number of time slots.
Univ. of Tehran
Computer Network
76
Receive-Initiated Mechanism




In most protocols, sender initiates a transfer
Alternatively, a receiver may send a
Ready-To-Receive (RTR) message to a
sender requesting it to being a packet
transfer
Sender node on receiving the RTR transmits
data
How does a receiver determine when to poll
a sender with RTR?

Based on history, and prediction of traffic from
the sender
Univ. of Tehran
Computer Network
77
Reliability




Wireless links are prone to errors. High packet
loss rate detrimental to transport-layer
performance.
Mechanisms needed to reduce packet loss rate
experienced by upper layers
When node B receives a data packet from node
A, node B sends an Acknowledgement (Ack). This
approach adopted in many protocols
If node A fails to receive an Ack, it will retransmit
the packet
A
Univ. of Tehran
B
Computer Network
C
78
Fairness Issue


Assume that initially, A and B both choose a
backoff interval in range [0,31] but their RTSs
collide
Nodes A and B then choose from range [0,63]



Node A chooses 4 slots and B choose 60 slots
After A transmits a packet, it next chooses from range
[0,31]
It is possible that A may transmit several packets
before B transmits its first packet
A
B
Two flows
C
Univ. of Tehran
Computer Network
D
79
MACAW Solution for Fairness



When a node transmits a packet, it appends the cw
value to the packet, all nodes hearing that cw value
use it for their future transmission attempts
Since cw is an indication of the level of congestion
in the vicinity of a specific receiver node, MACAW
proposes maintaining cw independently for each
receiver
Using per-receiver cw is particularly useful in multihop environments, since congestion level at
different receivers can be very different
Univ. of Tehran
Computer Network
80
Wireless Capacity

Wireless channel is inefficient due to




MAC backoff procedure
RTS/CTS mechanism
Frequency interference.
Possible solutions:




Use better backoff mechanisms.
Exploit more physical resources: more spectrum
Cell mechanism
Exploit diversity, use different frequencies.
Parallel control with data
Univ. of Tehran
Computer Network
81
Improve Spatial Reuse
Power/Rate Control
A
B
A B
Univ. of Tehran
C
Transmit
Power
Spatial
Rate
reuse
High
High
Low
Low
D
C
Low
High
D
Computer Network
82
Exploit Infrastructure

Infrastructure provides a tunnel to
forward packets
infrastructure
BS1
BS2
B
C
A
D
E
Z
Ad hoc connectivity
Univ. of Tehran
X
Computer Network
83
Exploit Antennas


Diversity antenna
Steered beam directional antenna
A
A
B
B
C
C
D
D
Univ. of Tehran
Computer Network
84
Directional Antennas
Not possible
using Omni
D
B
S
C
A
85
Pipelining two stages
• Two stage pipeline:
1. Random backoff and RTS/CTS handshake
2. Data transmission and ACK
• “Total” pipelining: Resolve contention completely in
stage 1
Random
backoff
Stage1
Univ. of Tehran
RTS/CTS
Data Transmission/ACK
Stage2
Computer Network
86
Next solution


Partitioning channel dynamically in order
to better utilize it.
Different from direction antenna, it is done
on the link layer and dynamically.
Univ. of Tehran
Computer Network
87
SSCH: Slotted Seeded Channel
Hopping – Overview

A dynamic assignment algorithm


divides the time into equal sized slots (e.g. 10
ms) and switches each radio across multiple
orthogonal channels on the boundary of slots
in a distributed manner
Main aspect of SSCH

channel scheduling



self-computation of tentative schedule
communication of schedules
synchronization with other nodes
Univ. of Tehran
Computer Network
88
Channel Scheduling -Self-Computation




Each node use (channel, seed) pairs to represent its
tentative schedule for the next slot
Seed: [1 , number of channels -1] Initialized randomly
Focus on the simple case of using one pair
Update rule:
new channel = (old channel + seed)
mod (number of channels)
A: Seed = 2
1
0
2
1
0
2
1
0
B: Seed = 1
0
1
2
0
1
2
0
1
Example: 3 channels, 2 seeds
Univ. of Tehran
Computer Network
89
The ECHOS Solution 

AP – CST algorithm (CST- Carrier Sense Thersh.)


Dynamically adjusts the CST in order to allow more
flows to co-exist in the same channel in current
802.11 architectures.
RNC – SC algorithm




Allows each cell or AP access to all available channels.
RNC algorithm executes in a centralized radio network
controller
Uses one channel as primary & the other two as
secondary channels
Allows to improve Hotspot performance beyond APCST.
Univ. of Tehran
Computer Network
90
Abilities of the Algorithms


Dynamically allocate channels to stations
Flexibly adopts parameters such as CST and/or transmit
power
THE CLAIM !

Performance of 802.11-based hotspots can be improved by
both these algorithms by up to 195% per-cell and 70%
overall.
Univ. of Tehran
Computer Network
91
Observations on Carrier Sensing
in 802.11


Qualnet simulator
transmission at 2Mbps
with a CST of -93dBm
& transmit power of
15dBm
How to calculate
the ranges?
Univ. of Tehran
Computer Network
92
Range Calculation



Suppose T & T’ are two transmitters at distance dt & di from the
receiver.
T’ is the interferer to the transmission from T.
Then,

SNR at the receiver is
assuming that
both the transmitters transmit with the same power
Strength of the received signal falls off as
Where,
K is a suitable constant
is the transmission power
d is the distance from the signal source


For successful reception, the requirement is that the SNR be above
a threshold
This yields the requirement:
Range
Univ. of Tehran
Computer Network
93
Observation 1
How to chose the optimum value of CST ?
- Dynamic
Univ. of Tehran
Computer Network
94
Idle Sense Access Method
GOALS




Optimize Throughput
Dynamically Adapt to Physical Channel
Conditions
Equal Time Shares for hosts with
different bit rate
Short-term fairness and Minimize Delay
Channel Contention
--Idle Slot
(No
carrier)
--Idle
slots are
shorter
Two-host contention modeled as a stochastic process
with three states
Channel Contention
•Host have always packets to send
•Host can hear each others


Pe : Attempt p. for a slot per node
Pt : Successful Tx p. for a given
slot


Pc : Collision p. for a given slot
Pi : Slot Idle p.
__

ni :
No. of consecutive idle slots
between two trans/colission
Channel Contention
All host have the same CW and trans/col are like the wait
interval
Approximate Pe [5]
Throughput Function
Cost Function
Sd= ave. frame size,
[5]Bianchi,Fratta & Oliveri, ”Performance
Analysis of 802.11 CSMA/CA Medium Access
Control Protocol”, Proc of PIMRC1996
Channel Contention
# of stations
Cost function w.r.t Contention
window
(for different numbers of hosts)
Channel Contention
Replace values in cost function and put first derivative
to zero gives:
Optimal value of CW increases
with N
Cost function less sensitive to
variations in CW
Optimal values obtained by
limiting N to ∞
Channel Contention

Idle Sense:
If mean (ni) exceeds this optimal value:
-> too much time spent waiting in idle slots
If mean (ni) less than the optimal value:
->excessive collisions

N<∞: specific root of cost derivative
Principles of Idle Sense



Each host estimates ni and uses it to
compute its CW
If N is known, we can determine optimal
ni from predetermined optimal values
If N is not known, a best estimate is used
for nitarget
Principles of Idle Sense
Control Algorithm


AIMD : Additive Increase, Multiplicative
Decrease
Using Pe=2/CW
Performance Analysis
DIFS: distributed interframe space ( decide if it is idle)
SIFS: short interframe space ( shorter than DIFS)
NAV: Network Allocation Vector ( contains info about packet length being Tx)
SIFS
BO = 5
BO = 3
A
DIFS
RTS
DATA
CTS
B
DIFS
BUSY DIFS
4/7/2017
RTS
DIFS
collision
ACK
BO = 8
C
BO = 7
BO = 4
BO = 5
NAV (RTS)
NAV(CTS)
DIFS
RTS
EECS557 course project
DIFS
104
CRITICAL ASSUMPTIONS




Ideal Channel conditions and finite number of
terminals
Ideal Channel conditions include (No Hidden
Terminals, No Channel Capture)
Constant & independent collision probability P
for each transmitted packet
System is in Overload Condition (Every station
is always ready to Transmit a Packet)
4/7/2017
EECS557 course project
105
Mathematical Model for Dynamics of DCF





s(t) – stochastic process representing back off stage (0, …. , m) of a given station
b(t) – stochastic process representing back off time counter (k, k-1,……,1,0) of a station
Bi-dimensional Process {s(t), b(t)} with state space (i, k) i  (0,..... m), k  (0,W i  1)
and W = CWmin (minimum contention window length)
Wi  2 i W
p – Conditional Collision Probability seen by a packet being transmitted (const and indep)
-1
-2
-3
-4
Transition Probabilites P for process {s(t),b(t)}
Eq 1 – Once Back off Counting Starts, Counting has to decrement with Probability 1
Eq 2 – Counter hits zero at t, Tx is a success, s(t+1) = 0, b(t+1) = k (uniform distribution in
0)
 Eq 3 – Counter hits zero at t, Tx is a collision, s(t+1) = i, b(t+1) = k (uniform distribution in
i)p  1  (1   ) (n1)
 Eq 4 – Counter is zero at t, Tx is a collision but s(t) = m, s(t+1) = m, b(t+1) = k, no new
CW

t – Probability that station transmits a packet (remember SLOTTED ALOHA)

n – number of stations
, p
What can we do now ?


4/7/2017

STATE TRANSITION DIAGRAM OF THE CHAIN BASED ON ABOVE TRANSITION MATRIX
EECS557
course
project
106
 STEADY STATE
ANALYSIS
OF THE
CHAIN TO FIND SOLUTION TO
State Transition Diagram for the Chain
S
C
• USE Global Balance Equations and Sum of Probability Distributions of all states=1 to solve for b0, 0
4/7/2017
EECS557 course project
107
Throughput Analysis Based on Model
• S := Fraction of Time channel is used to successfully transmit payload bits
• As an outside observer, see a random slot and observe what is happening
• Probability, Exactly 1 TX Occurring on the channel is successful given someone transmits
• Hybrid Scheme also possible.
• Packet Length may vary and throughput may relate itself to packet size distribution mean
• Ts, Tc, s,P are constant for model verification constant, and determined by standard
• Maximizing throughput over probabilities which are in terms of t, we get S is max when
• Remember Slotted Aloha Stabilization ?
• tdepends on m and W and can be changed adaptively
• But m and W fixed because of Physical Layer Standard
• Result – S can be significantly lower than maximum
4/7/2017
EECS557 course project
108
IMPORTANT RESULTS
For Sufficiently Large n, Smax is practically independent of no. of stations in
wireless network
•
• Maximum throughput achievable by BAS is very close to RTS/CTS
mechanism
• RTS/CTS scheme throughput is less insensitive to transmission probability t
• RTS/CTS scheme is network size independent for W <= 64 values. Basic
Mechanism throughput increases but significantly decreases with network size
• Key to these results – RTS/CTS mechanism reduces the time spent during a
collision, and it becomes more effective than Basic Access when W and n
increases the collision probability
• RTS/CTS even more effective when packet length are longer
• SEE PERFORMANCE EVALUATION NEXT
4/7/2017
EECS557 course project
109
PERFORMANCE EVALUATION

Performance is based on following Parameters





Network size n
Transmission probability t
Initial contention window size CWmin
Maximum Backoff stage m
Packet size
4/7/2017
EECS557 course project
110
Performance Evaluation: Network Size


Basic access strongly depends on it
n Throughput (except W = 128)
RTS/CTS not depends on it much
4/7/2017
EECS557 course project
111
Performance evaluation: transmission probability
Both decrease dramatically when n is large, but the basic access is
more sententive
4/7/2017 Basic
access
EECS557 course project
RTS/CTS
112
Performance evaluation: CWmin
•Basic Access: increases when station CWmin gets closer to
64, decreases as n increases
•RTS/CTS is almost independent on CWmin and n when
CWmin<64
4/7/2017 Basic
access
EECS557 course project
RTS/CTS
113
Performance Evaluation: Maximum Backoff stage
Almost no effect when m > 5
4/7/2017
EECS557 course project
114
Performance Evaluation: Packet Size
RTS/CTS is effective when packet size increases
4/7/2017
EECS557 course project
115
CONCLUSION
Giuseppe Bianchi, “ Performance Analysis of the IEEE 802.11 Distributed Coordination Function”, IEEE
Journal on
selected areas in Communications, Vol. 18, No. 3, March 2000


Contributions of the referenced Paper

Proposed analytical model
 Accurate: verified by comparison with simulations
 Simple
 Account for all exponential backoff details
 Evaluate basic and RTS/CTS access schemes

Performance evaluation on saturation throughput
Other Remarks

Model lacks in considering non-ideal channel conditions (like hidden
terminals, interfering stations, or multiple access points)

It can be extended towards study of throughput for different classes of
customer with different access priorities

Only considers saturation throughput
(overload
4/7/2017
EECS557 course
project conditions)
116