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 LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
36 #define WRITE_MLP GNUNET_NO
37 #define DEBUG_ATS GNUNET_NO
38 #define VERBOSE_GLPK GNUNET_NO
40 #define ENABLE_C8 GNUNET_YES
41 #define ENABLE_C9 GNUNET_YES
43 * Translate glpk solver error codes to text
44 * @param retcode return code
45 * @return string with result
48 mlp_solve_to_string (int retcode)
54 return "invalid basis";
56 return "singular matrix";
58 return "ill-conditioned matrix";
60 return "invalid bounds";
62 return "solver failed";
64 return "objective lower limit reached";
66 return "objective upper limit reached";
68 return "iteration limit exceeded";
70 return "time limit exceeded";
72 return "no primal feasible solution";
74 return "root LP optimum not provided";
76 return "search terminated by application";
78 return "relative mip gap tolerance reached";
80 return "no dual feasible solution";
82 return "no convergence";
84 return "numerical instability";
86 return "invalid data";
88 return "result out of range";
91 return "unknown error";
97 * Translate glpk status error codes to text
98 * @param retcode return code
99 * @return string with result
102 mlp_status_to_string (int retcode)
106 return "solution is undefined";
108 return "solution is feasible";
110 return "solution is infeasible";
112 return "no feasible solution exists";
114 return "solution is optimal";
116 return "solution is unbounded";
119 return "unknown error";
124 * Translate ATS properties to text
125 * Just intended for debugging
127 * @param ats_index the ATS index
128 * @return string with result
131 mlp_ats_to_string (int ats_index)
134 case GNUNET_ATS_ARRAY_TERMINATOR:
135 return "GNUNET_ATS_ARRAY_TERMINATOR";
136 case GNUNET_ATS_UTILIZATION_UP:
137 return "GNUNET_ATS_UTILIZATION_UP";
138 case GNUNET_ATS_UTILIZATION_DOWN:
139 return "GNUNET_ATS_UTILIZATION_DOWN";
140 case GNUNET_ATS_COST_LAN:
141 return "GNUNET_ATS_COST_LAN";
142 case GNUNET_ATS_COST_WAN:
143 return "GNUNET_ATS_COST_LAN";
144 case GNUNET_ATS_COST_WLAN:
145 return "GNUNET_ATS_COST_WLAN";
146 case GNUNET_ATS_NETWORK_TYPE:
147 return "GNUNET_ATS_NETWORK_TYPE";
148 case GNUNET_ATS_QUALITY_NET_DELAY:
149 return "GNUNET_ATS_QUALITY_NET_DELAY";
150 case GNUNET_ATS_QUALITY_NET_DISTANCE:
151 return "GNUNET_ATS_QUALITY_NET_DISTANCE";
159 * Find a peer in the DLL
161 * @param mlp the mlp handle
162 * @param peer the peer to find
163 * @return the peer struct
165 static struct ATS_Peer *
166 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
168 struct ATS_Peer *res = mlp->peer_head;
171 if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
179 * Intercept GLPK terminal output
180 * @param info the mlp handle
181 * @param s the string to print
182 * @return 0: glpk prints output on terminal, 0 != surpress output
185 mlp_term_hook (void *info, const char *s)
187 /* Not needed atm struct MLP_information *mlp = info; */
188 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
193 * Delete the MLP problem and free the constrain matrix
195 * @param mlp the MLP handle
198 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
202 if (mlp->prob != NULL)
203 glp_delete_prob(mlp->prob);
205 /* delete row index */
208 GNUNET_free (mlp->ia);
212 /* delete column index */
215 GNUNET_free (mlp->ja);
219 /* delete coefficients */
222 GNUNET_free (mlp->ar);
231 * Add constraints that are iterating over "forall addresses"
232 * and collects all existing peers for "forall peers" constraints
234 * @param cls GAS_MLP_Handle
235 * @param key Hashcode
236 * @param value ATS_Address
238 * @return GNUNET_OK to continue
241 create_constraint_it (void *cls, const struct GNUNET_HashCode * key, void *value)
243 struct GAS_MLP_Handle *mlp = cls;
244 struct ATS_Address *address = value;
245 struct MLP_information *mlpi;
246 unsigned int row_index;
249 GNUNET_assert (address->solver_information != NULL);
250 mlpi = (struct MLP_information *) address->solver_information;
252 /* c 1) bandwidth capping
253 * b_t + (-M) * n_t <= 0
255 row_index = glp_add_rows (mlp->prob, 1);
256 mlpi->r_c1 = row_index;
258 GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
259 glp_set_row_name (mlp->prob, row_index, name);
261 /* set row bounds: <= 0 */
262 glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
263 mlp->ia[mlp->ci] = row_index;
264 mlp->ja[mlp->ci] = mlpi->c_b;
265 mlp->ar[mlp->ci] = 1;
268 mlp->ia[mlp->ci] = row_index;
269 mlp->ja[mlp->ci] = mlpi->c_n;
270 mlp->ar[mlp->ci] = -mlp->BIG_M;
273 /* c 3) minimum bandwidth
274 * b_t + (-n_t * b_min) >= 0
277 row_index = glp_add_rows (mlp->prob, 1);
279 GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
280 glp_set_row_name (mlp->prob, row_index, name);
282 mlpi->r_c3 = row_index;
283 /* set row bounds: >= 0 */
284 glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
286 mlp->ia[mlp->ci] = row_index;
287 mlp->ja[mlp->ci] = mlpi->c_b;
288 mlp->ar[mlp->ci] = 1;
291 mlp->ia[mlp->ci] = row_index;
292 mlp->ja[mlp->ci] = mlpi->c_n;
293 mlp->ar[mlp->ci] = - (double) mlp->b_min;
296 /* c 4) minimum connections
297 * (1)*n_1 + ... + (1)*n_m >= n_min
299 mlp->ia[mlp->ci] = mlp->r_c4;
300 mlp->ja[mlp->ci] = mlpi->c_n;
301 mlp->ar[mlp->ci] = 1;
304 /* c 6) maximize diversity
305 * (1)*n_1 + ... + (1)*n_m - d == 0
307 mlp->ia[mlp->ci] = mlp->r_c6;
308 mlp->ja[mlp->ci] = mlpi->c_n;
309 mlp->ar[mlp->ci] = 1;
312 /* c 10) obey network specific quotas
313 * (1)*b_1 + ... + (1)*b_m <= quota_n
318 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
320 if (mlp->quota_index[c] == address->atsp_network_type)
322 cur_row = mlp->r_quota[c];
329 mlp->ia[mlp->ci] = cur_row;
330 mlp->ja[mlp->ci] = mlpi->c_b;
331 mlp->ar[mlp->ci] = 1;
344 * Find the required ATS information for an address
346 * @param addr the address
347 * @param ats_index the desired ATS index
349 * @return the index on success, otherwise GNUNET_SYSERR
352 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
354 struct GNUNET_ATS_Information * ats = addr->ats;
356 int found = GNUNET_NO;
357 for (c = 0; c < addr->ats_count; c++)
359 if (ats[c].type == ats_index)
365 if (found == GNUNET_YES)
368 return GNUNET_SYSERR;
373 * Adds the problem constraints for all addresses
374 * Required for problem recreation after address deletion
376 * @param mlp the mlp handle
377 * @param addresses all addresses
381 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
383 unsigned int n_addresses;
388 n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
390 /* Required indices in the constrain matrix
392 * feasibility constraints:
394 * c 1) bandwidth capping
395 * #rows: |n_addresses|
396 * #indices: 2 * |n_addresses|
398 * c 2) one active address per peer
400 * #indices: |n_addresses|
402 * c 3) minium bandwidth assigned
403 * #rows: |n_addresses|
404 * #indices: 2 * |n_addresses|
406 * c 4) minimum number of active connections
408 * #indices: |n_addresses|
410 * c 5) maximum ressource consumption
411 * #rows: |ressources|
412 * #indices: |n_addresses|
414 * c 10) obey network specific quota
415 * #rows: |network types
416 * #indices: |n_addresses|
418 * Sum for feasibility constraints:
419 * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1
420 * #indices: 7 * |n_addresses|
422 * optimality constraints:
426 * #indices: |n_addresses| + 1
429 * #rows: |quality properties|
430 * #indices: |n_addresses| + |quality properties|
434 * #indices: |n_addresses| + 1
438 * #indices: |n_addresses| + |peers|
441 /* last +1 caused by glpk index starting with one: [1..pi]*/
442 int pi = ((7 * n_addresses) + (5 * n_addresses + mlp->m_q + mlp->c_p + 2) + 1);
447 int *ia = GNUNET_malloc (pi * sizeof (int));
451 int *ja = GNUNET_malloc (pi * sizeof (int));
455 double *ar= GNUNET_malloc (pi * sizeof (double));
458 /* Adding constraint rows
459 * This constraints are kind of "for all addresses"
460 * Feasibility constraints:
462 * c 1) bandwidth capping
463 * c 3) minimum bandwidth
464 * c 4) minimum number of connections
465 * c 6) maximize diversity
466 * c 10) obey network specific quota
469 /* Row for c4) minimum connection */
470 int min = mlp->n_min;
471 /* Number of minimum connections is min(|Peers|, 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 /* Add rows for c 10) */
491 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
493 mlp->r_quota[c] = glp_add_rows (mlp->prob, 1);
495 GNUNET_asprintf(&text, "quota_ats_%i", mlp->quota_index[c]);
496 glp_set_row_name (mlp->prob, mlp->r_quota[c], text);
498 /* Set bounds to 0 <= x <= quota_out */
499 glp_set_row_bnds (mlp->prob, mlp->r_quota[c], GLP_UP, 0.0, mlp->quota_out[c]);
502 GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
504 /* Adding constraint rows
505 * This constraints are kind of "for all peers"
506 * Feasibility constraints:
508 * c 2) 1 address per peer
509 * sum (n_p1_1 + ... + n_p1_n) = 1
512 * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
515 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
518 /* Adding rows for c 8) */
519 mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p);
520 glp_set_row_name (mlp->prob, mlp->r_c8, "c8");
521 /* Set row bound == 0 */
522 glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0);
525 ia[mlp->ci] = mlp->r_c8;
526 ja[mlp->ci] = mlp->c_u;
530 struct ATS_Peer * peer = mlp->peer_head;
534 struct ATS_Address *addr = peer->head;
535 struct MLP_information *mlpi = NULL;
537 /* Adding rows for c 2) */
538 peer->r_c2 = glp_add_rows (mlp->prob, 1);
539 GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
540 glp_set_row_name (mlp->prob, peer->r_c2, name);
542 /* Set row bound == 1 */
543 glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
545 /* Adding rows for c 9) */
547 peer->r_c9 = glp_add_rows (mlp->prob, 1);
548 GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
549 glp_set_row_name (mlp->prob, peer->r_c9, name);
551 /* Set row bound == 0 */
552 glp_set_row_bnds (mlp->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
555 ia[mlp->ci] = peer->r_c9;
556 ja[mlp->ci] = mlp->c_r;
557 ar[mlp->ci] = -peer->f;
560 /* For all addresses of this peer */
563 mlpi = (struct MLP_information *) addr->solver_information;
565 /* coefficient for c 2) */
566 ia[mlp->ci] = peer->r_c2;
567 ja[mlp->ci] = mlpi->c_n;
571 /* coefficient for c 8) */
572 ia[mlp->ci] = mlp->r_c8;
573 ja[mlp->ci] = mlpi->c_b;
574 ar[mlp->ci] = peer->f;
578 /* coefficient for c 9) */
579 ia[mlp->ci] = peer->r_c9;
580 ja[mlp->ci] = mlpi->c_b;
590 /* c 7) For all quality metrics */
591 for (c = 0; c < mlp->m_q; c++)
594 struct ATS_Address *ta;
595 struct MLP_information * mlpi;
598 /* Adding rows for c 7) */
599 mlp->r_q[c] = glp_add_rows (mlp->prob, 1);
600 GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->q[c]));
601 glp_set_row_name (mlp->prob, mlp->r_q[c], name);
603 /* Set row bound == 0 */
604 glp_set_row_bnds (mlp->prob, mlp->r_q[c], GLP_FX, 0.0, 0.0);
606 ia[mlp->ci] = mlp->r_q[c];
607 ja[mlp->ci] = mlp->c_q[c];
611 for (tp = mlp->peer_head; tp != NULL; tp = tp->next)
612 for (ta = tp->head; ta != NULL; ta = ta->next)
614 mlpi = ta->solver_information;
615 value = mlpi->q_averaged[c];
617 mlpi->r_q[c] = mlp->r_q[c];
619 ia[mlp->ci] = mlp->r_q[c];
620 ja[mlp->ci] = mlpi->c_b;
621 ar[mlp->ci] = tp->f_q[c] * value;
629 * Add columns for all addresses
631 * @param cls GAS_MLP_Handle
632 * @param key Hashcode
633 * @param value ATS_Address
635 * @return GNUNET_OK to continue
638 create_columns_it (void *cls, const struct GNUNET_HashCode * key, void *value)
640 struct GAS_MLP_Handle *mlp = cls;
641 struct ATS_Address *address = value;
642 struct MLP_information *mlpi;
646 GNUNET_assert (address->solver_information != NULL);
647 mlpi = address->solver_information;
649 /* Add bandwidth column */
650 col = glp_add_cols (mlp->prob, 2);
655 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
656 glp_set_col_name (mlp->prob, mlpi->c_b , name);
658 /* Lower bound == 0 */
659 glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
660 /* Continuous value*/
661 glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
662 /* Objective function coefficient == 0 */
663 glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
666 /* Add usage column */
667 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
668 glp_set_col_name (mlp->prob, mlpi->c_n, name);
670 /* Limit value : 0 <= value <= 1 */
671 glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
673 glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
674 /* Objective function coefficient == 0 */
675 glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
683 * Create the MLP problem
685 * @param mlp the MLP handle
686 * @param addresses the hashmap containing all adresses
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 */
711 col = glp_add_cols (mlp->prob, 1);
714 glp_set_col_name (mlp->prob, col, "d");
715 /* Column objective function coefficient */
716 glp_set_obj_coef (mlp->prob, col, mlp->co_D);
717 /* Column lower bound = 0.0 */
718 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
720 /* Utilization u column */
721 col = glp_add_cols (mlp->prob, 1);
724 glp_set_col_name (mlp->prob, col, "u");
725 /* Column objective function coefficient */
726 glp_set_obj_coef (mlp->prob, col, mlp->co_U);
727 /* Column lower bound = 0.0 */
728 glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
731 /* Relativity r column */
732 col = glp_add_cols (mlp->prob, 1);
735 glp_set_col_name (mlp->prob, col, "r");
736 /* Column objective function coefficient */
737 glp_set_obj_coef (mlp->prob, col, mlp->co_R);
738 /* Column lower bound = 0.0 */
739 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);
770 * Solves the LP problem
772 * @param mlp the MLP Handle
773 * @param s_ctx context to return results
774 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
777 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
780 struct GNUNET_TIME_Relative duration;
781 struct GNUNET_TIME_Absolute end;
782 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
785 * Presolver is required if the problem was modified and an existing
786 * valid basis is now invalid */
787 if (mlp->presolver_required == GNUNET_YES)
788 mlp->control_param_lp.presolve = GLP_ON;
790 mlp->control_param_lp.presolve = GLP_OFF;
792 /* Solve LP problem to have initial valid solution */
794 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
797 /* The LP problem instance has been successfully solved. */
799 else if (res == GLP_EITLIM)
801 /* simplex iteration limit has been exceeded. */
802 // TODO Increase iteration limit?
804 else if (res == GLP_ETMLIM)
806 /* Time limit has been exceeded. */
807 // TODO Increase time limit?
811 /* Problem was ill-defined, retry with presolver */
812 if (mlp->presolver_required == GNUNET_NO)
814 mlp->presolver_required = GNUNET_YES;
819 /* Problem was ill-defined, no way to handle that */
820 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
822 "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
823 return GNUNET_SYSERR;
827 end = GNUNET_TIME_absolute_get ();
828 duration = GNUNET_TIME_absolute_get_difference (start, end);
830 mlp->lp_total_duration += duration.rel_value;
831 s_ctx->lp_duration = duration;
833 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
834 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time (ms)", duration.rel_value, GNUNET_NO);
835 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average (ms)",
836 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
838 /* Analyze problem status */
839 res = glp_get_status (mlp->prob);
841 /* solution is optimal */
843 /* solution is feasible */
847 /* Problem was ill-defined, no way to handle that */
849 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
851 "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
852 return GNUNET_SYSERR;
856 /* solved sucessfully, no presolver required next time */
857 mlp->presolver_required = GNUNET_NO;
864 * Solves the MLP problem
866 * @param mlp the MLP Handle
867 * @param s_ctx context to return results
868 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
871 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
874 struct GNUNET_TIME_Relative duration;
875 struct GNUNET_TIME_Absolute end;
876 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
878 /* solve MLP problem */
879 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
883 /* The MLP problem instance has been successfully solved. */
885 else if (res == GLP_EITLIM)
887 /* simplex iteration limit has been exceeded. */
888 // TODO Increase iteration limit?
890 else if (res == GLP_ETMLIM)
892 /* Time limit has been exceeded. */
893 // TODO Increase time limit?
897 /* Problem was ill-defined, no way to handle that */
898 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
900 "Solving MLP problem failed: %s\n", mlp_solve_to_string(res));
901 return GNUNET_SYSERR;
904 end = GNUNET_TIME_absolute_get ();
905 duration = GNUNET_TIME_absolute_get_difference (start, end);
907 mlp->mlp_total_duration += duration.rel_value;
908 s_ctx->mlp_duration = duration;
910 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
911 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time (ms)", duration.rel_value, GNUNET_NO);
912 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average (ms)",
913 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
915 /* Analyze problem status */
916 res = glp_mip_status(mlp->prob);
918 /* solution is optimal */
920 /* solution is feasible */
924 /* Problem was ill-defined, no way to handle that */
926 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
928 "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
929 return GNUNET_SYSERR;
936 int GAS_mlp_solve_problem (void *solver, struct GAS_MLP_SolutionContext *ctx);
940 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
942 struct GAS_MLP_Handle *mlp = cls;
943 struct GAS_MLP_SolutionContext ctx;
945 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
947 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
950 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
952 if (mlp->addr_in_problem != 0)
953 GAS_mlp_solve_problem(mlp, &ctx);
958 * Solves the MLP problem
960 * @param solver the MLP Handle
961 * @param ctx solution context
962 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
965 GAS_mlp_solve_problem (void *solver, struct GAS_MLP_SolutionContext *ctx)
967 struct GAS_MLP_Handle *mlp = solver;
969 /* Check if solving is already running */
970 if (GNUNET_YES == mlp->semaphore)
972 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
974 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
975 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
977 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
978 return GNUNET_SYSERR;
980 mlp->semaphore = GNUNET_YES;
982 mlp->last_execution = GNUNET_TIME_absolute_get ();
984 ctx->lp_result = GNUNET_SYSERR;
985 ctx->mlp_result = GNUNET_SYSERR;
986 ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
987 ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
989 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n");
994 GNUNET_asprintf(&name, "problem_%i", i);
995 glp_write_lp (mlp->prob, 0, name);
999 res = mlp_solve_lp_problem (mlp, ctx);
1000 ctx->lp_result = res;
1001 if (res != GNUNET_OK)
1003 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n");
1004 mlp->semaphore = GNUNET_NO;
1005 return GNUNET_SYSERR;
1009 GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
1010 glp_print_sol (mlp->prob, name);
1015 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n");
1016 res = mlp_solve_mlp_problem (mlp, ctx);
1017 ctx->mlp_result = res;
1018 if (res != GNUNET_OK)
1020 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n");
1021 mlp->semaphore = GNUNET_NO;
1022 return GNUNET_SYSERR;
1025 GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
1026 glp_print_mip (mlp->prob, name);
1030 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n",
1031 (GNUNET_OK == res) ? "successfully" : "failed", ctx->lp_duration.rel_value, ctx->mlp_duration.rel_value);
1032 /* Process result */
1033 struct ATS_Peer *p = NULL;
1034 struct ATS_Address *a = NULL;
1035 struct MLP_information *mlpi = NULL;
1037 for (p = mlp->peer_head; p != NULL; p = p->next)
1039 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id));
1040 for (a = p->head; a != NULL; a = a->next)
1045 mlpi = a->solver_information;
1047 b = glp_mip_col_val(mlp->prob, mlpi->c_b);
1050 n = glp_mip_col_val(mlp->prob, mlpi->c_n);
1052 mlpi->n = GNUNET_YES;
1054 mlpi->n = GNUNET_NO;
1056 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n",
1057 (n == 1.0) ? "[x]" : "[ ]", b);
1061 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1063 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1064 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1066 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1067 mlp->semaphore = GNUNET_NO;
1072 * Init the MLP problem solving component
1074 * @param cfg the GNUNET_CONFIGURATION_Handle handle
1075 * @param stats the GNUNET_STATISTICS handle
1076 * @param network array of GNUNET_ATS_NetworkType with length dest_length
1077 * @param out_dest array of outbound quotas
1078 * @param in_dest array of outbound quota
1079 * @param dest_length array length for quota arrays
1080 * @param bw_changed_cb callback for changed bandwidth amounts
1081 * @param bw_changed_cb_cls cls for callback
1082 * @return struct GAS_MLP_Handle on success, NULL on fail
1085 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1086 const struct GNUNET_STATISTICS_Handle *stats,
1088 unsigned long long *out_dest,
1089 unsigned long long *in_dest,
1091 GAS_bandwidth_changed_cb bw_changed_cb,
1092 void *bw_changed_cb_cls)
1094 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1099 unsigned long long tmp;
1102 struct GNUNET_TIME_Relative i_exec;
1104 char * quota_out_str;
1105 char * quota_in_str;
1107 struct GNUNET_TIME_Relative max_duration;
1108 long long unsigned int max_iterations;
1110 /* Init GLPK environment */
1111 int res = glp_init_env();
1114 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1115 "initialization successful");
1118 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1119 "environment is already initialized");
1122 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1123 "initialization failed (insufficient memory)");
1128 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1129 "initialization failed (unsupported programming model)");
1137 /* Create initial MLP problem */
1138 mlp->prob = glp_create_prob();
1139 GNUNET_assert (mlp->prob != NULL);
1141 mlp->BIG_M = (double) BIG_M_VALUE;
1143 /* Get timeout for iterations */
1144 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MAX_DURATION", &max_duration))
1146 max_duration = MLP_MAX_EXEC_DURATION;
1149 /* Get maximum number of iterations */
1150 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MAX_ITERATIONS", &max_iterations))
1152 max_iterations = MLP_MAX_ITERATIONS;
1155 /* Get diversity coefficient from configuration */
1156 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1159 D = (double) tmp / 100;
1163 /* Get proportionality coefficient from configuration */
1164 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1167 R = (double) tmp / 100;
1171 /* Get utilization coefficient from configuration */
1172 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1175 U = (double) tmp / 100;
1179 /* Get quality metric coefficients from configuration */
1181 int i_distance = -1;
1182 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1183 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1185 /* initialize quality coefficients with default value 1.0 */
1189 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1191 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1195 if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1196 "COEFFICIENT_QUALITY_DELAY",
1199 mlp->co_Q[i_delay] = (double) tmp / 100;
1201 mlp->co_Q[i_delay] = 1.0;
1203 if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1204 "COEFFICIENT_QUALITY_DISTANCE",
1206 mlp->co_Q[i_distance] = (double) tmp / 100;
1208 mlp->co_Q[i_distance] = 1.0;
1210 /* Get minimum bandwidth per used address from configuration */
1211 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1217 b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1220 /* Get minimum number of connections from configuration */
1221 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1228 /* Init network quotas */
1229 int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
1230 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1232 mlp->quota_index[c] = quotas[c];
1233 static char * entry_in = NULL;
1234 static char * entry_out = NULL;
1235 unsigned long long quota_in = 0;
1236 unsigned long long quota_out = 0;
1238 switch (quotas[c]) {
1239 case GNUNET_ATS_NET_UNSPECIFIED:
1240 entry_out = "UNSPECIFIED_QUOTA_OUT";
1241 entry_in = "UNSPECIFIED_QUOTA_IN";
1243 case GNUNET_ATS_NET_LOOPBACK:
1244 entry_out = "LOOPBACK_QUOTA_OUT";
1245 entry_in = "LOOPBACK_QUOTA_IN";
1247 case GNUNET_ATS_NET_LAN:
1248 entry_out = "LAN_QUOTA_OUT";
1249 entry_in = "LAN_QUOTA_IN";
1251 case GNUNET_ATS_NET_WAN:
1252 entry_out = "WAN_QUOTA_OUT";
1253 entry_in = "WAN_QUOTA_IN";
1255 case GNUNET_ATS_NET_WLAN:
1256 entry_out = "WLAN_QUOTA_OUT";
1257 entry_in = "WLAN_QUOTA_IN";
1263 if ((entry_in == NULL) || (entry_out == NULL))
1266 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_out, "a_out_str))
1268 if (0 == strcmp(quota_out_str, BIG_M_STRING) ||
1269 (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_out_str, "a_out)))
1270 quota_out = mlp->BIG_M;
1272 GNUNET_free (quota_out_str);
1273 quota_out_str = NULL;
1275 else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1277 quota_out = mlp->BIG_M;
1281 quota_out = mlp->BIG_M;
1284 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_in, "a_in_str))
1286 if (0 == strcmp(quota_in_str, BIG_M_STRING) ||
1287 (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_in_str, "a_in)))
1288 quota_in = mlp->BIG_M;
1290 GNUNET_free (quota_in_str);
1291 quota_in_str = NULL;
1293 else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1295 quota_in = mlp->BIG_M;
1299 quota_in = mlp->BIG_M;
1302 /* Check if defined quota could make problem unsolvable */
1303 if (((n_min * b_min) > quota_out) && (GNUNET_ATS_NET_UNSPECIFIED != quotas[c]))
1305 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Inconsistent quota configuration value `%s': "
1306 "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);
1313 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found `%s' quota %llu and `%s' quota %llu\n",
1314 entry_out, quota_out, entry_in, quota_in);
1315 GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_out, quota_out, GNUNET_NO);
1316 GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_in, quota_in, GNUNET_NO);
1317 mlp->quota_out[c] = quota_out;
1318 mlp->quota_in[c] = quota_in;
1321 /* Get minimum number of connections from configuration */
1322 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1323 "ATS_EXEC_INTERVAL",
1325 mlp->exec_interval = i_exec;
1327 mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1329 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1330 mlp->max_iterations = max_iterations;
1331 mlp->max_exec_duration = max_duration;
1332 mlp->auto_solve = GNUNET_YES;
1334 /* Redirect GLPK output to GNUnet logging */
1335 glp_error_hook((void *) mlp, &mlp_term_hook);
1337 /* Init LP solving parameters */
1338 glp_init_smcp(&mlp->control_param_lp);
1340 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1342 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1345 mlp->control_param_lp.it_lim = max_iterations;
1346 mlp->control_param_lp.tm_lim = max_duration.rel_value;
1348 /* Init MLP solving parameters */
1349 glp_init_iocp(&mlp->control_param_mlp);
1351 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1353 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1355 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1357 mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
1364 mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1365 mlp->semaphore = GNUNET_NO;
1370 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
1372 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
1373 GNUNET_i2s (&address->peer));
1375 GNUNET_assert (NULL != address);
1376 GNUNET_assert (NULL != address->solver_information);
1377 // GNUNET_assert (NULL != address->ats);
1379 struct MLP_information *mlpi = address->solver_information;
1380 //struct GNUNET_ATS_Information *ats = address->ats;
1381 GNUNET_assert (mlpi != NULL);
1384 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1387 /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */
1388 int index = GNUNET_SYSERR;
1390 if (index == GNUNET_SYSERR)
1393 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
1394 GNUNET_i2s (&address->peer),
1395 mlp_ats_to_string(mlp->q[c]),
1396 (double) ats[index].value);
1398 int i = mlpi->q_avg_i[c];*/
1399 double * qp = mlpi->q[c];
1401 qp[i] = (double) ats[index].value;
1405 for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
1407 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
1408 GNUNET_i2s (&address->peer),
1409 mlp_ats_to_string(mlp->q[c]),
1414 if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
1415 mlpi->q_avg_i[c] ++;
1417 mlpi->q_avg_i[c] = 0;
1425 case GNUNET_ATS_QUALITY_NET_DELAY:
1427 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1429 if (mlpi->q[c][c2] != -1)
1431 double * t2 = mlpi->q[c] ;
1436 if ((c3 > 0) && (avg > 0))
1437 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1438 mlpi->q_averaged[c] = (double) c3 / avg;
1440 mlpi->q_averaged[c] = 0.0;
1442 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1443 GNUNET_i2s (&address->peer),
1444 mlp_ats_to_string(mlp->q[c]),
1447 mlpi->q_averaged[c]);
1450 case GNUNET_ATS_QUALITY_NET_DISTANCE:
1452 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1454 if (mlpi->q[c][c2] != -1)
1456 double * t2 = mlpi->q[c] ;
1461 if ((c3 > 0) && (avg > 0))
1462 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1463 mlpi->q_averaged[c] = (double) c3 / avg;
1465 mlpi->q_averaged[c] = 0.0;
1467 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1468 GNUNET_i2s (&address->peer),
1469 mlp_ats_to_string(mlp->q[c]),
1472 mlpi->q_averaged[c]);
1479 if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
1482 /* Get current number of columns */
1483 int found = GNUNET_NO;
1484 int cols = glp_get_num_cols(mlp->prob);
1485 int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
1486 double *val = GNUNET_malloc (cols * sizeof (double) + 1);
1488 /* Get the matrix row of quality */
1489 int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
1490 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
1492 /* Get the index if matrix row of quality */
1493 for (c4 = 1; c4 <= length; c4++ )
1495 if (mlpi->c_b == ind[c4])
1497 /* Update the value */
1498 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
1499 mlp_ats_to_string(mlp->q[c]),
1500 glp_get_col_name (mlp->prob, ind[c4]),
1501 glp_get_row_name (mlp->prob, mlp->r_q[c]),
1503 mlpi->q_averaged[c]);
1504 val[c4] = mlpi->q_averaged[c];
1510 if (found == GNUNET_NO)
1513 ind[length+1] = mlpi->c_b;
1514 val[length+1] = mlpi->q_averaged[c];
1515 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]);
1516 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
1520 /* Get the index if matrix row of quality */
1521 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
1532 * Add a single address to the solve
1534 * @param solver the solver Handle
1535 * @param addresses the address hashmap containing all addresses
1536 * @param address the address to add
1539 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1545 * Updates a single address in the MLP problem
1547 * If the address did not exist before in the problem:
1548 * The MLP problem has to be recreated and the problem has to be resolved
1550 * Otherwise the addresses' values can be updated and the existing base can
1553 * @param solver the solver Handle
1554 * @param addresses the address hashmap containing all addresses
1555 * @param address the update address
1556 * @param session the new session (if changed otherwise current)
1557 * @param in_use the new address in use state (if changed otherwise current)
1558 * @param atsi the latest ATS information
1559 * @param atsi_count the atsi count
1562 GAS_mlp_address_update (void *solver,
1563 struct GNUNET_CONTAINER_MultiHashMap *addresses,
1564 struct ATS_Address *address,
1567 const struct GNUNET_ATS_Information *atsi,
1568 uint32_t atsi_count)
1570 struct GAS_MLP_Handle *mlp = solver;
1572 struct MLP_information *mlpi;
1573 struct GAS_MLP_SolutionContext ctx;
1575 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1577 /* We add a new address */
1578 if (address->solver_information == NULL)
1584 if (new == GNUNET_YES)
1586 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1589 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1593 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1594 mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1595 mlpi->q_avg_i[c] = 0;
1596 mlpi->q_averaged[c] = 0.0;
1599 address->solver_information = mlpi;
1600 mlp->addr_in_problem ++;
1601 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1603 /* Check for and add peer */
1604 struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1608 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1609 GNUNET_i2s (&address->peer));
1611 peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1616 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1622 memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1623 GNUNET_assert(address->prev == NULL);
1624 GNUNET_assert(address->next == NULL);
1625 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1626 GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1628 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1633 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1634 GNUNET_i2s (&address->peer));
1636 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1638 update_quality (mlp, address);
1642 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1643 GNUNET_i2s (&address->peer));
1645 update_quality (mlp, address);
1649 if (new == GNUNET_YES)
1651 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1653 mlp_delete_problem (mlp);
1654 mlp_create_problem (mlp, addresses);
1655 mlp->presolver_required = GNUNET_YES;
1657 if (mlp->auto_solve == GNUNET_YES)
1658 GAS_mlp_solve_problem (mlp, &ctx);
1662 * Deletes a single address in the MLP problem
1664 * The MLP problem has to be recreated and the problem has to be resolved
1666 * @param solver the MLP Handle
1667 * @param addresses the address hashmap
1668 * the address has to be already removed from the hashmap
1669 * @param address the address to delete
1670 * @param session_only delete only session not whole address
1673 GAS_mlp_address_delete (void *solver,
1674 struct GNUNET_CONTAINER_MultiHashMap * addresses,
1675 struct ATS_Address *address,
1678 struct GAS_MLP_Handle *mlp = solver;
1679 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1680 struct GAS_MLP_SolutionContext ctx;
1682 /* Free resources */
1683 if (address->solver_information != NULL)
1685 GNUNET_free (address->solver_information);
1686 address->solver_information = NULL;
1688 mlp->addr_in_problem --;
1689 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1692 /* Remove from peer list */
1693 struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1694 GNUNET_assert (head != NULL);
1696 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1698 GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1699 if ((head->head == NULL) && (head->tail == NULL))
1701 /* No address for peer left, remove peer */
1703 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1705 GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1708 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1711 /* Update problem */
1712 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1714 mlp_delete_problem (mlp);
1715 if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1717 mlp_create_problem (mlp, addresses);
1720 mlp->presolver_required = GNUNET_YES;
1721 if (mlp->auto_solve == GNUNET_YES)
1722 GAS_mlp_solve_problem (mlp, &ctx);
1727 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1730 struct ATS_Address *aa = (struct ATS_Address *) cls;
1731 struct ATS_Address *addr = value;
1732 struct MLP_information *mlpi = addr->solver_information;
1735 if (mlpi->n == GNUNET_YES)
1738 if (mlpi->b > (double) UINT32_MAX)
1739 aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1741 aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1742 aa->assigned_bw_in.value__ = htonl(0);
1750 * Get the preferred address for a specific peer
1752 * @param solver the MLP Handle
1753 * @param addresses address hashmap
1754 * @param peer the peer
1755 * @return suggested address
1757 const struct ATS_Address *
1758 GAS_mlp_get_preferred_address (void *solver,
1759 struct GNUNET_CONTAINER_MultiHashMap * addresses,
1760 const struct GNUNET_PeerIdentity *peer)
1762 struct ATS_Address * aa = NULL;
1763 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", GNUNET_i2s (peer));
1764 GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, mlp_get_preferred_address_it, aa);
1770 * Changes the preferences for a peer in the MLP problem
1772 * @param solver the MLP Handle
1773 * @param client client
1774 * @param peer the peer
1775 * @param kind the kind to change the preference
1776 * @param score the score
1779 GAS_mlp_address_change_preference (void *solver,
1781 const struct GNUNET_PeerIdentity *peer,
1782 enum GNUNET_ATS_PreferenceKind kind,
1785 struct GAS_MLP_Handle *mlp = solver;
1786 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1788 //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1789 //FIXME to finish implementation
1790 /* Here we have to do the matching */
1795 * Shutdown the MLP problem solving component
1797 * @param solver the solver handle
1800 GAS_mlp_done (void *solver)
1802 struct GAS_MLP_Handle *mlp = solver;
1803 struct ATS_Peer * peer;
1804 struct ATS_Address *addr;
1806 GNUNET_assert (mlp != NULL);
1808 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1810 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1811 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1814 /* clean up peer list */
1815 peer = mlp->peer_head;
1816 while (peer != NULL)
1818 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1819 GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1820 for (addr = peer->head; NULL != addr; addr = peer->head)
1822 GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1823 GNUNET_free (addr->solver_information);
1824 addr->solver_information = NULL;
1827 peer = mlp->peer_head;
1829 mlp_delete_problem (mlp);
1831 /* Clean up GLPK environment */
1838 /* end of gnunet-service-ats_addresses_mlp.c */