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_NO
  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: |n_addresses| + |quality properties|
 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   /* last +1 caused by glpk index starting with one */
 371   int pi = ((7 * n_addresses) + (4 * n_addresses +  mlp->m_q + mlp->c_p + 2) + 1);
 372   mlp->cm_size = pi;
 373   mlp->ci = 1;
 374
 375   /* row index */
 376   int *ia = GNUNET_malloc (pi * sizeof (int));
 377   mlp->ia = ia;
 378
 379   /* column index */
 380   int *ja = GNUNET_malloc (pi * sizeof (int));
 381   mlp->ja = ja;
 382
 383   /* coefficient */
 384   double *ar= GNUNET_malloc (pi * sizeof (double));
 385   mlp->ar = ar;
 386
 387   /* Adding constraint rows
 388    * This constraints are kind of "for all addresses"
 389    * Feasibility constraints:
 390    *
 391    * c 1) bandwidth capping
 392    * c 3) minimum bandwidth
 393    * c 4) minimum number of connections
 394    * c 6) maximize diversity
 395    */
 396
 397   int min = mlp->n_min;
 398   if (mlp->n_min > mlp->c_p)
 399     min = mlp->c_p;
 400
 401   mlp->r_c4 = glp_add_rows (mlp->prob, 1);
 402   glp_set_row_name (mlp->prob, mlp->r_c4, "c4");
 403   glp_set_row_bnds (mlp->prob, mlp->r_c4, GLP_LO, min, min);
 404
 405   /* Add row for c6) */
 406
 407   mlp->r_c6 = glp_add_rows (mlp->prob, 1);
 408   /* Set type type to fix */
 409   glp_set_row_bnds (mlp->prob, mlp->r_c6, GLP_FX, 0.0, 0.0);
 410   /* Setting -D */
 411   ia[mlp->ci] = mlp->r_c6 ;
 412   ja[mlp->ci] = mlp->c_d;
 413   ar[mlp->ci] = -1;
 414   mlp->ci++;
 415
 416   GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
 417
 418   /* Adding constraint rows
 419    * This constraints are kind of "for all peers"
 420    * Feasibility constraints:
 421    *
 422    * c 2) 1 address per peer
 423    * sum (n_p1_1 + ... + n_p1_n) = 1
 424    *
 425    * c 8) utilization
 426    * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
 427    *
 428    * c 9) relativity
 429    * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
 430    * */
 431
 432   /* Adding rows for c 8) */
 433   mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p);
 434   glp_set_row_name (mlp->prob, mlp->r_c8, "c8");
 435   /* Set row bound == 0 */
 436   glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0);
 437   /* -u */
 438   ia[mlp->ci] = mlp->r_c8;
 439   ja[mlp->ci] = mlp->c_u;
 440   ar[mlp->ci] = -1;
 441   mlp->ci++;
 442
 443   struct ATS_Peer * peer = mlp->peer_head;
 444   while (peer != NULL)
 445   {
 446     struct ATS_Address *addr = peer->head;
 447     struct MLP_information *mlpi = NULL;
 448
 449     /* Adding rows for c 2) */
 450     peer->r_c2 = glp_add_rows (mlp->prob, 1);
 451     GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
 452     glp_set_row_name (mlp->prob, peer->r_c2, name);
 453     GNUNET_free (name);
 454     /* Set row bound == 1 */
 455     glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
 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   /* c 7) For all quality metrics */
 496
 497   for (c = 0; c < mlp->m_q; c++)
 498   {
 499     struct ATS_Peer *p = mlp->peer_head;
 500     struct ATS_Address *addr = p->head;
 501     struct MLP_information * mlpi;
 502     double value = 1.0;
 503
 504     while (p != NULL)
 505     {
 506       /* Adding rows for c 7) */
 507       mlp->r_q[c] = glp_add_rows (mlp->prob, 1);
 508       GNUNET_asprintf(&name, "c7_q%i_atsi_%i", c, mlp->q[c]);
 509       glp_set_row_name (mlp->prob, mlp->r_q[c], name);
 510       GNUNET_free (name);
 511       /* Set row bound == 0 */
 512       glp_set_row_bnds (mlp->prob, mlp->r_q[c], GLP_LO, 0.0, 0.0);
 513
 514       /* Set -q_m */
 515       ia[mlp->ci] = mlp->r_q[c];
 516       ja[mlp->ci] = mlp->c_q[c];
 517       ar[mlp->ci] = -1;
 518       mlp->ci++;
 519
 520       while (addr != NULL)
 521       {
 522         mlpi = addr->mlp_information;
 523         ia[mlp->ci] = mlp->r_q[c];
 524         ja[mlp->ci] = mlpi->c_b;
 525         ar[mlp->ci] = p->f * value;
 526         mlp->ci++;
 527
 528         addr = addr->next;
 529       }
 530       p = p->next;
 531     }
 532   }
 533 }
 534
 535
 536 /**
 537  * Add columns for all addresses
 538  *
 539  * @param cls GAS_MLP_Handle
 540  * @param key Hashcode
 541  * @param value ATS_Address
 542  *
 543  * @return GNUNET_OK to continue
 544  */
 545 static int
 546 create_columns_it (void *cls, const GNUNET_HashCode * key, void *value)
 547 {
 548   struct GAS_MLP_Handle *mlp = cls;
 549   struct ATS_Address *address = value;
 550   struct MLP_information *mlpi;
 551   unsigned int col;
 552   char *name;
 553
 554   GNUNET_assert (address->mlp_information != NULL);
 555   mlpi = address->mlp_information;
 556
 557   /* Add bandwidth column */
 558   col = glp_add_cols (mlp->prob, 2);
 559   mlpi->c_b = col;
 560   mlpi->c_n = col + 1;
 561
 562   GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 563   glp_set_col_name (mlp->prob, mlpi->c_b , name);
 564   GNUNET_free (name);
 565   /* Lower bound == 0 */
 566   glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
 567   /* Continuous value*/
 568   glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
 569   /* Objective function coefficient == 0 */
 570   glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
 571
 572
 573   /* Add usage column */
 574   GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 575   glp_set_col_name (mlp->prob, mlpi->c_n, name);
 576   GNUNET_free (name);
 577   /* Limit value : 0 <= value <= 1 */
 578   glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
 579   /* Integer value*/
 580   glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
 581   /* Objective function coefficient == 0 */
 582   glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
 583
 584   return GNUNET_OK;
 585 }
 586
 587
 588
 589 /**
 590  * Create the MLP problem
 591  *
 592  * @param mlp the MLP handle
 593  * @return GNUNET_OK or GNUNET_SYSERR
 594  */
 595 static int
 596 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 597 {
 598   int res = GNUNET_OK;
 599   int col;
 600   int c;
 601   char *name;
 602
 603   GNUNET_assert (mlp->prob == NULL);
 604
 605   /* create the glpk problem */
 606   mlp->prob = glp_create_prob ();
 607
 608   /* Set a problem name */
 609   glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
 610
 611   /* Set optimization direction to maximize */
 612   glp_set_obj_dir (mlp->prob, GLP_MAX);
 613
 614   /* Adding invariant columns */
 615
 616   /* Diversity d column  */
 617
 618   col = glp_add_cols (mlp->prob, 1);
 619   mlp->c_d = col;
 620   /* Column name */
 621   glp_set_col_name (mlp->prob, col, "d");
 622   /* Column objective function coefficient */
 623   glp_set_obj_coef (mlp->prob, col, mlp->co_D);
 624   /* Column lower bound = 0.0 */
 625   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 626
 627   /* Utilization u column  */
 628
 629   col = glp_add_cols (mlp->prob, 1);
 630   mlp->c_u = col;
 631   /* Column name */
 632   glp_set_col_name (mlp->prob, col, "u");
 633   /* Column objective function coefficient */
 634   glp_set_obj_coef (mlp->prob, col, mlp->co_U);
 635   /* Column lower bound = 0.0 */
 636   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 637
 638   /* Relativity r column  */
 639   col = glp_add_cols (mlp->prob, 1);
 640   mlp->c_r = col;
 641   /* Column name */
 642   glp_set_col_name (mlp->prob, col, "r");
 643   /* Column objective function coefficient */
 644   glp_set_obj_coef (mlp->prob, col, mlp->co_R);
 645   /* Column lower bound = 0.0 */
 646   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 647
 648   /* Quality metric columns */
 649   col = glp_add_cols(mlp->prob, mlp->m_q);
 650   for (c = 0; c < mlp->m_q; c++)
 651   {
 652     mlp->c_q[c] = col + c;
 653     GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
 654     glp_set_col_name (mlp->prob, col + c, name);
 655     /* Column lower bound = 0.0 */
 656     glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
 657     GNUNET_free (name);
 658     /* Coefficient == Qm */
 659     glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
 660   }
 661
 662   /* Add columns for addresses */
 663   GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
 664
 665   /* Add constraints */
 666   mlp_add_constraints_all_addresses (mlp, addresses);
 667
 668   /* Load the matrix */
 669   glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
 670
 671   return res;
 672 }
 673
 674 /**
 675  * Solves the LP problem
 676  *
 677  * @param mlp the MLP Handle
 678  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 679  */
 680 static int
 681 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 682 {
 683   int res;
 684   struct GNUNET_TIME_Relative duration;
 685   struct GNUNET_TIME_Absolute end;
 686   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 687
 688   /* LP presolver?
 689    * Presolver is required if the problem was modified and an existing
 690    * valid basis is now invalid */
 691   if (mlp->presolver_required == GNUNET_YES)
 692     mlp->control_param_lp.presolve = GLP_ON;
 693   else
 694     mlp->control_param_lp.presolve = GLP_OFF;
 695
 696   /* Solve LP problem to have initial valid solution */
 697 lp_solv:
 698   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
 699   if (res == 0)
 700   {
 701     /* The LP problem instance has been successfully solved. */
 702   }
 703   else if (res == GLP_EITLIM)
 704   {
 705     /* simplex iteration limit has been exceeded. */
 706     // TODO Increase iteration limit?
 707   }
 708   else if (res == GLP_ETMLIM)
 709   {
 710     /* Time limit has been exceeded.  */
 711     // TODO Increase time limit?
 712   }
 713   else
 714   {
 715     /* Problem was ill-defined, retry with presolver */
 716     if (mlp->presolver_required == GNUNET_NO)
 717     {
 718       mlp->presolver_required = GNUNET_YES;
 719       goto lp_solv;
 720     }
 721     else
 722     {
 723       /* Problem was ill-defined, no way to handle that */
 724       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 725           "ats-mlp",
 726           "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
 727       return GNUNET_SYSERR;
 728     }
 729   }
 730
 731   end = GNUNET_TIME_absolute_get ();
 732   duration = GNUNET_TIME_absolute_get_difference (start, end);
 733   mlp->lp_solved++;
 734   mlp->lp_total_duration =+ duration.rel_value;
 735
 736   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 737   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
 738   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
 739                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 740
 741
 742   /* Analyze problem status  */
 743   res = glp_get_status (mlp->prob);
 744   switch (res) {
 745     /* solution is optimal */
 746     case GLP_OPT:
 747     /* solution is feasible */
 748     case GLP_FEAS:
 749       break;
 750
 751     /* Problem was ill-defined, no way to handle that */
 752     default:
 753       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 754           "ats-mlp",
 755           "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
 756       return GNUNET_SYSERR;
 757       break;
 758   }
 759
 760   /* solved sucessfully, no presolver required next time */
 761   mlp->presolver_required = GNUNET_NO;
 762
 763   return GNUNET_OK;
 764 }
 765
 766
 767 /**
 768  * Solves the MLP problem
 769  *
 770  * @param mlp the MLP Handle
 771  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 772  */
 773 int
 774 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 775 {
 776   int res;
 777   struct GNUNET_TIME_Relative duration;
 778   struct GNUNET_TIME_Absolute end;
 779   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 780
 781   /* solve MLP problem */
 782   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 783
 784   if (res == 0)
 785   {
 786     /* The MLP problem instance has been successfully solved. */
 787   }
 788   else if (res == GLP_EITLIM)
 789   {
 790     /* simplex iteration limit has been exceeded. */
 791     // TODO Increase iteration limit?
 792   }
 793   else if (res == GLP_ETMLIM)
 794   {
 795     /* Time limit has been exceeded.  */
 796     // TODO Increase time limit?
 797   }
 798   else
 799   {
 800     /* Problem was ill-defined, no way to handle that */
 801     GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 802         "ats-mlp",
 803         "Solving MLP problem failed:  %s\n", mlp_solve_to_string(res));
 804     return GNUNET_SYSERR;
 805   }
 806
 807   end = GNUNET_TIME_absolute_get ();
 808   duration = GNUNET_TIME_absolute_get_difference (start, end);
 809   mlp->mlp_solved++;
 810   mlp->mlp_total_duration =+ duration.rel_value;
 811
 812   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 813   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
 814   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
 815                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 816
 817   /* Analyze problem status  */
 818   res = glp_mip_status(mlp->prob);
 819   switch (res) {
 820     /* solution is optimal */
 821     case GLP_OPT:
 822     /* solution is feasible */
 823     case GLP_FEAS:
 824       break;
 825
 826     /* Problem was ill-defined, no way to handle that */
 827     default:
 828       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 829           "ats-mlp",
 830           "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
 831       return GNUNET_SYSERR;
 832       break;
 833   }
 834
 835   return GNUNET_OK;
 836 }
 837
 838 int mlp_solve_problem (struct GAS_MLP_Handle *mlp);
 839
 840 static void
 841 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 842 {
 843   struct GAS_MLP_Handle *mlp = cls;
 844
 845   mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 846
 847   if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 848     return;
 849
 850 #if DEBUG_ATS
 851   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
 852 #endif
 853   if (mlp->addr_in_problem != 0)
 854     mlp_solve_problem(mlp);
 855 }
 856
 857
 858 /**
 859  * Solves the MLP problem
 860  *
 861  * @param mlp the MLP Handle
 862  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 863  */
 864 int
 865 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
 866 {
 867   int res;
 868   mlp->last_execution = GNUNET_TIME_absolute_get ();
 869 #if DEBUG_ATS
 870   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solving\n");
 871 #endif
 872
 873 #if WRITE_MLP
 874   char * name;
 875   static int i;
 876   i++;
 877   GNUNET_asprintf(&name, "problem_%i", i);
 878   glp_write_lp (mlp->prob, 0, name);
 879   GNUNET_free (name);
 880 # endif
 881
 882   res = mlp_solve_lp_problem (mlp);
 883
 884 #if WRITE_MLP
 885   GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
 886   glp_print_sol (mlp->prob,  name);
 887   GNUNET_free (name);
 888 # endif
 889
 890   if (res != GNUNET_OK)
 891   {
 892 #if DEBUG_ATS
 893   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "LP Problem solving failed\n");
 894 #endif
 895     return GNUNET_SYSERR;
 896   }
 897
 898   res = mlp_solve_mlp_problem (mlp);
 899
 900 #if WRITE_MLP
 901   GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
 902   glp_print_mip (mlp->prob, name);
 903   GNUNET_free (name);
 904 # endif
 905   if (res != GNUNET_OK)
 906   {
 907 #if DEBUG_ATS
 908   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MLP Problem solving failed\n");
 909 #endif
 910     return GNUNET_SYSERR;
 911   }
 912
 913 #if DEBUG_ATS
 914   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved\n");
 915 #endif
 916
 917   /* Process result */
 918
 919   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
 920   {
 921     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
 922     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 923   }
 924   mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
 925   return res;
 926 }
 927
 928 /**
 929  * Init the MLP problem solving component
 930  *
 931  * @param stats the GNUNET_STATISTICS handle
 932  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 933  * @param max_iterations maximum time limit for the LP/MLP Solver
 934  * @return struct GAS_MLP_Handle * on success, NULL on fail
 935  */
 936 struct GAS_MLP_Handle *
 937 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 938               const struct GNUNET_STATISTICS_Handle *stats,
 939               struct GNUNET_TIME_Relative max_duration,
 940               unsigned int max_iterations)
 941 {
 942   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
 943
 944   double D;
 945   double R;
 946   double U;
 947   long long unsigned int tmp;
 948   unsigned int b_min;
 949   unsigned int n_min;
 950   struct GNUNET_TIME_Relative i_exec;
 951
 952   /* Init GLPK environment */
 953   GNUNET_assert (glp_init_env() == 0);
 954
 955   /* Create initial MLP problem */
 956   mlp->prob = glp_create_prob();
 957   GNUNET_assert (mlp->prob != NULL);
 958
 959   /* Get diversity coefficient from configuration */
 960   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 961                                                       "COEFFICIENT_D",
 962                                                       &tmp))
 963     D = (double) tmp / 100;
 964   else
 965     D = 1.0;
 966
 967   /* Get proportionality coefficient from configuration */
 968   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 969                                                       "COEFFICIENT_R",
 970                                                       &tmp))
 971     R = (double) tmp / 100;
 972   else
 973     R = 1.0;
 974
 975   /* Get utilization coefficient from configuration */
 976   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 977                                                       "COEFFICIENT_U",
 978                                                       &tmp))
 979     U = (double) tmp / 100;
 980   else
 981     U = 1.0;
 982
 983   /* Get quality metric coefficients from configuration */
 984   int i_delay = -1;
 985   int i_distance = -1;
 986   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
 987   int c;
 988   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 989   {
 990     /* initialize quality coefficients with default value 1.0 */
 991     mlp->co_Q[c] = 1.0;
 992
 993     mlp->q[c] = q[c];
 994     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
 995       i_delay = c;
 996     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
 997       i_distance = c;
 998   }
 999
