Subject: [P2PSIP] RELOAD Fragmentation - Take 2

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

Here is a attempt to see if we can support end-to-end reassembly without the need to maintain routing state.  Let's first take the case of via lists.  Instead of the via list containing the node ids of the intermediate nodes, if it is represented by a significantly smaller tag (say, a connection id) that only has relevance to the local node, we can drastically reduce the size of the via list.  For instance, something like 1-2bytes will be more than adequate to represent a connection id.  This would be a different form of a compressed via list.  This is also sufficient, since every node only needs to care about the first id on the destination list when it receives the message and that should correspond to its own tag on the corresponding via list.  

If we did the above, the growth of the via list should be insignificant (for normal routing with Olog(N) bounds).  If we then said that the source fragments the message, accommodating something in the order of 2 * log(N) bytes for via list growth, we should be able to expect it to work, barring issues due to varying MTUs.  It is also mainly an issue if the header itself grows to a size that requires fragmentation - however, this type of compressed via list should prevent that from happening.  

That said, we would deal with varying MTUs by using a mechanism analogous to IPv6 PMTU discovery (i.e., send an error to the source asking for further fragmentation). In this method, such multiple fragmentations should not be frequent anyway. 

Thoughts? 

Thanks,
Vidya

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

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Dec 2008 08:19:20 -0800

At Fri, 19 Dec 2008 00:20:37 -0800,
Narayanan, Vidya wrote:
> 
> Here is a attempt to see if we can support end-to-end reassembly
> without the need to maintain routing state.  Let's first take the
> case of via lists.  Instead of the via list containing the node ids
> of the intermediate nodes, if it is represented by a significantly
> smaller tag (say, a connection id) that only has relevance to the
> local node, we can drastically reduce the size of the via list.  For
> instance, something like 1-2bytes will be more than adequate to
> represent a connection id.  This would be a different form of a
> compressed via list.  This is also sufficient, since every node only
> needs to care about the first id on the destination list when it
> receives the message and that should correspond to its own tag on
> the corresponding via list.

This was actually one of the original designs for via lists and is
already permitted by the specification. Indeed, this is one of 
the major reasons to allow opaque via list entries.

That said, the sort of connection ID index you suggest isn't entirely
straightforward. you need to worry about connection ID reuse,
otherwise you can get collisions under any kind of instability.
For instance, Cullen suggested file descriptors would be a reasonable
implementation technique. However, because of the way UNIX systems use
file descriptors, when you close fd 5 and then do a new open, you tend
to get fd 5 again. If everyone is using file descriptors, it's not at
all unrealistic to expect a message to completely unwind the via list
before it eventually gets to the wrong origin destination.
This isn't to say that this problem can't be solved of course,
with judicious identifier assignment, checksums, etc., but I
suspect 1 byte and perhaps 2 will not be enough. 

A more robust approach would be to use a hash of the Node-ID
in the via list. You could use a much shorter hash but this
reduces the chance of collision drastically without having
to be clever about timeouts, etc.

Cullen and I at one point discussed another alternative: compressing
the Node-IDs themselves. The observation here is that with
common DHTs, the messages converge on the correct node, so
the Node-Ids in the via list rapidly get a common prefix.
You could probably use this to compress, though I don't have
calculations on how much improvement you get.

The bottom line, then, is that I don't think it's a good idea to
require one particular technique for via list compression. I
would need to think about whether it makes sense to design
a protocol on the assumption that every node will compress
via list entries. This does create inconveniences, including
making tracing packets through the network significantly harder.

> If we did the above, the growth of the via list should be
> insignificant (for normal routing with Olog(N) bounds). 

This doesn't solve the problem of route log growth, however.

-Ekr

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Fri, 19 Dec 2008 15:37:05 -0500

I'm not convinced that the extra expense of validating the return list
buys much.  Assuming that you do it with something smarter than just
the fd#, let's say it's a 16 bit identifier, use 8 or even 10 bits as
an index into a connection table and the remainder as a generation
identifier for what connection is in that slots, that should really
never result in the wrong path taken on the return.  Even if it does,
so what?  It's a rare failure that would waste a miniscule amount of
resources.

I personally think the via lists are much more important than the
route log, but do hate to lose rate log.  I guess the question for me
is whether route log is important enough to not do this, to require
multiple fragmentation options (seems undesireable), to append them
strictly to the end of messages, or to drop route log in favor of some
of the other diagnostic proposals.

I still believe that reassembly isn't nearly as expensive or as big a
change as it has been portrayed, but I want to work out some of those
issues in other threads.  Very short via list entries seem to have
potential for solving the biggest issues we've seen with
fragmentation, so I think we need to give serious analysis to what we
lose/gain if we adopt them.

Bruce

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Wed, 24 Dec 2008 12:26:40 -0800

I tend to agree with Bruce.  Also, I may have loosely used the term "connection id".  In essence, each node has an average of log(N) neighbors and it only needs to maintain an index for each one of its neighbors.  The node id can then be resolved from that index.  The index would be sufficient in the via-list, since it is only of local significance to each node.  I may be missing something about the collision that Ekr is talking about here. 

On the route log messages, I am actually in favor of removing that from the base draft and putting it into the diagnostics draft.  Also, I am not seeing the rationale for having the route logs be part of the header.  That said, if the route logging is inefficient due to repeated errors and re-fragmentation to accommodate the MTU issues, I don't think that is much of a problem. 

- Vidya

> -----Original Message-----
> From: Bruce Lowekamp [mailto:[email-masked]]
> Sent: Friday, December 19, 2008 12:37 PM
> To: Eric Rescorla
> Cc: Narayanan, Vidya; [email-masked]
> Subject: Re: [P2PSIP] RELOAD Fragmentation - Take 2
>