From da67ab282339deae88f88f125a7fa9de3d7bcfd3 Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Wed, 19 Jun 2013 05:11:51 +0000 Subject: [PATCH] renamed --- src/ats/gnunet-service-ats-solver_mlp.c | 1891 +++++++++++++++++++++++ src/ats/gnunet-service-ats-solver_mlp.h | 487 ++++++ 2 files changed, 2378 insertions(+) create mode 100644 src/ats/gnunet-service-ats-solver_mlp.c create mode 100644 src/ats/gnunet-service-ats-solver_mlp.h diff --git a/src/ats/gnunet-service-ats-solver_mlp.c b/src/ats/gnunet-service-ats-solver_mlp.c new file mode 100644 index 000000000..d7762d430 --- /dev/null +++ b/src/ats/gnunet-service-ats-solver_mlp.c @@ -0,0 +1,1891 @@ +/* + 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-solver_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, const 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-solver_mlp.h b/src/ats/gnunet-service-ats-solver_mlp.h new file mode 100644 index 000000000..e7464ca96 --- /dev/null +++ b/src/ats/gnunet-service-ats-solver_mlp.h @@ -0,0 +1,487 @@ +/* + 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 */ -- 2.25.1