Transcript Challenges and a Solution to Support QoS for Real

Muhammad Mahmudul Islam
Ronald Pose
Carlo Kopp
School of Computer Science & Software Engineering
Monash University, Australia
Problem Statement
Supporting real-time traffic in multi-hop ad-hoc network (e.g. a SAHN)
with a contention based MAC protocol is a challenging task
We explain the challenges
&
Provide a solution with respect to a SAHN
using IEEE 802.11e operating in EDCA mode
SAHN: Suburban Ad-Hoc Network
EDCA: Enhanced Distributed Channel Access, an improved version of
DCF (Distributed Coordination Function) of legacy 802.11
SAHN-MAC: EDCA of 802.11e + Proposed protocol
Topics Covered
SAHN
Challenges
Solution
Simulation results
SAHN (Suburban Ad-Hoc Network)







Multi-hop ad-hoc network
Ideal for cooperative nodes, e.g. connecting houses and business
Topology is quasi-static
Uses wireless technology
Multi-hop QoS routing
Decentralized
Multi Mbps broadband
service
 No charges for
SAHN traffic
 Can run alongside
TCP/IP
 Conceived by Ronald Pose & Carlo Kopp in 1997
at Monash University, Australia
Simulation Setup
Default setup
Used GloMoSim (version 2.02)
Nodes are separated by at most 240 meters,
Nodes use same TX power with a TX range of 240 m
Use EDCA of IEEE 802.11e in the link layer
Physical layer uses OFDM with a
Physical layer operates at the TX rate of 54 Mbps
Session consists of UDP type CBR traffic
Routing is done with DSR
Challenges (1/9)
How to support QoS for real-time traffic?
Prevent network saturation
Challenges (2/9)
Effect of saturation in network performance (1/2)
A
B
C
D
E
For 512 bytes payload, max achievable throughput between AE  5.2 Mbps
Establish a 2.6 Mbps session between AE
Since below saturation
Achieved throughput = 2.6 Mbps
End-to-end delay = 0.9 ms
Challenges (3/9)
Effect of saturation in network performance (2/2)
100
End-to-end delay
5
Throughput
4
3
10
2
1
0.1
1
Unsaturated
Near
[2.6 + 1.0]
Saturation
[2.6 + 2.4]
Saturated
[2.6 + 2.7]
Over
Saturated
[2.6 + 4.1]
Throughput (Mbps)
End-to-end delay (ms)
1000
0
Initial Load Added Load
Throughput degraded by 35% (1.7 Mbps)
End-to-end delay increased by 550% (559 ms)
At over saturation
Challenges (4/9)
Prevent network saturation
How?
Prevent adding new sessions if they saturate the network
How?
Reserve bandwidth
Bandwidth reservation for multi-hop ad-hoc network with
contention based MAC protocol is not trivial
Challenges (5/9)
Throughput
Amount of data carried from one node to another in a given time period
Expressed in bps
Associated with the application layer
Bandwidth
Bandwidth and throughput are same at the application layer
For adding overheads of different layers
BW at the physical layer > Throughput
Bandwidth Consumed
Bandwidth Utilization (U) =
Total Bandwidth
 100 %
