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