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"
36 * NOTE: Do not modify this documentation. This documentation is based on
37 * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
38 * use build_txt.sh to generate plaintext output
40 * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
41 * optimizing an mixed integer programming problem. The MLP solver uses a
42 * number of constraints to find the best adddress for a peer and an optimal
43 * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
46 * We defined a constraint system to find an optimal bandwidth assignment.
47 * This constraint system uses as an input data addresses, bandwidth quotas,
48 * preferences and quality values. This constraint system is stored in an
49 * matrix based equotation system.
53 * A (M)LP problem consists of a target function to optimizes, constraints
54 * and rows and columns. FIXME GLP uses three arrays to index the matrix: two
55 * integer arrays storing the row and column indices in the matrix and an
56 * float array to store the coeeficient.
58 * To solve the problem we first find an initial solution for the LP problem
59 * using the LP solver and then find an MLP solution based on this solution
60 * using the MLP solver.
62 * Solving (M)LP problems has the property that finding an initial solution
63 * for the LP problem is computationally expensive and finding the MLP
64 * solution is cheaper. This is especially interesting an existing LP
65 * solution can be reused if only coefficients in the matrix have changed
66 * (addresses updated). Only when the problem size changes (addresses added
67 * or deleted) a new LP solution has to be found.
70 * The mlp solver solves the bandwidth assignment problem only on demand when
71 * an address suggestion is requested. When an address is requested mlp the
72 * solves the mlp problem and if the active address or the bandwidth assigned
73 * changes it calls the callback to addresses. The mlp solver gets notified
74 * about new addresses (adding sessions), removed addresses (address
75 * deletions) and address updates. To benefit from the mlp properties
76 * mentioned in section 5 the solver rembers if since the last solution
77 * addresses were added or deleted (problem size changed, problem has to be
78 * rebuild and solved from sratch) or if addresses were updated and the
79 * existing solution can be reused.
83 * The quotas for each network segment are passed by addresses. MLP can be
84 * adapted using configuration settings and uses the following parameters:
86 * Maximum duration for a MLP solution procees (default: 3 sec.)
88 * Maximum number of iterations for a MLP solution process (default:
90 * * MLP_MIN_CONNECTIONS:
91 * Minimum number of desired connections (default: 4)
92 * * MLP_MIN_BANDWIDTH:
93 * Minimum amount of bandwidth assigned to an address (default: 1024)
94 * * MLP_COEFFICIENT_D:
95 * Diversity coefficient (default: 1.0)
96 * * MLP_COEFFICIENT_R:
97 * Relativity coefficient (default: 1.0)
98 * * MLP_COEFFICIENT_U:
99 * Utilization coefficient (default: 1.0)
100 * * MLP_COEFFICIENT_D:
101 * Diversity coefficient (default: 1.0)
102 * * MLP_COEFFICIENT_QUALITY_DELAY:
103 * Quality delay coefficient (default: 1.0)
104 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
105 * Quality distance coefficient (default: 1.0)
106 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
107 * Quality distance coefficient (default: 1.0)
108 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
109 * Quality distance coefficient (default: 1.0)
110 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
111 * Quality distance coefficient (default: 1.0)
113 * 5.2 Data structures used
115 * mlp has for each known peer a struct ATS_Peer containing information about
116 * a specific peer. The address field solver_information contains information
117 * about the mlp properties of this address.
121 * During initialization mlp initializes the GLPK libray used to solve the
122 * MLP problem: it initializes the glpk environment and creates an initial LP
123 * problem. Next it loads the configuration values from the configuration or
124 * uses the default values configured in -addresses_mlp.h. The quotas used
125 * are given by addresses but may have to be adjusted. mlp uses a upper limit
126 * for the bandwidth assigned called BIG M and a minimum amount of bandwidth
127 * an address gets assigned as well as a minium desired number of
128 * connections. If the configured quota is bigger than BIG M, it is reduced
129 * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
130 * *MLP_MIN_BANDWIDTH it is increased to this value.
136 #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
138 #define WRITE_MLP GNUNET_NO
139 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_YES
140 #define VERBOSE_GLPK GNUNET_NO
143 * Intercept GLPK terminal output
144 * @param info the mlp handle
145 * @param s the string to print
146 * @return 0: glpk prints output on terminal, 0 != surpress output
149 mlp_term_hook (void *info, const char *s)
151 /* Not needed atm struct MLP_information *mlp = info; */
152 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
160 * Delete the MLP problem and free the constrain matrix
162 * @param mlp the MLP handle
165 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
169 if (mlp->p.prob != NULL)
170 glp_delete_prob(mlp->p.prob);
172 /* delete row index */
173 if (mlp->p.ia != NULL)
175 GNUNET_free (mlp->p.ia);
179 /* delete column index */
180 if (mlp->p.ja != NULL)
182 GNUNET_free (mlp->p.ja);
186 /* delete coefficients */
187 if (mlp->p.ar != NULL)
189 GNUNET_free (mlp->p.ar);
199 * Translate ATS properties to text
200 * Just intended for debugging
202 * @param ats_index the ATS index
203 * @return string with result
206 mlp_ats_to_string (int ats_index)
209 case GNUNET_ATS_ARRAY_TERMINATOR:
210 return "GNUNET_ATS_ARRAY_TERMINATOR";
211 case GNUNET_ATS_UTILIZATION_UP:
212 return "GNUNET_ATS_UTILIZATION_UP";
213 case GNUNET_ATS_UTILIZATION_DOWN:
214 return "GNUNET_ATS_UTILIZATION_DOWN";
215 case GNUNET_ATS_COST_LAN:
216 return "GNUNET_ATS_COST_LAN";
217 case GNUNET_ATS_COST_WAN:
218 return "GNUNET_ATS_COST_LAN";
219 case GNUNET_ATS_COST_WLAN:
220 return "GNUNET_ATS_COST_WLAN";
221 case GNUNET_ATS_NETWORK_TYPE:
222 return "GNUNET_ATS_NETWORK_TYPE";
223 case GNUNET_ATS_QUALITY_NET_DELAY:
224 return "GNUNET_ATS_QUALITY_NET_DELAY";
225 case GNUNET_ATS_QUALITY_NET_DISTANCE:
226 return "GNUNET_ATS_QUALITY_NET_DISTANCE";
236 * Translate glpk solver error codes to text
237 * @param retcode return code
238 * @return string with result
241 mlp_solve_to_string (int retcode)
247 return "invalid basis";
249 return "singular matrix";
251 return "ill-conditioned matrix";
253 return "invalid bounds";
255 return "solver failed";
257 return "objective lower limit reached";
259 return "objective upper limit reached";
261 return "iteration limit exceeded";
263 return "time limit exceeded";
265 return "no primal feasible solution";
267 return "root LP optimum not provided";
269 return "search terminated by application";
271 return "relative mip gap tolerance reached";
273 return "no dual feasible solution";
275 return "no convergence";
277 return "numerical instability";
279 return "invalid data";
281 return "result out of range";
284 return "unknown error";
290 * Translate glpk status error codes to text
291 * @param retcode return code
292 * @return string with result
295 mlp_status_to_string (int retcode)
299 return "solution is undefined";
301 return "solution is feasible";
303 return "solution is infeasible";
305 return "no feasible solution exists";
307 return "solution is optimal";
309 return "solution is unbounded";
312 return "unknown error";
318 * Find a peer in the DLL
320 * @param mlp the mlp handle
321 * @param peer the peer to find
322 * @return the peer struct
324 static struct ATS_Peer *
325 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
327 struct ATS_Peer *res = mlp->peer_head;
330 if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
341 * Find the required ATS information for an address
343 * @param addr the address
344 * @param ats_index the desired ATS index
346 * @return the index on success, otherwise GNUNET_SYSERR
349 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
351 struct GNUNET_ATS_Information * ats = addr->ats;
353 int found = GNUNET_NO;
354 for (c = 0; c < addr->ats_count; c++)
356 if (ats[c].type == ats_index)
362 if (found == GNUNET_YES)
365 return GNUNET_SYSERR;
370 * Solves the LP problem
372 * @param mlp the MLP Handle
373 * @param s_ctx context to return results
374 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
377 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
380 struct GNUNET_TIME_Relative duration;
381 struct GNUNET_TIME_Absolute end;
382 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
385 * Presolver is required if the problem was modified and an existing
386 * valid basis is now invalid */
387 if (mlp->presolver_required == GNUNET_YES)
388 mlp->control_param_lp.presolve = GLP_ON;
390 mlp->control_param_lp.presolve = GLP_OFF;
392 /* Solve LP problem to have initial valid solution */
394 res = glp_simplex(mlp->prob, &mlp->control_param_lp);
397 /* The LP problem instance has been successfully solved. */
399 else if (res == GLP_EITLIM)
401 /* simplex iteration limit has been exceeded. */
402 // TODO Increase iteration limit?
404 else if (res == GLP_ETMLIM)
406 /* Time limit has been exceeded. */
407 // TODO Increase time limit?
411 /* Problem was ill-defined, retry with presolver */
412 if (mlp->presolver_required == GNUNET_NO)
414 mlp->presolver_required = GNUNET_YES;
419 /* Problem was ill-defined, no way to handle that */
420 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
422 "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
423 return GNUNET_SYSERR;
427 end = GNUNET_TIME_absolute_get ();
428 duration = GNUNET_TIME_absolute_get_difference (start, end);
430 mlp->lp_total_duration += duration.rel_value;
431 s_ctx->lp_duration = duration;
433 GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
434 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time (ms)", duration.rel_value, GNUNET_NO);
435 GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average (ms)",
436 mlp->lp_total_duration / mlp->lp_solved, GNUNET_NO);
438 /* Analyze problem status */
439 res = glp_get_status (mlp->prob);
441 /* solution is optimal */
443 /* solution is feasible */
447 /* Problem was ill-defined, no way to handle that */
449 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
451 "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
452 return GNUNET_SYSERR;
456 /* solved sucessfully, no presolver required next time */
457 mlp->presolver_required = GNUNET_NO;
464 * Solves the MLP problem
466 * @param mlp the MLP Handle
467 * @param s_ctx context to return results
468 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
471 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
474 struct GNUNET_TIME_Relative duration;
475 struct GNUNET_TIME_Absolute end;
476 struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
478 /* solve MLP problem */
479 res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
483 /* The MLP problem instance has been successfully solved. */
485 else if (res == GLP_EITLIM)
487 /* simplex iteration limit has been exceeded. */
488 // TODO Increase iteration limit?
490 else if (res == GLP_ETMLIM)
492 /* Time limit has been exceeded. */
493 // TODO Increase time limit?
497 /* Problem was ill-defined, no way to handle that */
498 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
500 "Solving MLP problem failed: %s\n", mlp_solve_to_string(res));
501 return GNUNET_SYSERR;
504 end = GNUNET_TIME_absolute_get ();
505 duration = GNUNET_TIME_absolute_get_difference (start, end);
507 mlp->mlp_total_duration += duration.rel_value;
508 s_ctx->mlp_duration = duration;
510 GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
511 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time (ms)", duration.rel_value, GNUNET_NO);
512 GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average (ms)",
513 mlp->mlp_total_duration / mlp->mlp_solved, GNUNET_NO);
515 /* Analyze problem status */
516 res = glp_mip_status(mlp->prob);
518 /* solution is optimal */
520 /* solution is feasible */
524 /* Problem was ill-defined, no way to handle that */
526 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
528 "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
529 return GNUNET_SYSERR;
536 int GAS_mlp_solve_problem (void *solver, struct GAS_MLP_SolutionContext *ctx);
540 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
542 struct GAS_MLP_Handle *mlp = cls;
543 struct GAS_MLP_SolutionContext ctx;
545 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
547 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
550 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
552 if (mlp->addresses_in_problem != 0)
553 GAS_mlp_solve_problem(mlp, &ctx);
560 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
562 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
563 GNUNET_i2s (&address->peer));
565 GNUNET_assert (NULL != address);
566 GNUNET_assert (NULL != address->solver_information);
567 // GNUNET_assert (NULL != address->ats);
569 struct MLP_information *mlpi = address->solver_information;
570 //struct GNUNET_ATS_Information *ats = address->ats;
571 GNUNET_assert (mlpi != NULL);
574 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
577 /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */
578 int index = GNUNET_SYSERR;
580 if (index == GNUNET_SYSERR)
583 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
584 GNUNET_i2s (&address->peer),
585 mlp_ats_to_string(mlp->q[c]),
586 (double) ats[index].value);
588 int i = mlpi->q_avg_i[c];*/
589 double * qp = mlpi->q[c];
591 qp[i] = (double) ats[index].value;
595 for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
597 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
598 GNUNET_i2s (&address->peer),
599 mlp_ats_to_string(mlp->q[c]),
604 if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
607 mlpi->q_avg_i[c] = 0;
615 case GNUNET_ATS_QUALITY_NET_DELAY:
617 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
619 if (mlpi->q[c][c2] != -1)
621 double * t2 = mlpi->q[c] ;
626 if ((c3 > 0) && (avg > 0))
627 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
628 mlpi->q_averaged[c] = (double) c3 / avg;
630 mlpi->q_averaged[c] = 0.0;
632 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
633 GNUNET_i2s (&address->peer),
634 mlp_ats_to_string(mlp->q[c]),
637 mlpi->q_averaged[c]);
640 case GNUNET_ATS_QUALITY_NET_DISTANCE:
642 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
644 if (mlpi->q[c][c2] != -1)
646 double * t2 = mlpi->q[c] ;
651 if ((c3 > 0) && (avg > 0))
652 /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
653 mlpi->q_averaged[c] = (double) c3 / avg;
655 mlpi->q_averaged[c] = 0.0;
657 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
658 GNUNET_i2s (&address->peer),
659 mlp_ats_to_string(mlp->q[c]),
662 mlpi->q_averaged[c]);
669 if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
672 /* Get current number of columns */
673 int found = GNUNET_NO;
674 int cols = glp_get_num_cols(mlp->prob);
675 int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
676 double *val = GNUNET_malloc (cols * sizeof (double) + 1);
678 /* Get the matrix row of quality */
679 int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
680 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
682 /* Get the index if matrix row of quality */
683 for (c4 = 1; c4 <= length; c4++ )
685 if (mlpi->c_b == ind[c4])
687 /* Update the value */
688 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
689 mlp_ats_to_string(mlp->q[c]),
690 glp_get_col_name (mlp->prob, ind[c4]),
691 glp_get_row_name (mlp->prob, mlp->r_q[c]),
693 mlpi->q_averaged[c]);
694 val[c4] = mlpi->q_averaged[c];
700 if (found == GNUNET_NO)
703 ind[length+1] = mlpi->c_b;
704 val[length+1] = mlpi->q_averaged[c];
705 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]);
706 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
710 /* Get the index if matrix row of quality */
711 glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
723 * Add constraints that are iterating over "forall addresses"
724 * and collects all existing peers for "forall peers" constraints
726 * @param cls GAS_MLP_Handle
727 * @param key Hashcode
728 * @param value ATS_Address
730 * @return GNUNET_OK to continue
733 create_constraint_it (void *cls, const struct GNUNET_HashCode * key, void *value)
735 struct GAS_MLP_Handle *mlp = cls;
736 struct MLP_Problem *p = &mlp->p;
737 struct ATS_Address *address = value;
738 struct MLP_information *mlpi;
739 unsigned int row_index;
742 GNUNET_assert (address->solver_information != NULL);
743 mlpi = (struct MLP_information *) address->solver_information;
745 /* c 1) bandwidth capping
746 * b_t + (-M) * n_t <= 0
748 row_index = glp_add_rows (p->prob, 1);
749 mlpi->r_c1 = row_index;
751 GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
752 glp_set_row_name (p->prob, row_index, name);
754 /* set row bounds: <= 0 */
755 glp_set_row_bnds (p->prob, row_index, GLP_UP, 0.0, 0.0);
756 p->ia[p->ci] = row_index;
757 p->ja[p->ci] = mlpi->c_b;
761 p->ia[p->ci] = row_index;
762 p->ja[p->ci] = mlpi->c_n;
763 p->ar[p->ci] = -mlp->BIG_M;
766 /* c 3) minimum bandwidth
767 * b_t + (-n_t * b_min) >= 0
770 row_index = glp_add_rows (p->prob, 1);
772 GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
773 glp_set_row_name (p->prob, row_index, name);
775 mlpi->r_c3 = row_index;
776 /* set row bounds: >= 0 */
777 glp_set_row_bnds (p->prob, row_index, GLP_LO, 0.0, 0.0);
779 p->ia[p->ci] = row_index;
780 p->ja[p->ci] = mlpi->c_b;
784 p->ia[p->ci] = row_index;
785 p->ja[p->ci] = mlpi->c_n;
786 p->ar[p->ci] = - (double) mlp->pv.b_min;
789 /* c 4) minimum connections
790 * (1)*n_1 + ... + (1)*n_m >= n_min
792 p->ia[p->ci] = p->r_c4;
793 p->ja[p->ci] = mlpi->c_n;
797 /* c 6) maximize diversity
798 * (1)*n_1 + ... + (1)*n_m - d == 0
800 p->ia[p->ci] = p->r_c6;
801 p->ja[p->ci] = mlpi->c_n;
805 /* c 10) obey network specific quotas
806 * (1)*b_1 + ... + (1)*b_m <= quota_n
811 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
813 if (mlp->pv.quota_index[c] == address->atsp_network_type)
815 cur_row = p->r_quota[c];
822 p->ia[p->ci] = cur_row;
823 p->ja[p->ci] = mlpi->c_b;
837 * Adds the problem constraints for all addresses
838 * Required for problem recreation after address deletion
840 * @param mlp the mlp handle
841 * @param addresses all addresses
845 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
847 unsigned int n_addresses;
848 struct MLP_Problem *p = &mlp->p;
853 n_addresses = p->addresses_in_problem;
855 /* Required indices in the constrain matrix
857 * feasibility constraints:
859 * c 1) bandwidth capping
860 * #rows: |n_addresses|
861 * #indices: 2 * |n_addresses|
863 * c 2) one active address per peer
865 * #indices: |n_addresses|
867 * c 3) minium bandwidth assigned
868 * #rows: |n_addresses|
869 * #indices: 2 * |n_addresses|
871 * c 4) minimum number of active connections
873 * #indices: |n_addresses|
875 * c 5) maximum ressource consumption
876 * #rows: |ressources|
877 * #indices: |n_addresses|
879 * c 10) obey network specific quota
880 * #rows: |network types
881 * #indices: |n_addresses|
883 * Sum for feasibility constraints:
884 * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1
885 * #indices: 7 * |n_addresses|
887 * optimality constraints:
891 * #indices: |n_addresses| + 1
894 * #rows: |quality properties|
895 * #indices: |n_addresses| + |quality properties|
899 * #indices: |n_addresses| + 1
903 * #indices: |n_addresses| + |peers|
906 /* last +1 caused by glpk index starting with one: [1..pi]*/
907 int pi = ((7 * n_addresses) + (5 * n_addresses + mlp->pv.m_q + mlp->c_p + 2) + 1);
912 int *ia = GNUNET_malloc (pi * sizeof (int));
916 int *ja = GNUNET_malloc (pi * sizeof (int));
920 double *ar= GNUNET_malloc (pi * sizeof (double));
923 /* Adding constraint rows
924 * This constraints are kind of "for all addresses"
925 * Feasibility constraints:
927 * c 1) bandwidth capping
928 * c 3) minimum bandwidth
929 * c 4) minimum number of connections
930 * c 6) maximize diversity
931 * c 10) obey network specific quota
934 /* Row for c4) minimum connection */
936 int min = mlp->pv.n_min;
937 /* Number of minimum connections is min(|Peers|, n_min) */
938 if (mlp->pv.n_min > mlp->c_p)
940 p->r_c4 = glp_add_rows (p->prob, 1);
941 glp_set_row_name (p->prob, p->r_c4, name);
942 glp_set_row_bnds (p->prob, p->r_c4, GLP_LO, min, min);
943 #if DEBUG_MLP_PROBLEM_CREATION
944 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
949 /* Add row for c6) */
951 p->r_c6 = glp_add_rows (p->prob, 1);
952 /* Set type type to fix */
953 glp_set_row_name (p->prob, p->r_c6, name);
954 glp_set_row_bnds (p->prob, p->r_c6, GLP_FX, 0.0, 0.0);
955 #if DEBUG_MLP_PROBLEM_CREATION
956 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
961 ia[p->ci] = p->r_c6 ;
965 #if DEBUG_MLP_PROBLEM_CREATION
966 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] == %.2f\n",
967 ia[p->ci], ja[p->ci], ar[p->ci]);
971 /* Add rows for c 10) */
972 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
974 p->r_quota[c] = glp_add_rows (p->prob, 1);
976 GNUNET_asprintf(&text, "quota_ats_%i", mlp->pv.quota_index[c]);
977 glp_set_row_name (p->prob, p->r_quota[c], text);
978 /* Set bounds to 0 <= x <= quota_out */
979 glp_set_row_bnds (p->prob, p->r_quota[c], GLP_UP, 0.0, mlp->pv.quota_out[c]);
980 #if DEBUG_MLP_PROBLEM_CREATION
981 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
983 "<=", mlp->pv.quota_out[c]);
988 //GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
990 /* Adding constraint rows
991 * This constraints are kind of "for all peers"
992 * Feasibility constraints:
994 * c 2) 1 address per peer
995 * sum (n_p1_1 + ... + n_p1_n) = 1
998 * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
1001 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
1004 /* Adding rows for c 8) */
1005 p->r_c8 = glp_add_rows (p->prob, mlp->c_p);
1007 glp_set_row_name (p->prob, p->r_c8, "c8");
1008 /* Set row bound == 0 */
1009 glp_set_row_bnds (p->prob, p->r_c8, GLP_FX, 0.0, 0.0);
1010 #if DEBUG_MLP_PROBLEM_CREATION
1011 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1017 ia[p->ci] = p->r_c8;
1021 #if DEBUG_MLP_PROBLEM_CREATION
1022 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] == %.2f\n",
1023 ia[p->ci], ja[p->ci], ar[p->ci]);
1026 struct ATS_Peer * peer = mlp->peer_head;
1028 while (peer != NULL)
1030 struct ATS_Address *addr = peer->head;
1031 struct MLP_information *mlpi = NULL;
1033 /* Adding rows for c 2) */
1034 peer->r_c2 = glp_add_rows (p->prob, 1);
1035 GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
1036 glp_set_row_name (p->prob, peer->r_c2, name);
1038 /* Set row bound == 1 */
1039 glp_set_row_bnds (p->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
1041 /* Adding rows for c 9) */
1042 peer->r_c9 = glp_add_rows (p->prob, 1);
1043 GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
1044 glp_set_row_name (p->prob, peer->r_c9, name);
1046 /* Set row bound == 0 */
1047 glp_set_row_bnds (p->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
1050 ia[p->ci] = peer->r_c9;
1052 ar[p->ci] = -peer->f;
1055 /* For all addresses of this peer */
1056 while (addr != NULL)
1058 mlpi = (struct MLP_information *) addr->solver_information;
1060 /* coefficient for c 2) */
1061 ia[p->ci] = peer->r_c2;
1062 ja[p->ci] = mlpi->c_n;
1066 /* coefficient for c 8) */
1067 ia[p->ci] = p->r_c8;
1068 ja[p->ci] = mlpi->c_b;
1069 ar[p->ci] = peer->f;
1073 /* coefficient for c 9) */
1074 ia[p->ci] = peer->r_c9;
1075 ja[p->ci] = mlpi->c_b;
1085 /* c 7) For all quality metrics */
1086 for (c = 0; c < mlp->pv.m_q; c++)
1088 struct ATS_Peer *tp;
1089 struct ATS_Address *ta;
1090 struct MLP_information * mlpi;
1093 /* Adding rows for c 7) */
1094 p->r_q[c] = glp_add_rows (p->prob, 1);
1095 GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c]));
1096 glp_set_row_name (p->prob, p->r_q[c], name);
1098 /* Set row bound == 0 */
1099 glp_set_row_bnds (p->prob, p->r_q[c], GLP_FX, 0.0, 0.0);
1101 ia[p->ci] = p->r_q[c];
1102 ja[p->ci] = p->c_q[c];
1106 for (tp = mlp->peer_head; tp != NULL; tp = tp->next)
1107 for (ta = tp->head; ta != NULL; ta = ta->next)
1109 mlpi = ta->solver_information;
1110 value = mlpi->q_averaged[c];
1112 mlpi->r_q[c] = p->r_q[c];
1114 ia[p->ci] = p->r_q[c];
1115 ja[p->ci] = mlpi->c_b;
1116 ar[p->ci] = tp->f_q[c] * value;
1124 * Add columns for all addresses
1126 * @param cls GAS_MLP_Handle
1127 * @param key Hashcode
1128 * @param value ATS_Address
1130 * @return GNUNET_OK to continue
1133 mlp_create_address_columns_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1135 struct GAS_MLP_Handle *mlp = cls;
1136 struct MLP_Problem *p = &mlp->p;
1137 struct ATS_Address *address = value;
1138 struct MLP_information *mlpi;
1142 if (NULL != address->solver_information)
1144 GNUNET_free (address->solver_information);
1145 address->solver_information = NULL;
1148 /* Check if we have to add this peer due to a pending request */
1149 if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
1152 p->addresses_in_problem ++;
1153 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1154 address->solver_information = mlpi;
1156 /* Add bandwidth column */
1157 col = glp_add_cols (p->prob, 2);
1159 mlpi->c_n = col + 1;
1162 GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1163 glp_set_col_name (p->prob, mlpi->c_b , name);
1164 /* Lower bound == 0 */
1165 glp_set_col_bnds (p->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
1166 /* Continuous value*/
1167 glp_set_col_kind (p->prob, mlpi->c_b , GLP_CV);
1168 /* Objective function coefficient == 0 */
1169 glp_set_obj_coef (p->prob, mlpi->c_b , 0);
1170 #if DEBUG_MLP_PROBLEM_CREATION
1171 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1172 mlpi->c_b, name, GNUNET_i2s(&address->peer), address);
1176 /* Add usage column */
1177 GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1178 glp_set_col_name (p->prob, mlpi->c_n, name);
1179 /* Limit value : 0 <= value <= 1 */
1180 glp_set_col_bnds (p->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
1182 glp_set_col_kind (p->prob, mlpi->c_n, GLP_IV);
1183 /* Objective function coefficient == 0 */
1184 glp_set_obj_coef (p->prob, mlpi->c_n, 0);
1185 #if DEBUG_MLP_PROBLEM_CREATION
1186 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1187 mlpi->c_n, name, GNUNET_i2s(&address->peer), address);
1195 * Create the MLP problem
1197 * @param mlp the MLP handle
1198 * @param addresses the hashmap containing all adresses
1199 * @return GNUNET_OK or GNUNET_SYSERR
1202 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1204 struct MLP_Problem *p = &mlp->p;
1205 int res = GNUNET_OK;
1210 LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n",
1211 GNUNET_CONTAINER_multihashmap_size(mlp->peers));
1213 GNUNET_assert (p->prob == NULL);
1215 /* create the glpk problem */
1216 p->prob = glp_create_prob ();
1217 p->addresses_in_problem = 0;;
1218 GNUNET_assert (NULL != p->prob);
1220 /* Set a problem name */
1221 glp_set_prob_name (p->prob, "GNUnet ats bandwidth distribution");
1223 /* Set optimization direction to maximize */
1224 glp_set_obj_dir (p->prob, GLP_MAX);
1226 /* Adding invariant columns */
1227 /* Diversity d column */
1228 p->c_d = glp_add_cols (p->prob, 1);
1230 glp_set_col_name (p->prob, p->c_d, "d");
1231 /* Column objective function coefficient */
1232 glp_set_obj_coef (p->prob, p->c_d, mlp->pv.co_D);
1233 /* Column lower bound = 0.0 */
1234 glp_set_col_bnds (p->prob, p->c_d, GLP_LO, 0.0, 0.0);
1235 #if DEBUG_MLP_PROBLEM_CREATION
1236 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1237 p->c_d, "d", mlp->pv.co_D);
1241 /* Utilization u column */
1242 p->c_u = glp_add_cols (p->prob, 1);
1244 glp_set_col_name (p->prob, p->c_u, "u");
1245 /* Column objective function coefficient */
1246 glp_set_obj_coef (p->prob, p->c_u, mlp->pv.co_U);
1247 /* Column lower bound = 0.0 */
1248 glp_set_col_bnds (p->prob, p->c_u, GLP_LO, 0.0, 0.0);
1249 #if DEBUG_MLP_PROBLEM_CREATION
1250 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1251 p->c_u, "u", mlp->pv.co_U);
1254 /* Relativity r column */
1255 p->c_r = glp_add_cols (p->prob, 1);
1257 glp_set_col_name (p->prob, p->c_r, "r");
1258 /* Column objective function coefficient */
1259 glp_set_obj_coef (p->prob, p->c_r, mlp->pv.co_R);
1260 /* Column lower bound = 0.0 */
1261 glp_set_col_bnds (p->prob, p->c_r, GLP_LO, 0.0, 0.0);
1262 #if DEBUG_MLP_PROBLEM_CREATION
1263 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1264 p->c_r, "r", mlp->pv.co_R);
1267 /* Quality metric columns */
1268 cur_col = glp_add_cols(p->prob, mlp->pv.m_q);
1269 for (c = 0; c < mlp->pv.m_q; c++)
1271 p->c_q[c] = cur_col + c;
1272 GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]);
1273 glp_set_col_name (p->prob, p->c_q[c], name);
1274 /* Column lower bound = 0.0 */
1275 glp_set_col_bnds (p->prob, p->c_q[c], GLP_LO, 0.0, 0.0);
1276 /* Coefficient == Qm */
1277 glp_set_obj_coef (p->prob, p->c_q[c], mlp->pv.co_Q[c]);
1278 #if DEBUG_MLP_PROBLEM_CREATION
1279 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1280 p->c_q[c], name, mlp->pv.co_Q[c]);
1285 /* Add columns for addresses */
1286 GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_address_columns_it, mlp);
1287 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problems contains %u addresses, %u addresses skipped \n",
1288 p->addresses_in_problem, GNUNET_CONTAINER_multihashmap_size(addresses)- p->addresses_in_problem);
1290 /* Add constraints rows */
1291 mlp_add_constraints_all_addresses (mlp, addresses);
1293 /* Load the matrix */
1294 //glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
1301 * Solves the MLP problem
1303 * @param solver the MLP Handle
1304 * @param addresses the address hashmap
1305 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
1308 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1310 struct GAS_MLP_Handle *mlp = solver;
1313 GNUNET_assert (NULL != solver);
1315 if ((GNUNET_NO == mlp->mlp_prob_changed) && (GNUNET_NO == mlp->mlp_prob_updated))
1317 LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1321 if (GNUNET_YES == mlp->mlp_prob_changed)
1323 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1324 mlp_delete_problem (mlp);
1325 mlp_create_problem (mlp, addresses);
1329 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1334 struct GAS_MLP_Handle *mlp = solver;
1337 GNUNET_assert (NULL != solver);
1338 GNUNET_assert (NULL != ctx);
1340 /* Check if solving is already running */
1341 if (GNUNET_YES == mlp->semaphore)
1343 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1345 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1346 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1348 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1349 return GNUNET_SYSERR;
1351 mlp->semaphore = GNUNET_YES;
1353 mlp->last_execution = GNUNET_TIME_absolute_get ();
1355 ctx->lp_result = GNUNET_SYSERR;
1356 ctx->mlp_result = GNUNET_SYSERR;
1357 ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1358 ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1360 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n");
1365 GNUNET_asprintf(&name, "problem_%i", i);
1366 glp_write_lp (mlp->prob, 0, name);
1370 res = mlp_solve_lp_problem (mlp, ctx);
1371 ctx->lp_result = res;
1372 if (res != GNUNET_OK)
1374 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n");
1375 mlp->semaphore = GNUNET_NO;
1376 return GNUNET_SYSERR;
1380 GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
1381 glp_print_sol (mlp->prob, name);
1386 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n");
1387 res = mlp_solve_mlp_problem (mlp, ctx);
1388 ctx->mlp_result = res;
1389 if (res != GNUNET_OK)
1391 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n");
1392 mlp->semaphore = GNUNET_NO;
1393 return GNUNET_SYSERR;
1396 GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
1397 glp_print_mip (mlp->prob, name);
1401 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n",
1402 (GNUNET_OK == res) ? "successfully" : "failed",
1403 ctx->lp_duration.rel_value,
1404 ctx->mlp_duration.rel_value);
1405 /* Process result */
1406 struct ATS_Peer *p = NULL;
1407 struct ATS_Address *a = NULL;
1408 struct MLP_information *mlpi = NULL;
1410 for (p = mlp->peer_head; p != NULL; p = p->next)
1412 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id));
1413 for (a = p->head; a != NULL; a = a->next)
1418 mlpi = a->solver_information;
1420 b = glp_mip_col_val(mlp->prob, mlpi->c_b);
1423 n = glp_mip_col_val(mlp->prob, mlpi->c_n);
1426 /* This is the address to be used */
1427 mlpi->n = GNUNET_YES;
1431 /* This is the address not used */
1432 mlpi->n = GNUNET_NO;
1435 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n",
1436 (n == 1.0) ? "[x]" : "[ ]", b);
1438 /* Notify addresses */
1439 if ((ntohl(a->assigned_bw_in.value__) != b) ||
1440 (ntohl(a->assigned_bw_out.value__) != b) ||
1441 (mlpi->n != a->active))
1443 a->assigned_bw_in.value__ = htonl(b);
1444 a->assigned_bw_out.value__ = htonl(b);
1445 a->active = mlpi->n;
1446 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, a);
1451 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1453 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1454 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1456 mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1457 mlp->semaphore = GNUNET_NO;
1461 /* Reset change and update marker */
1462 mlp->mlp_prob_updated = GNUNET_NO;
1463 mlp->mlp_prob_changed = GNUNET_NO;
1469 * Add a single address to the solve
1471 * @param solver the solver Handle
1472 * @param addresses the address hashmap containing all addresses
1473 * @param address the address to add
1476 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1478 struct GAS_MLP_Handle *mlp = solver;
1481 GNUNET_assert (NULL != solver);
1482 GNUNET_assert (NULL != addresses);
1483 GNUNET_assert (NULL != address);
1485 /* TODO Add address here */
1487 /* Is this peer included in the problem? */
1488 if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1490 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1493 if (NULL != address->solver_information)
1498 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1499 /* Problem size changed: new address for peer with pending request */
1500 mlp->mlp_prob_changed = GNUNET_YES;
1501 GAS_mlp_solve_problem (solver, addresses);
1505 * Updates a single address in the MLP problem
1507 * If the address did not exist before in the problem:
1508 * The MLP problem has to be recreated and the problem has to be resolved
1510 * Otherwise the addresses' values can be updated and the existing base can
1513 * @param solver the solver Handle
1514 * @param addresses the address hashmap containing all addresses
1515 * @param address the update address
1516 * @param session the new session (if changed otherwise current)
1517 * @param in_use the new address in use state (if changed otherwise current)
1518 * @param atsi the latest ATS information
1519 * @param atsi_count the atsi count
1522 GAS_mlp_address_update (void *solver,
1523 struct GNUNET_CONTAINER_MultiHashMap *addresses,
1524 struct ATS_Address *address,
1527 const struct GNUNET_ATS_Information *atsi,
1528 uint32_t atsi_count)
1531 struct GAS_MLP_Handle *mlp = solver;
1533 GNUNET_assert (NULL != solver);
1534 GNUNET_assert (NULL != addresses);
1535 GNUNET_assert (NULL != address);
1536 GNUNET_assert ((NULL != atsi) || (0 == atsi_count));
1538 /* TODO Update address here */
1540 /* Is this peer included in the problem? */
1541 if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1543 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1546 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1548 /* Problem size changed: new address for peer with pending request */
1549 mlp->mlp_prob_updated = GNUNET_YES;
1550 GAS_mlp_solve_problem (solver, addresses);
1554 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1556 /* We add a new address */
1557 if (address->solver_information == NULL)
1563 if (new == GNUNET_YES)
1565 mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1568 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1572 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1573 mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1574 mlpi->q_avg_i[c] = 0;
1575 mlpi->q_averaged[c] = 0.0;
1578 address->solver_information = mlpi;
1579 mlp->addresses_in_problem ++;
1580 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1582 /* Check for and add peer */
1583 struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1587 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1588 GNUNET_i2s (&address->peer));
1590 peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1595 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1601 memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1602 GNUNET_assert(address->prev == NULL);
1603 GNUNET_assert(address->next == NULL);
1604 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1605 GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1607 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1612 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1613 GNUNET_i2s (&address->peer));
1615 GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1617 update_quality (mlp, address);
1621 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1622 GNUNET_i2s (&address->peer));
1624 update_quality (mlp, address);
1628 if (new == GNUNET_YES)
1630 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1632 mlp_delete_problem (mlp);
1633 mlp_create_problem (mlp, addresses);
1634 mlp->presolver_required = GNUNET_YES;
1636 if (mlp->auto_solve == GNUNET_YES)
1637 GAS_mlp_solve_problem (mlp, &ctx);
1642 * Deletes a single address in the MLP problem
1644 * The MLP problem has to be recreated and the problem has to be resolved
1646 * @param solver the MLP Handle
1647 * @param addresses the address hashmap
1648 * the address has to be already removed from the hashmap
1649 * @param address the address to delete
1650 * @param session_only delete only session not whole address
1653 GAS_mlp_address_delete (void *solver,
1654 struct GNUNET_CONTAINER_MultiHashMap * addresses,
1655 struct ATS_Address *address,
1659 struct GAS_MLP_Handle *mlp = solver;
1661 GNUNET_assert (NULL != solver);
1662 GNUNET_assert (NULL != addresses);
1663 GNUNET_assert (NULL != address);
1665 /* TODO Delete address here */
1666 if (NULL != address->solver_information)
1668 GNUNET_free (address->solver_information);
1669 address->solver_information = NULL;
1672 /* Is this peer included in the problem? */
1673 if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1675 LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1678 LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1680 /* Problem size changed: new address for peer with pending request */
1681 mlp->mlp_prob_changed = GNUNET_YES;
1682 GAS_mlp_solve_problem (solver, addresses);
1686 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1687 struct GAS_MLP_SolutionContext ctx;
1689 /* Free resources */
1690 if (address->solver_information != NULL)
1692 GNUNET_free (address->solver_information);
1693 address->solver_information = NULL;
1695 mlp->addresses_in_problem --;
1696 GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1699 /* Remove from peer list */
1700 struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1701 GNUNET_assert (head != NULL);
1703 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1705 GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1706 if ((head->head == NULL) && (head->tail == NULL))
1708 /* No address for peer left, remove peer */
1710 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1712 GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1715 GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1718 /* Update problem */
1719 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1721 mlp_delete_problem (mlp);
1722 if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1724 mlp_create_problem (mlp, addresses);
1727 mlp->presolver_required = GNUNET_YES;
1728 if (mlp->auto_solve == GNUNET_YES)
1729 GAS_mlp_solve_problem (mlp, &ctx);
1736 * Find the active address in the set of addresses of a peer
1737 * @param cls destination
1738 * @param key peer id
1739 * @param value address
1743 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1746 struct ATS_Address *aa = (struct ATS_Address *) cls;
1747 struct ATS_Address *addr = value;
1748 struct MLP_information *mlpi = addr->solver_information;
1751 if (mlpi->n == GNUNET_YES)
1754 if (mlpi->b > (double) UINT32_MAX)
1755 aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1757 aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1758 aa->assigned_bw_in.value__ = htonl(0);
1766 * Get the preferred address for a specific peer
1768 * @param solver the MLP Handle
1769 * @param addresses address hashmap
1770 * @param peer the peer
1771 * @return suggested address
1773 const struct ATS_Address *
1774 GAS_mlp_get_preferred_address (void *solver,
1775 struct GNUNET_CONTAINER_MultiHashMap * addresses,
1776 const struct GNUNET_PeerIdentity *peer)
1778 struct GAS_MLP_Handle *mlp = solver;
1780 struct ATS_Address *res = NULL;
1782 GNUNET_assert (NULL != solver);
1783 GNUNET_assert (NULL != addresses);
1784 GNUNET_assert (NULL != peer);
1786 LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n",
1789 /* Is this peer included in the problem? */
1790 if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey)))
1792 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding peer `%s' to list of peers with requests\n",
1795 p = GNUNET_malloc (sizeof (struct ATS_Peer));
1797 GNUNET_CONTAINER_multihashmap_put (mlp->peers, &peer->hashPubKey, p, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
1799 /* Added new peer, we have to rebuild problem before solving */
1800 mlp->mlp_prob_changed = GNUNET_YES;
1802 GAS_mlp_solve_problem (mlp, addresses);
1804 /* Get prefered address */
1805 GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
1806 mlp_get_preferred_address_it, res);
1813 * Changes the preferences for a peer in the MLP problem
1815 * @param solver the MLP Handle
1816 * @param client client
1817 * @param peer the peer
1818 * @param kind the kind to change the preference
1819 * @param score the score
1822 GAS_mlp_address_change_preference (void *solver,
1824 const struct GNUNET_PeerIdentity *peer,
1825 enum GNUNET_ATS_PreferenceKind kind,
1828 //struct GAS_MLP_Handle *mlp = solver;
1830 LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n",
1835 GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1837 //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1838 //FIXME to finish implementation
1839 /* Here we have to do the matching */
1845 mlp_free_peers (void *cls, const struct GNUNET_HashCode *key, void *value)
1847 struct GNUNET_CONTAINER_MultiHashMap *map = cls;
1848 struct ATS_Peer *p = value;
1850 GNUNET_CONTAINER_multihashmap_remove (map, key, value);
1858 * Shutdown the MLP problem solving component
1860 * @param solver the solver handle
1863 GAS_mlp_done (void *solver)
1865 struct GAS_MLP_Handle *mlp = solver;
1866 struct ATS_Peer * peer;
1867 struct ATS_Address *addr;
1869 GNUNET_assert (mlp != NULL);
1871 LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n");
1873 if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1875 GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1876 mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1879 /* clean up peer list */
1880 peer = mlp->peer_head;
1881 while (peer != NULL)
1883 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1884 GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1885 for (addr = peer->head; NULL != addr; addr = peer->head)
1887 GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1888 GNUNET_free (addr->solver_information);
1889 addr->solver_information = NULL;
1892 peer = mlp->peer_head;
1894 mlp_delete_problem (mlp);
1896 GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &mlp_free_peers, mlp->peers);
1897 GNUNET_CONTAINER_multihashmap_destroy (mlp->peers);
1900 /* Clean up GLPK environment */
1904 LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n");
1909 * Init the MLP problem solving component
1911 * @param cfg the GNUNET_CONFIGURATION_Handle handle
1912 * @param stats the GNUNET_STATISTICS handle
1913 * @param network array of GNUNET_ATS_NetworkType with length dest_length
1914 * @param out_dest array of outbound quotas
1915 * @param in_dest array of outbound quota
1916 * @param dest_length array length for quota arrays
1917 * @param bw_changed_cb callback for changed bandwidth amounts
1918 * @param bw_changed_cb_cls cls for callback
1919 * @return struct GAS_MLP_Handle on success, NULL on fail
1922 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1923 const struct GNUNET_STATISTICS_Handle *stats,
1925 unsigned long long *out_dest,
1926 unsigned long long *in_dest,
1928 GAS_bandwidth_changed_cb bw_changed_cb,
1929 void *bw_changed_cb_cls)
1931 struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1936 unsigned long long tmp;
1939 struct GNUNET_TIME_Relative i_exec;
1944 struct GNUNET_TIME_Relative max_duration;
1945 long long unsigned int max_iterations;
1947 /* Init GLPK environment */
1948 int res = glp_init_env();
1951 LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1952 "initialization successful");
1955 LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1956 "environment is already initialized");
1959 LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1960 "initialization failed (insufficient memory)");
1965 LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1966 "initialization failed (unsupported programming model)");
1975 mlp->BIG_M = (double) BIG_M_VALUE;
1977 /* Get timeout for iterations */
1978 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MLP_MAX_DURATION", &max_duration))
1980 max_duration = MLP_MAX_EXEC_DURATION;
1983 /* Get maximum number of iterations */
1984 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations))
1986 max_iterations = MLP_MAX_ITERATIONS;
1989 /* Get diversity coefficient from configuration */
1990 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1991 "MLP_COEFFICIENT_D",
1993 D = (double) tmp / 100;
1997 /* Get proportionality coefficient from configuration */
1998 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1999 "MLP_COEFFICIENT_R",
2001 R = (double) tmp / 100;
2005 /* Get utilization coefficient from configuration */
2006 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2007 "MLP_COEFFICIENT_U",
2009 U = (double) tmp / 100;
2013 /* Get quality metric coefficients from configuration */
2015 int i_distance = NaN;
2016 int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
2017 for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
2019 /* initialize quality coefficients with default value 1.0 */
2020 mlp->pv.co_Q[c] = DEFAULT_QUALITY;
2022 mlp->pv.q[c] = q[c];
2023 if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
2025 if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
2029 if ((i_delay != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2030 "MLP_COEFFICIENT_QUALITY_DELAY",
2033 mlp->pv.co_Q[i_delay] = (double) tmp / 100;
2035 mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY;
2037 if ((i_distance != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2038 "MLP_COEFFICIENT_QUALITY_DISTANCE",
2040 mlp->pv.co_Q[i_distance] = (double) tmp / 100;
2042 mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY;
2044 /* Get minimum bandwidth per used address from configuration */
2045 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2046 "MLP_MIN_BANDWIDTH",
2051 b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2054 /* Get minimum number of connections from configuration */
2055 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2056 "MLP_MIN_CONNECTIONS",
2060 n_min = DEFAULT_MIN_CONNECTIONS;
2062 /* Init network quotas */
2063 int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
2064 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
2067 for (c2 = 0; c2 < dest_length; c2++)
2069 if (quotas[c] == network[c2])
2071 mlp->pv.quota_index[c] = network[c2];
2072 mlp->pv.quota_out[c] = out_dest[c2];
2073 mlp->pv.quota_in[c] = in_dest[c2];
2075 LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n",
2076 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2077 mlp->pv.quota_out[c],
2078 mlp->pv.quota_in[c]);
2083 /* Check if defined quota could make problem unsolvable */
2084 if ((n_min * b_min) > mlp->pv.quota_out[c])
2086 LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2087 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2088 mlp->pv.quota_out[c],
2090 mlp->pv.quota_out[c] = (n_min * b_min);
2092 if ((n_min * b_min) > mlp->pv.quota_in[c])
2094 LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2095 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2096 mlp->pv.quota_in[c],
2098 mlp->pv.quota_in[c] = (n_min * b_min);
2101 /* Check if bandwidth is too big to make problem solvable */
2102 if (mlp->BIG_M < mlp->pv.quota_out[c])
2104 LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2105 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2106 mlp->pv.quota_out[c],
2108 mlp->pv.quota_out[c] = mlp->BIG_M;
2110 if (mlp->BIG_M < mlp->pv.quota_in[c])
2112 LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2113 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2114 mlp->pv.quota_in[c],
2116 mlp->pv.quota_in[c] = mlp->BIG_M;
2119 if (GNUNET_NO == found)
2121 mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2122 mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2123 LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"),
2124 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2125 mlp->pv.quota_in[c],
2126 mlp->pv.quota_out[c]);
2130 /* Get minimum number of connections from configuration */
2131 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
2132 "MLP_EXEC_INTERVAL",
2134 mlp->exec_interval = i_exec;
2136 mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
2138 /* Assign options to handle */
2139 mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
2140 mlp->bw_changed_cb = bw_changed_cb;
2141 mlp->bw_changed_cb_cls = bw_changed_cb_cls;
2142 /* Setting MLP Input variables */
2146 mlp->pv.b_min = b_min;
2147 mlp->pv.n_min = n_min;
2148 mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount;
2150 mlp->semaphore = GNUNET_NO;
2151 mlp->max_iterations = max_iterations;
2152 mlp->max_exec_duration = max_duration;
2153 mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
2154 mlp->auto_solve = GNUNET_YES;
2155 mlp->mlp_prob_changed = GNUNET_NO;
2156 mlp->mlp_prob_updated = GNUNET_NO;
2158 mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO);
2161 /* Redirect GLPK output to GNUnet logging */
2162 glp_term_hook (&mlp_term_hook, (void *) mlp);
2164 /* Init LP solving parameters */
2165 glp_init_smcp(&mlp->control_param_lp);
2166 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2168 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2170 mlp->control_param_lp.it_lim = max_iterations;
2171 mlp->control_param_lp.tm_lim = max_duration.rel_value;
2173 /* Init MLP solving parameters */
2174 glp_init_iocp(&mlp->control_param_mlp);
2175 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2177 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2179 mlp->control_param_mlp.tm_lim = max_duration.rel_value;
2181 LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2186 /* end of gnunet-service-ats_addresses_mlp.c */