On Wed, Dec 17, 2008 at 7:48 PM, Salman Abdul Baset <[email protected]> wrote:
>
>> FWIW, storing forwarding state vs appending to the via list is a
>> long-standing option in the protocol. The only thing that is new is
>> whether to do hop-by-hop reassembly.
>>
>> I'd be interested in seeing a proposal for a DoS mitigation technique
>> on this type of attack that has nearly the effectiveness or simplicity
>> of hop-by-hop reassembly. For that matter, I'd be interested in a DoS
>> mitigation approach for storing return path state that is simpler than
>> using reassembly as a fall-back strategy.
>
> I mentioned the solution in an earlier post:
> http://www.ietf.org/mail-archive/web/p2psip/current/msg04541.html
>
> For return path state, one solution is to limit the inprogress messages from
> a certain peer to a configured number. If the peer still sends more
> messages, it can be informed to do ROUTE-QUERY, thereby preventing further
> consumption of memory on the intermediary nodes.
Looking at that idea, it provides a much simpler approach to dealing
with excessive state than the always reassemble. But it has a pretty
substantial cost, too. Let the max inprogress messages from a peer be
X. Since any peer in the system can send messages through it, it
effectively requires storage of X * N, where N is the number of peers
in the system. You can argue that it should be X * E+G, where E is
the number of evil peers and G is the number of good peers that have a
legitimate need to route messages through this peer, but it's really
hard to bound either of those numbers.
There's also a problem that I think this will break exponentially
spaced finger tables, such as used by chord. The first finger table
entry will be used for 50% of a peer's originiated requests (assuming
even distribution). I think it's going to be hard to set X high
enough so you don't force a peer to have additional connections beyond
its first finger table entry, but low enough to defend against DoS
attacks.
Going back to the size issue, I'm going to handwave at some numbers
here. Let's say that X is 10 and we route 100 messages per second
from 2500 peers (over the course of a few minutes). The current
message timeout in the draft (needs to be changed) is 15 seconds. So
you're storing state for 1500 messages at a typical time. For each
message you're storing
transaction id -> {return connection (could be an index in a table or
a pointer to a dtls structure), source Node-ID , timeout }
so that's 64 bits + 32/64 bits + 128 bits + 32 bits (for some
systems), let's round it to 40 bytes and allow 50% overhead for the
hashtable and data structure inefficiency, so 80 bytes per entry.
That gives 120K dedicated to message state.
Plus, we have to store counters for the number of messages we're
storing for each peer. For this, you have a hashtable of
Node-ID -> counter
so 128 + 32, so 20 bytes goes to 40 bytes. That's 100K for this data structure.
So essentially, 220K for the state and counters. Oh, and you need to
sweep your first hashtable occasionally to prune out expired
transactions, or introduce a queue for that. Seems implementation
dependent whether memory or CPU/memory bandwidth is cheaper, though I
would lean toward a separate queue structure, in which case we'll just
round and say we're at 300K of data structures.
Now keep in mind that X=10 is pretty low and will certainly cause
problems with a peer that has us as their first finger table entry or
a peer with a lot of (non-reload) clients behind it.
Now, for comparison with hop-by-hop reassembly, let's say a peer has
20 active connections and the max message size for the overlay is 5K,
and the max out-of-order is 5 fragments, with MTU=1500. So we need
per connection buffers of 5K + 10*1500=12500. * 20 connections gives
us 250K
So the data structure sizes are similar. I'll call it dead even since
these numbers can obviously be swung either way with slight tweaks of
the parameters.
A pro of the max-per-source approach is that it never slows messages
for buffering. A con is that it has a tradeoff in that it essentially
breaks exponentially spaced finger table routing for peers that have a
legitimate need to exceed whatever bound X is used.
The pro of the always reassemble approach is that it's rather simple
to implement. It also only needs to be done when a smallish return
path state table is full. The con is that it slows down messages by
whatever the time it is to assemble the entire message.
I prefer the always reassemble approach because it has fewer magic
numbers and it doesn't impact the rest of the system so much. But we
may need a more thorough comparison/writeup of the various approaches
to decide.
Bruce
_______________________________________________
P2PSIP mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/p2psip
