src/ats/gnunet-service-ats_addresses_mlp.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file ats/gnunet-service-ats_addresses_mlp.c
  23  * @brief ats mlp problem solver
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #include "gnunet-service-ats_addresses_mlp.h"
  31 #include "gnunet_statistics_service.h"
  32 #include "glpk.h"
  33 #include "float.h"
  34
  35 #define WRITE_MLP GNUNET_NO
  36 #define DEBUG_ATS GNUNET_YES
  37 /* A very big value */
  38 #define M DBL_MAX
  39
  40 /**
  41  * Translate glpk solver error codes to text
  42  * @param retcode return code
  43  * @return string with result
  44  */
  45 const char *
  46 mlp_solve_to_string (int retcode)
  47 {
  48   switch (retcode) {
  49     case 0:
  50       return "ok";
  51       break;
  52     case GLP_EBADB:
  53       return "invalid basis";
  54       break;
  55     case GLP_ESING:
  56       return "singular matrix";
  57       break;
  58     case GLP_ECOND:
  59       return "ill-conditioned matrix";
  60       break;
  61     case GLP_EBOUND:
  62       return "invalid bounds";
  63       break;
  64     case GLP_EFAIL:
  65       return "solver failed";
  66       break;
  67     case GLP_EOBJLL:
  68       return "objective lower limit reached";
  69       break;
  70     case GLP_EOBJUL:
  71       return "objective upper limit reached";
  72       break;
  73     case GLP_EITLIM:
  74       return "iteration limit exceeded";
  75       break;
  76     case GLP_ETMLIM:
  77       return "time limit exceeded";
  78       break;
  79     case GLP_ENOPFS:
  80       return "no primal feasible solution";
  81       break;
  82     case GLP_EROOT:
  83       return "root LP optimum not provided";
  84       break;
  85     case GLP_ESTOP:
  86       return "search terminated by application";
  87       break;
  88     case GLP_EMIPGAP:
  89       return "relative mip gap tolerance reached";
  90       break;
  91     case GLP_ENOFEAS:
  92       return "no dual feasible solution";
  93       break;
  94     case GLP_ENOCVG:
  95       return "no convergence";
  96       break;
  97     case GLP_EINSTAB:
  98       return "numerical instability";
  99       break;
 100     case GLP_EDATA:
 101       return "invalid data";
 102       break;
 103     case GLP_ERANGE:
 104       return "result out of range";
 105       break;
 106     default:
 107       GNUNET_break (0);
 108       return "unknown error";
 109       break;
 110   }
 111   GNUNET_break (0);
 112   return "unknown error";
 113 }
 114
 115
 116 /**
 117  * Translate glpk status error codes to text
 118  * @param retcode return code
 119  * @return string with result
 120  */
 121 const char *
 122 mlp_status_to_string (int retcode)
 123 {
 124   switch (retcode) {
 125     case GLP_UNDEF:
 126       return "solution is undefined";
 127       break;
 128     case GLP_FEAS:
 129       return "solution is feasible";
 130       break;
 131     case GLP_INFEAS:
 132       return "solution is infeasible";
 133       break;
 134     case GLP_NOFEAS:
 135       return "no feasible solution exists";
 136       break;
 137     case GLP_OPT:
 138       return "solution is optimal";
 139       break;
 140     case GLP_UNBND:
 141       return "solution is unbounded";
 142       break;
 143     default:
 144       GNUNET_break (0);
 145       return "unknown error";
 146       break;
 147   }
 148   GNUNET_break (0);
 149   return "unknown error";
 150 }
 151
 152 /**
 153  * Find a peer in the DLL
 154  * @param the peer to find
 155  * @return the peer struct
 156  */
 157 static struct ATS_Peer *
 158 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
 159 {
 160   struct ATS_Peer *res = mlp->peer_head;
 161   while (res != NULL)
 162   {
 163     if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
 164       break;
 165     res = res->next;
 166   }
 167   return res;
 168 }
 169
 170 /**
 171  * Intercept GLPK terminal output
 172  * @param info the mlp handle
 173  * @param s the string to print
 174  * @return 0: glpk prints output on terminal, 0 != surpress output
 175  */
 176 static int
 177 mlp_term_hook (void *info, const char *s)
 178 {
 179   /* Not needed atm struct MLP_information *mlp = info; */
 180   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
 181   return 1;
 182 }
 183
 184 /**
 185  * Delete the MLP problem and free the constrain matrix
 186  *
 187  * @param mlp the MLP handle
 188  */
 189 static void
 190 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 191 {
 192   if (mlp != NULL)
 193   {
 194     if (mlp->prob != NULL)
 195       glp_delete_prob(mlp->prob);
 196
 197     /* delete row index */
 198     if (mlp->ia != NULL)
 199     {
 200       GNUNET_free (mlp->ia);
 201       mlp->ia = NULL;
 202     }
 203
 204     /* delete column index */
 205     if (mlp->ja != NULL)
 206     {
 207       GNUNET_free (mlp->ja);
 208       mlp->ja = NULL;
 209     }
 210
 211     /* delete coefficients */
 212     if (mlp->ar != NULL)
 213     {
 214       GNUNET_free (mlp->ar);
 215       mlp->ar = NULL;
 216     }
 217     mlp->ci = 0;
 218     mlp->prob = NULL;
 219   }
 220 }
 221
 222 /**
 223  * Add constraints that are iterating over "forall addresses"
 224  * and collects all existing peers for "forall peers" constraints
 225  *
 226  * @param cls GAS_MLP_Handle
 227  * @param key Hashcode
 228  * @param value ATS_Address
 229  *
 230  * @return GNUNET_OK to continue
 231  */
 232 static int
 233 create_constraint_it (void *cls, const GNUNET_HashCode * key, void *value)
 234 {
 235   struct GAS_MLP_Handle *mlp = cls;
 236   struct ATS_Address *address = value;
 237   struct MLP_information *mlpi;
 238   unsigned int row_index;
 239
 240   GNUNET_assert (address->mlp_information != NULL);
 241   mlpi = (struct MLP_information *) address->mlp_information;
 242
 243   /* c 1) bandwidth capping
 244    * b_t  + (-M) * n_t <= 0
 245    */
 246   row_index = glp_add_rows (mlp->prob, 1);
 247   mlpi->r_c1 = row_index;
 248   /* set row bounds: <= 0 */
 249   glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
 250
 251   mlp->ia[mlp->ci] = row_index;
 252   mlp->ja[mlp->ci] = mlpi->c_b;
 253   mlp->ar[mlp->ci] = 1;
 254   mlp->ci++;
 255
 256   mlp->ia[mlp->ci] = row_index;
 257   mlp->ja[mlp->ci] = mlpi->c_n;
 258   mlp->ar[mlp->ci] = -M;
 259   mlp->ci++;
 260 #if 0
 261   /* c 3) minimum bandwidth
 262    * b_t + (-n_t * b_min) >= 0
 263    */
 264
 265   row_index = glp_add_rows (mlp->prob, 1);
 266   mlpi->r_c3 = row_index;
 267   /* set row bounds: >= 0 */
 268   glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
 269
 270   mlp->ia[mlp->ci] = row_index;
 271   mlp->ja[mlp->ci] = mlpi->c_b;
 272   mlp->ar[mlp->ci] = 1;
 273   mlp->ci++;
 274
 275   mlp->ia[mlp->ci] = row_index;
 276   mlp->ja[mlp->ci] = mlpi->c_n;
 277   mlp->ar[mlp->ci] = -mlp->b_min;
 278   mlp->ci++;
 279
 280   /* c 4) minimum connections
 281    * (1)*n_1 + ... + (1)*n_m >= n_min
 282    */
 283   mlp->ia[mlp->ci] = mlp->r_c4;
 284   mlp->ja[mlp->ci] = mlpi->c_n;
 285   mlp->ar[mlp->ci] = 1;
 286   mlp->ci++;
 287
 288   /* c 6) maximize diversity
 289    * (1)*n_1 + ... + (1)*n_m - d == 0
 290    */
 291   mlp->ia[mlp->ci] = mlp->r_c6;
 292   mlp->ja[mlp->ci] = mlpi->c_n;
 293   mlp->ar[mlp->ci] = 1;
 294   mlp->ci++;
 295 #endif
 296
 297   return GNUNET_OK;
 298 }
 299
 300
 301 /**
 302  * Adds the problem constraints for all addresses
 303  * Required for problem recreation after address deletion
 304  *
 305  * @param addresses all addresses
 306  */
 307
 308 static void
 309 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 310 {
 311   unsigned int n_addresses;
 312   int row_index;
 313   //int c;
 314
 315   /* Problem matrix*/
 316   n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses);
 317
 318   /* Required indices in the constrain matrix
 319    *
 320    * feasibility constraints:
 321    *
 322    * c 1) bandwidth capping
 323    * #rows: |n_addresses|
 324    * #indices: 2 * |n_addresses|
 325    *
 326    * c 2) one active address per peer
 327    * #rows: |peers|
 328    * #indices: |n_addresses|
 329    *
 330    * c 3) minium bandwidth assigned
 331    * #rows: |n_addresses|
 332    * #indices: 2 * |n_addresses|
 333    *
 334    * c 4) minimum number of active connections
 335    * #rows: 1
 336    * #indices: |n_addresses|
 337    *
 338    * c 5) maximum ressource consumption
 339    * #rows: |ressources|
 340    * #indices: |n_addresses|
 341    *
 342    * Sum for feasibility constraints:
 343    * #rows: 3 * |n_addresses| +  |ressources| + |peers| + 1
 344    * #indices: 7 * |n_addresses|
 345    *
 346    * optimality constraints:
 347    *
 348    * c 6) diversity
 349    * #rows: 1
 350    * #indices: |n_addresses| + 1
 351    *
 352    * c 7) quality
 353    * #rows: |quality properties|
 354    * #indices:|quality properties| + |n_addresses|
 355    * */
 356
 357   int pi = ((7 * n_addresses) /*+ (2 * n_addresses +  mlp->m_q + 1)*/);
 358   mlp->cm_size = pi;
 359   mlp->ci = 0;
 360
 361   /* row index */
 362   int *ia = GNUNET_malloc (pi * sizeof (int));
 363   mlp->ia = ia;
 364
 365   /* column index */
 366   int *ja = GNUNET_malloc (pi * sizeof (int));
 367   mlp->ja = ja;
 368
 369   /* coefficient */
 370   double *ar= GNUNET_malloc (pi * sizeof (double));
 371   mlp->ar = ar;
 372
 373   /* Adding constraint rows
 374    * This constraints are kind of "for all addresses"
 375    * Feasibility constraints:
 376    *
 377    * c 1) bandwidth capping
 378    * c 3) minimum bandwidth
 379    * c 4) minimum number of connections
 380    * c 6) maximize diversity
 381    */
 382
 383   int min = mlp->n_min;
 384   if (mlp->n_min > mlp->c_p)
 385     min = mlp->c_p;
 386 /*
 387   mlp->r_c4 = glp_add_rows (mlp->prob, 1);
 388   glp_set_row_bnds (mlp->prob, mlp->r_c4, GLP_FX, min, min);
 389 */
 390   /* Add row for c6) */
 391 #if 0
 392   mlp->r_c6 = glp_add_rows (mlp->prob, 1);
 393   /* Set type type to fix */
 394   glp_set_row_bnds (mlp->prob, mlp->r_c6, GLP_FX, 0.0, 0.0);
 395   /* Setting -D */
 396   ia[mlp->ci] = mlp->r_c6 ;
 397   ja[mlp->ci] = mlp->c_d;
 398   ar[mlp->ci] = -1;
 399   mlp->ci++;
 400 #endif
 401   GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
 402
 403   /* Adding constraint rows
 404    * This constraints are kind of "for all peers"
 405    * Feasibility constraints:
 406    *
 407    * c 2) 1 address per peer
 408    * sum (n_p1_1 + ... + n_p1_n) = 1
 409    */
 410 return;
 411   /* Adding rows for c 2) */
 412   row_index = glp_add_rows (mlp->prob, mlp->c_p);
 413
 414   struct ATS_Peer * peer = mlp->peer_head;
 415   while (peer != NULL)
 416   {
 417     struct ATS_Address *addr = peer->head;
 418     struct MLP_information *mlpi = (struct MLP_information *) addr->mlp_information;
 419     /* Adding row for c 2) */
 420     /* Set row bound == 1 */
 421     glp_set_row_bnds (mlp->prob, row_index, GLP_FX, 1.0, 1.0);
 422
 423     while (addr != NULL)
 424     {
 425       ia[mlp->ci] = row_index;
 426       ja[mlp->ci] = mlpi->c_n;
 427       ar[mlp->ci] = 1;
 428       mlp->ci++;
 429
 430       addr = addr->next;
 431     }
 432     peer = peer->next;
 433   }
 434
 435
 436   /* For all quality metrics */
 437 /*
 438   for (c = 0; c < mlp->m_q; c++)
 439   {
 440     struct ATS_Peer *p = mlp->peer_head;
 441     while (p != NULL)
 442     {
 443       ia[mlp->ci] = row_index;
 444       ja[mlp->ci] = mlp->c_q[c];
 445       ar[mlp->ci] = mlp->;
 446       mlp->ci++;
 447
 448       p = p->next;
 449     }
 450   }
 451 */
 452 }
 453
 454
 455 /**
 456  * Add columns for all addresses
 457  *
 458  * @param cls GAS_MLP_Handle
 459  * @param key Hashcode
 460  * @param value ATS_Address
 461  *
 462  * @return GNUNET_OK to continue
 463  */
 464 static int
 465 create_columns_it (void *cls, const GNUNET_HashCode * key, void *value)
 466 {
 467   struct GAS_MLP_Handle *mlp = cls;
 468   struct ATS_Address *address = value;
 469   struct MLP_information *mlpi;
 470   unsigned int col;
 471   char *name;
 472
 473   GNUNET_assert (address->mlp_information != NULL);
 474   mlpi = address->mlp_information;
 475
 476   /* Add bandwidth column */
 477   col = glp_add_cols (mlp->prob, 2);
 478   mlpi->c_b = col;
 479   mlpi->c_n = col + 1;
 480
 481   GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 482       "ats-mlp",
 483       "Culoumn %i %i\n", mlpi->c_b, mlpi->c_n);
 484
 485   GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 486   glp_set_col_name (mlp->prob, mlpi->c_b , name);
 487   GNUNET_free (name);
 488   /* Lower bound == 0 */
 489   glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
 490   /* Continuous value*/
 491   glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
 492   /* Objective function coefficient == 0 */
 493   glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
 494
 495
 496   /* Add usage column */
 497   GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 498   glp_set_col_name (mlp->prob, mlpi->c_n, name);
 499   GNUNET_free (name);
 500   /* Limit value : 0 <= value <= 1 */
 501   glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
 502   /* Integer value*/
 503   glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
 504   /* Objective function coefficient == 0 */
 505   glp_set_obj_coef (mlp->prob, mlpi->c_n, 1);
 506
 507   return GNUNET_OK;
 508 }
 509
 510
 511
 512 /**
 513  * Create the MLP problem
 514  *
 515  * @param mlp the MLP handle
 516  * @return GNUNET_OK or GNUNET_SYSERR
 517  */
 518 static int
 519 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 520 {
 521   int res = GNUNET_OK;
 522 /*
 523   int col;
 524   int c;
 525   char *name;
 526 */
 527   GNUNET_assert (mlp->prob == NULL);
 528
 529   /* create the glpk problem */
 530   mlp->prob = glp_create_prob ();
 531
 532   /* Set a problem name */
 533   glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
 534
 535   /* Set optimization direction to maximize */
 536   glp_set_obj_dir (mlp->prob, GLP_MAX);
 537
 538   /* Adding invariant columns */
 539
 540   /* Diversity d column  */
 541 #if 0
 542   col = glp_add_cols (mlp->prob, 1);
 543   mlp->c_d = col;
 544   /* Column name */
 545   glp_set_col_name (mlp->prob, col, "d");
 546   /* Column objective function coefficient */
 547   glp_set_obj_coef (mlp->prob, col, mlp->co_D);
 548   /* Column lower bound = 0.0 */
 549   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 550
 551   /* Utilization u column  */
 552
 553   col = glp_add_cols (mlp->prob, 1);
 554   mlp->c_u = col;
 555   /* Column name */
 556   glp_set_col_name (mlp->prob, col, "u");
 557   /* Column objective function coefficient */
 558   glp_set_obj_coef (mlp->prob, col, mlp->co_U);
 559   /* Column lower bound = 0.0 */
 560   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 561
 562   /* Relativity r column  */
 563   col = glp_add_cols (mlp->prob, 1);
 564   mlp->c_r = col;
 565   /* Column name */
 566   glp_set_col_name (mlp->prob, col, "r");
 567   /* Column objective function coefficient */
 568   glp_set_obj_coef (mlp->prob, col, mlp->co_R);
 569   /* Column lower bound = 0.0 */
 570   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 571
 572   /* Quality metric columns */
 573   col = glp_add_cols(mlp->prob, mlp->m_q);
 574   for (c = 0; c < mlp->m_q; c++)
 575   {
 576     mlp->c_q[c] = col + c;
 577     GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
 578     glp_set_col_name (mlp->prob, col + c, name);
 579     /* Column lower bound = 0.0 */
 580     glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
 581     GNUNET_free (name);
 582     /* Coefficient == Qm */
 583     glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
 584   }
 585 #endif
 586   /* Add columns for addresses */
 587   GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
 588
 589   /* Add constraints */
 590   mlp_add_constraints_all_addresses (mlp, addresses);
 591
 592   /* Load the matrix */
 593   glp_load_matrix(mlp->prob, (mlp->ci - 1), mlp->ia, mlp->ja, mlp->ar);
 594
 595   return res;
 596 }
 597
 598 /**
 599  * Solves the LP problem
 600  *
 601  * @param mlp the MLP Handle
 602  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 603  */
 604 static int
 605 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 606 {
 607   int res;
 608   struct GNUNET_TIME_Relative duration;
 609   struct GNUNET_TIME_Absolute end;
 610   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 611
 612   /* LP presolver?
 613    * Presolver is required if the problem was modified and an existing
 614    * valid basis is now invalid */
 615   if (mlp->presolver_required == GNUNET_YES)
 616     mlp->control_param_lp.presolve = GLP_ON;
 617   else
 618     mlp->control_param_lp.presolve = GLP_OFF;
 619
 620   /* Solve LP problem to have initial valid solution */
 621 lp_solv:
 622   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
 623   if (res == 0)
 624   {
 625     /* The LP problem instance has been successfully solved. */
 626   }
 627   else if (res == GLP_EITLIM)
 628   {
 629     /* simplex iteration limit has been exceeded. */
 630     // TODO Increase iteration limit?
 631   }
 632   else if (res == GLP_ETMLIM)
 633   {
 634     /* Time limit has been exceeded.  */
 635     // TODO Increase time limit?
 636   }
 637   else
 638   {
 639     /* Problem was ill-defined, retry with presolver */
 640     if (mlp->presolver_required == GNUNET_NO)
 641     {
 642       mlp->presolver_required = GNUNET_YES;
 643       goto lp_solv;
 644     }
 645     else
 646     {
 647       /* Problem was ill-defined, no way to handle that */
 648       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 649           "ats-mlp",
 650           "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
 651       return GNUNET_SYSERR;
 652     }
 653   }
 654
 655   end = GNUNET_TIME_absolute_get ();
 656   duration = GNUNET_TIME_absolute_get_difference (start, end);
 657   mlp->lp_solved++;
 658   mlp->lp_total_duration =+ duration.rel_value;
 659
 660   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 661   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
 662   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
 663                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 664
 665
 666   /* Analyze problem status  */
 667   res = glp_get_status (mlp->prob);
 668   switch (res) {
 669     /* solution is optimal */
 670     case GLP_OPT:
 671     /* solution is feasible */
 672     case GLP_FEAS:
 673       break;
 674
 675     /* Problem was ill-defined, no way to handle that */
 676     default:
 677       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 678           "ats-mlp",
 679           "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
 680       return GNUNET_SYSERR;
 681       break;
 682   }
 683
 684   /* solved sucessfully, no presolver required next time */
 685   mlp->presolver_required = GNUNET_NO;
 686
 687   return GNUNET_OK;
 688 }
 689
 690
 691 /**
 692  * Solves the MLP problem
 693  *
 694  * @param mlp the MLP Handle
 695  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 696  */
 697 int
 698 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 699 {
 700   int res;
 701   struct GNUNET_TIME_Relative duration;
 702   struct GNUNET_TIME_Absolute end;
 703   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 704
 705   /* solve MLP problem */
 706   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 707
 708   if (res == 0)
 709   {
 710     /* The MLP problem instance has been successfully solved. */
 711   }
 712   else if (res == GLP_EITLIM)
 713   {
 714     /* simplex iteration limit has been exceeded. */
 715     // TODO Increase iteration limit?
 716   }
 717   else if (res == GLP_ETMLIM)
 718   {
 719     /* Time limit has been exceeded.  */
 720     // TODO Increase time limit?
 721   }
 722   else
 723   {
 724     /* Problem was ill-defined, no way to handle that */
 725     GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 726         "ats-mlp",
 727         "Solving MLP problem failed:  %s\n", mlp_solve_to_string(res));
 728     return GNUNET_SYSERR;
 729   }
 730
 731   end = GNUNET_TIME_absolute_get ();
 732   duration = GNUNET_TIME_absolute_get_difference (start, end);
 733   mlp->mlp_solved++;
 734   mlp->mlp_total_duration =+ duration.rel_value;
 735
 736   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 737   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
 738   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
 739                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 740
 741   /* Analyze problem status  */
 742   res = glp_mip_status(mlp->prob);
 743   switch (res) {
 744     /* solution is optimal */
 745     case GLP_OPT:
 746     /* solution is feasible */
 747     case GLP_FEAS:
 748       break;
 749
 750     /* Problem was ill-defined, no way to handle that */
 751     default:
 752       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 753           "ats-mlp",
 754           "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
 755       return GNUNET_SYSERR;
 756       break;
 757   }
 758
 759   return GNUNET_OK;
 760 }
 761
 762 int mlp_solve_problem (struct GAS_MLP_Handle *mlp);
 763
 764 static void
 765 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 766 {
 767   struct GAS_MLP_Handle *mlp = cls;
 768
 769   mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 770
 771   if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 772     return;
 773
 774 #if DEBUG_ATS
 775   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
 776 #endif
 777   if (mlp->addr_in_problem != 0)
 778     mlp_solve_problem(mlp);
 779 }
 780
 781
 782 /**
 783  * Solves the MLP problem
 784  *
 785  * @param mlp the MLP Handle
 786  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 787  */
 788 int
 789 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
 790 {
 791   int res;
 792   mlp->last_execution = GNUNET_TIME_absolute_get ();
 793 #if DEBUG_ATS
 794   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solving\n");
 795 #endif
 796
 797 #if WRITE_MLP
 798   char * name;
 799   static int i;
 800   i++;
 801   GNUNET_asprintf(&name, "problem_%i", i);
 802   glp_write_lp (mlp->prob, 0, name);
 803   GNUNET_free (name);
 804 # endif
 805
 806   res = mlp_solve_lp_problem (mlp);
 807
 808 #if WRITE_MLP
 809   GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
 810   glp_print_sol (mlp->prob,  name);
 811   GNUNET_free (name);
 812 # endif
 813
 814   if (res != GNUNET_OK)
 815   {
 816 #if DEBUG_ATS
 817   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
 818 #endif
 819     return GNUNET_SYSERR;
 820   }
 821
 822   res = mlp_solve_mlp_problem (mlp);
 823
 824 #if WRITE_MLP
 825   GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
 826   glp_print_mip (mlp->prob, name);
 827   GNUNET_free (name);
 828 # endif
 829
 830
 831   if (res != GNUNET_OK)
 832   {
 833 #if DEBUG_ATS
 834   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MLP Problem solving failed\n");
 835 #endif
 836     return GNUNET_SYSERR;
 837   }
 838
 839   res = glp_mip_status(mlp->prob);
 840
 841   if (res != GNUNET_OK)
 842   {
 843 #if DEBUG_ATS
 844   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
 845 #endif
 846     return GNUNET_SYSERR;
 847   }
 848
 849 #if DEBUG_ATS
 850   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved: %i %s\n", res, mlp_status_to_string(res));
 851 #endif
 852
 853   /* Process result */
 854
 855   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
 856   {
 857     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
 858     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 859   }
 860   mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
 861   return res;
 862 }
 863
 864 /**
 865  * Init the MLP problem solving component
 866  *
 867  * @param stats the GNUNET_STATISTICS handle
 868  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 869  * @param max_iterations maximum time limit for the LP/MLP Solver
 870  * @return struct GAS_MLP_Handle * on success, NULL on fail
 871  */
 872 struct GAS_MLP_Handle *
 873 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 874               const struct GNUNET_STATISTICS_Handle *stats,
 875               struct GNUNET_TIME_Relative max_duration,
 876               unsigned int max_iterations)
 877 {
 878   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
 879
 880   double D;
 881   double R;
 882   double U;
 883   long long unsigned int tmp;
 884   unsigned int b_min;
 885   unsigned int n_min;
 886   struct GNUNET_TIME_Relative i_exec;
 887
 888   /* Init GLPK environment */
 889   GNUNET_assert (glp_init_env() == 0);
 890
 891   /* Create initial MLP problem */
 892   mlp->prob = glp_create_prob();
 893   GNUNET_assert (mlp->prob != NULL);
 894
 895   /* Get diversity coefficient from configuration */
 896   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 897                                                       "COEFFICIENT_D",
 898                                                       &tmp))
 899     D = (double) tmp / 100;
 900   else
 901     D = 1.0;
 902
 903   /* Get proportionality coefficient from configuration */
 904   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 905                                                       "COEFFICIENT_R",
 906                                                       &tmp))
 907     R = (double) tmp / 100;
 908   else
 909     R = 1.0;
 910
 911   /* Get utilization coefficient from configuration */
 912   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 913                                                       "COEFFICIENT_U",
 914                                                       &tmp))
 915     U = (double) tmp / 100;
 916   else
 917     U = 1.0;
 918
 919   /* Get quality metric coefficients from configuration */
 920   int i_delay = -1;
 921   int i_distance = -1;
 922   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
 923   int c;
 924   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 925   {
 926     /* initialize quality coefficients with default value 1.0 */
 927     mlp->co_Q[c] = 1.0;
 928
 929     mlp->q[c] = q[c];
 930     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
 931       i_delay = c;
 932     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
 933       i_distance = c;
 934   }
 935
 936   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 937                                                       "COEFFICIENT_QUALITY_DELAY",
 938                                                       &tmp)))
 939
 940     mlp->co_Q[i_delay] = (double) tmp / 100;
 941   else
 942     mlp->co_Q[i_delay] = 1.0;
 943
 944   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 945                                                       "COEFFICIENT_QUALITY_DISTANCE",
 946                                                       &tmp)))
 947     mlp->co_Q[i_distance] = (double) tmp / 100;
 948   else
 949     mlp->co_Q[i_distance] = 1.0;
 950
 951   /* Get minimum bandwidth per used address from configuration */
 952   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 953                                                       "MIN_BANDWIDTH",
 954                                                       &tmp))
 955     b_min = tmp;
 956   else
 957     b_min = 64000;
 958
 959   /* Get minimum number of connections from configuration */
 960   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 961                                                       "MIN_CONNECTIONS",
 962                                                       &tmp))
 963     n_min = tmp;
 964   else
 965     n_min = 4;
 966
 967   /* Get minimum number of connections from configuration */
 968   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
 969                                                         "ATS_EXEC_INTERVAL",
 970                                                         &i_exec))
 971     mlp->exec_interval = i_exec;
 972   else
 973     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
 974
 975   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
 976   mlp->max_iterations = max_iterations;
 977   mlp->max_exec_duration = max_duration;
 978
 979   /* Redirect GLPK output to GNUnet logging */
 980   glp_error_hook((void *) mlp, &mlp_term_hook);
 981
 982   /* Init LP solving parameters */
 983   glp_init_smcp(&mlp->control_param_lp);
 984 #if DEBUG_ATS
 985   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
 986 #else
 987   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
 988 #endif
 989   mlp->control_param_lp.it_lim = max_iterations;
 990   mlp->control_param_lp.tm_lim = max_duration.rel_value;
 991
 992   /* Init MLP solving parameters */
 993   glp_init_iocp(&mlp->control_param_mlp);
 994 #if DEBUG_ATS
 995   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
 996 #else
 997   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
 998 #endif
 999   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1000
