5 -- Initialize the routing table
6 function routing_table_init(id)
8 -- Bucket initialization
9 for i = 0,common.IDENTIFIER_SIZE do
10 routing_table.buckets[i] = {id = i, set = {}, list = {}}
13 -- Returns an identifier which is in a specific bucket of a routing table
14 function get_id_in_prefix(id, prefix)
19 identifier = math.pow(identifier,prefix - 1)
20 identifier = bxor(identifier,id)
23 -- Returns the corresponding node prefix for a given id
24 function get_node_prefix(id)
26 if is_integer(id / math.pow(2,i)) and (id / math.pow(2,i)) % 2 == 1 then
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]
39 -- Updates the routing table with a new value.
40 function routing_table_update(id)
41 if id == routing_table.id then
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)
51 simgrid.debug("Insert " .. id .. " in my routing table in bucket " .. bucket.id)
52 table.insert(bucket.list,id)
56 -- Returns the closest notes we know to a given id
57 function find_closest(destination_id)
58 local answer = {destination = destination_id, nodes = {}}
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)})
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)})
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)})
85 table.sort(answer.nodes, function(a,b) return a.distance < b.distance end)
87 while #answer.nodes > common.BUCKET_SIZE do
88 table.remove(answer.nodes)