Fixed full routing support for routers, no routing complexity is added routers are...

[simgrid.git] / src / surf / surf_routing.c

diff --git a/src/surf/surf_routing.c b/src/surf/surf_routing.c
index 742ccd5..ac58e67 100644 (file)
--- a/src/surf/surf_routing.c
+++ b/src/surf/surf_routing.c
@@ -11,7 +11,7 @@
 #include "xbt/graph.h"
 #include "xbt/set.h"
 
 #include "xbt/graph.h"
 #include "xbt/set.h"
 

-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");// FIXME: connect this under windows
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");

 
 routing_t used_routing = NULL;
 
 
 routing_t used_routing = NULL;
 


@@ -20,6 +20,7 @@ static void routing_model_full_create(size_t size_of_link,void *loopback);
 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);
 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);

+static void routing_model_none_create(size_t size_of_link, void*loopback);

 
 /* Definition of each model */
 struct model_type {
 
 /* Definition of each model */
 struct model_type {


@@ -32,6 +33,7 @@ struct model_type models[] =
   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },
   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },

+  {"none", "No routing (usable with Constant network only)", routing_model_none_create },

     {NULL,NULL,NULL}};
 
 
     {NULL,NULL,NULL}};
 
 


@@ -66,6 +68,13 @@ typedef struct {
 /*
  * Parsing
  */
 /*
  * Parsing
  */

+static void routing_full_parse_Srouter(void) {
+  int *val = xbt_malloc(sizeof(int));
+  DEBUG2("Seen router %s (#%d)",A_surfxml_host_id,used_routing->host_count);
+  *val = used_routing->host_count++;
+  xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
+}
+

 static void routing_full_parse_Shost(void) {
   int *val = xbt_malloc(sizeof(int));
   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
 static void routing_full_parse_Shost(void) {
   int *val = xbt_malloc(sizeof(int));
   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);


@@ -91,6 +100,134 @@ static void routing_full_parse_Eroute(void)
   }
 }
 
   }
 }
 

