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