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)
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.
if(var->weight <=0)
var->value = 0.0;
else {
+ //compute sigma_i + mu_i
tmp = 0;
for(i=0; i<var->cnsts_number; i++){
tmp += (var->cnsts[i].constraint)->lambda;
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);
}
*/
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; i<var->cnsts_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;
}
*/
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; i<var->cnsts_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;
+}
+
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;
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
* \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),
*/
/*
- * 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);
}
typedef enum {
MAXMIN,
SDP,
- LAGRANGE
+ LAGRANGE_RENO,
+ LAGRANGE_VEGAS,
} method_t;
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);
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);
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);
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);
/*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));
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();
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]);
{
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;
}