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
38 #define ENABLE_C8 GNUNET_YES
39 #define ENABLE_C9 GNUNET_YES
41 * Translate glpk solver error codes to text
42 * @param retcode return code
43 * @return string with result
46 mlp_solve_to_string (int retcode)
53 return "invalid basis";
56 return "singular matrix";
59 return "ill-conditioned matrix";
62 return "invalid bounds";
65 return "solver failed";
68 return "objective lower limit reached";
71 return "objective upper limit reached";
74 return "iteration limit exceeded";
77 return "time limit exceeded";
80 return "no primal feasible solution";
83 return "root LP optimum not provided";
86 return "search terminated by application";
89 return "relative mip gap tolerance reached";
92 return "no dual feasible solution";
95 return "no convergence";
98 return "numerical instability";
101 return "invalid data";
104 return "result out of range";
108 return "unknown error";
112 return "unknown error";
117 * Translate glpk status error codes to text
118 * @param retcode return code
119 * @return string with result
122 mlp_status_to_string (int retcode)
126 return "solution is undefined";
129 return "solution is feasible";
132 return "solution is infeasible";
135 return "no feasible solution exists";
138 return "solution is optimal";
141 return "solution is unbounded";
145 return "unknown error";
149 return "unknown error";
153 * Translate ATS properties to text
154 * Just intended for debugging
156 * @param ats_index the ATS index
157 * @return string with result
160 mlp_ats_to_string (int ats_index)
163 case GNUNET_ATS_ARRAY_TERMINATOR:
164 return "GNUNET_ATS_ARRAY_TERMINATOR";
166 case GNUNET_ATS_UTILIZATION_UP:
167 return "GNUNET_ATS_UTILIZATION_UP";
169 case GNUNET_ATS_UTILIZATION_DOWN:
170 return "GNUNET_ATS_UTILIZATION_DOWN";
172 case GNUNET_ATS_COST_LAN:
173 return "GNUNET_ATS_COST_LAN";
175 case GNUNET_ATS_COST_WAN:
176 return "GNUNET_ATS_COST_LAN";
178 case GNUNET_ATS_COST_WLAN:
179 return "GNUNET_ATS_COST_WLAN";
181 case GNUNET_ATS_NETWORK_TYPE:
182 return "GNUNET_ATS_NETWORK_TYPE";
184 case GNUNET_ATS_QUALITY_NET_DELAY:
185 return "GNUNET_ATS_QUALITY_NET_DELAY";
187 case GNUNET_ATS_QUALITY_NET_DISTANCE:
188 return "GNUNET_ATS_QUALITY_NET_DISTANCE";
195 return "unknown error";
199 * Find a peer in the DLL
201 * @param mlp the mlp handle
202 * @param peer the peer to find
203 * @return the peer struct
205 static struct ATS_Peer *
206 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
208 struct ATS_Peer *res = mlp->peer_head;
211 if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
219 * Intercept GLPK terminal output
220 * @param info the mlp handle
221 * @param s the string to print
222 * @return 0: glpk prints output on terminal, 0 != surpress output
225 mlp_term_hook (void *info, const char *s)
227 /* Not needed atm struct MLP_information *mlp = info; */
228 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
233 * Delete the MLP problem and free the constrain matrix
235 * @param mlp the MLP handle
238 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
242 if (mlp->prob != NULL)
243 glp_delete_prob(mlp->prob);
245 /* delete row index */
248 GNUNET_free (mlp->ia);
252 /* delete column index */
255 GNUNET_free (mlp->ja);
259 /* delete coefficients */
262 GNUNET_free (mlp->ar);
271 * Add constraints that are iterating over "forall addresses"
272 * and collects all existing peers for "forall peers" constraints
274 * @param cls GAS_MLP_Handle
275 * @param key Hashcode
276 * @param value ATS_Address
278 * @return GNUNET_OK to continue
281 create_constraint_it (void *cls, const GNUNET_HashCode * key, void *value)
283 struct GAS_MLP_Handle *mlp = cls;
284 struct ATS_Address *address = value;
285 struct MLP_information *mlpi;
286 unsigned int row_index;
289 GNUNET_assert (address->mlp_information != NULL);
290 mlpi = (struct MLP_information *) address->mlp_information;
292 /* c 1) bandwidth capping
293 * b_t + (-M) * n_t <= 0
295 row_index = glp_add_rows (mlp->prob, 1);
296 mlpi->r_c1 = row_index;
298 GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
299 glp_set_row_name (mlp->prob, row_index, name);
301 /* set row bounds: <= 0 */
302 glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
303 mlp->ia[mlp->ci] = row_index;
304 mlp->ja[mlp->ci] = mlpi->c_b;
305 mlp->ar[mlp->ci] = 1;
308 mlp->ia[mlp->ci] = row_index;
309 mlp->ja[mlp->ci] = mlpi->c_n;
310 mlp->ar[mlp->ci] = -mlp->BIG_M;
313 /* c 3) minimum bandwidth
314 * b_t + (-n_t * b_min) >= 0
317 row_index = glp_add_rows (mlp->prob, 1);
319 GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
320 glp_set_row_name (mlp->prob, row_index, name);
322 mlpi->r_c3 = row_index;
323 /* set row bounds: >= 0 */
324 glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
326 mlp->ia[mlp->ci] = row_index;
327 mlp->ja[mlp->ci] = mlpi->c_b;
328 mlp->ar[mlp->ci] = 1;
331 mlp->ia[mlp->ci] = row_index;
332 mlp->ja[mlp->ci] = mlpi->c_n;
333 mlp->ar[mlp->ci] = - (double) mlp->b_min;
336 /* c 4) minimum connections
337 * (1)*n_1 + ... + (1)*n_m >= n_min
339 mlp->ia[mlp->ci] = mlp->r_c4;
340 mlp->ja[mlp->ci] = mlpi->c_n;
341 mlp->ar[mlp->ci] = 1;
344 /* c 6) maximize diversity
345 * (1)*n_1 + ... + (1)*n_m - d == 0
347 mlp->ia[mlp->ci] = mlp->r_c6;
348 mlp->ja[mlp->ci] = mlpi->c_n;
349 mlp->ar[mlp->ci] = 1;
352 /* c 10) obey network specific quotas
353 * (1)*b_1 + ... + (1)*b_m <= quota_n
358 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
360 if (mlp->quota_index[c] == address->atsp_network_type)
362 cur_row = mlp->r_quota[c];
369 mlp->ia[mlp->ci] = cur_row;
370 mlp->ja[mlp->ci] = mlpi->c_b;
371 mlp->ar[mlp->ci] = 1;
383 * Find the required ATS information for an address
385 * @param addr the address
386 * @param ats_index the desired ATS index
388 * @return the index on success, otherwise GNUNET_SYSERR
392 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
394 struct GNUNET_ATS_Information * ats = addr->ats;
396 int found = GNUNET_NO;
397 for (c = 0; c < addr->ats_count; c++)
399 if (ats[c].type == ats_index)
405 if (found == GNUNET_YES)
408 return GNUNET_SYSERR;
412 * Adds the problem constraints for all addresses
413 * Required for problem recreation after address deletion
415 * @param mlp the mlp handle
416 * @param addresses all addresses
420 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
422 unsigned int n_addresses;
427 n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
429 /* Required indices in the constrain matrix
431 * feasibility constraints:
433 * c 1) bandwidth capping
434 * #rows: |n_addresses|
435 * #indices: 2 * |n_addresses|
437 * c 2) one active address per peer
439 * #indices: |n_addresses|
441 * c 3) minium bandwidth assigned
442 * #rows: |n_addresses|
443 * #indices: 2 * |n_addresses|
445 * c 4) minimum number of active connections
447 * #indices: |n_addresses|
449 * c 5) maximum ressource consumption
450 * #rows: |ressources|
451 * #indices: |n_addresses|
453 * c 10) obey network specific quota
454 * #rows: |network types
455 * #indices: |n_addresses|
457 * Sum for feasibility constraints:
458 * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1
459 * #indices: 7 * |n_addresses|
461 * optimality constraints:
465 * #indices: |n_addresses| + 1
468 * #rows: |quality properties|
469 * #indices: |n_addresses| + |quality properties|
473 * #indices: |n_addresses| + 1
477 * #indices: |n_addresses| + |peers|
480 /* last +1 caused by glpk index starting with one: [1..pi]*/
481 int pi = ((7 * n_addresses) + (5 * n_addresses + mlp->m_q + mlp->c_p + 2) + 1);
486 int *ia = GNUNET_malloc (pi * sizeof (int));
490 int *ja = GNUNET_malloc (pi * sizeof (int));
494 double *ar= GNUNET_malloc (pi * sizeof (double));
497 /* Adding constraint rows
498 * This constraints are kind of "for all addresses"
499 * Feasibility constraints:
501 * c 1) bandwidth capping
502 * c 3) minimum bandwidth
503 * c 4) minimum number of connections
504 * c 6) maximize diversity
505 * c 10) obey network specific quota
508 int min = mlp->n_min;
509 if (mlp->n_min > mlp->c_p)
512 mlp->r_c4 = glp_add_rows (mlp->prob, 1);
513 glp_set_row_name (mlp->prob, mlp->r_c4, "c4");
514 glp_set_row_bnds (mlp->prob, mlp->r_c4, GLP_LO, min, min);
516 /* Add row for c6) */
518 mlp->r_c6 = glp_add_rows (mlp->prob, 1);
519 /* Set type type to fix */
520 glp_set_row_bnds (mlp->prob, mlp->r_c6, GLP_FX, 0.0, 0.0);
522 ia[mlp->ci] = mlp->r_c6 ;
523 ja[mlp->ci] = mlp->c_d;
527 /* Add rows for c 10) */
528 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
530 mlp->r_quota[c] = glp_add_rows (mlp->prob, 1);
532 GNUNET_asprintf(&text, "quota_ats_%i", mlp->quota_index[c]);
533 glp_set_row_name (mlp->prob, mlp->r_quota[c], text);
535 /* Set bounds to 0 <= x <= quota_out */
536 glp_set_row_bnds (mlp->prob, mlp->r_quota[c], GLP_UP, 0.0, mlp->quota_out[c]);
539 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
541 /* Adding constraint rows
542 * This constraints are kind of "for all peers"
543 * Feasibility constraints:
545 * c 2) 1 address per peer
546 * sum (n_p1_1 + ... + n_p1_n) = 1
549 * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
552 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
555 /* Adding rows for c 8) */
556 mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p);
557 glp_set_row_name (mlp->prob, mlp->r_c8, "c8");
558 /* Set row bound == 0 */
559 glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0);
562 ia[mlp->ci] = mlp->r_c8;
563 ja[mlp->ci] = mlp->c_u;
567 struct ATS_Peer * peer = mlp->peer_head;
570 struct ATS_Address *addr = peer->head;
571 struct MLP_information *mlpi = NULL;
573 /* Adding rows for c 2) */
574 peer->r_c2 = glp_add_rows (mlp->prob, 1);
575 GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
576 glp_set_row_name (mlp->prob, peer->r_c2, name);
578 /* Set row bound == 1 */
579 glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
581 /* Adding rows for c 9) */
583 peer->r_c9 = glp_add_rows (mlp->prob, 1);
584 GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
585 glp_set_row_name (mlp->prob, peer->r_c9, name);
587 /* Set row bound == 0 */
588 glp_set_row_bnds (mlp->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
591 ia[mlp->ci] = peer->r_c9;
592 ja[mlp->ci] = mlp->c_r;
599 mlpi = (struct MLP_information *) addr->mlp_information;
601 /* coefficient for c 2) */
603 ia[mlp->ci] = peer->r_c2;
604 ja[mlp->ci] = mlpi->c_n;
608 /* coefficient for c 8) */
609 ia[mlp->ci] = mlp->r_c8;
610 ja[mlp->ci] = mlpi->c_b;
611 ar[mlp->ci] = peer->f;
615 /* coefficient for c 9) */
616 ia[mlp->ci] = peer->r_c9;
617 ja[mlp->ci] = mlpi->c_b;
627 /* c 7) For all quality metrics */
630 for (c = 0; c < mlp->m_q; c++)
633 struct ATS_Address *ta;
634 struct MLP_information * mlpi;
637 /* Adding rows for c 7) */
638 mlp->r_q[c] = glp_add_rows (mlp->prob, 1);
639 GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->q[c]));
640 glp_set_row_name (mlp->prob, mlp->r_q[c], name);
642 /* Set row bound == 0 */
643 glp_set_row_bnds (mlp->prob, mlp->r_q[c], GLP_LO, 0.0, 0.0);
645 ia[mlp->ci] = mlp->r_q[c];
646 ja[mlp->ci] = mlp->c_q[c];
650 for (tp = mlp->peer_head; tp != NULL; tp = tp->next)
651 for (ta = tp->head; ta != NULL; ta = ta->next)
653 mlpi = ta->mlp_information;
654 value = mlpi->q_averaged[c];
656 mlpi->r_q[c] = mlp->r_q[c];
658 ia[mlp->ci] = mlp->r_q[c];
659 ja[mlp->ci] = mlpi->c_b;
660 ar[mlp->ci] = tp->f * value;
668 * Add columns for all addresses
670 * @param cls GAS_MLP_Handle
671 * @param key Hashcode
672 * @param value ATS_Address
674 * @return GNUNET_OK to continue
677 create_columns_it (void *cls, const GNUNET_HashCode * key, void *value)
679 struct GAS_MLP_Handle *mlp = cls;
680 struct ATS_Address *address = value;
681 struct MLP_information *mlpi;
685 GNUNET_assert (address->mlp_information != NULL);
686 mlpi = address->mlp_information;
688 /* Add bandwidth column */
689 col = glp_add_cols (mlp->prob, 2);
694 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
695 glp_set_col_name (mlp->prob, mlpi->c_b , name);
697 /* Lower bound == 0 */
698 glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
699 /* Continuous value*/
700 glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
701 /* Objective function coefficient == 0 */
702 glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
705 /* Add usage column */
706 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
707 glp_set_col_name (mlp->prob, mlpi->c_n, name);
709 /* Limit value : 0 <= value <= 1 */
710 glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
712 glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
713 /* Objective function coefficient == 0 */
714 glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
722 * Create the MLP problem
724 * @param mlp the MLP handle
725 * @param addresses the hashmap containing all adresses
726 * @return GNUNET_OK or GNUNET_SYSERR
729 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
736 GNUNET_assert (mlp->prob == NULL);
738 /* create the glpk problem */
739 mlp->prob = glp_create_prob ();
741 /* Set a problem name */
742 glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
744 /* Set optimization direction to maximize */
745 glp_set_obj_dir (mlp->prob, GLP_MAX);
747 /* Adding invariant columns */
749 /* Diversity d column */
751 col = glp_add_cols (mlp->prob, 1);
754 glp_set_col_name (mlp->prob, col, "d");
755 /* Column objective function coefficient */
756 glp_set_obj_coef (mlp->prob, col, mlp->co_D);
757 /* Column lower bound = 0.0 */
758 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
760 /* Utilization u column */
762 col = glp_add_cols (mlp->prob, 1);
765 glp_set_col_name (mlp->prob, col, "u");
766 /* Column objective function coefficient */
767 glp_set_obj_coef (mlp->prob, col, mlp->co_U);
768 /* Column lower bound = 0.0 */
769 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
772 /* Relativity r column */
773 col = glp_add_cols (mlp->prob, 1);
776 glp_set_col_name (mlp->prob, col, "r");
777 /* Column objective function coefficient */
778 glp_set_obj_coef (mlp->prob, col, mlp->co_R);
779 /* Column lower bound = 0.0 */
780 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
783 /* Quality metric columns */
784 col = glp_add_cols(mlp->prob, mlp->m_q);
785 for (c = 0; c < mlp->m_q; c++)
787 mlp->c_q[c] = col + c;
788 GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
789 glp_set_col_name (mlp->prob, col + c, name);
790 /* Column lower bound = 0.0 */
791 glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
793 /* Coefficient == Qm */
794 glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
797 /* Add columns for addresses */
798 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
800 /* Add constraints */
801 mlp_add_constraints_all_addresses (mlp, addresses);
803 /* Load the matrix */
804 glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
812 struct GNUNET_TIME_Relative lp_duration;
813 struct GNUNET_TIME_Relative mlp_duration;
818 * Solves the LP problem
820 * @param mlp the MLP Handle
821 * @param s_ctx context to return results
822 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
825 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp, struct SolveContext *s_ctx)
828 struct GNUNET_TIME_Relative duration;
829 struct GNUNET_TIME_Absolute end;
830 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
833 * Presolver is required if the problem was modified and an existing
834 * valid basis is now invalid */
835 if (mlp->presolver_required == GNUNET_YES)
836 mlp->control_param_lp.presolve = GLP_ON;
838 mlp->control_param_lp.presolve = GLP_OFF;
840 /* Solve LP problem to have initial valid solution */
842 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
845 /* The LP problem instance has been successfully solved. */
847 else if (res == GLP_EITLIM)
849 /* simplex iteration limit has been exceeded. */
850 // TODO Increase iteration limit?
852 else if (res == GLP_ETMLIM)
854 /* Time limit has been exceeded. */
855 // TODO Increase time limit?
859 /* Problem was ill-defined, retry with presolver */
860 if (mlp->presolver_required == GNUNET_NO)
862 mlp->presolver_required = GNUNET_YES;
867 /* Problem was ill-defined, no way to handle that */
868 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
870 "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
871 return GNUNET_SYSERR;
875 end = GNUNET_TIME_absolute_get ();
876 duration = GNUNET_TIME_absolute_get_difference (start, end);
878 mlp->lp_total_duration =+ duration.rel_value;
879 s_ctx->lp_duration = duration;
880 GNUNET_assert (mlp->stats!= NULL);
881 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
882 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time (ms)", duration.rel_value, GNUNET_NO);
883 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average (ms)",
884 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
886 GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
888 "%llu %llu \n", duration.rel_value, mlp->lp_total_duration / mlp->lp_solved);
889 /* Analyze problem status */
890 res = glp_get_status (mlp->prob);
892 /* solution is optimal */
894 /* solution is feasible */
898 /* Problem was ill-defined, no way to handle that */
900 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
902 "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
903 return GNUNET_SYSERR;
907 /* solved sucessfully, no presolver required next time */
908 mlp->presolver_required = GNUNET_NO;
915 * Solves the MLP problem
917 * @param mlp the MLP Handle
918 * @param s_ctx context to return results
919 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
922 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp, struct SolveContext *s_ctx)
925 struct GNUNET_TIME_Relative duration;
926 struct GNUNET_TIME_Absolute end;
927 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
929 /* solve MLP problem */
930 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
934 /* The MLP problem instance has been successfully solved. */
936 else if (res == GLP_EITLIM)
938 /* simplex iteration limit has been exceeded. */
939 // TODO Increase iteration limit?
941 else if (res == GLP_ETMLIM)
943 /* Time limit has been exceeded. */
944 // TODO Increase time limit?
948 /* Problem was ill-defined, no way to handle that */
949 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
951 "Solving MLP problem failed: %s\n", mlp_solve_to_string(res));
952 return GNUNET_SYSERR;
955 end = GNUNET_TIME_absolute_get ();
956 duration = GNUNET_TIME_absolute_get_difference (start, end);
958 mlp->mlp_total_duration =+ duration.rel_value;
959 s_ctx->mlp_duration = duration;
961 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
962 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time (ms)", duration.rel_value, GNUNET_NO);
963 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average (ms)",
964 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
966 /* Analyze problem status */
967 res = glp_mip_status(mlp->prob);
969 /* solution is optimal */
971 /* solution is feasible */
975 /* Problem was ill-defined, no way to handle that */
977 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
979 "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
980 return GNUNET_SYSERR;
987 int GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp);
990 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
992 struct GAS_MLP_Handle *mlp = cls;
994 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
996 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
1000 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
1002 if (mlp->addr_in_problem != 0)
1003 GAS_mlp_solve_problem(mlp);
1007 * Solves the MLP problem
1009 * @param mlp the MLP Handle
1010 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
1013 GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp)
1016 struct SolveContext s_ctx;
1017 mlp->last_execution = GNUNET_TIME_absolute_get ();
1019 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n");
1024 GNUNET_asprintf(&name, "problem_%i", i);
1025 glp_write_lp (mlp->prob, 0, name);
1029 res = mlp_solve_lp_problem (mlp, &s_ctx);
1030 if (res != GNUNET_OK)
1032 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n");
1033 return GNUNET_SYSERR;
1036 GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
1037 glp_print_sol (mlp->prob, name);
1042 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n");
1043 res = mlp_solve_mlp_problem (mlp, &s_ctx);
1044 if (res != GNUNET_OK)
1046 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n");
1047 return GNUNET_SYSERR;
1050 GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
1051 glp_print_mip (mlp->prob, name);
1055 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n",
1056 (GNUNET_OK == res) ? "successfully" : "failed", s_ctx.lp_duration, s_ctx.mlp_duration);
1057 /* Process result */
1058 struct ATS_Peer *p = NULL;
1059 struct ATS_Address *a = NULL;
1060 struct MLP_information *mlpi = NULL;
1062 for (p = mlp->peer_head; p != NULL; p = p->next)
1064 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id));
1065 for (a = p->head; a != NULL; a = a->next)
1070 mlpi = a->mlp_information;
1072 b = glp_mip_col_val(mlp->prob, mlpi->c_b);
1075 n = glp_mip_col_val(mlp->prob, mlpi->c_n);
1077 mlpi->n = GNUNET_YES;
1079 mlpi->n = GNUNET_NO;
1081 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n",
1082 (n == 1.0) ? "[x]" : "[ ]", b);
1086 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1088 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1089 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1091 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1096 * Init the MLP problem solving component
1098 * @param cfg the GNUNET_CONFIGURATION_Handle handle
1099 * @param stats the GNUNET_STATISTICS handle
1100 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
1101 * @param max_iterations maximum time limit for the LP/MLP Solver
1102 * @return struct GAS_MLP_Handle * on success, NULL on fail
1104 struct GAS_MLP_Handle *
1105 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1106 const struct GNUNET_STATISTICS_Handle *stats,
1107 struct GNUNET_TIME_Relative max_duration,
1108 unsigned int max_iterations)
1110 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1115 long long unsigned int tmp;
1118 struct GNUNET_TIME_Relative i_exec;
1120 char * quota_out_str;
1121 char * quota_in_str;
1123 /* Init GLPK environment */
1125 if (0 != (res = glp_init_env()))
1127 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK %u\n", res);
1132 /* Create initial MLP problem */
1133 mlp->prob = glp_create_prob();
1134 GNUNET_assert (mlp->prob != NULL);
1136 mlp->BIG_M = (double) BIG_M_VALUE;
1138 /* Get diversity coefficient from configuration */
1139 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1142 D = (double) tmp / 100;
1146 /* Get proportionality coefficient from configuration */
1147 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1150 R = (double) tmp / 100;
1154 /* Get utilization coefficient from configuration */
1155 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1158 U = (double) tmp / 100;
1162 /* Get quality metric coefficients from configuration */
1164 int i_distance = -1;
1165 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1166 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1168 /* initialize quality coefficients with default value 1.0 */
1172 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1174 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1178 if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1179 "COEFFICIENT_QUALITY_DELAY",
1182 mlp->co_Q[i_delay] = (double) tmp / 100;
1184 mlp->co_Q[i_delay] = 1.0;
1186 if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1187 "COEFFICIENT_QUALITY_DISTANCE",
1189 mlp->co_Q[i_distance] = (double) tmp / 100;
1191 mlp->co_Q[i_distance] = 1.0;
1193 /* Get minimum bandwidth per used address from configuration */
1194 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1200 b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1203 /* Get minimum number of connections from configuration */
1204 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1211 /* Init network quotas */
1212 int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
1213 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1215 mlp->quota_index[c] = quotas[c];
1216 static char * entry_in = NULL;
1217 static char * entry_out = NULL;
1218 unsigned long long quota_in = 0;
1219 unsigned long long quota_out = 0;
1221 switch (quotas[c]) {
1222 case GNUNET_ATS_NET_UNSPECIFIED:
1223 entry_out = "UNSPECIFIED_QUOTA_OUT";
1224 entry_in = "UNSPECIFIED_QUOTA_IN";
1226 case GNUNET_ATS_NET_LOOPBACK:
1227 entry_out = "LOOPBACK_QUOTA_OUT";
1228 entry_in = "LOOPBACK_QUOTA_IN";
1230 case GNUNET_ATS_NET_LAN:
1231 entry_out = "LAN_QUOTA_OUT";
1232 entry_in = "LAN_QUOTA_IN";
1234 case GNUNET_ATS_NET_WAN:
1235 entry_out = "WAN_QUOTA_OUT";
1236 entry_in = "WAN_QUOTA_IN";
1238 case GNUNET_ATS_NET_WLAN:
1239 entry_out = "WLAN_QUOTA_OUT";
1240 entry_in = "WLAN_QUOTA_IN";
1246 if ((entry_in == NULL) || (entry_out == NULL))
1249 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_out, "a_out_str))
1251 if (0 == strcmp(quota_out_str, BIG_M_STRING) ||
1252 (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_out_str, "a_out)))
1253 quota_out = mlp->BIG_M;
1255 GNUNET_free (quota_out_str);
1256 quota_out_str = NULL;
1258 else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1260 quota_out = mlp->BIG_M;
1264 quota_out = mlp->BIG_M;
1267 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_in, "a_in_str))
1269 if (0 == strcmp(quota_in_str, BIG_M_STRING) ||
1270 (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_in_str, "a_in)))
1271 quota_in = mlp->BIG_M;
1273 GNUNET_free (quota_in_str);
1274 quota_in_str = NULL;
1276 else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1278 quota_in = mlp->BIG_M;
1282 quota_in = mlp->BIG_M;
1285 /* Check if defined quota could make problem unsolvable */
1286 if (((n_min * b_min) > quota_out) && (GNUNET_ATS_NET_UNSPECIFIED != quotas[c]))
1288 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Inconsistent quota configuration value `%s': " \
1289 "outbound quota (%u Bps) too small for combination of minimum connections and minimum bandwidth per peer (%u * %u Bps = %u)\n", entry_out, quota_out, n_min, b_min, n_min * b_min);
1296 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found `%s' quota %llu and `%s' quota %llu\n",
1297 entry_out, quota_out, entry_in, quota_in);
1298 GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_out, quota_out, GNUNET_NO);
1299 GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_in, quota_in, GNUNET_NO);
1300 mlp->quota_out[c] = quota_out;
1301 mlp->quota_in[c] = quota_in;
1304 /* Get minimum number of connections from configuration */
1305 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1306 "ATS_EXEC_INTERVAL",
1308 mlp->exec_interval = i_exec;
1310 mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1312 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1313 mlp->max_iterations = max_iterations;
1314 mlp->max_exec_duration = max_duration;
1315 mlp->auto_solve = GNUNET_YES;
1317 /* Redirect GLPK output to GNUnet logging */
1318 glp_error_hook((void *) mlp, &mlp_term_hook);
1320 /* Init LP solving parameters */
1321 glp_init_smcp(&mlp->control_param_lp);
1323 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1325 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1328 mlp->control_param_lp.it_lim = max_iterations;
1329 mlp->control_param_lp.tm_lim = max_duration.rel_value;
1331 /* Init MLP solving parameters */
1332 glp_init_iocp(&mlp->control_param_mlp);
1334 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1336 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1338 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1340 mlp->last_execution = GNUNET_TIME_absolute_get_forever();
1347 mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1353 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
1355 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
1356 GNUNET_i2s (&address->peer));
1358 GNUNET_assert (NULL != address);
1359 GNUNET_assert (NULL != address->mlp_information);
1360 GNUNET_assert (NULL != address->ats);
1362 struct MLP_information *mlpi = address->mlp_information;
1363 struct GNUNET_ATS_Information *ats = address->ats;
1364 GNUNET_assert (mlpi != NULL);
1367 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1369 int index = mlp_lookup_ats(address, mlp->q[c]);
1371 if (index == GNUNET_SYSERR)
1374 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
1375 GNUNET_i2s (&address->peer),
1376 mlp_ats_to_string(mlp->q[c]),
1377 (double) ats[index].value);
1379 int i = mlpi->q_avg_i[c];
1380 double * qp = mlpi->q[c];
1381 qp[i] = (double) ats[index].value;
1384 for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
1386 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
1387 GNUNET_i2s (&address->peer),
1388 mlp_ats_to_string(mlp->q[c]),
1393 if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
1394 mlpi->q_avg_i[c] ++;
1396 mlpi->q_avg_i[c] = 0;
1404 case GNUNET_ATS_QUALITY_NET_DELAY:
1406 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1408 if (mlpi->q[c][c2] != -1)
1410 double * t2 = mlpi->q[c] ;
1416 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1417 mlpi->q_averaged[c] = (double) c3 / avg;
1419 mlpi->q_averaged[c] = 0.0;
1421 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1422 GNUNET_i2s (&address->peer),
1423 mlp_ats_to_string(mlp->q[c]),
1426 mlpi->q_averaged[c]);
1429 case GNUNET_ATS_QUALITY_NET_DISTANCE:
1431 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1433 if (mlpi->q[c][c2] != -1)
1435 double * t2 = mlpi->q[c] ;
1441 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1442 mlpi->q_averaged[c] = (double) c3 / avg;
1444 mlpi->q_averaged[c] = 0.0;
1446 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1447 GNUNET_i2s (&address->peer),
1448 mlp_ats_to_string(mlp->q[c]),
1451 mlpi->q_averaged[c]);
1458 if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
1461 /* Get current number of columns */
1462 int found = GNUNET_NO;
1463 int cols = glp_get_num_cols(mlp->prob);
1464 int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
1465 double *val = GNUNET_malloc (cols * sizeof (double) + 1);
1467 /* Get the matrix row of quality */
1468 int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
1469 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
1471 /* Get the index if matrix row of quality */
1472 for (c4 = 1; c4 <= length; c4++ )
1474 if (mlpi->c_b == ind[c4])
1476 /* Update the value */
1477 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
1478 mlp_ats_to_string(mlp->q[c]),
1479 glp_get_col_name (mlp->prob, ind[c4]),
1480 glp_get_row_name (mlp->prob, mlp->r_q[c]),
1482 mlpi->q_averaged[c]);
1483 val[c4] = mlpi->q_averaged[c];
1489 if (found == GNUNET_NO)
1492 ind[length+1] = mlpi->c_b;
1493 val[length+1] = mlpi->q_averaged[c];
1494 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%i ind[%i] val[%i]: %i %f\n", length+1, length+1, length+1, mlpi->c_b, mlpi->q_averaged[c]);
1495 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
1499 /* Get the index if matrix row of quality */
1500 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
1510 * Updates a single address in the MLP problem
1512 * If the address did not exist before in the problem:
1513 * The MLP problem has to be recreated and the problem has to be resolved
1515 * Otherwise the addresses' values can be updated and the existing base can
1518 * @param mlp the MLP Handle
1519 * @param addresses the address hashmap
1520 * the address has to be already removed from the hashmap
1521 * @param address the address to update
1524 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1527 struct MLP_information *mlpi;
1529 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1531 /* We add a new address */
1532 if (address->mlp_information == NULL)
1538 if (new == GNUNET_YES)
1540 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1543 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1547 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1548 mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1549 mlpi->q_avg_i[c] = 0;
1550 mlpi->q_averaged[c] = 0.0;
1553 address->mlp_information = mlpi;
1554 mlp->addr_in_problem ++;
1555 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1557 /* Check for and add peer */
1558 struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1562 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1563 GNUNET_i2s (&address->peer));
1565 peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1570 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1576 memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1577 GNUNET_assert(address->prev == NULL);
1578 GNUNET_assert(address->next == NULL);
1579 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1580 GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1582 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1587 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1588 GNUNET_i2s (&address->peer));
1590 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1592 update_quality (mlp, address);
1596 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1597 GNUNET_i2s (&address->peer));
1599 update_quality (mlp, address);
1603 if (new == GNUNET_YES)
1605 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1607 mlp_delete_problem (mlp);
1608 mlp_create_problem (mlp, addresses);
1609 mlp->presolver_required = GNUNET_YES;
1611 if (mlp->auto_solve == GNUNET_YES)
1612 GAS_mlp_solve_problem (mlp);
1616 * Deletes a single address in the MLP problem
1618 * The MLP problem has to be recreated and the problem has to be resolved
1620 * @param mlp the MLP Handle
1621 * @param addresses the address hashmap
1622 * the address has to be already removed from the hashmap
1623 * @param address the address to delete
1626 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1628 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1630 /* Free resources */
1631 if (address->mlp_information != NULL)
1633 GNUNET_free (address->mlp_information);
1634 address->mlp_information = NULL;
1636 mlp->addr_in_problem --;
1637 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1640 /* Remove from peer list */
1641 struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1642 GNUNET_assert (head != NULL);
1644 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1646 GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1647 if ((head->head == NULL) && (head->tail == NULL))
1649 /* No address for peer left, remove peer */
1651 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1653 GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1656 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1659 /* Update problem */
1660 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1662 mlp_delete_problem (mlp);
1663 if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1665 mlp_create_problem (mlp, addresses);
1668 mlp->presolver_required = GNUNET_YES;
1669 if (mlp->auto_solve == GNUNET_YES)
1670 GAS_mlp_solve_problem (mlp);
1675 mlp_get_preferred_address_it (void *cls, const GNUNET_HashCode * key, void *value)
1678 struct ATS_PreferedAddress *aa = (struct ATS_PreferedAddress *) cls;
1679 struct ATS_Address *addr = value;
1680 struct MLP_information *mlpi = addr->mlp_information;
1683 if (mlpi->n == GNUNET_YES)
1686 if (mlpi->b > (double) UINT32_MAX)
1687 aa->bandwidth_out = UINT32_MAX;
1689 aa->bandwidth_out = (uint32_t) mlpi->b;
1690 aa->bandwidth_in = 0;
1698 * Get the preferred address for a specific peer
1700 * @param mlp the MLP Handle
1701 * @param addresses address hashmap
1702 * @param peer the peer
1703 * @return suggested address
1705 struct ATS_PreferedAddress *
1706 GAS_mlp_get_preferred_address (struct GAS_MLP_Handle *mlp,
1707 struct GNUNET_CONTAINER_MultiHashMap * addresses,
1708 const struct GNUNET_PeerIdentity *peer)
1710 struct ATS_PreferedAddress * aa = GNUNET_malloc (sizeof (struct ATS_PreferedAddress));
1712 aa->bandwidth_in = 0;
1713 aa->bandwidth_out = 0;
1714 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", GNUNET_i2s (peer));
1715 GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, mlp_get_preferred_address_it, aa);
1721 * Changes the preferences for a peer in the MLP problem
1723 * @param mlp the MLP Handle
1724 * @param peer the peer
1725 * @param kind the kind to change the preference
1726 * @param score the score
1729 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
1730 const struct GNUNET_PeerIdentity *peer,
1731 enum GNUNET_ATS_PreferenceKind kind,
1734 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1736 struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1738 /* Here we have to do the matching */
1742 * Shutdown the MLP problem solving component
1743 * @param mlp the MLP handle
1746 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
1748 struct ATS_Peer * peer;
1749 struct ATS_Address *addr;
1751 GNUNET_assert (mlp != NULL);
1753 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1755 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1756 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1759 /* clean up peer list */
1760 peer = mlp->peer_head;
1761 while (peer != NULL)
1763 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1764 GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1765 for (addr = peer->head; NULL != addr; addr = peer->head)
1767 GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1768 GNUNET_free (addr->mlp_information);
1769 addr->mlp_information = NULL;
1772 peer = mlp->peer_head;
1774 mlp_delete_problem (mlp);
1776 /* Clean up GLPK environment */
1783 /* end of gnunet-service-ats_addresses_mlp.c */