From: navarrop Date: Tue, 28 Sep 2010 08:52:20 +0000 (+0000) Subject: add the floyd algorithm for a routing schema X-Git-Tag: v3_5~596 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/2492d71e145ae1a72066746b1b48a3ced3be71b3 add the floyd algorithm for a routing schema git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@8228 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- diff --git a/src/surf/surf_routing.c b/src/surf/surf_routing.c index 7d25866d47..38deaf6380 100644 --- a/src/surf/surf_routing.c +++ b/src/surf/surf_routing.c @@ -71,9 +71,46 @@ static void model_full_load(); /* load parse functions for full routing model static void model_full_unload(); /* unload parse functions for full routing model */ static void model_full_end(); /* finalize the creation of full routing model */ +static void* model_floyd_create(); /* create structures for floyd routing model */ +static void model_floyd_load(); /* load parse functions for floyd routing model */ +static void model_floyd_unload(); /* unload parse functions for floyd routing model */ +static void model_floyd_end(); /* finalize the creation of floyd routing model */ + +static void* model_dijkstra_create(); /* create structures for dijkstra routing model */ +static void model_dijkstra_load(); /* load parse functions for dijkstra routing model */ +static void model_dijkstra_unload(); /* unload parse functions for dijkstra routing model */ +static void model_dijkstra_end(); /* finalize the creation of dijkstra routing model */ + +static void* model_dijkstracache_create(); /* create structures for dijkstracache routing model */ +static void model_dijkstracache_load(); /* load parse functions for dijkstracache routing model */ +static void model_dijkstracache_unload(); /* unload parse functions for dijkstracache routing model */ +static void model_dijkstracache_end(); /* finalize the creation of dijkstracache routing model */ + +static void* model_none_create(); /* none routing model */ +static void model_none_load(); /* none routing model */ +static void model_none_unload(); /* none routing model */ +static void model_none_end(); /* none routing model */ + /* Table of routing models */ +/* must be finish with null and carefull if change de order */ + +#define SURF_MODEL_FULL 0 +#define SURF_MODEL_FLOYD 1 +#define SURF_MODEL_DIJKSTRA 2 +#define SURF_MODEL_DIJKSTRACACHE 3 +#define SURF_MODEL_NONE 4 + struct s_model_type routing_models[] = -{ {"Full", "Full routing data", model_full_create, model_full_load, model_full_unload, model_full_end }, +{ {"Full", "Full routing data (fast, large memory requirements, fully expressive)", + model_full_create, model_full_load, model_full_unload, model_full_end }, + {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", + model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end }, + {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", + model_dijkstra_create ,model_dijkstra_load, model_dijkstra_unload, model_dijkstra_end }, + {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", + model_dijkstracache_create, model_dijkstracache_load, model_dijkstracache_unload, model_dijkstracache_end }, + {"none", "No routing (usable with Constant network only)", + model_none_create, model_none_load, model_none_unload, model_none_end }, {NULL,NULL,NULL,NULL,NULL,NULL}}; @@ -84,7 +121,9 @@ struct s_model_type routing_models[] = * * Allows find a "host" in any routing component */ -static void parse_S_host(void) { // FIXME: if not exists +static void parse_S_host(void) { + xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_host_id), + "The host \"%s\" already exist",A_surfxml_host_id); xbt_dict_set(global_routing->where_network_elements,A_surfxml_host_id,(void*)current_routing,NULL); } @@ -93,7 +132,9 @@ static void parse_S_host(void) { // FIXME: if not exists * * Allows find a "router" in any routing component */ -static void parse_S_router(void) { // FIXME: if not exists +static void parse_S_router(void) { + xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_router_id), + "The router \"%s\" already exist",A_surfxml_router_id); xbt_dict_set(global_routing->where_network_elements,A_surfxml_router_id,(void*)current_routing,NULL); } @@ -102,7 +143,9 @@ static void parse_S_router(void) { // FIXME: if not exists * * Allows find a "gateway" in any routing component */ -static void parse_S_gateway(void) { // FIXME: if not exists +static void parse_S_gateway(void) { + xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_gateway_id), + "The gateway \"%s\" already exist",A_surfxml_gateway_id); xbt_dict_set(global_routing->where_network_elements,A_surfxml_gateway_id,(void*)current_routing,NULL); } @@ -135,7 +178,8 @@ static void parse_S_AS(void) { new_routing->routing = model; new_routing->name = xbt_strdup(A_surfxml_AS_id); new_routing->routing_sons = xbt_dict_new(); - + INFO2("Routing %s for AS %s",A_surfxml_AS_routing,A_surfxml_AS_id); + if( current_routing == NULL && global_routing->root == NULL ) { /* it is the first one */ new_routing->routing_father = NULL; @@ -144,6 +188,8 @@ static void parse_S_AS(void) { else if( current_routing != NULL && global_routing->root != NULL ) { /* it is a part of the tree */ new_routing->routing_father = current_routing; + xbt_assert1(!xbt_dict_get_or_null(current_routing->routing_sons,A_surfxml_AS_id), + "The AS \"%s\" already exist",A_surfxml_AS_id); xbt_dict_set(current_routing->routing_sons,A_surfxml_AS_id,(void*)new_routing,NULL); /* unload the prev parse rules */ (*(current_routing->routing->unload))(); @@ -185,6 +231,8 @@ static void parse_E_AS(void) { * way as "parse_S_host", "parse_S_router" and "parse_S_gateway" do. */ static void _add_parse_AS(routing_component_t rc) { + xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,rc->name), + "The AS \"%s\" already exist",rc->name); xbt_dict_set(global_routing->where_network_elements,rc->name,rc->routing_father,NULL); xbt_dict_cursor_t cursor = NULL; char *key; @@ -237,6 +285,11 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { xbt_dynar_reset(global_routing->last_route); +// TODO: check if the route is between hosts +// xbt_assert2( ( src_ne->type == SURF_NETWORK_ELEMENT_HOST || src_ne-> == SURF_NETWORK_ELEMENT_AS ) +// && ( src_ne->type == SURF_NETWORK_ELEMENT_HOST || src_ne-> == SURF_NETWORK_ELEMENT_AS ) , +// "Invalid network elements \"%s\" or \"%s\" for make a route", src, dst); + /* (1) find the as-routetree where the src and dst are located */ src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src); dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst); @@ -276,7 +329,9 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { if( *current_src == *current_dst ) { /* (5.1) belong to the same routing component */ + xbt_assert1((*current_src)->get_route, "Invalid \"get_route\" for \"%s\"",(*current_src)->name); tmp_route = (*(*current_src)->get_route)(*current_src,src,dst); + xbt_assert3(tmp_route, "there is no route between \"%s\" and \"%s\" in \"%s\"",src,dst,(*current_src)->name); cpt = 0; xbt_dynar_foreach(tmp_route->generic_route.link_list, cpt, link) { xbt_dynar_push(global_routing->last_route,&link); @@ -288,7 +343,10 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { index_father_src = index_src+1; index_father_dst = index_dst+1; father = xbt_dynar_get_ptr(path_src,index_father_src); + xbt_assert1((*father)->get_route, "Invalid \"get_route\" for \"%s\"",(*father)->name); route_center_links = (*((*father)->get_route))(*father,(*current_src)->name,(*current_dst)->name); + xbt_assert3(route_center_links, "there is no route between \"%s\" and \"%s\" in \"%s\"", + (*current_src)->name,(*current_dst)->name,(*father)->name); /* (5.2.1) make the source path */ path_src_links = xbt_dynar_new(global_routing->size_of_link, NULL); @@ -297,10 +355,13 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { index_src--; for(index_src;index_src>=0;index_src--) { current_src = xbt_dynar_get_ptr(path_src,index_src); + xbt_assert1((*current_src_father)->get_route, "Invalid \"get_route\" for \"%s\"",(*current_src_father)->name); tmp_route = (*((*current_src_father)->get_route))(*current_src_father,(*current_src)->name,current_router_dst); + xbt_assert3(tmp_route, "there is no route between \"%s\" and \"%s\" in \"%s\"", + (*current_src)->name,(*current_dst)->name,(*current_src_father)->name); cpt = 0; xbt_dynar_foreach(tmp_route->generic_route.link_list, cpt, link) { - //xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d (5.2.1)", src, dst); + xbt_assert2(link,"NULL link in the route from src %s to dst %s (5.2.1)", src, dst); xbt_dynar_push(path_src_links,&link); } current_router_dst = tmp_route->src_gateway; @@ -314,10 +375,13 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { index_dst--; for(index_dst;index_dst>=0;index_dst--) { current_dst = xbt_dynar_get_ptr(path_dst,index_dst); + xbt_assert1((*current_dst_father)->get_route, "Invalid \"get_route\" for \"%s\"",(*current_dst_father)->name); tmp_route = (*((*current_dst_father)->get_route))(*current_dst_father,current_router_src,(*current_dst)->name); + xbt_assert3(tmp_route, "there is no route between \"%s\" and \"%s\" in \"%s\"", + (*current_src)->name,(*current_dst)->name,(*current_dst_father)->name); cpt = 0; xbt_dynar_foreach(tmp_route->generic_route.link_list, cpt, link) { - //xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d (5.2.1)", src, dst); + xbt_assert2(link,"NULL link in the route from src %s to dst %s (5.2.1)", src, dst); xbt_dynar_push(path_dst_links,&link); } current_router_src = tmp_route->dst_gateway; @@ -325,10 +389,16 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { } /* (5.2.3) the first part of the route */ + xbt_assert1((*current_src)->get_route, "Invalid \"get_route\" for \"%s\"",(*current_src)->name); path_first = ((*((*current_src)->get_route))(*current_src,src,current_router_dst))->generic_route.link_list; + xbt_assert3(path_first, "there is no route between \"%s\" and \"%s\" in \"%s\"", + src,current_router_dst,(*current_src)->name); /* (5.2.4) the last part of the route */ - path_last = ((*((*current_dst)->get_route))(*current_dst,dst,current_router_src))->generic_route.link_list; + xbt_assert1((*current_dst)->get_route, "Invalid \"get_route\" for \"%s\"",(*current_dst)->name); + path_last = ((*((*current_dst)->get_route))(*current_dst,current_router_src,dst))->generic_route.link_list; + xbt_assert3(path_last, "there is no route between \"%s\" and \"%s\" in \"%s\"", + current_router_src,dst,(*current_dst)->name); /* (5.2.5) make all paths together */ // FIXME: the paths non respect the right order @@ -361,7 +431,10 @@ static xbt_dynar_t get_route(const char* src,const char* dst) { xbt_dynar_free(&path_src); xbt_dynar_free(&path_dst); - return global_routing->last_route; + if( xbt_dynar_length(global_routing->last_route)==0 ) + return NULL; + else + return global_routing->last_route; } /** @@ -380,8 +453,10 @@ static void _finalize(routing_component_t rc) { xbt_dict_foreach(rc->routing_sons, cursor, key, elem) { _finalize(elem); } - xbt_dict_free(&(rc->routing_sons)); - xbt_free(rc->name); + xbt_dict_t tmp_sons = rc->routing_sons; + char* tmp_name = rc->name; + xbt_dict_free(&tmp_sons); + xbt_free(tmp_name); (*(rc->finalize))(rc); } } @@ -440,92 +515,110 @@ void routing_model_create(size_t size_of_links, void* loopback) { } +/* ************************************************************************** */ +/* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */ + +static char* src = NULL; /* temporary store the source name of a route */ +static char* dst = NULL; /* temporary store the destination name of a route */ +static char* gw_src = NULL; /* temporary store the gateway source name of a route */ +static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */ +static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */ + +static void generic_parse_S_route_new_and_endpoints(void); +static void generic_E_link_c_ctn_new_elem(void); +static void generic_parse_E_route_store_route(void); + /* ************************************************************************** */ /* *************************** FULL ROUTING ********************************* */ -#define TO_ROUTE_FULL(i,j) ((routing_component_full_t)current_routing)->routing_table[(i)+(j)*xbt_dict_length(((routing_component_full_t)current_routing)->to_index)] -#define TO_ROUTE_FULL_RC(i,j,rc) ((routing_component_full_t)rc)->routing_table[(i)+(j)*xbt_dict_length(((routing_component_full_t)rc)->to_index)] +#define TO_ROUTE_FULL(i,j,rc) ((routing_component_full_t)rc)->routing_table[(i)+(j)*xbt_dict_length(((routing_component_full_t)rc)->to_index)] /* Routing model structure */ typedef struct { s_routing_component_t generic_routing; - xbt_dict_t to_index; /* char* -> index* */ + xbt_dict_t parse_routes; /* store data during the parse process */ + xbt_dict_t to_index; /* char* -> network_element_t */ route_extended_t *routing_table; - xbt_dict_t parse_routes; -} s_routing_componentl_full_t,*routing_component_full_t; +} s_routing_component_full_t,*routing_component_full_t; /* Parse routing model functions */ -static char* src = NULL; /* temporary store the source name of a route */ -static char* dst = NULL; /* temporary store the destination name of a route */ -static char* gw_src = NULL; /* temporary store the gateway source name of a route */ -static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */ -static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */ - static void full_parse_S_host(void) { - int *val = xbt_malloc(sizeof(int)); - *val = xbt_dict_length(((routing_component_full_t)current_routing)->to_index); - xbt_dict_set(((routing_component_full_t)current_routing)->to_index,A_surfxml_host_id,val,xbt_free); + network_element_t ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(((routing_component_full_t)current_routing)->to_index); + ne->type = SURF_NETWORK_ELEMENT_HOST; + xbt_dict_set(((routing_component_full_t)current_routing)->to_index,A_surfxml_host_id,ne,xbt_free); } static void full_parse_S_gateway(void) { - int *val = xbt_malloc(sizeof(int)); - *val = xbt_dict_length(((routing_component_full_t)current_routing)->to_index); - xbt_dict_set(((routing_component_full_t)current_routing)->to_index,A_surfxml_gateway_id,val,xbt_free); -} - -static void full_parse_S_route_new_and_endpoints(void) { - if( src != NULL && dst != NULL && link_list != NULL ) - THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_route_src,A_surfxml_route_dst); - src = A_surfxml_route_src; - dst = A_surfxml_route_dst; - gw_src = A_surfxml_route_gw_src; - gw_dst = A_surfxml_route_gw_dst; - link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref); -} - -static void parse_E_link_c_ctn_new_elem(void) { - char *val; - val = xbt_strdup(A_surfxml_link_c_ctn_id); - xbt_dynar_push(link_list, &val); -} - -static void full_parse_E_route_store_route(void) { - char *route_name; - route_name = bprintf("%s#%s#%s#%s",src,dst,gw_src,gw_dst); - // FIXME: if not exists - xbt_dict_set(((routing_component_full_t)current_routing)->parse_routes, route_name, link_list, NULL); - free(route_name); - src = NULL; - dst = NULL; - link_list = NULL; + network_element_t ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(((routing_component_full_t)current_routing)->to_index); + ne->type = SURF_NETWORK_ELEMENT_GATEWAY; + xbt_dict_set(((routing_component_full_t)current_routing)->to_index,A_surfxml_gateway_id,ne,xbt_free); } /* Business methods */ static route_extended_t full_get_route(routing_component_t rc, const char* src,const char* dst) { + xbt_assert1(src && dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); + routing_component_full_t src_as, dst_as; - int *src_id,*dst_id; + int src_id,dst_id; + network_element_t ne_src,ne_dst; // FIXME: here we can use the current_routing var. - src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src); dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst); xbt_assert0(src_as != NULL && dst_as != NULL, "Ask for route \"from\" or \"to\" no found"); - xbt_assert0(src_as == dst_as, "The src and dst are in differents AS"); + xbt_assert0((routing_component_full_t)rc == dst_as, + "The routing component of src and dst is not the same as the network elements belong"); - xbt_assert0((routing_component_full_t)rc == dst_as, "The routing component of src and dst is not the same as the network elements belong"); + ne_src = (network_element_t) xbt_dict_get(src_as->to_index,src); + ne_dst = (network_element_t) xbt_dict_get(dst_as->to_index,dst); - src_id = (int*)xbt_dict_get(src_as->to_index,src); - dst_id = (int*)xbt_dict_get(dst_as->to_index,dst); + src_id = ne_src->id; + dst_id = ne_dst->id; - xbt_assert0(src_id != NULL && dst_id != NULL, "Ask for route \"from\" or \"to\" no found in the local table"); + xbt_assert0(ne_src != NULL && ne_dst != NULL, "Ask for route \"from\" or \"to\" no found in the local table"); + + if( xbt_dynar_length(TO_ROUTE_FULL(src_id,dst_id,src_as)->generic_route.link_list) > 0 ) + return TO_ROUTE_FULL(src_id,dst_id,src_as); + else + return NULL; +} + +static xbt_dict_t full_get_network_elements(routing_component_t rc, e_surf_network_element_type_t req_type) +{ + routing_component_full_t routing = (routing_component_full_t)rc; + xbt_dict_t result = xbt_dict_new(); + xbt_dict_cursor_t cursor = NULL; + char *key; + network_element_t ne; + // TODO: do the next (the AS_GATEWAY are definened in the AS in the this_AS) + if(req_type == SURF_NETWORK_ELEMENT_AS_GATEWAY ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } + // TODO: do the next (the links are not defined for the routing) + if(req_type == SURF_NETWORK_ELEMENT_LINK ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } + // TODO: do the next (the routers are not defined for this type of routing) + if(req_type == SURF_NETWORK_ELEMENT_ROUTER ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } - return TO_ROUTE_FULL_RC(*src_id,*dst_id,src_as); + xbt_dict_foreach(routing->to_index, cursor, key, ne) { + if( req_type == SURF_NETWORK_ELEMENT_NULL || req_type == ne->type ) { + e_surf_network_element_type_t *new_type = xbt_new0(e_surf_network_element_type_t,1); + *new_type = ne->type; + xbt_dict_set(result,key,new_type,xbt_free); + } + } + return result; } static void full_finalize(routing_component_t rc) { @@ -536,7 +629,7 @@ static void full_finalize(routing_component_t rc) { /* Delete routing table */ for (i=0;igeneric_route.link_list)); if(e_route->src_gateway) xbt_free(e_route->src_gateway); if(e_route->dst_gateway) xbt_free(e_route->dst_gateway); @@ -554,9 +647,10 @@ static void full_finalize(routing_component_t rc) { /* Creation routing model functions */ static void* model_full_create() { - routing_component_full_t new_component = xbt_new0(s_routing_componentl_full_t,1); + routing_component_full_t new_component = xbt_new0(s_routing_component_full_t,1); new_component->generic_routing.get_route = full_get_route; new_component->generic_routing.finalize = full_finalize; + new_component->generic_routing.get_network_elements = full_get_network_elements; new_component->to_index = xbt_dict_new(); new_component->parse_routes = xbt_dict_new(); return new_component; @@ -565,40 +659,40 @@ static void* model_full_create() { static void model_full_load() { surfxml_add_callback(STag_surfxml_host_cb_list, &full_parse_S_host); surfxml_add_callback(STag_surfxml_gateway_cb_list, &full_parse_S_gateway); - surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &parse_E_link_c_ctn_new_elem); - surfxml_add_callback(STag_surfxml_route_cb_list, &full_parse_S_route_new_and_endpoints); - surfxml_add_callback(ETag_surfxml_route_cb_list, &full_parse_E_route_store_route); + surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &generic_E_link_c_ctn_new_elem); + surfxml_add_callback(STag_surfxml_route_cb_list, &generic_parse_S_route_new_and_endpoints); + surfxml_add_callback(ETag_surfxml_route_cb_list, &generic_parse_E_route_store_route); } static void model_full_unload() { surfxml_del_callback(&STag_surfxml_host_cb_list, &full_parse_S_host); surfxml_del_callback(&STag_surfxml_gateway_cb_list, &full_parse_S_gateway); - surfxml_del_callback(&ETag_surfxml_link_c_ctn_cb_list, &parse_E_link_c_ctn_new_elem); - surfxml_del_callback(&STag_surfxml_route_cb_list, &full_parse_S_route_new_and_endpoints); - surfxml_del_callback(&ETag_surfxml_route_cb_list, &full_parse_E_route_store_route); + surfxml_del_callback(&ETag_surfxml_link_c_ctn_cb_list, &generic_E_link_c_ctn_new_elem); + surfxml_del_callback(&STag_surfxml_route_cb_list, &generic_parse_S_route_new_and_endpoints); + surfxml_del_callback(&ETag_surfxml_route_cb_list, &generic_parse_E_route_store_route); } static void model_full_end() { char *key, *end, *link_name, *src_name, *dst_name, *src_gw_name, *dst_gw_name; const char* sep = "#"; - int *src_id, *dst_id, *src_gw_id, *dst_gw_id; + network_element_t src_id, dst_id, src_gw_id, dst_gw_id, ne; + route_extended_t new_e_route; int i, j, cpt; routing_component_t component; xbt_dynar_t links; xbt_dict_cursor_t cursor = NULL; xbt_dynar_t keys = NULL; - routing_component_full_t src_as; - routing_component_full_t dst_as; - + routing_component_t src_as; + routing_component_t dst_as; routing_component_full_t routing = ((routing_component_full_t)current_routing); - + /* Add the AS found to local components */ xbt_dict_foreach(current_routing->routing_sons, cursor, key, component) { - int *val = xbt_malloc(sizeof(int)); - *val = xbt_dict_length(routing->to_index); - // FIXME: if exists - xbt_dict_set(routing->to_index,key,val,xbt_free); + ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(routing->to_index); + ne->type = SURF_NETWORK_ELEMENT_AS; + xbt_dict_set(routing->to_index,key,ne,xbt_free); } int table_size = xbt_dict_length(routing->to_index); @@ -607,11 +701,11 @@ static void model_full_end() { routing->routing_table = xbt_new0(route_extended_t, table_size * table_size); for (i=0;igeneric_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); new_e_route->src_gateway = NULL; new_e_route->dst_gateway = NULL; - TO_ROUTE_FULL(i,j) = new_e_route; + TO_ROUTE_FULL(i,j,current_routing) = new_e_route; } } @@ -635,9 +729,6 @@ static void model_full_end() { src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src_gw_name); if (src_as == NULL) THROW1(mismatch_error,0,"Network elements %s not found", src_gw_name); - src_gw_id = xbt_dict_get_or_null(src_as->to_index, src_gw_name); - if (src_gw_id == NULL) - THROW1(mismatch_error,0,"Network elements %s not found in the local tablfe", src_gw_name); } else { src_gw_name = NULL; // FIXME: maybe here put the same src_name. } @@ -646,20 +737,17 @@ static void model_full_end() { dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst_gw_name); if (dst_as == NULL) THROW1(mismatch_error,0,"Network elements %s not found", dst_gw_name); - dst_gw_id = xbt_dict_get_or_null(dst_as->to_index, dst_gw_name); - if (dst_gw_id == NULL) - THROW1(mismatch_error,0,"Network elements %s not found in the local table", dst_gw_name); } else { dst_gw_name = NULL; // FIXME: maybe here put the same dst_name. } - TO_ROUTE_FULL(*src_id,*dst_id)->src_gateway = xbt_strdup(src_gw_name); - TO_ROUTE_FULL(*src_id,*dst_id)->dst_gateway = xbt_strdup(dst_gw_name); + TO_ROUTE_FULL(src_id->id,dst_id->id,current_routing)->src_gateway = xbt_strdup(src_gw_name); + TO_ROUTE_FULL(src_id->id,dst_id->id,current_routing)->dst_gateway = xbt_strdup(dst_gw_name); xbt_dynar_foreach(links, cpt, link_name) { void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name); if (link) - xbt_dynar_push(TO_ROUTE_FULL(*src_id,*dst_id)->generic_route.link_list,&link); + xbt_dynar_push(TO_ROUTE_FULL(src_id->id,dst_id->id,current_routing)->generic_route.link_list,&link); else THROW1(mismatch_error,0,"Link %s not found", link_name); } @@ -678,15 +766,644 @@ static void model_full_end() { /* Add the loopback if needed */ for (i = 0; i < table_size; i++) - if (!xbt_dynar_length(TO_ROUTE_FULL(i, i)->generic_route.link_list)) - xbt_dynar_push(TO_ROUTE_FULL(i,i)->generic_route.link_list,&global_routing->loopback); + if (!xbt_dynar_length(TO_ROUTE_FULL(i, i,current_routing)->generic_route.link_list)) + xbt_dynar_push(TO_ROUTE_FULL(i,i,current_routing)->generic_route.link_list,&global_routing->loopback); /* Shrink the dynar routes (save unused slots) */ for (i=0;igeneric_route.link_list,0); + xbt_dynar_shrink(TO_ROUTE_FULL(i,j,current_routing)->generic_route.link_list,0); +} + +/* ************************************************************************** */ +/* *************************** FLOYD ROUTING ******************************** */ + +#define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size] +#define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size] +#define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size] +#define TO_FLOYD_AS(i,j) (routing->AS_table)[(i)+(j)*AS_table_size] + +/* Routing model structure */ + +typedef struct { + s_routing_component_t generic_routing; + route_extended_t last_route; + /* vars for calculate the floyd algorith. */ + int *predecessor_table; + void** link_table; /* char* -> network_element_t* */ + xbt_dict_t predecessor_to_index; + /* store information to solve any AS route */ + xbt_dict_t AS_to_index; /* char* -> network_element_t* */ + route_limits_t AS_table; + /* store data during the parse process */ + xbt_dict_t parse_routes; + +} s_routing_component_floyd_t,*routing_component_floyd_t; + +/* Parse routing model functions */ + +static void floyd_parse_S_host(void) { + network_element_t ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(((routing_component_floyd_t)current_routing)->predecessor_to_index); + ne->type = SURF_NETWORK_ELEMENT_HOST; + xbt_dict_set(((routing_component_floyd_t)current_routing)->predecessor_to_index,A_surfxml_host_id,ne,xbt_free); +} + +static void floyd_parse_S_gateway(void) { + network_element_t ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(((routing_component_floyd_t)current_routing)->predecessor_to_index); + ne->type = SURF_NETWORK_ELEMENT_GATEWAY; + xbt_dict_set(((routing_component_floyd_t)current_routing)->predecessor_to_index,A_surfxml_gateway_id,ne,xbt_free); +} + +static void floyd_parse_S_router(void) { + network_element_t ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(((routing_component_floyd_t)current_routing)->predecessor_to_index); + ne->type = SURF_NETWORK_ELEMENT_ROUTER; + xbt_dict_set(((routing_component_floyd_t)current_routing)->predecessor_to_index,A_surfxml_router_id,ne,xbt_free); +} + +/* Business methods */ + +static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) { + + xbt_assert1(src && dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); + + /* set utils vars */ + routing_component_floyd_t routing = (routing_component_floyd_t) rc; + int table_size = xbt_dict_length(routing->predecessor_to_index); + int AS_table_size; + /* clear the last route */ + xbt_dynar_reset(routing->last_route->generic_route.link_list); + if(routing->last_route->src_gateway) xbt_free(routing->last_route->src_gateway); + if(routing->last_route->dst_gateway) xbt_free(routing->last_route->dst_gateway); + routing->last_route->src_gateway = NULL; + routing->last_route->dst_gateway = NULL; + + /* find the network elements for make a route */ + network_element_t dst_ne = xbt_dict_get_or_null(routing->predecessor_to_index, dst); + network_element_t src_ne = xbt_dict_get_or_null(routing->predecessor_to_index, src); + network_element_t src_ne_AS, dst_ne_AS; + + /* if some network element is a AS, I need to find the adecuate gateway for the route */ + if(!src_ne || !dst_ne ) { + xbt_assert1(routing->AS_to_index, "AS table not found (\"%s\")",rc->name); + AS_table_size = xbt_dict_length(routing->AS_to_index); + src_ne_AS = xbt_dict_get_or_null(routing->AS_to_index, src); + dst_ne_AS = xbt_dict_get_or_null(routing->AS_to_index, dst); + xbt_assert2(src_ne_AS && dst_ne_AS, "Attempt to make a route between a hosts element and a AS (\"%s\",\"%s\")",src,dst); + route_limits_t limits = &TO_FLOYD_AS(src_ne_AS->id,dst_ne_AS->id); + if(!src_ne) routing->last_route->src_gateway = xbt_strdup(limits->src_gateway); + if(!dst_ne) routing->last_route->dst_gateway = xbt_strdup(limits->dst_gateway); + dst_ne = xbt_dict_get_or_null(routing->predecessor_to_index, limits->dst_gateway); + src_ne = xbt_dict_get_or_null(routing->predecessor_to_index, limits->src_gateway); + } + + xbt_assert2(src_ne != NULL || dst_ne != NULL, + "Invalid network elements \"%s\" or \"%s\" not found", src, dst); + + int src_id = src_ne->id; + int dst_id = dst_ne->id; + + int pred = dst_id; + int prev_pred = 0; + + do { + prev_pred = pred; + pred = TO_FLOYD_PRED(src_id, pred); + + if(pred == -1) // if no pred in route -> no route to host + break; + + xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst); + + xbt_dynar_unshift(routing->last_route->generic_route.link_list, &(TO_FLOYD_LINK(pred,prev_pred))); + + } while(pred != src_id); + + xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", src_id, dst_id,src,dst); + + if( xbt_dynar_length(routing->last_route->generic_route.link_list) > 0 ) + return routing->last_route; + else + return NULL; +} + +static xbt_dict_t floyd_get_network_elements(routing_component_t rc, e_surf_network_element_type_t req_type) +{ + routing_component_floyd_t routing = (routing_component_floyd_t)rc; + xbt_dict_t result = xbt_dict_new(); + xbt_dict_cursor_t cursor = NULL; + char *key; + network_element_t ne; + // TODO: do the next (the AS_GATEWAY are definened in the AS in the this_AS) + if(req_type == SURF_NETWORK_ELEMENT_AS_GATEWAY ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } + // TODO: do the next (the links are not defined for the routing) + if(req_type == SURF_NETWORK_ELEMENT_LINK ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } + // TODO: do the next (the routers are defined into predecessor_to_index) + if(req_type == SURF_NETWORK_ELEMENT_ROUTER ) { + xbt_assert0(0, "NOT IMPLEMENTED YET"); + } + + if( req_type == SURF_NETWORK_ELEMENT_NULL || req_type == SURF_NETWORK_ELEMENT_HOST ) { + xbt_dict_foreach(routing->predecessor_to_index, cursor, key, ne) { + if( ne->type == SURF_NETWORK_ELEMENT_HOST) { + e_surf_network_element_type_t *new_type = xbt_new0(e_surf_network_element_type_t,1); + *new_type = ne->type; + xbt_dict_set(result,key,new_type,xbt_free); + } + } + } + + if( req_type == SURF_NETWORK_ELEMENT_NULL || req_type == SURF_NETWORK_ELEMENT_AS || req_type == SURF_NETWORK_ELEMENT_GATEWAY ) { + xbt_dict_foreach(routing->predecessor_to_index, cursor, key, ne) { + if( req_type == SURF_NETWORK_ELEMENT_NULL || req_type == ne->type ) { + e_surf_network_element_type_t *new_type = xbt_new0(e_surf_network_element_type_t,1); + *new_type = ne->type; + xbt_dict_set(result,key,new_type,xbt_free); + } + } + } + return result; +} + +static void floyd_finalize(routing_component_t rc) { + routing_component_floyd_t routing = (routing_component_floyd_t)rc; + int i,j,AS_table_size; + if (routing) { + /* Delete dictionary index dict, predecessor and links table */ + xbt_free(routing->predecessor_table); + xbt_dict_free(&(routing->predecessor_to_index)); + xbt_free(routing->link_table); + /* Delete dictionary index and limit table */ + if(routing->AS_to_index) { + AS_table_size = xbt_dict_length(routing->AS_to_index); + xbt_dict_free(&(routing->AS_to_index)); + } + if(routing->AS_table) { + for(i=0;iAS_table); + /* Delete index dynar for last routes */ + if(routing->last_route->src_gateway) xbt_free(routing->last_route->src_gateway); + if(routing->last_route->dst_gateway) xbt_free(routing->last_route->dst_gateway); + xbt_dynar_free(&(routing->last_route->generic_route.link_list)); + xbt_free(routing->last_route); + /* Delete structure */ + xbt_free(rc); + } +} + +/* Creation routing model functions */ + +static void* model_floyd_create() { + routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1); + /* global vars */ + new_component->generic_routing.get_route = floyd_get_route; + new_component->generic_routing.finalize = floyd_finalize; + new_component->generic_routing.get_network_elements = floyd_get_network_elements; + /* local vars */ + new_component->last_route = xbt_new(s_route_extended_t,1); + new_component->last_route->src_gateway = NULL; + new_component->last_route->dst_gateway = NULL; + new_component->last_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); + new_component->predecessor_to_index = xbt_dict_new(); + new_component->AS_to_index = NULL; + new_component->AS_table = NULL; + new_component->parse_routes = xbt_dict_new(); + return new_component; +} + +static void model_floyd_load() { + surfxml_add_callback(STag_surfxml_host_cb_list, &floyd_parse_S_host); + surfxml_add_callback(STag_surfxml_gateway_cb_list, &floyd_parse_S_gateway); + surfxml_add_callback(STag_surfxml_router_cb_list, &floyd_parse_S_router); + surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &generic_E_link_c_ctn_new_elem); + surfxml_add_callback(STag_surfxml_route_cb_list, &generic_parse_S_route_new_and_endpoints); + surfxml_add_callback(ETag_surfxml_route_cb_list, &generic_parse_E_route_store_route); +} + +static void model_floyd_unload() { + surfxml_del_callback(&STag_surfxml_host_cb_list, &floyd_parse_S_host); + surfxml_del_callback(&STag_surfxml_gateway_cb_list, &floyd_parse_S_gateway); + surfxml_del_callback(&STag_surfxml_router_cb_list, &floyd_parse_S_router); + surfxml_del_callback(&ETag_surfxml_link_c_ctn_cb_list, &generic_E_link_c_ctn_new_elem); + surfxml_del_callback(&STag_surfxml_route_cb_list, &generic_parse_S_route_new_and_endpoints); + surfxml_del_callback(&ETag_surfxml_route_cb_list, &generic_parse_E_route_store_route); +} + +static void model_floyd_end() { + + routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing); + const char *sep = "#"; + char *key, *key_gw, *end, *link_name, *keyX, *keyY; + char *src_name, *dst_name, *src_gw_name, *dst_gw_name; + double * cost_table; + unsigned int i,j; + unsigned int a,b,c; + int host_count=0, AS_count=0; + void *data = NULL; + void *link = NULL; + e_surf_network_element_type_t *type_gw; + network_element_t ne, ne_gw, new_ne, src_ne, dst_ne, src_gw_ne, dst_gw_ne, neX, neY; + xbt_dict_cursor_t cursor=NULL, cursor_gw=NULL, cursorX=NULL, cursorY=NULL; + xbt_dynar_t links, keys; + routing_component_t component; + + /* (0) Check for if there are any host in the a AS */ + xbt_dict_foreach(routing->predecessor_to_index, cursor, key, ne) { + if(ne->type == SURF_NETWORK_ELEMENT_HOST ) host_count++; + } + AS_count = xbt_dict_length(current_routing->routing_sons); + + xbt_assert2( (host_count>0 && AS_count==0) || (host_count==0 && AS_count>0), + "Invalid count of network elements, %d AS and %d host found",AS_count,host_count); + + /* Add the AS gateways to network elements dictionary */ + xbt_dict_foreach(current_routing->routing_sons, cursor, key, component) { + xbt_assert1(component->get_network_elements, + "Invalid \"get_network_elements\" for \"%s\"",key); + xbt_dict_t gateways = (*(component->get_network_elements))(component,SURF_NETWORK_ELEMENT_GATEWAY); + xbt_dict_foreach(gateways, cursor_gw, key_gw, type_gw) { + new_ne = xbt_new0(s_network_element_t,1); + new_ne->id = xbt_dict_length(routing->predecessor_to_index); + new_ne->type = SURF_NETWORK_ELEMENT_AS_GATEWAY; + xbt_dict_set(routing->predecessor_to_index,key_gw,new_ne,xbt_free); + } + xbt_dict_free(&gateways); + } + + /* (1) first process: calculate the routing table using the floyd algorithm */ + + /* set the size of inicial table */ + int table_size = xbt_dict_length(routing->predecessor_to_index); + + /* Create Cost, Predecessor and Link tables */ + cost_table = xbt_new0(double, table_size*table_size); // link cost from host to host + routing->predecessor_table = xbt_new0(int, table_size*table_size); // predecessor host numbers + routing->link_table = xbt_new0(void*,table_size*table_size); // actual link between src and dst + + /* Initialize costs and predecessors */ + for(i=0;iparse_routes, cursor, key, data) { + + links = (xbt_dynar_t)data; + keys = xbt_str_split_str(key, sep); + + src_name = xbt_dynar_get_as(keys, 0, char*); + dst_name = xbt_dynar_get_as(keys, 1, char*); + src_gw_name = xbt_dynar_get_as(keys, 2, char*); + dst_gw_name = xbt_dynar_get_as(keys, 3, char*); + + src_ne = xbt_dict_get_or_null(routing->predecessor_to_index, src_name); + dst_ne = xbt_dict_get_or_null(routing->predecessor_to_index, dst_name); + src_gw_ne = xbt_dict_get_or_null(routing->predecessor_to_index, src_gw_name); + dst_gw_ne = xbt_dict_get_or_null(routing->predecessor_to_index, dst_gw_name); + + xbt_assert2(src_ne != NULL || src_gw_ne != NULL, + "Invalid source, network elements\"%s\" with gateway \"%s\" not found", src_name, src_gw_name); + xbt_assert2(dst_ne != NULL || dst_gw_ne != NULL, + "Invalid source, network elements\"%s\" with gateway \"%s\" not found", dst_name, dst_gw_name); + + //DEBUG4("Handle %d %d (from %d hosts): %ld links",src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links)); + xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host \"%s\" and \"%s\", should be 1", xbt_dynar_length(links), src_name, dst_name); + + link_name = xbt_dynar_getfirst_as(links, char*); + link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name); + + if( src_ne == NULL ) src_ne = src_gw_ne; + if( dst_ne == NULL ) dst_ne = dst_gw_ne; + + if (link) + link_list = link; + else + THROW1(mismatch_error,0,"Link %s not found", link_name); + + TO_FLOYD_LINK(src_ne->id,dst_ne->id) = link_list; + TO_FLOYD_PRED(src_ne->id,dst_ne->id) = src_ne->id; + + //link cost + TO_FLOYD_COST(src_ne->id,dst_ne->id) = 1; // assume 1 for now + + xbt_dynar_free(&keys); + } + + /* Add the loopback if needed */ + for (i = 0; i < table_size; i++) + if (TO_FLOYD_PRED(i,i) == -1) { // TODO: FIXED DAVID + TO_FLOYD_PRED(i,i) = i; + TO_FLOYD_COST(i,i) = 1; + TO_FLOYD_LINK(i,i) = global_routing->loopback; + } + + /* Calculate path costs */ + for(c=0;crouting_sons) > 0 ) { + + /* store index for the routing table */ + routing->AS_to_index = xbt_dict_new(); + + /* Add all local AS into AS_to_index */ + xbt_dict_foreach(current_routing->routing_sons, cursor, key, component) { + ne = xbt_new0(s_network_element_t,1); + ne->id = xbt_dict_length(routing->AS_to_index); + ne->type = SURF_NETWORK_ELEMENT_AS; + xbt_dict_set(routing->AS_to_index,key,ne,xbt_free); + } + + /* Add all local gateways into AS_to_index */ + xbt_dict_foreach(routing->predecessor_to_index, cursor, key, ne) { + if( ne->type == SURF_NETWORK_ELEMENT_GATEWAY ) { + new_ne = xbt_new0(s_network_element_t,1); + new_ne->id = xbt_dict_length(routing->AS_to_index); + new_ne->type = SURF_NETWORK_ELEMENT_GATEWAY; + xbt_dict_set(routing->AS_to_index,key,new_ne,xbt_free); + } + } + + /* size of the limits table for AS */ + int AS_table_size = xbt_dict_length(routing->AS_to_index); + + /* Create the limits table for AS */ + routing->AS_table = xbt_new0(s_route_limits_t, AS_table_size * AS_table_size); + for (i=0;iAS_to_index, cursorX, keyX, neX) { + xbt_dict_foreach(routing->AS_to_index, cursorY, keyY, neY) { + + if( neX != neY ) { // if the network elements are differents + + if( ( neX->type==SURF_NETWORK_ELEMENT_HOST || neX->type==SURF_NETWORK_ELEMENT_GATEWAY ) && + ( neY->type==SURF_NETWORK_ELEMENT_HOST || neY->type==SURF_NETWORK_ELEMENT_GATEWAY ) ) { + /* route between hosts or gateways : do not any thing */ + } else if( (neX->type==SURF_NETWORK_ELEMENT_AS && neY->type==SURF_NETWORK_ELEMENT_AS) || + (neX->type==SURF_NETWORK_ELEMENT_AS && neY->type==SURF_NETWORK_ELEMENT_GATEWAY) || + (neX->type==SURF_NETWORK_ELEMENT_GATEWAY && neY->type==SURF_NETWORK_ELEMENT_AS) ) { + /* route between AS */ + /* or route between AS and gateway */ + /* or route between gateway adn AS */ + + routing_component_t rcX, rcY; + xbt_dict_t list_ASgatewayX, list_ASgatewayY; + + if( neX->type==SURF_NETWORK_ELEMENT_AS ) { + rcX = xbt_dict_get_or_null(current_routing->routing_sons,keyX); + xbt_assert1(rcX && rcX->get_network_elements, + "Invalid \"get_network_elements\" for \"%s\"",keyX); + list_ASgatewayX = (*(rcX->get_network_elements))(rcX,SURF_NETWORK_ELEMENT_GATEWAY); + } else { + list_ASgatewayX = xbt_dict_new(); + e_surf_network_element_type_t *new_type = xbt_new0(e_surf_network_element_type_t,1); + *new_type = SURF_NETWORK_ELEMENT_GATEWAY; + xbt_dict_set(list_ASgatewayX,keyX,new_type,xbt_free); + } + + if( neY->type==SURF_NETWORK_ELEMENT_AS ) { + rcY = xbt_dict_get_or_null(current_routing->routing_sons,keyY); + xbt_assert1(rcY && rcY->get_network_elements, + "Invalid \"get_network_elements\" for \"%s\"",keyY); + list_ASgatewayY = (*(rcY->get_network_elements))(rcY,SURF_NETWORK_ELEMENT_GATEWAY); + } else { + list_ASgatewayY = xbt_dict_new(); + e_surf_network_element_type_t *new_type = xbt_new0(e_surf_network_element_type_t,1); + *new_type = SURF_NETWORK_ELEMENT_GATEWAY; + xbt_dict_set(list_ASgatewayY,keyY,new_type,xbt_free); + } + + xbt_dict_cursor_t cursorASgatewayX=NULL, cursorASgatewayY=NULL; + char * keyASgatewayX, *keyASgatewayY; + e_surf_network_element_type_t *typeASgatewayX, *typeASgatewayY; + + char* best_ASgatewayX = NULL; + char* best_ASgatewayY = NULL; + double best_cost = DBL_MAX; + + // test for all combinations fo Gateways between the AS + xbt_dict_foreach(list_ASgatewayX, cursorASgatewayX, keyASgatewayX, typeASgatewayX) { + xbt_dict_foreach(list_ASgatewayY, cursorASgatewayY, keyASgatewayY, typeASgatewayY) { + //printf(".....%s....%s....\n",keyASgatewayX,keyASgatewayY); + network_element_t src_ne = xbt_dict_get_or_null(routing->predecessor_to_index, keyASgatewayX); + network_element_t dst_ne = xbt_dict_get_or_null(routing->predecessor_to_index, keyASgatewayY); + double new_cost = TO_FLOYD_COST(src_ne->id,dst_ne->id); + if( best_cost > new_cost ) { + if(best_ASgatewayX) xbt_free(best_ASgatewayX); + if(best_ASgatewayY) xbt_free(best_ASgatewayY); + best_cost = new_cost; + best_ASgatewayX = xbt_strdup(keyASgatewayX); + best_ASgatewayY = xbt_strdup(keyASgatewayY); + } + } + } + // store the best combination of gateways into the table + xbt_assert2(best_ASgatewayX && best_ASgatewayY, + "Can not found a combination of gateways for a route between \"%s\" and \"%s\"",keyX,keyY); + network_element_t src_ne = xbt_dict_get_or_null(routing->AS_to_index, keyX); + network_element_t dst_ne = xbt_dict_get_or_null(routing->AS_to_index, keyY); + xbt_assert0(src_ne && dst_ne, "Invalid gateways for a make a route"); + TO_FLOYD_AS(src_ne->id,dst_ne->id).src_gateway = best_ASgatewayX; + TO_FLOYD_AS(src_ne->id,dst_ne->id).dst_gateway = best_ASgatewayY; + + /* free the list of gateways */ + xbt_dict_free(&list_ASgatewayX); + xbt_dict_free(&list_ASgatewayY); + + } else { + xbt_assert0(0, "Invalid network element type"); + } + } // close big if + } // close Y foreach + } // close X foreach + + } // close if for second process + + /* delete the parse table */ + xbt_dict_foreach(routing->parse_routes, cursor, key, links) { + xbt_dynar_free(&links); + } + + /* delete all the parsing temporary data */ + xbt_dict_free(&(routing->parse_routes)); + + /* cleanup */ + free(cost_table); +} + +/* ************************************************************************** */ +/* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */ + +typedef struct { + s_routing_component_t generic_routing; + xbt_graph_t route_graph; + xbt_dict_t graph_node_map; + xbt_dict_t route_cache; + xbt_dynar_t last_route; + int cached; +} s_routing_component_dijkstra_t,*routing_component_dijkstra_t; + +/* Parse routing model functions */ + +/* Business methods */ + +/* Creation routing model functions */ + +static void* model_dijkstra_create() { +} + +static void model_dijkstra_load() { +} + +static void model_dijkstra_unload() { +} + +static void model_dijkstra_end() { +} + +static void* model_dijkstracache_create() { +} + +static void model_dijkstracache_load() { +} + +static void model_dijkstracache_unload() { +} + +static void model_dijkstracache_end() { +} + + +/* ************************************************************************** */ +/* ******************************* NO ROUTING ******************************* */ + +/* Routing model structure */ +typedef struct { + s_routing_component_t generic_routing; +} s_routing_component_none_t,*routing_component_none_t; + +/* Business methods */ +static route_extended_t none_get_route(routing_component_t rc, const char* src,const char* dst){ + return NULL; +} +static void none_finalize(routing_component_t rc) { + xbt_free(rc); +} + +/* Creation routing model functions */ +static void* model_none_create() { + routing_component_none_t new_component = xbt_new0(s_routing_component_none_t,1); + new_component->generic_routing.get_route = none_get_route; + new_component->generic_routing.finalize = none_finalize; + return new_component; +} + +static void model_none_load() {} +static void model_none_unload() {} +static void model_none_end() {} + +/* ************************************************** */ +/* ********** PATERN FOR NEW ROUTING **************** */ + +/* The minimal configuration of a new routing model need the next functions, + * also you need to set at the start of the file, the new model in the model + * list. Remember keep the null ending of the list. + +/* Routing model structure */ +typedef struct { + s_routing_component_t generic_routing; + /* things that your routing model need */ +} s_routing_component_NEW_t,*routing_component_NEW_t; + +/* Parse routing model functions */ +static void NEW_parse_S_host(void) {} /* example*/ + +/* Business methods */ +static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {} /* mandatory */ +static void NEW_finalize(routing_component_t rc) {} /* mandatory */ + +/* Creation routing model functions */ +static void* model_NEW_create() {} /* mandatory */ +static void model_NEW_load() {} /* mandatory */ +static void model_NEW_unload() {} /* mandatory */ +static void model_NEW_end() {} /* mandatory */ + +/* ************************************************************************** */ +/* ************************* GENERIC PARSE FUNCTIONS ************************ */ + +static void generic_parse_S_route_new_and_endpoints(void) { + if( src != NULL && dst != NULL && link_list != NULL ) + THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_route_src,A_surfxml_route_dst); + src = A_surfxml_route_src; + dst = A_surfxml_route_dst; + gw_src = A_surfxml_route_gw_src; + gw_dst = A_surfxml_route_gw_dst; + link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref); +} + +static void generic_E_link_c_ctn_new_elem(void) { + char *val; + val = xbt_strdup(A_surfxml_link_c_ctn_id); + xbt_dynar_push(link_list, &val); +} + +static void generic_parse_E_route_store_route(void) { + char *route_name; + xbt_dict_t parse_routes; + if( current_routing->routing == &(routing_models[SURF_MODEL_FULL]) ) + parse_routes = ((routing_component_full_t)current_routing)->parse_routes; + else if( current_routing->routing == &(routing_models[SURF_MODEL_FLOYD]) ) + parse_routes = ((routing_component_floyd_t)current_routing)->parse_routes; + else + xbt_assert0(0, "Invalid model for call \"generic_parse_E_route_store_route\""); + route_name = bprintf("%s#%s#%s#%s",src,dst,gw_src,gw_dst); + xbt_assert2(xbt_dynar_length(link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst); + xbt_assert3(!xbt_dict_get_or_null(parse_routes,route_name), + "The route between \"%s\" and \"%s\" already exist (\"%s\")",src,dst,route_name); + xbt_dict_set(parse_routes, route_name, link_list, NULL); + free(route_name); + src = NULL; + dst = NULL; + link_list = NULL; } + //////////////////////////////////////////////////////////////////////////////// // HERE FINISH THE NEW CODE //////////////////////////////////////////////////////////////////////////////// @@ -698,15 +1415,19 @@ static void print_tree(routing_component_t rc) { xbt_dict_cursor_t cursor = NULL; char *key; int *val; - xbt_dict_foreach(((routing_component_full_t)rc)->to_index, cursor, key, val) { - printf("<%s-%d> ",key,*val); - } + if( rc->routing == &(routing_models[SURF_MODEL_FULL]) ) + { xbt_dict_foreach(((routing_component_full_t)rc)->to_index, cursor, key, val) { printf("<%s-%d> ",key,*val); } } + else if( rc->routing == &(routing_models[SURF_MODEL_FLOYD]) ) + { xbt_dict_foreach(((routing_component_floyd_t)rc)->predecessor_to_index, cursor, key, val) { printf("<%s-%d> ",key,*val); } + xbt_dict_foreach(((routing_component_floyd_t)rc)->AS_to_index, cursor, key, val) { printf("<%s-%d> ",key,*val); } } + else + xbt_assert0(0, "Invalid model for call \"print_tree\""); printf("\n"); routing_component_t elem; xbt_dict_foreach(rc->routing_sons, cursor, key, elem) { printf("<--\n"); print_tree(elem); - printf("-->\n"); + printf("-->\n"); } } @@ -739,9 +1460,33 @@ static void DEGUB_exit(void) { print_global(); printf("----------------------------------\n\n"); +// char* names[] = { "11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; +// int i,j,total = 8; + +// printf("-- print all the example routes --\n"); +// char* names[] = { "11.A","11.B","11.C"}; +// int i,j,total = 3; + +// char* names[] = { "141.A","141.B","143.A","143.B"}; +// int i,j,total = 4; + +// char* names[] = { "142.A","142.B","142.C" }; +// int i,j,total = 3; + +// char* names[] = { "142.A","142.B","142.C", "11.A","11.B","11.C","141.A","141.B","143.A","143.B","11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; +// int i,j,total = 3+4+8+3; + + char* names[] = { "11.A","11.B","11.C", + "121.A","121.B", + "122.A", + "13.A","13.B", + "141.A","141.B", + "142.A","142.B","142.C", + "143.A","143.B", + "15.A","15.B","15.C"}; + int i,j,total = 3+2+1+2+2+3+2+3; + printf("-- print all the example routes --\n"); - char* names[] = { "11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; - int i,j,total = 8; xbt_dynar_t links; void* link; for(i=0;i