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