Opened 9 years ago

Closed 9 years ago

Last modified 7 years ago

#2210 closed defect (fixed)

Stream starvation due to activation order in circuit_resume_edge_reading_helper()

Reported by: nickm Owned by: nickm
Priority: Medium Milestone: Tor: 0.2.2.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: fairness tor-relay
Cc: iang Actual Points:
Parent ID: #1298 Points:
Reviewer: Sponsor:

Description

On or-dev on 22 Nov 2010, Ian Goldberg wrote:

===
A number of groups (the UW people, the UCSD people, Roger(?) and
possibly others) have noticed that when many active streams (more than
about 4) are opened on a single circuit, 3 or 4 of them get service and
the rest starve until those are finished. Note that, for example, most
web browsers will open multiple streams at once to fetch parts of web
pages.

Here's a plot of 9 active streams on one circuit:

https://thunk.cs.uwaterloo.ca/mashael/broken.png

(This graph was from measurements on a private Tor network on
PlanetLab. This was from 0.2.3.0-alpha-dev, but the same behaviour was
observed previously on 0.2.2.*.)

Here's Mashael's writeup about the problem.

Our network consists of five nodes. An authoritative directory, a client
(also running as Onion Proxy), 3 Tor Onion Routers and a server. We
refer to the three onion routers as Entry, Middle and Exit. Our client
constructs a circuit through the network, where the first hop is Entry,
the second is Middle and the third is Exit. The constructed circuit is
used to create multiple streams to the server. Each stream basically
carries a request from the client to the server, which replies with
10,000 cells. We repeated this experiment for 2, 5, 9 and 13 streams.
The common result is that the last three client streams created "almost"
starved the other earlier streams until they fully completed
transferring their 10,000 cells.

This problem only occurs when we have a bottleneck OR in the path. We
continue to see the problem as long as the bandwidth offered by the
bottleneck router is less than approximately 80% of the bandwidth that
is offered by the other routers in the circuit. For example, if the
bandwidthrate of Entry and Exit is 630 KB/s and 720 KB/s, respectively,
the problem is still visible even when the bandwidthrate of Middle is up
to 550 KB/s. We verified that by setting the bandwidthrate command for
the Middle to a minimum value (20 KB/s) and then gradually increasing it
until the starvation of streams disappears from the resulting graphs at
approximately 600 KB/s.

The reason the "streams problem" occurs is due to the complicated
interaction between Tor's congestion control and libevent. At some point
during the experiment, the circuit window is exhausted, which blocks all
edge streams. When a circuit level sendme is received at Exit, it
resumes edge reading by looping over linked list of edge streams, and
calling connection_start_reading() to inform libevent to resume reading.
When the streams are activated again, Tor gets the chance to service the
first three streams activated before the circuit window is exhausted
again, which causes all streams to be blocked again. As an experiment,
we reversed the order in which the streams are activated, and indeed the
first three streams, rather than the last three, got service, while the
others starved.

Our solution is to change the order in which streams are activated. We
choose a random edge connection from the linked list, and then we
activate streams starting from that chosen stream. When we reach the end
of the list, then we continue from the head of the list until our chosen
stream (treating the linked list as a circular linked list). It would
probably be better to actually remember which streams have received
service recently, but this way is simple and effective.

Here's the graph again, with the patched Exit:

https://thunk.cs.uwaterloo.ca/mashael/fixed.png

The patch is attached.
===

Child Tickets

Attachments (1)

mashael_stream_fix.diff (2.4 KB) - added by nickm 9 years ago.

Download all attachments as: .zip

Change History (14)

Changed 9 years ago by nickm

Attachment: mashael_stream_fix.diff added

comment:1 Changed 9 years ago by nickm

Cc: iang added
Status: newneeds_review

comment:2 Changed 9 years ago by nickm

Looks okay to me. I say this should go into 0.2.2.x, with possible backport to 0.2.1.x as a followup to #1653.

comment:3 Changed 9 years ago by nickm

Initial review:

  • Windows doesn't have random(); you need to use rand() there instead
  • The "choose a random element" algorithm is a little nontrivial. We already loop through all the streams earlier in the function, I think; we could accumulate a num_streams there, and just do a "first_stream_idx = random() % num_streams;"
  • Having an n_streams and a num_streams in the same function is confusing.
  • Duplicating the code in the two versions of the loop is a little iffy. It might be better to lift it into a function or something. Duplicated code is prone to get out-of-sync.

This is all stuff we could fix up trivially, and we shouldn't block waiting for a revised patch, unless Ian or Mashael really wants to do one.

comment:4 Changed 9 years ago by cypherpunks

Why need OS-depends random() func if app has native crypto_rand_int()? What version of libevent used for test?

comment:5 Changed 9 years ago by iang

We used random() because we didn't want to drain cryptographic entropy for this, since it's not necessary.

We appear to be using libevent 1.3b.

nickm, you have the conch, but I think picking a random index isn't as nice, since you'll then have to iterate through the list to find the ith item anyway. If you're already iterating through the list earlier, perhaps put the "select a random list item" code in that loop?

I totally agree on the duplicated code, and on the n_streams / num_streams.

comment:6 Changed 9 years ago by nickm

For your tests, you should REALLY REALLY REALLY upgrade to libevent 1.4.12-stable or later: it has this bugfix:

o Activate fd events in a pseudorandom order with O(N) backends, so that we don't systematically favor low fds (select) or earlier-added fds (poll, win32).

On some systems, it won't matter; on some it will. But using old libevents *WILL* affect your performance numbers in other ways too.

(I'll try doing an updated branch rsn; I'm trying to avoid doing too much computer stuff over thanksgiving)

comment:7 Changed 9 years ago by nickm

Okay, the patch plus minor revisions against 0.2.2 is in branch "bug2210" in my public repository. Please have a look before it gets merged?

comment:8 Changed 9 years ago by iang

In the changes/bug2210 file, it's the newer streams that get preference, not the older ones, right? Streams are added to the beginning of the linked lists as they are created? (At least, that's what the experiments suggest.)

comment:9 Changed 9 years ago by nickm

ok; anything else, or should I revise the changes file and merge the code?

comment:10 Changed 9 years ago by iang

Looks OK to me.

comment:11 Changed 9 years ago by nickm

Resolution: fixed
Status: needs_reviewclosed

merged & closing. Thanks!

comment:12 Changed 7 years ago by nickm

Keywords: tor-relay added

comment:13 Changed 7 years ago by nickm

Component: Tor RelayTor
Note: See TracTickets for help on using tickets.