NodeTable using modified kademlia for node discovery and preference. More...

#include <NodeTable.h>

Inheritance diagram for dev::p2p::NodeTable:

Collaboration diagram for dev::p2p::NodeTable:

Classes
struct	NodeBucket

Public Types
enum	NodeRelation { Unknown = 0, Known }

enum	DiscoverType { Random = 0 }

Public Member Functions
	NodeTable (ba::io_service &_io, KeyPair const &_alias, NodeIPEndpoint const &_endpoint, bool _enabled=true)
	Constructor requiring host for I/O, credentials, and IP Address and port to listen on. More...

	~NodeTable ()

void	setEventHandler (NodeTableEventHandler *_handler)
	Set event handler for NodeEntryAdded and NodeEntryDropped events. More...

void	processEvents ()
	Called by implementation which provided handler to process NodeEntryAdded/NodeEntryDropped events. Events are coalesced by type whereby old events are ignored. More...

std::shared_ptr< NodeEntry >	addNode (Node const &_node, NodeRelation _relation=NodeRelation::Unknown)
	Add node. Node will be pinged and empty shared_ptr is returned if node has never been seen or NodeID is empty. More...

std::list< NodeID >	nodes () const
	Returns list of node ids active in node table. More...

unsigned	count () const
	Returns node count. More...

std::list< NodeEntry >	snapshot () const
	Returns snapshot of table. More...

bool	haveNode (NodeID const &_id)
	Returns true if node id is in node table. More...

Node	node (NodeID const &_id)
	Returns the Node to the corresponding node id or the empty Node if that id is not found. More...

Static Public Member Functions
static unsigned	distance (NodeID const &_a, NodeID const &_b)
	Returns distance based on xor metric two node ids. Used by NodeEntry and NodeTable. More...

Private Types
using	NodeSocket = UDPSocket< NodeTable, 1280 >

using	TimePoint = std::chrono::steady_clock::time_point
	Steady time point. More...

using	NodeIdTimePoint = std::pair< NodeID, TimePoint >

using	EvictionTimeout = std::pair< NodeIdTimePoint, NodeID >
	First NodeID (NodeIdTimePoint) may be evicted and replaced with second NodeID. More...

Private Member Functions
void	ping (NodeIPEndpoint _to) const
	Used to ping endpoint. More...

void	ping (NodeEntry *_n) const
	Used ping known node. Used by node table when refreshing buckets and as part of eviction process (see evict). More...

NodeEntry	center () const
	Returns center node entry which describes this node and used with dist() to calculate xor metric for node table nodes. More...

std::shared_ptr< NodeEntry >	nodeEntry (NodeID _id)
	Used by asynchronous operations to return NodeEntry which is active and managed by node table. More...

void	doDiscover (NodeID _target, unsigned _round=0, std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>> _tried=std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>>())
	Used to discovery nodes on network which are close to the given target. More...

std::vector< std::shared_ptr< NodeEntry > >	nearestNodeEntries (NodeID _target)
	Returns nodes from node table which are closest to target. More...

void	evict (std::shared_ptr< NodeEntry > _leastSeen, std::shared_ptr< NodeEntry > _new)
	Asynchronously drops _leastSeen node if it doesn't reply and adds _new node, otherwise _new node is thrown away. More...

void	noteActiveNode (Public const &_pubk, bi::udp::endpoint const &_endpoint)
	Called whenever activity is received from a node in order to maintain node table. More...

void	dropNode (std::shared_ptr< NodeEntry > _n)
	Used to drop node when timeout occurs or when evict() result is to keep previous node. More...

NodeBucket &	bucket_UNSAFE (NodeEntry const *_n)
	Returns references to bucket which corresponds to distance of node id. More...

void	onReceived (UDPSocketFace *, bi::udp::endpoint const &_from, bytesConstRef _packet)
	General Network Events. More...

void	onDisconnected (UDPSocketFace *)
	Called by m_socket when socket is disconnected. More...

void	doCheckEvictions ()
	Tasks. More...

void	doDiscovery ()
	Looks up a random node at interval. More...

Private Attributes
std::chrono::milliseconds const	c_evictionCheckInterval = std::chrono::milliseconds(75)
	Intervals. More...

std::chrono::milliseconds const	c_reqTimeout = std::chrono::milliseconds(300)
	How long to wait for requests (evict, find iterations). More...

std::chrono::milliseconds const	c_bucketRefresh = std::chrono::milliseconds(7200)
	Refresh interval prevents bucket from becoming stale. [Kademlia]. More...

std::unique_ptr< NodeTableEventHandler >	m_nodeEventHandler
	Event handler for node events. More...

Node	m_node
	This node. LOCK x_state if endpoint access or mutation is required. Do not modify id. More...

Secret	m_secret
	This nodes secret key. More...

