src/kernel/routing/DijkstraZone.cpp

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