path: root/proposals/324-rtt-congestion-control.txt

Filename: 324-rtt-congestion-control.txt
Title: RTT-based Congestion Control for Tor
Author: Mike Perry
Created: 02 July 2020
Status: Open


0. Motivation [MOTIVATION]

This proposal specifies how to incrementally deploy RTT-based congestion
control and improved queue management in Tor. It is written to allow us
to first deploy the system only at Exit relays, and then incrementally
improve the system by upgrading intermediate relays.

Lack of congestion control is the reason why Tor has an inherent speed
limit of about 500KB/sec for downloads and uploads via Exits, and even
slower for onion services. Because our stream SENDME windows are fixed
at 500 cells per stream, and only ~500 bytes can be sent in one cell,
the max speed of a single Tor stream is 500*500/circuit_latency. This
works out to about 500KB/sec max sustained throughput for a single
download, even if circuit latency is as low as 500ms.

Because onion services paths are more than twice the length of Exit
paths (and thus more than twice the circuit latency), onion service
throughput will always have less than half the throughput of Exit
throughput, until we deploy proper congestion control with dynamic
windows.

Proper congestion control will remove this speed limit for both Exits
and onion services, as well as reduce memory requirements for fast Tor
relays, by reducing queue lengths.

The high-level plan is to use Round Trip Time (RTT) as a primary
congestion signal, and compare the performance of two different
congestion window update algorithms that both use RTT as a congestion
signal.

The combination of RTT-based congestion signaling, a congestion window
update algorithm, and Circuit-EWMA will get us the most if not all of
the benefits we seek, and only requires clients and Exits to upgrade to
use it. Once this is deployed, circuit bandwidth caps will no longer be
capped at ~500kb/sec by the fixed window sizes of SENDME; queue latency
will fall significantly; memory requirements at relays should plummet;
and transient bottlenecks in the network should dissipate.

Extended background information on the choices made in this proposal can
be found at:
  https://lists.torproject.org/pipermail/tor-dev/2020-June/014343.html
  https://lists.torproject.org/pipermail/tor-dev/2020-January/014140.html

An exhaustive list of citations for further reading is in Section
[CITATIONS].


1. Overview [OVERVIEW]

This proposal has five main sections, after this overview. These
sections are referenced [IN_ALL_CAPS] rather than by number, for easy
searching.

Section [CONGESTION_SIGNALS] specifies how to use Tor's SENDME flow
control cells to measure circuit RTT, for use as an implicit congestion
signal. It also mentions an explicit congestion signal, which can be
used as a future optimization once all relays upgrade.

Section [CONTROL_ALGORITHMS] specifies two candidate congestion window
upgrade mechanisms, which will be compared for performance in simulation
in Shadow, as well as evaluated on the live network, and tuned via
consensus parameters listed in [CONSENSUS_PARAMETERS].

Section [FLOW_CONTROL] specifies how to handle back-pressure when one of
the endpoints stops reading data, but data is still arriving. In
particular, it specifies what to do with streams that are not being read
by an application, but still have data arriving on them.

Section [SYSTEM_INTERACTIONS] describes how congestion control will
interact with onion services, circuit padding, and conflux-style traffic
splitting.

Section [EVALUATION] describes how we will evaluate and tune our
options for control algorithms and their parameters.

Section [PROTOCOL_SPEC] describes the specific cell formats and
descriptor changes needed by this proposal.

Section [SECURITY_ANALYSIS] provides information about the DoS and
traffic analysis properties of congestion control.


2. Congestion Signals [CONGESTION_SIGNALS]

In order to detect congestion at relays on a circuit, Tor will use
circuit Round Trip Time (RTT) measurement. This signal will be used in
slightly different ways in our various [CONTROL_ALGORITHMS], which will
be compared against each other for optimum performance in Shadow and on
the live network.

To facilitate this, we will also change SENDME accounting logic
slightly. These changes only require clients, exits, and dirauths to
update.

