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_NO
35 #define DEBUG_ATS GNUNET_NO
36 #define VERBOSE_GLPK GNUNET_NO
39 * Translate glpk solver error codes to text
40 * @param retcode return code
41 * @return string with result
44 mlp_solve_to_string (int retcode)
51 return "invalid basis";
54 return "singular matrix";
57 return "ill-conditioned matrix";
60 return "invalid bounds";
63 return "solver failed";
66 return "objective lower limit reached";
69 return "objective upper limit reached";
72 return "iteration limit exceeded";
75 return "time limit exceeded";
78 return "no primal feasible solution";
81 return "root LP optimum not provided";
84 return "search terminated by application";
87 return "relative mip gap tolerance reached";
90 return "no dual feasible solution";
93 return "no convergence";
96 return "numerical instability";
99 return "invalid data";
102 return "result out of range";
106 return "unknown error";
110 return "unknown error";
115 * Translate glpk status error codes to text
116 * @param retcode return code
117 * @return string with result
120 mlp_status_to_string (int retcode)
124 return "solution is undefined";
127 return "solution is feasible";
130 return "solution is infeasible";
133 return "no feasible solution exists";
136 return "solution is optimal";
139 return "solution is unbounded";
143 return "unknown error";
147 return "unknown error";
151 * Translate ATS properties to text
152 * Just intended for debugging
154 * @param retcode return code
155 * @return string with result
158 mlp_ats_to_string (int ats_index)
161 case GNUNET_ATS_ARRAY_TERMINATOR:
162 return "GNUNET_ATS_ARRAY_TERMINATOR";
164 case GNUNET_ATS_UTILIZATION_UP:
165 return "GNUNET_ATS_UTILIZATION_UP";
167 case GNUNET_ATS_UTILIZATION_DOWN:
168 return "GNUNET_ATS_UTILIZATION_DOWN";
170 case GNUNET_ATS_COST_LAN:
171 return "GNUNET_ATS_COST_LAN";
173 case GNUNET_ATS_COST_WAN:
174 return "GNUNET_ATS_COST_LAN";
176 case GNUNET_ATS_COST_WLAN:
177 return "GNUNET_ATS_COST_WLAN";
179 case GNUNET_ATS_NETWORK_TYPE:
180 return "GNUNET_ATS_NETWORK_TYPE";
182 case GNUNET_ATS_QUALITY_NET_DELAY:
183 return "GNUNET_ATS_QUALITY_NET_DELAY";
185 case GNUNET_ATS_QUALITY_NET_DISTANCE:
186 return "GNUNET_ATS_QUALITY_NET_DISTANCE";
193 return "unknown error";
197 * Find a peer in the DLL
198 * @param the peer to find
199 * @return the peer struct
201 static struct ATS_Peer *
202 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
204 struct ATS_Peer *res = mlp->peer_head;
207 if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
215 * Intercept GLPK terminal output
216 * @param info the mlp handle
217 * @param s the string to print
218 * @return 0: glpk prints output on terminal, 0 != surpress output
221 mlp_term_hook (void *info, const char *s)
223 /* Not needed atm struct MLP_information *mlp = info; */
224 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
229 * Delete the MLP problem and free the constrain matrix
231 * @param mlp the MLP handle
234 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
238 if (mlp->prob != NULL)
239 glp_delete_prob(mlp->prob);
241 /* delete row index */
244 GNUNET_free (mlp->ia);
248 /* delete column index */
251 GNUNET_free (mlp->ja);
255 /* delete coefficients */
258 GNUNET_free (mlp->ar);
267 * Add constraints that are iterating over "forall addresses"
268 * and collects all existing peers for "forall peers" constraints
270 * @param cls GAS_MLP_Handle
271 * @param key Hashcode
272 * @param value ATS_Address
274 * @return GNUNET_OK to continue
277 create_constraint_it (void *cls, const GNUNET_HashCode * key, void *value)
279 struct GAS_MLP_Handle *mlp = cls;
280 struct ATS_Address *address = value;
281 struct MLP_information *mlpi;
282 unsigned int row_index;
285 GNUNET_assert (address->mlp_information != NULL);
286 mlpi = (struct MLP_information *) address->mlp_information;
288 /* c 1) bandwidth capping
289 * b_t + (-M) * n_t <= 0
291 row_index = glp_add_rows (mlp->prob, 1);
292 mlpi->r_c1 = row_index;
294 GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
295 glp_set_row_name (mlp->prob, row_index, name);
297 /* set row bounds: <= 0 */
298 glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
299 mlp->ia[mlp->ci] = row_index;
300 mlp->ja[mlp->ci] = mlpi->c_b;
301 mlp->ar[mlp->ci] = 1;
304 mlp->ia[mlp->ci] = row_index;
305 mlp->ja[mlp->ci] = mlpi->c_n;
306 mlp->ar[mlp->ci] = -mlp->BIG_M;
309 /* c 3) minimum bandwidth
310 * b_t + (-n_t * b_min) >= 0
313 row_index = glp_add_rows (mlp->prob, 1);
315 GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
316 glp_set_row_name (mlp->prob, row_index, name);
318 mlpi->r_c3 = row_index;
319 /* set row bounds: >= 0 */
320 glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
322 mlp->ia[mlp->ci] = row_index;
323 mlp->ja[mlp->ci] = mlpi->c_b;
324 mlp->ar[mlp->ci] = 1;
327 mlp->ia[mlp->ci] = row_index;
328 mlp->ja[mlp->ci] = mlpi->c_n;
329 mlp->ar[mlp->ci] = - (double) mlp->b_min;
332 /* c 4) minimum connections
333 * (1)*n_1 + ... + (1)*n_m >= n_min
335 mlp->ia[mlp->ci] = mlp->r_c4;
336 mlp->ja[mlp->ci] = mlpi->c_n;
337 mlp->ar[mlp->ci] = 1;
340 /* c 6) maximize diversity
341 * (1)*n_1 + ... + (1)*n_m - d == 0
343 mlp->ia[mlp->ci] = mlp->r_c6;
344 mlp->ja[mlp->ci] = mlpi->c_n;
345 mlp->ar[mlp->ci] = 1;
352 * Find the required ATS information for an address
354 * @param addr the address
355 * @param ats_index the desired ATS index
357 * @return the index on success, otherwise GNUNET_SYSERR
361 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
363 struct GNUNET_ATS_Information * ats = addr->ats;
365 int found = GNUNET_NO;
366 for (c = 0; c < addr->ats_count; c++)
368 if (ats[c].type == ats_index)
374 if (found == GNUNET_YES)
377 return GNUNET_SYSERR;
381 * Adds the problem constraints for all addresses
382 * Required for problem recreation after address deletion
384 * @param addresses all addresses
388 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
390 unsigned int n_addresses;
395 n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
397 /* Required indices in the constrain matrix
399 * feasibility constraints:
401 * c 1) bandwidth capping
402 * #rows: |n_addresses|
403 * #indices: 2 * |n_addresses|
405 * c 2) one active address per peer
407 * #indices: |n_addresses|
409 * c 3) minium bandwidth assigned
410 * #rows: |n_addresses|
411 * #indices: 2 * |n_addresses|
413 * c 4) minimum number of active connections
415 * #indices: |n_addresses|
417 * c 5) maximum ressource consumption
418 * #rows: |ressources|
419 * #indices: |n_addresses|
421 * Sum for feasibility constraints:
422 * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1
423 * #indices: 7 * |n_addresses|
425 * optimality constraints:
429 * #indices: |n_addresses| + 1
432 * #rows: |quality properties|
433 * #indices: |n_addresses| + |quality properties|
437 * #indices: |n_addresses| + 1
441 * #indices: |n_addresses| + |peers|
444 /* last +1 caused by glpk index starting with one */
445 int pi = ((7 * n_addresses) + (4 * n_addresses + mlp->m_q + mlp->c_p + 2) + 1);
450 int *ia = GNUNET_malloc (pi * sizeof (int));
454 int *ja = GNUNET_malloc (pi * sizeof (int));
458 double *ar= GNUNET_malloc (pi * sizeof (double));
461 /* Adding constraint rows
462 * This constraints are kind of "for all addresses"
463 * Feasibility constraints:
465 * c 1) bandwidth capping
466 * c 3) minimum bandwidth
467 * c 4) minimum number of connections
468 * c 6) maximize diversity
471 int min = mlp->n_min;
472 if (mlp->n_min > mlp->c_p)
475 mlp->r_c4 = glp_add_rows (mlp->prob, 1);
476 glp_set_row_name (mlp->prob, mlp->r_c4, "c4");
477 glp_set_row_bnds (mlp->prob, mlp->r_c4, GLP_LO, min, min);
479 /* Add row for c6) */
481 mlp->r_c6 = glp_add_rows (mlp->prob, 1);
482 /* Set type type to fix */
483 glp_set_row_bnds (mlp->prob, mlp->r_c6, GLP_FX, 0.0, 0.0);
485 ia[mlp->ci] = mlp->r_c6 ;
486 ja[mlp->ci] = mlp->c_d;
490 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
492 /* Adding constraint rows
493 * This constraints are kind of "for all peers"
494 * Feasibility constraints:
496 * c 2) 1 address per peer
497 * sum (n_p1_1 + ... + n_p1_n) = 1
500 * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
503 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
506 /* Adding rows for c 8) */
507 mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p);
508 glp_set_row_name (mlp->prob, mlp->r_c8, "c8");
509 /* Set row bound == 0 */
510 glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0);
512 ia[mlp->ci] = mlp->r_c8;
513 ja[mlp->ci] = mlp->c_u;
517 struct ATS_Peer * peer = mlp->peer_head;
520 struct ATS_Address *addr = peer->head;
521 struct MLP_information *mlpi = NULL;
523 /* Adding rows for c 2) */
524 peer->r_c2 = glp_add_rows (mlp->prob, 1);
525 GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
526 glp_set_row_name (mlp->prob, peer->r_c2, name);
528 /* Set row bound == 1 */
529 glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
531 /* Adding rows for c 9) */
532 peer->r_c9 = glp_add_rows (mlp->prob, 1);
533 GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
534 glp_set_row_name (mlp->prob, peer->r_c9, name);
536 /* Set row bound == 0 */
537 glp_set_row_bnds (mlp->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
540 ia[mlp->ci] = peer->r_c9;
541 ja[mlp->ci] = mlp->c_r;
547 mlpi = (struct MLP_information *) addr->mlp_information;
549 ia[mlp->ci] = peer->r_c2;
550 ja[mlp->ci] = mlpi->c_n;
554 ia[mlp->ci] = mlp->r_c8;
555 ja[mlp->ci] = mlpi->c_b;
556 ar[mlp->ci] = peer->f;
559 ia[mlp->ci] = peer->r_c9;
560 ja[mlp->ci] = mlpi->c_b;
569 /* c 7) For all quality metrics */
571 for (c = 0; c < mlp->m_q; c++)
573 struct ATS_Peer *p = mlp->peer_head;
574 struct ATS_Address *addr = p->head;
575 struct MLP_information * mlpi;
580 /* Adding rows for c 7) */
581 mlp->r_q[c] = glp_add_rows (mlp->prob, 1);
582 GNUNET_asprintf(&name, "c7_q%i_atsi_%i", c, mlp->q[c]);
583 glp_set_row_name (mlp->prob, mlp->r_q[c], name);
585 /* Set row bound == 0 */
586 glp_set_row_bnds (mlp->prob, mlp->r_q[c], GLP_LO, 0.0, 0.0);
589 ia[mlp->ci] = mlp->r_q[c];
590 ja[mlp->ci] = mlp->c_q[c];
596 mlpi = addr->mlp_information;
597 /* lookup ATS information */
598 int index = mlp_lookup_ats(addr, mlp->q[c]);
600 if (index != GNUNET_SYSERR)
602 value = (double) addr->ats[index].value;
604 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Quality %i with ATS property `%s' has index %i in addresses ats information has value %f\n", c, mlp_ats_to_string(mlp->q[c]), index, (double) addr->ats[index].value);
609 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Quality %i with ATS property `%s' not existing\n", c, mlp_ats_to_string(mlp->q[c]), index);
611 mlpi = addr->mlp_information;
613 mlpi->r_q[c] = mlp->r_q[c];
614 mlpi->c_q[c] = mlpi->c_b;
617 ia[mlp->ci] = mlp->r_q[c];
618 ja[mlp->ci] = mlpi->c_b;
619 ar[mlp->ci] = p->f * value;
631 * Add columns for all addresses
633 * @param cls GAS_MLP_Handle
634 * @param key Hashcode
635 * @param value ATS_Address
637 * @return GNUNET_OK to continue
640 create_columns_it (void *cls, const GNUNET_HashCode * key, void *value)
642 struct GAS_MLP_Handle *mlp = cls;
643 struct ATS_Address *address = value;
644 struct MLP_information *mlpi;
648 GNUNET_assert (address->mlp_information != NULL);
649 mlpi = address->mlp_information;
651 /* Add bandwidth column */
652 col = glp_add_cols (mlp->prob, 2);
656 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
657 glp_set_col_name (mlp->prob, mlpi->c_b , name);
659 /* Lower bound == 0 */
660 glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
661 /* Continuous value*/
662 glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
663 /* Objective function coefficient == 0 */
664 glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
667 /* Add usage column */
668 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
669 glp_set_col_name (mlp->prob, mlpi->c_n, name);
671 /* Limit value : 0 <= value <= 1 */
672 glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
674 glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
675 /* Objective function coefficient == 0 */
676 glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
684 * Create the MLP problem
686 * @param mlp the MLP handle
687 * @return GNUNET_OK or GNUNET_SYSERR
690 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
697 GNUNET_assert (mlp->prob == NULL);
699 /* create the glpk problem */
700 mlp->prob = glp_create_prob ();
702 /* Set a problem name */
703 glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
705 /* Set optimization direction to maximize */
706 glp_set_obj_dir (mlp->prob, GLP_MAX);
708 /* Adding invariant columns */
710 /* Diversity d column */
712 col = glp_add_cols (mlp->prob, 1);
715 glp_set_col_name (mlp->prob, col, "d");
716 /* Column objective function coefficient */
717 glp_set_obj_coef (mlp->prob, col, mlp->co_D);
718 /* Column lower bound = 0.0 */
719 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
721 /* Utilization u column */
723 col = glp_add_cols (mlp->prob, 1);
726 glp_set_col_name (mlp->prob, col, "u");
727 /* Column objective function coefficient */
728 glp_set_obj_coef (mlp->prob, col, mlp->co_U);
729 /* Column lower bound = 0.0 */
730 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
732 /* Relativity r column */
733 col = glp_add_cols (mlp->prob, 1);
736 glp_set_col_name (mlp->prob, col, "r");
737 /* Column objective function coefficient */
738 glp_set_obj_coef (mlp->prob, col, mlp->co_R);
739 /* Column lower bound = 0.0 */
740 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
742 /* Quality metric columns */
743 col = glp_add_cols(mlp->prob, mlp->m_q);
744 for (c = 0; c < mlp->m_q; c++)
746 mlp->c_q[c] = col + c;
747 GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
748 glp_set_col_name (mlp->prob, col + c, name);
749 /* Column lower bound = 0.0 */
750 glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
752 /* Coefficient == Qm */
753 glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
756 /* Add columns for addresses */
757 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
759 /* Add constraints */
760 mlp_add_constraints_all_addresses (mlp, addresses);
762 /* Load the matrix */
763 glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
769 * Solves the LP problem
771 * @param mlp the MLP Handle
772 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
775 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
778 struct GNUNET_TIME_Relative duration;
779 struct GNUNET_TIME_Absolute end;
780 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
783 * Presolver is required if the problem was modified and an existing
784 * valid basis is now invalid */
785 if (mlp->presolver_required == GNUNET_YES)
786 mlp->control_param_lp.presolve = GLP_ON;
788 mlp->control_param_lp.presolve = GLP_OFF;
790 /* Solve LP problem to have initial valid solution */
792 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
795 /* The LP problem instance has been successfully solved. */
797 else if (res == GLP_EITLIM)
799 /* simplex iteration limit has been exceeded. */
800 // TODO Increase iteration limit?
802 else if (res == GLP_ETMLIM)
804 /* Time limit has been exceeded. */
805 // TODO Increase time limit?
809 /* Problem was ill-defined, retry with presolver */
810 if (mlp->presolver_required == GNUNET_NO)
812 mlp->presolver_required = GNUNET_YES;
817 /* Problem was ill-defined, no way to handle that */
818 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
820 "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
821 return GNUNET_SYSERR;
825 end = GNUNET_TIME_absolute_get ();
826 duration = GNUNET_TIME_absolute_get_difference (start, end);
828 mlp->lp_total_duration =+ duration.rel_value;
830 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
831 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
832 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
833 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
836 /* Analyze problem status */
837 res = glp_get_status (mlp->prob);
839 /* solution is optimal */
841 /* solution is feasible */
845 /* Problem was ill-defined, no way to handle that */
847 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
849 "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
850 return GNUNET_SYSERR;
854 /* solved sucessfully, no presolver required next time */
855 mlp->presolver_required = GNUNET_NO;
862 * Solves the MLP problem
864 * @param mlp the MLP Handle
865 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
868 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
871 struct GNUNET_TIME_Relative duration;
872 struct GNUNET_TIME_Absolute end;
873 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
875 /* solve MLP problem */
876 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
880 /* The MLP problem instance has been successfully solved. */
882 else if (res == GLP_EITLIM)
884 /* simplex iteration limit has been exceeded. */
885 // TODO Increase iteration limit?
887 else if (res == GLP_ETMLIM)
889 /* Time limit has been exceeded. */
890 // TODO Increase time limit?
894 /* Problem was ill-defined, no way to handle that */
895 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
897 "Solving MLP problem failed: %s\n", mlp_solve_to_string(res));
898 return GNUNET_SYSERR;
901 end = GNUNET_TIME_absolute_get ();
902 duration = GNUNET_TIME_absolute_get_difference (start, end);
904 mlp->mlp_total_duration =+ duration.rel_value;
906 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
907 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
908 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
909 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
911 /* Analyze problem status */
912 res = glp_mip_status(mlp->prob);
914 /* solution is optimal */
916 /* solution is feasible */
920 /* Problem was ill-defined, no way to handle that */
922 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
924 "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
925 return GNUNET_SYSERR;
932 int GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp);
935 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
937 struct GAS_MLP_Handle *mlp = cls;
939 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
941 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
945 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
947 if (mlp->addr_in_problem != 0)
948 GAS_mlp_solve_problem(mlp);
953 * Solves the MLP problem
955 * @param mlp the MLP Handle
956 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
959 GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp)
962 mlp->last_execution = GNUNET_TIME_absolute_get ();
964 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solving\n");
971 GNUNET_asprintf(&name, "problem_%i", i);
972 glp_write_lp (mlp->prob, 0, name);
976 res = mlp_solve_lp_problem (mlp);
979 GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
980 glp_print_sol (mlp->prob, name);
984 if (res != GNUNET_OK)
987 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
989 return GNUNET_SYSERR;
992 res = mlp_solve_mlp_problem (mlp);
995 GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
996 glp_print_mip (mlp->prob, name);
999 if (res != GNUNET_OK)
1002 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MLP Problem solving failed\n");
1004 return GNUNET_SYSERR;
1008 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved\n");
1011 /* Process result */
1013 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1015 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1016 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1018 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1023 * Init the MLP problem solving component
1025 * @param stats the GNUNET_STATISTICS handle
1026 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
1027 * @param max_iterations maximum time limit for the LP/MLP Solver
1028 * @return struct GAS_MLP_Handle * on success, NULL on fail
1030 struct GAS_MLP_Handle *
1031 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1032 const struct GNUNET_STATISTICS_Handle *stats,
1033 struct GNUNET_TIME_Relative max_duration,
1034 unsigned int max_iterations)
1036 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1041 long long unsigned int tmp;
1044 struct GNUNET_TIME_Relative i_exec;
1046 /* Init GLPK environment */
1047 GNUNET_assert (glp_init_env() == 0);
1049 /* Create initial MLP problem */
1050 mlp->prob = glp_create_prob();
1051 GNUNET_assert (mlp->prob != NULL);
1053 /* Get diversity coefficient from configuration */
1054 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1057 D = (double) tmp / 100;
1061 /* Get proportionality coefficient from configuration */
1062 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1065 R = (double) tmp / 100;
1069 /* Get utilization coefficient from configuration */
1070 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1073 U = (double) tmp / 100;
1077 /* Get quality metric coefficients from configuration */
1079 int i_distance = -1;
1080 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1082 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1084 /* initialize quality coefficients with default value 1.0 */
1088 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1090 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1094 if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1095 "COEFFICIENT_QUALITY_DELAY",
1098 mlp->co_Q[i_delay] = (double) tmp / 100;
1100 mlp->co_Q[i_delay] = 1.0;
1102 if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1103 "COEFFICIENT_QUALITY_DISTANCE",
1105 mlp->co_Q[i_distance] = (double) tmp / 100;
1107 mlp->co_Q[i_distance] = 1.0;
1109 /* Get minimum bandwidth per used address from configuration */
1110 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1117 /* Get minimum number of connections from configuration */
1118 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1125 /* Get minimum number of connections from configuration */
1126 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1127 "ATS_EXEC_INTERVAL",
1129 mlp->exec_interval = i_exec;
1131 mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1133 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1134 mlp->max_iterations = max_iterations;
1135 mlp->max_exec_duration = max_duration;
1136 mlp->auto_solve = GNUNET_YES;
1138 /* Redirect GLPK output to GNUnet logging */
1139 glp_error_hook((void *) mlp, &mlp_term_hook);
1141 /* Init LP solving parameters */
1142 glp_init_smcp(&mlp->control_param_lp);
1144 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1146 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1148 mlp->control_param_lp.it_lim = max_iterations;
1149 mlp->control_param_lp.tm_lim = max_duration.rel_value;
1151 /* Init MLP solving parameters */
1152 glp_init_iocp(&mlp->control_param_mlp);
1154 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1156 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1158 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1160 mlp->last_execution = GNUNET_TIME_absolute_get_forever();
1163 mlp->BIG_M = (double) UINT32_MAX;
1169 mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1176 * Updates a single address in the MLP problem
1178 * If the address did not exist before in the problem:
1179 * The MLP problem has to be recreated and the problem has to be resolved
1181 * Otherwise the addresses' values can be updated and the existing base can
1184 * @param mlp the MLP Handle
1185 * @param addresses the address hashmap
1186 * the address has to be already removed from the hashmap
1187 * @param address the address to update
1190 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1193 struct MLP_information *mlpi;
1195 GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
1197 /* We add a new address */
1198 if (address->mlp_information == NULL)
1204 if (new == GNUNET_YES)
1206 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1209 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1216 address->mlp_information = mlpi;
1217 mlp->addr_in_problem ++;
1219 /* Check for and add peer */
1220 struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1224 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n",
1225 GNUNET_i2s (&address->peer));
1227 peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1232 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1238 memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1239 GNUNET_assert(address->prev == NULL);
1240 GNUNET_assert(address->next == NULL);
1241 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1242 GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1248 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n",
1249 GNUNET_i2s (&address->peer));
1251 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1257 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n",
1258 GNUNET_i2s (&address->peer));
1260 mlpi = address->mlp_information;
1262 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1264 int index = mlp_lookup_ats(address, mlp->q[c]);
1265 if ((index != GNUNET_SYSERR) && (mlpi->c_q[c] != 0) && (mlpi->r_q[c] != 0))
1267 if (mlpi->q[c] == (double) address->ats[index].value)
1270 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating address for peer `%s' value `%s'from %f to %f\n",
1271 GNUNET_i2s (&address->peer),
1272 mlp_ats_to_string(mlp->q[c]),
1274 (double) address->ats[index].value);
1278 case GNUNET_ATS_QUALITY_NET_DELAY:
1279 mlpi->q[c] = (double) address->ats[index].value;
1281 case GNUNET_ATS_QUALITY_NET_DISTANCE:
1282 mlpi->q[c] = (double) address->ats[index].value;
1288 /* Get current number of columns */
1289 int cols = glp_get_num_cols(mlp->prob);
1290 int *ind = GNUNET_malloc (cols * sizeof (int));
1291 double *val = GNUNET_malloc (cols * sizeof (double));
1293 /* Get the matrix row of quality */
1294 cols = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
1297 /* Get the index if matrix row of quality */
1298 for (c2 = 1; c2 <= cols; c2++ )
1301 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Existing element column %i : %f\n",
1304 if ((mlpi->c_b == ind[c2]) && (val[c2] != mlpi->q[c]))
1306 /* Update the value */
1307 val[c2] = mlpi->q[c];
1309 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "New element column %i : %f\n",
1315 /* Get the index if matrix row of quality */
1316 glp_set_mat_row (mlp->prob, mlpi->r_q[c], cols, ind, val);
1325 if (new == GNUNET_YES)
1327 mlp_delete_problem (mlp);
1328 mlp_create_problem (mlp, addresses);
1329 mlp->presolver_required = GNUNET_YES;
1331 if (mlp->auto_solve == GNUNET_YES)
1332 GAS_mlp_solve_problem (mlp);
1336 * Deletes a single address in the MLP problem
1338 * The MLP problem has to be recreated and the problem has to be resolved
1340 * @param mlp the MLP Handle
1341 * @param addresses the address hashmap
1342 * the address has to be already removed from the hashmap
1343 * @param address the address to delete
1346 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1348 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1350 /* Free resources */
1351 if (address->mlp_information != NULL)
1353 GNUNET_free (address->mlp_information);
1354 address->mlp_information = NULL;
1356 mlp->addr_in_problem --;
1359 /* Remove from peer list */
1360 struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1361 GNUNET_assert (head != NULL);
1363 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1365 GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1366 if ((head->head == NULL) && (head->tail == NULL))
1368 /* No address for peer left, remove peer */
1370 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1372 GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1377 /* Update problem */
1378 mlp_delete_problem (mlp);
1379 if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1381 mlp_create_problem (mlp, addresses);
1384 mlp->presolver_required = GNUNET_YES;
1385 if (mlp->auto_solve == GNUNET_YES)
1386 GAS_mlp_solve_problem (mlp);
1391 * Changes the preferences for a peer in the MLP problem
1393 * @param mlp the MLP Handle
1394 * @param peer the peer
1395 * @param kind the kind to change the preference
1396 * @param float the score
1399 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
1400 const struct GNUNET_PeerIdentity *peer,
1401 enum GNUNET_ATS_PreferenceKind kind,
1404 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1406 struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1408 /* Here we have to do the matching */
1412 * Shutdown the MLP problem solving component
1413 * @param mlp the MLP handle
1416 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
1418 struct ATS_Peer * peer;
1419 struct ATS_Peer * tmp;
1421 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1423 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1424 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1427 /* clean up peer list */
1430 peer = mlp->peer_head;
1431 while (peer != NULL)
1433 GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1439 mlp_delete_problem (mlp);
1441 /* Clean up GLPK environment */
1448 /* end of gnunet-service-ats_addresses_mlp.c */