Transcript Link asymmetry - GIST Networked Computing Systems Laboratory

On Accurate and Asymmetry-aware Measurement of
Link Quality in Wireless Mesh Networks
Author : Kyun-Han Kim
Conference : MobiCom 06
2009. 5. 18
Presenter : Koh Choi
Networked Media Laboratory
Dept. of Information & Communications
Gwangju Institute of Science & Technology (GIST)
DEPT. OF INFO. & COMM., GIST
Introduction
Important thing of link-quality information
Availability of accurate link-quality information
To select the best relay nodes.
Application, such as video streaming and VoIP, need link-quality information
Diagnosing a network
Large scale WMN requires accurate long-term statistics of link-quality information
Proposed EAR(Efficient and Accurate link-quality monitoR)
Three complementary measurement schemes
Passive, Cooperative, and Active monitoring
Identify the existence of wireless link asymmetry
By measuring the quality of each link in both directions of the link
Cross-layer architecture across both the network layer and the IEEE 802.11based device driver
Makes EAR easily deployable in existing multi-hop wireless mesh networks
Main focus
Present a novel link-quality measurement framework
Show potential benefits of the framework
DEPT. OF INFO. & COMM., GIST
Limitation of related work(1/2)
BAP(Broadcast-based Active Probing)
Widely used for adopting link-quality-aware routing metrics
Such as ETX(Expected Transmission Count) and ETT(Expected Transmission Time)
Based on inexpensive broadcast
Easy to implement at all layers
Different PHY settings
Bidirectional measurements
A
B
LAB  S AB  S BA
BAP
A
Data
B
SBA=0.6
A
SAB=0.9
LAB = LBA = 0.54
Bidirectional measurement
DEPT. OF INFO. & COMM., GIST
B
ACK
LAB= 0.9
Real data transmission
Limitation of related work(2/2)
Unicast-based Active Probing
Same PHY settings as data transmissions
Unidirectional measurement(LAB≠ LBA)
Blind to underlying retransmission at MAC
Self-monitoring data frame transmission
Reduce probing overheads
Use unicast and unidirectional results
Require active probing for probing idle links
Blind to underlying retransmission at MAC
DEPT. OF INFO. & COMM., GIST
A
B
EAR Design and Operations(1/1)
Tegg ≥ Pthresh
MeasureMeasureTcrss ≥ Cthresh Cooperative
period (i)
Cycle (i)
Tcrss < Pthresh Tcrss ≥ Cthresh
UpdateActiveperiod (i)
Time
Tcrss ≤ Cthresh
DEPT. OF INFO. & COMM., GIST
Task
Processor
Techniques
Passive
Cooperative
Active
Routing-table
Manager
Link State
Table

Passive
Tegg < Pthresh
Task
Timers


Outgoing traffic
Incoming traffic
oEAR MAC
Tegg ≥ Pthresh

iEAR
 Distributed measurement
 Hybrid techniques
 Unicast-based results
 Cross-layer interaction
Management Information Base at MAC
 Data frame transmission results
Link quality of interest
 Link capacity: Data transmission rate
 Delivery ratio: d = NS/NT