As a future optimization, it is possible to send a direct ECN congestion
signal. This signal *will* require all relays on a circuit to upgrade to
support it, but it will reduce congestion by making the first congestion event
on a circuit much faster to detect.

To reduce confusion and complexity of this proposal, this signal has been
moved to the ideas repository, under xxx-backward-ecn.txt [BACKWARD_ECN].


2.1 RTT measurement

Recall that Tor clients, exits, and onion services send
RELAY_COMMAND_SENDME relay cells every CIRCWINDOW_INCREMENT (100) cells
of received RELAY_COMMAND_DATA.

This allows those endpoints to measure the current circuit RTT, by
measuring the amount of time between sending of every 100th data cell
and the arrival of the SENDME command that the other endpoint
immediately sends to ack that 100th cell.

Circuits will record the current RTT measurement as a field in their
circuit_t data structure. They will also record the minimum and maximum
RTT seen so far.

Algorithms that make use of this RTT measurement for congestion
window update are specified in [CONTROL_ALGORITHMS].

2.2. SENDME behavior changes

We will make four major changes to SENDME behavior to aid in computing
and using RTT as a congestion signal.

First, we will need to establish a ProtoVer of "FlowCtrl=2" to signal
support by Exits for the new SENDME format and congestion control
algorithm mechanisms.  We will need a similar announcement in the onion
service descriptors of services that support congestion control.

Second, we will turn CIRCWINDOW_INCREMENT into a consensus parameter
'circwindow_inc', instead of using a hardcoded value of 100 cells. It is
likely that more frequent SENDME cells will provide quicker reaction to
congestion, since the RTT will be measured more often. If
experimentation in Shadow shows that more frequent SENDMEs reduce
congestion and improve performance but add significant overhead, we can
reduce SENDME overhead by allowing SENDME cells to carry stream data, as
well, using Proposal 325.

  TODO: If two endpoints view different consensus parameters for
        'circwindow_inc', we will have complications measuring RTT,
        as well as complications for authenticated SENDME hash
        accounting. We need a way for endpoints to negotiate SENDME
        pacing with eachother, perhaps during circuit setup. This will
        require changes to the Onionskin/CREATE cell format (and
        RELAY_COMMAND_EXTEND), as mentioned in Section [PROTOCOL_SPEC].
        This could be accomplished via hs-ntor's handshake, which
        allows extra data fields in the circuit handshake.

  TODO: circwindow_inc's rate of change could be capped for safety

  TODO: As an optimization, 'circwindow_inc' could change as a function
        of slow start vs AIMD.

Second, all end-to-end relay cells except RELAY_COMMAND_DROP and SENDME
itself will count towards SENDME cell counts. The details behind how these
cells are handled is addressed in section [SYSTEM_INTERACTIONS].

   TODO: List any other exceptions. There probably are some more.

Third, authenticated SENDMEs can remain as-is in terms of protocol
behavior, but will require some implementation updates to account for
variable window sizes and variable SENDME pacing. In particular, the
sendme_last_digests list for auth sendmes needs updated checks for
larger windows and CIRCWINDOW_INCREMENT changes. Other functions to
examine include:
     - circuit_sendme_cell_is_next()
     - sendme_record_cell_digest_on_circ()
     - sendme_record_received_cell_digest()
     - sendme_record_sending_cell_digest()
     - send_randomness_after_n_cells

Fourth, stream level SENDMEs will be eliminated. Details on handling
streams and backpressure is covered in [FLOW_CONTROL].


3. Congestion Window Update Algorithms [CONTROL_ALGORITHMS]

We specify two candidate window update algorithms. The specification
describes the update algorithms for the slow start phase and the
steady state phase separately, with some explanation. Then the
combined algorithm is given.

Note that these algorithms differ slightly from the background tor-dev
mails[1,2], due to corrections and improvements. Hence they have been
given different names than in those two mails.

These algorithms will be evaluated by running Shadow simulations, to
help determine parameter ranges, but experimentation on the live network
will be required to determine which of these algorithms performs best
when in competition with our current SENDME behavior, as used by real
network traffic. This experimentation and tuning is detailed in section
[EVALUATION].

