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