Bandwidth throttling (was Re: Padding)

[Roger Dingledine]

(Yes, I'm answering my own mail too, here :)

On Thu, Jul 04, 2002 at 04:24:53AM -0400, Roger Dingledine wrote:
> 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.
[snip]
> In order to keep the pipelining smooth, a downstream node will want to
> send further sendme cells before the window reaches zero.

Let's examine this issue farther. If we really don't want to get cells
that we can't immediately pass on, then we can't afford to send back a
sendme window that's larger than the one we got from in front of us.

That is, when Alice opens a circuit to Bob, then no node in the circuit
will be willing to accept data cells except the one connected to Bob. So
that node $k-1$ will send a "sendme 100" instruction to $k-2$. At this
point node $k-2$ will be willing to receive data cells, so it will
send a "sendme 100" cell to $k-3$. (It could choose to send a smaller
sendme value, but it can't risk sending a larger one, because then it
might be stuck with cells it can't do anything with.) Eventually the
"sendme 100" instruction will ripple back to node $1$, at which point
Alice will be allowed to queue 100 cells. These cells will travel forward
on the circuit, and when the first 10 of them (say) have reached $k-1$,
it will send a "sendme 10" back. So data cells will travel forward and
"sendme 10" cells will ripple back.

If at any point node $1$ has sent its entire window and a "sendme 10"
hasn't arrived yet, node $1$ will stop reading from Alice and stop
sending cells. It seems that we need to choose the parameters 100 and
10 such that this occurrence is rare, but without spending lots of our
bandwidth on sendme cells.

We can probably get added robustness, and better performance, by adding
internal buffers to each node for each circuit. Thus a given node is free
to send a "sendme 50" on its own, knowing that it's got 50 cells worth of
internal buffer space already set aside for that circuit. This internal
buffering, similar to what routers do, can help smooth the pipelining.

Adding internal buffers for better performance probably doesn't have to
be done anytime soon. But I suppose we'll see. :)

--Roger