Subject: [P2PSIP] RELOAD fragmentation

From: Eric Rescorla <[email-masked]>
Date: Fri, 12 Dec 2008 10:08:42 -0800

The author team has been trying to flesh out the RELOAD fragmentation model and
we're considering whether it needs a rethink. This is principally an 
issue for UDP.

Briefly, the current model is as follows:

- Nodes communicate to each other by encapsulating every RELOAD message
  in a FramedMessage (see 5.4.1.2). These are acknowledged at the
  hop-by-hop level. Each FramedMessage contains a complete RELOAD message
  or ACK.
- If a message exceeds the maximum size that a node feels it can send
  to an adjacent node (this principally is an issue for UDP), it is expected
  to fragment it. Each fragment replicates the ForwardingHeader.
- Intermediate nodes are not expected to reassemble fragments.

The bits on the wire aren't fully fleshed out, but this is what we had in
mind.

Unfortunately, it's not clear that this works. Unlike IP (except with LSRR),
the RELOAD header grows and could potentially exceed the MTU all on its
own. So, it's not clear how to handle that case.

The reason we didn't go for intermediate node reassembly was that (by analogy
to IP) we didn't want to impose excessive burdens on the intermediate
nodes). However, it's not clear that this is a good analogy. After all,
you're already consuming reasource for the TLS and other state for
the adjacent peer anyway, and it's quite straightforward for them
to force you to chew up buffer space by sending a very large partial
message, so it's not clear there is a security issue here that 
can't be solved just by having some sort of trivial timeout and
maximum size on the receiver side.

Aside from state, the major disadvantage of hop-by-hop fragmentation
is performance for larger messages, since it becomes effectively a
stop-and-wait protocol instead of a windowed protocol. I'm not sure
how big a deal that is, since I think we more or less agreed in MSP
that it's not a good idea to push lrge messages across the overlay,
but I thought it should be mentioned.

-Ekr

_______________________________________________
P2PSIP mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2psip

---

From: Ted Hardie <[email-masked]>
Date: Mon, 15 Dec 2008 12:11:44 -0800

>own. So, it's not clear how to handle that case.

Is this growth primarily in the via list?  If that is the case, then it
seems possible to solve this using a combination of the fragment
field and the via list.  If the fragment field's high order two bits
indicate that this is a fragment, you could replace the via list
with a null list for any fragment after the first complete rendering
of the via list.  That requires one more state in the fragment field
(via list not yet complete;via list complete).  It also requires you
to presume that the via list can be split across fragments and
and that fragments with "via list not yet complete" set are
going to have no real data--just segments of the via list--in them.

The same things can be done when other headers grow, obviously;
it is just a bit easiert to do when it is only one header that has to
be tracked in this way. 
			regards,
				Ted

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Tue, 16 Dec 2008 11:33:49 -0800

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Eric Rescorla
> Sent: Friday, December 12, 2008 10:09 AM
> To: [email-masked]
> Subject: [P2PSIP] RELOAD fragmentation
> 

Yeah, unfortunately, the growth is an issue and I don't think the above method can be guaranteed to work.  Short of the sending nodes being able to estimate the size of the overlay and hence extrapolate the expected number of entries in a via list and adjust the message size accordingly, we may have a problem.  

> maximum size on the receiver side.

I do think security issues can be handled using timeouts; but, as a general philosophy, I don't think it is good to pile on more functionality on intermediate nodes just because they are already doing something else.  In this particular case though, when symmetric routing is in use, I'm not sure there is a good alternative - I describe one option below, but I can't say that's necessarily good either.  

> how big a deal that is, 

Well, you are, however, potentially increasing the lookup latency.  The via list is probably the only reason that an intermediate node may be required to fragment the message.  An alternative might be for each node to maintain state about the previous hop instead of including a via list.  This still provides symmetric routing; however, each node will have to maintain state to route the response back.  Security issues with state maintenance will be handled using similar timeouts as you mention above.  

> since I think we more or less agreed in MSP

I think we should have a design that helps avoiding large messages across the overlay - I'll take this up in a separate thread.  

Thanks,
Vidya

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Tue, 16 Dec 2008 11:35:21 -0800

> going to have no real data--just segments of the via list--in them.

Maybe I'm missing something basic here.  How would the sending node even know that the via list was rendered completely at any time? 

Regards,
Vidya

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Tue, 16 Dec 2008 15:09:40 -0500

The two problems are the growth of the via list and route logging.
Like you've suggested, it's impossible to figure out how long the via
list needs to get.  There are some hackish possibilities like allowing
extra room in the first fragment for the via list to grow and letting
the first fragment be re-fragmented if the via list grows beyond the
MTU of subsequent hops (since MTU can drop, always need to support
that behavior, anyway).  Another option would be to reorder the
message so that the via list is at the end (although there's a similar
problem with the destination list being too long, anyway).

So I think there are some solutions to having the intervening peers
keep state, but the complexity concerns me.  It's a lot simpler to
have intermediate peers reassemble and maybe do something like
restrict the amount of buffering required per connection, which seems
reasonable if we require the sender not to interleave frags from
different messages.  (Obviously the network can still reorder, but I
think we can establish a reasonable bound on that.)

Bruce

---

From: Ted Hardie <[email-masked]>
Date: Tue, 16 Dec 2008 12:21:24 -0800

At 12:09 PM -0800 12/16/08, Bruce Lowekamp wrote:
>that behavior, anyway). 

