Transcript Support for Real-Time Traffic in a SAHN

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
In a previous paper in WOCN 2005
We have explained the challenges
&
Provided a solution with respect to a SAHN
using IEEE 802.11e operating in EDCA mode
In this paper
Extend our previous work
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
Why? (Explaining next)
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
Why? (Explaining next)
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 (Usα) and for neighboring ρ (Usρ)
At each ρ measure U for itself (Usρ)
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?
Solution in previous work
At each α measure U for itself (Usα) and for neighboring ρ (Usρ)
At each ρ measure U for itself (Usρ)
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?
In this work
At each α measure U for itself (Usα) and for neighboring ρ (Usρ)
At each ρ measure U for itself (Usρ)
Solution (1/14)
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/14)
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/14)
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/14)
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/14)
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/14)
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/14)
Generalized form of the analytical model for Usα
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 (9/14)
Generalized form of the analytical model for Usρ (1/6)
F
E
G
H
I
J
A
B
C
D
T1
T2
T3
T4
K
Consider the session s between AD
s consists of a single data packet
Total 3 transactions on links AB, BC & CD during T1-T2, T2-T3 & T3-T4
respectively
E-K are passive participants of s
Solution (9/14)
Generalized form of the analytical model for Usρ (2/6)
F
E
G
H
A
B
T1
T2
I
C
T1-T2: UsE = UsF = UsG = UsH
J
D
K
= Us(b)
Solution (9/14)
Generalized form of the analytical model for Usρ (3/6)
F
E
G
A
H
I
B
C
T2
T3
J
D
T1-T2: UsE = UsF = UsG = UsH
T2-T3:
UsG = UsH = UsI
K
= Us(b)
= Us(b)
Solution (9/14)
Generalized form of the analytical model for Usρ (4/6)
F
E
G
A
H
B
I
J
C
D
T3
T4
K
T1-T2: UsE = UsF = UsG = UsH
T2-T3:
T3-T4:
UsG = UsH = UsI
UsH = UsI = UsJ = UsK
= Us(b)
= Us(b)
= Us(b)
Solution (9/14)
Generalized form of the analytical model for Usρ (5/6)
F
E
G
H
I
J
A
B
C
D
T1
T2
T3
T4
K
T1-T2: UsE = UsF = UsG = UsH
T2-T3:
= Us(b)
UsG = UsH = UsI
T3-T4:
T1-T4: UsE = 1 
Us(b)
UsI = 2  Us(b)
= Us(b)
UsH = UsI = UsJ = UsK
= Us(b)
UsF = 1  Us(b)
UsG = 2  Us(b)
UsJ = 1  Us(b)
UsK = 1  Us(b)
UsH = 3  Us(b)
Solution (9/14)
Generalized form of the analytical model for Usρ (7/8)
F
E
G
H
I
A
B
C
T1
T2
T3
T1-T4: UsE = 1 
Us(b)
UsI = 2  Us(b)
J
D
K
UsF = 1  Us(b)
UsG = 2  Us(b)
UsJ = 1  Us(b)
UsK = 1  Us(b)
UsH = 3  Us(b)
The relationship between UsG & Us(b) depends on the number of links
carrying the same packet for s
Similar relation holds for other passive participants too
Solution (9/14)
Generalized form of the analytical model for Usρ (8/8)
Therefore we can write
Usα/ρ= n  Us(b)
n = number of links an α/ρ hears carrying the same data packet for s
Solution (10/14)
What to measure?
Each active participant has to measure
Usα= n  Us(b)
Usρ= n  Us(b)
Each passive 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 (11/14)
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 (12/14)
Estimate n of Usα by an α, i.e. an α is estimating n for itself
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
Solution (13/14)
Estimate n of Usρ by an α, i.e. an α is estimating n for its passive neighbors
Let ρ be a passive participant of α
Initialize n to 0
Makes a list of all APs within 2-hop radius of ρ
The list  (α1, α 2….. α k) including α
For each α i  (α 1, α 2….. α k), add 1 to n if
ρ
RTS, DATA
αi
CTS, ACK
RTS, DATA
CTS, ACK
αi+1
(1)
α = α i & ρ is located as in Fig (1) &
the TX range of α iα i+1 (α i+1α i) reaches ρ
α = α i & ρ is a 2-hop neighbor as in Fig (2) &
the TX range of α i+1α i reaches ρ
αi
RTS, DATA
CTS, ACK
ρ
RTS, DATA
α = α i & ρ is a 1-hop neighbor as in Fig (3) &
the TX range of α i α i+1 reaches ρ
ρ
αi+1
CTS, ACK
(2)
αi
RTS, DATA
(3)
CTS, ACK
αi+1
Solution (14/14)
Estimate n of Usρ by a ρ, i.e. a ρ is estimating n for itself
Let ρ be a passive participant overhearing a SIREQ
Initialize n to 0
Makes a list of all APs within 2-hop radius of ρ
The list  (α1, α 2….. α k)
For each α i  (α 1, α 2….. α k), add 1 to n if
ρ
RTS, DATA
αi
CTS, ACK
RTS, DATA
CTS, ACK
αi+1
(1)
ρ is located as in Fig (1) &
the TX range of α iα i+1 (α i+1α i) reaches ρ
α i is a 2-hop neighbor of ρ as in Fig (2) &
the TX range of α i+1α i reaches ρ
αi
RTS, DATA
CTS, ACK
ρ
RTS, DATA
α i is a 1-hop neighbor as in Fig (3) &
the TX range of α i α i+1 reaches ρ
ρ
αi+1
CTS, ACK
(2)
αi
RTS, DATA
(3)
CTS, ACK
αi+1
Simulation Setup
For performance evaluation
30 nodes on a 1500 × 1500 square meters flat terrain
Each node had at most 6 neighbors
Each simulation run consisted of at most 12 sessions
Each session was offered a load of 1 Mbps
A new session was added every 2 sec
Simulation time for each test case was 50 sec
For simplicity all sessions were of the same AC
All established sessions were executed till the end of the simulation run
Path length of each route in each test case was fixed
Path lengths among various test cases varied between 2-6
The avg values of performance metrics were recorded at 1 sec interval
Simulation Result (1/5)
SAHN-MAC & 802.11e have been compared with respect to
End-to-end delay
Throughput
Delivery ratio
Delivery ratio is the percentage of data received successfully at the final
destination
With the given configurations both SAHN-MAC & 802.11e performed
similarly up to path length 3
Simulation Result (2/5)
Path length = 5
Not stable
Fairly stable
Simulation Result (3/5)
Path length = 5
Fairly stable
Not stable
Simulation Result (4/5)
Path length = 5
Fairly stable
Not stable
Simulation Result (5/5)
Summary of performance evaluation
Additions of new sessions increased network load
802.11e cannot stop the network from overloading since it does not
have any admission control mechanism
SAHN-MAC did not allow any session to initiate if the new session
could choke ongoing sessions
Thus SAHN-MAC maintains fairly stable network performance
compared to 802.11e
Conclusion
Extended initial SAHN-MAC by considering neighboring nodes in
bandwidth calculation
Simulation results show SAHN-MAC can support fairly deterministic
QoS which important for real-time traffic
At present we are extending SAHN-MAC for multiple frequency
channels & directional antennas
We would also like to build a scheduling scheme at the MAC layer to
handle different classes of traffic efficiently
Questions
Thank you