+/* Cluster tag functions */
+
+static void routing_full_parse_change_cpu_data(const char *hostName,
+                                  const char *surfxml_host_power,
+                                  const char *surfxml_host_availability,
+                                  const char *surfxml_host_availability_file,
+                                  const char *surfxml_host_state_file)
+{
+  int AX_ptr = 0;
+
+  SURFXML_BUFFER_SET(host_id, hostName);
+  SURFXML_BUFFER_SET(host_power, surfxml_host_power /*hostPower */ );
+  SURFXML_BUFFER_SET(host_availability, surfxml_host_availability);
+  SURFXML_BUFFER_SET(host_availability_file, surfxml_host_availability_file);
+  SURFXML_BUFFER_SET(host_state_file, surfxml_host_state_file);
+}
+
+static void routing_full_parse_change_link_data(const char *linkName,
+                                   const char *surfxml_link_bandwidth,
+                                   const char *surfxml_link_bandwidth_file,
+                                   const char *surfxml_link_latency,
+                                   const char *surfxml_link_latency_file,
+                                   const char *surfxml_link_state_file)
+{
+  int AX_ptr = 0;
+
+  SURFXML_BUFFER_SET(link_id, linkName);
+  SURFXML_BUFFER_SET(link_bandwidth, surfxml_link_bandwidth);
+  SURFXML_BUFFER_SET(link_bandwidth_file, surfxml_link_bandwidth_file);
+  SURFXML_BUFFER_SET(link_latency, surfxml_link_latency);
+  SURFXML_BUFFER_SET(link_latency_file, surfxml_link_latency_file);
+  SURFXML_BUFFER_SET(link_state_file, surfxml_link_state_file);
+}
+
+static void routing_full_parse_Scluster(void)
+{
+  static int AX_ptr = 0;
+
+  char *cluster_id = A_surfxml_cluster_id;
+  char *cluster_prefix = A_surfxml_cluster_prefix;
+  char *cluster_suffix = A_surfxml_cluster_suffix;
+  char *cluster_radical = A_surfxml_cluster_radical;
+  char *cluster_power = A_surfxml_cluster_power;
+  char *cluster_bw = A_surfxml_cluster_bw;
+  char *cluster_lat = A_surfxml_cluster_lat;
+  char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
+  char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
+  char *backbone_name;
+
+  surfxml_bufferstack_push(1);
+
+  /* Make set */
+  SURFXML_BUFFER_SET(set_id, cluster_id);
+  SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
+  SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
+  SURFXML_BUFFER_SET(set_radical, cluster_radical);
+
+  SURFXML_START_TAG(set);
+  SURFXML_END_TAG(set);
+
+  /* Make foreach */
+  SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
+
+  SURFXML_START_TAG(foreach);
+
+  /* Make host for the foreach */
+  routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
+  A_surfxml_host_state = A_surfxml_host_state_ON;
+
+  SURFXML_START_TAG(host);
+  SURFXML_END_TAG(host);
+
+  /* Make link for the foreach */
+  routing_full_parse_change_link_data("$1", cluster_bw, "", cluster_lat, "", "");
+  A_surfxml_link_state = A_surfxml_link_state_ON;
+  A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
+
+  SURFXML_START_TAG(link);
+  SURFXML_END_TAG(link);
+
+  SURFXML_END_TAG(foreach);
+
+  /* Make backbone link */
+  backbone_name = bprintf("%s_bb", cluster_id);
+  routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
+                         "");
+  A_surfxml_link_state = A_surfxml_link_state_ON;
+  A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
+
+  SURFXML_START_TAG(link);
+  SURFXML_END_TAG(link);
+
+  /* Make route multi with the outside world, i.e. cluster->$* */
+  SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
+  SURFXML_BUFFER_SET(route_c_multi_dst, "$*");
+  A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
+  A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_OVERRIDE;
+
+  SURFXML_START_TAG(route_c_multi);
+
+  SURFXML_BUFFER_SET(link_c_ctn_id, "$src");
+
+  SURFXML_START_TAG(link_c_ctn);
+  SURFXML_END_TAG(link_c_ctn);
+
+  SURFXML_END_TAG(route_c_multi);
+
+  /* Make route multi between cluster hosts, i.e. cluster->cluster */
+  SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
+  SURFXML_BUFFER_SET(route_c_multi_dst, cluster_id);
+  A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_POSTPEND;
+  A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
+
+  SURFXML_START_TAG(route_c_multi);
+
+  SURFXML_BUFFER_SET(link_c_ctn_id, backbone_name);
+
+  SURFXML_START_TAG(link_c_ctn);
+  SURFXML_END_TAG(link_c_ctn);
+
+  SURFXML_END_TAG(route_c_multi);
+
+  free(backbone_name);
+
+  /* Restore buff */
+  surfxml_bufferstack_pop(1);
+}
+

 
 static void routing_full_parse_end(void) {
   routing_full_t routing = (routing_full_t) used_routing;
 
 static void routing_full_parse_end(void) {
   routing_full_t routing = (routing_full_t) used_routing;


@@ -181,27 +318,82 @@ static void routing_model_full_create(size_t size_of_link,void *loopback) {
   /* Setup the parsing callbacks we need */
   routing->generic_routing.host_id = xbt_dict_new();
   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
   /* Setup the parsing callbacks we need */
   routing->generic_routing.host_id = xbt_dict_new();
   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);

+  surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);

   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
   surfxml_add_callback(STag_surfxml_route_cb_list,
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
   surfxml_add_callback(STag_surfxml_route_cb_list,
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);

+  surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
+}
+
+/* ************************************************************************** */
+
+static void routing_shortest_path_parse_Scluster(void)
+{
+  static int AX_ptr = 0;
+
+  char *cluster_id = A_surfxml_cluster_id;
+  char *cluster_prefix = A_surfxml_cluster_prefix;
+  char *cluster_suffix = A_surfxml_cluster_suffix;
+  char *cluster_radical = A_surfxml_cluster_radical;
+  char *cluster_power = A_surfxml_cluster_power;
+  char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
+  char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
+  char *backbone_name;
+
+  surfxml_bufferstack_push(1);
+
+  /* Make set */
+  SURFXML_BUFFER_SET(set_id, cluster_id);
+  SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
+  SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
+  SURFXML_BUFFER_SET(set_radical, cluster_radical);
+
+  SURFXML_START_TAG(set);
+  SURFXML_END_TAG(set);
+
+  /* Make foreach */
+  SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
+
+  SURFXML_START_TAG(foreach);
+
+  /* Make host for the foreach */
+  routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
+  A_surfxml_host_state = A_surfxml_host_state_ON;
+
+  SURFXML_START_TAG(host);
+  SURFXML_END_TAG(host);
+
+  SURFXML_END_TAG(foreach);
+
+  /* Make backbone link */
+  backbone_name = bprintf("%s_bb", cluster_id);
+  routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
+                         "");
+  A_surfxml_link_state = A_surfxml_link_state_ON;
+  A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
+
+  SURFXML_START_TAG(link);
+  SURFXML_END_TAG(link);
+
+  free(backbone_name);
+
+  /* Restore buff */
+  surfxml_bufferstack_pop(1);

 }
 
 /* ************************************************************************** */
 /* *************************** FLOYD ROUTING ********************************* */
 typedef struct {
   s_routing_t generic_routing;
 }
 
 /* ************************************************************************** */
 /* *************************** FLOYD ROUTING ********************************* */
 typedef struct {
   s_routing_t generic_routing;

-  double *cost_table;

   int *predecessor_table;
   void** link_table;
   int *predecessor_table;
   void** link_table;

-  
+  xbt_dynar_t last_route;

   void *loopback;
   size_t size_of_link;
 } s_routing_floyd_t,*routing_floyd_t;
 
   void *loopback;
   size_t size_of_link;
 } s_routing_floyd_t,*routing_floyd_t;
 

