1 /* Copyright (c) 2009, 2010. The SimGrid Team.
2 * All rights reserved. */
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. */
10 #include "gras_config.h"
13 #include <pcre.h> /* regular expresion library */
15 #include "surf_private.h"
16 #include "xbt/dynar.h"
18 #include "xbt/config.h"
19 #include "xbt/graph.h"
22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
25 routing_global_t global_routing = NULL;
26 routing_component_t current_routing = NULL;
27 model_type_t current_routing_model = NULL;
29 /* Prototypes of each model */
30 static void* model_full_create(void); /* create structures for full routing model */
31 static void model_full_load(void); /* load parse functions for full routing model */
32 static void model_full_unload(void); /* unload parse functions for full routing model */
33 static void model_full_end(void); /* finalize the creation of full routing model */
35 static void* model_floyd_create(void); /* create structures for floyd routing model */
36 static void model_floyd_load(void); /* load parse functions for floyd routing model */
37 static void model_floyd_unload(void); /* unload parse functions for floyd routing model */
38 static void model_floyd_end(void); /* finalize the creation of floyd routing model */
40 static void* model_dijkstra_both_create(int cached); /* create by calling dijkstra or dijkstracache */
41 static void* model_dijkstra_create(void); /* create structures for dijkstra routing model */
42 static void* model_dijkstracache_create(void); /* create structures for dijkstracache routing model */
43 static void model_dijkstra_both_load(void); /* load parse functions for dijkstra routing model */
44 static void model_dijkstra_both_unload(void); /* unload parse functions for dijkstra routing model */
45 static void model_dijkstra_both_end(void); /* finalize the creation of dijkstra routing model */
47 static void* model_rulebased_create(void); /* create structures for rulebased routing model */
48 static void model_rulebased_load(void); /* load parse functions for rulebased routing model */
49 static void model_rulebased_unload(void); /* unload parse functions for rulebased routing model */
50 static void model_rulebased_end(void); /* finalize the creation of rulebased routing model */
52 static void* model_none_create(void); /* none routing model */
53 static void model_none_load(void); /* none routing model */
54 static void model_none_unload(void); /* none routing model */
55 static void model_none_end(void); /* none routing model */
57 static void routing_full_parse_Scluster(void);/*cluster bypass*/
59 static void parse_Sconfig(void);/*config Tag*/
61 /* this lines are only for replace use like index in the model table */
66 SURF_MODEL_DIJKSTRACACHE,
74 /* must be finish with null and carefull if change de order */
75 struct s_model_type routing_models[] =
76 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)",
77 model_full_create, model_full_load, model_full_unload, model_full_end },
78 {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
79 model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end },
80 {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
81 model_dijkstra_create ,model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
82 {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
83 model_dijkstracache_create, model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
84 {"none", "No routing (usable with Constant network only)",
85 model_none_create, model_none_load, model_none_unload, model_none_end },
87 {"RuleBased", "Rule-Based routing data (...)", model_rulebased_create, model_rulebased_load, model_rulebased_unload, model_rulebased_end },
89 {NULL,NULL,NULL,NULL,NULL,NULL}};
91 /* ************************************************************************** */
92 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
94 static void generic_set_processing_unit(routing_component_t rc, const char* name);
95 static void generic_set_autonomous_system(routing_component_t rc, const char* name);
96 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route);
97 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
98 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
100 /* ************************************************************************** */
101 /* *************** GENERIC BUSINESS METHODS (declarations) ****************** */
103 static xbt_dynar_t generic_get_onelink_routes (routing_component_t rc);
104 static int generic_is_router (routing_component_t rc, const char *name);
105 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst);
107 /* ************************************************************************** */
108 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
110 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order);
111 static void generic_free_route(route_t route);
112 static void generic_free_extended_route(route_extended_t e_route);
113 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element);
114 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element);
115 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst);
117 /* ************************************************************************** */
118 /* **************************** GLOBAL FUNCTIONS **************************** */
120 /* global parse functions */
121 static char* src = NULL; /* temporary store the source name of a route */
122 static char* dst = NULL; /* temporary store the destination name of a route */
123 static char* gw_src = NULL; /* temporary store the gateway source name of a route */
124 static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */
125 static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */
128 * \brief Add a "host" to the network element list
130 static void parse_S_host(char* host_id) {
131 if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
132 xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,host_id),
133 "Reading a host, processing unit \"%s\" already exist",host_id);
134 xbt_assert1(current_routing->set_processing_unit,
135 "no defined method \"set_processing_unit\" in \"%s\"",current_routing->name);
136 (*(current_routing->set_processing_unit))(current_routing,host_id);
137 xbt_dict_set(global_routing->where_network_elements,host_id,(void*)current_routing,NULL);
141 * \brief Add a host to the network element list from XML
143 static void parse_S_host_XML(void)
145 parse_S_host(A_surfxml_host_id);
149 * \brief Add a host to the network element list from lua script
151 static void parse_S_host_lua(char *host_id)
153 parse_S_host(host_id);
160 * \brief Add a "router" to the network element list
162 static void parse_S_router(void) {
163 if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
164 xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_router_id),
165 "Reading a router, processing unit \"%s\" already exist",A_surfxml_router_id);
166 xbt_assert1(current_routing->set_processing_unit,
167 "no defined method \"set_processing_unit\" in \"%s\"",current_routing->name);
168 (*(current_routing->set_processing_unit))(current_routing,A_surfxml_router_id);
169 xbt_dict_set(global_routing->where_network_elements,A_surfxml_router_id,(void*)current_routing,NULL);
171 TRACE_surf_host_declaration (A_surfxml_router_id, 0);
176 * \brief Set the endponints for a route
178 static void parse_S_route_new_and_endpoints(char *src_id,char *dst_id) {
179 if( src != NULL && dst != NULL && link_list != NULL )
180 THROW2(arg_error,0,"Route between %s to %s can not be defined",src_id,dst_id);
183 xbt_assert2(strlen(src)>0||strlen(dst)>0,
184 "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
185 link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
189 * \breif Set the endpoints for a route from XML
191 static void parse_S_route_new_and_endpoints_XML(void)
193 parse_S_route_new_and_endpoints(A_surfxml_route_src,A_surfxml_route_dst);
197 * \breif Set the endpoints for a route from lua
199 static void parse_S_route_new_and_endpoints_lua(char *id_src,char *id_dst)
201 parse_S_route_new_and_endpoints(id_src,id_dst);
205 * \brief Set the endponints and gateways for a ASroute
207 static void parse_S_ASroute_new_and_endpoints(void) {
208 if( src != NULL && dst != NULL && link_list != NULL )
209 THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_ASroute_src,A_surfxml_ASroute_dst);
210 src = A_surfxml_ASroute_src;
211 dst = A_surfxml_ASroute_dst;
212 gw_src = A_surfxml_ASroute_gw_src;
213 gw_dst = A_surfxml_ASroute_gw_dst;
214 xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
215 "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
216 link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
220 * \brief Set the endponints for a bypassRoute
222 static void parse_S_bypassRoute_new_and_endpoints(void) {
223 if( src != NULL && dst != NULL && link_list != NULL )
224 THROW2(arg_error,0,"Bypass Route between %s to %s can not be defined",A_surfxml_bypassRoute_src,A_surfxml_bypassRoute_dst);
225 src = A_surfxml_bypassRoute_src;
226 dst = A_surfxml_bypassRoute_dst;
227 gw_src = A_surfxml_bypassRoute_gw_src;
228 gw_dst = A_surfxml_bypassRoute_gw_dst;
229 xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
230 "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
231 link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
235 * \brief Set a new link on the actual list of link for a route or ASroute
237 static void parse_E_link_ctn_new_elem(char *link_id) {
239 val = xbt_strdup(link_id);
240 xbt_dynar_push(link_list, &val);
244 * \brief Set a new link on the actual list of link for a route or ASroute from XML
247 static void parse_E_link_ctn_new_elem_XML(void)
249 parse_E_link_ctn_new_elem(A_surfxml_link_ctn_id);
253 * \brief Set a new link on the actual list of link for a route or ASroute from lua
255 static void parse_E_link_c_ctn_new_elem_lua(char *link_id) {
257 parse_E_link_ctn_new_elem(link_id);
261 * \brief Store the route by calling the set_route function of the current routing component
263 static void parse_E_route_store_route(void) {
264 route_t route = xbt_new0(s_route_t,1);
265 route->link_list = link_list;
266 // xbt_assert1(generic_processing_units_exist(current_routing,src),"the \"%s\" processing units gateway does not exist",src);
267 // xbt_assert1(generic_processing_units_exist(current_routing,dst),"the \"%s\" processing units gateway does not exist",dst);
268 xbt_assert1(current_routing->set_route,"no defined method \"set_route\" in \"%s\"",current_routing->name);
269 (*(current_routing->set_route))(current_routing,src,dst,route);
276 * \brief Store the ASroute by calling the set_ASroute function of the current routing component
278 static void parse_E_ASroute_store_route(void) {
279 route_extended_t e_route = xbt_new0(s_route_extended_t,1);
280 e_route->generic_route.link_list = link_list;
281 e_route->src_gateway = xbt_strdup(gw_src);
282 e_route->dst_gateway = xbt_strdup(gw_dst);
283 // xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
284 // xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
285 // xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
286 // xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
287 xbt_assert1(current_routing->set_ASroute,"no defined method \"set_ASroute\" in \"%s\"",current_routing->name);
288 (*(current_routing->set_ASroute))(current_routing,src,dst,e_route);
297 * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
299 static void parse_E_bypassRoute_store_route(void) {
300 route_extended_t e_route = xbt_new0(s_route_extended_t,1);
301 e_route->generic_route.link_list = link_list;
302 e_route->src_gateway = xbt_strdup(gw_src);
303 e_route->dst_gateway = xbt_strdup(gw_dst);
304 // xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
305 // xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
306 // xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
307 // xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
308 xbt_assert1(current_routing->set_bypassroute,"no defined method \"set_bypassroute\" in \"%s\"",current_routing->name);
309 (*(current_routing->set_bypassroute))(current_routing,src,dst,e_route);
318 * \brief Make a new routing component
320 * make the new structure and
321 * set the parsing functions to allows parsing the part of the routing tree
323 static void parse_S_AS(char* AS_id,char* AS_routing) {
324 routing_component_t new_routing;
325 model_type_t model = NULL;
326 char* wanted = AS_routing;
328 /* seach the routing model */
329 for (cpt=0;routing_models[cpt].name;cpt++)
330 if (!strcmp(wanted,routing_models[cpt].name))
331 model = &routing_models[cpt];
332 /* if its not exist, error */
333 if( model == NULL ) {
334 fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
335 for (cpt=0;routing_models[cpt].name;cpt++)
336 if (!strcmp(wanted,routing_models[cpt].name))
337 fprintf(stderr," %s: %s\n",routing_models[cpt].name,routing_models[cpt].desc);
341 /* make a new routing component */
342 new_routing = (routing_component_t)(*(model->create))();
343 new_routing->routing = model;
344 new_routing->hierarchy = SURF_ROUTING_NULL;
345 new_routing->name = xbt_strdup(AS_id);
346 new_routing->routing_sons = xbt_dict_new();
347 //INFO2("Routing %s for AS %s",A_surfxml_AS_routing,A_surfxml_AS_id);
349 if( current_routing == NULL && global_routing->root == NULL ){
351 /* it is the first one */
352 new_routing->routing_father = NULL;
353 global_routing->root = new_routing;
355 } else if( current_routing != NULL && global_routing->root != NULL ) {
357 xbt_assert1(!xbt_dict_get_or_null(current_routing->routing_sons,AS_id),
358 "The AS \"%s\" already exist",AS_id);
359 /* it is a part of the tree */
360 new_routing->routing_father = current_routing;
361 /* set the father behavior */
362 if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
363 /* add to the sons dictionary */
364 xbt_dict_set(current_routing->routing_sons,AS_id,(void*)new_routing,NULL);
365 /* add to the father element list */
366 (*(current_routing->set_autonomous_system))(current_routing,AS_id);
367 /* unload the prev parse rules */
368 (*(current_routing->routing->unload))();
371 THROW0(arg_error,0,"All defined components must be belong to a AS");
373 /* set the new parse rules */
374 (*(new_routing->routing->load))();
375 /* set the new current component of the tree */
376 current_routing = new_routing;
380 * Detect the routing model type of the routing component from XML platforms
382 static void parse_S_AS_XML(void)
384 parse_S_AS(A_surfxml_AS_id,A_surfxml_AS_routing);
388 * define the routing model type of routing component from lua script
390 static void parse_S_AS_lua(char* id,char* mode)
397 * \brief Finish the creation of a new routing component
399 * When you finish to read the routing component, other structures must be created.
400 * the "end" method allow to do that for any routing model type
402 static void parse_E_AS(char *AS_id) {
404 if( current_routing == NULL ) {
405 THROW1(arg_error,0,"Close AS(%s), that never open",AS_id);
407 xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,current_routing->name),
408 "The AS \"%s\" already exist",current_routing->name);
409 xbt_dict_set(global_routing->where_network_elements,current_routing->name,current_routing->routing_father,NULL);
410 (*(current_routing->routing->unload))();
411 (*(current_routing->routing->end))();
412 current_routing = current_routing->routing_father;
413 if( current_routing != NULL )
414 (*(current_routing->routing->load))();
419 * \brief Finish the creation of a new routing component from XML
421 static void parse_E_AS_XML(void)
423 parse_E_AS(A_surfxml_AS_id);
427 * \brief Finish the creation of a new routing component from lua
429 static void parse_E_AS_lua(char *id)
434 /* Aux Business methods */
437 * \brief Get the AS father and the first elements of the chain
439 * \param src the source host name
440 * \param dst the destination host name
442 * Get the common father of the to processing units, and the first different
443 * father in the chain
445 static xbt_dynar_t elements_father(const char* src,const char* dst) {
447 xbt_assert0(src&&dst,"bad parameters for \"elements_father\" method");
449 xbt_dynar_t result = xbt_dynar_new(sizeof(char*), NULL);
451 routing_component_t src_as, dst_as;
452 int index_src, index_dst, index_father_src, index_father_dst;
453 xbt_dynar_t path_src = NULL;
454 xbt_dynar_t path_dst = NULL;
455 routing_component_t current = NULL;
456 routing_component_t* current_src = NULL;
457 routing_component_t* current_dst = NULL;
458 routing_component_t* father = NULL;
460 /* (1) find the as where the src and dst are located */
461 src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
462 dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
463 xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
465 /* (2) find the path to the root routing component */
466 path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
468 while( current != NULL ) {
469 xbt_dynar_push(path_src,¤t);
470 current = current->routing_father;
472 path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
474 while( current != NULL ) {
475 xbt_dynar_push(path_dst,¤t);
476 current = current->routing_father;
479 /* (3) find the common father */
480 index_src = (path_src->used)-1;
481 index_dst = (path_dst->used)-1;
482 current_src = xbt_dynar_get_ptr(path_src,index_src);
483 current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
484 while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
485 current_src = xbt_dynar_get_ptr(path_src,index_src);
486 current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
492 current_src = xbt_dynar_get_ptr(path_src,index_src);
493 current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
495 /* (4) they are not in the same routing component, make the path */
496 index_father_src = index_src+1;
497 index_father_dst = index_dst+1;
499 if(*current_src==*current_dst)
500 father = current_src;
502 father = xbt_dynar_get_ptr(path_src,index_father_src);
504 /* (5) result generation */
505 xbt_dynar_push(result,father); /* first same the father of src and dst */
506 xbt_dynar_push(result,current_src); /* second the first different father of src */
507 xbt_dynar_push(result,current_dst); /* three the first different father of dst */
509 xbt_dynar_free(&path_src);
510 xbt_dynar_free(&path_dst);
515 /* Global Business methods */
518 * \brief Recursive function for get_route
520 * \param src the source host name
521 * \param dst the destination host name
523 * This fuction is call by "get_route". It allow to walk through the
524 * routing components tree.
526 static route_extended_t _get_route(const char* src,const char* dst) {
531 DEBUG2("Solve route \"%s\" to \"%s\"",src,dst);
533 xbt_assert0(src&&dst,"bad parameters for \"_get_route\" method");
535 route_extended_t e_route, e_route_cnt, e_route_src=NULL, e_route_dst=NULL;
537 xbt_dynar_t elem_father_list = elements_father(src,dst);
539 routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
540 routing_component_t src_father = xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
541 routing_component_t dst_father = xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
543 e_route = xbt_new0(s_route_extended_t,1);
544 e_route->src_gateway = NULL;
545 e_route->dst_gateway = NULL;
546 e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
548 if(src_father==dst_father) { /* SURF_ROUTING_BASE */
550 if( strcmp(src,dst) ){
551 e_route_cnt = (*(common_father->get_route))(common_father,src,dst);
552 xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src,dst);
553 xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
554 xbt_dynar_push(e_route->generic_route.link_list,&link);
556 generic_free_extended_route(e_route_cnt);
559 } else { /* SURF_ROUTING_RECURSIVE */
561 route_extended_t e_route_bypass = NULL;
563 if(common_father->get_bypass_route)
564 e_route_bypass = (*(common_father->get_bypass_route))(common_father,src,dst);
567 e_route_cnt = e_route_bypass;
569 e_route_cnt = (*(common_father->get_route))(common_father,src_father->name,dst_father->name);
571 xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src_father->name,dst_father->name);
573 xbt_assert2( (e_route_cnt->src_gateway==NULL) == (e_route_cnt->dst_gateway==NULL) ,
574 "bad gateway for route between \"%s\" and \"%s\"",src,dst);
576 if( src != e_route_cnt->src_gateway ) {
577 e_route_src = _get_route(src,e_route_cnt->src_gateway);
578 xbt_assert2(e_route_src,"no route between \"%s\" and \"%s\"",src,e_route_cnt->src_gateway);
579 xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
580 xbt_dynar_push(e_route->generic_route.link_list,&link);
584 xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
585 xbt_dynar_push(e_route->generic_route.link_list,&link);
588 if( e_route_cnt->dst_gateway != dst ) {
589 e_route_dst = _get_route(e_route_cnt->dst_gateway,dst);
590 xbt_assert2(e_route_dst,"no route between \"%s\" and \"%s\"",e_route_cnt->dst_gateway,dst);
591 xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
592 xbt_dynar_push(e_route->generic_route.link_list,&link);
596 e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway);
597 e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway);
599 generic_free_extended_route(e_route_src);
600 generic_free_extended_route(e_route_cnt);
601 generic_free_extended_route(e_route_dst);
604 xbt_dynar_free(&elem_father_list);
610 * \brief Generic method: find a route between hosts
612 * \param src the source host name
613 * \param dst the destination host name
615 * walk through the routing components tree and find a route between hosts
616 * by calling the differents "get_route" functions in each routing component
618 static xbt_dynar_t get_route(const char* src,const char* dst) {
620 route_extended_t e_route;
621 xbt_dynar_t elem_father_list = elements_father(src,dst);
622 routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
625 e_route = _get_route(src,dst);
627 e_route = (*(common_father->get_route))(common_father,src,dst);
629 xbt_assert2(e_route,"no route between \"%s\" and \"%s\"",src,dst);
631 if(global_routing->last_route) xbt_dynar_free( &(global_routing->last_route) );
632 global_routing->last_route = e_route->generic_route.link_list;
634 if(e_route->src_gateway) xbt_free(e_route->src_gateway);
635 if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
638 xbt_dynar_free(&elem_father_list);
640 if( xbt_dynar_length(global_routing->last_route)==0 )
643 return global_routing->last_route;
647 * \brief Recursive function for finalize
649 * \param rc the source host name
651 * This fuction is call by "finalize". It allow to finalize the
652 * AS or routing components. It delete all the structures.
654 static void _finalize(routing_component_t rc) {
656 xbt_dict_cursor_t cursor = NULL;
658 routing_component_t elem;
659 xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
662 xbt_dict_t tmp_sons = rc->routing_sons;
663 char* tmp_name = rc->name;
664 xbt_dict_free(&tmp_sons);
666 xbt_assert1(rc->finalize,"no defined method \"finalize\" in \"%s\"",current_routing->name);
667 (*(rc->finalize))(rc);
672 * \brief Generic method: delete all the routing structures
674 * walk through the routing components tree and delete the structures
675 * by calling the differents "finalize" functions in each routing component
677 static void finalize(void) {
678 /* delete recursibly all the tree */
679 _finalize(global_routing->root);
680 /* delete "where" dict */
681 xbt_dict_free(&(global_routing->where_network_elements));
682 /* delete last_route */
683 xbt_dynar_free(&(global_routing->last_route));
684 /* delete global routing structure */
685 xbt_free(global_routing);
688 static xbt_dynar_t recursive_get_onelink_routes (routing_component_t rc)
690 xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
692 //adding my one link routes
695 xbt_dynar_t onelink_mine = rc->get_onelink_routes (rc);
697 xbt_dynar_foreach(onelink_mine, cpt, link) {
698 xbt_dynar_push(ret,&link);
704 xbt_dict_cursor_t cursor=NULL;
705 routing_component_t rc_child;
706 xbt_dict_foreach(rc->routing_sons, cursor, key, rc_child) {
707 xbt_dynar_t onelink_child = recursive_get_onelink_routes (rc_child);
709 xbt_dynar_foreach(onelink_child, cpt, link) {
710 xbt_dynar_push(ret,&link);
717 static xbt_dynar_t get_onelink_routes(void)
719 return recursive_get_onelink_routes (global_routing->root);
722 static int is_router(const char *name)
724 routing_component_t rc=NULL;
725 rc = xbt_dict_get(global_routing->where_network_elements,name);
726 return rc->is_router(rc, name);
730 * \brief Generic method: create the global routing schema
732 * Make a global routing structure and set all the parsing functions.
734 void routing_model_create(size_t size_of_links, void* loopback) {
736 /* config the uniq global routing */
737 global_routing = xbt_new0(s_routing_global_t,1);
738 global_routing->where_network_elements = xbt_dict_new();
739 global_routing->root = NULL;
740 global_routing->get_route = get_route;
741 global_routing->get_onelink_routes = get_onelink_routes;
742 global_routing->is_router = is_router;
743 global_routing->finalize = finalize;
744 global_routing->loopback = loopback;
745 global_routing->size_of_link = size_of_links;
746 global_routing->last_route = xbt_dynar_new(size_of_links, NULL);
748 /* no current routing at moment */
749 current_routing = NULL;
751 /* parse generic elements */
752 surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host_XML);
753 surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
755 surfxml_add_callback(STag_surfxml_route_cb_list, &parse_S_route_new_and_endpoints_XML);
756 surfxml_add_callback(STag_surfxml_ASroute_cb_list, &parse_S_ASroute_new_and_endpoints);
757 surfxml_add_callback(STag_surfxml_bypassRoute_cb_list, &parse_S_bypassRoute_new_and_endpoints);
759 surfxml_add_callback(ETag_surfxml_link_ctn_cb_list, &parse_E_link_ctn_new_elem_XML);
761 surfxml_add_callback(ETag_surfxml_route_cb_list, &parse_E_route_store_route);
762 surfxml_add_callback(ETag_surfxml_ASroute_cb_list, &parse_E_ASroute_store_route);
763 surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list, &parse_E_bypassRoute_store_route);
765 surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS_XML);
766 surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS_XML);
768 surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
770 surfxml_add_callback(STag_surfxml_config_cb_list, &parse_Sconfig);
773 /* ************************************************************************** */
774 /* *************************** FULL ROUTING ********************************* */
776 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
778 /* Routing model structure */
781 s_routing_component_t generic_routing;
782 xbt_dict_t parse_routes; /* store data during the parse process */
783 xbt_dict_t to_index; /* char* -> network_element_t */
784 xbt_dict_t bypassRoutes;
785 route_extended_t *routing_table;
786 } s_routing_component_full_t,*routing_component_full_t;
788 /* Business methods */
789 static xbt_dynar_t full_get_onelink_routes(routing_component_t rc)
791 xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
793 routing_component_full_t routing = (routing_component_full_t)rc;
794 int table_size = xbt_dict_length(routing->to_index);
795 xbt_dict_cursor_t c1 = NULL, c2 = NULL;
796 char *k1, *d1, *k2, *d2;
797 xbt_dict_foreach(routing->to_index, c1, k1, d1) {
798 xbt_dict_foreach (routing->to_index, c2, k2, d2) {
799 int *src_id = xbt_dict_get_or_null(routing->to_index, k1);
800 int *dst_id = xbt_dict_get_or_null(routing->to_index, k2);
801 xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
802 route_extended_t route = TO_ROUTE_FULL(*src_id,*dst_id);
804 if (xbt_dynar_length(route->generic_route.link_list) == 1){
805 void *link = *(void**)xbt_dynar_get_ptr(route->generic_route.link_list,0);
807 onelink_t onelink = xbt_new0 (s_onelink_t, 1);
808 onelink->src = xbt_strdup (k1);
809 onelink->dst = xbt_strdup (k2);
810 onelink->link_ptr = link;
811 xbt_dynar_push (ret, &onelink);
819 static int full_is_router(routing_component_t rc, const char *name)
821 routing_component_full_t routing = (routing_component_full_t)rc;
823 if(SURF_NETWORK_ELEMENT_ROUTER == ( (network_element_t) xbt_dict_get(routing->to_index , name) )->type )
829 static route_extended_t full_get_route(routing_component_t rc, const char* src,const char* dst) {
830 xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
833 routing_component_full_t routing = (routing_component_full_t)rc;
834 int table_size = xbt_dict_length(routing->to_index);
836 generic_src_dst_check(rc,src,dst);
837 int *src_id = xbt_dict_get_or_null(routing->to_index,src);
838 int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
839 xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
841 route_extended_t e_route = NULL;
842 route_extended_t new_e_route = NULL;
846 e_route = TO_ROUTE_FULL(*src_id,*dst_id);
849 new_e_route = xbt_new0(s_route_extended_t,1);
850 new_e_route->src_gateway = xbt_strdup(e_route->src_gateway);
851 new_e_route->dst_gateway = xbt_strdup(e_route->dst_gateway);
852 new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
853 xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
854 xbt_dynar_push(new_e_route->generic_route.link_list,&link);
860 static void full_finalize(routing_component_t rc) {
861 routing_component_full_t routing = (routing_component_full_t)rc;
862 int table_size = xbt_dict_length(routing->to_index);
865 /* Delete routing table */
866 for (i=0;i<table_size;i++)
867 for (j=0;j<table_size;j++)
868 generic_free_extended_route(TO_ROUTE_FULL(i,j));
869 xbt_free(routing->routing_table);
870 /* Delete bypass dict */
871 xbt_dict_free(&routing->bypassRoutes);
872 /* Delete index dict */
873 xbt_dict_free(&(routing->to_index));
874 /* Delete structure */
879 /* Creation routing model functions */
881 static void* model_full_create(void) {
882 routing_component_full_t new_component = xbt_new0(s_routing_component_full_t,1);
883 new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
884 new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
885 new_component->generic_routing.set_route = generic_set_route;
886 new_component->generic_routing.set_ASroute = generic_set_ASroute;
887 new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
888 new_component->generic_routing.get_route = full_get_route;
889 new_component->generic_routing.get_onelink_routes = full_get_onelink_routes;
890 new_component->generic_routing.is_router = full_is_router;
891 new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
892 new_component->generic_routing.finalize = full_finalize;
893 new_component->to_index = xbt_dict_new();
894 new_component->bypassRoutes = xbt_dict_new();
895 new_component->parse_routes = xbt_dict_new();
896 return new_component;
899 static void model_full_load(void) {
900 /* use "surfxml_add_callback" to add a parse function call */
903 static void model_full_unload(void) {
904 /* use "surfxml_del_callback" to remove a parse function call */
907 static void model_full_end(void) {
910 const char* sep = "#";
914 route_extended_t e_route;
917 xbt_dict_cursor_t cursor = NULL;
918 xbt_dynar_t keys = NULL;
921 routing_component_full_t routing = ((routing_component_full_t)current_routing);
922 int table_size = xbt_dict_length(routing->to_index);
924 /* Create the routing table */
925 routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
927 /* Put the routes in position */
928 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
929 keys = xbt_str_split_str(key, sep);
930 src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
931 dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
932 TO_ROUTE_FULL(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,1);
933 xbt_dynar_free(&keys);
936 /* delete the parse table */
937 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
938 route = (route_t)data;
939 xbt_dynar_free(&(route->link_list));
943 /* delete parse dict */
944 xbt_dict_free(&(routing->parse_routes));
946 /* Add the loopback if needed */
947 if(current_routing->hierarchy == SURF_ROUTING_BASE) {
948 for (i = 0; i < table_size; i++) {
949 e_route = TO_ROUTE_FULL(i, i);
951 e_route = xbt_new0(s_route_extended_t,1);
952 e_route->src_gateway = NULL;
953 e_route->dst_gateway = NULL;
954 e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
955 xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
956 TO_ROUTE_FULL(i, i) = e_route;
961 /* Shrink the dynar routes (save unused slots) */
962 for (i=0;i<table_size;i++)
963 for (j=0;j<table_size;j++)
964 if(TO_ROUTE_FULL(i,j))
965 xbt_dynar_shrink(TO_ROUTE_FULL(i,j)->generic_route.link_list,0);
968 /* ************************************************************************** */
969 /* *************************** FLOYD ROUTING ******************************** */
971 #define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size]
972 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
973 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
975 /* Routing model structure */
978 s_routing_component_t generic_routing;
979 /* vars for calculate the floyd algorith. */
980 int *predecessor_table;
981 route_extended_t *link_table; /* char* -> int* */
983 xbt_dict_t bypassRoutes;
984 /* store data during the parse process */
985 xbt_dict_t parse_routes;
986 } s_routing_component_floyd_t,*routing_component_floyd_t;
988 static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst);
990 /* Business methods */
991 static xbt_dynar_t floyd_get_onelink_routes(routing_component_t rc)
993 xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
995 routing_component_floyd_t routing = (routing_component_floyd_t)rc;
996 //int table_size = xbt_dict_length(routing->to_index);
997 xbt_dict_cursor_t c1 = NULL, c2 = NULL;
998 char *k1, *d1, *k2, *d2;
999 xbt_dict_foreach(routing->to_index, c1, k1, d1) {
1000 xbt_dict_foreach (routing->to_index, c2, k2, d2) {
1001 route_extended_t route = floyd_get_route (rc, k1, k2);
1003 if (xbt_dynar_length(route->generic_route.link_list) == 1){
1004 void *link = *(void**)xbt_dynar_get_ptr(route->generic_route.link_list,0);
1005 onelink_t onelink = xbt_new0 (s_onelink_t, 1);
1006 onelink->src = xbt_strdup (k1);
1007 onelink->dst = xbt_strdup (k2);
1008 onelink->link_ptr = link;
1009 xbt_dynar_push (ret, &onelink);
1017 static int floyd_is_router(routing_component_t rc, const char *name)
1019 routing_component_floyd_t routing = (routing_component_floyd_t)rc;
1021 if(SURF_NETWORK_ELEMENT_ROUTER == ( (network_element_t) xbt_dict_get(routing->to_index , name) )->type )
1027 static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) {
1028 xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1030 /* set utils vars */
1031 routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1032 int table_size = xbt_dict_length(routing->to_index);
1034 generic_src_dst_check(rc,src,dst);
1035 int *src_id = xbt_dict_get_or_null(routing->to_index,src);
1036 int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
1037 xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
1039 /* create a result route */
1040 route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
1041 new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1042 new_e_route->src_gateway = NULL;
1043 new_e_route->dst_gateway = NULL;
1048 char *gw_src=NULL,*gw_dst=NULL, *prev_gw_src,*prev_gw_dst, *first_gw=NULL;
1055 pred = TO_FLOYD_PRED(*src_id, pred);
1056 if(pred == -1) /* if no pred in route -> no route to host */
1058 xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst);
1060 prev_gw_src = gw_src;
1061 prev_gw_dst = gw_dst;
1063 route_extended_t e_route = TO_FLOYD_LINK(pred,prev_pred);
1064 gw_src = e_route->src_gateway;
1065 gw_dst = e_route->dst_gateway;
1067 if(first) first_gw = gw_dst;
1069 if(rc->hierarchy == SURF_ROUTING_RECURSIVE && !first && strcmp(gw_dst,prev_gw_src)) {
1070 xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
1071 xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
1072 links = e_route_as_to_as;
1074 xbt_dynar_foreach(links, cpt, link) {
1075 xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
1080 links = e_route->generic_route.link_list;
1081 xbt_dynar_foreach(links, cpt, link) {
1082 xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1086 } while(pred != *src_id);
1087 xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", *src_id, *dst_id,src,dst);
1089 if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1090 new_e_route->src_gateway = xbt_strdup(gw_src);
1091 new_e_route->dst_gateway = xbt_strdup(first_gw);
1097 static void floyd_finalize(routing_component_t rc) {
1098 routing_component_floyd_t routing = (routing_component_floyd_t)rc;
1101 table_size = xbt_dict_length(routing->to_index);
1102 /* Delete link_table */
1103 for (i=0;i<table_size;i++)
1104 for (j=0;j<table_size;j++)
1105 generic_free_extended_route(TO_FLOYD_LINK(i,j));
1106 xbt_free(routing->link_table);
1107 /* Delete bypass dict */
1108 xbt_dict_free(&routing->bypassRoutes);
1109 /* Delete index dict */
1110 xbt_dict_free(&(routing->to_index));
1111 /* Delete dictionary index dict, predecessor and links table */
1112 xbt_free(routing->predecessor_table);
1113 /* Delete structure */
1118 static void* model_floyd_create(void) {
1119 routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1);
1120 new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
1121 new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
1122 new_component->generic_routing.set_route = generic_set_route;
1123 new_component->generic_routing.set_ASroute = generic_set_ASroute;
1124 new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1125 new_component->generic_routing.get_route = floyd_get_route;
1126 new_component->generic_routing.get_onelink_routes = floyd_get_onelink_routes;
1127 new_component->generic_routing.is_router = floyd_is_router;
1128 new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
1129 new_component->generic_routing.finalize = floyd_finalize;
1130 new_component->to_index = xbt_dict_new();
1131 new_component->bypassRoutes = xbt_dict_new();
1132 new_component->parse_routes = xbt_dict_new();
1133 return new_component;
1136 static void model_floyd_load(void) {
1137 /* use "surfxml_add_callback" to add a parse function call */
1140 static void model_floyd_unload(void) {
1141 /* use "surfxml_del_callback" to remove a parse function call */
1144 static void model_floyd_end(void) {
1146 routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
1147 xbt_dict_cursor_t cursor = NULL;
1148 double * cost_table;
1149 char *key,*data, *end;
1150 const char *sep = "#";
1153 unsigned int i,j,a,b,c;
1155 /* set the size of inicial table */
1156 int table_size = xbt_dict_length(routing->to_index);
1158 /* Create Cost, Predecessor and Link tables */
1159 cost_table = xbt_new0(double, table_size*table_size); /* link cost from host to host */
1160 routing->predecessor_table = xbt_new0(int, table_size*table_size); /* predecessor host numbers */
1161 routing->link_table = xbt_new0(route_extended_t, table_size*table_size); /* actual link between src and dst */
1163 /* Initialize costs and predecessors*/
1164 for(i = 0; i<table_size;i++)
1165 for(j = 0; j<table_size;j++) {
1166 TO_FLOYD_COST(i,j) = DBL_MAX;
1167 TO_FLOYD_PRED(i,j) = -1;
1168 TO_FLOYD_LINK(i,j) = NULL; /* fixed, missing in the previous version */
1171 /* Put the routes in position */
1172 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1173 keys = xbt_str_split_str(key, sep);
1174 src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
1175 dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
1176 TO_FLOYD_LINK(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,0);
1177 TO_FLOYD_PRED(src_id,dst_id) = src_id;
1179 TO_FLOYD_COST(src_id,dst_id) = ((TO_FLOYD_LINK(src_id,dst_id))->generic_route.link_list)->used; /* count of links, old model assume 1 */
1180 xbt_dynar_free(&keys);
1183 /* Add the loopback if needed */
1184 if(current_routing->hierarchy == SURF_ROUTING_BASE) {
1185 for (i = 0; i < table_size; i++) {
1186 route_extended_t e_route = TO_FLOYD_LINK(i, i);
1188 e_route = xbt_new0(s_route_extended_t,1);
1189 e_route->src_gateway = NULL;
1190 e_route->dst_gateway = NULL;
1191 e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1192 xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1193 TO_FLOYD_LINK(i,i) = e_route;
1194 TO_FLOYD_PRED(i,i) = i;
1195 TO_FLOYD_COST(i,i) = 1;
1199 /* Calculate path costs */
1200 for(c=0;c<table_size;c++) {
1201 for(a=0;a<table_size;a++) {
1202 for(b=0;b<table_size;b++) {
1203 if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
1204 if(TO_FLOYD_COST(a,b) == DBL_MAX ||
1205 (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
1206 TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
1207 TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
1214 /* delete the parse table */
1215 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1216 route_t route = (route_t)data;
1217 xbt_dynar_free(&(route->link_list));
1221 /* delete parse dict */
1222 xbt_dict_free(&(routing->parse_routes));
1225 xbt_free(cost_table);
1228 /* ************************************************************************** */
1229 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1232 s_routing_component_t generic_routing;
1233 xbt_dict_t to_index;
1234 xbt_dict_t bypassRoutes;
1235 xbt_graph_t route_graph; /* xbt_graph */
1236 xbt_dict_t graph_node_map; /* map */
1237 xbt_dict_t route_cache; /* use in cache mode */
1239 xbt_dict_t parse_routes;
1240 } s_routing_component_dijkstra_t,*routing_component_dijkstra_t;
1243 typedef struct graph_node_data {
1245 int graph_id; /* used for caching internal graph id's */
1246 } s_graph_node_data_t, * graph_node_data_t;
1248 typedef struct graph_node_map_element {
1250 } s_graph_node_map_element_t, * graph_node_map_element_t;
1252 typedef struct route_cache_element {
1255 } s_route_cache_element_t, * route_cache_element_t;
1257 /* Free functions */
1259 static void route_cache_elem_free(void *e) {
1260 route_cache_element_t elm=(route_cache_element_t)e;
1262 xbt_free(elm->pred_arr);
1267 static void graph_node_map_elem_free(void *e) {
1268 graph_node_map_element_t elm = (graph_node_map_element_t)e;
1274 static void graph_edge_data_free(void *e) {
1275 route_extended_t e_route = (route_extended_t)e;
1277 xbt_dynar_free(&(e_route->generic_route.link_list));
1278 if(e_route->src_gateway) xbt_free(e_route->src_gateway);
1279 if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
1284 /* Utility functions */
1286 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) {
1287 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1288 xbt_node_t node = NULL;
1289 graph_node_data_t data = NULL;
1290 graph_node_map_element_t elm = NULL;
1292 data = xbt_new0(struct graph_node_data, 1);
1294 data->graph_id = graph_id;
1295 node = xbt_graph_new_node(routing->route_graph, data);
1297 elm = xbt_new0(struct graph_node_map_element, 1);
1299 xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
1304 static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) {
1305 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1306 graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
1312 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route ) {
1313 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1315 xbt_node_t src = NULL;
1316 xbt_node_t dst = NULL;
1317 graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
1318 graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
1321 src = src_elm->node;
1324 dst = dst_elm->node;
1326 /* add nodes if they don't exist in the graph */
1327 if(src_id == dst_id && src == NULL && dst == NULL) {
1328 src = route_graph_new_node(rc,src_id, -1);
1332 src = route_graph_new_node(rc,src_id, -1);
1335 dst = route_graph_new_node(rc,dst_id, -1);
1339 /* add link as edge to graph */
1340 xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1343 static void add_loopback_dijkstra(routing_component_dijkstra_t rc) {
1344 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1346 xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1348 xbt_node_t node = NULL;
1349 unsigned int cursor2;
1350 xbt_dynar_foreach(nodes, cursor2, node) {
1351 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1352 xbt_edge_t edge = NULL;
1353 unsigned int cursor;
1356 xbt_dynar_foreach(out_edges, cursor, edge) {
1357 xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1358 if(other_node == node) {
1365 route_extended_t e_route = xbt_new0(s_route_extended_t,1);
1366 e_route->src_gateway = NULL;
1367 e_route->dst_gateway = NULL;
1368 e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1369 xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1370 xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1375 /* Business methods */
1376 static xbt_dynar_t dijkstra_get_onelink_routes(routing_component_t rc)
1378 xbt_die("\"dijkstra_get_onelink_routes\" function not implemented yet");
1381 static int dijkstra_is_router(routing_component_t rc, const char *name)
1383 routing_component_dijkstra_t routing = (routing_component_dijkstra_t)rc;
1385 if(SURF_NETWORK_ELEMENT_ROUTER == ( (network_element_t) xbt_dict_get(routing->to_index , name) )->type )
1391 static route_extended_t dijkstra_get_route(routing_component_t rc, const char* src,const char* dst) {
1392 xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1394 /* set utils vars */
1395 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1397 generic_src_dst_check(rc,src,dst);
1398 int *src_id = xbt_dict_get_or_null(routing->to_index,src);
1399 int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
1400 xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
1402 /* create a result route */
1403 route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
1404 new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1405 new_e_route->src_gateway = NULL;
1406 new_e_route->dst_gateway = NULL;
1408 int *pred_arr = NULL;
1409 int src_node_id = 0;
1410 int dst_node_id = 0;
1411 int * nodeid = NULL;
1413 route_extended_t e_route;
1417 xbt_dynar_t links = NULL;
1418 route_cache_element_t elm = NULL;
1419 xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1421 /* Use the graph_node id mapping set to quickly find the nodes */
1422 graph_node_map_element_t src_elm = graph_node_map_search(routing,*src_id);
1423 graph_node_map_element_t dst_elm = graph_node_map_search(routing,*dst_id);
1424 xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", *src_id, *dst_id);
1425 src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
1426 dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
1428 /* if the src and dst are the same */ /* fixed, missing in the previous version */
1429 if( src_node_id == dst_node_id ) {
1431 xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1432 xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1433 xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1435 xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1437 e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1439 links = e_route->generic_route.link_list;
1440 xbt_dynar_foreach(links, cpt, link) {
1441 xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1447 if(routing->cached) {
1448 /*check if there is a cached predecessor list avail */
1449 elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
1452 if(elm) { /* cached mode and cache hit */
1453 pred_arr = elm->pred_arr;
1454 } else { /* not cached mode or cache miss */
1455 double * cost_arr = NULL;
1456 xbt_heap_t pqueue = NULL;
1459 int nr_nodes = xbt_dynar_length(nodes);
1460 cost_arr = xbt_new0(double, nr_nodes); /* link cost from src to other hosts */
1461 pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */
1462 pqueue = xbt_heap_new(nr_nodes, xbt_free);
1465 cost_arr[src_node_id] = 0.0;
1467 for(i = 0; i < nr_nodes; i++) {
1468 if(i != src_node_id) {
1469 cost_arr[i] = DBL_MAX;
1474 /* initialize priority queue */
1475 nodeid = xbt_new0(int, 1);
1477 xbt_heap_push(pqueue, nodeid, cost_arr[i]);
1481 /* apply dijkstra using the indexes from the graph's node array */
1482 while(xbt_heap_size(pqueue) > 0) {
1483 int * v_id = xbt_heap_pop(pqueue);
1484 xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
1485 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
1486 xbt_edge_t edge = NULL;
1487 unsigned int cursor;
1489 xbt_dynar_foreach(out_edges, cursor, edge) {
1490 xbt_node_t u_node = xbt_graph_edge_get_target(edge);
1491 graph_node_data_t data = xbt_graph_node_get_data(u_node);
1492 int u_id = data->graph_id;
1493 route_extended_t tmp_e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1494 int cost_v_u = (tmp_e_route->generic_route.link_list)->used; /* count of links, old model assume 1 */
1496 if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
1497 pred_arr[u_id] = *v_id;
1498 cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
1499 nodeid = xbt_new0(int, 1);
1501 xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
1505 /* free item popped from pqueue */
1510 xbt_heap_free(pqueue);
1513 /* compose route path with links */
1514 char *gw_src=NULL,*gw_dst=NULL, *prev_gw_src,*prev_gw_dst, *first_gw=NULL;
1516 for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
1517 xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
1518 xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
1519 xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
1521 xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1523 prev_gw_src = gw_src;
1524 prev_gw_dst = gw_dst;
1526 e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1527 gw_src = e_route->src_gateway;
1528 gw_dst = e_route->dst_gateway;
1530 if(v==dst_node_id) first_gw = gw_dst;
1532 if(rc->hierarchy == SURF_ROUTING_RECURSIVE && v!=dst_node_id && strcmp(gw_dst,prev_gw_src)) {
1533 xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
1534 xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
1535 links = e_route_as_to_as;
1537 xbt_dynar_foreach(links, cpt, link) {
1538 xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
1543 links = e_route->generic_route.link_list;
1544 xbt_dynar_foreach(links, cpt, link) {
1545 xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1550 if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1551 new_e_route->src_gateway = xbt_strdup(gw_src);
1552 new_e_route->dst_gateway = xbt_strdup(first_gw);
1555 if(routing->cached && elm == NULL) {
1556 /* add to predecessor list of the current src-host to cache */
1557 elm = xbt_new0(struct route_cache_element, 1);
1558 elm->pred_arr = pred_arr;
1560 xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
1563 if(!routing->cached)
1569 static void dijkstra_finalize(routing_component_t rc) {
1570 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1573 xbt_graph_free_graph(routing->route_graph, &xbt_free, &graph_edge_data_free, &xbt_free);
1574 xbt_dict_free(&routing->graph_node_map);
1576 xbt_dict_free(&routing->route_cache);
1577 /* Delete bypass dict */
1578 xbt_dict_free(&routing->bypassRoutes);
1579 /* Delete index dict */
1580 xbt_dict_free(&(routing->to_index));
1581 /* Delete structure */
1586 /* Creation routing model functions */
1588 static void* model_dijkstra_both_create(int cached) {
1589 routing_component_dijkstra_t new_component = xbt_new0(s_routing_component_dijkstra_t,1);
1590 new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
1591 new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
1592 new_component->generic_routing.set_route = generic_set_route;
1593 new_component->generic_routing.set_ASroute = generic_set_ASroute;
1594 new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1595 new_component->generic_routing.get_route = dijkstra_get_route;
1596 new_component->generic_routing.get_onelink_routes = dijkstra_get_onelink_routes;
1597 new_component->generic_routing.is_router = dijkstra_is_router;
1598 new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
1599 new_component->generic_routing.finalize = dijkstra_finalize;
1600 new_component->cached = cached;
1601 new_component->to_index = xbt_dict_new();
1602 new_component->bypassRoutes = xbt_dict_new();
1603 new_component->parse_routes = xbt_dict_new();
1604 return new_component;
1607 static void* model_dijkstra_create(void) {
1608 return model_dijkstra_both_create(0);
1611 static void* model_dijkstracache_create(void) {
1612 return model_dijkstra_both_create(1);
1615 static void model_dijkstra_both_load(void) {
1616 /* use "surfxml_add_callback" to add a parse function call */
1619 static void model_dijkstra_both_unload(void) {
1620 /* use "surfxml_del_callback" to remove a parse function call */
1623 static void model_dijkstra_both_end(void) {
1624 routing_component_dijkstra_t routing = (routing_component_dijkstra_t) current_routing;
1625 xbt_dict_cursor_t cursor = NULL;
1626 char *key, *data, *end;
1627 const char *sep = "#";
1629 xbt_node_t node = NULL;
1630 unsigned int cursor2;
1631 xbt_dynar_t nodes = NULL;
1635 /* Create the topology graph */
1636 routing->route_graph = xbt_graph_new_graph(1, NULL);
1637 routing->graph_node_map = xbt_dict_new();
1640 routing->route_cache = xbt_dict_new();
1642 /* Put the routes in position */
1643 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1644 keys = xbt_str_split_str(key, sep);
1645 src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
1646 dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
1647 route_extended_t e_route = generic_new_extended_route(current_routing->hierarchy,data,0);
1648 route_new_dijkstra(routing,src_id,dst_id,e_route);
1649 xbt_dynar_free(&keys);
1652 /* delete the parse table */
1653 xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1654 route = (route_t)data;
1655 xbt_dynar_free(&(route->link_list));
1659 /* delete parse dict */
1660 xbt_dict_free(&(routing->parse_routes));
1662 /* Add the loopback if needed */
1663 if(current_routing->hierarchy == SURF_ROUTING_BASE)
1664 add_loopback_dijkstra(routing);
1666 /* initialize graph indexes in nodes after graph has been built */
1667 nodes = xbt_graph_get_nodes(routing->route_graph);
1669 xbt_dynar_foreach(nodes, cursor2, node) {
1670 graph_node_data_t data = xbt_graph_node_get_data(node);
1671 data->graph_id = cursor2;
1676 #ifdef HAVE_PCRE_LIB
1677 /* ************************************************** */
1678 /* ************** RULE-BASED ROUTING **************** */
1680 /* Routing model structure */
1683 s_routing_component_t generic_routing;
1684 xbt_dict_t dict_processing_units;
1685 xbt_dict_t dict_autonomous_systems;
1686 xbt_dynar_t list_route;
1687 xbt_dynar_t list_ASroute;
1688 } s_routing_component_rulebased_t,*routing_component_rulebased_t;
1690 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
1691 typedef struct s_rule_route_extended s_rule_route_extended_t, *rule_route_extended_t;
1693 struct s_rule_route {
1694 xbt_dynar_t re_str_link; // dynar of char*
1699 struct s_rule_route_extended {
1700 s_rule_route_t generic_rule_route;
1701 char* re_src_gateway;
1702 char* re_dst_gateway;
1705 static void rule_route_free(void *e) {
1706 rule_route_t* elem = (rule_route_t*)(e);
1708 xbt_dynar_free(&(*elem)->re_str_link);
1709 pcre_free((*elem)->re_src);
1710 pcre_free((*elem)->re_dst);
1716 static void rule_route_extended_free(void *e) {
1717 rule_route_extended_t* elem = (rule_route_extended_t*)e;
1719 xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
1720 pcre_free((*elem)->generic_rule_route.re_src);
1721 pcre_free((*elem)->generic_rule_route.re_dst);
1722 xbt_free((*elem)->re_src_gateway);
1723 xbt_free((*elem)->re_dst_gateway);
1728 /* Parse routing model functions */
1730 static void model_rulebased_set_processing_unit(routing_component_t rc, const char* name) {
1731 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1732 xbt_dict_set(routing->dict_processing_units, name, (void*)(-1), NULL);
1735 static void model_rulebased_set_autonomous_system(routing_component_t rc, const char* name) {
1736 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1737 xbt_dict_set(routing->dict_autonomous_systems, name, (void*)(-1), NULL);
1740 static void model_rulebased_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
1741 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1742 rule_route_t ruleroute = xbt_new0(s_rule_route_t,1);
1745 ruleroute->re_src = pcre_compile(src,0,&error,&erroffset,NULL);
1746 xbt_assert3(ruleroute->re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, src, error);
1747 ruleroute->re_dst = pcre_compile(dst,0,&error,&erroffset,NULL);
1748 xbt_assert3(ruleroute->re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, dst, error);
1749 ruleroute->re_str_link = route->link_list;
1750 xbt_dynar_push(routing->list_route,&ruleroute);
1754 static void model_rulebased_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {
1755 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1756 rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t,1);
1759 ruleroute_e->generic_rule_route.re_src = pcre_compile(src,0,&error,&erroffset,NULL);
1760 xbt_assert3(ruleroute_e->generic_rule_route.re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, src, error);
1761 ruleroute_e->generic_rule_route.re_dst = pcre_compile(dst,0,&error,&erroffset,NULL);
1762 xbt_assert3(ruleroute_e->generic_rule_route.re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, dst, error);
1763 ruleroute_e->generic_rule_route.re_str_link = route->generic_route.link_list;
1764 ruleroute_e->re_src_gateway = route->src_gateway;
1765 ruleroute_e->re_dst_gateway = route->dst_gateway;
1766 xbt_dynar_push(routing->list_ASroute,&ruleroute_e);
1767 xbt_free(route->src_gateway);
1768 xbt_free(route->dst_gateway);
1772 static void model_rulebased_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1773 xbt_die("bypass routing not supported for Route-Based model");
1776 #define BUFFER_SIZE 4096 /* result buffer size */
1777 #define OVECCOUNT 30 /* should be a multiple of 3 */
1779 static char* remplace(char* value, const char** src_list, int src_size, const char** dst_list, int dst_size ) {
1781 char result_result[BUFFER_SIZE];
1782 int i_result_buffer;
1783 int value_length = (int)strlen(value);
1787 i_result_buffer = 0;
1789 if( value[i] == '$' ) {
1793 int number_length = 0;
1794 while( '0' <= value[i+number_length] && value[i+number_length] <= '9' ) {
1797 xbt_assert2( number_length!=0, "bad string parameter, no number indication, at offset: %d (\"%s\")",i,value);
1800 number = atoi(value+i);
1802 xbt_assert2(i+2<value_length,"bad string parameter, too few chars, at offset: %d (\"%s\")",i,value);
1804 // solve the indication
1805 const char** param_list;
1807 if( value[i] == 's' && value[i+1] == 'r' && value[i+2] == 'c' ) {
1808 param_list = src_list;
1809 param_size = src_size;
1810 } else if( value[i] == 'd' && value[i+1] == 's' && value[i+2] == 't' ) {
1811 param_list = dst_list;
1812 param_size = dst_size;
1814 xbt_assert2(0,"bad string parameter, support only \"src\" and \"dst\", at offset: %d (\"%s\")",i,value);
1818 xbt_assert4( param_size >= number, "bad string parameter, not enough length param_size, at offset: %d (\"%s\") %d %d",i,value,param_size,number);
1820 const char* param = param_list[number];
1821 int size = strlen(param);
1823 for(cp = 0; cp < size; cp++ ) {
1824 result_result[i_result_buffer] = param[cp];
1826 if( i_result_buffer >= BUFFER_SIZE ) break;
1829 result_result[i_result_buffer] = value[i];
1834 } while(i<value_length && i_result_buffer < BUFFER_SIZE);
1836 xbt_assert2( i_result_buffer < BUFFER_SIZE, "solving string \"%s\", small buffer size (%d)",value,BUFFER_SIZE);
1837 result_result[i_result_buffer] = 0;
1838 return xbt_strdup(result_result);
1841 static xbt_dynar_t rulebased_get_onelink_routes(routing_component_t rc)
1843 xbt_die("\"rulebased_get_onelink_routes\" function not implemented yet");
1846 static int rulebased_is_router(routing_component_t rc, const char *name)
1848 //routing_component_rulebased_t routing = (routing_component_rulebased_t)rc;
1852 xbt_die("\"rulebased_is_router\" function not implemented yet");
1855 /* Business methods */
1856 static route_extended_t rulebased_get_route(routing_component_t rc, const char* src,const char* dst) {
1857 xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1859 /* set utils vars */
1860 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1862 int are_processing_units;
1863 xbt_dynar_t rule_list;
1864 if( xbt_dict_get_or_null(routing->dict_processing_units,src) && xbt_dict_get_or_null(routing->dict_processing_units,dst) ) {
1865 are_processing_units = 1;
1866 rule_list = routing->list_route;
1867 } else if( xbt_dict_get_or_null(routing->dict_autonomous_systems,src) && xbt_dict_get_or_null(routing->dict_autonomous_systems,dst) ) {
1868 are_processing_units = 0;
1869 rule_list = routing->list_ASroute;
1871 xbt_assert2(NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
1875 int src_length = (int)strlen(src);
1876 int dst_length = (int)strlen(dst);
1878 xbt_dynar_t links_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1880 rule_route_t ruleroute;
1882 int ovector_src[OVECCOUNT];
1883 int ovector_dst[OVECCOUNT];
1884 const char** list_src = NULL;
1885 const char** list_dst = NULL;
1886 xbt_dynar_foreach(rule_list, cpt, ruleroute) {
1887 rc_src = pcre_exec(ruleroute->re_src,NULL,src,src_length,0,0,ovector_src,OVECCOUNT);
1889 rc_dst = pcre_exec(ruleroute->re_dst,NULL,dst,dst_length,0,0,ovector_dst,OVECCOUNT);
1891 xbt_assert1(!pcre_get_substring_list(src,ovector_src,rc_src,&list_src),"error solving substring list for src \"%s\"",src);
1892 xbt_assert1(!pcre_get_substring_list(dst,ovector_dst,rc_dst,&list_dst),"error solving substring list for src \"%s\"",dst);
1894 xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
1895 char* new_link_name = remplace(link_name,list_src,rc_src,list_dst,rc_dst);
1896 void* link = xbt_dict_get_or_null(surf_network_model->resource_set, new_link_name);
1898 xbt_dynar_push(links_list,&link);
1900 THROW1(mismatch_error,0,"Link %s not found", new_link_name);
1901 xbt_free(new_link_name);
1905 if( rc_src >= 0 && rc_dst >= 0 ) break;
1908 route_extended_t new_e_route = NULL;
1909 if(rc_src >= 0 && rc_dst >= 0) {
1910 new_e_route = xbt_new0(s_route_extended_t,1);
1911 new_e_route->generic_route.link_list = links_list;
1912 } else if( !strcmp(src,dst) && are_processing_units ) {
1913 new_e_route = xbt_new0(s_route_extended_t,1);
1914 xbt_dynar_push(links_list,&(global_routing->loopback));
1915 new_e_route->generic_route.link_list = links_list;
1917 xbt_dynar_free(&link_list);
1920 if(!are_processing_units && new_e_route)
1922 rule_route_extended_t ruleroute_extended = (rule_route_extended_t)ruleroute;
1923 new_e_route->src_gateway = remplace(ruleroute_extended->re_src_gateway,list_src,rc_src,list_dst,rc_dst);
1924 new_e_route->dst_gateway = remplace(ruleroute_extended->re_dst_gateway,list_src,rc_src,list_dst,rc_dst);
1927 if(list_src) pcre_free_substring_list(list_src);
1928 if(list_dst) pcre_free_substring_list(list_dst);
1933 static route_extended_t rulebased_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {
1937 static void rulebased_finalize(routing_component_t rc) {
1938 routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1940 xbt_dict_free(&routing->dict_processing_units);
1941 xbt_dict_free(&routing->dict_autonomous_systems);
1942 xbt_dynar_free(&routing->list_route);
1943 xbt_dynar_free(&routing->list_ASroute);
1944 /* Delete structure */
1949 /* Creation routing model functions */
1950 static void* model_rulebased_create(void) {
1951 routing_component_rulebased_t new_component = xbt_new0(s_routing_component_rulebased_t,1);
1952 new_component->generic_routing.set_processing_unit = model_rulebased_set_processing_unit;
1953 new_component->generic_routing.set_autonomous_system = model_rulebased_set_autonomous_system;
1954 new_component->generic_routing.set_route = model_rulebased_set_route;
1955 new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
1956 new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
1957 new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
1958 new_component->generic_routing.is_router = rulebased_is_router;
1959 new_component->generic_routing.get_route = rulebased_get_route;
1960 new_component->generic_routing.get_bypass_route = NULL; //rulebased_get_bypass_route;
1961 new_component->generic_routing.finalize = rulebased_finalize;
1962 /* initialization of internal structures */
1963 new_component->dict_processing_units = xbt_dict_new();
1964 new_component->dict_autonomous_systems = xbt_dict_new();
1965 new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
1966 new_component->list_ASroute = xbt_dynar_new(sizeof(rule_route_extended_t), &rule_route_extended_free);
1967 return new_component;
1970 static void model_rulebased_load(void) {
1971 /* use "surfxml_add_callback" to add a parse function call */
1974 static void model_rulebased_unload(void) {
1975 /* use "surfxml_del_callback" to remove a parse function call */
1978 static void model_rulebased_end(void) {
1981 #endif /* HAVE_PCRE_LIB */
1983 /* ************************************************************************** */
1984 /* ******************************* NO ROUTING ******************************* */
1986 /* Routing model structure */
1988 s_routing_component_t generic_routing;
1989 } s_routing_component_none_t,*routing_component_none_t;
1991 /* Business methods */
1992 static xbt_dynar_t none_get_onelink_routes(routing_component_t rc){
1995 static int none_is_router(routing_component_t rc, const char *name){
1998 static route_extended_t none_get_route(routing_component_t rc, const char* src,const char* dst){
2001 static route_extended_t none_get_bypass_route(routing_component_t rc, const char* src,const char* dst){
2004 static void none_finalize(routing_component_t rc) {
2008 static void none_set_processing_unit(routing_component_t rc, const char* name) {}
2009 static void none_set_autonomous_system(routing_component_t rc, const char* name) {}
2011 /* Creation routing model functions */
2012 static void* model_none_create(void) {
2013 routing_component_none_t new_component = xbt_new0(s_routing_component_none_t,1);
2014 new_component->generic_routing.set_processing_unit = none_set_processing_unit;
2015 new_component->generic_routing.set_autonomous_system = none_set_autonomous_system;
2016 new_component->generic_routing.set_route = NULL;
2017 new_component->generic_routing.set_ASroute = NULL;
2018 new_component->generic_routing.set_bypassroute = NULL;
2019 new_component->generic_routing.get_route = none_get_route;
2020 new_component->generic_routing.get_onelink_routes = none_get_onelink_routes;
2021 new_component->generic_routing.is_router = none_is_router;
2022 new_component->generic_routing.get_bypass_route = none_get_bypass_route;
2023 new_component->generic_routing.finalize = none_finalize;
2024 return new_component;
2027 static void model_none_load(void) {}
2028 static void model_none_unload(void) {}
2029 static void model_none_end(void) {}
2031 /* ************************************************** */
2032 /* ********** PATERN FOR NEW ROUTING **************** */
2034 /* The minimal configuration of a new routing model need the next functions,
2035 * also you need to set at the start of the file, the new model in the model
2036 * list. Remember keep the null ending of the list.
2038 /*** Routing model structure ***/
2040 // s_routing_component_t generic_routing;
2041 // /* things that your routing model need */
2042 // } s_routing_component_NEW_t,*routing_component_NEW_t;
2044 /*** Parse routing model functions ***/
2045 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
2046 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
2047 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
2048 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
2049 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
2051 /*** Business methods ***/
2052 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2053 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2054 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
2056 /*** Creation routing model functions ***/
2057 // static void* model_NEW_create(void) {
2058 // routing_component_NEW_t new_component = xbt_new0(s_routing_component_NEW_t,1);
2059 // new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
2060 // new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
2061 // new_component->generic_routing.set_route = model_NEW_set_route;
2062 // new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
2063 // new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
2064 // new_component->generic_routing.get_route = NEW_get_route;
2065 // new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
2066 // new_component->generic_routing.finalize = NEW_finalize;
2067 // /* initialization of internal structures */
2068 // return new_component;
2069 // } /* mandatory */
2070 // static void model_NEW_load(void) {} /* mandatory */
2071 // static void model_NEW_unload(void) {} /* mandatory */
2072 // static void model_NEW_end(void) {} /* mandatory */
2074 /* ************************************************************************** */
2075 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
2077 static void generic_set_processing_unit(routing_component_t rc, const char* name) {
2078 DEBUG1("Load process unit \"%s\"",name);
2079 model_type_t modeltype = rc->routing;
2080 int *id = xbt_new0(int,1);
2081 xbt_dict_t _to_index;
2082 if(modeltype==&routing_models[SURF_MODEL_FULL])
2083 _to_index = ((routing_component_full_t)rc)->to_index;
2085 else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
2086 _to_index = ((routing_component_floyd_t)rc)->to_index;
2088 else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2089 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
2090 _to_index = ((routing_component_dijkstra_t)rc)->to_index;
2092 else xbt_die("\"generic_set_processing_unit\" not supported");
2093 *id = xbt_dict_length(_to_index);
2094 xbt_dict_set(_to_index,name,id,xbt_free);
2097 static void generic_set_autonomous_system(routing_component_t rc, const char* name) {
2098 DEBUG1("Load Autonomous system \"%s\"",name);
2099 model_type_t modeltype = rc->routing;
2100 int *id = xbt_new0(int,1);
2101 xbt_dict_t _to_index;
2102 if(modeltype==&routing_models[SURF_MODEL_FULL])
2103 _to_index = ((routing_component_full_t)rc)->to_index;
2105 else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
2106 _to_index = ((routing_component_floyd_t)rc)->to_index;
2108 else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2109 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
2110 _to_index = ((routing_component_dijkstra_t)rc)->to_index;
2112 else xbt_die("\"generic_set_autonomous_system\" not supported");
2113 *id = xbt_dict_length(_to_index);
2114 xbt_dict_set(_to_index,name,id,xbt_free);
2117 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
2118 DEBUG2("Load Route from \"%s\" to \"%s\"",src,dst);
2119 model_type_t modeltype = rc->routing;
2120 xbt_dict_t _parse_routes;
2121 xbt_dict_t _to_index;
2123 int *src_id, *dst_id;
2125 if(modeltype==&routing_models[SURF_MODEL_FULL]) {
2126 _parse_routes = ((routing_component_full_t)rc)->parse_routes;
2127 _to_index = ((routing_component_full_t)rc)->to_index;
2129 } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
2130 _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
2131 _to_index = ((routing_component_floyd_t)rc)->to_index;
2133 } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2134 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
2135 _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
2136 _to_index = ((routing_component_dijkstra_t)rc)->to_index;
2138 } else xbt_die("\"generic_set_route\" not supported");
2140 src_id = xbt_dict_get_or_null(_to_index, src);
2141 dst_id = xbt_dict_get_or_null(_to_index, dst);
2143 xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
2144 route_name = bprintf("%d#%d",*src_id,*dst_id);
2146 xbt_assert2(xbt_dynar_length(route->link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
2147 xbt_assert2(!xbt_dict_get_or_null(_parse_routes,route_name),
2148 "The route between \"%s\" and \"%s\" already exist",src,dst);
2150 xbt_dict_set(_parse_routes, route_name, route, NULL);
2151 xbt_free(route_name);
2154 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
2155 DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"",src,e_route->src_gateway,dst,e_route->dst_gateway);
2156 model_type_t modeltype = rc->routing;
2157 xbt_dict_t _parse_routes;
2158 xbt_dict_t _to_index;
2160 int *src_id, *dst_id;
2162 if(modeltype==&routing_models[SURF_MODEL_FULL]) {
2163 _parse_routes = ((routing_component_full_t)rc)->parse_routes;
2164 _to_index = ((routing_component_full_t)rc)->to_index;
2166 } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
2167 _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
2168 _to_index = ((routing_component_floyd_t)rc)->to_index;
2170 } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2171 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
2172 _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
2173 _to_index = ((routing_component_dijkstra_t)rc)->to_index;
2175 } else xbt_die("\"generic_set_route\" not supported");
2177 src_id = xbt_dict_get_or_null(_to_index, src);
2178 dst_id = xbt_dict_get_or_null(_to_index, dst);
2180 xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
2181 route_name = bprintf("%d#%d",*src_id,*dst_id);
2183 xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
2184 xbt_assert4(!xbt_dict_get_or_null(_parse_routes,route_name),
2185 "The route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
2187 xbt_dict_set(_parse_routes, route_name, e_route, NULL);
2188 xbt_free(route_name);
2191 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
2192 DEBUG2("Load bypassRoute from \"%s\" to \"%s\"",src,dst);
2193 model_type_t modeltype = rc->routing;
2194 xbt_dict_t dict_bypassRoutes;
2196 if(modeltype==&routing_models[SURF_MODEL_FULL]) {
2197 dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
2198 } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
2199 dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
2200 } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2201 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
2202 dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
2203 } else xbt_die("\"generic_set_bypassroute\" not supported");
2204 route_name = bprintf("%s#%s",src,dst);
2205 xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
2206 xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes,route_name),
2207 "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
2209 route_extended_t new_e_route = generic_new_extended_route(SURF_ROUTING_RECURSIVE,e_route,0);
2210 xbt_dynar_free( &(e_route->generic_route.link_list) );
2213 xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, (void(*)(void*))generic_free_extended_route );
2214 xbt_free(route_name);
2217 /* ************************************************************************** */
2218 /* *********************** GENERIC BUSINESS METHODS ************************* */
2220 static xbt_dynar_t generic_get_onelink_routes (routing_component_t rc)
2222 xbt_die("\"generic_get_onelink_routes\" not implemented yet");
2225 static int generic_is_router (routing_component_t rc, const char *name)
2227 xbt_die("\"generic_is_router\" not implemented yet");
2230 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst) {
2231 model_type_t modeltype = rc->routing;
2232 xbt_dict_t dict_bypassRoutes;
2234 if(modeltype==&routing_models[SURF_MODEL_FULL]) {
2235 dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
2236 } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
2237 dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
2238 } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
2239 modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
2240 dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
2241 } else xbt_die("\"generic_get_bypassroute\" not supported");
2244 routing_component_t src_as, dst_as;
2245 int index_src, index_dst;
2246 xbt_dynar_t path_src = NULL;
2247 xbt_dynar_t path_dst = NULL;
2248 routing_component_t current = NULL;
2249 routing_component_t* current_src = NULL;
2250 routing_component_t* current_dst = NULL;
2252 /* (1) find the as where the src and dst are located */
2253 src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
2254 dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
2255 xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
2257 /* (2) find the path to the root routing component */
2258 path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
2260 while( current != NULL ) {
2261 xbt_dynar_push(path_src,¤t);
2262 current = current->routing_father;
2264 path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
2266 while( current != NULL ) {
2267 xbt_dynar_push(path_dst,¤t);
2268 current = current->routing_father;
2271 /* (3) find the common father */
2272 index_src = (path_src->used)-1;
2273 index_dst = (path_dst->used)-1;
2274 current_src = xbt_dynar_get_ptr(path_src,index_src);
2275 current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
2276 while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
2277 routing_component_t *tmp_src,*tmp_dst;
2278 tmp_src = xbt_dynar_pop_ptr(path_src);
2279 tmp_dst = xbt_dynar_pop_ptr(path_dst);
2282 current_src = xbt_dynar_get_ptr(path_src,index_src);
2283 current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
2286 int max_index_src = (path_src->used)-1;
2287 int max_index_dst = (path_dst->used)-1;
2289 int max_index = max(max_index_src,max_index_dst);
2292 route_extended_t e_route_bypass = NULL;
2294 for( max=0;max<=max_index;max++)
2298 if( i <= max_index_src && max <= max_index_dst ) {
2299 char* route_name = bprintf("%s#%s",
2300 (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,i)))->name,
2301 (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
2302 e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2303 xbt_free(route_name);
2305 if( e_route_bypass ) break;
2306 if( max <= max_index_src && i <= max_index_dst ) {
2307 char* route_name = bprintf("%s#%s",
2308 (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
2309 (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,i)))->name);
2310 e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2311 xbt_free(route_name);
2313 if( e_route_bypass ) break;
2316 if( e_route_bypass ) break;
2318 if( max <= max_index_src && max <= max_index_dst ) {
2319 char* route_name = bprintf("%s#%s",
2320 (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
2321 (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
2322 e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2323 xbt_free(route_name);
2325 if( e_route_bypass ) break;
2328 xbt_dynar_free(&path_src);
2329 xbt_dynar_free(&path_dst);
2331 route_extended_t new_e_route = NULL;
2333 if(e_route_bypass) {
2336 new_e_route = xbt_new0(s_route_extended_t,1);
2337 new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
2338 new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
2339 new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
2340 xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
2341 xbt_dynar_push(new_e_route->generic_route.link_list,&link);
2348 /* ************************************************************************** */
2349 /* ************************* GENERIC AUX FUNCTIONS ************************** */
2351 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order) {
2354 route_extended_t e_route, new_e_route;
2357 xbt_dynar_t links, links_id;
2359 new_e_route = xbt_new0(s_route_extended_t,1);
2360 new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
2361 new_e_route->src_gateway = NULL;
2362 new_e_route->dst_gateway = NULL;
2364 xbt_assert0(hierarchy == SURF_ROUTING_BASE || hierarchy == SURF_ROUTING_RECURSIVE,
2365 "the hierarchy type is not defined");
2367 if(hierarchy == SURF_ROUTING_BASE ) {
2369 route = (route_t)data;
2370 links = route->link_list;
2372 } else if(hierarchy == SURF_ROUTING_RECURSIVE ) {
2374 e_route = (route_extended_t)data;
2375 xbt_assert0(e_route->src_gateway&&e_route->dst_gateway,"bad gateway, is null");
2376 links = e_route->generic_route.link_list;
2378 /* remeber not erase the gateway names */
2379 new_e_route->src_gateway = e_route->src_gateway;
2380 new_e_route->dst_gateway = e_route->dst_gateway;
2383 links_id = new_e_route->generic_route.link_list;
2385 xbt_dynar_foreach(links, cpt, link_name) {
2387 void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2391 xbt_dynar_push(links_id,&link);
2393 xbt_dynar_unshift(links_id,&link);
2396 THROW1(mismatch_error,0,"Link %s not found", link_name);
2402 static void generic_free_route(route_t route) {
2404 xbt_dynar_free(&(route->link_list));
2409 static void generic_free_extended_route(route_extended_t e_route) {
2411 xbt_dynar_free(&(e_route->generic_route.link_list));
2412 if(e_route->src_gateway) xbt_free(e_route->src_gateway);
2413 if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
2418 static routing_component_t generic_as_exist(routing_component_t find_from, routing_component_t to_find) {
2419 //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
2420 xbt_dict_cursor_t cursor = NULL;
2423 routing_component_t elem;
2424 xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
2425 if( to_find == elem || generic_as_exist(elem,to_find) ){
2430 if(found) return to_find;
2434 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element) {
2435 //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
2436 routing_component_t element_as, result, elem;
2437 xbt_dict_cursor_t cursor = NULL;
2439 element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
2440 result = ((routing_component_t)-1);
2442 result = generic_as_exist(rc,element_as);
2447 xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
2448 found = !strcmp(elem->name,element);
2451 if( found ) return element_as;
2456 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element) {
2457 routing_component_t element_as;
2458 element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
2459 if(element_as==rc) return element_as;
2460 return generic_as_exist(rc,element_as);
2463 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst) {
2465 routing_component_t src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
2466 routing_component_t dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
2468 xbt_assert3(src_as != NULL && dst_as != NULL,
2469 "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
2470 xbt_assert4(src_as == dst_as,
2471 "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
2472 xbt_assert2(rc == dst_as,
2473 "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
2476 static void parse_Sconfig(void)
2479 DEBUG0("--->init of tag config");
2482 static void routing_full_parse_Scluster(void)
2484 static int AX_ptr = 0;
2486 char *cluster_id = A_surfxml_cluster_id;
2487 char *cluster_prefix = A_surfxml_cluster_prefix;
2488 char *cluster_suffix = A_surfxml_cluster_suffix;
2489 char *cluster_radical = A_surfxml_cluster_radical;
2490 char *cluster_power = A_surfxml_cluster_power;
2491 char *cluster_bw = A_surfxml_cluster_bw;
2492 char *cluster_lat = A_surfxml_cluster_lat;
2493 char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
2494 char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
2495 char *host_id, *groups, *link_id;
2496 char *router_id, *link_router, *link_backbone, *route_src_dst;
2499 xbt_dynar_t radical_elements;
2500 xbt_dynar_t radical_ends;
2501 #ifndef HAVE_PCRE_LIB
2502 xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
2503 char *route_src,*route_dst;
2507 static unsigned int surfxml_buffer_stack_stack_ptr = 1;
2508 static unsigned int surfxml_buffer_stack_stack[1024];
2510 surfxml_buffer_stack_stack[0]= 0;
2512 surfxml_bufferstack_push(1);
2514 SURFXML_BUFFER_SET(AS_id, cluster_id);
2515 #ifdef HAVE_PCRE_LIB
2516 SURFXML_BUFFER_SET(AS_routing, "RuleBased");
2517 DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">",cluster_id);
2519 SURFXML_BUFFER_SET(AS_routing, "Full");
2520 DEBUG1("<AS id=\"%s\"\trouting=\"Full\">",cluster_id);
2522 SURFXML_START_TAG(AS);
2524 radical_elements = xbt_str_split(cluster_radical, ",");
2525 xbt_dynar_foreach(radical_elements, iter, groups)
2527 radical_ends = xbt_str_split(groups, "-");
2528 switch (xbt_dynar_length(radical_ends))
2531 surf_parse_get_int(&start, xbt_dynar_get_as(radical_ends, 0, char *));
2532 host_id = bprintf("%s_%d%s", cluster_prefix, start, cluster_suffix);
2533 #ifndef HAVE_PCRE_LIB
2534 xbt_dynar_push_as(tab_elements_num, int, start);
2536 link_id = bprintf("%s_link_%d", cluster_id, start);
2538 DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>",host_id,cluster_power);
2539 SURFXML_BUFFER_SET(host_id, host_id);
2540 SURFXML_BUFFER_SET(host_power, cluster_power);
2541 SURFXML_BUFFER_SET(host_availability, "1.0");
2542 SURFXML_BUFFER_SET(host_availability_file, "");
2543 A_surfxml_host_state = A_surfxml_host_state_ON;
2544 SURFXML_BUFFER_SET(host_state_file, "");
2545 SURFXML_START_TAG(host);
2546 SURFXML_END_TAG(host);
2548 DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>",link_id,cluster_bw,cluster_lat);
2549 SURFXML_BUFFER_SET(link_id, link_id);
2550 SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
2551 SURFXML_BUFFER_SET(link_latency, cluster_lat);
2552 SURFXML_BUFFER_SET(link_bandwidth_file, "");
2553 SURFXML_BUFFER_SET(link_latency_file, "");
2554 A_surfxml_link_state = A_surfxml_link_state_ON;
2555 SURFXML_BUFFER_SET(link_state_file, "");
2556 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
2557 SURFXML_START_TAG(link);
2558 SURFXML_END_TAG(link);
2564 surf_parse_get_int(&start, xbt_dynar_get_as(radical_ends, 0, char *));
2565 surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
2566 DEBUG2("Create hosts and links from %d to %d",start,end);
2567 for (i = start; i <= end; i++)
2569 host_id = bprintf("%s_%d%s", cluster_prefix, i, cluster_suffix);
2570 #ifndef HAVE_PCRE_LIB
2571 xbt_dynar_push_as(tab_elements_num, int, i);
2573 link_id = bprintf("%s_link_%d", cluster_id, i);
2575 DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>",host_id,cluster_power);
2576 SURFXML_BUFFER_SET(host_id, host_id);
2577 SURFXML_BUFFER_SET(host_power, cluster_power);
2578 SURFXML_BUFFER_SET(host_availability, "1.0");
2579 SURFXML_BUFFER_SET(host_availability_file, "");
2580 A_surfxml_host_state = A_surfxml_host_state_ON;
2581 SURFXML_BUFFER_SET(host_state_file, "");
2582 SURFXML_START_TAG(host);
2583 SURFXML_END_TAG(host);
2585 DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>",link_id,cluster_bw,cluster_lat);
2586 SURFXML_BUFFER_SET(link_id, link_id);
2587 SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
2588 SURFXML_BUFFER_SET(link_latency, cluster_lat);
2589 SURFXML_BUFFER_SET(link_bandwidth_file, "");
2590 SURFXML_BUFFER_SET(link_latency_file, "");
2591 A_surfxml_link_state = A_surfxml_link_state_ON;
2592 SURFXML_BUFFER_SET(link_state_file, "");
2593 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
2594 SURFXML_START_TAG(link);
2595 SURFXML_END_TAG(link);
2600 DEBUG0("Malformed radical");
2603 xbt_dynar_free(&radical_ends);
2607 router_id = bprintf("%s_%s_router%s",cluster_prefix,cluster_id,cluster_suffix);
2608 link_router = bprintf("%s_link_%s_router",cluster_id,cluster_id);
2609 link_backbone = bprintf("%s_backbone",cluster_id);
2611 DEBUG1("<router id=\"%s\"/>",router_id);
2612 SURFXML_BUFFER_SET(router_id, router_id);;
2613 SURFXML_START_TAG(router);
2614 SURFXML_END_TAG(router);
2616 DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>",link_router,cluster_bw,cluster_lat);
2617 SURFXML_BUFFER_SET(link_id, link_router);
2618 SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
2619 SURFXML_BUFFER_SET(link_latency, cluster_lat);
2620 SURFXML_BUFFER_SET(link_bandwidth_file, "");
2621 SURFXML_BUFFER_SET(link_latency_file, "");
2622 A_surfxml_link_state = A_surfxml_link_state_ON;
2623 SURFXML_BUFFER_SET(link_state_file, "");
2624 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
2625 SURFXML_START_TAG(link);
2626 SURFXML_END_TAG(link);
2628 DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>",link_backbone,cluster_bb_bw,cluster_bb_lat);
2629 SURFXML_BUFFER_SET(link_id, link_backbone);
2630 SURFXML_BUFFER_SET(link_bandwidth, cluster_bb_bw);
2631 SURFXML_BUFFER_SET(link_latency, cluster_bb_lat);
2632 SURFXML_BUFFER_SET(link_bandwidth_file, "");
2633 SURFXML_BUFFER_SET(link_latency_file, "");
2634 A_surfxml_link_state = A_surfxml_link_state_ON;
2635 SURFXML_BUFFER_SET(link_state_file, "");
2636 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
2637 SURFXML_START_TAG(link);
2638 SURFXML_END_TAG(link);
2640 char *new_suffix = bprintf("%s","");
2642 radical_elements = xbt_str_split(cluster_suffix, ".");
2643 xbt_dynar_foreach(radical_elements, iter, groups)
2645 if(strcmp(groups,""))
2647 new_suffix = bprintf("%s\\.%s",new_suffix,groups);
2650 route_src_dst = bprintf("%s_(.*)%s",cluster_prefix,new_suffix);
2654 #ifdef HAVE_PCRE_LIB
2656 DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\">",route_src_dst,route_src_dst);
2657 SURFXML_BUFFER_SET(route_src, route_src_dst);
2658 SURFXML_BUFFER_SET(route_dst, route_src_dst);
2659 SURFXML_START_TAG(route);
2661 DEBUG1("<link:ctn\tid=\"%s_link_$1src\"/>",cluster_id);
2662 SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_link_$1src",cluster_id));
2663 SURFXML_START_TAG(link_ctn);
2664 SURFXML_END_TAG(link_ctn);
2666 DEBUG1("<link:ctn\tid=\"%s_backbone\"/>",cluster_id);
2667 SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_backbone",cluster_id));
2668 SURFXML_START_TAG(link_ctn);
2669 SURFXML_END_TAG(link_ctn);
2671 DEBUG1("<link:ctn\tid=\"%s_link_$1dst\"/>",cluster_id);
2672 SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_link_$1dst",cluster_id));
2673 SURFXML_START_TAG(link_ctn);
2674 SURFXML_END_TAG(link_ctn);
2677 SURFXML_END_TAG(route);
2679 for(i=0 ; i<=xbt_dynar_length(tab_elements_num) ; i++)
2681 for(j=0 ; j<=xbt_dynar_length(tab_elements_num) ; j++)
2683 if(i == xbt_dynar_length(tab_elements_num))
2685 route_src = router_id;
2689 route_src = bprintf("%s_%d%s",cluster_prefix,xbt_dynar_get_as(tab_elements_num,i,int),cluster_suffix);
2692 if(j == xbt_dynar_length(tab_elements_num))
2694 route_dst = router_id;
2698 route_dst = bprintf("%s_%d%s",cluster_prefix,xbt_dynar_get_as(tab_elements_num,j,int),cluster_suffix);
2701 DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\">",route_src,route_dst);
2702 SURFXML_BUFFER_SET(route_src, route_src);
2703 SURFXML_BUFFER_SET(route_dst, route_dst);
2704 SURFXML_START_TAG(route);
2706 if(i == xbt_dynar_length(tab_elements_num))
2708 route_src = link_router;
2712 route_src = bprintf("%s_link_%d",cluster_id,xbt_dynar_get_as(tab_elements_num,i,int));
2715 if(j == xbt_dynar_length(tab_elements_num))
2717 route_dst = link_router;
2721 route_dst = bprintf("%s_link_%d",cluster_id,xbt_dynar_get_as(tab_elements_num,j,int));
2724 DEBUG1("<link:ctn\tid=\"%s\"/>",route_src);
2725 SURFXML_BUFFER_SET(link_ctn_id, route_src);
2726 SURFXML_START_TAG(link_ctn);
2727 SURFXML_END_TAG(link_ctn);
2729 DEBUG1("<link:ctn\tid=\"%s_backbone\"/>",cluster_id);
2730 SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_backbone",cluster_id));
2731 SURFXML_START_TAG(link_ctn);
2732 SURFXML_END_TAG(link_ctn);
2734 DEBUG1("<link:ctn\tid=\"%s\"/>",route_dst);
2735 SURFXML_BUFFER_SET(link_ctn_id, route_dst);
2736 SURFXML_START_TAG(link_ctn);
2737 SURFXML_END_TAG(link_ctn);
2740 SURFXML_END_TAG(route);
2743 xbt_dynar_free(&tab_elements_num);
2747 SURFXML_END_TAG(AS);
2750 surfxml_bufferstack_pop(1);
2754 * New methods to init the routing model component from the lua script
2758 * calling parse_S_AS_lua with lua values
2760 void routing_AS_init(const char* AS_id,const char* AS_routing)
2762 parse_S_AS_lua((char*)AS_id,(char*)AS_routing);
2766 * calling parse_E_AS_lua to fisnish the creation of routing component
2768 void routing_AS_end(const char *AS_id)
2770 parse_E_AS_lua((char*)AS_id);
2774 * add a host to the network element list
2777 void routing_add_host(const char* host_id)
2779 parse_S_host_lua((char*)host_id);
2783 * Set a new link on the actual list of link for a route or ASroute
2785 void routing_add_link(const char* link_id)
2787 parse_E_link_c_ctn_new_elem_lua((char*)link_id);
2791 *Set the endpoints for a route
2793 void routing_set_route(const char* src_id,const char *dst_id)
2795 parse_S_route_new_and_endpoints_lua((char*)src_id,(char*)dst_id);
2799 * Store the route by calling parse_E_route_store_route
2801 void routing_store_route(void)
2803 parse_E_route_store_route();