1000   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1001                                                       "COEFFICIENT_QUALITY_DELAY",
1002                                                       &tmp)))
1003
1004     mlp->co_Q[i_delay] = (double) tmp / 100;
1005   else
1006     mlp->co_Q[i_delay] = 1.0;
1007
1008   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1009                                                       "COEFFICIENT_QUALITY_DISTANCE",
1010                                                       &tmp)))
1011     mlp->co_Q[i_distance] = (double) tmp / 100;
1012   else
1013     mlp->co_Q[i_distance] = 1.0;
1014
1015   /* Get minimum bandwidth per used address from configuration */
1016   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1017                                                       "MIN_BANDWIDTH",
1018                                                       &tmp))
1019     b_min = tmp;
1020   else
1021     b_min = 64000;
1022
1023   /* Get minimum number of connections from configuration */
1024   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1025                                                       "MIN_CONNECTIONS",
1026                                                       &tmp))
1027     n_min = tmp;
1028   else
1029     n_min = 4;
1030
1031   /* Get minimum number of connections from configuration */
1032   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1033                                                         "ATS_EXEC_INTERVAL",
1034                                                         &i_exec))
1035     mlp->exec_interval = i_exec;
1036   else
1037     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1038
1039   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1040   mlp->max_iterations = max_iterations;
1041   mlp->max_exec_duration = max_duration;
1042
1043   /* Redirect GLPK output to GNUnet logging */
1044   glp_error_hook((void *) mlp, &mlp_term_hook);
1045
1046   /* Init LP solving parameters */
1047   glp_init_smcp(&mlp->control_param_lp);
1048 #if VERBOSE_GLPK
1049   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1050 #else
1051   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1052 #endif
1053   mlp->control_param_lp.it_lim = max_iterations;
1054   mlp->control_param_lp.tm_lim = max_duration.rel_value;
1055
1056   /* Init MLP solving parameters */
1057   glp_init_iocp(&mlp->control_param_mlp);
1058 #if VERBOSE_GLPK
1059   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1060 #else
1061   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1062 #endif
1063   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1064
1065   mlp->last_execution = GNUNET_TIME_absolute_get_forever();
1066
1067
1068   mlp->BIG_M = (double) UINT32_MAX;
1069   mlp->co_D = D;
1070   mlp->co_R = R;
1071   mlp->co_U = U;
1072   mlp->b_min = b_min;
1073   mlp->n_min = n_min;
1074   mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1075
1076   return mlp;
1077 }
1078
1079 /**
1080  * Updates a single address in the MLP problem
1081  *
1082  * If the address did not exist before in the problem:
1083  * The MLP problem has to be recreated and the problem has to be resolved
1084  *
1085  * Otherwise the addresses' values can be updated and the existing base can
1086  * be reused
1087  *
1088  * @param mlp the MLP Handle
1089  * @param addresses the address hashmap
1090  *        the address has to be already removed from the hashmap
1091  * @param address the address to update
1092  */
1093 void
1094 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1095 {
1096   int new;
1097   struct MLP_information *mlpi;
1098   int c;
1099
1100   GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
1101
1102   /* We add a new address */
1103   if (address->mlp_information == NULL)
1104     new = GNUNET_YES;
1105   else
1106     new = GNUNET_NO;
1107
1108   /* Do the update */
1109   if (new == GNUNET_YES)
1110   {
1111     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1112     address->mlp_information = mlpi;
1113     mlp->addr_in_problem ++;
1114
1115     /* Check for and add peer */
1116     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1117     if (peer == NULL)
1118     {
1119 #if DEBUG_ATS
1120       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n", GNUNET_i2s (&address->peer));
1121 #endif
1122       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1123       peer->head = NULL;
1124       peer->tail = NULL;
1125
1126       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1127       {
1128         peer->f_q[c] = 1.0;
1129       }
1130       peer->f = 1.0;
1131
1132       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1133       GNUNET_assert(address->prev == NULL);
1134       GNUNET_assert(address->next == NULL);
1135       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1136       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1137       mlp->c_p ++;
1138     }
1139     else
1140     {
1141 #if DEBUG_ATS
1142       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n", GNUNET_i2s (&address->peer));
1143 #endif
1144       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1145     }
1146   }
1147   else
1148   {
1149 #if DEBUG_ATS
1150     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n", GNUNET_i2s (&address->peer));
1151 #endif
1152     mlpi = address->mlp_information;
1153
1154   }
1155
1156   /* Recalculate */
1157   if (new == GNUNET_YES)
1158   {
1159     mlp_delete_problem (mlp);
1160     mlp_create_problem (mlp, addresses);
1161     mlp->presolver_required = GNUNET_YES;
1162   }
1163   mlp_solve_problem (mlp);
1164 }
1165
1166 /**
1167  * Deletes a single address in the MLP problem
1168  *
1169  * The MLP problem has to be recreated and the problem has to be resolved
1170  *
1171  * @param mlp the MLP Handle
1172  * @param addresses the address hashmap
1173  *        the address has to be already removed from the hashmap
1174  * @param address the address to delete
1175  */
1176 void
1177 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1178 {
1179   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1180
1181   /* Free resources */
1182   if (address->mlp_information != NULL)
1183   {
1184     GNUNET_free (address->mlp_information);
1185     address->mlp_information = NULL;
1186
1187     mlp->addr_in_problem --;
1188   }
1189
1190   /* Remove from peer list */
1191   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1192   GNUNET_assert (head != NULL);
1193 #if DEBUG_ATS
1194   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1195 #endif
1196   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1197   if ((head->head == NULL) && (head->tail == NULL))
1198   {
1199     /* No address for peer left, remove peer */
1200 #if DEBUG_ATS
1201     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1202 #endif
1203     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1204     GNUNET_free (head);
1205     mlp->c_p --;
1206   }
1207
1208   /* Update problem */
1209   mlp_delete_problem (mlp);
1210   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1211   {
1212     mlp_create_problem (mlp, addresses);
1213
1214     /* Recalculate */
1215     mlp->presolver_required = GNUNET_YES;
1216     mlp_solve_problem (mlp);
1217   }
1218 }
1219
1220 /**
1221  * Changes the preferences for a peer in the MLP problem
1222  *
1223  * @param mlp the MLP Handle
1224  * @param peer the peer
1225  * @param kind the kind to change the preference
1226  * @param float the score
1227  */
1228 void
1229 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
1230                                    const struct GNUNET_PeerIdentity *peer,
1231                                    enum GNUNET_ATS_PreferenceKind kind,
1232                                    float score)
1233 {
1234   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1235
1236   struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1237   p = p;
1238   /* Here we have to do the matching */
1239 }
1240
1241 /**
1242  * Shutdown the MLP problem solving component
1243  * @param mlp the MLP handle
1244  */
1245 void
1246 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
1247 {
1248   struct ATS_Peer * peer;
1249   struct ATS_Peer * tmp;
1250
1251   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1252   {
1253     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1254     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1255   }
1256
1257   /* clean up peer list */
1258   if (mlp != NULL)
1259   {
1260     peer = mlp->peer_head;
1261     while (peer != NULL)
1262     {
1263       GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1264       tmp = peer->next;
1265       GNUNET_free (peer);
1266       peer = tmp;
1267     }
1268   }
1269   mlp_delete_problem (mlp);
1270
1271   /* Clean up GLPK environment */
1272   glp_free_env();
1273
1274   GNUNET_free (mlp);
1275 }
1276
1277
1278 /* end of gnunet-service-ats_addresses_mlp.c */