Filename: 111-local-traffic-priority.txt
Title: Prioritizing local traffic over relayed traffic
Author: Roger Dingledine
Created: 14-Mar-2007
Status: Closed
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.