Crate kademlia_routing_table [−] [src]

A routing table to manage contacts for a node in a Kademlia distributed hash table.

This crate uses the Kademlia mechanism for routing messages in a peer-to-peer network, and generalises it to provide redundancy in every step: for senders, messages in transit and receivers. It contains the routing table and the functionality to decide via which of its entries to route a message, but not the networking functionality itself.

Addresses and distance functions

Nodes in the network are addressed with a XorName, a 512-bit unsigned integer. The XOR distance between two nodes with addresses x and y is x ^ y. This distance function has the property that no two points ever have the same distance from a given point, i. e. if x ^ y == x ^ z, then y == z. This property allows us to define the close group of an address as the GROUP_SIZE closest nodes to that address, guaranteeing that the close group will always have exactly GROUP_SIZE members (unless, of course, the whole network has less than GROUP_SIZE nodes).

The routing table is associated with a node with some name x, and manages a number of contacts to other nodes, sorting them into up to 512 buckets, depending on their XOR distance from x:

  • If 2512 > x ^ y >= 2511, then y is in bucket 0.
  • If 2511 > x ^ y >= 2510, then y is in bucket 1.
  • If 2510 > x ^ y >= 2509, then y is in bucket 2.
  • ...
  • If 2 > x ^ y >= 1, then y is in bucket 511.

Equivalently, y is in bucket n if the longest common prefix of x and y has length n, i. e. the first binary digit in which x and y disagree is the (n + 1)-th one. We call the length of the remainder, without the common prefix, the bucket distance of x and y. Hence x and y have bucket distance 512 - n if and only if y belongs in bucket number n.

The bucket distance is coarser than the XOR distance: Whenever the bucket distance from y to x is less than the bucket distance from z to x, then y ^ x < z ^ x. But not vice-versa: Often y ^ x < z ^ x, even if the bucket distances are equal. The XOR distance ranges from 0 to 2512 (exclusive), while the bucket distance ranges from 0 to 512 (inclusive).

Guarantees

The routing table provides functions to decide, for a message with a given destination, which nodes in the table to pass the message on to, so that it is guaranteed that:

  • If the destination is the address of a node, the message will reach that node after at most 511 hops.
  • Otherwise the message will reach every member of the close group of the destination address, i. e. all GROUP_SIZE nodes in the network that are XOR-closest to that address, and each node knows whether it belongs to that group.
  • Each node in a given address' close group is connected to each other node in that group. In particular, every node is connected to its own close group.
  • The number of total hop messages created for each message is at most PARALLELISM * 512.
  • For each node there are at most 512 * GROUP_SIZE other nodes in the network for which it can obtain the IP address, at any point in time.

However, to be able to make these guarantees, the routing table must be filled with sufficiently many contacts. Specifically, the following invariant must be ensured:

Whenever a bucket n has fewer than GROUP_SIZE entries, it contains all nodes in the network with bucket distance 512 - n.

The user of this crate therefore needs to make sure that whenever a node joins or leaves, all affected nodes in the network update their routing tables accordingly.

Resilience against malfunctioning nodes

In each hop during routing, messages are passed on to PARALLELISM other nodes, so that even if PARALLELISM - 1 nodes between the source and destination fail, they are still successfully delivered.

The concept of close groups exists to provide resilience even against failures of the source or destination itself: If every member of a group tries to send the same message, it will arrive even if some members fail. And if a message is sent to a whole group, it will arrive in most, even if some of them malfunction.

Close groups can thus be used as inherently redundant authorities in the network that messages can be sent to and received from, using a consensus algorithm: A message from a group authority is considered to be legitimate, if at least QUORUM_SIZE group members have sent a message with the same content.

Structs

AddedNodeDetails

This is returned by RoutingTable::add_node if a new node has been added.
DroppedNodeDetails

This is returned by RoutingTable::drop_connection if a node was dropped.
RoutingTable

A routing table to manage contacts for a node.

Enums

Destination

A message destination.

Constants

GROUP_SIZE

The size of a close group.
PARALLELISM

The number of nodes a message is sent to in each hop for redundancy.

Traits

ContactInfo

Contact info about a node in the network.