class DEVp2p::Kademlia::RoutingTable

Attributes

node[R]

Public Class Methods

new(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 9
def initialize(node)
  @node = node
  @buckets = [KBucket.new(0, MAX_NODE_ID)]
end

Public Instance Methods

add(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 35
def add(node)
  raise ArgumentError, 'cannot add self' if node == @node

  bucket = bucket_by_node node
  eviction_candidate = bucket.add node

  if eviction_candidate # bucket is full
    # split if the bucket has the local node in its range or if the depth
    # is not congruent to 0 mod B
    if bucket.in_range?(@node) || bucket.splitable?
      split_bucket bucket
      return add(node) # retry
    end

    # nothing added, ping eviction_candidate
    return eviction_candidate
  end

  nil # successfully added to not full bucket
end
bucket_by_node(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 60
def bucket_by_node(node)
  @buckets.each do |bucket|
    if node.id < bucket.right
      raise KademliaRoutingError, "mal-formed routing table" unless node.id >= bucket.left
      return bucket
    end
  end

  raise KademliaNodeNotFound
end
buckets_by_distance(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 76
def buckets_by_distance(node)
  raise ArgumentError, 'node must be Node' unless node.is_a?(Node)
  buckets_by_id_distance(node.id)
end
buckets_by_id_distance(id) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 71
def buckets_by_id_distance(id)
  raise ArgumentError, 'id must be integer' unless id.is_a?(Integer)
  @buckets.sort_by {|b| b.id_distance(id) }
end
buckets_count() click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 89
def buckets_count
  @buckets.size
end
delete(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 56
def delete(node)
  bucket_by_node(node).delete node
end
each(&block) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 15
def each(&block)
  @buckets.each do |b|
    b.each(&block)
  end
end
idle_buckets() click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 26
def idle_buckets
  t_idle = Time.now - IDLE_BUCKET_REFRESH_INTERVAL
  @buckets.select {|b| b.last_updated < t_idle }
end
include?(node) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 81
def include?(node)
  bucket_by_node(node).include?(node)
end
neighbours(node, k=K) click to toggle source

sorting by bucket.midpoint does not work in edge cases, buld a short list of ‘k * 2` nodes and sort and shorten it.

TODO: can we do better?

# File lib/devp2p/kademlia/routing_table.rb, line 99
def neighbours(node, k=K)
  raise ArgumentError, 'node must be Node or node id' unless node.instance_of?(Node) || node.is_a?(Integer)

  node = node.id if node.instance_of?(Node)

  nodes = []
  buckets_by_id_distance(node).each do |bucket|
    bucket.nodes_by_id_distance(node).each do |n|
      if n != node
        nodes.push n
        break if nodes.size == k * 2
      end
    end
  end

  nodes.sort_by {|n| n.id_distance(node) }[0,k]
end
neighbours_within_distance(id, distance) click to toggle source

naive correct version simply compares all nodes

# File lib/devp2p/kademlia/routing_table.rb, line 120
def neighbours_within_distance(id, distance)
  raise ArgumentError, 'invalid id' unless id.is_a?(Integer)

  select {|n| n.id_distance(id) <= distance }
    .sort_by {|n| n.id_distance(id) }
end
not_full_buckets() click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 31
def not_full_buckets
  @buckets.select {|b| b.size < K }
end
size() click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 85
def size
  @buckets.map(&:size).reduce(0, &:+)
end
split_bucket(bucket) click to toggle source
# File lib/devp2p/kademlia/routing_table.rb, line 21
def split_bucket(bucket)
  index = @buckets.index bucket
  @buckets[index..index] = bucket.split
end