QoS Solution?

[Roger Dingledine]

On Sun, Mar 20, 2005 at 07:09:23PM -0600, Mike Perry wrote:
> So I've got another question actually. A few weeks ago, I proposed a
> possible QoS solution to the bittorrent/general network load issue to
> this list and then to or-dev
> (http://archives.seul.org/or/dev/Feb-2005/msg00008.html).
> 
> Basically, the idea was to seperate traffic into 4 classes based upon
> exit port, and then use some form of Weighted Fair Queuing algorithm
> to balance between them
> (http://archives.seul.org/or/dev/Feb-2005/msg00008.html).
[snip]
> This scheme was met with resistence for fear of cheating and
> unfairness, but I think it might help to mitigate your attack. 

Hi Mike,

Sorry for the delay in answering this. I've been trying to let the
various approaches filter around in my head first.

I don't think we should do explicit QoS. We're always going to
be wondering if we've got the categories right, and we'll always be
worrying that we're pushing everybody to start doing all their traffic
over port 80.

I think we should dynamically decide fairness on a per-circuit basis
based on how many cells it's already tried to push through recently.

This means if you do a quick page fetch on port 80 it works fine,
but if you pull down a dvd on port 80 you start getting less priority;
yet a long-term IM conversation over port 80 is still pretty zippy.

It also means we can decide priorities at entry/middle hops without
needing to know what port is involved, and we don't need to mess with
changing Tor's network protocol or compatibility (which means we're
forward-compatible with a better implementation somebody might do down
the road).

It still means there would be voodoo constants we need to pick and tweak
until we're happy. So be it.

And we need to pick where we're going to queue things. Two options come
to mind: A) each circuit has an outqueue and OR conns would thumb through
the outqueues, lifting off cells to send when needed. B) each OR conn
has a priority queue with say 4 bins, and circuits decide the priority
of each cell, based on a busyness stat on the circuit, and stick it in
the appropriate bin. Then conns have some algorithm to give precedence
to some bins without totally starving others.

Option B) seems conceptually easier, but our requirement for in-order
delivery of cells on each circuit will screw it up. Imagine you have
a greedy circuit, and its cells are going onto the low-priority bin;
then the circuit gets more polite, and its newer cells go onto the
high-priority bin, and get sent first. Bad news. So maybe option A)
is better. Is there an option C) out there somewhere?

If we go with A), we'd probably want to implement linked lists of circs
associated with each conn, so it's easy to hunt through them without
going through the global circuit list. One more list to keep track of
(yuck) but probably worth it.

We'd want to pick cells such that conn's outbuf has >=16kB on it when
we flush, since that's the TLS record size. Easy enough. Whenever it
has less than that, we can go through circuits until we've got nothing
to send or it's full enough.

Another worry is that there's no way to 'push back' TCP-style on a given
circuit, since circuits are multiplexed over a single OR connection
from the previous OR, and you don't know the next cell's circuit
without reading it off the network, at which point you've already
accepted it. Right now we handle this by having explicit end-to-end
acknowledgements per circuit (and per stream inside a circuit, but let's
ignore that for now), so if you don't get your ack you're not allowed to
send any more cells until you do. So the circuit queues would have a max
length of CIRCWINDOW_START (1000) cells hanging out. But this is already
an issue now, since you can open a lot of circuits and force ORs to use
up more and more buffer space (until they decide the OR conn's buffer
is too big and kill the whole thing). In fact, by dividing queues up
into per-circuit queues, we would get more control, and we could have
a smarter algorithm for picking which circuits need to die when we're
out of buffer space.

(Side note: our circuit windows are fixed at 1000 right now, which
probably impacts our performance for quick transfers of sizes over
512kB. We should be able to get much better performance by implementing
dynamic-sized windows. But on the theory that we're not trying to optimize
for bulk transfers, I'm going to continue to ignore this.)

Another worry is reconciling our fairness scheme with bandwidthrate
constraints (per per-connection and global; and read and write)). But
hopefully we can modularize the issue and have a separate algorithm that
decides how much we get to read/write on each OR conn, and that should
be entirely separate from what cells we end up putting on them. It's a
good thing we're not trying to let circuits use multiple OR conns.

Of course, by pushing low priority stuff aside only when there is high
priority stuff, we're making Steven and George's Oakland attack even
more effective. But I believe that we need to learn to live with it, as
directly combatting it will reduce usability and performance for Tor,
which is a bad plan. Our real defense against their attack is to grow
the network until it becomes hard for them to measure all of it quickly
and reliably.

What did I leave out?

--Roger