-
-
-#define FLOYD_COST(i,j) ((routing_floyd_t)used_routing)->cost_table[(i)+(j)*(used_routing)->host_count]
+#define FLOYD_COST(i,j) cost_table[(i)+(j)*(used_routing)->host_count]

 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
 
 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
 


@@ -209,22 +401,22 @@ static void routing_floyd_parse_end(void) {
 
   routing_floyd_t routing = (routing_floyd_t) used_routing;
   int nb_link = 0;
 
   routing_floyd_t routing = (routing_floyd_t) used_routing;
   int nb_link = 0;

-  unsigned int cpt = 0;    

   void* link_list = NULL;
   void* link_list = NULL;

+  double * cost_table;

   xbt_dict_cursor_t cursor = NULL;
   char *key,*data, *end;
   const char *sep = "#";
   xbt_dynar_t links, keys;
   xbt_dict_cursor_t cursor = NULL;
   char *key,*data, *end;
   const char *sep = "#";
   xbt_dynar_t links, keys;

-  char *link_name = NULL;

 
   unsigned int i,j;
 
   int host_count = routing->generic_routing.host_count;
 
   /* Create Cost, Predecessor and Link tables */
 
   unsigned int i,j;
 
   int host_count = routing->generic_routing.host_count;
 
   /* Create Cost, Predecessor and Link tables */

-  routing->cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
+  cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host

   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst

+  routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);

 
   /* Initialize costs and predecessors*/
   for(i = 0; i<host_count;i++)
 
   /* Initialize costs and predecessors*/
   for(i = 0; i<host_count;i++)


@@ -248,14 +440,13 @@ static void routing_floyd_parse_end(void) {
         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 %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
     
         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 %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
     

-    xbt_dynar_foreach (links, cpt, link_name) {
-      void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
-      if (link)
-        link_list = link;
-      else
-        THROW1(mismatch_error,0,"Link %s not found", link_name);
+    char * link_name = xbt_dynar_getfirst_as(links, char*);
+    void * link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
+    if (link)
+      link_list = link;
+    else
+      THROW1(mismatch_error,0,"Link %s not found", link_name);

     
     

-    }

 
     FLOYD_LINK(src_id,dst_id) = link_list;
     FLOYD_PRED(src_id, dst_id) = src_id;
 
     FLOYD_LINK(src_id,dst_id) = link_list;
     FLOYD_PRED(src_id, dst_id) = src_id;


@@ -288,6 +479,9 @@ static void routing_floyd_parse_end(void) {
       }
     }
   }
       }
     }
   }