1001   mlp->last_execution = GNUNET_TIME_absolute_get_forever();
1002
1003   mlp->co_D = D;
1004   mlp->co_R = R;
1005   mlp->co_U = U;
1006   mlp->b_min = b_min;
1007   mlp->n_min = n_min;
1008   mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1009
1010   return mlp;
1011 }
1012
1013 /**
1014  * Updates a single address in the MLP problem
1015  *
1016  * If the address did not exist before in the problem:
1017  * The MLP problem has to be recreated and the problem has to be resolved
1018  *
1019  * Otherwise the addresses' values can be updated and the existing base can
1020  * be reused
1021  *
1022  * @param mlp the MLP Handle
1023  * @param addresses the address hashmap
1024  *        the address has to be already removed from the hashmap
1025  * @param address the address to update
1026  */
1027 void
1028 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1029 {
1030   int new;
1031   struct MLP_information *mlpi;
1032   int c;
1033
1034   GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
1035
1036   /* We add a new address */
1037   if (address->mlp_information == NULL)
1038     new = GNUNET_YES;
1039   else
1040     new = GNUNET_NO;
1041
1042   /* Do the update */
1043   if (new == GNUNET_YES)
1044   {
1045     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1046     address->mlp_information = mlpi;
1047     mlp->addr_in_problem ++;
1048
1049     /* Check for and add peer */
1050     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1051     if (peer == NULL)
1052     {
1053 #if DEBUG_ATS
1054       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n", GNUNET_i2s (&address->peer));
1055 #endif
1056       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1057       peer->head = NULL;
1058       peer->tail = NULL;
1059
1060       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1061       {
1062         peer->f_q[c] = 1.0;
1063       }
1064
1065       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1066       GNUNET_assert(address->prev == NULL);
1067       GNUNET_assert(address->next == NULL);
1068       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1069       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1070       mlp->c_p ++;
1071     }
1072     else
1073     {
1074 #if DEBUG_ATS
1075       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n", GNUNET_i2s (&address->peer));
1076 #endif
1077       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1078     }
1079   }
1080   else
1081   {
1082 #if DEBUG_ATS
1083     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n", GNUNET_i2s (&address->peer));
1084 #endif
1085   }
1086
1087   /* Recalculate */
1088   if (new == GNUNET_YES)
1089   {
1090     mlp_delete_problem (mlp);
1091     mlp_create_problem (mlp, addresses);
1092     mlp->presolver_required = GNUNET_YES;
1093   }
1094   mlp_solve_problem (mlp);
1095 }
1096
1097 /**
1098  * Deletes a single address in the MLP problem
1099  *
1100  * The MLP problem has to be recreated and the problem has to be resolved
1101  *
1102  * @param mlp the MLP Handle
1103  * @param addresses the address hashmap
1104  *        the address has to be already removed from the hashmap
1105  * @param address the address to delete
1106  */
1107 void
1108 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1109 {
1110   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1111
1112   /* Free resources */
1113   if (address->mlp_information != NULL)
1114   {
1115     GNUNET_free (address->mlp_information);
1116     address->mlp_information = NULL;
1117
1118     mlp->addr_in_problem --;
1119   }
1120
1121   /* Remove from peer list */
1122   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1123   GNUNET_assert (head != NULL);
1124 #if DEBUG_ATS
1125   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1126 #endif
1127   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1128   if ((head->head == NULL) && (head->tail == NULL))
1129   {
1130     /* No address for peer left, remove peer */
1131 #if DEBUG_ATS
1132     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1133 #endif
1134     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1135     GNUNET_free (head);
1136     mlp->c_p --;
1137   }
1138
1139   /* Update problem */
1140   mlp_delete_problem (mlp);
1141   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1142   {
1143 #if DEBUG_ATS
1144     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "mlp_create_problem %i\n",__LINE__);
1145 #endif
1146     mlp_create_problem (mlp, addresses);
1147
1148     /* Recalculate */
1149     mlp->presolver_required = GNUNET_YES;
1150     mlp_solve_problem (mlp);
1151   }
1152 }
1153
1154 /**
1155  * Changes the preferences for a peer in the MLP problem
1156  *
1157  * @param mlp the MLP Handle
1158  * @param peer the peer
1159  * @param kind the kind to change the preference
1160  * @param float the score
1161  */
1162 void
1163 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
1164                                    const struct GNUNET_PeerIdentity *peer,
1165                                    enum GNUNET_ATS_PreferenceKind kind,
1166                                    float score)
1167 {
1168   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1169
1170   struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1171   p = p;
1172   /* Here we have to do the matching */
1173 }
1174
1175 /**
1176  * Shutdown the MLP problem solving component
1177  * @param mlp the MLP handle
1178  */
1179 void
1180 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
1181 {
1182   struct ATS_Peer * peer;
1183   struct ATS_Peer * tmp;
1184
1185   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1186   {
1187     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1188     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1189   }
1190
1191   /* clean up peer list */
1192   if (mlp != NULL)
1193   {
1194     peer = mlp->peer_head;
1195     while (peer != NULL)
1196     {
1197       GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1198       tmp = peer->next;
1199       GNUNET_free (peer);
1200       peer = tmp;
1201     }
1202   }
1203   mlp_delete_problem (mlp);
1204
1205   /* Clean up GLPK environment */
1206   glp_free_env();
1207
1208   GNUNET_free (mlp);
1209 }
1210
1211
1212 /* end of gnunet-service-ats_addresses_mlp.c */