src/surf/network.c

   1
   2 /*
   3  * Network with improved management of tasks, IM (Improved Management).
   4  * Uses a heap to store actions so that the share_resources is faster.
   5  * This model automatically sets the selective update flag to 1 and is
   6  * highly dependent on the maxmin lmm module.
   7  */
   8
   9 /* Copyright (c) 2009, 2010, 2011. The SimGrid Team.
  10  * All rights reserved.                                                     */
  11
  12 /* This program is free software; you can redistribute it and/or modify it
  13  * under the terms of the license (GNU LGPL) which comes with this package. */
  14
  15 #include "network_private.h"
  16 #include "xbt/log.h"
  17 #include "xbt/str.h"
  18
  19 #include "surf_private.h"
  20 #include "xbt/dict.h"
  21 #include "maxmin_private.h"
  22 #include "surf/surfxml_parse_values.h"
  23 #include "surf/surf_resource.h"
  24 #include "surf/surf_resource_lmm.h"
  25
  26 #undef GENERIC_ACTION
  27 #define GENERIC_ACTION(action) action->generic_action
  28
  29
  30 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_network, surf,
  31                                 "Logging specific to the SURF network module");
  32
  33 surf_model_t surf_network_model = NULL;
  34 static lmm_system_t network_maxmin_system = NULL;
  35 static void (*network_solve) (lmm_system_t) = NULL;
  36
  37 double sg_sender_gap = 0.0;
  38 double sg_latency_factor = 1.0; /* default value; can be set by model or from command line */
  39 double sg_bandwidth_factor = 1.0;       /* default value; can be set by model or from command line */
  40 double sg_weight_S_parameter = 0.0;     /* default value; can be set by model or from command line */
  41
  42 double sg_tcp_gamma = 0.0;
  43 int sg_network_crosstraffic = 0;
  44
  45 xbt_dict_t gap_lookup = NULL;
  46
  47 e_UM_t network_update_mechanism = UM_UNDEFINED;
  48 static int selective_update = 0;
  49
  50 static int net_action_is_suspended(surf_action_t action);
  51 static void update_action_remaining(double now);
  52
  53 static xbt_swag_t net_modified_set = NULL;
  54 static xbt_heap_t net_action_heap = NULL;
  55 xbt_swag_t keep_track = NULL;
  56
  57 /* added to manage the communication action's heap */
  58 static void net_action_update_index_heap(void *action, int i)
  59 {
  60   ((surf_action_network_CM02_t) action)->index_heap = i;
  61 }
  62
  63 /* insert action on heap using a given key and a hat (heap_action_type)
  64  * a hat can be of three types for communications:
  65  *
  66  * NORMAL = this is a normal heap entry stating the date to finish transmitting
  67  * LATENCY = this is a heap entry to warn us when the latency is payed
  68  * MAX_DURATION =this is a heap entry to warn us when the max_duration limit is reached
  69  */
  70 static void heap_insert(surf_action_network_CM02_t    action, double key, enum heap_action_type hat){
  71   action->hat = hat;
  72   xbt_heap_push(net_action_heap, action, key);
  73 }
  74
  75 static void heap_remove(surf_action_network_CM02_t action){
  76   action->hat = NONE;
  77   if(((surf_action_network_CM02_t) action)->index_heap >= 0){
  78       xbt_heap_remove(net_action_heap,action->index_heap);
  79   }
  80 }
  81
  82 /******************************************************************************/
  83 /*                           Factors callbacks                                */
  84 /******************************************************************************/
  85 static double constant_latency_factor(double size)
  86 {
  87   return sg_latency_factor;
  88 }
  89
  90 static double constant_bandwidth_factor(double size)
  91 {
  92   return sg_bandwidth_factor;
  93 }
  94
  95 static double constant_bandwidth_constraint(double rate, double bound,
  96                                             double size)
  97 {
  98   return rate;
  99 }
 100
 101
 102 /**********************/
 103 /*   SMPI callbacks   */
 104 /**********************/
 105 static double smpi_latency_factor(double size)
 106 {
 107   /* 1 B <= size <= 1 KiB */
 108   if (size <= 1024.0) {
 109     return 1.0056;
 110   }
 111
 112   /* 2 KiB <= size <= 32 KiB */
 113   if (size <= 32768.0) {
 114     return 1.8805;
 115   }
 116
 117   /* 64 KiB <= size <= 4 MiB */
 118   return 22.7111;
 119 }
 120
 121 static double smpi_bandwidth_factor(double size)
 122 {
 123   /* 1 B <= size <= 1 KiB */
 124   if (size <= 1024.0) {
 125     return 0.2758;
 126   }
 127
 128   /* 2 KiB <= size <= 32 KiB */
 129   if (size <= 32768.0) {
 130     return 0.5477;
 131   }
 132
 133   /* 64 KiB <= size <= 4 MiB */
 134   return 0.9359;
 135 }
 136
 137 static double smpi_bandwidth_constraint(double rate, double bound,
 138                                         double size)
 139 {
 140   return rate < 0 ? bound : min(bound, rate * smpi_bandwidth_factor(size));
 141 }
 142
 143 static double (*latency_factor_callback) (double) =
 144     &constant_latency_factor;
 145 static double (*bandwidth_factor_callback) (double) =
 146     &constant_bandwidth_factor;
 147 static double (*bandwidth_constraint_callback) (double, double, double) =
 148     &constant_bandwidth_constraint;
 149
 150 static void (*gap_append) (double, const link_CM02_t, surf_action_network_CM02_t) = NULL;
 151 static void (*gap_remove) (surf_action_network_CM02_t) = NULL;
 152
 153 static void* net_create_resource(const char *name,
 154                                 double bw_initial,
 155                                 tmgr_trace_t bw_trace,
 156                                 double lat_initial,
 157                                 tmgr_trace_t lat_trace,
 158                                 e_surf_resource_state_t
 159                                 state_initial,
 160                                 tmgr_trace_t state_trace,
 161                                 e_surf_link_sharing_policy_t
 162                                 policy, xbt_dict_t properties)
 163 {
 164   link_CM02_t nw_link = (link_CM02_t)
 165       surf_resource_lmm_new(sizeof(s_link_CM02_t),
 166                             surf_network_model, name, properties,
 167                             network_maxmin_system,
 168                             sg_bandwidth_factor * bw_initial,
 169                             history,
 170                             state_initial, state_trace,
 171                             bw_initial, bw_trace);
 172
 173   xbt_assert(!xbt_lib_get_or_null(link_lib, name, SURF_LINK_LEVEL),
 174               "Link '%s' declared several times in the platform file.",
 175               name);
 176
 177   nw_link->lat_current = lat_initial;
 178   if (lat_trace)
 179     nw_link->lat_event =
 180         tmgr_history_add_trace(history, lat_trace, 0.0, 0, nw_link);
 181
 182   if (policy == SURF_LINK_FATPIPE)
 183     lmm_constraint_shared(nw_link->lmm_resource.constraint);
 184
 185   xbt_lib_set(link_lib, name, SURF_LINK_LEVEL, nw_link);
 186
 187   return nw_link;
 188 }
 189
 190 static void net_parse_link_init(sg_platf_link_cbarg_t link)
 191 {
 192   if(link->policy == SURF_LINK_FULLDUPLEX){
 193     char *link_id;
 194     link_id = bprintf("%s_UP", link->id);
 195           net_create_resource(link_id,
 196                            link->bandwidth,
 197                            link->bandwidth_trace,
 198                            link->latency,
 199                            link->latency_trace,
 200                            link->state,
 201                            link->state_trace,
 202                            link->policy,
 203                            link->properties);
 204           xbt_free(link_id);
 205     link_id = bprintf("%s_DOWN", link->id);
 206     net_create_resource(link_id,
 207                         link->bandwidth,
 208                         link->bandwidth_trace,
 209                         link->latency,
 210                         link->latency_trace,
 211                         link->state,
 212                         link->state_trace,
 213                         link->policy,
 214                         link->properties);
 215     xbt_free(link_id);
 216   }
 217   else{
 218     net_create_resource(link->id,
 219                         link->bandwidth,
 220                         link->bandwidth_trace,
 221                         link->latency,
 222                         link->latency_trace,
 223                         link->state,
 224                         link->state_trace,
 225                         link->policy,
 226                         link->properties);
 227   }
 228 }
 229
 230 static void net_add_traces(void)
 231 {
 232   xbt_dict_cursor_t cursor = NULL;
 233   char *trace_name, *elm;
 234
 235   static int called = 0;
 236   if (called)
 237     return;
 238   called = 1;
 239
 240   /* connect all traces relative to network */
 241   xbt_dict_foreach(trace_connect_list_link_avail, cursor, trace_name, elm) {
 242     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 243     link_CM02_t link =
 244                 xbt_lib_get_or_null(link_lib, elm, SURF_LINK_LEVEL);
 245
 246     xbt_assert(link, "Cannot connect trace %s to link %s: link undefined",
 247                 trace_name, elm);
 248     xbt_assert(trace,
 249                 "Cannot connect trace %s to link %s: trace undefined",
 250                 trace_name, elm);
 251
 252     link->lmm_resource.state_event =
 253         tmgr_history_add_trace(history, trace, 0.0, 0, link);
 254   }
 255
 256   xbt_dict_foreach(trace_connect_list_bandwidth, cursor, trace_name, elm) {
 257     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 258     link_CM02_t link =
 259                 xbt_lib_get_or_null(link_lib, elm, SURF_LINK_LEVEL);
 260
 261     xbt_assert(link, "Cannot connect trace %s to link %s: link undefined",
 262                 trace_name, elm);
 263     xbt_assert(trace,
 264                 "Cannot connect trace %s to link %s: trace undefined",
 265                 trace_name, elm);
 266
 267     link->lmm_resource.power.event =
 268         tmgr_history_add_trace(history, trace, 0.0, 0, link);
 269   }
 270
 271   xbt_dict_foreach(trace_connect_list_latency, cursor, trace_name, elm) {
 272     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 273     link_CM02_t link =
 274                 xbt_lib_get_or_null(link_lib, elm, SURF_LINK_LEVEL);
 275
 276     xbt_assert(link, "Cannot connect trace %s to link %s: link undefined",
 277                 trace_name, elm);
 278     xbt_assert(trace,
 279                 "Cannot connect trace %s to link %s: trace undefined",
 280                 trace_name, elm);
 281
 282     link->lat_event = tmgr_history_add_trace(history, trace, 0.0, 0, link);
 283   }
 284 }
 285
 286 static void net_define_callbacks(void)
 287 {
 288   /* Figuring out the network links */
 289   sg_platf_link_add_cb(net_parse_link_init);
 290   sg_platf_postparse_add_cb(net_add_traces);
 291 }
 292
 293 static int net_resource_used(void *resource_id)
 294 {
 295   return lmm_constraint_used(network_maxmin_system,
 296                              ((surf_resource_lmm_t)
 297                               resource_id)->constraint);
 298 }
 299
 300 static int net_action_unref(surf_action_t action)
 301 {
 302   action->refcount--;
 303   if (!action->refcount) {
 304     xbt_swag_remove(action, action->state_set);
 305     if (((surf_action_network_CM02_t) action)->variable){
 306       lmm_variable_free(network_maxmin_system,
 307                         ((surf_action_network_CM02_t) action)->variable);
 308     }
 309     if(network_update_mechanism == UM_LAZY){// remove action from the heap
 310       heap_remove((surf_action_network_CM02_t) action);
 311       xbt_swag_remove(action, net_modified_set);
 312     }
 313 #ifdef HAVE_TRACING
 314     xbt_free(((surf_action_network_CM02_t) action)->src_name);
 315     xbt_free(((surf_action_network_CM02_t) action)->dst_name);
 316     xbt_free(action->category);
 317 #endif
 318     surf_action_free(&action);
 319     return 1;
 320   }
 321   return 0;
 322 }
 323
 324
 325
 326 static void net_action_cancel(surf_action_t action)
 327 {
 328   surf_network_model->action_state_set(action, SURF_ACTION_FAILED);
 329   if(network_update_mechanism == UM_LAZY){// remove action from the heap
 330     xbt_swag_remove(action, net_modified_set);
 331     heap_remove((surf_action_network_CM02_t) action);
 332   }
 333 }
 334
 335 void net_action_recycle(surf_action_t action)
 336 {
 337   return;
 338 }
 339
 340 #ifdef HAVE_LATENCY_BOUND_TRACKING
 341 static int net_get_link_latency_limited(surf_action_t action)
 342 {
 343   return action->latency_limited;
 344 }
 345 #endif
 346
 347 double net_action_get_remains(surf_action_t action)
 348 {
 349   if(network_update_mechanism == UM_LAZY)/* update remains before return it */
 350     update_action_remaining(surf_get_clock());
 351   return action->remains;
 352 }
 353
 354 static void update_action_remaining(double now){
 355   surf_action_network_CM02_t action = NULL;
 356   double delta = 0.0;
 357
 358   xbt_swag_foreach(action, net_modified_set) {
 359
 360     if(action->suspended != 0){
 361         continue;
 362     }
 363
 364     delta = now - action->last_update;
 365
 366     double_update(&(action->generic_action.remains),
 367                   lmm_variable_getvalue(action->variable) * delta);
 368
 369     if (action->generic_action.max_duration != NO_MAX_DURATION)
 370       double_update(&(action->generic_action.max_duration), delta);
 371
 372     if ((action->generic_action.remains <= 0) &&
 373         (lmm_get_variable_weight(action->variable) > 0)) {
 374       action->generic_action.finish = surf_get_clock();
 375       surf_network_model->action_state_set((surf_action_t) action,
 376                                            SURF_ACTION_DONE);
 377       heap_remove(action);
 378     } else if ((action->generic_action.max_duration != NO_MAX_DURATION)
 379                && (action->generic_action.max_duration <= 0)) {
 380       action->generic_action.finish = surf_get_clock();
 381       surf_network_model->action_state_set((surf_action_t) action,
 382                                            SURF_ACTION_DONE);
 383       heap_remove(action);
 384     }
 385
 386     action->last_update = now;
 387   }
 388 }
 389
 390 static double net_share_resources_full(double now)
 391 {
 392   s_surf_action_network_CM02_t s_action;
 393   surf_action_network_CM02_t action = NULL;
 394   xbt_swag_t running_actions =
 395       surf_network_model->states.running_action_set;
 396   double min;
 397
 398   min = generic_maxmin_share_resources(running_actions,
 399                                        xbt_swag_offset(s_action,
 400                                                        variable),
 401                                        network_maxmin_system,
 402                                        network_solve);
 403
 404 #define VARIABLE(action) (*((lmm_variable_t*)(((char *) (action)) + xbt_swag_offset(s_action, variable)  )))
 405
 406   xbt_swag_foreach(action, running_actions) {
 407 #ifdef HAVE_LATENCY_BOUND_TRACKING
 408     if (lmm_is_variable_limited_by_latency(action->variable)) {
 409       (action->generic_action).latency_limited = 1;
 410     } else {
 411       (action->generic_action).latency_limited = 0;
 412     }
 413 #endif
 414     if (action->latency > 0) {
 415       min = (min<0)?action->latency:min(min,action->latency);
 416     }
 417   }
 418
 419   XBT_DEBUG("Min of share resources %f", min);
 420
 421   return min;
 422 }
 423
 424 static double net_share_resources_lazy(double now)
 425 {
 426   surf_action_network_CM02_t action = NULL;
 427   double min=-1;
 428   double value;
 429
 430   XBT_DEBUG("Before share resources, the size of modified actions set is %d", xbt_swag_size(net_modified_set));
 431   update_action_remaining(now);
 432
 433   keep_track = net_modified_set;
 434   lmm_solve(network_maxmin_system);
 435   keep_track = NULL;
 436
 437   XBT_DEBUG("After share resources, The size of modified actions set is %d", xbt_swag_size(net_modified_set));
 438
 439   xbt_swag_foreach(action, net_modified_set) {
 440     int max_dur_flag = 0;
 441
 442     if (GENERIC_ACTION(action).state_set != surf_network_model->states.running_action_set){
 443       continue;
 444     }
 445
 446     /* bogus priority, skip it */
 447     if (GENERIC_ACTION(action).priority <= 0){
 448       continue;
 449     }
 450
 451     min = -1;
 452     value = lmm_variable_getvalue(action->variable);
 453     if (value > 0) {
 454       if (GENERIC_ACTION(action).remains > 0) {
 455         value = GENERIC_ACTION(action).remains / value;
 456         min = now + value;
 457       } else {
 458         value = 0.0;
 459         min = now;
 460       }
 461     }
 462
 463     if ((GENERIC_ACTION(action).max_duration != NO_MAX_DURATION)
 464         && (min == -1
 465             || GENERIC_ACTION(action).start +
 466             GENERIC_ACTION(action).max_duration < min)){
 467       min =   GENERIC_ACTION(action).start +
 468           GENERIC_ACTION(action).max_duration;
 469       max_dur_flag = 1;
 470     }
 471
 472     XBT_DEBUG("Action(%p) Start %lf Finish %lf Max_duration %lf", action,
 473         GENERIC_ACTION(action).start, now + value,
 474         GENERIC_ACTION(action).max_duration);
 475
 476     if (action->index_heap >= 0) {
 477       heap_remove((surf_action_network_CM02_t) action);
 478     }
 479
 480     if (min != -1) {
 481       heap_insert((surf_action_network_CM02_t) action, min, max_dur_flag?MAX_DURATION:NORMAL);
 482       XBT_DEBUG("Insert at heap action(%p) min %lf now %lf", action, min, now);
 483     }
 484   }
 485
 486   //hereafter must have already the min value for this resource model
 487   if(xbt_heap_size(net_action_heap) > 0 ){
 488     min = xbt_heap_maxkey(net_action_heap) - now ;
 489   }else{
 490     min = -1;
 491   }
 492
 493   XBT_DEBUG("The minimum with the HEAP %lf", min);
 494
 495   return min;
 496 }
 497
 498 static void net_update_actions_state_full(double now, double delta)
 499 {
 500   double deltap = 0.0;
 501   surf_action_network_CM02_t action = NULL;
 502   surf_action_network_CM02_t next_action = NULL;
 503   xbt_swag_t running_actions =
 504       surf_network_model->states.running_action_set;
 505   /*
 506      xbt_swag_t failed_actions =
 507      surf_network_model->states.failed_action_set;
 508    */
 509
 510   xbt_swag_foreach_safe(action, next_action, running_actions) {
 511     deltap = delta;
 512     if (action->latency > 0) {
 513       if (action->latency > deltap) {
 514         double_update(&(action->latency), deltap);
 515         deltap = 0.0;
 516       } else {
 517         double_update(&(deltap), action->latency);
 518         action->latency = 0.0;
 519       }
 520       if ((action->latency == 0.0) && !(action->suspended))
 521         lmm_update_variable_weight(network_maxmin_system, action->variable,
 522                                    action->weight);
 523     }
 524 #ifdef HAVE_TRACING
 525     if (TRACE_is_enabled()) {
 526       xbt_dynar_t route=NULL;
 527       routing_get_route_and_latency(action->src_name, action->dst_name,&route,NULL);
 528       link_CM02_t link;
 529       unsigned int i;
 530       xbt_dynar_foreach(route, i, link) {
 531         TRACE_surf_link_set_utilization(link->lmm_resource.generic_resource.name,
 532                                         action->generic_action.data,
 533                                         (surf_action_t) action,
 534                                         lmm_variable_getvalue
 535                                         (action->variable), now - delta,
 536                                         delta);
 537       }
 538     }
 539 #endif
 540     if(!lmm_get_number_of_cnst_from_var(network_maxmin_system, action->variable)) {
 541         /* There is actually no link used, hence an infinite bandwidth.
 542          * This happens often when using models like vivaldi.
 543          * In such case, just make sure that the action completes immediately.
 544          */
 545       double_update(&(action->generic_action.remains),
 546           action->generic_action.remains);
 547     }
 548     double_update(&(action->generic_action.remains),
 549                   lmm_variable_getvalue(action->variable) * deltap);
 550     if (action->generic_action.max_duration != NO_MAX_DURATION)
 551       double_update(&(action->generic_action.max_duration), delta);
 552
 553     if ((action->generic_action.remains <= 0) &&
 554         (lmm_get_variable_weight(action->variable) > 0)) {
 555       action->generic_action.finish = surf_get_clock();
 556       surf_network_model->action_state_set((surf_action_t) action,
 557                                            SURF_ACTION_DONE);
 558
 559       if(gap_remove) gap_remove(action);
 560     } else if ((action->generic_action.max_duration != NO_MAX_DURATION)
 561                && (action->generic_action.max_duration <= 0)) {
 562       action->generic_action.finish = surf_get_clock();
 563       surf_network_model->action_state_set((surf_action_t) action,
 564                                            SURF_ACTION_DONE);
 565       if(gap_remove) gap_remove(action);
 566     }
 567   }
 568
 569   return;
 570 }
 571
 572 static void net_update_actions_state_lazy(double now, double delta)
 573 {
 574   surf_action_network_CM02_t action = NULL;
 575
 576   while ((xbt_heap_size(net_action_heap) > 0)
 577          && (double_equals(xbt_heap_maxkey(net_action_heap), now))) {
 578     action = xbt_heap_pop(net_action_heap);
 579     XBT_DEBUG("Action %p: finish", action);
 580     GENERIC_ACTION(action).finish = surf_get_clock();
 581
 582     // if I am wearing a latency heat
 583     if( action->hat ==  LATENCY){
 584         lmm_update_variable_weight(network_maxmin_system, action->variable,
 585                                            action->weight);
 586         heap_remove(action);
 587         action->last_update = surf_get_clock();
 588
 589     // if I am wearing a max_duration or normal hat
 590     }else if( action->hat == MAX_DURATION || action->hat == NORMAL ){
 591         // no need to communicate anymore
 592         // assume that flows that reached max_duration have remaining of 0
 593         GENERIC_ACTION(action).remains = 0;
 594         action->generic_action.finish = surf_get_clock();
 595               surf_network_model->action_state_set((surf_action_t) action,
 596                                                    SURF_ACTION_DONE);
 597         heap_remove(action);
 598     }
 599   }
 600   return;
 601 }
 602
 603 static void net_update_resource_state(void *id,
 604                                       tmgr_trace_event_t event_type,
 605                                       double value, double date)
 606 {
 607   link_CM02_t nw_link = id;
 608   /*   printf("[" "%lg" "] Asking to update network card \"%s\" with value " */
 609   /*     "%lg" " for event %p\n", surf_get_clock(), nw_link->name, */
 610   /*     value, event_type); */
 611
 612   if (event_type == nw_link->lmm_resource.power.event) {
 613     double delta =
 614         sg_weight_S_parameter / value - sg_weight_S_parameter /
 615         (nw_link->lmm_resource.power.peak *
 616          nw_link->lmm_resource.power.scale);
 617     lmm_variable_t var = NULL;
 618     lmm_element_t elem = NULL;
 619     surf_action_network_CM02_t action = NULL;
 620
 621     nw_link->lmm_resource.power.peak = value;
 622     lmm_update_constraint_bound(network_maxmin_system,
 623                                 nw_link->lmm_resource.constraint,
 624                                 sg_bandwidth_factor *
 625                                 (nw_link->lmm_resource.power.peak *
 626                                  nw_link->lmm_resource.power.scale));
 627 #ifdef HAVE_TRACING
 628     TRACE_surf_link_set_bandwidth(date, (char *)(((nw_link->lmm_resource).generic_resource).name),
 629                                   sg_bandwidth_factor *
 630                                   (nw_link->lmm_resource.power.peak *
 631                                    nw_link->lmm_resource.power.scale));
 632 #endif
 633     if (sg_weight_S_parameter > 0) {
 634       while ((var = lmm_get_var_from_cnst
 635               (network_maxmin_system, nw_link->lmm_resource.constraint,
 636                &elem))) {
 637         action = lmm_variable_id(var);
 638         action->weight += delta;
 639         if (!(action->suspended))
 640           lmm_update_variable_weight(network_maxmin_system,
 641                                      action->variable, action->weight);
 642       }
 643     }
 644     if (tmgr_trace_event_free(event_type))
 645       nw_link->lmm_resource.power.event = NULL;
 646   } else if (event_type == nw_link->lat_event) {
 647     double delta = value - nw_link->lat_current;
 648     lmm_variable_t var = NULL;
 649     lmm_element_t elem = NULL;
 650     surf_action_network_CM02_t action = NULL;
 651
 652     nw_link->lat_current = value;
 653     while ((var = lmm_get_var_from_cnst
 654             (network_maxmin_system, nw_link->lmm_resource.constraint,
 655              &elem))) {
 656       action = lmm_variable_id(var);
 657       action->lat_current += delta;
 658       action->weight += delta;
 659       if (action->rate < 0)
 660         lmm_update_variable_bound(network_maxmin_system, action->variable,
 661                                   sg_tcp_gamma / (2.0 *
 662                                                   action->lat_current));
 663       else {
 664         lmm_update_variable_bound(network_maxmin_system, action->variable,
 665                                   min(action->rate,
 666                                       sg_tcp_gamma / (2.0 *
 667                                                       action->lat_current)));
 668
 669         if (action->rate < sg_tcp_gamma / (2.0 * action->lat_current)) {
 670           XBT_INFO("Flow is limited BYBANDWIDTH");
 671         } else {
 672           XBT_INFO("Flow is limited BYLATENCY, latency of flow is %f",
 673                 action->lat_current);
 674         }
 675       }
 676       if (!(action->suspended))
 677         lmm_update_variable_weight(network_maxmin_system, action->variable,
 678                                    action->weight);
 679
 680     }
 681     if (tmgr_trace_event_free(event_type))
 682       nw_link->lat_event = NULL;
 683   } else if (event_type == nw_link->lmm_resource.state_event) {
 684     if (value > 0)
 685       nw_link->lmm_resource.state_current = SURF_RESOURCE_ON;
 686     else {
 687       lmm_constraint_t cnst = nw_link->lmm_resource.constraint;
 688       lmm_variable_t var = NULL;
 689       lmm_element_t elem = NULL;
 690
 691       nw_link->lmm_resource.state_current = SURF_RESOURCE_OFF;
 692       while ((var = lmm_get_var_from_cnst
 693               (network_maxmin_system, cnst, &elem))) {
 694         surf_action_t action = lmm_variable_id(var);
 695
 696         if (surf_action_state_get(action) == SURF_ACTION_RUNNING ||
 697             surf_action_state_get(action) == SURF_ACTION_READY) {
 698           action->finish = date;
 699           surf_network_model->action_state_set(action, SURF_ACTION_FAILED);
 700         }
 701       }
 702     }
 703     if (tmgr_trace_event_free(event_type))
 704       nw_link->lmm_resource.state_event = NULL;
 705   } else {
 706     XBT_CRITICAL("Unknown event ! \n");
 707     xbt_abort();
 708   }
 709
 710   XBT_DEBUG("There were a resource state event, need to update actions related to the constraint (%p)", nw_link->lmm_resource.constraint);
 711   return;
 712 }
 713
 714
 715 static surf_action_t net_communicate(const char *src_name,
 716                                      const char *dst_name, double size,
 717                                      double rate)
 718 {
 719   unsigned int i;
 720   link_CM02_t link;
 721   int failed = 0;
 722   surf_action_network_CM02_t action = NULL;
 723   double bandwidth_bound;
 724   double latency=0.0;
 725   xbt_dynar_t back_route = NULL;
 726   int constraints_per_variable = 0;
 727
 728   xbt_dynar_t route=xbt_dynar_new(global_routing->size_of_link,NULL);
 729
 730   XBT_IN("(%s,%s,%g,%g)", src_name, dst_name, size, rate);
 731
 732   routing_get_route_and_latency(src_name, dst_name, &route, &latency);
 733   xbt_assert(!xbt_dynar_is_empty(route) || latency,
 734               "You're trying to send data from %s to %s but there is no connection at all between these two hosts.",
 735               src_name, dst_name);
 736
 737   xbt_dynar_foreach(route, i, link) {
 738     if (link->lmm_resource.state_current == SURF_RESOURCE_OFF) {
 739       failed = 1;
 740       break;
 741     }
 742   }
 743   if (sg_network_crosstraffic == 1) {
 744     routing_get_route_and_latency(dst_name, src_name, &back_route,NULL);
 745     xbt_dynar_foreach(back_route, i, link) {
 746       if (link->lmm_resource.state_current == SURF_RESOURCE_OFF) {
 747         failed = 1;
 748         break;
 749       }
 750     }
 751   }
 752
 753   action =
 754       surf_action_new(sizeof(s_surf_action_network_CM02_t), size,
 755                       surf_network_model, failed);
 756 #ifdef HAVE_LATENCY_BOUND_TRACKING
 757   (action->generic_action).latency_limited = 0;
 758 #endif
 759   action->weight = action->latency = latency;
 760
 761   xbt_swag_insert(action, action->generic_action.state_set);
 762   action->rate = rate;
 763   if(network_update_mechanism == UM_LAZY){
 764     action->index_heap = -1;
 765     action->last_update = surf_get_clock();
 766   }
 767
 768   bandwidth_bound = -1.0;
 769   if(sg_weight_S_parameter>0) {
 770     xbt_dynar_foreach(route, i, link) {
 771       action->weight +=
 772           sg_weight_S_parameter /
 773           (link->lmm_resource.power.peak * link->lmm_resource.power.scale);
 774     }
 775   }
 776   xbt_dynar_foreach(route, i, link) {
 777     double bb = bandwidth_factor_callback(size) *
 778         (link->lmm_resource.power.peak * link->lmm_resource.power.scale);
 779     bandwidth_bound = (bandwidth_bound < 0.0)?bb:min(bandwidth_bound,bb);
 780   }
 781
 782   action->lat_current = action->latency;
 783   action->latency *= latency_factor_callback(size);
 784   action->rate =
 785       bandwidth_constraint_callback(action->rate, bandwidth_bound,
 786                                         size);
 787   if(gap_append) {
 788     xbt_assert(!xbt_dynar_is_empty(route),"Using a model with a gap (e.g., SMPI) with a platform without links (e.g. vivaldi)!!!");
 789
 790     link = *(link_CM02_t*)xbt_dynar_get_ptr(route, 0);
 791     gap_append(size, link, action);
 792     XBT_DEBUG("Comm %p: %s -> %s gap=%f (lat=%f)",
 793            action, src_name, dst_name, action->sender.gap, action->latency);
 794   }
 795
 796   constraints_per_variable = xbt_dynar_length(route);
 797   if (back_route != NULL)
 798     constraints_per_variable += xbt_dynar_length(back_route);
 799
 800   if (action->latency > 0){
 801       action->variable =
 802         lmm_variable_new(network_maxmin_system, action, 0.0, -1.0,
 803                          constraints_per_variable);
 804     if(network_update_mechanism == UM_LAZY){
 805       // add to the heap the event when the latency is payed
 806       XBT_DEBUG("Added action (%p) one latency event at date %f", action, action->latency + action->last_update);
 807       heap_insert(action, action->latency + action->last_update, xbt_dynar_is_empty(route)?NORMAL:LATENCY);
 808     }
 809   } else
 810     action->variable =
 811         lmm_variable_new(network_maxmin_system, action, 1.0, -1.0,
 812                          constraints_per_variable);
 813
 814   if (action->rate < 0) {
 815     lmm_update_variable_bound(network_maxmin_system, action->variable,
 816         (action->lat_current > 0)?
 817             sg_tcp_gamma / (2.0 * action->lat_current)  :-1.0);
 818   } else {
 819     lmm_update_variable_bound(network_maxmin_system, action->variable,
 820         (action->lat_current > 0)?
 821             min(action->rate, sg_tcp_gamma / (2.0 * action->lat_current))
 822             :action->rate);
 823   }
 824
 825   xbt_dynar_foreach(route, i, link) {
 826     lmm_expand(network_maxmin_system, link->lmm_resource.constraint,
 827                action->variable, 1.0);
 828   }
 829
 830   if (sg_network_crosstraffic == 1) {
 831     XBT_DEBUG("Fullduplex active adding backward flow using 5%%");
 832     xbt_dynar_foreach(back_route, i, link) {
 833       lmm_expand(network_maxmin_system, link->lmm_resource.constraint,
 834                  action->variable, .05);
 835     }
 836   }
 837
 838 #ifdef HAVE_TRACING
 839   if (TRACE_is_enabled()) {
 840     action->src_name = xbt_strdup(src_name);
 841     action->dst_name = xbt_strdup(dst_name);
 842   } else {
 843     action->src_name = action->dst_name = NULL;
 844   }
 845 #endif
 846
 847   xbt_dynar_free(&route);
 848   XBT_OUT();
 849
 850   return (surf_action_t) action;
 851 }
 852
 853 static xbt_dynar_t net_get_route(const char *src, const char *dst)
 854 {
 855   xbt_dynar_t route=NULL;
 856   routing_get_route_and_latency(src, dst,&route,NULL);
 857   return route;
 858 }
 859
 860 static double net_get_link_bandwidth(const void *link)
 861 {
 862   surf_resource_lmm_t lmm = (surf_resource_lmm_t) link;
 863   return lmm->power.peak * lmm->power.scale;
 864 }
 865
 866 static double net_get_link_latency(const void *link)
 867 {
 868   return ((link_CM02_t) link)->lat_current;
 869 }
 870
 871 static int net_link_shared(const void *link)
 872 {
 873   return
 874       lmm_constraint_is_shared(((surf_resource_lmm_t) link)->constraint);
 875 }
 876
 877 static void net_action_suspend(surf_action_t action)
 878 {
 879   ((surf_action_network_CM02_t) action)->suspended = 1;
 880   lmm_update_variable_weight(network_maxmin_system,
 881                              ((surf_action_network_CM02_t)
 882                               action)->variable, 0.0);
 883
 884   if(network_update_mechanism == UM_LAZY)// remove action from the heap
 885     heap_remove((surf_action_network_CM02_t) action);
 886 }
 887
 888 static void net_action_resume(surf_action_t action)
 889 {
 890   if (((surf_action_network_CM02_t) action)->suspended) {
 891     lmm_update_variable_weight(network_maxmin_system,
 892                                ((surf_action_network_CM02_t)
 893                                 action)->variable,
 894                                ((surf_action_network_CM02_t)
 895                                 action)->weight);
 896     ((surf_action_network_CM02_t) action)->suspended = 0;
 897     if(network_update_mechanism == UM_LAZY)// remove action from the heap
 898       heap_remove((surf_action_network_CM02_t) action);
 899   }
 900 }
 901
 902 static int net_action_is_suspended(surf_action_t action)
 903 {
 904   return ((surf_action_network_CM02_t) action)->suspended;
 905 }
 906
 907 void net_action_set_max_duration(surf_action_t action, double duration)
 908 {
 909   action->max_duration = duration;
 910   if(network_update_mechanism == UM_LAZY)// remove action from the heap
 911     heap_remove((surf_action_network_CM02_t) action);
 912 }
 913
 914 #ifdef HAVE_TRACING
 915 static void net_action_set_category(surf_action_t action, const char *category)
 916 {
 917   action->category = xbt_strdup (category);
 918 }
 919 #endif
 920
 921 static void net_finalize(void)
 922 {
 923   surf_model_exit(surf_network_model);
 924   surf_network_model = NULL;
 925
 926   lmm_system_free(network_maxmin_system);
 927   network_maxmin_system = NULL;
 928
 929   if(network_update_mechanism == UM_LAZY){
 930     xbt_heap_free(net_action_heap);
 931     xbt_swag_free(net_modified_set);
 932   }
 933 }
 934
 935 static void smpi_gap_append(double size, const link_CM02_t link, surf_action_network_CM02_t action) {
 936    const char* src = link->lmm_resource.generic_resource.name;
 937    xbt_fifo_t fifo;
 938    surf_action_network_CM02_t last_action;
 939    double bw;
 940
 941    if(sg_sender_gap > 0.0) {
 942       if(!gap_lookup) {
 943          gap_lookup = xbt_dict_new();
 944       }
 945       fifo = (xbt_fifo_t)xbt_dict_get_or_null(gap_lookup, src);
 946       action->sender.gap = 0.0;
 947       if(fifo && xbt_fifo_size(fifo) > 0) {
 948          /* Compute gap from last send */
 949          last_action = (surf_action_network_CM02_t)xbt_fifo_get_item_content(xbt_fifo_get_last_item(fifo));
 950          bw = net_get_link_bandwidth(link);
 951          action->sender.gap = last_action->sender.gap + max(sg_sender_gap, last_action->sender.size / bw);
 952          action->latency += action->sender.gap;
 953       }
 954       /* Append action as last send */
 955       action->sender.link_name = link->lmm_resource.generic_resource.name;
 956       fifo = (xbt_fifo_t)xbt_dict_get_or_null(gap_lookup, action->sender.link_name);
 957       if(!fifo) {
 958          fifo = xbt_fifo_new();
 959          xbt_dict_set(gap_lookup, action->sender.link_name, fifo, NULL);
 960       }
 961       action->sender.fifo_item = xbt_fifo_push(fifo, action);
 962       action->sender.size = size;
 963    }
 964 }
 965
 966 static void smpi_gap_remove(surf_action_network_CM02_t action) {
 967    xbt_fifo_t fifo;
 968    size_t size;
 969
 970    if(sg_sender_gap > 0.0 && action->sender.link_name && action->sender.fifo_item) {
 971       fifo = (xbt_fifo_t)xbt_dict_get_or_null(gap_lookup, action->sender.link_name);
 972       xbt_fifo_remove_item(fifo, action->sender.fifo_item);
 973       size = xbt_fifo_size(fifo);
 974       if(size == 0) {
 975          xbt_fifo_free(fifo);
 976          xbt_dict_remove(gap_lookup, action->sender.link_name);
 977          size = xbt_dict_length(gap_lookup);
 978          if(size == 0) {
 979             xbt_dict_free(&gap_lookup);
 980          }
 981       }
 982    }
 983 }
 984
 985 static void surf_network_model_init_internal(void)
 986 {
 987   s_surf_action_network_CM02_t comm;
 988   surf_network_model = surf_model_init();
 989
 990   surf_network_model->name = "network";
 991   surf_network_model->action_unref = net_action_unref;
 992   surf_network_model->action_cancel = net_action_cancel;
 993   surf_network_model->action_recycle = net_action_recycle;
 994   surf_network_model->get_remains = net_action_get_remains;
 995 #ifdef HAVE_LATENCY_BOUND_TRACKING
 996   surf_network_model->get_latency_limited = net_get_link_latency_limited;
 997 #endif
 998
 999   surf_network_model->model_private->resource_used = net_resource_used;
1000   if(network_update_mechanism == UM_LAZY) {
1001     surf_network_model->model_private->share_resources = net_share_resources_lazy;
1002     surf_network_model->model_private->update_actions_state = net_update_actions_state_lazy;
1003   } else if(network_update_mechanism == UM_FULL) {
1004     surf_network_model->model_private->share_resources = net_share_resources_full;
1005     surf_network_model->model_private->update_actions_state = net_update_actions_state_full;
1006   }
1007
1008   surf_network_model->model_private->update_resource_state =
1009                   net_update_resource_state;
1010   surf_network_model->model_private->finalize = net_finalize;
1011
1012   surf_network_model->suspend = net_action_suspend;
1013   surf_network_model->resume = net_action_resume;
1014   surf_network_model->is_suspended = net_action_is_suspended;
1015   surf_cpu_model->set_max_duration = net_action_set_max_duration;
1016
1017   surf_network_model->extension.network.communicate = net_communicate;
1018   surf_network_model->extension.network.get_route = net_get_route;
1019   surf_network_model->extension.network.get_link_bandwidth =
1020                   net_get_link_bandwidth;
1021   surf_network_model->extension.network.get_link_latency =
1022                   net_get_link_latency;
1023   surf_network_model->extension.network.link_shared = net_link_shared;
1024   surf_network_model->extension.network.add_traces = net_add_traces;
1025   surf_network_model->extension.network.create_resource =
1026                   net_create_resource;
1027
1028  if (!network_maxmin_system)
1029     network_maxmin_system = lmm_system_new(selective_update);
1030
1031  routing_model_create(sizeof(link_CM02_t),
1032       net_create_resource("__loopback__",
1033           498000000, NULL, 0.000015, NULL,
1034           SURF_RESOURCE_ON, NULL,
1035           SURF_LINK_FATPIPE, NULL));
1036
1037   if(network_update_mechanism == UM_LAZY){
1038     net_action_heap = xbt_heap_new(8,NULL);
1039     xbt_heap_set_update_callback(net_action_heap, net_action_update_index_heap);
1040     net_modified_set =
1041         xbt_swag_new(xbt_swag_offset(comm, action_list_hookup));
1042   }
1043 }
1044
1045 static void set_update_mechanism(void) {
1046   char *optim = xbt_cfg_get_string(_surf_cfg_set, "network/optim");
1047   int select = xbt_cfg_get_int(_surf_cfg_set, "network/maxmin_selective_update");
1048
1049   if(!strcmp(optim,"Full")) {
1050     network_update_mechanism = UM_FULL;
1051     selective_update = select;
1052   } else if (!strcmp(optim,"Lazy")) {
1053     network_update_mechanism = UM_LAZY;
1054     selective_update = 1;
1055     xbt_assert((select==1) || (xbt_cfg_is_default_value(_surf_cfg_set,"network/maxmin_selective_update")),
1056         "Disabling selective update while using the lazy update mechanism is dumb!");
1057   } else {
1058     xbt_die("Unsupported optimization (%s) for this model",optim);
1059   }
1060 }
1061
1062 /************************************************************************/
1063 /* New model based on LV08 and experimental results of MPI ping-pongs   */
1064 /************************************************************************/
1065 /* @Inproceedings{smpi_ipdps, */
1066 /*  author={Pierre-Nicolas Clauss and Mark Stillwell and Stéphane Genaud and Frédéric Suter and Henri Casanova and Martin Quinson}, */
1067 /*  title={Single Node On-Line Simulation of {MPI} Applications with SMPI}, */
1068 /*  booktitle={25th IEEE International Parallel and Distributed Processing Symposium (IPDPS'11)}, */
1069 /*  address={Anchorage (Alaska) USA}, */
1070 /*  month=may, */
1071 /*  year={2011} */
1072 /*  } */
1073 void surf_network_model_init_SMPI(void)
1074 {
1075
1076   if (surf_network_model)
1077     return;
1078   set_update_mechanism();
1079
1080   surf_network_model_init_internal();
1081   latency_factor_callback = &smpi_latency_factor;
1082   bandwidth_factor_callback = &smpi_bandwidth_factor;
1083   bandwidth_constraint_callback = &smpi_bandwidth_constraint;
1084   gap_append = &smpi_gap_append;
1085   gap_remove = &smpi_gap_remove;
1086   net_define_callbacks();
1087   xbt_dynar_push(model_list, &surf_network_model);
1088   network_solve = lmm_solve;
1089
1090   xbt_cfg_setdefault_double(_surf_cfg_set, "network/sender_gap", 10e-6);
1091   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S", 8775);
1092 }
1093
1094 /************************************************************************/
1095 /* New model based on optimizations discussed during Pedro Velho's thesis*/
1096 /************************************************************************/
1097 /* @techreport{VELHO:2011:HAL-00646896:1, */
1098 /*      url = {http://hal.inria.fr/hal-00646896/en/}, */
1099 /*      title = {{Flow-level network models: have we reached the limits?}}, */
1100 /*      author = {Velho, Pedro and Schnorr, Lucas and Casanova, Henri and Legrand, Arnaud}, */
1101 /*      type = {Rapport de recherche}, */
1102 /*      institution = {INRIA}, */
1103 /*      number = {RR-7821}, */
1104 /*      year = {2011}, */
1105 /*      month = Nov, */
1106 /*      pdf = {http://hal.inria.fr/hal-00646896/PDF/rr-validity.pdf}, */
1107 /*  } */
1108 void surf_network_model_init_LegrandVelho(void)
1109 {
1110   char *model = xbt_cfg_get_string(_surf_cfg_set, "network/model");
1111
1112   if (surf_network_model)
1113     return;
1114
1115   if(!strcmp(model,"LV08_fullupdate")) {
1116     XBT_WARN("[*Deprecated*. Use --cfg=network/model:LV08 with option --cfg=network/optim:Full instead.]");
1117   }
1118   set_update_mechanism();
1119
1120   surf_network_model_init_internal();
1121   net_define_callbacks();
1122   xbt_dynar_push(model_list, &surf_network_model);
1123   network_solve = lmm_solve;
1124
1125   xbt_cfg_setdefault_double(_surf_cfg_set, "network/latency_factor", 10.4); // 13.01 when callibration is done without phase effects
1126   xbt_cfg_setdefault_double(_surf_cfg_set, "network/bandwidth_factor",0.92);// 0.97 when callibration is done without phase effects
1127   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S", 8775);       // 20537 when callibration is done without phase effects
1128 }
1129
1130 /***************************************************************************/
1131 /* The nice TCP sharing model designed by Loris Marchal and Henri Casanova */
1132 /***************************************************************************/
1133 /* @TechReport{      rr-lip2002-40, */
1134 /*   author        = {Henri Casanova and Loris Marchal}, */
1135 /*   institution   = {LIP}, */
1136 /*   title         = {A Network Model for Simulation of Grid Application}, */
1137 /*   number        = {2002-40}, */
1138 /*   month         = {oct}, */
1139 /*   year          = {2002} */
1140 /* } */
1141 void surf_network_model_init_CM02(void)
1142 {
1143
1144   if (surf_network_model)
1145     return;
1146
1147   set_update_mechanism();
1148   surf_network_model_init_internal();
1149   net_define_callbacks();
1150   xbt_dynar_push(model_list, &surf_network_model);
1151   network_solve = lmm_solve;
1152
1153   xbt_cfg_setdefault_double(_surf_cfg_set, "network/latency_factor", 1.0);
1154   xbt_cfg_setdefault_double(_surf_cfg_set, "network/bandwidth_factor", 1.0);
1155   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S", 0.0);
1156 }
1157
1158 /***************************************************************************/
1159 /* The models from Steven H. Low                                           */
1160 /***************************************************************************/
1161 /* @article{Low03,                                                         */
1162 /*   author={Steven H. Low},                                               */
1163 /*   title={A Duality Model of {TCP} and Queue Management Algorithms},     */
1164 /*   year={2003},                                                          */
1165 /*   journal={{IEEE/ACM} Transactions on Networking},                      */
1166 /*    volume={11}, number={4},                                             */
1167 /*  }                                                                      */
1168 void surf_network_model_init_Reno(void)
1169 {
1170   if (surf_network_model)
1171     return;
1172
1173   set_update_mechanism();
1174   surf_network_model_init_internal();
1175   net_define_callbacks();
1176
1177   xbt_dynar_push(model_list, &surf_network_model);
1178   lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
1179                                     func_reno_fpi);
1180   network_solve = lagrange_solve;
1181
1182   xbt_cfg_setdefault_double(_surf_cfg_set, "network/latency_factor", 10.4);
1183   xbt_cfg_setdefault_double(_surf_cfg_set, "network/bandwidth_factor",
1184                             0.92);
1185   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S", 8775);
1186 }
1187
1188
1189 void surf_network_model_init_Reno2(void)
1190 {
1191   if (surf_network_model)
1192     return;
1193
1194   set_update_mechanism();
1195   surf_network_model_init_internal();
1196   net_define_callbacks();
1197
1198   xbt_dynar_push(model_list, &surf_network_model);
1199   lmm_set_default_protocol_function(func_reno2_f, func_reno2_fp,
1200                                     func_reno2_fpi);
1201   network_solve = lagrange_solve;
1202
1203   xbt_cfg_setdefault_double(_surf_cfg_set, "network/latency_factor", 10.4);
1204   xbt_cfg_setdefault_double(_surf_cfg_set, "network/bandwidth_factor",
1205                             0.92);
1206   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S_parameter",
1207                             8775);
1208 }
1209
1210 void surf_network_model_init_Vegas(void)
1211 {
1212   if (surf_network_model)
1213     return;
1214
1215   set_update_mechanism();
1216   surf_network_model_init_internal();
1217   net_define_callbacks();
1218
1219   xbt_dynar_push(model_list, &surf_network_model);
1220   lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
1221                                     func_vegas_fpi);
1222   network_solve = lagrange_solve;
1223
1224   xbt_cfg_setdefault_double(_surf_cfg_set, "network/latency_factor", 10.4);
1225   xbt_cfg_setdefault_double(_surf_cfg_set, "network/bandwidth_factor",
1226                             0.92);
1227   xbt_cfg_setdefault_double(_surf_cfg_set, "network/weight_S", 8775);
1228 }