All of these algorithms have rules to update 'cwnd' - the current
congestion window max. They also change the meaning of 'package_window'
to be a positive count of the total number of sent cells that are awaiting
SENDME ack. Thus, 'package_window' is never allowed to exceed 'cwnd', and
the remaining cells that can be sent at any time is 'cwnd - package_window'.

C Tor also maintains a 'deliver_window', which it uses to track how many cells
it has received, in order to send the appropriate number of SENDME acks.

  TODO: This 'deliver_window' count can be updated by the other
        endpoint using the congestion control rules to watch for
        cheating. Alternatively, it can be simplified just to count
        the number of cells we get until we send a SENDME.

Implementation of different algorithms should be very simple - each
algorithm should have a different set of package_window update functions
depending on the selected algorithm, as specified by consensus parameter
'cc_alg'.

For C Tor's current flow control, these functions are defined in sendme.c,
and are called by relay.c:
  - sendme_note_circuit_data_packaged()
  - sendme_circuit_data_received()
  - sendme_circuit_consider_sending()
  - sendme_process_circuit_level()

Despite the complexity of the following algorithms in their TCP
implementations, their Tor equivalents are extremely simple, each being
just a handful of lines of C. This simplicity is possible because Tor
does not have to deal with out-of-order delivery, packet drops,
duplicate packets, and other network issues at the circuit layer, due to
the fact that Tor circuits already have reliability and in-order
delivery at that layer.

We are also removing the aspects of TCP that cause the congestion
algorithm to reset into slow start after being idle for too long, or
after too many congestion signals. These are deliberate choices that
simplify the algorithms and also should provide better performance for
Tor workloads.

  TODO: We may want to experiment with adding revert-to-slow-start back
        in, but slow start is very expensive in a lot of ways, so let's
        see if we can avoid falling back into it, if at all possible.

For explanatory reasons, we present the slow start and the AIMD portions of
each algorithm separately, and then combine the two pieces to show the
full control algorithm, in each case. The full algorithms are considered
canonical (sections 3.1.3 and 3.2.3).

Note that these algorithms contain division in this shorthand. Division can be
elided with relocating those lines to update less often (ie: only once per
'cwnd', to avoid dividing by 'cwnd' every SENDME).

In all cases, variables in these sections are either consensus parameters
specified in [CONSENSUS_PARAMETERS], or scoped to the circuit.


3.1. Tor Westwood: TCP Westwood using RTT signaling [TOR_WESTWOOD]
   http://intronetworks.cs.luc.edu/1/html/newtcps.html#tcp-westwood
   http://nrlweb.cs.ucla.edu/nrlweb/publication/download/99/2001-mobicom-0.pdf
   http://cpham.perso.univ-pau.fr/TCP/ccr_v31.pdf
   https://c3lab.poliba.it/images/d/d7/Westwood_linux.pdf

Recall that TCP Westwood is basically TCP Reno, but it uses RTT to help
estimate the bandwidth-delay-product (BDP) of the link, and use that for
"Fast recovery" after a congestion signal arrives.

We will also be using the RTT congestion signal as per BOOTLEG_RTT_TOR
here, from the Options mail[1] and Defenestrator paper[3].

This system must keep track of two main measurements, per circuit:
RTT_min, and RTT_max. Both are measured using the time delta between
every 'circwindow_inc' relay cells and the SENDME response. The first RTT_min
can be measured arbitrarily, so long as it is larger than what we would get
from SENDME.

Recall that BOOTLEG_RTT_TOR emits a congestion signal when the current
RTT falls below some fractional threshold ('rtt_thresh') fraction
between RTT_min and RTT_max. This check is:
   RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max

(We can also optionally use the ECN signal described in
ideas/xxx-backward-ecn.txt, to exit Slow Start.)

Tor Westwood will require each circuit endpoint to maintain a
Bandwidth-Delay-Product (BDP) and Bandwidth Estimate (BWE) variable.

The bandwidth estimate is the current congestion window size divided by
the RTT estimate:

   BWE = cwnd / RTT_current

