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