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