tor/doc/spec/proposals/111-local-traffic-priority.txt

Filename: 111-local-traffic-priority.txt
Title: Prioritizing local traffic over relayed traffic
Version: $Revision$
Last-Modified: $Date$
Author: Roger Dingledine
Created: 14-Mar-2007
Status: Finished
Implemented-In: 0.2.0.x

Overview:

  We describe some ways to let Tor users operate as a relay and enforce
  rate limiting for relayed traffic without impacting their locally
  initiated traffic.

Motivation:

  Right now we encourage people who use Tor as a client to configure it
  as a relay too ("just click the button in Vidalia"). Most of these users
  are on asymmetric links, meaning they have a lot more download capacity
  than upload capacity. But if they enable rate limiting too, suddenly
  they're limited to the same download capacity as upload capacity. And
  they have to enable rate limiting, or their upstream pipe gets filled
  up, starts dropping packets, and now their net connection doesn't work
  even for non-Tor stuff. So they end up turning off the relaying part
  so they can use Tor (and other applications) again.

  So far this hasn't mattered that much: most of our fast relays are
  being operated only in relay mode, so the rate limiting makes sense
  for them. But if we want to be able to attract many more relays in
  the future, we need to let ordinary users act as relays too.

  Further, as we begin to deploy the blocking-resistance design and we
  rely on ordinary users to click the "Tor for Freedom" button, this
  limitation will become a serious stumbling block to getting volunteers
  to act as bridges.

The problem:

  Tor implements its rate limiting on the 'read' side by only reading
  a certain number of bytes from the network in each second. If it has
  emptied its token bucket, it doesn't read any more from the network;
  eventually TCP notices and stalls until we resume reading. But if we
  want to have two classes of service, we can't know what class a given
  incoming cell will be until we look at it, at which point we've already
  read it.

Some options:

  Option 1: read when our token bucket is full enough, and if it turns
  out that what we read was local traffic, then add the tokens back into
  the token bucket. This will work when local traffic load alternates
  with relayed traffic load; but it's a poor option in general, because
  when we're receiving both local and relayed traffic, there are plenty
  of cases where we'll end up with an empty token bucket, and then we're
  back where we were before.

  More generally, notice that our problem is easy when a given TCP
  connection either has entirely local circuits or entirely relayed
  circuits. In fact, even if they are both present, if one class is
  entirely idle (none of its circuits have sent or received in the past
  N seconds), we can ignore that class until it wakes up again. So it
  only gets complex when a single connection contains active circuits
  of both classes.

  Next, notice that local traffic uses only the entry guards, whereas
  relayed traffic likely doesn't. So if we're a bridge handling just
  a few users, the expected number of overlapping connections would be
  almost zero, and even if we're a full relay the number of overlapping
  connections will be quite small.

  Option 2: build separate TCP connections for local traffic and for
  relayed traffic. In practice this will actually only require a few
  extra TCP connections: we would only need redundant TCP connections
  to at most the number of entry guards in use.

  However, this approach has some drawbacks. First, if the remote side
  wants to extend a circuit to you, how does it know which TCP connection
  to send it on? We would need some extra scheme to label some connections
  "client-only" during construction. Perhaps we could do this by seeing
  whether any circuit was made via CREATE_FAST; but this still opens
  up a race condition where the other side sends a create request
  immediately. The only ways I can imagine to avoid the race entirely
  are to specify our preference in the VERSIONS cell, or to add some
  sort of "nope, not this connection, why don't you try another rather
  than failing" response to create cells, or to forbid create cells on
  connections that you didn't initiate and on which you haven't seen
  any circuit creation requests yet -- this last one would lead to a bit
  more connection bloat but doesn't seem so bad. And we already accept
  this race for the case where directory authorities establish new TCP
  connections periodically to check reachability, and then hope to hang
  up on them soon after. (In any case this issue is moot for bridges,
  since each destination will be one-way with respect to extend requests:
  either receiving extend requests from bridge users or sending extend
  requests to the Tor server, never both.)

  The second problem with option 2 is that using two TCP connections
  reveals that there are two classes of traffic (and probably quickly
  reveals which is which, based on throughput). Now, it's unclear whether
  this information is already available to the other relay -- he would
  easily be able to tell that some circuits are fast and some are rate
  limited, after all -- but it would be nice to not add even more ways to
  leak that information. Also, it's less clear that an external observer
  already has this information if the circuits are all bundled together,
  and for this case it's worth trying to protect it.

  Option 3: tell the other side about our rate limiting rules. When we
  establish the TCP connection, specify the different policy classes we
  have configured. Each time we extend a circuit, specify which policy
  class that circuit should be part of. Then hope the other side obeys
  our wishes. (If he doesn't, hang up on him.) Besides the design and
  coordination hassles involved in this approach, there's a big problem:
  our rate limiting classes apply to all our connections, not just
  pairwise connections. How does one server we're connected to know how
  much of our bucket has already been spent by another? I could imagine
  a complex and inefficient "ok, now you can send me those two more cells
  that you've got queued" protocol. I'm not sure how else we could do it.

  (Gosh. How could UDP designs possibly be compatible with rate limiting
  with multiple bucket sizes?)

  Option 4: put both classes of circuits over a single connection, and
  keep track of the last time we read or wrote a high-priority cell. If
  it's been less than N seconds, give the whole connection high priority,
  else give the whole connection low priority.

  Option 5: put both classes of circuits over a single connection, and
  play a complex juggling game by periodically telling the remote side
  what rate limits to set for that connection, so you end up giving
  priority to the right connections but still stick to roughly your
  intended bandwidthrate and relaybandwidthrate.

  Option 6: ?

Prognosis:

  Nick really didn't like option 2 because of the partitioning questions.

  I've put option 4 into place as of Tor 0.2.0.3-alpha.

  In terms of implementation, it will be easy: just add a time_t to
  or_connection_t that specifies client_used (used by the initiator
  of the connection to rate limit it differently depending on how
  recently the time_t was reset). We currently update client_used
  in three places:
    - command_process_relay_cell() when we receive a relay cell for
      an origin circuit.
    - relay_send_command_from_edge() when we send a relay cell for
      an origin circuit.
    - circuit_deliver_create_cell() when send a create cell.
  We could probably remove the third case and it would still work,
  but hey.