Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
c6ad3d8f35a38449df3445a9b2534079a4ff1540
[simgrid.git] / src / surf / lagrange.c
1 /*      $Id$     */
2
3 /* Copyright (c) 2007 Arnaud Legrand, Pedro Velho. All rights reserved.     */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 /*
9  * Modelling the proportional fairness using the Lagrange Optimization 
10  * Approach. For a detailed description see:
11  * "ssh://username@scm.gforge.inria.fr/svn/memo/people/pvelho/lagrange/ppf.ps".
12  */
13 #include "xbt/log.h"
14 #include "xbt/sysdep.h"
15 #include "xbt/mallocator.h"
16 #include "maxmin_private.h"
17
18 #include <stdlib.h>
19 #ifndef MATH
20 #include <math.h>
21 #endif
22
23
24 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf,
25                                 "Logging specific to SURF (lagrange)");
26
27 void lagrange_solve(lmm_system_t sys)
28 {
29
30   /*
31    * Lagrange Variables.
32    */
33   double epsilon_min_error = 1e-6;
34   double overall_error = 1;
35   double sigma_step = 0.5e-3;
36   double capacity_error, bound_error;
37   double sum_capacity = 0;
38   double sum_bound = 0;
39   
40
41   /*
42    * Variables to manipulate the data structure proposed to model the maxmin
43    * fairness. See docummentation for more details.
44    */
45   lmm_element_t elem = NULL;
46   xbt_swag_t cnst_list = NULL;
47   lmm_constraint_t cnst1 = NULL;
48   lmm_constraint_t cnst2 = NULL;
49   xbt_swag_t var_list = NULL;
50   xbt_swag_t elem_list = NULL;
51   lmm_variable_t var1 = NULL;
52   lmm_variable_t var2 = NULL;
53
54
55   /*
56    * Auxiliar variables.
57    */
58   int iteration=0;
59   int max_iterations=100000;
60   double mu_partial=0;
61   double lambda_partial=0;
62
63
64   if ( !(sys->modified))
65     return;
66   
67   /* 
68    * Initialize the var list variable with only the active variables. 
69    * Associate an index in the swag variables and compute the sum
70    * of all round trip time constraints. May change depending on the 
71    * function f(x).
72    */
73   var_list = &(sys->active_variable_set);
74   i=0;
75   xbt_swag_foreach(var1, var_list) {
76     if(var1->weight != 0.0){
77       i++;
78       sum_bound += var1->bound;
79     }
80   }
81
82   /* 
83    * Compute the sum of all capacities constraints. May change depending
84    * on the function f(x).
85    */
86   cnst_list=&(sys->active_constraint_set); 
87   xbt_swag_foreach(cnst1, cnst_list) {
88     ┬ásum_capacity += cnst1->value;
89   }
90
91   
92   /*
93    * While doesn't reach a minimun error or a number maximum of iterations.
94    */
95   while(overall_error > epsilon_min_error && iteration < max_iterations){
96
97     iteration++;
98
99     
100     
101     /*                        d Dual
102      * Compute the value of ----------- (\lambda^k, \mu^k) this portion
103      *                       d \mu_i^k
104      * of code depends on function f(x).
105      */
106     bound_error = 0;
107     xbt_swag_foreach(var1, var_list) {
108       
109       mu_partial = 0;
110       
111       //for each link elem1 that uses flow of variable var1 do
112       //mu_partial += elem1->weight + var1->bound; 
113
114       mu_partial = - (1 / mu_partial) + sum_bound;
115
116       var1->bound = var1->bound + sigma_step * mu_partial;
117     }
118
119     
120     
121     /*
122      * Verify for each capacity constraint (lambda) the error associated. 
123      */
124     xbt_swag_foreach(cnst1, cnst_list) {
125       cnst2 = xbt_swag_getNext(cnst1,(var_list)->offset);
126       if(cnst2 != NULL){
127         ┬ácapacity_error += fabs(cnst1->value - cnsts2->value);
128       }
129     }
130
131     /*
132      * Verify for each variable the error of round trip time constraint (mu).
133      */
134     bound_error = 0;
135     xbt_swag_foreach(var1, var_list) {
136       var2 = xbt_swag_getNext(var1,(var_list)->offset);
137       if(var2 != NULL){
138         bound_error += fabs( var2->weight - var1->weight);
139       }
140     }
141
142     overall_error = capacity_error + bound_error;
143   }
144
145 }