From eb46f8ef11f386cac9f2da08028a93ee5e963b93 Mon Sep 17 00:00:00 2001 From: Frederic Suter Date: Wed, 10 Jan 2018 12:07:33 +0100 Subject: [PATCH 1/1] convert kademlia example to s4u --- examples/s4u/CMakeLists.txt | 21 +- examples/s4u/dht-kademlia/answer.cpp | 82 +++++ examples/s4u/dht-kademlia/answer.hpp | 36 ++ examples/s4u/dht-kademlia/generate.py | 42 +++ examples/s4u/dht-kademlia/message.hpp | 44 +++ examples/s4u/dht-kademlia/node.cpp | 311 ++++++++++++++++++ examples/s4u/dht-kademlia/node.hpp | 42 +++ examples/s4u/dht-kademlia/routing_table.cpp | 65 ++++ examples/s4u/dht-kademlia/routing_table.hpp | 37 +++ .../s4u/dht-kademlia/s4u-dht-kademlia.cpp | 102 ++++++ .../s4u/dht-kademlia/s4u-dht-kademlia.hpp | 40 +++ .../s4u/dht-kademlia/s4u-dht-kademlia.tesh | 33 ++ .../s4u/dht-kademlia/s4u-dht-kademlia_d.xml | 72 ++++ 13 files changed, 924 insertions(+), 3 deletions(-) create mode 100644 examples/s4u/dht-kademlia/answer.cpp create mode 100644 examples/s4u/dht-kademlia/answer.hpp create mode 100755 examples/s4u/dht-kademlia/generate.py create mode 100644 examples/s4u/dht-kademlia/message.hpp create mode 100644 examples/s4u/dht-kademlia/node.cpp create mode 100644 examples/s4u/dht-kademlia/node.hpp create mode 100644 examples/s4u/dht-kademlia/routing_table.cpp create mode 100644 examples/s4u/dht-kademlia/routing_table.hpp create mode 100644 examples/s4u/dht-kademlia/s4u-dht-kademlia.cpp create mode 100644 examples/s4u/dht-kademlia/s4u-dht-kademlia.hpp create mode 100644 examples/s4u/dht-kademlia/s4u-dht-kademlia.tesh create mode 100644 examples/s4u/dht-kademlia/s4u-dht-kademlia_d.xml diff --git a/examples/s4u/CMakeLists.txt b/examples/s4u/CMakeLists.txt index 9b3d096aff..b5dc97e423 100644 --- a/examples/s4u/CMakeLists.txt +++ b/examples/s4u/CMakeLists.txt @@ -26,6 +26,18 @@ foreach (file s4u-dht-chord node) 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) @@ -38,6 +50,7 @@ endforeach() 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 @@ -55,13 +68,15 @@ set(xml_files ${xml_files} ${CMAKE_CURRENT_SOURCE_DIR}/actor-create/s4u-a ${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 @@ -72,7 +87,7 @@ foreach(example actor-create actor-daemon actor-join actor-kill actor-lifetime a 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 diff --git a/examples/s4u/dht-kademlia/answer.cpp b/examples/s4u/dht-kademlia/answer.cpp new file mode 100644 index 0000000000..48ee12bdf3 --- /dev/null +++ b/examples/s4u/dht-kademlia/answer.cpp @@ -0,0 +1,82 @@ +/* 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& a, const std::pair& 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(id, distance)); + size_++; + } +} +} diff --git a/examples/s4u/dht-kademlia/answer.hpp b/examples/s4u/dht-kademlia/answer.hpp new file mode 100644 index 0000000000..e17a5b9b62 --- /dev/null +++ b/examples/s4u/dht-kademlia/answer.hpp @@ -0,0 +1,36 @@ +/* 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 + +namespace kademlia { +bool sortbydistance(const std::pair& a, const std::pair& 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> 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 diff --git a/examples/s4u/dht-kademlia/generate.py b/examples/s4u/dht-kademlia/generate.py new file mode 100755 index 0000000000..d75dbbad54 --- /dev/null +++ b/examples/s4u/dht-kademlia/generate.py @@ -0,0 +1,42 @@ +#!/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("\n" + "\n" + "\n \n" + " \n \n \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 = " \n "\ + "\n \n \n \n" % ( + i, my_id, known_id, end_date) + sys.stdout.write(line) + all_ids.append(my_id) + +sys.stdout.write("") diff --git a/examples/s4u/dht-kademlia/message.hpp b/examples/s4u/dht-kademlia/message.hpp new file mode 100644 index 0000000000..910be6aafa --- /dev/null +++ b/examples/s4u/dht-kademlia/message.hpp @@ -0,0 +1,44 @@ +/* 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 diff --git a/examples/s4u/dht-kademlia/node.cpp b/examples/s4u/dht-kademlia/node.cpp new file mode 100644 index 0000000000..46d7e1d93e --- /dev/null +++ b/examples/s4u/dht-kademlia/node.cpp @@ -0,0 +1,311 @@ +/* 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); + 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(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(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; +} diff --git a/examples/s4u/dht-kademlia/node.hpp b/examples/s4u/dht-kademlia/node.hpp new file mode 100644 index 0000000000..10625d03ae --- /dev/null +++ b/examples/s4u/dht-kademlia/node.hpp @@ -0,0 +1,42 @@ +/* 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 */ diff --git a/examples/s4u/dht-kademlia/routing_table.cpp b/examples/s4u/dht-kademlia/routing_table.cpp new file mode 100644 index 0000000000..d93a57f0d9 --- /dev/null +++ b/examples/s4u/dht-kademlia/routing_table.cpp @@ -0,0 +1,65 @@ +/* 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(); +} +} diff --git a/examples/s4u/dht-kademlia/routing_table.hpp b/examples/s4u/dht-kademlia/routing_table.hpp new file mode 100644 index 0000000000..60354ce0f4 --- /dev/null +++ b/examples/s4u/dht-kademlia/routing_table.hpp @@ -0,0 +1,37 @@ +/* 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 + +namespace kademlia { + +/* Routing table bucket */ +class Bucket { + unsigned int id_; // bucket id +public: + std::deque 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 diff --git a/examples/s4u/dht-kademlia/s4u-dht-kademlia.cpp b/examples/s4u/dht-kademlia/s4u-dht-kademlia.cpp new file mode 100644 index 0000000000..c6aa178669 --- /dev/null +++ b/examples/s4u/dht-kademlia/s4u-dht-kademlia.cpp @@ -0,0 +1,102 @@ +/* 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(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; +} diff --git a/examples/s4u/dht-kademlia/s4u-dht-kademlia.hpp b/examples/s4u/dht-kademlia/s4u-dht-kademlia.hpp new file mode 100644 index 0000000000..c5bf43f556 --- /dev/null +++ b/examples/s4u/dht-kademlia/s4u-dht-kademlia.hpp @@ -0,0 +1,40 @@ +/* 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 +#include + +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 diff --git a/examples/s4u/dht-kademlia/s4u-dht-kademlia.tesh b/examples/s4u/dht-kademlia/s4u-dht-kademlia.tesh new file mode 100644 index 0000000000..ec1a873132 --- /dev/null +++ b/examples/s4u/dht-kademlia/s4u-dht-kademlia.tesh @@ -0,0 +1,33 @@ +#! ./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 diff --git a/examples/s4u/dht-kademlia/s4u-dht-kademlia_d.xml b/examples/s4u/dht-kademlia/s4u-dht-kademlia_d.xml new file mode 100644 index 0000000000..e199776298 --- /dev/null +++ b/examples/s4u/dht-kademlia/s4u-dht-kademlia_d.xml @@ -0,0 +1,72 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + -- 2.20.1