From 4a4e894b55ffb547811f1b6befe4ffc6cc57709e Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Wed, 20 Feb 2013 16:24:28 +0000 Subject: [PATCH] changes --- src/ats/gnunet-service-ats_addresses_mlp.c | 1483 +++++++++++--------- src/ats/gnunet-service-ats_addresses_mlp.h | 25 + src/ats/test_ats_mlp.c | 11 +- 3 files changed, 847 insertions(+), 672 deletions(-) diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c index c8d9759a1..95a7a3b11 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.c +++ b/src/ats/gnunet-service-ats_addresses_mlp.c @@ -137,10 +137,64 @@ #define WRITE_MLP GNUNET_NO #define DEBUG_ATS GNUNET_NO -#define VERBOSE_GLPK GNUNET_NO +#define VERBOSE_GLPK GNUNET_YES + + +/** + * 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; */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s", s); + return 1; +} + +/** + * Delete the MLP problem and free the constrain matrix + * + * @param mlp the MLP handle + */ +static void +mlp_delete_problem (struct GAS_MLP_Handle *mlp) +{ + if (mlp != NULL) + { + if (mlp->prob != NULL) + glp_delete_prob(mlp->prob); + + /* delete row index */ + if (mlp->ia != NULL) + { + GNUNET_free (mlp->ia); + mlp->ia = NULL; + } + + /* delete column index */ + if (mlp->ja != NULL) + { + GNUNET_free (mlp->ja); + mlp->ja = NULL; + } + + /* delete coefficients */ + if (mlp->ar != NULL) + { + GNUNET_free (mlp->ar); + mlp->ar = NULL; + } + mlp->ci = 0; + mlp->prob = NULL; + } +} + + +#if 0 -#define ENABLE_C8 GNUNET_YES -#define ENABLE_C9 GNUNET_YES /** * Translate glpk solver error codes to text * @param retcode return code @@ -277,57 +331,6 @@ mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *pee return res; } -/** - * 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; */ - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s", s); - return 1; -} - -/** - * Delete the MLP problem and free the constrain matrix - * - * @param mlp the MLP handle - */ -static void -mlp_delete_problem (struct GAS_MLP_Handle *mlp) -{ - if (mlp != NULL) - { - if (mlp->prob != NULL) - glp_delete_prob(mlp->prob); - - /* delete row index */ - if (mlp->ia != NULL) - { - GNUNET_free (mlp->ia); - mlp->ia = NULL; - } - - /* delete column index */ - if (mlp->ja != NULL) - { - GNUNET_free (mlp->ja); - mlp->ja = NULL; - } - - /* delete coefficients */ - if (mlp->ar != NULL) - { - GNUNET_free (mlp->ar); - mlp->ar = NULL; - } - mlp->ci = 0; - mlp->prob = NULL; - } -} /** * Add constraints that are iterating over "forall addresses" @@ -781,93 +784,6 @@ create_columns_it (void *cls, const struct GNUNET_HashCode * key, void *value) -/** - * 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) -{ - int res = GNUNET_OK; - int col; - int c; - char *name; - - GNUNET_assert (mlp->prob == NULL); - - /* create the glpk problem */ - mlp->prob = glp_create_prob (); - - /* Set a problem name */ - glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution"); - - /* Set optimization direction to maximize */ - glp_set_obj_dir (mlp->prob, GLP_MAX); - - /* Adding invariant columns */ - - /* Diversity d column */ - col = glp_add_cols (mlp->prob, 1); - mlp->c_d = col; - /* Column name */ - glp_set_col_name (mlp->prob, col, "d"); - /* Column objective function coefficient */ - glp_set_obj_coef (mlp->prob, col, mlp->co_D); - /* Column lower bound = 0.0 */ - glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); - - /* Utilization u column */ - col = glp_add_cols (mlp->prob, 1); - mlp->c_u = col; - /* Column name */ - glp_set_col_name (mlp->prob, col, "u"); - /* Column objective function coefficient */ - glp_set_obj_coef (mlp->prob, col, mlp->co_U); - /* Column lower bound = 0.0 */ - glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); - -#if ENABLE_C9 - /* Relativity r column */ - col = glp_add_cols (mlp->prob, 1); - mlp->c_r = col; - /* Column name */ - glp_set_col_name (mlp->prob, col, "r"); - /* Column objective function coefficient */ - glp_set_obj_coef (mlp->prob, col, mlp->co_R); - /* Column lower bound = 0.0 */ - glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); -#endif - - /* Quality metric columns */ - col = glp_add_cols(mlp->prob, mlp->m_q); - for (c = 0; c < mlp->m_q; c++) - { - mlp->c_q[c] = col + c; - GNUNET_asprintf (&name, "q_%u", mlp->q[c]); - glp_set_col_name (mlp->prob, col + c, name); - /* Column lower bound = 0.0 */ - glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0); - GNUNET_free (name); - /* Coefficient == Qm */ - glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]); - } - - /* Add columns for addresses */ - GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp); - - /* Add constraints */ - mlp_add_constraints_all_addresses (mlp, addresses); - - /* Load the matrix */ - glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar); - - return res; -} - - /** * Solves the LP problem * @@ -1056,584 +972,425 @@ mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) } -/** - * Solves the MLP problem - * - * @param solver the MLP Handle - * @param ctx solution context - * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure - */ -int -GAS_mlp_solve_problem (void *solver, struct GAS_MLP_SolutionContext *ctx) -{ - struct GAS_MLP_Handle *mlp = solver; - int res; - - GNUNET_assert (NULL != solver); - GNUNET_assert (NULL != ctx); - /* Check if solving is already running */ - if (GNUNET_YES == mlp->semaphore) - { - if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK) - { - GNUNET_SCHEDULER_cancel(mlp->mlp_task); - mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; - } - mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp); - return GNUNET_SYSERR; - } - mlp->semaphore = GNUNET_YES; - mlp->last_execution = GNUNET_TIME_absolute_get (); +static void +update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address) +{ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n", + GNUNET_i2s (&address->peer)); - ctx->lp_result = GNUNET_SYSERR; - ctx->mlp_result = GNUNET_SYSERR; - ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL; - ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL; + GNUNET_assert (NULL != address); + GNUNET_assert (NULL != address->solver_information); +// GNUNET_assert (NULL != address->ats); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n"); -#if WRITE_MLP - char * name; - static int i; - i++; - GNUNET_asprintf(&name, "problem_%i", i); - glp_write_lp (mlp->prob, 0, name); - GNUNET_free (name); -# endif + struct MLP_information *mlpi = address->solver_information; + //struct GNUNET_ATS_Information *ats = address->ats; + GNUNET_assert (mlpi != NULL); - res = mlp_solve_lp_problem (mlp, ctx); - ctx->lp_result = res; - if (res != GNUNET_OK) + int c; + for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++) { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n"); - mlp->semaphore = GNUNET_NO; - return GNUNET_SYSERR; - } -#if WRITE_MLP - GNUNET_asprintf(&name, "problem_%i_lp_solution", i); - glp_print_sol (mlp->prob, name); - GNUNET_free (name); -# endif + /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */ + int index = GNUNET_SYSERR; + if (index == GNUNET_SYSERR) + continue; + /* FIXME + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n", + GNUNET_i2s (&address->peer), + mlp_ats_to_string(mlp->q[c]), + (double) ats[index].value); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n"); - res = mlp_solve_mlp_problem (mlp, ctx); - ctx->mlp_result = res; - if (res != GNUNET_OK) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n"); - mlp->semaphore = GNUNET_NO; - return GNUNET_SYSERR; - } -#if WRITE_MLP - GNUNET_asprintf(&name, "problem_%i_mlp_solution", i); - glp_print_mip (mlp->prob, name); - GNUNET_free (name); -# endif + int i = mlpi->q_avg_i[c];*/ + double * qp = mlpi->q[c]; + /* FIXME + qp[i] = (double) ats[index].value; + */ - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n", - (GNUNET_OK == res) ? "successfully" : "failed", - ctx->lp_duration.rel_value, - ctx->mlp_duration.rel_value); - /* Process result */ - struct ATS_Peer *p = NULL; - struct ATS_Address *a = NULL; - struct MLP_information *mlpi = NULL; + int t; + for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n", + GNUNET_i2s (&address->peer), + mlp_ats_to_string(mlp->q[c]), + t, + qp[t]); + } - for (p = mlp->peer_head; p != NULL; p = p->next) - { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id)); - for (a = p->head; a != NULL; a = a->next) + if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH)) + mlpi->q_avg_i[c] ++; + else + mlpi->q_avg_i[c] = 0; + + + int c2; + int c3; + double avg = 0.0; + switch (mlp->q[c]) { - double b = 0.0; - double n = 0.0; + case GNUNET_ATS_QUALITY_NET_DELAY: + c3 = 0; + for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++) + { + if (mlpi->q[c][c2] != -1) + { + double * t2 = mlpi->q[c] ; + avg += t2[c2]; + c3 ++; + } + } + if ((c3 > 0) && (avg > 0)) + /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/ + mlpi->q_averaged[c] = (double) c3 / avg; + else + mlpi->q_averaged[c] = 0.0; - mlpi = a->solver_information; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n", + GNUNET_i2s (&address->peer), + mlp_ats_to_string(mlp->q[c]), + avg, + avg / (double) c3, + mlpi->q_averaged[c]); - b = glp_mip_col_val(mlp->prob, mlpi->c_b); - mlpi->b = b; + break; + case GNUNET_ATS_QUALITY_NET_DISTANCE: + c3 = 0; + for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++) + { + if (mlpi->q[c][c2] != -1) + { + double * t2 = mlpi->q[c] ; + avg += t2[c2]; + c3 ++; + } + } + if ((c3 > 0) && (avg > 0)) + /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/ + mlpi->q_averaged[c] = (double) c3 / avg; + else + mlpi->q_averaged[c] = 0.0; - n = glp_mip_col_val(mlp->prob, mlpi->c_n); - if (n == 1.0) - { - /* This is the address to be used */ - mlpi->n = GNUNET_YES; - } - else - { - /* This is the address not used */ - mlpi->n = GNUNET_NO; - } + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n", + GNUNET_i2s (&address->peer), + mlp_ats_to_string(mlp->q[c]), + avg, + avg / (double) c3, + mlpi->q_averaged[c]); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n", - (n == 1.0) ? "[x]" : "[ ]", b); + break; + default: + break; + } - /* Notify addresses */ - if ((ntohl(a->assigned_bw_in.value__) != b) || - (ntohl(a->assigned_bw_out.value__) != b) || - (mlpi->n != a->active)) + if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0)) + { + + /* Get current number of columns */ + int found = GNUNET_NO; + int cols = glp_get_num_cols(mlp->prob); + int *ind = GNUNET_malloc (cols * sizeof (int) + 1); + double *val = GNUNET_malloc (cols * sizeof (double) + 1); + + /* Get the matrix row of quality */ + int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b); + int c4; + /* Get the index if matrix row of quality */ + for (c4 = 1; c4 <= length; c4++ ) { - a->assigned_bw_in.value__ = htonl(b); - a->assigned_bw_out.value__ = htonl(b); - a->active = mlpi->n; - mlp->bw_changed_cb (mlp->bw_changed_cb_cls, a); + if (mlpi->c_b == ind[c4]) + { + /* Update the value */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n", + mlp_ats_to_string(mlp->q[c]), + glp_get_col_name (mlp->prob, ind[c4]), + glp_get_row_name (mlp->prob, mlp->r_q[c]), + val[c4], + mlpi->q_averaged[c]); + val[c4] = mlpi->q_averaged[c]; + found = GNUNET_YES; + break; + } } - } - } - if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK) - { - GNUNET_SCHEDULER_cancel(mlp->mlp_task); - mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; + if (found == GNUNET_NO) + { + + ind[length+1] = mlpi->c_b; + val[length+1] = mlpi->q_averaged[c]; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%i ind[%i] val[%i]: %i %f\n", length+1, length+1, length+1, mlpi->c_b, mlpi->q_averaged[c]); + glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val); + } + else + { + /* Get the index if matrix row of quality */ + glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val); + } + + GNUNET_free (ind); + GNUNET_free (val); + } } - mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp); - mlp->semaphore = GNUNET_NO; - return res; } +#endif + /** - * Init the MLP problem solving component + * Create the MLP problem * - * @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 + * @param mlp the MLP handle + * @param addresses the hashmap containing all adresses + * @return GNUNET_OK or GNUNET_SYSERR */ -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) +static int +mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) { - 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; - struct GNUNET_TIME_Relative i_exec; + int res = GNUNET_OK; int c; - int c2; - int found; + int cur_col; + int elements = 0; + char *name; - struct GNUNET_TIME_Relative max_duration; - long long unsigned int max_iterations; + LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n", + GNUNET_CONTAINER_multihashmap_size(mlp->peers)); - /* 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; - } + GNUNET_assert (mlp->prob == NULL); - /* Create initial MLP problem */ - mlp->prob = glp_create_prob(); - if (NULL == mlp->prob) - { - LOG (GNUNET_ERROR_TYPE_ERROR, "Failed to create MLP problem!"); - GNUNET_free (mlp); - return NULL; - } + /* create the glpk problem */ + mlp->prob = glp_create_prob (); + GNUNET_assert (NULL != mlp->prob); - mlp->BIG_M = (double) BIG_M_VALUE; + /* Set a problem name */ + glp_set_prob_name (mlp->prob, "GNUnet ats bandwidth distribution"); - /* 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; - } + /* Set optimization direction to maximize */ + glp_set_obj_dir (mlp->prob, GLP_MAX); - /* Get maximum number of iterations */ - if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations)) + /* Adding invariant columns */ + /* Diversity d column */ + mlp->c_d = glp_add_cols (mlp->prob, 1); + /* Column name */ + glp_set_col_name (mlp->prob, mlp->c_d, "d"); + /* Column objective function coefficient */ + glp_set_obj_coef (mlp->prob, mlp->c_d, mlp->co_D); + /* Column lower bound = 0.0 */ + glp_set_col_bnds (mlp->prob, mlp->c_d, GLP_LO, 0.0, 0.0); + + /* Utilization u column */ + mlp->c_u = glp_add_cols (mlp->prob, 1); + /* Column name */ + glp_set_col_name (mlp->prob, mlp->c_u, "u"); + /* Column objective function coefficient */ + glp_set_obj_coef (mlp->prob, mlp->c_u, mlp->co_U); + /* Column lower bound = 0.0 */ + glp_set_col_bnds (mlp->prob, mlp->c_u, GLP_LO, 0.0, 0.0); + + /* Relativity r column */ + mlp->c_r = glp_add_cols (mlp->prob, 1); + /* Column name */ + glp_set_col_name (mlp->prob, mlp->c_r, "r"); + /* Column objective function coefficient */ + glp_set_obj_coef (mlp->prob, mlp->c_r, mlp->co_R); + /* Column lower bound = 0.0 */ + glp_set_col_bnds (mlp->prob, mlp->c_r, GLP_LO, 0.0, 0.0); + + /* Quality metric columns */ + cur_col = glp_add_cols(mlp->prob, mlp->m_q); + for (c = 0; c < mlp->m_q; c++) { - max_iterations = MLP_MAX_ITERATIONS; + mlp->c_q[c] = cur_col + c; + GNUNET_asprintf (&name, "q_%u", mlp->q[c]); + glp_set_col_name (mlp->prob, mlp->c_q[c], name); + /* Column lower bound = 0.0 */ + glp_set_col_bnds (mlp->prob, mlp->c_q[c], GLP_LO, 0.0, 0.0); + GNUNET_free (name); + /* Coefficient == Qm */ + glp_set_obj_coef (mlp->prob, mlp->c_q[c], mlp->co_Q[c]); } - /* 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; + /* Add columns for addresses */ + //GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp); - /* 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; + /* Add constraints */ + //mlp_add_constraints_all_addresses (mlp, addresses); - /* 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; + /* Load the matrix */ + glp_load_matrix(mlp->prob, elements /*(mlp->ci-1)*/, mlp->ia, mlp->ja, mlp->ar); - /* Get quality metric coefficients from configuration */ - int i_delay = NaN; - int i_distance = 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->co_Q[c] = DEFAULT_QUALITY; + return res; +} - mlp->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; + +/** + * Solves the MLP problem + * + * @param solver the MLP Handle + * @param ctx solution context + * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure + */ +int +GAS_mlp_solve_problem (void *solver) +{ + struct GAS_MLP_Handle *mlp = solver; + int res = 0; + + 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); + mlp_create_problem (mlp, NULL); + } + else + { + LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n"); + } + + /* Solve problem */ +#if 0 + struct GAS_MLP_Handle *mlp = solver; + int res; + + GNUNET_assert (NULL != solver); + GNUNET_assert (NULL != ctx); + + /* Check if solving is already running */ + if (GNUNET_YES == mlp->semaphore) + { + if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel(mlp->mlp_task); + mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; + } + mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp); + return GNUNET_SYSERR; } + mlp->semaphore = GNUNET_YES; - if ((i_delay != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_QUALITY_DELAY", - &tmp))) + mlp->last_execution = GNUNET_TIME_absolute_get (); - mlp->co_Q[i_delay] = (double) tmp / 100; - else - mlp->co_Q[i_delay] = DEFAULT_QUALITY; + ctx->lp_result = GNUNET_SYSERR; + ctx->mlp_result = GNUNET_SYSERR; + ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL; + ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL; - if ((i_distance != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", - "MLP_COEFFICIENT_QUALITY_DISTANCE", - &tmp))) - mlp->co_Q[i_distance] = (double) tmp / 100; - else - mlp->co_Q[i_distance] = DEFAULT_QUALITY; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n"); +#if WRITE_MLP + char * name; + static int i; + i++; + GNUNET_asprintf(&name, "problem_%i", i); + glp_write_lp (mlp->prob, 0, name); + GNUNET_free (name); +# endif - /* 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 + res = mlp_solve_lp_problem (mlp, ctx); + ctx->lp_result = res; + if (res != GNUNET_OK) { - b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n"); + mlp->semaphore = GNUNET_NO; + return GNUNET_SYSERR; } - /* 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; +#if WRITE_MLP + GNUNET_asprintf(&name, "problem_%i_lp_solution", i); + glp_print_sol (mlp->prob, name); + GNUNET_free (name); +# endif - /* Init network quotas */ - int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType; - for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n"); + res = mlp_solve_mlp_problem (mlp, ctx); + ctx->mlp_result = res; + if (res != GNUNET_OK) { - found = GNUNET_NO; - for (c2 = 0; c2 < dest_length; c2++) - { - if (quotas[c] == network[c2]) - { - mlp->quota_index[c] = network[c2]; - mlp->quota_out[c] = out_dest[c2]; - mlp->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->quota_index[c]), - mlp->quota_out[c], - mlp->quota_in[c]); - break; - } - } + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n"); + mlp->semaphore = GNUNET_NO; + return GNUNET_SYSERR; + } +#if WRITE_MLP + GNUNET_asprintf(&name, "problem_%i_mlp_solution", i); + glp_print_mip (mlp->prob, name); + GNUNET_free (name); +# endif - /* Check if defined quota could make problem unsolvable */ - if ((n_min * b_min) > mlp->quota_out[c]) + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n", + (GNUNET_OK == res) ? "successfully" : "failed", + ctx->lp_duration.rel_value, + ctx->mlp_duration.rel_value); + /* Process result */ + struct ATS_Peer *p = NULL; + struct ATS_Address *a = NULL; + struct MLP_information *mlpi = NULL; + + for (p = mlp->peer_head; p != NULL; p = p->next) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id)); + for (a = p->head; a != NULL; a = a->next) + { + double b = 0.0; + double n = 0.0; + + mlpi = a->solver_information; + + b = glp_mip_col_val(mlp->prob, mlpi->c_b); + mlpi->b = b; + + n = glp_mip_col_val(mlp->prob, mlpi->c_n); + if (n == 1.0) { - 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->quota_index[c]), - mlp->quota_out[c], - (n_min * b_min)); - mlp->quota_out[c] = (n_min * b_min); + /* This is the address to be used */ + mlpi->n = GNUNET_YES; } - if ((n_min * b_min) > mlp->quota_in[c]) + else { - 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->quota_index[c]), - mlp->quota_in[c], - (n_min * b_min)); - mlp->quota_in[c] = (n_min * b_min); + /* This is the address not used */ + mlpi->n = GNUNET_NO; } - /* Check if bandwidth is too big to make problem solvable */ - if (mlp->BIG_M < mlp->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->quota_index[c]), - mlp->quota_out[c], - mlp->BIG_M); - mlp->quota_out[c] = mlp->BIG_M; - } - if (mlp->BIG_M < mlp->quota_in[c]) + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n", + (n == 1.0) ? "[x]" : "[ ]", b); + + /* Notify addresses */ + if ((ntohl(a->assigned_bw_in.value__) != b) || + (ntohl(a->assigned_bw_out.value__) != b) || + (mlpi->n != a->active)) { - LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"), - GNUNET_ATS_print_network_type(mlp->quota_index[c]), - mlp->quota_in[c], - mlp->BIG_M); - mlp->quota_in[c] = mlp->BIG_M; + a->assigned_bw_in.value__ = htonl(b); + a->assigned_bw_out.value__ = htonl(b); + a->active = mlpi->n; + mlp->bw_changed_cb (mlp->bw_changed_cb_cls, a); } - - if (GNUNET_NO == found) - { - mlp->quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); - mlp->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->quota_index[c]), - mlp->quota_in[c], - mlp->quota_out[c]); - } + } } - /* Get minimum number of connections from configuration */ - if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats", - "MLP_EXEC_INTERVAL", - &i_exec)) - mlp->exec_interval = i_exec; - else - mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30); - - /* 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->co_D = D; - mlp->co_R = R; - mlp->co_U = U; - mlp->b_min = b_min; - mlp->n_min = n_min; - mlp->m_q = GNUNET_ATS_QualityPropertiesCount; + if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel(mlp->mlp_task); + mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; + } + mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp); mlp->semaphore = GNUNET_NO; - mlp->max_iterations = max_iterations; - mlp->max_exec_duration = max_duration; - mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS; - mlp->auto_solve = GNUNET_YES; - - /* Redirect GLPK output to GNUnet logging */ - glp_error_hook((void *) mlp, &mlp_term_hook); - - /* 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; + return res; #endif - mlp->control_param_mlp.tm_lim = max_duration.rel_value; - - LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n"); - - return mlp; -} - -static void -update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address) -{ - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n", - GNUNET_i2s (&address->peer)); - - GNUNET_assert (NULL != address); - GNUNET_assert (NULL != address->solver_information); -// GNUNET_assert (NULL != address->ats); - - struct MLP_information *mlpi = address->solver_information; - //struct GNUNET_ATS_Information *ats = address->ats; - GNUNET_assert (mlpi != NULL); - - int c; - for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++) - { - - /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */ - int index = GNUNET_SYSERR; - - if (index == GNUNET_SYSERR) - continue; - /* FIXME - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->q[c]), - (double) ats[index].value); - - int i = mlpi->q_avg_i[c];*/ - double * qp = mlpi->q[c]; - /* FIXME - qp[i] = (double) ats[index].value; - */ - - int t; - for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++) - { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->q[c]), - t, - qp[t]); - } - - if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH)) - mlpi->q_avg_i[c] ++; - else - mlpi->q_avg_i[c] = 0; - - - int c2; - int c3; - double avg = 0.0; - switch (mlp->q[c]) - { - case GNUNET_ATS_QUALITY_NET_DELAY: - c3 = 0; - for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++) - { - if (mlpi->q[c][c2] != -1) - { - double * t2 = mlpi->q[c] ; - avg += t2[c2]; - c3 ++; - } - } - if ((c3 > 0) && (avg > 0)) - /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/ - mlpi->q_averaged[c] = (double) c3 / avg; - else - mlpi->q_averaged[c] = 0.0; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->q[c]), - avg, - avg / (double) c3, - mlpi->q_averaged[c]); - - break; - case GNUNET_ATS_QUALITY_NET_DISTANCE: - c3 = 0; - for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++) - { - if (mlpi->q[c][c2] != -1) - { - double * t2 = mlpi->q[c] ; - avg += t2[c2]; - c3 ++; - } - } - if ((c3 > 0) && (avg > 0)) - /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/ - mlpi->q_averaged[c] = (double) c3 / avg; - else - mlpi->q_averaged[c] = 0.0; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n", - GNUNET_i2s (&address->peer), - mlp_ats_to_string(mlp->q[c]), - avg, - avg / (double) c3, - mlpi->q_averaged[c]); - - break; - default: - break; - } - - if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0)) - { - - /* Get current number of columns */ - int found = GNUNET_NO; - int cols = glp_get_num_cols(mlp->prob); - int *ind = GNUNET_malloc (cols * sizeof (int) + 1); - double *val = GNUNET_malloc (cols * sizeof (double) + 1); - - /* Get the matrix row of quality */ - int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b); - int c4; - /* Get the index if matrix row of quality */ - for (c4 = 1; c4 <= length; c4++ ) - { - if (mlpi->c_b == ind[c4]) - { - /* Update the value */ - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n", - mlp_ats_to_string(mlp->q[c]), - glp_get_col_name (mlp->prob, ind[c4]), - glp_get_row_name (mlp->prob, mlp->r_q[c]), - val[c4], - mlpi->q_averaged[c]); - val[c4] = mlpi->q_averaged[c]; - found = GNUNET_YES; - break; - } - } - - if (found == GNUNET_NO) - { - ind[length+1] = mlpi->c_b; - val[length+1] = mlpi->q_averaged[c]; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%i ind[%i] val[%i]: %i %f\n", length+1, length+1, length+1, mlpi->c_b, mlpi->q_averaged[c]); - glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val); - } - else - { - /* Get the index if matrix row of quality */ - glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val); - } + /* Reset change and update marker */ + mlp->mlp_prob_updated = GNUNET_NO; + mlp->mlp_prob_changed = GNUNET_NO; - GNUNET_free (ind); - GNUNET_free (val); - } - } + return res; } - /** * Add a single address to the solve * @@ -1644,8 +1401,25 @@ update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address) void GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address) { - LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s'\n", GNUNET_i2s(&address->peer)); - return; + struct GAS_MLP_Handle *mlp = solver; + struct ATS_Peer *p; + + GNUNET_assert (NULL != solver); + GNUNET_assert (NULL != addresses); + GNUNET_assert (NULL != address); + + /* TODO Add address here */ + + /* 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; + GAS_mlp_solve_problem (solver); } /** @@ -1674,15 +1448,30 @@ GAS_mlp_address_update (void *solver, const struct GNUNET_ATS_Information *atsi, uint32_t atsi_count) { - struct GAS_MLP_Handle *mlp = solver; - int new; - struct MLP_information *mlpi; - struct GAS_MLP_SolutionContext ctx; + struct ATS_Peer *p; + struct GAS_MLP_Handle *mlp = solver; + + GNUNET_assert (NULL != solver); + GNUNET_assert (NULL != addresses); + GNUNET_assert (NULL != address); + GNUNET_assert ((NULL != atsi) || (0 == atsi_count)); + + /* TODO Update address here */ + + /* 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)); - LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s'\n", - GNUNET_i2s(&address->peer)); + /* Problem size changed: new address for peer with pending request */ + mlp->mlp_prob_updated = GNUNET_YES; + GAS_mlp_solve_problem (solver); return; +#if 0 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO); /* We add a new address */ @@ -1767,6 +1556,7 @@ GAS_mlp_address_update (void *solver, } if (mlp->auto_solve == GNUNET_YES) GAS_mlp_solve_problem (mlp, &ctx); +#endif } /** @@ -1786,12 +1576,29 @@ GAS_mlp_address_delete (void *solver, struct ATS_Address *address, int session_only) { - struct GAS_MLP_Handle *mlp = solver; + struct ATS_Peer *p; + struct GAS_MLP_Handle *mlp = solver; + + GNUNET_assert (NULL != solver); + GNUNET_assert (NULL != addresses); + GNUNET_assert (NULL != address); + + /* TODO Delete address here */ + + /* 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)); - LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s'\n", - GNUNET_i2s(&address->peer)); + /* Problem size changed: new address for peer with pending request */ + mlp->mlp_prob_changed = GNUNET_YES; + GAS_mlp_solve_problem (solver); return; +#if 0 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO); struct GAS_MLP_SolutionContext ctx; @@ -1837,8 +1644,17 @@ GAS_mlp_address_delete (void *solver, if (mlp->auto_solve == GNUNET_YES) GAS_mlp_solve_problem (mlp, &ctx); } +#endif } + +/** + * 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) { @@ -1875,11 +1691,37 @@ GAS_mlp_get_preferred_address (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, const struct GNUNET_PeerIdentity *peer) { - struct ATS_Address * aa = NULL; + 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)); - GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, mlp_get_preferred_address_it, aa); - return aa; + + /* 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); + 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; + } + GAS_mlp_solve_problem (mlp); + + /* Get prefered address */ + GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, + mlp_get_preferred_address_it, res); + + return res; } @@ -1899,18 +1741,35 @@ GAS_mlp_address_change_preference (void *solver, enum GNUNET_ATS_PreferenceKind kind, float score) { - struct GAS_MLP_Handle *mlp = solver; + //struct GAS_MLP_Handle *mlp = solver; LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n", GNUNET_i2s(peer)); + + return; +#if 0 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO); //struct ATS_Peer *p = mlp_find_peer (mlp, peer); //FIXME to finish implementation /* Here we have to do the matching */ - +#endif } + +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 * @@ -1950,6 +1809,10 @@ GAS_mlp_done (void *solver) } 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); @@ -1958,4 +1821,288 @@ GAS_mlp_done (void *solver) } +/** + * 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) +{ + 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; + struct GNUNET_TIME_Relative i_exec; + 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; + } + + /* Create initial MLP problem */ + mlp->prob = glp_create_prob(); + if (NULL == mlp->prob) + { + LOG (GNUNET_ERROR_TYPE_ERROR, "Failed to create MLP problem!"); + GNUNET_free (mlp); + return NULL; + } + + mlp->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 = NaN; + int i_distance = 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->co_Q[c] = DEFAULT_QUALITY; + + mlp->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 != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", + "MLP_COEFFICIENT_QUALITY_DELAY", + &tmp))) + + mlp->co_Q[i_delay] = (double) tmp / 100; + else + mlp->co_Q[i_delay] = DEFAULT_QUALITY; + + if ((i_distance != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats", + "MLP_COEFFICIENT_QUALITY_DISTANCE", + &tmp))) + mlp->co_Q[i_distance] = (double) tmp / 100; + else + mlp->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->quota_index[c] = network[c2]; + mlp->quota_out[c] = out_dest[c2]; + mlp->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->quota_index[c]), + mlp->quota_out[c], + mlp->quota_in[c]); + break; + } + } + + /* Check if defined quota could make problem unsolvable */ + if ((n_min * b_min) > mlp->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->quota_index[c]), + mlp->quota_out[c], + (n_min * b_min)); + mlp->quota_out[c] = (n_min * b_min); + } + if ((n_min * b_min) > mlp->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->quota_index[c]), + mlp->quota_in[c], + (n_min * b_min)); + mlp->quota_in[c] = (n_min * b_min); + } + + /* Check if bandwidth is too big to make problem solvable */ + if (mlp->BIG_M < mlp->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->quota_index[c]), + mlp->quota_out[c], + mlp->BIG_M); + mlp->quota_out[c] = mlp->BIG_M; + } + if (mlp->BIG_M < mlp->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->quota_index[c]), + mlp->quota_in[c], + mlp->BIG_M); + mlp->quota_in[c] = mlp->BIG_M; + } + + if (GNUNET_NO == found) + { + mlp->quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); + mlp->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->quota_index[c]), + mlp->quota_in[c], + mlp->quota_out[c]); + } + } + + /* Get minimum number of connections from configuration */ + if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats", + "MLP_EXEC_INTERVAL", + &i_exec)) + mlp->exec_interval = i_exec; + else + mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30); + + /* 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->co_D = D; + mlp->co_R = R; + mlp->co_U = U; + mlp->b_min = b_min; + mlp->n_min = n_min; + mlp->m_q = GNUNET_ATS_QualityPropertiesCount; + mlp->semaphore = GNUNET_NO; + mlp->max_iterations = max_iterations; + mlp->max_exec_duration = max_duration; + mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS; + mlp->auto_solve = GNUNET_YES; + mlp->mlp_prob_changed = GNUNET_NO; + mlp->mlp_prob_updated = GNUNET_NO; + + mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO); + + /* Setup GLPK */ + /* Redirect GLPK output to GNUnet logging */ + glp_error_hook((void *) mlp, &mlp_term_hook); + + /* 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 index 8efe6cd1a..c0e2a9bd2 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.h +++ b/src/ats/gnunet-service-ats_addresses_mlp.h @@ -129,6 +129,21 @@ struct GAS_MLP_Handle 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; + /** * Solves the task in an regular interval */ @@ -331,6 +346,16 @@ struct MLP_information int q_avg_i[GNUNET_ATS_QualityPropertiesCount]; }; +/** + * Solves the MLP problem + * + * @param solver the MLP Handle + * @param ctx solution context + * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure + */ +int +GAS_mlp_solve_problem (void *solver); + /** * Init the MLP problem solving component diff --git a/src/ats/test_ats_mlp.c b/src/ats/test_ats_mlp.c index 0239189c7..b6aa30c04 100644 --- a/src/ats/test_ats_mlp.c +++ b/src/ats/test_ats_mlp.c @@ -125,7 +125,7 @@ bandwidth_changed_cb (void *cls, struct ATS_Address *address) { GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP tells suggests me for peer `%s' address `%s':`%s'\n", GNUNET_i2s(&address->peer), address->plugin, address->addr); - end_now (0); + //end_now (0); } static void @@ -182,7 +182,6 @@ check (void *cls, char *const *args, const char *cfgfile, end_now (1); return; } - mlp->auto_solve = GNUNET_NO; /* Create peer */ if (GNUNET_SYSERR == GNUNET_CRYPTO_hash_from_string(PEERID0, &p.hashPubKey)) @@ -211,6 +210,10 @@ check (void *cls, char *const *args, const char *cfgfile, ats.value = htonl (GNUNET_ATS_NET_WAN); GAS_mlp_address_update (mlp, addresses, address[0], 1, GNUNET_NO, &ats, 1); + + /* Retrieving preferred address for peer and wait for callback */ + GAS_mlp_get_preferred_address (mlp, addresses, &p); + /* Create address 1 */ address[1] = create_address (&p, "test_plugin", "test_addr1", strlen("test_addr1")+1, 0); if (NULL == address[1]) @@ -222,6 +225,7 @@ check (void *cls, char *const *args, const char *cfgfile, GNUNET_CONTAINER_multihashmap_put (addresses, &p.hashPubKey, address[1], GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); + /* Adding address 1*/ GAS_mlp_address_add (mlp, addresses, address[1]); @@ -230,8 +234,7 @@ check (void *cls, char *const *args, const char *cfgfile, ats.value = htonl (GNUNET_ATS_NET_WAN); GAS_mlp_address_update (mlp, addresses, address[1], 1, GNUNET_NO, &ats, 1); - /* Retrieving preferred address for peer and wait for callback */ - GAS_mlp_get_preferred_address (mlp, addresses, &p); + GAS_mlp_address_delete (mlp, addresses, address[0], GNUNET_NO); end_now (0); //struct GAS_MLP_SolutionContext ctx; -- 2.25.1