The BDP estimate is computed by multiplying the Bandwidth estimate by
the circuit latency:

   BDP = BWE * RTT_min

The BDP can also be measured directly using the peak package_window observed
on the circuit so far (though this may over-estimate if queues build up):

   BDP = max(package_window)

This queue delay error may be reduced by using the RTT during the max
package_window to get BWE, and then computing BDP:

   BWE = max(package_window)/RTT_current    # RTT during max package_window
   BDP = BWE * RTT_min

  TODO: Different papers on TCP Westwood and TCP Vegas recommend
        different methods for estimating BWE and BDP. See citations for
        details, but common options for BWE are 'package_window/RTT_current'
        or 'circwindow_inc*sendme_arrival_rate'. They also recommend
        averaging and filtering of the BWE, due to ack compression in
        inbound queues. We will need to experiment to determine how to
        best compute the BWE and BDP for Tor circuits.

3.1.1. Tor Westwood: Slow Start

Prior to the first congestion signal, Tor Westwood will update its
congestion window exponentially, as per Slow Start.

Recall that this first congestion signal can be either BOOTLEG_RTT_TOR's
RTT threshold signal, or ideas/xxx-backward-ecn.txt cell command signal.

For simplicity, we will just write the BOOTLEG_RTT_TOR check, which
compares the current RTT measurement to the observed min and max RTT,
using the consensus parameter 'rtt_thresh'.

This section of the update algorithm is:

   package_window = package_window - circwindow_inc  # For acked cells

   # BOOTLEG_RTT_TOR threshold check:
   if RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max:
      cwnd = cwnd + circwindow_inc                   # Exponential growth
    else:
      BDP = BWE*RTT_min                              # Or other BDP estimate
      cwnd = min(cwnd * cwnd_recovery_m, BDP)
      in_slow_start = 0

Increasing the congestion window by 100 *more* cells every SENDME allows
the sender to send 100 *more* cells every 100 cells. Thus, this is an
exponential function that causes cwnd to double every cwnd cells.

Once a congestion signal is experienced, Slow Start is exited, and the
Additive-Increase-Multiplicative-Decrease (AIMD) steady-state phase
begins.

3.1.2. Tor Westwood: Steady State AIMD

After slow start exits, in steady-state, after every SENDME response
without a congestion signal, the window is updated as:

   package_window = package_window - circwindow_inc  # For acked cells
   cwnd = cwnd + circwindow_inc/cwnd                 # Linear window growth

This comes out to increasing cwnd by 1, every time cwnd cells are
successfully sent without a congestion signal occurring. Thus this is
additive linear growth, not exponential growth.

If there is a congestion signal, cwnd is updated as:

   package_window = package_window - circwindow_inc  # For acked cells
   cwnd = min(cwnd * cwnd_recovery_m, BDP)           # For window shrink

This is called "Fast Recovery". If you dig into the citations, actual
TCP Westwood has some additional details for responding to multiple
packet losses that in some cases can fall back into slow-start, as well
as some smoothing of the BDP to make up for dropped acks. Tor does not
need either of these aspects of complexity.

3.1.3. Tor Westwood: Complete SENDME Update Algorithm

Here is the complete congestion window algorithm for Tor Westwood, using
only RTT signaling.

Recall that 'package_window' is not allowed to exceed 'cwnd' while sending.
'package_window' must also never become negative - this is a protocol error
that indicates a malicious endpoint.

This will run each time we get a SENDME (aka sendme_process_circuit_level()):

   in_slow_start = 1                                   # Per-circuit indicator

   Every received SENDME ack, do:
     package_window = package_window - circwindow_inc  # Update acked cells

     # BOOTLEG_RTT_TOR threshold; can also be BACKWARD_ECN check:
     if RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max:
       if in_slow_start:
         cwnd = cwnd + circwindow_inc                  # Exponential growth
       else:
         cwnd = cwnd + circwindow_inc/cwnd             # Linear growth
     else:
       BDP = BWE*RTT_mi