Bandwidth throttling (was Re: Padding)

[Roger Dingledine]

On Thu, Jun 27, 2002 at 04:09:20PM +0100, Andrei Serjantov wrote:
> OR -> OR links: I propose we leave the n^2 padding for now. Though we have
> this idea that each OR may only need to be connected to a few OR's
> (statically)  and this would give the same anonymity as being connected to
> all of them, but then the OP's need to know which OR's are connected to
> which to choose valid routes. Any opinions on this?

I'll wait for word from George on an analysis of this. I'm fine sticking
with n^2 for the foreseeable future.

> Padding: Constant padding to, say, 500Kbit. Per OR -> OR link. Each way.

Ow. I don't know what Internet you live on, but this is a lot. :) For 50
nodes, that's 25 Megabits per second each way per node. I think we must
take a lesson from Freedom here, and look for less expensive approaches.

Bandwidth throttling and flow control are closely tied to traffic shaping.
There are several issues to solve here. We need to make sure a node:
 
1) doesn't send too many data cells per timeslice
2) doesn't send too many bytes per timeslice
3) doesn't receive too many bytes per timeslice
 
My proposed solution has several components:
 
A) To prevent too many data cells from coming in to a node, we introduce
'sendme' cells for flow control. Each circuit has a window parameter at
each hop, which is the number of data cells it's allowed to send. If
the circuit's window reaches 0, it stops sending data cells. When a
sendme cell arrives, the window is incremented by a value specified in
the payload of the sendme.

(We could have the flow control be connection-wide rather than for
individual circuits, but then we end up with DoS vulnerabilities a
la Pipenet.)

The adversary can observe some of the nodes, learn which ones are stalled,
and correlate circuits and thus bridge honest nodes. But simple packet
counting attacks will already bridge nodes. Traffic padding may foil
passive adversaries, but not adversaries who are part of the network. So
with this lighter threat model, where we don't worry about correlation
attacks, we can afford to have the granularity of per-circuit flow
control.

Now, an aside before we get too much further: is there really anything
we can do against the active (node-owning) adversary? Perhaps, if we
introduce dummy traffic that looks legitimate to some nodes in the
circuit. Paul, can you elaborate on this more? In any case, I'm scared
to death of DoS, so this is it for now.

In order to keep the pipelining smooth, a downstream node will want to
send further sendme cells before the window reaches zero.

I'll cover the remaining requirements in the next few mails. Time for
some sleep.

--Roger