Re: Bandwidth throttling (was Re: Padding)

[Matej Pfajfar <badbytes@freehaven.net>]

> 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

-- 
Matej Pfajfar

GPG Public Keys @ http://matejpfajfar.co.uk/keys