aboutsummaryrefslogtreecommitdiff
path: root/src/ats/plugin_ats_mlp.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/ats/plugin_ats_mlp.c')
-rw-r--r--src/ats/plugin_ats_mlp.c2924
1 files changed, 0 insertions, 2924 deletions
diff --git a/src/ats/plugin_ats_mlp.c b/src/ats/plugin_ats_mlp.c
deleted file mode 100644
index 6ab823b1e..000000000
--- a/src/ats/plugin_ats_mlp.c
+++ /dev/null
@@ -1,2924 +0,0 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2011-2014 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
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 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
21/**
22 * @file ats/plugin_ats_mlp.c
23 * @brief ats mlp problem solver
24 * @author Matthias Wachs
25 * @author Christian Grothoff
26 */
27#include "platform.h"
28#include "gnunet_util_lib.h"
29#include "gnunet_ats_service.h"
30#include "gnunet_ats_plugin.h"
31#include "gnunet-service-ats_addresses.h"
32#include "gnunet_statistics_service.h"
33#include <float.h>
34#include <glpk.h>
35
36
37#define BIG_M_VALUE (UINT32_MAX) / 10
38#define BIG_M_STRING "unlimited"
39
40#define MLP_AVERAGING_QUEUE_LENGTH 3
41
42#define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply ( \
43 GNUNET_TIME_UNIT_SECONDS, 10)
44#define MLP_MAX_ITERATIONS 4096
45
46#define MLP_DEFAULT_D 1.0
47#define MLP_DEFAULT_R 1.0
48#define MLP_DEFAULT_U 1.0
49#define MLP_DEFAULT_QUALITY 1.0
50#define MLP_DEFAULT_MIN_CONNECTIONS 4
51#define MLP_DEFAULT_PEER_PREFERENCE 1.0
52
53#define MLP_NaN -1
54#define MLP_UNDEFINED 0
55#define GLP_YES 1.0
56#define GLP_NO 0.0
57
58enum MLP_Output_Format
59{
60 MLP_MPS,
61 MLP_CPLEX,
62 MLP_GLPK
63};
64
65
66enum QualityMetrics
67{
68 RQ_QUALITY_METRIC_DELAY = 0,
69 RQ_QUALITY_METRIC_DISTANCE = 1,
70 RQ_QUALITY_METRIC_COUNT = 2
71};
72
73
74static const char *
75print_quality_type (enum QualityMetrics qm)
76{
77 switch (qm)
78 {
79 case RQ_QUALITY_METRIC_DELAY:
80 return "delay";
81
82 case RQ_QUALITY_METRIC_DISTANCE:
83 return "distance";
84
85 default:
86 GNUNET_break (0);
87 return NULL;
88 }
89}
90
91
92struct MLP_Solution
93{
94 int lp_res;
95 int lp_presolv;
96 int mip_res;
97 int mip_presolv;
98
99 double lp_objective_value;
100 double mlp_objective_value;
101 double mlp_gap;
102 double lp_mlp_gap;
103
104 int p_elements;
105 int p_cols;
106 int p_rows;
107
108 int n_peers;
109 int n_addresses;
110};
111
112struct ATS_Peer
113{
114 struct GNUNET_PeerIdentity id;
115
116 /* Was this peer already added to the current problem? */
117 int processed;
118
119 /* constraint 2: 1 address per peer*/
120 unsigned int r_c2;
121
122 /* constraint 9: relativity */
123 unsigned int r_c9;
124
125 /* Legacy preference value */
126 double f;
127};
128
129struct MLP_Problem
130{
131 /**
132 * GLPK (MLP) problem object
133 */
134 glp_prob *prob;
135
136 /* Number of addresses in problem */
137 unsigned int num_addresses;
138 /* Number of peers in problem */
139 unsigned int num_peers;
140 /* Number of elements in problem matrix */
141 unsigned int num_elements;
142
143 /* Row index constraint 2: */
144 unsigned int r_c2;
145 /* Row index constraint 4: minimum connections */
146 unsigned int r_c4;
147 /* Row index constraint 6: maximize diversity */
148 unsigned int r_c6;
149 /* Row index constraint 8: utilization*/
150 unsigned int r_c8;
151 /* Row index constraint 9: relativity*/
152 unsigned int r_c9;
153 /* Row indices quality metrics */
154 int r_q[RQ_QUALITY_METRIC_COUNT];
155 /* Row indices ATS network quotas */
156 int r_quota[GNUNET_NT_COUNT];
157
158 /* Column index Diversity (D) column */
159 int c_d;
160 /* Column index Utilization (U) column */
161 int c_u;
162 /* Column index Proportionality (R) column */
163 int c_r;
164 /* Column index quality metrics */
165 int c_q[RQ_QUALITY_METRIC_COUNT];
166
167 /* Problem matrix */
168 /* Current index */
169 unsigned int ci;
170 /* Row index array */
171 int *ia;
172 /* Column index array */
173 int *ja;
174 /* Column index value */
175 double *ar;
176};
177
178struct MLP_Variables
179{
180 /* Big M value for bandwidth capping */
181 double BIG_M;
182
183 /* MIP Gap */
184 double mip_gap;
185
186 /* LP MIP Gap */
187 double lp_mip_gap;
188
189 /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
190 int m_q;
191
192 /* Number of quality metrics */
193 int m_rc;
194
195 /* Quality metric coefficients*/
196 double co_Q[RQ_QUALITY_METRIC_COUNT];
197
198 /* Ressource costs coefficients*/
199 double co_RC[RQ_QUALITY_METRIC_COUNT];
200
201 /* Diversity coefficient */
202 double co_D;
203
204 /* Utility coefficient */
205 double co_U;
206
207 /* Relativity coefficient */
208 double co_R;
209
210 /* Minimum bandwidth assigned to an address */
211 unsigned int b_min;
212
213 /* Minimum number of addresses with bandwidth assigned */
214 unsigned int n_min;
215
216 /* Quotas */
217 /* Array mapping array index to ATS network */
218 int quota_index[GNUNET_NT_COUNT];
219 /* Outbound quotas */
220 unsigned long long quota_out[GNUNET_NT_COUNT];
221 /* Inbound quotas */
222
223 unsigned long long quota_in[GNUNET_NT_COUNT];
224
225 /* ATS ressource costs
226 * array with GNUNET_ATS_QualityPropertiesCount elements
227 * contains mapping to GNUNET_ATS_Property
228 * */
229 int rc[RQ_QUALITY_METRIC_COUNT];
230};
231
232/**
233 * MLP Handle
234 */
235struct GAS_MLP_Handle
236{
237 struct GNUNET_ATS_PluginEnvironment *env;
238
239 /**
240 * Exclude peer from next result propagation
241 */
242 const struct GNUNET_PeerIdentity *exclude_peer;
243
244 /**
245 * Encapsulation for the MLP problem
246 */
247 struct MLP_Problem p;
248
249 /**
250 * Encapsulation for the MLP problem variables
251 */
252 struct MLP_Variables pv;
253
254 /**
255 * Encapsulation for the MLP solution
256 */
257 struct MLP_Solution ps;
258
259 /**
260 * Bulk lock
261 */
262 int stat_bulk_lock;
263
264 /**
265 * Number of changes while solver was locked
266 */
267 int stat_bulk_requests;
268
269 /**
270 * GLPK LP control parameter
271 */
272 glp_smcp control_param_lp;
273
274 /**
275 * GLPK LP control parameter
276 */
277 glp_iocp control_param_mlp;
278
279 /**
280 * Peers with pending address requests
281 */
282 struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
283
284 /**
285 * Was the problem updated since last solution
286 */
287 int stat_mlp_prob_updated;
288
289 /**
290 * Has the problem size changed since last solution
291 */
292 int stat_mlp_prob_changed;
293
294 /**
295 * Solve the problem automatically when updates occur?
296 * Default: GNUNET_YES
297 * Can be disabled for test and measurements
298 */
299 int opt_mlp_auto_solve;
300
301 /**
302 * Write all MILP problems to a MPS file
303 */
304 int opt_dump_problem_all;
305
306 /**
307 * Write all MILP problem solutions to a file
308 */
309 int opt_dump_solution_all;
310
311 /**
312 * Write MILP problems to a MPS file when solver fails
313 */
314 int opt_dump_problem_on_fail;
315
316 /**
317 * Write MILP problem solutions to a file when solver fails
318 */
319 int opt_dump_solution_on_fail;
320
321 /**
322 * solve feasibility only
323 */
324 int opt_dbg_feasibility_only;
325
326 /**
327 * solve autoscale the problem
328 */
329 int opt_dbg_autoscale_problem;
330
331 /**
332 * use the intopt presolver instead of simplex
333 */
334 int opt_dbg_intopt_presolver;
335
336 /**
337 * Print GLPK output
338 */
339 int opt_dbg_glpk_verbose;
340
341 /**
342 * solve autoscale the problem
343 */
344 int opt_dbg_optimize_relativity;
345
346 /**
347 * solve autoscale the problem
348 */
349 int opt_dbg_optimize_diversity;
350
351 /**
352 * solve autoscale the problem
353 */
354 int opt_dbg_optimize_quality;
355
356 /**
357 * solve autoscale the problem
358 */
359 int opt_dbg_optimize_utility;
360
361
362 /**
363 * Output format
364 */
365 enum MLP_Output_Format opt_log_format;
366};
367
368/**
369 * Address specific MLP information
370 */
371struct MLP_information
372{
373 /**
374 * Bandwidth assigned outbound
375 */
376 uint32_t b_out;
377
378 /**
379 * Bandwidth assigned inbound
380 */
381 uint32_t b_in;
382
383 /**
384 * Address selected
385 */
386 int n;
387
388 /**
389 * bandwidth column index
390 */
391 signed int c_b;
392
393 /**
394 * address usage column
395 */
396 signed int c_n;
397
398 /* row indexes */
399
400 /**
401 * constraint 1: bandwidth capping
402 */
403 unsigned int r_c1;
404
405 /**
406 * constraint 3: minimum bandwidth
407 */
408 unsigned int r_c3;
409};
410
411
412
413/**
414 *
415 * NOTE: Do not modify this documentation. This documentation is based on
416 * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
417 * use build_txt.sh to generate plaintext output
418 *
419 * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
420 * optimizing an mixed integer programming problem. The MLP solver uses a
421 * number of constraints to find the best adddress for a peer and an optimal
422 * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
423 * MLP problem.
424 *
425 * We defined a constraint system to find an optimal bandwidth assignment.
426 * This constraint system uses as an input data addresses, bandwidth quotas,
427 * preferences and quality values. This constraint system is stored in an
428 * matrix based equotation system.
429 *
430 * 5 Using GLPK
431 *
432 * A (M)LP problem consists of a target function to optimizes, constraints
433 * and rows and columns. FIXME GLP uses three arrays to index the matrix: two
434 * integer arrays storing the row and column indices in the matrix and an
435 * float array to store the coeeficient.
436 *
437 * To solve the problem we first find an initial solution for the LP problem
438 * using the LP solver and then find an MLP solution based on this solution
439 * using the MLP solver.
440 *
441 * Solving (M)LP problems has the property that finding an initial solution
442 * for the LP problem is computationally expensive and finding the MLP
443 * solution is cheaper. This is especially interesting an existing LP
444 * solution can be reused if only coefficients in the matrix have changed
445 * (addresses updated). Only when the problem size changes (addresses added
446 * or deleted) a new LP solution has to be found.
447 *
448 * Intended usage
449 * The mlp solver solves the bandwidth assignment problem only on demand when
450 * an address suggestion is requested. When an address is requested mlp the
451 * solves the mlp problem and if the active address or the bandwidth assigned
452 * changes it calls the callback to addresses. The mlp solver gets notified
453 * about new addresses (adding sessions), removed addresses (address
454 * deletions) and address updates. To benefit from the mlp properties
455 * mentioned in section 5 the solver rembers if since the last solution
456 * addresses were added or deleted (problem size changed, problem has to be
457 * rebuild and solved from sratch) or if addresses were updated and the
458 * existing solution can be reused.
459 *
460 * 5.1 Input data
461 *
462 * The quotas for each network segment are passed by addresses. MLP can be
463 * adapted using configuration settings and uses the following parameters:
464 * * MLP_MAX_DURATION:
465 * Maximum duration for a MLP solution procees (default: 3 sec.)
466 * * MLP_MAX_ITERATIONS:
467 * Maximum number of iterations for a MLP solution process (default:
468 * 1024)
469 * * MLP_MIN_CONNECTIONS:
470 * Minimum number of desired connections (default: 4)
471 * * MLP_MIN_BANDWIDTH:
472 * Minimum amount of bandwidth assigned to an address (default: 1024)
473 * * MLP_COEFFICIENT_D:
474 * Diversity coefficient (default: 1.0)
475 * * MLP_COEFFICIENT_R:
476 * Relativity coefficient (default: 1.0)
477 * * MLP_COEFFICIENT_U:
478 * Utilization coefficient (default: 1.0)
479 * * MLP_COEFFICIENT_D:
480 * Diversity coefficient (default: 1.0)
481 * * MLP_COEFFICIENT_QUALITY_DELAY:
482 * Quality delay coefficient (default: 1.0)
483 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
484 * Quality distance coefficient (default: 1.0)
485 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
486 * Quality distance coefficient (default: 1.0)
487 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
488 * Quality distance coefficient (default: 1.0)
489 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
490 * Quality distance coefficient (default: 1.0)
491 *
492 * 5.2 Data structures used
493 *
494 * mlp has for each known peer a struct ATS_Peer containing information about
495 * a specific peer. The address field solver_information contains information
496 * about the mlp properties of this address.
497 *
498 * 5.3 Initializing
499 *
500 * During initialization mlp initializes the GLPK libray used to solve the
501 * MLP problem: it initializes the glpk environment and creates an initial LP
502 * problem. Next it loads the configuration values from the configuration or
503 * uses the default values configured in -addresses_mlp.h. The quotas used
504 * are given by addresses but may have to be adjusted. mlp uses a upper limit
505 * for the bandwidth assigned called BIG M and a minimum amount of bandwidth
506 * an address gets assigned as well as a minium desired number of
507 * connections. If the configured quota is bigger than BIG M, it is reduced
508 * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
509 * *MLP_MIN_BANDWIDTH it is increased to this value.
510 *
511 * 5.4 Shutdown
512
513 */
514
515#define LOG(kind, ...) GNUNET_log_from (kind, "ats-mlp", __VA_ARGS__)
516
517/**
518 * Print debug output for mlp problem creation
519 */
520#define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
521
522
523/**
524 * Intercept GLPK terminal output
525 * @param info the mlp handle
526 * @param s the string to print
527 * @return 0: glpk prints output on terminal, 0 != surpress output
528 */
529static int
530mlp_term_hook (void *info, const char *s)
531{
532 struct GAS_MLP_Handle *mlp = info;
533
534 if (mlp->opt_dbg_glpk_verbose)
535 LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
536 return 1;
537}
538
539
540/**
541 * Reset peers for next problem creation
542 *
543 * @param cls not used
544 * @param key the key
545 * @param value ATS_Peer
546 * @return #GNUNET_OK
547 */
548static int
549reset_peers (void *cls,
550 const struct GNUNET_PeerIdentity *key,
551 void *value)
552{
553 struct ATS_Peer *peer = value;
554
555 peer->processed = GNUNET_NO;
556 return GNUNET_OK;
557}
558
559/**
560 * Delete the MLP problem and free the constrain matrix
561 *
562 * @param mlp the MLP handle
563 */
564static void
565mlp_delete_problem (struct GAS_MLP_Handle *mlp)
566{
567 int c;
568
569 if (mlp == NULL)
570 return;
571 if (mlp->p.prob != NULL)
572 {
573 glp_delete_prob (mlp->p.prob);
574 mlp->p.prob = NULL;
575 }
576
577 /* delete row index */
578 if (mlp->p.ia != NULL)
579 {
580 GNUNET_free (mlp->p.ia);
581 mlp->p.ia = NULL;
582 }
583
584 /* delete column index */
585 if (mlp->p.ja != NULL)
586 {
587 GNUNET_free (mlp->p.ja);
588 mlp->p.ja = NULL;
589 }
590
591 /* delete coefficients */
592 if (mlp->p.ar != NULL)
593 {
594 GNUNET_free (mlp->p.ar);
595 mlp->p.ar = NULL;
596 }
597 mlp->p.ci = 0;
598 mlp->p.prob = NULL;
599
600 mlp->p.c_d = MLP_UNDEFINED;
601 mlp->p.c_r = MLP_UNDEFINED;
602 mlp->p.r_c2 = MLP_UNDEFINED;
603 mlp->p.r_c4 = MLP_UNDEFINED;
604 mlp->p.r_c6 = MLP_UNDEFINED;
605 mlp->p.r_c9 = MLP_UNDEFINED;
606 for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
607 mlp->p.r_q[c] = MLP_UNDEFINED;
608 for (c = 0; c < GNUNET_NT_COUNT; c++)
609 mlp->p.r_quota[c] = MLP_UNDEFINED;
610 mlp->p.ci = MLP_UNDEFINED;
611
612
613 GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
614 &reset_peers, NULL);
615}
616
617
618/**
619 * Translate glpk status error codes to text
620 * @param retcode return code
621 * @return string with result
622 */
623static const char *
624mlp_status_to_string (int retcode)
625{
626 switch (retcode)
627 {
628 case GLP_UNDEF:
629 return "solution is undefined";
630
631 case GLP_FEAS:
632 return "solution is feasible";
633
634 case GLP_INFEAS:
635 return "solution is infeasible";
636
637 case GLP_NOFEAS:
638 return "no feasible solution exists";
639
640 case GLP_OPT:
641 return "solution is optimal";
642
643 case GLP_UNBND:
644 return "solution is unbounded";
645
646 default:
647 GNUNET_break (0);
648 return "unknown error";
649 }
650}
651
652
653/**
654 * Translate glpk solver error codes to text
655 * @param retcode return code
656 * @return string with result
657 */
658static const char *
659mlp_solve_to_string (int retcode)
660{
661 switch (retcode)
662 {
663 case 0:
664 return "ok";
665
666 case GLP_EBADB:
667 return "invalid basis";
668
669 case GLP_ESING:
670 return "singular matrix";
671
672 case GLP_ECOND:
673 return "ill-conditioned matrix";
674
675 case GLP_EBOUND:
676 return "invalid bounds";
677
678 case GLP_EFAIL:
679 return "solver failed";
680
681 case GLP_EOBJLL:
682 return "objective lower limit reached";
683
684 case GLP_EOBJUL:
685 return "objective upper limit reached";
686
687 case GLP_EITLIM:
688 return "iteration limit exceeded";
689
690 case GLP_ETMLIM:
691 return "time limit exceeded";
692
693 case GLP_ENOPFS:
694 return "no primal feasible solution";
695
696 case GLP_ENODFS:
697 return "no dual feasible solution";
698
699 case GLP_EROOT:
700 return "root LP optimum not provided";
701
702 case GLP_ESTOP:
703 return "search terminated by application";
704
705 case GLP_EMIPGAP:
706 return "relative mip gap tolerance reached";
707
708 case GLP_ENOFEAS:
709 return "no dual feasible solution";
710
711 case GLP_ENOCVG:
712 return "no convergence";
713
714 case GLP_EINSTAB:
715 return "numerical instability";
716
717 case GLP_EDATA:
718 return "invalid data";
719
720 case GLP_ERANGE:
721 return "result out of range";
722
723 default:
724 GNUNET_break (0);
725 return "unknown error";
726 }
727}
728
729
730struct CountContext
731{
732 const struct GNUNET_CONTAINER_MultiPeerMap *map;
733 int result;
734};
735
736static int
737mlp_create_problem_count_addresses_it (void *cls,
738 const struct GNUNET_PeerIdentity *key,
739 void *value)
740{
741 struct CountContext *cctx = cls;
742
743 /* Check if we have to add this peer due to a pending request */
744 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
745 cctx->result++;
746 return GNUNET_OK;
747}
748
749
750static int
751mlp_create_problem_count_addresses (const struct
752 GNUNET_CONTAINER_MultiPeerMap *
753 requested_peers,
754 const struct
755 GNUNET_CONTAINER_MultiPeerMap *addresses)
756{
757 struct CountContext cctx;
758
759 cctx.map = requested_peers;
760 cctx.result = 0;
761 GNUNET_CONTAINER_multipeermap_iterate (addresses,
762 &mlp_create_problem_count_addresses_it,
763 &cctx);
764 return cctx.result;
765}
766
767
768static int
769mlp_create_problem_count_peers_it (void *cls,
770 const struct GNUNET_PeerIdentity *key,
771 void *value)
772{
773 struct CountContext *cctx = cls;
774
775 /* Check if we have to addresses for the requested peer */
776 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
777 cctx->result++;
778 return GNUNET_OK;
779}
780
781
782static int
783mlp_create_problem_count_peers (const struct
784 GNUNET_CONTAINER_MultiPeerMap *requested_peers,
785 const struct
786 GNUNET_CONTAINER_MultiPeerMap *addresses)
787{
788 struct CountContext cctx;
789
790 cctx.map = addresses;
791 cctx.result = 0;
792 GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
793 &mlp_create_problem_count_peers_it,
794 &cctx);
795 return cctx.result;
796}
797
798
799/**
800 * Updates an existing value in the matrix
801 *
802 * Extract the row, updates the value and updates the row in the problem
803 *
804 * @param p the mlp problem
805 * @param row the row to create the value in
806 * @param col the column to create the value in
807 * @param val the value to set
808 * @param line calling line for debbuging
809 * @return GNUNET_YES value changed, GNUNET_NO value did not change, GNUNET_SYSERR
810 * on error
811 */
812static int
813mlp_create_problem_update_value (struct MLP_Problem *p,
814 int row, int col, double val,
815 int line)
816{
817 int c_cols;
818 int c_elems;
819 int c1;
820 int res;
821 int found;
822 double *val_array;
823 int *ind_array;
824
825 GNUNET_assert (NULL != p->prob);
826
827 /* Get number of columns and prepare data structure */
828 c_cols = glp_get_num_cols (p->prob);
829 if (0 >= c_cols)
830 return GNUNET_SYSERR;
831
832 val_array = GNUNET_malloc ((c_cols + 1) * sizeof(double));
833 GNUNET_assert (NULL != val_array);
834 ind_array = GNUNET_malloc ((c_cols + 1) * sizeof(int));
835 GNUNET_assert (NULL != ind_array);
836 /* Extract the row */
837
838 /* Update the value */
839 c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
840 found = GNUNET_NO;
841 for (c1 = 1; c1 < (c_elems + 1); c1++)
842 {
843 if (ind_array[c1] == col)
844 {
845 found = GNUNET_YES;
846 break;
847 }
848 }
849 if (GNUNET_NO == found)
850 {
851 ind_array[c_elems + 1] = col;
852 val_array[c_elems + 1] = val;
853 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
854 glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
855 val);
856 glp_set_mat_row (p->prob, row, c_elems + 1, ind_array, val_array);
857 GNUNET_free (ind_array);
858 GNUNET_free (val_array);
859 return GNUNET_YES;
860 }
861 else
862 {
863 /* Update value */
864 LOG (GNUNET_ERROR_TYPE_DEBUG,
865 "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
866 glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
867 val_array[c1], val);
868 if (val != val_array[c1])
869 res = GNUNET_YES;
870 else
871 res = GNUNET_NO;
872 val_array[c1] = val;
873 /* Update the row in the matrix */
874 glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
875 }
876
877 GNUNET_free (ind_array);
878 GNUNET_free (val_array);
879 return res;
880}
881
882/**
883 * Creates a new value in the matrix
884 *
885 * Sets the row and column index in the problem array and increments the
886 * position field
887 *
888 * @param p the mlp problem
889 * @param row the row to create the value in
890 * @param col the column to create the value in
891 * @param val the value to set
892 * @param line calling line for debbuging
893 */
894static void
895mlp_create_problem_set_value (struct MLP_Problem *p,
896 int row, int col, double val,
897 int line)
898{
899 if ((p->ci) >= p->num_elements)
900 {
901 LOG (GNUNET_ERROR_TYPE_DEBUG,
902 "[P]: line %u: Request for index %u bigger than array size of %u\n",
903 line, p->ci + 1, p->num_elements);
904 GNUNET_break (0);
905 return;
906 }
907 if ((0 == row) || (0 == col))
908 {
909 GNUNET_break (0);
910 LOG (GNUNET_ERROR_TYPE_ERROR,
911 "[P]: Invalid call from line %u: row = %u, col = %u\n",
912 line, row, col);
913 }
914 p->ia[p->ci] = row;
915 p->ja[p->ci] = col;
916 p->ar[p->ci] = val;
917#if DEBUG_MLP_PROBLEM_CREATION
918 LOG (GNUNET_ERROR_TYPE_DEBUG,
919 "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n",
920 line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
921#endif
922 p->ci++;
923}
924
925static int
926mlp_create_problem_create_column (struct MLP_Problem *p, char *name,
927 unsigned int type, unsigned int bound, double
928 lb, double ub,
929 double coef)
930{
931 int col = glp_add_cols (p->prob, 1);
932
933 glp_set_col_name (p->prob, col, name);
934 glp_set_col_bnds (p->prob, col, bound, lb, ub);
935 glp_set_col_kind (p->prob, col, type);
936 glp_set_obj_coef (p->prob, col, coef);
937#if DEBUG_MLP_PROBLEM_CREATION
938 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
939 col, name, coef);
940#endif
941 return col;
942}
943
944static int
945mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name,
946 unsigned int bound, double lb, double ub)
947{
948 char *op;
949 int row = glp_add_rows (p->prob, 1);
950
951 /* set row name */
952 glp_set_row_name (p->prob, row, name);
953 /* set row bounds: <= 0 */
954 glp_set_row_bnds (p->prob, row, bound, lb, ub);
955 switch (bound)
956 {
957 case GLP_UP:
958 GNUNET_asprintf (&op, "-inf <= x <= %.2f", ub);
959 break;
960
961 case GLP_DB:
962 GNUNET_asprintf (&op, "%.2f <= x <= %.2f", lb, ub);
963 break;
964
965 case GLP_FX:
966 GNUNET_asprintf (&op, "%.2f == x == %.2f", lb, ub);
967 break;
968
969 case GLP_LO:
970 GNUNET_asprintf (&op, "%.2f <= x <= inf", lb);
971 break;
972
973 default:
974 GNUNET_asprintf (&op, "ERROR");
975 break;
976 }
977#if DEBUG_MLP_PROBLEM_CREATION
978 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
979 row, name, op);
980#endif
981 GNUNET_free (op);
982 return row;
983}
984
985/**
986 * Create the
987 * - address columns b and n
988 * - address dependent constraint rows c1, c3
989 * - peer dependent rows c2 and c9
990 * - Set address dependent entries in problem matrix as well
991 */
992static int
993mlp_create_problem_add_address_information (void *cls,
994 const struct
995 GNUNET_PeerIdentity *key,
996 void *value)
997{
998 struct GAS_MLP_Handle *mlp = cls;
999 struct MLP_Problem *p = &mlp->p;
1000 struct ATS_Address *address = value;
1001 struct ATS_Peer *peer;
1002 struct MLP_information *mlpi;
1003 char *name;
1004 double cur_bigm;
1005 uint32_t addr_net;
1006 uint32_t addr_net_index;
1007 unsigned long long max_quota;
1008 int c;
1009
1010 /* Check if we have to add this peer due to a pending request */
1011 if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers,
1012 key))
1013 return GNUNET_OK;
1014
1015 mlpi = address->solver_information;
1016 if (NULL == mlpi)
1017 {
1018 fprintf (stderr, "%s %p\n", GNUNET_i2s (&address->peer), address);
1019 GNUNET_break (0);
1020 return GNUNET_OK;
1021 }
1022
1023 addr_net = address->properties.scope;
1024 for (addr_net_index = 0; addr_net_index < GNUNET_NT_COUNT; addr_net_index++)
1025 {
1026 if (mlp->pv.quota_index[addr_net_index] == addr_net)
1027 break;
1028 }
1029
1030 if (addr_net_index >= GNUNET_NT_COUNT)
1031 {
1032 GNUNET_break (0);
1033 return GNUNET_OK;
1034 }
1035
1036 max_quota = 0;
1037 for (c = 0; c < GNUNET_NT_COUNT; c++)
1038 {
1039 if (mlp->pv.quota_out[c] > max_quota)
1040 max_quota = mlp->pv.quota_out[c];
1041 if (mlp->pv.quota_in[c] > max_quota)
1042 max_quota = mlp->pv.quota_in[c];
1043 }
1044 if (max_quota > mlp->pv.BIG_M)
1045 cur_bigm = (double) mlp->pv.BIG_M;
1046 else
1047 cur_bigm = max_quota;
1048
1049
1050 /* Get peer */
1051 peer = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, key);
1052 GNUNET_assert (NULL != peer);
1053 if (peer->processed == GNUNET_NO)
1054 {
1055 /* Add peer dependent constraints */
1056 /* Add c2) One address active per peer */
1057 GNUNET_asprintf (&name, "c2_%s", GNUNET_i2s (&address->peer));
1058 peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0,
1059 1.0);
1060 GNUNET_free (name);
1061 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1062 {
1063 if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1064 {
1065 /* Add c9) Relativity */
1066 GNUNET_asprintf (&name, "c9_%s", GNUNET_i2s (&address->peer));
1067 peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0,
1068 0.0);
1069 GNUNET_free (name);
1070 /* c9) set coefficient */
1071 mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f,
1072 __LINE__);
1073 }
1074 }
1075 peer->processed = GNUNET_YES;
1076 }
1077
1078 /* Reset addresses' solver information */
1079 mlpi->c_b = 0;
1080 mlpi->c_n = 0;
1081 mlpi->n = 0;
1082 mlpi->r_c1 = 0;
1083 mlpi->r_c3 = 0;
1084
1085 /* Add bandwidth column */
1086 GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer),
1087 address->plugin, address);
1088 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1089 {
1090 mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0,
1091 0.0, 0.0);
1092 }
1093 else
1094 {
1095 /* Maximize for bandwidth assignment in feasibility testing */
1096 mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0,
1097 0.0, 1.0);
1098 }
1099 GNUNET_free (name);
1100
1101 /* Add address active column */
1102 GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer),
1103 address->plugin, address);
1104 mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0,
1105 1.0, 0.0);
1106 GNUNET_free (name);
1107
1108 /* Add address dependent constraints */
1109 /* Add c1) bandwidth capping: b_t + (-M) * n_t <= 0 */
1110 GNUNET_asprintf (&name, "c1_%s_%s_%p", GNUNET_i2s (&address->peer),
1111 address->plugin, address);
1112 mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
1113 GNUNET_free (name);
1114 /* c1) set b = 1 coefficient */
1115 mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1116 /* c1) set n = - min (M, quota) coefficient */
1117 cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
1118 if (cur_bigm > mlp->pv.BIG_M)
1119 cur_bigm = (double) mlp->pv.BIG_M;
1120 mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1121
1122 /* Add constraint c 3) minimum bandwidth
1123 * b_t + (-n_t * b_min) >= 0
1124 * */
1125 GNUNET_asprintf (&name, "c3_%s_%s_%p", GNUNET_i2s (&address->peer),
1126 address->plugin, address);
1127 mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1128 GNUNET_free (name);
1129
1130 /* c3) set b = 1 coefficient */
1131 mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1132 /* c3) set n = -b_min coefficient */
1133 mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n,
1134 -((double ) mlp->pv.b_min), __LINE__);
1135
1136
1137 /* Set coefficient entries in invariant rows */
1138
1139 /* Feasbility */
1140
1141 /* c 4) minimum connections */
1142 mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
1143 /* c 2) 1 address peer peer */
1144 mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1145 /* c 10) obey network specific quotas
1146 * (1)*b_1 + ... + (1)*b_m <= quota_n
1147 */
1148 mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1,
1149 __LINE__);
1150
1151 /* Optimality */
1152 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1153 {
1154 /* c 6) maximize diversity */
1155 mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
1156 /* c 9) relativity */
1157 if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1158 mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1159 /* c 8) utility */
1160 if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1161 mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
1162 /* c 7) Optimize quality */
1163 /* For all quality metrics, set quality of this address */
1164 if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1165 {
1166 mlp_create_problem_set_value (p,
1167 p->r_q[RQ_QUALITY_METRIC_DELAY],
1168 mlpi->c_b,
1169 address->norm_delay.norm,
1170 __LINE__);
1171 mlp_create_problem_set_value (p,
1172 p->r_q[RQ_QUALITY_METRIC_DISTANCE],
1173 mlpi->c_b,
1174 address->norm_distance.norm,
1175 __LINE__);
1176 }
1177 }
1178
1179 return GNUNET_OK;
1180}
1181
1182
1183/**
1184 * Create the invariant columns c4, c6, c10, c8, c7
1185 */
1186static void
1187mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct
1188 MLP_Problem *p)
1189{
1190 int c;
1191
1192 /* Feasibility */
1193
1194 /* Row for c4) minimum connection */
1195 /* Number of minimum connections is min(|Peers|, n_min) */
1196 p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO,
1197 (mlp->pv.n_min >
1198 p->num_peers) ?
1199 p->num_peers : mlp->pv.n_min,
1200 0.0);
1201
1202 /* Rows for c 10) Enforce network quotas */
1203 for (c = 0; c < GNUNET_NT_COUNT; c++)
1204 {
1205 char *text;
1206 GNUNET_asprintf (&text, "c10_quota_ats_%s",
1207 GNUNET_NT_to_string (mlp->pv.quota_index[c]));
1208 p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0,
1209 mlp->pv.quota_out[c]);
1210 GNUNET_free (text);
1211 }
1212
1213 /* Optimality */
1214 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1215 {
1216 char *name;
1217 /* Add row for c6) Maximize for diversity */
1218 if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1219 {
1220 p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0,
1221 0.0);
1222 /* Set c6 ) Setting -D */
1223 mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
1224 }
1225
1226 /* Adding rows for c 8) Maximize utility */
1227 if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1228 {
1229 p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0,
1230 0.0);
1231 /* -u */
1232 mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
1233 }
1234
1235 /* For all quality metrics:
1236 * c 7) Maximize quality, austerity */
1237 if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1238 {
1239 for (c = 0; c < mlp->pv.m_q; c++)
1240 {
1241 GNUNET_asprintf (&name,
1242 "c7_q%i_%s", c,
1243 print_quality_type (c));
1244 p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0,
1245 0.0);
1246 GNUNET_free (name);
1247 mlp_create_problem_set_value (p,
1248 p->r_q[c],
1249 p->c_q[c], -1, __LINE__);
1250 }
1251 }
1252 }
1253}
1254
1255
1256/**
1257 * Create the invariant columns d, u, r, q0 ... qm
1258 */
1259static void
1260mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct
1261 MLP_Problem *p)
1262{
1263 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1264 {
1265 char *name;
1266 int c;
1267
1268 /* Diversity d column */
1269 if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1270 p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0,
1271 0.0, mlp->pv.co_D);
1272
1273 /* Utilization u column */
1274 if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1275 p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0,
1276 0.0, mlp->pv.co_U);
1277
1278 /* Relativity r column */
1279 if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1280 p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0,
1281 0.0, mlp->pv.co_R);
1282
1283 /* Quality metric columns */
1284 if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1285 {
1286 for (c = 0; c < mlp->pv.m_q; c++)
1287 {
1288 GNUNET_asprintf (&name, "q_%u", c);
1289 p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO,
1290 0.0, 0.0,
1291 mlp->pv.co_Q[c]);
1292 GNUNET_free (name);
1293 }
1294 }
1295 }
1296}
1297
1298
1299/**
1300 * Create the MLP problem
1301 *
1302 * @param mlp the MLP handle
1303 * @return #GNUNET_OK or #GNUNET_SYSERR
1304 */
1305static int
1306mlp_create_problem (struct GAS_MLP_Handle *mlp)
1307{
1308 struct MLP_Problem *p = &mlp->p;
1309 int res = GNUNET_OK;
1310
1311 GNUNET_assert (p->prob == NULL);
1312 GNUNET_assert (p->ia == NULL);
1313 GNUNET_assert (p->ja == NULL);
1314 GNUNET_assert (p->ar == NULL);
1315 /* Reset MLP problem struct */
1316
1317 /* create the glpk problem */
1318 p->prob = glp_create_prob ();
1319 GNUNET_assert (NULL != p->prob);
1320 p->num_peers = mlp_create_problem_count_peers (mlp->requested_peers,
1321 mlp->env->addresses);
1322 p->num_addresses = mlp_create_problem_count_addresses (mlp->requested_peers,
1323 mlp->env->addresses);
1324
1325 /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1326 p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses
1327 + mlp->pv.m_q + p->num_peers + 2 + 1);
1328 LOG (GNUNET_ERROR_TYPE_DEBUG,
1329 "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1330 p->num_peers,
1331 p->num_addresses,
1332 mlp->pv.m_q,
1333 p->num_elements);
1334
1335 /* Set a problem name */
1336 glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
1337 /* Set optimization direction to maximize */
1338 glp_set_obj_dir (p->prob, GLP_MAX);
1339
1340 /* Create problem matrix */
1341 /* last +1 caused by glpk index starting with one: [1..elements]*/
1342 p->ci = 1;
1343 /* row index */
1344 p->ia = GNUNET_malloc (p->num_elements * sizeof(int));
1345 /* column index */
1346 p->ja = GNUNET_malloc (p->num_elements * sizeof(int));
1347 /* coefficient */
1348 p->ar = GNUNET_malloc (p->num_elements * sizeof(double));
1349
1350 if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1351 {
1352 LOG (GNUNET_ERROR_TYPE_ERROR, _ (
1353 "Problem size too large, cannot allocate memory!\n"));
1354 return GNUNET_SYSERR;
1355 }
1356
1357 /* Adding invariant columns */
1358 mlp_create_problem_add_invariant_columns (mlp, p);
1359
1360 /* Adding address independent constraint rows */
1361 mlp_create_problem_add_invariant_rows (mlp, p);
1362
1363 /* Adding address dependent columns constraint rows */
1364 GNUNET_CONTAINER_multipeermap_iterate (mlp->env->addresses,
1365 &
1366 mlp_create_problem_add_address_information,
1367 mlp);
1368
1369 /* Load the matrix */
1370 LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1371 glp_load_matrix (p->prob, (p->ci) - 1, p->ia, p->ja, p->ar);
1372 if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
1373 {
1374 glp_scale_prob (p->prob, GLP_SF_AUTO);
1375 }
1376
1377 return res;
1378}
1379
1380
1381/**
1382 * Solves the LP problem
1383 *
1384 * @param mlp the MLP Handle
1385 * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1386 */
1387static int
1388mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
1389{
1390 int res = 0;
1391 int res_status = 0;
1392
1393 res = glp_simplex (mlp->p.prob, &mlp->control_param_lp);
1394 if (0 == res)
1395 LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1396 mlp_solve_to_string (res));
1397 else
1398 LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1399 mlp_solve_to_string (res));
1400
1401 /* Analyze problem status */
1402 res_status = glp_get_status (mlp->p.prob);
1403 switch (res_status)
1404 {
1405 case GLP_OPT: /* solution is optimal */
1406 LOG (GNUNET_ERROR_TYPE_INFO,
1407 "Solving LP problem: %s, %s\n",
1408 mlp_solve_to_string (res),
1409 mlp_status_to_string (res_status));
1410 return GNUNET_OK;
1411
1412 default:
1413 LOG (GNUNET_ERROR_TYPE_ERROR,
1414 "Solving LP problem failed: %s %s\n",
1415 mlp_solve_to_string (res),
1416 mlp_status_to_string (res_status));
1417 return GNUNET_SYSERR;
1418 }
1419}
1420
1421
1422/**
1423 * Propagates the results when MLP problem was solved
1424 *
1425 * @param cls the MLP handle
1426 * @param key the peer identity
1427 * @param value the address
1428 * @return #GNUNET_OK to continue
1429 */
1430static int
1431mlp_propagate_results (void *cls,
1432 const struct GNUNET_PeerIdentity *key,
1433 void *value)
1434{
1435 struct GAS_MLP_Handle *mlp = cls;
1436 struct ATS_Address *address;
1437 struct MLP_information *mlpi;
1438 double mlp_bw_in = MLP_NaN;
1439 double mlp_bw_out = MLP_NaN;
1440 double mlp_use = MLP_NaN;
1441
1442 /* Check if we have to add this peer due to a pending request */
1443 if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers,
1444 key))
1445 {
1446 return GNUNET_OK;
1447 }
1448 address = value;
1449 GNUNET_assert (address->solver_information != NULL);
1450 mlpi = address->solver_information;
1451
1452 mlp_bw_in = glp_mip_col_val (mlp->p.prob, mlpi->c_b);/* FIXME */
1453 if (mlp_bw_in > (double) UINT32_MAX)
1454 {
1455 LOG (GNUNET_ERROR_TYPE_DEBUG,
1456 "Overflow in assigned bandwidth, reducing ...\n");
1457 mlp_bw_in = (double) UINT32_MAX;
1458 }
1459 mlp_bw_out = glp_mip_col_val (mlp->p.prob, mlpi->c_b);
1460 if (mlp_bw_out > (double) UINT32_MAX)
1461 {
1462 LOG (GNUNET_ERROR_TYPE_DEBUG,
1463 "Overflow in assigned bandwidth, reducing ...\n");
1464 mlp_bw_out = (double) UINT32_MAX;
1465 }
1466 mlp_use = glp_mip_col_val (mlp->p.prob, mlpi->c_n);
1467
1468 /*
1469 * Debug: solution
1470 * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1471 * GNUNET_i2s(&address->peer), address->plugin,
1472 * address->addr_len, address->session_id);
1473 */
1474
1475 if (GLP_YES == mlp_use)
1476 {
1477 /* This address was selected by the solver to be used */
1478 mlpi->n = GNUNET_YES;
1479 if (GNUNET_NO == address->active)
1480 {
1481 /* Address was not used before, enabling address */
1482 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1483 (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1484 address->active = GNUNET_YES;
1485 address->assigned_bw_in = mlp_bw_in;
1486 mlpi->b_in = mlp_bw_in;
1487 address->assigned_bw_out = mlp_bw_out;
1488 mlpi->b_out = mlp_bw_out;
1489 if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer,
1490 mlp->exclude_peer)))
1491 mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1492 return GNUNET_OK;
1493 }
1494 else if (GNUNET_YES == address->active)
1495 {
1496 /* Address was used before, check for bandwidth change */
1497 if ((mlp_bw_out != address->assigned_bw_out) ||
1498 (mlp_bw_in != address->assigned_bw_in))
1499 {
1500 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1501 (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1502 address->assigned_bw_in = mlp_bw_in;
1503 mlpi->b_in = mlp_bw_in;
1504 address->assigned_bw_out = mlp_bw_out;
1505 mlpi->b_out = mlp_bw_out;
1506 if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer,
1507 mlp->
1508 exclude_peer)))
1509 mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1510 return GNUNET_OK;
1511 }
1512 }
1513 else
1514 GNUNET_break (0);
1515 }
1516 else if (GLP_NO == mlp_use)
1517 {
1518 /* This address was selected by the solver to be not used */
1519 mlpi->n = GNUNET_NO;
1520 if (GNUNET_NO == address->active)
1521 {
1522 /* Address was not used before, nothing to do */
1523 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1524 (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1525 return GNUNET_OK;
1526 }
1527 else if (GNUNET_YES == address->active)
1528 {
1529 /* Address was used before, disabling address */
1530 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1531 (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1532 address->active = GNUNET_NO;
1533 /* Set bandwidth to 0 */
1534 address->assigned_bw_in = 0;
1535 mlpi->b_in = 0;
1536 address->assigned_bw_out = 0;
1537 mlpi->b_out = 0;
1538 return GNUNET_OK;
1539 }
1540 else
1541 GNUNET_break (0);
1542 }
1543 else
1544 GNUNET_break (0);
1545
1546 return GNUNET_OK;
1547}
1548
1549
1550static void
1551notify (struct GAS_MLP_Handle *mlp,
1552 enum GAS_Solver_Operation op,
1553 enum GAS_Solver_Status stat,
1554 enum GAS_Solver_Additional_Information add)
1555{
1556 mlp->env->info_cb (mlp->env->cls,
1557 op,
1558 stat,
1559 add);
1560}
1561
1562
1563static void
1564mlp_branch_and_cut_cb (glp_tree *tree, void *info)
1565{
1566 struct GAS_MLP_Handle *mlp = info;
1567 double mlp_obj = 0;
1568
1569 switch (glp_ios_reason (tree))
1570 {
1571 case GLP_ISELECT:
1572 /* Do nothing here */
1573 break;
1574
1575 case GLP_IPREPRO:
1576 /* Do nothing here */
1577 break;
1578
1579 case GLP_IROWGEN:
1580 /* Do nothing here */
1581 break;
1582
1583 case GLP_IHEUR:
1584 /* Do nothing here */
1585 break;
1586
1587 case GLP_ICUTGEN:
1588 /* Do nothing here */
1589 break;
1590
1591 case GLP_IBRANCH:
1592 /* Do nothing here */
1593 break;
1594
1595 case GLP_IBINGO:
1596 /* A better solution was found */
1597 mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
1598 mlp_obj = glp_mip_obj_val (mlp->p.prob);
1599 mlp->ps.lp_mlp_gap = (abs (mlp_obj - mlp->ps.lp_objective_value)) / (abs (
1600 mlp_obj)
1601 +
1602 DBL_EPSILON);
1603
1604 LOG (GNUNET_ERROR_TYPE_INFO,
1605 "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1606 mlp->ps.mlp_gap, mlp->pv.mip_gap,
1607 mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1608
1609 if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1610 {
1611 LOG (GNUNET_ERROR_TYPE_INFO,
1612 "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1613 mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1614 glp_ios_terminate (tree);
1615 }
1616
1617 if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1618 {
1619 LOG (GNUNET_ERROR_TYPE_INFO,
1620 "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1621 mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1622 glp_ios_terminate (tree);
1623 }
1624
1625 break;
1626
1627 default:
1628 break;
1629 }
1630 // GNUNET_break (0);
1631}
1632
1633
1634/**
1635 * Solves the MLP problem
1636 *
1637 * @param solver the MLP Handle
1638 * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1639 */
1640static int
1641GAS_mlp_solve_problem (void *solver)
1642{
1643 struct GAS_MLP_Handle *mlp = solver;
1644 char *filename;
1645 int res_lp = 0;
1646 int mip_res = 0;
1647 int mip_status = 0;
1648
1649 struct GNUNET_TIME_Absolute start_total;
1650 struct GNUNET_TIME_Absolute start_cur_op;
1651 struct GNUNET_TIME_Relative dur_total;
1652 struct GNUNET_TIME_Relative dur_setup;
1653 struct GNUNET_TIME_Relative dur_lp;
1654 struct GNUNET_TIME_Relative dur_mlp;
1655
1656 GNUNET_assert (NULL != solver);
1657 dur_lp = GNUNET_TIME_UNIT_ZERO;
1658
1659 if (GNUNET_YES == mlp->stat_bulk_lock)
1660 {
1661 mlp->stat_bulk_requests++;
1662 return GNUNET_NO;
1663 }
1664 notify (mlp, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS,
1665 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1666 GAS_INFO_UPDATED);
1667 start_total = GNUNET_TIME_absolute_get ();
1668
1669 if (0 == GNUNET_CONTAINER_multipeermap_size (mlp->requested_peers))
1670 {
1671 notify (mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1672 return GNUNET_OK; /* No pending requests */
1673 }
1674 if (0 == GNUNET_CONTAINER_multipeermap_size (mlp->env->addresses))
1675 {
1676 notify (mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1677 return GNUNET_OK; /* No addresses available */
1678 }
1679
1680 if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1681 && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1682 {
1683 LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1684 notify (mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1685 return GNUNET_OK;
1686 }
1687 if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1688 {
1689 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1690 notify (mlp, GAS_OP_SOLVE_SETUP_START, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1691 mlp_delete_problem (mlp);
1692 if (GNUNET_SYSERR == mlp_create_problem (mlp))
1693 {
1694 notify (mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_FAIL, GAS_INFO_FULL);
1695 return GNUNET_SYSERR;
1696 }
1697 notify (mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1698 if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1699 {
1700 mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1701 mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1702 }
1703 else
1704 {
1705 mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1706 mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1707 dur_lp = GNUNET_TIME_UNIT_ZERO;
1708 }
1709 }
1710 else
1711 {
1712 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1713 }
1714
1715 /* Reset solution info */
1716 mlp->ps.lp_objective_value = 0.0;
1717 mlp->ps.mlp_gap = 1.0;
1718 mlp->ps.mlp_objective_value = 0.0;
1719 mlp->ps.lp_mlp_gap = 0.0;
1720
1721 dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
1722
1723 /* Run LP solver */
1724 if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1725 {
1726 notify (mlp, GAS_OP_SOLVE_MLP_LP_START, GAS_STAT_SUCCESS,
1727 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1728 GAS_INFO_UPDATED);
1729 LOG (GNUNET_ERROR_TYPE_DEBUG,
1730 "Running LP solver %s\n",
1731 (GLP_YES == mlp->control_param_lp.presolve) ? "with presolver" :
1732 "without presolver");
1733 start_cur_op = GNUNET_TIME_absolute_get ();
1734
1735 /* Solve LP */
1736 /* Only for debugging:
1737 * Always use LP presolver:
1738 * mlp->control_param_lp.presolve = GLP_YES; */
1739 res_lp = mlp_solve_lp_problem (mlp);
1740 if (GNUNET_OK == res_lp)
1741 {
1742 mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
1743 LOG (GNUNET_ERROR_TYPE_DEBUG,
1744 "LP solution was: %.3f\n",
1745 mlp->ps.lp_objective_value);
1746 }
1747
1748 dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1749 notify (mlp, GAS_OP_SOLVE_MLP_LP_STOP,
1750 (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1751 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1752 GAS_INFO_UPDATED);
1753 }
1754
1755 if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1756 res_lp = GNUNET_OK;
1757
1758 /* Run MLP solver */
1759 if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1760 {
1761 LOG (GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1762 notify (mlp, GAS_OP_SOLVE_MLP_MLP_START, GAS_STAT_SUCCESS,
1763 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1764 GAS_INFO_UPDATED);
1765 start_cur_op = GNUNET_TIME_absolute_get ();
1766
1767 /* Solve MIP */
1768
1769 /* Only for debugging, always use LP presolver */
1770 if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1771 mlp->control_param_mlp.presolve = GNUNET_YES;
1772
1773 mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
1774 switch (mip_res)
1775 {
1776 case 0:
1777 /* Successful */
1778 LOG (GNUNET_ERROR_TYPE_INFO,
1779 "Solving MLP problem: %s\n",
1780 mlp_solve_to_string (mip_res));
1781 break;
1782
1783 case GLP_ETMLIM: /* Time limit reached */
1784 case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1785 case GLP_ESTOP: /* Solver was instructed to stop*/
1786 /* Semi-successful */
1787 LOG (GNUNET_ERROR_TYPE_INFO,
1788 "Solving MLP problem solution was interupted: %s\n",
1789 mlp_solve_to_string (mip_res));
1790 break;
1791
1792 case GLP_EBOUND:
1793 case GLP_EROOT:
1794 case GLP_ENOPFS:
1795 case GLP_ENODFS:
1796 case GLP_EFAIL:
1797 default:
1798 /* Fail */
1799 LOG (GNUNET_ERROR_TYPE_INFO,
1800 "Solving MLP problem failed: %s\n",
1801 mlp_solve_to_string (mip_res));
1802 break;
1803 }
1804
1805 /* Analyze problem status */
1806 mip_status = glp_mip_status (mlp->p.prob);
1807 switch (mip_status)
1808 {
1809 case GLP_OPT: /* solution is optimal */
1810 LOG (GNUNET_ERROR_TYPE_WARNING,
1811 "Solution of MLP problem is optimal: %s, %s\n",
1812 mlp_solve_to_string (mip_res),
1813 mlp_status_to_string (mip_status));
1814 mip_res = GNUNET_OK;
1815 break;
1816
1817 case GLP_FEAS: /* solution is feasible but not proven optimal */
1818
1819 if ((mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1820 (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap))
1821 {
1822 LOG (GNUNET_ERROR_TYPE_INFO,
1823 "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1824 mlp_solve_to_string (mip_res),
1825 mlp_status_to_string (mip_status));
1826 mip_res = GNUNET_OK;
1827 }
1828 else
1829 {
1830 LOG (GNUNET_ERROR_TYPE_WARNING,
1831 "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1832 mlp_solve_to_string (mip_res),
1833 mlp_status_to_string (mip_status));
1834 mip_res = GNUNET_SYSERR;
1835 }
1836 break;
1837
1838 case GLP_UNDEF: /* Solution undefined */
1839 case GLP_NOFEAS: /* No feasible solution */
1840 default:
1841 LOG (GNUNET_ERROR_TYPE_ERROR,
1842 "Solving MLP problem failed: %s %s\n",
1843 mlp_solve_to_string (mip_res),
1844 mlp_status_to_string (mip_status));
1845 mip_res = GNUNET_SYSERR;
1846 break;
1847 }
1848
1849 dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1850 dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1851
1852 notify (mlp, GAS_OP_SOLVE_MLP_MLP_STOP,
1853 (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1854 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1855 GAS_INFO_UPDATED);
1856 }
1857 else
1858 {
1859 /* Do not execute mip solver since lp solution is invalid */
1860 dur_mlp = GNUNET_TIME_UNIT_ZERO;
1861 dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1862
1863 notify (mlp, GAS_OP_SOLVE_MLP_MLP_STOP, GAS_STAT_FAIL,
1864 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1865 GAS_INFO_UPDATED);
1866 mip_res = GNUNET_SYSERR;
1867 }
1868
1869 /* Notify about end */
1870 notify (mlp, GAS_OP_SOLVE_STOP,
1871 ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ?
1872 GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1873 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL :
1874 GAS_INFO_UPDATED);
1875
1876 LOG (GNUNET_ERROR_TYPE_DEBUG,
1877 "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1878 (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1879 (unsigned long long) dur_total.rel_value_us,
1880 (unsigned long long) dur_setup.rel_value_us,
1881 (unsigned long long) dur_lp.rel_value_us,
1882 (unsigned long long) dur_mlp.rel_value_us);
1883
1884 /* Save stats */
1885 mlp->ps.lp_res = res_lp;
1886 mlp->ps.mip_res = mip_res;
1887 mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1888 mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1889 mlp->ps.p_cols = glp_get_num_cols (mlp->p.prob);
1890 mlp->ps.p_rows = glp_get_num_rows (mlp->p.prob);
1891 mlp->ps.p_elements = mlp->p.num_elements;
1892
1893 /* Propagate result*/
1894 notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
1895 (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS :
1896 GAS_STAT_FAIL,
1897 GAS_INFO_NONE);
1898 if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1899 {
1900 GNUNET_CONTAINER_multipeermap_iterate (mlp->env->addresses,
1901 &mlp_propagate_results, mlp);
1902 }
1903 notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
1904 (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS :
1905 GAS_STAT_FAIL,
1906 GAS_INFO_NONE);
1907
1908 struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get ();
1909 if ((GNUNET_YES == mlp->opt_dump_problem_all) ||
1910 (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK !=
1911 mip_res))))
1912 {
1913 /* Write problem to disk */
1914 switch (mlp->opt_log_format)
1915 {
1916 case MLP_CPLEX:
1917 GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.cplex",
1918 mlp->p.num_peers,
1919 mlp->p.num_addresses, time.abs_value_us);
1920 glp_write_lp (mlp->p.prob, NULL, filename);
1921 break;
1922
1923 case MLP_GLPK:
1924 GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.glpk",
1925 mlp->p.num_peers,
1926 mlp->p.num_addresses, time.abs_value_us);
1927 glp_write_prob (mlp->p.prob, 0, filename);
1928 break;
1929
1930 case MLP_MPS:
1931 GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1932 mlp->p.num_addresses, time.abs_value_us);
1933 glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1934 break;
1935
1936 default:
1937 break;
1938 }
1939 LOG (GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1940 GNUNET_free (filename);
1941 }
1942 if ((mlp->opt_dump_solution_all) ||
1943 (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK !=
1944 mip_res))))
1945 {
1946 /* Write solution to disk */
1947 GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1948 mlp->p.num_addresses, time.abs_value_us);
1949 glp_print_mip (mlp->p.prob, filename);
1950 LOG (GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1951 GNUNET_free (filename);
1952 }
1953
1954 /* Reset change and update marker */
1955 mlp->control_param_lp.presolve = GLP_NO;
1956 mlp->stat_mlp_prob_updated = GNUNET_NO;
1957 mlp->stat_mlp_prob_changed = GNUNET_NO;
1958
1959 if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1960 return GNUNET_OK;
1961 else
1962 return GNUNET_SYSERR;
1963}
1964
1965/**
1966 * Add a single address to the solve
1967 *
1968 * @param solver the solver Handle
1969 * @param address the address to add
1970 * @param network network type of this address
1971 */
1972static void
1973GAS_mlp_address_add (void *solver,
1974 struct ATS_Address *address,
1975 uint32_t network)
1976{
1977 struct GAS_MLP_Handle *mlp = solver;
1978
1979 if (GNUNET_NT_COUNT <= network)
1980 {
1981 GNUNET_break (0);
1982 return;
1983 }
1984
1985 if (NULL == address->solver_information)
1986 {
1987 address->solver_information = GNUNET_new (struct MLP_information);
1988 }
1989 else
1990 LOG (GNUNET_ERROR_TYPE_ERROR,
1991 _ ("Adding address for peer `%s' multiple times\n"),
1992 GNUNET_i2s (&address->peer));
1993
1994 /* Is this peer included in the problem? */
1995 if (NULL ==
1996 GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
1997 &address->peer))
1998 {
1999 /* FIXME: should this be an error? */
2000 LOG (GNUNET_ERROR_TYPE_DEBUG,
2001 "Adding address for peer `%s' without address request\n",
2002 GNUNET_i2s (&address->peer));
2003 return;
2004 }
2005
2006 LOG (GNUNET_ERROR_TYPE_DEBUG,
2007 "Adding address for peer `%s' with address request \n",
2008 GNUNET_i2s (&address->peer));
2009 /* Problem size changed: new address for peer with pending request */
2010 mlp->stat_mlp_prob_changed = GNUNET_YES;
2011 if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2012 GAS_mlp_solve_problem (solver);
2013}
2014
2015
2016/**
2017 * Transport properties for this address have changed
2018 *
2019 * @param solver solver handle
2020 * @param address the address
2021 */
2022static void
2023GAS_mlp_address_property_changed (void *solver,
2024 struct ATS_Address *address)
2025{
2026 struct MLP_information *mlpi = address->solver_information;
2027 struct GAS_MLP_Handle *mlp = solver;
2028
2029 if (NULL == mlp->p.prob)
2030 return; /* There is no MLP problem to update yet */
2031
2032 if (NULL == mlpi)
2033 {
2034 LOG (GNUNET_ERROR_TYPE_INFO,
2035 _ ("Updating address property for peer `%s' %p not added before\n"),
2036 GNUNET_i2s (&address->peer),
2037 address);
2038 GNUNET_break (0);
2039 return;
2040 }
2041 if (NULL ==
2042 GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2043 &address->peer))
2044 {
2045 /* Peer is not requested, so no need to update problem */
2046 return;
2047 }
2048 LOG (GNUNET_ERROR_TYPE_DEBUG,
2049 "Updating properties for peer `%s'\n",
2050 GNUNET_i2s (&address->peer));
2051
2052 if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
2053 return;
2054
2055 /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
2056 if ((GNUNET_YES ==
2057 mlp_create_problem_update_value (&mlp->p,
2058 mlp->p.r_q[RQ_QUALITY_METRIC_DELAY],
2059 mlpi->c_b,
2060 address->norm_delay.norm,
2061 __LINE__)) ||
2062 (GNUNET_YES ==
2063 mlp_create_problem_update_value (&mlp->p,
2064 mlp->p.r_q[RQ_QUALITY_METRIC_DISTANCE],
2065 mlpi->c_b,
2066 address->norm_distance.norm,
2067 __LINE__)))
2068 {
2069 mlp->stat_mlp_prob_updated = GNUNET_YES;
2070 if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2071 GAS_mlp_solve_problem (solver);
2072 }
2073}
2074
2075
2076/**
2077 * Find the active address in the set of addresses of a peer
2078 * @param cls destination
2079 * @param key peer id
2080 * @param value address
2081 * @return #GNUNET_OK
2082 */
2083static int
2084mlp_get_preferred_address_it (void *cls,
2085 const struct GNUNET_PeerIdentity *key,
2086 void *value)
2087{
2088 static int counter = 0;
2089 struct ATS_Address **aa = cls;
2090 struct ATS_Address *addr = value;
2091 struct MLP_information *mlpi = addr->solver_information;
2092
2093 if (mlpi == NULL)
2094 return GNUNET_YES;
2095
2096 /*
2097 * Debug output
2098 * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2099 * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
2100 * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
2101 * (GNUNET_YES == addr->active) ? "active" : "inactive",
2102 * (GNUNET_YES == mlpi->n) ? "active" : "inactive");
2103 */
2104
2105 if (GNUNET_YES == mlpi->n)
2106 {
2107 (*aa) = addr;
2108 (*aa)->assigned_bw_in = mlpi->b_in;
2109 (*aa)->assigned_bw_out = mlpi->b_out;
2110 return GNUNET_NO;
2111 }
2112 counter++;
2113 return GNUNET_YES;
2114}
2115
2116
2117static double
2118get_peer_pref_value (struct GAS_MLP_Handle *mlp,
2119 const struct GNUNET_PeerIdentity *peer)
2120{
2121 double res;
2122 const double *preferences;
2123 int c;
2124
2125 preferences = mlp->env->get_preferences (mlp->env->cls, peer);
2126 res = 0.0;
2127 for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
2128 {
2129 /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2130 * c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2131 res += preferences[c];
2132 }
2133
2134 res /= GNUNET_ATS_PREFERENCE_END;
2135 res += 1.0;
2136
2137 LOG (GNUNET_ERROR_TYPE_DEBUG,
2138 "Peer preference for peer `%s' == %.2f\n",
2139 GNUNET_i2s (peer), res);
2140
2141 return res;
2142}
2143
2144
2145/**
2146 * Get the preferred address for a specific peer
2147 *
2148 * @param solver the MLP Handle
2149 * @param peer the peer
2150 */
2151static void
2152GAS_mlp_get_preferred_address (void *solver,
2153 const struct GNUNET_PeerIdentity *peer)
2154{
2155 struct GAS_MLP_Handle *mlp = solver;
2156 struct ATS_Peer *p;
2157 struct ATS_Address *res;
2158
2159 LOG (GNUNET_ERROR_TYPE_DEBUG,
2160 "Getting preferred address for `%s'\n",
2161 GNUNET_i2s (peer));
2162
2163 /* Is this peer included in the problem? */
2164 if (NULL ==
2165 GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2166 peer))
2167 {
2168 LOG (GNUNET_ERROR_TYPE_INFO,
2169 "Adding peer `%s' to list of requested_peers with requests\n",
2170 GNUNET_i2s (peer));
2171
2172 p = GNUNET_new (struct ATS_Peer);
2173 p->id = (*peer);
2174 p->f = get_peer_pref_value (mlp, peer);
2175 GNUNET_CONTAINER_multipeermap_put (mlp->requested_peers,
2176 peer, p,
2177 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
2178
2179 /* Added new peer, we have to rebuild problem before solving */
2180 mlp->stat_mlp_prob_changed = GNUNET_YES;
2181
2182 if ((GNUNET_YES == mlp->opt_mlp_auto_solve) &&
2183 (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (
2184 mlp->env->addresses,
2185 peer)))
2186 {
2187 mlp->exclude_peer = peer;
2188 GAS_mlp_solve_problem (mlp);
2189 mlp->exclude_peer = NULL;
2190 }
2191 }
2192 /* Get prefered address */
2193 res = NULL;
2194 GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses, peer,
2195 &mlp_get_preferred_address_it,
2196 &res);
2197 if (NULL != res)
2198 mlp->env->bandwidth_changed_cb (mlp->env->cls,
2199 res);
2200}
2201
2202
2203/**
2204 * Deletes a single address in the MLP problem
2205 *
2206 * The MLP problem has to be recreated and the problem has to be resolved
2207 *
2208 * @param solver the MLP Handle
2209 * @param address the address to delete
2210 */
2211static void
2212GAS_mlp_address_delete (void *solver,
2213 struct ATS_Address *address)
2214{
2215 struct GAS_MLP_Handle *mlp = solver;
2216 struct MLP_information *mlpi;
2217 struct ATS_Address *res;
2218 int was_active;
2219
2220 mlpi = address->solver_information;
2221 if (NULL != mlpi)
2222 {
2223 /* Remove full address */
2224 GNUNET_free (mlpi);
2225 address->solver_information = NULL;
2226 }
2227 was_active = address->active;
2228 address->active = GNUNET_NO;
2229 address->assigned_bw_in = 0;
2230 address->assigned_bw_out = 0;
2231
2232 /* Is this peer included in the problem? */
2233 if (NULL ==
2234 GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2235 &address->peer))
2236 {
2237 LOG (GNUNET_ERROR_TYPE_INFO,
2238 "Deleting address for peer `%s' without address request \n",
2239 GNUNET_i2s (&address->peer));
2240 return;
2241 }
2242 LOG (GNUNET_ERROR_TYPE_INFO,
2243 "Deleting address for peer `%s' with address request \n",
2244 GNUNET_i2s (&address->peer));
2245
2246 /* Problem size changed: new address for peer with pending request */
2247 mlp->stat_mlp_prob_changed = GNUNET_YES;
2248 if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2249 {
2250 GAS_mlp_solve_problem (solver);
2251 }
2252 if (GNUNET_YES == was_active)
2253 {
2254 GAS_mlp_get_preferred_address (solver, &address->peer);
2255 res = NULL;
2256 GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses,
2257 &address->peer,
2258 &mlp_get_preferred_address_it,
2259 &res);
2260 if (NULL == res)
2261 {
2262 /* No alternative address, disconnecting peer */
2263 mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
2264 }
2265 }
2266}
2267
2268
2269/**
2270 * Start a bulk operation
2271 *
2272 * @param solver the solver
2273 */
2274static void
2275GAS_mlp_bulk_start (void *solver)
2276{
2277 struct GAS_MLP_Handle *s = solver;
2278
2279 LOG (GNUNET_ERROR_TYPE_DEBUG,
2280 "Locking solver for bulk operation ...\n");
2281 GNUNET_assert (NULL != solver);
2282 s->stat_bulk_lock++;
2283}
2284
2285
2286static void
2287GAS_mlp_bulk_stop (void *solver)
2288{
2289 struct GAS_MLP_Handle *s = solver;
2290
2291 LOG (GNUNET_ERROR_TYPE_DEBUG,
2292 "Unlocking solver from bulk operation ...\n");
2293 GNUNET_assert (NULL != solver);
2294
2295 if (s->stat_bulk_lock < 1)
2296 {
2297 GNUNET_break (0);
2298 return;
2299 }
2300 s->stat_bulk_lock--;
2301
2302 if (0 < s->stat_bulk_requests)
2303 {
2304 GAS_mlp_solve_problem (solver);
2305 s->stat_bulk_requests = 0;
2306 }
2307}
2308
2309
2310
2311/**
2312 * Stop notifying about address and bandwidth changes for this peer
2313 *
2314 * @param solver the MLP handle
2315 * @param peer the peer
2316 */
2317static void
2318GAS_mlp_stop_get_preferred_address (void *solver,
2319 const struct GNUNET_PeerIdentity *peer)
2320{
2321 struct GAS_MLP_Handle *mlp = solver;
2322 struct ATS_Peer *p = NULL;
2323
2324 GNUNET_assert (NULL != solver);
2325 GNUNET_assert (NULL != peer);
2326 if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2327 peer)))
2328 {
2329 GNUNET_assert (GNUNET_YES ==
2330 GNUNET_CONTAINER_multipeermap_remove (mlp->requested_peers,
2331 peer, p));
2332 GNUNET_free (p);
2333
2334 mlp->stat_mlp_prob_changed = GNUNET_YES;
2335 if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2336 {
2337 GAS_mlp_solve_problem (solver);
2338 }
2339 }
2340}
2341
2342
2343/**
2344 * Changes the preferences for a peer in the MLP problem
2345 *
2346 * @param solver the MLP Handle
2347 * @param peer the peer
2348 * @param kind the kind to change the preference
2349 * @param pref_rel the relative score
2350 */
2351static void
2352GAS_mlp_address_change_preference (void *solver,
2353 const struct GNUNET_PeerIdentity *peer,
2354 enum GNUNET_ATS_PreferenceKind kind,
2355 double pref_rel)
2356{
2357 struct GAS_MLP_Handle *mlp = solver;
2358 struct ATS_Peer *p;
2359
2360 LOG (GNUNET_ERROR_TYPE_DEBUG,
2361 "Changing preference for address for peer `%s' to %.2f\n",
2362 GNUNET_i2s (peer),
2363 pref_rel);
2364
2365 GNUNET_STATISTICS_update (mlp->env->stats,
2366 "# LP address preference changes", 1, GNUNET_NO);
2367 /* Update the constraints with changed preferences */
2368
2369
2370
2371 /* Update relativity constraint c9 */
2372 if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2373 peer)))
2374 {
2375 LOG (GNUNET_ERROR_TYPE_INFO,
2376 "Updating preference for unknown peer `%s'\n",
2377 GNUNET_i2s (peer));
2378 return;
2379 }
2380
2381 if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2382 {
2383 p->f = get_peer_pref_value (mlp, peer);
2384 mlp_create_problem_update_value (&mlp->p,
2385 p->r_c9,
2386 mlp->p.c_r,
2387 -p->f,
2388 __LINE__);
2389
2390 /* Problem size changed: new address for peer with pending request */
2391 mlp->stat_mlp_prob_updated = GNUNET_YES;
2392 if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2393 GAS_mlp_solve_problem (solver);
2394 }
2395}
2396
2397
2398/**
2399 * Get application feedback for a peer
2400 *
2401 * @param solver the solver handle
2402 * @param application the application
2403 * @param peer the peer to change the preference for
2404 * @param scope the time interval for this feedback: [now - scope .. now]
2405 * @param kind the kind to change the preference
2406 * @param score the score
2407 */
2408static void
2409GAS_mlp_address_preference_feedback (void *solver,
2410 struct GNUNET_SERVICE_Client *application,
2411 const struct GNUNET_PeerIdentity *peer,
2412 const struct GNUNET_TIME_Relative scope,
2413 enum GNUNET_ATS_PreferenceKind kind,
2414 double score)
2415{
2416 struct GAS_PROPORTIONAL_Handle *s = solver;
2417
2418 GNUNET_assert (NULL != solver);
2419 GNUNET_assert (NULL != peer);
2420 GNUNET_assert (NULL != s);
2421}
2422
2423
2424static int
2425mlp_free_peers (void *cls,
2426 const struct GNUNET_PeerIdentity *key, void *value)
2427{
2428 struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2429 struct ATS_Peer *p = value;
2430
2431 GNUNET_assert (GNUNET_YES ==
2432 GNUNET_CONTAINER_multipeermap_remove (map, key, value));
2433 GNUNET_free (p);
2434
2435 return GNUNET_OK;
2436}
2437
2438
2439/**
2440 * Shutdown the MLP problem solving component
2441 *
2442 * @param cls the solver handle
2443 * @return NULL
2444 */
2445void *
2446libgnunet_plugin_ats_mlp_done (void *cls)
2447{
2448 struct GNUNET_ATS_SolverFunctions *sf = cls;
2449 struct GAS_MLP_Handle *mlp = sf->cls;
2450
2451 LOG (GNUNET_ERROR_TYPE_DEBUG,
2452 "Shutting down mlp solver\n");
2453 mlp_delete_problem (mlp);
2454 GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
2455 &mlp_free_peers,
2456 mlp->requested_peers);
2457 GNUNET_CONTAINER_multipeermap_destroy (mlp->requested_peers);
2458 mlp->requested_peers = NULL;
2459
2460 /* Clean up GLPK environment */
2461 glp_free_env ();
2462 GNUNET_free (mlp);
2463
2464 LOG (GNUNET_ERROR_TYPE_DEBUG,
2465 "Shutdown down of mlp solver complete\n");
2466 return NULL;
2467}
2468
2469
2470void *
2471libgnunet_plugin_ats_mlp_init (void *cls)
2472{
2473 static struct GNUNET_ATS_SolverFunctions sf;
2474 struct GNUNET_ATS_PluginEnvironment *env = cls;
2475 struct GAS_MLP_Handle *mlp = GNUNET_new (struct GAS_MLP_Handle);
2476 float f_tmp;
2477 unsigned long long tmp;
2478 unsigned int b_min;
2479 unsigned int n_min;
2480 int c;
2481 char *outputformat;
2482
2483 struct GNUNET_TIME_Relative max_duration;
2484 long long unsigned int max_iterations;
2485
2486 /* Init GLPK environment */
2487 int res = glp_init_env ();
2488
2489 switch (res)
2490 {
2491 case 0:
2492 LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2493 "initialization successful");
2494 break;
2495
2496 case 1:
2497 LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2498 "environment is already initialized");
2499 break;
2500
2501 case 2:
2502 LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2503 "initialization failed (insufficient memory)");
2504 GNUNET_free (mlp);
2505 return NULL;
2506 break;
2507
2508 case 3:
2509 LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2510 "initialization failed (unsupported programming model)");
2511 GNUNET_free (mlp);
2512 return NULL;
2513 break;
2514
2515 default:
2516 break;
2517 }
2518
2519 mlp->opt_dump_problem_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2520 "ats",
2521 "MLP_DUMP_PROBLEM_ALL");
2522 if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2523 mlp->opt_dump_problem_all = GNUNET_NO;
2524
2525 mlp->opt_dump_solution_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2526 "ats",
2527 "MLP_DUMP_SOLUTION_ALL");
2528 if (GNUNET_SYSERR == mlp->opt_dump_solution_all)
2529 mlp->opt_dump_solution_all = GNUNET_NO;
2530
2531 mlp->opt_dump_problem_on_fail = GNUNET_CONFIGURATION_get_value_yesno (
2532 env->cfg,
2533 "ats",
2534 "MLP_DUMP_PROBLEM_ON_FAIL");
2535 if (GNUNET_SYSERR == mlp->opt_dump_problem_on_fail)
2536 mlp->opt_dump_problem_on_fail = GNUNET_NO;
2537
2538 mlp->opt_dump_solution_on_fail = GNUNET_CONFIGURATION_get_value_yesno (
2539 env->cfg,
2540 "ats",
2541 "MLP_DUMP_SOLUTION_ON_FAIL");
2542 if (GNUNET_SYSERR == mlp->opt_dump_solution_on_fail)
2543 mlp->opt_dump_solution_on_fail = GNUNET_NO;
2544
2545 mlp->opt_dbg_glpk_verbose = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2546 "ats",
2547 "MLP_DBG_GLPK_VERBOSE");
2548 if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2549 mlp->opt_dbg_glpk_verbose = GNUNET_NO;
2550
2551 mlp->opt_dbg_feasibility_only = GNUNET_CONFIGURATION_get_value_yesno (
2552 env->cfg,
2553 "ats",
2554 "MLP_DBG_FEASIBILITY_ONLY");
2555 if (GNUNET_SYSERR == mlp->opt_dbg_feasibility_only)
2556 mlp->opt_dbg_feasibility_only = GNUNET_NO;
2557 if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
2558 LOG (GNUNET_ERROR_TYPE_WARNING,
2559 "MLP solver is configured to check feasibility only!\n");
2560
2561 mlp->opt_dbg_autoscale_problem = GNUNET_CONFIGURATION_get_value_yesno (
2562 env->cfg,
2563 "ats",
2564 "MLP_DBG_AUTOSCALE_PROBLEM");
2565 if (GNUNET_SYSERR == mlp->opt_dbg_autoscale_problem)
2566 mlp->opt_dbg_autoscale_problem = GNUNET_NO;
2567 if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
2568 LOG (GNUNET_ERROR_TYPE_WARNING,
2569 "MLP solver is configured automatically scale the problem!\n");
2570
2571 mlp->opt_dbg_intopt_presolver = GNUNET_CONFIGURATION_get_value_yesno (
2572 env->cfg,
2573 "ats",
2574 "MLP_DBG_INTOPT_PRESOLVE");
2575 if (GNUNET_SYSERR == mlp->opt_dbg_intopt_presolver)
2576 mlp->opt_dbg_intopt_presolver = GNUNET_NO;
2577 if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
2578 LOG (GNUNET_ERROR_TYPE_WARNING,
2579 "MLP solver is configured use the mlp presolver\n");
2580
2581 mlp->opt_dbg_optimize_diversity = GNUNET_CONFIGURATION_get_value_yesno (
2582 env->cfg,
2583 "ats",
2584 "MLP_DBG_OPTIMIZE_DIVERSITY");
2585 if (GNUNET_SYSERR == mlp->opt_dbg_optimize_diversity)
2586 mlp->opt_dbg_optimize_diversity = GNUNET_YES;
2587 if (GNUNET_NO == mlp->opt_dbg_optimize_diversity)
2588 LOG (GNUNET_ERROR_TYPE_WARNING,
2589 "MLP solver is not optimizing for diversity\n");
2590
2591 mlp->opt_dbg_optimize_relativity = GNUNET_CONFIGURATION_get_value_yesno (
2592 env->cfg,
2593 "ats",
2594 "MLP_DBG_OPTIMIZE_RELATIVITY");
2595 if (GNUNET_SYSERR == mlp->opt_dbg_optimize_relativity)
2596 mlp->opt_dbg_optimize_relativity = GNUNET_YES;
2597 if (GNUNET_NO == mlp->opt_dbg_optimize_relativity)
2598 LOG (GNUNET_ERROR_TYPE_WARNING,
2599 "MLP solver is not optimizing for relativity\n");
2600
2601 mlp->opt_dbg_optimize_quality = GNUNET_CONFIGURATION_get_value_yesno (
2602 env->cfg,
2603 "ats",
2604 "MLP_DBG_OPTIMIZE_QUALITY");
2605 if (GNUNET_SYSERR == mlp->opt_dbg_optimize_quality)
2606 mlp->opt_dbg_optimize_quality = GNUNET_YES;
2607 if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2608 LOG (GNUNET_ERROR_TYPE_WARNING,
2609 "MLP solver is not optimizing for quality\n");
2610
2611 mlp->opt_dbg_optimize_utility = GNUNET_CONFIGURATION_get_value_yesno (
2612 env->cfg,
2613 "ats",
2614 "MLP_DBG_OPTIMIZE_UTILITY");
2615 if (GNUNET_SYSERR == mlp->opt_dbg_optimize_utility)
2616 mlp->opt_dbg_optimize_utility = GNUNET_YES;
2617 if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2618 LOG (GNUNET_ERROR_TYPE_WARNING,
2619 "MLP solver is not optimizing for utility\n");
2620
2621 if ((GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2622 (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2623 (GNUNET_NO == mlp->opt_dbg_optimize_relativity) &&
2624 (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2625 (GNUNET_NO == mlp->opt_dbg_feasibility_only))
2626 {
2627 LOG (GNUNET_ERROR_TYPE_ERROR,
2628 _ (
2629 "MLP solver is not optimizing for anything, changing to feasibility check\n"));
2630 mlp->opt_dbg_feasibility_only = GNUNET_YES;
2631 }
2632
2633 if (GNUNET_SYSERR == GNUNET_CONFIGURATION_get_value_string (env->cfg,
2634 "ats",
2635 "MLP_LOG_FORMAT",
2636 &outputformat))
2637 mlp->opt_log_format = MLP_CPLEX;
2638 else
2639 {
2640 GNUNET_STRINGS_utf8_toupper (outputformat, outputformat);
2641 if (0 == strcmp (outputformat, "MPS"))
2642 {
2643 mlp->opt_log_format = MLP_MPS;
2644 }
2645 else if (0 == strcmp (outputformat, "CPLEX"))
2646 {
2647 mlp->opt_log_format = MLP_CPLEX;
2648 }
2649 else if (0 == strcmp (outputformat, "GLPK"))
2650 {
2651 mlp->opt_log_format = MLP_GLPK;
2652 }
2653 else
2654 {
2655 LOG (GNUNET_ERROR_TYPE_WARNING,
2656 "Invalid log format `%s' in configuration, using CPLEX!\n",
2657 outputformat);
2658 mlp->opt_log_format = MLP_CPLEX;
2659 }
2660 GNUNET_free (outputformat);
2661 }
2662
2663 mlp->pv.BIG_M = (double) BIG_M_VALUE;
2664
2665 mlp->pv.mip_gap = (double) 0.0;
2666 if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2667 "MLP_MAX_MIP_GAP",
2668 &f_tmp))
2669 {
2670 if ((f_tmp < 0.0) || (f_tmp > 1.0))
2671 {
2672 LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2673 "MIP gap", f_tmp);
2674 }
2675 else
2676 {
2677 mlp->pv.mip_gap = f_tmp;
2678 LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2679 "MIP gap", f_tmp);
2680 }
2681 }
2682
2683 mlp->pv.lp_mip_gap = (double) 0.0;
2684 if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2685 "MLP_MAX_LP_MIP_GAP",
2686 &f_tmp))
2687 {
2688 if ((f_tmp < 0.0) || (f_tmp > 1.0))
2689 {
2690 LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2691 "LP/MIP", f_tmp);
2692 }
2693 else
2694 {
2695 mlp->pv.lp_mip_gap = f_tmp;
2696 LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2697 "LP/MIP", f_tmp);
2698 }
2699 }
2700
2701 /* Get timeout for iterations */
2702 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (env->cfg, "ats",
2703 "MLP_MAX_DURATION",
2704 &max_duration))
2705 {
2706 max_duration = MLP_MAX_EXEC_DURATION;
2707 }
2708
2709 /* Get maximum number of iterations */
2710 if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2711 "MLP_MAX_ITERATIONS",
2712 &max_iterations))
2713 {
2714 max_iterations = MLP_MAX_ITERATIONS;
2715 }
2716
2717 /* Get diversity coefficient from configuration */
2718 mlp->pv.co_D = MLP_DEFAULT_D;
2719 if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2720 "MLP_COEFFICIENT_D",
2721 &f_tmp))
2722 {
2723 if ((f_tmp < 0.0))
2724 {
2725 LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2726 "MLP_COEFFICIENT_D", f_tmp);
2727 }
2728 else
2729 {
2730 mlp->pv.co_D = f_tmp;
2731 LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2732 "MLP_COEFFICIENT_D", f_tmp);
2733 }
2734 }
2735
2736 /* Get relativity coefficient from configuration */
2737 mlp->pv.co_R = MLP_DEFAULT_R;
2738 if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2739 "MLP_COEFFICIENT_R",
2740 &f_tmp))
2741 {
2742 if ((f_tmp < 0.0))
2743 {
2744 LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2745 "MLP_COEFFICIENT_R", f_tmp);
2746 }
2747 else
2748 {
2749 mlp->pv.co_R = f_tmp;
2750 LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2751 "MLP_COEFFICIENT_R", f_tmp);
2752 }
2753 }
2754
2755
2756 /* Get utilization coefficient from configuration */
2757 mlp->pv.co_U = MLP_DEFAULT_U;
2758 if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2759 "MLP_COEFFICIENT_U",
2760 &f_tmp))
2761 {
2762 if ((f_tmp < 0.0))
2763 {
2764 LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2765 "MLP_COEFFICIENT_U", f_tmp);
2766 }
2767 else
2768 {
2769 mlp->pv.co_U = f_tmp;
2770 LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2771 "MLP_COEFFICIENT_U", f_tmp);
2772 }
2773 }
2774
2775 /* Get quality metric coefficients from configuration */
2776 for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
2777 {
2778 /* initialize quality coefficients with default value 1.0 */
2779 mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2780 }
2781
2782
2783 if (GNUNET_OK ==
2784 GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2785 "MLP_COEFFICIENT_QUALITY_DELAY",
2786 &tmp))
2787 mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double) tmp / 100;
2788 else
2789 mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = MLP_DEFAULT_QUALITY;
2790
2791 if (GNUNET_OK ==
2792 GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2793 "MLP_COEFFICIENT_QUALITY_DISTANCE",
2794 &tmp))
2795 mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double) tmp / 100;
2796 else
2797 mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = MLP_DEFAULT_QUALITY;
2798
2799 /* Get minimum bandwidth per used address from configuration */
2800 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2801 "MLP_MIN_BANDWIDTH",
2802 &tmp))
2803 b_min = tmp;
2804 else
2805 {
2806 b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2807 }
2808
2809 /* Get minimum number of connections from configuration */
2810 if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2811 "MLP_MIN_CONNECTIONS",
2812 &tmp))
2813 n_min = tmp;
2814 else
2815 n_min = MLP_DEFAULT_MIN_CONNECTIONS;
2816
2817 /* Init network quotas */
2818 for (c = 0; c < GNUNET_NT_COUNT; c++)
2819 {
2820 mlp->pv.quota_index[c] = c;
2821 mlp->pv.quota_out[c] = env->out_quota[c];
2822 mlp->pv.quota_in[c] = env->in_quota[c];
2823
2824 LOG (GNUNET_ERROR_TYPE_INFO,
2825 "Quota for network `%s' (in/out) %llu/%llu\n",
2826 GNUNET_NT_to_string (c),
2827 mlp->pv.quota_out[c],
2828 mlp->pv.quota_in[c]);
2829 /* Check if defined quota could make problem unsolvable */
2830 if ((n_min * b_min) > mlp->pv.quota_out[c])
2831 {
2832 LOG (GNUNET_ERROR_TYPE_INFO,
2833 _ (
2834 "Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2835 GNUNET_NT_to_string (mlp->pv.quota_index[c]),
2836 mlp->pv.quota_out[c],
2837 (n_min * b_min));
2838 mlp->pv.quota_out[c] = (n_min * b_min);
2839 }
2840 if ((n_min * b_min) > mlp->pv.quota_in[c])
2841 {
2842 LOG (GNUNET_ERROR_TYPE_INFO,
2843 _ (
2844 "Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2845 GNUNET_NT_to_string (mlp->pv.quota_index[c]),
2846 mlp->pv.quota_in[c],
2847 (n_min * b_min));
2848 mlp->pv.quota_in[c] = (n_min * b_min);
2849 }
2850 /* Check if bandwidth is too big to make problem solvable */
2851 if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2852 {
2853 LOG (GNUNET_ERROR_TYPE_INFO,
2854 _ (
2855 "Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2856 GNUNET_NT_to_string (mlp->pv.quota_index[c]),
2857 mlp->pv.quota_out[c],
2858 mlp->pv.BIG_M);
2859 mlp->pv.quota_out[c] = mlp->pv.BIG_M;
2860 }
2861 if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2862 {
2863 LOG (GNUNET_ERROR_TYPE_INFO,
2864 _ (
2865 "Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2866 GNUNET_NT_to_string (mlp->pv.quota_index[c]),
2867 mlp->pv.quota_in[c],
2868 mlp->pv.BIG_M);
2869 mlp->pv.quota_in[c] = mlp->pv.BIG_M;
2870 }
2871 }
2872 mlp->env = env;
2873 sf.cls = mlp;
2874 sf.s_add = &GAS_mlp_address_add;
2875 sf.s_address_update_property = &GAS_mlp_address_property_changed;
2876 sf.s_get = &GAS_mlp_get_preferred_address;
2877 sf.s_get_stop = &GAS_mlp_stop_get_preferred_address;
2878 sf.s_pref = &GAS_mlp_address_change_preference;
2879 sf.s_feedback = &GAS_mlp_address_preference_feedback;
2880 sf.s_del = &GAS_mlp_address_delete;
2881 sf.s_bulk_start = &GAS_mlp_bulk_start;
2882 sf.s_bulk_stop = &GAS_mlp_bulk_stop;
2883
2884 /* Setting MLP Input variables */
2885 mlp->pv.b_min = b_min;
2886 mlp->pv.n_min = n_min;
2887 mlp->pv.m_q = RQ_QUALITY_METRIC_COUNT;
2888 mlp->stat_mlp_prob_changed = GNUNET_NO;
2889 mlp->stat_mlp_prob_updated = GNUNET_NO;
2890 mlp->opt_mlp_auto_solve = GNUNET_YES;
2891 mlp->requested_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
2892 mlp->stat_bulk_requests = 0;
2893 mlp->stat_bulk_lock = 0;
2894
2895 /* Setup GLPK */
2896 /* Redirect GLPK output to GNUnet logging */
2897 glp_term_hook (&mlp_term_hook, (void *) mlp);
2898
2899 /* Init LP solving parameters */
2900 glp_init_smcp (&mlp->control_param_lp);
2901 mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2902 if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2903 mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2904
2905 mlp->control_param_lp.it_lim = max_iterations;
2906 mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2907
2908 /* Init MLP solving parameters */
2909 glp_init_iocp (&mlp->control_param_mlp);
2910 /* Setting callback function */
2911 mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2912 mlp->control_param_mlp.cb_info = mlp;
2913 mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2914 mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2915 if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2916 mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2917 mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2918
2919 LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2920
2921 return &sf;
2922}
2923
2924/* end of plugin_ats_mlp.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-26 22:35:44 +0000