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