examples/lua/kademlia/routing_table.lua

   1 -- Routing table data
   2 routing_table = {
   3 buckets = {},
   4 }
   5 -- Initialize the routing table
   6 function routing_table_init(id)
   7         routing_table.id = id
   8         -- Bucket initialization
   9         for i = 0,common.IDENTIFIER_SIZE do
  10                 routing_table.buckets[i] = {id = i, set = {}, list = {}}
  11         end
  12 end
  13 -- Returns an identifier which is in a specific bucket of a routing table
  14 function get_id_in_prefix(id, prefix)
  15         if id == 0 then
  16                 return 0
  17         end
  18         local identifier = 1
  19         identifier = math.pow(identifier,prefix - 1)
  20         identifier = bxor(identifier,id)
  21         return identifier
  22 end
  23 -- Returns the corresponding node prefix for a given id
  24 function get_node_prefix(id)
  25         for i = 0,32 do
  26                 if is_integer(id / math.pow(2,i)) and (id / math.pow(2,i)) % 2 == 1 then
  27                         return 31 - i
  28                 end
  29         end
  30         return 0
  31 end
  32 -- Finds the corresponding bucket in a routing table for a given identifier
  33 function find_bucket(id)
  34         local xor_number = bxor(id,routing_table.id)
  35         local prefix = get_node_prefix(xor_number)
  36         --simgrid.info("Prefix:" .. prefix .. " number:" .. xor_number)
  37         return routing_table.buckets[prefix]
  38 end
  39 -- Updates the routing table with a new value.
  40 function routing_table_update(id)
  41         if id == routing_table.id then
  42                 return
  43         end
  44         local bucket = find_bucket(id)
  45         if bucket.set[id] ~= nil then
  46                 simgrid.debug("Updating " .. id .. " in my routing table")
  47                 -- If the element is already in the bucket, we update it.
  48                 table.remove(bucket.list,index_of(bucket.list,id))
  49                 table.insert(bucket.list,0,id)
  50         else
  51                 simgrid.debug("Insert " .. id .. " in my routing table in bucket " .. bucket.id)
  52                 table.insert(bucket.list,id)
  53                 bucket.set[id] = true
  54         end
  55 end
  56 -- Returns the closest notes we know to a given id
  57 function find_closest(destination_id)
  58         local answer = {destination = destination_id, nodes = {}}
  59
  60         local bucket = find_bucket(destination_id)
  61         for i,v in pairs(bucket.list) do
  62                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
  63         end
  64
  65         local i = 1
  66
  67         while #answer.nodes < common.BUCKET_SIZE and ((bucket.id - i) >= 0 or (bucket.id + i) <= common.IDENTIFIER_SIZE) do
  68                 -- Check the previous buckets
  69                 if bucket.id - i >= 0 then
  70                         local bucket_p = routing_table.buckets[bucket.id - i]
  71                         for i,v in pairs(bucket_p.list) do
  72                                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
  73                         end
  74                 end
  75                 -- Check the next buckets
  76                 if bucket.id + i <= common.IDENTIFIER_SIZE then
  77                         local bucket_n = routing_table.buckets[bucket.id + i]
  78                         for i,v in pairs(bucket_n.list) do
  79                                 table.insert(answer.nodes,{id = v, distance = bxor(v,destination_id)})
  80                         end
  81                 end
  82                 i = i + 1
  83         end
  84         -- Sort the list
  85         table.sort(answer.nodes, function(a,b) return a.distance < b.distance end)
  86         -- Trim the list
  87         while #answer.nodes > common.BUCKET_SIZE do
  88                 table.remove(answer.nodes)
  89         end
  90
  91         return answer
  92 end