Mutex	x_nodes
	LOCK x_state first if both locks are required. Mutable for thread-safe copy in nodes() const. More...

std::unordered_map< NodeID, std::shared_ptr< NodeEntry > >	m_nodes
	Known Node Endpoints. More...

Mutex	x_state
	LOCK x_state first if both x_nodes and x_state locks are required. More...

std::array< NodeBucket, s_bins >	m_state
	State of p2p node network. More...

Mutex	x_evictions
	LOCK x_evictions first if both x_nodes and x_evictions locks are required. More...

std::deque< EvictionTimeout >	m_evictions
	Eviction timeouts. More...

Mutex	x_pubkDiscoverPings
	LOCK x_nodes first if both x_nodes and x_pubkDiscoverPings locks are required. More...

std::unordered_map< bi::address, TimePoint >	m_pubkDiscoverPings
	List of pending pings where node entry wasn't created due to unkown pubk. More...

Mutex	x_findNodeTimeout

std::list< NodeIdTimePoint >	m_findNodeTimeout
	Timeouts for pending Ping and FindNode requests. More...

std::shared_ptr< NodeSocket >	m_socket
	Shared pointer for our UDPSocket; ASIO requires shared_ptr. More...

NodeSocket *	m_socketPointer
	Set to m_socket.get(). Socket is created in constructor and disconnected in destructor to ensure access to pointer is safe. More...

DeadlineOps	m_timers
	this should be the last member - it must be destroyed first More...

Static Private Attributes
static unsigned const	s_addressByteSize = h256::size
	Constants for Kademlia, derived from address space. More...

static unsigned const	s_bits = 8 * s_addressByteSize
	Denoted by n in [Kademlia]. More...

static unsigned const	s_bins = s_bits - 1
	Size of m_state (excludes root, which is us). More...

static unsigned const	s_maxSteps = boost::static_log2<s_bits>::value
	Max iterations of discovery. (discover) More...

static unsigned const	s_bucketSize = 16
	Chosen constants. More...

static unsigned const	s_alpha = 3
	Denoted by in [Kademlia]. Number of concurrent FindNode requests. More...

Friends
std::ostream &	operator<< (std::ostream &_out, NodeTable const &_nodeTable)

Detailed Description

NodeTable using modified kademlia for node discovery and preference.

Node table requires an IO service, creates a socket for incoming UDP messages and implements a kademlia-like protocol. Node requests and responses are used to build a node table which can be queried to obtain a list of potential nodes to connect to, and, passes events to Host whenever a node is added or removed to/from the table.

Thread-safety is ensured by modifying NodeEntry details via shared_ptr replacement instead of mutating values.

NodeTable accepts a port for UDP and will listen to the port on all available interfaces.

[Optimization]

Todo:

serialize evictions per-bucket

store evictions in map, unit-test eviction logic

store root node in table

encapsulate discover into NetworkAlgorithm (task)

expiration and sha3(id) 'to' for messages which are replies (prevents replay)

cache Ping and FindSelf

firewall

^ s_bitsPerStep = 8; // Denoted by b in [Kademlia]. Bits by which address space is divided.

[Networking]

Todo:: eth/upnp/natpmp/stun/ice/etc for public-discovery

[Protocol]

Todo:: optimize knowledge at opposite edges; eg, s_bitsPerStep lookups. (Can be done via pointers to NodeBucket)

Definition at line 121 of file NodeTable.h.

Member Typedef Documentation

using dev::p2p::NodeTable::EvictionTimeout = std::pair<NodeIdTimePoint, NodeID>

private

First NodeID (NodeIdTimePoint) may be evicted and replaced with second NodeID.

Definition at line 127 of file NodeTable.h.

using dev::p2p::NodeTable::NodeIdTimePoint = std::pair<NodeID, TimePoint>

private

Definition at line 126 of file NodeTable.h.

using dev::p2p::NodeTable::NodeSocket = UDPSocket<NodeTable, 1280>

private

Definition at line 124 of file NodeTable.h.

using dev::p2p::NodeTable::TimePoint = std::chrono::steady_clock::time_point

private

Steady time point.

Definition at line 125 of file NodeTable.h.

Member Enumeration Documentation

enum dev::p2p::NodeTable::DiscoverType

Enumerator
Random

Definition at line 131 of file NodeTable.h.

enum dev::p2p::NodeTable::NodeRelation

Enumerator
Unknown
Known

Definition at line 130 of file NodeTable.h.

Constructor & Destructor Documentation

NodeTable::NodeTable	(	ba::io_service &	_io,
		KeyPair const &	_alias,
		NodeIPEndpoint const &	_endpoint,
		bool	_enabled = `true`
	)

Constructor requiring host for I/O, credentials, and IP Address and port to listen on.

Definition at line 43 of file NodeTable.cpp.

Here is the call graph for this function:

NodeTable::~NodeTable ( )

