Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Replace surf by surf++ and make it compile
[simgrid.git] / src / surf / network.cpp
1 #include "network.hpp"
2 #include "maxmin_private.h"
3 #include "simgrid/sg_config.h"
4
5 extern "C" {
6 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_network, surf,
7                                 "Logging specific to the SURF network module");
8 }
9
10 NetworkCm02ModelPtr surf_network_model = NULL;
11
12 double sg_sender_gap = 0.0;
13 double sg_latency_factor = 1.0; /* default value; can be set by model or from command line */
14 double sg_bandwidth_factor = 1.0;       /* default value; can be set by model or from command line */
15 double sg_weight_S_parameter = 0.0;     /* default value; can be set by model or from command line */
16
17 double sg_tcp_gamma = 0.0;
18 int sg_network_crosstraffic = 0;
19
20 /*********
21  * Model *
22  *********/
23
24 /************************************************************************/
25 /* New model based on optimizations discussed during Pedro Velho's thesis*/
26 /************************************************************************/
27 /* @techreport{VELHO:2011:HAL-00646896:1, */
28 /*      url = {http://hal.inria.fr/hal-00646896/en/}, */
29 /*      title = {{Flow-level network models: have we reached the limits?}}, */
30 /*      author = {Velho, Pedro and Schnorr, Lucas and Casanova, Henri and Legrand, Arnaud}, */
31 /*      type = {Rapport de recherche}, */
32 /*      institution = {INRIA}, */
33 /*      number = {RR-7821}, */
34 /*      year = {2011}, */
35 /*      month = Nov, */
36 /*      pdf = {http://hal.inria.fr/hal-00646896/PDF/rr-validity.pdf}, */
37 /*  } */
38 void surf_network_model_init_LegrandVelho(void)
39 {
40   if (surf_network_model)
41     return;
42
43   surf_network_model = new NetworkCm02Model();
44   xbt_dynar_push(model_list, &surf_network_model);
45
46   xbt_cfg_setdefault_double(_sg_cfg_set, "network/latency_factor",
47                             13.01);
48   xbt_cfg_setdefault_double(_sg_cfg_set, "network/bandwidth_factor",
49                             0.97);
50   xbt_cfg_setdefault_double(_sg_cfg_set, "network/weight_S", 20537);
51 }
52
53 /***************************************************************************/
54 /* The nice TCP sharing model designed by Loris Marchal and Henri Casanova */
55 /***************************************************************************/
56 /* @TechReport{      rr-lip2002-40, */
57 /*   author        = {Henri Casanova and Loris Marchal}, */
58 /*   institution   = {LIP}, */
59 /*   title         = {A Network Model for Simulation of Grid Application}, */
60 /*   number        = {2002-40}, */
61 /*   month         = {oct}, */
62 /*   year          = {2002} */
63 /* } */
64 void surf_network_model_init_CM02(void)
65 {
66
67   if (surf_network_model)
68     return;
69
70   surf_network_model = new NetworkCm02Model();
71   xbt_dynar_push(model_list, &surf_network_model);
72
73   xbt_cfg_setdefault_double(_sg_cfg_set, "network/latency_factor", 1.0);
74   xbt_cfg_setdefault_double(_sg_cfg_set, "network/bandwidth_factor",
75                             1.0);
76   xbt_cfg_setdefault_double(_sg_cfg_set, "network/weight_S", 0.0);
77 }
78
79 /***************************************************************************/
80 /* The models from Steven H. Low                                           */
81 /***************************************************************************/
82 /* @article{Low03,                                                         */
83 /*   author={Steven H. Low},                                               */
84 /*   title={A Duality Model of {TCP} and Queue Management Algorithms},     */
85 /*   year={2003},                                                          */
86 /*   journal={{IEEE/ACM} Transactions on Networking},                      */
87 /*    volume={11}, number={4},                                             */
88 /*  }                                                                      */
89 void surf_network_model_init_Reno(void)
90 {
91   if (surf_network_model)
92     return;
93
94   surf_network_model = new NetworkCm02Model();
95   xbt_dynar_push(model_list, &surf_network_model);
96   lmm_set_default_protocol_function(func_reno_f, func_reno_fp,
97                                     func_reno_fpi);
98   surf_network_model->f_networkSolve = lagrange_solve;
99
100   xbt_cfg_setdefault_double(_sg_cfg_set, "network/latency_factor", 10.4);
101   xbt_cfg_setdefault_double(_sg_cfg_set, "network/bandwidth_factor",
102                             0.92);
103   xbt_cfg_setdefault_double(_sg_cfg_set, "network/weight_S", 8775);
104 }
105
106
107 void surf_network_model_init_Reno2(void)
108 {
109   if (surf_network_model)
110     return;
111
112   surf_network_model = new NetworkCm02Model();
113   xbt_dynar_push(model_list, &surf_network_model);
114   lmm_set_default_protocol_function(func_reno2_f, func_reno2_fp,
115                                     func_reno2_fpi);
116   surf_network_model->f_networkSolve = lagrange_solve;
117
118   xbt_cfg_setdefault_double(_sg_cfg_set, "network/latency_factor", 10.4);
119   xbt_cfg_setdefault_double(_sg_cfg_set, "network/bandwidth_factor",
120                             0.92);
121   xbt_cfg_setdefault_double(_sg_cfg_set, "network/weight_S_parameter",
122                             8775);
123 }
124
125 void surf_network_model_init_Vegas(void)
126 {
127   if (surf_network_model)
128     return;
129
130   surf_network_model = new NetworkCm02Model();
131   xbt_dynar_push(model_list, &surf_network_model);
132   lmm_set_default_protocol_function(func_vegas_f, func_vegas_fp,
133                                     func_vegas_fpi);
134   surf_network_model->f_networkSolve = lagrange_solve;
135
136   xbt_cfg_setdefault_double(_sg_cfg_set, "network/latency_factor", 10.4);
137   xbt_cfg_setdefault_double(_sg_cfg_set, "network/bandwidth_factor",
138                             0.92);
139   xbt_cfg_setdefault_double(_sg_cfg_set, "network/weight_S", 8775);
140 }
141
142 NetworkCm02Model::NetworkCm02Model() : NetworkCm02Model("network"){
143 }
144
145 NetworkCm02Model::NetworkCm02Model(string name) : Model(name){
146   NetworkCm02ActionLmmPtr comm;
147
148   char *optim = xbt_cfg_get_string(_sg_cfg_set, "network/optim");
149   int select =
150       xbt_cfg_get_boolean(_sg_cfg_set, "network/maxmin_selective_update");
151
152   if (!strcmp(optim, "Full")) {
153     p_updateMechanism = UM_FULL;
154     m_selectiveUpdate = select;
155   } else if (!strcmp(optim, "Lazy")) {
156     p_updateMechanism = UM_LAZY;
157     m_selectiveUpdate = 1;
158     xbt_assert((select == 1)
159                ||
160                (xbt_cfg_is_default_value
161                 (_sg_cfg_set, "network/maxmin_selective_update")),
162                "Disabling selective update while using the lazy update mechanism is dumb!");
163   } else {
164     xbt_die("Unsupported optimization (%s) for this model", optim);
165   }
166
167   if (!p_maxminSystem)
168         p_maxminSystem = lmm_system_new(m_selectiveUpdate);
169
170   routing_model_create(createResource("__loopback__",
171                                                    498000000, NULL, 0.000015, NULL,
172                                                    SURF_RESOURCE_ON, NULL,
173                                                    SURF_LINK_FATPIPE, NULL));
174
175   if (p_updateMechanism == UM_LAZY) {
176         p_actionHeap = xbt_heap_new(8, NULL);
177         xbt_heap_set_update_callback(p_actionHeap, surf_action_lmm_update_index_heap);
178         p_modifiedSet = xbt_swag_new(xbt_swag_offset((*comm), p_actionListHookup));
179         p_maxminSystem->keep_track = p_modifiedSet;
180   }
181 }
182
183 NetworkCm02LinkLmmPtr NetworkCm02Model::createResource(const char *name,
184                                  double bw_initial,
185                                  tmgr_trace_t bw_trace,
186                                  double lat_initial,
187                                  tmgr_trace_t lat_trace,
188                                  e_surf_resource_state_t state_initial,
189                                  tmgr_trace_t state_trace,
190                                  e_surf_link_sharing_policy_t policy,
191                                  xbt_dict_t properties)
192 {
193   xbt_assert(!xbt_lib_get_or_null(link_lib, name, SURF_LINK_LEVEL),
194              "Link '%s' declared several times in the platform file.",
195              name);
196
197   NetworkCm02LinkLmmPtr nw_link =
198                   new NetworkCm02LinkLmm(this, name, properties, p_maxminSystem, sg_bandwidth_factor * bw_initial, history,
199                                                  state_initial, state_trace, bw_initial, bw_trace, lat_initial, lat_trace, policy);
200
201
202   xbt_lib_set(link_lib, name, SURF_LINK_LEVEL, nw_link);
203   XBT_DEBUG("Create link '%s'",name);
204
205   return nw_link;
206 }
207
208 void NetworkCm02Model::updateActionsStateLazy(double now, double delta)
209 {
210   NetworkCm02ActionLmmPtr action;
211   while ((xbt_heap_size(p_actionHeap) > 0)
212          && (double_equals(xbt_heap_maxkey(p_actionHeap), now))) {
213     action = (NetworkCm02ActionLmmPtr) xbt_heap_pop(p_actionHeap);
214     XBT_DEBUG("Something happened to action %p", action);
215 #ifdef HAVE_TRACING
216     if (TRACE_is_enabled()) {
217       int n = lmm_get_number_of_cnst_from_var(p_maxminSystem, action->p_variable);
218       unsigned int i;
219       for (i = 0; i < n; i++){
220         lmm_constraint_t constraint = lmm_get_cnst_from_var(p_maxminSystem,
221                                                             action->p_variable,
222                                                             i);
223         NetworkCm02LinkPtr link = (NetworkCm02LinkPtr) lmm_constraint_id(constraint);
224         TRACE_surf_link_set_utilization(link->m_name,
225                                         action->p_category,
226                                         (lmm_variable_getvalue(action->p_variable)*
227                                             lmm_get_cnst_weight_from_var(p_maxminSystem,
228                                                 action->p_variable,
229                                                 i)),
230                                         action->m_lastUpdate,
231                                         now - action->m_lastUpdate);
232       }
233     }
234 #endif
235
236     // if I am wearing a latency hat
237     if (action->m_hat == LATENCY) {
238       XBT_DEBUG("Latency paid for action %p. Activating", action);
239       lmm_update_variable_weight(p_maxminSystem, action->p_variable, action->m_weight);
240       action->heapRemove(p_actionHeap);
241       action->m_lastUpdate = surf_get_clock();
242
243         // if I am wearing a max_duration or normal hat
244     } else if (action->m_hat == MAX_DURATION ||
245         action->m_hat == NORMAL) {
246         // no need to communicate anymore
247         // assume that flows that reached max_duration have remaining of 0
248       action->m_finish = surf_get_clock();
249       XBT_DEBUG("Action %p finished", action);
250       action->m_remains = 0;
251       action->m_finish = surf_get_clock();
252       action->setState(SURF_ACTION_DONE);
253       action->heapRemove(p_actionHeap);
254
255       action->gapRemove();
256     }
257   }
258   return;
259 }
260
261 xbt_dynar_t NetworkCm02Model::getRoute(RoutingEdgePtr src, RoutingEdgePtr dst)
262 {
263   xbt_dynar_t route = NULL;
264   routing_platf->getRouteAndLatency(src, dst, &route, NULL);
265   return route;
266 }
267
268 NetworkCm02ActionPtr NetworkCm02Model::communicate(RoutingEdgePtr src, RoutingEdgePtr dst,
269                                                 double size, double rate)
270 {
271   unsigned int i;
272   NetworkCm02LinkLmmPtr link;
273   int failed = 0;
274   NetworkCm02ActionLmmPtr action = NULL;
275   double bandwidth_bound;
276   double latency = 0.0;
277   xbt_dynar_t back_route = NULL;
278   int constraints_per_variable = 0;
279
280   xbt_dynar_t route = xbt_dynar_new(sizeof(RoutingEdgePtr), NULL);
281
282   XBT_IN("(%s,%s,%g,%g)", src->p_name, dst->p_name, size, rate);
283
284   routing_platf->getRouteAndLatency(src, dst, &route, &latency);
285   xbt_assert(!xbt_dynar_is_empty(route) || latency,
286              "You're trying to send data from %s to %s but there is no connection at all between these two hosts.",
287              src->p_name, dst->p_name);
288
289   xbt_dynar_foreach(route, i, link) {
290     if (link->p_stateCurrent == SURF_RESOURCE_OFF) {
291       failed = 1;
292       break;
293     }
294   }
295   if (sg_network_crosstraffic == 1) {
296           routing_platf->getRouteAndLatency(dst, src, &back_route, NULL);
297     xbt_dynar_foreach(back_route, i, link) {
298       if (link->p_stateCurrent == SURF_RESOURCE_OFF) {
299         failed = 1;
300         break;
301       }
302     }
303   }
304
305   action = new NetworkCm02ActionLmm(this, size, failed);
306
307 #ifdef HAVE_LATENCY_BOUND_TRACKING
308   action->m_latencyLimited = 0;
309 #endif
310   action->m_weight = action->m_latency = latency;
311
312   xbt_swag_insert(action, action->p_stateSet);
313   action->m_rate = rate;
314   if (p_updateMechanism == UM_LAZY) {
315     action->m_indexHeap = -1;
316     action->m_lastUpdate = surf_get_clock();
317   }
318
319   bandwidth_bound = -1.0;
320   if (sg_weight_S_parameter > 0) {
321     xbt_dynar_foreach(route, i, link) {
322       action->m_weight +=
323          sg_weight_S_parameter /
324          (link->p_power.peak * link->p_power.scale);
325     }
326   }
327   xbt_dynar_foreach(route, i, link) {
328     double bb = bandwidthFactor(size) *
329         (link->p_power.peak * link->p_power.scale);
330     bandwidth_bound =
331         (bandwidth_bound < 0.0) ? bb : min(bandwidth_bound, bb);
332   }
333
334   action->m_latCurrent = action->m_latency;
335   action->m_latency *= latencyFactor(size);
336   action->m_rate = bandwidthConstraint(action->m_rate, bandwidth_bound, size);
337   if (m_haveGap) {
338     xbt_assert(!xbt_dynar_is_empty(route),
339                "Using a model with a gap (e.g., SMPI) with a platform without links (e.g. vivaldi)!!!");
340
341     link = *(NetworkCm02LinkLmmPtr *) xbt_dynar_get_ptr(route, 0);
342     gapAppend(size, link, action);
343     XBT_DEBUG("Comm %p: %s -> %s gap=%f (lat=%f)",
344               action, src->p_name, dst->p_name, action->m_senderGap,
345               action->m_latency);
346   }
347
348   constraints_per_variable = xbt_dynar_length(route);
349   if (back_route != NULL)
350     constraints_per_variable += xbt_dynar_length(back_route);
351
352   if (action->m_latency > 0) {
353     action->p_variable = lmm_variable_new(p_maxminSystem, action, 0.0, -1.0,
354                          constraints_per_variable);
355     if (p_updateMechanism == UM_LAZY) {
356       // add to the heap the event when the latency is payed
357       XBT_DEBUG("Added action (%p) one latency event at date %f", action,
358                 action->m_latency + action->m_lastUpdate);
359       action->heapInsert(p_actionHeap, action->m_latency + action->m_lastUpdate, xbt_dynar_is_empty(route) ? NORMAL : LATENCY);
360     }
361   } else
362     action->p_variable = lmm_variable_new(p_maxminSystem, action, 1.0, -1.0, constraints_per_variable);
363
364   if (action->m_rate < 0) {
365     lmm_update_variable_bound(p_maxminSystem, action->p_variable, (action->m_latCurrent > 0) ? sg_tcp_gamma / (2.0 * action->m_latCurrent) : -1.0);
366   } else {
367     lmm_update_variable_bound(p_maxminSystem, action->p_variable, (action->m_latCurrent > 0) ? min(action->m_rate, sg_tcp_gamma / (2.0 * action->m_latCurrent)) : action->m_rate);
368   }
369
370   xbt_dynar_foreach(route, i, link) {
371     lmm_expand(p_maxminSystem, link->p_constraint, action->p_variable, 1.0);
372   }
373
374   if (sg_network_crosstraffic == 1) {
375     XBT_DEBUG("Fullduplex active adding backward flow using 5%%");
376     xbt_dynar_foreach(back_route, i, link) {
377       lmm_expand(p_maxminSystem, link->p_constraint, action->p_variable, .05);
378     }
379   }
380
381   xbt_dynar_free(&route);
382   XBT_OUT();
383
384   return action;
385 }
386
387 double NetworkCm02Model::latencyFactor(double size) {
388   return sg_latency_factor;
389 }
390
391 double NetworkCm02Model::bandwidthFactor(double size) {
392   return sg_bandwidth_factor;
393 }
394
395 double NetworkCm02Model::bandwidthConstraint(double rate, double bound, double size) {
396   return rate;
397 }
398
399 /************
400  * Resource *
401  ************/
402 NetworkCm02LinkLmm::NetworkCm02LinkLmm(NetworkCm02ModelPtr model, const char *name, xbt_dict_t props,
403                                    lmm_system_t system,
404                                    double constraint_value,
405                                    tmgr_history_t history,
406                                    e_surf_resource_state_t state_init,
407                                    tmgr_trace_t state_trace,
408                                    double metric_peak,
409                                    tmgr_trace_t metric_trace,
410                                    double lat_initial,
411                                    tmgr_trace_t lat_trace,
412                                    e_surf_link_sharing_policy_t policy)
413 : ResourceLmm(model, name, props, system, constraint_value, history, state_init, state_trace, metric_peak, metric_trace)
414 {
415   m_latCurrent = lat_initial;
416   if (lat_trace)
417         p_latEvent = tmgr_history_add_trace(history, lat_trace, 0.0, 0, this);
418
419   if (policy == SURF_LINK_FATPIPE)
420         lmm_constraint_shared(p_constraint);
421 }
422
423 bool NetworkCm02LinkLmm::isUsed()
424 {
425   return lmm_constraint_used(p_model->p_maxminSystem, p_constraint);
426 }
427
428 double NetworkCm02Link::getLatency()
429 {
430   return m_latCurrent;
431 }
432
433 double NetworkCm02LinkLmm::getBandwidth()
434 {
435   return p_power.peak * p_power.scale;
436 }
437
438 bool NetworkCm02LinkLmm::isShared()
439 {
440   return lmm_constraint_is_shared(p_constraint);
441 }
442
443 void NetworkCm02LinkLmm::updateState(tmgr_trace_event_t event_type,
444                                       double value, double date)
445 {
446   /*   printf("[" "%lg" "] Asking to update network card \"%s\" with value " */
447   /*     "%lg" " for event %p\n", surf_get_clock(), nw_link->name, */
448   /*     value, event_type); */
449
450   if (event_type == p_power.event) {
451     double delta =
452         sg_weight_S_parameter / value - sg_weight_S_parameter /
453         (p_power.peak * p_power.scale);
454     lmm_variable_t var = NULL;
455     lmm_element_t elem = NULL;
456     NetworkCm02ActionLmmPtr action = NULL;
457
458     p_power.peak = value;
459     lmm_update_constraint_bound(p_model->p_maxminSystem,
460                                 p_constraint,
461                                 sg_bandwidth_factor *
462                                 (p_power.peak * p_power.scale));
463 #ifdef HAVE_TRACING
464     TRACE_surf_link_set_bandwidth(date, m_name, sg_bandwidth_factor * p_power.peak * p_power.scale);
465 #endif
466     if (sg_weight_S_parameter > 0) {
467       while ((var = lmm_get_var_from_cnst(p_model->p_maxminSystem, p_constraint, &elem))) {
468         action = (NetworkCm02ActionLmmPtr) lmm_variable_id(var);
469         action->m_weight += delta;
470         if (!action->m_suspended)
471           lmm_update_variable_weight(p_model->p_maxminSystem, action->p_variable, action->m_weight);
472       }
473     }
474     if (tmgr_trace_event_free(event_type))
475       p_power.event = NULL;
476   } else if (event_type == p_latEvent) {
477     double delta = value - m_latCurrent;
478     lmm_variable_t var = NULL;
479     lmm_element_t elem = NULL;
480     NetworkCm02ActionLmmPtr action = NULL;
481
482     m_latCurrent = value;
483     while ((var = lmm_get_var_from_cnst(p_model->p_maxminSystem, p_constraint, &elem))) {
484       action = (NetworkCm02ActionLmmPtr) lmm_variable_id(var);
485       action->m_latCurrent += delta;
486       action->m_weight += delta;
487       if (action->m_rate < 0)
488         lmm_update_variable_bound(p_model->p_maxminSystem, action->p_variable, sg_tcp_gamma / (2.0 * action->m_latCurrent));
489       else {
490         lmm_update_variable_bound(p_model->p_maxminSystem, action->p_variable,
491                                   min(action->m_rate, sg_tcp_gamma / (2.0 * action->m_latCurrent)));
492
493         if (action->m_rate < sg_tcp_gamma / (2.0 * action->m_latCurrent)) {
494           XBT_INFO("Flow is limited BYBANDWIDTH");
495         } else {
496           XBT_INFO("Flow is limited BYLATENCY, latency of flow is %f",
497                    action->m_latCurrent);
498         }
499       }
500       if (!action->m_suspended)
501         lmm_update_variable_weight(p_model->p_maxminSystem, action->p_variable, action->m_weight);
502
503     }
504     if (tmgr_trace_event_free(event_type))
505       p_latEvent = NULL;
506   } else if (event_type == p_stateEvent) {
507     if (value > 0)
508       p_stateCurrent = SURF_RESOURCE_ON;
509     else {
510       lmm_constraint_t cnst = p_constraint;
511       lmm_variable_t var = NULL;
512       lmm_element_t elem = NULL;
513
514       p_stateCurrent = SURF_RESOURCE_OFF;
515       while ((var = lmm_get_var_from_cnst(p_model->p_maxminSystem, cnst, &elem))) {
516         ActionPtr action = (ActionPtr) lmm_variable_id(var);
517
518         if (action->getState() == SURF_ACTION_RUNNING ||
519             action->getState() == SURF_ACTION_READY) {
520           action->m_finish = date;
521           action->setState(SURF_ACTION_FAILED);
522         }
523       }
524     }
525     if (tmgr_trace_event_free(event_type))
526       p_stateEvent = NULL;
527   } else {
528     XBT_CRITICAL("Unknown event ! \n");
529     xbt_abort();
530   }
531
532   XBT_DEBUG
533       ("There were a resource state event, need to update actions related to the constraint (%p)",
534        p_constraint);
535   return;
536 }
537
538 /**********
539  * Action *
540  **********/
541 void NetworkCm02ActionLmm::updateRemainingLazy(double now)
542 {
543   double delta = 0.0;
544
545   if (m_suspended != 0)
546     return;
547
548   delta = now - m_lastUpdate;
549
550   if (m_remains > 0) {
551     XBT_DEBUG("Updating action(%p): remains was %lf, last_update was: %lf", this, m_remains, m_lastUpdate);
552     double_update(&(m_remains), m_lastValue * delta);
553
554     XBT_DEBUG("Updating action(%p): remains is now %lf", this, m_remains);
555   }
556
557   if (m_maxDuration != NO_MAX_DURATION)
558     double_update(&m_maxDuration, delta);
559
560   if (m_remains <= 0 &&
561       (lmm_get_variable_weight(p_variable) > 0)) {
562     m_finish = surf_get_clock();
563     setState(SURF_ACTION_DONE);
564
565     heapRemove(p_model->p_actionHeap);
566   } else if (((m_maxDuration != NO_MAX_DURATION)
567       && (m_maxDuration <= 0))) {
568     m_finish = surf_get_clock();
569     setState(SURF_ACTION_DONE);
570     heapRemove(p_model->p_actionHeap);
571   }
572
573   m_lastUpdate = now;
574   m_lastValue = lmm_variable_getvalue(p_variable);
575 }
576 void NetworkCm02ActionLmm::recycle()
577 {
578   return;
579 }
580