Introduction
State of the Art
Methodology
Results
Conclusion
DCF modeling and optimization of long-distance
IEEE802.11n point-to-point links
Michael Rademacher
[email protected]
19. ITG Fachtagung Mobilkommunikation Osnabr¨
uck. May 21, 2014
Hochschule
Bonn-Rhein-Sieg
Introduction
State of the Art
Methodology
Results
Conclusion
Introduction
WiFi based Long Distance networks (WiLD)
Are used to overcome the digital divide in rural areas
Off-the-shelf IEEE802.11 hardware operating in the ISM-Band
Wireless Mesh Network (WMN), WiBACK
Our previous work on WiLDs
Make 802.11a suitable for long distance point-to-point links
Maximize the throughput by exploiting 802.11n
A lot of measurements on different links (distances)
Uni-directional traffic, maximum modulation (and frame-aggregation)
e.g. 200 Mbps: 802.11n, 10 km, 40 MHz, 2x2 MIMO, MCS 15
M. Rademacher
2
Introduction
State of the Art
Methodology
Results
Conclusion
Motivation
1
2
The 802.11 point-to-point performance depends on:
Environment
Traffic
MAC parameter
Distance
Protocol (e.g IP/UDP)
Slot time (σ)
MCS
Payload size
Contention Window (CW)
BER
Frame aggregation
Max. retransmission (R)
The MAC was designed by the IEEE compromising:
)
Numerous stations in a cell (AP)
Spatial restrictions of a few hundred meters
Optimization potential!
Mathematical modeling instead of countless measurements
M. Rademacher
3
Introduction
State of the Art
Methodology
Results
Conclusion
Background: Distributed Coordination Function (DCF)
0<CW<31
Back-off freeze: CW=12
0<CW<31
PPDU
CW=6
CW=18
slot
0<CW<31
ACK
CW=12
Back-off
freeze: CW=6
CW
SIFS
PPDU
CW= 6
DIFS
0<CW<31
0<CW<31
ACK
Timeout CW=22
PPDU
CW=6
slot
0<CW<31
Propagation
time
ACK
CW=9
CW
M. Rademacher
Back-off
freeze: CW=3
SIFS
CW= 3
DIFS
4
Introduction
State of the Art
Methodology
Results
Conclusion
State of the Art
802.11 MAC layer modeling has been well researched
Mainly based on two publication by Bianchi or Cali et. al
Numerous extensions have been published
Only a few publications deal with the topic of WiLD
Large WMN instead of point-to-point links
Simulations for validation and different assumptions (no BER)
A revised version of Binachis’ model was chosen as a base:
Based on conditional probability
Well studied by several researchers
Validated against simulations
M. Rademacher
5
Introduction
State of the Art
Methodology
Results
Conclusion
Methodology - 802.11 MAC modeling in a nutshell
Two important observations for saturated link conditions:
- The presence of a discrete time-scale (slot time σ)
- Only three different events can occur on the channel
1
2
3
Transmission successful: Ps and Ts
Collision: Pc and Tc
Idle: Pi and σ
1-3 Can be expressed with a constant transmission and collision probability!
Saturation throughput (S):
S[
Bit
Ps E [P]
]=
Time
Pi σ + Ps Ts + Pc Tc
M. Rademacher
Average access delay (D):
D=
N
S/E [P]
6
Introduction
State of the Art
Methodology
Results
Conclusion
Numerous extensions: integrated (#) or developed ( )
# Erroneous links (BER)
# Backoff-freezing and anomalous slots
# The current 802.11-2012 standard specifications
Long-distance point-to-point links
The 802.11n standard
Physical Layer extension (HT-MCS and MIMO)
A-MPDU MAC aggregation on erroneous links
Additional delay factors (System Delay)
Reordering Time
Buffer and Processing Times
Finite Buffering (Throughput decrease)
Peculiarities of Hardware and the Linux Soft-MAC
M. Rademacher
7
Introduction
State of the Art
Methodology
Results
Conclusion
Validation on real-world WiLD links
Outdoor router, modified Linux
Kernel
Developed measurement tools
Delay correction
Design of Experiments
≈ 5000 different measurements
Model deviation
1
mean: TDiff
mean: DDiff
median: TDiff
median: DDiff
Overall low deviations (≈ 0.02),...
0.1
... independent of the link distance.
Deviation slightly higher for
0.01
0.001
0
1
M. Rademacher
2
3
4
5
Distance [km]
6
7
8
- The delay
- High A-MPDU factors
8
Introduction
State of the Art
Methodology
Results
Conclusion
What to-do with the developed modeling approach:
1. Estimation
Influence of the distance
Influence of the payload size
Influence of the aggregation factor
Influence of the BER








on throughput and delay







2. Optimization of the 802.11 MAC parameters
Optimum CW and R to maximize throughput and minimize delay
M. Rademacher
9
Introduction
State of the Art
Methodology
Results
Conclusion
Estimation: 802.11a WiLD links
6 Mbps
24 Mbps
54 Mbps
10
24
8
18
6
12
4
6
2
0
0
10
20
30
Distance [km]
40
Delay [ms]
Throughput [Mbps]
30
0
50
Throughput (fixed) and delay (dotted) for 802.11a
20 MHz, 1450 Bytes, IP/UDP bi-directional saturation
M. Rademacher
10
Introduction
State of the Art
Methodology
Results
Conclusion
Estimation: 802.11n WiLD links
agg=−3
agg=0
18
agg=3
100
15
80
12
60
9
40
6
20
3
0
0
10
20
30
Distance [km]
40
Delay [ms]
Throughput [Mbps]
120
0
50
Throughput (fixed) and delay (dotted) for 802.11n
20 MHz, 1450 Bytes, MIMO, MCS 15, IP/UDP bi-directional saturation
A-MPDU=213+agg Bytes
M. Rademacher
11
Introduction
State of the Art
Methodology
Results
Conclusion
Optimization - A multi single-objective problem
Scalarization
Payload
MCS
Model
Throughput
f(T,D)=
Optimizer
maximize
Retry
Delay
Distance
CWmin
Retry + CWmin
50
0.4
1 / Delay [ms]
Delay [ms]
40
30
20
0.2
v
u
u
t
0.1
10
0
0
∀ CWmin and R
maximize
0.3
5
10
Throughput [Mbps]
M. Rademacher
15
0
0
5
10
Throughput [Mbps]
F
Di
Dmax
!2
+
Si
Smax
2


15
12
Introduction
State of the Art
Methodology
Results
Conclusion
Optimization - 802.11a
Distances (1-50 km)
Payload (50-1450 Byte)
Modulations (all)
6 Mbps
0.8
0.6
0.6
0.4
0.4
0.2
0.2
10
20
30
Distance [km]
CWmin=7
200
0.8
400
Payload [Byte]
Optimum CWmin [%]
CWmin=3
0.6
0.4
600
800
1000
0.2
1200
0
6
M. Rademacher
9
12
18
24
Modulation
36
1
54 Mbps
0.8
0
0
1
24 Mbps
48
54
1400
0
50
40
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
7
3
3
3
3
3
3
3
7
3
3
3
3
3
3
3
7
3
3
3
3
3
3
3
7
7
3
3
3
3
3
3
7
7
3
3
3
3
3
3
7
7
3
3
3
3
3
3
7
7
7
3
3
3
3
3
7
7
7
3
3
3
3
3
7
7
7
3
3
3
3
3
6
9
12 18 24 36 48 54
Modulation
13
Delay decrease
Parameter:
Throughput increase
1
Introduction
State of the Art
Methodology
Results
Conclusion
Optimization - 802.11n
15 31 31 15 15 15 15 15 31 15 15 15 15 15 15 15
10
15
Payload (50-1450 Byte)
15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
15 15 15 15 15 15
7
7
15 15 15 15
7
7
7
7
15 15 15 15 15
7
7
15 15 15
7
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
15 15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
15 15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
15 15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
15 15 15
7
7
7
7
7
15
7
7
7
7
7
7
7
15 15 15
7
7
7
7
7
15
7
7
7
7
7
7
7
15 15 15
7
7
7
7
7
15
7
7
7
7
7
7
7
15 15 15
20
MCS (0-15)
7
7
7
7
7
7
15
7
7
7
7
7
7
15 15
7
7
7
7
7
15
7
7
7
7
7
7
7
15
7
7
7
7
7
7
15
7
7
7
7
7
7
7
7
15
7
7
7
7
7
7
15
7
7
7
7
7
7
7
2
4
6
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
10
15
7
7
7
0
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
5
Distance [km]
A-MPDU factor
5
Distance [km]
Bandwidth (20/40 MHz)
15 31 31 31 31 15 15 15 31 31 31 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
Parameter:
15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
8 10 12 14
MCS
7
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
15 15 15 15 15 15 15
7
15 15 15 15
7
7
7
7
15 15 15 15 15 15
7
7
15 15 15 15
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15 15
7
7
7
15 15 15
7
7
7
7
7
15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
7
15 15 15
7
7
7
7
15 15
7
7
7
7
7
7
0
2
4
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
5
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
⇒ Less throughput gain
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
20
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
15 15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
7
15 15 15 15 15 15 15 15 15 15 15
7
7
7
7
0
2
4
6
8 10 12 14
MCS
(c) 32 KBytes
M. Rademacher
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
Distance [km]
Distance [km]
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
CWmin = 15 is the default
8 10 12 14
MCS
15 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15
6
(b) 16 KBytes
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
Higher variation of optimum
7
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
10
7
7
7
15 31 31 31 31 31 31 31 31 31 31 31 31 15 15 15
5
7
15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15
20
(a) 8 KBytes
Distance (1-20 km)
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
10
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
20
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
7
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
0
2
4
6
8 10 12 14
MCS
(d) 64 KBytes
14
Introduction
State of the Art
Methodology
Results
Conclusion
Conclusion and Contribution
A unified model for 802.11a/802.11n long-distance point-to-point links
Extension to the well-known DCF model by Bianchi
Extensive verification on real hardware
∃ An optimum value for CWmin and R
The range of this optimum values is less than expected beforehand
A QoS gain especially for 802.11a
Designer of WiLD can use this model to estimate and optimize the
links beforehand, thus enabling a more accurate network planning.
M. Rademacher
15
Introduction
State of the Art
Methodology
Results
Conclusion
Future work
Include loss in optimization function (important for TCP)
Shift up- and downlink capacities using MAC parameter
Machine Learning of the current traffic situation
Evaluate a new MAC layer for WiLD links
Frequency Division Multiplexing (FDD)
Token based approach
TVWS integration using off-the-shelf WiFi cards
Access technologies for WiLDs
M. Rademacher
16
References
Q&A
Thank your for your attention.
Are there any questions?
M. Rademacher
17
References
References I
[1]
Bianchi, G.
Performance analysis of the IEEE 802.11 distributed coordination function.
IEEE Journal on Selected Areas in Communications 18, 3 (1998), 535–547.
[2]
[3]
Bianchi, G., and Tinnirello, I.
Remarks on IEEE 802.11 dcf performance analysis.
Communications Letters, IEEE 9, 8 (2005), 765–767.
Bing, B.
Emerging Technologies in Wireless LANs - Theory, Design, and Deployment, 1. ed.
Cambridge University Press, Cambridge, 2008.
[4]
Cali, F., Conti, M., and Gregori, E.
IEEE 802.11 wireless lan: capacity analysis and protocol enhancement.
In Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (1998), pp. 142–149.
[5]
Foh, C. H., and Tantra, J.
Comments on ieee 802.11 saturation throughput analysis with freezing of backoff counters.
Communications Letters, IEEE 9, 2 (2005), 130–132.
[6]
Ieee standard for information technology - telecommunications and information exchange between systems - local and
metropolitan area networks - specific requirements - part 11: Wireless lan medium access control (mac) and physical layer
(phy) specifications.
IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999) (Dec 2007), 1–1076.
M. Rademacher
18
References
References II
[7]
Ieee standard for information technology-telecommunications and information exchange between systems local and
metropolitan area networks-specific requirements part 11: Wireless lan medium access control (mac) and physical layer
(phy) specifications.
[8]
Rademacher, M., Kretschmer, M., and Jonas, K.
Exploiting ieee802.11n mimo technology for cost-effective broadband back-hauling.
In Fifth International IEEE EAI Conference on e-Infrastructure and eServices for Developing Countries (Oct 2013).
[9]
S Salmer´
on-Ntutumu, J Sim´
o-Reigadas, R. P.
IEEE Std 802.11-2012 (Revision of IEEE Std 802.11-2007) (Feb 2012), 1–2793.
Comparison of mac protocols for 802.11-based long distance networks.
In Proceedings of the 1st Workshop Wireless For Development (Aug 2008).
[10] Simo-Reigadas, J., Martinez-Fernandez, A., Ramos-Lopez, J., and Seoane-Pascual, J.
Modeling and optimizing ieee 802.11 dcf for long-distance links.
IEEE Transactions on Mobile Computing 9, 6 (2010), 881–896.
[11] Ziouva, E., Antonakopoulos, T., Ziouva, E., and Antonakopoulos, T.
Reprint csma/ca performance under high traffic conditions: Throughput and delay analysis, Feb 2002.
M. Rademacher
19
References
Backup
M. Rademacher
20
References
Validation - Influence of different buffer-sizes 802.11n
60
30
100
24
80
18
60
12
40
6
20
40
MCS 7
Model
MCS 3
Model
30
20
0
0
20
40
60
Buffer size in KByte
80
10
0
0
100
(a) MCS 3
100
60
48
80
50
36
60
24
40
12
20
20
40
60
Buffer size in KByte
(c) MCS 7
M. Rademacher
80
0
100
Throughput [Mbps]
60
0
0
20
40
60
80
Buffer size [KByte]
100
(b) Without buffer modeling
Delay [Mbps]
Throughput [Mbps]
Throughput [Mbps]
Delay [Mbps]
Throughput [Mbps]
50
40
MCS 7
Model
MCS 3
Model
30
20
10
0
20
40
60
80
Buffer size [KByte]
100
(d) With buffer modeling
21
References
Estimation: Influence of the BER for 802.11n WiLD links
120
18
agg=0
agg=3
100
15
80
12
60
9
40
6
20
3
0 −8
10
−7
10
−6
10
BER
−5
10
Delay [ms]
Throughput [Mbps]
agg=−3
0
−4
10
Throughput (fixed) and delay (dotted) for 802.11a
20 MHz, 1450 Bytes, 5 km, MIMO, MCS 15
M. Rademacher
22
References
Validation - Influence of different buffer-sizes 802.11n
60
30
100
24
80
18
60
12
40
6
20
40
MCS 7
Model
MCS 3
Model
30
20
0
0
20
40
60
Buffer size in KByte
80
10
0
0
100
(a) MCS 3
100
60
48
80
50
36
60
24
40
12
20
20
40
60
Buffer size in KByte
(c) MCS 7
M. Rademacher
80
0
100
Throughput [Mbps]
60
0
0
20
40
60
80
Buffer size [KByte]
100
(b) Without buffer modeling
Delay [Mbps]
Throughput [Mbps]
Throughput [Mbps]
Delay [Mbps]
Throughput [Mbps]
50
40
MCS 7
Model
MCS 3
Model
30
20
10
0
20
40
60
80
Buffer size [KByte]
100
(d) With buffer modeling
23
References
Traffic Class seperation
1.2
CWmin=3
CWmin=7
CWmin=15
PPS ratio
1
0.8
PPSj
0.5(1 − τ )2δj
≈
PPSk
1 − 0.5(1 − τ )2δj
0.6
0.4
0.2
0
0
1
2
3
4
5
AIFS(BE)
Two different techniques can be applied to protect traffic classes:
CWmin differentiation
AIFS differentiation
Even small values for AIFS => high traffic class separation
Amount of separation depend on CWmin as well
M. Rademacher
24
References
Influence of the payload size 802.11a and 802.11n
6 Mbps
24 Mbps
54 Mbps
8
15
6
10
4
5
2
0
0
500
1000
Payload Size [Byte]
Delay [Mbps]
Throughput [Mbps]
20
0
1500
Influence of the Payload for 802.11a
M. Rademacher
25
References
Influence of the payload size 802.11a and 802.11n
agg=−3
agg=0
agg=3
18
100
15
80
12
60
9
40
6
20
3
0
0
500
1000
Payload [Byte]
Delay [ms]
Throughput [Mbps]
120
0
1500
Influence of the Payload for 802.11n A-MPDU aggregation 20MHz MCS 15
M. Rademacher
26
References
Influence of the errounous links 802.11a and 802.11n
20
6 Mbps
24 Mbps
54 Mbps
30
20
10
15
10
Delay [ms]
Throughput [Mbps]
25
15
5
5
0
0
0.2
0.4
0.6
0.8
0
1
PER
Influence of the PER for 802.11a
M. Rademacher
27
References
Influence of the errounous links 802.11a and 802.11n
120
18
agg=0
agg=3
100
15
80
12
60
9
40
6
20
3
0 −8
10
−7
10
−6
10
BER
−5
10
Delay [ms]
Throughput [Mbps]
agg=−3
0
−4
10
Influence of the BER for 802.11n A-MPDU aggregation 20MHz MCS 15
M. Rademacher
28

DATE SUBJECT SUB CODE DATE SUBJECT SUB CODE 07.06

ΕΙΣ ΜΝΗΜΗ ΝΙΚ. ΚΟΥΜΙΩΤΗ 2014

A pulsar wind nebula associated with PSR J2032+4127 as the