Struct kademlia_routing_table::RoutingTable

pub struct RoutingTable<T: ContactInfo> { /* fields omitted */ }

A routing table to manage contacts for a node.

It maintains a list of T::Names representing connected peer nodes, and provides algorithms for routing messages.

See the crate documentation for details.

Methods

impl<T> RoutingTable<T> where
    T: ContactInfo,
    T::Name: PartialEq + Xorable, 

fn new(our_info: T, bucket_size: usize, extra_entries: usize) -> Self

Creates a new routing table for the node with the given info.

bucket_size specifies the minimum number of bucket entries: Whenever a new node joins the network which belongs to a bucket with < bucket_size entries, it must be added to that bucket. This guarantees that all nodes know which k-groups they belong to, for each k <= bucket_size.

In excess of bucket_size, extra_entries are considered desired in each bucket. After that, additional entries are considered unneeded: If both sides agree, they should disconnect.

fn add(&mut self, info: T) -> Option<AddedNodeDetails<T>>

Adds a contact to the routing table, or updates it.

Returns None if the contact already existed or was denied (see allow_connection). Otherwise it returns AddedNodeDetails.

fn need_to_add(&self, name: &T::Name) -> bool

Returns whether it is desirable to add the given contact to the routing table.

Returns false if adding the contact in question would not bring the routing table closer to satisfy the invariant. It returns true if and only if the new contact would be among the bucket_size closest nodes in its bucket.

fn remove_if_unneeded(&mut self, name: &T::Name) -> bool

Removes name from routing table and returns true if we no longer need to stay connected.

We should remain connected iff the entry is among the self.max_bucket_size closest nodes in its bucket or if we have any close groups in common with it.

fn allow_connection(&self, name: &T::Name) -> bool

Returns whether we can allow the given contact to connect to us.

The connection is allowed if:

• they already are one of our contacts,
• we need them in our routing table to satisfy the invariant or
• we are in the bucket_size-group of one of their bucket addresses.

fn remove(&mut self, name: &T::Name) -> Option<DroppedNodeDetails>

Removes the contact from the table.

If no entry with that name is found, None is returned. Otherwise, the entry is removed from the routing table and DroppedNodeDetails are returned.

fn target_nodes(
    &self,
    dst: Destination<T::Name>,
    hop: &T::Name,
    route: usize
) -> Vec<T>

Returns a collection of nodes to which a message should be sent onwards.

If the message is addressed at a group we are a member of, this returns all other members of that group.

If the message is addressed at an individual node that is directly connected to us, this returns the destination node.

If we are the individual recipient, it also returns an empty collection.

Otherwise it returns the n-th closest node to the target if route is n.

Arguments

• dst - The destination of the message.
• hop - The name of the node that relayed the message to us, or ourselves if we are the original sender.
• route - The route number.

fn is_recipient(&self, dst: Destination<T::Name>) -> bool

Returns whether the message is addressed to this node.

If this returns true, this node is either the single recipient of the message, or a member of the group authority to which it is addressed. It therefore needs to handle the message.

fn other_close_nodes(&self, name: &T::Name, group_size: usize) -> Option<Vec<T>>

Returns the other members of name's close group, or None if we are not a member of it.

fn close_nodes(&self, name: &T::Name, group_size: usize) -> Option<Vec<T>>

Returns the members of name's close group, or None if we are not a member of it.

fn is_close(&self, name: &T::Name, group_size: usize) -> bool

Returns true if there are fewer than GROUP_SIZE nodes in our routing table that are closer to name than we are.

In other words, it returns true whenever we cannot rule out that we might be among the group_size closest nodes to name.

If the routing table is filled in such a way that each bucket contains group_size elements unless there aren't enough such nodes in the network, then this criterion is actually sufficient! In that case, true is returned if and only if we are among the group_size closest node to name in the network.

fn len(&self) -> usize

Number of entries in the routing table.

fn is_empty(&self) -> bool

Returns true if there are no entries in the routing table.

fn clear(&mut self)

Removes all entries from the routing table.

fn our_name(&self) -> &T::Name

Returns the name of the node this routing table is for.

fn contains(&self, name: &T::Name) -> bool

Returns whether the node with this name is in the routing table.

fn bucket_size(&self) -> usize

Returns the bucket size constant, i. e. the minimum number of entries that need to be added to each bucket, if possible.

fn max_bucket_size(&self) -> usize

Returns the maximum bucket size constant, i. e. the number of entries above which bucket entries are considered unneeded.

fn get(&self, name: &T::Name) -> Option<&T>

Returns the contact associated with the given name.

fn bucket_len(&self, index: usize) -> usize

Returns the number of entries in the bucket with the given index.

fn bucket_count(&self) -> usize

Returns the number of buckets.

This is one more than the index of the bucket containing the closest peer, or 0 if the routing table is empty.

fn iter(&self) -> Iter<T>

Returns an iterator over all entries, sorted by distance.

fn closest_nodes_to(
    &self,
    target: &T::Name,
    n: usize,
    ourselves: bool
) -> Vec<T>

Returns the n nodes in our routing table that are closest to target.

Returns fewer than n nodes if the routing table doesn't have enough entries. If ourselves is true, this could potentially include ourselves. Otherwise, our own name is skipped.

fn is_in_any_close_group_with(
    &self,
    bucket_index: usize,
    group_size: usize
) -> bool

Returns whether we share any close groups with the nodes in the given bucket.

If the bucket is not full or we have less than group_size - 1 contacts with a greater bucket index, then for every node in that bucket there exists an address which both that node and our own node are in the close group of. In that case, the result is true.

Otherwise, no such address exists and false is returned.

impl<T: ContactInfo> RoutingTable<T> where
    T::Name: ContactInfo + Clone, 

fn to_names(&self) -> RoutingTable<T::Name>

Converts all entries to T::Names and returns a new RoutingTable with them.

Trait Implementations

impl<T: Debug + ContactInfo> Debug for RoutingTable<T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Clone + ContactInfo> Clone for RoutingTable<T>

fn clone(&self) -> RoutingTable<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Eq + ContactInfo> Eq for RoutingTable<T>

impl<T: PartialEq + ContactInfo> PartialEq for RoutingTable<T>

fn eq(&self, __arg_0: &RoutingTable<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &RoutingTable<T>) -> bool

This method tests for !=.