aboutsummaryrefslogtreecommitdiff
path: root/src/transport/gnunet-service-transport_ats.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/transport/gnunet-service-transport_ats.c')
-rw-r--r--src/transport/gnunet-service-transport_ats.c1754
1 files changed, 0 insertions, 1754 deletions
diff --git a/src/transport/gnunet-service-transport_ats.c b/src/transport/gnunet-service-transport_ats.c
deleted file mode 100644
index 220fe522b..000000000
--- a/src/transport/gnunet-service-transport_ats.c
+++ /dev/null
@@ -1,1754 +0,0 @@
1/*
2 This file is part of GNUnet.
3 (C) 2009, 2010 Christian Grothoff (and other contributing authors)
4
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.
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 General Public License for more details.
14
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.
19*/
20
21/**
22 * @file transport/gnunet-service-transport_ats.c
23 * @brief automatic transport selection
24 * @author Matthias Wachs
25 *
26 */
27
28
29#include "gnunet-service-transport_ats.h"
30#include "gnunet_transport_service.h"
31#include "gnunet_statistics_service.h"
32#include "gnunet_container_lib.h"
33
34
35
36
37
38/* LP/MIP problem object */
39
40#if !HAVE_LIBGLPK
41
42#ifndef GLP_PROB_DEFINED
43#define GLP_PROB_DEFINED
44typedef struct
45{
46 double _opaque_prob[100];
47} glp_prob;
48#endif
49
50typedef struct
51{ /* integer optimizer control parameters */
52 int msg_lev; /* message level (see glp_smcp) */
53 int br_tech; /* branching technique: */
54#define GLP_BR_FFV 1 /* first fractional variable */
55#define GLP_BR_LFV 2 /* last fractional variable */
56#define GLP_BR_MFV 3 /* most fractional variable */
57#define GLP_BR_DTH 4 /* heuristic by Driebeck and Tomlin */
58#define GLP_BR_PCH 5 /* hybrid pseudocost heuristic */
59 int bt_tech; /* backtracking technique: */
60#define GLP_BT_DFS 1 /* depth first search */
61#define GLP_BT_BFS 2 /* breadth first search */
62#define GLP_BT_BLB 3 /* best local bound */
63#define GLP_BT_BPH 4 /* best projection heuristic */
64 double tol_int; /* mip.tol_int */
65 double tol_obj; /* mip.tol_obj */
66 int tm_lim; /* mip.tm_lim (milliseconds) */
67 int out_frq; /* mip.out_frq (milliseconds) */
68 int out_dly; /* mip.out_dly (milliseconds) */
69 /* mip.cb_func */
70 void *cb_info; /* mip.cb_info */
71 int cb_size; /* mip.cb_size */
72 int pp_tech; /* preprocessing technique: */
73#define GLP_PP_NONE 0 /* disable preprocessing */
74#define GLP_PP_ROOT 1 /* preprocessing only on root level */
75#define GLP_PP_ALL 2 /* preprocessing on all levels */
76 double mip_gap; /* relative MIP gap tolerance */
77 int mir_cuts; /* MIR cuts (GLP_ON/GLP_OFF) */
78 int gmi_cuts; /* Gomory's cuts (GLP_ON/GLP_OFF) */
79 int cov_cuts; /* cover cuts (GLP_ON/GLP_OFF) */
80 int clq_cuts; /* clique cuts (GLP_ON/GLP_OFF) */
81 int presolve; /* enable/disable using MIP presolver */
82 int binarize; /* try to binarize integer variables */
83 int fp_heur; /* feasibility pump heuristic */
84#if 1 /* 28/V-2010 */
85 int alien; /* use alien solver */
86#endif
87 double foo_bar[29]; /* (reserved) */
88} glp_iocp;
89
90typedef struct
91{ /* simplex method control parameters */
92 int msg_lev; /* message level: */
93#define GLP_MSG_OFF 0 /* no output */
94#define GLP_MSG_ERR 1 /* warning and error messages only */
95#define GLP_MSG_ON 2 /* normal output */
96#define GLP_MSG_ALL 3 /* full output */
97#define GLP_MSG_DBG 4 /* debug output */
98 int meth; /* simplex method option: */
99#define GLP_PRIMAL 1 /* use primal simplex */
100#define GLP_DUALP 2 /* use dual; if it fails, use primal */
101#define GLP_DUAL 3 /* use dual simplex */
102 int pricing; /* pricing technique: */
103#define GLP_PT_STD 0x11 /* standard (Dantzig rule) */
104#define GLP_PT_PSE 0x22 /* projected steepest edge */
105 int r_test; /* ratio test technique: */
106#define GLP_RT_STD 0x11 /* standard (textbook) */
107#define GLP_RT_HAR 0x22 /* two-pass Harris' ratio test */
108 double tol_bnd; /* spx.tol_bnd */
109 double tol_dj; /* spx.tol_dj */
110 double tol_piv; /* spx.tol_piv */
111 double obj_ll; /* spx.obj_ll */
112 double obj_ul; /* spx.obj_ul */
113 int it_lim; /* spx.it_lim */
114 int tm_lim; /* spx.tm_lim (milliseconds) */
115 int out_frq; /* spx.out_frq */
116 int out_dly; /* spx.out_dly (milliseconds) */
117 int presolve; /* enable/disable using LP presolver */
118 double foo_bar[36]; /* (reserved) */
119} glp_smcp;
120
121/* optimization direction flag: */
122#define GLP_MIN 1 /* minimization */
123#define GLP_MAX 2 /* maximization */
124
125/* kind of structural variable: */
126#define GLP_CV 1 /* continuous variable */
127#define GLP_IV 2 /* integer variable */
128#define GLP_BV 3 /* binary variable */
129
130/* type of auxiliary/structural variable: */
131#define GLP_FR 1 /* free variable */
132#define GLP_LO 2 /* variable with lower bound */
133#define GLP_UP 3 /* variable with upper bound */
134#define GLP_DB 4 /* double-bounded variable */
135#define GLP_FX 5 /* fixed variable */
136
137/* solution indicator: */
138#define GLP_SOL 1 /* basic solution */
139#define GLP_IPT 2 /* interior-point solution */
140#define GLP_MIP 3 /* mixed integer solution */
141
142/* solution status: */
143#define GLP_UNDEF 1 /* solution is undefined */
144#define GLP_FEAS 2 /* solution is feasible */
145#define GLP_INFEAS 3 /* solution is infeasible */
146#define GLP_NOFEAS 4 /* no feasible solution exists */
147#define GLP_OPT 5 /* solution is optimal */
148#define GLP_UNBND 6 /* solution is unbounded */
149
150/* return codes: */
151#define GLP_EBADB 0x01 /* invalid basis */
152#define GLP_ESING 0x02 /* singular matrix */
153#define GLP_ECOND 0x03 /* ill-conditioned matrix */
154#define GLP_EBOUND 0x04 /* invalid bounds */
155#define GLP_EFAIL 0x05 /* solver failed */
156#define GLP_EOBJLL 0x06 /* objective lower limit reached */
157#define GLP_EOBJUL 0x07 /* objective upper limit reached */
158#define GLP_EITLIM 0x08 /* iteration limit exceeded */
159#define GLP_ETMLIM 0x09 /* time limit exceeded */
160#define GLP_ENOPFS 0x0A /* no primal feasible solution */
161#define GLP_ENODFS 0x0B /* no dual feasible solution */
162#define GLP_EROOT 0x0C /* root LP optimum not provided */
163#define GLP_ESTOP 0x0D /* search terminated by application */
164#define GLP_EMIPGAP 0x0E /* relative mip gap tolerance reached */
165#define GLP_ENOFEAS 0x0F /* no primal/dual feasible solution */
166#define GLP_ENOCVG 0x10 /* no convergence */
167#define GLP_EINSTAB 0x11 /* numerical instability */
168#define GLP_EDATA 0x12 /* invalid data */
169#define GLP_ERANGE 0x13 /* result out of range */
170
171/* enable/disable flag: */
172#define GLP_ON 1 /* enable something */
173#define GLP_OFF 0 /* disable something */
174
175#endif
176
177/*
178 * Wrappers for GLPK Functions
179 */
180
181
182void *
183_lp_create_prob (void)
184{
185#if HAVE_LIBGLPK
186 return glp_create_prob ();
187#else
188 // Function not implemented
189 GNUNET_break (0);
190#endif
191 return NULL;
192}
193
194void
195_lp_set_obj_dir (glp_prob *P, int dir)
196{
197#if HAVE_LIBGLPK
198 return glp_set_obj_dir (P, dir);
199#else
200 // Function not implemented
201 GNUNET_break (0);
202#endif
203}
204
205void
206_lp_set_prob_name (glp_prob *P, const char *name)
207{
208#if HAVE_LIBGLPK
209 glp_set_prob_name (P, name);
210#else
211 // Function not implemented
212 GNUNET_break (0);
213#endif
214}
215
216int
217_lp_add_cols (glp_prob *P, int ncs)
218{
219#if HAVE_LIBGLPK
220 return glp_add_cols (P, ncs);
221#else
222 // Function not implemented
223 GNUNET_break (0);
224#endif
225 return 0;
226}
227
228int
229_lp_add_rows (glp_prob *P, int nrs)
230{
231#if HAVE_LIBGLPK
232 return glp_add_rows (P, nrs);
233#else
234 // Function not implemented
235 GNUNET_break (0);
236#endif
237 return 0;
238}
239
240
241void
242_lp_set_row_bnds (glp_prob *P, int i, int type, double lb, double ub)
243{
244#if HAVE_LIBGLPK
245 glp_set_row_bnds (P, i, type, lb, ub);
246#else
247 // Function not implemented
248 GNUNET_break (0);
249#endif
250}
251
252void
253_lp_init_smcp (void *parm)
254{
255#if HAVE_LIBGLPK
256 glp_init_smcp (parm);
257#else
258 // Function not implemented
259 GNUNET_break (0);
260#endif
261}
262
263void
264_lp_set_col_name (glp_prob *P, int j, const char *name)
265{
266#if HAVE_LIBGLPK
267 glp_set_col_name (P, j, name);
268#else
269 // Function not implemented
270 GNUNET_break (0);
271#endif
272}
273
274void
275_lp_set_col_bnds (glp_prob *P, int j, int type, double lb, double ub)
276{
277#if HAVE_LIBGLPK
278 glp_set_col_bnds (P, j, type, lb, ub);
279#else
280 // Function not implemented
281 GNUNET_break (0);
282#endif
283}
284
285void
286_lp_set_obj_coef (glp_prob *P, int j, double coef)
287{
288#if HAVE_LIBGLPK
289 glp_set_obj_coef (P, j, coef);
290#else
291 // Function not implemented
292 GNUNET_break (0);
293#endif
294}
295
296void
297_lp_delete_prob (void *P)
298{
299#if HAVE_LIBGLPK
300 glp_delete_prob (P);
301#else
302 // Function not implemented
303 GNUNET_break (0);
304#endif
305}
306
307static int
308_lp_simplex (glp_prob *P, void *parm)
309{
310#if HAVE_LIBGLPK
311 return glp_simplex (P, parm);
312#else
313 // Function not implemented
314 GNUNET_break (0);
315#endif
316 return 0;
317}
318
319static void
320_lp_load_matrix (glp_prob *P, int ne, const int ia[], const int ja[],
321 const double ar[])
322{
323#if HAVE_LIBGLPK
324 glp_load_matrix (P, ne, ia, ja, ar);
325#else
326 // Function not implemented
327 GNUNET_break (0);
328#endif
329}
330
331static void
332_lp_set_mat_row (glp_prob *P, int i, int len, const int ind[],
333 const double val[])
334{
335#if HAVE_LIBGLPK
336 glp_set_mat_row (P, i, len, ind, val);
337#else
338 // Function not implemented
339 GNUNET_break (0);
340#endif
341}
342
343static int
344_lp_write_lp (glp_prob *P, const void *parm, const char *fname)
345{
346#if HAVE_LIBGLPK
347 return glp_write_lp (P, parm, fname);
348#else
349 // Function not implemented
350 GNUNET_break (0);
351#endif
352 return 0;
353}
354
355static void
356_lp_init_iocp (void *parm)
357{
358#if HAVE_LIBGLPK
359 glp_init_iocp (parm);
360#else
361 // Function not implemented
362 GNUNET_break (0);
363#endif
364}
365
366static int
367_lp_intopt (glp_prob *P, const void *parm)
368{
369#if HAVE_LIBGLPK
370 return glp_intopt (P, parm);
371#else
372 // Function not implemented
373 GNUNET_break (0);
374#endif
375 return 0;
376}
377
378static int
379_lp_get_status (glp_prob *P)
380{
381#if HAVE_LIBGLPK
382 return glp_get_status (P);
383#else
384 // Function not implemented
385 GNUNET_break (0);
386#endif
387 return 0;
388}
389
390static int
391_lp_mip_status (glp_prob *P)
392{
393#if HAVE_LIBGLPK
394 return glp_mip_status (P);
395#else
396 // Function not implemented
397 GNUNET_break (0);
398#endif
399 return 0;
400}
401
402static void
403_lp_set_col_kind (glp_prob *P, int j, int kind)
404{
405#if HAVE_LIBGLPK
406 glp_set_col_kind (P, j, kind);
407#else
408 // Function not implemented
409 GNUNET_break (0);
410#endif
411}
412
413static void
414_lp_free_env (void)
415{
416#if HAVE_LIBGLPK
417 glp_free_env ();
418#else
419 // Function not implemented
420 GNUNET_break (0);
421#endif
422}
423
424static const char *
425_lp_get_col_name (glp_prob *P, int j)
426{
427#if HAVE_LIBGLPK
428 return glp_get_col_name (P, j);
429#else
430 // Function not implemented
431 GNUNET_break (0);
432#endif
433 return NULL;
434}
435
436static double
437_lp_mip_obj_val (glp_prob *P)
438{
439#if HAVE_LIBGLPK
440 return glp_mip_obj_val (P);
441#else
442 // Function not implemented
443 GNUNET_break (0);
444#endif
445 return 0.0;
446}
447
448
449static double
450_lp_get_col_prim (glp_prob *P, int j)
451{
452#if HAVE_LIBGLPK
453 return glp_get_col_prim (P, j);
454#else
455 // Function not implemented
456 GNUNET_break (0);
457#endif
458 return 0.0;
459}
460
461static int
462_lp_print_sol (glp_prob *P, const char *fname)
463{
464#if HAVE_LIBGLPK
465#else
466 // Function not implemented
467 GNUNET_break (0);
468#endif
469 return 0;
470}
471
472/*
473 * Dummy functions for CFLAGS
474 */
475
476static void
477_dummy2 ();
478static void
479_dummy ()
480{
481 return;
482 _lp_get_col_name (NULL, 0);
483 _lp_mip_obj_val (NULL);
484 _lp_get_col_prim (NULL, 0);
485 _lp_set_mat_row (NULL, 0, 0, NULL, NULL);
486 _dummy2 ();
487}
488
489
490
491static void
492_dummy2 ()
493{
494 ats_modify_problem_state (NULL, 0);
495 qm[1].atis_index = 0;
496 _dummy ();
497 int t = ATS_COST_UPDATED + ATS_MODIFIED + ATS_NEW;
498
499 t++;
500}
501
502/*
503 * ATS Functions
504 */
505
506
507/**
508 * Initialize ATS
509 * @param cfg configuration handle to retrieve configuration (to be removed)
510 * @return
511 */
512
513struct ATS_Handle *
514ats_init (double D, double U, double R, int v_b_min, int v_n_min,
515 int max_iterations, struct GNUNET_TIME_Relative max_duration,
516 GNUNET_TRANSPORT_ATS_AddressNotification address_not,
517 GNUNET_TRANSPORT_ATS_ResultCallback res_cb)
518{
519 struct ATS_Handle *ats = NULL;
520
521 ats = GNUNET_malloc (sizeof (struct ATS_Handle));
522
523 ats->prob = NULL;
524
525 ats->addr_notification = address_not;
526 ats->result_cb = res_cb;
527
528 ats->max_iterations = max_iterations;
529 ats->max_exec_duration = max_duration;
530
531 ats->D = D;
532 ats->U = U;
533 ats->R = R;
534 ats->v_b_min = v_b_min;
535 ats->v_n_min = v_n_min;
536 ats->dump_min_peers = 0;
537 ats->dump_min_addr = 0;
538 ats->dump_overwrite = GNUNET_NO;
539 ats->mechanisms = NULL;
540 ats->peers = NULL;
541 ats->successful_executions = 0;
542 ats->invalid_executions = 0;
543
544 return ats;
545}
546
547
548/** solve the bandwidth distribution problem
549 * @param max_it maximum iterations
550 * @param max_dur maximum duration in ms
551 * @param D weight for diversity
552 * @param U weight for utility
553 * @param R weight for relativity
554 * @param v_b_min minimal bandwidth per peer
555 * @param v_n_min minimum number of connections
556 * @param stat result struct
557 * @return GNUNET_SYSERR if glpk is not available, number of mechanisms used
558 */
559int
560ats_create_problem (struct ATS_Handle *ats, struct ATS_internals *stat,
561 struct ATS_peer *peers, int c_p,
562 struct ATS_mechanism *mechanisms, int c_m)
563{
564 if ((c_p == 0) || (c_m == 0))
565 return GNUNET_SYSERR;
566
567 ats->prob = _lp_create_prob ();
568
569 int c;
570 int c_c_ressources = available_ressources;
571 int c_q_metrics = available_quality_metrics;
572
573 double M = VERY_BIG_DOUBLE_VALUE;
574 double Q[c_q_metrics + 1];
575
576 for (c = 1; c <= c_q_metrics; c++)
577 {
578 Q[c] = 1;
579 }
580
581 if (ats->v_n_min > c_p)
582 ats->v_n_min = c_p;
583#if VERBOSE_ATS
584 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
585 "Creating problem with: %i peers, %i mechanisms, %i resource entries, %i quality metrics \n",
586 c_p, c_m, c_c_ressources, c_q_metrics);
587#endif
588
589 int size =
590 1 + 3 + 10 * c_m + c_p + (c_q_metrics * c_m) + c_q_metrics +
591 c_c_ressources * c_m;
592 int row_index;
593 int array_index = 1;
594 int *ia = GNUNET_malloc (size * sizeof (int));
595 int *ja = GNUNET_malloc (size * sizeof (int));
596 double *ar = GNUNET_malloc (size * sizeof (double));
597
598 _lp_set_prob_name (ats->prob, "gnunet ats bandwidth distribution");
599 _lp_set_obj_dir (ats->prob, GLP_MAX);
600
601 /* adding columns */
602 char *name;
603
604 _lp_add_cols (ats->prob, 2 * c_m);
605 /* adding b_t cols */
606 for (c = 1; c <= c_m; c++)
607 {
608 GNUNET_asprintf (&name, "p_%s_b%i",
609 GNUNET_i2s (&(mechanisms[c].peer->peer)), c);
610 _lp_set_col_name (ats->prob, c, name);
611 GNUNET_free (name);
612 _lp_set_col_bnds (ats->prob, c, GLP_LO, 0.0, 0.0);
613 _lp_set_col_kind (ats->prob, c, GLP_CV);
614 _lp_set_obj_coef (ats->prob, c, 0);
615 }
616
617 /* adding n_t cols */
618 for (c = c_m + 1; c <= 2 * c_m; c++)
619 {
620 GNUNET_asprintf (&name, "p_%s_n%i",
621 GNUNET_i2s (&(mechanisms[c - c_m].peer->peer)), (c - c_m));
622 _lp_set_col_name (ats->prob, c, name);
623 GNUNET_free (name);
624 _lp_set_col_bnds (ats->prob, c, GLP_DB, 0.0, 1.0);
625 _lp_set_col_kind (ats->prob, c, GLP_IV);
626 _lp_set_obj_coef (ats->prob, c, 0);
627 }
628
629 /* feasibility constraints */
630 /* Constraint 1: one address per peer */
631 row_index = 1;
632
633 _lp_add_rows (ats->prob, c_p);
634
635 for (c = 1; c <= c_p; c++)
636 {
637#if VERBOSE_ATS
638 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
639#endif
640
641 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 1.0, 1.0);
642 struct ATS_mechanism *m = peers[c].m_head;
643
644 while (m != NULL)
645 {
646 ia[array_index] = row_index;
647 ja[array_index] = (c_m + m->col_index);
648 ar[array_index] = 1;
649#if VERBOSE_ATS
650 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
651 array_index, ia[array_index], ja[array_index],
652 ar[array_index]);
653#endif
654 array_index++;
655 m = m->next;
656 }
657 row_index++;
658 }
659
660 /* Constraint 2: only active mechanism gets bandwidth assigned */
661 _lp_add_rows (ats->prob, c_m);
662 for (c = 1; c <= c_m; c++)
663 {
664 /* b_t - n_t * M <= 0 */
665#if VERBOSE_ATS
666 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
667#endif
668 _lp_set_row_bnds (ats->prob, row_index, GLP_UP, 0.0, 0.0);
669 ia[array_index] = row_index;
670 ja[array_index] = mechanisms[c].col_index;
671 ar[array_index] = 1;
672#if VERBOSE_ATS
673 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
674 array_index, ia[array_index], ja[array_index], ar[array_index]);
675#endif
676 array_index++;
677 ia[array_index] = row_index;
678 ja[array_index] = c_m + mechanisms[c].col_index;
679 ar[array_index] = -M;
680#if VERBOSE_ATS
681 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
682 array_index, ia[array_index], ja[array_index], ar[array_index]);
683#endif
684 array_index++;
685 row_index++;
686 }
687
688 /* Constraint 3: minimum bandwidth */
689 _lp_add_rows (ats->prob, c_m);
690
691 for (c = 1; c <= c_m; c++)
692 {
693 /* b_t - n_t * b_min <= 0 */
694#if VERBOSE_ATS
695 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
696#endif
697#if HAVE_LIBGLPK
698 _lp_set_row_bnds (ats->prob, row_index, GLP_LO, 0.0, 0.0);
699#endif
700 ia[array_index] = row_index;
701 ja[array_index] = mechanisms[c].col_index;
702 ar[array_index] = 1;
703#if VERBOSE_ATS
704 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
705 array_index, ia[array_index], ja[array_index], ar[array_index]);
706#endif
707 array_index++;
708 ia[array_index] = row_index;
709 ja[array_index] = c_m + mechanisms[c].col_index;
710 ar[array_index] = -ats->v_b_min;
711#if VERBOSE_ATS
712 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
713 array_index, ia[array_index], ja[array_index], ar[array_index]);
714#endif
715 array_index++;
716 row_index++;
717 }
718 int c2;
719
720 /* Constraint 4: max ressource capacity */
721 /* V cr: bt * ct_r <= cr_max
722 * */
723
724 _lp_add_rows (ats->prob, available_ressources);
725
726 double ct_max = VERY_BIG_DOUBLE_VALUE;
727 double ct_min = 0.0;
728
729 stat->begin_cr = array_index;
730
731 for (c = 0; c < available_ressources; c++)
732 {
733 ct_max = ressources[c].c_max;
734 ct_min = ressources[c].c_min;
735#if VERBOSE_ATS
736 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] %f..%f\n",
737 row_index, ct_min, ct_max);
738#endif
739#if HAVE_LIBGLPK
740 _lp_set_row_bnds (ats->prob, row_index, GLP_DB, ct_min, ct_max);
741#endif
742 for (c2 = 1; c2 <= c_m; c2++)
743 {
744 double value = 0;
745
746 ia[array_index] = row_index;
747 ja[array_index] = c2;
748 value = mechanisms[c2].ressources[c].c;
749 ar[array_index] = value;
750#if VERBOSE_ATS
751 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
752 array_index, ia[array_index], ja[array_index],
753 ar[array_index]);
754#endif
755 array_index++;
756 }
757 row_index++;
758 }
759 stat->end_cr = array_index--;
760
761 /* Constraint 5: min number of connections */
762 _lp_add_rows (ats->prob, 1);
763
764 for (c = 1; c <= c_m; c++)
765 {
766 // b_t - n_t * b_min >= 0
767#if VERBOSE_ATS
768 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
769#endif
770 _lp_set_row_bnds (ats->prob, row_index, GLP_LO, ats->v_n_min, 0.0);
771 ia[array_index] = row_index;
772 ja[array_index] = c_m + mechanisms[c].col_index;
773 ar[array_index] = 1;
774#if VERBOSE_ATS
775 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
776 array_index, ia[array_index], ja[array_index], ar[array_index]);
777#endif
778 array_index++;
779 }
780 row_index++;
781
782 // optimisation constraints
783
784 // adding columns
785
786 // Constraint 6: optimize for diversity
787 int col_d;
788
789 col_d = _lp_add_cols (ats->prob, 1);
790
791 _lp_set_col_name (ats->prob, col_d, "d");
792 _lp_set_obj_coef (ats->prob, col_d, ats->D);
793 _lp_set_col_bnds (ats->prob, col_d, GLP_LO, 0.0, 0.0);
794 _lp_add_rows (ats->prob, 1);
795 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
796
797 stat->col_d = col_d;
798#if VERBOSE_ATS
799 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
800#endif
801 for (c = 1; c <= c_m; c++)
802 {
803 ia[array_index] = row_index;
804 ja[array_index] = c_m + mechanisms[c].col_index;
805 ar[array_index] = 1;
806#if VERBOSE_ATS
807 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
808 array_index, ia[array_index], ja[array_index], ar[array_index]);
809#endif
810 array_index++;
811 }
812 ia[array_index] = row_index;
813 ja[array_index] = col_d;
814 ar[array_index] = -1;
815#if VERBOSE_ATS
816 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
817 array_index, ia[array_index], ja[array_index], ar[array_index]);
818#endif
819 array_index++;
820 row_index++;
821
822 // Constraint 7: optimize for quality
823 int col_qm;
824
825 col_qm = _lp_add_cols (ats->prob, c_q_metrics);
826
827 stat->col_qm = col_qm;
828 //GNUNET_assert (col_qm == (2*c_mechs) + 3 + 1);
829 for (c = 0; c < c_q_metrics; c++)
830 {
831 GNUNET_asprintf (&name, "Q_%s", qm[c].name);
832 _lp_set_col_name (ats->prob, col_qm + c, name);
833 _lp_set_col_bnds (ats->prob, col_qm + c, GLP_LO, 0.0, 0.0);
834 GNUNET_free (name);
835 _lp_set_obj_coef (ats->prob, col_qm + c, Q[c]);
836 }
837
838 _lp_add_rows (ats->prob, available_quality_metrics);
839
840 stat->begin_qm = row_index;
841 for (c = 1; c <= c_q_metrics; c++)
842 {
843#if VERBOSE_ATS
844 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
845#endif
846 double value = 1;
847
848 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
849 for (c2 = 1; c2 <= c_m; c2++)
850 {
851 ia[array_index] = row_index;
852 ja[array_index] = c2;
853 if (qm[c - 1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY)
854 {
855 double v0 = 0, v1 = 0, v2 = 0;
856
857 v0 = mechanisms[c2].quality[c - 1].values[0];
858 if (v1 < 1)
859 v0 = 0.1;
860 v1 = mechanisms[c2].quality[c - 1].values[1];
861 if (v1 < 1)
862 v0 = 0.1;
863 v2 = mechanisms[c2].quality[c - 1].values[2];
864 if (v1 < 1)
865 v0 = 0.1;
866 value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0);
867 value = 1;
868 }
869 if (qm[c - 1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE)
870 {
871 double v0 = 0, v1 = 0, v2 = 0;
872
873 v0 = mechanisms[c2].quality[c - 1].values[0];
874 if (v0 < 1)
875 v0 = 1;
876 v1 = mechanisms[c2].quality[c - 1].values[1];
877 if (v1 < 1)
878 v1 = 1;
879 v2 = mechanisms[c2].quality[c - 1].values[2];
880 if (v2 < 1)
881 v2 = 1;
882 value = (v0 + 2 * v1 + 3 * v2) / 6.0;
883 if (value >= 1)
884 value = (double) 10 / value;
885 else
886 value = 10;
887 }
888 ar[array_index] = (mechanisms[c2].peer->f) * value;
889#if VERBOSE_ATS
890 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",
891 array_index, qm[c - 1].name, ia[array_index], ja[array_index],
892 ar[array_index]);
893#endif
894 array_index++;
895 }
896 ia[array_index] = row_index;
897 ja[array_index] = col_qm + c - 1;
898 ar[array_index] = -1;
899#if VERBOSE_ATS
900 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
901 array_index, ia[array_index], ja[array_index], ar[array_index]);
902#endif
903 array_index++;
904 row_index++;
905 }
906 stat->end_qm = row_index - 1;
907
908 // Constraint 8: optimize bandwidth utility
909 int col_u;
910
911 col_u = _lp_add_cols (ats->prob, 1);
912
913 _lp_set_col_name (ats->prob, col_u, "u");
914 _lp_set_obj_coef (ats->prob, col_u, ats->U);
915 _lp_set_col_bnds (ats->prob, col_u, GLP_LO, 0.0, 0.0);
916 _lp_add_rows (ats->prob, 1);
917 stat->col_u = col_u;
918#if VERBOSE_ATS
919 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
920#endif
921 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
922 for (c = 1; c <= c_m; c++)
923 {
924 ia[array_index] = row_index;
925 ja[array_index] = c;
926 ar[array_index] = mechanisms[c].peer->f;
927#if VERBOSE_ATS
928 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
929 array_index, ia[array_index], ja[array_index], ar[array_index]);
930#endif
931 array_index++;
932 }
933 ia[array_index] = row_index;
934 ja[array_index] = col_u;
935 ar[array_index] = -1;
936#if VERBOSE_ATS
937 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
938 array_index, ia[array_index], ja[array_index], ar[array_index]);
939#endif
940
941 array_index++;
942 row_index++;
943
944 // Constraint 9: optimize relativity
945 int col_r;
946
947 col_r = _lp_add_cols (ats->prob, 1);
948
949 _lp_set_col_name (ats->prob, col_r, "r");
950 _lp_set_obj_coef (ats->prob, col_r, ats->R);
951 _lp_set_col_bnds (ats->prob, col_r, GLP_LO, 0.0, 0.0);
952 _lp_add_rows (ats->prob, c_p);
953
954 stat->col_r = col_r;
955 for (c = 1; c <= c_p; c++)
956 {
957 _lp_set_row_bnds (ats->prob, row_index, GLP_LO, 0.0, 0.0);
958 struct ATS_mechanism *m = peers[c].m_head;
959
960 while (m != NULL)
961 {
962 ia[array_index] = row_index;
963 ja[array_index] = m->col_index;
964 ar[array_index] = 1 / mechanisms[c].peer->f;
965#if VERBOSE_ATS
966 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
967 array_index, ia[array_index], ja[array_index],
968 ar[array_index]);
969#endif
970 array_index++;
971 m = m->next;
972 }
973 ia[array_index] = row_index;
974 ja[array_index] = col_r;
975 ar[array_index] = -1;
976#if VERBOSE_ATS
977 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
978 array_index, ia[array_index], ja[array_index], ar[array_index]);
979#endif
980 array_index++;
981 row_index++;
982 }
983
984 /* Loading the matrix */
985 _lp_load_matrix (ats->prob, array_index - 1, ia, ja, ar);
986
987 stat->c_mechs = c_m;
988 stat->c_peers = c_p;
989 stat->solution = 0;
990 stat->valid = GNUNET_YES;
991
992 /* clean up */
993 GNUNET_free (ja);
994 GNUNET_free (ia);
995 GNUNET_free (ar);
996
997 return GNUNET_OK;
998}
999
1000
1001void
1002ats_delete_problem (struct ATS_Handle *ats)
1003{
1004#if DEBUG_ATS
1005 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting problem\n");
1006#endif
1007 int c;
1008
1009 for (c = 0; c < (ats->internal).c_mechs; c++)
1010 GNUNET_free_non_null (ats->mechanisms[c].rc);
1011 if (ats->mechanisms != NULL)
1012 {
1013 GNUNET_free (ats->mechanisms);
1014 ats->mechanisms = NULL;
1015 }
1016
1017 if (ats->peers != NULL)
1018 {
1019 GNUNET_free (ats->peers);
1020 ats->peers = NULL;
1021 }
1022
1023 if (ats->prob != NULL)
1024 {
1025 _lp_delete_prob (ats->prob);
1026 ats->prob = NULL;
1027 }
1028
1029 ats->internal.begin_cr = GNUNET_SYSERR;
1030 ats->internal.begin_qm = GNUNET_SYSERR;
1031 ats->internal.c_mechs = 0;
1032 ats->internal.c_peers = 0;
1033 ats->internal.end_cr = GNUNET_SYSERR;
1034 ats->internal.end_qm = GNUNET_SYSERR;
1035 ats->internal.solution = GNUNET_SYSERR;
1036 ats->internal.valid = GNUNET_SYSERR;
1037}
1038
1039void
1040ats_modify_problem_state (struct ATS_Handle *ats, enum ATS_problem_state s)
1041{
1042 if (ats == NULL)
1043 return;
1044 switch (s)
1045 {
1046 case ATS_NEW:
1047 ats->internal.recreate_problem = GNUNET_NO;
1048 ats->internal.modified_quality = GNUNET_NO;
1049 ats->internal.modified_resources = GNUNET_NO;
1050 break;
1051 case ATS_MODIFIED:
1052 ats->internal.recreate_problem = GNUNET_YES;
1053 break;
1054 case ATS_QUALITY_UPDATED:
1055 ats->internal.modified_quality = GNUNET_YES;
1056 break;
1057 case ATS_COST_UPDATED:
1058 ats->internal.modified_resources = GNUNET_YES;
1059 break;
1060 case ATS_QUALITY_COST_UPDATED:
1061 ats->internal.modified_resources = GNUNET_YES;
1062 ats->internal.modified_quality = GNUNET_YES;
1063 break;
1064 default:
1065 return;
1066 }
1067
1068
1069
1070}
1071
1072void
1073ats_solve_problem (struct ATS_Handle *ats, unsigned int max_it,
1074 unsigned int max_dur, unsigned int c_peers,
1075 unsigned int c_mechs, struct ATS_internals *stat)
1076{
1077 int result = GNUNET_SYSERR;
1078 int lp_solution = GNUNET_SYSERR;
1079 int mlp_solution = GNUNET_SYSERR;
1080
1081 // Solving simplex
1082
1083 glp_smcp opt_lp;
1084
1085 _lp_init_smcp (&opt_lp);
1086#if VERBOSE_ATS
1087 opt_lp.msg_lev = GLP_MSG_ALL;
1088#else
1089 opt_lp.msg_lev = GLP_MSG_OFF;
1090#endif
1091 // setting iteration limit
1092 opt_lp.it_lim = max_it;
1093 // maximum duration
1094 opt_lp.tm_lim = max_dur;
1095
1096 if (ats->internal.recreate_problem == GNUNET_YES)
1097 opt_lp.presolve = GLP_ON;
1098
1099 result = _lp_simplex (ats->prob, &opt_lp);
1100 lp_solution = _lp_get_status (ats->prob);
1101
1102 if ((result == GLP_ETMLIM) || (result == GLP_EITLIM))
1103 {
1104 ats->internal.valid = GNUNET_NO;
1105 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1106 "ATS exceeded time or iteration limit!\n");
1107 return;
1108 }
1109
1110 if (ats_evaluate_results (result, lp_solution, "LP") == GNUNET_YES)
1111 {
1112 stat->valid = GNUNET_YES;
1113 }
1114 else
1115 {
1116 ats->internal.simplex_rerun_required = GNUNET_YES;
1117 opt_lp.presolve = GLP_ON;
1118 result = _lp_simplex (ats->prob, &opt_lp);
1119 lp_solution = _lp_get_status (ats->prob);
1120
1121 // TODO: Remove if this does not appear until release
1122 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1123 "" "EXECUTED SIMPLEX WITH PRESOLVER! %i \n", lp_solution);
1124
1125 if (ats_evaluate_results (result, lp_solution, "LP") != GNUNET_YES)
1126 {
1127 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1128 "After execution simplex with presolver: STILL INVALID!\n");
1129 char *filename;
1130
1131 GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%llu.mlp",
1132 ats->internal.c_peers, ats->internal.c_mechs,
1133 GNUNET_TIME_absolute_get ().abs_value);
1134 _lp_write_lp ((void *) ats->prob, NULL, filename);
1135 GNUNET_free (filename);
1136 stat->valid = GNUNET_NO;
1137 ats->internal.recreate_problem = GNUNET_YES;
1138 return;
1139 }
1140 stat->valid = GNUNET_YES;
1141 }
1142
1143 // Solving mlp
1144 glp_iocp opt_mlp;
1145
1146 _lp_init_iocp (&opt_mlp);
1147 // maximum duration
1148 opt_mlp.tm_lim = max_dur;
1149 // output level
1150#if VERBOSE_ATS
1151 opt_mlp.msg_lev = GLP_MSG_ALL;
1152#else
1153 opt_mlp.msg_lev = GLP_MSG_OFF;
1154#endif
1155
1156 result = _lp_intopt (ats->prob, &opt_mlp);
1157 mlp_solution = _lp_mip_status (ats->prob);
1158 stat->solution = mlp_solution;
1159
1160 if (ats_evaluate_results (result, mlp_solution, "MLP") == GNUNET_YES)
1161 {
1162 stat->valid = GNUNET_YES;
1163 }
1164 else
1165 {
1166 // TODO: Remove if this does not appear until release
1167 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1168 "MLP solution for %i peers, %i mechs is invalid: %i\n",
1169 ats->internal.c_peers, ats->internal.c_mechs, mlp_solution);
1170 stat->valid = GNUNET_NO;
1171 }
1172
1173#if VERBOSE_ATS
1174 if (_lp_get_col_prim (ats->prob, 2 * c_mechs + 1) != 1)
1175 {
1176 int c;
1177
1178 for (c = 1; c <= available_quality_metrics; c++)
1179 {
1180 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1181 _lp_get_col_name (ats->prob, 2 * c_mechs + 3 + c),
1182 _lp_get_col_prim (ats->prob, 2 * c_mechs + 3 + c));
1183 }
1184 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1185 _lp_get_col_name (ats->prob, 2 * c_mechs + 1),
1186 _lp_get_col_prim (ats->prob, 2 * c_mechs + 1));
1187 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1188 _lp_get_col_name (ats->prob, 2 * c_mechs + 2),
1189 _lp_get_col_prim (ats->prob, 2 * c_mechs + 2));
1190 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1191 _lp_get_col_name (ats->prob, 2 * c_mechs + 3),
1192 _lp_get_col_prim (ats->prob, 2 * c_mechs + 3));
1193 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "objective value: %f\n",
1194 _lp_mip_obj_val (ats->prob));
1195 }
1196#endif
1197}
1198
1199
1200void
1201ats_shutdown (struct ATS_Handle *ats)
1202{
1203#if DEBUG_ATS
1204 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ATS shutdown\n");
1205#endif
1206 ats_delete_problem (ats);
1207 _lp_free_env ();
1208
1209 GNUNET_free (ats);
1210}
1211
1212void
1213ats_update_problem_qm (struct ATS_Handle *ats)
1214{
1215 int array_index;
1216 int row_index;
1217 int c, c2;
1218 int c_q_metrics = available_quality_metrics;
1219
1220 int *ja =
1221 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1222 available_quality_metrics) * sizeof (int));
1223 double *ar =
1224 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1225 available_quality_metrics) * sizeof (double));
1226#if DEBUG_ATS
1227 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n");
1228#endif
1229 row_index = ats->internal.begin_qm;
1230
1231 for (c = 1; c <= c_q_metrics; c++)
1232 {
1233 array_index = 1;
1234 double value = 1;
1235
1236#if VERBOSE_ATS
1237 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
1238#endif
1239 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
1240 for (c2 = 1; c2 <= ats->internal.c_mechs; c2++)
1241 {
1242 ja[array_index] = c2;
1243 GNUNET_assert (ats->mechanisms[c2].addr != NULL);
1244 GNUNET_assert (ats->mechanisms[c2].peer != NULL);
1245
1246 if (qm[c - 1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DELAY)
1247 {
1248 double v0 = 0, v1 = 0, v2 = 0;
1249
1250 v0 = ats->mechanisms[c2].quality[c - 1].values[0];
1251 if (v1 < 1)
1252 v0 = 0.1;
1253 v1 = ats->mechanisms[c2].quality[c - 1].values[1];
1254 if (v1 < 1)
1255 v0 = 0.1;
1256 v2 = ats->mechanisms[c2].quality[c - 1].values[2];
1257 if (v1 < 1)
1258 v0 = 0.1;
1259 value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0);
1260 //value = 1;
1261 }
1262 if (qm[c - 1].atis_index == GNUNET_TRANSPORT_ATS_QUALITY_NET_DISTANCE)
1263 {
1264 double v0 = 0, v1 = 0, v2 = 0;
1265
1266 v0 = ats->mechanisms[c2].quality[c - 1].values[0];
1267 if (v0 < 1)
1268 v0 = 1;
1269 v1 = ats->mechanisms[c2].quality[c - 1].values[1];
1270 if (v1 < 1)
1271 v1 = 1;
1272 v2 = ats->mechanisms[c2].quality[c - 1].values[2];
1273 if (v2 < 1)
1274 v2 = 1;
1275 value = (v0 + 2 * v1 + 3 * v2) / 6.0;
1276 if (value >= 1)
1277 value = (double) 10 / value;
1278 else
1279 value = 10;
1280 }
1281 ar[array_index] = (ats->mechanisms[c2].peer->f) * value;
1282#if VERBOSE_ATS
1283 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",
1284 array_index, qm[c - 1].name, row_index, ja[array_index],
1285 ar[array_index]);
1286#endif
1287 array_index++;
1288 }
1289 ja[array_index] = ats->internal.col_qm + c - 1;
1290 ar[array_index] = -1;
1291
1292#if VERBOSE_ATS
1293 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
1294 array_index, row_index, ja[array_index], ar[array_index]);
1295#endif
1296 _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar);
1297 array_index = 1;
1298 row_index++;
1299 }
1300 GNUNET_free_non_null (ja);
1301 GNUNET_free_non_null (ar);
1302
1303}
1304
1305
1306void
1307ats_calculate_bandwidth_distribution (struct ATS_Handle *ats)
1308{
1309 struct GNUNET_TIME_Absolute start;
1310 struct GNUNET_TIME_Relative creation;
1311 struct GNUNET_TIME_Relative solving;
1312 int c_m;
1313 int c_p;
1314 char *text = "unmodified";
1315
1316#if FIXME_WACHS
1317 int dur;
1318
1319 if (INT_MAX < ats->max_exec_duration.rel_value)
1320 dur = INT_MAX;
1321 else
1322 dur = (int) ats->max_exec_duration.rel_value;
1323#endif
1324
1325 ats->internal.simplex_rerun_required = GNUNET_NO;
1326 start = GNUNET_TIME_absolute_get ();
1327 if ((ats->internal.recreate_problem == GNUNET_YES) || (ats->prob == NULL) ||
1328 (ats->internal.valid == GNUNET_NO))
1329 {
1330 text = "new";
1331 ats->internal.recreate_problem = GNUNET_YES;
1332 ats_delete_problem (ats);
1333 ats->addr_notification (&ats->peers, &c_p, &ats->mechanisms, &c_m);
1334#if DEBUG_ATS
1335 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1336 "Service returned: %i peer, %i mechs\n", c_p, c_m);
1337#endif
1338 ats_create_problem (ats, &ats->internal, ats->peers, c_p, ats->mechanisms,
1339 c_m);
1340
1341
1342#if DEBUG_ATS
1343 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1344 "Peers/Addresses were modified... new problem: %i peer, %i mechs\n",
1345 ats->internal.c_peers, ats->internal.c_mechs);
1346#endif
1347 }
1348
1349 else if ((ats->internal.recreate_problem == GNUNET_NO) &&
1350 (ats->internal.modified_resources == GNUNET_YES) &&
1351 (ats->internal.valid == GNUNET_YES))
1352 {
1353 text = "modified resources";
1354 ats_update_problem_cr (ats);
1355 }
1356 else if ((ats->internal.recreate_problem == GNUNET_NO) &&
1357 (ats->internal.modified_quality == GNUNET_YES) &&
1358 (ats->internal.valid == GNUNET_YES))
1359 {
1360 text = "modified quality";
1361 ats_update_problem_qm (ats);
1362 //ats_update_problem_qm_TEST ();
1363 }
1364#if DEBUG_ATS
1365 else
1366 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Problem is %s\n", text);
1367#endif
1368
1369 creation =
1370 GNUNET_TIME_absolute_get_difference (start, GNUNET_TIME_absolute_get ());
1371 start = GNUNET_TIME_absolute_get ();
1372
1373 ats->internal.solution = GLP_UNDEF;
1374 if (ats->internal.valid == GNUNET_YES)
1375 {
1376 ats_solve_problem (ats, ats->max_iterations,
1377 ats->max_exec_duration.rel_value, ats->internal.c_peers,
1378 ats->internal.c_mechs, &ats->internal);
1379 }
1380 solving =
1381 GNUNET_TIME_absolute_get_difference (start, GNUNET_TIME_absolute_get ());
1382
1383 if (ats->internal.valid == GNUNET_YES)
1384 {
1385 /* Telling about new distribution */
1386 ats->result_cb ();
1387
1388 int msg_type = GNUNET_ERROR_TYPE_DEBUG;
1389
1390#if DEBUG_ATS
1391 msg_type = GNUNET_ERROR_TYPE_ERROR;
1392#endif
1393 GNUNET_log (msg_type,
1394 "MLP %s: creation time: %llu, execution time: %llu, %i peers, %i mechanisms, simplex rerun: %s, solution %s\n",
1395 text, creation.rel_value, solving.rel_value,
1396 ats->internal.c_peers, ats->internal.c_mechs,
1397 (ats->internal.simplex_rerun_required ==
1398 GNUNET_NO) ? "NO" : "YES",
1399 (ats->internal.solution == 5) ? "OPTIMAL" : "INVALID");
1400 ats->successful_executions++;
1401 GNUNET_STATISTICS_set (ats->stats, "# ATS successful executions",
1402 ats->successful_executions, GNUNET_NO);
1403
1404 if ((ats->internal.recreate_problem == GNUNET_YES) || (ats->prob == NULL))
1405 GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_NEW, GNUNET_NO);
1406 else if ((ats->internal.modified_resources == GNUNET_YES) &&
1407 (ats->internal.modified_quality == GNUNET_NO))
1408 GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_COST_UPDATED,
1409 GNUNET_NO);
1410 else if ((ats->internal.modified_resources == GNUNET_NO) &&
1411 (ats->internal.modified_quality == GNUNET_YES) &&
1412 (ats->internal.simplex_rerun_required == GNUNET_NO))
1413 GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_QUALITY_UPDATED,
1414 GNUNET_NO);
1415 else if ((ats->internal.modified_resources == GNUNET_YES) &&
1416 (ats->internal.modified_quality == GNUNET_YES) &&
1417 (ats->internal.simplex_rerun_required == GNUNET_NO))
1418 GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_QUALITY_COST_UPDATED,
1419 GNUNET_NO);
1420 else if (ats->internal.simplex_rerun_required == GNUNET_NO)
1421 GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_UNMODIFIED,
1422 GNUNET_NO);
1423 }
1424 else
1425 {
1426 if (ats->internal.c_peers != 0)
1427 {
1428 ats->invalid_executions++;
1429 GNUNET_STATISTICS_set (ats->stats, "# ATS invalid executions",
1430 ats->invalid_executions, GNUNET_NO);
1431 }
1432 else
1433 {
1434 GNUNET_STATISTICS_set (ats->stats, "# ATS successful executions",
1435 ats->successful_executions, GNUNET_NO);
1436 }
1437 }
1438
1439 GNUNET_STATISTICS_set (ats->stats, "ATS duration",
1440 solving.rel_value + creation.rel_value, GNUNET_NO);
1441 GNUNET_STATISTICS_set (ats->stats, "ATS mechanisms", ats->internal.c_mechs,
1442 GNUNET_NO);
1443 GNUNET_STATISTICS_set (ats->stats, "ATS peers", ats->internal.c_peers,
1444 GNUNET_NO);
1445 GNUNET_STATISTICS_set (ats->stats, "ATS solution", ats->internal.solution,
1446 GNUNET_NO);
1447 GNUNET_STATISTICS_set (ats->stats, "ATS timestamp", start.abs_value,
1448 GNUNET_NO);
1449
1450 if ((ats->save_mlp == GNUNET_YES) &&
1451 (ats->internal.c_mechs >= ats->dump_min_peers) &&
1452 (ats->internal.c_mechs >= ats->dump_min_addr))
1453 {
1454 char *filename;
1455
1456 if (ats->dump_overwrite == GNUNET_NO)
1457 {
1458 GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.mlp",
1459 ats->internal.c_peers, ats->internal.c_mechs, text,
1460 GNUNET_TIME_absolute_get ().abs_value);
1461 _lp_write_lp ((void *) ats->prob, NULL, filename);
1462 }
1463 else
1464 {
1465 GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.mlp", ats->internal.c_peers,
1466 ats->internal.c_mechs);
1467 _lp_write_lp ((void *) ats->prob, NULL, filename);
1468 }
1469 GNUNET_free (filename);
1470 }
1471 if ((ats->save_solution == GNUNET_YES) &&
1472 (ats->internal.c_mechs >= ats->dump_min_peers) &&
1473 (ats->internal.c_mechs >= ats->dump_min_addr))
1474 {
1475 char *filename;
1476
1477 if (ats->dump_overwrite == GNUNET_NO)
1478 {
1479 GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.sol",
1480 ats->internal.c_peers, ats->internal.c_mechs, text,
1481 GNUNET_TIME_absolute_get ().abs_value);
1482 _lp_print_sol (ats->prob, filename);
1483 }
1484 else
1485 {
1486 GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.sol", ats->internal.c_peers,
1487 ats->internal.c_mechs);
1488 _lp_print_sol (ats->prob, filename);
1489 }
1490 GNUNET_free (filename);
1491 }
1492
1493 ats->internal.recreate_problem = GNUNET_NO;
1494 ats->internal.modified_resources = GNUNET_NO;
1495 ats->internal.modified_quality = GNUNET_NO;
1496}
1497
1498/**
1499 * Evaluate the result of the last simplex or mlp solving
1500 * @param result return value returned by the solver
1501 * @param solution solution state
1502 * @param problem mlp or lp
1503 * @return GNUNET_NO if solution is invalid, GNUNET_YES if solution is
1504 * valid
1505 */
1506
1507int
1508ats_evaluate_results (int result, int solution, char *problem)
1509{
1510 int cont = GNUNET_NO;
1511
1512#if DEBUG_ATS || VERBOSE_ATS
1513 int error_kind = GNUNET_ERROR_TYPE_DEBUG;
1514#endif
1515#if VERBOSE_ATS
1516 error_kind = GNUNET_ERROR_TYPE_ERROR;
1517#endif
1518 switch (result)
1519 {
1520 case GNUNET_SYSERR: /* GNUNET problem, not GLPK related */
1521#if DEBUG_ATS || VERBOSE_ATS
1522 GNUNET_log (error_kind, "%s, GLPK solving not executed\n", problem);
1523#endif
1524 break;
1525 case GLP_ESTOP: /* search terminated by application */
1526#if DEBUG_ATS || VERBOSE_ATS
1527 GNUNET_log (error_kind, "%s , Search terminated by application\n", problem);
1528#endif
1529 break;
1530 case GLP_EITLIM: /* iteration limit exceeded */
1531#if DEBUG_ATS || VERBOSE_ATS
1532 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Iteration limit exceeded\n",
1533 problem);
1534#endif
1535 break;
1536 case GLP_ETMLIM: /* time limit exceeded */
1537#if DEBUG_ATS || VERBOSE_ATS
1538 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Time limit exceeded\n", problem);
1539#endif
1540 break;
1541 case GLP_ENOPFS: /* no primal feasible solution */
1542 case GLP_ENODFS: /* no dual feasible solution */
1543#if DEBUG_ATS || VERBOSE_ATS
1544 GNUNET_log (error_kind, "%s No feasible solution\n", problem);
1545#endif
1546 break;
1547 case GLP_EBADB: /* invalid basis */
1548 case GLP_ESING: /* singular matrix */
1549 case GLP_ECOND: /* ill-conditioned matrix */
1550 case GLP_EBOUND: /* invalid bounds */
1551 case GLP_EFAIL: /* solver failed */
1552 case GLP_EOBJLL: /* objective lower limit reached */
1553 case GLP_EOBJUL: /* objective upper limit reached */
1554 case GLP_EROOT: /* root LP optimum not provided */
1555#if DEBUG_ATS || VERBOSE_ATS
1556 GNUNET_log (error_kind, "%s Invalid Input data: %i\n", problem, result);
1557#endif
1558 break;
1559 case 0:
1560#if DEBUG_ATS || VERBOSE_ATS
1561 GNUNET_log (error_kind, "%s Problem has been solved\n", problem);
1562#endif
1563 break;
1564 }
1565
1566 switch (solution)
1567 {
1568 case GLP_UNDEF:
1569#if DEBUG_ATS || VERBOSE_ATS
1570 GNUNET_log (error_kind, "%s solution is undefined\n", problem);
1571#endif
1572 break;
1573 case GLP_OPT:
1574#if DEBUG_ATS || VERBOSE_ATS
1575 GNUNET_log (error_kind, "%s solution is optimal\n", problem);
1576#endif
1577 cont = GNUNET_YES;
1578 break;
1579 case GLP_FEAS:
1580#if DEBUG_ATS || VERBOSE_ATS
1581 GNUNET_log (error_kind,
1582 "%s solution is %s feasible, however, its optimality (or non-optimality) has not been proven\n",
1583 problem, (0 == strcmp (problem, "LP") ? "" : "integer"));
1584#endif
1585 cont = GNUNET_YES;
1586 break;
1587 case GLP_NOFEAS:
1588#if DEBUG_ATS || VERBOSE_ATS
1589 GNUNET_log (error_kind, "%s problem has no %sfeasible solution\n", problem,
1590 (0 == strcmp (problem, "LP") ? "" : "integer "));
1591#endif
1592 break;
1593 case GLP_INFEAS:
1594#if DEBUG_ATS || VERBOSE_ATS
1595 GNUNET_log (error_kind, "%s problem is infeasible \n", problem);
1596#endif
1597 break;
1598 case GLP_UNBND:
1599#if DEBUG_ATS || VERBOSE_ATS
1600 GNUNET_log (error_kind, "%s problem is unbounded \n", problem);
1601#endif
1602 default:
1603 break;
1604 }
1605 return cont;
1606}
1607
1608void
1609ats_update_problem_cr (struct ATS_Handle *ats)
1610{
1611 int array_index;
1612 int row_index;
1613 int c, c2;
1614 double ct_max, ct_min;
1615
1616 int *ja =
1617 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1618 available_quality_metrics) * sizeof (int));
1619 double *ar =
1620 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1621 available_quality_metrics) * sizeof (double));
1622
1623 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n");
1624 row_index = ats->internal.begin_cr;
1625 array_index = 1;
1626
1627 for (c = 0; c < available_ressources; c++)
1628 {
1629 ct_max = ressources[c].c_max;
1630 ct_min = ressources[c].c_min;
1631#if VERBOSE_ATS
1632 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] %f..%f\n",
1633 row_index, ct_min, ct_max);
1634#endif
1635 _lp_set_row_bnds (ats->prob, row_index, GLP_DB, ct_min, ct_max);
1636 for (c2 = 1; c2 <= ats->internal.c_mechs; c2++)
1637 {
1638 double value = 0;
1639
1640 GNUNET_assert (ats->mechanisms[c2].addr != NULL);
1641 GNUNET_assert (ats->mechanisms[c2].peer != NULL);
1642
1643 ja[array_index] = c2;
1644 value = ats->mechanisms[c2].ressources[c].c;
1645 ar[array_index] = value;
1646#if VERBOSE_ATS
1647 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
1648 array_index, row_index, ja[array_index], ar[array_index]);
1649#endif
1650 array_index++;
1651 }
1652 _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar);
1653 row_index++;
1654 }
1655 GNUNET_free_non_null (ja);
1656 GNUNET_free_non_null (ar);
1657
1658}
1659
1660void
1661ats_set_logging_options (struct ATS_Handle *ats,
1662 struct GNUNET_STATISTICS_Handle *stats,
1663 const struct GNUNET_CONFIGURATION_Handle *cfg)
1664{
1665 int minimum_addresses;
1666 int minimum_peers;
1667 int overwrite_dump;
1668 int log_solution;
1669 int log_problem;
1670 unsigned long long value;
1671
1672 if (ats == NULL)
1673 return;
1674 log_problem =
1675 GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_MLP");
1676 log_solution =
1677 GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_SOLUTION");
1678 overwrite_dump =
1679 GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_OVERWRITE");
1680 if (GNUNET_OK ==
1681 GNUNET_CONFIGURATION_get_value_number (cfg, "transport", "DUMP_MIN_PEERS",
1682 &value))
1683 minimum_peers = (int) value;
1684 if (GNUNET_OK ==
1685 GNUNET_CONFIGURATION_get_value_number (cfg, "transport", "DUMP_MIN_ADDRS",
1686 &value))
1687 minimum_addresses = (int) value;
1688
1689
1690 ats->stats = stats;
1691 ats->dump_min_addr = minimum_addresses;
1692 ats->dump_min_peers = minimum_peers;
1693 ats->dump_overwrite = overwrite_dump;
1694 ats->save_mlp = log_problem;
1695 ats->save_solution = log_solution;
1696}
1697
1698#if 0
1699static void
1700ats_update_problem_qm_TEST ()
1701{
1702 int row_index;
1703 int c int c2;
1704 int c_old;
1705 int changed = 0;
1706
1707 int old_ja[ats->internal.c_mechs + 2];
1708 double old_ar[ats->internal.c_mechs + 2];
1709
1710 int *ja =
1711 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1712 available_quality_metrics) * sizeof (int));
1713 double *ar =
1714 GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1715 available_quality_metrics) * sizeof (double));
1716#if DEBUG_ATS
1717 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1718 "Updating problem quality metrics TEST\n");
1719#endif
1720 if (ats->internal.begin_qm > 0)
1721 row_index = ats->internal.begin_qm;
1722 else
1723 return;
1724 for (c = 0; c < available_quality_metrics; c++)
1725 {
1726 c_old = _lp_get_mat_row (ats->prob, row_index, old_ja, old_ar);
1727 _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
1728 for (c2 = 1; c2 <= c_old; c2++)
1729 {
1730 ja[c2] = old_ja[c2];
1731 if ((changed < 3) && (c2 > 2) && (old_ar[c2] != -1))
1732 {
1733 ar[c2] = old_ar[c2] + 5 - changed;
1734 changed++;
1735 }
1736 else
1737 ar[c2] = old_ar[c2];
1738#if VERBOSE_ATS
1739 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1740 "[index]=[%i]: old [%i,%i]=%f new [%i,%i]=%f\n", c2,
1741 row_index, old_ja[c2], old_ar[c2], row_index, ja[c2], ar[c2]);
1742#endif
1743 }
1744 _lp_set_mat_row (ats->prob, row_index, c_old, ja, ar);
1745 row_index++;
1746 }
1747 GNUNET_free_non_null (ja);
1748 GNUNET_free_non_null (ar);
1749}
1750#endif
1751
1752
1753
1754/* end of transport_ats.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-19 13:43:49 +0000