examples/lua/kademlia/routing_table.lua

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