The behavior I was assuming (and did not state well--sorry) was that
you could allot a certain amount to the via list and reassembly/refragmentation
would occur only if the via list growth forced it.  This gets a little
more difficult if there are two headers (via list and route logging),
but I think it does work. 

This is a hack (politely, I guess I could call it a "hybrid solution"),
but it does allow common cases to go forward without reassembly
and refragmentation (any case where the amount of growth
allotted was sufficient) while handling the less common case
of an addition causing an over-run. 

>Another option would be to reorder the

Any particular reason not to do this?
				Ted

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Tue, 16 Dec 2008 12:34:40 -0800

> From: Bruce Lowekamp [mailto:[email-masked]]
> Sent: Tuesday, December 16, 2008 12:10 PM
> To: Narayanan, Vidya
> Cc: Hardie, Ted; Eric Rescorla; [email-masked]
> Subject: Re: [P2PSIP] RELOAD fragmentation
> 
> extra room in the first fragment for the via list to grow 

Yes, this is what I meant with doing a overlay size estimation and sizing the message accordingly.  But, obviously, it has the problem you talk about below with varying MTUs.  I don't think this is a solution worth considering.   

> and letting

I don't see the similarity of the problem with destination list - in the case of a destination list, the originator of the message deals with the largest size that message will get to - so, fragementation at the sender works here.  Or, am I missing something? 

> have intermediate peers reassemble 

Hmmm.. I am not sure about that.  I don't think keeping state is necessarily more complex.  Even with fragmentation, you'll need timeouts to handle the DoS attacks Ekr was talking about - so, in either case, you have state that needs to timeout.  OTOH, keeping forwarding state reduces the lookup latency as opposed to dealing with fragmentation and reassembly at the intermediate peers. 

- Vidya

> and maybe do something like
> > Maybe I'm missing something basic here.  How would the sending node
> even know that the via list was rendered completely at any time?
> >
> > Regards,
> > Vidya
> >

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Tue, 16 Dec 2008 13:38:12 -0800

Going back to the basics here - is there a reason we cannot let IP handle fragmentation for UDP messages and keep the added functionality to just reliability? 

Maybe I'm missing something fundamental - but, it seems like as inefficient as that may actually be, it might be the simplest solution to the problem. 

Thoughts? 

Vidya

> Behalf Of Narayanan, Vidya
> Sent: Tuesday, December 16, 2008 12:35 PM
> To: Bruce Lowekamp
> Cc: [email-masked]
> Yes, this is what I meant with doing a overlay size estimation and
> sizing the message accordingly.  But, obviously, it has the problem you
> talk about below with varying MTUs.  I don't think this is a solution
> worth considering.
> 
> > and letting
> I don't see the similarity of the problem with destination list - in
> the case of a destination list, the originator of the message deals
> with the largest size that message will get to - so, fragementation at
> the sender works here.  Or, am I missing something?
> 
> Hmmm.. I am not sure about that.  I don't think keeping state is
> necessarily more complex.  Even with fragmentation, you'll need
> timeouts to handle the DoS attacks Ekr was talking about - so, in
> either case, you have state that needs to timeout.  OTOH, keeping
> forwarding state reduces the lookup latency as opposed to dealing with
> fragmentation and reassembly at the intermediate peers.
> 
> - Vidya
> 
> > On Tue, Dec 16, 2008 at 2:35 PM, Narayanan, Vidya
> <[email-masked]>
> > wrote:
> > >>
> > >> Is this growth primarily in the via list?  If that is the case,
> then
> > it

---

From: Salman Abdul Baset <[email-masked]>
Date: Tue, 16 Dec 2008 16:43:10 -0500 (EST)

To summarize the discussion, fragmentation happens due to:

c1) via-list and route-list growth (only in recursive routing)
c2) resource + header size exceeding MTU
   -at the request originator
   -or at the intermediate nodes.

Solution space consists of whether intermediate nodes should:

s1) store via/route-list in the local memory
s2) store via/route-list + fragment state in the message
s3) perform per-hop reassembly of fragments
s4) perform e2e reassembly of fragments

The protocol provides ROUTE-QUERY message which allows to search for the 
destination peer before performing the transfer (essentially, iterative 
routing). This is one way to avoid via-list and route-query growth 
problem.

As a fragmentation solution, I prefer s1|s2 with s4.

I am not in favor of (s3), i.e., per-hop reassembly of fragments as a MUST 
in base spec whether this is for via/route-list or for large messages.

-salman

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Tue, 16 Dec 2008 16:57:42 -0500

(Replies to both Ted and Vidya's messages below)

> but I think it does work.

Yeah, I think I agree it can work.  Will be a little bit tricky
(especially with the route log at the end and via list at the
beginning) coming up with headers that can express what's going on,
but I think it can be done.  We probably need to work out a complete
solution and then see whether the complexity is worthwhile.

> Any particular reason not to do this?

The current spec says that the via list grows in the route header at
the front and the route log is appended to the back.  Then the via
list can just be swapped with the destination list to route the reply.
 We could say that both route log and via list are part of the same
structure at the end of the message, but then assembling the
destination list becomes significantly more complicated (and
unnecessarily so in the common case, unless we just view fragmented
messages as an entirely different format).

> I don't see the similarity of the problem with destination list - in the case of a destination list, the originator of the message deals with the largest size that message will get to - so, frageme…

The destination list could be longer than the first frag.  So at some
point, a peer will have to wait for the second frag and either
reassemble or just have all future peers buffer until they know where
to route the reply.

> Hmmm.. I am not sure about that.  I don't think keeping state is necessarily more complex.  Even with fragmentation, you'll need timeouts to handle the DoS attacks Ekr was talking about - so, in ei…

Sorry, I didn't word that clearly.  I'm concerned about the complexity
of doing on-the-fly refragmentation as the via list grows.  I think
keeping state is pretty simple.  It just a question of the amount of
state required and the potential for attacks.

So it seems like we're discussing 3 options:

1) add to/change the protocol so that on-the-fly refragmentation,
via-list appending, and destination list reassembly work
2) store forwarding state on the on-path peers so the via list doesn't
have to grow
3) reassemble the message at each hop.

