src/ats/gnunet-service-ats_math.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/gnunet-service-transport_ats.c
  23  * @brief automatic transport selection
  24  * @author Matthias Wachs
  25  *
  26  */
  27
  28
  29 #include "gnunet-service-transport_ats.h"
  30 #include "gnunet_transport_service.h"
  31 #include "gnunet_statistics_service.h"
  32 #include "gnunet_container_lib.h"
  33
  34
  35
  36
  37
  38 /* LP/MIP problem object */
  39
  40 #if !HAVE_LIBGLPK
  41
  42 #ifndef GLP_PROB_DEFINED
  43 #define GLP_PROB_DEFINED
  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
 477 _dummy2 ();
 478 static void
 479 _dummy ()
 480 {
 481   return;
 482   _lp_get_col_name (NULL, 0);
 483   _lp_mip_obj_val (NULL);
 484   _lp_get_col_prim (NULL, 0);
 485   _lp_set_mat_row (NULL, 0, 0, NULL, NULL);
 486   _dummy2 ();
 487 }
 488
 489
 490
 491 static void
 492 _dummy2 ()
 493 {
 494   ats_modify_problem_state (NULL, 0);
 495   qm[1].atis_index = 0;
 496   _dummy ();
 497   int t = ATS_COST_UPDATED + ATS_MODIFIED + ATS_NEW;
 498
 499   t++;
 500 }
 501
 502 /*
 503  * ATS Functions
 504  */
 505
 506
 507 /**
 508  * Initialize ATS
 509  * @param cfg configuration handle to retrieve configuration (to be removed)
 510  * @return
 511  */
 512
 513 struct ATS_Handle *
 514 ats_init (double D, double U, double R, int v_b_min, int v_n_min,
 515           int max_iterations, struct GNUNET_TIME_Relative max_duration,
 516           GNUNET_ATS_AddressNotification address_not,
 517           GNUNET_ATS_ResultCallback res_cb)
 518 {
 519   struct ATS_Handle *ats = NULL;
 520
 521   ats = GNUNET_malloc (sizeof (struct ATS_Handle));
 522
 523   ats->prob = NULL;
 524
 525   ats->addr_notification = address_not;
 526   ats->result_cb = res_cb;
 527
 528   ats->max_iterations = max_iterations;
 529   ats->max_exec_duration = max_duration;
 530
 531   ats->D = D;
 532   ats->U = U;
 533   ats->R = R;
 534   ats->v_b_min = v_b_min;
 535   ats->v_n_min = v_n_min;
 536   ats->dump_min_peers = 0;
 537   ats->dump_min_addr = 0;
 538   ats->dump_overwrite = GNUNET_NO;
 539   ats->mechanisms = NULL;
 540   ats->peers = NULL;
 541   ats->successful_executions = 0;
 542   ats->invalid_executions = 0;
 543
 544   return ats;
 545 }
 546
 547
 548 /** solve the bandwidth distribution problem
 549  * @param max_it maximum iterations
 550  * @param max_dur maximum duration in ms
 551  * @param D     weight for diversity
 552  * @param U weight for utility
 553  * @param R weight for relativity
 554  * @param v_b_min minimal bandwidth per peer
 555  * @param v_n_min minimum number of connections
 556  * @param stat result struct
 557  * @return GNUNET_SYSERR if glpk is not available, number of mechanisms used
 558  */
 559 int
 560 ats_create_problem (struct ATS_Handle *ats, struct ATS_internals *stat,
 561                     struct ATS_peer *peers, int c_p,
 562                     struct ATS_mechanism *mechanisms, int c_m)
 563 {
 564   if ((c_p == 0) || (c_m == 0))
 565     return GNUNET_SYSERR;
 566
 567   ats->prob = _lp_create_prob ();
 568
 569   int c;
 570   int c_c_ressources = available_ressources;
 571   int c_q_metrics = available_quality_metrics;
 572
 573   double M = VERY_BIG_DOUBLE_VALUE;
 574   double Q[c_q_metrics + 1];
 575
 576   for (c = 1; c <= c_q_metrics; c++)
 577   {
 578     Q[c] = 1;
 579   }
 580
 581   if (ats->v_n_min > c_p)
 582     ats->v_n_min = c_p;
 583 #if VERBOSE_ATS
 584   GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 585               "Creating problem with: %i peers, %i mechanisms, %i resource entries, %i quality metrics \n",
 586               c_p, c_m, c_c_ressources, c_q_metrics);
 587 #endif
 588
 589   int size =
 590       1 + 3 + 10 * c_m + c_p + (c_q_metrics * c_m) + c_q_metrics +
 591       c_c_ressources * c_m;
 592   int row_index;
 593   int array_index = 1;
 594   int *ia = GNUNET_malloc (size * sizeof (int));
 595   int *ja = GNUNET_malloc (size * sizeof (int));
 596   double *ar = GNUNET_malloc (size * sizeof (double));
 597
 598   _lp_set_prob_name (ats->prob, "gnunet ats bandwidth distribution");
 599   _lp_set_obj_dir (ats->prob, GLP_MAX);
 600
 601   /* adding columns */
 602   char *name;
 603
 604   _lp_add_cols (ats->prob, 2 * c_m);
 605   /* adding b_t cols */
 606   for (c = 1; c <= c_m; c++)
 607   {
 608     GNUNET_asprintf (&name, "p_%s_b%i",
 609                      GNUNET_i2s (&(mechanisms[c].peer->peer)), c);
 610     _lp_set_col_name (ats->prob, c, name);
 611     GNUNET_free (name);
 612     _lp_set_col_bnds (ats->prob, c, GLP_LO, 0.0, 0.0);
 613     _lp_set_col_kind (ats->prob, c, GLP_CV);
 614     _lp_set_obj_coef (ats->prob, c, 0);
 615   }
 616
 617   /* adding n_t cols */
 618   for (c = c_m + 1; c <= 2 * c_m; c++)
 619   {
 620     GNUNET_asprintf (&name, "p_%s_n%i",
 621                      GNUNET_i2s (&(mechanisms[c - c_m].peer->peer)), (c - c_m));
 622     _lp_set_col_name (ats->prob, c, name);
 623     GNUNET_free (name);
 624     _lp_set_col_bnds (ats->prob, c, GLP_DB, 0.0, 1.0);
 625     _lp_set_col_kind (ats->prob, c, GLP_IV);
 626     _lp_set_obj_coef (ats->prob, c, 0);
 627   }
 628
 629   /* feasibility constraints */
 630   /* Constraint 1: one address per peer */
 631   row_index = 1;
 632
 633   _lp_add_rows (ats->prob, c_p);
 634
 635   for (c = 1; c <= c_p; c++)
 636   {
 637 #if VERBOSE_ATS
 638     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 639 #endif
 640
 641     _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 1.0, 1.0);
 642     struct ATS_mechanism *m = peers[c].m_head;
 643
 644     while (m != NULL)
 645     {
 646       ia[array_index] = row_index;
 647       ja[array_index] = (c_m + m->col_index);
 648       ar[array_index] = 1;
 649 #if VERBOSE_ATS
 650       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 651                   array_index, ia[array_index], ja[array_index],
 652                   ar[array_index]);
 653 #endif
 654       array_index++;
 655       m = m->next;
 656     }
 657     row_index++;
 658   }
 659
 660   /* Constraint 2: only active mechanism gets bandwidth assigned */
 661   _lp_add_rows (ats->prob, c_m);
 662   for (c = 1; c <= c_m; c++)
 663   {
 664     /* b_t - n_t * M <= 0 */
 665 #if VERBOSE_ATS
 666     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 667 #endif
 668     _lp_set_row_bnds (ats->prob, row_index, GLP_UP, 0.0, 0.0);
 669     ia[array_index] = row_index;
 670     ja[array_index] = mechanisms[c].col_index;
 671     ar[array_index] = 1;
 672 #if VERBOSE_ATS
 673     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 674                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 675 #endif
 676     array_index++;
 677     ia[array_index] = row_index;
 678     ja[array_index] = c_m + mechanisms[c].col_index;
 679     ar[array_index] = -M;
 680 #if VERBOSE_ATS
 681     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 682                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 683 #endif
 684     array_index++;
 685     row_index++;
 686   }
 687
 688   /* Constraint 3: minimum bandwidth */
 689   _lp_add_rows (ats->prob, c_m);
 690
 691   for (c = 1; c <= c_m; c++)
 692   {
 693     /* b_t - n_t * b_min <= 0 */
 694 #if VERBOSE_ATS
 695     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 696 #endif
 697 #if HAVE_LIBGLPK
 698     _lp_set_row_bnds (ats->prob, row_index, GLP_LO, 0.0, 0.0);
 699 #endif
 700     ia[array_index] = row_index;
 701     ja[array_index] = mechanisms[c].col_index;
 702     ar[array_index] = 1;
 703 #if VERBOSE_ATS
 704     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 705                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 706 #endif
 707     array_index++;
 708     ia[array_index] = row_index;
 709     ja[array_index] = c_m + mechanisms[c].col_index;
 710     ar[array_index] = -ats->v_b_min;
 711 #if VERBOSE_ATS
 712     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 713                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 714 #endif
 715     array_index++;
 716     row_index++;
 717   }
 718   int c2;
 719
 720   /* Constraint 4: max ressource capacity */
 721   /* V cr: bt * ct_r <= cr_max
 722    * */
 723
 724   _lp_add_rows (ats->prob, available_ressources);
 725
 726   double ct_max = VERY_BIG_DOUBLE_VALUE;
 727   double ct_min = 0.0;
 728
 729   stat->begin_cr = array_index;
 730
 731   for (c = 0; c < available_ressources; c++)
 732   {
 733     ct_max = ressources[c].c_max;
 734     ct_min = ressources[c].c_min;
 735 #if VERBOSE_ATS
 736     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] %f..%f\n",
 737                 row_index, ct_min, ct_max);
 738 #endif
 739 #if HAVE_LIBGLPK
 740     _lp_set_row_bnds (ats->prob, row_index, GLP_DB, ct_min, ct_max);
 741 #endif
 742     for (c2 = 1; c2 <= c_m; c2++)
 743     {
 744       double value = 0;
 745
 746       ia[array_index] = row_index;
 747       ja[array_index] = c2;
 748       value = mechanisms[c2].ressources[c].c;
 749       ar[array_index] = value;
 750 #if VERBOSE_ATS
 751       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 752                   array_index, ia[array_index], ja[array_index],
 753                   ar[array_index]);
 754 #endif
 755       array_index++;
 756     }
 757     row_index++;
 758   }
 759   stat->end_cr = array_index--;
 760
 761   /* Constraint 5: min number of connections */
 762   _lp_add_rows (ats->prob, 1);
 763
 764   for (c = 1; c <= c_m; c++)
 765   {
 766     // b_t - n_t * b_min >= 0
 767 #if VERBOSE_ATS
 768     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 769 #endif
 770     _lp_set_row_bnds (ats->prob, row_index, GLP_LO, ats->v_n_min, 0.0);
 771     ia[array_index] = row_index;
 772     ja[array_index] = c_m + mechanisms[c].col_index;
 773     ar[array_index] = 1;
 774 #if VERBOSE_ATS
 775     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 776                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 777 #endif
 778     array_index++;
 779   }
 780   row_index++;
 781
 782   // optimisation constraints
 783
 784   // adding columns
 785
 786   // Constraint 6: optimize for diversity
 787   int col_d;
 788
 789   col_d = _lp_add_cols (ats->prob, 1);
 790
 791   _lp_set_col_name (ats->prob, col_d, "d");
 792   _lp_set_obj_coef (ats->prob, col_d, ats->D);
 793   _lp_set_col_bnds (ats->prob, col_d, GLP_LO, 0.0, 0.0);
 794   _lp_add_rows (ats->prob, 1);
 795   _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
 796
 797   stat->col_d = col_d;
 798 #if VERBOSE_ATS
 799   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 800 #endif
 801   for (c = 1; c <= c_m; c++)
 802   {
 803     ia[array_index] = row_index;
 804     ja[array_index] = c_m + mechanisms[c].col_index;
 805     ar[array_index] = 1;
 806 #if VERBOSE_ATS
 807     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 808                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 809 #endif
 810     array_index++;
 811   }
 812   ia[array_index] = row_index;
 813   ja[array_index] = col_d;
 814   ar[array_index] = -1;
 815 #if VERBOSE_ATS
 816   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 817               array_index, ia[array_index], ja[array_index], ar[array_index]);
 818 #endif
 819   array_index++;
 820   row_index++;
 821
 822   // Constraint 7: optimize for quality
 823   int col_qm;
 824
 825   col_qm = _lp_add_cols (ats->prob, c_q_metrics);
 826
 827   stat->col_qm = col_qm;
 828   //GNUNET_assert (col_qm == (2*c_mechs) + 3 + 1);
 829   for (c = 0; c < c_q_metrics; c++)
 830   {
 831     GNUNET_asprintf (&name, "Q_%s", qm[c].name);
 832     _lp_set_col_name (ats->prob, col_qm + c, name);
 833     _lp_set_col_bnds (ats->prob, col_qm + c, GLP_LO, 0.0, 0.0);
 834     GNUNET_free (name);
 835     _lp_set_obj_coef (ats->prob, col_qm + c, Q[c]);
 836   }
 837
 838   _lp_add_rows (ats->prob, available_quality_metrics);
 839
 840   stat->begin_qm = row_index;
 841   for (c = 1; c <= c_q_metrics; c++)
 842   {
 843 #if VERBOSE_ATS
 844     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 845 #endif
 846     double value = 1;
 847
 848     _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
 849     for (c2 = 1; c2 <= c_m; c2++)
 850     {
 851       ia[array_index] = row_index;
 852       ja[array_index] = c2;
 853       if (qm[c - 1].atis_index == GNUNET_ATS_QUALITY_NET_DELAY)
 854       {
 855         double v0 = 0, v1 = 0, v2 = 0;
 856
 857         v0 = mechanisms[c2].quality[c - 1].values[0];
 858         if (v1 < 1)
 859           v0 = 0.1;
 860         v1 = mechanisms[c2].quality[c - 1].values[1];
 861         if (v1 < 1)
 862           v0 = 0.1;
 863         v2 = mechanisms[c2].quality[c - 1].values[2];
 864         if (v1 < 1)
 865           v0 = 0.1;
 866         value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0);
 867         value = 1;
 868       }
 869       if (qm[c - 1].atis_index == GNUNET_ATS_QUALITY_NET_DISTANCE)
 870       {
 871         double v0 = 0, v1 = 0, v2 = 0;
 872
 873         v0 = mechanisms[c2].quality[c - 1].values[0];
 874         if (v0 < 1)
 875           v0 = 1;
 876         v1 = mechanisms[c2].quality[c - 1].values[1];
 877         if (v1 < 1)
 878           v1 = 1;
 879         v2 = mechanisms[c2].quality[c - 1].values[2];
 880         if (v2 < 1)
 881           v2 = 1;
 882         value = (v0 + 2 * v1 + 3 * v2) / 6.0;
 883         if (value >= 1)
 884           value = (double) 10 / value;
 885         else
 886           value = 10;
 887       }
 888       ar[array_index] = (mechanisms[c2].peer->f) * value;
 889 #if VERBOSE_ATS
 890       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",
 891                   array_index, qm[c - 1].name, ia[array_index], ja[array_index],
 892                   ar[array_index]);
 893 #endif
 894       array_index++;
 895     }
 896     ia[array_index] = row_index;
 897     ja[array_index] = col_qm + c - 1;
 898     ar[array_index] = -1;
 899 #if VERBOSE_ATS
 900     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 901                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 902 #endif
 903     array_index++;
 904     row_index++;
 905   }
 906   stat->end_qm = row_index - 1;
 907
 908   // Constraint 8: optimize bandwidth utility
 909   int col_u;
 910
 911   col_u = _lp_add_cols (ats->prob, 1);
 912
 913   _lp_set_col_name (ats->prob, col_u, "u");
 914   _lp_set_obj_coef (ats->prob, col_u, ats->U);
 915   _lp_set_col_bnds (ats->prob, col_u, GLP_LO, 0.0, 0.0);
 916   _lp_add_rows (ats->prob, 1);
 917   stat->col_u = col_u;
 918 #if VERBOSE_ATS
 919   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
 920 #endif
 921   _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
 922   for (c = 1; c <= c_m; c++)
 923   {
 924     ia[array_index] = row_index;
 925     ja[array_index] = c;
 926     ar[array_index] = mechanisms[c].peer->f;
 927 #if VERBOSE_ATS
 928     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 929                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 930 #endif
 931     array_index++;
 932   }
 933   ia[array_index] = row_index;
 934   ja[array_index] = col_u;
 935   ar[array_index] = -1;
 936 #if VERBOSE_ATS
 937   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 938               array_index, ia[array_index], ja[array_index], ar[array_index]);
 939 #endif
 940
 941   array_index++;
 942   row_index++;
 943
 944   // Constraint 9: optimize relativity
 945   int col_r;
 946
 947   col_r = _lp_add_cols (ats->prob, 1);
 948
 949   _lp_set_col_name (ats->prob, col_r, "r");
 950   _lp_set_obj_coef (ats->prob, col_r, ats->R);
 951   _lp_set_col_bnds (ats->prob, col_r, GLP_LO, 0.0, 0.0);
 952   _lp_add_rows (ats->prob, c_p);
 953
 954   stat->col_r = col_r;
 955   for (c = 1; c <= c_p; c++)
 956   {
 957     _lp_set_row_bnds (ats->prob, row_index, GLP_LO, 0.0, 0.0);
 958     struct ATS_mechanism *m = peers[c].m_head;
 959
 960     while (m != NULL)
 961     {
 962       ia[array_index] = row_index;
 963       ja[array_index] = m->col_index;
 964       ar[array_index] = 1 / mechanisms[c].peer->f;
 965 #if VERBOSE_ATS
 966       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 967                   array_index, ia[array_index], ja[array_index],
 968                   ar[array_index]);
 969 #endif
 970       array_index++;
 971       m = m->next;
 972     }
 973     ia[array_index] = row_index;
 974     ja[array_index] = col_r;
 975     ar[array_index] = -1;
 976 #if VERBOSE_ATS
 977     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
 978                 array_index, ia[array_index], ja[array_index], ar[array_index]);
 979 #endif
 980     array_index++;
 981     row_index++;
 982   }
 983
 984   /* Loading the matrix */
 985   _lp_load_matrix (ats->prob, array_index - 1, ia, ja, ar);
 986
 987   stat->c_mechs = c_m;
 988   stat->c_peers = c_p;
 989   stat->solution = 0;
 990   stat->valid = GNUNET_YES;
 991
 992   /* clean up */
 993   GNUNET_free (ja);
 994   GNUNET_free (ia);
 995   GNUNET_free (ar);
 996
 997   return GNUNET_OK;
 998 }
 999
