Each key has a location, the routing key. Each node also has a location. When a node receives a request for a key, if it does not have the key, it routes it onward. The path it takes is chosen as follows. First, the request may be instantly rejected if pInstantReject is currently greater than zero (part of load management). Second, if the request is out of hops to live, it may be dropped. Third, the original requester, backed off peers, and peers which have recently failed to retrieve the key in question are declared ineligible for routing. Finally, among eligible nodes, the request is routed to the node whose location is closest to the data location. (If FOAF routing is enabled, then the request is routed to the peer which has the closest peer to the key -- that is, we route based on the locations of the friends of a friend (FOAF) rather than the locations of our friends (peers).) In other words, routing is a simple greedy routing algorithm, with relatively simple load balancing. The sophistication in the routing comes from the underlying network topology rather than the algorithm: greedy routing works well, provided that the connections between nodes have the right balance between connections to nodes with nearby locations and connections to nodes with distant locations.
Requests are not flood routed: each incoming request is sent to only one peer. If that peer rejects the request, then it may instead be routed to a different peer, but it will never be routed to more than one peer at a time.
Requests have a hops to live counter. At each hop, the counter is decremented. However, for security reasons, the HTL counter is only probabilistically decremented when htl = maxhtl. This protects the original requester: a node receiving a request with htl = maxhtl does not know whether it is receiving it from the original requester or not. Similarly, to protect the node which actually has the data, requests are only probabilistically stopped at htl = 0. At present (build 1226), the probability of decrementing at maxhtl is 0.5, and the probability of stopping at htl = 0 is 0.25. The maximum htl value is 18.
Inserts are routed in the same fashion.
The overall idea is that requests and inserts for the same key will get routed to similar portions of the keyspace, and so the request will arrive at a node that has the data.
See also
NetworkTopology
Darknet
Opennet
Sink
