Struct routing::RoutingTable
[−]
[src]
pub struct RoutingTable<T: Binary + Clone + Copy + Debug + Default + Hash + Xorable> { /* fields omitted */ }
A routing table to manage contacts for a node.
It maintains a list of sections (identified by a Prefix<T>
), each with a
list node identifiers of type T
(e.g. XorName
) representing connected
peer nodes, and provides algorithms for routing messages.
See the crate documentation for details.
Methods
impl<T: Binary + Clone + Copy + Debug + Default + Hash + Xorable> RoutingTable<T>
[src]
fn new(our_name: T, min_section_size: usize) -> Self
Creates a new RoutingTable
.
fn add_prefixes(&mut self, prefixes: Vec<Prefix<T>>) -> Result<(), Error>
Adds the list of Prefix
es as empty sections.
Called once a node has been approved by its own section and is given its peers' tables. Expects the current sections to be empty.
fn our_prefix(&self) -> &Prefix<T>
Returns the Prefix
of our section
fn our_section(&self) -> &BTreeSet<T>
Returns our own section, including our own name.
fn all_sections(&self) -> BTreeMap<Prefix<T>, BTreeSet<T>>
Returns the whole routing table, including our section and our name
fn section_with_prefix(&self, prefix: &Prefix<T>) -> Option<&BTreeSet<T>>
Returns the section with the given prefix, if any (includes own name if is own section)
fn len(&self) -> usize
Returns the total number of entries in the routing table, excluding our own name.
fn is_empty(&self) -> bool
Is the table empty? (Returns true
if no nodes besides our own are known;
empty sections are ignored.)
fn min_section_size(&self) -> usize
Returns the minimum section size.
fn min_split_size(&self) -> usize
Returns the number of nodes which need to exist in each subsection of a given section to allow it to be split.
fn has(&self, name: &T) -> bool
Returns whether the table contains the given name
.
fn iter(&self) -> Iter<T>
Iterates over all nodes known by the routing table, excluding our own name.
fn network_size_estimate(&self) -> (u64, bool)
Compute an estimate of the size of the network from the size of our routing table.
Return (estimate, exact), with exact = true iff we have the whole network in our routing table.
fn other_prefixes(&self) -> BTreeSet<Prefix<T>>
Collects prefixes of all sections known by the routing table other than ours into a
BTreeSet
.
fn prefixes(&self) -> BTreeSet<Prefix<T>>
Collects prefixes of all sections known by the routing table into a BTreeSet
.
fn close_names(&self, name: &T) -> Option<BTreeSet<T>>
If our section is the closest one to name
, returns all names in our section including
ours, otherwise returns None
.
fn other_close_names(&self, name: &T) -> Option<BTreeSet<T>>
If our section is the closest one to name
, returns all names in our section excluding
ours, otherwise returns None
.
fn is_closest(&self, name: &T, count: usize) -> bool
Are we among the count
closest nodes to name
?
fn closest_names(&self, name: &T, count: usize) -> Option<Vec<&T>>
Returns the count
closest entries to name
in the routing table, including our own name,
sorted by ascending distance to name
. If we are not close, returns None
.
fn other_closest_names(&self, name: &T, count: usize) -> Option<Vec<&T>>
Returns the count-1
closest entries to name
in the routing table, excluding
our own name, sorted by ascending distance to name
- or None
, if our name
isn't among count
names closest to name
.
fn is_in_our_section(&self, name: &T) -> bool
Returns true if name
is in our section (including if it is our own name).
fn need_to_add(&self, name: &T) -> Result<(), Error>
Returns Ok(())
if the given contact should be added to the routing table.
Returns Err
if name
already exists in the routing table, or it doesn't fall within any
of our sections, or it's our own name.
fn should_join_our_section(&self, name: &T) -> Result<(), Error>
Returns Err(Error::PeerNameUnsuitable)
if name
is not within our section, or
Err(Error::AlreadyExists)
if name
is already in our table.
fn validate_joining_node(&self, name: &T) -> Result<(), Error>
Validates a joining node's name.
fn add(&mut self, name: T, want_to_merge: bool) -> Result<bool, Error>
Adds a contact to the routing table.
Returns Err
if name
already existed in the routing table, or it doesn't fall within any
of our sections, or it's our own name. Otherwise it returns Ok(true)
if the addition
succeeded and should cause our section to split or Ok(false)
if the addition succeeded and
shouldn't cause a split.
fn split(&mut self, prefix: Prefix<T>) -> (Vec<T>, Option<Prefix<T>>)
Splits a section.
If the section exists in the routing table, it is split, otherwise this function is a no-op. If any of the sections don't satisfy the invariant any more (i.e. only differ in one bit from our own prefix), they are removed and those contacts are returned. If the split is happening to our own section, our new prefix is returned in the optional field.
fn add_prefix(&mut self, prefix: Prefix<T>) -> Vec<T>
Adds the given prefix to the routing table, merging or splitting if necessary. Returns the entries that have been dropped.
fn remove(&mut self, name: &T) -> Result<RemovalDetails<T>, Error>
Removes a contact from the routing table.
If no entry with that name is found, Err(Error::NoSuchPeer)
is returned. Otherwise, the
entry is removed from the routing table and RemovalDetails
is returned. See that struct's
docs for further info.
fn should_merge(&self,
we_want_to_merge: bool,
they_want_to_merge: bool)
-> Option<OwnMergeDetails<T>>
we_want_to_merge: bool,
they_want_to_merge: bool)
-> Option<OwnMergeDetails<T>>
If our section is required to merge, returns the details to initiate merging.
Merging is required if any section has dropped below the minimum size and can only restore it by ultimately merging with us.
However, merging happens in simple steps, each of which involves only two sections. If. e.g.
section 1
drops below the minimum size, and the other sections are 01
, 001
and 000
,
then this will return true
only in the latter two. Once they are merged and have
established all their new connections, it will return true
in 01
and 00
. Only after
that, the section 0
will merge with section 1
.
fn merge_own_section(&mut self,
merge_details: OwnMergeDetails<T>)
-> OwnMergeState<T>
merge_details: OwnMergeDetails<T>)
-> OwnMergeState<T>
When a merge of our own section is triggered (either from our own section or a neighbouring one) this function handles the incoming merge details from the peers within the merging sections.
The actual merge of the section is only done once all expected merging sections have
provided details. See the docs for OwnMergeState
for full details of the return value.
fn merge_other_section(&mut self,
merge_details: OtherMergeDetails<T>)
-> BTreeSet<T>
merge_details: OtherMergeDetails<T>)
-> BTreeSet<T>
Merges all existing compatible sections into the new one defined by merge_details.prefix
.
Our own section is not included in the merge.
The appropriate targets (all contacts from merge_details.sections
which are not currently
held in the routing table) are returned so the caller can establish connections to these
peers and subsequently add them.
fn targets(&self,
dst: &Authority<T>,
exclude: T,
route: usize)
-> Result<BTreeSet<T>, Error>
dst: &Authority<T>,
exclude: T,
route: usize)
-> Result<BTreeSet<T>, Error>
Returns a collection of nodes to which a message for the given Authority
should be sent
onwards. In all non-error cases below, the returned collection will have the members of
exclude
removed, possibly resulting in an empty set being returned.
If the destination is an
Authority::Section
:- if our section is the closest on the network (i.e. our section's prefix is a prefix of the destination), returns all other members of our section; otherwise
- returns the
route
-th closest member of the RT to the target
If the destination is an
Authority::PrefixSection
:- if the prefix is compatible with our prefix and is fully-covered by prefixes in our RT, returns all members in these prefixes except ourself; otherwise
- if the prefix is compatible with our prefix and is not fully-covered by prefixes in
our RT, returns
Err(Error::CannotRoute)
; otherwise - returns the
route
-th closest member of the RT to the lower bound of the target prefix
If the destination is a group (
ClientManager
,NaeManager
orNodeManager
):- if our section is the closest on the network (i.e. our section's prefix is a prefix of the destination), returns all other members of our section; otherwise
- returns the
route
-th closest member of the RT to the target
If the destination is an individual node (
ManagedNode
orClient
):- if our name is the destination, returns an empty set; otherwise
- if the destination name is an entry in the routing table, returns it; otherwise
- returns the
route
-th closest member of the RT to the target
Returns whether we are a part of the given authority.
fn get_section(&self, name: &T) -> Option<&BTreeSet<T>>
Returns the section matching the given name
, if present.
Includes our own name in the case that our prefix matches name
.
fn our_name(&self) -> &T
Returns our name.
fn is_valid(&self) -> bool
Returns whether the Routing invariant is currently held for this table or not.
fn find_section_prefix(&self, name: &T) -> Option<Prefix<T>>
Returns the prefix of the section in which name
belongs, or None
if there is no such
section in the routing table.
fn assign_to_min_len_prefix(&self, name: &T) -> T
Returns name
modified so that it belongs to one of the known prefixes with minimal bit
length, favouring our own prefix if it is one of the shortest.
Trait Implementations
impl<T: Clone + Binary + Clone + Copy + Debug + Default + Hash + Xorable> Clone for RoutingTable<T>
[src]
fn clone(&self) -> RoutingTable<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<T: Eq + Binary + Clone + Copy + Debug + Default + Hash + Xorable> Eq for RoutingTable<T>
[src]
impl<T: PartialEq + Binary + Clone + Copy + Debug + Default + Hash + Xorable> PartialEq for RoutingTable<T>
[src]
fn eq(&self, __arg_0: &RoutingTable<T>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, __arg_0: &RoutingTable<T>) -> bool
This method tests for !=
.