1000
1001 void
1002 ats_delete_problem (struct ATS_Handle *ats)
1003 {
1004 #if DEBUG_ATS
1005   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting problem\n");
1006 #endif
1007   int c;
1008
1009   for (c = 0; c < (ats->internal).c_mechs; c++)
1010     GNUNET_free_non_null (ats->mechanisms[c].rc);
1011   if (ats->mechanisms != NULL)
1012   {
1013     GNUNET_free (ats->mechanisms);
1014     ats->mechanisms = NULL;
1015   }
1016
1017   if (ats->peers != NULL)
1018   {
1019     GNUNET_free (ats->peers);
1020     ats->peers = NULL;
1021   }
1022
1023   if (ats->prob != NULL)
1024   {
1025     _lp_delete_prob (ats->prob);
1026     ats->prob = NULL;
1027   }
1028
1029   ats->internal.begin_cr = GNUNET_SYSERR;
1030   ats->internal.begin_qm = GNUNET_SYSERR;
1031   ats->internal.c_mechs = 0;
1032   ats->internal.c_peers = 0;
1033   ats->internal.end_cr = GNUNET_SYSERR;
1034   ats->internal.end_qm = GNUNET_SYSERR;
1035   ats->internal.solution = GNUNET_SYSERR;
1036   ats->internal.valid = GNUNET_SYSERR;
1037 }
1038
1039 void
1040 ats_modify_problem_state (struct ATS_Handle *ats, enum ATS_problem_state s)
1041 {
1042   if (ats == NULL)
1043     return;
1044   switch (s)
1045   {
1046   case ATS_NEW:
1047     ats->internal.recreate_problem = GNUNET_NO;
1048     ats->internal.modified_quality = GNUNET_NO;
1049     ats->internal.modified_resources = GNUNET_NO;
1050     break;
1051   case ATS_MODIFIED:
1052     ats->internal.recreate_problem = GNUNET_YES;
1053     break;
1054   case ATS_QUALITY_UPDATED:
1055     ats->internal.modified_quality = GNUNET_YES;
1056     break;
1057   case ATS_COST_UPDATED:
1058     ats->internal.modified_resources = GNUNET_YES;
1059     break;
1060   case ATS_QUALITY_COST_UPDATED:
1061     ats->internal.modified_resources = GNUNET_YES;
1062     ats->internal.modified_quality = GNUNET_YES;
1063     break;
1064   default:
1065     return;
1066   }
1067
1068
1069
1070 }
1071
1072 void
1073 ats_solve_problem (struct ATS_Handle *ats, unsigned int max_it,
1074                    unsigned int max_dur, unsigned int c_peers,
1075                    unsigned int c_mechs, struct ATS_internals *stat)
1076 {
1077   int result = GNUNET_SYSERR;
1078   int lp_solution = GNUNET_SYSERR;
1079   int mlp_solution = GNUNET_SYSERR;
1080
1081   // Solving simplex
1082
1083   glp_smcp opt_lp;
1084
1085   _lp_init_smcp (&opt_lp);
1086 #if VERBOSE_ATS
1087   opt_lp.msg_lev = GLP_MSG_ALL;
1088 #else
1089   opt_lp.msg_lev = GLP_MSG_OFF;
1090 #endif
1091   // setting iteration limit
1092   opt_lp.it_lim = max_it;
1093   // maximum duration
1094   opt_lp.tm_lim = max_dur;
1095
1096   if (ats->internal.recreate_problem == GNUNET_YES)
1097     opt_lp.presolve = GLP_ON;
1098
1099   result = _lp_simplex (ats->prob, &opt_lp);
1100   lp_solution = _lp_get_status (ats->prob);
1101
1102   if ((result == GLP_ETMLIM) || (result == GLP_EITLIM))
1103   {
1104     ats->internal.valid = GNUNET_NO;
1105     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1106                 "ATS exceeded time or iteration limit!\n");
1107     return;
1108   }
1109
1110   if (ats_evaluate_results (result, lp_solution, "LP") == GNUNET_YES)
1111   {
1112     stat->valid = GNUNET_YES;
1113   }
1114   else
1115   {
1116     ats->internal.simplex_rerun_required = GNUNET_YES;
1117     opt_lp.presolve = GLP_ON;
1118     result = _lp_simplex (ats->prob, &opt_lp);
1119     lp_solution = _lp_get_status (ats->prob);
1120
1121     // TODO: Remove if this does not appear until release
1122     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1123                 "" "EXECUTED SIMPLEX WITH PRESOLVER! %i \n", lp_solution);
1124
1125     if (ats_evaluate_results (result, lp_solution, "LP") != GNUNET_YES)
1126     {
1127       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1128                   "After execution simplex with presolver: STILL INVALID!\n");
1129       char *filename;
1130
1131       GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%llu.mlp",
1132                        ats->internal.c_peers, ats->internal.c_mechs,
1133                        GNUNET_TIME_absolute_get ().abs_value);
1134       _lp_write_lp ((void *) ats->prob, NULL, filename);
1135       GNUNET_free (filename);
1136       stat->valid = GNUNET_NO;
1137       ats->internal.recreate_problem = GNUNET_YES;
1138       return;
1139     }
1140     stat->valid = GNUNET_YES;
1141   }
1142
1143   // Solving mlp
1144   glp_iocp opt_mlp;
1145
1146   _lp_init_iocp (&opt_mlp);
1147   // maximum duration
1148   opt_mlp.tm_lim = max_dur;
1149   // output level
1150 #if VERBOSE_ATS
1151   opt_mlp.msg_lev = GLP_MSG_ALL;
1152 #else
1153   opt_mlp.msg_lev = GLP_MSG_OFF;
1154 #endif
1155
1156   result = _lp_intopt (ats->prob, &opt_mlp);
1157   mlp_solution = _lp_mip_status (ats->prob);
1158   stat->solution = mlp_solution;
1159
1160   if (ats_evaluate_results (result, mlp_solution, "MLP") == GNUNET_YES)
1161   {
1162     stat->valid = GNUNET_YES;
1163   }
1164   else
1165   {
1166     // TODO: Remove if this does not appear until release
1167     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1168                 "MLP solution for %i peers, %i mechs is invalid: %i\n",
1169                 ats->internal.c_peers, ats->internal.c_mechs, mlp_solution);
1170     stat->valid = GNUNET_NO;
1171   }
1172
1173 #if VERBOSE_ATS
1174   if (_lp_get_col_prim (ats->prob, 2 * c_mechs + 1) != 1)
1175   {
1176     int c;
1177
1178     for (c = 1; c <= available_quality_metrics; c++)
1179     {
1180       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1181                   _lp_get_col_name (ats->prob, 2 * c_mechs + 3 + c),
1182                   _lp_get_col_prim (ats->prob, 2 * c_mechs + 3 + c));
1183     }
1184     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1185                 _lp_get_col_name (ats->prob, 2 * c_mechs + 1),
1186                 _lp_get_col_prim (ats->prob, 2 * c_mechs + 1));
1187     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1188                 _lp_get_col_name (ats->prob, 2 * c_mechs + 2),
1189                 _lp_get_col_prim (ats->prob, 2 * c_mechs + 2));
1190     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s %f\n",
1191                 _lp_get_col_name (ats->prob, 2 * c_mechs + 3),
1192                 _lp_get_col_prim (ats->prob, 2 * c_mechs + 3));
1193     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "objective value:  %f\n",
1194                 _lp_mip_obj_val (ats->prob));
1195   }
1196 #endif
1197 }
1198
1199
1200 void
1201 ats_shutdown (struct ATS_Handle *ats)
1202 {
1203 #if DEBUG_ATS
1204   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "ATS shutdown\n");
1205 #endif
1206   ats_delete_problem (ats);
1207   _lp_free_env ();
1208
1209   GNUNET_free (ats);
1210 }
1211
1212 void
1213 ats_update_problem_qm (struct ATS_Handle *ats)
1214 {
1215   int array_index;
1216   int row_index;
1217   int c, c2;
1218   int c_q_metrics = available_quality_metrics;
1219
1220   int *ja =
1221       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1222                       available_quality_metrics) * sizeof (int));
1223   double *ar =
1224       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1225                       available_quality_metrics) * sizeof (double));
1226 #if DEBUG_ATS
1227   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n");
1228 #endif
1229   row_index = ats->internal.begin_qm;
1230
1231   for (c = 1; c <= c_q_metrics; c++)
1232   {
1233     array_index = 1;
1234     double value = 1;
1235
1236 #if VERBOSE_ATS
1237     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] \n", row_index);
1238 #endif
1239     _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
1240     for (c2 = 1; c2 <= ats->internal.c_mechs; c2++)
1241     {
1242       ja[array_index] = c2;
1243       GNUNET_assert (ats->mechanisms[c2].addr != NULL);
1244       GNUNET_assert (ats->mechanisms[c2].peer != NULL);
1245
1246       if (qm[c - 1].atis_index == GNUNET_ATS_QUALITY_NET_DELAY)
1247       {
1248         double v0 = 0, v1 = 0, v2 = 0;
1249
1250         v0 = ats->mechanisms[c2].quality[c - 1].values[0];
1251         if (v1 < 1)
1252           v0 = 0.1;
1253         v1 = ats->mechanisms[c2].quality[c - 1].values[1];
1254         if (v1 < 1)
1255           v0 = 0.1;
1256         v2 = ats->mechanisms[c2].quality[c - 1].values[2];
1257         if (v1 < 1)
1258           v0 = 0.1;
1259         value = 100.0 / ((v0 + 2 * v1 + 3 * v2) / 6.0);
1260         //value = 1;
1261       }
1262       if (qm[c - 1].atis_index == GNUNET_ATS_QUALITY_NET_DISTANCE)
1263       {
1264         double v0 = 0, v1 = 0, v2 = 0;
1265
1266         v0 = ats->mechanisms[c2].quality[c - 1].values[0];
1267         if (v0 < 1)
1268           v0 = 1;
1269         v1 = ats->mechanisms[c2].quality[c - 1].values[1];
1270         if (v1 < 1)
1271           v1 = 1;
1272         v2 = ats->mechanisms[c2].quality[c - 1].values[2];
1273         if (v2 < 1)
1274           v2 = 1;
1275         value = (v0 + 2 * v1 + 3 * v2) / 6.0;
1276         if (value >= 1)
1277           value = (double) 10 / value;
1278         else
1279           value = 10;
1280       }
1281       ar[array_index] = (ats->mechanisms[c2].peer->f) * value;
1282 #if VERBOSE_ATS
1283       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: %s [%i,%i]=%f \n",
1284                   array_index, qm[c - 1].name, row_index, ja[array_index],
1285                   ar[array_index]);
1286 #endif
1287       array_index++;
1288     }
1289     ja[array_index] = ats->internal.col_qm + c - 1;
1290     ar[array_index] = -1;
1291
1292 #if VERBOSE_ATS
1293     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
1294                 array_index, row_index, ja[array_index], ar[array_index]);
1295 #endif
1296     _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar);
1297     array_index = 1;
1298     row_index++;
1299   }
1300   GNUNET_free_non_null (ja);
1301   GNUNET_free_non_null (ar);
1302
1303 }
1304
1305
1306 void
1307 ats_calculate_bandwidth_distribution (struct ATS_Handle *ats)
1308 {
1309   struct GNUNET_TIME_Absolute start;
1310   struct GNUNET_TIME_Relative creation;
1311   struct GNUNET_TIME_Relative solving;
1312   int c_m;
1313   int c_p;
1314   char *text = "unmodified";
1315
1316 #if FIXME_WACHS
1317   int dur;
1318
1319   if (INT_MAX < ats->max_exec_duration.rel_value)
1320     dur = INT_MAX;
1321   else
1322     dur = (int) ats->max_exec_duration.rel_value;
1323 #endif
1324
1325   ats->internal.simplex_rerun_required = GNUNET_NO;
1326   start = GNUNET_TIME_absolute_get ();
1327   if ((ats->internal.recreate_problem == GNUNET_YES) || (ats->prob == NULL) ||
1328       (ats->internal.valid == GNUNET_NO))
1329   {
1330     text = "new";
1331     ats->internal.recreate_problem = GNUNET_YES;
1332     ats_delete_problem (ats);
1333     ats->addr_notification (&ats->peers, &c_p, &ats->mechanisms, &c_m);
1334 #if DEBUG_ATS
1335     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1336                 "Service returned: %i peer, %i mechs\n", c_p, c_m);
1337 #endif
1338     ats_create_problem (ats, &ats->internal, ats->peers, c_p, ats->mechanisms,
1339                         c_m);
1340
1341
1342 #if DEBUG_ATS
1343     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1344                 "Peers/Addresses were modified... new problem: %i peer, %i mechs\n",
1345                 ats->internal.c_peers, ats->internal.c_mechs);
1346 #endif
1347   }
1348
1349   else if ((ats->internal.recreate_problem == GNUNET_NO) &&
1350            (ats->internal.modified_resources == GNUNET_YES) &&
1351            (ats->internal.valid == GNUNET_YES))
1352   {
1353     text = "modified resources";
1354     ats_update_problem_cr (ats);
1355   }
1356   else if ((ats->internal.recreate_problem == GNUNET_NO) &&
1357            (ats->internal.modified_quality == GNUNET_YES) &&
1358            (ats->internal.valid == GNUNET_YES))
1359   {
1360     text = "modified quality";
1361     ats_update_problem_qm (ats);
1362     //ats_update_problem_qm_TEST ();
1363   }
1364 #if DEBUG_ATS
1365   else
1366     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Problem is %s\n", text);
1367 #endif
1368
1369   creation =
1370       GNUNET_TIME_absolute_get_difference (start, GNUNET_TIME_absolute_get ());
1371   start = GNUNET_TIME_absolute_get ();
1372
1373   ats->internal.solution = GLP_UNDEF;
1374   if (ats->internal.valid == GNUNET_YES)
1375   {
1376     ats_solve_problem (ats, ats->max_iterations,
1377                        ats->max_exec_duration.rel_value, ats->internal.c_peers,
1378                        ats->internal.c_mechs, &ats->internal);
1379   }
1380   solving =
1381       GNUNET_TIME_absolute_get_difference (start, GNUNET_TIME_absolute_get ());
1382
1383   if (ats->internal.valid == GNUNET_YES)
1384   {
1385     /* Telling about new distribution */
1386     ats->result_cb ();
1387
1388     int msg_type = GNUNET_ERROR_TYPE_DEBUG;
1389
1390 #if DEBUG_ATS
1391     msg_type = GNUNET_ERROR_TYPE_ERROR;
1392 #endif
1393     GNUNET_log (msg_type,
1394                 "MLP %s: creation time: %llu, execution time: %llu, %i peers, %i mechanisms, simplex rerun: %s, solution %s\n",
1395                 text, creation.rel_value, solving.rel_value,
1396                 ats->internal.c_peers, ats->internal.c_mechs,
1397                 (ats->internal.simplex_rerun_required ==
1398                  GNUNET_NO) ? "NO" : "YES",
1399                 (ats->internal.solution == 5) ? "OPTIMAL" : "INVALID");
1400     ats->successful_executions++;
1401     GNUNET_STATISTICS_set (ats->stats, "# ATS successful executions",
1402                            ats->successful_executions, GNUNET_NO);
1403
1404     if ((ats->internal.recreate_problem == GNUNET_YES) || (ats->prob == NULL))
1405       GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_NEW, GNUNET_NO);
1406     else if ((ats->internal.modified_resources == GNUNET_YES) &&
1407              (ats->internal.modified_quality == GNUNET_NO))
1408       GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_COST_UPDATED,
1409                              GNUNET_NO);
1410     else if ((ats->internal.modified_resources == GNUNET_NO) &&
1411              (ats->internal.modified_quality == GNUNET_YES) &&
1412              (ats->internal.simplex_rerun_required == GNUNET_NO))
1413       GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_QUALITY_UPDATED,
1414                              GNUNET_NO);
1415     else if ((ats->internal.modified_resources == GNUNET_YES) &&
1416              (ats->internal.modified_quality == GNUNET_YES) &&
1417              (ats->internal.simplex_rerun_required == GNUNET_NO))
1418       GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_QUALITY_COST_UPDATED,
1419                              GNUNET_NO);
1420     else if (ats->internal.simplex_rerun_required == GNUNET_NO)
1421       GNUNET_STATISTICS_set (ats->stats, "ATS state", ATS_UNMODIFIED,
1422                              GNUNET_NO);
1423   }
1424   else
1425   {
1426     if (ats->internal.c_peers != 0)
1427     {
1428       ats->invalid_executions++;
1429       GNUNET_STATISTICS_set (ats->stats, "# ATS invalid executions",
1430                              ats->invalid_executions, GNUNET_NO);
1431     }
1432     else
1433     {
1434       GNUNET_STATISTICS_set (ats->stats, "# ATS successful executions",
1435                              ats->successful_executions, GNUNET_NO);
1436     }
1437   }
1438
1439   GNUNET_STATISTICS_set (ats->stats, "ATS duration",
1440                          solving.rel_value + creation.rel_value, GNUNET_NO);
1441   GNUNET_STATISTICS_set (ats->stats, "ATS mechanisms", ats->internal.c_mechs,
1442                          GNUNET_NO);
1443   GNUNET_STATISTICS_set (ats->stats, "ATS peers", ats->internal.c_peers,
1444                          GNUNET_NO);
1445   GNUNET_STATISTICS_set (ats->stats, "ATS solution", ats->internal.solution,
1446                          GNUNET_NO);
1447   GNUNET_STATISTICS_set (ats->stats, "ATS timestamp", start.abs_value,
1448                          GNUNET_NO);
1449
1450   if ((ats->save_mlp == GNUNET_YES) &&
1451       (ats->internal.c_mechs >= ats->dump_min_peers) &&
1452       (ats->internal.c_mechs >= ats->dump_min_addr))
1453   {
1454     char *filename;
1455
1456     if (ats->dump_overwrite == GNUNET_NO)
1457     {
1458       GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.mlp",
1459                        ats->internal.c_peers, ats->internal.c_mechs, text,
1460                        GNUNET_TIME_absolute_get ().abs_value);
1461       _lp_write_lp ((void *) ats->prob, NULL, filename);
1462     }
1463     else
1464     {
1465       GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.mlp", ats->internal.c_peers,
1466                        ats->internal.c_mechs);
1467       _lp_write_lp ((void *) ats->prob, NULL, filename);
1468     }
1469     GNUNET_free (filename);
1470   }
1471   if ((ats->save_solution == GNUNET_YES) &&
1472       (ats->internal.c_mechs >= ats->dump_min_peers) &&
1473       (ats->internal.c_mechs >= ats->dump_min_addr))
1474   {
1475     char *filename;
1476
1477     if (ats->dump_overwrite == GNUNET_NO)
1478     {
1479       GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i_%s_%llu.sol",
1480                        ats->internal.c_peers, ats->internal.c_mechs, text,
1481                        GNUNET_TIME_absolute_get ().abs_value);
1482       _lp_print_sol (ats->prob, filename);
1483     }
1484     else
1485     {
1486       GNUNET_asprintf (&filename, "ats_mlp_p%i_m%i.sol", ats->internal.c_peers,
1487                        ats->internal.c_mechs);
1488       _lp_print_sol (ats->prob, filename);
1489     }
1490     GNUNET_free (filename);
1491   }
1492
1493   ats->internal.recreate_problem = GNUNET_NO;
1494   ats->internal.modified_resources = GNUNET_NO;
1495   ats->internal.modified_quality = GNUNET_NO;
1496 }
1497
1498 /**
1499  * Evaluate the result of the last simplex or mlp solving
1500  * @param result return value returned by the solver
1501  * @param solution solution state
1502  * @param problem mlp or lp
1503  * @return GNUNET_NO if solution is invalid, GNUNET_YES if solution is
1504  *      valid
1505  */
1506
1507 int
1508 ats_evaluate_results (int result, int solution, char *problem)
1509 {
1510   int cont = GNUNET_NO;
1511
1512 #if DEBUG_ATS || VERBOSE_ATS
1513   int error_kind = GNUNET_ERROR_TYPE_DEBUG;
1514 #endif
1515 #if VERBOSE_ATS
1516   error_kind = GNUNET_ERROR_TYPE_ERROR;
1517 #endif
1518   switch (result)
1519   {
1520   case GNUNET_SYSERR:          /* GNUNET problem, not GLPK related */
1521 #if DEBUG_ATS || VERBOSE_ATS
1522     GNUNET_log (error_kind, "%s, GLPK solving not executed\n", problem);
1523 #endif
1524     break;
1525   case GLP_ESTOP:              /* search terminated by application */
1526 #if DEBUG_ATS || VERBOSE_ATS
1527     GNUNET_log (error_kind, "%s , Search terminated by application\n", problem);
1528 #endif
1529     break;
1530   case GLP_EITLIM:             /* iteration limit exceeded */
1531 #if DEBUG_ATS || VERBOSE_ATS
1532     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Iteration limit exceeded\n",
1533                 problem);
1534 #endif
1535     break;
1536   case GLP_ETMLIM:             /* time limit exceeded */
1537 #if DEBUG_ATS || VERBOSE_ATS
1538     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s Time limit exceeded\n", problem);
1539 #endif
1540     break;
1541   case GLP_ENOPFS:             /* no primal feasible solution */
1542   case GLP_ENODFS:             /* no dual feasible solution */
1543 #if DEBUG_ATS || VERBOSE_ATS
1544     GNUNET_log (error_kind, "%s No feasible solution\n", problem);
1545 #endif
1546     break;
1547   case GLP_EBADB:              /* invalid basis */
1548   case GLP_ESING:              /* singular matrix */
1549   case GLP_ECOND:              /* ill-conditioned matrix */
1550   case GLP_EBOUND:             /* invalid bounds */
1551   case GLP_EFAIL:              /* solver failed */
1552   case GLP_EOBJLL:             /* objective lower limit reached */
1553   case GLP_EOBJUL:             /* objective upper limit reached */
1554   case GLP_EROOT:              /* root LP optimum not provided */
1555 #if DEBUG_ATS || VERBOSE_ATS
1556     GNUNET_log (error_kind, "%s Invalid Input data: %i\n", problem, result);
1557 #endif
1558     break;
1559   case 0:
1560 #if DEBUG_ATS || VERBOSE_ATS
1561     GNUNET_log (error_kind, "%s Problem has been solved\n", problem);
1562 #endif
1563     break;
1564   }
1565
1566   switch (solution)
1567   {
1568   case GLP_UNDEF:
1569 #if DEBUG_ATS || VERBOSE_ATS
1570     GNUNET_log (error_kind, "%s solution is undefined\n", problem);
1571 #endif
1572     break;
1573   case GLP_OPT:
1574 #if DEBUG_ATS || VERBOSE_ATS
1575     GNUNET_log (error_kind, "%s solution is optimal\n", problem);
1576 #endif
1577     cont = GNUNET_YES;
1578     break;
1579   case GLP_FEAS:
1580 #if DEBUG_ATS || VERBOSE_ATS
1581     GNUNET_log (error_kind,
1582                 "%s solution is %s feasible, however, its optimality (or non-optimality) has not been proven\n",
1583                 problem, (0 == strcmp (problem, "LP") ? "" : "integer"));
1584 #endif
1585     cont = GNUNET_YES;
1586     break;
1587   case GLP_NOFEAS:
1588 #if DEBUG_ATS || VERBOSE_ATS
1589     GNUNET_log (error_kind, "%s problem has no %sfeasible solution\n", problem,
1590                 (0 == strcmp (problem, "LP") ? "" : "integer "));
1591 #endif
1592     break;
1593   case GLP_INFEAS:
1594 #if DEBUG_ATS || VERBOSE_ATS
1595     GNUNET_log (error_kind, "%s problem is infeasible \n", problem);
1596 #endif
1597     break;
1598   case GLP_UNBND:
1599 #if DEBUG_ATS || VERBOSE_ATS
1600     GNUNET_log (error_kind, "%s problem is unbounded \n", problem);
1601 #endif
1602   default:
1603     break;
1604   }
1605   return cont;
1606 }
1607
1608 void
1609 ats_update_problem_cr (struct ATS_Handle *ats)
1610 {
1611   int array_index;
1612   int row_index;
1613   int c, c2;
1614   double ct_max, ct_min;
1615
1616   int *ja =
1617       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1618                       available_quality_metrics) * sizeof (int));
1619   double *ar =
1620       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1621                       available_quality_metrics) * sizeof (double));
1622
1623   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating problem quality metrics\n");
1624   row_index = ats->internal.begin_cr;
1625   array_index = 1;
1626
1627   for (c = 0; c < available_ressources; c++)
1628   {
1629     ct_max = ressources[c].c_max;
1630     ct_min = ressources[c].c_min;
1631 #if VERBOSE_ATS
1632     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "bounds [row]=[%i] %f..%f\n",
1633                 row_index, ct_min, ct_max);
1634 #endif
1635     _lp_set_row_bnds (ats->prob, row_index, GLP_DB, ct_min, ct_max);
1636     for (c2 = 1; c2 <= ats->internal.c_mechs; c2++)
1637     {
1638       double value = 0;
1639
1640       GNUNET_assert (ats->mechanisms[c2].addr != NULL);
1641       GNUNET_assert (ats->mechanisms[c2].peer != NULL);
1642
1643       ja[array_index] = c2;
1644       value = ats->mechanisms[c2].ressources[c].c;
1645       ar[array_index] = value;
1646 #if VERBOSE_ATS
1647       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "[index]=[%i]: [%i,%i]=%f \n",
1648                   array_index, row_index, ja[array_index], ar[array_index]);
1649 #endif
1650       array_index++;
1651     }
1652     _lp_set_mat_row (ats->prob, row_index, array_index, ja, ar);
1653     row_index++;
1654   }
1655   GNUNET_free_non_null (ja);
1656   GNUNET_free_non_null (ar);
1657
1658 }
1659
1660 void
1661 ats_set_logging_options (struct ATS_Handle *ats,
1662                          struct GNUNET_STATISTICS_Handle *stats,
1663                          const struct GNUNET_CONFIGURATION_Handle *cfg)
1664 {
1665   int minimum_addresses;
1666   int minimum_peers;
1667   int overwrite_dump;
1668   int log_solution;
1669   int log_problem;
1670   unsigned long long value;
1671
1672   if (ats == NULL)
1673     return;
1674   log_problem =
1675       GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_MLP");
1676   log_solution =
1677       GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_SOLUTION");
1678   overwrite_dump =
1679       GNUNET_CONFIGURATION_get_value_yesno (cfg, "transport", "DUMP_OVERWRITE");
1680   if (GNUNET_OK ==
1681       GNUNET_CONFIGURATION_get_value_number (cfg, "transport", "DUMP_MIN_PEERS",
1682                                              &value))
1683     minimum_peers = (int) value;
1684   if (GNUNET_OK ==
1685       GNUNET_CONFIGURATION_get_value_number (cfg, "transport", "DUMP_MIN_ADDRS",
1686                                              &value))
1687     minimum_addresses = (int) value;
1688
1689
1690   ats->stats = stats;
1691   ats->dump_min_addr = minimum_addresses;
1692   ats->dump_min_peers = minimum_peers;
1693   ats->dump_overwrite = overwrite_dump;
1694   ats->save_mlp = log_problem;
1695   ats->save_solution = log_solution;
1696 }
1697
1698 #if 0
1699 static void
1700 ats_update_problem_qm_TEST ()
1701 {
1702   int row_index;
1703   int c int c2;
1704   int c_old;
1705   int changed = 0;
1706
1707   int old_ja[ats->internal.c_mechs + 2];
1708   double old_ar[ats->internal.c_mechs + 2];
1709
1710   int *ja =
1711       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1712                       available_quality_metrics) * sizeof (int));
1713   double *ar =
1714       GNUNET_malloc ((1 + ats->internal.c_mechs * 2 + 3 +
1715                       available_quality_metrics) * sizeof (double));
1716 #if DEBUG_ATS
1717   GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1718               "Updating problem quality metrics TEST\n");
1719 #endif
1720   if (ats->internal.begin_qm > 0)
1721     row_index = ats->internal.begin_qm;
1722   else
1723     return;
1724   for (c = 0; c < available_quality_metrics; c++)
1725   {
1726     c_old = _lp_get_mat_row (ats->prob, row_index, old_ja, old_ar);
1727     _lp_set_row_bnds (ats->prob, row_index, GLP_FX, 0.0, 0.0);
1728     for (c2 = 1; c2 <= c_old; c2++)
1729     {
1730       ja[c2] = old_ja[c2];
1731       if ((changed < 3) && (c2 > 2) && (old_ar[c2] != -1))
1732       {
1733         ar[c2] = old_ar[c2] + 5 - changed;
1734         changed++;
1735       }
1736       else
1737         ar[c2] = old_ar[c2];
1738 #if VERBOSE_ATS
1739       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1740                   "[index]=[%i]: old [%i,%i]=%f  new [%i,%i]=%f\n", c2,
1741                   row_index, old_ja[c2], old_ar[c2], row_index, ja[c2], ar[c2]);
1742 #endif
1743     }
1744     _lp_set_mat_row (ats->prob, row_index, c_old, ja, ar);
1745     row_index++;
1746   }
1747   GNUNET_free_non_null (ja);
1748   GNUNET_free_non_null (ar);
1749 }
1750 #endif
1751
1752
1753
1754 /* end of transport_ats.c */