any of those will work.  I think 2 and 3 are both rather simple to
specify and implement, although 2 has some state size concerns and 3
will slow down performance.  1 I think is harder to specify and
implement, but has fewer of the drawbacks of 2 and 3.

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Tue, 16 Dec 2008 16:58:44 -0500

In particular with NATs, you can't rely on fragments being received.

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Tue, 16 Dec 2008 17:01:02 -0500

Should have included a reference for that, since TSVWG actually
included a discussion in their recent UDP guidelines doc.

http://tools.ietf.org/html/rfc5405#section-3.2

Bruce

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Tue, 16 Dec 2008 14:23:56 -0800

Yep - I was just reminded of this same issue by one of our developers as well :) 

I like Salman's option of S1 with S4 (intermediate nodes maintain state for symmetric routing; fragmentation/reassembly done e2e).  Even for this, I think we would need to specify an error that can be returned by an intermediate node that may realize that the fragment is too big to be sent over the next link (similar to IPv6 PMTU discovery using the ICMPv6 Packet Too Big packet).   

We are then talking about always setting the DF bit for IPv4 and avoiding any fragmentation at IPv6 as well.  

Vidya

> Sent: Tuesday, December 16, 2008 2:01 PM
> To: Narayanan, Vidya
> Cc: [email-masked]
> >> Going back to the basics here - is there a reason we cannot let IP
> handle fragmentation for UDP messages and keep the added functionality
> to just reliability?
> >>
> >> Maybe I'm missing something fundamental - but, it seems like as
> inefficient as that may actually be, it might be the simplest solution
> to the problem.
> >>
> >> Thoughts?
> >>
> >> Vidya
> >>
> >>> > >> field and the via list.  If the fragment field's high order
> two
> >>> bits
> >>> > >> (via list not yet complete;via list complete).  It also
> requires
> >>> you
> >>> > >> it is just a bit easiert to do when it is only one header that
> has
> >>> > to
> >>> > >> be tracked in this way.
> >>> > >>                       regards,
> >>> > >>                               Ted
> >>> > >>

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Tue, 16 Dec 2008 22:12:08 -0500

Question for the group, do we have scenarios where we expect peers to
be have enough in-progress messages that they would exceed their
memory available for storing state?  This would have to involve high
bandwidth peers with low amounts of memory (or a very long end-to-end
timeout on transactions).

I want to like this solution, but I'm concerned that there may be
scenarios where it doesn't work.  I'm also concerned that buffer
parameters that work fine under normal overlay behavior would make it
very easy to DoS a peer with only a couple of compromised nodes in the
system.

Bruce

---

From: Song Haibin <[email-masked]>
Date: Wed, 17 Dec 2008 14:49:36 +0800

If we must use symmetric routing, then I also think s1 or s4 would be
better.

However, I have some additional thought, that there are routing modes that
we need not to use the via-list or route-list, such as overlay native
routing.

Best Regards,
Haibin
Email: [email-masked]
Skype: alexsonghw

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
>Narayanan, Vidya
>Sent: Wednesday, December 17, 2008 6:24 AM
>To: Bruce Lowekamp
>Cc: [email-masked]
>I like Salman's option of S1 with S4 (intermediate nodes maintain state for
>symmetric routing; fragmentation/reassembly done e2e).  Even for this, I
think
>we would need to specify an error that can be returned by an intermediate
node
>that may realize that the fragment is too big to be sent over the next link
>(similar to IPv6 PMTU discovery using the ICMPv6 Packet Too Big packet).
>
>We are then talking about always setting the DF bit for IPv4 and avoiding
any
>fragmentation at IPv6 as well.
>
>Vidya
>

---

From: jiangxingfeng <[email-masked]>
Date: Wed, 17 Dec 2008 15:17:53 +0800

> Yeah, unfortunately, the growth is an issue and I don't think the above method
> can be guaranteed to work.  Short of the sending nodes being able to estimate
> the size of the overlay and hence extrapolate the expected number of entries
> in a via list and adjust the message size accordingly, we may have a problem.

IMHO, some statistics data from diagnostic procedure may be helpful for a sending node to estimate the possible hops for the request to be sent. For example, in Chord, the peer can periodically to send ping message to collect the hops needed to random keys which are located in difference scope in the circle. With this statistics data in mind, if a node wants to send a request keyed by key A, it can estimate the most accurate hops. More statistics data collected, more accurate number of the possible hops. OTOH, the peer also could record the maximum hop number, which is also be helpful to avoid future fragmentation. 

> Well, you are, however, potentially increasing the lookup latency.  The via
> list is probably the only reason that an intermediate node may be required to
> fragment the message.  An alternative might be for each node to maintain state
> about the previous hop instead of including a via list. 

My concern about the state maintaining mechanism for symmetric recursive is still security issues. If a malicious peer controls a couple of peers, it can let peer A sends a great number of requests which is destined to peer B. Upon receiving the request, the peer B won't give the response intentionally. In this case, all intermediate peers are full of state which could be only be cleared by timeout, so that the overlay will experience the DoS.  Am I missing something?

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 10:34:34 -0500

