From 7ab56eb9d4ef29905a76380fff022c9e189d89ca Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Wed, 19 Jun 2013 05:11:02 +0000 Subject: [PATCH] renaming mlp solver for consistency --- src/ats/Makefile.am | 2 +- src/ats/gnunet-service-ats_addresses.c | 4 +- src/ats/gnunet-service-ats_addresses.h | 2 +- src/ats/gnunet-service-ats_addresses_mlp.c | 1892 -------------------- src/ats/gnunet-service-ats_addresses_mlp.h | 487 ----- src/ats/gnunet-service-ats_normalization.c | 2 +- src/ats/gnunet-service-ats_normalization.h | 2 +- 7 files changed, 6 insertions(+), 2385 deletions(-) delete mode 100644 src/ats/gnunet-service-ats_addresses_mlp.c delete mode 100644 src/ats/gnunet-service-ats_addresses_mlp.h diff --git a/src/ats/Makefile.am b/src/ats/Makefile.am index 4b4823888..0fc88dd24 100644 --- a/src/ats/Makefile.am +++ b/src/ats/Makefile.am @@ -17,7 +17,7 @@ endif if HAVE_LIBGLPK GN_LIBGLPK = -lglpk - GN_MLP_SRC = gnunet-service-ats_addresses_mlp.c gnunet-service-ats_addresses_mlp.h + GN_MLP_SRC = gnunet-service-ats-solver_mlp.c gnunet-service-ats-solver_mlp.h GN_MLP_TEST = test_ats_mlp GN_MLP_TEST_UPDATE = test_ats_mlp_update GN_MLP_TEST_AVG = test_ats_mlp_averaging diff --git a/src/ats/gnunet-service-ats_addresses.c b/src/ats/gnunet-service-ats_addresses.c index baf49dfcc..e0a2449c1 100644 --- a/src/ats/gnunet-service-ats_addresses.c +++ b/src/ats/gnunet-service-ats_addresses.c @@ -33,7 +33,7 @@ #include "gnunet-service-ats_scheduling.h" #include "gnunet-service-ats_reservations.h" #if HAVE_LIBGLPK -#include "gnunet-service-ats_addresses_mlp.h" +#include "gnunet-service-ats-solver_mlp.h" #endif #include "gnunet-service-ats-solver_proportional.h" @@ -1310,7 +1310,7 @@ normalized_preference_changed_cb (void *cls, } const double * -get_preferences_cb (void *cls, struct GNUNET_PeerIdentity *id) +get_preferences_cb (void *cls, const struct GNUNET_PeerIdentity *id) { return GAS_normalization_get_preferences (id); } diff --git a/src/ats/gnunet-service-ats_addresses.h b/src/ats/gnunet-service-ats_addresses.h index e62f73315..0da559d20 100644 --- a/src/ats/gnunet-service-ats_addresses.h +++ b/src/ats/gnunet-service-ats_addresses.h @@ -355,7 +355,7 @@ typedef void (*GAS_bandwidth_changed_cb) (void *cls, struct ATS_Address *address); typedef const double * - (*GAS_get_preferences) (void *cls, struct GNUNET_PeerIdentity *id); + (*GAS_get_preferences) (void *cls, const struct GNUNET_PeerIdentity *id); /* diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c deleted file mode 100644 index 38c7c0019..000000000 --- a/src/ats/gnunet-service-ats_addresses_mlp.c +++ /dev/null @@ -1,1892 +0,0 @@ -/* - This file is part of GNUnet. - (C) 2011 Christian Grothoff (and other contributing authors) - - GNUnet is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 3, or (at your - option) any later version. - - GNUnet is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. -*/ - -/** - * @file ats/gnunet-service-ats_addresses_mlp.c - * @brief ats mlp problem solver - * @author Matthias Wachs - * @author Christian Grothoff - */ -#include "platform.h" -#include "gnunet_util_lib.h" -#include "gnunet-service-ats_addresses.h" -#include "gnunet-service-ats_addresses_mlp.h" -#include "gnunet_statistics_service.h" -#include "glpk.h" - -/** - * - * NOTE: Do not modify this documentation. This documentation is based on - * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex - * use build_txt.sh to generate plaintext output - * - * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby - * optimizing an mixed integer programming problem. The MLP solver uses a - * number of constraints to find the best adddress for a peer and an optimal - * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the - * MLP problem. - * - * We defined a constraint system to find an optimal bandwidth assignment. - * This constraint system uses as an input data addresses, bandwidth quotas, - * preferences and quality values. This constraint system is stored in an - * matrix based equotation system. - * - * 5 Using GLPK - * - * A (M)LP problem consists of a target function to optimizes, constraints - * and rows and columns. FIXME GLP uses three arrays to index the matrix: two - * integer arrays storing the row and column indices in the matrix and an - * float array to store the coeeficient. - * - * To solve the problem we first find an initial solution for the LP problem - * using the LP solver and then find an MLP solution based on this solution - * using the MLP solver. - * - * Solving (M)LP problems has the property that finding an initial solution - * for the LP problem is computationally expensive and finding the MLP - * solution is cheaper. This is especially interesting an existing LP - * solution can be reused if only coefficients in the matrix have changed - * (addresses updated). Only when the problem size changes (addresses added - * or deleted) a new LP solution has to be found. - * - * Intended usage - * The mlp solver solves the bandwidth assignment problem only on demand when - * an address suggestion is requested. When an address is requested mlp the - * solves the mlp problem and if the active address or the bandwidth assigned - * changes it calls the callback to addresses. The mlp solver gets notified - * about new addresses (adding sessions), removed addresses (address - * deletions) and address updates. To benefit from the mlp properties - * mentioned in section 5 the solver rembers if since the last solution - * addresses were added or deleted (problem size changed, problem has to be - * rebuild and solved from sratch) or if addresses were updated and the - * existing solution can be reused. - * - * 5.1 Input data - * - * The quotas for each network segment are passed by addresses. MLP can be - * adapted using configuration settings and uses the following parameters: - * * MLP_MAX_DURATION: - * Maximum duration for a MLP solution procees (default: 3 sec.) - * * MLP_MAX_DURATION: - * Maximum number of iterations for a MLP solution process (default: - * 1024) - * * MLP_MIN_CONNECTIONS: - * Minimum number of desired connections (default: 4) - * * MLP_MIN_BANDWIDTH: - * Minimum amount of bandwidth assigned to an address (default: 1024) - * * MLP_COEFFICIENT_D: - * Diversity coefficient (default: 1.0) - * * MLP_COEFFICIENT_R: - * Relativity coefficient (default: 1.0) - * * MLP_COEFFICIENT_U: - * Utilization coefficient (default: 1.0) - * * MLP_COEFFICIENT_D: - * Diversity coefficient (default: 1.0) - * * MLP_COEFFICIENT_QUALITY_DELAY: - * Quality delay coefficient (default: 1.0) - * * MLP_COEFFICIENT_QUALITY_DISTANCE: - * Quality distance coefficient (default: 1.0) - * * MLP_COEFFICIENT_QUALITY_DISTANCE: - * Quality distance coefficient (default: 1.0) - * * MLP_COEFFICIENT_QUALITY_DISTANCE: - * Quality distance coefficient (default: 1.0) - * * MLP_COEFFICIENT_QUALITY_DISTANCE: - * Quality distance coefficient (default: 1.0) - * - * 5.2 Data structures used - * - * mlp has for each known peer a struct ATS_Peer containing information about - * a specific peer. The address field solver_information contains information - * about the mlp properties of this address. - * - * 5.3 Initializing - * - * During initialization mlp initializes the GLPK libray used to solve the - * MLP problem: it initializes the glpk environment and creates an initial LP - * problem. Next it loads the configuration values from the configuration or - * uses the default values configured in -addresses_mlp.h. The quotas used - * are given by addresses but may have to be adjusted. mlp uses a upper limit - * for the bandwidth assigned called BIG M and a minimum amount of bandwidth - * an address gets assigned as well as a minium desired number of - * connections. If the configured quota is bigger than BIG M, it is reduced - * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS - * *MLP_MIN_BANDWIDTH it is increased to this value. - * - * 5.4 Shutdown - - */ - -#define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__) - -/** - * Print debug output for mlp problem creation - */ -#define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO - -/** - * Enable GLPK verbose output - */ -#define VERBOSE_GLPK GNUNET_NO - -/** - * Maximize bandwidth assigned - * - * This option can be used to test if problem can be solved at all without - * optimizing for utility, diversity or relativity - * - */ -#define MAXIMIZE_FOR_BANDWIDTH_ASSIGNED GNUNET_NO - -/** - * Intercept GLPK terminal output - * @param info the mlp handle - * @param s the string to print - * @return 0: glpk prints output on terminal, 0 != surpress output - */ -static int -mlp_term_hook (void *info, const char *s) -{ - /* Not needed atm struct MLP_information *mlp = info; */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "%s", s); - return 1; -} - - -/** - * Reset peers for next problem creation - * - * @param cls not used - * @param key the key - * @param value ATS_Peer - * @return GNUNET_OK - */ -static int -reset_peers (void *cls, const struct GNUNET_HashCode * key, void *value) - { - struct ATS_Peer *peer = value; - peer->processed = GNUNET_NO; - return GNUNET_OK; - } - -/** - * Delete the MLP problem and free the constrain matrix - * - * @param mlp the MLP handle - */ -static void -mlp_delete_problem (struct GAS_MLP_Handle *mlp) -{ - int c; - if (mlp == NULL) - return; - if (mlp->p.prob != NULL) - { - glp_delete_prob(mlp->p.prob); - mlp->p.prob = NULL; - } - - /* delete row index */ - if (mlp->p.ia != NULL) - { - GNUNET_free (mlp->p.ia); - mlp->p.ia = NULL; - } - - /* delete column index */ - if (mlp->p.ja != NULL) - { - GNUNET_free (mlp->p.ja); - mlp->p.ja = NULL; - } - - /* delete coefficients */ - if (mlp->p.ar != NULL) - { - GNUNET_free (mlp->p.ar); - mlp->p.ar = NULL; - } - mlp->p.ci = 0; - mlp->p.prob = NULL; - - mlp->p.c_d = MLP_UNDEFINED; - mlp->p.c_r = MLP_UNDEFINED; - mlp->p.r_c2 = MLP_UNDEFINED; - mlp->p.r_c4 = MLP_UNDEFINED; - mlp->p.r_c6 = MLP_UNDEFINED; - mlp->p.r_c9 = MLP_UNDEFINED; - for (c = 0; c < mlp->pv.m_q ; c ++) - mlp->p.r_q[c] = MLP_UNDEFINED; - for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++) - mlp->p.r_quota[c] = MLP_UNDEFINED; - mlp->p.ci = MLP_UNDEFINED; - - - GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &reset_peers, NULL); -} - - -/** - * Translate ATS properties to text - * Just intended for debugging - * - * @param ats_index the ATS index - * @return string with result - */ -const char * -mlp_ats_to_string (int ats_index) -{ - switch (ats_index) { - case GNUNET_ATS_ARRAY_TERMINATOR: - return "GNUNET_ATS_ARRAY_TERMINATOR"; - case GNUNET_ATS_UTILIZATION_UP: - return "GNUNET_ATS_UTILIZATION_UP"; - case GNUNET_ATS_UTILIZATION_DOWN: - return "GNUNET_ATS_UTILIZATION_DOWN"; - case GNUNET_ATS_COST_LAN: - return "GNUNET_ATS_COST_LAN"; - case GNUNET_ATS_COST_WAN: - return "GNUNET_ATS_COST_LAN"; - case GNUNET_ATS_COST_WLAN: - return "GNUNET_ATS_COST_WLAN"; - case GNUNET_ATS_NETWORK_TYPE: - return "GNUNET_ATS_NETWORK_TYPE"; - case GNUNET_ATS_QUALITY_NET_DELAY: - return "GNUNET_ATS_QUALITY_NET_DELAY"; - case GNUNET_ATS_QUALITY_NET_DISTANCE: - return "GNUNET_ATS_QUALITY_NET_DISTANCE"; - default: - GNUNET_break (0); - return "unknown"; - } -} - -/** - * Translate glpk status error codes to text - * @param retcode return code - * @return string with result - */ -const char * -mlp_status_to_string (int retcode) -{ - switch (retcode) { - case GLP_UNDEF: - return "solution is undefined"; - case GLP_FEAS: - return "solution is feasible"; - case GLP_INFEAS: - return "solution is infeasible"; - case GLP_NOFEAS: - return "no feasible solution exists"; - case GLP_OPT: - return "solution is optimal"; - case GLP_UNBND: - return "solution is unbounded"; - default: - GNUNET_break (0); - return "unknown error"; - } -} - -/** - * Translate glpk solver error codes to text - * @param retcode return code - * @return string with result - */ -const char * -mlp_solve_to_string (int retcode) -{ - switch (retcode) { - case 0: - return "ok"; - case GLP_EBADB: - return "invalid basis"; - case GLP_ESING: - return "singular matrix"; - case GLP_ECOND: - return "ill-conditioned matrix"; - case GLP_EBOUND: - return "invalid bounds"; - case GLP_EFAIL: - return "solver failed"; - case GLP_EOBJLL: - return "objective lower limit reached"; - case GLP_EOBJUL: - return "objective upper limit reached"; - case GLP_EITLIM: - return "iteration limit exceeded"; - case GLP_ETMLIM: - return "time limit exceeded"; - case GLP_ENOPFS: - return "no primal feasible solution"; - case GLP_ENODFS: - return "no dual feasible solution"; - case GLP_EROOT: - return "root LP optimum not provided"; - case GLP_ESTOP: - return "search terminated by application"; - case GLP_EMIPGAP: - return "relative mip gap tolerance reached"; - case GLP_ENOFEAS: - return "no dual feasible solution"; - case GLP_ENOCVG: - return "no convergence"; - case GLP_EINSTAB: - return "numerical instability"; - case GLP_EDATA: - return "invalid data"; - case GLP_ERANGE: - return "result out of range"; - default: - GNUNET_break (0); - return "unknown error"; - } -} - -/** - * Extract an ATS performance info from an address - * - * @param address the address - * @param type the type to extract in HBO - * @return the value in HBO or GNUNET_ATS_VALUE_UNDEFINED in HBO if value does not exist - */ -static int -get_performance_info (struct ATS_Address *address, uint32_t type) -{ - int c1; - GNUNET_assert (NULL != address); - - if ((NULL == address->atsi) || (0 == address->atsi_count)) - return GNUNET_ATS_VALUE_UNDEFINED; - - for (c1 = 0; c1 < address->atsi_count; c1++) - { - if (ntohl(address->atsi[c1].type) == type) - return ntohl(address->atsi[c1].value); - } - return GNUNET_ATS_VALUE_UNDEFINED; -} - - -struct CountContext -{ - struct GNUNET_CONTAINER_MultiHashMap * peers; - int result; -}; - -static int -mlp_create_problem_count_addresses_it (void *cls, const struct GNUNET_HashCode *key, void *value) -{ - struct CountContext *cctx = cls; - /* Check if we have to add this peer due to a pending request */ - if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(cctx->peers, key)) - cctx->result++; - return GNUNET_OK; -} - -static int mlp_create_problem_count_addresses ( - struct GNUNET_CONTAINER_MultiHashMap * peers, - struct GNUNET_CONTAINER_MultiHashMap * addresses) -{ - struct CountContext cctx; - cctx.peers = peers; - cctx.result = 0; - GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_create_problem_count_addresses_it, &cctx); - return cctx.result; -} - - - -static void -mlp_create_problem_set_value (struct MLP_Problem *p, - int row, int col, double val, - int line) -{ - if ((p->ci) >= p->num_elements) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n", - line, p->ci + 1, p->num_elements); - GNUNET_break (0); - return; - } - if ((0 == row) || (0 == col)) - GNUNET_break (0); - p->ia[p->ci] = row ; - p->ja[p->ci] = col; - p->ar[p->ci] = val; -#if DEBUG_MLP_PROBLEM_CREATION - LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n", - line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]); -#endif - p->ci++; -} - -static int -mlp_create_problem_create_column (struct MLP_Problem *p, char *name, - unsigned int type, unsigned int bound, double lb, double ub, - double coef) -{ - int col = glp_add_cols (p->prob, 1); - glp_set_col_name (p->prob, col, name); - glp_set_col_bnds (p->prob, col, bound, lb, ub); - glp_set_col_kind (p->prob, col, type); - glp_set_obj_coef (p->prob, col, coef); -#if DEBUG_MLP_PROBLEM_CREATION - LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n", - col, name, coef); -#endif - return col; -} - -static int -mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name, - unsigned int bound, double lb, double ub) -{ - char * op; - int row = glp_add_rows (p->prob, 1); - /* set row name */ - glp_set_row_name (p->prob, row, name); - /* set row bounds: <= 0 */ - glp_set_row_bnds (p->prob, row, bound, lb, ub); - switch (bound) { - case GLP_UP: - GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub); - break; - case GLP_DB: - GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub); - break; - case GLP_FX: - GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub); - break; - case GLP_LO: - GNUNET_asprintf(&op, "%.2f <= x <= inf", lb); - break; - default: - GNUNET_asprintf(&op, "ERROR"); - break; - } -#if DEBUG_MLP_PROBLEM_CREATION - LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n", - row, name, op); -#endif - GNUNET_free (op); - return row; -} - -/** - * Create the - * - address columns b and n - * - address dependent constraint rows c1, c3 - * - peer dependent rows c2 and c9 - * - Set address dependent entries in problem matrix as well - */ -static int -mlp_create_problem_add_address_information (void *cls, const struct GNUNET_HashCode *key, void *value) -{ - struct GAS_MLP_Handle *mlp = cls; - struct MLP_Problem *p = &mlp->p; - struct ATS_Address *address = value; - struct ATS_Peer *peer; - struct MLP_information *mlpi; - char *name; - uint32_t addr_net; - int c; - - /* Check if we have to add this peer due to a pending request */ - if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key)) - return GNUNET_OK; - - mlpi = address->solver_information; - if (NULL == mlpi) - { - GNUNET_break (0); - return GNUNET_OK; - } - - /* Get peer */ - peer = GNUNET_CONTAINER_multihashmap_get (mlp->peers, key); - if (peer->processed == GNUNET_NO) - { - /* Add peer dependent constraints */ - /* Add constraint c2 */ - GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer)); - peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0); - GNUNET_free (name); - /* Add constraint c9 */ - GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer)); - peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0); - GNUNET_free (name); - /* c 9) set coefficient */ - mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f, __LINE__); - - peer->processed = GNUNET_YES; - } - - /* Reset addresses' solver information */ - mlpi->c_b = 0; - mlpi->c_n = 0; - mlpi->n = 0; - mlpi->r_c1 = 0; - mlpi->r_c3 = 0; - for (c = 0; c < mlp->pv.m_q; c++) - mlpi->r_q[0] = 0; - - /* Add bandwidth column */ - GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address); -#if TEST_MAX_BW_ASSIGNMENT - mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0); -#else - mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0); -#endif - - GNUNET_free (name); - - /* Add usage column */ - GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address); - mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0); - GNUNET_free (name); - - /* Add address dependent constraints */ - /* Add constraint c1) bandwidth capping - * b_t + (-M) * n_t <= 0 - * */ - GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address); - mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0); - GNUNET_free (name); - - /* c1) set b = 1 coefficient */ - mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__); - /* c1) set n = -M coefficient */ - mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -mlp->pv.BIG_M, __LINE__); - - /* Add constraint c 3) minimum bandwidth - * b_t + (-n_t * b_min) >= 0 - * */ - GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address); - mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0); - GNUNET_free (name); - - /* c3) set b = 1 coefficient */ - mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__); - /* c3) set n = -b_min coefficient */ - mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__); - - - /* Set coefficient entries in invariant rows */ - /* c 4) minimum connections */ - mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__); - /* c 6) maximize diversity */ - mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__); - /* c 2) 1 address peer peer */ - mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__); - /* c 9) relativity */ - mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__); - /* c 8) utility */ - mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__); - - /* c 10) obey network specific quotas - * (1)*b_1 + ... + (1)*b_m <= quota_n - */ - for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) - { - addr_net = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE); - if (GNUNET_ATS_VALUE_UNDEFINED == addr_net) - addr_net = GNUNET_ATS_NET_UNSPECIFIED; - - if (mlp->pv.quota_index[c] == addr_net) - { - mlp_create_problem_set_value (p, p->r_quota[c], mlpi->c_b, 1, __LINE__); - break; - } - } - - /* c 7) Optimize quality */ - /* For all quality metrics, set quality of this address */ - for (c = 0; c < mlp->pv.m_q; c++) - { - - mlp_create_problem_set_value (p, p->r_q[c], mlpi->c_b, mlpi->q_averaged[c], __LINE__); - } - - return GNUNET_OK; -} - -/** - * Create the invariant columns c4, c6, c10, c8, c7 - */ -static void -mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p) -{ - char *name; - int c; - - /* Row for c4) minimum connection */ - /* Number of minimum connections is min(|Peers|, n_min) */ - p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0); - - /* Add row for c6) */ - p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0); - /* c6 )Setting -D */ - mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__); - - /* Add rows for c 10) */ - for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) - { - char * text; - GNUNET_asprintf(&text, "c10_quota_ats_%s", GNUNET_ATS_print_network_type(mlp->pv.quota_index[c])); - p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]); - GNUNET_free (text); - } - - /* Adding rows for c 8) */ - p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0); - /* -u */ - mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__); - - /* c 7) For all quality metrics */ - for (c = 0; c < mlp->pv.m_q; c++) - { - GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c])); - p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0); - GNUNET_free (name); - mlp_create_problem_set_value (p, p->r_q[c], p->c_q[c], -1, __LINE__); - } -} - - -/** - * Create the invariant columns d, u, r, q0 ... qm - */ -static void -mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p) -{ - char *name; - int c; - -#if TEST_MAX_BW_ASSIGNMENT - mlp->pv.co_D = 0.0; - mlp->pv.co_U = 0.0; - -#endif - //mlp->pv.co_R = 0.0; - - /* Diversity d column */ - p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D); - - /* Utilization u column */ - p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U); - - /* Relativity r column */ - p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R); - - /* Quality metric columns */ - for (c = 0; c < mlp->pv.m_q; c++) - { - GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]); -#if TEST_MAX_BW_ASSIGNMENT - p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0); -#else - p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]); -#endif - GNUNET_free (name); - } -} - - -/** - * Create the MLP problem - * - * @param mlp the MLP handle - * @param addresses the hashmap containing all adresses - * @return GNUNET_OK or GNUNET_SYSERR - */ -static int -mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) -{ - struct MLP_Problem *p = &mlp->p; - int res = GNUNET_OK; - - GNUNET_assert (p->prob == NULL); - GNUNET_assert (p->ia == NULL); - GNUNET_assert (p->ja == NULL); - GNUNET_assert (p->ar == NULL); - /* Reset MLP problem struct */ - - /* create the glpk problem */ - p->prob = glp_create_prob (); - GNUNET_assert (NULL != p->prob); - p->num_peers = GNUNET_CONTAINER_multihashmap_size (mlp->peers); - p->num_addresses = mlp_create_problem_count_addresses (mlp->peers, addresses); - - /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */ - p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses + mlp->pv.m_q + p->num_peers + 2 + 1); - LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n", - p->num_peers, p->num_addresses, mlp->pv.m_q, p->num_elements); - - /* Set a problem name */ - glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution"); - /* Set optimization direction to maximize */ - glp_set_obj_dir (p->prob, GLP_MAX); - - /* Create problem matrix */ - /* last +1 caused by glpk index starting with one: [1..elements]*/ - p->ci = 1; - /* row index */ - p->ia = GNUNET_malloc (p->num_elements * sizeof (int)); - /* column index */ - p->ja = GNUNET_malloc (p->num_elements * sizeof (int)); - /* coefficient */ - p->ar = GNUNET_malloc (p->num_elements * sizeof (double)); - - if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar)) - { - LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n")); - return GNUNET_SYSERR; - } - - /* Adding invariant columns */ - mlp_create_problem_add_invariant_columns (mlp, p); - - /* Adding address independent constraint rows */ - mlp_create_problem_add_invariant_rows (mlp, p); - - /* Adding address dependent columns constraint rows */ - GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_create_problem_add_address_information, mlp); - - /* Load the matrix */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n"); - glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar); - - return res; -} - -/** - * Solves the LP problem - * - * @param mlp the MLP Handle - * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure - */ -static int -mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp) -{ - int res = 0; - - res = glp_simplex(mlp->p.prob, &mlp->control_param_lp); - if (0 == res) - LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", res, mlp_solve_to_string(res)); - else - LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res)); - - /* Analyze problem status */ - res = glp_get_status (mlp->p.prob); - switch (res) { - /* solution is optimal */ - case GLP_OPT: - /* solution is feasible */ - case GLP_FEAS: - LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", - res, mlp_status_to_string(res)); - return GNUNET_OK; - /* Problem was ill-defined, no way to handle that */ - default: - LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed, no solution: 0x%02X %s\n", - res, mlp_status_to_string(res)); - return GNUNET_SYSERR; - } -} - - -/** - * Solves the MLP problem - * - * @param mlp the MLP Handle - * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure - */ -int -mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp) -{ - int res = 0; - res = glp_intopt(mlp->p.prob, &mlp->control_param_mlp); - if (0 == res) - LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_solve_to_string(res)); - else - LOG (GNUNET_ERROR_TYPE_WARNING, "Solving MLP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res)); - /* Analyze problem status */ - res = glp_mip_status(mlp->p.prob); - switch (res) { - /* solution is optimal */ - case GLP_OPT: - /* solution is feasible */ - case GLP_FEAS: - LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_status_to_string(res)); - return GNUNET_OK; - /* Problem was ill-defined, no way to handle that */ - default: - LOG (GNUNET_ERROR_TYPE_WARNING,"Solving MLP problem failed, 0x%02X %s\n\n", res, mlp_status_to_string(res)); - return GNUNET_SYSERR; - } -} - - -/** - * Propagates the results when MLP problem was solved - * - * @param cls the MLP handle - * @param key the peer identity - * @param value the address - * @return GNUNET_OK to continue - */ -int -mlp_propagate_results (void *cls, const struct GNUNET_HashCode *key, void *value) -{ - struct GAS_MLP_Handle *mlp = cls; - struct ATS_Address *address; - struct MLP_information *mlpi; - double mlp_bw_in = MLP_NaN; - double mlp_bw_out = MLP_NaN; - double mlp_use = MLP_NaN; - - /* Check if we have to add this peer due to a pending request */ - if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key)) - return GNUNET_OK; - address = value; - GNUNET_assert (address->solver_information != NULL); - mlpi = address->solver_information; - - mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */ - if (mlp_bw_in > (double) UINT32_MAX) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" ); - mlp_bw_in = (double) UINT32_MAX; - } - mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b); - if (mlp_bw_out > (double) UINT32_MAX) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" ); - mlp_bw_out = (double) UINT32_MAX; - } - mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n); - - - - if ((GLP_YES == mlp_use) && (GNUNET_NO == address->active)) - { - /* Address switch: Activate address*/ - LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); - address->active = GNUNET_YES; - address->assigned_bw_in.value__ = htonl (mlp_bw_in); - mlpi->b_in.value__ = htonl(mlp_bw_in); - address->assigned_bw_out.value__ = htonl (mlp_bw_out); - mlpi->b_out.value__ = htonl(mlp_bw_out); - mlpi->n = mlp_use; - mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); - } - else if ((GLP_NO == mlp_use) && (GNUNET_YES == address->active)) - { - /* Address switch: Disable address*/ - LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); - address->active = GNUNET_NO; - /* Set bandwidth to 0 */ - address->assigned_bw_in.value__ = htonl (0); - mlpi->b_in.value__ = htonl(mlp_bw_in); - address->assigned_bw_out.value__ = htonl (0); - mlpi->b_out.value__ = htonl(mlp_bw_out); - mlpi->n = mlp_use; - mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); - } - else if ((mlp_bw_out != ntohl(address->assigned_bw_out.value__)) || - (mlp_bw_in != ntohl(address->assigned_bw_in.value__))) - { - /* Bandwidth changed */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); - address->assigned_bw_in.value__ = htonl (mlp_bw_in); - mlpi->b_in.value__ = htonl(mlp_bw_in); - address->assigned_bw_out.value__ = htonl (mlp_bw_out); - mlpi->b_out.value__ = htonl(mlp_bw_out); - mlpi->n = mlp_use; - mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); - } - else - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); - } - - return GNUNET_OK; -} - - - -/** - * Solves the MLP problem - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure - */ -int -GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses) -{ - struct GAS_MLP_Handle *mlp = solver; - char *filename; - int res_lp = 0; - int res_mip = 0; - struct GNUNET_TIME_Absolute start_build; - struct GNUNET_TIME_Relative duration_build; - struct GNUNET_TIME_Absolute start_lp; - struct GNUNET_TIME_Relative duration_lp; - struct GNUNET_TIME_Absolute start_mlp; - struct GNUNET_TIME_Relative duration_mlp; - GNUNET_assert (NULL != solver); - - if ((GNUNET_NO == mlp->mlp_prob_changed) && (GNUNET_NO == mlp->mlp_prob_updated)) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n"); - return GNUNET_OK; - } - - if (GNUNET_YES == mlp->mlp_prob_changed) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n"); - mlp_delete_problem (mlp); - start_build = GNUNET_TIME_absolute_get(); - if (GNUNET_SYSERR == mlp_create_problem (mlp, addresses)) - return GNUNET_SYSERR; - duration_build = GNUNET_TIME_absolute_get_duration (start_build); - mlp->control_param_lp.presolve = GLP_YES; - mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */ - } - else - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n"); - duration_build.rel_value = 0; - } - - /* Run LP solver */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "Running LP solver %s\n", (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver"); - start_lp = GNUNET_TIME_absolute_get(); - res_lp = mlp_solve_lp_problem (mlp); - duration_lp = GNUNET_TIME_absolute_get_duration (start_lp); - - - /* Run LP solver */ - LOG (GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n"); - start_mlp = GNUNET_TIME_absolute_get(); - res_mip = mlp_solve_mlp_problem (mlp); - - duration_mlp = GNUNET_TIME_absolute_get_duration (start_mlp); - - /* Save stats */ - mlp->ps.lp_res = res_lp; - mlp->ps.mip_res = res_mip; - mlp->ps.build_dur = duration_build; - mlp->ps.lp_dur = duration_lp; - mlp->ps.mip_dur = duration_mlp; - mlp->ps.lp_presolv = mlp->control_param_lp.presolve; - mlp->ps.mip_presolv = mlp->control_param_mlp.presolve; - mlp->ps.p_cols = glp_get_num_cols (mlp->p.prob); - mlp->ps.p_rows = glp_get_num_rows (mlp->p.prob); - mlp->ps.p_elements = mlp->p.num_elements; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Execution time: Build %llu ms, LP %llu ms, MLP %llu ms\n", - (unsigned long long) duration_build.rel_value, - (unsigned long long) duration_lp.rel_value, - (unsigned long long) duration_mlp.rel_value); - - /* Propagate result*/ - if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip)) - GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_propagate_results, mlp); - - struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get(); - if (GNUNET_YES == mlp->write_mip_mps) - { - /* Write problem and solution to disk */ - GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers, mlp->p.num_addresses, time.abs_value); - glp_write_mps(mlp->p.prob, GLP_MPS_FILE, NULL, filename); - GNUNET_free (filename); - } - if (GNUNET_YES == mlp->write_mip_sol) - { - GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers, mlp->p.num_addresses, time.abs_value); - glp_print_mip (mlp->p.prob, filename ); - GNUNET_free (filename); - } - - /* Reset change and update marker */ - mlp->control_param_lp.presolve = GLP_NO; - mlp->mlp_prob_updated = GNUNET_NO; - mlp->mlp_prob_changed = GNUNET_NO; - - if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip)) - return GNUNET_OK; - else - return GNUNET_SYSERR; -} - -/** - * Add a single address to the solve - * - * @param solver the solver Handle - * @param addresses the address hashmap containing all addresses - * @param address the address to add - * @param network network type of this address - */ -void -GAS_mlp_address_add (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address *address, - uint32_t network) -{ - struct GAS_MLP_Handle *mlp = solver; - struct ATS_Peer *p; - struct MLP_information *mlpi; - int c1; - int c2; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != addresses); - GNUNET_assert (NULL != address); - - - if (NULL == address->solver_information) - { - address->solver_information = GNUNET_malloc (sizeof (struct MLP_information)); - mlpi = address->solver_information; - for (c1 = 0; c1 < mlp->pv.m_q; c1++) - { - mlpi->q_averaged[c1] = DEFAULT_QUALITY; - for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++) - mlpi->q[c1][c2] = MLP_NaN; - } - } - else - LOG (GNUNET_ERROR_TYPE_ERROR, _("Adding address for peer `%s' multiple times\n"), GNUNET_i2s(&address->peer)); - - /* Is this peer included in the problem? */ - if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey))) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer)); - return; - } - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer)); - /* Problem size changed: new address for peer with pending request */ - mlp->mlp_prob_changed = GNUNET_YES; - if (GNUNET_YES == mlp->mlp_auto_solve) - GAS_mlp_solve_problem (solver, addresses); -} - - -static void -mlp_update_quality (struct GAS_MLP_Handle *mlp, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address * address, - const struct GNUNET_ATS_Information *ats_prev, uint32_t ats_prev_count) -{ - struct MLP_information *mlpi = address->solver_information; - unsigned int c_ats_entry; - unsigned int c_queue_entries; - unsigned int c_cmp; - unsigned int c_queue_it; - unsigned int c_row; - unsigned int c_qual; - unsigned int c_net; - int qual_changed; - int type_index; - int avg_index; - uint32_t type; - uint32_t prev_value; - uint32_t new_value; - double avg; - double *queue; - int rows; - double *val; - int *ind; - - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating %u quality metrics for peer `%s'\n", - ats_prev_count, GNUNET_i2s (&address->peer)); - - GNUNET_assert (NULL != mlp); - GNUNET_assert (NULL != address); - GNUNET_assert (NULL != address->solver_information); - GNUNET_assert (NULL != ats_prev); - - if (NULL == mlp->p.prob) - return; - - qual_changed = GNUNET_NO; - for (c_ats_entry = 0; c_ats_entry < ats_prev_count; c_ats_entry++) - { - type = ntohl (ats_prev[c_ats_entry].type); - prev_value = ntohl (ats_prev[c_ats_entry].value); - type_index = -1; - avg_index = -1; - - /* Check for network update */ - if (type == GNUNET_ATS_NETWORK_TYPE) - { - new_value = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE); - if (GNUNET_ATS_VALUE_UNDEFINED == new_value) - new_value = GNUNET_ATS_NET_UNSPECIFIED; - if (new_value != prev_value) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating network for peer `%s' from `%s' to `%s'\n", - GNUNET_i2s (&address->peer), - GNUNET_ATS_print_network_type(prev_value), - GNUNET_ATS_print_network_type(new_value)); - } - - if (mlpi->c_b == MLP_UNDEFINED) - continue; /* This address is not yet in the matrix*/ - - rows = glp_get_num_rows(mlp->p.prob); - ind = GNUNET_malloc (rows * sizeof (int) + 1); - val = GNUNET_malloc (rows * sizeof (double) + 1); - int length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val); - - for (c_net = 0; c_net <= length + 1; c_net ++) - { - if (ind[c_net] == mlp->p.r_quota[prev_value]) - break; /* Found index for old network */ - } - val[c_net] = 0.0; - glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val); - /* Set updated column */ - ind[c_net] = mlp->p.r_quota[new_value]; - val[c_net] = 1.0; - glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val); - GNUNET_free (ind); - GNUNET_free (val); - - rows = glp_get_num_rows(mlp->p.prob); - ind = GNUNET_malloc (rows * sizeof (int) + 1); - val = GNUNET_malloc (rows * sizeof (double) + 1); - length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val); - - for (c_net = 0; c_net <= length + 1; c_net ++) - { - if (ind[c_net] == mlp->p.r_quota[prev_value]) - LOG (GNUNET_ERROR_TYPE_DEBUG, "Removing old network index [%u] == [%f]\n",ind[c_net],val[c_net]); - if (ind[c_net] == mlp->p.r_quota[new_value]) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Setting new network index [%u] == [%f]\n",ind[c_net],val[c_net]); - break; - } - } - GNUNET_free (ind); - GNUNET_free (val); - mlp->mlp_prob_changed = GNUNET_YES; - continue; - } - - - /* Find index for this ATS type */ - for (c_cmp = 0; c_cmp < mlp->pv.m_q; c_cmp++) - { - if (type == mlp->pv.q[c_cmp]) - { - type_index = c_cmp; - break; - } - } - if (-1 == type_index) - continue; /* quality index not found */ - - /* Get average queue index */ - avg_index = mlpi->q_avg_i[type_index]; - - /* Update averaging queue */ - new_value = get_performance_info (address, type); - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating peer `%s': `%s' from %u to %u\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->pv.q[type_index]), prev_value, new_value); - GNUNET_assert (GNUNET_ATS_VALUE_UNDEFINED != new_value); - mlpi->q[type_index][avg_index] = new_value; - - /* Update averaging index */ - if (mlpi->q_avg_i[type_index] + 1 < (MLP_AVERAGING_QUEUE_LENGTH)) - mlpi->q_avg_i[type_index] ++; - else - mlpi->q_avg_i[type_index] = 0; - - /* Update average depending on ATS type */ - switch (type) - { - case GNUNET_ATS_QUALITY_NET_DISTANCE: - case GNUNET_ATS_QUALITY_NET_DELAY: - c_queue_entries = 0; - avg = 0; - for (c_queue_it = 0; c_queue_it < MLP_AVERAGING_QUEUE_LENGTH; c_queue_it++) - { - if (mlpi->q[type_index][c_queue_it] != MLP_NaN) - { - queue = mlpi->q[type_index] ; - avg += queue[c_queue_it]; - c_queue_entries ++; - } - } - if ((c_queue_entries > 0) && (avg > 0)) - /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/ - mlpi->q_averaged[type_index] = (double) c_queue_entries / avg; - else - mlpi->q_averaged[type_index] = 0.0; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating peer `%s': `%s' average sum of %u elements == %f, average == %f, weight == %f\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->pv.q[type_index]), - c_queue_entries, - avg, - avg / (double) c_queue_entries, - mlpi->q_averaged[type_index]); - qual_changed = GNUNET_YES; - break; - default: - GNUNET_break (0); - LOG (GNUNET_ERROR_TYPE_DEBUG, _("Update for ATS type `%s' not implemented!\n"), - mlp_ats_to_string(type)); - } - } - - /* Changed, but quality will be automatically set during rebuild */ - if ((GNUNET_YES == mlp->mlp_prob_changed) && - (GNUNET_YES == mlp->mlp_auto_solve)) - { - GAS_mlp_solve_problem (mlp, addresses); - return; - } - - /* Update problem matrix if required */ - if (GNUNET_NO == qual_changed) - return; - - /* Address not yet included in matrix */ - if (MLP_UNDEFINED == mlpi->c_b) - return; - - /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] - * Get column mlpi->c_b */ - rows = glp_get_num_rows(mlp->p.prob); - ind = GNUNET_malloc (rows * sizeof (int) + 1); - val = GNUNET_malloc (rows * sizeof (double) + 1); - int length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val); - - for (c_qual = 0; c_qual < mlp->pv.m_q; c_qual++) - { - for (c_row = 0; c_row <= length; c_row ++) - { - if (ind[c_row] == mlp->p.r_q[c_qual]) - val[c_row] = mlpi->q_averaged[c_qual]; - } - } - /* Set updated column */ - glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val); - GNUNET_free (ind); - GNUNET_free (val); - mlp->mlp_prob_updated = GNUNET_YES; -} - -/** - * Updates a single address in the MLP problem - * - * If the address did not exist before in the problem: - * The MLP problem has to be recreated and the problem has to be resolved - * - * ATS performance information in address are already updated, delta + previous - * values are included in atsi_prev (value GNUNET_ATS_VALUE_UNDEFINED if not existing before) - * - * Otherwise the addresses' values can be updated and the existing base can - * be reused - * - * @param solver the solver Handle - * @param addresses the address hashmap containing all addresses - * @param address the update address - * @param prev_session the new session (if changed otherwise current) - * @param prev_in_use the new address in use state (if changed otherwise current) - * @param prev_atsi ATS information updated + previous values, GNUNET_ATS_VALUE_UNDEFINED if not existing before - * @param prev_atsi_count number of atsi values updated - */ -void -GAS_mlp_address_update (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address *address, - uint32_t prev_session, - int prev_in_use, - const struct GNUNET_ATS_Information *prev_atsi, - uint32_t prev_atsi_count) -{ - struct ATS_Peer *p; - struct GAS_MLP_Handle *mlp = solver; - struct MLP_information *mlpi = address->solver_information; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != addresses); - GNUNET_assert (NULL != address); - GNUNET_assert ((NULL != prev_atsi) || (0 == prev_atsi_count)); - - if (NULL == mlpi) - { - LOG (GNUNET_ERROR_TYPE_ERROR, _("Updating address for peer `%s' not added before\n"), GNUNET_i2s(&address->peer)); - return; - } - mlp_update_quality (mlp, addresses, address, prev_atsi, prev_atsi_count); - - /* Is this peer included in the problem? */ - if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey))) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' without address request \n", GNUNET_i2s(&address->peer)); - return; - } - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' with address request \n", GNUNET_i2s(&address->peer)); - - /* Problem size changed: new address for peer with pending request */ - mlp->mlp_prob_updated = GNUNET_YES; - if (GNUNET_YES == mlp->mlp_auto_solve) - GAS_mlp_solve_problem (solver, addresses); - return; -} - -/** - * Deletes a single address in the MLP problem - * - * The MLP problem has to be recreated and the problem has to be resolved - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * the address has to be already removed from the hashmap - * @param address the address to delete - * @param session_only delete only session not whole address - */ -void -GAS_mlp_address_delete (void *solver, - struct GNUNET_CONTAINER_MultiHashMap * addresses, - struct ATS_Address *address, - int session_only) -{ - struct ATS_Peer *p; - struct GAS_MLP_Handle *mlp = solver; - struct MLP_information *mlpi; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != addresses); - GNUNET_assert (NULL != address); - - mlpi = address->solver_information; - - if (NULL != mlpi) - { - GNUNET_free (mlpi); - address->solver_information = NULL; - } - - /* Is this peer included in the problem? */ - if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey))) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' without address request \n", GNUNET_i2s(&address->peer)); - return; - } - LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' with address request \n", GNUNET_i2s(&address->peer)); - - /* Problem size changed: new address for peer with pending request */ - mlp->mlp_prob_changed = GNUNET_YES; - if (GNUNET_YES == mlp->mlp_auto_solve) - GAS_mlp_solve_problem (solver, addresses); - return; -} - - -/** - * Find the active address in the set of addresses of a peer - * @param cls destination - * @param key peer id - * @param value address - * @return GNUNET_OK - */ -static int -mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value) -{ - - struct ATS_Address *aa = (struct ATS_Address *) cls; - struct ATS_Address *addr = value; - struct MLP_information *mlpi = addr->solver_information; - if (mlpi == NULL) - return GNUNET_YES; - if (mlpi->n == GNUNET_YES) - { - aa = addr; - aa->assigned_bw_in = mlpi->b_in; - aa->assigned_bw_out = mlpi->b_out; - return GNUNET_NO; - } - return GNUNET_YES; -} - - -static double get_peer_pref_value (struct GAS_MLP_Handle *mlp, struct GNUNET_PeerIdentity *peer) -{ - double res; - const double *preferences = NULL; - int c; - preferences = mlp->get_preferences (mlp->get_preferences_cls, peer); - - res = 0.0; - for (c = 0; c < GNUNET_ATS_PreferenceCount; c++) - { - if (c != GNUNET_ATS_PREFERENCE_END) - { - //fprintf (stderr, "VALUE[%u] %s %.3f \n", c, GNUNET_i2s (&cur->addr->peer), t[c]); - res += preferences[c]; - } - } - res /= (GNUNET_ATS_PreferenceCount -1); - return res; -} - - -/** - * Get the preferred address for a specific peer - * - * @param solver the MLP Handle - * @param addresses address hashmap - * @param peer the peer - * @return suggested address - */ -const struct ATS_Address * -GAS_mlp_get_preferred_address (void *solver, - struct GNUNET_CONTAINER_MultiHashMap * addresses, - const struct GNUNET_PeerIdentity *peer) -{ - struct GAS_MLP_Handle *mlp = solver; - struct ATS_Peer *p; - struct ATS_Address *res = NULL; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != addresses); - GNUNET_assert (NULL != peer); - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", - GNUNET_i2s (peer)); - - /* Is this peer included in the problem? */ - if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey))) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding peer `%s' to list of peers with requests\n", - GNUNET_i2s (peer)); - - p = GNUNET_malloc (sizeof (struct ATS_Peer)); - p->id = (*peer); - p->f = get_peer_pref_value (mlp, peer); - GNUNET_CONTAINER_multihashmap_put (mlp->peers, &peer->hashPubKey, p, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); - - /* Added new peer, we have to rebuild problem before solving */ - mlp->mlp_prob_changed = GNUNET_YES; - } - if (GNUNET_YES == mlp->mlp_auto_solve) - GAS_mlp_solve_problem (mlp, addresses); - - /* Get prefered address */ - GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, - mlp_get_preferred_address_it, res); - - return res; -} - - -/** - * Stop notifying about address and bandwidth changes for this peer - * - * @param solver the MLP handle - * @param addresses address hashmap - * @param peer the peer - */ -void -GAS_mlp_stop_get_preferred_address (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - const struct GNUNET_PeerIdentity *peer) -{ - struct GAS_MLP_Handle *mlp = solver; - struct ATS_Peer *p = NULL; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != addresses); - GNUNET_assert (NULL != peer); - - if (NULL != (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey))) - { - GNUNET_CONTAINER_multihashmap_remove (mlp->peers, &peer->hashPubKey, p); - GNUNET_free (p); - } -} - - -/** - * Changes the preferences for a peer in the MLP problem - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * @param peer the peer - * @param kind the kind to change the preference - * @param pref_rel the relative score - */ -void -GAS_mlp_address_change_preference (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - const struct GNUNET_PeerIdentity *peer, - enum GNUNET_ATS_PreferenceKind kind, - double pref_rel) -{ - struct GAS_MLP_Handle *mlp = solver; - struct ATS_Peer *p = NULL; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n", - GNUNET_i2s(peer)); - - GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO); - - /* Update the constraints with changed preferences */ - - - /* Update quality constraint c7 */ - - /* Update relativity constraint c9 */ - if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey))) - { - LOG (GNUNET_ERROR_TYPE_ERROR, "Updating preference for unknown peer `%s' \n", GNUNET_i2s(peer)); - return; - } - p->f = get_peer_pref_value (mlp, peer); - mlp_create_problem_set_value (&mlp->p, p->r_c9, mlp->p.c_r, -p->f, __LINE__); - - - /* Problem size changed: new address for peer with pending request */ - mlp->mlp_prob_updated = GNUNET_YES; - if (GNUNET_YES == mlp->mlp_auto_solve) - GAS_mlp_solve_problem (solver, addresses); - return; -} - - -static int -mlp_free_peers (void *cls, const struct GNUNET_HashCode *key, void *value) -{ - struct GNUNET_CONTAINER_MultiHashMap *map = cls; - struct ATS_Peer *p = value; - - GNUNET_CONTAINER_multihashmap_remove (map, key, value); - GNUNET_free (p); - - return GNUNET_OK; -} - - -/** - * Shutdown the MLP problem solving component - * - * @param solver the solver handle - */ -void -GAS_mlp_done (void *solver) -{ - struct GAS_MLP_Handle *mlp = solver; - GNUNET_assert (mlp != NULL); - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n"); - mlp_delete_problem (mlp); - - GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &mlp_free_peers, mlp->peers); - GNUNET_CONTAINER_multihashmap_destroy (mlp->peers); - mlp->peers = NULL; - - /* Clean up GLPK environment */ - glp_free_env(); - GNUNET_free (mlp); - - LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n"); -} - - -/** - * Init the MLP problem solving component - * - * @param cfg the GNUNET_CONFIGURATION_Handle handle - * @param stats the GNUNET_STATISTICS handle - * @param network array of GNUNET_ATS_NetworkType with length dest_length - * @param out_dest array of outbound quotas - * @param in_dest array of outbound quota - * @param dest_length array length for quota arrays - * @param bw_changed_cb callback for changed bandwidth amounts - * @param bw_changed_cb_cls cls for callback - * @return struct GAS_MLP_Handle on success, NULL on fail - */ -void * -GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg, - const struct GNUNET_STATISTICS_Handle *stats, - int *network, - unsigned long long *out_dest, - unsigned long long *in_dest, - int dest_length, - GAS_bandwidth_changed_cb bw_changed_cb, - void *bw_changed_cb_cls, - GAS_get_preferences get_preference, - void *get_preference_cls) -{ - struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle)); - - double D; - double R; - double U; - unsigned long long tmp; - unsigned int b_min; - unsigned int n_min; - int c; - int c2; - int found; - - struct GNUNET_TIME_Relative max_duration; - long long unsigned int max_iterations; - - /* Init GLPK environment */ - int res = glp_init_env(); - switch (res) { - case 0: - LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n", - "initialization successful"); - break; - case 1: - LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n", - "environment is already initialized"); - break; - case 2: - LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n", - "initialization failed (insufficient memory)"); - GNUNET_free(mlp); - return NULL; - break; - case 3: - LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n", - "initialization failed (unsupported programming model)"); - GNUNET_free(mlp); - return NULL; - break; - default: - break; - } - - - mlp->pv.BIG_M = (double) BIG_M_VALUE; - - /* Get timeout for iterations */ - if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MLP_MAX_DURATION", &max_duration)) - { - max_duration = MLP_MAX_EXEC_DURATION; - } - - /* Get maximum number of iterations */ - if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations)) - { - max_iterations = MLP_MAX_ITERATIONS; - } - - /* Get diversity coefficient from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_D", - &tmp)) - D = (double) tmp / 100; - else - D = DEFAULT_D; - - /* Get proportionality coefficient from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_R", - &tmp)) - R = (double) tmp / 100; - else - R = DEFAULT_R; - - /* Get utilization coefficient from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_U", - &tmp)) - U = (double) tmp / 100; - else - U = DEFAULT_U; - - /* Get quality metric coefficients from configuration */ - int i_delay = MLP_NaN; - int i_distance = MLP_NaN; - int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties; - for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++) - { - /* initialize quality coefficients with default value 1.0 */ - mlp->pv.co_Q[c] = DEFAULT_QUALITY; - - mlp->pv.q[c] = q[c]; - if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY) - i_delay = c; - if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE) - i_distance = c; - } - - if ((i_delay != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_QUALITY_DELAY", - &tmp))) - - mlp->pv.co_Q[i_delay] = (double) tmp / 100; - else - mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY; - - if ((i_distance != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_QUALITY_DISTANCE", - &tmp))) - mlp->pv.co_Q[i_distance] = (double) tmp / 100; - else - mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY; - - /* Get minimum bandwidth per used address from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_MIN_BANDWIDTH", - &tmp)) - b_min = tmp; - else - { - b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); - } - - /* Get minimum number of connections from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_MIN_CONNECTIONS", - &tmp)) - n_min = tmp; - else - n_min = DEFAULT_MIN_CONNECTIONS; - - /* Init network quotas */ - int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType; - for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) - { - found = GNUNET_NO; - for (c2 = 0; c2 < dest_length; c2++) - { - if (quotas[c] == network[c2]) - { - mlp->pv.quota_index[c] = network[c2]; - mlp->pv.quota_out[c] = out_dest[c2]; - mlp->pv.quota_in[c] = in_dest[c2]; - found = GNUNET_YES; - LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n", - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_out[c], - mlp->pv.quota_in[c]); - break; - } - } - - /* Check if defined quota could make problem unsolvable */ - if ((n_min * b_min) > mlp->pv.quota_out[c]) - { - LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"), - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_out[c], - (n_min * b_min)); - mlp->pv.quota_out[c] = (n_min * b_min); - } - if ((n_min * b_min) > mlp->pv.quota_in[c]) - { - LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"), - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_in[c], - (n_min * b_min)); - mlp->pv.quota_in[c] = (n_min * b_min); - } - - /* Check if bandwidth is too big to make problem solvable */ - if (mlp->pv.BIG_M < mlp->pv.quota_out[c]) - { - LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"), - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_out[c], - mlp->pv.BIG_M); - mlp->pv.quota_out[c] = mlp->pv.BIG_M ; - } - if (mlp->pv.BIG_M < mlp->pv.quota_in[c]) - { - LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"), - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_in[c], - mlp->pv.BIG_M); - mlp->pv.quota_in[c] = mlp->pv.BIG_M ; - } - - if (GNUNET_NO == found) - { - mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); - mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); - LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"), - GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), - mlp->pv.quota_in[c], - mlp->pv.quota_out[c]); - } - } - - /* Assign options to handle */ - mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats; - mlp->bw_changed_cb = bw_changed_cb; - mlp->bw_changed_cb_cls = bw_changed_cb_cls; - mlp->get_preferences = get_preference; - mlp->get_preferences_cls = get_preference_cls; - /* Setting MLP Input variables */ - mlp->pv.co_D = D; - mlp->pv.co_R = R; - mlp->pv.co_U = U; - mlp->pv.b_min = b_min; - mlp->pv.n_min = n_min; - mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount; - mlp->write_mip_mps = GNUNET_NO; - mlp->write_mip_sol = GNUNET_NO; - mlp->mlp_prob_changed = GNUNET_NO; - mlp->mlp_prob_updated = GNUNET_NO; - mlp->mlp_auto_solve = GNUNET_YES; - mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO); - - /* Setup GLPK */ - /* Redirect GLPK output to GNUnet logging */ - glp_term_hook (&mlp_term_hook, (void *) mlp); - - /* Init LP solving parameters */ - glp_init_smcp(&mlp->control_param_lp); - mlp->control_param_lp.msg_lev = GLP_MSG_OFF; -#if VERBOSE_GLPK - mlp->control_param_lp.msg_lev = GLP_MSG_ALL; -#endif - mlp->control_param_lp.it_lim = max_iterations; - mlp->control_param_lp.tm_lim = max_duration.rel_value; - - /* Init MLP solving parameters */ - glp_init_iocp(&mlp->control_param_mlp); - mlp->control_param_mlp.msg_lev = GLP_MSG_OFF; -#if VERBOSE_GLPK - mlp->control_param_mlp.msg_lev = GLP_MSG_ALL; -#endif - mlp->control_param_mlp.tm_lim = max_duration.rel_value; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n"); - - return mlp; -} - -/* end of gnunet-service-ats_addresses_mlp.c */ diff --git a/src/ats/gnunet-service-ats_addresses_mlp.h b/src/ats/gnunet-service-ats_addresses_mlp.h deleted file mode 100644 index e7464ca96..000000000 --- a/src/ats/gnunet-service-ats_addresses_mlp.h +++ /dev/null @@ -1,487 +0,0 @@ -/* - This file is part of GNUnet. - (C) 2011 Christian Grothoff (and other contributing authors) - - GNUnet is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 3, or (at your - option) any later version. - - GNUnet is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. -*/ - -/** - * @file ats/gnunet-service-ats_addresses_mlp.h - * @brief ats MLP problem solver - * @author Matthias Wachs - * @author Christian Grothoff - */ -#include "platform.h" -#include "gnunet_statistics_service.h" -#include "gnunet-service-ats_addresses.h" -#if HAVE_LIBGLPK -#include "glpk.h" -#endif - -#ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H -#define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H - -#define BIG_M_VALUE (UINT32_MAX) /10 -#define BIG_M_STRING "unlimited" - -#define MLP_AVERAGING_QUEUE_LENGTH 3 - -#define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10) -#define MLP_MAX_ITERATIONS 4096 - -#define DEFAULT_D 1.0 -#define DEFAULT_R 1.0 -#define DEFAULT_U 1.0 -#define DEFAULT_QUALITY 1.0 -#define DEFAULT_MIN_CONNECTIONS 4 -#define DEFAULT_PEER_PREFERENCE 1.0 - -#define MLP_NaN -1 -#define MLP_UNDEFINED 0 -#define GLP_YES 1.0 -#define GLP_NO 0.0 - - -struct MLP_Solution -{ - struct GNUNET_TIME_Relative build_dur; - struct GNUNET_TIME_Relative lp_dur; - struct GNUNET_TIME_Relative mip_dur; - - int lp_res; - int lp_presolv; - int mip_res; - int mip_presolv; - - int p_elements; - int p_cols; - int p_rows; - - int n_peers; - int n_addresses; - -}; - -struct ATS_Peer -{ - struct GNUNET_PeerIdentity id; - - /* Was this peer already added to the current problem? */ - int processed; - - /* constraint 2: 1 address per peer*/ - unsigned int r_c2; - - /* constraint 9: relativity */ - unsigned int r_c9; - - /* Legacy preference value */ - double f; - -#if 0 - /* Array of quality preferences */ - double f_q[GNUNET_ATS_QualityPropertiesCount]; - -#endif -}; - - - -struct MLP_Problem -{ - /** - * GLPK (MLP) problem object - */ -#if HAVE_LIBGLPK - glp_prob *prob; -#else - void *prob; -#endif - /* Number of addresses in problem */ - unsigned int num_addresses; - /* Number of peers in problem */ - unsigned int num_peers; - /* Number of elements in problem matrix */ - unsigned int num_elements; - - /* Row index constraint 2: */ - unsigned int r_c2; - /* Row index constraint 4: minimum connections */ - unsigned int r_c4; - /* Row index constraint 6: maximize diversity */ - unsigned int r_c6; - /* Row index constraint 8: utilization*/ - unsigned int r_c8; - /* Row index constraint 9: relativity*/ - unsigned int r_c9; - /* Row indices quality metrics */ - int r_q[GNUNET_ATS_QualityPropertiesCount]; - /* Row indices ATS network quotas */ - int r_quota[GNUNET_ATS_NetworkTypeCount]; - - /* Column index Diversity (D) column */ - int c_d; - /* Column index Utilization (U) column */ - int c_u; - /* Column index Proportionality (R) column */ - int c_r; - /* Column index quality metrics */ - int c_q[GNUNET_ATS_QualityPropertiesCount]; - - /* Problem matrix */ - /* Current index */ - unsigned int ci; - /* Row index array */ - int *ia; - /* Column index array */ - int *ja; - /* Column index value */ - double *ar; -}; - -struct MLP_Variables -{ - /* Big M value for bandwidth capping */ - double BIG_M; - - /* ATS Quality metrics - * - * Array with GNUNET_ATS_QualityPropertiesCount elements - * contains mapping to GNUNET_ATS_Property*/ - int q[GNUNET_ATS_QualityPropertiesCount]; - - /* Number of quality metrics */ - int m_q; - - /* Number of quality metrics */ - int m_rc; - - /* Quality metric coefficients*/ - double co_Q[GNUNET_ATS_QualityPropertiesCount]; - - /* Ressource costs coefficients*/ - double co_RC[GNUNET_ATS_QualityPropertiesCount]; - - /* Diversity coefficient */ - double co_D; - - /* Utility coefficient */ - double co_U; - - /* Relativity coefficient */ - double co_R; - - /* Minimum bandwidth assigned to an address */ - unsigned int b_min; - - /* Minimum number of addresses with bandwidth assigned */ - unsigned int n_min; - - /* Quotas */ - /* Array mapping array index to ATS network */ - int quota_index [GNUNET_ATS_NetworkTypeCount]; - /* Outbound quotas */ - unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount]; - /* Inbound quotas */ - - unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount]; - - /* ATS ressource costs - * array with GNUNET_ATS_QualityPropertiesCount elements - * contains mapping to GNUNET_ATS_Property - * */ - int rc[GNUNET_ATS_QualityPropertiesCount]; - -}; - - -/** - * MLP Handle - */ -struct GAS_MLP_Handle -{ - /** - * Statistics handle - */ - struct GNUNET_STATISTICS_Handle *stats; - - /** - * Addresses' bandwidth changed callback - */ - GAS_bandwidth_changed_cb bw_changed_cb; - - /** - * Addresses' bandwidth changed callback closure - */ - void *bw_changed_cb_cls; - - GAS_get_preferences get_preferences; - - void *get_preferences_cls; - - struct MLP_Problem p; - - struct MLP_Variables pv; - - struct MLP_Solution ps; - - /** - * GLPK LP control parameter - */ -#if HAVE_LIBGLPK - glp_smcp control_param_lp; -#else - void *control_param_lp; -#endif - - /** - * GLPK LP control parameter - */ -#if HAVE_LIBGLPK - glp_iocp control_param_mlp; -#else - void *control_param_mlp; -#endif - - /** - * Peers with pending address requests - */ - struct GNUNET_CONTAINER_MultiHashMap *peers; - - /** - * Was the problem updated since last solution - */ - int mlp_prob_updated; - - /** - * Has the problem size changed since last solution - */ - int mlp_prob_changed; - - /** - * Solve the problem automatically when updates occur? - * Default: GNUNET_YES - * Can be disabled for test and measurements - */ - int mlp_auto_solve; - - /** - * Write MILP problem to a MPS file - */ - int write_mip_mps; - - /** - * Write MILP problem to a MPS file - */ - int write_mip_sol; - -}; - - -/** - * Address specific MLP information - */ -struct MLP_information -{ - - /* Bandwidth assigned */ - struct GNUNET_BANDWIDTH_Value32NBO b_out; - struct GNUNET_BANDWIDTH_Value32NBO b_in; - - /* Address selected */ - int n; - - /* bandwidth column index */ - signed int c_b; - - /* address usage column */ - signed int c_n; - - /* row indexes */ - - /* constraint 1: bandwidth capping */ - unsigned int r_c1; - - /* constraint 3: minimum bandwidth */ - unsigned int r_c3; - - /* Quality information row indices */ - unsigned int r_q[GNUNET_ATS_QualityPropertiesCount]; - - /* Quality information */ - double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH]; - - /* Quality information averaged */ - double q_averaged[GNUNET_ATS_QualityPropertiesCount]; - - /* Averaging index */ - int q_avg_i[GNUNET_ATS_QualityPropertiesCount]; -}; - -/** - * Solves the MLP problem - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure - */ -int -GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses); - - -/** - * Init the MLP problem solving component - * - * @param cfg configuration handle - * @param stats the GNUNET_STATISTICS handle - * @param network array of GNUNET_ATS_NetworkType with length dest_length - * @param out_dest array of outbound quotas - * @param in_dest array of outbound quota - * @param dest_length array length for quota arrays - * @param bw_changed_cb callback for changed bandwidth amounts - * @param bw_changed_cb_cls cls for callback - * @return struct GAS_MLP_Handle on success, NULL on fail - */ -void * -GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg, - const struct GNUNET_STATISTICS_Handle *stats, - int *network, - unsigned long long *out_dest, - unsigned long long *in_dest, - int dest_length, - GAS_bandwidth_changed_cb bw_changed_cb, - void *bw_changed_cb_cls, - GAS_get_preferences get_preference, - void *get_preference_cls); - - -/** - * Add a single address within a network to the solver - * - * @param solver the solver Handle - * @param addresses the address hashmap containing all addresses - * @param address the address to add - * @param network network type of this address - */ -void -GAS_mlp_address_add (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address *address, - uint32_t network); - -/** - * Updates a single address in the MLP problem - * - * If the address did not exist before in the problem: - * The MLP problem has to be recreated and the problem has to be resolved - * - * ATS performance information in address are already updated, delta + previous - * values are included in atsi_prev (value GNUNET_ATS_VALUE_UNDEFINED if not existing before) - * - * Otherwise the addresses' values can be updated and the existing base can - * be reused - * - * @param solver the solver Handle - * @param addresses the address hashmap containing all addresses - * @param address the update address - * @param prev_session the new session (if changed otherwise current) - * @param prev_in_use the new address in use state (if changed otherwise current) - * @param prev_atsi ATS information updated + previous values, GNUNET_ATS_VALUE_UNDEFINED if not existing before - * @param prev_atsi_count number of atsi values updated - */ -void -GAS_mlp_address_update (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address *address, - uint32_t prev_session, - int prev_in_use, - const struct GNUNET_ATS_Information *prev_atsi, - uint32_t prev_atsi_count); - - -/** - * Deletes a single address in the MLP problem - * - * The MLP problem has to be recreated and the problem has to be resolved - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * the address has to be already removed from the hashmap - * @param address the address to delete - * @param session_only delete only session not whole address - */ -void -GAS_mlp_address_delete (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - struct ATS_Address *address, - int session_only); - - -/** - * Changes the preferences for a peer in the MLP problem - * - * @param solver the MLP Handle - * @param addresses the address hashmap - * @param peer the peer - * @param kind the kind to change the preference - * @param pref_rel the relative score - */ -void -GAS_mlp_address_change_preference (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - const struct GNUNET_PeerIdentity *peer, - enum GNUNET_ATS_PreferenceKind kind, - double pref_rel); - - -/** - * Get the preferred address for a specific peer - * - * @param solver the MLP Handle - * @param addresses address hashmap - * @param peer the peer - * @return suggested address - */ -const struct ATS_Address * -GAS_mlp_get_preferred_address (void *solver, - struct GNUNET_CONTAINER_MultiHashMap * addresses, - const struct GNUNET_PeerIdentity *peer); - - -/** - * Stop notifying about address and bandwidth changes for this peer - * - * @param solver the MLP handle - * @param addresses address hashmap - * @param peer the peer - */ - -void -GAS_mlp_stop_get_preferred_address (void *solver, - struct GNUNET_CONTAINER_MultiHashMap *addresses, - const struct GNUNET_PeerIdentity *peer); - - -/** - * Shutdown the MLP problem solving component - * - * @param solver the solver handle - */ -void -GAS_mlp_done (void *solver); - -#endif -/* end of gnunet-service-ats_addresses_mlp.h */ diff --git a/src/ats/gnunet-service-ats_normalization.c b/src/ats/gnunet-service-ats_normalization.c index c437a7f8e..7a461778e 100644 --- a/src/ats/gnunet-service-ats_normalization.c +++ b/src/ats/gnunet-service-ats_normalization.c @@ -420,7 +420,7 @@ GAS_normalization_change_preference (void *src, * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind, default preferences if peer does not exist */ const double * -GAS_normalization_get_preferences (struct GNUNET_PeerIdentity *id) +GAS_normalization_get_preferences (const struct GNUNET_PeerIdentity *id) { GNUNET_assert (NULL != peers); GNUNET_assert (NULL != id); diff --git a/src/ats/gnunet-service-ats_normalization.h b/src/ats/gnunet-service-ats_normalization.h index ff94138e6..78fddbc56 100644 --- a/src/ats/gnunet-service-ats_normalization.h +++ b/src/ats/gnunet-service-ats_normalization.h @@ -47,7 +47,7 @@ typedef void * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind, NULL if peer does not exist */ const double * -GAS_normalization_get_preferences (struct GNUNET_PeerIdentity *id); +GAS_normalization_get_preferences (const struct GNUNET_PeerIdentity *id); /** -- 2.25.1