+
+  //cleanup
+  free(cost_table);

 }
 
 /*
 }
 
 /*


@@ -300,7 +494,7 @@ static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
   int pred = dst_id;
   int prev_pred = 0;
 
   int pred = dst_id;
   int prev_pred = 0;
 

-  xbt_dynar_t link_list = xbt_dynar_new(routing->size_of_link, NULL);
+  xbt_dynar_reset(routing->last_route);

 
   do {
     prev_pred = pred;
 
   do {
     prev_pred = pred;


@@ -309,17 +503,13 @@ static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
     if(pred == -1) // if no pred in route -> no route to host
         break;
 
     if(pred == -1) // if no pred in route -> no route to host
         break;
 

-    xbt_dynar_unshift(link_list, &FLOYD_LINK(pred,prev_pred));
+    xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));

 
   } while(pred != src_id);
 
   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
 
 
   } while(pred != src_id);
 
   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
 

-  return link_list;
-}
-
-static void routing_floyd_finalize_route(xbt_dynar_t route) {
-  xbt_dynar_free(&route);
+  return routing->last_route;

 }
 
 static void routing_floyd_finalize(void) {
 }
 
 static void routing_floyd_finalize(void) {


@@ -327,8 +517,8 @@ static void routing_floyd_finalize(void) {
 
   if (routing) {
     free(routing->link_table);
 
   if (routing) {
     free(routing->link_table);

-    free(routing->cost_table);

     free(routing->predecessor_table);
     free(routing->predecessor_table);

+    xbt_dynar_free(&routing->last_route);

     xbt_dict_free(&used_routing->host_id);
     free(routing);
     routing=NULL;
     xbt_dict_free(&used_routing->host_id);
     free(routing);
     routing=NULL;


@@ -340,9 +530,9 @@ static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
   routing->generic_routing.name = "Floyd";
   routing->generic_routing.host_count = 0;
   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
   routing->generic_routing.name = "Floyd";
   routing->generic_routing.host_count = 0;

+  routing->generic_routing.host_id = xbt_dict_new();

   routing->generic_routing.get_route = routing_floyd_get_route;
   routing->generic_routing.finalize = routing_floyd_finalize;
   routing->generic_routing.get_route = routing_floyd_get_route;
   routing->generic_routing.finalize = routing_floyd_finalize;

-  routing->generic_routing.finalize_route = routing_floyd_finalize_route;

   routing->size_of_link = size_of_link;
   routing->loopback = loopback;
 
   routing->size_of_link = size_of_link;
   routing->loopback = loopback;
 


@@ -350,12 +540,12 @@ static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
   used_routing = (routing_t) routing;
   
   /* Setup the parsing callbacks we need */
   used_routing = (routing_t) routing;
   
   /* Setup the parsing callbacks we need */

-  routing->generic_routing.host_id = xbt_dict_new();

   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
   surfxml_add_callback(STag_surfxml_route_cb_list, 
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
   surfxml_add_callback(STag_surfxml_route_cb_list, 
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);

+  surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);

   
 }
 
   
 }
 


@@ -364,8 +554,9 @@ static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
 typedef struct {
   s_routing_t generic_routing;
   xbt_graph_t route_graph;
 typedef struct {
   s_routing_t generic_routing;
   xbt_graph_t route_graph;

-  xbt_set_t graph_node_map;
-  xbt_set_t route_cache;
+  xbt_dict_t graph_node_map;
+  xbt_dict_t route_cache;
+  xbt_dynar_t last_route;

   int cached;
   void *loopback;
   size_t size_of_link;
   int cached;
   void *loopback;
   size_t size_of_link;


@@ -374,18 +565,14 @@ typedef struct {
 
 typedef struct graph_node_data {
   int id; 
 
 typedef struct graph_node_data {
   int id; 

-  int graph_id; //used for caching internal id's
+  int graph_id; //used for caching internal graph id's

 } s_graph_node_data_t, * graph_node_data_t;
 
 typedef struct graph_node_map_element {
 } s_graph_node_data_t, * graph_node_data_t;
 
 typedef struct graph_node_map_element {

-  XBT_SET_HEADERS;
-

   xbt_node_t node;
 } s_graph_node_map_element_t, * graph_node_map_element_t;
 
 typedef struct route_cache_element {
   xbt_node_t node;
 } s_graph_node_map_element_t, * graph_node_map_element_t;
 
 typedef struct route_cache_element {

-  XBT_SET_HEADERS;
-

   int * pred_arr;
   int size;
 } s_route_cache_element_t, * route_cache_element_t;    
   int * pred_arr;
   int size;
 } s_route_cache_element_t, * route_cache_element_t;    


@@ -397,7 +584,6 @@ static void route_cache_elem_free(void *e) {
   route_cache_element_t elm=(route_cache_element_t)e;
 
   if (elm) {
   route_cache_element_t elm=(route_cache_element_t)e;
 
   if (elm) {

-    free(elm->name);

     free(elm->pred_arr);
     free(elm);
   }
     free(elm->pred_arr);
     free(elm);
   }


@@ -407,7 +593,6 @@ static void graph_node_map_elem_free(void *e) {
   graph_node_map_element_t elm = (graph_node_map_element_t)e;
 
   if(elm) {
   graph_node_map_element_t elm = (graph_node_map_element_t)e;
 
   if(elm) {

-    free(elm->name);

     free(elm);
   }
 }
     free(elm);
   }
 }


@@ -424,11 +609,8 @@ static xbt_node_t route_graph_new_node(int id, int graph_id) {
   xbt_node_t node = xbt_graph_new_node(routing->route_graph, data);
 
   graph_node_map_element_t elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
   xbt_node_t node = xbt_graph_new_node(routing->route_graph, data);
 
   graph_node_map_element_t elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));

-  elm->name_len = 0;
-  elm->name = bprintf("%d",id);

   elm->node = node;
   elm->node = node;

-
-  xbt_set_add(routing->graph_node_map, (xbt_set_elm_t)elm, &graph_node_map_elem_free);
+  xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);

 
   return node;
 }
 
   return node;
 }


