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