From: velho Date: Fri, 29 Jun 2007 15:21:29 +0000 (+0000) Subject: Added all TCP VEGAS/RENO related functions. TODO: the diff functions in X-Git-Tag: v3.3~1739 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/92a1a3afd9e836da4c7cec7022097b7956c6d749 Added all TCP VEGAS/RENO related functions. TODO: the diff functions in file lagrange.c. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3621 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- diff --git a/src/include/surf/maxmin.h b/src/include/surf/maxmin.h index 98c5f27ce5..81a1a3ef46 100644 --- a/src/include/surf/maxmin.h +++ b/src/include/surf/maxmin.h @@ -62,17 +62,7 @@ void lmm_update(lmm_system_t sys, lmm_constraint_t cnst, void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, double bound); -/** \brief Add the value delta to var->df the sum of latencys. - * - * \param sys the lmm_system_t - * \param var the lmm_variable_t - * - * Add the value delta to var->df (the sum of latencys associated to the - * flow). Whenever this function is called a change is signed in the system. To - * avoid false system changing detection it is a good idea to test - * (delta != 0) before calling it. - * - */ + void lmm_update_variable_latency(lmm_system_t sys, lmm_variable_t var, double delta); @@ -98,4 +88,33 @@ void lagrange_solve(lmm_system_t sys); void lagrange_dicotomi_solve(lmm_system_t sys); + + +/** + * Default functions associated to the chosen protocol. When + * using the lagrangian approach. + */ +double (* func_f_def ) (lmm_variable_t , double); +double (* func_fp_def ) (lmm_variable_t , double); +double (* func_fpi_def ) (lmm_variable_t , double); +double (* func_fpip_def) (lmm_variable_t , double); + + + +void lmm_set_default_protocol_functions(double (* func_f) (lmm_variable_t var, double x), + double (* func_fp) (lmm_variable_t var, double x), + double (* func_fpi) (lmm_variable_t var, double x), + double (* func_fpip) (lmm_variable_t var, double x)); + +double func_reno_f(lmm_variable_t var, double x); +double func_reno_fp(lmm_variable_t var, double x); +double func_reno_fpi(lmm_variable_t var, double x); +double func_reno_fpip(lmm_variable_t var, double x); + +double func_vegas_f(lmm_variable_t var, double x); +double func_vegas_fp(lmm_variable_t var, double x); +double func_vegas_fpi(lmm_variable_t var, double x); +double func_vegas_fpip(lmm_variable_t var, double x); + + #endif /* _SURF_MAXMIN_H */ diff --git a/src/include/surf/surf.h b/src/include/surf/surf.h index 267a97a3c2..a35a9923e4 100644 --- a/src/include/surf/surf.h +++ b/src/include/surf/surf.h @@ -345,12 +345,67 @@ XBT_PUBLIC(void) surf_workstation_resource_init_CLM03(const char *filename); * * \see surf_workstation_resource_init_CLM03() */ - XBT_PUBLIC(void) surf_workstation_resource_init_KCCFLN05(const char *filename); - +/** \brief Initializes the platform with the model KCCFLN05 using the proportional + * approach as described in [TAG03]. + * + * \ingroup SURF_resources + * \param filename XML platform file name + * + * This function implements the proportional fairness known as the maximization + * of sum ( x1*x2*...*xn ). + * + * Reference: + * + * [TAG03]. Corinne Touati, Eitan Altman, and Jérôme Galtier. + * Semi-definite programming approach for bandwidth allocation and routing in networks. + * Game Theory and Applications, 9:169-179, December 2003. Nova publisher. + * With this model, the workstations and the network are handled together. + * There is no network resource. This platform model is the default one for + * MSG and SimDag. + * + * \see surf_workstation_resource_init_CLM03() + */ XBT_PUBLIC(void) surf_workstation_resource_init_KCCFLN05_proportionnal(const char *filename); +/** \brief Initializes the platform with the model KCCFLN05 using a lagrange + * optimization approach to compute the effectivet bandwidth of each flow based + * on the Vegas TCP flavor fairness as shown in [LOW03]. + * + * \ingroup SURF_resources + * \param filename XML platform file name + * + * This problem is related to max( sum( a * Df * ln(xi) ) ) which is equivalent + * to the proportional fairness. + * + * Reference: + * [LOW03] S. H. Low. A duality model of TCP and queue management algorithms. + * IEEE/ACM Transaction on Networking, 11(4):525-536, 2003. + * + */ +XBT_PUBLIC(void) surf_workstation_resource_init_KCCFLN05_Vegas(const char *filename); + +/** \brief Initializes the platform with the model KCCFLN05 using a lagrange + * optimization approach to compute the effectivet bandwidth of each flow based + * on the Reno TCP flavor fairness as shown in [LOW03]. + * + * \ingroup SURF_resources + * \param filename XML platform file name + * + * The problem is related to max( sum( arctan(C * Df * xi) ) ). + * + * Reference: + * [LOW03] S. H. Low. A duality model of TCP and queue management algorithms. + * IEEE/ACM Transaction on Networking, 11(4):525-536, 2003. + * + * \see surf_workstation_resource_init_KCCFLN05_Vegas() + */ +XBT_PUBLIC(void) surf_workstation_resource_init_KCCFLN05_Reno(const char *filename); + + + + #ifdef USE_GTNETS XBT_PUBLIC(void) surf_workstation_resource_init_GTNETS(const char *filename); #endif @@ -424,6 +479,7 @@ XBT_PUBLIC(double)surf_get_clock(void); */ XBT_PUBLIC(void) surf_exit(void); + SG_END_DECL() #endif /* _SURF_SURF_H */ diff --git a/src/msg/global.c b/src/msg/global.c index 6bb1f927ef..db2623660a 100644 --- a/src/msg/global.c +++ b/src/msg/global.c @@ -1,3 +1,4 @@ + /* $Id$ */ /* Copyright (c) 2002,2003,2004 Arnaud Legrand. All rights reserved. */ diff --git a/src/surf/maxmin.c b/src/surf/maxmin.c index 2131d8fb06..d616c715e0 100644 --- a/src/surf/maxmin.c +++ b/src/surf/maxmin.c @@ -11,6 +11,7 @@ #include "xbt/mallocator.h" #include "maxmin_private.h" #include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, "Logging specific to SURF (maxmin)"); @@ -527,6 +528,18 @@ void lmm_update(lmm_system_t sys, lmm_constraint_t cnst, } } +/** \brief Attribute the value bound to var->bound. + * + * \param sys the lmm_system_t + * \param var the lmm_variable_t + * \param bound the new bound to associate with var + * + * Makes var->bound equal to bound. Whenever this function is called + * a change is signed in the system. To + * avoid false system changing detection it is a good idea to test + * (bound != 0) before calling it. + * + */ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, double bound) { @@ -534,6 +547,18 @@ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, var->bound = bound; } +/** \brief Add the value delta to var->df (the sum of latencies). + * + * \param sys the lmm_system_t associated + * \param var the lmm_variable_t which need to updated + * \param delta the variation of the latency + * + * Add the value delta to var->df (the sum of latencys associated to the + * flow). Whenever this function is called a change is signed in the system. To + * avoid false system changing detection it is a good idea to test + * (delta != 0) before calling it. + * + */ void lmm_update_variable_latency(lmm_system_t sys, lmm_variable_t var, double delta) { @@ -591,3 +616,102 @@ 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 + * \param func_fp partial differential of f (f prime, f') + * \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. + * + */ +void lmm_set_default_protocol_functions(double (* func_f) (lmm_variable_t var, double x), + double (* func_fp) (lmm_variable_t var, double x), + double (* func_fpi) (lmm_variable_t var, double x), + double (* func_fpip) (lmm_variable_t var, double x)) + +{ + func_f_def = func_f; + func_fp_def = func_fp; + func_fpi_def = func_fpi; + func_fpip_def = func_fpip; +} + + +/* + * NOTE for Reno: all functions consider the network + * coeficient (alpha) equal to 1. + */ + +/* + * For Reno 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."); + return var->df * log(x); +} + +/* + * For Reno fp: $\frac{\alpha D_f}{x}$ + */ +double func_reno_fp(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return var->df/x; +} + +/* + * For Reno fpi: $\frac{\alpha D_f}{x}$ + */ +double func_reno_fpi(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return var->df/x; +} + +/* + * For Reno fpip: $-\frac{\alpha D_f}{x^2}$ + */ +double func_reno_fpip(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + 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)$ + */ +double func_vegas_f(lmm_variable_t var, double x){ + xbt_assert0(x,"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}$ + */ +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); +} + +/* + * For Vegas fpi: $\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}$ + */ +double func_vegas_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); +} + +/* + * For Vegas fpip: $-\frac{1}{2x^2\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}}$ + */ +double func_vegas_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)); +} diff --git a/src/surf/workstation_KCCFLN05.c b/src/surf/workstation_KCCFLN05.c index 1097df4e55..e3878a2fd6 100644 --- a/src/surf/workstation_KCCFLN05.c +++ b/src/surf/workstation_KCCFLN05.c @@ -1079,3 +1079,34 @@ void surf_workstation_resource_init_KCCFLN05_proportionnal(const char *filename) use_sdp_solver=1; xbt_dynar_push(resource_list, &surf_workstation_resource); } + +void surf_workstation_resource_init_KCCFLN05_Vegas(const char *filename) +{ + xbt_assert0(!surf_cpu_resource, "CPU resource type already defined"); + xbt_assert0(!surf_network_resource, "network resource type already defined"); + resource_init_internal(); + parse_file(filename); + + lmm_set_default_protocol_functions(func_vegas_f, func_vegas_fp, func_vegas_fpi, func_vegas_fpip); + + surf_workstation_resource->common_public->name = "Workstation KCCFLN05 (proportionnal)"; + use_lagrange_solver=1; + xbt_dynar_push(resource_list, &surf_workstation_resource); +} + +void surf_workstation_resource_init_KCCFLN05_Reno(const char *filename) +{ + xbt_assert0(!surf_cpu_resource, "CPU resource type already defined"); + xbt_assert0(!surf_network_resource, "network resource type already defined"); + resource_init_internal(); + parse_file(filename); + + lmm_set_default_protocol_functions(func_reno_f, func_reno_fp, func_reno_fpi, func_reno_fpip); + + surf_workstation_resource->common_public->name = "Workstation KCCFLN05 (proportionnal)"; + use_lagrange_solver=1; + xbt_dynar_push(resource_list, &surf_workstation_resource); +} + + + diff --git a/src/surf/workstation_KCCFLN05_private.h b/src/surf/workstation_KCCFLN05_private.h index 458808a4aa..c7ff0a757a 100644 --- a/src/surf/workstation_KCCFLN05_private.h +++ b/src/surf/workstation_KCCFLN05_private.h @@ -79,4 +79,7 @@ typedef struct surf_action_workstation_KCCFLN05 { } s_surf_action_workstation_KCCFLN05_t, *surf_action_workstation_KCCFLN05_t; + + + #endif /* _SURF_WORKSTATION_KCCFLN05_PRIVATE_H */