@@ -436,9 +618,7 @@ static xbt_node_t route_graph_new_node(int id, int graph_id) {
 static graph_node_map_element_t graph_node_map_search(int id) {
   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 
 static graph_node_map_element_t graph_node_map_search(int id) {
   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 

-  char * id_str = bprintf("%d",id);
-  graph_node_map_element_t elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, id_str);
-  free(id_str);
+  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));

 
   return elm;
 }
 
   return elm;
 }


@@ -451,12 +631,8 @@ static void route_new_dijkstra(int src_id, int dst_id, void* link) {
 
   xbt_node_t src = NULL;
   xbt_node_t dst = NULL;
 
   xbt_node_t src = NULL;
   xbt_node_t dst = NULL;

-  char * src_id_str = bprintf("%d",src_id);
-  char * dst_id_str = bprintf("%d",dst_id);
-  graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, src_id_str);
-  graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, dst_id_str);
-  free(src_id_str);
-  free(dst_id_str);
+  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));
+  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));

 
   if(src_elm)
     src = src_elm->node;
 
   if(src_elm)
     src = src_elm->node;


@@ -512,18 +688,17 @@ static void add_loopback_dijkstra(void) {
 static void routing_dijkstra_parse_end(void) {
   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
   int nb_link = 0;
 static void routing_dijkstra_parse_end(void) {
   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
   int nb_link = 0;

-  unsigned int cpt = 0;

   xbt_dict_cursor_t cursor = NULL;
   char *key, *data, *end;
   const char *sep = "#";
   xbt_dynar_t links, keys;
   xbt_dict_cursor_t cursor = NULL;
   char *key, *data, *end;
   const char *sep = "#";
   xbt_dynar_t links, keys;

-  char *link_name = NULL;

 
   /* Create the topology graph */
   routing->route_graph = xbt_graph_new_graph(1, NULL);
 
   /* Create the topology graph */
   routing->route_graph = xbt_graph_new_graph(1, NULL);

-  routing->graph_node_map = xbt_set_new();
+  routing->graph_node_map = xbt_dict_new();
+  routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);

   if(routing->cached)
   if(routing->cached)

-    routing->route_cache = xbt_set_new();
+    routing->route_cache = xbt_dict_new();

 
 
   /* Put the routes in position */
 
 
   /* Put the routes in position */


@@ -541,13 +716,12 @@ static void routing_dijkstra_parse_end(void) {
 
     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
 
 
     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
 

-    xbt_dynar_foreach(links, cpt, link_name) {
-      void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
-      if (link)
-        route_new_dijkstra(src_id,dst_id,link);
-      else
-        THROW1(mismatch_error,0,"Link %s not found", link_name);
-    }
+    char* link_name = xbt_dynar_getfirst_as(links, char*);
+    void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
+    if (link)
+      route_new_dijkstra(src_id,dst_id,link);
+    else
+      THROW1(mismatch_error,0,"Link %s not found", link_name);

     
   }
 
     
   }
 


@@ -586,9 +760,7 @@ static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
   route_cache_element_t elm = NULL;
   if(routing->cached) {
     /*check if there is a cached predecessor list avail */
   route_cache_element_t elm = NULL;
   if(routing->cached) {
     /*check if there is a cached predecessor list avail */

-    char * src_id_str = bprintf("%d",src_id);
-    elm = (route_cache_element_t)xbt_set_get_by_name_or_null(routing->route_cache, src_id_str);
-    free(src_id_str);
+    elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));

   }
 
   if(elm) { //cached mode and cache hit
   }
 
   if(elm) { //cached mode and cache hit


@@ -653,7 +825,7 @@ static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
   }
 
   //compose route path with links
   }
 
   //compose route path with links

