XOR based routing table used for P2P networks such as a Kademlia DHT.
npm install xor-routing-table
Similar to k-buckets, but implemented using the simplifications described in https://github.com/ethereum/wiki/wiki/Kademlia-Peer-Selection
To understand the concept behind peer routing, DHTs, and the terms used here, I recommend reading the Kademlia DHT paper as well.
const RoutingTable =const randomBytes =// Create a new table that stores nodes "close" to the passed in id.// The id should be uniformily distributed, ie a hash, random bytes etc.const table =// Add a node to the routing tabletabletable// Get the 20 nodes "closest" to a passed in idconst closest = table
table = new RoutingTable(id, [options])
Create a new routing table.
id should be a Buffer that is uniformily distributed.
k: 20 // The max row size
bool = table.add(node)
Insert a new node.
node.id must be a Buffer of same length as
When inserting a node the XOR distance between the node and the table.id is
calculated and used to figure which table row this node should be inserted into.
true if the node could be added to the corresponding row or
false if not.
false is returned the onfullrow function is invoked for the corresponding row and node.
node = table.get(id)
Get a node from the table using its id. Returns
null if no node has the passed in
bool = table.has(id)
true if a node exists for the passed in
nodes = table.closest(id, [maxNodes])
Returns an array of the closest (in XOR distance) nodes to the passed in id.
id should be Buffer of same length as
table.id. Per default at max
nodes are returned, but this can be configured using the
This method is normally used in a routing context, i.e. figuring out which nodes in a DHT should store a value based on its id.
bool = table.remove(id)
Remove a node using its id. Returns
true if a node existed for the id and
was removed and
nodes = table.toArray()
Returns all nodes from table as an array. If you create a new routing table from these nodes it will be identical to the used here.
Emitted when a new row is added to the routing table. At max,
A fixed size array of all rows in the table. Normally you would not need to worry about accessing rows directly outside the row event.
For the row passed in the the
onfullrow function the following API exists.
The row index. Represents how many prefix bits are shared between nodes in the row and the table id.
A list of all the nodes in the row, sorted by their
Property set to null initially you can use if you want to store optional data on the row.
bool = row.add(node)
table.add but for a specific row. Only use this to add the
bool = row.remove(node)
table.remove but for a specific row. Only use this to remove the
"worst" node from the row when wanting to add the newNode.
Emitted when a new node is added to this row.
Emitted when a node has been removed from this row.
Emitted when a node wants to be added to this row, but the row is full (stores
When this happens you should check if any of the nodes already in the row (
"worse" than the passed node. If that is the case, remove the "worst" one and re-add the node passed in the arguments.
Various algorithms can be implemented to handle full rows, which is why the routing table leaves most of this logic up to the user. These kind of algorithms include adding the rejected node to a cache and wait for another node in the row to be removed before trying to insert it again, or using an LRU cache to determine which node already in the row has been heard from yet.