Re: Bandwidth throttling (was Re: Padding)

[Andrei Serjantov <aas23@hermes.cam.ac.uk>]

Hi,

Sorry for my disappearence. Am on a very short holiday and have only
just kept up with the messages. I talk a little about bandwidth below.

Also planning to look at the threat model and strengthening the design
a little to cope with 1st COR -> last COR vulnerability. Hope everyone
is well.

>(I start out assuming constant link padding and equal bandwidth between
>all nodes. I remove these assumptions as I go.)
>
>We want to limit nodes to sending a fixed rate of traffic at any given
>time. In order to get good mixing, we send one cell to every other node,
>every time click. So if we want to be sending 10 kilobytes per second
>per connection, then that's 80 cells per second, or a cell every 12.5
>milliseconds (round to 13). So every 13 milliseconds, you add another
>128 bytes to the outbuf of each connection (either a non-padding cell
>if you've got one, else a padding cell), and try to flush it.

Fine. That's almost the original proposal or at least what we were
thinking about with Matej.

>If all senders obey the sending rate, then receivers won't need to limit
>their receiving rate. But we must handle misbehaving senders. Nodes
>use a standard token bucket to limit received cells: each node keeps a
>"bucket" of tokens for each connection. Every second it adds 10k tokens
>to the bucket (but not to exceed some max, e.g. 10 seconds worth), and
>for each byte that it receives, it removes a token from the bucket. When
>the bucket is empty, it stops reading.

You are making sure that the receivers receive only the number of
cells they expect to. How they do it is an implementation issue.

>So far so good. Now because "whether we send a packet" is completely
>separated from "when we receive data cells", we don't have to send a
>cell to every node each time. As long as we send cells out predictably,
>we can send to each connection independently. [Somebody please tell me
>that we're ok with the anonymity implications here. I think in order
>for an adversary to take advantage of this, he needs to own lots of
>nodes around us, in which case he's got better attacks already? But it's
>critical that we investigate this question more.]
>
>So each connection can have a different bandwidth set for it, and the
>only complication this adds is that I have to keep track of timing for
>each of them in the code. Now to add in the notion of traffic shaping.

So now what you are saying is that we will have different bandwidths
on each connection from our current COR to the others. I think you
also imply that we will keep connections to other OR's even if there
are no circuits on them (is this comprehensible?). This does, of
course, reduce anonymity in comparison to constant-bandwidth on all
links case (shall I describe how and why or is it self-evident?) and
this reduction can be calculated by methods which are no too far away
from those described in our PET2002 paper + padding. One of the things
I am working on!

>When a connection is established, the two participants negotiate a
>maximum bandwidth. This is the number of tokens the receiver adds to
>his token bucket each second. The sender, on the other hand, generally
>wants to send quite a bit less than this maximum.
>
>Every five minutes, the sender decides how much bandwidth he wants to
>use for the next 5 minute interval. He randomly determines a padding
>chance $p$, between 10% and 24%. (This addresses Andrei's issues from
>before. Whenever a node is going to send a data cell he checks $p$ and
>possibly sends a padding cell instead.) If he's been using less than
>33% of the channel for data cells, then he drops his bandwidth by one
>class. If he's been using more than 66% of his bandwidth for data cells,
>he increases his bandwidth by one class. Else he stays at the same place.

I am a little surprised at the fact that you are satisfied with
this. My original proposal said "Pad to max bandwidth on all
connections equally, independent on whether there are circuits on the
connections or not". You are now saying "Pad on each connection to
hide the real bandwidth, but only as much as that, and pad the
connections without circuits a little as well".

The reason why I am surprised is that you have not saved a whole lot
of bandwidth. But maybe you are ok with this.

Ok, feel free to demand more info on this.... All this padding
analysis is the same for Mixmaster and I intend to write it up with
George. So we have a few things to say.

A.



------------------
Andrei Serjantov
Queens' College
Cambridge CB3 9ET
http://www.cl.cam.ac.uk/~aas23/