src/transport/gnunet-service-transport_ats.c

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