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 simulated 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 deployment file
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, err = 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
91 elseif now >= next_lookup_date then
93 next_lookup_date = simgrid.get_clock() + lookup_delay
96 -- nothing to do: sleep for a while
97 simgrid.process.sleep(5)
100 now = simgrid.get_clock()
108 -- Makes the current node leave the ring
111 simgrid.info("Leaving the ring")
112 -- TODO: notify others
115 -- This function is called when the current node receives a task.
116 -- - task: the task received
117 function handle_task(task)
119 local type = task.type
121 if type == "find successor" then
123 simgrid.info("Received a 'find successor' request from " .. task.answer_to ..
124 " for id " .. task.request_id)
126 -- is my successor the successor?
127 if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
129 simgrid.info("Sending back a 'find successor answer' to " ..
130 task.answer_to .. ": the successor of " .. task.request_id ..
131 " is " .. my_node.fingers[1])
133 task.type = "find successor answer"
134 task.answer = my_node.fingers[1]
135 task:dsend(task.answer_to)
137 -- forward the request to the closest preceding finger in my table
139 simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")
140 task:dsend(closest_preceding_node(task.request_id))
143 elseif type == "get predecessor" then
144 task.type = "get predecessor answer"
145 task.answer = my_node.predecessor
146 task:dsend(task.answer_to)
148 elseif type == "notify" then
149 -- someone is telling me that he may be my new predecessor
150 notify(task.request_id)
152 elseif type == "predecessor leaving" then
155 elseif type == "successor_leaving" then
158 elseif type == "find successor answer" then
161 elseif type == "get predecessor answer" then
165 error("Unknown type of task received: " .. task.type)
169 -- Returns whether an id belongs to the interval [a, b[.
170 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
171 -- 1 belongs to [62, 3].
172 -- 1 does not belong to [3, 62].
173 -- 63 belongs to [62, 3].
174 -- 63 does not belong to [3, 62].
175 -- 24 belongs to [21, 29].
176 -- 24 does not belong to [29, 21].
177 function is_in_interval(id, a, b)
179 -- normalize the parameters
184 -- make sure a <= b and a <= id
196 -- Returns whether the current node is in the ring.
197 function has_joined()
199 return my_node.fingers[1] ~= nil
202 -- Creates a new Chord ring.
204 my_node.predecessor = nil
205 my_node.fingers[1] = my_node.id
208 -- Attemps to join the Chord ring.
209 -- - known_id: id of a node already in the ring
210 -- - return value: true if the join was successful
211 function join(known_id)
213 simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)
215 local successor = remote_find_successor(known_id, my_node.id)
216 if successor == nil then
217 simgrid.info("Cannot join the ring.")
221 my_node.predecessor = nil
222 my_node.fingers[1] = successor
226 -- Returns the closest preceding finger of an id with respect to the finger
227 -- table of the current node.
228 -- - id: the id to find
229 -- - return value: the closest preceding finger of that id
230 function closest_preceding_node(id)
232 for i = nb_bits, 1, -1 do
233 if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
234 -- finger i is the first one before id
235 return my_node.fingers[i]
240 -- Finds the successor of an id
241 -- id: the id to find
242 -- return value: the id of the successor, or nil if the request failed
243 function find_successor(id)
245 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
246 -- my successor is the successor
247 return my_node.fingers[1]
250 -- ask to the closest preceding finger in my table
251 local ask_to = closest_preceding_node(id)
252 return remote_find_successor(ask_to, id)
255 -- Asks a remote node the successor of an id.
256 -- ask_to: id of a remote node to ask to
257 -- id: the id to find
258 -- return value: the id of the successor, or nil if the request failed
259 function remote_find_successor(ask_to, id)
261 local task = simgrid.task.new("", comp_size, comm_size)
262 task.type = "find successor"
264 task.answer_to = my_node.id
266 simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id)
267 if task:send(ask_to, timeout) then
268 -- request successfully sent: wait for an answer
270 simgrid.info("Sent the 'find successor' request to " .. ask_to ..
271 " for id " .. id .. ", waiting for the answer")
274 task = simgrid.comm.wait(my_node.comm_recv, timeout)
275 my_node.comm_recv = simgrid.task.irecv(my_node.id)
278 -- failed to receive the answer
279 simgrid.info("Failed to receive the answer to my 'find successor' request")
282 -- a task was received: is it the expected answer?
283 if task.type ~= "find successor answer" or task.request_id ~= id then
284 -- this is not our answer
285 simgrid.info("Received another request of type " .. task.type)
288 -- this is our answer
289 simgrid.info("Received the answer to my 'find successor' request for id " ..
290 id .. ": the successor is " .. task.answer)
296 simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
303 -- Asks a remote node its predecessor.
304 -- ask_to: id of a remote node to ask to
305 -- return value: the id of its predecessor, or nil if the request failed
306 function remote_get_predecessor(ask_to)
308 local task = simgrid.task.new("", comp_size, comm_size)
309 task.type = "get predecessor"
310 task.answer_to = my_node.id
312 if task:send(ask_to, timeout) then
313 -- request successfully sent: wait for an answer
315 task = simgrid.comm.wait(my_node.comm_recv, timeout)
316 my_node.comm_recv = simgrid.task.irecv(my_node.id)
319 -- failed to receive the answer
322 -- a task was received: is it the expected answer?
323 if task.type ~= "get predecessor answer" then
324 -- this is not our answer
327 -- this is our answer
328 -- FIXME make sure the message answers to this particular request
338 -- Checks the immediate successor of the current node.
342 local successor = my_node.fingers[1]
343 if successor ~= my_node.id then
344 candidate = remote_get_predecessor(successor)
346 candidate = my_node.predecessor
349 -- this node is a candidate to become my new successor
350 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
351 my_node.fingers[1] = candidate
354 if successor ~= my_node.id then
355 remote_notify(successor, my_node.id)
359 -- Notifies the current node that its predecessor my have changed
360 -- - candidate_predecessor: the possible new predecessor
361 function notify(candidate_predecessor)
363 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
364 my_node.predecessor + 1, my_node.id - 1) then
365 my_node.predecessor = candidate_predecessor
369 -- Notifies a remote node that its predecessor my have changed.
371 -- - candidate the possible new predecessor
372 function remote_notify(notify_to, candidate_predecessor)
374 local task = simgrid.task.new("", comp_size, comm_size)
376 task.request_id = candidate_predecessor
377 task:dsend(notify_to)
380 -- Refreshes the finger table of the current node.
381 function fix_fingers()
383 local i = my_node.next_finger_to_fix
384 local id = find_successor(my_node.id + 2^i)
386 if id ~= my_node.fingers[i] then
387 my_node.fingers[i] = id
389 my_node.next_finger_to_fix = (i % nb_bits) + 1
393 -- Checks whether the predecessor of the current node has failed.
394 function check_predecessor()
398 -- Performs a find successor request to an arbitrary id.
399 function random_lookup()
404 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
405 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")