1 -- A SimGrid Lua implementation of the Chord DHT
10 max_simulation_time = 1000
12 fix_fingers_delay = 120
13 check_predecessor_delay = 120
16 -- current node (don't worry, globals are duplicated in each process)
19 next_finger_to_fix = 1,
25 -- Main function of each Chord process
28 -- - the id of a guy I know in the system (except for the first node)
31 -- TODO simplify the parameters
34 my_node.id = tonumber(args[1])
36 known_id = tonumber(args[2])
39 -- initialize the node
41 my_node.fingers[i] = my_node.id
43 my_node.comm_recv = simgrid.task.irecv(my_node.id)
46 local join_success = false
47 if known_id == nil then
52 join_success = join(known_id)
58 local now = simgrid.get_clock()
59 local next_stabilize_date = now + stabilize_delay
60 local next_fix_fingers_date = now + fix_fingers_delay
61 local next_check_predecessor_date = now + check_predecessor_delay
62 local next_lookup_date = now + lookup_delay
66 while now < max_simulation_time do
68 task, success = simgrid.comm.test(my_node.comm_recv)
71 -- I received a task: answer it
72 my_node.comm_recv = simgrid.task.irecv(my_node.id)
75 -- the communication has failed: nevermind
76 my_node.comm_recv = simgrid.task.irecv(my_node.id)
78 -- no task was received: do periodic calls
79 if now >= next_stabilize_date then
81 next_stabilize_date = simgrid.get_clock() + stabilize_delay
83 elseif now >= next_fix_fingers_date then
85 next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay
87 elseif now >= next_check_predecessor_date then
89 next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
90 elseif now >= next_lookup_date then
92 next_lookup_date = simgrid.get_clock() + lookup_delay
95 -- nothing to do: sleep for a while
96 simgrid.process.sleep(5)
99 now = simgrid.get_clock()
107 -- Makes the current node leave the ring
110 simgrid.info("Leaving the ring")
111 -- TODO: notify others
114 -- This function is called when the current node receives a task.
115 -- - task: the task received
116 function handle_task(task)
118 local type = task.type
120 if type == "find successor" then
122 simgrid.info("Received a 'find successor' request from " .. task.answer_to ..
123 " for id " .. task.request_id)
125 -- is my successor the successor?
126 if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
128 simgrid.info("Sending back a 'find successor answer' to " ..
129 task.answer_to .. ": the successor of " .. task.request_id ..
130 " is " .. my_node.fingers[1])
132 local ans_task = simgrid.task.new("", comp_size, comm_size)
133 ans_task.type = "find successor answer"
134 ans_task.request_id = task.request_id
135 ans_task.answer = my_node.fingers[1]
136 ans_task:dsend(task.answer_to)
138 -- forward the request to the closest preceding finger in my table
140 simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")
142 local next_task = simgrid.task.new("", comp_size, comm_size)
143 next_task.type = "find successor"
144 next_task.request_id = task.request_id
145 next_task.answer_to = task.answer_to
146 next_task:dsend(closest_preceding_node(next_task.request_id))
149 elseif type == "get predecessor" then
150 local ans_task = simgrid.task.new("", comp_size, comm_size)
151 ans_task.type = "get predecessor answer"
152 ans_task.answer = my_node.predecessor
153 ans_task:dsend(task.answer_to)
155 elseif type == "notify" then
156 -- someone is telling me that he may be my new predecessor
157 notify(task.request_id)
159 elseif type == "predecessor leaving" then
162 elseif type == "successor_leaving" then
165 elseif type == "find successor answer" then
168 elseif type == "get predecessor answer" then
172 error("Unknown type of task received: " .. task.type)
176 -- Returns whether an id belongs to the interval [a, b[.
177 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
178 -- 1 belongs to [62, 3].
179 -- 1 does not belong to [3, 62].
180 -- 63 belongs to [62, 3].
181 -- 63 does not belong to [3, 62].
182 -- 24 belongs to [21, 29].
183 -- 24 does not belong to [29, 21].
184 function is_in_interval(id, a, b)
186 -- normalize the parameters
191 -- make sure a <= b and a <= id
203 -- Returns whether the current node is in the ring.
204 function has_joined()
206 return my_node.fingers[1] ~= nil
209 -- Creates a new Chord ring.
211 my_node.predecessor = nil
212 my_node.fingers[1] = my_node.id
215 -- Attemps to join the Chord ring.
216 -- - known_id: id of a node already in the ring
217 -- - return value: true if the join was successful
218 function join(known_id)
220 simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)
222 local successor = remote_find_successor(known_id, my_node.id)
223 if successor == nil then
224 simgrid.info("Cannot join the ring.")
228 my_node.predecessor = nil
229 my_node.fingers[1] = successor
233 -- Returns the closest preceding finger of an id with respect to the finger
234 -- table of the current node.
235 -- - id: the id to find
236 -- - return value: the closest preceding finger of that id
237 function closest_preceding_node(id)
239 for i = nb_bits, 1, -1 do
240 if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
241 -- finger i is the first one before id
242 return my_node.fingers[i]
247 -- Finds the successor of an id
248 -- id: the id to find
249 -- return value: the id of the successor, or nil if the request failed
250 function find_successor(id)
252 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
253 -- my successor is the successor
254 return my_node.fingers[1]
257 -- ask to the closest preceding finger in my table
258 local ask_to = closest_preceding_node(id)
259 return remote_find_successor(ask_to, id)
262 -- Asks a remote node the successor of an id.
263 -- ask_to: id of a remote node to ask to
264 -- id: the id to find
265 -- return value: the id of the successor, or nil if the request failed
266 function remote_find_successor(ask_to, id)
268 local task = simgrid.task.new("", comp_size, comm_size)
269 task.type = "find successor"
271 task.answer_to = my_node.id
273 simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id)
274 if task:send(ask_to, timeout) then
275 -- request successfully sent: wait for an answer
277 simgrid.info("Sent the 'find successor' request to " .. ask_to ..
278 " for id " .. id .. ", waiting for the answer")
281 task = simgrid.comm.wait(my_node.comm_recv, timeout)
282 my_node.comm_recv = simgrid.task.irecv(my_node.id)
285 -- failed to receive the answer
286 simgrid.info("Failed to receive the answer to my 'find successor' request")
289 -- a task was received: is it the expected answer?
290 if task.type ~= "find successor answer" or task.request_id ~= id then
291 -- this is not our answer
292 simgrid.info("Received another request of type " .. task.type)
295 -- this is our answer
296 simgrid.info("Received the answer to my 'find successor' request for id " ..
297 id .. ": the successor is " .. task.answer)
303 simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
310 -- Asks a remote node its predecessor.
311 -- ask_to: id of a remote node to ask to
312 -- return value: the id of its predecessor, or nil if the request failed
313 function remote_get_predecessor(ask_to)
315 local task = simgrid.task.new("", comp_size, comm_size)
316 task.type = "get predecessor"
317 task.answer_to = my_node.id
319 if task:send(ask_to, timeout) then
320 -- request successfully sent: wait for an answer
322 task = simgrid.comm.wait(my_node.comm_recv, timeout)
323 my_node.comm_recv = simgrid.task.irecv(my_node.id)
326 -- failed to receive the answer
329 -- a task was received: is it the expected answer?
330 if task.type ~= "get predecessor answer" then
331 -- this is not our answer
334 -- this is our answer
335 -- FIXME make sure the message answers to this particular request
345 -- Checks the immediate successor of the current node.
349 local successor = my_node.fingers[1]
350 if successor ~= my_node.id then
351 candidate = remote_get_predecessor(successor)
353 candidate = my_node.predecessor
356 -- this node is a candidate to become my new successor
357 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
358 my_node.fingers[1] = candidate
361 if successor ~= my_node.id then
362 remote_notify(successor, my_node.id)
366 -- Notifies the current node that its predecessor my have changed
367 -- - candidate_predecessor: the possible new predecessor
368 function notify(candidate_predecessor)
370 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
371 my_node.predecessor + 1, my_node.id - 1) then
372 my_node.predecessor = candidate_predecessor
376 -- Notifies a remote node that its predecessor my have changed.
378 -- - candidate the possible new predecessor
379 function remote_notify(notify_to, candidate_predecessor)
381 local task = simgrid.task.new("", comp_size, comm_size)
383 task.request_id = candidate_predecessor
384 task:dsend(notify_to)
387 -- Refreshes the finger table of the current node.
388 function fix_fingers()
390 local i = my_node.next_finger_to_fix
391 local id = find_successor(my_node.id + 2^i)
393 if id ~= my_node.fingers[i] then
394 my_node.fingers[i] = id
396 my_node.next_finger_to_fix = (i % nb_bits) + 1
400 -- Checks whether the predecessor of the current node has failed.
401 function check_predecessor()
405 -- Performs a find successor request to an arbitrary id.
406 function random_lookup()
411 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
412 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")