2 * Copyright (c) 2006-2013. The SimGrid Team.
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the license (GNU LGPL) which comes with this package.
10 import org.simgrid.msg.Comm;
11 import org.simgrid.msg.Host;
12 import org.simgrid.msg.Msg;
13 import org.simgrid.msg.MsgException;
14 import org.simgrid.msg.Process;
15 import org.simgrid.msg.Task;
16 import org.simgrid.msg.TimeoutException;
20 public class Node extends Process {
28 protected String mailbox;
36 protected String predMailbox;
38 * Index of the next finger to fix
40 protected int nextFingerToFix;
42 * Current communication
44 protected Comm commReceive;
46 * Last time I changed a finger or my predecessor
48 protected double lastChangeDate;
56 public Node(Host host, String name, String[] args) {
57 super(host,name,args);
60 public void main(String[] args) throws MsgException {
61 if (args.length != 2 && args.length != 4) {
62 Msg.info("You need to provide 2 or 4 arguments.");
65 double initTime = Msg.getClock();
67 boolean joinSuccess = false;
70 double nextStabilizeDate = initTime + Common.PERIODIC_STABILIZE_DELAY;
71 double nextFixFingersDate = initTime + Common.PERIODIC_FIX_FINGERS_DELAY;
72 double nextCheckPredecessorDate = initTime + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
73 double nextLookupDate = initTime + Common.PERIODIC_LOOKUP_DELAY;
75 id = Integer.valueOf(args[0]);
76 mailbox = Integer.toString(id);
78 fingers = new int[Common.NB_BITS];
79 for (i = 0; i < Common.NB_BITS; i++) {
85 if (args.length == 2) {
86 deadline = Integer.valueOf(args[1]);
91 int knownId = Integer.valueOf(args[1]);
92 deadline = Integer.valueOf(args[3]);
93 //Msg.info("Hey! Let's join the system with the id " + id + ".");
95 joinSuccess = join(knownId);
98 double currentClock = Msg.getClock();
99 while (currentClock < (initTime + deadline) && currentClock < Common.MAX_SIMULATION_TIME) {
100 if (commReceive == null) {
101 commReceive = Task.irecv(this.mailbox);
104 if (!commReceive.test()) {
105 if (currentClock >= nextStabilizeDate) {
107 nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
109 else if (currentClock >= nextFixFingersDate) {
111 nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
113 else if (currentClock >= nextCheckPredecessorDate) {
114 this.checkPredecessor();
115 nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
117 else if (currentClock >= nextLookupDate) {
119 nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
124 currentClock = Msg.getClock();
127 handleTask(commReceive.getTask());
128 currentClock = Msg.getClock();
133 catch (Exception e) {
134 currentClock = Msg.getClock();
140 if (commReceive != null) {
145 Msg.info("I couldn't join the ring");
148 void handleTask(Task task) {
149 if (task instanceof FindSuccessorTask) {
150 FindSuccessorTask fTask = (FindSuccessorTask)task;
151 Msg.debug("Receiving a 'Find Successor' request from " + fTask.issuerHostName + " for id " + fTask.requestId);
152 // is my successor the successor?
153 if (isInInterval(fTask.requestId, this.id + 1, fingers[0])) {
154 //Msg.info("Send the request to " + fTask.answerTo + " with answer " + fingers[0]);
155 FindSuccessorAnswerTask answer = new FindSuccessorAnswerTask(host.getName(), mailbox, fingers[0]);
156 answer.dsend(fTask.answerTo);
159 // otherwise, forward the request to the closest preceding finger in my table
160 int closest = closestPrecedingNode(fTask.requestId);
161 //Msg.info("Forward the request to " + closest);
162 fTask.dsend(Integer.toString(closest));
165 else if (task instanceof GetPredecessorTask) {
166 GetPredecessorTask gTask = (GetPredecessorTask)(task);
167 Msg.debug("Receiving a 'Get Predecessor' request from " + gTask.issuerHostName);
168 GetPredecessorAnswerTask answer = new GetPredecessorAnswerTask(host.getName(), mailbox, predId);
169 answer.dsend(gTask.answerTo);
171 else if (task instanceof NotifyTask) {
172 NotifyTask nTask = (NotifyTask)task;
173 notify(nTask.requestId);
176 Msg.debug("Ignoring unexpected task of type:" + task);
180 * @brief Makes the current node quit the system
183 Msg.debug("Well Guys! I Think it's time for me to quit ;)");
184 quitNotify(1); //Notify my successor
185 quitNotify(-1); //Notify my predecessor.
189 * @brief Notifies the successor or the predecessor of the current node
191 * @param to 1 to notify the successor, -1 to notify the predecessor
193 static void quitNotify( int to) {
197 * @brief Initializes the current node as the first one of the system.
200 Msg.debug("Create a new Chord ring...");
205 * Makes the current node join the ring, knowing the id of a node
206 * already in the ring
208 boolean join(int knownId) {
209 Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
211 int successorId = remoteFindSuccessor(knownId, this.id);
212 if (successorId == -1) {
213 Msg.info("Cannot join the ring.");
216 setFinger(0, successorId);
218 return successorId != -1;
222 * Sets the node predecessor
224 void setPredecessor(int predecessorId) {
225 if (predecessorId != predId) {
226 predId = predecessorId;
227 if (predecessorId != -1) {
228 predMailbox = Integer.toString(predId);
230 lastChangeDate = Msg.getClock();
234 * @brief Asks another node its predecessor.
235 * @param askTo the node to ask to
236 * @return the id of its predecessor node, or -1 if the request failed
237 * (or if the node does not know its predecessor)
239 int remoteGetPredecessor(int askTo) {
240 int predecessorId = -1;
241 boolean stop = false;
242 Msg.debug("Sending a 'Get Predecessor' request to " + askTo);
243 String mailboxTo = Integer.toString(askTo);
244 GetPredecessorTask sendTask = new GetPredecessorTask(host.getName(), this.mailbox);
246 sendTask.send(mailboxTo, Common.TIMEOUT);
249 if (commReceive == null) {
250 commReceive = Task.irecv(this.mailbox);
252 commReceive.waitCompletion(Common.TIMEOUT);
253 Task taskReceived = commReceive.getTask();
254 if (taskReceived instanceof GetPredecessorAnswerTask) {
255 predecessorId = ((GetPredecessorAnswerTask) taskReceived).answerId;
259 handleTask(taskReceived);
265 catch (MsgException e) {
270 catch (MsgException e) {
271 Msg.debug("Failed to send the Get Predecessor request");
275 return predecessorId;
278 * @brief Makes the current node find the successor node of an id.
279 * @param node the current node
280 * @param id the id to find
281 * @return the id of the successor node, or -1 if the request failed
283 int findSuccessor(int id) {
284 if (isInInterval(id, this.id + 1, fingers[0])) {
288 int closest = this.closestPrecedingNode(id);
289 return remoteFindSuccessor(closest, id);
292 * @brief Asks another node the successor node of an id.
294 int remoteFindSuccessor(int askTo, int id) {
296 boolean stop = false;
297 String mailbox = Integer.toString(askTo);
298 Task sendTask = new FindSuccessorTask(host.getName(), this.mailbox, id);
299 Msg.debug("Sending a 'Find Successor' request to " + mailbox + " for id " + id);
301 sendTask.send(mailbox, Common.TIMEOUT);
303 if (commReceive == null) {
304 commReceive = Task.irecv(this.mailbox);
307 commReceive.waitCompletion(Common.TIMEOUT);
308 Task task = commReceive.getTask();
309 if (task instanceof FindSuccessorAnswerTask) {
310 //TODO: Check if this this our answer.
311 FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
313 successor = fTask.answerId;
320 catch (TimeoutException e) {
326 catch (TimeoutException e) {
327 Msg.debug("Failed to send the 'Find Successor' request");
329 catch (MsgException e) {
330 Msg.debug("Failed to receive Find Successor");
337 * @brief This function is called periodically. It checks the immediate
338 * successor of the current node.
341 Msg.debug("Stabilizing node");
343 int successorId = fingers[0];
344 if (successorId != this.id){
345 candidateId = remoteGetPredecessor(successorId);
348 candidateId = predId;
350 //This node is a candidate to become my new successor
351 if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
352 setFinger(0, candidateId);
354 if (successorId != this.id) {
355 remoteNotify(successorId, this.id);
360 * \brief Notifies the current node that its predecessor may have changed.
361 * \param candidate_id the possible new predecessor
363 void notify(int predecessorCandidateId) {
364 if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
365 setPredecessor(predecessorCandidateId);
368 //Don't have to change the predecessor.
372 * \brief Notifies a remote node that its predecessor may have changed.
373 * \param notify_id id of the node to notify
374 * \param candidate_id the possible new predecessor
376 void remoteNotify(int notifyId, int predecessorCandidateId) {
377 Msg.debug("Sending a 'Notify' request to " + notifyId);
378 Task sentTask = new NotifyTask(host.getName(), this.mailbox, predecessorCandidateId);
379 sentTask.dsend(Integer.toString(notifyId));
382 * \brief This function is called periodically.
383 * It refreshes the finger table of the current node.
386 Msg.debug("Fixing fingers");
387 int i = this.nextFingerToFix;
388 int id = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
390 if (id != fingers[i]) {
393 nextFingerToFix = (i + 1) % Common.NB_BITS;
397 * \brief This function is called periodically.
398 * It checks whether the predecessor has failed
400 void checkPredecessor() {
404 * \brief Performs a find successor request to a random id.
406 void randomLookup() {
408 //Msg.info("Making a lookup request for id " + id);
415 * @brief Returns the closest preceding finger of an id
416 * with respect to the finger table of the current node.
417 * @param id the id to find
418 * \return the closest preceding finger of that id
420 int closestPrecedingNode(int id) {
422 for (i = Common.NB_BITS - 1; i >= 0; i--) {
423 if (isInInterval(fingers[i], this.id + 1, id - 1)) {
430 * @brief Returns whether an id belongs to the interval [start, end].
432 * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
433 * 1 belongs to [62, 3]
434 * 1 does not belong to [3, 62]
435 * 63 belongs to [62, 3]
436 * 63 does not belong to [3, 62]
437 * 24 belongs to [21, 29]
438 * 24 does not belong to [29, 21]
440 * \param id id to check
441 * \param start lower bound
442 * \param end upper bound
443 * \return a non-zero value if id in in [start, end]
445 static boolean isInInterval(int id, int start, int end) {
447 start = normalize(start);
448 end = normalize(end);
450 // make sure end >= start and id >= start
452 end += Common.NB_KEYS;
455 id += Common.NB_KEYS;
461 * @brief Turns an id into an equivalent id in [0, nb_keys).
463 * @return the corresponding normalized id
465 static int normalize(int id) {
466 return id & (Common.NB_KEYS - 1);
469 * \brief Sets a finger of the current node.
470 * \param finger_index index of the finger to set (0 to nb_bits - 1)
471 * \param id the id to set for this finger
473 void setFinger(int fingerIndex, int id) {
474 if (id != fingers[fingerIndex]) {
475 fingers[fingerIndex] = id;
476 lastChangeDate = Msg.getClock();