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"
37 * Intercept GLPK terminal output
42 mlp_term_hook (void *info, const char *s)
44 /* Not needed atm struct MLP_information *mlp = info; */
45 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
46 /* 0: glpk prints output on terminal, != surpress output */
51 * Create the MLP problem
53 * @param mlp the MLP handle
54 * @return GNUNET_OK or GNUNET_SYSERR
58 mlp_create_problem (struct GAS_MLP_Handle *mlp)
65 /* Set a problem name */
66 glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
68 /* Set optimization direction to maximize */
69 glp_set_obj_dir (mlp->prob, GLP_MAX);
71 /* Adding invariant columns */
73 /* Diversity d column */
75 col = glp_add_cols (mlp->prob, 1);
78 glp_set_col_name (mlp->prob, col, "d");
79 /* Column objective function coefficient */
80 glp_set_obj_coef (mlp->prob, col, mlp->co_D);
81 /* Column lower bound = 0.0 */
82 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
84 /* Utilization u column */
86 col = glp_add_cols (mlp->prob, 1);
89 glp_set_col_name (mlp->prob, col, "u");
90 /* Column objective function coefficient */
91 glp_set_obj_coef (mlp->prob, col, mlp->co_U);
92 /* Column lower bound = 0.0 */
93 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
95 /* Relativity r column */
96 col = glp_add_cols (mlp->prob, 1);
99 glp_set_col_name (mlp->prob, col, "r");
100 /* Column objective function coefficient */
101 glp_set_obj_coef (mlp->prob, col, mlp->co_R);
102 /* Column lower bound = 0.0 */
103 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
105 /* Quality metric columns */
106 col = glp_add_cols(mlp->prob, mlp->m);
107 for (c = 0; c < mlp->m; c++)
109 mlp->c_q[c] = col + c;
110 GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
111 glp_set_col_name (mlp->prob, col + c, name);
112 /* Column lower bound = 0.0 */
113 glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
115 /* Coefficient == Qm */
116 glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
123 * Solves the LP problem
125 * @param mlp the MLP Handle
126 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
129 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
132 struct GNUNET_TIME_Relative duration;
133 struct GNUNET_TIME_Absolute end;
134 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
137 * Presolver is required if the problem was modified and an existing
138 * valid basis is now invalid */
139 if (mlp->presolver_required == GNUNET_YES)
140 mlp->control_param_lp.presolve = GLP_ON;
142 mlp->control_param_lp.presolve = GLP_OFF;
144 /* Solve LP problem to have initial valid solution */
146 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
149 /* The LP problem instance has been successfully solved. */
151 else if (res == GLP_EITLIM)
153 /* simplex iteration limit has been exceeded. */
154 // TODO Increase iteration limit?
156 else if (res == GLP_ETMLIM)
158 /* Time limit has been exceeded. */
159 // TODO Increase time limit?
163 /* Problem was ill-defined, retry with presolver */
164 if (mlp->presolver_required == GNUNET_NO)
166 mlp->presolver_required = GNUNET_YES;
171 /* Problem was ill-defined, no way to handle that */
172 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
174 "Solving LP problem failed: glp_simplex error 0x%X\n", res);
175 return GNUNET_SYSERR;
179 end = GNUNET_TIME_absolute_get ();
180 duration = GNUNET_TIME_absolute_get_difference (start, end);
182 mlp->lp_total_duration =+ duration.rel_value;
184 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
185 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
186 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
187 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
190 /* Analyze problem status */
191 res = glp_get_status (mlp->prob);
193 /* solution is optimal */
195 /* solution is feasible */
199 /* Problem was ill-defined, no way to handle that */
201 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
203 "Solving LP problem failed, no solution: glp_get_status 0x%X\n", res);
204 return GNUNET_SYSERR;
208 /* solved sucessfully, no presolver required next time */
209 mlp->presolver_required = GNUNET_NO;
216 * Solves the MLP problem
218 * @param mlp the MLP Handle
219 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
222 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
225 struct GNUNET_TIME_Relative duration;
226 struct GNUNET_TIME_Absolute end;
227 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
229 /* solve MLP problem */
230 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
234 /* The MLP problem instance has been successfully solved. */
236 else if (res == GLP_EITLIM)
238 /* simplex iteration limit has been exceeded. */
239 // TODO Increase iteration limit?
241 else if (res == GLP_ETMLIM)
243 /* Time limit has been exceeded. */
244 // TODO Increase time limit?
248 /* Problem was ill-defined, no way to handle that */
249 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
251 "Solving MLP problem failed: glp_intopt error 0x%X\n", res);
252 return GNUNET_SYSERR;
255 end = GNUNET_TIME_absolute_get ();
256 duration = GNUNET_TIME_absolute_get_difference (start, end);
258 mlp->mlp_total_duration =+ duration.rel_value;
260 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
261 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
262 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
263 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
265 /* Analyze problem status */
266 res = glp_mip_status(mlp->prob);
268 /* solution is optimal */
270 /* solution is feasible */
274 /* Problem was ill-defined, no way to handle that */
276 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
278 "Solving MLP problem failed, no solution: glp_mip_status 0x%X\n", res);
279 return GNUNET_SYSERR;
287 * Solves the MLP problem
289 * @param mlp the MLP Handle
290 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
293 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
296 mlp->last_execution = GNUNET_TIME_absolute_get ();
297 res = mlp_solve_lp_problem (mlp);
298 if (res == GNUNET_OK)
299 res = mlp_solve_mlp_problem (mlp);
304 * Init the MLP problem solving component
306 * @param stats the GNUNET_STATISTICS handle
307 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
308 * @param max_iterations maximum time limit for the LP/MLP Solver
309 * @return struct GAS_MLP_Handle * on success, NULL on fail
311 struct GAS_MLP_Handle *
312 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
313 const struct GNUNET_STATISTICS_Handle *stats,
314 struct GNUNET_TIME_Relative max_duration,
315 unsigned int max_iterations)
317 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
322 long long unsigned int tmp;
326 /* Init GLPK environment */
327 GNUNET_assert (glp_init_env() == 0);
329 /* Create initial MLP problem */
330 mlp->prob = glp_create_prob();
331 GNUNET_assert (mlp->prob != NULL);
333 /* Get diversity coefficient from configuration */
334 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
337 D = (double) tmp / 100;
341 /* Get proportionality coefficient from configuration */
342 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
345 R = (double) tmp / 100;
349 /* Get utilization coefficient from configuration */
350 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
353 U = (double) tmp / 100;
357 /* Get quality metric coefficients from configuration */
360 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
362 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
364 /* initialize quality coefficients with default value 1.0 */
368 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
370 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
374 if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
375 "COEFFICIENT_QUALITY_DELAY",
378 mlp->co_Q[i_delay] = (double) tmp / 100;
380 mlp->co_Q[i_delay] = 1.0;
382 if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
383 "COEFFICIENT_QUALITY_DISTANCE",
385 mlp->co_Q[i_distance] = (double) tmp / 100;
387 mlp->co_Q[i_distance] = 1.0;
389 /* Get minimum bandwidth per used address from configuration */
390 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
397 /* Get minimum number of connections from configuration */
398 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
405 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
406 mlp->max_iterations = max_iterations;
407 mlp->max_exec_duration = max_duration;
409 /* Redirect GLPK output to GNUnet logging */
410 glp_error_hook((void *) mlp, &mlp_term_hook);
412 /* Init LP solving parameters */
413 glp_init_smcp(&mlp->control_param_lp);
415 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
417 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
419 mlp->control_param_lp.it_lim = max_iterations;
420 mlp->control_param_lp.tm_lim = max_duration.rel_value;
422 /* Init MLP solving parameters */
423 glp_init_iocp(&mlp->control_param_mlp);
425 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
427 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
429 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
431 mlp->last_execution = GNUNET_TIME_absolute_get_forever();
438 mlp->m = GNUNET_ATS_QualityPropertiesCount;
440 mlp_create_problem (mlp);
445 * Updates a single address in the MLP problem
447 * If the address did not exist before in the problem:
448 * The MLP problem has to be recreated and the problem has to be resolved
450 * Otherwise the addresses' values can be updated and the existing base can
453 * @param mlp the MLP Handle
454 * @param addresses the address hashmap
455 * @param address the address to update
458 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
462 struct MLP_information *mlpi;
465 GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
467 /* We add a new address */
468 if (address->mlp_information == NULL)
471 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
472 address->mlp_information = mlpi;
474 /* Add bandwidth column */
475 col = glp_add_cols (mlp->prob, 2);
479 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
480 glp_set_col_name (mlp->prob, mlpi->c_b , name);
482 /* Lower bound == 0 */
483 glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
484 /* Continuous value*/
485 glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
486 /* Objective function coefficient == 0 */
487 glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
489 /* Add usage column */
490 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
491 glp_set_col_name (mlp->prob, mlpi->c_n, name);
493 /* Limit value : 0 <= value <= 1 */
494 glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
496 glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
497 /* Objective function coefficient == 0 */
498 glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
508 if (new == GNUNET_YES)
509 mlp->presolver_required = GNUNET_YES;
510 mlp_solve_problem (mlp);
514 * Deletes a single address in the MLP problem
516 * The MLP problem has to be recreated and the problem has to be resolved
518 * @param mlp the MLP Handle
519 * @param addresses the address hashmap
520 * @param address the address to delete
523 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
525 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
528 if (address->mlp_information != NULL)
530 GNUNET_free (address->mlp_information);
531 address->mlp_information = NULL;
537 mlp->presolver_required = GNUNET_YES;
538 mlp_solve_problem (mlp);
542 * Deletes a single address in the MLP problem
544 * @param mlp the MLP Handle
545 * @param addresses the address hashmap
546 * @param address the address to change the preference
549 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
551 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
555 * Shutdown the MLP problem solving component
556 * @param mlp the MLP handle
559 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
562 glp_delete_prob(mlp->prob);
564 /* Clean up GLPK environment */
571 /* end of gnunet-service-ats_addresses_mlp.c */