[p2p-hackers] Oceanstore's routing (was Re: [freenet-devl] updating with access control lists)

hal at finney.org hal at finney.org
Thu Mar 1 09:08:05 UTC 2001

Oskar writes:
> What I meant was going backwards. So if your node had label 012345 (base 6
> now), you would find the node on the network that was closest, maybe
> with label 012344 (it would be at the end of primary neighbor sequence
> for your id). Then you check it's backwards neighbors in the 6th
> level, ie those nodes that have it as a primary reference in the 6th
> level, and you have all the nodes with the same id as you to 5th, from
> which you can choose your primary references in the 6th level, and so on.

I see how this would work.  You are essentially enumerating all the nodes
in the network by picking one as the root and walking the tree down.
By itself this would be O(n), but you might be able to apply some
heuristics based on assumed locality in the tree, since nodes especially
in the lower branches are supposed to be physically close together.
That's where you need pruning the most since it is where the number of
nodes becomes large.

Thanks for the clarification -


More information about the P2p-hackers mailing list