Understanding how to manage message routing direction in P2P Chord/Pastry-like networks

Question

This is a question about a large scalable P2P networking approach: logical ring net ovrlay.

Consider the context of P2P networking. There are N computers that are connected everyone to each other through a ring. Every node has a routing table memorizing the predecessor and the successor node. This is the simplest case when routing tables store only a predecessor and a successor. Every node is provided with an id which is a number. The ring is organized so that ascending numbers are assigned in clockwose direction.

So we can have a situation like this: * - 12 - 13 - 45 - 55 - 180 - 255 - * This network has 6 nodes and they are connected in circle.

When a node must send a message to another node, the routing tables are used, if the generic node has an incoming message, it looks at the dest address and, if not in his routing table, the successor or predecesor will be up to route it.

Now let's consider this example. In my simple network, node 13 wants to send a message to node 255. Since every node can see only a predecessor and a successor, every node is not able to consider the global network, in P2P, in fact, a node can see only a part of the net. So node 13 has a decision to take: where to route the message (since the destination is not in its neighbourhood)? Does the message have to be sent to 45 or to 12? (clockwise or counterclockwise?).

Well, obviously, sending to 12 is a better decision, but how is node 13 able to know this?

The simplest solution would be: always route clockwise, but in this case a very near node will be reached in so much time..... while it was behind the corner....

How to handle this?

PS: There are solution like Fingering applied to clockwise routing based approaches. Fingering puts in routing table other addresses in order to create jump links... This is a solution that can be used but with clockwise routing only...

http://en.wikipedia.org/wiki/File:Chord_route.png

I would like to know a good solution in order to find the right routing direction... does it exist? How does Chord handle this?

Thank you.

Answer 1

If every node remember link to the next one, the second one, the fourth one, the eighth one, and so on, then it takes only log(n) time to find any node. I believe that this is fast enough to not consider if you should go cw or ccw.