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
  36 /**
  37  * Intercept GLPK terminal output
  38  *
  39  */
  40
  41 static int
  42 mlp_term_hook (void *info, const char *s)
  43 {
  44   /* Not needed atm struct MLP_information *mlp = info; */
  45   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s", s);
  46   /* 0: glpk prints output on terminal, != surpress output */
  47   return 1;
  48 }
  49
  50 /**
  51  * Create the MLP problem
  52  *
  53  * @param mlp the MLP handle
  54  * @return GNUNET_OK or GNUNET_SYSERR
  55  */
  56
  57 static int
  58 mlp_create_problem (struct GAS_MLP_Handle *mlp)
  59 {
  60   int res = GNUNET_OK;
  61   int col;
  62   int c;
  63   char *name;
  64
  65   /* Set a problem name */
  66   glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution");
  67
  68   /* Set optimization direction to maximize */
  69   glp_set_obj_dir (mlp->prob, GLP_MAX);
  70
  71   /* Adding invariant columns */
  72
  73   /* Diversity d column  */
  74
  75   col = glp_add_cols (mlp->prob, 1);
  76   mlp->c_d = col;
  77   /* Column name */
  78   glp_set_col_name (mlp->prob, col, "d");
  79   /* Column objective function coefficient */
  80   glp_set_obj_coef (mlp->prob, col, mlp->co_D);
  81   /* Column lower bound = 0.0 */
  82   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
  83
  84   /* Utilization u column  */
  85
  86   col = glp_add_cols (mlp->prob, 1);
  87   mlp->c_u = col;
  88   /* Column name */
  89   glp_set_col_name (mlp->prob, col, "u");
  90   /* Column objective function coefficient */
  91   glp_set_obj_coef (mlp->prob, col, mlp->co_U);
  92   /* Column lower bound = 0.0 */
  93   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
  94
  95   /* Relativity r column  */
  96   col = glp_add_cols (mlp->prob, 1);
  97   mlp->c_r = col;
  98   /* Column name */
  99   glp_set_col_name (mlp->prob, col, "r");
 100   /* Column objective function coefficient */
 101   glp_set_obj_coef (mlp->prob, col, mlp->co_R);
 102   /* Column lower bound = 0.0 */
 103   glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
 104
 105   /* Quality metric columns */
 106   col = glp_add_cols(mlp->prob, mlp->m);
 107   for (c = 0; c < mlp->m; c++)
 108   {
 109     mlp->c_q[c] = col + c;
 110     GNUNET_asprintf (&name, "q_%u", mlp->q[c]);
 111     glp_set_col_name (mlp->prob, col + c, name);
 112     /* Column lower bound = 0.0 */
 113     glp_set_col_bnds (mlp->prob, col + c, GLP_LO, 0.0, 0.0);
 114     GNUNET_free (name);
 115     /* Coefficient == Qm */
 116     glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
 117   }
 118
 119   return res;
 120 }
 121
 122 /**
 123  * Solves the LP problem
 124  *
 125  * @param mlp the MLP Handle
 126  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 127  */
 128 static int
 129 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 130 {
 131   int res;
 132   struct GNUNET_TIME_Relative duration;
 133   struct GNUNET_TIME_Absolute end;
 134   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 135
 136   /* LP presolver?
 137    * Presolver is required if the problem was modified and an existing
 138    * valid basis is now invalid */
 139   if (mlp->presolver_required == GNUNET_YES)
 140     mlp->control_param_lp.presolve = GLP_ON;
 141   else
 142     mlp->control_param_lp.presolve = GLP_OFF;
 143
 144   /* Solve LP problem to have initial valid solution */
 145 lp_solv:
 146   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
 147   if (res == 0)
 148   {
 149     /* The LP problem instance has been successfully solved. */
 150   }
 151   else if (res == GLP_EITLIM)
 152   {
 153     /* simplex iteration limit has been exceeded. */
 154     // TODO Increase iteration limit?
 155   }
 156   else if (res == GLP_ETMLIM)
 157   {
 158     /* Time limit has been exceeded.  */
 159     // TODO Increase time limit?
 160   }
 161   else
 162   {
 163     /* Problem was ill-defined, retry with presolver */
 164     if (mlp->presolver_required == GNUNET_NO)
 165     {
 166       mlp->presolver_required = GNUNET_YES;
 167       goto lp_solv;
 168     }
 169     else
 170     {
 171       /* Problem was ill-defined, no way to handle that */
 172       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 173           "ats-mlp",
 174           "Solving LP problem failed: glp_simplex error 0x%X\n", res);
 175       return GNUNET_SYSERR;
 176     }
 177   }
 178
 179   end = GNUNET_TIME_absolute_get ();
 180   duration = GNUNET_TIME_absolute_get_difference (start, end);
 181   mlp->lp_solved++;
 182   mlp->lp_total_duration =+ duration.rel_value;
 183
 184   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 185   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time", duration.rel_value, GNUNET_NO);
 186   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average",
 187                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 188
 189
 190   /* Analyze problem status  */
 191   res = glp_get_status (mlp->prob);
 192   switch (res) {
 193     /* solution is optimal */
 194     case GLP_OPT:
 195     /* solution is feasible */
 196     case GLP_FEAS:
 197       break;
 198
 199     /* Problem was ill-defined, no way to handle that */
 200     default:
 201       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 202           "ats-mlp",
 203           "Solving LP problem failed, no solution: glp_get_status 0x%X\n", res);
 204       return GNUNET_SYSERR;
 205       break;
 206   }
 207
 208   /* solved sucessfully, no presolver required next time */
 209   mlp->presolver_required = GNUNET_NO;
 210
 211   return GNUNET_OK;
 212 }
 213
 214
 215 /**
 216  * Solves the MLP problem
 217  *
 218  * @param mlp the MLP Handle
 219  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 220  */
 221 int
 222 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 223 {
 224   int res;
 225   struct GNUNET_TIME_Relative duration;
 226   struct GNUNET_TIME_Absolute end;
 227   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 228
 229   /* solve MLP problem */
 230   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 231
 232   if (res == 0)
 233   {
 234     /* The MLP problem instance has been successfully solved. */
 235   }
 236   else if (res == GLP_EITLIM)
 237   {
 238     /* simplex iteration limit has been exceeded. */
 239     // TODO Increase iteration limit?
 240   }
 241   else if (res == GLP_ETMLIM)
 242   {
 243     /* Time limit has been exceeded.  */
 244     // TODO Increase time limit?
 245   }
 246   else
 247   {
 248     /* Problem was ill-defined, no way to handle that */
 249     GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 250         "ats-mlp",
 251         "Solving MLP problem failed: glp_intopt error 0x%X\n", res);
 252     return GNUNET_SYSERR;
 253   }
 254
 255   end = GNUNET_TIME_absolute_get ();
 256   duration = GNUNET_TIME_absolute_get_difference (start, end);
 257   mlp->mlp_solved++;
 258   mlp->mlp_total_duration =+ duration.rel_value;
 259
 260   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 261   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time", duration.rel_value, GNUNET_NO);
 262   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average",
 263                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 264
 265   /* Analyze problem status  */
 266   res = glp_mip_status(mlp->prob);
 267   switch (res) {
 268     /* solution is optimal */
 269     case GLP_OPT:
 270     /* solution is feasible */
 271     case GLP_FEAS:
 272       break;
 273
 274     /* Problem was ill-defined, no way to handle that */
 275     default:
 276       GNUNET_log_from (GNUNET_ERROR_TYPE_ERROR,
 277           "ats-mlp",
 278           "Solving MLP problem failed, no solution: glp_mip_status 0x%X\n", res);
 279       return GNUNET_SYSERR;
 280       break;
 281   }
 282
 283   return GNUNET_OK;
 284 }
 285
 286 /**
 287  * Solves the MLP problem
 288  *
 289  * @param mlp the MLP Handle
 290  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 291  */
 292 int
 293 mlp_solve_problem (struct GAS_MLP_Handle *mlp)
 294 {
 295   int res;
 296   mlp->last_execution = GNUNET_TIME_absolute_get ();
 297   res = mlp_solve_lp_problem (mlp);
 298   if (res == GNUNET_OK)
 299     res = mlp_solve_mlp_problem (mlp);
 300   return res;
 301 }
 302
 303 /**
 304  * Init the MLP problem solving component
 305  *
 306  * @param stats the GNUNET_STATISTICS handle
 307  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 308  * @param max_iterations maximum time limit for the LP/MLP Solver
 309  * @return struct GAS_MLP_Handle * on success, NULL on fail
 310  */
 311 struct GAS_MLP_Handle *
 312 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 313               const struct GNUNET_STATISTICS_Handle *stats,
 314               struct GNUNET_TIME_Relative max_duration,
 315               unsigned int max_iterations)
 316 {
 317   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
 318
 319   double D;
 320   double R;
 321   double U;
 322   long long unsigned int tmp;
 323   unsigned int b_min;
 324   unsigned int n_min;
 325
 326   /* Init GLPK environment */
 327   GNUNET_assert (glp_init_env() == 0);
 328
 329   /* Create initial MLP problem */
 330   mlp->prob = glp_create_prob();
 331   GNUNET_assert (mlp->prob != NULL);
 332
 333   /* Get diversity coefficient from configuration */
 334   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 335                                                       "COEFFICIENT_D",
 336                                                       &tmp))
 337     D = (double) tmp / 100;
 338   else
 339     D = 1.0;
 340
 341   /* Get proportionality coefficient from configuration */
 342   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 343                                                       "COEFFICIENT_R",
 344                                                       &tmp))
 345     R = (double) tmp / 100;
 346   else
 347     R = 1.0;
 348
 349   /* Get utilization coefficient from configuration */
 350   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 351                                                       "COEFFICIENT_U",
 352                                                       &tmp))
 353     U = (double) tmp / 100;
 354   else
 355     U = 1.0;
 356
 357   /* Get quality metric coefficients from configuration */
 358   int i_delay = -1;
 359   int i_distance = -1;
 360   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
 361   int c;
 362   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 363   {
 364     /* initialize quality coefficients with default value 1.0 */
 365     mlp->co_Q[c] = 1.0;
 366
 367     mlp->q[c] = q[c];
 368     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
 369       i_delay = c;
 370     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
 371       i_distance = c;
 372   }
 373
 374   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 375                                                       "COEFFICIENT_QUALITY_DELAY",
 376                                                       &tmp)))
 377
 378     mlp->co_Q[i_delay] = (double) tmp / 100;
 379   else
 380     mlp->co_Q[i_delay] = 1.0;
 381
 382   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 383                                                       "COEFFICIENT_QUALITY_DISTANCE",
 384                                                       &tmp)))
 385     mlp->co_Q[i_distance] = (double) tmp / 100;
 386   else
 387     mlp->co_Q[i_distance] = 1.0;
 388
 389   /* Get minimum bandwidth per used address from configuration */
 390   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 391                                                       "MIN_BANDWIDTH",
 392                                                       &tmp))
 393     b_min = tmp;
 394   else
 395     b_min = 64000;
 396
 397   /* Get minimum number of connections from configuration */
 398   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
 399                                                       "MIN_CONNECTIONS",
 400                                                       &tmp))
 401     n_min = tmp;
 402   else
 403     n_min = 4;
 404
 405   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
 406   mlp->max_iterations = max_iterations;
 407   mlp->max_exec_duration = max_duration;
 408
 409   /* Redirect GLPK output to GNUnet logging */
 410   glp_error_hook((void *) mlp, &mlp_term_hook);
 411
 412   /* Init LP solving parameters */
 413   glp_init_smcp(&mlp->control_param_lp);
 414 #if DEBUG_MLP
 415   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
 416 #else
 417   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
 418 #endif
 419   mlp->control_param_lp.it_lim = max_iterations;
 420   mlp->control_param_lp.tm_lim = max_duration.rel_value;
 421
 422   /* Init MLP solving parameters */
 423   glp_init_iocp(&mlp->control_param_mlp);
 424 #if DEBUG_MLP
 425   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
 426 #else
 427   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
 428 #endif
 429   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
 430
 431   mlp->last_execution = GNUNET_TIME_absolute_get_forever();
 432
 433   mlp->co_D = D;
 434   mlp->co_R = R;
 435   mlp->co_U = U;
 436   mlp->b_min = b_min;
 437   mlp->n_min = n_min;
 438   mlp->m = GNUNET_ATS_QualityPropertiesCount;
 439
 440   mlp_create_problem (mlp);
 441   return mlp;
 442 }
 443
 444 /**
 445  * Updates a single address in the MLP problem
 446  *
 447  * If the address did not exist before in the problem:
 448  * The MLP problem has to be recreated and the problem has to be resolved
 449  *
 450  * Otherwise the addresses' values can be updated and the existing base can
 451  * be reused
 452  *
 453  * @param mlp the MLP Handle
 454  * @param addresses the address hashmap
 455  * @param address the address to update
 456  */
 457 void
 458 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 459 {
 460   int new;
 461   int col;
 462   struct MLP_information *mlpi;
 463   char * name;
 464
 465   GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
 466
 467   /* We add a new address */
 468   if (address->mlp_information == NULL)
 469   {
 470     new = GNUNET_YES;
 471     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
 472     address->mlp_information = mlpi;
 473
 474     /* Add bandwidth column */
 475     col = glp_add_cols (mlp->prob, 2);
 476     mlpi->c_b = col;
 477     mlpi->c_n = col + 1;
 478
 479     GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 480     glp_set_col_name (mlp->prob, mlpi->c_b , name);
 481     GNUNET_free (name);
 482     /* Lower bound == 0 */
 483     glp_set_col_bnds (mlp->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
 484     /* Continuous value*/
 485     glp_set_col_kind (mlp->prob, mlpi->c_b , GLP_CV);
 486     /* Objective function coefficient == 0 */
 487     glp_set_obj_coef (mlp->prob, mlpi->c_b , 0);
 488
 489     /* Add usage column */
 490     GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
 491     glp_set_col_name (mlp->prob, mlpi->c_n, name);
 492     GNUNET_free (name);
 493     /* Limit value : 0 <= value <= 1 */
 494     glp_set_col_bnds (mlp->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
 495     /* Integer value*/
 496     glp_set_col_kind (mlp->prob, mlpi->c_n, GLP_IV);
 497     /* Objective function coefficient == 0 */
 498     glp_set_obj_coef (mlp->prob, mlpi->c_n, 0);
 499
 500     /* Add */
 501   }
 502   else
 503     new = GNUNET_NO;
 504
 505   /* Do the update */
 506
 507   /* Recalculate */
 508   if (new == GNUNET_YES)
 509     mlp->presolver_required = GNUNET_YES;
 510   mlp_solve_problem (mlp);
 511 }
 512
 513 /**
 514  * Deletes a single address in the MLP problem
 515  *
 516  * The MLP problem has to be recreated and the problem has to be resolved
 517  *
 518  * @param mlp the MLP Handle
 519  * @param addresses the address hashmap
 520  * @param address the address to delete
 521  */
 522 void
 523 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 524 {
 525   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
 526
 527   /* Free resources */
 528   if (address->mlp_information != NULL)
 529   {
 530     GNUNET_free (address->mlp_information);
 531     address->mlp_information = NULL;
 532   }
 533
 534   /* Update problem */
 535
 536   /* Recalculate */
 537   mlp->presolver_required = GNUNET_YES;
 538   mlp_solve_problem (mlp);
 539 }
 540
 541 /**
 542  * Deletes a single address in the MLP problem
 543  *
 544  * @param mlp the MLP Handle
 545  * @param addresses the address hashmap
 546  * @param address the address to change the preference
 547  */
 548 void
 549 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 550 {
 551   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
 552 }
 553
 554 /**
 555  * Shutdown the MLP problem solving component
 556  * @param mlp the MLP handle
 557  */
 558 void
 559 GAS_mlp_done (struct GAS_MLP_Handle *mlp)
 560 {
 561   if (mlp != NULL)
 562     glp_delete_prob(mlp->prob);
 563
 564   /* Clean up GLPK environment */
 565   glp_free_env();
 566
 567   GNUNET_free (mlp);
 568 }
 569
 570
 571 /* end of gnunet-service-ats_addresses_mlp.c */