3 /* Copyright (c) 2007 Arnaud Legrand, Pedro Velho. All rights reserved. */
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. */
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".
14 #include "xbt/sysdep.h"
15 #include "xbt/mallocator.h"
16 #include "maxmin_private.h"
24 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf,
25 "Logging specific to SURF (lagrange)");
27 void lagrange_solve(lmm_system_t sys)
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;
42 * Variables to manipulate the data structure proposed to model the maxmin
43 * fairness. See docummentation for more details.
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;
59 int max_iterations=100000;
61 double lambda_partial=0;
64 if ( !(sys->modified))
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
73 var_list = &(sys->active_variable_set);
75 xbt_swag_foreach(var1, var_list) {
76 if(var1->weight != 0.0){
78 sum_bound += var1->bound;
83 * Compute the sum of all capacities constraints. May change depending
84 * on the function f(x).
86 cnst_list=&(sys->active_constraint_set);
87 xbt_swag_foreach(cnst1, cnst_list) {
88 sum_capacity += cnst1->value;
93 * While doesn't reach a minimun error or a number maximum of iterations.
95 while(overall_error > epsilon_min_error && iteration < max_iterations){
102 * Compute the value of ----------- (\lambda^k, \mu^k) this portion
104 * of code depends on function f(x).
107 xbt_swag_foreach(var1, var_list) {
111 //for each link elem1 that uses flow of variable var1 do
112 //mu_partial += elem1->weight + var1->bound;
114 mu_partial = - (1 / mu_partial) + sum_bound;
116 var1->bound = var1->bound + sigma_step * mu_partial;
122 * Verify for each capacity constraint (lambda) the error associated.
124 xbt_swag_foreach(cnst1, cnst_list) {
125 cnst2 = xbt_swag_getNext(cnst1,(var_list)->offset);
127 capacity_error += fabs(cnst1->value - cnsts2->value);
132 * Verify for each variable the error of round trip time constraint (mu).
135 xbt_swag_foreach(var1, var_list) {
136 var2 = xbt_swag_getNext(var1,(var_list)->offset);
138 bound_error += fabs( var2->weight - var1->weight);
142 overall_error = capacity_error + bound_error;