Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
New Lua example: Chord (work in progress)
[simgrid.git] / examples / lua / chord / chord.lua
1 -- A SimGrid Lua implementation of the Chord DHT
2
3 require("simgrid")
4
5 nb_bits = 24
6 nb_keys = 2^nb_bits
7 comp_size = 0
8 comm_size = 10
9 timeout = 50
10 max_simulation_time = 1000
11 stabilize_delay = 20
12 fix_fingers_delay = 120
13 check_predecessor_delay = 120
14 lookup_delay = 10
15
16 -- current node (globals are duplicated in each process)
17 my_node = {
18   id = my_id,
19   next_finger_to_fix = 1,
20   fingers = {},
21   predecessor = nil
22   comm_recv = nil
23 }
24
25 -- Main function of each Chord process
26 -- Arguments:
27 -- - my id
28 -- - the id of a guy I know in the system (except for the first node)
29 function node(my_id, known_id)
30
31   simgrid.info("Hello, I'm a node")
32   --
33   -- join the ring
34   local success = false
35   if known_id == nil then
36     -- first node
37     create()
38     success = true
39   else
40     success = join(known_id)
41   end
42
43   -- main loop
44   if join_success then
45
46     local now = simgrid.get_clock()
47     local next_stabilize_date = now + stabilize_delay
48     local next_fix_fingers_date = now + fix_fingers_delay
49     local next_check_predecessor_date = now + check_predecessor_delay
50     local next_lookup_date = now + lookup_delay
51
52     local task
53     my_node.comm_recv = simgrid.task.irecv(my_node.id)
54
55     while simgrid.get_clock() < max_simulation_time do
56
57       task = simgrid.comm.test(node.comm_recv)
58
59       if task then
60         -- I received a task: answer it
61         my_node.comm_recv = simgrid.task.irecv(my_node.id)
62         handle_task(task)
63       else
64         -- no task was received: do periodic calls
65         if simgrid.get_clock() >= next_fix_fingers_date then
66         
67         end
68       end
69     end
70     leave()
71   end
72 end
73
74 -- Returns whether an id belongs to the interval [a, b[.
75 -- The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
76 -- 1 belongs to [62, 3].
77 -- 1 does not belong to [3, 62].
78 -- 63 belongs to [62, 3].
79 -- 63 does not belong to [3, 62].
80 -- 24 belongs to [21, 29].
81 -- 24 does not belong to [29, 21].
82 function is_in_interval(id, a, b)
83
84   -- normalize the parameters
85   id = id % nb_bits
86   a = a % nb_bits
87   b = b % nb_bits
88  
89   -- make sure a <= b and a <= id
90   if b < a then
91     b = b + nb_keys
92   end
93
94   if id < a then
95     id = id + nb_keys
96   end
97
98   return id <= b
99 end
100
101 -- Finds the successor of an id
102 -- id: the id to find
103 -- return value: the id of the successor, or -1 if the request failed
104 function find_successor(d)
105
106   if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
107     -- my successor is the successor
108     return my_node.fingers[1]
109   end
110
111   -- ask to the closest preceding finger in my table
112   local ask_to = closest_preceding_node(id)
113   return remote_find_successor(ask_to, id)
114 end
115
116 -- Asks a remote node the successor of an id.
117 -- ask_to: id of a remote node to ask to
118 -- id: the id to find
119 -- return value: the id of the successor, or -1 if the request failed
120 function remote_find_successor(ask_to, id)
121
122   local successor
123   local task = simgrid.task.new(comp_size, comm_size)
124   task[type] = "find successor"
125   task[request_id] = id
126   task[issuer] = my_node.id
127
128   if task:send(ask_to, timeout) then
129     -- request successfully sent: wait for an answer
130     local stop = false
131     repeat
132       task = simgrid.comm.wait(my_node.comm_recv, timeout)
133       my_node.comm_recv = simgrid.task.irecv(my_node.id)
134     
135       if not task then
136         -- failed to receiver the answer
137         stop = true
138       else
139         -- a task was received: is it the expected answer?
140         if task[type] ~= "find successor" or task[request_id] ~= id then
141           -- this is not our anwser
142           handle_task(task)
143         else
144           -- this is our answer
145           successor = task[answer_id]
146           stop = true
147         end
148       end
149     until stop
150   end
151
152   return successor
153 end
154
155 -- Returns the closest preceding finger of an id with respect to the finger
156 -- table of the current node.
157 -- - id: the id to find
158 -- - return value: the closest preceding finger of that id
159 function closest_preceding_node(id)
160
161   for i = nb_bits, 1, -1 do
162     if is_in_interval(my_node.fingers[i].id, my_node.id + 1, id - 1) then
163       -- finger i is the first one before id
164       return my_node.fingers[i].id
165     end
166   end
167 end
168
169 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
170 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")
171 simgrid.run()
172