2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file ats/gnunet-service-ats_addresses_mlp.c
23 * @brief ats mlp problem solver
24 * @author Matthias Wachs
25 * @author Christian Grothoff
28 #include "gnunet_util_lib.h"
29 #include "gnunet-service-ats_addresses.h"
30 #include "gnunet-service-ats_addresses_mlp.h"
31 #include "gnunet_statistics_service.h"
34 #define WRITE_MLP GNUNET_YES
35 #define DEBUG_ATS GNUNET_YES
36 /* A very big value (~1 TB/s)*/
37 #define M 1100000000000
40 * Translate glpk solver error codes to text
41 * @param retcode return code
42 * @return string with result
45 mlp_solve_to_string (int retcode)
52 return "invalid basis";
55 return "singular matrix";
58 return "ill-conditioned matrix";
61 return "invalid bounds";
64 return "solver failed";
67 return "objective lower limit reached";
70 return "objective upper limit reached";
73 return "iteration limit exceeded";
76 return "time limit exceeded";
79 return "no primal feasible solution";
82 return "root LP optimum not provided";
85 return "search terminated by application";
88 return "relative mip gap tolerance reached";
91 return "no dual feasible solution";
94 return "no convergence";
97 return "numerical instability";
100 return "invalid data";
103 return "result out of range";
107 return "unknown error";
111 return "unknown error";
116 * Translate glpk status error codes to text
117 * @param retcode return code
118 * @return string with result
121 mlp_status_to_string (int retcode)
125 return "solution is undefined";
128 return "solution is feasible";
131 return "solution is infeasible";
134 return "no feasible solution exists";
137 return "solution is optimal";
140 return "solution is unbounded";
144 return "unknown error";
148 return "unknown error";
152 * Find a peer in the DLL
153 * @param the peer to find
154 * @return the peer struct
156 static struct ATS_Peer *
157 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
159 struct ATS_Peer *res = mlp->peer_head;
162 if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
170 * Intercept GLPK terminal output
171 * @param info the mlp handle
172 * @param s the string to print
173 * @return 0: glpk prints output on terminal, 0 != surpress output
176 mlp_term_hook (void *info, const char *s)
178 /* Not needed atm struct MLP_information *mlp = info; */
179 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
184 * Delete the MLP problem and free the constrain matrix
186 * @param mlp the MLP handle
189 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
193 if (mlp->prob != NULL)
194 glp_delete_prob(mlp->prob);
196 /* delete row index */
199 GNUNET_free (mlp->ia);
203 /* delete column index */
206 GNUNET_free (mlp->ja);
210 /* delete coefficients */
213 GNUNET_free (mlp->ar);
222 * Add constraints that are iterating over "forall addresses"
223 * and collects all existing peers for "forall peers" constraints
225 * @param cls GAS_MLP_Handle
226 * @param key Hashcode
227 * @param value ATS_Address
229 * @return GNUNET_OK to continue
232 create_constraint_it (void *cls, const GNUNET_HashCode * key, void *value)
234 struct GAS_MLP_Handle *mlp = cls;
235 struct ATS_Address *address = value;
236 struct MLP_information *mlpi;
237 unsigned int row_index;
239 GNUNET_assert (address->mlp_information != NULL);
240 mlpi = (struct MLP_information *) address->mlp_information;
242 /* c 1) bandwidth capping
243 * b_t + (-M) * n_t <= 0
245 row_index = glp_add_rows (mlp->prob, 1);
246 mlpi->r_c1 = row_index;
247 /* set row bounds: <= 0 */
248 glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
249 mlp->ia[mlp->ci] = row_index;
250 mlp->ja[mlp->ci] = mlpi->c_b;
251 mlp->ar[mlp->ci] = 1;
254 mlp->ia[mlp->ci] = row_index;
255 mlp->ja[mlp->ci] = mlpi->c_n;
256 mlp->ar[mlp->ci] = -M;
259 /* c 3) minimum bandwidth
260 * b_t + (-n_t * b_min) >= 0
263 row_index = glp_add_rows (mlp->prob, 1);
264 mlpi->r_c3 = row_index;
265 /* set row bounds: >= 0 */
266 glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
267 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
269 "!!!!! bmin %i\n", mlp->b_min);
271 mlp->ia[mlp->ci] = row_index;
272 mlp->ja[mlp->ci] = mlpi->c_b;
273 mlp->ar[mlp->ci] = 1;
276 mlp->ia[mlp->ci] = row_index;
277 mlp->ja[mlp->ci] = mlpi->c_n;
278 mlp->ar[mlp->ci] = -64000;
279 //mlp->ar[mlp->ci] = -mlp->b_min;
282 /* c 4) minimum connections
283 * (1)*n_1 + ... + (1)*n_m >= n_min
285 mlp->ia[mlp->ci] = mlp->r_c4;
286 mlp->ja[mlp->ci] = mlpi->c_n;
287 mlp->ar[mlp->ci] = 1;
290 /* c 6) maximize diversity
291 * (1)*n_1 + ... + (1)*n_m - d == 0
293 mlp->ia[mlp->ci] = mlp->r_c6;
294 mlp->ja[mlp->ci] = mlpi->c_n;
295 mlp->ar[mlp->ci] = 1;
304 * Adds the problem constraints for all addresses
305 * Required for problem recreation after address deletion
307 * @param addresses all addresses
311 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
313 unsigned int n_addresses;
318 n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
320 /* Required indices in the constrain matrix
322 * feasibility constraints:
324 * c 1) bandwidth capping
325 * #rows: |n_addresses|
326 * #indices: 2 * |n_addresses|
328 * c 2) one active address per peer
330 * #indices: |n_addresses|
332 * c 3) minium bandwidth assigned
333 * #rows: |n_addresses|
334 * #indices: 2 * |n_addresses|
336 * c 4) minimum number of active connections
338 * #indices: |n_addresses|
340 * c 5) maximum ressource consumption
341 * #rows: |ressources|
342 * #indices: |n_addresses|
344 * Sum for feasibility constraints:
345 * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1
346 * #indices: 7 * |n_addresses|
348 * optimality constraints:
352 * #indices: |n_addresses| + 1
355 * #rows: |quality properties|
356 * #indices:|quality properties| + |n_addresses|
359 int pi = ((7 * n_addresses) /*+ (2 * n_addresses + mlp->m_q + 1)*/);
364 int *ia = GNUNET_malloc (pi * sizeof (int));
368 int *ja = GNUNET_malloc (pi * sizeof (int));
372 double *ar= GNUNET_malloc (pi * sizeof (double));
375 /* Adding constraint rows
376 * This constraints are kind of "for all addresses"
377 * Feasibility constraints:
379 * c 1) bandwidth capping
380 * c 3) minimum bandwidth
381 * c 4) minimum number of connections
382 * c 6) maximize diversity
385 int min = mlp->n_min;
386 if (mlp->n_min > mlp->c_p)
389 mlp->r_c4 = glp_add_rows (mlp->prob, 1);
390 glp_set_row_bnds (mlp->prob, mlp->r_c4, GLP_FX, min, min);
392 /* Add row for c6) */
394 mlp->r_c6 = glp_add_rows (mlp->prob, 1);
395 /* Set type type to fix */
396 glp_set_row_bnds (mlp->prob, mlp->r_c6, GLP_FX, 0.0, 0.0);
398 ia[mlp->ci] = mlp->r_c6 ;
399 ja[mlp->ci] = mlp->c_d;
403 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
405 /* Adding constraint rows
406 * This constraints are kind of "for all peers"
407 * Feasibility constraints:
409 * c 2) 1 address per peer
410 * sum (n_p1_1 + ... + n_p1_n) = 1
413 /* Adding rows for c 2) */
414 row_index = glp_add_rows (mlp->prob, mlp->c_p);
416 struct ATS_Peer * peer = mlp->peer_head;
419 struct ATS_Address *addr = peer->head;
420 struct MLP_information *mlpi = (struct MLP_information *) addr->mlp_information;
421 /* Adding row for c 2) */
422 /* Set row bound == 1 */
423 glp_set_row_bnds (mlp->prob, row_index, GLP_FX, 1.0, 1.0);
427 ia[mlp->ci] = row_index;
428 ja[mlp->ci] = mlpi->c_n;
438 /* For all quality metrics */
440 for (c = 0; c < mlp->m_q; c++)
442 struct ATS_Peer *p = mlp->peer_head;
445 ia[mlp->ci] = row_index;
446 ja[mlp->ci] = mlp->c_q[c];
458 * Add columns for all addresses
460 * @param cls GAS_MLP_Handle
461 * @param key Hashcode
462 * @param value ATS_Address
464 * @return GNUNET_OK to continue
467 create_columns_it (void *cls, const GNUNET_HashCode * key, void *value)
469 struct GAS_MLP_Handle *mlp = cls;
470 struct ATS_Address *address = value;
471 struct MLP_information *mlpi;
475 GNUNET_assert (address->mlp_information != NULL);
476 mlpi = address->mlp_information;
478 /* Add bandwidth column */
479 col = glp_add_cols (mlp->prob, 2);
483 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
485 "Culoumn %i %i\n", mlpi->c_b, mlpi->c_n);
487 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
488 glp_set_col_name (mlp->prob, mlpi->c_b , name);
490 /* Lower bound == 0 */
491 glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
492 /* Continuous value*/
493 glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
494 /* Objective function coefficient == 0 */
495 glp_set_obj_coef (mlp->prob, mlpi->c_b , 1);
498 /* Add usage column */
499 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
500 glp_set_col_name (mlp->prob, mlpi->c_n, name);
502 /* Limit value : 0 <= value <= 1 */
503 glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
505 glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
506 /* Objective function coefficient == 0 */
507 glp_set_obj_coef (mlp->prob, mlpi->c_n, 1);
515 * Create the MLP problem
517 * @param mlp the MLP handle
518 * @return GNUNET_OK or GNUNET_SYSERR
521 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
529 GNUNET_assert (mlp->prob == NULL);
531 /* create the glpk problem */
532 mlp->prob = glp_create_prob ();
534 /* Set a problem name */
535 glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
537 /* Set optimization direction to maximize */
538 glp_set_obj_dir (mlp->prob, GLP_MAX);
540 /* Adding invariant columns */
542 /* Diversity d column */
544 col = glp_add_cols (mlp->prob, 1);
547 glp_set_col_name (mlp->prob, col, "d");
548 /* Column objective function coefficient */
549 glp_set_obj_coef (mlp->prob, col, mlp->co_D);
550 /* Column lower bound = 0.0 */
551 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
553 /* Utilization u column */
555 col = glp_add_cols (mlp->prob, 1);
558 glp_set_col_name (mlp->prob, col, "u");
559 /* Column objective function coefficient */
560 glp_set_obj_coef (mlp->prob, col, mlp->co_U);
561 /* Column lower bound = 0.0 */
562 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
564 /* Relativity r column */
565 col = glp_add_cols (mlp->prob, 1);
568 glp_set_col_name (mlp->prob, col, "r");
569 /* Column objective function coefficient */
570 glp_set_obj_coef (mlp->prob, col, mlp->co_R);
571 /* Column lower bound = 0.0 */
572 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
574 /* Quality metric columns */
575 col = glp_add_cols(mlp->prob, mlp->m_q);
576 for (c = 0; c < mlp->m_q; c++)
578 mlp->c_q[c] = col + c;
579 GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
580 glp_set_col_name (mlp->prob, col + c, name);
581 /* Column lower bound = 0.0 */
582 glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
584 /* Coefficient == Qm */
585 glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
588 /* Add columns for addresses */
589 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
591 /* Add constraints */
592 mlp_add_constraints_all_addresses (mlp, addresses);
594 /* Load the matrix */
595 glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
601 * Solves the LP problem
603 * @param mlp the MLP Handle
604 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
607 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
610 struct GNUNET_TIME_Relative duration;
611 struct GNUNET_TIME_Absolute end;
612 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
615 * Presolver is required if the problem was modified and an existing
616 * valid basis is now invalid */
617 if (mlp->presolver_required == GNUNET_YES)
618 mlp->control_param_lp.presolve = GLP_ON;
620 mlp->control_param_lp.presolve = GLP_OFF;
622 /* Solve LP problem to have initial valid solution */
624 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
627 /* The LP problem instance has been successfully solved. */
629 else if (res == GLP_EITLIM)
631 /* simplex iteration limit has been exceeded. */
632 // TODO Increase iteration limit?
634 else if (res == GLP_ETMLIM)
636 /* Time limit has been exceeded. */
637 // TODO Increase time limit?
641 /* Problem was ill-defined, retry with presolver */
642 if (mlp->presolver_required == GNUNET_NO)
644 mlp->presolver_required = GNUNET_YES;
649 /* Problem was ill-defined, no way to handle that */
650 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
652 "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
653 return GNUNET_SYSERR;
657 end = GNUNET_TIME_absolute_get ();
658 duration = GNUNET_TIME_absolute_get_difference (start, end);
660 mlp->lp_total_duration =+ duration.rel_value;
662 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
663 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
664 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
665 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
668 /* Analyze problem status */
669 res = glp_get_status (mlp->prob);
671 /* solution is optimal */
673 /* solution is feasible */
677 /* Problem was ill-defined, no way to handle that */
679 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
681 "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
682 return GNUNET_SYSERR;
686 /* solved sucessfully, no presolver required next time */
687 mlp->presolver_required = GNUNET_NO;
694 * Solves the MLP problem
696 * @param mlp the MLP Handle
697 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
700 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
703 struct GNUNET_TIME_Relative duration;
704 struct GNUNET_TIME_Absolute end;
705 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
707 /* solve MLP problem */
708 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
712 /* The MLP problem instance has been successfully solved. */
714 else if (res == GLP_EITLIM)
716 /* simplex iteration limit has been exceeded. */
717 // TODO Increase iteration limit?
719 else if (res == GLP_ETMLIM)
721 /* Time limit has been exceeded. */
722 // TODO Increase time limit?
726 /* Problem was ill-defined, no way to handle that */
727 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
729 "Solving MLP problem failed: %s\n", mlp_solve_to_string(res));
730 return GNUNET_SYSERR;
733 end = GNUNET_TIME_absolute_get ();
734 duration = GNUNET_TIME_absolute_get_difference (start, end);
736 mlp->mlp_total_duration =+ duration.rel_value;
738 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
739 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
740 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
741 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
743 /* Analyze problem status */
744 res = glp_mip_status(mlp->prob);
746 /* solution is optimal */
748 /* solution is feasible */
752 /* Problem was ill-defined, no way to handle that */
754 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
756 "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
757 return GNUNET_SYSERR;
764 int mlp_solve_problem (struct GAS_MLP_Handle *mlp);
767 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
769 struct GAS_MLP_Handle *mlp = cls;
771 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
773 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
777 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
779 if (mlp->addr_in_problem != 0)
780 mlp_solve_problem(mlp);
785 * Solves the MLP problem
787 * @param mlp the MLP Handle
788 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
791 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
794 mlp->last_execution = GNUNET_TIME_absolute_get ();
796 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solving\n");
803 GNUNET_asprintf(&name, "problem_%i", i);
804 glp_write_lp (mlp->prob, 0, name);
808 res = mlp_solve_lp_problem (mlp);
811 GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
812 glp_print_sol (mlp->prob, name);
816 if (res != GNUNET_OK)
819 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
821 return GNUNET_SYSERR;
824 res = mlp_solve_mlp_problem (mlp);
827 GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
828 glp_print_mip (mlp->prob, name);
833 if (res != GNUNET_OK)
836 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MLP Problem solving failed\n");
838 return GNUNET_SYSERR;
841 res = glp_mip_status(mlp->prob);
843 if (res != GNUNET_OK)
846 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
848 return GNUNET_SYSERR;
852 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved: %i %s\n", res, mlp_status_to_string(res));
857 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
859 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
860 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
862 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
867 * Init the MLP problem solving component
869 * @param stats the GNUNET_STATISTICS handle
870 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
871 * @param max_iterations maximum time limit for the LP/MLP Solver
872 * @return struct GAS_MLP_Handle * on success, NULL on fail
874 struct GAS_MLP_Handle *
875 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
876 const struct GNUNET_STATISTICS_Handle *stats,
877 struct GNUNET_TIME_Relative max_duration,
878 unsigned int max_iterations)
880 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
885 long long unsigned int tmp;
888 struct GNUNET_TIME_Relative i_exec;
890 /* Init GLPK environment */
891 GNUNET_assert (glp_init_env() == 0);
893 /* Create initial MLP problem */
894 mlp->prob = glp_create_prob();
895 GNUNET_assert (mlp->prob != NULL);
897 /* Get diversity coefficient from configuration */
898 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
901 D = (double) tmp / 100;
905 /* Get proportionality coefficient from configuration */
906 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
909 R = (double) tmp / 100;
913 /* Get utilization coefficient from configuration */
914 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
917 U = (double) tmp / 100;
921 /* Get quality metric coefficients from configuration */
924 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
926 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
928 /* initialize quality coefficients with default value 1.0 */
932 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
934 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
938 if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
939 "COEFFICIENT_QUALITY_DELAY",
942 mlp->co_Q[i_delay] = (double) tmp / 100;
944 mlp->co_Q[i_delay] = 1.0;
946 if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
947 "COEFFICIENT_QUALITY_DISTANCE",
949 mlp->co_Q[i_distance] = (double) tmp / 100;
951 mlp->co_Q[i_distance] = 1.0;
953 /* Get minimum bandwidth per used address from configuration */
954 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
961 /* Get minimum number of connections from configuration */
962 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
969 /* Get minimum number of connections from configuration */
970 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
973 mlp->exec_interval = i_exec;
975 mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
977 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
978 mlp->max_iterations = max_iterations;
979 mlp->max_exec_duration = max_duration;
981 /* Redirect GLPK output to GNUnet logging */
982 glp_error_hook((void *) mlp, &mlp_term_hook);
984 /* Init LP solving parameters */
985 glp_init_smcp(&mlp->control_param_lp);
987 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
989 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
991 mlp->control_param_lp.it_lim = max_iterations;
992 mlp->control_param_lp.tm_lim = max_duration.rel_value;
994 /* Init MLP solving parameters */
995 glp_init_iocp(&mlp->control_param_mlp);
997 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
999 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1001 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1003 mlp->last_execution = GNUNET_TIME_absolute_get_forever();
1010 mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1016 * Updates a single address in the MLP problem
1018 * If the address did not exist before in the problem:
1019 * The MLP problem has to be recreated and the problem has to be resolved
1021 * Otherwise the addresses' values can be updated and the existing base can
1024 * @param mlp the MLP Handle
1025 * @param addresses the address hashmap
1026 * the address has to be already removed from the hashmap
1027 * @param address the address to update
1030 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1033 struct MLP_information *mlpi;
1036 GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
1038 /* We add a new address */
1039 if (address->mlp_information == NULL)
1045 if (new == GNUNET_YES)
1047 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1048 address->mlp_information = mlpi;
1049 mlp->addr_in_problem ++;
1051 /* Check for and add peer */
1052 struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1056 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n", GNUNET_i2s (&address->peer));
1058 peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1062 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1067 memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1068 GNUNET_assert(address->prev == NULL);
1069 GNUNET_assert(address->next == NULL);
1070 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1071 GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1077 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n", GNUNET_i2s (&address->peer));
1079 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1085 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n", GNUNET_i2s (&address->peer));
1090 if (new == GNUNET_YES)
1092 mlp_delete_problem (mlp);
1093 mlp_create_problem (mlp, addresses);
1094 mlp->presolver_required = GNUNET_YES;
1096 mlp_solve_problem (mlp);
1100 * Deletes a single address in the MLP problem
1102 * The MLP problem has to be recreated and the problem has to be resolved
1104 * @param mlp the MLP Handle
1105 * @param addresses the address hashmap
1106 * the address has to be already removed from the hashmap
1107 * @param address the address to delete
1110 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1112 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1114 /* Free resources */
1115 if (address->mlp_information != NULL)
1117 GNUNET_free (address->mlp_information);
1118 address->mlp_information = NULL;
1120 mlp->addr_in_problem --;
1123 /* Remove from peer list */
1124 struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1125 GNUNET_assert (head != NULL);
1127 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1129 GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1130 if ((head->head == NULL) && (head->tail == NULL))
1132 /* No address for peer left, remove peer */
1134 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1136 GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1141 /* Update problem */
1142 mlp_delete_problem (mlp);
1143 if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1146 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "mlp_create_problem %i\n",__LINE__);
1148 mlp_create_problem (mlp, addresses);
1151 mlp->presolver_required = GNUNET_YES;
1152 mlp_solve_problem (mlp);
1157 * Changes the preferences for a peer in the MLP problem
1159 * @param mlp the MLP Handle
1160 * @param peer the peer
1161 * @param kind the kind to change the preference
1162 * @param float the score
1165 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
1166 const struct GNUNET_PeerIdentity *peer,
1167 enum GNUNET_ATS_PreferenceKind kind,
1170 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1172 struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1174 /* Here we have to do the matching */
1178 * Shutdown the MLP problem solving component
1179 * @param mlp the MLP handle
1182 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
1184 struct ATS_Peer * peer;
1185 struct ATS_Peer * tmp;
1187 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1189 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1190 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1193 /* clean up peer list */
1196 peer = mlp->peer_head;
1197 while (peer != NULL)
1199 GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1205 mlp_delete_problem (mlp);
1207 /* Clean up GLPK environment */
1214 /* end of gnunet-service-ats_addresses_mlp.c */