2 * Copyright 2006-2012. The SimGrid Team. All rights reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package.
9 import org.simgrid.msg.Comm;
10 import org.simgrid.msg.Host;
11 import org.simgrid.msg.Msg;
12 import org.simgrid.msg.MsgException;
13 import org.simgrid.msg.Process;
14 import org.simgrid.msg.Task;
15 import org.simgrid.msg.TimeoutException;
19 public class Node extends Process {
27 protected String mailbox;
35 protected String predMailbox;
37 * Index of the next finger to fix
39 protected int nextFingerToFix;
41 * Current communication
43 protected Comm commReceive;
45 * Last time I changed a finger or my predecessor
47 protected double lastChangeDate;
55 public Node(Host host, String name, String[] args) {
56 super(host,name,args);
59 public void main(String[] args) throws MsgException {
60 if (args.length != 2 && args.length != 4) {
61 Msg.info("You need to provide 2 or 4 arguments.");
64 double initTime = Msg.getClock();
66 boolean joinSuccess = false;
69 double nextStabilizeDate = initTime + Common.PERIODIC_STABILIZE_DELAY;
70 double nextFixFingersDate = initTime + Common.PERIODIC_FIX_FINGERS_DELAY;
71 double nextCheckPredecessorDate = initTime + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
72 double nextLookupDate = initTime + Common.PERIODIC_LOOKUP_DELAY;
74 id = Integer.valueOf(args[0]);
75 mailbox = Integer.toString(id);
77 fingers = new int[Common.NB_BITS];
78 for (i = 0; i < Common.NB_BITS; i++) {
84 if (args.length == 2) {
85 deadline = Integer.valueOf(args[1]);
90 int knownId = Integer.valueOf(args[1]);
91 deadline = Integer.valueOf(args[3]);
92 //Msg.info("Hey! Let's join the system with the id " + id + ".");
94 joinSuccess = join(knownId);
97 double currentClock = Msg.getClock();
98 while (currentClock < (initTime + deadline) && currentClock < Common.MAX_SIMULATION_TIME) {
99 if (commReceive == null) {
100 commReceive = Task.irecv(this.mailbox);
103 if (!commReceive.test()) {
104 if (currentClock >= nextStabilizeDate) {
106 nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
108 else if (currentClock >= nextFixFingersDate) {
110 nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
112 else if (currentClock >= nextCheckPredecessorDate) {
113 this.checkPredecessor();
114 nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
116 else if (currentClock >= nextLookupDate) {
118 nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
123 currentClock = Msg.getClock();
126 handleTask(commReceive.getTask());
127 currentClock = Msg.getClock();
132 catch (Exception e) {
133 currentClock = Msg.getClock();
139 if (commReceive != null) {
144 Msg.info("I couldn't join the ring");
147 void handleTask(Task task) {
148 if (task instanceof FindSuccessorTask) {
149 FindSuccessorTask fTask = (FindSuccessorTask)task;
150 Msg.debug("Receiving a 'Find Successor' request from " + fTask.issuerHostName + " for id " + fTask.requestId);
151 // is my successor the successor?
152 if (isInInterval(fTask.requestId, this.id + 1, fingers[0])) {
153 //Msg.info("Send the request to " + fTask.answerTo + " with answer " + fingers[0]);
154 FindSuccessorAnswerTask answer = new FindSuccessorAnswerTask(host.getName(), mailbox, fingers[0]);
155 answer.dsend(fTask.answerTo);
158 // otherwise, forward the request to the closest preceding finger in my table
159 int closest = closestPrecedingNode(fTask.requestId);
160 //Msg.info("Forward the request to " + closest);
161 fTask.dsend(Integer.toString(closest));
164 else if (task instanceof GetPredecessorTask) {
165 GetPredecessorTask gTask = (GetPredecessorTask)(task);
166 Msg.debug("Receiving a 'Get Predecessor' request from " + gTask.issuerHostName);
167 GetPredecessorAnswerTask answer = new GetPredecessorAnswerTask(host.getName(), mailbox, predId);
168 answer.dsend(gTask.answerTo);
170 else if (task instanceof NotifyTask) {
171 NotifyTask nTask = (NotifyTask)task;
172 notify(nTask.requestId);
175 Msg.debug("Ignoring unexpected task of type:" + task);
179 * @brief Makes the current node quit the system
182 Msg.debug("Well Guys! I Think it's time for me to quit ;)");
183 quitNotify(1); //Notify my successor
184 quitNotify(-1); //Notify my predecessor.
188 * @brief Notifies the successor or the predecessor of the current node
190 * @param to 1 to notify the successor, -1 to notify the predecessor
192 static void quitNotify( int to) {
196 * @brief Initializes the current node as the first one of the system.
199 Msg.debug("Create a new Chord ring...");
204 * Makes the current node join the ring, knowing the id of a node
205 * already in the ring
207 boolean join(int knownId) {
208 Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
210 int successorId = remoteFindSuccessor(knownId, this.id);
211 if (successorId == -1) {
212 Msg.info("Cannot join the ring.");
215 setFinger(0, successorId);
217 return successorId != -1;
221 * Sets the node predecessor
223 void setPredecessor(int predecessorId) {
224 if (predecessorId != predId) {
225 predId = predecessorId;
226 if (predecessorId != -1) {
227 predMailbox = Integer.toString(predId);
229 lastChangeDate = Msg.getClock();
233 * @brief Asks another node its predecessor.
234 * @param askTo the node to ask to
235 * @return the id of its predecessor node, or -1 if the request failed
236 * (or if the node does not know its predecessor)
238 int remoteGetPredecessor(int askTo) {
239 int predecessorId = -1;
240 boolean stop = false;
241 Msg.debug("Sending a 'Get Predecessor' request to " + askTo);
242 String mailboxTo = Integer.toString(askTo);
243 GetPredecessorTask sendTask = new GetPredecessorTask(host.getName(), this.mailbox);
245 sendTask.send(mailboxTo, Common.TIMEOUT);
248 if (commReceive == null) {
249 commReceive = Task.irecv(this.mailbox);
251 commReceive.waitCompletion(Common.TIMEOUT);
252 Task taskReceived = commReceive.getTask();
253 if (taskReceived instanceof GetPredecessorAnswerTask) {
254 predecessorId = ((GetPredecessorAnswerTask) taskReceived).answerId;
258 handleTask(taskReceived);
264 catch (MsgException e) {
269 catch (MsgException e) {
270 Msg.debug("Failed to send the Get Predecessor request");
274 return predecessorId;
277 * @brief Makes the current node find the successor node of an id.
278 * @param node the current node
279 * @param id the id to find
280 * @return the id of the successor node, or -1 if the request failed
282 int findSuccessor(int id) {
283 if (isInInterval(id, this.id + 1, fingers[0])) {
287 int closest = this.closestPrecedingNode(id);
288 return remoteFindSuccessor(closest, id);
291 * @brief Asks another node the successor node of an id.
293 int remoteFindSuccessor(int askTo, int id) {
295 boolean stop = false;
296 String mailbox = Integer.toString(askTo);
297 Task sendTask = new FindSuccessorTask(host.getName(), this.mailbox, id);
298 Msg.debug("Sending a 'Find Successor' request to " + mailbox + " for id " + id);
300 sendTask.send(mailbox, Common.TIMEOUT);
302 if (commReceive == null) {
303 commReceive = Task.irecv(this.mailbox);
306 commReceive.waitCompletion(Common.TIMEOUT);
307 Task task = commReceive.getTask();
308 if (task instanceof FindSuccessorAnswerTask) {
309 //TODO: Check if this this our answer.
310 FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
312 successor = fTask.answerId;
319 catch (TimeoutException e) {
325 catch (TimeoutException e) {
326 Msg.debug("Failed to send the 'Find Successor' request");
328 catch (MsgException e) {
329 Msg.debug("Failed to receive Find Successor");
336 * @brief This function is called periodically. It checks the immediate
337 * successor of the current node.
340 Msg.debug("Stabilizing node");
342 int successorId = fingers[0];
343 if (successorId != this.id){
344 candidateId = remoteGetPredecessor(successorId);
347 candidateId = predId;
349 //This node is a candidate to become my new successor
350 if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
351 setFinger(0, candidateId);
353 if (successorId != this.id) {
354 remoteNotify(successorId, this.id);
359 * \brief Notifies the current node that its predecessor may have changed.
360 * \param candidate_id the possible new predecessor
362 void notify(int predecessorCandidateId) {
363 if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
364 setPredecessor(predecessorCandidateId);
367 //Don't have to change the predecessor.
371 * \brief Notifies a remote node that its predecessor may have changed.
372 * \param notify_id id of the node to notify
373 * \param candidate_id the possible new predecessor
375 void remoteNotify(int notifyId, int predecessorCandidateId) {
376 Msg.debug("Sending a 'Notify' request to " + notifyId);
377 Task sentTask = new NotifyTask(host.getName(), this.mailbox, predecessorCandidateId);
378 sentTask.dsend(Integer.toString(notifyId));
381 * \brief This function is called periodically.
382 * It refreshes the finger table of the current node.
385 Msg.debug("Fixing fingers");
386 int i = this.nextFingerToFix;
387 int id = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
389 if (id != fingers[i]) {
392 nextFingerToFix = (i + 1) % Common.NB_BITS;
396 * \brief This function is called periodically.
397 * It checks whether the predecessor has failed
399 void checkPredecessor() {
403 * \brief Performs a find successor request to a random id.
405 void randomLookup() {
407 //Msg.info("Making a lookup request for id " + id);
414 * @brief Returns the closest preceding finger of an id
415 * with respect to the finger table of the current node.
416 * @param id the id to find
417 * \return the closest preceding finger of that id
419 int closestPrecedingNode(int id) {
421 for (i = Common.NB_BITS - 1; i >= 0; i--) {
422 if (isInInterval(fingers[i], this.id + 1, id - 1)) {
429 * @brief Returns whether an id belongs to the interval [start, end].
431 * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
432 * 1 belongs to [62, 3]
433 * 1 does not belong to [3, 62]
434 * 63 belongs to [62, 3]
435 * 63 does not belong to [3, 62]
436 * 24 belongs to [21, 29]
437 * 24 does not belong to [29, 21]
439 * \param id id to check
440 * \param start lower bound
441 * \param end upper bound
442 * \return a non-zero value if id in in [start, end]
444 static boolean isInInterval(int id, int start, int end) {
446 start = normalize(start);
447 end = normalize(end);
449 // make sure end >= start and id >= start
451 end += Common.NB_KEYS;
454 id += Common.NB_KEYS;
460 * @brief Turns an id into an equivalent id in [0, nb_keys).
462 * @return the corresponding normalized id
464 static int normalize(int id) {
465 return id & (Common.NB_KEYS - 1);
468 * \brief Sets a finger of the current node.
469 * \param finger_index index of the finger to set (0 to nb_bits - 1)
470 * \param id the id to set for this finger
472 void setFinger(int fingerIndex, int id) {
473 if (id != fingers[fingerIndex]) {
474 fingers[fingerIndex] = id;
475 lastChangeDate = Msg.getClock();