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