endforeach()
set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-chord/s4u-dht-chord.hpp)
+# KADEMLIA EXAMPLE
+add_executable (s4u-dht-kademlia dht-kademlia/s4u-dht-kademlia.cpp dht-kademlia/node.cpp
+ dht-kademlia/routing_table.cpp dht-kademlia/answer.cpp)
+target_link_libraries(s4u-dht-kademlia simgrid)
+set_target_properties(s4u-dht-kademlia PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/dht-kademlia)
+foreach (file answer routing_table node s4u-dht-kademlia)
+ set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.cpp
+ ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.hpp)
+endforeach()
+set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/message.hpp)
+
+# BITTORRENT EXAMPLE
add_executable (s4u-bittorrent app-bittorrent/s4u-bittorrent.cpp app-bittorrent/s4u-peer.cpp
app-bittorrent/s4u-tracker.cpp)
target_link_libraries(s4u-bittorrent simgrid)
set(examples_src ${examples_src} PARENT_SCOPE)
set(tesh_files ${tesh_files} ${CMAKE_CURRENT_SOURCE_DIR}/app-bittorrent/s4u-app-bittorrent.tesh
${CMAKE_CURRENT_SOURCE_DIR}/dht-chord/s4u-dht-chord.tesh
+ ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/s4u-dht-kademlia.tesh
${CMAKE_CURRENT_SOURCE_DIR}/actor-lifetime/s4u-actor-lifetime.tesh
${CMAKE_CURRENT_SOURCE_DIR}/actor-yield/s4u-actor-yield.tesh
${CMAKE_CURRENT_SOURCE_DIR}/async-wait/s4u-async-wait.tesh
${CMAKE_CURRENT_SOURCE_DIR}/async-waitall/s4u-async-waitall_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/async-wait/s4u-async-wait_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/dht-chord/s4u-dht-chord_d.xml
+ ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/s4u-dht-kademlia_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/energy-boot/platform_boot.xml
${CMAKE_CURRENT_SOURCE_DIR}/io-file-remote/s4u-io-file-remote_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/platform-properties/s4u-platform-properties_d.xml
- ${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm-split_d.xml
+ ${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm-split_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm_d.xml
${CMAKE_CURRENT_SOURCE_DIR}/replay-storage/s4u-replay-storage_d.xml
- PARENT_SCOPE)
+ PARENT_SCOPE)
+set(bin_files ${bin_files} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/generate.py PARENT_SCOPE)
set(txt_files ${txt_files} ${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm-split-p0.txt
${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm-split-p1.txt
${CMAKE_CURRENT_SOURCE_DIR}/replay-comm/s4u-replay-comm.txt
app-bittorrent app-chainsend app-masterworker app-pingpong app-token-ring
async-wait async-waitall async-waitany
cloud-capping cloud-simple
- dht-chord
+ dht-chord dht-kademlia
energy-exec energy-boot energy-link energy-vm
exec-async exec-basic exec-dvfs exec-monitor exec-ptask exec-remote
platform-properties plugin-hostload mutex
--- /dev/null
+/* Copyright (c) 2012-2014, 2016-2017. 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. */
+
+#include "answer.hpp"
+
+XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(kademlia_node);
+
+namespace kademlia {
+
+bool sortbydistance(const std::pair<unsigned int, unsigned int>& a, const std::pair<unsigned int, unsigned int>& b)
+{
+ return (a.second < b.second);
+}
+
+/** @brief Prints a answer_t, for debugging purposes */
+void Answer::print()
+{
+ XBT_INFO("Searching %08x, size %u", destination_id_, size_);
+ unsigned int i = 0;
+ for (auto contact : nodes)
+ XBT_INFO("Node %08x: %08x is at distance %u", i++, contact.first, contact.second);
+}
+
+/** @brief Merge two answers together, only keeping the best nodes
+ * @param source the source of the nodes to add
+ */
+unsigned int Answer::merge(Answer* source)
+{
+ if (this == source)
+ return 0;
+
+ unsigned int nb_added = 0;
+ for (auto contact : source->nodes) {
+ if (std::find(nodes.begin(), nodes.end(), contact) == nodes.end()) {
+ nodes.push_back(contact);
+ size_++;
+ nb_added++;
+ }
+ }
+ std::sort(nodes.begin(), nodes.end(), sortbydistance);
+ trim();
+ return nb_added;
+}
+
+/** @brief Trims an Answer, in order for it to have a size of less or equal to "bucket_size" */
+void Answer::trim()
+{
+ while (size_ > BUCKET_SIZE) {
+ nodes.pop_back();
+ size_--;
+ }
+ xbt_assert(nodes.size() == size_, "Wrong size for the answer");
+}
+
+/** @brief Returns if the destination we are trying to find is found
+ * @return if the destination is found.
+ */
+bool Answer::destinationFound()
+{
+ if (nodes.empty())
+ return 0;
+
+ return (*nodes.begin()).second == 0;
+}
+
+/** @brief Adds the content of a bucket unsigned into a answer object.
+ * @param bucket the bucket we have to had unsigned into
+ */
+void Answer::addBucket(Bucket* bucket)
+{
+ xbt_assert((bucket != nullptr), "Provided a NULL bucket");
+
+ for (auto id : bucket->nodes) {
+ unsigned int distance = id ^ destination_id_;
+ nodes.push_back(std::pair<unsigned int, unsigned int>(id, distance));
+ size_++;
+ }
+}
+}
--- /dev/null
+/* Copyright (c) 2012, 2014, 2016, 2017. 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. */
+
+#ifndef _KADEMLIA_ANSWER_HPP_
+#define _KADEMLIA_ANSWER_HPP_
+
+#include "node.hpp"
+#include "routing_table.hpp"
+#include <set>
+
+namespace kademlia {
+bool sortbydistance(const std::pair<unsigned int, unsigned int>& a, const std::pair<unsigned int, unsigned int>& b);
+
+/* Node query answer. contains the elements closest to the id given. */
+class Answer {
+ unsigned int destination_id_;
+ unsigned int size_ = 0;
+
+public:
+ std::vector<std::pair<unsigned int, unsigned int>> nodes;
+ explicit Answer(unsigned int destination_id) : destination_id_(destination_id) {}
+ virtual ~Answer() = default;
+ unsigned int getDestinationId() { return destination_id_; }
+ unsigned int getSize() { return size_; }
+ void print();
+ unsigned int merge(Answer* a);
+ void trim();
+ bool destinationFound();
+ void addBucket(kademlia::Bucket* bucket);
+};
+}
+
+#endif
--- /dev/null
+#!/usr/bin/env python
+
+# Copyright (c) 2012, 2014. 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 sys
+import random
+
+if len(sys.argv) != 4:
+ print(
+ "Usage: python generate.py nb_nodes nb_bits end_date > deployment_file.xml")
+ sys.exit(1)
+
+nb_nodes = int(sys.argv[1])
+nb_bits = int(sys.argv[2])
+end_date = int(sys.argv[3])
+
+max_id = 2 ** nb_bits - 1
+all_ids = [0]
+
+sys.stdout.write("<?xml version='1.0'?>\n"
+ "<!DOCTYPE platform SYSTEM \"http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd\">\n"
+ "<platform version=\"4\">\n <process host=\"node-0.acme.org\" function=\"node\">\n"
+ " <argument value=\"0\"/>\n <argument value=\"%d\"/>\n </process>\n" % end_date)
+
+for i in range(1, nb_nodes):
+ ok = False
+ while not ok:
+ my_id = random.randint(0, max_id)
+ ok = not my_id in all_ids
+ known_id = all_ids[random.randint(0, len(all_ids) - 1)]
+ start_date = i * 10
+ line = " <process host=\"node-%d.acme.org\" function=\"node\">\n <argument value=\"%s\"/>"\
+ "\n <argument value=\"%s\"/>\n <argument value=\"%d\"/>\n </process>\n" % (
+ i, my_id, known_id, end_date)
+ sys.stdout.write(line)
+ all_ids.append(my_id)
+
+sys.stdout.write("</platform>")
--- /dev/null
+/* Copyright (c) 2012, 2014-2016. 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. */
+
+#ifndef _KADEMLIA_TASK_HPP_
+#define _KADEMLIA_TASK_HPP_
+#include "answer.hpp"
+#include "simgrid/s4u.hpp"
+
+namespace kademlia {
+class Answer;
+
+class Message {
+public:
+ unsigned int sender_id_ = 0; // Id of the guy who sent the task
+ unsigned int destination_id_ = 0; // Id we are trying to find, if needed.
+ Answer* answer_ = nullptr; // Answer to the request made, if needed.
+ simgrid::s4u::MailboxPtr answer_to_ = nullptr; // mailbox to send the answer to (if not an answer).
+ char* issuer_host_name_ = nullptr; // used for logging
+
+ explicit Message(unsigned int sender_id, unsigned int destination_id, Answer* answer,
+ simgrid::s4u::MailboxPtr mailbox, const char* hostname)
+ : sender_id_(sender_id)
+ , destination_id_(destination_id)
+ , answer_(answer)
+ , answer_to_(mailbox)
+ , issuer_host_name_(xbt_strdup(hostname))
+ {
+ }
+ explicit Message(unsigned int sender_id, unsigned int destination_id, simgrid::s4u::MailboxPtr mailbox,
+ const char* hostname)
+ : Message(sender_id, destination_id, nullptr, mailbox, hostname)
+ {
+ }
+ ~Message()
+ {
+ if (issuer_host_name_)
+ xbt_free(issuer_host_name_);
+ }
+};
+}
+#endif
--- /dev/null
+/* Copyright (c) 2010, 2012-2017. 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. */
+
+#include "node.hpp"
+#include "routing_table.hpp"
+
+XBT_LOG_NEW_DEFAULT_CATEGORY(kademlia_node, "Messages specific for this example");
+
+namespace kademlia {
+static void destroy(void* message)
+{
+ Message* msg = static_cast<Message*>(message);
+ delete msg->answer_;
+ delete msg;
+}
+
+/**
+ * @brief Tries to join the network
+ * @param known_id id of the node I know in the network.
+ */
+bool Node::join(unsigned int known_id)
+{
+ Answer* node_list;
+ unsigned int i;
+ bool got_answer = false;
+
+ /* Add the guy we know to our routing table and ourselves. */
+ routingTableUpdate(id_);
+ routingTableUpdate(known_id);
+
+ /* First step: Send a "FIND_NODE" request to the node we know */
+ sendFindNode(known_id, id_);
+
+ simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id_));
+ do {
+ if (receive_comm == nullptr)
+ receive_comm = mailbox->get_async(&received_msg);
+ if (receive_comm->test()) {
+ XBT_DEBUG("Received an answer from the node I know.");
+ got_answer = true;
+ // retrieve the node list and ping them.
+ Message* msg = static_cast<Message*>(received_msg);
+ node_list = msg->answer_;
+ if (node_list) {
+ for (auto contact : node_list->nodes)
+ routingTableUpdate(contact.first);
+ } else {
+ handleFindNode(msg);
+ }
+ delete msg->answer_;
+ delete msg;
+ receive_comm = nullptr;
+ } else
+ simgrid::s4u::this_actor::sleep_for(1);
+ } while (not got_answer);
+
+ /* Second step: Send a FIND_NODE to a a random node in buckets */
+ unsigned int bucket_id = table->findBucket(known_id)->getId();
+ for (i = 0; ((bucket_id > i) || (bucket_id + i) <= identifier_size) && i < JOIN_BUCKETS_QUERIES; i++) {
+ if (bucket_id > i) {
+ unsigned int id_in_bucket = get_id_in_prefix(id_, bucket_id - i);
+ findNode(id_in_bucket, false);
+ }
+ if (bucket_id + i <= identifier_size) {
+ unsigned int id_in_bucket = get_id_in_prefix(id_, bucket_id + i);
+ findNode(id_in_bucket, false);
+ }
+ }
+ return got_answer;
+}
+
+/** @brief Send a "FIND_NODE" to a node
+ * @param id node we are querying
+ * @param destination node we are trying to find.
+ */
+void Node::sendFindNode(unsigned int id, unsigned int destination)
+{
+ /* Gets the mailbox to send to */
+ simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id));
+ /* Build the task */
+ Message* msg = new Message(id_, destination, simgrid::s4u::Mailbox::byName(std::to_string(id_)),
+ simgrid::s4u::Host::current()->getCname());
+
+ /* Send the task */
+ mailbox->put_init(msg, 1)->detach(kademlia::destroy);
+ XBT_VERB("Asking %u for its closest nodes", id);
+}
+
+/**
+ * Sends to the best "kademlia_alpha" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best
+ * nodes
+ */
+unsigned int Node::sendFindNodeToBest(Answer* node_list)
+{
+ unsigned int i = 0;
+ unsigned int j = 0;
+ unsigned int destination = node_list->getDestinationId();
+ for (auto node_to_query : node_list->nodes) {
+ /* We need to have at most "kademlia_alpha" requests each time, according to the protocol */
+ /* Gets the node we want to send the query to */
+ if (node_to_query.first != id_) { /* No need to query ourselves */
+ sendFindNode(node_to_query.first, destination);
+ j++;
+ }
+ i++;
+ if (j == kademlia_alpha)
+ break;
+ }
+ return i;
+}
+
+/** @brief Updates/Puts the node id unsigned into our routing table
+ * @param id The id of the node we need to add unsigned into our routing table
+ */
+void Node::routingTableUpdate(unsigned int id)
+{
+ // retrieval of the bucket in which the should be
+ Bucket* bucket = table->findBucket(id);
+
+ // check if the id is already in the bucket.
+ auto id_pos = std::find(bucket->nodes.begin(), bucket->nodes.end(), id);
+
+ if (id_pos == bucket->nodes.end()) {
+ /* We check if the bucket is full or not. If it is, we evict an old element */
+ if (bucket->nodes.size() >= BUCKET_SIZE) {
+ bucket->nodes.pop_back();
+ }
+ bucket->nodes.push_front(id);
+ XBT_VERB("I'm adding to my routing table %08x", id);
+ } else {
+ // We push the element to the front
+ bucket->nodes.erase(id_pos);
+ bucket->nodes.push_front(id);
+ XBT_VERB("I'm updating %08x", id);
+ }
+}
+
+/** @brief Finds the closest nodes to the node given.
+ * @param node : our node
+ * @param destination_id : the id of the guy we are trying to find
+ */
+Answer* Node::findClosest(unsigned int destination_id)
+{
+ Answer* answer = new Answer(destination_id);
+ /* We find the corresponding bucket for the id */
+ Bucket* bucket = table->findBucket(destination_id);
+ int bucket_id = bucket->getId();
+ xbt_assert((bucket_id <= identifier_size), "Bucket found has a wrong identifier");
+ /* So, we copy the contents of the bucket unsigned into our answer */
+ answer->addBucket(bucket);
+
+ /* However, if we don't have enough elements in our bucket, we NEED to include at least "bucket_size" elements
+ * (if, of course, we know at least "bucket_size" elements. So we're going to look unsigned into the other buckets.
+ */
+ for (int i = 1; answer->getSize() < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < identifier_size)); i++) {
+ /* We check the previous buckets */
+ if (bucket_id - i >= 0) {
+ Bucket* bucket_p = table->buckets[bucket_id - i];
+ answer->addBucket(bucket_p);
+ }
+ /* We check the next buckets */
+ if (bucket_id + i <= identifier_size) {
+ Bucket* bucket_n = table->buckets[bucket_id + i];
+ answer->addBucket(bucket_n);
+ }
+ }
+ /* We trim the array to have only bucket_size or less elements */
+ std::sort(answer->nodes.begin(), answer->nodes.end(), sortbydistance);
+ answer->trim();
+
+ return answer;
+}
+
+/** @brief Send a request to find a node in the node routing table.
+ * @param id_to_find the id of the node we are trying to find
+ */
+bool Node::findNode(unsigned int id_to_find, bool count_in_stats)
+{
+ unsigned int queries;
+ unsigned int answers;
+ bool destination_found = false;
+ unsigned int nodes_added = 0;
+ double global_timeout = simgrid::s4u::Engine::getClock() + find_node_global_timeout;
+ unsigned int steps = 0;
+
+ /* First we build a list of who we already know */
+ Answer* node_list = findClosest(id_to_find);
+ xbt_assert((node_list != nullptr), "node_list incorrect");
+ XBT_DEBUG("Doing a FIND_NODE on %08x", id_to_find);
+
+ /* Ask the nodes on our list if they have information about the node we are trying to find */
+ do {
+ answers = 0;
+ queries = sendFindNodeToBest(node_list);
+ nodes_added = 0;
+ double timeout = simgrid::s4u::Engine::getClock() + find_node_timeout;
+ steps++;
+ double time_beginreceive = simgrid::s4u::Engine::getClock();
+
+ simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(id_));
+ do {
+ if (receive_comm == nullptr)
+ receive_comm = mailbox->get_async(&received_msg);
+
+ if (receive_comm->test()) {
+ Message* msg = static_cast<Message*>(received_msg);
+ // Check if what we have received is what we are looking for.
+ if (msg->answer_ && msg->answer_->getDestinationId() == id_to_find) {
+ routingTableUpdate(msg->sender_id_);
+ // Handle the answer
+ for (auto contact : node_list->nodes)
+ routingTableUpdate(contact.first);
+ answers++;
+
+ nodes_added = node_list->merge(msg->answer_);
+ XBT_DEBUG("Received an answer from %s (%s) with %lu nodes on it", msg->answer_to_->getCname(),
+ msg->issuer_host_name_, msg->answer_->nodes.size());
+ } else {
+ if (msg->answer_) {
+ routingTableUpdate(msg->sender_id_);
+ XBT_DEBUG("Received a wrong answer for a FIND_NODE");
+ } else {
+ handleFindNode(msg);
+ }
+ // Update the timeout if we didn't have our answer
+ timeout += simgrid::s4u::Engine::getClock() - time_beginreceive;
+ time_beginreceive = simgrid::s4u::Engine::getClock();
+ }
+ delete msg->answer_;
+ delete msg;
+ receive_comm = nullptr;
+ } else {
+ simgrid::s4u::this_actor::sleep_for(1);
+ }
+ } while (simgrid::s4u::Engine::getClock() < timeout && answers < queries);
+ destination_found = node_list->destinationFound();
+ } while (not destination_found && (nodes_added > 0 || answers == 0) &&
+ simgrid::s4u::Engine::getClock() < global_timeout && steps < MAX_STEPS);
+
+ if (destination_found) {
+ if (count_in_stats)
+ find_node_success++;
+ if (queries > 4)
+ XBT_VERB("FIND_NODE on %08x success in %u steps", id_to_find, steps);
+ routingTableUpdate(id_to_find);
+ } else {
+ if (count_in_stats) {
+ find_node_failed++;
+ XBT_VERB("%08x not found in %u steps", id_to_find, steps);
+ }
+ }
+ delete node_list;
+ return destination_found;
+}
+
+/** @brief Does a pseudo-random lookup for someone in the system
+ * @param node caller node data
+ */
+void Node::randomLookup()
+{
+ unsigned int id_to_look = RANDOM_LOOKUP_NODE; // Totally random.
+ /* TODO: Use some pseudo-random generator like RngStream. */
+ XBT_DEBUG("I'm doing a random lookup");
+ findNode(id_to_look, true);
+}
+
+/** @brief Handles the answer to an incoming "find_node" task */
+void Node::handleFindNode(Message* msg)
+{
+ routingTableUpdate(msg->sender_id_);
+ XBT_VERB("Received a FIND_NODE from %s (%s), he's trying to find %08x", msg->answer_to_->getCname(),
+ msg->issuer_host_name_, msg->destination_id_);
+ // Building the answer to the request
+ Message* answer =
+ new Message(id_, msg->destination_id_, findClosest(msg->destination_id_),
+ simgrid::s4u::Mailbox::byName(std::to_string(id_)), simgrid::s4u::Host::current()->getCname());
+ // Sending the answer
+ msg->answer_to_->put_init(answer, 1)->detach(kademlia::destroy);
+}
+}
+/**@brief Returns an identifier which is in a specific bucket of a routing table
+ * @param id id of the routing table owner
+ * @param prefix id of the bucket where we want that identifier to be
+ */
+unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix)
+{
+ if (prefix == 0) {
+ return 0;
+ } else {
+ return (1U << ((unsigned int)(prefix - 1))) ^ id;
+ }
+}
+
+/** @brief Returns the prefix of an identifier.
+ * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored.
+ * @param id : big unsigned int id to test
+ * @param nb_bits : key size
+ */
+unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits)
+{
+ unsigned int size = sizeof(unsigned int) * 8;
+ for (unsigned int j = 0; j < size; j++) {
+ if (((id >> (size - 1 - j)) & 0x1) != 0) {
+ return nb_bits - (j);
+ }
+ }
+ return 0;
+}
--- /dev/null
+/* Copyright (c) 2012, 2014-2017. 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. */
+
+#ifndef _KADEMLIA_NODE_HPP
+#define _KADEMLIA_NODE_HPP
+#include "answer.hpp"
+#include "message.hpp"
+#include "routing_table.hpp"
+#include "s4u-dht-kademlia.hpp"
+
+namespace kademlia {
+
+class Node {
+ unsigned int id_; // node id - 160 bits
+ RoutingTable* table = nullptr; // node routing table
+public:
+ simgrid::s4u::CommPtr receive_comm;
+ void* received_msg = nullptr;
+ unsigned int find_node_success = 0; // Number of find_node which have succeeded.
+ unsigned int find_node_failed = 0; // Number of find_node which have failed.
+ explicit Node(unsigned int node_id) : id_(node_id), table(new RoutingTable(node_id)), receive_comm(nullptr) {}
+ ~Node() { delete table; }
+ unsigned int getId() { return id_; }
+
+ bool join(unsigned int known_id);
+ void sendFindNode(unsigned int id, unsigned int destination);
+ unsigned int sendFindNodeToBest(Answer* node_list);
+ void routingTableUpdate(unsigned int id);
+ Answer* findClosest(unsigned int destination_id);
+ bool findNode(unsigned int id_to_find, bool count_in_stats);
+ void randomLookup();
+ void handleFindNode(Message* msg);
+};
+}
+// identifier functions
+unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix);
+unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits);
+
+#endif /* _MSG_EXAMPLES_ROUTING_H */
--- /dev/null
+/* Copyright (c) 2012-2017. 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. */
+
+#include "routing_table.hpp"
+#include "node.hpp"
+
+XBT_LOG_NEW_DEFAULT_CATEGORY(kademlia_routing_table, "Messages specific for this example");
+
+namespace kademlia {
+
+/** @brief Initialization of a node routing table. */
+RoutingTable::RoutingTable(unsigned int node_id) : id_(node_id)
+{
+ buckets = new Bucket*[identifier_size + 1];
+ for (unsigned int i = 0; i < identifier_size + 1; i++)
+ buckets[i] = new Bucket(i);
+}
+
+RoutingTable::~RoutingTable()
+{
+ // Free the buckets.
+ for (unsigned int i = 0; i <= identifier_size; i++) {
+ delete buckets[i];
+ }
+ delete[] buckets;
+}
+
+void RoutingTable::print()
+{
+ XBT_INFO("Routing table of %08x:", id_);
+
+ for (unsigned int i = 0; i <= identifier_size; i++) {
+ if (not buckets[i]->nodes.empty()) {
+ XBT_INFO("Bucket number %u: ", i);
+ int j = 0;
+ for (auto value : buckets[i]->nodes) {
+ XBT_INFO("Element %d: %08x", j, value);
+ j++;
+ }
+ }
+ }
+}
+
+/** @brief Finds the corresponding bucket in a routing table for a given identifier
+ * @param id the identifier
+ * @return the bucket in which the the identifier would be.
+ */
+Bucket* RoutingTable::findBucket(unsigned int id)
+{
+ unsigned int xor_number = id_ ^ id;
+ unsigned int prefix = get_node_prefix(xor_number, identifier_size);
+ xbt_assert(prefix <= identifier_size, "Tried to return a bucket that doesn't exist.");
+ return buckets[prefix];
+}
+
+/** Returns if the routing table contains the id. */
+bool RoutingTable::contains(unsigned int node_id)
+{
+ Bucket* bucket = findBucket(node_id);
+ return std::find(bucket->nodes.begin(), bucket->nodes.end(), node_id) != bucket->nodes.end();
+}
+}
--- /dev/null
+/* Copyright (c) 2012, 2014, 2017. 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. */
+
+#ifndef _KADEMLIA_ROUTING_TABLE_HPP
+#define _KADEMLIA_ROUTING_TABLE_HPP
+#include "s4u-dht-kademlia.hpp"
+#include <deque>
+
+namespace kademlia {
+
+/* Routing table bucket */
+class Bucket {
+ unsigned int id_; // bucket id
+public:
+ std::deque<unsigned int> nodes; // Nodes in the bucket.
+ unsigned int getId() { return id_; }
+ explicit Bucket(unsigned int id) : id_(id) {}
+ ~Bucket() = default;
+};
+
+/* Node routing table */
+class RoutingTable {
+ unsigned int id_; // node id of the client's routing table
+public:
+ Bucket** buckets; // Node bucket list - 160 sized.
+ explicit RoutingTable(unsigned int node_id);
+ ~RoutingTable();
+ void print();
+ Bucket* findBucket(unsigned int id);
+ bool contains(unsigned int node_id);
+};
+}
+
+#endif
--- /dev/null
+/* Copyright (c) 2012, 2014-2017. 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. */
+
+#include "s4u-dht-kademlia.hpp"
+
+#include "message.hpp"
+#include "node.hpp"
+#include "simgrid/s4u.hpp"
+
+XBT_LOG_NEW_DEFAULT_CATEGORY(kademlia, "Messages specific for this example");
+
+/** @brief Node function
+ * @param my node ID
+ * @param the ID of the person I know in the system (or not)
+ * @param Time before I leave the system because I'm bored
+ */
+static int node(int argc, char* argv[])
+{
+ bool join_success = true;
+ double deadline;
+ xbt_assert(argc == 3 || argc == 4, "Wrong number of arguments");
+ /* Node initialization */
+ unsigned int node_id = strtoul(argv[1], nullptr, 0);
+ kademlia::Node* node = new kademlia::Node(node_id);
+
+ if (argc == 4) {
+ XBT_INFO("Hi, I'm going to join the network with id %u", node->getId());
+ unsigned int known_id = strtoul(argv[2], NULL, 0);
+ join_success = node->join(known_id);
+ deadline = std::stod(argv[3]);
+ } else {
+ deadline = std::stod(argv[2]);
+ XBT_INFO("Hi, I'm going to create the network with id %u", node->getId());
+ node->routingTableUpdate(node->getId());
+ }
+
+ if (join_success) {
+ XBT_VERB("Ok, I'm joining the network with id %u", node->getId());
+ // We start the main loop
+ double next_lookup_time = simgrid::s4u::Engine::getClock() + random_lookup_interval;
+
+ XBT_VERB("Main loop start");
+
+ simgrid::s4u::MailboxPtr mailbox = simgrid::s4u::Mailbox::byName(std::to_string(node->getId()));
+
+ while (simgrid::s4u::Engine::getClock() < deadline) {
+ if (node->receive_comm == nullptr)
+ node->receive_comm = mailbox->get_async(&node->received_msg);
+
+ if (node->receive_comm->test()) {
+ // There has been a message, we need to handle it !
+ kademlia::Message* msg = static_cast<kademlia::Message*>(node->received_msg);
+ if (msg) {
+ node->handleFindNode(msg);
+ delete msg->answer_;
+ delete msg;
+ node->receive_comm = nullptr;
+ } else
+ simgrid::s4u::this_actor::sleep_for(1);
+ } else {
+ /* We search for a pseudo random node */
+ if (simgrid::s4u::Engine::getClock() >= next_lookup_time) {
+ node->randomLookup();
+ next_lookup_time += random_lookup_interval;
+ } else {
+ // Didn't get a message: sleep for a while...
+ simgrid::s4u::this_actor::sleep_for(1);
+ }
+ }
+ }
+ } else {
+ XBT_INFO("I couldn't join the network :(");
+ }
+ XBT_DEBUG("I'm leaving the network");
+ XBT_INFO("%u/%u FIND_NODE have succeeded", node->find_node_success, node->find_node_success + node->find_node_failed);
+ delete node;
+
+ return 0;
+}
+
+/** @brief Main function */
+int main(int argc, char* argv[])
+{
+ simgrid::s4u::Engine e(&argc, argv);
+
+ /* Check the arguments */
+ xbt_assert(argc > 2, "Usage: %s platform_file deployment_file\n\tExample: %s cluster.xml dht-kademlia_d.xml\n",
+ argv[0], argv[0]);
+
+ e.loadPlatform(argv[1]);
+ e.registerFunction("node", node);
+ e.loadDeployment(argv[2]);
+
+ e.run();
+
+ XBT_INFO("Simulated time: %g", simgrid::s4u::Engine::getClock());
+
+ return 0;
+}
--- /dev/null
+/* Copyright (c) 2012, 2014, 2016. 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. */
+
+#ifndef _S4U_KADEMLIA_HPP
+#define _S4U_KADEMLIA_HPP
+#include <algorithm>
+#include <simgrid/s4u.hpp>
+
+namespace kademlia {
+class Answer;
+class Message;
+class Ping;
+}
+
+#define max_join_trials 4
+
+#define RECEIVE_TIMEOUT 1
+
+#define ping_timeout 55
+#define find_node_timeout 10
+#define find_node_global_timeout 50
+
+#define kademlia_alpha 3
+#define BUCKET_SIZE 20
+
+#define identifier_size 32
+#define max_answers_to_ask 20
+
+#define random_lookup_interval 100
+
+#define MAX_STEPS 10
+
+#define JOIN_BUCKETS_QUERIES 5
+
+#define RANDOM_LOOKUP_NODE 0
+
+#endif
--- /dev/null
+#! ./tesh
+
+p Testing the Kademlia implementation with MSG
+
+! output sort 19
+$ $SG_TEST_EXENV ${bindir:=.}/s4u-dht-kademlia ${platfdir}/cluster.xml ${srcdir:=.}/s4u-dht-kademlia_d.xml "--log=root.fmt:[%10.6r]%e(%02i:%P@%h)%e%m%n"
+> [ 0.000000] ( 1:node@node-0.acme.org) Hi, I'm going to create the network with id 0
+> [ 0.000000] ( 2:node@node-1.acme.org) Hi, I'm going to join the network with id 1
+> [ 0.000000] ( 3:node@node-2.acme.org) Hi, I'm going to join the network with id 3
+> [ 0.000000] ( 4:node@node-3.acme.org) Hi, I'm going to join the network with id 7
+> [ 0.000000] ( 5:node@node-4.acme.org) Hi, I'm going to join the network with id 15
+> [ 0.000000] ( 6:node@node-5.acme.org) Hi, I'm going to join the network with id 31
+> [ 0.000000] ( 7:node@node-6.acme.org) Hi, I'm going to join the network with id 63
+> [ 0.000000] ( 8:node@node-7.acme.org) Hi, I'm going to join the network with id 127
+> [ 0.000000] ( 9:node@node-8.acme.org) Hi, I'm going to join the network with id 255
+> [ 0.000000] (10:node@node-9.acme.org) Hi, I'm going to join the network with id 511
+> [ 0.000000] (11:node@node-10.acme.org) Hi, I'm going to join the network with id 1023
+> [ 0.000000] (12:node@node-11.acme.org) Hi, I'm going to join the network with id 2047
+> [ 0.000000] (13:node@node-12.acme.org) Hi, I'm going to join the network with id 4095
+> [780.000000] ( 7:node@node-6.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] ( 9:node@node-8.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] ( 3:node@node-2.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] ( 2:node@node-1.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] (11:node@node-10.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] ( 1:node@node-0.acme.org) 7/7 FIND_NODE have succeeded
+> [780.000000] ( 5:node@node-4.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] (13:node@node-12.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] ( 8:node@node-7.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] ( 6:node@node-5.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] (10:node@node-9.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] (12:node@node-11.acme.org) 6/6 FIND_NODE have succeeded
+> [780.000000] ( 4:node@node-3.acme.org) 5/5 FIND_NODE have succeeded
+> [780.000000] ( 0:maestro@) Simulated time: 780
--- /dev/null
+<?xml version='1.0'?>
+<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid/simgrid.dtd">
+<platform version="4.1">
+
+ <actor host="node-0.acme.org" function="node">
+ <argument value="0x0000"/> <!-- my id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+
+ <actor host="node-1.acme.org" function="node">
+ <argument value="0x0001"/> <!-- my id -->
+ <argument value="0"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+
+ <actor host="node-2.acme.org" function="node">
+ <argument value="0x0003"/> <!-- my id -->
+ <argument value="0x0001"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+
+ <actor host="node-3.acme.org" function="node">
+ <argument value="0x0007"/> <!-- my id -->
+ <argument value="0x0003"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-4.acme.org" function="node">
+ <argument value="0x000f"/> <!-- my id -->
+ <argument value="0x0007"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-5.acme.org" function="node">
+ <argument value="0x001f"/> <!-- my id -->
+ <argument value="0x000f"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-6.acme.org" function="node">
+ <argument value="0x003f"/> <!-- my id -->
+ <argument value="0x001f"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-7.acme.org" function="node">
+ <argument value="0x007f"/> <!-- my id -->
+ <argument value="0x003f"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-8.acme.org" function="node">
+ <argument value="0x00ff"/> <!-- my id -->
+ <argument value="0x007f"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-9.acme.org" function="node">
+ <argument value="0x01ff"/> <!-- my id -->
+ <argument value="0x00ff"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-10.acme.org" function="node">
+ <argument value="0x03ff"/> <!-- my id -->
+ <argument value="0x01ff"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-11.acme.org" function="node">
+ <argument value="0x07ff"/> <!-- my id -->
+ <argument value="0x03ff"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+ <actor host="node-12.acme.org" function="node">
+ <argument value="0x0fff"/> <!-- my id -->
+ <argument value="0x0000"/> <!-- known id -->
+ <argument value ="780"/> <!-- deadline -->
+ </actor>
+</platform>