> IMHO, some statistics data from diagnostic procedure may be helpful for a sending node to estimate the possible hops for the request to be sent. For example, in Chord, the peer can periodically to…

Unfortunately, it's growth of the via list that's the biggest concern
here, so using diagnostics to solve the problem is hard since all
those messages have via lists (and you have no guarantee that all of
the vias will fit in the first frag even if you put nothing else in
it.

> My concern about the state maintaining mechanism for symmetric recursive is still security issues. If a malicious peer controls a couple of peers, it can let peer A sends a great number of requests…

No, that was the security concern I had in my last response, and I
agree with you.  After further thought, I don't believe we can require
storing return path state as the solution, however, there is another
option I think will work in all cases.

Here's my proposal.  There are two options that work that don't
require major changes to the header structure to handle corner cases.
 Basically, I think that in most cases storing state will be OK
(except when you're under attack).  However, since we're prohibiting
large messages from the overlay (or at least not supporting them now),
really, hop-by-hop reassembly isn't that bad anyway.  Almost all
messages will be 2 or 3 frags on the typical (1500 MTU) network.

A peer using UDP (or other) for an overlay link protocol MUST either
maintain return path state or perform hop-by-hop reassembly.   It is
RECOMMENDED that a peer be configured with a maximum amount of state
it is willing to maintain for return paths for messages, and if that
amount is exceeded, fall back to hop-by-hop reassembly.

In defining the UDP overlay link protocol, the spec will say that a
peer fragmenting a message MUST NOT interleave other messages with the
fragments, and for reassembly will specify a maximum number of
out-of-order packets that must be buffered before discarding the
partial message.

(more careful wording of the two paragraphs is required, but I think
that captures the core)

That way, any peer is allowed to reassemble, and that can be done with
a finite amount of buffer space, so that approach is safe from attack.
 Storing return path state is a slight optimization that can be done
when space is available to store return state.

There's a corner case where a peer doing reassembly after several hops
of peers storing state might see more interleaving packets that have
built up on the intermediate hops.  However, the hop-by-hop ACKs will
take care of that.

Bruce

---

From: Ted Hardie <[email-masked]>
Date: Wed, 17 Dec 2008 09:10:37 -0800

>amount is exceeded, fall back to hop-by-hop reassembly.

First off, I've never been a fan of having to have two code paths where
one will do.  This seems to say that return path state is preferred
but hop-by-hop reassembly works in all cases.  Why is the trade-off
preferring return path state enough to overcome the ick factor
of having to maintain two code paths and switch between them?

>out-of-order packets that must be buffered before discarding the

This seems to guarantee that a packet requiring fragmentation MUST
create head of line blocking until all fragments are sent.   What
are the cases where interleaving messages might have occurred?

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 12:52:18 -0500

> of having to maintain two code paths and switch between them?

Basically I view the return path state option as an optimization.  If
you want to optimize away the performance penalty of doing reassembly,
you can, but I think the extra code is purely optional.  From a spec
level, I'm happy with that because I think it allows the simple
single-path implementation to work fine, and those who wish to add
multiple code paths to tune are free to do so.

> are the cases where interleaving messages might have occurred?

I was thinking of in-network reordering being the only problem here.
For short messages, I don't think HoL blocking is a concern here.  If
it becomes a concern, I think we're into the realm we need to look at
for dealing with larger messages.  (With relatively small messages
being sent out at line rate, even if an implementation was to not do
HoL blocking internally, the OS would still buffer the same amount, so
it's something of a shell game here.  Separate topic of whether we
need to have congestion control in the overlay link protocol.)

Bruce

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Dec 2008 13:53:19 -0500 (EST)

Unless, overlay and nodes can somehow enforce message size, we cannot 
assume minimal size messages (2-3 frags).

The return path state is simply a back pointer to the node (IP address, 
message identifier) from which the message was received.

The concern about return path state is that it may tremendously increase 
the use of memory because:
  1. a significant portion of inprogress messages timeout wasting memory.
  2. peers are under DoS so that there a lot of inprogress messages.

However, for fragmentation:
  (1) 1. is still a problem.
  (2) peers can also be under DoS using fragmentation.
      a) A peer(s) try to store a large data object or
      b) send many messages within the desired fragment count (2 or 3) to
       chew up memory space at the next hop.

For return path state, a solution to 2. 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.

For fragmentation, a solution to (2-a) is that nodes limit the number 
of maximum fragments per message. However, that does not address (2-b).

(2-b) requires the same scheme as for return path state, i.e., 
rate-limit and ask the exceeding sender to perform ROUTE-QUERY.

Reassembly is still e2e.

It is not clear to me that space-wise, why per-hop reassembly of 2-3 1500 
bytes segment is better than storing a <10 byte message identifier 
and a 4-byte IP address of the node from which the message was received.

Observe that return-path state or via-lists are required to maintain 
symmetric routing. However, it is not clear to me why this should be a 
MUST. If sender->destination routing is done on object-ID and 
destination->sender routing is done on sender ID, then there is no need 
for via-lists or return-path states. Such scheme utilizes existing 
connections between peers.

-salman

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Wed, 17 Dec 2008 11:14:49 -0800

I agree with Salman here.  I also agree with Ted in that introducing options when it is really not needed is a bad thing.  I don't see the logic of avoiding DoS attacks with hop-by-hop fragmentation and reassembly.  Nodes can be subject to DoS attacks either way.  And, this won't be the first time we'd be designing protocols that have to deal with state exhaustion attacks.  

I suggest we stick to keeping return path state and talk about DoS attack mitigation strategies in the document. 

Vidya 

> Behalf Of Salman Abdul Baset
> Sent: Wednesday, December 17, 2008 10:53 AM
> To: Bruce Lowekamp
> Cc: [email-masked]

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 15:35:49 -0500

On Wed, Dec 17, 2008 at 1:53 PM, Salman Abdul Baset <[email-masked]> wrote:
>
> Unless, overlay and nodes can somehow enforce message size, we cannot assume
> minimal size messages (2-3 frags).
>

We decided in MSP that we will require that. In fact, overlay config
already restricts resource size.  Technically it doesn't currently
apply to messages, but we had clear consensus in MSP that we would do
so.

(more below)

> The concern about return path state is that it may tremendously increase the
> use of memory because:
> For return path state, a solution to 2. 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.
>
> For fragmentation, a solution to (2-a) is that nodes limit the number of
> maximum fragments per message. However, that does not address (2-b).
>
> (2-b) requires the same scheme as for return path state, i.e., rate-limit
> and ask the exceeding sender to perform ROUTE-QUERY.
>
> Reassembly is still e2e.
>
> bytes segment is better than storing a <10 byte message identifier and a
> 4-byte IP address of the node from which the message was received.
>

The implication of the requirement that a peer MUST NOT interleave one
message with another is that the amount of buffer required for
reassembly is capped per connection.  It's # of connections * MTU *
max tolerated out-of-order arrival (which for TCP for example is 4).
That's a deterministic amount of space that scales per connection, so
it's pretty small.

> symmetric routing. However, it is not clear to me why this should be a MUST.
> If sender->destination routing is done on object-ID and destination->sender
> routing is done on sender ID, then there is no need for via-lists or
> return-path states. Such scheme utilizes existing connections between peers.

This has been discussed repeatedly on the mailing list and the
discussion is in the appendix of the base draft.  Please refer to
those other discussions.

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 15:46:11 -0500

You're right that there's always a need for DoS mitigation, but we
need to make the protocol immune from attacks when we can.  I believe
per-hop reassembly provides a way to eliminate one significant avenue
for DoS attacks, and there is a compatible optimization strategy for
those who wish to do a more complex implementation with associated DoS
mitigation.  Admittedly, there are still other attacks.  But with
static sized buffers, this seems to eliminate a big one to me.

Bruce

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Dec 2008 16:12:05 -0500 (EST)

> That's a deterministic amount of space that scales per connection, so

This approach creates head-of-line blocking. The storage space is needed 
for reordering but more importantly, the space is needed to completely 
reassemble the fragmented message at every hop as per above scheme.

Per-hop reassembly has been brought up in the context of small number of 
fragments (2-3) but what is this small really? Is 10 fragments small? Is 
20 fragments small?

> discussion is in the appendix of the base draft.  Please refer to

Indeed. My point was to highlight routing mode tradeoff in the context 
of fragmentation discussion.

-s

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Wed, 17 Dec 2008 15:51:11 -0800

> Sent: Wednesday, December 17, 2008 12:46 PM
> To: Narayanan, Vidya
> Cc: Salman Abdul Baset; [email-masked]
> need to make the protocol immune from attacks when we can.  

That's not how security solutions should be designed.  Addressing threats without an analysis of the risk of the threat, burden on the attacker, impact of the attack and effectiveness vs complexity of solutions is not useful.   

> I believe
> for DoS attacks, 

I don't believe so.  We need to design protocols that are robust and have some ways to mitigate DoS attacks (cannot really eliminate DoS) that have high impact.  In this case, per-hop reassembly actually does not even effectively mitigate the attack - one could be consuming resources by sending more and more fragments.  Consider the case when a sender (attacker) starts with a large via list already - even if there were bounds on the size of the actual message, this is possible.   

> and there is a compatible optimization strategy for
> mitigation.  

Providing options increases the complexity of the protocol and this is certainly not a place where I see the need for options.  The DoS mitigation techniques will be needed regardless and that is always optional. 

Vidya

> Admittedly, there are still other attacks.  But with
> > I agree with Salman here.  I also agree with Ted in that introducing
> options when it is really not needed is a bad thing.  I don't see the
> logic of avoiding DoS attacks with hop-by-hop fragmentation and
> reassembly.  Nodes can be subject to DoS attacks either way.  And, this
> won't be the first time we'd be designing protocols that have to deal
> with state exhaustion attacks.
> >
> > I suggest we stick to keeping return path state and talk about DoS
> attack mitigation strategies in the document.
> >
> > Vidya
> >
> >>       b) send many messages within the desired fragment count (2 or
> 3)
> >> to

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 19:33:22 -0500

> That's not how security solutions should be designed.  Addressing threats without an analysis of the risk of the threat, burden on the attacker, impact of the attack and effectiveness vs complexity…

I'm quite confident you don't mean that designing a protocol that
isn't subject to certain attacks is a bad thing.

In terms of a threat analysis, obviously it's nothing formal, but
what's been in this thread so far is that any entity authorized to
send messages across the overlay can send an arbitrary number of
messages through a given peer, consuming as much state as the rate at
which they are able to send messages times the timeout for that state.
 The impact is fairly obvious, and we haven't reached consensus on the
effectiveness or complexity of the solutions yet.

> I don't believe so.  We need to design protocols that are robust and have some ways to mitigate DoS attacks (cannot really eliminate DoS) that have high impact.  In this case, per-hop reassembly ac…

