From: Samuel Lepetit Date: Mon, 25 Jun 2012 14:51:57 +0000 (+0200) Subject: Add kademlia example X-Git-Tag: v3_9_90~569^2~19^2~33 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/0feff83cd4e93e9202cab54ec970cc7e4d6931c7?ds=sidebyside Add kademlia example --- diff --git a/CMakeLists.txt b/CMakeLists.txt index bf8b5b362a..34b5cee374 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -165,6 +165,18 @@ set(JAVA_EXAMPLES ${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 @@ -239,7 +251,7 @@ set(XML_FILES ${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 @@ -249,6 +261,7 @@ set(XML_FILES ${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 ) @@ -398,6 +411,7 @@ add_custom_command( 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 @@ -447,6 +461,7 @@ ADD_TEST(bypass ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE 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) @@ -456,7 +471,7 @@ ADD_TEST(priority ${TESH_BIN_PATH} ${TESH_OPTION} --setenv srcdir=${CMAKE 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) diff --git a/examples/kademlia/Answer.java b/examples/kademlia/Answer.java new file mode 100644 index 0000000000..ac142b7993 --- /dev/null +++ b/examples/kademlia/Answer.java @@ -0,0 +1,98 @@ +/* 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 nodes; + + /** + * Constructor + */ + public Answer(int destinationId) { + this.destinationId = destinationId; + nodes = new ArrayList(); + } + /** + * Returns the destination id + */ + int getDestinationId() { + return destinationId; + } + /** + * Returns the list of the nodes in the answer + */ + ArrayList 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 + + "]"; + } + +} diff --git a/examples/kademlia/Bucket.java b/examples/kademlia/Bucket.java new file mode 100644 index 0000000000..032799b751 --- /dev/null +++ b/examples/kademlia/Bucket.java @@ -0,0 +1,76 @@ +/* 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 nodes; + private int id; + + /** + * Constructor + */ + public Bucket(int id) { + this.nodes = new ArrayList(); + 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 + "]"; + } + +} diff --git a/examples/kademlia/Common.java b/examples/kademlia/Common.java new file mode 100644 index 0000000000..a8ea1a04af --- /dev/null +++ b/examples/kademlia/Common.java @@ -0,0 +1,45 @@ +/* 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; +} diff --git a/examples/kademlia/Contact.java b/examples/kademlia/Contact.java new file mode 100644 index 0000000000..61215e76ed --- /dev/null +++ b/examples/kademlia/Contact.java @@ -0,0 +1,46 @@ +package kademlia; + +/** + * Contains the information about a foreign node according to + * a node we are trying to find. + */ +public class Contact implements Comparable { + 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 diff --git a/examples/kademlia/FindNodeAnswerTask.java b/examples/kademlia/FindNodeAnswerTask.java new file mode 100644 index 0000000000..05d0217cf0 --- /dev/null +++ b/examples/kademlia/FindNodeAnswerTask.java @@ -0,0 +1,35 @@ +/* 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; + } + +} diff --git a/examples/kademlia/FindNodeTask.java b/examples/kademlia/FindNodeTask.java new file mode 100644 index 0000000000..9ad0582771 --- /dev/null +++ b/examples/kademlia/FindNodeTask.java @@ -0,0 +1,33 @@ +/* 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; + } + +} diff --git a/examples/kademlia/Kademlia.java b/examples/kademlia/Kademlia.java new file mode 100644 index 0000000000..70d0524ff8 --- /dev/null +++ b/examples/kademlia/Kademlia.java @@ -0,0 +1,29 @@ +/* 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(); + } +} diff --git a/examples/kademlia/KademliaTask.java b/examples/kademlia/KademliaTask.java new file mode 100644 index 0000000000..5566a3cf7c --- /dev/null +++ b/examples/kademlia/KademliaTask.java @@ -0,0 +1,32 @@ +/* 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; + } +} diff --git a/examples/kademlia/Node.java b/examples/kademlia/Node.java new file mode 100644 index 0000000000..7312d26951 --- /dev/null +++ b/examples/kademlia/Node.java @@ -0,0 +1,350 @@ +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())); + } + + +} diff --git a/examples/kademlia/PingAnswerTask.java b/examples/kademlia/PingAnswerTask.java new file mode 100644 index 0000000000..4c76dffb3a --- /dev/null +++ b/examples/kademlia/PingAnswerTask.java @@ -0,0 +1,16 @@ +/* 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); + } +} diff --git a/examples/kademlia/PingTask.java b/examples/kademlia/PingTask.java new file mode 100644 index 0000000000..24b2ac5136 --- /dev/null +++ b/examples/kademlia/PingTask.java @@ -0,0 +1,19 @@ +/* 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); + } +} diff --git a/examples/kademlia/RoutingTable.java b/examples/kademlia/RoutingTable.java new file mode 100644 index 0000000000..a25acdfa38 --- /dev/null +++ b/examples/kademlia/RoutingTable.java @@ -0,0 +1,132 @@ +/* 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 buckets; + /** + * Id of the routing table owner + */ + private int id; + /** + * Constructor + */ + public RoutingTable(int id) { + this.id = id; + buckets = new Vector(); + 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; + } + +} diff --git a/examples/kademlia/kademlia.tesh b/examples/kademlia/kademlia.tesh new file mode 100644 index 0000000000..a51ddf045e --- /dev/null +++ b/examples/kademlia/kademlia.tesh @@ -0,0 +1,19 @@ +#! ./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. + diff --git a/examples/kademlia/kademlia.xml b/examples/kademlia/kademlia.xml new file mode 100644 index 0000000000..a6eeaaa04f --- /dev/null +++ b/examples/kademlia/kademlia.xml @@ -0,0 +1,28 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + +