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 }