Remember that requiring peers to not interleave messages severely
restricts the amount of buffer space required (to essentially max
message size + max out of order (10 is very reasonable) * MTU per
connection.   Obviously there can be an attack on network resources,
but it's true that you can DoS any node in the Internet by flooding it
with random data.  That's not a protocol-specific attack.

> Providing options increases the complexity of the protocol and this is certainly not a place where I see the need for options.  The DoS mitigation techniques will be needed regardless and that is a…

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.

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 19:35:39 -0500

On Wed, Dec 17, 2008 at 4:12 PM, Salman Abdul Baset <[email-masked]> wrote:
> This approach creates head-of-line blocking. The storage space is needed for
> reordering but more importantly, the space is needed to completely
> fragments (2-3) but what is this small really? Is 10 fragments small? Is 20
> fragments small?
>

Like I said, consensus at MSP was to restrict the size of the messages
in order to avoid needing to address the impact of HoL blocking and
the other issues created by large messages.  The max size would be
determined by overlay configuration.   If you believe the base
protocol needs to address large message issues such as HoL blocking,
please start a new thread to propose that.

Bruce

>>> MUST.
> Indeed. My point was to highlight routing mode tradeoff in the context of
> fragmentation discussion.
>
> -s
>
>

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 17 Dec 2008 19:48:53 -0500 (EST)

> 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.

-s

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Wed, 17 Dec 2008 17:04:50 -0800

<snip>

> with random data.  That's not a protocol-specific attack.

Exactly.  And, given that this is possible, it does not make sense to provide point solutions to mitigate DoS attacks.  If there are multiple ways of launching an attack, mitigating it in one place achieves nothing. 
 
> using reassembly as a fall-back strategy.

But, the hop-by-hop reassembly does not quite mitigate the attack.  Timers and any limits on number of messages from a given node are required in both cases.  The buffer size for keeping forwarding state will be lower than that required for fragments and the timers for the former will be longer than the latter.  However, as a function of memory, they amount to more or less the same thing.  The per hop reassembly unnecessarily removes the ability to have a windowed protocol. I can't see how it is useful. 

Vidya

---

From: jiangxingfeng <[email-masked]>
Date: Thu, 18 Dec 2008 09:09:43 +0800

> > IMHO, some statistics data from diagnostic procedure may be helpful for a
> sending node to estimate the possible hops for the request to be sent. For
> example, in Chord, the peer can periodically to send ping message to collect
> the hops needed to random keys which are located in difference scope in the
> circle. With this statistics data in mind, if a node wants to send a request
> keyed by key A, it can estimate the most accurate hops. More statistics data
> collected, more accurate number of the possible hops. OTOH, the peer also could
> record the maximum hop number, which is also be helpful to avoid future
> fragmentation.
> >
> 

DRR or RPR proposed in relay draft do not require via-list to route the response, so the diagnostic message can rely on DRR or RPR to be routed.

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 22:27:40 -0500

On Wed, Dec 17, 2008 at 7:48 PM, Salman Abdul Baset <[email-masked]> wrote:
> 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

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Wed, 17 Dec 2008 22:38:16 -0500

> Exactly.  And, given that this is possible, it does not make sense to provide point solutions to mitigate DoS attacks.  If there are multiple ways of launching an attack, mitigating it in one place…

I'm sorry, maybe I'm missing something, but my understanding of your
argument here is that since a node can always be subjected to a random
traffic flood, there's no point in defending against any other DoS
attack.  But the state space attack is much easier to launch than a
raw traffic flood, as it takes only a small UDP datagram to consume
each entry for 15 seconds.  From some rough calculations, that looks
like about 1MB of state per 1Mb of traffic generated through the peer.

> But, the hop-by-hop reassembly does not quite mitigate the attack.  Timers and any limits on number of messages from a given node are required in both cases.  The buffer size for keeping forwarding…

I tried to work through some numbers in my response to Salman, but I
think there are some misunderstandings here.  The hop-by-hop
reassembly requires no timers or limits on the number of messages from
a given node.  That simplification comes from the prohibition on
interleaving fragments from multiple messages.  In that sense, it's
much cleaner.

So right now I'm assuming it doesn't prohibit a windowed protocol
because I'm assuming that a windowed protocol would be implemented
either as an entirely separate overlay link protocol or by decomposing
a larger message into smaller messages that are routed across the
existing links protocols.

Bruce

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Thu, 18 Dec 2008 17:05:07 -0800

I think the math on this needs to be revisited.  Here's a shot at it: 

Assuming uniform distribution of objects and queries, an effective storage of X*N is not valid for a functional overlay, simply because not every node will route through a particular node. Rather, O(log N) would be the right order of messages routed through a given node. If we think about X * (E+G), then G is O(log n). However, at E >> O(log N), the overlay is not going to be functional anyway and that is not the case under discussion.

Sticking to your calculation model, the total amount of memory for storing routing state would be Transaction ID + return connection + source Node ID + timeout. For the source node ID field, you don't actually need to store all the 128 bits, since you only maintain log N connections.  You could just do with log (N = 2500) bits ~ 12 ~ 2 bytes of information. This alone would reduce the total storage cost to 18 bytes. Accounting for a 15second timer (which, btw, I think is too long), this gives a total of 27K for message state and around 8K for the NodeID counter. This leads us to a total of 35K and even with 50% overhead each on the hash and data structure (which also seems too high), to around 70K (compared to the 220K you indicate below).

Along the same lines, for the hop-by-hop reassembly approach, we have 5K + 5*1500 = 12500 (12.5K) and with log N connections (~12 with N = 2500), we get a total requirement of 150K. This is atleast twice as worse. Also, I am not sure I understand the reasoning as to why there is 50% overhead in the first case compared to no overhead for the hop-by-hop reassembly case. If no overhead is taken into consideration, then the hop-by-hop reassembly would be four times worse.  Also, we have to include the via list in the calculation for the hop-by-hop reassembly approach and this makes it worse.  

With this, I'm not seeing a case for per-hop reassembly of messages.  In fact, I don't even think there is a need to put an upper bound on the number of in-progress messages a node can have at any given time.  Also, if anything, the buffer exhaustion attack that you seem to be worried about is more feasible with per-hop reassembly.  

Vidya

> Sent: Wednesday, December 17, 2008 7:28 PM
> To: Salman Abdul Baset
> Cc: Narayanan, Vidya; [email-masked]
> messages from

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Thu, 18 Dec 2008 17:16:58 -0800

> >
> > Exactly.  And, given that this is possible, it does not make sense to
> provide point solutions to mitigate DoS attacks.  If there are multiple
> ways of launching an attack, mitigating it in one place achieves
> nothing.
> >
> 

Sorry, perhaps what I wrote wasn't clear.  The buffer exhaustion attack is accomplished in several ways, including when a large amount of traffic is sent to a node.  Plus, please see my earlier email on the math - I think that the attack is actually easier when intermediate nodes are reassembling fragments. 

> interleaving fragments from multiple messages.  

That is a big cost to pay in terms of latency.  After some real data from experience, IPv6 corrected the shortcoming of IPv4 in the fragmentation case - overlay routing is not all that different from IP routing in terms of the architecture and function (differences in magnitude and capabilities of the devices may even out).  So, both in terms of the threat model and tradeoffs like these in fragmentation, we should be learning from the same lessons.  Of course, even going with the math points to the same thing to me. 

Vidya

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Thu, 18 Dec 2008 23:50:02 -0500

I think it's enough that the buffer space is close.  The exact details
of the amount of state stored for return path are fairly variable
depending on specifics of the deployment.  Plus, in all cases the
amount of state required doesn't appear to be terribly significant
compared to the space required to store the messages waiting for the
hop-by-hop ACK.

> Assuming uniform distribution of objects and queries, an effective storage of X*N is not valid for a functional overlay, simply because not every node will route through a particular node. Rather,…

Yes, X * N is worst case, though none of the rest of my numbers
depended on that.  Interesting question how large E can get here
before other aspects of the overlay break down.

> Sticking to your calculation model, the total amount of memory for storing routing state would be Transaction ID + return connection + source Node ID + timeout. For the source node ID field, you do…

You need the source node id when you're counting number of
transactions you're storing per source, which is Salman's proposal.

> Along the same lines, for the hop-by-hop reassembly approach, we have 5K + 5*1500 = 12500 (12.5K) and with log N connections (~12 with N = 2500), we get a total requirement of 150K. This is atleast…

Hash tables have relatively high overhead compared to the overhead for
the reassembly buffers.

> With this, I'm not seeing a case for per-hop reassembly of messages.  In fact, I don't even think there is a need to put an upper bound on the number of in-progress messages a node can have at any…

I'm sorry, but I don't see anything above that leads to any of these
conclusions.  Why is it not necessary to bound the number of messages
a peer sends through you?  Wasn't that the method Salman proposed for
detecting when you're under attack?  How can a buffer exhaustion
attack possibly apply to a technique with statically sized buffers?

Ultimately, the motivation for hop-by-hop reassembly is that it is
provably immune to this particular attack, with a slight latency
penalty.  Storing return path state is harder to bound the size of the
state under "normal" conditions and requires probabilistic detection
of attacks.  False positives degrade overlay performance
significantly.  (Open to suggestions of other ways of detecting and
mitigating attacks.)

For an internet-scale protocol, I really prefer provably immune to
probabilistic arguments with poor behaviors under unanticipated
non-attack scenarios.  I was actually one of the strong proponents of
the original text for end-to-end reassembly only, but the need to
store return path somewhere (in the message or on the peers) makes
this a fundamentally different problem than internet routing.

In most scenarios, the return state storage will work fine and have
better performance.  I'm just not convinced it has good failure
behavior.  If performance is the focus, the best performance that I
can see is still to store return path state and fall back to
reassembly under attack.

Bruce

---

From: "Wei Gengyu" <[email-masked]>
Date: Fri, 19 Dec 2008 14:54:48 +0800

Hi,

Is it right that Preventing RELOAD fragmentation is acturally to prevent IP 
fragmentation?

If via-list is so long that the RELOAD message is bigger than MTU,
is it possible to have an short identifer represented as via-list aftering 
routing across overlay?

Regards,

Gengyu

----- Original Message ----- 
From: "Bruce Lowekamp" <[email-masked]>
To: "Narayanan, Vidya" <[email-masked]>
Cc: "Salman Abdul Baset" <[email-masked]>; <[email-masked]>
Sent: Friday, December 19, 2008 12:50 PM
Subject: Re: [P2PSIP] RELOAD fragmentation

>> Assuming uniform distribution of objects and queries, an effective 
>> storage of X*N is not valid for a functional overlay, simply because not 
>> every node will route through a particular node. Rather, O(log N) would 
>> be the right order of messages routed through a given node. If we think 
>> about X * (E+G), then G is O(log n). However, at E >> O(log N), the 
>> overlay is not going to be functional anyway and that is not the case 
>> under discussion.
>>
>
>> Sticking to your calculation model, the total amount of memory for 
>> storing routing state would be Transaction ID + return connection + 
>> source Node ID + timeout. For the source node ID field, you don't 
>> actually need to store all the 128 bits, since you only maintain log N 
>> connections.  You could just do with log (N = 2500) bits ~ 12 ~ 2 bytes 
>> of information. This alone would reduce the total storage cost to 18 
>> bytes. Accounting for a 15second timer (which, btw, I think is too long), 
>> this gives a total of 27K for message state and around 8K for the NodeID 
>> counter. This leads us to a total of 35K and even with 50% overhead each 
>> on the hash and data structure (which also seems too high), to around 70K 
>> (compared to the 220K you indicate below).
>>
>
>> Along the same lines, for the hop-by-hop reassembly approach, we have 5K 
>> + 5*1500 = 12500 (12.5K) and with log N connections (~12 with N = 2500), 
>> we get a total requirement of 150K. This is atleast twice as worse. Also, 
>> I am not sure I understand the reasoning as to why there is 50% overhead 
>> in the first case compared to no overhead for the hop-by-hop reassembly 
>> case. If no overhead is taken into consideration, then the hop-by-hop 
>> reassembly would be four times worse.  Also, we have to include the via 
>> list in the calculation for the hop-by-hop reassembly approach and this 
>> makes it worse.
>>
>
>> With this, I'm not seeing a case for per-hop reassembly of messages.  In 
>> fact, I don't even think there is a need to put an upper bound on the 
>> number of in-progress messages a node can have at any given time.  Also, 
>> if anything, the buffer exhaustion attack that you seem to be worried 
>> about is more feasible with per-hop reassembly.
>>
>

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Fri, 19 Dec 2008 00:19:42 -0800

> Sent: Thursday, December 18, 2008 8:50 PM
> To: Narayanan, Vidya
> I think it's enough that the buffer space is close.  

The point in my email is that it isn't.  But, I agree that it isn't significant either way. 

>The exact details
> storage of X*N is not valid for a functional overlay, simply because
> not every node will route through a particular node. Rather, O(log N)
> would be the right order of messages routed through a given node. If we
> think about X * (E+G), then G is O(log n). However, at E >> O(log N),
> the overlay is not going to be functional anyway and that is not the
> case under discussion.
> >
> 

When E gets large enough that the overlay operation gets disrupted, we have bigger problems than buffer space exhaustion.  So, that is a question that will have several dimensions to it.  

> bytes. Accounting for a 15second timer (which, btw, I think is too
> long), this gives a total of 27K for message state and around 8K for
> the NodeID counter. This leads us to a total of 35K and even with 50%
> overhead each on the hash and data structure (which also seems too
> high), to around 70K (compared to the 220K you indicate below).
> >
> 

I don't believe that a node needs to be counting the number of transactions per source.  That is not the only way a node can be under attack anyway - a misbehaving finger may route everything it gets through a given node irrespective of the destination - in which case, the source of the message tells you nothing. The only thing a node can realistically do is determine when it is serving beyond its capacity and then kick in some mitigation or backoff techniques. 

> > Along the same lines, for the hop-by-hop reassembly approach, we have
> 5K + 5*1500 = 12500 (12.5K) and with log N connections (~12 with N =
> 2500), we get a total requirement of 150K. This is atleast twice as
> worse. Also, I am not sure I understand the reasoning as to why there
> is 50% overhead in the first case compared to no overhead for the hop-
> by-hop reassembly case. If no overhead is taken into consideration,
> then the hop-by-hop reassembly would be four times worse.  Also, we
> have to include the via list in the calculation for the hop-by-hop
> reassembly approach and this makes it worse.
> >
> 
> > With this, I'm not seeing a case for per-hop reassembly of messages.
> In fact, I don't even think there is a need to put an upper bound on
> the number of in-progress messages a node can have at any given time.
> Also, if anything, the buffer exhaustion attack that you seem to be
> worried about is more feasible with per-hop reassembly.
> >
> 
> detecting when you're under attack?  

I should have caught that before and clarified it - but, as I mentioned above, it is not an effective way of detecting an attack and I don't think it buys anything.  

> How can a buffer exhaustion

I guess what you mean is buffers that don't grow with messages - but, this comes at a cost of preventing message interleaving, which is steep.  However, even with that, you have to accommodate for a variable buffer size, given that you don't know what the size of the via list may be.  You need to account for a malicious node continuing to send more and more fragments - which brings timers into the picture again, upon expiry of which, the fragments need to be purged.  Also, if you want to allow interleaving, the problem gets worse.  

> penalty.  

I don't think we can conclude that the impact to latency is "slight".  I actually think it would be significant enough to be undesirable.  

> Storing return path state is harder to bound the size of the
> non-attack scenarios.  

I'm not sure I understand the poor behavior in non-attack scenarios.  A little more explanation around that sentence would help me.   

> I was actually one of the strong proponents of

Not really.  It isn't fundamentally different from LSRR in IPv4 or the Source Routing Header in IPv6. Of course, there are plenty of other issues with IPv6 Type 0 RH that are not relevant here :) 

> can see is still to store return path state and fall back to

I don't think the failure behaviors are that different and I really think we are trying to find a solution for an attack in one particular scenario, while the attack can be launched in several other ways.  The performance differences in my mind make the end-to-end reassembly the best option. 

Vidya 

> >> >> of hop-by-hop reassembly.  For that matter, I'd be interested in
> a
> >> DoS
> >> so 128 + 32, so 20 bytes goes to 40 bytes.  That's 100K for this
> data
> >> structure.
> >>