simgrid-java/examples/chord/Node.java

   1 /*
   2  * Copyright 2006-2012. The SimGrid Team. All rights reserved.
   3  *
   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.
   6  */
   7 package chord;
   8
   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;
  16 /**
  17  * Node data
  18  */
  19 public class Node extends Process {
  20         /**
  21          * Node id
  22          */
  23         protected int id;
  24         /**
  25          * Node mailbox
  26          */
  27         protected String mailbox;
  28         /**
  29          * Predecessor id
  30          */
  31         protected int predId;
  32         /**
  33          * Predecessor mailbox
  34          */
  35         protected String predMailbox;
  36         /**
  37          * Index of the next finger to fix
  38          */
  39         protected int nextFingerToFix;
  40         /**
  41          * Current communication
  42          */
  43         protected Comm commReceive;
  44         /**
  45          * Last time I changed a finger or my predecessor
  46          */
  47         protected double lastChangeDate;
  48         /**
  49          * Node fingers
  50          */
  51         int fingers[];
  52         /**
  53          * Constructor
  54          */
  55         public Node(Host host, String name, String[] args) {
  56                 super(host,name,args);
  57         }
  58         @Override
  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.");
  62                         return;
  63                 }
  64                 double initTime = Msg.getClock();
  65                 int i;
  66                 boolean joinSuccess = false;
  67                 double deadline;
  68
  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;
  73
  74                 id = Integer.valueOf(args[0]);
  75                 mailbox = Integer.toString(id);
  76
  77                 fingers = new int[Common.NB_BITS];
  78                 for (i = 0; i < Common.NB_BITS; i++) {
  79                         fingers[i] = -1;
  80                         setFinger(i,this.id);
  81                 }
  82
  83                 //First node
  84                 if (args.length == 2) {
  85                         deadline = Integer.valueOf(args[1]);
  86                         create();
  87                         joinSuccess = true;
  88                 }
  89                 else {
  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 + ".");
  93
  94                         joinSuccess = join(knownId);
  95                 }
  96                 if (joinSuccess) {
  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);
 101                                 }
 102                                 try {
 103                                         if (!commReceive.test()) {
 104                                                 if (currentClock >= nextStabilizeDate) {
 105                                                         stabilize();
 106                                                         nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
 107                                                 }
 108                                                 else if (currentClock >= nextFixFingersDate) {
 109                                                         fixFingers();
 110                                                         nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
 111                                                 }
 112                                                 else if (currentClock >= nextCheckPredecessorDate) {
 113                                                         this.checkPredecessor();
 114                                                         nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
 115                                                 }
 116                                                 else if (currentClock >= nextLookupDate) {
 117                                                         this.randomLookup();
 118                                                         nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
 119                                                 }
 120                                                 else {
 121                                                         waitFor(5);
 122                                                 }
 123                                                 currentClock = Msg.getClock();
 124                                         }
 125                                         else {
 126                                                 handleTask(commReceive.getTask());
 127                                                 currentClock = Msg.getClock();
 128                                                 commReceive = null;
 129
 130                                         }
 131                                 }
 132                                 catch (Exception e) {
 133                                         currentClock = Msg.getClock();
 134                                         commReceive = null;
 135                                 }
 136
 137                         }
 138                         leave();
 139                         if (commReceive != null) {
 140                                 commReceive = null;
 141                         }
 142                 }
 143                 else {
 144                         Msg.info("I couldn't join the ring");
 145                 }
 146         }
 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);
 156                         }
 157                         else {
 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));
 162                         }
 163                 }
 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);
 169                 }
 170                 else if (task instanceof NotifyTask) {
 171                         NotifyTask nTask = (NotifyTask)task;
 172                         notify(nTask.requestId);
 173                 }
 174                 else {
 175                         Msg.debug("Ignoring unexpected task of type:" + task);
 176                 }
 177         }
 178         /**
 179          * @brief Makes the current node quit the system
 180          */
 181         void leave() {
 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.
 185                 // TODO ...
 186         }
 187         /**
 188          * @brief Notifies the successor or the predecessor of the current node
 189          * of the departure
 190          * @param to 1 to notify the successor, -1 to notify the predecessor
 191          */
 192         static void quitNotify( int to) {
 193                 //TODO
 194         }
 195         /**
 196       * @brief Initializes the current node as the first one of the system.
 197          */
 198         void create() {
 199                 Msg.debug("Create a new Chord ring...");
 200                 setPredecessor(-1);
 201
 202         }
 203         /**
 204          * Makes the current node join the ring, knowing the id of a node
 205          * already in the ring
 206          */
 207         boolean join(int knownId) {
 208                 Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
 209                 setPredecessor(-1);
 210                 int successorId = remoteFindSuccessor(knownId, this.id);
 211                 if (successorId == -1) {
 212                         Msg.info("Cannot join the ring.");
 213                 }
 214                 else {
 215                         setFinger(0, successorId);
 216                 }
 217                 return successorId != -1;
 218         }
 219
 220         /**
 221          * Sets the node predecessor
 222          */
 223         void setPredecessor(int predecessorId) {
 224                 if (predecessorId != predId) {
 225                         predId = predecessorId;
 226                         if (predecessorId != -1) {
 227                                 predMailbox = Integer.toString(predId);
 228                         }
 229                         lastChangeDate = Msg.getClock();
 230                 }
 231         }
 232         /**
 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)
 237          */
 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);
 244                 try {
 245                         sendTask.send(mailboxTo, Common.TIMEOUT);
 246                         try {
 247                                 do {
 248                                         if (commReceive == null) {
 249                                                 commReceive = Task.irecv(this.mailbox);
 250                                         }
 251                                         commReceive.waitCompletion(Common.TIMEOUT);
 252                                         Task taskReceived = commReceive.getTask();
 253                                         if (taskReceived instanceof GetPredecessorAnswerTask) {
 254                                                 predecessorId = ((GetPredecessorAnswerTask) taskReceived).answerId;
 255                                                 stop = true;
 256                                         }
 257                                         else {
 258                                                 handleTask(taskReceived);
 259                                         }
 260                                         commReceive = null;
 261                                 } while (!stop);
 262
 263                         }
 264                         catch (MsgException e) {
 265                                 commReceive = null;
 266                                 stop = true;
 267                         }
 268                 }
 269                 catch (MsgException e) {
 270                         Msg.debug("Failed to send the Get Predecessor request");
 271                 }
 272
 273
 274                 return predecessorId;
 275         }
 276         /**
 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
 281          */
 282         int findSuccessor(int id) {
 283                 if (isInInterval(id, this.id + 1, fingers[0])) {
 284                         return fingers[0];
 285                 }
 286
 287                 int closest = this.closestPrecedingNode(id);
 288                 return remoteFindSuccessor(closest, id);
 289         }
 290         /**
 291          * @brief Asks another node the successor node of an id.
 292          */
 293         int remoteFindSuccessor(int askTo, int id) {
 294                 int successor = -1;
 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);
 299                 try {
 300                         sendTask.send(mailbox, Common.TIMEOUT);
 301                         do {
 302                                 if (commReceive == null) {
 303                                         commReceive = Task.irecv(this.mailbox);
 304                                 }
 305                                 try {
 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;
 311                                                 stop = true;
 312                                                 successor = fTask.answerId;
 313                                         }
 314                                         else {
 315                                                 handleTask(task);
 316                                         }
 317                                         commReceive = null;
 318                                 }
 319                                 catch (TimeoutException e) {
 320                                         stop = true;
 321                                         commReceive = null;
 322                                 }
 323                         } while (!stop);
 324                 }
 325                 catch (TimeoutException e) {
 326                         Msg.debug("Failed to send the 'Find Successor' request");
 327                 }
 328                 catch (MsgException e) {
 329                         Msg.debug("Failed to receive Find Successor");
 330                 }
 331
 332                 return successor;
 333
 334         }
 335         /**
 336          * @brief This function is called periodically. It checks the immediate
 337          * successor of the current node.
 338          */
 339         void stabilize() {
 340                 Msg.debug("Stabilizing node");
 341                 int candidateId;
 342                 int successorId = fingers[0];
 343                 if (successorId != this.id){
 344                         candidateId = remoteGetPredecessor(successorId);
 345                 }
 346                 else {
 347                         candidateId = predId;
 348                 }
 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);
 352                 }
 353                 if (successorId != this.id) {
 354                         remoteNotify(successorId, this.id);
 355                 }
 356
 357         }
 358         /**
 359          * \brief Notifies the current node that its predecessor may have changed.
 360          * \param candidate_id the possible new predecessor
 361          */
 362         void notify(int predecessorCandidateId) {
 363                 if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
 364                         setPredecessor(predecessorCandidateId);
 365                 }
 366                 else {
 367                         //Don't have to change the predecessor.
 368                 }
 369         }
 370         /**
 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
 374          */
 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));
 379         }
 380         /**
 381          * \brief This function is called periodically.
 382          * It refreshes the finger table of the current node.
 383          */
 384         void fixFingers() {
 385                 Msg.debug("Fixing fingers");
 386                 int i = this.nextFingerToFix;
 387                 int id = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
 388                 if (id != -1) {
 389                         if (id != fingers[i]) {
 390                                 setFinger(i, id);
 391                         }
 392                         nextFingerToFix = (i + 1) % Common.NB_BITS;
 393                 }
 394         }
 395         /**
 396          * \brief This function is called periodically.
 397          * It checks whether the predecessor has failed
 398          */
 399         void checkPredecessor() {
 400                 //TODO
 401         }
 402         /**
 403          * \brief Performs a find successor request to a random id.
 404          */
 405         void randomLookup() {
 406                 int id = 1337;
 407                 //Msg.info("Making a lookup request for id " + id);
 408                 findSuccessor(id);
 409         }
 410
 411
 412
 413         /**
 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
 418          */
 419         int closestPrecedingNode(int id) {
 420                 int i;
 421                 for (i = Common.NB_BITS - 1; i >= 0; i--) {
 422                         if (isInInterval(fingers[i], this.id + 1, id - 1)) {
 423                                 return fingers[i];
 424                         }
 425                 }
 426                 return this.id;
 427         }
 428         /**
 429          * @brief Returns whether an id belongs to the interval [start, end].
 430          *
 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]
 438          *
 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]
 443          */
 444         static boolean isInInterval(int id, int start, int end) {
 445                 id = normalize(id);
 446                 start = normalize(start);
 447                 end = normalize(end);
 448
 449                 // make sure end >= start and id >= start
 450                 if (end < start) {
 451                         end += Common.NB_KEYS;
 452                 }
 453                 if (id < start) {
 454                         id += Common.NB_KEYS;
 455                 }
 456                 return (id <= end);
 457
 458         }
 459         /**
 460          * @brief Turns an id into an equivalent id in [0, nb_keys).
 461          * @param id an id
 462          * @return the corresponding normalized id
 463          */
 464         static int normalize(int id) {
 465                 return id & (Common.NB_KEYS - 1);
 466         }
 467         /**
 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
 471          */
 472         void setFinger(int fingerIndex, int id) {
 473                 if (id != fingers[fingerIndex]) {
 474                         fingers[fingerIndex] = id;
 475                         lastChangeDate = Msg.getClock();
 476                 }
 477         }
 478 }