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 void lagrange_solve(lmm_system_t sys)
  30 {
  31
  32   /*
  33    * Lagrange Variables.
  34    */
  35   double epsilon_min_error = 1e-6;
  36   double overall_error = 1;
  37   double sigma_step = 0.5e-3;
  38   double capacity_error=0, bound_error=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   xbt_swag_t elem_list = NULL;
  46   lmm_element_t elem1 = NULL;
  47   lmm_element_t elem2 = NULL;
  48
  49   xbt_swag_t cnst_list = NULL;
  50   lmm_constraint_t cnst1 = NULL;
  51   lmm_constraint_t cnst2 = NULL;
  52
  53   xbt_swag_t var_list = NULL;
  54   lmm_variable_t var1 = NULL;
  55   lmm_variable_t var2 = NULL;
  56
  57
  58   /*
  59    * Auxiliar variables.
  60    */
  61   int iteration=0;
  62   int max_iterations=100000;
  63   double mu_partial=0;
  64   double lambda_partial=0;
  65   double tmp=0;
  66   int i;
  67
  68
  69   if ( !(sys->modified))
  70     return;
  71
  72   /*
  73    * Initialize the var list variable with only the active variables.
  74    * Associate an index in the swag variables. Saves the initial value
  75    * of bound associated with.
  76    */
  77   var_list = &(sys->variable_set);
  78   i=0;
  79   xbt_swag_foreach(var1, var_list) {
  80     if(var1->weight != 0.0){
  81       i++;
  82       var1->initial_bound = var1->bound;
  83     }
  84   }
  85
  86   /*
  87    * Saves the initial bound of each constraint.
  88    */
  89   cnst_list=&(sys->active_constraint_set);
  90   xbt_swag_foreach(cnst1, cnst_list) {
  91     cnst1->initial_bound = cnst1->bound;
  92   }
  93
  94
  95   /*
  96    * While doesn't reach a minimun error or a number maximum of iterations.
  97    */
  98   while(overall_error > epsilon_min_error && iteration < max_iterations){
  99
 100     iteration++;
 101
 102
 103     /*                        d Dual
 104      * Compute the value of ----------- (\lambda^k, \mu^k) this portion
 105      *                       d \mu_i^k
 106      * of code depends on function f(x).
 107      */
 108     var_list = &(sys->variable_set);
 109     xbt_swag_foreach(var1, var_list) {
 110
 111       mu_partial = 0;
 112
 113       //for each link with capacity cnsts[i] that uses flow of variable var1 do
 114       for(i=0; i<var1->cnsts_number; i++){
 115         elem1 = &(var1->cnsts[i]);
 116         mu_partial += (elem1->constraint)->bound + var1->initial_bound;
 117       }
 118
 119       mu_partial = -1 / mu_partial + var1->initial_bound;
 120       var1->bound = var1->bound + sigma_step * mu_partial;
 121     }
 122
 123
 124     /*                         d Dual
 125      * Compute the value of ------------- (\lambda^k, \mu^k) this portion
 126      *                      d \lambda_i^k
 127      * of code depends on function f(x).
 128      */
 129     cnst_list=&(sys->active_constraint_set);
 130     xbt_swag_foreach(cnst1, cnst_list) {
 131
 132       lambda_partial = 0;
 133
 134       elem_list = &(cnst1->active_element_set);
 135
 136       xbt_swag_foreach(elem1, elem_list) {
 137         lambda_partial = 0;
 138
 139         var2 = elem1->variable;
 140
 141         //for each link with capacity cnsts[i] that uses flow of variable var1 do
 142         for(i=0; i<var2->cnsts_number; i++){
 143           elem2 = &(var2->cnsts[i]);
 144           tmp += (elem2->constraint)->bound + var2->bound;
 145         }
 146
 147         lambda_partial += -1 / tmp;
 148       }
 149
 150       lambda_partial += cnst1->initial_bound;
 151       cnst1->bound = cnst1->bound + sigma_step * lambda_partial;
 152     }
 153
 154
 155
 156     /*
 157      * Verify for each capacity constraint (lambda) the error associated.
 158      */
 159     cnst_list=&(sys->active_constraint_set);
 160     xbt_swag_foreach(cnst1, cnst_list) {
 161       cnst2 = xbt_swag_getNext(cnst1,(var_list)->offset);
 162       if(cnst2 != NULL){
 163         capacity_error += fabs( cnst1->bound - cnst2->bound );
 164       }
 165     }
 166
 167     /*
 168      * Verify for each variable the error of round trip time constraint (mu).
 169      */
 170     bound_error = 0;
 171     var_list = &(sys->variable_set);
 172     xbt_swag_foreach(var1, var_list) {
 173       var2 = xbt_swag_getNext(var1,(var_list)->offset);
 174       if(var2 != NULL){
 175         bound_error += fabs( var2->bound - var1->bound);
 176       }
 177     }
 178
 179     overall_error = capacity_error + bound_error;
 180   }
 181
 182
 183   if(overall_error > epsilon_min_error){
 184     DEBUG1("The method converge in %d iterations.", iteration);
 185   }
 186
 187   /*
 188    * Now computes the values of each variable (\rho) based on
 189    * the values of \lambda and \mu.
 190    */
 191   var_list = &(sys->variable_set);
 192   xbt_swag_foreach(var1, var_list) {
 193     tmp = 0;
 194     for(i=0; i<var1->cnsts_number; i++){
 195       elem1 = &(var1->cnsts[i]);
 196       tmp += (elem1->constraint)->bound + var1->bound;
 197     }
 198     var1->weight = 1 / tmp;
 199   }
 200
 201
 202
 203
 204 }