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]

Creates a new RoutingTable.

Adds the list of Prefixes 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.

Returns the Prefix of our section

Returns our own section, including our own name.

Returns the whole routing table, including our section and our name

Returns the section with the given prefix, if any (includes own name if is own section)

Returns the total number of entries in the routing table, excluding our own name.

Is the table empty? (Returns true if no nodes besides our own are known; empty sections are ignored.)

Returns the minimum section size.

Returns the number of nodes which need to exist in each subsection of a given section to allow it to be split.

Returns whether the table contains the given name.

Iterates over all nodes known by the routing table, excluding our own name.

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.

Collects prefixes of all sections known by the routing table other than ours into a BTreeSet.

Collects prefixes of all sections known by the routing table into a BTreeSet.

If our section is the closest one to name, returns all names in our section including ours, otherwise returns None.

If our section is the closest one to name, returns all names in our section excluding ours, otherwise returns None.

Are we among the count closest nodes to name?

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.

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.

Returns true if name is in our section (including if it is our own name).

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.

Returns Err(Error::PeerNameUnsuitable) if name is not within our section, or Err(Error::AlreadyExists) if name is already in our table.

Validates a joining node's name.

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.

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.

Adds the given prefix to the routing table, merging or splitting if necessary. Returns the entries that have been dropped.

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.

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.

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.

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.

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 or NodeManager):

    • 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 or Client):

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

Returns the section matching the given name, if present. Includes our own name in the case that our prefix matches name.

Returns our name.

Returns whether the Routing invariant is currently held for this table or not.

Returns the prefix of the section in which name belongs, or None if there is no such section in the routing table.

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]

Returns a copy of the value. Read more

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]

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

This method tests for !=.

impl<T: Binary + Clone + Copy + Debug + Default + Hash + Xorable> Binary for RoutingTable<T>
[src]

Formats the value using the given formatter.

impl<T: Binary + Clone + Copy + Debug + Default + Hash + Xorable> Debug for RoutingTable<T>
[src]

Formats the value using the given formatter.