Pastry (DHT) - Routing

Routing

A packet can be routed to any address in the keyspace whether there is a peer with that node ID or not. The packet is routed toward its proper place on the circular ring and the peer whose node ID is closest to the desired destination will receive the packet. Whenever a peer receives a packet to route or wants to send a packet it first examines its leaf set and routes directly to the correct node if one is found. If this fails, the peer next consults its routing table with the goal of finding the address of a node which shares a longer prefix with the destination address than the peer itself. If the peer does not have any contacts with a longer prefix or the contact has died it will pick a peer from its contact list with the same length prefix whose node ID is numerically closer to the destination and send the packet to that peer. Since the number of correct digits in the address always either increases or stays the same — and if it stays the same the distance between the packet and its destination grows smaller — the routing protocol converges.