${CMAKE_HOME_DIRECTORY}/examples/commTime/Master.java
${CMAKE_HOME_DIRECTORY}/examples/commTime/Slave.java
${CMAKE_HOME_DIRECTORY}/examples/commTime/CommTimeTest.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Answer.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Bucket.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Common.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Contact.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Kademlia.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/Node.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/RoutingTable.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/FindNodeAnswerTask.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/FindNodeTask.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/KademliaTask.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/PingAnswerTask.java
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/PingTask.java
${CMAKE_HOME_DIRECTORY}/examples/io/IO.java
${CMAKE_HOME_DIRECTORY}/examples/io/Node.java
${CMAKE_HOME_DIRECTORY}/examples/masterslave/FinalizeTask.java
${CMAKE_HOME_DIRECTORY}/examples/chord/chord10000.xml
${CMAKE_HOME_DIRECTORY}/examples/chord/chord1000.xml
${CMAKE_HOME_DIRECTORY}/examples/chord/chord90.xml
- ${CMAKE_HOME_DIRECTORY}/examples/suspend/suspendDeployment.xml
+ ${CMAKE_HOME_DIRECTORY}/examples/kademlia/kademlia.xml
${CMAKE_HOME_DIRECTORY}/examples/master_slave_kill/platform.xml
${CMAKE_HOME_DIRECTORY}/examples/mutualExclusion/centralized/mutex_centralized_deployment.xml
${CMAKE_HOME_DIRECTORY}/examples/mutualExclusion/ring3.xml
${CMAKE_HOME_DIRECTORY}/examples/startKillTime/deployment_start.xml
${CMAKE_HOME_DIRECTORY}/examples/startKillTime/deployment_start_kill.xml
${CMAKE_HOME_DIRECTORY}/examples/startKillTime/deployment.xml
+ ${CMAKE_HOME_DIRECTORY}/examples/suspend/suspendDeployment.xml
${CMAKE_HOME_DIRECTORY}/examples/io/storage.xml
${CMAKE_HOME_DIRECTORY}/examples/tracing/tracingPingPongDeployment.xml
)
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/chord/*.java
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/cloud/*.java
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/commTime/*.java
+ COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/kademlia/*.java
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/io/*.java
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/masterslave/*.java
COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/master_slave_bypass/*.java
ADD_TEST(commTime ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/commTime/commtime.tesh)
ADD_TEST(chord ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/chord/chord.tesh)
ADD_TEST(cloud ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/cloud/cloud.tesh)
+ADD_TEST(kademlia ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/kademlia/kademlia.tesh)
ADD_TEST(kill ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/master_slave_kill/kill.tesh)
ADD_TEST(masterslave ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/masterslave/masterslave.tesh)
ADD_TEST(migration ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/migration/migration.tesh)
ADD_TEST(startKillTime ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/startKillTime/startKillTime.tesh)
ADD_TEST(suspend ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/suspend/suspend.tesh)
#Don't forget to put new test in this list!!!
-set(test_list async bittorrent bypass chord cloud commTime kill masterslave migration mutualExclusion pingPong priority startKillTime suspend)
+set(test_list async bittorrent bypass chord cloud commTime kademlia kill masterslave migration mutualExclusion pingPong priority startKillTime suspend)
if(HAVE_TRACING)
ADD_TEST(tracing ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE_HOME_DIRECTORY} ${CMAKE_HOME_DIRECTORY}/examples/tracing/tracingPingPong.tesh)
set(test_list ${test_list} tracing)
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+import java.util.ArrayList;
+import java.util.Collections;
+
+/**
+ * Answer to a "FIND_NODE" query. Contains the nodes closest to
+ * an id given.
+ */
+public class Answer {
+ /**
+ * Id of the node we're trying to find
+ */
+ private int destinationId;
+ /**
+ * Closest nodes in the answer.
+ */
+ private ArrayList<Contact> nodes;
+
+ /**
+ * Constructor
+ */
+ public Answer(int destinationId) {
+ this.destinationId = destinationId;
+ nodes = new ArrayList<Contact>();
+ }
+ /**
+ * Returns the destination id
+ */
+ int getDestinationId() {
+ return destinationId;
+ }
+ /**
+ * Returns the list of the nodes in the answer
+ */
+ ArrayList<Contact> getNodes() {
+ return nodes;
+ }
+ /**
+ * Returns the answer array size
+ */
+ int size() {
+ return nodes.size();
+ }
+ /**
+ * Remove an element from the answer.
+ */
+ public void remove(int index) {
+ nodes.remove(index);
+ }
+ /**
+ * Add a contact to the answer.
+ */
+ public void add(Contact contact) {
+ nodes.add(contact);
+ }
+ /**
+ * Merge the contents of this answer with another answer
+ */
+ public int merge(Answer answer) {
+ int nbAdded = 0;
+
+ for (Contact c: answer.getNodes()) {
+ if (!nodes.contains(c)) {
+ nbAdded++;
+ nodes.add(c);
+ }
+ }
+ Collections.sort(nodes);
+ //Trim the list
+ while (answer.size() > Common.BUCKET_SIZE) {
+ answer.remove(answer.size() - 1);
+ }
+ return nbAdded;
+ }
+ /**
+ * Returns if the destination has been found
+ */
+ public boolean destinationFound() {
+ if (nodes.size() < 1) {
+ return false;
+ }
+ Contact tail = nodes.get(0);
+ return tail.getDistance() == 0;
+ }
+ @Override
+ public String toString() {
+ return "Answer [destinationId=" + destinationId + ", nodes=" + nodes
+ + "]";
+ }
+
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+package kademlia;
+
+import java.util.ArrayList;
+
+/**
+ * Stores the information held in a bucket
+ */
+public class Bucket {
+ private ArrayList<Integer> nodes;
+ private int id;
+
+ /**
+ * Constructor
+ */
+ public Bucket(int id) {
+ this.nodes = new ArrayList<Integer>();
+ this.id = id;
+ }
+ /**
+ * Returns the bucket's id.
+ */
+ public int getId() {
+ return this.id;
+ }
+ /**
+ * Returns how many nodes there is in the bucket
+ */
+ public int size() {
+ return nodes.size();
+ }
+ /**
+ * Returns if the bucket contains the element
+ */
+ public boolean contains(int id) {
+ return nodes.contains(id);
+ }
+ /**
+ * Add an to the front of the bucket
+ */
+ public void add(int id) {
+ nodes.add(0,id);
+ }
+ /**
+ * Pushs an element into the front of a bucket.
+ */
+ public void pushToFront(int id) {
+ int i = nodes.indexOf(id);
+ nodes.remove(i);
+ nodes.add(0, id);
+ }
+ /**
+ * Returns a node
+ */
+ public int getNode(int id) {
+ return nodes.get(id);
+ }
+ /**
+ * Adds the content of the bucket into a answer object.
+ */
+ public void addToAnswer(Answer answer, int destination) {
+ for (int id : this.nodes) {
+ answer.getNodes().add(new Contact(id,id ^ destination));
+ }
+ }
+
+ @Override
+ public String toString() {
+ return "Bucket [id= " + id + " nodes=" + nodes + "]";
+ }
+
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+package kademlia;
+/**
+ * Common constants used all over the simulation
+ */
+public class Common {
+ public final static int COMM_SIZE = 1;
+ public final static int COMP_SIZE = 0;
+
+ public final static int RANDOM_LOOKUP_INTERVAL = 100;
+
+ public final static int alpha = 3;
+ /**
+ * Size of the nodes identifier
+ */
+ public final static int IDENTIFIER_SIZE = 32;
+ /**
+ * Maximum size of the buckets
+ */
+ public final static int BUCKET_SIZE = 20;
+ /**
+ * Maximum number of trial for the "JOIN" request
+ */
+ public final static int MAX_JOIN_TRIALS = 4;
+ /**
+ * Timeout for a "FIND_NODE" request to a node
+ */
+ public final static int FIND_NODE_TIMEOUT = 10;
+ /**
+ * Global timeout for a FIND_NODE.
+ */
+ public final static int FIND_NODE_GLOBAL_TIMEOUT = 50;
+ /**
+ * Timeout for a "PING" request
+ */
+ public final static int PING_TIMEOUT = 35;
+
+ public final static int MAX_STEPS = 10;
+
+ public final static int JOIN_BUCKETS_QUERIES = 1;
+}
--- /dev/null
+package kademlia;
+
+/**
+ * Contains the information about a foreign node according to
+ * a node we are trying to find.
+ */
+public class Contact implements Comparable<Object> {
+ private int id;
+ private int distance;
+
+ public Contact(int id, int distance) {
+ this.id = id;
+ this.distance = distance;
+ }
+
+ public int getId() {
+ return id;
+ }
+
+ public int getDistance() {
+ return distance;
+ }
+
+ public boolean equals(Object x) {
+ return x.equals(id) ;
+ }
+
+ public int compareTo(Object o) {
+ Contact c = (Contact)o;
+ if (distance < c.distance) {
+ return -1;
+ }
+ else if (distance == c.distance) {
+ return 0;
+ }
+ else {
+ return 1;
+ }
+ }
+
+ @Override
+ public String toString() {
+ return "Contact [id=" + id + ", distance=" + distance + "]";
+ }
+
+}
\ No newline at end of file
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+import kademlia.Answer;
+
+public class FindNodeAnswerTask extends KademliaTask {
+ /**
+ * Destination id
+ */
+ protected int destinationId;
+ /**
+ * Answer to the FIND_NODE query.
+ */
+ protected Answer answer;
+ /**
+ * Constructor
+ */
+ public FindNodeAnswerTask(int senderId, int destinationId, Answer answer) {
+ super(senderId);
+ this.destinationId = destinationId;
+ this.answer = answer;
+ }
+ public int getDestinationId() {
+ return destinationId;
+ }
+ public Answer getAnswer() {
+ return answer;
+ }
+
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+/**
+ * @brief Find node tasks sent by a node to another
+ * "Find Node" task sent by a node to another. Ask him for
+ * its closest nodes from a destination.
+ */
+public class FindNodeTask extends KademliaTask {
+ /**
+ * Id of the node we are trying to find: the destination
+ */
+ private int destination;
+ /**
+ * Constructor
+ */
+ public FindNodeTask(int senderId, int destination) {
+ super(senderId);
+ this.destination = destination;
+ }
+
+
+
+ public int getDestination() {
+ return destination;
+ }
+
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+package kademlia;
+import org.simgrid.msg.Msg;
+import org.simgrid.msg.MsgException;
+/**
+ * Main class of the simulation. Launch the simulation.
+ */
+public class Kademlia {
+ public static void main(String[] args) throws MsgException {
+ /* initialize the MSG simulation. Must be done before anything else (even logging). */
+ Msg.init(args);
+ if(args.length < 2) {
+ Msg.info("Usage : Kademlia platform_file deployment_file");
+ Msg.info("example : Kademlia platform.xml deployment.xml");
+ System.exit(1);
+ }
+
+ /* construct the platform and deploy the application */
+ Msg.createEnvironment(args[0]);
+ Msg.deployApplication(args[1]);
+
+ /* execute the simulation. */
+ Msg.run();
+ }
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+import kademlia.Common;
+
+import org.simgrid.msg.Task;
+
+/**
+ * @brief Base class for all the tasks related to Kademlia.
+ */
+public class KademliaTask extends Task {
+ /**
+ * Sender id
+ */
+ protected int senderId;
+
+ /**
+ * Constructor
+ */
+ public KademliaTask(int senderId) {
+ super("kademliatask",Common.COMP_SIZE,Common.COMM_SIZE);
+ this.senderId = senderId;
+ }
+ public int getSenderId() {
+ return senderId;
+ }
+}
--- /dev/null
+package kademlia;
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+import org.simgrid.msg.Host;
+
+import org.simgrid.msg.Comm;
+import org.simgrid.msg.Msg;
+import org.simgrid.msg.MsgException;
+import org.simgrid.msg.Process;
+import org.simgrid.msg.Task;
+/**
+ * Main class of the simulation, contains the logic of a node.
+ */
+public class Node extends Process {
+ /**
+ * Id in the network.
+ */
+ protected int id;
+ /**
+ * Routing table
+ */
+ protected RoutingTable table;
+ /**
+ * Deadline
+ */
+ protected int deadline;
+ /**
+ * FIND_NODE which have succeeded.
+ */
+ protected int findNodeSuccedded = 0;
+ /**
+ * FIND_NODE which have failed
+ */
+ protected int findNodeFailed = 0;
+
+ protected Comm comm;
+
+ public Node(Host host, String name, String[]args) {
+ super(host,name,args);
+ }
+
+ @Override
+ public void main(String[] args) throws MsgException {
+ //Check the number of arguments.
+ if (args.length != 2 && args.length != 3) {
+ Msg.info("Wrong argument count.");
+ return;
+ }
+ this.id = Integer.valueOf(args[0]);
+ this.table = new RoutingTable(this.id);
+
+ if (args.length == 3) {
+ this.deadline = Integer.valueOf(args[2]).intValue();
+ Msg.info("Hi, I'm going to join the network with the id " + id + "!");
+ if (joinNetwork(Integer.valueOf(args[1]))) {
+ this.mainLoop();
+ }
+ else {
+ Msg.info("I couldn't join the network :(");
+ }
+ }
+ else {
+ this.deadline = Integer.valueOf(args[1]).intValue();
+ Msg.info("Hi, I'm going to create the network with the id " + id + "!");
+ table.update(this.id);
+ this.mainLoop();
+ }
+ Msg.debug("I'm leaving the network");
+ Msg.debug("Here is my routing table:" + table);
+ }
+ /**
+ * Node main loop
+ */
+ public void mainLoop() {
+ double next_lookup_time = Msg.getClock() + Common.RANDOM_LOOKUP_INTERVAL;
+ while (Msg.getClock() < this.deadline) {
+ try {
+ if (comm == null) {
+ comm = Task.irecv(Integer.toString(id));
+ }
+ if (!comm.test()) {
+ if (Msg.getClock() >= next_lookup_time) {
+ randomLookup();
+ next_lookup_time += Common.RANDOM_LOOKUP_INTERVAL;
+ }
+ else {
+ waitFor(1);
+ }
+ }
+ else {
+ Task task = comm.getTask();
+ handleTask(task);
+ comm = null;
+ }
+ }
+ catch (Exception e) {
+
+ }
+ }
+ Msg.info(findNodeSuccedded + "/" + (findNodeSuccedded + findNodeFailed) + " FIND_NODE have succedded.");
+ }
+ /**
+ * @brief Try to make the node join the network
+ * @param idKnown Id of someone we know in the system
+ */
+ public boolean joinNetwork(int idKnown) {
+ boolean answerGot = false;
+ double timeBegin = Msg.getClock();
+ Msg.debug("Joining the network knowing " + idKnown);
+ //Add ourselves and the node we know to our routing table
+ table.update(this.id);
+ table.update(idKnown);
+ //Send a "FIND_NODE" to the node we know.
+ sendFindNode(idKnown,this.id);
+ //Wait for the answer.
+ int trials = 0;
+
+ do {
+ try {
+ if (comm == null) {
+ comm = Task.irecv(Integer.toString(id));
+ }
+ if (comm != null) {
+ if (!comm.test()) {
+ waitFor(1);
+ }
+ else {
+ Task task = comm.getTask();
+ if (task instanceof FindNodeAnswerTask) {
+ answerGot = true;
+ //Retrieve the node list and ping them
+ FindNodeAnswerTask answerTask = (FindNodeAnswerTask)task;
+ Answer answer = answerTask.getAnswer();
+ answerGot = true;
+ //answersGotten++;
+ if (answer.getDestinationId() == this.id) {
+ //Ping everyone in the list
+ for (Contact c : answer.getNodes()) {
+ table.update(c.getId());
+ }
+ }
+ }
+ else {
+ handleTask(task);
+ }
+ comm = null;
+ }
+ }
+
+ }
+ catch (Exception ex) {
+ trials++;
+ Msg.info("FIND_NODE failed");
+ }
+ } while (!answerGot && trials < Common.MAX_JOIN_TRIALS);
+ /* Second step: Send a FIND_NODE in a node in each bucket */
+ int bucketId = table.findBucket(idKnown).getId();
+ for (int i = 0; ((bucketId - i) > 0 ||
+ (bucketId + i) <= Common.IDENTIFIER_SIZE) &&
+ i < Common.JOIN_BUCKETS_QUERIES; i++) {
+ if (bucketId - i > 0) {
+ int idInBucket = table.getIdInPrefix(this.id,bucketId - i);
+ this.findNode(idInBucket,false);
+ }
+ if (bucketId + i <= Common.IDENTIFIER_SIZE) {
+ int idInBucket = table.getIdInPrefix(this.id,bucketId + i);
+ findNode(idInBucket,false);
+ }
+ }
+ Msg.debug("Time spent:" + (Msg.getClock() - timeBegin));
+ return answerGot;
+ }
+ /**
+ * Send a request to find a node in the node's routing table.
+ */
+ public boolean findNode(int destination, boolean counts) {
+ int queries, answers, totalQueries = 0, totalAnswers = 0;
+ int nodesAdded = 0;
+ boolean destinationFound = false;
+ int steps = 0;
+ double timeBeginReceive;
+ double timeout, globalTimeout = Msg.getClock() + Common.FIND_NODE_GLOBAL_TIMEOUT;
+ //Build a list of the closest nodes we already know.
+ Answer nodeList = table.findClosest(destination);
+ Msg.debug("Doing a FIND_NODE on " + destination);
+ do {
+ answers = 0;
+ queries = this.sendFindNodeToBest(nodeList);
+ totalQueries += queries;
+ nodesAdded = 0;
+ timeout = Msg.getClock() + Common.FIND_NODE_TIMEOUT;
+ steps++;
+ do {
+ try {
+ timeBeginReceive = Msg.getClock();
+ if (comm == null) {
+ comm = Task.irecv(Integer.toString(id));
+ }
+ comm.waitCompletion(10);
+ if (!comm.test()) {
+ waitFor(1);
+ }
+ else {
+ Task task = comm.getTask();
+ if (task instanceof FindNodeAnswerTask) {
+ FindNodeAnswerTask answerTask = (FindNodeAnswerTask)task;
+ //Check if we received what we are looking for.
+ if (answerTask.getDestinationId() == destination) {
+ table.update(answerTask.getSenderId());
+ //Add the answer to our routing table
+ for (Contact c: answerTask.getAnswer().getNodes()) {
+ table.update(c.getId());
+ }
+ answers++;
+ totalAnswers++;
+
+ nodesAdded = nodeList.merge(answerTask.getAnswer());
+ }
+ else {
+ handleTask(task);
+ timeout += Msg.getClock() - timeBeginReceive;
+ }
+ }
+ else {
+ handleTask(task);
+ timeout += Msg.getClock() - timeBeginReceive;
+ }
+ comm = null;
+ }
+ }
+ catch (Exception e) {
+ comm = null;
+ }
+ } while (answers < queries && Msg.getClock() < timeout);
+ destinationFound = nodeList.destinationFound();
+ } while (!destinationFound && (nodesAdded > 0 || answers == 0) && Msg.getClock() < globalTimeout && steps < Common.MAX_STEPS);
+
+ if (destinationFound) {
+ if (counts) {
+ findNodeSuccedded++;
+ }
+ Msg.debug("Find node on " + destination + " succedded with " + totalQueries + " queries and " + totalAnswers + " answers");
+ }
+ else {
+ Msg.debug("Find node on " + destination + " failed");
+ Msg.debug("Queried " + queries + " nodes to find " + destination + ", got " + totalAnswers + " answers");
+ Msg.debug(nodeList.toString());
+ if (counts) {
+ findNodeFailed++;
+ }
+ }
+ return destinationFound;
+ }
+ /**
+ * Sends a "PING" request to a node
+ * @param destination Ping destination id.
+ */
+ public void ping(int destination) {
+ boolean destinationFound = false;
+ double timeout = Msg.getClock() + Common.PING_TIMEOUT;
+ PingTask pingTask = new PingTask(this.id);
+ /* Sending the ping task */
+ pingTask.dsend(Integer.toString(destination));
+ do
+ {
+ try {
+ Task task = Task.receive(Integer.toString(this.id),Common.PING_TIMEOUT);
+ if (task instanceof PingAnswerTask) {
+ PingAnswerTask answerTask = (PingAnswerTask)task;
+ if (answerTask.getSenderId() == destination) {
+ this.table.update(destination);
+ destinationFound = true;
+ }
+ else {
+ handleTask(task);
+ }
+ }
+ else {
+ handleTask(task);
+ }
+ waitFor(1);
+ }
+ catch (Exception ex) {
+ }
+ } while (Msg.getClock() < timeout && !destinationFound);
+ }
+ /**
+ * Sends a "FIND_NODE" request (task) to the node we know.
+ * @brief id Id of the node we are querying
+ * @brief destination id of the node we are trying to find.
+ */
+ public void sendFindNode(int id, int destination) {
+ Msg.debug("Sending a FIND_NODE to " + Integer.toString(id) + " to find " + destination );
+ FindNodeTask task = new FindNodeTask(this.id,destination);
+ task.dsend(Integer.toString(id));
+ }
+ /**
+ * Sends a "FIND_NODE" request to the best "alpha" nodes in a node
+ * list
+ */
+ public int sendFindNodeToBest(Answer nodeList) {
+ int destination = nodeList.getDestinationId();
+ int i;
+ for (i = 0; i < Common.alpha && i < nodeList.size(); i++) {
+ Contact node = nodeList.getNodes().get(i);
+ if (node.getId() != this.id) {
+ this.sendFindNode(node.getId(),destination);
+ }
+ }
+ return i;
+ }
+ /**
+ * Does a random lookup
+ */
+ public void randomLookup() {
+ findNode(0,true);
+ }
+ /**
+ * Handles an incomming task
+ * @param task The task we need to handle
+ */
+ public void handleTask(Task task) {
+ if (task instanceof KademliaTask) {
+ table.update(((KademliaTask) task).getSenderId());
+ if (task instanceof FindNodeTask) {
+ handleFindNode((FindNodeTask)task);
+ }
+ else if (task instanceof PingTask) {
+ handlePing((PingTask)task);
+ }
+ }
+ }
+ public void handleFindNode(FindNodeTask task) {
+ Msg.debug("Received a FIND_NODE from " + task.getSenderId());
+ Answer answer = table.findClosest(task.getDestination());
+ FindNodeAnswerTask taskToSend = new FindNodeAnswerTask(this.id,task.getDestination(),answer);
+ taskToSend.dsend(Integer.toString(task.getSenderId()));
+ }
+ public void handlePing(PingTask task) {
+ Msg.debug("Received a PING from " + task.getSenderId());
+ PingAnswerTask taskToSend = new PingAnswerTask(this.id);
+ taskToSend.dsend(Integer.toString(task.getSenderId()));
+ }
+
+
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+public class PingAnswerTask extends KademliaTask {
+ /**
+ * Constructor
+ */
+ public PingAnswerTask(int senderId) {
+ super(senderId);
+ }
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+package kademlia;
+
+/**
+ * @brief "PING" task sent by a node to another to see if it is still alive
+ */
+public class PingTask extends KademliaTask {
+ /**
+ * Constructor
+ */
+ public PingTask(int senderId) {
+ super(senderId);
+ }
+}
--- /dev/null
+/* Copyright (c) 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+package kademlia;
+import java.util.Collections;
+import java.util.Vector;
+
+import org.simgrid.msg.Msg;
+/**
+ * @brief Contains the various data of a routing table.
+ */
+public class RoutingTable {
+ /**
+ * Bucket list
+ */
+ private Vector<Bucket> buckets;
+ /**
+ * Id of the routing table owner
+ */
+ private int id;
+ /**
+ * Constructor
+ */
+ public RoutingTable(int id) {
+ this.id = id;
+ buckets = new Vector<Bucket>();
+ for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) {
+ buckets.add(new Bucket(i));
+ }
+ }
+ /**
+ * Returns an identifier which is in a specific bucket of a routing table
+ * @brief id id of the routing table owner
+ * @brief prefix id of the bucket where we want that identifier to be
+ */
+ public int getIdInPrefix(int id, int prefix) {
+ if (prefix == 0) {
+ return 0;
+ }
+ int identifier = 1;
+ identifier = identifier << (prefix - 1);
+ identifier = identifier ^ id;
+ return identifier;
+ }
+ /**
+ * Returns the corresponding node prefix for a given id
+ */
+ public int getNodePrefix(int id) {
+ for (int j = 0; j < 32; j++) {
+ if ((id >> (32 - 1 - j) & 0x1) != 0) {
+ return 32 - j;
+ }
+ }
+ return 0;
+ }
+ /**
+ * Fins the corresponding bucket in a routing table for a given identifier
+ */
+ public Bucket findBucket(int id) {
+ int xorNumber = id ^ this.id;
+// Msg.info("Number:" + xorNumber.toString(16));
+ int prefix = this.getNodePrefix(xorNumber);
+
+ return buckets.get(prefix);
+ }
+ /**
+ * Updates the routing table with a new value.
+ */
+ public void update(int id) {
+
+ Bucket bucket = this.findBucket(id);
+ if (bucket.contains(id)) {
+ Msg.debug("Updating " + Integer.toString(id) + " in my routing table");
+ //If the element is already in the bucket, we update it.
+ bucket.pushToFront(id);
+ }
+ else {
+ Msg.debug("Adding " + id + " to my routing table");
+ bucket.add(id);
+ if (bucket.size() > Common.BUCKET_SIZE) {
+ //TODO: Ping the least seen guy and remove him if he is offline.
+ }
+ }
+ }
+ /**
+ * Returns the closest notes we know to a given id
+ */
+ public Answer findClosest(int destinationId) {
+ Answer answer = new Answer(destinationId);
+
+
+ Bucket bucket = this.findBucket(destinationId);
+ bucket.addToAnswer(answer,destinationId);
+
+ for (int i = 1; answer.size() < Common.BUCKET_SIZE &&
+ (bucket.getId() - i) >= 0 &&
+ (bucket.getId() + i) <= Common.IDENTIFIER_SIZE; i++) {
+ //Check the previous buckets
+ if (bucket.getId() - i >= 0) {
+ Bucket bucketP = this.buckets.get(bucket.getId() - i);
+ bucketP.addToAnswer(answer,destinationId);
+ }
+ //Check the next buckets
+ if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) {
+ Bucket bucketN = this.buckets.get(bucket.getId() + i);
+ bucketN.addToAnswer(answer, destinationId);
+ }
+ }
+ //We sort the list
+ Collections.sort(answer.getNodes());
+ //We trim the list
+ while (answer.size() > Common.BUCKET_SIZE) {
+ answer.remove(answer.size() - 1); //TODO: Not the best thing.
+ }
+
+ return answer;
+ }
+
+ @Override
+ public String toString() {
+ String string = "RoutingTable [ id=" + id + " " ;
+ for (int i = 0; i < buckets.size(); i++) {
+ if (buckets.get(i).size() > 0) {
+ string += buckets.get(i) + " ";
+ }
+ }
+ return string;
+ }
+
+}
--- /dev/null
+#! ./tesh
+
+! output sort
+
+$ java -cp .:${srcdir:=.}/examples:${srcdir:=.}/simgrid.jar kademlia/Kademlia ${srcdir:=.}/examples/platform.xml ${srcdir:=.}/examples/kademlia/kademlia.xml
+> [0.000000] [jmsg/INFO] Ready to run MSG_MAIN
+> [900.956202] [jmsg/INFO] Done running MSG_MAIN
+> [900.956202] [jmsg/INFO] MSG_main finished
+> [900.956202] [jmsg/INFO] Clean java world
+> [900.956202] [jmsg/INFO] Clean native world
+> [Boivin:kademlia.Node:(2) 0.000000] [jmsg/INFO] Hi, I'm going to join the network with the id 1!
+> [Boivin:kademlia.Node:(2) 900.956202] [jmsg/INFO] 8/8 FIND_NODE have succedded.
+> [Jacquelin:kademlia.Node:(1) 0.000000] [jmsg/INFO] Hi, I'm going to create the network with the id 0!
+> [Jacquelin:kademlia.Node:(1) 900.000000] [jmsg/INFO] 8/8 FIND_NODE have succedded.
+> [Jean_Yves:kademlia.Node:(3) 0.000000] [jmsg/INFO] Hi, I'm going to join the network with the id 2!
+> [Jean_Yves:kademlia.Node:(3) 900.956202] [jmsg/INFO] 8/8 FIND_NODE have succedded.
+> [TeX:kademlia.Node:(4) 0.000000] [jmsg/INFO] Hi, I'm going to join the network with the id 4!
+> [TeX:kademlia.Node:(4) 900.570419] [jmsg/INFO] 8/8 FIND_NODE have succedded.
+
--- /dev/null
+<?xml version='1.0'?>
+<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd">
+<platform version="3">
+
+ <process host="Jacquelin" function="kademlia.Node">
+ <argument value="0"/> <!-- my id -->
+ <argument value ="900"/> <!-- deadline -->
+ </process>
+
+ <process host="Boivin" function="kademlia.Node">
+ <argument value="1"/> <!-- my id -->
+ <argument value="0"/> <!-- known id -->
+ <argument value ="900"/> <!-- deadline -->
+ </process>
+
+ <process host="Jean_Yves" function="kademlia.Node">
+ <argument value="2"/> <!-- my id -->
+ <argument value="0"/> <!-- known id -->
+ <argument value ="900"/> <!-- deadline -->
+ </process>
+
+ <process host="TeX" function="kademlia.Node">
+ <argument value="4"/> <!-- my id -->
+ <argument value="0"/> <!-- known id -->
+ <argument value ="900"/> <!-- deadline -->
+ </process>
+
+</platform>
