src/kernel/routing/DijkstraZone.cpp

   1 /* Copyright (c) 2009-2022. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include <simgrid/kernel/routing/DijkstraZone.hpp>
   7 #include <simgrid/kernel/routing/NetPoint.hpp>
   8 #include <xbt/string.hpp>
   9
  10 #include "src/kernel/resource/StandardLinkImpl.hpp"
  11
  12 #include <climits>
  13 #include <queue>
  14 #include <vector>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_dijkstra, surf, "Routing part of surf -- dijkstra routing logic");
  17
  18 namespace simgrid {
  19 namespace kernel {
  20 namespace routing {
  21
  22 class GraphNodeData {
  23 public:
  24   explicit GraphNodeData(unsigned long id) : id_(id) {}
  25   unsigned long id_;
  26   unsigned long graph_id_ = UINT_MAX; /* used for caching internal graph id's */
  27 };
  28
  29 void DijkstraZone::route_graph_delete(xbt_graph_t g)
  30 {
  31   xbt_graph_free_graph(
  32       g, [](void* n) { delete static_cast<GraphNodeData*>(n); }, [](void* e) { delete static_cast<Route*>(e); },
  33       nullptr);
  34 }
  35
  36 void DijkstraZone::do_seal()
  37 {
  38   unsigned int cursor;
  39   xbt_node_t node = nullptr;
  40
  41   /* Add the loopback if needed */
  42   if (get_network_model()->loopback_ && get_hierarchy() == RoutingMode::base) {
  43     xbt_dynar_foreach (xbt_graph_get_nodes(route_graph_.get()), cursor, node) {
  44       bool found      = false;
  45       xbt_edge_t edge = nullptr;
  46       unsigned int cursor2;
  47       xbt_dynar_foreach (xbt_graph_node_get_outedges(node), cursor2, edge) {
  48         if (xbt_graph_edge_get_target(edge) == node) { // There is an edge from node to itself
  49           found = true;
  50           break;
  51         }
  52       }
  53
  54       if (not found) {
  55         auto* route = new Route();
  56         route->link_list_.push_back(get_network_model()->loopback_);
  57         xbt_graph_new_edge(route_graph_.get(), node, node, route);
  58       }
  59     }
  60   }
  61
  62   /* initialize graph indexes in nodes after graph has been built */
  63   const_xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_.get());
  64
  65   xbt_dynar_foreach (nodes, cursor, node) {
  66     auto* data      = static_cast<GraphNodeData*>(xbt_graph_node_get_data(node));
  67     data->graph_id_ = cursor;
  68   }
  69 }
  70
  71 xbt_node_t DijkstraZone::route_graph_new_node(unsigned long id)
  72 {
  73   xbt_node_t node = xbt_graph_new_node(route_graph_.get(), new GraphNodeData(id));
  74   graph_node_map_.emplace(id, node);
  75
  76   return node;
  77 }
  78
  79 xbt_node_t DijkstraZone::node_map_search(unsigned long id)
  80 {
  81   auto ret = graph_node_map_.find(id);
  82   return ret == graph_node_map_.end() ? nullptr : ret->second;
  83 }
  84
  85 /* Parsing */
  86
  87 void DijkstraZone::get_local_route(const NetPoint* src, const NetPoint* dst, Route* route, double* lat)
  88 {
  89   get_route_check_params(src, dst);
  90   unsigned long src_id = src->id();
  91   unsigned long dst_id = dst->id();
  92
  93   const_xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_.get());
  94
  95   /* Use the graph_node id mapping set to quickly find the nodes */
  96   const s_xbt_node_t* src_elm = node_map_search(src_id);
  97   const s_xbt_node_t* dst_elm = node_map_search(dst_id);
  98
  99   unsigned long src_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(src_elm))->graph_id_;
 100   unsigned long dst_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(dst_elm))->graph_id_;
 101
 102   /* if the src and dst are the same */
 103   if (src_node_id == dst_node_id) {
 104     const s_xbt_node_t* node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
 105     const s_xbt_node_t* node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
 106     const s_xbt_edge_t* edge     = xbt_graph_get_edge(route_graph_.get(), node_s_v, node_e_v);
 107
 108     if (edge == nullptr)
 109       throw std::invalid_argument(xbt::string_printf("No route from '%s' to '%s'", src->get_cname(), dst->get_cname()));
 110
 111     const Route* e_route = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 112
 113     insert_link_latency(route->link_list_, e_route->link_list_, lat);
 114   }
 115
 116   auto elm                             = route_cache_.emplace(src_id, std::vector<unsigned long>());
 117   std::vector<unsigned long>& pred_arr = elm.first->second;
 118
 119   if (elm.second) { /* new element was inserted (not cached mode, or cache miss) */
 120     unsigned long nr_nodes = xbt_dynar_length(nodes);
 121     std::vector<unsigned long> cost_arr(nr_nodes); /* link cost from src to other hosts */
 122     pred_arr.resize(nr_nodes);              /* predecessors in path from src */
 123     using Qelt = std::pair<double, unsigned long>;
 124     std::priority_queue<Qelt, std::vector<Qelt>, std::greater<>> pqueue;
 125
 126     /* initialize */
 127     cost_arr[src_node_id] = 0;
 128
 129     for (unsigned long i = 0; i < nr_nodes; i++) {
 130       if (i != src_node_id) {
 131         cost_arr[i] = ULONG_MAX;
 132       }
 133
 134       pred_arr[i] = 0;
 135
 136       /* initialize priority queue */
 137       pqueue.emplace(cost_arr[i], i);
 138     }
 139
 140     /* apply dijkstra using the indexes from the graph's node array */
 141     while (not pqueue.empty()) {
 142       unsigned long v_id = pqueue.top().second;
 143       pqueue.pop();
 144       const s_xbt_node_t* v_node = xbt_dynar_get_as(nodes, v_id, xbt_node_t);
 145       xbt_edge_t edge            = nullptr;
 146       unsigned int cursor;
 147
 148       xbt_dynar_foreach (xbt_graph_node_get_outedges(v_node), cursor, edge) {
 149         const s_xbt_node_t* u_node           = xbt_graph_edge_get_target(edge);
 150         const GraphNodeData* data            = static_cast<GraphNodeData*>(xbt_graph_node_get_data(u_node));
 151         unsigned long u_id                   = data->graph_id_;
 152         const Route* tmp_e_route             = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 153         unsigned long cost_v_u               = tmp_e_route->link_list_.size(); /* count of links, old model assume 1 */
 154
 155         if (cost_v_u + cost_arr[v_id] < cost_arr[u_id]) {
 156           pred_arr[u_id] = v_id;
 157           cost_arr[u_id] = cost_v_u + cost_arr[v_id];
 158           pqueue.emplace(cost_arr[u_id], u_id);
 159         }
 160       }
 161     }
 162   }
 163
 164   /* compose route path with links */
 165   NetPoint* gw_src   = nullptr;
 166   NetPoint* first_gw = nullptr;
 167
 168   for (unsigned long v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
 169     const s_xbt_node_t* node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
 170     const s_xbt_node_t* node_v      = xbt_dynar_get_as(nodes, v, xbt_node_t);
 171     const s_xbt_edge_t* edge        = xbt_graph_get_edge(route_graph_.get(), node_pred_v, node_v);
 172
 173     if (edge == nullptr)
 174       throw std::invalid_argument(xbt::string_printf("No route from '%s' to '%s'", src->get_cname(), dst->get_cname()));
 175
 176     const Route* e_route = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 177
 178     const NetPoint* prev_gw_src = gw_src;
 179     gw_src                      = e_route->gw_src_;
 180     NetPoint* gw_dst            = e_route->gw_dst_;
 181
 182     if (v == dst_node_id)
 183       first_gw = gw_dst;
 184
 185     if (get_hierarchy() == RoutingMode::recursive && v != dst_node_id &&
 186         gw_dst->get_name() != prev_gw_src->get_name()) {
 187       std::vector<resource::StandardLinkImpl*> e_route_as_to_as;
 188
 189       const NetPoint* gw_dst_net_elm      = nullptr;
 190       const NetPoint* prev_gw_src_net_elm = nullptr;
 191       get_global_route(gw_dst_net_elm, prev_gw_src_net_elm, e_route_as_to_as, nullptr);
 192       std::reverse(begin(e_route_as_to_as), end(e_route_as_to_as));
 193       insert_link_latency(route->link_list_, e_route_as_to_as, lat);
 194     }
 195
 196     insert_link_latency(route->link_list_, e_route->link_list_, lat);
 197   }
 198
 199   if (get_hierarchy() == RoutingMode::recursive) {
 200     route->gw_src_ = gw_src;
 201     route->gw_dst_ = first_gw;
 202   }
 203
 204   if (not cached_)
 205     route_cache_.clear();
 206 }
 207
 208 void DijkstraZone::add_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
 209                              const std::vector<s4u::LinkInRoute>& link_list, bool symmetrical)
 210 {
 211   add_route_check_params(src, dst, gw_src, gw_dst, link_list, symmetrical);
 212
 213   new_edge(src->id(), dst->id(),
 214            new_extended_route(get_hierarchy(), gw_src, gw_dst, get_link_list_impl(link_list, false), true));
 215
 216   if (symmetrical)
 217     new_edge(dst->id(), src->id(),
 218              new_extended_route(get_hierarchy(), gw_dst, gw_src, get_link_list_impl(link_list, true), false));
 219 }
 220
 221 void DijkstraZone::new_edge(unsigned long src_id, unsigned long dst_id, Route* route)
 222 {
 223   XBT_DEBUG("Create Route from '%lu' to '%lu'", src_id, dst_id);
 224
 225   // Get the extremities, or create them if they don't exist yet
 226   xbt_node_t src = node_map_search(src_id);
 227   if (src == nullptr)
 228     src = route_graph_new_node(src_id);
 229
 230   xbt_node_t dst = node_map_search(dst_id);
 231   if (dst == nullptr)
 232     dst = route_graph_new_node(dst_id);
 233
 234   // Make sure that this graph edge was not already added to the graph
 235   if (xbt_graph_get_edge(route_graph_.get(), src, dst) != nullptr) {
 236     if (route->gw_dst_ == nullptr || route->gw_src_ == nullptr)
 237       throw std::invalid_argument(
 238           xbt::string_printf("Route from %s to %s already exists", route->src_->get_cname(), route->dst_->get_cname()));
 239     else
 240       throw std::invalid_argument(xbt::string_printf("Route from %s@%s to %s@%s already exists",
 241                                                      route->src_->get_cname(), route->gw_src_->get_cname(),
 242                                                      route->dst_->get_cname(), route->gw_dst_->get_cname()));
 243   }
 244
 245   // Finally add it
 246   xbt_graph_new_edge(route_graph_.get(), src, dst, route);
 247 }
 248 } // namespace routing
 249 } // namespace kernel
 250
 251 namespace s4u {
 252 NetZone* create_dijkstra_zone(const std::string& name, bool cache)
 253 {
 254   return (new kernel::routing::DijkstraZone(name, cache))->get_iface();
 255 }
 256 } // namespace s4u
 257
 258 } // namespace simgrid