1 -- A SimGrid Lua implementation of the Chord DHT
3 -- Copyright (c) 2011-2012, 2014. The SimGrid Team.
4 -- All rights reserved.
6 -- This program is free software; you can redistribute it and/or modify it
7 -- under the terms of the license (GNU LGPL) which comes with this package.
16 max_simulation_time = 1000
18 fix_fingers_delay = 120
19 check_predecessor_delay = 120
22 -- current node (don't worry, globals are duplicated in each simulated process)
25 next_finger_to_fix = 1,
31 -- Main function of each Chord process
34 -- - the id of a guy I know in the system (except for the first node)
37 -- TODO simplify the deployment file
40 my_node.id = tonumber(args[1])
42 known_id = tonumber(args[2])
45 -- initialize the node
47 my_node.fingers[i] = my_node.id
49 my_node.comm_recv = simgrid.task.irecv(my_node.id)
52 local join_success = false
53 if known_id == nil then
58 join_success = join(known_id)
64 local now = simgrid.get_clock()
65 local next_stabilize_date = now + stabilize_delay
66 local next_fix_fingers_date = now + fix_fingers_delay
67 local next_check_predecessor_date = now + check_predecessor_delay
68 local next_lookup_date = now + lookup_delay
72 while now < max_simulation_time do
74 task, err = my_node.comm_recv:test()
77 -- I received a task: answer it
78 my_node.comm_recv = simgrid.task.irecv(my_node.id)
81 -- the communication has failed: nevermind
82 my_node.comm_recv = simgrid.task.irecv(my_node.id)
84 -- no task was received: do periodic calls
85 if now >= next_stabilize_date then
87 next_stabilize_date = simgrid.get_clock() + stabilize_delay
89 elseif now >= next_fix_fingers_date then
91 next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay
93 elseif now >= next_check_predecessor_date then
95 next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
97 elseif now >= next_lookup_date then
99 next_lookup_date = simgrid.get_clock() + lookup_delay
102 -- nothing to do: sleep for a while
103 simgrid.process.sleep(5)
106 now = simgrid.get_clock()
114 -- Makes the current node leave the ring
117 simgrid.info("Leaving the ring")
118 -- TODO: notify others
121 -- This function is called when the current node receives a task.
122 -- - task: the task received
123 function handle_task(task)
125 local type = task.type
127 if type == "find successor" then
129 simgrid.info("Received a 'find successor' request from " .. task.answer_to ..
130 " for id " .. task.request_id)
132 -- is my successor the successor?
133 if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
135 simgrid.info("Sending back a 'find successor answer' to " ..
136 task.answer_to .. ": the successor of " .. task.request_id ..
137 " is " .. my_node.fingers[1])
139 task.type = "find successor answer"
140 task.answer = my_node.fingers[1]
141 task:dsend(task.answer_to)
143 -- forward the request to the closest preceding finger in my table
145 simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")
146 task:dsend(closest_preceding_node(task.request_id))
149 elseif type == "get predecessor" then
150 task.type = "get predecessor answer"
151 task.answer = my_node.predecessor
152 task:dsend(task.answer_to)
154 elseif type == "notify" then
155 -- someone is telling me that he may be my new predecessor
156 notify(task.request_id)
158 elseif type == "predecessor leaving" then
161 elseif type == "successor_leaving" then
164 elseif type == "find successor answer" then
167 elseif type == "get predecessor answer" then
171 error("Unknown type of task received: " .. task.type)
175 -- Returns whether an id belongs to the interval [a, b[.
176 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
177 -- 1 belongs to [62, 3].
178 -- 1 does not belong to [3, 62].
179 -- 63 belongs to [62, 3].
180 -- 63 does not belong to [3, 62].
181 -- 24 belongs to [21, 29].
182 -- 24 does not belong to [29, 21].
183 function is_in_interval(id, a, b)
185 -- normalize the parameters
190 -- make sure a <= b and a <= id
202 -- Returns whether the current node is in the ring.
203 function has_joined()
205 return my_node.fingers[1] ~= nil
208 -- Creates a new Chord ring.
210 my_node.predecessor = nil
211 my_node.fingers[1] = my_node.id
214 -- Attemps to join the Chord ring.
215 -- - known_id: id of a node already in the ring
216 -- - return value: true if the join was successful
217 function join(known_id)
219 simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)
221 local successor = remote_find_successor(known_id, my_node.id)
222 if successor == nil then
223 simgrid.info("Cannot join the ring.")
227 my_node.predecessor = nil
228 my_node.fingers[1] = successor
232 -- Returns the closest preceding finger of an id with respect to the finger
233 -- table of the current node.
234 -- - id: the id to find
235 -- - return value: the closest preceding finger of that id
236 function closest_preceding_node(id)
238 for i = nb_bits, 1, -1 do
239 if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
240 -- finger i is the first one before id
241 return my_node.fingers[i]
246 -- Finds the successor of an id
247 -- id: the id to find
248 -- return value: the id of the successor, or nil if the request failed
249 function find_successor(id)
251 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
252 -- my successor is the successor
253 return my_node.fingers[1]
256 -- ask to the closest preceding finger in my table
257 local ask_to = closest_preceding_node(id)
258 return remote_find_successor(ask_to, id)
261 -- Asks a remote node the successor of an id.
262 -- ask_to: id of a remote node to ask to
263 -- id: the id to find
264 -- return value: the id of the successor, or nil if the request failed
265 function remote_find_successor(ask_to, id)
267 local task = simgrid.task.new("", comp_size, comm_size)
268 task.type = "find successor"
270 task.answer_to = my_node.id
272 simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id)
273 if task:send(ask_to, timeout) then
274 -- request successfully sent: wait for an answer
276 simgrid.info("Sent the 'find successor' request to " .. ask_to ..
277 " for id " .. id .. ", waiting for the answer")
280 task = my_node.comm_recv:wait(timeout)
281 my_node.comm_recv = simgrid.task.irecv(my_node.id)
284 -- failed to receive the answer
285 simgrid.info("Failed to receive the answer to my 'find successor' request")
288 -- a task was received: is it the expected answer?
289 if task.type ~= "find successor answer" or task.request_id ~= id then
290 -- this is not our answer
291 simgrid.info("Received another request of type " .. task.type)
294 -- this is our answer
295 simgrid.info("Received the answer to my 'find successor' request for id " ..
296 id .. ": the successor is " .. task.answer)
302 simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
309 -- Asks a remote node its predecessor.
310 -- ask_to: id of a remote node to ask to
311 -- return value: the id of its predecessor, or nil if the request failed
312 function remote_get_predecessor(ask_to)
314 local task = simgrid.task.new("", comp_size, comm_size)
315 task.type = "get predecessor"
316 task.answer_to = my_node.id
318 if task:send(ask_to, timeout) then
319 -- request successfully sent: wait for an answer
321 task = my_node.comm_recv:wait(timeout)
322 my_node.comm_recv = simgrid.task.irecv(my_node.id)
325 -- failed to receive the answer
328 -- a task was received: is it the expected answer?
329 if task.type ~= "get predecessor answer" then
330 -- this is not our answer
333 -- this is our answer
334 -- FIXME make sure the message answers to this particular request
344 -- Checks the immediate successor of the current node.
348 local successor = my_node.fingers[1]
349 if successor ~= my_node.id then
350 candidate = remote_get_predecessor(successor)
352 candidate = my_node.predecessor
355 -- this node is a candidate to become my new successor
356 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
357 my_node.fingers[1] = candidate
360 if successor ~= my_node.id then
361 remote_notify(successor, my_node.id)
365 -- Notifies the current node that its predecessor my have changed
366 -- - candidate_predecessor: the possible new predecessor
367 function notify(candidate_predecessor)
369 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
370 my_node.predecessor + 1, my_node.id - 1) then
371 my_node.predecessor = candidate_predecessor
375 -- Notifies a remote node that its predecessor my have changed.
377 -- - candidate the possible new predecessor
378 function remote_notify(notify_to, candidate_predecessor)
380 local task = simgrid.task.new("", comp_size, comm_size)
382 task.request_id = candidate_predecessor
383 task:dsend(notify_to)
386 -- Refreshes the finger table of the current node.
387 function fix_fingers()
389 local i = my_node.next_finger_to_fix
390 local id = find_successor(my_node.id + 2^i)
392 if id ~= my_node.fingers[i] then
393 my_node.fingers[i] = id
395 my_node.next_finger_to_fix = (i % nb_bits) + 1
399 -- Checks whether the predecessor of the current node has failed.
400 function check_predecessor()
404 -- Performs a find successor request to an arbitrary id.
405 function random_lookup()
410 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
411 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")