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 protected]] > Sent: Friday, December 19, 2008 12:37 PM > To: Eric Rescorla > Cc: Narayanan, Vidya; [email protected] > Subject: Re: [P2PSIP] RELOAD Fragmentation - Take 2 > > 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 > > > On Fri, Dec 19, 2008 at 11:19 AM, Eric Rescorla > <[email protected]> wrote: > > 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 > > _______________________________________________ P2PSIP mailing list [email protected] https://www.ietf.org/mailman/listinfo/p2psip
