Crate kademlia_routing_table [−] [src]
A routing table to manage connections 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
connections 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 for routing
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 connections. Specifically, the following invariant must be ensured:
Whenever a bucket
n
has fewer thanGROUP_SIZE
entries, it contains all nodes in the network with bucket distance512 - 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 |
DroppedNodeDetails |
This is returned by |
NodeInfo |
A routing table entry representing a node and the connections to that node. |
RoutingTable |
A routing table to manage connections for a node. |
Enums
Destination |
A message destination. |
HopType |
Specifies the number of times we have already passed on a particular message. |
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
HasName |
A trait for anything that has a |