Logo AND Algorithmique Numérique Distribuée

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