Routing

Stephen Oliver edited this page Mar 30, 2017 · 1 revision

Note: this page needs verification for accuracy, it is based on build 1226 of Freenet 0.7.5.

Keys

Each Freenet key has a location, the routing key.

Nodes

Each node also has a location.

Requests

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:

  1. The request may be instantly rejected if pInstantReject is currently greater than zero (part of load management).

  2. If the request is out of hops to live, it may be dropped.

  3. 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.

HTL (Hops to Live)

Requests have a hops to live counter. At each hop, from one node to another, 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

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

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.