src/surf/surf_routing_dijkstra.cpp

   1 /* Copyright (c) 2009-2015. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "surf_routing_dijkstra.hpp"
   8 #include "network_interface.hpp"
   9
  10 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_dijkstra, surf, "Routing part of surf -- dijkstra routing logic");
  11
  12 /* Free functions */
  13
  14 static void route_cache_elem_free(void *e)
  15 {
  16   route_cache_element_t elm = (route_cache_element_t) e;
  17   if (elm) {
  18     xbt_free(elm->pred_arr);
  19     xbt_free(elm);
  20   }
  21 }
  22
  23 static void graph_node_map_elem_free(void *e)
  24 {
  25   graph_node_map_element_t elm = (graph_node_map_element_t) e;
  26   xbt_free(elm);
  27 }
  28
  29 static void graph_edge_data_free(void *e) // FIXME: useless code duplication
  30 {
  31   sg_platf_route_cbarg_t e_route = (sg_platf_route_cbarg_t) e;
  32   if (e_route) {
  33     xbt_dynar_free(&(e_route->link_list));
  34     xbt_free(e_route);
  35   }
  36 }
  37
  38 AS_t model_dijkstra_create(void){
  39   return new AsDijkstra(0);
  40 }
  41
  42 AS_t model_dijkstracache_create(void){
  43   return new AsDijkstra(1);
  44 }
  45
  46 void model_dijkstra_both_end(AS_t as)
  47 {
  48   AsDijkstra *THIS_AS = static_cast<AsDijkstra*>(as);
  49   xbt_node_t node = NULL;
  50   unsigned int cursor2;
  51   xbt_dynar_t nodes = NULL;
  52
  53   /* Create the topology graph */
  54   if(!THIS_AS->p_routeGraph)
  55     THIS_AS->p_routeGraph = xbt_graph_new_graph(1, NULL);
  56   if(!THIS_AS->p_graphNodeMap)
  57     THIS_AS->p_graphNodeMap = xbt_dict_new_homogeneous(&graph_node_map_elem_free);
  58
  59   if (THIS_AS->m_cached && !THIS_AS->p_routeCache)
  60     THIS_AS->p_routeCache = xbt_dict_new_homogeneous(&route_cache_elem_free);
  61
  62   /* Add the loopback if needed */
  63   if (routing_platf->p_loopback && as->p_hierarchy == SURF_ROUTING_BASE)
  64     THIS_AS->addLoopback();
  65
  66   /* initialize graph indexes in nodes after graph has been built */
  67   nodes = xbt_graph_get_nodes(THIS_AS->p_routeGraph);
  68
  69   xbt_dynar_foreach(nodes, cursor2, node) {
  70     graph_node_data_t data = (graph_node_data_t) xbt_graph_node_get_data(node);
  71     data->graph_id = cursor2;
  72   }
  73 }
  74
  75 /* Utility functions */
  76
  77 xbt_node_t AsDijkstra::routeGraphNewNode(int id, int graph_id)
  78 {
  79   xbt_node_t node = NULL;
  80   graph_node_data_t data = NULL;
  81   graph_node_map_element_t elm = NULL;
  82
  83   data = xbt_new0(struct graph_node_data, 1);
  84   data->id = id;
  85   data->graph_id = graph_id;
  86   node = xbt_graph_new_node(p_routeGraph, data);
  87
  88   elm = xbt_new0(struct graph_node_map_element, 1);
  89   elm->node = node;
  90   xbt_dict_set_ext(p_graphNodeMap, (char *) (&id), sizeof(int),
  91       (xbt_set_elm_t) elm, NULL);
  92
  93   return node;
  94 }
  95
  96 graph_node_map_element_t AsDijkstra::nodeMapSearch(int id)
  97 {
  98   graph_node_map_element_t elm = (graph_node_map_element_t)
  99           xbt_dict_get_or_null_ext(p_graphNodeMap,
 100               (char *) (&id),
 101               sizeof(int));
 102   return elm;
 103 }
 104
 105 /* Parsing */
 106
 107 void AsDijkstra::newRoute(int src_id, int dst_id, sg_platf_route_cbarg_t e_route)
 108 {
 109   XBT_DEBUG("Load Route from \"%d\" to \"%d\"", src_id, dst_id);
 110   xbt_node_t src = NULL;
 111   xbt_node_t dst = NULL;
 112
 113   graph_node_map_element_t src_elm = (graph_node_map_element_t)
 114           xbt_dict_get_or_null_ext(p_graphNodeMap,
 115               (char *) (&src_id),
 116               sizeof(int));
 117   graph_node_map_element_t dst_elm = (graph_node_map_element_t)
 118           xbt_dict_get_or_null_ext(p_graphNodeMap,
 119               (char *) (&dst_id),
 120               sizeof(int));
 121
 122
 123   if (src_elm)
 124     src = src_elm->node;
 125
 126   if (dst_elm)
 127     dst = dst_elm->node;
 128
 129   /* add nodes if they don't exist in the graph */
 130   if (src_id == dst_id && src == NULL && dst == NULL) {
 131     src = this->routeGraphNewNode(src_id, -1);
 132     dst = src;
 133   } else {
 134     if (src == NULL) {
 135       src = this->routeGraphNewNode(src_id, -1);
 136     }
 137     if (dst == NULL) {
 138       dst = this->routeGraphNewNode(dst_id, -1);
 139     }
 140   }
 141
 142   /* add link as edge to graph */
 143   xbt_graph_new_edge(p_routeGraph, src, dst, e_route);
 144 }
 145
 146 void AsDijkstra::addLoopback() {
 147   xbt_dynar_t nodes = xbt_graph_get_nodes(p_routeGraph);
 148
 149   xbt_node_t node = NULL;
 150   unsigned int cursor2;
 151   xbt_dynar_foreach(nodes, cursor2, node) {
 152     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
 153     xbt_edge_t edge = NULL;
 154     unsigned int cursor;
 155
 156     int found = 0;
 157     xbt_dynar_foreach(out_edges, cursor, edge) {
 158       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
 159       if (other_node == node) {
 160         found = 1;
 161         break;
 162       }
 163     }
 164
 165     if (!found) {
 166       sg_platf_route_cbarg_t e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 167       e_route->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 168       xbt_dynar_push(e_route->link_list, &routing_platf->p_loopback);
 169       xbt_graph_new_edge(p_routeGraph, node, node, e_route);
 170     }
 171   }
 172 }
 173
 174 xbt_dynar_t AsDijkstra::getOnelinkRoutes()
 175 {
 176   xbt_dynar_t ret = xbt_dynar_new(sizeof(Onelink*), xbt_free_f);
 177   sg_platf_route_cbarg_t route = xbt_new0(s_sg_platf_route_cbarg_t,1);
 178   route->link_list = xbt_dynar_new(sizeof(sg_routing_link_t),NULL);
 179
 180   int src,dst;
 181   RoutingEdge *src_elm, *dst_elm;
 182   int table_size = (int)xbt_dynar_length(p_indexNetworkElm);
 183   for(src=0; src < table_size; src++) {
 184     for(dst=0; dst< table_size; dst++) {
 185       xbt_dynar_reset(route->link_list);
 186       src_elm = xbt_dynar_get_as(p_indexNetworkElm, src, RoutingEdge*);
 187       dst_elm = xbt_dynar_get_as(p_indexNetworkElm, dst, RoutingEdge*);
 188       this->getRouteAndLatency(src_elm, dst_elm,route, NULL);
 189
 190       if (xbt_dynar_length(route->link_list) == 1) {
 191         void *link = *(void **) xbt_dynar_get_ptr(route->link_list, 0);
 192         Onelink *onelink;
 193         if (p_hierarchy == SURF_ROUTING_BASE)
 194           onelink = new Onelink(link, src_elm, dst_elm);
 195         else if (p_hierarchy == SURF_ROUTING_RECURSIVE)
 196           onelink = new Onelink(link, route->gw_src, route->gw_dst);
 197         else
 198           onelink = new Onelink(link, NULL, NULL);
 199         xbt_dynar_push(ret, &onelink);
 200       }
 201     }
 202   }
 203   return ret;
 204 }
 205
 206 void AsDijkstra::getRouteAndLatency(RoutingEdge *src, RoutingEdge *dst, sg_platf_route_cbarg_t route, double *lat)
 207 {
 208
 209   /* set utils vars */
 210
 211   srcDstCheck(src, dst);
 212   int *src_id = src->getIdPtr();
 213   int *dst_id = dst->getIdPtr();
 214
 215   if (!src_id || !dst_id)
 216     THROWF(arg_error,0,"No route from '%s' to '%s'",src->getName(),dst->getName());
 217
 218   int *pred_arr = NULL;
 219   int src_node_id = 0;
 220   int dst_node_id = 0;
 221   int *nodeid = NULL;
 222   int v;
 223   sg_platf_route_cbarg_t e_route;
 224   int size = 0;
 225   unsigned int cpt;
 226   void *link;
 227   xbt_dynar_t links = NULL;
 228   route_cache_element_t elm = NULL;
 229   xbt_dynar_t nodes = xbt_graph_get_nodes(p_routeGraph);
 230
 231   /* Use the graph_node id mapping set to quickly find the nodes */
 232   graph_node_map_element_t src_elm = nodeMapSearch(*src_id);
 233   graph_node_map_element_t dst_elm = nodeMapSearch(*dst_id);
 234
 235   src_node_id = ((graph_node_data_t)
 236       xbt_graph_node_get_data(src_elm->node))->graph_id;
 237   dst_node_id = ((graph_node_data_t)
 238       xbt_graph_node_get_data(dst_elm->node))->graph_id;
 239
 240   /* if the src and dst are the same */
 241   if (src_node_id == dst_node_id) {
 242
 243     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
 244     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
 245     xbt_edge_t edge = xbt_graph_get_edge(p_routeGraph, node_s_v, node_e_v);
 246
 247     if (edge == NULL)
 248       THROWF(arg_error, 0, "No route from '%s' to '%s'", src->getName(), dst->getName());
 249
 250     e_route = (sg_platf_route_cbarg_t) xbt_graph_edge_get_data(edge);
 251
 252     links = e_route->link_list;
 253     xbt_dynar_foreach(links, cpt, link) {
 254       xbt_dynar_unshift(route->link_list, &link);
 255       if (lat)
 256         *lat += static_cast<Link*>(link)->getLatency();
 257     }
 258
 259   }
 260
 261   if (m_cached) {
 262     /*check if there is a cached predecessor list avail */
 263     elm = (route_cache_element_t)
 264             xbt_dict_get_or_null_ext(p_routeCache, (char *) (&src_id),
 265                 sizeof(int));
 266   }
 267
 268   if (elm) {                    /* cached mode and cache hit */
 269     pred_arr = elm->pred_arr;
 270   } else {                      /* not cached mode or cache miss */
 271     double *cost_arr = NULL;
 272     xbt_heap_t pqueue = NULL;
 273     int i = 0;
 274
 275     int nr_nodes = xbt_dynar_length(nodes);
 276     cost_arr = xbt_new0(double, nr_nodes);      /* link cost from src to other hosts */
 277     pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */
 278     pqueue = xbt_heap_new(nr_nodes, xbt_free_f);
 279
 280     /* initialize */
 281     cost_arr[src_node_id] = 0.0;
 282
 283     for (i = 0; i < nr_nodes; i++) {
 284       if (i != src_node_id) {
 285         cost_arr[i] = DBL_MAX;
 286       }
 287
 288       pred_arr[i] = 0;
 289
 290       /* initialize priority queue */
 291       nodeid = xbt_new0(int, 1);
 292       *nodeid = i;
 293       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
 294
 295     }
 296
 297     /* apply dijkstra using the indexes from the graph's node array */
 298     while (xbt_heap_size(pqueue) > 0) {
 299       int *v_id = (int *) xbt_heap_pop(pqueue);
 300       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
 301       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
 302       xbt_edge_t edge = NULL;
 303       unsigned int cursor;
 304
 305       xbt_dynar_foreach(out_edges, cursor, edge) {
 306         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
 307         graph_node_data_t data = (graph_node_data_t) xbt_graph_node_get_data(u_node);
 308         int u_id = data->graph_id;
 309         sg_platf_route_cbarg_t tmp_e_route = (sg_platf_route_cbarg_t) xbt_graph_edge_get_data(edge);
 310         int cost_v_u = (tmp_e_route->link_list)->used;    /* count of links, old model assume 1 */
 311
 312         if (cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
 313           pred_arr[u_id] = *v_id;
 314           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
 315           nodeid = xbt_new0(int, 1);
 316           *nodeid = u_id;
 317           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
 318         }
 319       }
 320
 321       /* free item popped from pqueue */
 322       xbt_free(v_id);
 323     }
 324
 325     xbt_free(cost_arr);
 326     xbt_heap_free(pqueue);
 327   }
 328
 329   /* compose route path with links */
 330   RoutingEdge *gw_src = NULL, *gw_dst, *prev_gw_src, *first_gw = NULL;
 331   RoutingEdge *gw_dst_net_elm = NULL, *prev_gw_src_net_elm = NULL;
 332
 333   for (v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
 334     xbt_node_t node_pred_v =
 335         xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
 336     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
 337     xbt_edge_t edge =
 338         xbt_graph_get_edge(p_routeGraph, node_pred_v, node_v);
 339
 340     if (edge == NULL)
 341       THROWF(arg_error, 0, "No route from '%s' to '%s'", src->getName(), dst->getName());
 342
 343     prev_gw_src = gw_src;
 344
 345     e_route = (sg_platf_route_cbarg_t) xbt_graph_edge_get_data(edge);
 346     gw_src = e_route->gw_src;
 347     gw_dst = e_route->gw_dst;
 348
 349     if (v == dst_node_id)
 350       first_gw = gw_dst;
 351
 352     if (p_hierarchy == SURF_ROUTING_RECURSIVE && v != dst_node_id
 353         && strcmp(gw_dst->getName(), prev_gw_src->getName())) {
 354       xbt_dynar_t e_route_as_to_as=NULL;
 355
 356       routing_platf->getRouteAndLatency(gw_dst_net_elm, prev_gw_src_net_elm, &e_route_as_to_as, NULL);
 357       if (edge == NULL)
 358         THROWF(arg_error,0,"No route from '%s' to '%s'", src->getName(), dst->getName());
 359       links = e_route_as_to_as;
 360       int pos = 0;
 361       xbt_dynar_foreach(links, cpt, link) {
 362         xbt_dynar_insert_at(route->link_list, pos, &link);
 363         if (lat)
 364           *lat += static_cast<Link*>(link)->getLatency();
 365         pos++;
 366       }
 367     }
 368
 369     links = e_route->link_list;
 370     xbt_dynar_foreach(links, cpt, link) {
 371       xbt_dynar_unshift(route->link_list, &link);
 372       if (lat)
 373         *lat += static_cast<Link*>(link)->getLatency();
 374     }
 375     size++;
 376   }
 377
 378   if (p_hierarchy == SURF_ROUTING_RECURSIVE) {
 379     route->gw_src = gw_src;
 380     route->gw_dst = first_gw;
 381   }
 382
 383   if (m_cached && elm == NULL) {
 384     /* add to predecessor list of the current src-host to cache */
 385     elm = xbt_new0(struct route_cache_element, 1);
 386     elm->pred_arr = pred_arr;
 387     elm->size = size;
 388     xbt_dict_set_ext(p_routeCache, (char *) (&src_id), sizeof(int),
 389         (xbt_set_elm_t) elm, NULL);
 390   }
 391
 392   if (!m_cached)
 393     xbt_free(pred_arr);
 394 }
 395
 396 AsDijkstra::~AsDijkstra()
 397 {
 398   xbt_graph_free_graph(p_routeGraph, &xbt_free_f,
 399       &graph_edge_data_free, &xbt_free_f);
 400   xbt_dict_free(&p_graphNodeMap);
 401   if (m_cached)
 402     xbt_dict_free(&p_routeCache);
 403 }
 404
 405 /* Creation routing model functions */
 406
 407 AsDijkstra::AsDijkstra() : AsGeneric(), m_cached(0) {
 408   p_routeGraph = NULL;
 409   p_graphNodeMap = NULL;
 410   p_routeCache = NULL;
 411 }
 412
 413 AsDijkstra::AsDijkstra(int cached) : AsGeneric(), m_cached(cached)
 414 {
 415   p_routeGraph = NULL;
 416   p_graphNodeMap = NULL;
 417   p_routeCache = NULL;
 418   /*new_component->generic_routing.parse_route = model_dijkstra_both_parse_route;
 419   new_component->generic_routing.parse_ASroute = model_dijkstra_both_parse_route;
 420   new_component->generic_routing.get_route_and_latency = dijkstra_get_route_and_latency;
 421   new_component->generic_routing.get_onelink_routes =
 422       dijkstra_get_onelink_routes;
 423   new_component->generic_routing.get_graph = generic_get_graph;
 424   new_component->generic_routing.finalize = dijkstra_finalize;
 425   new_component->cached = cached;*/
 426 }
 427
 428 void AsDijkstra::end()
 429 {
 430   xbt_node_t node = NULL;
 431   unsigned int cursor2;
 432   xbt_dynar_t nodes = NULL;
 433
 434   /* Create the topology graph */
 435   if(!p_routeGraph)
 436         p_routeGraph = xbt_graph_new_graph(1, NULL);
 437   if(!p_graphNodeMap)
 438     p_graphNodeMap = xbt_dict_new_homogeneous(&graph_node_map_elem_free);
 439
 440   if (m_cached && !p_routeCache)
 441     p_routeCache = xbt_dict_new_homogeneous(&route_cache_elem_free);
 442
 443   /* Add the loopback if needed */
 444   if (routing_platf->p_loopback && p_hierarchy == SURF_ROUTING_BASE)
 445     addLoopback();
 446
 447   /* initialize graph indexes in nodes after graph has been built */
 448   nodes = xbt_graph_get_nodes(p_routeGraph);
 449
 450   xbt_dynar_foreach(nodes, cursor2, node) {
 451     graph_node_data_t data = (graph_node_data_t) xbt_graph_node_get_data(node);
 452     data->graph_id = cursor2;
 453   }
 454
 455 }
 456
 457 void AsDijkstra::parseASroute(sg_platf_route_cbarg_t route)
 458 {
 459   parseRoute(route);
 460 }
 461
 462 void AsDijkstra::parseRoute(sg_platf_route_cbarg_t route)
 463 {
 464   char *src = (char*)(route->src);
 465   char *dst = (char*)(route->dst);
 466
 467   int as_route = 0;
 468   if(!route->gw_dst && !route->gw_src)
 469     XBT_DEBUG("Load Route from \"%s\" to \"%s\"", src, dst);
 470   else{
 471     XBT_DEBUG("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
 472         route->gw_src->getName(), dst, route->gw_dst->getName());
 473     as_route = 1;
 474     if(route->gw_dst->getRcType() == SURF_NETWORK_ELEMENT_NULL)
 475       surf_parse_error("The gw_dst '%s' does not exist!",route->gw_dst->getName());
 476     if(route->gw_src->getRcType() == SURF_NETWORK_ELEMENT_NULL)
 477       surf_parse_error("The gw_src '%s' does not exist!",route->gw_src->getName());
 478   }
 479
 480   RoutingEdge *src_net_elm, *dst_net_elm;
 481
 482   src_net_elm = sg_routing_edge_by_name_or_null(src);
 483   dst_net_elm = sg_routing_edge_by_name_or_null(dst);
 484
 485   xbt_assert(src_net_elm, "Network elements %s not found", src);
 486   xbt_assert(dst_net_elm, "Network elements %s not found", dst);
 487
 488   /* Create the topology graph */
 489   if(!p_routeGraph)
 490     p_routeGraph = xbt_graph_new_graph(1, NULL);
 491   if(!p_graphNodeMap)
 492     p_graphNodeMap = xbt_dict_new_homogeneous(&graph_node_map_elem_free);
 493
 494   if (m_cached && !p_routeCache)
 495     p_routeCache = xbt_dict_new_homogeneous(&route_cache_elem_free);
 496
 497   sg_platf_route_cbarg_t e_route = newExtendedRoute(p_hierarchy, route, 1);
 498   newRoute(src_net_elm->getId(), dst_net_elm->getId(), e_route);
 499
 500   // Symmetrical YES
 501   if ( (route->symmetrical == TRUE && as_route == 0)
 502       || (route->symmetrical == TRUE && as_route == 1)
 503   )
 504   {
 505     if(!route->gw_dst && !route->gw_src)
 506       XBT_DEBUG("Load Route from \"%s\" to \"%s\"", dst, src);
 507     else
 508       XBT_DEBUG("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
 509           route->gw_dst->getName(), src, route->gw_src->getName());
 510
 511     xbt_dynar_t nodes = xbt_graph_get_nodes(p_routeGraph);
 512     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_net_elm->getId(), xbt_node_t);
 513     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_net_elm->getId(), xbt_node_t);
 514     xbt_edge_t edge =
 515         xbt_graph_get_edge(p_routeGraph, node_e_v, node_s_v);
 516
 517     if (edge)
 518       THROWF(arg_error,0,"(AS)Route from '%s' to '%s' already exists",src,dst);
 519
 520     if (route->gw_dst && route->gw_src) {
 521       RoutingEdge *gw_tmp;
 522       gw_tmp = route->gw_src;
 523       route->gw_src = route->gw_dst;
 524       route->gw_dst = gw_tmp;
 525     }
 526     sg_platf_route_cbarg_t link_route_back = newExtendedRoute(p_hierarchy, route, 0);
 527     newRoute(dst_net_elm->getId(), src_net_elm->getId(), link_route_back);
 528   }
 529   xbt_dynar_free(&route->link_list);
 530 }