1 -- Copyright (c) 2012, 2014. The SimGrid Team.
2 -- All rights reserved.
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.
11 -- Initialize the routing table
12 function routing_table_init(id)
14 -- Bucket initialization
15 for i = 0,common.IDENTIFIER_SIZE do
16 routing_table.buckets[i] = {id = i, set = {}, list = {}}
19 -- Returns an identifier which is in a specific bucket of a routing table
20 function get_id_in_prefix(id, prefix)
25 identifier = math.pow(identifier,prefix - 1)
26 identifier = bxor(identifier,id)
29 -- Returns the corresponding node prefix for a given id
30 function get_node_prefix(id)
32 if is_integer(id / math.pow(2,i)) and (id / math.pow(2,i)) % 2 == 1 then
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]
45 -- Updates the routing table with a new value.
46 function routing_table_update(id)
47 if id == routing_table.id then
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)
57 simgrid.debug("Insert " .. id .. " in my routing table in bucket " .. bucket.id)
58 table.insert(bucket.list,id)
62 -- Returns the closest notes we know to a given id
63 function find_closest(destination_id)
64 local answer = {destination = destination_id, nodes = {}}
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)})
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)})
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)})
91 table.sort(answer.nodes, function(a,b) return a.distance < b.distance end)
93 while #answer.nodes > common.BUCKET_SIZE do
94 table.remove(answer.nodes)