src/surf/surf_routing_dijkstra.cpp

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