From 579d27969fbc1fa8004de922816a0068e52a9fa6 Mon Sep 17 00:00:00 2001 From: Martin Quinson Date: Wed, 28 Dec 2016 00:17:32 +0100 Subject: [PATCH] Improve the routing documentation --- doc/doxygen/module-index.doc | 83 +++++++++++++++++++++++++++- doc/doxygen/module-surf.doc | 7 --- doc/doxygen/platform.doc | 78 ++++---------------------- src/kernel/routing/ClusterZone.cpp | 21 +++---- src/kernel/routing/ClusterZone.hpp | 51 +++++++++++++++++ src/kernel/routing/DijkstraZone.hpp | 10 ++++ src/kernel/routing/DragonflyZone.hpp | 8 +-- src/kernel/routing/EmptyZone.hpp | 8 ++- src/kernel/routing/FatTreeZone.hpp | 6 +- src/kernel/routing/FloydZone.hpp | 10 +++- src/kernel/routing/FullZone.hpp | 8 ++- src/kernel/routing/NetCard.hpp | 4 +- src/kernel/routing/NetZoneImpl.hpp | 15 ++--- src/kernel/routing/RoutedZone.hpp | 36 ++++++++++++ src/kernel/routing/TorusZone.hpp | 5 ++ src/kernel/routing/VivaldiZone.hpp | 32 ++++++++++- 16 files changed, 273 insertions(+), 109 deletions(-) diff --git a/doc/doxygen/module-index.doc b/doc/doxygen/module-index.doc index cfecff095d..b89f0d6e22 100644 --- a/doc/doxygen/module-index.doc +++ b/doc/doxygen/module-index.doc @@ -1,11 +1,11 @@ /** -@defgroup XBT_API XBT +@defgroup XBT_API XBT: SimGrid core toolbox @brief The core toolbox of SimGrid, containing useful datatypes and friends */ /** -@defgroup TRACE_API TRACE -@brief Tracing mechanism and its functions. +@defgroup TRACE_API TRACING +@brief Gather data about your simulation for later analysis SimGrid can trace the resource (of hosts and links) utilization using any of its programming interfaces (MSG, SimDAG and SMPI). This means @@ -22,6 +22,83 @@ are specified, simulations can still be traced using a special parameter in the command line (see \ref outcomes_vizu for details). */ +/** @defgroup ROUTING_API Routing: Determining the communication paths + @brief Organize the platform to determine the links used by each communication + +@section routing_basics Basic Concepts + +The purpose of the simgrid::kernel::routing module is to retrieve the +routing path between two points in a time- and space-efficient manner. +Indeed, the network model needs both the list of links that the convey +the created communication, and the summed latency that these links +represent. This operation is clearly on the critical path of most +SimGrid simulations. + +When defining how the information is routed in the simulated network, +it is certainly very tempting to use a formalism somehow similar to +how it is defined on real network. One would have to define the +routing tables of each routers interconnections sub-networks, just +like in the real life. Given the daunting amount of configuration +required, we could complete the information given by the user with +classical protocols such as BGP and RIP. Many network simulator take +such configuration as an input, for good reasons. + +This is not the way it goes in SimGrid: the network routing is defined +in a global and compact way instead. This eases the modeling of very +large systems, and allows highly optimized datastructures and +algorithms in the simulator. The proposed description mechanism is +thus much more convinient and efficient. In addition, it is more +expressive than the classical solution based on forwarding tables on +each host and router. + +The price to pay is that this representation of networks is very +specific to SimGrid, so you will have to read further to understand +it, even if you already know how real networks work. + +The central notion here are \b Networking \b Zones. NetZones represent +network areas in which the routing is done in an homogeneous way. +Conceptually, netzones generalize from the ideas of local networks +(such as Ethernet switched networks) and Autonomous System. The +network as a whole is represented as a single hierarchy of netzones, +meaning that every netzone is part of another netzone (but the \c +NetRoot, which is the top-level netzone). + +The main goal of the routing module is to provide a list of links +traversed by a given communication and/or a latency to apply. These +information are then used by the network model to compute the time +that this communication takes. This information is retrieved by three +combined algorithms: intra-zone routing, inter-zone routing, and the +bypass mechanism. + +The intra-zone level is naturally handled by the netzones. Each +netzone have to specify the routing algorithm it uses for that. +@ref{FullZone} netzones have complete matrix where matrix(a,b) +represents the full path (the list of links) between the hosts a and +b. @ref{FloydZone} apply the Floyd-Warshall algorithm to compute the +paths. @ref{ClusterZone} model classical switched or hub networks, +where each component is connected through a private link onto a common +backbone. Many other routing algorithms are provided to model the +classical needs, but you can naturally define your own routing if the +provided ones do not fit your needs. + +The inter-zone algorithm is used when the communication +traverses more than one zone. The overall path goes from the source up +in the netzones' tree, until the first common ancestor zone, and moves +down to the destination. It crawls the differing netzones on its path +according to the user-defined inter-zone routes, moving from gateway +to gateway. + +You can also use the bypass mechanism to specify manually some +shortcuts that directly provide the list of links interconnecting two +given processes. + +@section routing_declaring Declaring a platform + +For now, you can only declare a platform from an XML file, but we are +working to make it possible from the C++ code (or even from bindings +in other languages). Until then, please head to \ref platform. + +*/ /** \defgroup SIMIX_API SIMIX \brief POSIX-like interface for building simulation diff --git a/doc/doxygen/module-surf.doc b/doc/doxygen/module-surf.doc index 8587e4ed94..50c52f72c4 100644 --- a/doc/doxygen/module-surf.doc +++ b/doc/doxygen/module-surf.doc @@ -7,7 +7,6 @@ - \ref SURF_build_api - \ref SURF_c_bindings - \ref SURF_interface - - \ref SURF_routing_interface - \ref SURF_cpu_interface - \ref SURF_network_interface - \ref SURF_storage_interface @@ -93,12 +92,6 @@ @brief Describes the general interface for all components (Cpu, Network, Storage, Host, VM) */ -/** -@defgroup SURF_routing_interface SURF Routing Interface -@ingroup SURF_API -@brief Describes the routing interface -*/ - /** @defgroup SURF_cpu_interface SURF Cpu Interface @ingroup SURF_API diff --git a/doc/doxygen/platform.doc b/doc/doxygen/platform.doc index b35d4e575a..6aebdf5075 100644 --- a/doc/doxygen/platform.doc +++ b/doc/doxygen/platform.doc @@ -16,9 +16,11 @@ this information as an input: For more information on SimGrid's deployment features, please refer to the \ref deployment section. -The platform description may be intricate. This documentation is all about how to write this file. First, the basic -concepts are introduced. Then, advanced options are explained. Finally, some hints and tips on how to write a better -platform description are given. +The platform description may be intricate. This documentation is all +about how to write this file. You should read about the +@ref routing_basics "routing basic concepts" before proceeding. This page +first contain a reference guide of the XML. Finally, it gives some hints and tips on how to write a better +platform description. \section pf_overview Some words about XML and DTD @@ -34,75 +36,17 @@ If you read the DTD, you should notice the following: provide backward compatibility. \li The DTD contains definitions for both the platform description and deployment files used by SimGrid. -\section pf_basics Basic concepts - -It is certainly very tempting to defining how the information is -routed in the simulated network in a way that is very similar to how -it is defined on real network. One would have to define the routing -tables of each routers interconnections sub-networks, just like in the -real life. Given the daunting amount of configuration required, we -could complete the information given by the user with classical -protocols such as BGP and RIP. Many network simulator take such -configuration as an input, for good reasons. - -This is not the way it goes in SimGrid: the network routing is defined -in a global and compact way instead. This eases the modeling of very -large systems, and allows highly optimized datastructures and -algorithms in the simulator. The proposed description mechanism is -thus much more convinient and efficient. In addition, it is more -expressive than the classical solution based on forwarding tables on -each host and router. - -The price to pay is that this representation of networks is very -specific to SimGrid, so you will have to read further to understand -it, even if you already know how real networks work. - -The central notion here are \b Networking \b Zones. NetZones represent -network areas in which the routing is done in an homogeneous way. -Conceptually, netzones generalize from the ideas of local networks -(such as Ethernet switched networks) and Autonomous System. The -network as a whole is represented as a single hierarchy of netzones, -meaning that every netzone is part of another netzone (but the \c -NetRoot, which is the top-level netzone). - -The main goal of the routing module is to provide a list of links -traversed by a given communication and/or a latency to apply. These -information are then used by the network model to compute the time -that this communication takes. This information is retrieved by three -combined algorithms: intra-zone routing, inter-zone routing, and the -bypass mechanism. - -The intra-zone level is naturally handled by the netzones. Each -netzone have to specify the routing algorithm it uses for that. -@ref{FullZone} netzones have complete matrix where matrix(a,b) -represents the full path (the list of links) between the hosts a and -b. @ref{FloydZone} apply the Floyd-Warshall algorithm to compute the -paths. @ref{ClusterZone} model classical switched or hub networks, -where each component is connected through a private link onto a common -backbone. Many other routing algorithms are provided to model the -classical needs, but you can naturally define your own routing if the -provided ones do not fit your needs. - -The inter-zone algorithm is used when the communication -traverses more than one zone. The overall path goes from the source up -in the netzones' tree, until the first common ancestor zone, and moves -down to the destination. It crawls the differing netzones on its path -according to the user-defined inter-zone routes, moving from gateway -to gateway. - -You can also use the bypass mechanism to specify manually some -shortcuts that directly provide the list of links interconnecting two -given processes. +\section pf_netzones Defining a netzone + +Here is a simplistic example, describing a netzone using the Full +routing. Other supported values for the routing attribute can be +found below, Section \ref pf_raf. \verbatim \endverbatim -\remark - Other supported values for the routing attribute can be found below, Section - \ref pf_raf. - There is also the ```` tag; this tag takes two attributes, ``src`` (source) and ``dst`` (destination). Both source and destination must be valid identifiers for routers (these will be @@ -375,7 +319,7 @@ the router name is defined as the resulting String in the following java line of code: @verbatim -router_name = prefix + clusterId + _router + suffix; +router_name = prefix + clusterId + "_router" + suffix; @endverbatim diff --git a/src/kernel/routing/ClusterZone.cpp b/src/kernel/routing/ClusterZone.cpp index f4715b7b59..d2eb784757 100644 --- a/src/kernel/routing/ClusterZone.cpp +++ b/src/kernel/routing/ClusterZone.cpp @@ -26,16 +26,17 @@ void ClusterZone::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg xbt_assert(!privateLinks_.empty(), "Cluster routing: no links attached to the source node - did you use host_link tag?"); - if (!src->isRouter()) { // No specific link for router + if ((src->id() == dst->id()) && hasLoopback_) { + xbt_assert(!src->isRouter(), "Routing from a cluster private router to itself is meaningless"); - if ((src->id() == dst->id()) && hasLoopback_) { - std::pair info = privateLinks_.at(src->id() * linkCountPerNode_); - route->link_list->push_back(info.first); - if (lat) - *lat += info.first->latency(); - return; - } + std::pair info = privateLinks_.at(src->id() * linkCountPerNode_); + route->link_list->push_back(info.first); + if (lat) + *lat += info.first->latency(); + return; + } + if (!src->isRouter()) { // No private link for the private router if (hasLimiter_) { // limiter for sender std::pair info = privateLinks_.at(src->id() * linkCountPerNode_ + (hasLoopback_ ? 1 : 0)); route->link_list->push_back(info.first); @@ -57,8 +58,8 @@ void ClusterZone::getLocalRoute(NetCard* src, NetCard* dst, sg_platf_route_cbarg } if (!dst->isRouter()) { // No specific link for router - std::pair info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_ + hasLimiter_); + std::pair info = privateLinks_.at(dst->id() * linkCountPerNode_ + hasLoopback_ + hasLimiter_); if (info.second) { // link down route->link_list->push_back(info.second); if (lat) @@ -116,7 +117,7 @@ void ClusterZone::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges } } -void ClusterZone::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int, int position) +void ClusterZone::create_links_for_node(sg_platf_cluster_cbarg_t cluster, int id, int /*rank*/, int position) { char* link_id = bprintf("%s_link_%d", cluster->id, id); diff --git a/src/kernel/routing/ClusterZone.hpp b/src/kernel/routing/ClusterZone.hpp index adca587a1d..a9065181ab 100644 --- a/src/kernel/routing/ClusterZone.hpp +++ b/src/kernel/routing/ClusterZone.hpp @@ -14,6 +14,57 @@ namespace simgrid { namespace kernel { namespace routing { +/** @ingroup ROUTING_API + * @brief NetZone where each component is connected through a private link + * + * Cluster zones have a collection of private links that interconnect their components. + * This is particularly well adapted to model a collection of elements interconnected + * through a hub or a through a switch. + * + * In a cluster, each component are given from 1 to 3 private links at creation: + * - Private link (mandatory): link connecting the component to the cluster core. + * - Limiter (optional): Additional link on the way from the component to the cluster core + * - Loopback (optional): non-shared link connecting the component to itself. + * + * Then, the cluster core may be constituted of a specific backbone link or not; + * A backbone can easily represent a network connected in a Hub. + * If you want to model a switch, either don't use a backbone at all, + * or use a fatpipe link (non-shared link) to represent the switch backplane. + * + * \verbatim + * (outer world) + * | + * ======+====== <--backbone + * | | | | + * l0| l1| l2| l4| <-- private links + limiters + * | | | | + * X X X X <-- cluster's hosts + * \endverbatim + * + * \verbatim + * (outer world) + * | <-- NO backbone + * /|\ + * / | \ <-- private links + limiters __________ + * / | \ + * l0 / l1| \l2 + * / | \ + * host0 host1 host2 + * \endverbatim + + * So, a communication from an host A to an host B goes through the following links (if they exist): + * limiter(A)_UP, private(A)_UP, backbone, private(B)_DOWN, limiter(B)_DOWN. + * link_UP and link_DOWN usually share the exact same characteristics, but their + * performance are not shared, to model the fact that TCP links are full-duplex. + * + * A cluster is connected to the outer world through a router that is connected + * directly to the cluster's backbone (no private link). + * + * A communication from an host A to the outer world goes through the following links: + * limiter(A)_UP, private(A)_UP, backbone + * (because the private router is directly connected to the cluster core). + */ + class XBT_PRIVATE ClusterZone : public NetZoneImpl { public: explicit ClusterZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/DijkstraZone.hpp b/src/kernel/routing/DijkstraZone.hpp index 99442cb543..a8432cb4c9 100644 --- a/src/kernel/routing/DijkstraZone.hpp +++ b/src/kernel/routing/DijkstraZone.hpp @@ -30,6 +30,16 @@ namespace routing { * Classes * ***********/ +/** @ingroup ROUTING_API + * @brief NetZone with an explicit routing computed on need with Dijsktra + * + * The path between components is computed each time you request it, + * using the Dijkstra algorithm. A cache can be used to reduce the computation. + * + * This result in rather small platform file, very fast initialization, and intermediate memory requirements + * (somewhere between the one of @{DijkstraZone} and the one of @{FullZone}). + */ + /** Dijkstra routing data: fast initialization, slow lookup, small memory requirements, shortest path routing only */ class XBT_PRIVATE DijkstraZone : public RoutedZone { public: diff --git a/src/kernel/routing/DragonflyZone.hpp b/src/kernel/routing/DragonflyZone.hpp index 2090b32233..2cc15a51fa 100644 --- a/src/kernel/routing/DragonflyZone.hpp +++ b/src/kernel/routing/DragonflyZone.hpp @@ -25,10 +25,8 @@ public: ~DragonflyRouter(); }; -/** - * \class AsClusterDragonfly - * - * \brief Dragonfly representation and routing. +/** @ingroup ROUTING_API + * @brief NetZone using a Dragonfly topology * * Generate dragonfly according to the topology asked for, according to: * Cray Cascade: a Scalable HPC System based on a Dragonfly Network @@ -53,7 +51,7 @@ public: * LIMITATIONS (for now): * - Routing is only static and uses minimal routes. * - When n links are used between two routers/groups, we consider only one link with n times the bandwidth (needs to - * be validated on a real system) + * be validated on a real system) * - All links have the same characteristics for now * - Blue links are all attached to routers in the chassis n°0. This limits * the number of groups possible to the number of blades in a chassis. This diff --git a/src/kernel/routing/EmptyZone.hpp b/src/kernel/routing/EmptyZone.hpp index ad8c7a3e57..09b2fda222 100644 --- a/src/kernel/routing/EmptyZone.hpp +++ b/src/kernel/routing/EmptyZone.hpp @@ -12,7 +12,13 @@ namespace simgrid { namespace kernel { namespace routing { -/** No specific routing. Mainly useful with the constant network model */ +/** @ingroup ROUTING_API + * @brief NetZone with no routing, useful with the constant network model + * + * Such netzones never contain any link, and the latency is always left unchanged: + * the constant time network model computes this latency externally. + */ + class XBT_PRIVATE EmptyZone : public NetZoneImpl { public: explicit EmptyZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/FatTreeZone.hpp b/src/kernel/routing/FatTreeZone.hpp index 33937fa262..96616462dc 100644 --- a/src/kernel/routing/FatTreeZone.hpp +++ b/src/kernel/routing/FatTreeZone.hpp @@ -72,10 +72,8 @@ public: FatTreeNode* downNode; }; -/** - * \class AsClusterFatTree - * - * \brief Fat tree representation and routing. +/** @ingroup ROUTING_API + * @brief NetZone using a Fat-Tree topology * * Generate fat trees according to the topology asked for, according to: * Eitan Zahavi, D-Mod-K Routing Providing Non-Blocking Traffic for Shift diff --git a/src/kernel/routing/FloydZone.hpp b/src/kernel/routing/FloydZone.hpp index 27bcdc8889..74f0868cb9 100644 --- a/src/kernel/routing/FloydZone.hpp +++ b/src/kernel/routing/FloydZone.hpp @@ -12,7 +12,15 @@ namespace simgrid { namespace kernel { namespace routing { -/** Floyd routing data: slow initialization, fast lookup, lesser memory requirements, shortest path routing only */ +/** @ingroup ROUTING_API + * @brief NetZone with an explicit routing computed at initialization with Floyd-Warshal + * + * The path between components is computed at creation time from every one-hop links, + * using the Floyd-Warshal algorithm. + * + * This result in rather small platform file, slow initialization time, and intermediate memory requirements + * (somewhere between the one of @{DijkstraZone} and the one of @{FullZone}). + */ class XBT_PRIVATE FloydZone : public RoutedZone { public: explicit FloydZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/FullZone.hpp b/src/kernel/routing/FullZone.hpp index b3e93c6dee..e81519c180 100644 --- a/src/kernel/routing/FullZone.hpp +++ b/src/kernel/routing/FullZone.hpp @@ -12,7 +12,13 @@ namespace simgrid { namespace kernel { namespace routing { -/** Full routing: fast, large memory requirements, fully expressive */ +/** @ingroup ROUTING_API + * @brief NetZone with an explicit routing provided by the user + * + * The full communication matrix is provided at creation, so this model + * has the highest expressive power and the lowest computational requirements, + * but also the highest memory requirements (both in platform file and in memory). + */ class XBT_PRIVATE FullZone : public RoutedZone { public: explicit FullZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/NetCard.hpp b/src/kernel/routing/NetCard.hpp index 42c9ceb580..bffc783c3a 100644 --- a/src/kernel/routing/NetCard.hpp +++ b/src/kernel/routing/NetCard.hpp @@ -19,8 +19,8 @@ namespace simgrid { namespace kernel { namespace routing { -/** @ingroup SURF_routing_interface - * @brief Network cards are the vertices in the graph representing the network, used to compute paths between nodes. +/** @ingroup ROUTING_API + * @brief Network cards are the vertices in the graph representing the network, used to compute paths between nodes. * * @details This represents a position in the network. One can route information between two netcards */ diff --git a/src/kernel/routing/NetZoneImpl.hpp b/src/kernel/routing/NetZoneImpl.hpp index 4e1aa5876a..bc4341b738 100644 --- a/src/kernel/routing/NetZoneImpl.hpp +++ b/src/kernel/routing/NetZoneImpl.hpp @@ -21,20 +21,21 @@ class EngineImpl; namespace routing { class BypassRoute; -/** @brief Networking Zones +/** @ingroup ROUTING_API + * @brief Private implementation of the Networking Zones * - * A netzone is a network container, in charge of routing information between elements (hosts) and to the nearby - * netzones. In SimGrid, there is a hierarchy of netzones, ie a tree with a unique root NetZone, that you can retrieve - * from the s4u::Engine. + * A netzone is a network container, in charge of routing information between elements (hosts and sub-netzones) + * and to the nearby netzones. In SimGrid, there is a hierarchy of netzones, ie a tree with a unique root + * NetZone, that you can retrieve with simgrid::s4u::Engine::netRoot(). * * The purpose of the kernel::routing module is to retrieve the routing path between two points in a time- and * space-efficient manner. This is done by NetZoneImpl::getGlobalRoute(), called when creating a communication to * retrieve both the list of links that the create communication will use, and the summed latency that these * links represent. * - * The network could recompute the latency by itself from the list, but it would require an additional link - * set traversal. This operation being on the critical path of SimGrid, the routing computes the latency on the - * behalf of the network. + * The network model could recompute the latency by itself from the list, but it would require an additional + * traversal of the link set. This operation being on the critical path of SimGrid, the routing computes the + * latency on the behalf of the network while constructing the link set. * * Finding the path between two nodes is rather complex because we navigate a hierarchy of netzones, each of them * being a full network. In addition, the routing can declare shortcuts (called bypasses), either within a NetZone diff --git a/src/kernel/routing/RoutedZone.hpp b/src/kernel/routing/RoutedZone.hpp index 918856ff89..18c122b65e 100644 --- a/src/kernel/routing/RoutedZone.hpp +++ b/src/kernel/routing/RoutedZone.hpp @@ -12,6 +12,42 @@ namespace simgrid { namespace kernel { namespace routing { +/** @ingroup ROUTING_API + * @brief NetZone with an explicit routing (abstract class) + * + * This abstract class factorizes code between its subclasses: Full, Dijkstra and Floyd. + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + *
Comparison of the RoutedZone subclasses
DijkstraZoneFloydZoneFullZone
Platform-file contentOnly 1-hop routes (rather small)Only 1-hop routes (rather small)Every path, explicitly (very large)
Initialization timeAlmost nothingFloyd-Warshall algorithm: O(n^3)Almost nothing
Memory usage1-hop routes (+ cache of routes)O(n^2) data (intermediate)O(n^2) + sum of path lengths (very large)
Lookup timeDijkstra Algo: O(n^3)not much (reconstruction phase)Almost nothing
ExpressivenessOnly shortest pathOnly shortest pathEverything
+ */ + class XBT_PRIVATE RoutedZone : public NetZoneImpl { public: explicit RoutedZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/TorusZone.hpp b/src/kernel/routing/TorusZone.hpp index 1361f9b8f4..8d8c7a1a92 100644 --- a/src/kernel/routing/TorusZone.hpp +++ b/src/kernel/routing/TorusZone.hpp @@ -12,6 +12,11 @@ namespace simgrid { namespace kernel { namespace routing { +/** @ingroup ROUTING_API + * @brief NetZone using a Torus topology + * + */ + class XBT_PRIVATE TorusZone : public ClusterZone { public: explicit TorusZone(NetZone* father, const char* name); diff --git a/src/kernel/routing/VivaldiZone.hpp b/src/kernel/routing/VivaldiZone.hpp index 56da872f31..2c84ac7452 100644 --- a/src/kernel/routing/VivaldiZone.hpp +++ b/src/kernel/routing/VivaldiZone.hpp @@ -12,7 +12,37 @@ namespace simgrid { namespace kernel { namespace routing { -/* This extends cluster because each host has a private link */ +/** @ingroup ROUTING_API + * @brief NetZone modeling peers connected to the cloud through a private link + * + * This netzone model is particularly well adapted to Peer-to-Peer and Clouds platforms: + * each component is connected to the cloud through a private link of which the upload + * and download rate may be asymmetric. + * + * The network core (between the private links) is assumed to be over-sized so only the + * latency is taken into account. Instead of a matrix of latencies that would become too + * large when the amount of peers grows, Vivaldi netzones give a coordinate to each peer + * and compute the latency between host A=(xA,yA,zA) and host B=(xB,yB,zB) as follows: + * + * latency = sqrt( (xA-xB)² + (yA-yB)² ) + zA + zB + * + * The resulting value is assumed to be in milliseconds. + * + * So, to go from an host A to an host B, the following links would be used: + * private(A)_UP, private(B)_DOWN, with the additional latency computed above. + * + * Such Network Coordinate systems were shown to provide rather good latency estimations + * in a compact way. Other systems, such as + * + * were shown superior to the Vivaldi system and could be also implemented in SimGrid. + * + * + * @todo: the third dimension of the coordinates could be dropped and integrated in the peer private links. + * + * @todo: we should provide a script to compute the coordinates from a matrix of latency measurements, + * according to the corresponding publications. + */ + class XBT_PRIVATE VivaldiZone : public ClusterZone { public: explicit VivaldiZone(NetZone* father, const char* name); -- 2.20.1