-  xbt_dynar_t link_list = xbt_dynar_new(routing->size_of_link, NULL);
+  xbt_dynar_reset(routing->last_route);

 
   int v;
   int size = 0;
 
   int v;
   int size = 0;


@@ -665,7 +837,7 @@ static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
 
     void * link = xbt_graph_edge_get_data(edge);
     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
 
     void * link = xbt_graph_edge_get_data(edge);

-    xbt_dynar_unshift(link_list, &link);
+    xbt_dynar_unshift(routing->last_route, &link);

     size++;
   }
 
     size++;
   }
 


@@ -673,31 +845,27 @@ static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
   if(routing->cached && elm == NULL) {
     //add to predecessor list of the current src-host to cache
     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
   if(routing->cached && elm == NULL) {
     //add to predecessor list of the current src-host to cache
     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));

-    elm->name = bprintf("%d",src_id);
-    elm->name_len = 0;

     elm->pred_arr = pred_arr;
     elm->size = size;
     elm->pred_arr = pred_arr;
     elm->size = size;

-    xbt_set_add(routing->route_cache, (xbt_set_elm_t)elm, &route_cache_elem_free);
+    xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);

   }
 
   if(!routing->cached)
     free(pred_arr);
 
   }
 
   if(!routing->cached)
     free(pred_arr);
 

-  return link_list;
+  return routing->last_route;

 }
 
 }
 

-static void routing_dijkstra_finalize_route(xbt_dynar_t route) {
-  xbt_dynar_free(&route);
-}

 
 static void routing_dijkstra_finalize(void) {
   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
 
   if (routing) {
     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
 
 static void routing_dijkstra_finalize(void) {
   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
 
   if (routing) {
     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);

-    xbt_set_free(&routing->graph_node_map);
+    xbt_dict_free(&routing->graph_node_map);

     if(routing->cached)
     if(routing->cached)

-      xbt_set_free(&routing->route_cache);
+      xbt_dict_free(&routing->route_cache);
+    xbt_dynar_free(&routing->last_route);

     xbt_dict_free(&used_routing->host_id);
     free(routing);
     routing=NULL;
     xbt_dict_free(&used_routing->host_id);
     free(routing);
     routing=NULL;


@@ -714,7 +882,6 @@ static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback
   routing->generic_routing.host_count = 0;
   routing->generic_routing.get_route = routing_dijkstra_get_route;
   routing->generic_routing.finalize = routing_dijkstra_finalize;
   routing->generic_routing.host_count = 0;
   routing->generic_routing.get_route = routing_dijkstra_get_route;
   routing->generic_routing.finalize = routing_dijkstra_finalize;

-  routing->generic_routing.finalize_route = routing_dijkstra_finalize_route;

   routing->size_of_link = size_of_link;
   routing->loopback = loopback;
   routing->cached = cached;
   routing->size_of_link = size_of_link;
   routing->loopback = loopback;
   routing->cached = cached;


@@ -729,6 +896,7 @@ static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback
   surfxml_add_callback(STag_surfxml_route_cb_list,
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
   surfxml_add_callback(STag_surfxml_route_cb_list,
       &routing_full_parse_Sroute_set_endpoints);
   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);

+  surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);

 }
 
 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
 }
 
 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {


@@ -738,3 +906,27 @@ static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
 }
 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
 }

+
+/* ************************************************** */
+/* ********** NO ROUTING **************************** */
+
+static void routing_none_finalize(void) {
+  if (used_routing) {
+    xbt_dict_free(&used_routing->host_id);
+    free(used_routing);
+    used_routing=NULL;
+  }
+}
+
+static void routing_model_none_create(size_t size_of_link,void *loopback) {
+  routing_t routing = xbt_new0(s_routing_t,1);
+  INFO0("Null routing");
+  routing->name = "none";
+  routing->host_count = 0;
+  routing->host_id = xbt_dict_new();
+  routing->get_route = NULL;
+  routing->finalize = routing_none_finalize;
+
+  /* Set it in position */
+  used_routing = (routing_t) routing;
+}