Opened 7 years ago

Last modified 15 months ago

#5159 new defect

Round robin on connection level (more unfairness)

Reported by: Flo Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay fairness needs-design
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

The function connection_bucket_round_robin() returns the respective read/ write limit for a single connection. It prevents a connection from taking over.

Nevertheless, the function depends on the current fill level of the token bucket, what results in unfairness among the connections. In order to illustrate this behavior, I plotted the return values of the function (y-axis) in ratio to the bucket fill level (x-axis) -- cf. roundrobin.pdf. I also simulated this property with five concurrent connections and the assumption that connections always read as much as they get granted -- cf. rrsimulation.pdf.

Indeed this is not a huge difference/ unfairness and I would hope that overall it is somewhat balanced. Although, I would suggest to implement the round robin with a constant return value.

Child Tickets

Attachments (4)

roundrobin.pdf (7.5 KB) - added by Flo 7 years ago.
connection_bucket_round_robin()
rrsimulation.pdf (6.8 KB) - added by Flo 7 years ago.
r/w limit of concurrent connections
rrsim-30kb-tor.pdf (6.7 KB) - added by Flo 6 years ago.
r/w limit of concurrent connections (30KB)
rrsim-30kb-const.pdf (6.4 KB) - added by Flo 6 years ago.
r/w limit of concurrent connections with constant return value (30KB)

Download all attachments as: .zip

Change History (10)

Changed 7 years ago by Flo

Attachment: roundrobin.pdf added

connection_bucket_round_robin()

Changed 7 years ago by Flo

Attachment: rrsimulation.pdf added

r/w limit of concurrent connections

comment:1 Changed 7 years ago by arma

What do your plots look like when there are 5 connections and you're running on a relay that is rate limited to 30KB/s? (and what would they look like if the round robin had a constant return value?)

Changed 6 years ago by Flo

Attachment: rrsim-30kb-tor.pdf added

r/w limit of concurrent connections (30KB)

Changed 6 years ago by Flo

Attachment: rrsim-30kb-const.pdf added

r/w limit of concurrent connections with constant return value (30KB)

comment:2 in reply to:  1 Changed 6 years ago by Flo

Replying to arma:

What do your plots look like when there are 5 connections and you're running on a relay that is rate limited to 30KB/s? (and what would they look like if the round robin had a constant return value?)

Sorry for my late response. I just missed yours.
I attached the requested simulations.

In case of the constant return value, the divergence in event 2 is the rest that is left in the bucket. But apart from that it is fair. I am just not sure what value to choose. In this case I used the num_bytes_low value.

comment:3 Changed 6 years ago by nickm

Milestone: Tor: unspecified

comment:4 Changed 6 years ago by nickm

Keywords: tor-relay added

comment:5 Changed 6 years ago by nickm

Component: Tor RelayTor

comment:6 Changed 15 months ago by nickm

Keywords: fairness needs-design added
Severity: Normal
Note: See TracTickets for help on using tickets.