From 141bef2081f9b1142f8fed35474919caaf6f53c7 Mon Sep 17 00:00:00 2001 From: Matthias Wachs Date: Tue, 5 Jul 2011 15:02:20 +0000 Subject: [PATCH] putting ats to external file... first steps --- src/transport/gnunet-service-transport.c | 1671 +------------------- src/transport/transport_ats.c | 1824 ++++++++++++++++++++++ src/transport/transport_ats.h | 371 +++++ 3 files changed, 2229 insertions(+), 1637 deletions(-) create mode 100644 src/transport/transport_ats.c create mode 100644 src/transport/transport_ats.h diff --git a/src/transport/gnunet-service-transport.c b/src/transport/gnunet-service-transport.c index f12787a55..249ad5104 100644 --- a/src/transport/gnunet-service-transport.c +++ b/src/transport/gnunet-service-transport.c @@ -38,9 +38,8 @@ #include "gnunet_signatures.h" #include "gnunet_transport_plugin.h" #include "transport.h" -#if HAVE_LIBGLPK -#include -#endif +#include "transport_ats.h" + #define DEBUG_BLACKLIST GNUNET_NO @@ -48,10 +47,6 @@ #define DEBUG_TRANSPORT_HELLO GNUNET_NO -#define DEBUG_ATS GNUNET_NO - -#define VERBOSE_ATS GNUNET_NO - /** * Should we do some additional checks (to validate behavior * of clients)? @@ -152,14 +147,6 @@ */ #define CONNECTED_LATENCY_EVALUATION_MAX_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 1) -#define VERY_BIG_DOUBLE_VALUE 100000000000LL - -#define ATS_NEW 0 -#define ATS_Q_UPDATED 1 -#define ATS_C_UPDATED 2 -#define ATS_QC_UPDATED 3 -#define ATS_UNMODIFIED 4 - /** * List of addresses of other peers */ @@ -855,296 +842,6 @@ struct CheckHelloValidatedContext unsigned int ve_count; }; -struct ATS_quality_metric -{ - int index; - int atis_index; - char * name; -}; - -struct ATS_mechanism -{ - struct ATS_mechanism * prev; - struct ATS_mechanism * next; - struct ForeignAddressList * addr; - struct TransportPlugin * plugin; - struct ATS_peer * peer; - int col_index; - int id; - struct ATS_ressource_cost * rc; -}; - -struct ATS_peer -{ - int id; - struct GNUNET_PeerIdentity peer; - struct NeighbourList * n; - struct ATS_mechanism * m_head; - struct ATS_mechanism * m_tail; - - /* preference value f */ - double f; - int t; -}; - -struct ATS_stat -{ - /** - * result of last GLPK run - * 5 == OPTIMAL - */ - int solution; - - /** - * Ressource costs or quality metrics changed - * update problem before solving - */ - int modified_resources; - - /** - * Ressource costs or quality metrics changed, update matrix - * update problem before solving - */ - int modified_quality; - - /** - * Peers have connected or disconnected - * problem has to be recreated - */ - int recreate_problem; - - /** - * Was the available basis invalid and we needed to rerun simplex? - */ - int simplex_rerun_required; - - /** - * is problem currently valid and can it be solved - */ - int valid; - - /** - * Number of transport mechanisms in the problem - */ - int c_mechs; - - /** - * Number of transport mechanisms in the problem - */ - int c_peers; - - /** - * row index where quality related rows start - */ - int begin_qm; - - /** - * row index where quality related rows end - */ - int end_qm; - - /** - * row index where ressource cost related rows start - */ - int begin_cr; - - /** - * row index where ressource cost related rows end - */ - int end_cr; - - /** - * column index for objective function value d - */ - int col_d; - - /** - * column index for objective function value u - */ - int col_u; - - /** - * column index for objective function value r - */ - int col_r; - - /** - * column index for objective function value quality metrics - */ - int col_qm; - - /** - * column index for objective function value cost ressources - */ - int col_cr; -}; - -struct ATS_ressource_entry -{ - /* index in ressources array */ - int index; - /* depending ATSi parameter to calculcate limits */ - int atis_index; - /* lower bound */ - double c; -}; - - -struct ATS_ressource -{ - /* index in ressources array */ - int index; - /* depending ATSi parameter to calculcate limits */ - int atis_index; - /* cfg option to load limits */ - char * cfg_param; - /* lower bound */ - double c_min; - /* upper bound */ - double c_max; - - /* cofficients for the specific plugins */ - double c_unix; - double c_tcp; - double c_udp; - double c_http; - double c_https; - double c_wlan; - double c_default; -}; - -static struct ATS_ressource ressources[] = -{ - /* FIXME: the coefficients for the specific plugins */ - {1, 7, "LAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 1, 3}, - {2, 7, "WAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 2, 3}, - {3, 4, "WLAN_ENERGY_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 0, 0, 0, 0, 2, 1} -/* - {4, 4, "COST_ENERGY_CONSUMPTION", VERY_BIG_DOUBLE_VALUE}, - {5, 5, "COST_CONNECT", VERY_BIG_DOUBLE_VALUE}, - {6, 6, "COST_BANDWITH_AVAILABLE", VERY_BIG_DOUBLE_VALUE}, - {7, 7, "COST_NETWORK_OVERHEAD", VERY_BIG_DOUBLE_VALUE},*/ -}; - -static int available_ressources = 3; - - - -struct ATS_info -{ - - /** - * Time of last execution - */ - struct GNUNET_TIME_Absolute last; - /** - * Minimum intervall between two executions - */ - struct GNUNET_TIME_Relative min_delta; - /** - * Regular intervall when execution is triggered - */ - struct GNUNET_TIME_Relative exec_interval; - /** - * Maximum execution time per calculation - */ - struct GNUNET_TIME_Relative max_exec_duration; - -#if HAVE_LIBGLPK - /** - * GLPK (MLP) problem object - */ - glp_prob *prob; -#endif - - /** - * task to recalculate the bandwidth assignment - */ - GNUNET_SCHEDULER_TaskIdentifier ats_task; - - /** - * Current state of the GLPK problem - */ - struct ATS_stat stat; - - /** - * mechanisms used in current problem - * needed for problem modification - */ - struct ATS_mechanism * mechanisms; - - /** - * peers used in current problem - * needed for problem modification - */ - struct ATS_peer * peers; - - /** - * number of successful executions - */ - int successful_executions; - - /** - * number with an invalid result - */ - int invalid_executions; - - /** - * Maximum number of LP iterations per calculation - */ - int max_iterations; - - /** - * Dump problem to a file? - */ - int save_mlp; - - /** - * Dump solution to a file - */ - int save_solution; - - /** - * Dump solution when minimum peers: - */ - int dump_min_peers; - - /** - * Dump solution when minimum addresses: - */ - int dump_min_addr; - - /** - * Dump solution overwrite file: - */ - int dump_overwrite; - - /** - * Diversity weight - */ - double D; - - /** - * Utility weight - */ - double U; - - /** - * Relativity weight - */ - double R; - - /** - * Minimum bandwidth per peer - */ - int v_b_min; - - /** - * Minimum number of connections per peer - */ - int v_n_min; -}; - /** * Our HELLO message. @@ -1232,22 +929,6 @@ static int shutdown_in_progress; */ static struct ATS_info *ats; -struct ATS_quality_entry -{ - int index; - int atsi_index; - uint32_t values[3]; - int current; -}; - -static struct ATS_quality_metric qm[] = -{ - {1, 1028, "QUALITY_NET_DISTANCE"}, - {2, 1034, "QUALITY_NET_DELAY"}, -}; -static int available_quality_metrics = 2; - - /** * The peer specified by the given neighbour has timed-out or a plugin * has disconnected. We may either need to do nothing (other plugins @@ -1271,27 +952,9 @@ static void disconnect_neighbour (struct NeighbourList *n, int check); */ static void try_transmission_to_peer (struct NeighbourList *n); -static void ats_shutdown ( ); - -static void ats_notify_peer_connect ( - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_TRANSPORT_ATS_Information *ats_data, int ats_count); - -static void ats_notify_peer_disconnect ( - const struct GNUNET_PeerIdentity *peer); - -#if 0 -static void ats_notify_ats_data ( - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_TRANSPORT_ATS_Information *ats_data); -#endif - -struct ForeignAddressList * ats_get_preferred_address ( +struct ForeignAddressList * get_preferred_ats_address ( struct NeighbourList *n); -static void -ats_calculate_bandwidth_distribution (); - /** * Find an entry in the neighbour list for a particular peer. * @@ -1992,7 +1655,7 @@ try_transmission_to_peer (struct NeighbourList *n) if (mq->specific_address == NULL) { /* TODO: ADD ATS */ - mq->specific_address = ats_get_preferred_address(n); + mq->specific_address = get_preferred_ats_address(n); GNUNET_STATISTICS_update (stats, gettext_noop ("# transport selected peer address freely"), 1, @@ -2933,9 +2596,14 @@ notify_clients_connect (const struct GNUNET_PeerIdentity *peer, (&(cim->ats))[2].value = htonl (0); memcpy (&cim->id, peer, sizeof (struct GNUNET_PeerIdentity)); + /* notify ats about connecting peer */ /* notify ats about connecting peer */ if (shutdown_in_progress == GNUNET_NO) - ats_notify_peer_connect (peer, &(cim->ats), 2); + { + ats->stat.recreate_problem = GNUNET_YES; + ats_calculate_bandwidth_distribution (ats, stats, neighbours); + } + cpos = clients; while (cpos != NULL) @@ -2980,7 +2648,10 @@ notify_clients_disconnect (const struct GNUNET_PeerIdentity *peer) /* notify ats about connecting peer */ if (shutdown_in_progress == GNUNET_NO) - ats_notify_peer_disconnect (peer); + { + ats->stat.recreate_problem = GNUNET_YES; + ats_calculate_bandwidth_distribution (ats, stats, neighbours); + } cpos = clients; while (cpos != NULL) @@ -5586,9 +5257,7 @@ plugin_env_receive (void *cls, const struct GNUNET_PeerIdentity *peer, for (c=0; cstat.recreate_problem == GNUNET_YES) - opt_lp.presolve = GLP_ON; - result = glp_simplex(ats->prob, &opt_lp); - lp_solution = glp_get_status (ats->prob); - - if ((result == GLP_ETMLIM) || (result == GLP_EITLIM)) - { - ats->stat.valid = GNUNET_NO; - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ATS exceeded time or iteration limit!\n"); - return; - } - - if (ats_evaluate_results(result, lp_solution, "LP") == GNUNET_YES) - { - stat->valid = GNUNET_YES; - } - else - { - ats->stat.simplex_rerun_required = GNUNET_YES; - opt_lp.presolve = GLP_ON; - result = glp_simplex(ats->prob, &opt_lp); - lp_solution = glp_get_status (ats->prob); - - // TODO: Remove if this does not appear until release - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "EXECUTED SIMPLEX WITH PRESOLVER! %i \n", lp_solution); - - if (ats_evaluate_results(result, lp_solution, "LP") != GNUNET_YES) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "After execution simplex with presolver: STILL INVALID!\n"); - char * filename; - GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%llu.mlp",ats->stat.c_peers, ats->stat.c_mechs, GNUNET_TIME_absolute_get().abs_value); - glp_write_lp (ats->prob, NULL, filename); - GNUNET_free (filename); - stat->valid = GNUNET_NO; - ats->stat.recreate_problem = GNUNET_YES; - return; - } - stat->valid = GNUNET_YES; - } - - // Solving mlp - glp_iocp opt_mlp; - glp_init_iocp(&opt_mlp); - // maximum duration - opt_mlp.tm_lim = max_dur; - // output level -#if VERBOSE_ATS - opt_mlp.msg_lev = GLP_MSG_ALL; -#else - opt_mlp.msg_lev = GLP_MSG_OFF; -#endif - - result = glp_intopt (ats->prob, &opt_mlp); - mlp_solution = glp_mip_status (ats->prob); - stat->solution = mlp_solution; - - if (ats_evaluate_results(result, mlp_solution, "MLP") == GNUNET_YES) - { - stat->valid = GNUNET_YES; - } - else - { - // TODO: Remove if this does not appear until release - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP solution for %i peers, %i mechs is invalid: %i\n", ats->stat.c_peers, ats->stat.c_mechs, mlp_solution); - stat->valid = GNUNET_NO; - } - -/* - int check; - int error = GNUNET_NO; - double bw; - struct ATS_mechanism *t = NULL; - for (c=1; c<= (c_peers); c++ ) - { - check = GNUNET_NO; - t = peers[c].m_head; - while (t!=NULL) - { - bw = glp_get_col_prim(prob, t->col_index); - if (bw > 1.0) - { -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[%i][%i] `%s' %s %s %f\n", c, t->col_index, GNUNET_h2s(&peers[c].peer.hashPubKey), t->plugin->short_name, glp_get_col_name(prob,t->col_index), bw); -#endif - if (check ==GNUNET_YES) - { - glp_write_sol(prob, "invalid_solution.mlp"); - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Invalid solution, check invalid_solution.mlp"); - GNUNET_STATISTICS_update (stats, "ATS invalid solutions", 1, GNUNET_NO); - error = GNUNET_YES; - } - if (check ==GNUNET_NO) - check = GNUNET_YES; - } - t = t->next; - } - }*/ - -#if VERBOSE_ATS - if (glp_get_col_prim(ats->prob,2*c_mechs+1) != 1) - { - int c; - for (c=1; c<= available_quality_metrics; c++ ) - { - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+3+c), glp_get_col_prim(ats->prob,2*c_mechs+3+c)); - } - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+1), glp_get_col_prim(ats->prob,2*c_mechs+1)); - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+2), glp_get_col_prim(ats->prob,2*c_mechs+2)); - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+3), glp_get_col_prim(ats->prob,2*c_mechs+3)); - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "objective value: %f\n", glp_mip_obj_val(ats->prob)); - } -#endif -} - -static void ats_delete_problem () -{ -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting problem\n"); -#endif - int c; - - for (c=0; c< (ats->stat).c_mechs; c++) - GNUNET_free_non_null (ats->mechanisms[c].rc); - - - if (ats->mechanisms!=NULL) - { - GNUNET_free(ats->mechanisms); - ats->mechanisms = NULL; - } - - if (ats->peers!=NULL) - { - GNUNET_free(ats->peers); - ats->peers = NULL; - } - - if (ats->prob != NULL) - { - glp_delete_prob(ats->prob); - ats->prob = NULL; - } - - ats->stat.begin_cr = GNUNET_SYSERR; - ats->stat.begin_qm = GNUNET_SYSERR; - ats->stat.c_mechs = 0; - ats->stat.c_peers = 0; - ats->stat.end_cr = GNUNET_SYSERR; - ats->stat.end_qm = GNUNET_SYSERR; - ats->stat.solution = GNUNET_SYSERR; - ats->stat.valid = GNUNET_SYSERR; -} - - -static void ats_update_problem_qm () -{ - int array_index; - int row_index; - int c, c2; - int c_q_metrics = available_quality_metrics; - - int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); - double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n"); -#endif - row_index = ats->stat.begin_qm; - - for (c=1; c <= c_q_metrics; c++) - { - array_index = 1; - double value = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); - for (c2=1; c2<=ats->stat.c_mechs; c2++) - { - ja[array_index] = c2; - - GNUNET_assert (ats->mechanisms[c2].addr != NULL); - GNUNET_assert (ats->mechanisms[c2].peer != NULL); - - if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY) - { - double v0 = 0, v1 = 0, v2 = 0; - - v0 = ats->mechanisms[c2].addr->quality[c-1].values[0]; - if (v1 < 1) v0 = 0.1; - v1 = ats->mechanisms[c2].addr->quality[c-1].values[1]; - if (v1 < 1) v0 = 0.1; - v2 = ats->mechanisms[c2].addr->quality[c-1].values[2]; - if (v1 < 1) v0 = 0.1; - value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0); - //value = 1; - } - if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE) - { - double v0 = 0, v1 = 0, v2 = 0; - v0 = ats->mechanisms[c2].addr->quality[c-1].values[0]; - if (v0 < 1) v0 = 1; - v1 = ats->mechanisms[c2].addr->quality[c-1].values[1]; - if (v1 < 1) v1 = 1; - v2 = ats->mechanisms[c2].addr->quality[c-1].values[2]; - if (v2 < 1) v2 = 1; - value = (v0 + 2 * v1 + 3 * v2) / 6.0; - if (value >= 1) - value = (double) 10 / value; - else - value = 10; - } - ar[array_index] = (ats->mechanisms[c2].peer->f) * value; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",array_index, qm[c-1].name, row_index, ja[array_index], ar[array_index]); -#endif - array_index++; - } - ja[array_index] = ats->stat.col_qm + c - 1; - ar[array_index] = -1; - -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, row_index, ja[array_index], ar[array_index]); -#endif - glp_set_mat_row (ats->prob, row_index, array_index, ja, ar); - - array_index = 1; - row_index++; - } - - GNUNET_free_non_null (ja); - GNUNET_free_non_null (ar); -} - - -static void ats_update_problem_cr () -{ - - int array_index; - int row_index; - int c, c2; - double ct_max, ct_min; - - int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); - double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); - - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n"); - row_index = ats->stat.begin_cr; - array_index = 1; - - for (c=0; cprob, row_index, GLP_DB, ct_min, ct_max); - - for (c2=1; c2<=ats->stat.c_mechs; c2++) - { - double value = 0; - - GNUNET_assert (ats->mechanisms[c2].addr != NULL); - GNUNET_assert (ats->mechanisms[c2].peer != NULL); - - ja[array_index] = c2; - value = ats->mechanisms[c2].addr->ressources[c].c; - ar[array_index] = value; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, row_index, ja[array_index], ar[array_index]); -#endif - array_index++; - } - glp_set_mat_row (ats->prob, row_index, array_index, ja, ar); - - row_index ++; - } - - - GNUNET_free_non_null (ja); - GNUNET_free_non_null (ar); -} - - -#if 0 -static void ats_update_problem_qm_TEST () -{ - int row_index; - int c, c2; - - int old_ja[ats->stat.c_mechs + 2]; - double old_ar[ats->stat.c_mechs + 2]; - int c_old; - int changed = 0; - - int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); - double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics TEST\n"); -#endif - if (ats->stat.begin_qm >0) - row_index = ats->stat.begin_qm; - else - return; - - - for (c=0; cprob, row_index, old_ja, old_ar); - - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); - - for (c2=1; c2<=c_old; c2++) - { - ja[c2] = old_ja[c2]; - if ((changed < 3) && (c2>2) && (old_ar[c2] != -1)) - { - ar[c2] = old_ar[c2] + 5 - changed; - changed ++; - } - else - ar[c2] = old_ar[c2]; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: old [%i,%i]=%f new [%i,%i]=%f\n",c2, row_index, old_ja[c2], old_ar[c2], row_index, ja[c2], ar[c2]); -#endif - } - glp_set_mat_row (ats->prob, row_index, c_old, ja, ar); - - row_index ++; - } - - GNUNET_free_non_null (ja); - GNUNET_free_non_null (ar); -} -#endif //END: HAVE_LIBGLPK - -/** solve the bandwidth distribution problem - * @param max_it maximum iterations - * @param max_dur maximum duration in ms - * @param D weight for diversity - * @param U weight for utility - * @param R weight for relativity - * @param v_b_min minimal bandwidth per peer - * @param v_n_min minimum number of connections - * @param stat result struct - * @return GNUNET_SYSERR if glpk is not available, number of mechanisms used - */ -static int ats_create_problem (double D, double U, double R, int v_b_min, int v_n_min, struct ATS_stat *stat) -{ - ats->prob = glp_create_prob(); - - int c; - int c_peers = 0; - int c_mechs = 0; - - int c_c_ressources = available_ressources; - int c_q_metrics = available_quality_metrics; - - double M = VERY_BIG_DOUBLE_VALUE; - double Q[c_q_metrics+1]; - for (c=1; c<=c_q_metrics; c++) - { - Q[c] = 1; - } - - struct NeighbourList *next = neighbours; - while (next!=NULL) - { - int found_addresses = GNUNET_NO; - struct ReadyList *r_next = next->plugins; - while (r_next != NULL) - { - struct ForeignAddressList * a_next = r_next->addresses; - while (a_next != NULL) - { - c_mechs++; - found_addresses = GNUNET_YES; - a_next = a_next->next; - } - r_next = r_next->next; - } - if (found_addresses) c_peers++; - next = next->next; - } - - if (c_mechs==0) - { -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "No addresses for bw distribution available\n", c_peers); -#endif - stat->valid = GNUNET_NO; - stat->c_peers = 0; - stat->c_mechs = 0; - return GNUNET_SYSERR; - } - - GNUNET_assert (ats->mechanisms == NULL); - ats->mechanisms = GNUNET_malloc((1+c_mechs) * sizeof (struct ATS_mechanism)); - GNUNET_assert (ats->peers == NULL); - ats->peers = GNUNET_malloc((1+c_peers) * sizeof (struct ATS_peer)); - - struct ATS_mechanism * mechanisms = ats->mechanisms; - struct ATS_peer * peers = ats->peers; - - c_mechs = 1; - c_peers = 1; - - next = neighbours; - while (next!=NULL) - { - int found_addresses = GNUNET_NO; - struct ReadyList *r_next = next->plugins; - while (r_next != NULL) - { - struct ForeignAddressList * a_next = r_next->addresses; - while (a_next != NULL) - { - if (found_addresses == GNUNET_NO) - { - peers[c_peers].peer = next->id; - peers[c_peers].m_head = NULL; - peers[c_peers].m_tail = NULL; - peers[c_peers].f = 1.0 / c_mechs; - } - - mechanisms[c_mechs].addr = a_next; - mechanisms[c_mechs].col_index = c_mechs; - mechanisms[c_mechs].peer = &peers[c_peers]; - mechanisms[c_mechs].next = NULL; - mechanisms[c_mechs].plugin = r_next->plugin; - - GNUNET_CONTAINER_DLL_insert_tail(peers[c_peers].m_head, peers[c_peers].m_tail, &mechanisms[c_mechs]); - found_addresses = GNUNET_YES; - c_mechs++; - - a_next = a_next->next; - } - r_next = r_next->next; - } - if (found_addresses == GNUNET_YES) - c_peers++; - next = next->next; - } - c_mechs--; - c_peers--; - - if (v_n_min > c_peers) - v_n_min = c_peers; - -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Creating problem with: %i peers, %i mechanisms, %i resource entries, %i quality metrics \n", c_peers, c_mechs, c_c_ressources, c_q_metrics); -#endif - - int size = 1 + 3 + 10 *c_mechs + c_peers + (c_q_metrics*c_mechs)+ c_q_metrics + c_c_ressources * c_mechs ; - int row_index; - int array_index=1; - int * ia = GNUNET_malloc (size * sizeof (int)); - int * ja = GNUNET_malloc (size * sizeof (int)); - double * ar = GNUNET_malloc(size* sizeof (double)); - - glp_set_prob_name(ats->prob, "gnunet ats bandwidth distribution"); - glp_set_obj_dir(ats->prob, GLP_MAX); - - /* adding columns */ - char * name; - glp_add_cols(ats->prob, 2 * c_mechs); - /* adding b_t cols */ - for (c=1; c <= c_mechs; c++) - { - - GNUNET_asprintf(&name, "p_%s_b%i",GNUNET_i2s(&(mechanisms[c].peer->peer)), c); - glp_set_col_name(ats->prob, c, name); - GNUNET_free (name); - glp_set_col_bnds(ats->prob, c, GLP_LO, 0.0, 0.0); - glp_set_col_kind(ats->prob, c, GLP_CV); - glp_set_obj_coef(ats->prob, c, 0); - - } - /* adding n_t cols */ - for (c=c_mechs+1; c <= 2*c_mechs; c++) - { - GNUNET_asprintf(&name, "p_%s_n%i",GNUNET_i2s(&(mechanisms[c-c_mechs].peer->peer)),(c-c_mechs)); - glp_set_col_name(ats->prob, c, name); - GNUNET_free (name); - glp_set_col_bnds(ats->prob, c, GLP_DB, 0.0, 1.0); - glp_set_col_kind(ats->prob, c, GLP_IV); - glp_set_obj_coef(ats->prob, c, 0); - } - - /* feasibility constraints */ - /* Constraint 1: one address per peer*/ - row_index = 1; - glp_add_rows(ats->prob, c_peers); - for (c=1; c<=c_peers; c++) - { -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 1.0, 1.0); - - struct ATS_mechanism *m = peers[c].m_head; - while (m!=NULL) - { - ia[array_index] = row_index; - ja[array_index] = (c_mechs + m->col_index); - ar[array_index] = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - m = m->next; - } - row_index++; - } - - /* Constraint 2: only active mechanism gets bandwidth assigned */ - glp_add_rows(ats->prob, c_mechs); - for (c=1; c<=c_mechs; c++) - { - /* b_t - n_t * M <= 0 */ -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_UP, 0.0, 0.0); - - ia[array_index] = row_index; - ja[array_index] = mechanisms[c].col_index; - ar[array_index] = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - ia[array_index] = row_index; - ja[array_index] = c_mechs + mechanisms[c].col_index; - ar[array_index] = -M; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - row_index ++; - } - - /* Constraint 3: minimum bandwidth*/ - glp_add_rows(ats->prob, c_mechs); - for (c=1; c<=c_mechs; c++) - { - /* b_t - n_t * b_min <= 0 */ -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_LO, 0.0, 0.0); - - ia[array_index] = row_index; - ja[array_index] = mechanisms[c].col_index; - ar[array_index] = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - ia[array_index] = row_index; - ja[array_index] = c_mechs + mechanisms[c].col_index; - ar[array_index] = -v_b_min; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - row_index ++; - } - int c2; - /* Constraint 4: max ressource capacity */ - /* V cr: bt * ct_r <= cr_max - * */ - glp_add_rows(ats->prob, available_ressources); - double ct_max = VERY_BIG_DOUBLE_VALUE; - double ct_min = 0.0; - - stat->begin_cr = array_index; - - for (c=0; cprob, row_index, GLP_DB, ct_min, ct_max); - - for (c2=1; c2<=c_mechs; c2++) - { - double value = 0; - ia[array_index] = row_index; - ja[array_index] = c2; - value = mechanisms[c2].addr->ressources[c].c; - ar[array_index] = value; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - } - row_index ++; - } - stat->end_cr = array_index--; - - /* Constraint 5: min number of connections*/ - glp_add_rows(ats->prob, 1); - for (c=1; c<=c_mechs; c++) - { - // b_t - n_t * b_min >= 0 -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_LO, v_n_min, 0.0); - - ia[array_index] = row_index; - ja[array_index] = c_mechs + mechanisms[c].col_index; - ar[array_index] = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - } - row_index ++; - - // optimisation constraints - - // adding columns - - // Constraint 6: optimize for diversity - int col_d; - col_d = glp_add_cols(ats->prob, 1); - stat->col_d = col_d; - //GNUNET_assert (col_d == (2*c_mechs) + 1); - glp_set_col_name(ats->prob, col_d, "d"); - glp_set_obj_coef(ats->prob, col_d, D); - glp_set_col_bnds(ats->prob, col_d, GLP_LO, 0.0, 0.0); - glp_add_rows(ats->prob, 1); -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); - for (c=1; c<=c_mechs; c++) - { - ia[array_index] = row_index; - ja[array_index] = c_mechs + mechanisms[c].col_index; - ar[array_index] = 1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - } - ia[array_index] = row_index; - ja[array_index] = col_d; - ar[array_index] = -1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - row_index ++; - - - // Constraint 7: optimize for quality - int col_qm; - col_qm = glp_add_cols(ats->prob, c_q_metrics); - stat->col_qm = col_qm; - //GNUNET_assert (col_qm == (2*c_mechs) + 3 + 1); - for (c=0; c< c_q_metrics; c++) - { - GNUNET_asprintf(&name, "Q_%s",qm[c].name); - glp_set_col_name(ats->prob, col_qm + c, name); - glp_set_col_bnds(ats->prob, col_qm + c, GLP_LO, 0.0, 0.0); - GNUNET_free (name); - glp_set_obj_coef(ats->prob, col_qm + c, Q[c]); - } - glp_add_rows(ats->prob, available_quality_metrics); - stat->begin_qm = row_index; - for (c=1; c <= c_q_metrics; c++) - { -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - double value = 1; - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); - for (c2=1; c2<=c_mechs; c2++) - { - - ia[array_index] = row_index; - ja[array_index] = c2; - if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY) - { - double v0 = 0, v1 = 0, v2 = 0; - v0 = mechanisms[c2].addr->quality[c-1].values[0]; - if (v1 < 1) v0 = 0.1; - v1 = mechanisms[c2].addr->quality[c-1].values[1]; - if (v1 < 1) v0 = 0.1; - v2 = mechanisms[c2].addr->quality[c-1].values[2]; - if (v1 < 1) v0 = 0.1; - value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0); - value = 1; - } - if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE) - { - double v0 = 0, v1 = 0, v2 = 0; - v0 = mechanisms[c2].addr->quality[c-1].values[0]; - if (v0 < 1) v0 = 1; - v1 = mechanisms[c2].addr->quality[c-1].values[1]; - if (v1 < 1) v1 = 1; - v2 = mechanisms[c2].addr->quality[c-1].values[2]; - if (v2 < 1) v2 = 1; - value = (v0 + 2 * v1 + 3 * v2) / 6.0; - if (value >= 1) - value = (double) 10 / value; - else - value = 10; - } - ar[array_index] = (mechanisms[c2].peer->f) * value ; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",array_index, qm[c-1].name, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - } - - ia[array_index] = row_index; - ja[array_index] = col_qm + c - 1; - ar[array_index] = -1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - row_index++; - } - stat->end_qm = row_index-1; - - // Constraint 8: optimize bandwidth utility - int col_u; - col_u = glp_add_cols(ats->prob, 1); - stat->col_u = col_u; - //GNUNET_assert (col_u == (2*c_mechs) + 2); - glp_set_col_name(ats->prob, col_u, "u"); - glp_set_obj_coef(ats->prob, col_u, U); - glp_set_col_bnds(ats->prob, col_u, GLP_LO, 0.0, 0.0); - glp_add_rows(ats->prob, 1); -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); -#endif - glp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); - for (c=1; c<=c_mechs; c++) - { - ia[array_index] = row_index; - ja[array_index] = c; - ar[array_index] = mechanisms[c].peer->f; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - } - ia[array_index] = row_index; - ja[array_index] = col_u; - ar[array_index] = -1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - - array_index++; - row_index ++; - - // Constraint 9: optimize relativity - int col_r; - col_r = glp_add_cols(ats->prob, 1); - stat->col_r = col_r; - //GNUNET_assert (col_r == (2*c_mechs) + 3); - glp_set_col_name(ats->prob, col_r, "r"); - glp_set_obj_coef(ats->prob, col_r, R); - glp_set_col_bnds(ats->prob, col_r, GLP_LO, 0.0, 0.0); - glp_add_rows(ats->prob, c_peers); - for (c=1; c<=c_peers; c++) - { - glp_set_row_bnds(ats->prob, row_index, GLP_LO, 0.0, 0.0); - - struct ATS_mechanism *m = peers[c].m_head; - while (m!=NULL) - { - ia[array_index] = row_index; - ja[array_index] = m->col_index; - ar[array_index] = 1 / mechanisms[c].peer->f; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - m = m->next; - } - ia[array_index] = row_index; - ja[array_index] = col_r; - ar[array_index] = -1; -#if VERBOSE_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); -#endif - array_index++; - - row_index++; - } - - /* Loading the matrix */ - glp_load_matrix(ats->prob, array_index-1, ia, ja, ar); - - stat->c_mechs = c_mechs; - stat->c_peers = c_peers; - stat->solution = 0; - stat->valid = GNUNET_YES; - - /* clean up */ - - GNUNET_free (ja); - GNUNET_free (ia); - GNUNET_free (ar); - - return GNUNET_OK; - -} - -void ats_notify_ats_data ( - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_TRANSPORT_ATS_Information *ats_data) -{ -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_BULK, "ATS_notify_ats_data: %s\n",GNUNET_i2s(peer)); -#endif - if (shutdown_in_progress == GNUNET_NO) - ats_calculate_bandwidth_distribution(); -} -#endif //END: HAVE_LIBGLPK - -static void -ats_calculate_bandwidth_distribution () -{ -#if HAVE_LIBGLPK - - struct GNUNET_TIME_Absolute start; - struct GNUNET_TIME_Relative creation; - struct GNUNET_TIME_Relative solving; - char *text = "unmodified"; - - struct GNUNET_TIME_Relative delta = GNUNET_TIME_absolute_get_difference (ats->last, GNUNET_TIME_absolute_get()); - if (delta.rel_value < ats->min_delta.rel_value) - { -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_BULK, "Minimum time between cycles not reached\n"); -#endif - return; - } - - if (shutdown_in_progress == GNUNET_YES) - { -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_BULK, "Transport service is shutting down\n"); -#endif - return; - } - -#if FIXME_WACHS - int dur; - if (INT_MAX < ats->max_exec_duration.rel_value) - dur = INT_MAX; - else - dur = (int) ats->max_exec_duration.rel_value; -#endif - - ats->stat.simplex_rerun_required = GNUNET_NO; - start = GNUNET_TIME_absolute_get(); - if ((ats->stat.recreate_problem == GNUNET_YES) || (ats->prob==NULL) || (ats->stat.valid == GNUNET_NO)) - { - text = "new"; - ats->stat.recreate_problem = GNUNET_YES; - ats_delete_problem (); - ats_create_problem (ats->D, ats->U, ats->R, ats->v_b_min, ats->v_n_min, &ats->stat); -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Peers/Addresses were modified... new problem: %i peer, %i mechs\n", ats->stat.c_peers, ats->stat.c_mechs); -#endif - } - - else if ((ats->stat.recreate_problem == GNUNET_NO) && (ats->stat.modified_resources == GNUNET_YES) && (ats->stat.valid == GNUNET_YES)) - { - text = "modified resources"; - ats_update_problem_cr(); - } - else if ((ats->stat.recreate_problem == GNUNET_NO) && (ats->stat.modified_quality == GNUNET_YES) && (ats->stat.valid == GNUNET_YES)) - { - text = "modified quality"; - ats_update_problem_qm(); - //ats_update_problem_qm_TEST (); - - } -#if DEBUG_ATS - else GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Problem is unmodified\n"); -#endif - - creation = GNUNET_TIME_absolute_get_difference(start,GNUNET_TIME_absolute_get()); - start = GNUNET_TIME_absolute_get(); - - ats->stat.solution = GLP_UNDEF; - if (ats->stat.valid == GNUNET_YES) - { - ats_solve_problem(ats->max_iterations, ats->max_exec_duration.rel_value, ats->stat.c_peers, ats->stat.c_mechs, &ats->stat); - } - solving = GNUNET_TIME_absolute_get_difference(start,GNUNET_TIME_absolute_get()); - - if (ats->stat.valid == GNUNET_YES) - { - int msg_type = GNUNET_ERROR_TYPE_DEBUG; -#if DEBUG_ATS - msg_type = GNUNET_ERROR_TYPE_ERROR; -#endif - GNUNET_log (msg_type, "MLP %s: creation time: %llu, execution time: %llu, %i mechanisms, simplex rerun: %s, solution %s\n", - text, creation.rel_value, solving.rel_value, - ats->stat.c_mechs, - (ats->stat.simplex_rerun_required == GNUNET_NO) ? "NO" : "YES", (ats->stat.solution == 5) ? "OPTIMAL" : "INVALID"); - ats->successful_executions ++; - GNUNET_STATISTICS_set (stats, "# ATS successful executions", ats->successful_executions, GNUNET_NO); - - if ((ats->stat.recreate_problem == GNUNET_YES) || (ats->prob==NULL)) - GNUNET_STATISTICS_set (stats, "ATS state",ATS_NEW, GNUNET_NO); - else if ((ats->stat.modified_resources == GNUNET_YES) && - (ats->stat.modified_quality == GNUNET_NO)) - GNUNET_STATISTICS_set (stats, "ATS state", ATS_C_UPDATED, GNUNET_NO); - else if ((ats->stat.modified_resources == GNUNET_NO) && - (ats->stat.modified_quality == GNUNET_YES) && - (ats->stat.simplex_rerun_required == GNUNET_NO)) - GNUNET_STATISTICS_set (stats, "ATS state", ATS_Q_UPDATED, GNUNET_NO); - else if ((ats->stat.modified_resources == GNUNET_YES) && - (ats->stat.modified_quality == GNUNET_YES) && - (ats->stat.simplex_rerun_required == GNUNET_NO)) - GNUNET_STATISTICS_set (stats, "ATS state", ATS_QC_UPDATED, GNUNET_NO); - else if (ats->stat.simplex_rerun_required == GNUNET_NO) - GNUNET_STATISTICS_set (stats, "ATS state", ATS_UNMODIFIED, GNUNET_NO); - } - else - { - if (ats->stat.c_peers != 0) - { - ats->invalid_executions ++; - GNUNET_STATISTICS_set (stats, "# ATS invalid executions", ats->invalid_executions, GNUNET_NO); - } - else - { - GNUNET_STATISTICS_set (stats, "# ATS successful executions", ats->successful_executions, GNUNET_NO); - } - } - - GNUNET_STATISTICS_set (stats, "ATS duration", solving.rel_value + creation.rel_value, GNUNET_NO); - GNUNET_STATISTICS_set (stats, "ATS mechanisms", ats->stat.c_mechs, GNUNET_NO); - GNUNET_STATISTICS_set (stats, "ATS peers", ats->stat.c_peers, GNUNET_NO); - GNUNET_STATISTICS_set (stats, "ATS solution", ats->stat.solution, GNUNET_NO); - GNUNET_STATISTICS_set (stats, "ATS timestamp", start.abs_value, GNUNET_NO); - - if ((ats->save_mlp == GNUNET_YES) && (ats->stat.c_mechs >= ats->dump_min_peers) && (ats->stat.c_mechs >= ats->dump_min_addr)) - { - char * filename; - if (ats->dump_overwrite == GNUNET_NO) - { - GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.mlp", - ats->stat.c_peers, ats->stat.c_mechs, text, GNUNET_TIME_absolute_get().abs_value); - glp_write_lp (ats->prob, NULL, filename); - } - else - { - GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.mlp", - ats->stat.c_peers, ats->stat.c_mechs ); - glp_write_lp (ats->prob, NULL, filename); - } - GNUNET_free (filename); - } - if ((ats->save_solution == GNUNET_YES) && (ats->stat.c_mechs >= ats->dump_min_peers) && (ats->stat.c_mechs >= ats->dump_min_addr)) - { - char * filename; - if (ats->dump_overwrite == GNUNET_NO) - { - GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.sol", - ats->stat.c_peers, ats->stat.c_mechs, text, GNUNET_TIME_absolute_get().abs_value); - glp_print_sol (ats->prob, filename); - } - else - { - GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.sol", - ats->stat.c_peers, ats->stat.c_mechs); - glp_print_sol (ats->prob, filename); - } - GNUNET_free (filename); - } - - ats->last = GNUNET_TIME_absolute_get(); - ats->stat.recreate_problem = GNUNET_NO; - ats->stat.modified_resources = GNUNET_NO; - ats->stat.modified_quality = GNUNET_NO; -#endif -} static void -ats_schedule_calculation (void *cls, +schedule_ats (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) { - struct ATS_info *ats = (struct ATS_info *) cls; - if (ats==NULL) return; - - ats->ats_task = GNUNET_SCHEDULER_NO_TASK; - if ( (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0) - return; - - if (shutdown_in_progress == GNUNET_YES) - return; + struct ATS_info *ats = (struct ATS_info *) cls; + if (ats==NULL) + return; + ats->ats_task = GNUNET_SCHEDULER_NO_TASK; + if ( (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0) + return; + if (shutdown_in_progress == GNUNET_YES) + return; #if DEBUG_ATS GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Running scheduled calculation\n"); #endif - - ats_calculate_bandwidth_distribution (ats); - - ats->ats_task = GNUNET_SCHEDULER_add_delayed (ats->exec_interval, - &ats_schedule_calculation, ats); -} - -void ats_init () -{ - int c = 0; - unsigned long long value; - char * section; - - ats = GNUNET_malloc(sizeof (struct ATS_info)); - - ats->min_delta = ATS_MIN_INTERVAL; - ats->exec_interval = ATS_EXEC_INTERVAL; - ats->max_exec_duration = ATS_MAX_EXEC_DURATION; - ats->max_iterations = ATS_MAX_ITERATIONS; - ats->ats_task = GNUNET_SCHEDULER_NO_TASK; - -#if !HAVE_LIBGLPK - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ATS not active\n"); - return; -#endif - - ats->D = 1.0; - ats->U = 1.0; - ats->R = 1.0; - ats->v_b_min = 64000; - ats->v_n_min = 10; - ats->dump_min_peers = 1; - ats->dump_min_addr = 1; - ats->dump_overwrite = GNUNET_NO; - ats->mechanisms = NULL; - ats->peers = NULL; - ats->successful_executions = 0; - ats->invalid_executions = 0; - -#if HAVE_LIBGLPK - ats->prob = NULL; -#endif - - /* loading cost ressources */ - for (c=0; csave_mlp = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_MLP"); - - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_SOLUTION")) - ats->save_solution = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_SOLUTION"); - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_OVERWRITE")) - ats->dump_overwrite = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_OVERWRITE"); - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_MIN_PEERS")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_MIN_PEERS", &value); - ats->dump_min_peers= value; - } - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_MIN_ADDRS")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_MIN_ADDRS", &value); - ats->dump_min_addr= value; - } - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_OVERWRITE")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_OVERWRITE", &value); - ats->min_delta.rel_value = value; - } - - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_MIN_INTERVAL")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_MIN_INTERVAL", &value); - ats->min_delta.rel_value = value; - } - - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_EXEC_INTERVAL")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_EXEC_INTERVAL", &value); - ats->exec_interval.rel_value = value; - } - if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_MIN_INTERVAL")) - { - GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_MIN_INTERVAL", &value); - ats->min_delta.rel_value = value; - } - - ats->ats_task = GNUNET_SCHEDULER_add_now(&ats_schedule_calculation, ats); -} - - -static void ats_shutdown () -{ -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ats_destroy\n"); -#endif - if (ats->ats_task != GNUNET_SCHEDULER_NO_TASK) - GNUNET_SCHEDULER_cancel(ats->ats_task); - ats->ats_task = GNUNET_SCHEDULER_NO_TASK; - -#if HAVE_LIBGLPK - ats_delete_problem (); - glp_free_env(); -#endif - GNUNET_free (ats); -} - - -void ats_notify_peer_connect ( - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_TRANSPORT_ATS_Information *ats_data, int ats_count) -{ -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ats_notify_peer_connect: %s\n",GNUNET_i2s(peer)); -#endif - //update_addr_ats(); - ats->stat.recreate_problem = GNUNET_YES; - ats_calculate_bandwidth_distribution(ats); -} - -void ats_notify_peer_disconnect ( - const struct GNUNET_PeerIdentity *peer) -{ -#if DEBUG_ATS - GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ats_notify_peer_disconnect: %s\n",GNUNET_i2s(peer)); -#endif - ats->stat.recreate_problem = GNUNET_YES; - ats_calculate_bandwidth_distribution (ats); + ats_calculate_bandwidth_distribution (ats, stats, neighbours); + ats->ats_task = GNUNET_SCHEDULER_add_delayed (ats->exec_interval, + &schedule_ats, ats); } -struct ForeignAddressList * ats_get_preferred_address ( +struct ForeignAddressList * get_preferred_ats_address ( struct NeighbourList *n) { -#if DEBUG_ATS - //GNUNET_log (GNUNET_ERROR_TYPE_BULK, "ats_get_prefered_transport for peer: %s\n",GNUNET_i2s(&n->id)); -#endif - struct ReadyList *next = n->plugins; - while (next != NULL) - { -#if DEBUG_ATS - //GNUNET_log (GNUNET_ERROR_TYPE_BULK, "plugin: %s %i\n",next->plugin->short_name,strcmp(next->plugin->short_name,"unix")); -#endif - next = next->next; - } - return find_ready_address(n); + // TODO get ATS prefered address + return find_ready_address(n); } /** @@ -7808,7 +6203,9 @@ run (void *cls, if (no_transports) refresh_hello (); - ats_init(); + ats = ats_init (cfg); + GNUNET_assert (ats != NULL); + ats->ats_task = GNUNET_SCHEDULER_add_now (&schedule_ats, ats); #if DEBUG_TRANSPORT GNUNET_log (GNUNET_ERROR_TYPE_INFO, diff --git a/src/transport/transport_ats.c b/src/transport/transport_ats.c new file mode 100644 index 000000000..cf558c038 --- /dev/null +++ b/src/transport/transport_ats.c @@ -0,0 +1,1824 @@ +/* + This file is part of GNUnet. + (C) 2009, 2010 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 transport/transport_ats.c + * @brief automatic transport selection + * @author Matthias Wachs + * + */ + +#include "transport_ats.h" +#include "gnunet_transport_service.h" +#include "gnunet_statistics_service.h" +#include "gnunet_container_lib.h" + +/** + * FIXME to be removed + * Entry in linked list of all of our current neighbours. + */ +struct NeighbourList +{ + + /** + * This is a linked list. + */ + struct NeighbourList *next; + + /** + * Which of our transports is connected to this peer + * and what is their status? + */ + struct ReadyList *plugins; + + /** + * Head of list of messages we would like to send to this peer; + * must contain at most one message per client. + */ + struct MessageQueue *messages_head; + + /** + * Tail of list of messages we would like to send to this peer; must + * contain at most one message per client. + */ + struct MessageQueue *messages_tail; + + /** + * Head of list of messages of messages we expected the continuation + * to be called to destroy the message + */ + struct MessageQueue *cont_head; + + /** + * Tail of list of messages of messages we expected the continuation + * to be called to destroy the message + */ + struct MessageQueue *cont_tail; + + /** + * Buffer for at most one payload message used when we receive + * payload data before our PING-PONG has succeeded. We then + * store such messages in this intermediary buffer until the + * connection is fully up. + */ + struct GNUNET_MessageHeader *pre_connect_message_buffer; + + /** + * Context for peerinfo iteration. + * NULL after we are done processing peerinfo's information. + */ + struct GNUNET_PEERINFO_IteratorContext *piter; + + /** + * Public key for this peer. Valid only if the respective flag is set below. + */ + struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded publicKey; + + /** + * Identity of this neighbour. + */ + struct GNUNET_PeerIdentity id; + + /** + * ID of task scheduled to run when this peer is about to + * time out (will free resources associated with the peer). + */ + GNUNET_SCHEDULER_TaskIdentifier timeout_task; + + /** + * ID of task scheduled to run when we should retry transmitting + * the head of the message queue. Actually triggered when the + * transmission is timing out (we trigger instantly when we have + * a chance of success). + */ + GNUNET_SCHEDULER_TaskIdentifier retry_task; + + /** + * How long until we should consider this peer dead + * (if we don't receive another message in the + * meantime)? + */ + struct GNUNET_TIME_Absolute peer_timeout; + + /** + * Tracker for inbound bandwidth. + */ + struct GNUNET_BANDWIDTH_Tracker in_tracker; + + /** + * The latency we have seen for this particular address for + * this particular peer. This latency may have been calculated + * over multiple transports. This value reflects how long it took + * us to receive a response when SENDING via this particular + * transport/neighbour/address combination! + * + * FIXME: we need to periodically send PINGs to update this + * latency (at least more often than the current "huge" (11h?) + * update interval). + */ + struct GNUNET_TIME_Relative latency; + + /** + * How often has the other peer (recently) violated the + * inbound traffic limit? Incremented by 10 per violation, + * decremented by 1 per non-violation (for each + * time interval). + */ + unsigned int quota_violation_count; + + /** + * DV distance to this peer (1 if no DV is used). + */ + uint32_t distance; + + /** + * Have we seen an PONG from this neighbour in the past (and + * not had a disconnect since)? + */ + int received_pong; + + /** + * Do we have a valid public key for this neighbour? + */ + int public_key_valid; + + /** + * Performance data for the peer. + */ + struct GNUNET_TRANSPORT_ATS_Information *ats; + + /** + * Identity of the neighbour. + */ + struct GNUNET_PeerIdentity peer; + +}; + +/** + * FIXME to be removed + * + * List of addresses of other peers + */ +struct ForeignAddressList +{ + /** + * This is a linked list. + */ + struct ForeignAddressList *next; + + /** + * Which ready list does this entry belong to. + */ + struct ReadyList *ready_list; + + /** + * How long until we auto-expire this address (unless it is + * re-confirmed by the transport)? + */ + struct GNUNET_TIME_Absolute expires; + + /** + * Task used to re-validate addresses, updates latencies and + * verifies liveness. + */ + GNUNET_SCHEDULER_TaskIdentifier revalidate_task; + + /** + * The address. + */ + const void *addr; + + /** + * Session (or NULL if no valid session currently exists or if the + * plugin does not use sessions). + */ + struct Session *session; + + struct ATS_ressource_entry * ressources; + + struct ATS_quality_entry * quality; + + /** + * What was the last latency observed for this address, plugin and peer? + */ + struct GNUNET_TIME_Relative latency; + + /** + * If we did not successfully transmit a message to the given peer + * via this connection during the specified time, we should consider + * the connection to be dead. This is used in the case that a TCP + * transport simply stalls writing to the stream but does not + * formerly get a signal that the other peer died. + */ + struct GNUNET_TIME_Absolute timeout; + + /** + * How often have we tried to connect using this plugin? Used to + * discriminate against addresses that do not work well. + * FIXME: not yet used, but should be! + */ + unsigned int connect_attempts; + + /** + * DV distance to this peer (1 if no DV is used). + * FIXME: need to set this from transport plugins! + */ + uint32_t distance; + + /** + * Length of addr. + */ + uint16_t addrlen; + + /** + * Have we ever estimated the latency of this address? Used to + * ensure that the first time we add an address, we immediately + * probe its latency. + */ + int8_t estimated; + + /** + * Are we currently connected via this address? The first time we + * successfully transmit or receive data to a peer via a particular + * address, we set this to GNUNET_YES. If we later get an error + * (disconnect notification, transmission failure, timeout), we set + * it back to GNUNET_NO. + */ + int8_t connected; + + /** + * Is this plugin currently busy transmitting to the specific target? + * GNUNET_NO if not (initial, default state is GNUNET_NO). Internal + * messages do not count as 'in transmit'. + */ + int8_t in_transmit; + + /** + * Has this address been validated yet? + */ + int8_t validated; + +}; + +/** + * FIXME: REMOVE + * + * For a given Neighbour, which plugins are available + * to talk to this peer and what are their costs? + */ +struct ReadyList +{ + /** + * This is a linked list. + */ + struct ReadyList *next; + + /** + * Which of our transport plugins does this entry + * represent? + */ + struct TransportPlugin *plugin; + + /** + * Transport addresses, latency, and readiness for + * this particular plugin. + */ + struct ForeignAddressList *addresses; + + /** + * To which neighbour does this ready list belong to? + */ + struct NeighbourList *neighbour; +}; + +/* optimization direction flag: */ +#define GLP_MIN 1 /* minimization */ +#define GLP_MAX 2 /* maximization */ + +/* kind of structural variable: */ +#define GLP_CV 1 /* continuous variable */ +#define GLP_IV 2 /* integer variable */ +#define GLP_BV 3 /* binary variable */ + +/* type of auxiliary/structural variable: */ +#define GLP_FR 1 /* free variable */ +#define GLP_LO 2 /* variable with lower bound */ +#define GLP_UP 3 /* variable with upper bound */ +#define GLP_DB 4 /* double-bounded variable */ +#define GLP_FX 5 /* fixed variable */ + +/* solution status: */ +#define GLP_UNDEF 1 /* solution is undefined */ +#define GLP_FEAS 2 /* solution is feasible */ +#define GLP_INFEAS 3 /* solution is infeasible */ +#define GLP_NOFEAS 4 /* no feasible solution exists */ +#define GLP_OPT 5 /* solution is optimal */ +#define GLP_UNBND 6 /* solution is unbounded */ + +/* return codes: */ +#define GLP_EBADB 0x01 /* invalid basis */ +#define GLP_ESING 0x02 /* singular matrix */ +#define GLP_ECOND 0x03 /* ill-conditioned matrix */ +#define GLP_EBOUND 0x04 /* invalid bounds */ +#define GLP_EFAIL 0x05 /* solver failed */ +#define GLP_EOBJLL 0x06 /* objective lower limit reached */ +#define GLP_EOBJUL 0x07 /* objective upper limit reached */ +#define GLP_EITLIM 0x08 /* iteration limit exceeded */ +#define GLP_ETMLIM 0x09 /* time limit exceeded */ +#define GLP_ENOPFS 0x0A /* no primal feasible solution */ +#define GLP_ENODFS 0x0B /* no dual feasible solution */ +#define GLP_EROOT 0x0C /* root LP optimum not provided */ +#define GLP_ESTOP 0x0D /* search terminated by application */ +#define GLP_EMIPGAP 0x0E /* relative mip gap tolerance reached */ +#define GLP_ENOFEAS 0x0F /* no primal/dual feasible solution */ +#define GLP_ENOCVG 0x10 /* no convergence */ +#define GLP_EINSTAB 0x11 /* numerical instability */ +#define GLP_EDATA 0x12 /* invalid data */ +#define GLP_ERANGE 0x13 /* result out of range */ + +/* enable/disable flag: */ +#define GLP_ON 1 /* enable something */ +#define GLP_OFF 0 /* disable something */ + +typedef struct +{ /* simplex method control parameters */ + int msg_lev; /* message level: */ +#define GLP_MSG_OFF 0 /* no output */ +#define GLP_MSG_ERR 1 /* warning and error messages only */ +#define GLP_MSG_ON 2 /* normal output */ +#define GLP_MSG_ALL 3 /* full output */ +#define GLP_MSG_DBG 4 /* debug output */ + int meth; /* simplex method option: */ +#define GLP_PRIMAL 1 /* use primal simplex */ +#define GLP_DUALP 2 /* use dual; if it fails, use primal */ +#define GLP_DUAL 3 /* use dual simplex */ + int pricing; /* pricing technique: */ +#define GLP_PT_STD 0x11 /* standard (Dantzig rule) */ +#define GLP_PT_PSE 0x22 /* projected steepest edge */ + int r_test; /* ratio test technique: */ +#define GLP_RT_STD 0x11 /* standard (textbook) */ +#define GLP_RT_HAR 0x22 /* two-pass Harris' ratio test */ + double tol_bnd; /* spx.tol_bnd */ + double tol_dj; /* spx.tol_dj */ + double tol_piv; /* spx.tol_piv */ + double obj_ll; /* spx.obj_ll */ + double obj_ul; /* spx.obj_ul */ + int it_lim; /* spx.it_lim */ + int tm_lim; /* spx.tm_lim (milliseconds) */ + int out_frq; /* spx.out_frq */ + int out_dly; /* spx.out_dly (milliseconds) */ + int presolve; /* enable/disable using LP presolver */ + double foo_bar[36]; /* (reserved) */ +} glp_smcp; + + +typedef struct +{ /* integer optimizer control parameters */ + int msg_lev; /* message level (see glp_smcp) */ + int br_tech; /* branching technique: */ +#define GLP_BR_FFV 1 /* first fractional variable */ +#define GLP_BR_LFV 2 /* last fractional variable */ +#define GLP_BR_MFV 3 /* most fractional variable */ +#define GLP_BR_DTH 4 /* heuristic by Driebeck and Tomlin */ +#define GLP_BR_PCH 5 /* hybrid pseudocost heuristic */ + int bt_tech; /* backtracking technique: */ +#define GLP_BT_DFS 1 /* depth first search */ +#define GLP_BT_BFS 2 /* breadth first search */ +#define GLP_BT_BLB 3 /* best local bound */ +#define GLP_BT_BPH 4 /* best projection heuristic */ + double tol_int; /* mip.tol_int */ + double tol_obj; /* mip.tol_obj */ + int tm_lim; /* mip.tm_lim (milliseconds) */ + int out_frq; /* mip.out_frq (milliseconds) */ + int out_dly; /* mip.out_dly (milliseconds) */ + + void *cb_info; /* mip.cb_info */ + int cb_size; /* mip.cb_size */ + int pp_tech; /* preprocessing technique: */ +#define GLP_PP_NONE 0 /* disable preprocessing */ +#define GLP_PP_ROOT 1 /* preprocessing only on root level */ +#define GLP_PP_ALL 2 /* preprocessing on all levels */ + double mip_gap; /* relative MIP gap tolerance */ + int mir_cuts; /* MIR cuts (GLP_ON/GLP_OFF) */ + int gmi_cuts; /* Gomory's cuts (GLP_ON/GLP_OFF) */ + int cov_cuts; /* cover cuts (GLP_ON/GLP_OFF) */ + int clq_cuts; /* clique cuts (GLP_ON/GLP_OFF) */ + int presolve; /* enable/disable using MIP presolver */ + int binarize; /* try to binarize integer variables */ + int fp_heur; /* feasibility pump heuristic */ +#if 1 /* 28/V-2010 */ + int alien; /* use alien solver */ +#endif + double foo_bar[29]; /* (reserved) */ +} glp_iocp; + + +void _lp_set_prob_name (void *P, const char *name) +{ +#if HAVE_GLPK + glp_set_prob_name(P, name); +#endif +} + +int _lp_add_cols (void *P, int ncs) +{ +#if HAVE_GLPK + return glp_add_cols(P, ncs); +#endif + return 0; +} + +void _lp_set_row_bnds (void *P, int i, int type, double lb, double ub) +{ +#if HAVE_GLPK + glp_set_row_bnds(P, i , type, lb, ub); +#endif +} + +void _lp_init_smcp (void * parm) +{ +#if HAVE_GLPK + glp_init_smcp(parm); +#endif +} + +void _lp_set_col_name (void *P, int j, const char *name) +{ +#if HAVE_GLPK + glp_set_col_name (P, j, name); +#endif +} + +void _lp_set_col_bnds (void *P, int j, int type, double lb, + double ub) +{ +#if HAVE_GLPK + glp_set_col_bnds(P, j, type, lb, ub); +#endif +} + +void _lp_set_obj_coef(void *P, int j, double coef) +{ +#if HAVE_GLPK + _lp_set_obj_coef(P, j, coef); +#endif +} + +void _lp_delete_prob (void * P) +{ +#if HAVE_GLPK + glp_delete_prob (P); +#endif +} + +int _lp_simplex(void *P, void *parm) +{ +#if HAVE_GLPK + return glp_simplex (P, parm); +#endif + return 0; +} + +void _lp_load_matrix (void *P, int ne, const int ia[], + const int ja[], const double ar[]) +{ +#if HAVE_GLPK + glp_load_matrix(P, ne, ia, ja, ar); +#endif +} + +void _lp_set_mat_row (void *P, int i, int len, const int ind[], + const double val[]) +{ +#if HAVE_GLPK + glp_set_mat_row (P, i, len, ind, val); +#endif +} + +int _lp_write_lp (void * *P, const void *parm, const char *fname) +{ +#if HAVE_GLPK + return glp_write_lp (P, parm, fname); +#endif + return 0; +} + +void _lp_init_iocp (void *parm) +{ +#if HAVE_GLPK + glp_init_iocp (parm); +#endif +} + +int _lp_intopt (void *P, const void *parm) +{ +#if HAVE_GLPK + return glp_intopt (P, parm); +#endif + return 0; +} + +int _lp_get_status (void *P) +{ +#if HAVE_GLPK + return glp_get_status (P); +#endif + return 0; +} + +int _lp_mip_status(void *P) +{ +#if HAVE_GLPK + return glp_mip_status (P); +#endif + return 0; +} + + +struct ATS_info * ats_init (const struct GNUNET_CONFIGURATION_Handle *cfg) +{ +#if !HAVE_LIBGLPK + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ATS not active\n"); + return NULL; +#endif + + struct ATS_info * ats = NULL; + int c = 0; + unsigned long long value; + char * section; + + ats = GNUNET_malloc(sizeof (struct ATS_info)); + + ats->prob = NULL; + + ats->min_delta = ATS_MIN_INTERVAL; + ats->exec_interval = ATS_EXEC_INTERVAL; + ats->max_exec_duration = ATS_MAX_EXEC_DURATION; + ats->max_iterations = ATS_MAX_ITERATIONS; + ats->ats_task = GNUNET_SCHEDULER_NO_TASK; + + ats->D = 1.0; + ats->U = 1.0; + ats->R = 1.0; + ats->v_b_min = 64000; + ats->v_n_min = 10; + ats->dump_min_peers = 1; + ats->dump_min_addr = 1; + ats->dump_overwrite = GNUNET_NO; + ats->mechanisms = NULL; + ats->peers = NULL; + ats->successful_executions = 0; + ats->invalid_executions = 0; + + /* loading cost ressources */ + for (c=0; csave_mlp = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_MLP"); + + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_SOLUTION")) + ats->save_solution = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_SOLUTION"); + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_OVERWRITE")) + ats->dump_overwrite = GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport","DUMP_OVERWRITE"); + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_MIN_PEERS")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_MIN_PEERS", &value); + ats->dump_min_peers= value; + } + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_MIN_ADDRS")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_MIN_ADDRS", &value); + ats->dump_min_addr= value; + } + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "DUMP_OVERWRITE")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","DUMP_OVERWRITE", &value); + ats->min_delta.rel_value = value; + } + + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_MIN_INTERVAL")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_MIN_INTERVAL", &value); + ats->min_delta.rel_value = value; + } + + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_EXEC_INTERVAL")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_EXEC_INTERVAL", &value); + ats->exec_interval.rel_value = value; + } + if (GNUNET_CONFIGURATION_have_value(cfg, "transport", "ATS_MIN_INTERVAL")) + { + GNUNET_CONFIGURATION_get_value_number(cfg, "transport","ATS_MIN_INTERVAL", &value); + ats->min_delta.rel_value = value; + } + return ats; +} + + +/** solve the bandwidth distribution problem + * @param max_it maximum iterations + * @param max_dur maximum duration in ms + * @param D weight for diversity + * @param U weight for utility + * @param R weight for relativity + * @param v_b_min minimal bandwidth per peer + * @param v_n_min minimum number of connections + * @param stat result struct + * @return GNUNET_SYSERR if glpk is not available, number of mechanisms used + */ +int ats_create_problem (struct ATS_info *ats, struct NeighbourList *neighbours, double D, double U, double R, int v_b_min, int v_n_min, struct ATS_stat *stat) +{ +#if !HAVE_LIBGLPK + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ATS not active\n"); + return GNUNET_SYSERR; +#endif + +#if HAVE_LIBGLPK + ats->prob = glp_create_prob(); +#endif + + int c; + int c_peers = 0; + int c_mechs = 0; + + int c_c_ressources = available_ressources; + int c_q_metrics = available_quality_metrics; + + double M = VERY_BIG_DOUBLE_VALUE; + double Q[c_q_metrics+1]; + for (c=1; c<=c_q_metrics; c++) + { + Q[c] = 1; + } + + struct NeighbourList *next = neighbours; + while (next!=NULL) + { + int found_addresses = GNUNET_NO; + struct ReadyList *r_next = next->plugins; + while (r_next != NULL) + { + struct ForeignAddressList * a_next = r_next->addresses; + while (a_next != NULL) + { + c_mechs++; + found_addresses = GNUNET_YES; + a_next = a_next->next; + } + r_next = r_next->next; + } + if (found_addresses) c_peers++; + next = next->next; + } + + if (c_mechs==0) + { +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "No addresses for bw distribution available\n", c_peers); +#endif + stat->valid = GNUNET_NO; + stat->c_peers = 0; + stat->c_mechs = 0; + return GNUNET_SYSERR; + } + + GNUNET_assert (ats->mechanisms == NULL); + ats->mechanisms = GNUNET_malloc((1+c_mechs) * sizeof (struct ATS_mechanism)); + GNUNET_assert (ats->peers == NULL); + ats->peers = GNUNET_malloc((1+c_peers) * sizeof (struct ATS_peer)); + + struct ATS_mechanism * mechanisms = ats->mechanisms; + struct ATS_peer * peers = ats->peers; + + c_mechs = 1; + c_peers = 1; + + next = neighbours; + while (next!=NULL) + { + int found_addresses = GNUNET_NO; + struct ReadyList *r_next = next->plugins; + while (r_next != NULL) + { + struct ForeignAddressList * a_next = r_next->addresses; + while (a_next != NULL) + { + if (found_addresses == GNUNET_NO) + { + peers[c_peers].peer = next->id; + peers[c_peers].m_head = NULL; + peers[c_peers].m_tail = NULL; + peers[c_peers].f = 1.0 / c_mechs; + } + + mechanisms[c_mechs].addr = a_next; + mechanisms[c_mechs].col_index = c_mechs; + mechanisms[c_mechs].peer = &peers[c_peers]; + mechanisms[c_mechs].next = NULL; + mechanisms[c_mechs].plugin = r_next->plugin; + + GNUNET_CONTAINER_DLL_insert_tail(peers[c_peers].m_head, peers[c_peers].m_tail, &mechanisms[c_mechs]); + found_addresses = GNUNET_YES; + c_mechs++; + + a_next = a_next->next; + } + r_next = r_next->next; + } + if (found_addresses == GNUNET_YES) + c_peers++; + next = next->next; + } + c_mechs--; + c_peers--; + + if (v_n_min > c_peers) + v_n_min = c_peers; + +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Creating problem with: %i peers, %i mechanisms, %i resource entries, %i quality metrics \n", c_peers, c_mechs, c_c_ressources, c_q_metrics); +#endif + + int size = 1 + 3 + 10 *c_mechs + c_peers + (c_q_metrics*c_mechs)+ c_q_metrics + c_c_ressources * c_mechs ; + int row_index; + int array_index=1; + int * ia = GNUNET_malloc (size * sizeof (int)); + int * ja = GNUNET_malloc (size * sizeof (int)); + double * ar = GNUNET_malloc(size* sizeof (double)); + + + _lp_set_prob_name (ats->prob, "gnunet ats bandwidth distribution"); +#if HAVE_LIBGLPK + glp_set_obj_dir(ats->prob, GLP_MAX); +#endif + + /* adding columns */ + char * name; + _lp_add_cols(ats->prob, 2 * c_mechs); + /* adding b_t cols */ + for (c=1; c <= c_mechs; c++) + { +#if HAVE_LIBGLPK + GNUNET_asprintf(&name, "p_%s_b%i",GNUNET_i2s(&(mechanisms[c].peer->peer)), c); + _lp_set_col_name(ats->prob, c, name); + GNUNET_free (name); + _lp_set_col_bnds(ats->prob, c, GLP_LO, 0.0, 0.0); + glp_set_col_kind(ats->prob, c, GLP_CV); + _lp_set_obj_coef(ats->prob, c, 0); +#endif + + } + /* adding n_t cols */ + for (c=c_mechs+1; c <= 2*c_mechs; c++) + { +#if HAVE_LIBGLPK + GNUNET_asprintf(&name, "p_%s_n%i",GNUNET_i2s(&(mechanisms[c-c_mechs].peer->peer)),(c-c_mechs)); + _lp_set_col_name(ats->prob, c, name); + GNUNET_free (name); + _lp_set_col_bnds(ats->prob, c, GLP_DB, 0.0, 1.0); + glp_set_col_kind(ats->prob, c, GLP_IV); + _lp_set_obj_coef(ats->prob, c, 0); +#endif + } + + /* feasibility constraints */ + /* Constraint 1: one address per peer*/ + row_index = 1; +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, c_peers); +#endif + for (c=1; c<=c_peers; c++) + { +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif +#if HAVE_LIBGLPK + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 1.0, 1.0); +#endif + struct ATS_mechanism *m = peers[c].m_head; + while (m!=NULL) + { + ia[array_index] = row_index; + ja[array_index] = (c_mechs + m->col_index); + ar[array_index] = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + m = m->next; + } + row_index++; + } + + /* Constraint 2: only active mechanism gets bandwidth assigned */ +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, c_mechs); +#endif + for (c=1; c<=c_mechs; c++) + { + /* b_t - n_t * M <= 0 */ +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif +#if HAVE_LIBGLPK + _lp_set_row_bnds(ats->prob, row_index, GLP_UP, 0.0, 0.0); +#endif + ia[array_index] = row_index; + ja[array_index] = mechanisms[c].col_index; + ar[array_index] = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + ia[array_index] = row_index; + ja[array_index] = c_mechs + mechanisms[c].col_index; + ar[array_index] = -M; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + row_index ++; + } + + /* Constraint 3: minimum bandwidth*/ +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, c_mechs); +#endif + for (c=1; c<=c_mechs; c++) + { + /* b_t - n_t * b_min <= 0 */ +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif +#if HAVE_LIBGLPK + _lp_set_row_bnds(ats->prob, row_index, GLP_LO, 0.0, 0.0); +#endif + ia[array_index] = row_index; + ja[array_index] = mechanisms[c].col_index; + ar[array_index] = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + ia[array_index] = row_index; + ja[array_index] = c_mechs + mechanisms[c].col_index; + ar[array_index] = -v_b_min; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + row_index ++; + } + int c2; + /* Constraint 4: max ressource capacity */ + /* V cr: bt * ct_r <= cr_max + * */ +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, available_ressources); +#endif + double ct_max = VERY_BIG_DOUBLE_VALUE; + double ct_min = 0.0; + + stat->begin_cr = array_index; + + for (c=0; cprob, row_index, GLP_DB, ct_min, ct_max); +#endif + for (c2=1; c2<=c_mechs; c2++) + { + double value = 0; + ia[array_index] = row_index; + ja[array_index] = c2; + value = mechanisms[c2].addr->ressources[c].c; + ar[array_index] = value; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + } + row_index ++; + } + stat->end_cr = array_index--; + + /* Constraint 5: min number of connections*/ +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, 1); +#endif + for (c=1; c<=c_mechs; c++) + { + // b_t - n_t * b_min >= 0 +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif +#if HAVE_LIBGLPK + _lp_set_row_bnds(ats->prob, row_index, GLP_LO, v_n_min, 0.0); +#endif + ia[array_index] = row_index; + ja[array_index] = c_mechs + mechanisms[c].col_index; + ar[array_index] = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + } + row_index ++; + + // optimisation constraints + + // adding columns + + // Constraint 6: optimize for diversity + int col_d; + + col_d = _lp_add_cols(ats->prob, 1); +#if HAVE_LIBGLPK + _lp_set_col_name(ats->prob, col_d, "d"); + _lp_set_obj_coef(ats->prob, col_d, D); + _lp_set_col_bnds(ats->prob, col_d, GLP_LO, 0.0, 0.0); + glp_add_rows(ats->prob, 1); + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); +#endif + stat->col_d = col_d; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif + for (c=1; c<=c_mechs; c++) + { + ia[array_index] = row_index; + ja[array_index] = c_mechs + mechanisms[c].col_index; + ar[array_index] = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + } + ia[array_index] = row_index; + ja[array_index] = col_d; + ar[array_index] = -1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + row_index ++; + + + // Constraint 7: optimize for quality + int col_qm; + col_qm = _lp_add_cols(ats->prob, c_q_metrics); + + stat->col_qm = col_qm; + //GNUNET_assert (col_qm == (2*c_mechs) + 3 + 1); + for (c=0; c< c_q_metrics; c++) + { + GNUNET_asprintf(&name, "Q_%s",qm[c].name); + _lp_set_col_name (ats->prob, col_qm + c, name); + _lp_set_col_bnds (ats->prob, col_qm + c, GLP_LO, 0.0, 0.0); + GNUNET_free (name); + _lp_set_obj_coef (ats->prob, col_qm + c, Q[c]); + } +#if HAVE_LIBGLPK + glp_add_rows(ats->prob, available_quality_metrics); +#endif + stat->begin_qm = row_index; + for (c=1; c <= c_q_metrics; c++) + { +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif + double value = 1; +#if HAVE_LIBGLPK + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); +#endif + for (c2=1; c2<=c_mechs; c2++) + { + + ia[array_index] = row_index; + ja[array_index] = c2; + if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY) + { + double v0 = 0, v1 = 0, v2 = 0; + v0 = mechanisms[c2].addr->quality[c-1].values[0]; + if (v1 < 1) v0 = 0.1; + v1 = mechanisms[c2].addr->quality[c-1].values[1]; + if (v1 < 1) v0 = 0.1; + v2 = mechanisms[c2].addr->quality[c-1].values[2]; + if (v1 < 1) v0 = 0.1; + value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0); + value = 1; + } + if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE) + { + double v0 = 0, v1 = 0, v2 = 0; + v0 = mechanisms[c2].addr->quality[c-1].values[0]; + if (v0 < 1) v0 = 1; + v1 = mechanisms[c2].addr->quality[c-1].values[1]; + if (v1 < 1) v1 = 1; + v2 = mechanisms[c2].addr->quality[c-1].values[2]; + if (v2 < 1) v2 = 1; + value = (v0 + 2 * v1 + 3 * v2) / 6.0; + if (value >= 1) + value = (double) 10 / value; + else + value = 10; + } + ar[array_index] = (mechanisms[c2].peer->f) * value ; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",array_index, qm[c-1].name, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + } + + ia[array_index] = row_index; + ja[array_index] = col_qm + c - 1; + ar[array_index] = -1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + row_index++; + } + stat->end_qm = row_index-1; + + // Constraint 8: optimize bandwidth utility + int col_u; + + col_u = _lp_add_cols(ats->prob, 1); +#if HAVE_LIBGLPK + _lp_set_col_name(ats->prob, col_u, "u"); + _lp_set_obj_coef(ats->prob, col_u, U); + _lp_set_col_bnds(ats->prob, col_u, GLP_LO, 0.0, 0.0); + glp_add_rows(ats->prob, 1); +#endif + stat->col_u = col_u; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); + for (c=1; c<=c_mechs; c++) + { + ia[array_index] = row_index; + ja[array_index] = c; + ar[array_index] = mechanisms[c].peer->f; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + } + ia[array_index] = row_index; + ja[array_index] = col_u; + ar[array_index] = -1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + + array_index++; + row_index ++; + + // Constraint 9: optimize relativity + int col_r; + + col_r = _lp_add_cols(ats->prob, 1); +#if HAVE_LIBGLPK + _lp_set_col_name(ats->prob, col_r, "r"); + _lp_set_obj_coef(ats->prob, col_r, R); + _lp_set_col_bnds(ats->prob, col_r, GLP_LO, 0.0, 0.0); + glp_add_rows(ats->prob, c_peers); +#endif + stat->col_r = col_r; + for (c=1; c<=c_peers; c++) + { + _lp_set_row_bnds(ats->prob, row_index, GLP_LO, 0.0, 0.0); + + struct ATS_mechanism *m = peers[c].m_head; + while (m!=NULL) + { + ia[array_index] = row_index; + ja[array_index] = m->col_index; + ar[array_index] = 1 / mechanisms[c].peer->f; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + m = m->next; + } + ia[array_index] = row_index; + ja[array_index] = col_r; + ar[array_index] = -1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, ia[array_index], ja[array_index], ar[array_index]); +#endif + array_index++; + row_index++; + } + + /* Loading the matrix */ + _lp_load_matrix(ats->prob, array_index-1, ia, ja, ar); + + stat->c_mechs = c_mechs; + stat->c_peers = c_peers; + stat->solution = 0; + stat->valid = GNUNET_YES; + + /* clean up */ + GNUNET_free (ja); + GNUNET_free (ia); + GNUNET_free (ar); + + return GNUNET_OK; +} + + +void ats_delete_problem (struct ATS_info * ats) +{ +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting problem\n"); +#endif + int c; + + for (c=0; c< (ats->stat).c_mechs; c++) + GNUNET_free_non_null (ats->mechanisms[c].rc); + + + if (ats->mechanisms!=NULL) + { + GNUNET_free(ats->mechanisms); + ats->mechanisms = NULL; + } + + if (ats->peers!=NULL) + { + GNUNET_free(ats->peers); + ats->peers = NULL; + } + + if (ats->prob != NULL) + { + _lp_delete_prob(ats->prob); + ats->prob = NULL; + } + + ats->stat.begin_cr = GNUNET_SYSERR; + ats->stat.begin_qm = GNUNET_SYSERR; + ats->stat.c_mechs = 0; + ats->stat.c_peers = 0; + ats->stat.end_cr = GNUNET_SYSERR; + ats->stat.end_qm = GNUNET_SYSERR; + ats->stat.solution = GNUNET_SYSERR; + ats->stat.valid = GNUNET_SYSERR; +} + + + +void ats_solve_problem (struct ATS_info * ats, unsigned int max_it, unsigned int max_dur, unsigned int c_peers, unsigned int c_mechs, struct ATS_stat *stat) +{ + int result = GNUNET_SYSERR; + int lp_solution = GNUNET_SYSERR; + int mlp_solution = GNUNET_SYSERR; + + // Solving simplex + + glp_smcp opt_lp; + + _lp_init_smcp(&opt_lp); +#if VERBOSE_ATS + opt_lp.msg_lev = GLP_MSG_ALL; +#else + opt_lp.msg_lev = GLP_MSG_OFF; +#endif + + // setting iteration limit + opt_lp.it_lim = max_it; + // maximum duration + opt_lp.tm_lim = max_dur; + + if (ats->stat.recreate_problem == GNUNET_YES) + opt_lp.presolve = GLP_ON; + result = _lp_simplex(ats->prob, &opt_lp); + lp_solution = _lp_get_status (ats->prob); + + if ((result == GLP_ETMLIM) || (result == GLP_EITLIM)) + { + ats->stat.valid = GNUNET_NO; + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ATS exceeded time or iteration limit!\n"); + return; + } + + if (ats_evaluate_results(result, lp_solution, "LP") == GNUNET_YES) + { + stat->valid = GNUNET_YES; + } + else + { + ats->stat.simplex_rerun_required = GNUNET_YES; + opt_lp.presolve = GLP_ON; + result = _lp_simplex(ats->prob, &opt_lp); + lp_solution = _lp_get_status (ats->prob); + + // TODO: Remove if this does not appear until release + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "EXECUTED SIMPLEX WITH PRESOLVER! %i \n", lp_solution); + + if (ats_evaluate_results(result, lp_solution, "LP") != GNUNET_YES) + { + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "After execution simplex with presolver: STILL INVALID!\n"); + char * filename; + GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%llu.mlp",ats->stat.c_peers, ats->stat.c_mechs, GNUNET_TIME_absolute_get().abs_value); + _lp_write_lp (ats->prob, NULL, filename); + GNUNET_free (filename); + stat->valid = GNUNET_NO; + ats->stat.recreate_problem = GNUNET_YES; + return; + } + stat->valid = GNUNET_YES; + } + + // Solving mlp + glp_iocp opt_mlp; + _lp_init_iocp(&opt_mlp); + // maximum duration + opt_mlp.tm_lim = max_dur; + // output level +#if VERBOSE_ATS + opt_mlp.msg_lev = GLP_MSG_ALL; +#else + opt_mlp.msg_lev = GLP_MSG_OFF; +#endif + + result = _lp_intopt (ats->prob, &opt_mlp); + mlp_solution = _lp_mip_status (ats->prob); + stat->solution = mlp_solution; + + if (ats_evaluate_results(result, mlp_solution, "MLP") == GNUNET_YES) + { + stat->valid = GNUNET_YES; + } + else + { + // TODO: Remove if this does not appear until release + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP solution for %i peers, %i mechs is invalid: %i\n", ats->stat.c_peers, ats->stat.c_mechs, mlp_solution); + stat->valid = GNUNET_NO; + } + +/* + int check; + int error = GNUNET_NO; + double bw; + struct ATS_mechanism *t = NULL; + for (c=1; c<= (c_peers); c++ ) + { + check = GNUNET_NO; + t = peers[c].m_head; + while (t!=NULL) + { + bw = glp_get_col_prim(prob, t->col_index); + if (bw > 1.0) + { +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[%i][%i] `%s' %s %s %f\n", c, t->col_index, GNUNET_h2s(&peers[c].peer.hashPubKey), t->plugin->short_name, glp_get_col_name(prob,t->col_index), bw); +#endif + if (check ==GNUNET_YES) + { + glp_write_sol(prob, "invalid_solution.mlp"); + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Invalid solution, check invalid_solution.mlp"); + GNUNET_STATISTICS_update (stats, "ATS invalid solutions", 1, GNUNET_NO); + error = GNUNET_YES; + } + if (check ==GNUNET_NO) + check = GNUNET_YES; + } + t = t->next; + } + }*/ + +#if VERBOSE_ATS + if (glp_get_col_prim(ats->prob,2*c_mechs+1) != 1) + { + int c; + for (c=1; c<= available_quality_metrics; c++ ) + { + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+3+c), glp_get_col_prim(ats->prob,2*c_mechs+3+c)); + } + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+1), glp_get_col_prim(ats->prob,2*c_mechs+1)); + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+2), glp_get_col_prim(ats->prob,2*c_mechs+2)); + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n", glp_get_col_name(ats->prob,2*c_mechs+3), glp_get_col_prim(ats->prob,2*c_mechs+3)); + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "objective value: %f\n", glp_mip_obj_val(ats->prob)); + } +#endif +} + + +void ats_shutdown (struct ATS_info * ats) +{ +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ats_destroy\n"); +#endif + if (ats->ats_task != GNUNET_SCHEDULER_NO_TASK) + GNUNET_SCHEDULER_cancel(ats->ats_task); + ats->ats_task = GNUNET_SCHEDULER_NO_TASK; + +#if HAVE_LIBGLPK + ats_delete_problem (ats); + glp_free_env(); +#endif + GNUNET_free (ats); +} + +void ats_update_problem_qm (struct ATS_info * ats) +{ + int array_index; + int row_index; + int c, c2; + int c_q_metrics = available_quality_metrics; + + int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); + double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n"); +#endif + row_index = ats->stat.begin_qm; + + for (c=1; c <= c_q_metrics; c++) + { + array_index = 1; + double value = 1; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n",row_index); +#endif + + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); + for (c2=1; c2<=ats->stat.c_mechs; c2++) + { + ja[array_index] = c2; + + GNUNET_assert (ats->mechanisms[c2].addr != NULL); + GNUNET_assert (ats->mechanisms[c2].peer != NULL); + + if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY) + { + double v0 = 0, v1 = 0, v2 = 0; + + v0 = ats->mechanisms[c2].addr->quality[c-1].values[0]; + if (v1 < 1) v0 = 0.1; + v1 = ats->mechanisms[c2].addr->quality[c-1].values[1]; + if (v1 < 1) v0 = 0.1; + v2 = ats->mechanisms[c2].addr->quality[c-1].values[2]; + if (v1 < 1) v0 = 0.1; + value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0); + //value = 1; + } + if (qm[c-1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE) + { + double v0 = 0, v1 = 0, v2 = 0; + v0 = ats->mechanisms[c2].addr->quality[c-1].values[0]; + if (v0 < 1) v0 = 1; + v1 = ats->mechanisms[c2].addr->quality[c-1].values[1]; + if (v1 < 1) v1 = 1; + v2 = ats->mechanisms[c2].addr->quality[c-1].values[2]; + if (v2 < 1) v2 = 1; + value = (v0 + 2 * v1 + 3 * v2) / 6.0; + if (value >= 1) + value = (double) 10 / value; + else + value = 10; + } + ar[array_index] = (ats->mechanisms[c2].peer->f) * value; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",array_index, qm[c-1].name, row_index, ja[array_index], ar[array_index]); +#endif + array_index++; + } + ja[array_index] = ats->stat.col_qm + c - 1; + ar[array_index] = -1; + +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, row_index, ja[array_index], ar[array_index]); +#endif + _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar); + + array_index = 1; + row_index++; + } + + GNUNET_free_non_null (ja); + GNUNET_free_non_null (ar); +} + + +void +ats_calculate_bandwidth_distribution (struct ATS_info * ats, struct GNUNET_STATISTICS_Handle *stats, struct NeighbourList *neighbours) +{ +#if HAVE_LIBGLPK + + struct GNUNET_TIME_Absolute start; + struct GNUNET_TIME_Relative creation; + struct GNUNET_TIME_Relative solving; + char *text = "unmodified"; + + struct GNUNET_TIME_Relative delta = GNUNET_TIME_absolute_get_difference (ats->last, GNUNET_TIME_absolute_get()); + if (delta.rel_value < ats->min_delta.rel_value) + { +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_BULK, "Minimum time between cycles not reached\n"); +#endif + return; + } + +#if FIXME_WACHS + int dur; + if (INT_MAX < ats->max_exec_duration.rel_value) + dur = INT_MAX; + else + dur = (int) ats->max_exec_duration.rel_value; +#endif + + ats->stat.simplex_rerun_required = GNUNET_NO; + start = GNUNET_TIME_absolute_get(); + if ((ats->stat.recreate_problem == GNUNET_YES) || (ats->prob==NULL) || (ats->stat.valid == GNUNET_NO)) + { + text = "new"; + ats->stat.recreate_problem = GNUNET_YES; + ats_delete_problem (ats); + ats_create_problem (ats, neighbours, ats->D, ats->U, ats->R, ats->v_b_min, ats->v_n_min, &ats->stat); +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Peers/Addresses were modified... new problem: %i peer, %i mechs\n", ats->stat.c_peers, ats->stat.c_mechs); +#endif + } + + else if ((ats->stat.recreate_problem == GNUNET_NO) && (ats->stat.modified_resources == GNUNET_YES) && (ats->stat.valid == GNUNET_YES)) + { + text = "modified resources"; + ats_update_problem_cr (ats); + } + else if ((ats->stat.recreate_problem == GNUNET_NO) && (ats->stat.modified_quality == GNUNET_YES) && (ats->stat.valid == GNUNET_YES)) + { + text = "modified quality"; + ats_update_problem_qm (ats); + //ats_update_problem_qm_TEST (); + + } +#if DEBUG_ATS + else GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Problem is unmodified\n"); +#endif + + creation = GNUNET_TIME_absolute_get_difference(start,GNUNET_TIME_absolute_get()); + start = GNUNET_TIME_absolute_get(); + + ats->stat.solution = GLP_UNDEF; + if (ats->stat.valid == GNUNET_YES) + { + ats_solve_problem(ats, ats->max_iterations, ats->max_exec_duration.rel_value, ats->stat.c_peers, ats->stat.c_mechs, &ats->stat); + } + solving = GNUNET_TIME_absolute_get_difference(start,GNUNET_TIME_absolute_get()); + + if (ats->stat.valid == GNUNET_YES) + { + int msg_type = GNUNET_ERROR_TYPE_DEBUG; +#if DEBUG_ATS + msg_type = GNUNET_ERROR_TYPE_ERROR; +#endif + GNUNET_log (msg_type, "MLP %s: creation time: %llu, execution time: %llu, %i mechanisms, simplex rerun: %s, solution %s\n", + text, creation.rel_value, solving.rel_value, + ats->stat.c_mechs, + (ats->stat.simplex_rerun_required == GNUNET_NO) ? "NO" : "YES", (ats->stat.solution == 5) ? "OPTIMAL" : "INVALID"); + ats->successful_executions ++; + GNUNET_STATISTICS_set (stats, "# ATS successful executions", ats->successful_executions, GNUNET_NO); + + if ((ats->stat.recreate_problem == GNUNET_YES) || (ats->prob==NULL)) + GNUNET_STATISTICS_set (stats, "ATS state",ATS_NEW, GNUNET_NO); + else if ((ats->stat.modified_resources == GNUNET_YES) && + (ats->stat.modified_quality == GNUNET_NO)) + GNUNET_STATISTICS_set (stats, "ATS state", ATS_C_UPDATED, GNUNET_NO); + else if ((ats->stat.modified_resources == GNUNET_NO) && + (ats->stat.modified_quality == GNUNET_YES) && + (ats->stat.simplex_rerun_required == GNUNET_NO)) + GNUNET_STATISTICS_set (stats, "ATS state", ATS_Q_UPDATED, GNUNET_NO); + else if ((ats->stat.modified_resources == GNUNET_YES) && + (ats->stat.modified_quality == GNUNET_YES) && + (ats->stat.simplex_rerun_required == GNUNET_NO)) + GNUNET_STATISTICS_set (stats, "ATS state", ATS_QC_UPDATED, GNUNET_NO); + else if (ats->stat.simplex_rerun_required == GNUNET_NO) + GNUNET_STATISTICS_set (stats, "ATS state", ATS_UNMODIFIED, GNUNET_NO); + } + else + { + if (ats->stat.c_peers != 0) + { + ats->invalid_executions ++; + GNUNET_STATISTICS_set (stats, "# ATS invalid executions", ats->invalid_executions, GNUNET_NO); + } + else + { + GNUNET_STATISTICS_set (stats, "# ATS successful executions", ats->successful_executions, GNUNET_NO); + } + } + + GNUNET_STATISTICS_set (stats, "ATS duration", solving.rel_value + creation.rel_value, GNUNET_NO); + GNUNET_STATISTICS_set (stats, "ATS mechanisms", ats->stat.c_mechs, GNUNET_NO); + GNUNET_STATISTICS_set (stats, "ATS peers", ats->stat.c_peers, GNUNET_NO); + GNUNET_STATISTICS_set (stats, "ATS solution", ats->stat.solution, GNUNET_NO); + GNUNET_STATISTICS_set (stats, "ATS timestamp", start.abs_value, GNUNET_NO); + + if ((ats->save_mlp == GNUNET_YES) && (ats->stat.c_mechs >= ats->dump_min_peers) && (ats->stat.c_mechs >= ats->dump_min_addr)) + { + char * filename; + if (ats->dump_overwrite == GNUNET_NO) + { + GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.mlp", + ats->stat.c_peers, ats->stat.c_mechs, text, GNUNET_TIME_absolute_get().abs_value); + _lp_write_lp (ats->prob, NULL, filename); + } + else + { + GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.mlp", + ats->stat.c_peers, ats->stat.c_mechs ); + _lp_write_lp (ats->prob, NULL, filename); + } + GNUNET_free (filename); + } + if ((ats->save_solution == GNUNET_YES) && (ats->stat.c_mechs >= ats->dump_min_peers) && (ats->stat.c_mechs >= ats->dump_min_addr)) + { + char * filename; + if (ats->dump_overwrite == GNUNET_NO) + { + GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.sol", + ats->stat.c_peers, ats->stat.c_mechs, text, GNUNET_TIME_absolute_get().abs_value); + glp_print_sol (ats->prob, filename); + } + else + { + GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.sol", + ats->stat.c_peers, ats->stat.c_mechs); + glp_print_sol (ats->prob, filename); + } + GNUNET_free (filename); + } + + ats->last = GNUNET_TIME_absolute_get(); + ats->stat.recreate_problem = GNUNET_NO; + ats->stat.modified_resources = GNUNET_NO; + ats->stat.modified_quality = GNUNET_NO; +#endif +} + +int ats_evaluate_results (int result, int solution, char * problem) +{ + int cont = GNUNET_NO; +#if DEBUG_ATS || VERBOSE_ATS + int error_kind = GNUNET_ERROR_TYPE_DEBUG; +#endif +#if VERBOSE_ATS + error_kind = GNUNET_ERROR_TYPE_ERROR; +#endif + + switch (result) { + case GNUNET_SYSERR : /* GNUNET problem, not GLPK related */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s , GLPK solving not executed\n", problem); +#endif + break; + case GLP_ESTOP : /* search terminated by application */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s , Search terminated by application\n", problem); +#endif + break; + case GLP_EITLIM : /* iteration limit exceeded */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Iteration limit exceeded\n", problem); +#endif + break; + case GLP_ETMLIM : /* time limit exceeded */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Time limit exceeded\n", problem); +#endif + break; + case GLP_ENOPFS : /* no primal feasible solution */ + case GLP_ENODFS : /* no dual feasible solution */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s No feasible solution\n", problem); +#endif + break; + + case GLP_EBADB : /* invalid basis */ + case GLP_ESING : /* singular matrix */ + case GLP_ECOND : /* ill-conditioned matrix */ + case GLP_EBOUND : /* invalid bounds */ + case GLP_EFAIL : /* solver failed */ + case GLP_EOBJLL : /* objective lower limit reached */ + case GLP_EOBJUL : /* objective upper limit reached */ + case GLP_EROOT : /* root LP optimum not provided */ +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s Invalid Input data: %i\n", problem, result); +#endif + break; + + case 0: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s Problem has been solved\n", problem); +#endif + break; + } + + switch (solution) { + case GLP_UNDEF: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s solution is undefined\n", problem); +#endif + break; + case GLP_OPT: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s solution is optimal\n", problem); +#endif + cont=GNUNET_YES; + break; + case GLP_FEAS: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s solution is %s feasible, however, its optimality (or non-optimality) has not been proven, \n", problem, (0==strcmp(problem,"LP")?"":"integer")); +#endif + cont=GNUNET_YES; + break; + case GLP_NOFEAS: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s problem has no %sfeasible solution\n", problem, (0==strcmp(problem,"LP")?"":"integer ")); +#endif + break; + case GLP_INFEAS: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s problem is infeasible \n", problem); +#endif + break; + case GLP_UNBND: +#if DEBUG_ATS || VERBOSE_ATS + GNUNET_log (error_kind, "%s problem is unbounded \n", problem); +#endif + default: + break; + } +return cont; +} + +void ats_update_problem_cr (struct ATS_info * ats) +{ + + int array_index; + int row_index; + int c, c2; + double ct_max, ct_min; + + int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); + double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); + + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n"); + row_index = ats->stat.begin_cr; + array_index = 1; + + for (c=0; cprob, row_index, GLP_DB, ct_min, ct_max); + + for (c2=1; c2<=ats->stat.c_mechs; c2++) + { + double value = 0; + + GNUNET_assert (ats->mechanisms[c2].addr != NULL); + GNUNET_assert (ats->mechanisms[c2].peer != NULL); + + ja[array_index] = c2; + value = ats->mechanisms[c2].addr->ressources[c].c; + ar[array_index] = value; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",array_index, row_index, ja[array_index], ar[array_index]); +#endif + array_index++; + } + _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar); + + row_index ++; + } + + + GNUNET_free_non_null (ja); + GNUNET_free_non_null (ar); +} + +#if 0 +static void ats_update_problem_qm_TEST () +{ + int row_index; + int c, c2; + + int old_ja[ats->stat.c_mechs + 2]; + double old_ar[ats->stat.c_mechs + 2]; + int c_old; + int changed = 0; + + int *ja = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (int)); + double *ar = GNUNET_malloc ((1 + ats->stat.c_mechs*2 + 3 + available_quality_metrics) * sizeof (double)); +#if DEBUG_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics TEST\n"); +#endif + if (ats->stat.begin_qm >0) + row_index = ats->stat.begin_qm; + else + return; + + + for (c=0; cprob, row_index, old_ja, old_ar); + + _lp_set_row_bnds(ats->prob, row_index, GLP_FX, 0.0, 0.0); + + for (c2=1; c2<=c_old; c2++) + { + ja[c2] = old_ja[c2]; + if ((changed < 3) && (c2>2) && (old_ar[c2] != -1)) + { + ar[c2] = old_ar[c2] + 5 - changed; + changed ++; + } + else + ar[c2] = old_ar[c2]; +#if VERBOSE_ATS + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: old [%i,%i]=%f new [%i,%i]=%f\n",c2, row_index, old_ja[c2], old_ar[c2], row_index, ja[c2], ar[c2]); +#endif + } + _lp_set_mat_row (ats->prob, row_index, c_old, ja, ar); + + row_index ++; + } + + GNUNET_free_non_null (ja); + GNUNET_free_non_null (ar); +} +#endif + + + +/* end of transport_ats.c */ + diff --git a/src/transport/transport_ats.h b/src/transport/transport_ats.h new file mode 100644 index 000000000..33c0d1103 --- /dev/null +++ b/src/transport/transport_ats.h @@ -0,0 +1,371 @@ +#include "platform.h" +#include "gnunet_constants.h" +#include "gnunet_scheduler_lib.h" +#include "gnunet_statistics_service.h" + + +#if HAVE_LIBGLPK +#include +#endif + +/* + * ATS defines + */ + +#define DEBUG_ATS GNUNET_NO +#define VERBOSE_ATS GNUNET_NO + + +/* Minimum time between to calculations*/ +#define ATS_MIN_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 15) +#define ATS_EXEC_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30) +#define ATS_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3) +#define ATS_MAX_ITERATIONS INT_MAX + +#define ATS_DEFAULT_D 1.0 +#define ATS_DEFAULT_U 1.0 +#define ATS_DEFAULT_R 1.0 +#define ATS_DEFAULT_B_MIN 64000 +#define ATS_DEFAULT_N_MIN 10 + +#define VERY_BIG_DOUBLE_VALUE 100000000000LL + +#define ATS_NEW 0 +#define ATS_Q_UPDATED 1 +#define ATS_C_UPDATED 2 +#define ATS_QC_UPDATED 3 +#define ATS_UNMODIFIED 4 + +/* + * ATS data structures + */ + +struct ATS_stat +{ + /** + * result of last GLPK run + * 5 == OPTIMAL + */ + int solution; + + /** + * Ressource costs or quality metrics changed + * update problem before solving + */ + int modified_resources; + + /** + * Ressource costs or quality metrics changed, update matrix + * update problem before solving + */ + int modified_quality; + + /** + * Peers have connected or disconnected + * problem has to be recreated + */ + int recreate_problem; + + /** + * Was the available basis invalid and we needed to rerun simplex? + */ + int simplex_rerun_required; + + /** + * is problem currently valid and can it be solved + */ + int valid; + + /** + * Number of transport mechanisms in the problem + */ + int c_mechs; + + /** + * Number of transport mechanisms in the problem + */ + int c_peers; + + /** + * row index where quality related rows start + */ + int begin_qm; + + /** + * row index where quality related rows end + */ + int end_qm; + + /** + * row index where ressource cost related rows start + */ + int begin_cr; + + /** + * row index where ressource cost related rows end + */ + int end_cr; + + /** + * column index for objective function value d + */ + int col_d; + + /** + * column index for objective function value u + */ + int col_u; + + /** + * column index for objective function value r + */ + int col_r; + + /** + * column index for objective function value quality metrics + */ + int col_qm; + + /** + * column index for objective function value cost ressources + */ + int col_cr; +}; + +struct ATS_info +{ + + /** + * Time of last execution + */ + struct GNUNET_TIME_Absolute last; + /** + * Minimum intervall between two executions + */ + struct GNUNET_TIME_Relative min_delta; + /** + * Regular intervall when execution is triggered + */ + struct GNUNET_TIME_Relative exec_interval; + /** + * Maximum execution time per calculation + */ + struct GNUNET_TIME_Relative max_exec_duration; + + /** + * GLPK (MLP) problem object + */ +#if HAVE_LIBGLPK + + glp_prob *prob; +#else + void * prob; +#endif + + /** + * task to recalculate the bandwidth assignment + */ + GNUNET_SCHEDULER_TaskIdentifier ats_task; + + /** + * Current state of the GLPK problem + */ + struct ATS_stat stat; + + /** + * mechanisms used in current problem + * needed for problem modification + */ + struct ATS_mechanism * mechanisms; + + /** + * peers used in current problem + * needed for problem modification + */ + struct ATS_peer * peers; + + /** + * number of successful executions + */ + int successful_executions; + + /** + * number with an invalid result + */ + int invalid_executions; + + /** + * Maximum number of LP iterations per calculation + */ + int max_iterations; + + /** + * Dump problem to a file? + */ + int save_mlp; + + /** + * Dump solution to a file + */ + int save_solution; + + /** + * Dump solution when minimum peers: + */ + int dump_min_peers; + + /** + * Dump solution when minimum addresses: + */ + int dump_min_addr; + + /** + * Dump solution overwrite file: + */ + int dump_overwrite; + + /** + * Diversity weight + */ + double D; + + /** + * Utility weight + */ + double U; + + /** + * Relativity weight + */ + double R; + + /** + * Minimum bandwidth per peer + */ + int v_b_min; + + /** + * Minimum number of connections per peer + */ + int v_n_min; +}; + +struct ATS_mechanism +{ + struct ATS_mechanism * prev; + struct ATS_mechanism * next; + struct ForeignAddressList * addr; + struct TransportPlugin * plugin; + struct ATS_peer * peer; + int col_index; + int id; + struct ATS_ressource_cost * rc; +}; + +struct ATS_peer +{ + int id; + struct GNUNET_PeerIdentity peer; + struct NeighbourList * n; + struct ATS_mechanism * m_head; + struct ATS_mechanism * m_tail; + + /* preference value f */ + double f; + int t; +}; + +struct ATS_ressource +{ + /* index in ressources array */ + int index; + /* depending ATSi parameter to calculcate limits */ + int atis_index; + /* cfg option to load limits */ + char * cfg_param; + /* lower bound */ + double c_min; + /* upper bound */ + double c_max; + + /* cofficients for the specific plugins */ + double c_unix; + double c_tcp; + double c_udp; + double c_http; + double c_https; + double c_wlan; + double c_default; +}; + + +struct ATS_ressource_entry +{ + /* index in ressources array */ + int index; + /* depending ATSi parameter to calculcate limits */ + int atis_index; + /* lower bound */ + double c; +}; + + +struct ATS_quality_metric +{ + int index; + int atis_index; + char * name; +}; + +struct ATS_quality_entry +{ + int index; + int atsi_index; + uint32_t values[3]; + int current; +}; + +/* + * ATS ressources + */ + +#define available_ressources 3 + +static struct ATS_ressource ressources[] = +{ + /* FIXME: the coefficients for the specific plugins */ + {1, 7, "LAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 1, 3}, + {2, 7, "WAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 2, 3}, + {3, 4, "WLAN_ENERGY_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 0, 0, 0, 0, 2, 1} +/* + {4, 4, "COST_ENERGY_CONSUMPTION", VERY_BIG_DOUBLE_VALUE}, + {5, 5, "COST_CONNECT", VERY_BIG_DOUBLE_VALUE}, + {6, 6, "COST_BANDWITH_AVAILABLE", VERY_BIG_DOUBLE_VALUE}, + {7, 7, "COST_NETWORK_OVERHEAD", VERY_BIG_DOUBLE_VALUE},*/ +}; + +/* + * ATS quality metrics + */ + +static struct ATS_quality_metric qm[] = +{ + {1, 1028, "QUALITY_NET_DISTANCE"}, + {2, 1034, "QUALITY_NET_DELAY"}, +}; + +#define available_quality_metrics 2 + +/* + * ATS functions + */ +struct ATS_info * ats_init (const struct GNUNET_CONFIGURATION_Handle *cfg); +void ats_shutdown (struct ATS_info * ats); +void ats_delete_problem (struct ATS_info * ats); +int ats_create_problem (struct ATS_info * ats, struct NeighbourList *n, double D, double U, double R, int v_b_min, int v_n_min, struct ATS_stat *stat); +void ats_calculate_bandwidth_distribution (struct ATS_info * ats, struct GNUNET_STATISTICS_Handle *stats, struct NeighbourList *neighbours); +void ats_solve_problem (struct ATS_info * ats, unsigned int max_it, unsigned int max_dur, unsigned int c_peers, unsigned int c_mechs, struct ATS_stat *stat); +int ats_evaluate_results (int result, int solution, char * problem); +void ats_update_problem_qm (struct ATS_info * ats); +void ats_update_problem_cr (struct ATS_info * ats); + -- 2.25.1