5
Approach of EAR(1/2)
Efficient and Accurate link-quality monitoR
Exploits existing traffic by adaptive selection of passive, active or cooperative
measurement scheme
Uses unicast packets and derives unidirectional results
Distributed and periodic measurement
Independently measures the quality of link from a node to its neighbor in a fullydistributed way
Cross-layer interaction
Inner EAR : periodically collects and derives link-quality information in the network
layer
Outer EAR : monitors egress/cross traffic at the device driver
Mesh Router
Inner EAR or iEAR
IP
EAR
Device driver
MAC / PHY
DEPT. OF INFO. & COMM., GIST
Outer EAR or oEAR
Approach of EAR(2/2)
Tegg ≥ Pthresh
Passive
Tegg < Pthresh Tegg ≥ Pthresh
Tcrss ≥ Cthresh Cooperative
(A)
Tcrss < PthreshTcrss ≥ Cthresh
Tcrss ≤ Cthresh
Active
(B)
(C)
• Egress traffic(Tegg)
• Certain threshold(Pthresh)
• Actual traffic level(Cthresh)
Operation of EAR
Measuring node has enough egress traffic, EAR favors passive monitoring
Passive scheme : collect accurate and stable link-quality information from a large
volume of existing data traffic.
When measuring node has no egress traffic to a neighbor node, but has
cross-traffic, use cooperative scheme
This scheme use broadcast nature of wireless media.
Cooperative node(C) overhear the traffic from the measuring node (B) to the other
neighbors(A) – (cross traffic)
No egress/cross traffic, use active scheme
Send unicast probe packets to neighbor nodes.
DEPT. OF INFO. & COMM., GIST
Measurement techniques(1/3)
Passive scheme
A
B
C
 Monitoring at a device driver
 Interaction with MAC’s MIB
 Obtaining transmission results
Link-state table at B
Time
Links Scheme Ratio Data rate
BA Passive 0.9 11 Mbps
DEPT. OF INFO. & COMM., GIST
Measurement techniques(2/3)
Cooperative scheme
A
B
C
 Selective overhearing
 Overhearing cross traffic
 Reporting overhearing results
Link-state table at B
Time
Links Scheme Ratio Data rate
BA Passive 0.9 11 Mbps
BC
Coop
0.9 11 Mbps
DEPT. OF INFO. & COMM., GIST
Measurement techniques(3/3)
Active scheme
A
B
C
 Minimizing probe overheads
 Adaptive active probing timer (ET)
 Using a cooperation technique
Link-state table at B
Time
Links Scheme Ratio Data rate
BA
Active
0.9 11 Mbps
BC Active-Co 0.9 11 Mbps
ET=rand[0,W]
P
DEPT. OF INFO. & COMM., GIST
W=2
W=4
W=1
P
P
P
P
Cycle
10
Performance Evaluation(1/1)
Implementation
Linux kernel-2.4.20
N
W
ETX and ETT routing metrics
BAP for comparison
E
N4
S
N8
Corridor
Testbed
N10
N9
2nd floor of EECS Building
10 mesh nodes
N7
N5
N1
N2
IEEE 802.11b PCMCIA
Evaluation Metrics
Accuracy, asymmetry-awareness, and efficiency
DEPT. OF INFO. & COMM., GIST
Offices
N6
N3
Performance Evaluation(1/3)-Accuracy
 Comparison between BAP and EAR
▪ BAP: 10.2% error
▪ EAR: 1.6% error
SN1N2
N1
N2
LN1N2
EAR reduces measurement error from 4 to 20 times,
compared to BAP, and provides unidirectional results
DEPT. OF INFO. & COMM., GIST
Performance Evaluation(2/3)-Link asymmetry
 Link asymmetry is common
diff =| SF– SB |
duration
Wireless link-quality has different degrees of quality
asymmetry with different amounts of asymmetry duration
DEPT. OF INFO. & COMM., GIST
Performance Evaluation(3/3)-Efficiency
 Probing overheads
▪ Large number of neighboring
▪
▪
nodes in 200m x 200m
No egress/cross traffic
Thanks to cooperation and
exponential back-off timers
 Use of data traffic for measurements
13 times more
measurement
traffic than BAP
owing to hybrid
approach
DEPT. OF INFO. & COMM., GIST
14
Conclusion
EAR(Efficient and Accurate link-quality monitoR)
Solves problems of varying and asymmetric wireless link-quality in wireless mesh
network
A hybrid measurement framework
Efficiently and accurately measures wireless link quality
Useful for wireless network protocols
Routing, QoS support and networks diagnosis
Remaining Issues
Measurement of other QoS parameters(e.g, latency)
Extension for MANETs
What is link quality?
Why does not consider available bandwidth of link?
They only consider data transmission rate and delivery ratio.
It need available bandwidth and latency value.
DEPT. OF INFO. & COMM., GIST