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 local ans_task = simgrid.task.new("", comp_size, comm_size)
134 ans_task.type = "find successor answer"
135 ans_task.request_id = task.request_id
136 ans_task.answer = my_node.fingers[1]
137 ans_task:dsend(task.answer_to)
139 -- forward the request to the closest preceding finger in my table
141 simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")
143 local next_task = simgrid.task.new("", comp_size, comm_size)
144 next_task.type = "find successor"
145 next_task.request_id = task.request_id
146 next_task.answer_to = task.answer_to
147 next_task:dsend(closest_preceding_node(next_task.request_id))
150 elseif type == "get predecessor" then
151 local ans_task = simgrid.task.new("", comp_size, comm_size)
152 ans_task.type = "get predecessor answer"
153 ans_task.answer = my_node.predecessor
154 ans_task:dsend(task.answer_to)
156 elseif type == "notify" then
157 -- someone is telling me that he may be my new predecessor
158 notify(task.request_id)
160 elseif type == "predecessor leaving" then
163 elseif type == "successor_leaving" then
166 elseif type == "find successor answer" then
169 elseif type == "get predecessor answer" then
173 error("Unknown type of task received: " .. task.type)
177 -- Returns whether an id belongs to the interval [a, b[.
178 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
179 -- 1 belongs to [62, 3].
180 -- 1 does not belong to [3, 62].
181 -- 63 belongs to [62, 3].
182 -- 63 does not belong to [3, 62].
183 -- 24 belongs to [21, 29].
184 -- 24 does not belong to [29, 21].
185 function is_in_interval(id, a, b)
187 -- normalize the parameters
192 -- make sure a <= b and a <= id
204 -- Returns whether the current node is in the ring.
205 function has_joined()
207 return my_node.fingers[1] ~= nil
210 -- Creates a new Chord ring.
212 my_node.predecessor = nil
213 my_node.fingers[1] = my_node.id
216 -- Attemps to join the Chord ring.
217 -- - known_id: id of a node already in the ring
218 -- - return value: true if the join was successful
219 function join(known_id)
221 simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)
223 local successor = remote_find_successor(known_id, my_node.id)
224 if successor == nil then
225 simgrid.info("Cannot join the ring.")
229 my_node.predecessor = nil
230 my_node.fingers[1] = successor
234 -- Returns the closest preceding finger of an id with respect to the finger
235 -- table of the current node.
236 -- - id: the id to find
237 -- - return value: the closest preceding finger of that id
238 function closest_preceding_node(id)
240 for i = nb_bits, 1, -1 do
241 if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
242 -- finger i is the first one before id
243 return my_node.fingers[i]
248 -- Finds the successor of an id
249 -- id: the id to find
250 -- return value: the id of the successor, or nil if the request failed
251 function find_successor(id)
253 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
254 -- my successor is the successor
255 return my_node.fingers[1]
258 -- ask to the closest preceding finger in my table
259 local ask_to = closest_preceding_node(id)
260 return remote_find_successor(ask_to, id)
263 -- Asks a remote node the successor of an id.
264 -- ask_to: id of a remote node to ask to
265 -- id: the id to find
266 -- return value: the id of the successor, or nil if the request failed
267 function remote_find_successor(ask_to, id)
269 local task = simgrid.task.new("", comp_size, comm_size)
270 task.type = "find successor"
272 task.answer_to = my_node.id
274 simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id)
275 if task:send(ask_to, timeout) then
276 -- request successfully sent: wait for an answer
278 simgrid.info("Sent the 'find successor' request to " .. ask_to ..
279 " for id " .. id .. ", waiting for the answer")
282 task = simgrid.comm.wait(my_node.comm_recv, timeout)
283 my_node.comm_recv = simgrid.task.irecv(my_node.id)
286 -- failed to receive the answer
287 simgrid.info("Failed to receive the answer to my 'find successor' request")
290 -- a task was received: is it the expected answer?
291 if task.type ~= "find successor answer" or task.request_id ~= id then
292 -- this is not our answer
293 simgrid.info("Received another request of type " .. task.type)
296 -- this is our answer
297 simgrid.info("Received the answer to my 'find successor' request for id " ..
298 id .. ": the successor is " .. task.answer)
304 simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
311 -- Asks a remote node its predecessor.
312 -- ask_to: id of a remote node to ask to
313 -- return value: the id of its predecessor, or nil if the request failed
314 function remote_get_predecessor(ask_to)
316 local task = simgrid.task.new("", comp_size, comm_size)
317 task.type = "get predecessor"
318 task.answer_to = my_node.id
320 if task:send(ask_to, timeout) then
321 -- request successfully sent: wait for an answer
323 task = simgrid.comm.wait(my_node.comm_recv, timeout)
324 my_node.comm_recv = simgrid.task.irecv(my_node.id)
327 -- failed to receive the answer
330 -- a task was received: is it the expected answer?
331 if task.type ~= "get predecessor answer" then
332 -- this is not our answer
335 -- this is our answer
336 -- FIXME make sure the message answers to this particular request
346 -- Checks the immediate successor of the current node.
350 local successor = my_node.fingers[1]
351 if successor ~= my_node.id then
352 candidate = remote_get_predecessor(successor)
354 candidate = my_node.predecessor
357 -- this node is a candidate to become my new successor
358 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
359 my_node.fingers[1] = candidate
362 if successor ~= my_node.id then
363 remote_notify(successor, my_node.id)
367 -- Notifies the current node that its predecessor my have changed
368 -- - candidate_predecessor: the possible new predecessor
369 function notify(candidate_predecessor)
371 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
372 my_node.predecessor + 1, my_node.id - 1) then
373 my_node.predecessor = candidate_predecessor
377 -- Notifies a remote node that its predecessor my have changed.
379 -- - candidate the possible new predecessor
380 function remote_notify(notify_to, candidate_predecessor)
382 local task = simgrid.task.new("", comp_size, comm_size)
384 task.request_id = candidate_predecessor
385 task:dsend(notify_to)
388 -- Refreshes the finger table of the current node.
389 function fix_fingers()
391 local i = my_node.next_finger_to_fix
392 local id = find_successor(my_node.id + 2^i)
394 if id ~= my_node.fingers[i] then
395 my_node.fingers[i] = id
397 my_node.next_finger_to_fix = (i % nb_bits) + 1
401 -- Checks whether the predecessor of the current node has failed.
402 function check_predecessor()
406 -- Performs a find successor request to an arbitrary id.
407 function random_lookup()
412 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
413 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")