From c027c476705c1c88c5c76570ccdd75809fbc3af2 Mon Sep 17 00:00:00 2001 From: velho Date: Mon, 2 Jul 2007 20:24:59 +0000 Subject: [PATCH] Added the generic method to model fairness depending on the transport protocol specific constraints and behavior. Protocols TCP Reno and Vegas already implemented. Seems to work with the testbed in src/testsuite/surf/simeng_usage. Still need to be tested using a msg application. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3644 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- src/surf/lagrange.c | 94 ++++++++++++------------ src/surf/maxmin.c | 94 +++++++++++++++--------- testsuite/surf/simeng_usage.c | 132 +++++++++++++++++++++++++--------- 3 files changed, 208 insertions(+), 112 deletions(-) diff --git a/src/surf/lagrange.c b/src/surf/lagrange.c index c3aa908cf4..af1b2f9ae3 100644 --- a/src/surf/lagrange.c +++ b/src/surf/lagrange.c @@ -31,6 +31,8 @@ double dicotomi(double init, double diff(double, void*), void *var_cnst, double double partial_diff_mu (double mu, void * param_var); //computes the value of the differential of constraint param_cnst applied to lambda double partial_diff_lambda (double lambda, void * param_cnst); +//auxiliar function to compute the partial_diff +double diff_aux(lmm_variable_t var, double x); void lagrange_solve(lmm_system_t sys) @@ -131,20 +133,6 @@ void lagrange_solve(lmm_system_t sys) cnst->lambda = cnst->new_lambda; } - -/* /\* */ -/* * Update values of mu and lambda */ -/* *\/ */ -/* //forall mu_i in mu_1, mu_2, ..., mu_n */ -/* xbt_swag_foreach(var, var_list) { */ -/* var->mu = var->new_mu ; */ -/* } */ - -/* //forall lambda_i in lambda_1, lambda_2, ..., lambda_n */ -/* xbt_swag_foreach(cnst, cnst_list) { */ -/* cnst->lambda = cnst->new_lambda; */ -/* } */ - /* * Now computes the values of each variable (\rho) based on * the values of \lambda and \mu. @@ -154,6 +142,7 @@ void lagrange_solve(lmm_system_t sys) if(var->weight <=0) var->value = 0.0; else { + //compute sigma_i + mu_i tmp = 0; for(i=0; icnsts_number; i++){ tmp += (var->cnsts[i].constraint)->lambda; @@ -161,14 +150,15 @@ void lagrange_solve(lmm_system_t sys) tmp+=var->mu; } - if(tmp == 0.0) - WARN0("CAUTION: division by 0.0"); + //uses the partial differential inverse function + tmp = var->func_fpi(var, tmp); //computes de overall_error - if(overall_error < fabs(var->value - 1.0/tmp)){ - overall_error = fabs(var->value - 1.0/tmp); + if(overall_error < fabs(var->value - tmp)){ + overall_error = fabs(var->value - tmp); } - var->value = 1.0 / tmp; + + var->value = tmp; } DEBUG4("======> value of var %s (%p) = %e, overall_error = %e", (char *)var->id, var, var->value, overall_error); } @@ -301,14 +291,22 @@ double dicotomi(double init, double diff(double, void*), void *var_cnst, double */ double partial_diff_mu(double mu, void *param_var){ double mu_partial=0.0; + double sigma_mu=0.0; lmm_variable_t var = (lmm_variable_t)param_var; int i; - //for each link with capacity cnsts[i] that uses flow of variable var do + //compute sigma_i for(i=0; icnsts_number; i++) - mu_partial += (var->cnsts[i].constraint)->lambda; + sigma_mu += (var->cnsts[i].constraint)->lambda; + + //compute sigma_i + mu_i + sigma_mu += var->mu; - mu_partial = ( -1.0 / (mu_partial + mu) ) + var->bound; + //use auxiliar function passing (sigma_i + mu_i) + mu_partial = diff_aux(var, sigma_mu) ; + + //add the RTT limit + mu_partial += var->bound; return mu_partial; } @@ -318,56 +316,63 @@ double partial_diff_mu(double mu, void *param_var){ */ double partial_diff_lambda(double lambda, void *param_cnst){ - double tmp=0.0; int i; xbt_swag_t elem_list = NULL; lmm_element_t elem = NULL; lmm_variable_t var = NULL; lmm_constraint_t cnst= (lmm_constraint_t) param_cnst; double lambda_partial=0.0; - + double sigma_mu=0.0; elem_list = &(cnst->element_set); - DEBUG2("Computting diff of cnst (%p) %s", cnst, (char *)cnst->id); xbt_swag_foreach(elem, elem_list) { var = elem->variable; if(var->weight<=0) continue; - tmp = 0; - - //DEBUG2("===> Variable (%p) %s", var, (char *)var->id); + //initilize de sumation variable + sigma_mu = 0.0; + //compute sigma_i of variable var for(i=0; icnsts_number; i++){ - tmp += (var->cnsts[i].constraint)->lambda; - //DEBUG1("======> lambda %e + ", (var->cnsts[i].constraint)->lambda); + sigma_mu += (var->cnsts[i].constraint)->lambda; } - if(var->bound > 0) - tmp += var->mu; - - - //DEBUG2("======> lambda - %e + %e ", cnst->lambda, lambda); + //add mu_i if this flow has a RTT constraint associated + if(var->bound > 0) sigma_mu += var->mu; - tmp = tmp - cnst->lambda + lambda; + //replace value of cnst->lambda by the value of parameter lambda + sigma_mu = (sigma_mu - cnst->lambda) + lambda; - //avoid a disaster value of lambda - //if(tmp==0) tmp = 10e-8; - - lambda_partial += (-1.0/tmp); - - //DEBUG1("======> %e ", (-1.0/tmp)); + //use the auxiliar function passing (\sigma_i + \mu_i) + lambda_partial += diff_aux(var, sigma_mu); } lambda_partial += cnst->bound; - //DEBUG1("===> %e ", lambda_partial); - return lambda_partial; } + + +double diff_aux(lmm_variable_t var, double x){ + double tmp_fp, tmp_fpi, tmp_fpip, result; + + xbt_assert0(var->func_fp, "Initialize the protocol functions first create variables before."); + + tmp_fp = var->func_fp(var, x); + tmp_fpi = var->func_fpi(var, x); + tmp_fpip = var->func_fpip(var, x); + + result = tmp_fpip*(var->func_fp(var, tmp_fpi)); + result = result - tmp_fpi; + + result = result - (tmp_fpip * x); + + return result; +} @@ -375,3 +380,4 @@ double partial_diff_lambda(double lambda, void *param_cnst){ + diff --git a/src/surf/maxmin.c b/src/surf/maxmin.c index d616c715e0..e36c5c88fe 100644 --- a/src/surf/maxmin.c +++ b/src/surf/maxmin.c @@ -174,7 +174,13 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, var->weight = weight; var->bound = bound; var->value = 0.0; - var->df = 0.0; + var->df = 1.0; + + var->func_f = func_f_def; + var->func_fp = func_fp_def; + var->func_fpi = func_fpi_def; + var->func_fpip = func_fpip_def; + if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set)); else xbt_swag_insert_at_tail(var,&(sys->variable_set)); XBT_OUT; @@ -616,6 +622,8 @@ lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint return xbt_swag_getNext(cnst,(sys->active_constraint_set).offset); } + + /** \brief Attribute the value bound to var->bound. * * \param func_f default function f associated with the chosen protocol flavor @@ -623,7 +631,7 @@ lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint * \param func_fpi inverse of the partial differential of f (f prime inverse, (f')^{-1}) * \param func_fpip partial differential of the inverse of the partial differential of f (f prime inverse prime, ((f')^{-1})') * - * Set default functions to the ones passed as parameters. + * Set default functions to the ones passed as parameters. This is a polimorfism in C pure, enjoy the roots of programming. * */ void lmm_set_default_protocol_functions(double (* func_f) (lmm_variable_t var, double x), @@ -645,73 +653,93 @@ void lmm_set_default_protocol_functions(double (* func_f) (lmm_variable_t var */ /* - * For Reno f: $\alpha_f d_f \log\left(x_f\right)$ + * For Vegas f: $\alpha_f d_f \log\left(x_f\right)$ */ -double func_reno_f(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); +double func_vegas_f(lmm_variable_t var, double x){ return var->df * log(x); } /* - * For Reno fp: $\frac{\alpha D_f}{x}$ + * For Vegas fp: $\frac{\alpha D_f}{x}$ */ -double func_reno_fp(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); +double func_vegas_fp(lmm_variable_t var, double x){ + //avoid a disaster value - c'est du bricolage mais ca marche + if(x == 0) x = 10e-8; return var->df/x; } /* - * For Reno fpi: $\frac{\alpha D_f}{x}$ + * For Vegas fpi: $\frac{\alpha D_f}{x}$ */ -double func_reno_fpi(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); +double func_vegas_fpi(lmm_variable_t var, double x){ + //avoid a disaster value - c'est du bricolage mais ca marche + if(x == 0) x = 10e-8; return var->df/x; } /* - * For Reno fpip: $-\frac{\alpha D_f}{x^2}$ + * For Vegas fpip: $-\frac{\alpha D_f}{x^2}$ */ -double func_reno_fpip(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); +double func_vegas_fpip(lmm_variable_t var, double x){ + //avoid a disaster value - c'est du bricolage mais ca marche + if(x == 0) x = 10e-8; return -( var->df/(x*x) ) ; } /* - * For Vegas f: $\frac{\sqrt{\frac{3}{2}}}{D_f} \arctan\left(\sqrt{\frac{3}{2}}x_f D_f\right)$ + * For Reno f: $\frac{\sqrt{\frac{3}{2}}}{D_f} \arctan\left(\sqrt{\frac{3}{2}}x_f D_f\right)$ */ -double func_vegas_f(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); +double func_reno_f(lmm_variable_t var, double x){ + xbt_assert0( var->df, "Please report this bug."); // \sqrt{3/2} = 0.8164965808 return (0.8164965808 / var->df) * atan( (0.8164965808 / var->df)*x ); } /* - * For Vegas fp: $\frac{3{D_f}^2}{3{D_f}^2x^2 + 2}$ + * For Reno fp: $\frac{3}{3 {D_f}^2 x^2 + 2}$ */ -double func_vegas_fp(lmm_variable_t var, double x){ - xbt_assert0(x,"Please report this bug."); - return (3*var->df*var->df) / (3*var->df*var->df*x*x + 2); +double func_reno_fp(lmm_variable_t var, double x){ + return 3 / (3*var->df*var->df*x*x + 2); } /* - * For Vegas fpi: $\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}$ + * For Reno fpi: $\sqrt{\frac{1}{{D_f}^2 x} - \frac{2}{3{D_f}^2}}$ */ -double func_vegas_fpi(lmm_variable_t var, double x){ +double func_reno_fpi(lmm_variable_t var, double x){ double res_fpi; - xbt_assert0( (x<0.0) ,"Please report this bug."); - xbt_assert0( (var->df<0.0), "Please report this bug."); - res_fpi = (1/x) - 2/(3*var->df*var->df); - return sqrt(res_fpi); + xbt_assert0( var->df, "Please report this bug."); + + //avoid a disaster value - c'est du bricolage mais ca marche + if(x == 0) x = 10e-8; + + res_fpi = 1/(var->df*var->df*x) - 2/(3*var->df*var->df); + + //avoid a disaster value of res_fpi + if(res_fpi < 0.0) return 0.0; + else return sqrt(res_fpi); } /* - * For Vegas fpip: $-\frac{1}{2x^2\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}}$ + * For Reno fpip: $-\frac{1}{2 {D_f}^2 x^2\sqrt{\frac{1}{{D_f}^2 x} - \frac{2}{3{D_f}^2}}}$ */ -double func_vegas_fpip(lmm_variable_t var, double x){ +double func_reno_fpip(lmm_variable_t var, double x){ double res_fpip; - xbt_assert0(x,"Please report this bug."); - xbt_assert0( (x<0.0), "Please report this bug."); - res_fpip = sqrt(1/x - 2/(3*var->df*var->df)); - return -(1/(2*x*x*res_fpip)); + double critical_test; + + xbt_assert0(var->df,"Please report this bug."); + + //avoid division by zero - c'est du bricolage mais ca marche + if(x == 0) x = 10e-8; + + res_fpip = 1/(var->df*var->df*x) - 2/(3*var->df*var->df); + + //avoid square root of negative number + if(res_fpip < 0.0) return 0.0; + + //avoid division by zero + critical_test = (2*var->df*var->df*x*x*sqrt(res_fpip)); + + if(critical_test == 0.0) return 0.0; + else return -(1/critical_test); } diff --git a/testsuite/surf/simeng_usage.c b/testsuite/surf/simeng_usage.c index b9aaebf22d..7924e1de8b 100644 --- a/testsuite/surf/simeng_usage.c +++ b/testsuite/surf/simeng_usage.c @@ -32,7 +32,8 @@ XBT_LOG_NEW_DEFAULT_CATEGORY(surf_test,"Messages specific for surf example"); typedef enum { MAXMIN, SDP, - LAGRANGE + LAGRANGE_RENO, + LAGRANGE_VEGAS, } method_t; void test1(method_t method); @@ -48,6 +49,15 @@ void test1(method_t method) lmm_variable_t R_2 = NULL; lmm_variable_t R_3 = NULL; + if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas + lmm_set_default_protocol_functions(func_vegas_f, func_vegas_fp, func_vegas_fpi, func_vegas_fpip); + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno + lmm_set_default_protocol_functions(func_reno_f, func_reno_fp, func_reno_fpi, func_reno_fpip); + } + + Sys = lmm_system_new(); L1 = lmm_constraint_new(Sys, (void *) "L1", 1.0); L2 = lmm_constraint_new(Sys, (void *) "L2", 10.0); @@ -74,16 +84,32 @@ void test1(method_t method) PRINT_VAR(R_3); DEBUG0("\n"); - if(method==MAXMIN) + + +Added the generic method to model fairness depending on the +transport protocol specific constraints and behavior. Protocols +TCP Reno and Vegas already implemented. Seems to work +with the testbed in src/testsuite/surf/simeng_usage. Still +need to be tested using a msg application. + + + + + if(method==MAXMIN){ lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) + }else if(method==SDP){ sdp_solve(Sys); #endif - else if(method==LAGRANGE) + }else if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas + lagrange_solve(Sys); + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno lagrange_solve(Sys); - else + }else{ xbt_assert0(0,"Invalid method"); + } PRINT_VAR(R_1_2_3); PRINT_VAR(R_1); @@ -103,6 +129,15 @@ void test2(method_t method) lmm_variable_t T1 = NULL; lmm_variable_t T2 = NULL; + + if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas + lmm_set_default_protocol_functions(func_vegas_f, func_vegas_fp, func_vegas_fpi, func_vegas_fpip); + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno + lmm_set_default_protocol_functions(func_reno_f, func_reno_fp, func_reno_fpi, func_reno_fpip); + } + Sys = lmm_system_new(); CPU1 = lmm_constraint_new(Sys, (void *) "CPU1", 200.0); CPU2 = lmm_constraint_new(Sys, (void *) "CPU2", 100.0); @@ -117,16 +152,23 @@ void test2(method_t method) PRINT_VAR(T2); DEBUG0("\n"); - if(method==MAXMIN) + + + if(method==MAXMIN){ lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) + }else if(method==SDP){ sdp_solve(Sys); #endif - else if(method==LAGRANGE) + }else if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas + lagrange_solve(Sys); + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno lagrange_solve(Sys); - else + }else{ xbt_assert0(0,"Invalid method"); + } PRINT_VAR(T1); PRINT_VAR(T2); @@ -156,6 +198,7 @@ void test3(method_t method) /*array to add the the constraints of fictiv variables */ double B[15] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, + 1, 1, 1, 1, 1}; A = (double **)calloc(links+5, sizeof(double)); @@ -242,6 +285,14 @@ void test3(method_t method) A[14][15] = 1.0; + if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas + lmm_set_default_protocol_functions(func_vegas_f, func_vegas_fp, func_vegas_fpi, func_vegas_fpip); + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno + lmm_set_default_protocol_functions(func_reno_f, func_reno_fp, func_reno_fpi, func_reno_fpip); + } + Sys = lmm_system_new(); @@ -289,16 +340,21 @@ void test3(method_t method) PRINT_VAR(tmp_var[j]); } - if(method==MAXMIN) + if(method==MAXMIN){ lmm_solve(Sys); #ifdef HAVE_SDP - else if(method==SDP) + }else if(method==SDP){ sdp_solve(Sys); #endif - else if(method==LAGRANGE) + }else if(method==LAGRANGE_VEGAS){ + //set default functions for TCP Vegas lagrange_solve(Sys); - else + }else if(method==LAGRANGE_RENO){ + //set default functions for TCP Reno + lagrange_solve(Sys); + }else{ xbt_assert0(0,"Invalid method"); + } for(j=0; j<16; j++){ PRINT_VAR(tmp_var[j]); @@ -318,35 +374,41 @@ int main(int argc, char **argv) { xbt_init(&argc,argv); -/* DEBUG0("***** Test 1 (Max-Min) ***** \n"); */ -/* test1(MAXMIN); */ -/* #ifdef HAVE_SDP */ -/* DEBUG0("***** Test 1 (SDP) ***** \n"); */ -/* test1(SDP); */ -/* #endif */ -/* DEBUG0("***** Test 1 (Lagrange - dicotomi) ***** \n"); */ -/* test1(LAGRANGE); */ + DEBUG0("***** Test 1 (Max-Min) ***** \n"); + test1(MAXMIN); +#ifdef HAVE_SDP + DEBUG0("***** Test 1 (SDP) ***** \n"); + test1(SDP); +#endif + DEBUG0("***** Test 1 (Lagrange - Vegas) ***** \n"); + test1(LAGRANGE_VEGAS); + DEBUG0("***** Test 1 (Lagrange - Reno) ***** \n"); + test1(LAGRANGE_RENO); -/* DEBUG0("***** Test 2 (Max-Min) ***** \n"); */ -/* test2(MAXMIN); */ -/* #ifdef HAVE_SDP */ -/* DEBUG0("***** Test 2 (SDP) ***** \n"); */ -/* test2(SDP); */ -/* #endif */ -/* DEBUG0("***** Test 2 (Lagrange) ***** \n"); */ -/* test2(LAGRANGE); */ + DEBUG0("***** Test 2 (Max-Min) ***** \n"); + test2(MAXMIN); +#ifdef HAVE_SDP + DEBUG0("***** Test 2 (SDP) ***** \n"); + test2(SDP); +#endif + DEBUG0("***** Test 2 (Lagrange - Vegas) ***** \n"); + test2(LAGRANGE_VEGAS); + DEBUG0("***** Test 2 (Lagrange - Reno) ***** \n"); + test2(LAGRANGE_RENO); -/* DEBUG0("***** Test 3 (Max-Min) ***** \n"); */ -/* test3(MAXMIN); */ + + DEBUG0("***** Test 3 (Max-Min) ***** \n"); + test3(MAXMIN); #ifdef HAVE_SDP DEBUG0("***** Test 3 (SDP) ***** \n"); test3(SDP); -#endif - DEBUG0("***** Test 3 (Lagrange) ***** \n"); - test3(LAGRANGE); - +#endif + DEBUG0("***** Test 3 (Lagrange - Vegas) ***** \n"); + test3(LAGRANGE_VEGAS); + DEBUG0("***** Test 3 (Lagrange - Reno) ***** \n"); + test3(LAGRANGE_RENO); return 0; } -- 2.20.1