src/kernel/routing/DijkstraZone.cpp

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