From: velho <velho@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Date: Tue, 20 Mar 2007 10:05:44 +0000 (+0000)
Subject: Start the development of the lagrange optimization method to implement
X-Git-Tag: v3.3~2048
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/a8e926e86ef601549e7f37b4b2b1d210dc6dd5f1?hp=f68341674691958569f4f36fe7e4b3f50200cdcc

Start the development of the lagrange optimization method to implement
the proportional fairness.


git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3312 48e7efb5-ca39-0410-a469-dd3cf9ba447f
---

diff --git a/src/surf/lagrange.c b/src/surf/lagrange.c
new file mode 100644
index 0000000000..c6ad3d8f35
--- /dev/null
+++ b/src/surf/lagrange.c
@@ -0,0 +1,145 @@
+/* 	$Id$	 */
+
+/* Copyright (c) 2007 Arnaud Legrand, Pedro Velho. All rights reserved.     */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+/*
+ * Modelling the proportional fairness using the Lagrange Optimization 
+ * Approach. For a detailed description see:
+ * "ssh://username@scm.gforge.inria.fr/svn/memo/people/pvelho/lagrange/ppf.ps".
+ */
+#include "xbt/log.h"
+#include "xbt/sysdep.h"
+#include "xbt/mallocator.h"
+#include "maxmin_private.h"
+
+#include <stdlib.h>
+#ifndef MATH
+#include <math.h>
+#endif
+
+
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf,
+				"Logging specific to SURF (lagrange)");
+
+void lagrange_solve(lmm_system_t sys)
+{
+
+  /*
+   * Lagrange Variables.
+   */
+  double epsilon_min_error = 1e-6;
+  double overall_error = 1;
+  double sigma_step = 0.5e-3;
+  double capacity_error, bound_error;
+  double sum_capacity = 0;
+  double sum_bound = 0;
+  
+
+  /*
+   * Variables to manipulate the data structure proposed to model the maxmin
+   * fairness. See docummentation for more details.
+   */
+  lmm_element_t elem = NULL;
+  xbt_swag_t cnst_list = NULL;
+  lmm_constraint_t cnst1 = NULL;
+  lmm_constraint_t cnst2 = NULL;
+  xbt_swag_t var_list = NULL;
+  xbt_swag_t elem_list = NULL;
+  lmm_variable_t var1 = NULL;
+  lmm_variable_t var2 = NULL;
+
+
+  /*
+   * Auxiliar variables.
+   */
+  int iteration=0;
+  int max_iterations=100000;
+  double mu_partial=0;
+  double lambda_partial=0;
+
+
+  if ( !(sys->modified))
+    return;
+  
+  /* 
+   * Initialize the var list variable with only the active variables. 
+   * Associate an index in the swag variables and compute the sum
+   * of all round trip time constraints. May change depending on the 
+   * function f(x).
+   */
+  var_list = &(sys->active_variable_set);
+  i=0;
+  xbt_swag_foreach(var1, var_list) {
+    if(var1->weight != 0.0){
+      i++;
+      sum_bound += var1->bound;
+    }
+  }
+
+  /* 
+   * Compute the sum of all capacities constraints. May change depending
+   * on the function f(x).
+   */
+  cnst_list=&(sys->active_constraint_set); 
+  xbt_swag_foreach(cnst1, cnst_list) {
+     sum_capacity += cnst1->value;
+  }
+
+  
+  /*
+   * While doesn't reach a minimun error or a number maximum of iterations.
+   */
+  while(overall_error > epsilon_min_error && iteration < max_iterations){
+
+    iteration++;
+
+    
+    
+    /*                        d Dual
+     * Compute the value of ----------- (\lambda^k, \mu^k) this portion
+     *                       d \mu_i^k
+     * of code depends on function f(x).
+     */
+    bound_error = 0;
+    xbt_swag_foreach(var1, var_list) {
+      
+      mu_partial = 0;
+      
+      //for each link elem1 that uses flow of variable var1 do
+      //mu_partial += elem1->weight + var1->bound; 
+
+      mu_partial = - (1 / mu_partial) + sum_bound;
+
+      var1->bound = var1->bound + sigma_step * mu_partial;
+    }
+
+    
+    
+    /*
+     * Verify for each capacity constraint (lambda) the error associated. 
+     */
+    xbt_swag_foreach(cnst1, cnst_list) {
+      cnst2 = xbt_swag_getNext(cnst1,(var_list)->offset);
+      if(cnst2 != NULL){
+	 capacity_error += fabs(cnst1->value - cnsts2->value);
+      }
+    }
+
+    /*
+     * Verify for each variable the error of round trip time constraint (mu).
+     */
+    bound_error = 0;
+    xbt_swag_foreach(var1, var_list) {
+      var2 = xbt_swag_getNext(var1,(var_list)->offset);
+      if(var2 != NULL){
+	bound_error += fabs( var2->weight - var1->weight);
+      }
+    }
+
+    overall_error = capacity_error + bound_error;
+  }
+
+}