src/transport/gnunet-service-transport_ats.c

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