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
_______________________________________________
P2PSIP mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/p2psip