Challenges (6/9)
Effect of multiple hops on U
Establish a 3.4 Mbps session between end nodes
Each packet = 512 bytes
A
Adding
B
NW & MAC headers & RTS/CTS/ACK overheads
UA  18 % & UB  18 %
A
B
C
D
E
Challenges (7/9)
U of neighbors may be wasted
Establish a 3.4 Mbps session between AE, Each packet = 512 bytes
Passive Participant (ρ)
F
G
A
H
B
I
C
J
D
K
E
Active Participant (α)
Challenges (8/9)
Why we need to know U of passive participants?
Add another 3.4 Mbps
session GK
F
G
A
H
B
I
C
J
D
K
E
U of some of the nodes
exceed their working limits
E.g. UC has to be 
128.724%
(72.619 + 56.105)
Challenges (9/9)
Support QoS for real-time traffic
How?
Do not allow new session if it causes the network to get saturated
How?
Allocate BW before establishing a session
How?
Measure BW without choking ongoing sessions
How?
At each α measure U for itself and for neighboring ρ
At each ρ measure U for itself
Challenges (9/9)
Support QoS for real-time traffic
How?
Do not allow new session if it causes the network to get saturated
How?
Allocate BW before establishing a session
How?
Measure BW without choking ongoing sessions
How?
At each α measure U for itself and for neighboring ρ
At each ρ measure U for itself
Solution (1/10)
Basics of the analytical model
Step 1 starts at T1
A
B RTS C
Step 2
D
Step 3
A
B DATA C
B
C
B CTS C
D
Step 4 finishes at T2
D
A
B ACK C
A single transaction
Interference Zone T1-T2
A
A
D
D
Solution (2/10)
Base case (it consists of 2 nodes)
UsA  U of session s at node A
Us(b)  base case U of session s
UsA = Us (b) UsB = Us (b)
ACK
DATA
CTS
RTS
DATA
RTS
A
ACK
CTS
B
UsA= UsB = Us(b)
Solution (3/10)
Other case (3 nodes)
UsC = 2 x Us (b)
UsB = 2 x Us (b)
UsA = 2 x Us (b)
ACK
DATA
CTS
RTS
DATA
RTS
ACK
DATA
CTS
RTS
DATA
RTS
A
ACK
CTS
ACK
CTS
B
C
UsA= UsB = UsC = 2 x Us(b)
Solution (4/10)
Other case (4 nodes)
UsD = 2 x Us (b)
UsC = 3 x Us (b)
UsB = 3 x Us (b)
Us
A
=2x
RTS
ACK
DATA
CTS
RTS
DATA
RTS
ACK
DATA
CTS
RTS
DATA
RTS
A
ACK
DATA
CTS
RTS
DATA
Us (b)
ACK
CTS
ACK
CTS
ACK
CTS
B
C
D
UsA= UsD = 2 x Us(b)
UsB= UsC = 3 x Us(b)
Solution (5/10)
Other case (5 nodes)
UsE = 2 x Us (b)
UsD = 3 x Us (b)
UsC = 4 x Us (b)
UsB = 3 x Us (b)
Us
A
=2x
Us (b)
RTS
ACK
DATA
CTS
RTS
DATA
RTS
ACK
DATA
CTS
RTS
DATA
RTS
ACK
DATA
CTS
RTS
DATA
RTS
A
ACK
DATA
CTS
RTS
DATA
ACK
CTS
ACK
CTS
ACK
CTS
ACK
CTS
B
C
D
E
UsA= UsE = 2 x Us(b)
UsB= UsD = 3 x Us(b)
UsC = 4 x Us(b)
Solution (6/10)
Other case (6 nodes)
UsD = 4 x Us (b)
UsE = 3 x Us (b)
UsF = 2 x Us (b)
UsC = 4 x Us (b)
Us
B
=3x
ACK
DATA
CTS
RTS
RTS
ACK
DATA
CTS
RTS
DATA
RTS
A
ACK
DATA
CTS
RTS
RTS
DATA
ACK
DATA
CTS
RTS
RTS
DATA
UsA = 2 x Us (b)
RTS
DATA
Us (b)
ACK
DATA
CTS
RTS
DATA
ACK
CTS
ACK
CTS
ACK
CTS
ACK
CTS
ACK
CTS
B
C
D
E
F
UsA= UsF = 2 x Us(b)
UsB= UsE = 3 x Us(b)
UsC= UsD = 4 x Us(b)
Solution (7/10)
Generalized form of the analytical model
2 Nodes
UsA=
UsB
=
Us(b)
5 Nodes
UsA= UsE = 2 x Us(b)
UsB= UsD = 3 x Us(b)
UsC = 4 x Us(b)
3 Nodes
4 Nodes
UsA= UsB = UsC = 2 x Us(b)
UsA= UsD = 2 x Us(b)
UsB= UsC = 3 x Us(b)
6 Nodes
UsA= UsF = 2 x Us(b)
UsB= UsE = 3 x Us(b)
UsC= UsD = 4 x Us(b)
We can infer
Usα depends on the number of transactions α can hear transferring the same
data packet for s
Each transaction involves
a specific link that joins the TX and the RX active participants
Generalized form
Usα= n  Us(b)
n = number of links an α hears carrying the same data packet for s
Solution (8/10)
What to measure?
Each active participant has to measure
Usα= n  Us(b)
A session initialization request packet (SIREQ) is sent before a session starts
SIREQ contains
Throughput requirement
List of active participants in the route
Estimate
Us(b)  from Info_1
Estimate the value of n
……….Info_1
……….Info_2
………Trivial
………Explaining next
Solution (9/10)
Estimate the value of n
Let NH represent a neighbor of each node within 2–hop radius
Each node knows the following information about NH
(1) NH’s geographical location
(2) list of the NH’s neighbors and
NH’s neighbors’ geographical locations
(3) transmission ranges assigned to NH with its neighbors
Info_2 + Info_3
Algorithm
Estimate n
……….Info_3
Solution (10/10)
Algorithm to estimate n of Usα by an α
Let α be the active participant estimating the value of n
Initialize n to 0
Makes a list of all active participants (APs) within 2-hop radius.
The list  (α1, α 2….. α k) including α
For each α i  (α 1, α 2….. α k), add 1 to n if
α i = α
αi
α i is neighbor as in Fig (1)
RTS, DATA
CTS, ACK
α
(1)
α i is a 2-hop neighbor as in Fig (2) &
the TX range of α i+1 α i reaches α
αi
α i is a neighbor as in Fig (3) &
the TX range of α i α i+1 reaches α
α
RTS, DATA
CTS, ACK
αi+1
CTS, ACK
α
(2)
RTS, DATA
αi
(3)
RTS, DATA
CTS, ACK
αi+1
Simulation Result (1/3)
We have validated the correctness of the proposed bandwidth estimation
scheme using some simple test cases in 2 phases
Simulation Result (2/3)
Phase1
Each test case dealt with a single session
All nodes were arranged in a straight line
Each session was established between end nodes
Each node could be within the TX range of at most 2 other nodes
For various test cases
the number of nodes varied between 2-11
traffic load of varied between 45 Kbps - 8 Mbps
We have logged U of each node every 1 min & averaged them at the end
Result
SAHN-MAC estimated U at each active participant with  93% accuracy
Simulation Result (3/3)
Phase2
70 nodes placed in a 3000 m by 3000 m flat terrain
Each node had at most 6 neighbors
Each test case consisted of 20 sessions with same path length & AC but
with different src & dst pairs
Path length varied various test cases between 3-5
We have logged U of each node every 1 min & averaged them at the end
Result
SAHN-MAC estimated U at each active participant with  85% accuracy
Why SAHN-MAC is less accurate in Phase 2?
At present SAHN-MAC does not consider passive participants for
estimating utilization of each session
Conclusion
Discussed the challenges for supporting deterministic QoS for real-time
traffic in multi-hop ad-hoc networks
Provided a solution
We are extending SAHN-MAC to estimate Usρ and measure performance
We would like to
extend SAHN-MAC for multiple frequency channels & directional
antennas
build a scheduling scheme at the MAC layer to handle different
classes of traffic efficiently
Questions
Thank you