Definition at line 68 of file NodeTable.cpp.

Here is the call graph for this function:

Member Function Documentation

shared_ptr< NodeEntry > NodeTable::addNode	(	Node const &	_node,
		NodeRelation	_relation = `NodeRelation::Unknown`
	)

Add node. Node will be pinged and empty shared_ptr is returned if node has never been seen or NodeID is empty.

Definition at line 80 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

NodeTable::NodeBucket & NodeTable::bucket_UNSAFE ( NodeEntry const * _n )

private

Returns references to bucket which corresponds to distance of node id.

Warning: Only use the return reference locked x_state mutex.

Definition at line 392 of file NodeTable.cpp.

Here is the caller graph for this function:

NodeEntry dev::p2p::NodeTable::center ( ) const

inlineprivate

Returns center node entry which describes this node and used with dist() to calculate xor metric for node table nodes.

Definition at line 202 of file NodeTable.h.

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned dev::p2p::NodeTable::count ( ) const

inline

Returns node count.

Definition at line 153 of file NodeTable.h.

Here is the caller graph for this function:

static unsigned dev::p2p::NodeTable::distance	(	NodeID const &	_a,
		NodeID const &	_b
	)

inlinestatic

Returns distance based on xor metric two node ids. Used by NodeEntry and NodeTable.

Definition at line 138 of file NodeTable.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doCheckEvictions ( )

private

Tasks.

Called by evict() to ensure eviction check is scheduled to run and terminates when no evictions remain. Asynchronous.

Definition at line 531 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doDiscover	(	NodeID	_target,
		unsigned	_round = `0`,
		std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>>	_tried = `std::shared_ptr<std::set<std::shared_ptr<NodeEntry>>>()`
	)

private

Used to discovery nodes on network which are close to the given target.

Sends s_alpha concurrent requests to nodes nearest to target, for nodes nearest to target, up to s_maxSteps rounds.

Definition at line 155 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doDiscovery ( )

private

Looks up a random node at interval.

Definition at line 562 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::dropNode ( std::shared_ptr< NodeEntry > _n )

private

Used to drop node when timeout occurs or when evict() result is to keep previous node.

Definition at line 377 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::evict	(	std::shared_ptr< NodeEntry >	_leastSeen,
		std::shared_ptr< NodeEntry >	_new
	)

private

Asynchronously drops _leastSeen node if it doesn't reply and adds _new node, otherwise _new node is thrown away.

Definition at line 308 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool dev::p2p::NodeTable::haveNode ( NodeID const & _id )

inline

Returns true if node id is in node table.

Definition at line 159 of file NodeTable.h.

Here is the caller graph for this function:

vector< shared_ptr< NodeEntry > > NodeTable::nearestNodeEntries ( NodeID _target )

private

Returns nodes from node table which are closest to target.

Definition at line 217 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Node NodeTable::node ( NodeID const & _id )

Returns the Node to the corresponding node id or the empty Node if that id is not found.

Definition at line 138 of file NodeTable.cpp.

Here is the caller graph for this function:

shared_ptr< NodeEntry > NodeTable::nodeEntry ( NodeID _id )

private

Used by asynchronous operations to return NodeEntry which is active and managed by node table.

Definition at line 149 of file NodeTable.cpp.

Here is the caller graph for this function:

list< NodeID > NodeTable::nodes ( ) const

Returns list of node ids active in node table.

Definition at line 118 of file NodeTable.cpp.

Here is the caller graph for this function:

void NodeTable::noteActiveNode	(	Public const &	_pubk,
		bi::udp::endpoint const &	_endpoint
	)

private

Called whenever activity is received from a node in order to maintain node table.

Definition at line 325 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void dev::p2p::NodeTable::onDisconnected ( UDPSocketFace * )

inlineprivatevirtual

Called by m_socket when socket is disconnected.

Reimplemented from dev::p2p::UDPSocketEvents.

Definition at line 234 of file NodeTable.h.

void NodeTable::onReceived	(	UDPSocketFace *	,
		bi::udp::endpoint const &	_from,
		bytesConstRef	_packet
	)

privatevirtual

General Network Events.

Called by m_socket when packet is received.

Implements dev::p2p::UDPSocketEvents.

Definition at line 397 of file NodeTable.cpp.

Here is the call graph for this function:

void NodeTable::ping ( NodeIPEndpoint _to ) const

private

Used to ping endpoint.

Definition at line 292 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::ping ( NodeEntry * _n ) const

private

Used ping known node. Used by node table when refreshing buckets and as part of eviction process (see evict).

Definition at line 302 of file NodeTable.cpp.

Here is the call graph for this function:

void NodeTable::processEvents ( )

Called by implementation which provided handler to process NodeEntryAdded/NodeEntryDropped events. Events are coalesced by type whereby old events are ignored.

Definition at line 74 of file NodeTable.cpp.

