Class: DEVp2p::Kademlia::RoutingTable

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/devp2p/kademlia/routing_table.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(node) ⇒ RoutingTable

Returns a new instance of RoutingTable.



10
11
12
13
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 10

def initialize(node)
  @node = node
  @buckets = [KBucket.new(0, MAX_NODE_ID)]
end

Instance Attribute Details

#node ⇒ Object (readonly)

Returns the value of attribute node.



8
9
10
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 8

def node
  @node
end

Instance Method Details

#add(node) ⇒ Object

Raises:

  • (ArgumentError) 


36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 36

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) ⇒ Object

Raises:



61
62
63
64
65
66
67
68
69
70
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 61

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) ⇒ Object

Raises:

  • (ArgumentError) 


77
78
79
80
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 77

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) ⇒ Object

Raises:

  • (ArgumentError) 


72
73
74
75
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 72

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 ⇒ Object 



90
91
92
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 90

def buckets_count
  @buckets.size
end

#delete(node) ⇒ Object 



57
58
59
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 57

def delete(node)
  bucket_by_node(node).delete node
end

#each(&block) ⇒ Object 



16
17
18
19
20
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 16

def each(&block)
  @buckets.each do |b|
    b.each(&block)
  end
end

#idle_buckets ⇒ Object 



27
28
29
30
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 27

def idle_buckets
  t_idle = Time.now - IDLE_BUCKET_REFRESH_INTERVAL
  @buckets.select {|b| b.last_updated < t_idle }
end

#include?(node) ⇒ Boolean

Returns:

  • (Boolean) 


82
83
84
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 82

def include?(node)
  bucket_by_node(node).include?(node)
end

#neighbours(node, k = K) ⇒ Object

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?

Raises:

  • (ArgumentError) 


100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 100

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) ⇒ Object

naive correct version simply compares all nodes

Raises:

  • (ArgumentError) 


121
122
123
124
125
126
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 121

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 ⇒ Object 



32
33
34
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 32

def not_full_buckets
  @buckets.select {|b| b.size < K }
end

#size ⇒ Object 



86
87
88
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 86

def size
  @buckets.map(&:size).reduce(0, &:+)
end

#split_bucket(bucket) ⇒ Object 



22
23
24
25
 
# File 'lib/devp2p/kademlia/routing_table.rb', line 22

def split_bucket(bucket)
  index = @buckets.index bucket
  @buckets[index..index] = bucket.split
end