-
- routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
- const char *sep = "#";
- char *key, *key_gw, *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, 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;i<table_size;i++)
- for(j=0;j<table_size;j++) {
- TO_FLOYD_COST(i,j) = DBL_MAX;
- TO_FLOYD_PRED(i,j) = -1;
- TO_FLOYD_LINK(i,j) = NULL; // TODO: FIXED DAVID
- }
-
- /* Put the routes in position */
- xbt_dict_foreach(routing->parse_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;c<table_size;c++) {
- for(a=0;a<table_size;a++) {
- for(b=0;b<table_size;b++) {
- if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
- if(TO_FLOYD_COST(a,b) == DBL_MAX ||
- (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
- TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
- TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
- }
- }
- }
- }
- }
-
- /* (2) second process: if there are any AS, make a routing table for AS limits */
-
- if( xbt_dict_length(current_routing->routing_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;i<AS_table_size;i++) {
- for (j=0;j<AS_table_size;j++) {
- TO_FLOYD_AS(i,j).src_gateway = NULL;
- TO_FLOYD_AS(i,j).dst_gateway = NULL;
- }
- }
-
- /* (3) third process: find the best gateways for each AS */
-
- // select two AS or gateways
- xbt_dict_foreach(routing->AS_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);