void dev::p2p::NodeTable::setEventHandler ( NodeTableEventHandler * _handler )

inline

Set event handler for NodeEntryAdded and NodeEntryDropped events.

Definition at line 141 of file NodeTable.h.

list< NodeEntry > NodeTable::snapshot ( ) const

Returns snapshot of table.

Definition at line 127 of file NodeTable.cpp.

Here is the caller graph for this function:

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	_out,
		NodeTable const &	_nodeTable
	)

friend

Definition at line 270 of file NodeTable.h.

Member Data Documentation

std::chrono::milliseconds const dev::p2p::NodeTable::c_bucketRefresh = std::chrono::milliseconds(7200)

private

Refresh interval prevents bucket from becoming stale. [Kademlia].

Definition at line 187 of file NodeTable.h.

std::chrono::milliseconds const dev::p2p::NodeTable::c_evictionCheckInterval = std::chrono::milliseconds(75)

private

Intervals.

Interval at which eviction timeouts are checked.

Definition at line 185 of file NodeTable.h.

std::chrono::milliseconds const dev::p2p::NodeTable::c_reqTimeout = std::chrono::milliseconds(300)

private

How long to wait for requests (evict, find iterations).

Definition at line 186 of file NodeTable.h.

std::deque<EvictionTimeout> dev::p2p::NodeTable::m_evictions

private

Eviction timeouts.

Definition at line 256 of file NodeTable.h.

std::list<NodeIdTimePoint> dev::p2p::NodeTable::m_findNodeTimeout

private

Timeouts for pending Ping and FindNode requests.

Definition at line 262 of file NodeTable.h.

Node dev::p2p::NodeTable::m_node

private

This node. LOCK x_state if endpoint access or mutation is required. Do not modify id.

Definition at line 246 of file NodeTable.h.

std::unique_ptr<NodeTableEventHandler> dev::p2p::NodeTable::m_nodeEventHandler

private

Event handler for node events.

Definition at line 244 of file NodeTable.h.

std::unordered_map<NodeID, std::shared_ptr<NodeEntry> > dev::p2p::NodeTable::m_nodes

private

Known Node Endpoints.

Definition at line 250 of file NodeTable.h.

std::unordered_map<bi::address, TimePoint> dev::p2p::NodeTable::m_pubkDiscoverPings

private

List of pending pings where node entry wasn't created due to unkown pubk.

Definition at line 259 of file NodeTable.h.

Secret dev::p2p::NodeTable::m_secret

private

This nodes secret key.

Definition at line 247 of file NodeTable.h.

std::shared_ptr<NodeSocket> dev::p2p::NodeTable::m_socket

private

Shared pointer for our UDPSocket; ASIO requires shared_ptr.

Definition at line 264 of file NodeTable.h.

NodeSocket* dev::p2p::NodeTable::m_socketPointer

private

Set to m_socket.get(). Socket is created in constructor and disconnected in destructor to ensure access to pointer is safe.

Definition at line 265 of file NodeTable.h.

std::array<NodeBucket, s_bins> dev::p2p::NodeTable::m_state

private

State of p2p node network.

Definition at line 253 of file NodeTable.h.

DeadlineOps dev::p2p::NodeTable::m_timers

private

this should be the last member - it must be destroyed first

Definition at line 267 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_addressByteSize = h256::size

staticprivate

Constants for Kademlia, derived from address space.

Size of address type in bytes.

Definition at line 172 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_alpha = 3

staticprivate

Denoted by in [Kademlia]. Number of concurrent FindNode requests.

Definition at line 180 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bins = s_bits - 1

staticprivate

Size of m_state (excludes root, which is us).

Definition at line 174 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bits = 8 * s_addressByteSize

staticprivate

Denoted by n in [Kademlia].

Definition at line 173 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bucketSize = 16

staticprivate

Chosen constants.

Denoted by k in [Kademlia]. Number of nodes stored in each bucket.

Definition at line 179 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_maxSteps = boost::static_log2<s_bits>::value

staticprivate

Max iterations of discovery. (discover)

Definition at line 175 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_evictions

private

LOCK x_evictions first if both x_nodes and x_evictions locks are required.

Definition at line 255 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_findNodeTimeout

private

Definition at line 261 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_nodes

mutableprivate

LOCK x_state first if both locks are required. Mutable for thread-safe copy in nodes() const.

Definition at line 249 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_pubkDiscoverPings

private

LOCK x_nodes first if both x_nodes and x_pubkDiscoverPings locks are required.

Definition at line 258 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_state

mutableprivate

LOCK x_state first if both x_nodes and x_state locks are required.

Definition at line 252 of file NodeTable.h.

The documentation for this class was generated from the following files:

src/cpp-ethereum/libp2p/NodeTable.h
src/cpp-ethereum/libp2p/NodeTable.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation