Bandwidth throttling (was Re: Padding)

Matej Pfajfar badbytes at
Thu Jul 4 09:04:17 UTC 2002

> I'll wait for word from George on an analysis of this. I'm fine sticking
> with n^2 for the foreseeable future.
If we find a good way of handling traffic shaping then this becomes less 
of a problem - i.e. if the connections don't guzzle up constant bandwidth, 
then the overhead cost of the connections is something we can handle?

> > 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.
An interesting solution that I read in some paper (and I need to find out 
which!) is this: when a node receives a cell destined to go over one of 
its longstanding connections - it transmits the cell and also sends a 
single padding cell on all of the other longstanding connections it is 
adjacent to. No other padding.

> 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.
Yes that's the sort of idea I had with ACK/NACK cells - but there is no 
provision for discarding cells. I think we need to be able to drop cells
(at each node, in whichever way we like) to protect against DoS. In this 
idea, a node can't drop a cell once it has received it because it isn't 
being buffered anywhere else. So should we not consider end-to-end (OP -> 
COR_last) flow control?

> (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.)
I agree. That's bad.

> 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.
OK, I need some more help with this - are you worried about an active 
adversary discovering the bandwidth of individual circuits?
A way of preventing this (just a quick idea, not thought about this) is to 
introduce another 
"command" field to the cell. A node will forward all non-padding cells 
unless the new field matches some certain value (which we could put in the 
onion). It will also replace the field with a new value for the next hop 
(also contained in the onion). The OP could then introduce random dummy 
traffic which only some nodes would recognize as dummy. 


Matej Pfajfar

GPG Public Keys @

More information about the tor-dev mailing list