Accuracy of Tor Bandwidth Estimation Study
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
Rob Jansen
and Aaron Johnson
U.S. Naval Research Laboratory
R
o
b
J
a
n
s
e
n
Center for High Assurance Computer Systems
U.S. Naval Research Laboratory
Passive and Active Measurement Conference 2021
Virtual Event
March 29
th
– 31
st
, 2021
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
2
U.S. Naval Research Laboratory
M
a
i
n
R
e
s
u
l
t
s
•
T
o
r
u
n
d
e
r
e
s
t
i
m
a
t
e
s
i
t
s
t
o
t
a
l
n
e
t
w
o
r
k
b
a
n
d
w
i
d
t
h
c
a
p
a
c
i
t
y
b
y
a
b
o
u
t
2
0
0
G
b
i
t
/
s
(
5
0
%
)
•
~20% of relays have > 50% variation in bandwidth estimates
•
W
e
d
i
s
c
o
v
e
r
e
d
s
i
g
n
i
f
i
c
a
n
t
e
r
r
o
r
i
n
b
a
n
d
w
i
d
t
h
c
a
p
a
c
i
t
y
e
s
t
i
m
a
t
i
o
n
,
w
i
t
h
l
a
r
g
e
r
e
r
r
o
r
f
o
r
:
•
High-capacity relays
•
Exit relays
•
Relays with lower uptimes
•
I
n
a
c
c
u
r
a
t
e
c
a
p
a
c
i
t
y
m
e
a
s
u
r
e
m
e
n
t
s
m
a
y
l
e
a
d
t
o
s
u
b
o
p
t
i
m
a
l
l
o
a
d
b
a
l
a
n
c
i
n
g
•
Affects performance for all Tor users
200 Gbit/s
(50%)
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
3
U.S. Naval Research Laboratory
M
a
i
n
C
o
n
t
r
i
b
u
t
i
o
n
s
•
A
n
a
l
y
s
i
s
o
f
p
a
s
s
i
v
e
r
e
l
a
y
m
e
a
s
u
r
e
m
e
n
t
s
•
Understand variation in capacity estimates from historical data
•
Variation indicates inaccurate estimation
•
A
c
t
i
v
e
s
p
e
e
d
t
e
s
t
e
x
p
e
r
i
m
e
n
t
t
o
m
e
a
s
u
r
e
r
e
l
a
y
s
•
Flood relays with traffic to drive up their observed bandwidth
•
Cause relays to learn their bandwidth limits and better estimate their capacity
•
Analyze change in bandwidth reports before/after speed test
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
4
U.S. Naval Research Laboratory
M
a
i
n
C
o
n
t
r
i
b
u
t
i
o
n
s
•
A
n
a
l
y
s
i
s
o
f
p
a
s
s
i
v
e
r
e
l
a
y
m
e
a
s
u
r
e
m
e
n
t
s
•
Understand variation in capacity estimates from historical data
•
Variation indicates inaccurate estimation
•
A
c
t
i
v
e
s
p
e
e
d
t
e
s
t
e
x
p
e
r
i
m
e
n
t
t
o
m
e
a
s
u
r
e
r
e
l
a
y
s
•
Flood relays with traffic to drive up their observed bandwidth
•
Cause relays to learn their bandwidth limits and better estimate their capacity
•
Analyze change in bandwidth reports before/after speed test
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
5
U.S. Naval Research Laboratory
D
e
f
i
n
i
t
i
o
n
s
a
n
d
P
r
o
b
l
e
m
•
F
o
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
(
i
.
e
.
,
t
h
e
t
r
u
e
c
a
p
a
c
i
t
y
)
•
The max sustainable rate at which a relay can forward traffic
•
This value is unknown, so relays must estimate it
•
O
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
•
The max throughput a relay has sustained for any 10 second period over last 5 days
•
This value is reported to Tor metrics every 18 hours
•
Load balancing weights are derived from observed bandwidth
•
P
r
o
b
l
e
m
:
o
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
!
=
f
o
r
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
•
Insufficient client traffic limits the observed bandwidth
•
Underutilized relay will never learn its true forwarding capacity
•
Weighting based on observed bandwidth will be inaccurate
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
6
U.S. Naval Research Laboratory
D
e
f
i
n
i
t
i
o
n
s
a
n
d
P
r
o
b
l
e
m
•
F
o
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
(
i
.
e
.
,
t
h
e
t
r
u
e
c
a
p
a
c
i
t
y
)
•
The max sustainable rate at which a relay can forward traffic
•
This value is unknown, so relays must estimate it
•
O
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
•
The max throughput a relay has sustained for any 10 second period over last 5 days
•
This value is reported to Tor metrics every 18 hours
•
Load balancing weights are derived from observed bandwidth
•
P
r
o
b
l
e
m
:
o
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
!
=
f
o
r
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
•
Insufficient client traffic limits the observed bandwidth
•
Underutilized relay will never learn its true forwarding capacity
•
Weighting based on observed bandwidth will be inaccurate
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
7
U.S. Naval Research Laboratory
D
e
f
i
n
i
t
i
o
n
s
a
n
d
P
r
o
b
l
e
m
•
F
o
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
(
i
.
e
.
,
t
h
e
t
r
u
e
c
a
p
a
c
i
t
y
)
•
The max sustainable rate at which a relay can forward traffic
•
This value is unknown, so relays must estimate it
•
O
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
•
The max throughput a relay has sustained for any 10 second period over last 5 days
•
This value is reported to Tor metrics every 18 hours
•
Load balancing weights are derived from observed bandwidth
•
P
r
o
b
l
e
m
:
o
b
s
e
r
v
e
d
b
a
n
d
w
i
d
t
h
!
=
f
o
r
w
a
r
d
i
n
g
c
a
p
a
c
i
t
y
•
Insufficient client traffic limits the observed bandwidth
•
Underutilized relay will never learn its true forwarding capacity
•
Weighting based on observed bandwidth will be inaccurate
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
8
U.S. Naval Research Laboratory
A
c
t
i
v
e
S
p
e
e
d
T
e
s
t
E
x
p
e
r
i
m
e
n
t
•
H
y
p
o
t
h
e
s
i
s
:
t
h
e
p
r
e
d
o
m
i
n
a
n
t
e
r
r
o
r
i
s
t
o
u
n
d
e
r
e
s
t
i
m
a
t
e
t
h
e
t
r
u
e
c
a
p
a
c
i
t
y
o
f
T
o
r
r
e
l
a
y
s
•
E
x
p
e
r
i
m
e
n
t
:
p
e
r
f
o
r
m
a
s
p
e
e
d
t
e
s
t
o
n
t
h
e
l
i
v
e
T
o
r
n
e
t
w
o
r
k
•
Actively attempt to send 1 Gbit/s of traffic through each relay
•
Extra traffic should increase relays’ observed bandwidth
•
New observed bandwidths should better reflect forwarding capacity of relay
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
9
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
E
x
p
e
r
i
m
e
n
t
Relay being tested
Experiment Machine (1 Gbit/s)
Return ‘echo’ cells
without decrypting
Send ‘echo’ cells
Forward encrypted cells like normal
10 TCP connections
10 TCP connections
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
10
10
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
R
e
s
u
l
t
s
Tor underestimates its total capacity by about 50%
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
11
11
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
R
e
s
u
l
t
s
The estimated capacity increased after our experiment for most relays
(some by a 10x or greater factor)
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
12
12
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
R
e
s
u
l
t
s
We discovered more capacity on higher-capacity relays
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
13
13
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
R
e
s
u
l
t
s
Load balancing weights changed significantly for many relays
(some by a 10x or greater factor)
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
14
14
U.S. Naval Research Laboratory
S
u
m
m
a
r
y
•
C
o
n
t
r
i
b
u
t
i
o
n
s
•
Historical measurements: ~20% of relays have >50% variation in bandwidth estimates
•
Active speed test experiment:
−
Tor underestimates total capacity by ~50%
−
Larger error associated with high-capacity, exit, and lower uptime relays
•
R
e
s
e
a
r
c
h
a
r
t
i
f
a
c
t
s
a
v
a
i
l
a
b
l
e
a
t
:
•
https://torbwest-pam2021.github.io
•
C
o
n
t
a
c
t
•
<rob.g.jansen@nrl.navy.mil>, robgjansen.com, @robgjansen
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
15
15
U.S. Naval Research Laboratory
A
n
a
l
y
s
i
s
o
f
H
i
s
t
o
r
i
c
a
l
B
a
n
d
w
i
d
t
h
D
a
t
a
•
U
s
e
r
e
l
a
t
i
v
e
s
t
a
n
d
a
r
d
d
e
v
i
a
t
i
o
n
t
o
u
n
d
e
r
s
t
a
n
d
v
a
r
i
a
t
i
o
n
•
A(r,w) = adv. bws for relay r during week w
•
RSD(A(r,w)) = stdev(A(r,w)) / mean(A(r,w))
•
W
e
f
i
n
d
s
i
g
n
i
f
i
c
a
n
t
v
a
r
i
a
t
i
o
n
i
n
r
e
l
a
y
s
’
b
a
n
d
w
i
d
t
h
s
•
the capacity estimates of 25% of relays
vary by 41% or more
•
the capacity estimates of 10% of relays
vary by 71% or more
•
some relays’ capacity estimates vary by
more than 200%
O
n
t
h
e
A
c
c
u
r
a
c
y
o
f
T
o
r
B
a
n
d
w
i
d
t
h
E
s
t
i
m
a
t
i
o
n
|
16
16
U.S. Naval Research Laboratory
S
p
e
e
d
T
e
s
t
R
e
s
u
l
t
s
We discovered more capacity on lower-uptime relays
Study by Rob Jansen and Aaron Johnson from the U.S. Naval Research Laboratory reveals that Tor underestimates its network bandwidth capacity, with significant errors in estimation for high-capacity relays, exit relays, and relays with lower uptimes. The findings emphasize the importance of accurate capacity measurements for optimal load balancing and performance enhancement for all Tor users.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On the Accuracy of Tor Bandwidth Estimation Rob Jansen and Aaron Johnson U.S. Naval Research Laboratory Passive and Active Measurement Conference 2021 Rob Jansen Center for High Assurance Computer Systems U.S. Naval Research Laboratory Virtual Event March 29th 31st , 2021
Main Results Tor underestimates its total network bandwidth capacity by about 200 Gbit/s (50%) ~20% of relays have > 50% variation in bandwidth estimates 200 Gbit/s (50%) We discovered significant error in bandwidth capacity estimation, with larger error for: High-capacity relays Exit relays Relays with lower uptimes Inaccurate capacity measurements may lead to suboptimal load balancing Affects performance for all Tor users U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 2
Main Contributions Analysis of passive relay measurements Understand variation in capacity estimates from historical data Variation indicates inaccurate estimation Active speed test experiment to measure relays Flood relays with traffic to drive up their observed bandwidth Cause relays to learn their bandwidth limits and better estimate their capacity Analyze change in bandwidth reports before/after speed test U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 3
Main Contributions Analysis of passive relay measurements Understand variation in capacity estimates from historical data Variation indicates inaccurate estimation Active speed test experiment to measure relays Flood relays with traffic to drive up their observed bandwidth Cause relays to learn their bandwidth limits and better estimate their capacity Analyze change in bandwidth reports before/after speed test U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 4
Definitions and Problem Fowarding capacity (i.e., the true capacity) The max sustainable rate at which a relay can forward traffic This value is unknown, so relays must estimate it Observed bandwidth The max throughput a relay has sustained for any 10 second period over last 5 days This value is reported to Tor metrics every 18 hours Load balancing weights are derived from observed bandwidth Problem: observed bandwidth != forwarding capacity Insufficient client traffic limits the observed bandwidth Underutilized relay will never learn its true forwarding capacity Weighting based on observed bandwidth will be inaccurate U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 5
Definitions and Problem Fowarding capacity (i.e., the true capacity) The max sustainable rate at which a relay can forward traffic This value is unknown, so relays must estimate it Observed bandwidth The max throughput a relay has sustained for any 10 second period over last 5 days This value is reported to Tor metrics every 18 hours Load balancing weights are derived from observed bandwidth Problem: observed bandwidth != forwarding capacity Insufficient client traffic limits the observed bandwidth Underutilized relay will never learn its true forwarding capacity Weighting based on observed bandwidth will be inaccurate U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 6
Definitions and Problem Fowarding capacity (i.e., the true capacity) The max sustainable rate at which a relay can forward traffic This value is unknown, so relays must estimate it Observed bandwidth The max throughput a relay has sustained for any 10 second period over last 5 days This value is reported to Tor metrics every 18 hours Load balancing weights are derived from observed bandwidth Problem: observed bandwidth != forwarding capacity Insufficient client traffic limits the observed bandwidth Underutilized relay will never learn its true forwarding capacity Weighting based on observed bandwidth will be inaccurate U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 7
Active Speed Test Experiment Hypothesis: the predominant error is to underestimate the true capacity of Tor relays Experiment: perform a speed test on the live Tor network Actively attempt to send 1 Gbit/s of traffic through each relay Extra traffic should increase relays observed bandwidth New observed bandwidths should better reflect forwarding capacity of relay U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 8
Speed Test Experiment Experiment Machine (1 Gbit/s) Return echo cells without decrypting Send echo cells 10 TCP connections 10 TCP connections Relay being tested Forward encrypted cells like normal U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 9
Speed Test Results Tor underestimates its total capacity by about 50% U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 10
Speed Test Results The estimated capacity increased after our experiment for most relays (some by a 10x or greater factor) U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 11
Speed Test Results We discovered more capacity on higher-capacity relays U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 12
Speed Test Results Load balancing weights changed significantly for many relays (some by a 10x or greater factor) U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 13
Summary Contributions Historical measurements: ~20% of relays have >50% variation in bandwidth estimates Active speed test experiment: Tor underestimates total capacity by ~50% Larger error associated with high-capacity, exit, and lower uptime relays Research artifacts available at: https://torbwest-pam2021.github.io Contact <rob.g.jansen@nrl.navy.mil>, robgjansen.com, @robgjansen U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 14
Analysis of Historical Bandwidth Data Use relative standard deviation to understand variation A(r,w) = adv. bws for relay r during week w RSD(A(r,w)) = stdev(A(r,w)) / mean(A(r,w)) We find significant variation in relays bandwidths the capacity estimates of 25% of relays vary by 41% or more the capacity estimates of 10% of relays vary by 71% or more some relays capacity estimates vary by more than 200% U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 15
Speed Test Results We discovered more capacity on lower-uptime relays U.S. Naval Research Laboratory On the Accuracy of Tor Bandwidth Estimation | 16
