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