Logo AND Algorithmique Numérique Distribuée

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