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 /**
  35  *
  36  * NOTE: Do not modify this documentation. This documentation is based on
  37  * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
  38  * use build_txt.sh to generate plaintext output
  39  *
  40  *    The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
  41  *    optimizing an mixed integer programming problem. The MLP solver uses a
  42  *    number of constraints to find the best adddress for a peer and an optimal
  43  *    bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
  44  *    MLP problem.
  45  *
  46  *    We defined a constraint system to find an optimal bandwidth assignment.
  47  *    This constraint system uses as an input data addresses, bandwidth quotas,
  48  *    preferences and quality values. This constraint system is stored in an
  49  *    matrix based equotation system.
  50  *
  51  *   5 Using GLPK
  52  *
  53  *    A (M)LP problem consists of a target function to optimizes, constraints
  54  *    and rows and columns. FIXME GLP uses three arrays to index the matrix: two
  55  *    integer arrays storing the row and column indices in the matrix and an
  56  *    float array to store the coeeficient.
  57  *
  58  *    To solve the problem we first find an initial solution for the LP problem
  59  *    using the LP solver and then find an MLP solution based on this solution
  60  *    using the MLP solver.
  61  *
  62  *    Solving (M)LP problems has the property that finding an initial solution
  63  *    for the LP problem is computationally expensive and finding the MLP
  64  *    solution is cheaper. This is especially interesting an existing LP
  65  *    solution can be reused if only coefficients in the matrix have changed
  66  *    (addresses updated). Only when the problem size changes (addresses added
  67  *    or deleted) a new LP solution has to be found.
  68  *
  69  *    Intended usage
  70  *    The mlp solver solves the bandwidth assignment problem only on demand when
  71  *    an address suggestion is requested. When an address is requested mlp the
  72  *    solves the mlp problem and if the active address or the bandwidth assigned
  73  *    changes it calls the callback to addresses. The mlp solver gets notified
  74  *    about new addresses (adding sessions), removed addresses (address
  75  *    deletions) and address updates. To benefit from the mlp properties
  76  *    mentioned in section 5 the solver rembers if since the last solution
  77  *    addresses were added or deleted (problem size changed, problem has to be
  78  *    rebuild and solved from sratch) or if addresses were updated and the
  79  *    existing solution can be reused.
  80  *
  81  *     5.1 Input data
  82  *
  83  *    The quotas for each network segment are passed by addresses. MLP can be
  84  *    adapted using configuration settings and uses the following parameters:
  85  *      * MLP_MAX_DURATION:
  86  *        Maximum duration for a MLP solution procees (default: 3 sec.)
  87  *      * MLP_MAX_DURATION:
  88  *        Maximum number of iterations for a MLP solution process (default:
  89  *        1024)
  90  *      * MLP_MIN_CONNECTIONS:
  91  *        Minimum number of desired connections (default: 4)
  92  *      * MLP_MIN_BANDWIDTH:
  93  *        Minimum amount of bandwidth assigned to an address (default: 1024)
  94  *      * MLP_COEFFICIENT_D:
  95  *        Diversity coefficient (default: 1.0)
  96  *      * MLP_COEFFICIENT_R:
  97  *        Relativity coefficient (default: 1.0)
  98  *      * MLP_COEFFICIENT_U:
  99  *        Utilization coefficient (default: 1.0)
 100  *      * MLP_COEFFICIENT_D:
 101  *        Diversity coefficient (default: 1.0)
 102  *      * MLP_COEFFICIENT_QUALITY_DELAY:
 103  *        Quality delay coefficient (default: 1.0)
 104  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 105  *        Quality distance coefficient (default: 1.0)
 106  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 107  *        Quality distance coefficient (default: 1.0)
 108  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 109  *        Quality distance coefficient (default: 1.0)
 110  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 111  *        Quality distance coefficient (default: 1.0)
 112  *
 113  *     5.2 Data structures used
 114  *
 115  *    mlp has for each known peer a struct ATS_Peer containing information about
 116  *    a specific peer. The address field solver_information contains information
 117  *    about the mlp properties of this address.
 118  *
 119  *     5.3 Initializing
 120  *
 121  *    During initialization mlp initializes the GLPK libray used to solve the
 122  *    MLP problem: it initializes the glpk environment and creates an initial LP
 123  *    problem. Next it loads the configuration values from the configuration or
 124  *    uses the default values configured in -addresses_mlp.h. The quotas used
 125  *    are given by addresses but may have to be adjusted. mlp uses a upper limit
 126  *    for the bandwidth assigned called BIG M and a minimum amount of bandwidth
 127  *    an address gets assigned as well as a minium desired number of
 128  *    connections. If the configured quota is bigger than BIG M, it is reduced
 129  *    to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
 130  *    *MLP_MIN_BANDWIDTH it is increased to this value.
 131  *
 132  *     5.4 Shutdown
 133
 134  */
 135
 136 #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
 137
 138 /**
 139  * Print debug output for mlp problem creation
 140  */
 141 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
 142
 143 /**
 144  * Enable GLPK verbose output
 145  */
 146 #define VERBOSE_GLPK GNUNET_NO
 147
 148 /**
 149  * Maximize bandwidth assigned
 150  *
 151  * This option can be used to test if problem can be solved at all without
 152  * optimizing for utility, diversity or relativity
 153  *
 154  */
 155 #define MAXIMIZE_FOR_BANDWIDTH_ASSIGNED GNUNET_NO
 156
 157 /**
 158  * Intercept GLPK terminal output
 159  * @param info the mlp handle
 160  * @param s the string to print
 161  * @return 0: glpk prints output on terminal, 0 != surpress output
 162  */
 163 static int
 164 mlp_term_hook (void *info, const char *s)
 165 {
 166   /* Not needed atm struct MLP_information *mlp = info; */
 167   LOG (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
 168   return 1;
 169 }
 170
 171
 172 /**
 173  * Reset peers for next problem creation
 174  *
 175  * @param cls not used
 176  * @param key the key
 177  * @param value ATS_Peer
 178  * @return GNUNET_OK
 179  */
 180 static int
 181 reset_peers (void *cls, const struct GNUNET_HashCode * key, void *value)
 182  {
 183          struct ATS_Peer *peer = value;
 184          peer->processed = GNUNET_NO;
 185          return GNUNET_OK;
 186  }
 187
 188 /**
 189  * Delete the MLP problem and free the constrain matrix
 190  *
 191  * @param mlp the MLP handle
 192  */
 193 static void
 194 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 195 {
 196         int c;
 197   if (mlp == NULL)
 198         return;
 199         if (mlp->p.prob != NULL)
 200         {
 201                 glp_delete_prob(mlp->p.prob);
 202                 mlp->p.prob = NULL;
 203         }
 204
 205         /* delete row index */
 206         if (mlp->p.ia != NULL)
 207         {
 208                 GNUNET_free (mlp->p.ia);
 209                 mlp->p.ia = NULL;
 210         }
 211
 212         /* delete column index */
 213         if (mlp->p.ja != NULL)
 214         {
 215                 GNUNET_free (mlp->p.ja);
 216                 mlp->p.ja = NULL;
 217         }
 218
 219         /* delete coefficients */
 220         if (mlp->p.ar != NULL)
 221         {
 222                 GNUNET_free (mlp->p.ar);
 223                 mlp->p.ar = NULL;
 224         }
 225         mlp->p.ci = 0;
 226         mlp->p.prob = NULL;
 227
 228   mlp->p.c_d = MLP_UNDEFINED;
 229   mlp->p.c_r = MLP_UNDEFINED;
 230   mlp->p.r_c2 = MLP_UNDEFINED;
 231   mlp->p.r_c4 = MLP_UNDEFINED;
 232   mlp->p.r_c6 = MLP_UNDEFINED;
 233   mlp->p.r_c9 = MLP_UNDEFINED;
 234   for (c = 0; c < mlp->pv.m_q ; c ++)
 235         mlp->p.r_q[c] = MLP_UNDEFINED;
 236   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++)
 237         mlp->p.r_quota[c] = MLP_UNDEFINED;
 238   mlp->p.ci = MLP_UNDEFINED;
 239
 240
 241   GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &reset_peers, NULL);
 242 }
 243
 244
 245 /**
 246  * Translate ATS properties to text
 247  * Just intended for debugging
 248  *
 249  * @param ats_index the ATS index
 250  * @return string with result
 251  */
 252 const char *
 253 mlp_ats_to_string (int ats_index)
 254 {
 255   switch (ats_index) {
 256     case GNUNET_ATS_ARRAY_TERMINATOR:
 257       return "GNUNET_ATS_ARRAY_TERMINATOR";
 258     case GNUNET_ATS_UTILIZATION_UP:
 259       return "GNUNET_ATS_UTILIZATION_UP";
 260     case GNUNET_ATS_UTILIZATION_DOWN:
 261       return "GNUNET_ATS_UTILIZATION_DOWN";
 262     case GNUNET_ATS_COST_LAN:
 263       return "GNUNET_ATS_COST_LAN";
 264     case GNUNET_ATS_COST_WAN:
 265       return "GNUNET_ATS_COST_LAN";
 266     case GNUNET_ATS_COST_WLAN:
 267       return "GNUNET_ATS_COST_WLAN";
 268     case GNUNET_ATS_NETWORK_TYPE:
 269       return "GNUNET_ATS_NETWORK_TYPE";
 270     case GNUNET_ATS_QUALITY_NET_DELAY:
 271       return "GNUNET_ATS_QUALITY_NET_DELAY";
 272     case GNUNET_ATS_QUALITY_NET_DISTANCE:
 273       return "GNUNET_ATS_QUALITY_NET_DISTANCE";
 274     default:
 275       GNUNET_break (0);
 276       return "unknown";
 277   }
 278 }
 279
 280 /**
 281  * Translate glpk status error codes to text
 282  * @param retcode return code
 283  * @return string with result
 284  */
 285 const char *
 286 mlp_status_to_string (int retcode)
 287 {
 288   switch (retcode) {
 289     case GLP_UNDEF:
 290       return "solution is undefined";
 291     case GLP_FEAS:
 292       return "solution is feasible";
 293     case GLP_INFEAS:
 294       return "solution is infeasible";
 295     case GLP_NOFEAS:
 296       return "no feasible solution exists";
 297     case GLP_OPT:
 298       return "solution is optimal";
 299     case GLP_UNBND:
 300       return "solution is unbounded";
 301     default:
 302       GNUNET_break (0);
 303       return "unknown error";
 304   }
 305 }
 306
 307 /**
 308  * Translate glpk solver error codes to text
 309  * @param retcode return code
 310  * @return string with result
 311  */
 312 const char *
 313 mlp_solve_to_string (int retcode)
 314 {
 315   switch (retcode) {
 316     case 0:
 317       return "ok";
 318     case GLP_EBADB:
 319       return "invalid basis";
 320     case GLP_ESING:
 321       return "singular matrix";
 322     case GLP_ECOND:
 323       return "ill-conditioned matrix";
 324     case GLP_EBOUND:
 325       return "invalid bounds";
 326     case GLP_EFAIL:
 327       return "solver failed";
 328     case GLP_EOBJLL:
 329       return "objective lower limit reached";
 330     case GLP_EOBJUL:
 331       return "objective upper limit reached";
 332     case GLP_EITLIM:
 333       return "iteration limit exceeded";
 334     case GLP_ETMLIM:
 335       return "time limit exceeded";
 336     case GLP_ENOPFS:
 337       return "no primal feasible solution";
 338     case GLP_ENODFS:
 339       return "no dual feasible solution";
 340     case GLP_EROOT:
 341       return "root LP optimum not provided";
 342     case GLP_ESTOP:
 343       return "search terminated by application";
 344     case GLP_EMIPGAP:
 345       return "relative mip gap tolerance reached";
 346     case GLP_ENOFEAS:
 347       return "no dual feasible solution";
 348     case GLP_ENOCVG:
 349       return "no convergence";
 350     case GLP_EINSTAB:
 351       return "numerical instability";
 352     case GLP_EDATA:
 353       return "invalid data";
 354     case GLP_ERANGE:
 355       return "result out of range";
 356     default:
 357       GNUNET_break (0);
 358       return "unknown error";
 359   }
 360 }
 361
 362 /**
 363  * Extract an ATS performance info from an address
 364  *
 365  * @param address the address
 366  * @param type the type to extract in HBO
 367  * @return the value in HBO or GNUNET_ATS_VALUE_UNDEFINED in HBO if value does not exist
 368  */
 369 static int
 370 get_performance_info (struct ATS_Address *address, uint32_t type)
 371 {
 372         int c1;
 373         GNUNET_assert (NULL != address);
 374
 375         if ((NULL == address->atsi) || (0 == address->atsi_count))
 376                         return GNUNET_ATS_VALUE_UNDEFINED;
 377
 378         for (c1 = 0; c1 < address->atsi_count; c1++)
 379         {
 380                         if (ntohl(address->atsi[c1].type) == type)
 381                                 return ntohl(address->atsi[c1].value);
 382         }
 383         return GNUNET_ATS_VALUE_UNDEFINED;
 384 }
 385
 386
 387 struct CountContext
 388 {
 389         struct GNUNET_CONTAINER_MultiHashMap * peers;
 390         int result;
 391 };
 392
 393 static int
 394 mlp_create_problem_count_addresses_it (void *cls, const struct GNUNET_HashCode *key, void *value)
 395 {
 396         struct CountContext *cctx = cls;
 397   /* Check if we have to add this peer due to a pending request */
 398   if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains(cctx->peers, key))
 399         cctx->result++;
 400   return GNUNET_OK;
 401 }
 402
 403 static int mlp_create_problem_count_addresses (
 404                 struct GNUNET_CONTAINER_MultiHashMap * peers,
 405                 struct GNUNET_CONTAINER_MultiHashMap * addresses)
 406 {
 407         struct CountContext cctx;
 408         cctx.peers = peers;
 409         cctx.result = 0;
 410   GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_create_problem_count_addresses_it, &cctx);
 411   return cctx.result;
 412 }
 413
 414
 415
 416 static void
 417 mlp_create_problem_set_value (struct MLP_Problem *p,
 418                                                                                                                         int row, int col, double val,
 419                                                                                                                         int line)
 420 {
 421         if ((p->ci) >= p->num_elements)
 422         {
 423                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
 424                                 line, p->ci + 1, p->num_elements);
 425                 GNUNET_break (0);
 426                 return;
 427         }
 428         if ((0 == row) || (0 == col))
 429                 GNUNET_break (0);
 430   p->ia[p->ci] = row ;
 431   p->ja[p->ci] = col;
 432   p->ar[p->ci] = val;
 433 #if  DEBUG_MLP_PROBLEM_CREATION
 434         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u ==  %.2f\n",
 435                         line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
 436 #endif
 437   p->ci++;
 438 }
 439
 440 static int
 441 mlp_create_problem_create_column (struct MLP_Problem *p, char *name,
 442                 unsigned int type, unsigned int bound, double lb, double ub,
 443                 double coef)
 444 {
 445         int col = glp_add_cols (p->prob, 1);
 446   glp_set_col_name (p->prob, col, name);
 447   glp_set_col_bnds (p->prob, col, bound, lb, ub);
 448   glp_set_col_kind (p->prob, col, type);
 449   glp_set_obj_coef (p->prob, col, coef);
 450 #if  DEBUG_MLP_PROBLEM_CREATION
 451         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
 452                         col, name, coef);
 453 #endif
 454   return col;
 455 }
 456
 457 static int
 458 mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name,
 459                 unsigned int bound, double lb, double ub)
 460 {
 461         char * op;
 462   int row = glp_add_rows (p->prob, 1);
 463   /* set row name */
 464   glp_set_row_name (p->prob, row, name);
 465   /* set row bounds: <= 0 */
 466   glp_set_row_bnds (p->prob, row, bound, lb, ub);
 467   switch (bound) {
 468                 case GLP_UP:
 469                         GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
 470                         break;
 471                 case GLP_DB:
 472                         GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
 473                         break;
 474                 case GLP_FX:
 475                         GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
 476                         break;
 477                 case GLP_LO:
 478                         GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
 479                         break;
 480                 default:
 481                         GNUNET_asprintf(&op, "ERROR");
 482                         break;
 483         }
 484 #if  DEBUG_MLP_PROBLEM_CREATION
 485                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
 486                                 row, name, op);
 487 #endif
 488         GNUNET_free (op);
 489         return row;
 490 }
 491
 492 /**
 493  * Create the
 494  * - address columns b and n
 495  * - address dependent constraint rows c1, c3
 496  * - peer dependent rows c2 and c9
 497  * - Set address dependent entries in problem matrix as well
 498  */
 499 static int
 500 mlp_create_problem_add_address_information (void *cls, const struct GNUNET_HashCode *key, void *value)
 501 {
 502   struct GAS_MLP_Handle *mlp = cls;
 503   struct MLP_Problem *p = &mlp->p;
 504   struct ATS_Address *address = value;
 505   struct ATS_Peer *peer;
 506   struct MLP_information *mlpi;
 507   char *name;
 508   uint32_t addr_net;
 509   int c;
 510
 511   /* Check if we have to add this peer due to a pending request */
 512   if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
 513         return GNUNET_OK;
 514
 515   mlpi = address->solver_information;
 516   if (NULL == mlpi)
 517   {
 518                 GNUNET_break (0);
 519                 return GNUNET_OK;
 520   }
 521
 522   /* Get peer */
 523   peer = GNUNET_CONTAINER_multihashmap_get (mlp->peers, key);
 524   if (peer->processed == GNUNET_NO)
 525   {
 526                 /* Add peer dependent constraints */
 527                 /* Add constraint c2 */
 528           GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
 529           peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0);
 530                 GNUNET_free (name);
 531                 /* Add constraint c9 */
 532           GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
 533           peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
 534                 GNUNET_free (name);
 535           /* c 9) set coefficient */
 536                 mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f, __LINE__);
 537
 538                 peer->processed = GNUNET_YES;
 539   }
 540
 541   /* Reset addresses' solver information */
 542   mlpi->c_b = 0;
 543   mlpi->c_n = 0;
 544   mlpi->n = 0;
 545   mlpi->r_c1 = 0;
 546   mlpi->r_c3 = 0;
 547   for (c = 0; c < mlp->pv.m_q; c++)
 548         mlpi->r_q[0] = 0;
 549
 550   /* Add bandwidth column */
 551   GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
 552 #if TEST_MAX_BW_ASSIGNMENT
 553   mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
 554 #else
 555   mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
 556 #endif
 557
 558   GNUNET_free (name);
 559
 560   /* Add usage column */
 561   GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
 562   mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
 563   GNUNET_free (name);
 564
 565         /* Add address dependent constraints */
 566         /* Add constraint c1) bandwidth capping
 567    * b_t  + (-M) * n_t <= 0
 568    * */
 569   GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
 570   mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
 571         GNUNET_free (name);
 572
 573         /*  c1) set b = 1 coefficient */
 574         mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
 575         /*  c1) set n = -M coefficient */
 576         mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -mlp->pv.BIG_M, __LINE__);
 577
 578   /* Add constraint c 3) minimum bandwidth
 579    * b_t + (-n_t * b_min) >= 0
 580    * */
 581   GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
 582         mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
 583         GNUNET_free (name);
 584
 585         /*  c3) set b = 1 coefficient */
 586         mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
 587         /*  c3) set n = -b_min coefficient */
 588         mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__);
 589
 590
 591         /* Set coefficient entries in invariant rows */
 592   /* c 4) minimum connections */
 593         mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
 594   /* c 6) maximize diversity */
 595         mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
 596   /* c 2) 1 address peer peer */
 597         mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
 598   /* c 9) relativity */
 599         mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
 600   /* c 8) utility */
 601         mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
 602
 603   /* c 10) obey network specific quotas
 604    * (1)*b_1 + ... + (1)*b_m <= quota_n
 605    */
 606   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 607   {
 608         addr_net = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE);
 609         if (GNUNET_ATS_VALUE_UNDEFINED == addr_net)
 610                 addr_net = GNUNET_ATS_NET_UNSPECIFIED;
 611
 612     if (mlp->pv.quota_index[c] == addr_net)
 613     {
 614                 mlp_create_problem_set_value (p, p->r_quota[c], mlpi->c_b, 1, __LINE__);
 615       break;
 616     }
 617   }
 618
 619   /* c 7) Optimize quality */
 620   /* For all quality metrics, set quality of this address */
 621   for (c = 0; c < mlp->pv.m_q; c++)
 622         mlp_create_problem_set_value (p, p->r_q[c], mlpi->c_b, mlpi->q_averaged[c], __LINE__);
 623
 624   return GNUNET_OK;
 625 }
 626
 627 /**
 628  * Create the invariant columns c4, c6, c10, c8, c7
 629  */
 630 static void
 631 mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
 632 {
 633   char *name;
 634   int c;
 635
 636   /* Row for c4) minimum connection */
 637   /* Number of minimum connections is min(|Peers|, n_min) */
 638   p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0);
 639
 640   /* Add row for c6) */
 641         p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0);
 642   /* c6 )Setting -D */
 643         mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
 644
 645   /* Add rows for c 10) */
 646   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 647   {
 648       char * text;
 649       GNUNET_asprintf(&text, "c10_quota_ats_%s", GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
 650                 p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
 651                 GNUNET_free (text);
 652   }
 653
 654   /* Adding rows for c 8) */
 655   p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0);
 656   /* -u */
 657         mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
 658
 659         /* c 7) For all quality metrics */
 660         for (c = 0; c < mlp->pv.m_q; c++)
 661         {
 662                 GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c]));
 663                 p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0);
 664                 GNUNET_free (name);
 665                 mlp_create_problem_set_value (p, p->r_q[c], p->c_q[c], -1, __LINE__);
 666         }
 667 }
 668
 669
 670 /**
 671  * Create the invariant columns d, u, r, q0 ... qm
 672  */
 673 static void
 674 mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
 675 {
 676   char *name;
 677   int c;
 678
 679 #if TEST_MAX_BW_ASSIGNMENT
 680   mlp->pv.co_D = 0.0;
 681   mlp->pv.co_U = 0.0;
 682
 683 #endif
 684   //mlp->pv.co_R = 0.0;
 685
 686   /* Diversity d column  */
 687   p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
 688
 689   /* Utilization u column  */
 690   p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
 691
 692   /* Relativity r column  */
 693   p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
 694
 695   /* Quality metric columns */
 696   for (c = 0; c < mlp->pv.m_q; c++)
 697   {
 698     GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]);
 699 #if TEST_MAX_BW_ASSIGNMENT
 700         p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
 701 #else
 702         p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
 703 #endif
 704         GNUNET_free (name);
 705   }
 706 }
 707
 708
 709 /**
 710  * Create the MLP problem
 711  *
 712  * @param mlp the MLP handle
 713  * @param addresses the hashmap containing all adresses
 714  * @return GNUNET_OK or GNUNET_SYSERR
 715  */
 716 static int
 717 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 718 {
 719   struct MLP_Problem *p = &mlp->p;
 720         int res = GNUNET_OK;
 721
 722   GNUNET_assert (p->prob == NULL);
 723   GNUNET_assert (p->ia == NULL);
 724   GNUNET_assert (p->ja == NULL);
 725   GNUNET_assert (p->ar == NULL);
 726   /* Reset MLP problem struct */
 727
 728   /* create the glpk problem */
 729   p->prob = glp_create_prob ();
 730   GNUNET_assert (NULL != p->prob);
 731   p->num_peers = GNUNET_CONTAINER_multihashmap_size (mlp->peers);
 732   p->num_addresses = mlp_create_problem_count_addresses (mlp->peers, addresses);
 733
 734   /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
 735   p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +  mlp->pv.m_q + p->num_peers + 2 + 1);
 736         LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
 737                         p->num_peers, p->num_addresses, mlp->pv.m_q, p->num_elements);
 738
 739   /* Set a problem name */
 740   glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
 741   /* Set optimization direction to maximize */
 742   glp_set_obj_dir (p->prob, GLP_MAX);
 743
 744   /* Create problem matrix */
 745   /* last +1 caused by glpk index starting with one: [1..elements]*/
 746   p->ci = 1;
 747   /* row index */
 748   p->ia = GNUNET_malloc (p->num_elements * sizeof (int));
 749   /* column index */
 750   p->ja = GNUNET_malloc (p->num_elements * sizeof (int));
 751   /* coefficient */
 752   p->ar = GNUNET_malloc (p->num_elements * sizeof (double));
 753
 754   if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
 755   {
 756                 LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
 757                 return GNUNET_SYSERR;
 758   }
 759
 760   /* Adding invariant columns */
 761   mlp_create_problem_add_invariant_columns (mlp, p);
 762
 763   /* Adding address independent constraint rows */
 764   mlp_create_problem_add_invariant_rows (mlp, p);
 765
 766   /* Adding address independent constraint rows */
 767   GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_create_problem_add_address_information, mlp);
 768
 769   /* Load the matrix */
 770         LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
 771   glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar);
 772
 773   return res;
 774 }
 775
 776 /**
 777  * Solves the LP problem
 778  *
 779  * @param mlp the MLP Handle
 780  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 781  */
 782 static int
 783 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
 784 {
 785         int res = 0;
 786
 787         res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
 788         if (0 == res)
 789                 LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", res, mlp_solve_to_string(res));
 790         else
 791                 LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res));
 792
 793   /* Analyze problem status  */
 794   res = glp_get_status (mlp->p.prob);
 795   switch (res) {
 796     /* solution is optimal */
 797     case GLP_OPT:
 798     /* solution is feasible */
 799     case GLP_FEAS:
 800       LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n",
 801                 res, mlp_status_to_string(res));
 802       return GNUNET_OK;
 803     /* Problem was ill-defined, no way to handle that */
 804     default:
 805       LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed, no solution: 0x%02X %s\n",
 806                 res, mlp_status_to_string(res));
 807       return GNUNET_SYSERR;
 808   }
 809 }
 810
 811
 812 /**
 813  * Solves the MLP problem
 814  *
 815  * @param mlp the MLP Handle
 816  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 817  */
 818 int
 819 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp)
 820 {
 821         int res = 0;
 822         res = glp_intopt(mlp->p.prob, &mlp->control_param_mlp);
 823         if (0 == res)
 824                 LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_solve_to_string(res));
 825         else
 826                 LOG (GNUNET_ERROR_TYPE_WARNING, "Solving MLP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res));
 827   /* Analyze problem status  */
 828   res = glp_mip_status(mlp->p.prob);
 829   switch (res) {
 830     /* solution is optimal */
 831     case GLP_OPT:
 832     /* solution is feasible */
 833     case GLP_FEAS:
 834       LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_status_to_string(res));
 835       return GNUNET_OK;
 836     /* Problem was ill-defined, no way to handle that */
 837     default:
 838       LOG (GNUNET_ERROR_TYPE_WARNING,"Solving MLP problem failed, 0x%02X %s\n\n", res, mlp_status_to_string(res));
 839       return GNUNET_SYSERR;
 840   }
 841 }
 842
 843
 844 /**
 845  * Propagates the results when MLP problem was solved
 846  *
 847  * @param cls the MLP handle
 848  * @param key the peer identity
 849  * @param value the address
 850  * @return GNUNET_OK to continue
 851  */
 852 int
 853 mlp_propagate_results (void *cls, const struct GNUNET_HashCode *key, void *value)
 854 {
 855         struct GAS_MLP_Handle *mlp = cls;
 856         struct ATS_Address *address;
 857         struct MLP_information *mlpi;
 858         double mlp_bw_in = MLP_NaN;
 859         double mlp_bw_out = MLP_NaN;
 860         double mlp_use = MLP_NaN;
 861
 862   /* Check if we have to add this peer due to a pending request */
 863   if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
 864         return GNUNET_OK;
 865   address = value;
 866   GNUNET_assert (address->solver_information != NULL);
 867   mlpi = address->solver_information;
 868
 869   mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
 870   if (mlp_bw_in > (double) UINT32_MAX)
 871   {
 872                 LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
 873                 mlp_bw_in = (double) UINT32_MAX;
 874   }
 875   mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
 876   if (mlp_bw_out > (double) UINT32_MAX)
 877   {
 878                 LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
 879                 mlp_bw_out = (double) UINT32_MAX;
 880   }
 881   mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
 882
 883
 884
 885   if ((GLP_YES == mlp_use) && (GNUNET_NO == address->active))
 886   {
 887         /* Address switch: Activate address*/
 888         LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
 889                 address->active = GNUNET_YES;
 890                 address->assigned_bw_in.value__ = htonl (mlp_bw_in);
 891                 mlpi->b_in.value__ = htonl(mlp_bw_in);
 892                 address->assigned_bw_out.value__ = htonl (mlp_bw_out);
 893                 mlpi->b_out.value__ = htonl(mlp_bw_out);
 894                 mlpi->n = mlp_use;
 895                 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address);
 896   }
 897   else if ((GLP_NO == mlp_use) && (GNUNET_YES == address->active))
 898   {
 899                 /* Address switch: Disable address*/
 900         LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
 901                 address->active = GNUNET_NO;
 902                 /* Set bandwidth to 0 */
 903                 address->assigned_bw_in.value__ = htonl (0);
 904                 mlpi->b_in.value__ = htonl(mlp_bw_in);
 905                 address->assigned_bw_out.value__ = htonl (0);
 906                 mlpi->b_out.value__ = htonl(mlp_bw_out);
 907                 mlpi->n = mlp_use;
 908                 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address);
 909   }
 910   else if ((mlp_bw_out != ntohl(address->assigned_bw_out.value__)) ||
 911                                  (mlp_bw_in != ntohl(address->assigned_bw_in.value__)))
 912   {
 913         /* Bandwidth changed */
 914                 LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
 915                 address->assigned_bw_in.value__ = htonl (mlp_bw_in);
 916                 mlpi->b_in.value__ = htonl(mlp_bw_in);
 917                 address->assigned_bw_out.value__ = htonl (mlp_bw_out);
 918                 mlpi->b_out.value__ = htonl(mlp_bw_out);
 919                 mlpi->n = mlp_use;
 920                 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address);
 921   }
 922   else
 923   {
 924     LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n", (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
 925   }
 926
 927   return GNUNET_OK;
 928 }
 929
 930
 931
 932 /**
 933  * Solves the MLP problem
 934  *
 935  * @param solver the MLP Handle
 936  * @param addresses the address hashmap
 937  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 938  */
 939 int
 940 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 941 {
 942         struct GAS_MLP_Handle *mlp = solver;
 943         char *filename;
 944         int res_lp = 0;
 945         int res_mip = 0;
 946         struct GNUNET_TIME_Absolute start_build;
 947         struct GNUNET_TIME_Relative duration_build;
 948         struct GNUNET_TIME_Absolute start_lp;
 949         struct GNUNET_TIME_Relative duration_lp;
 950         struct GNUNET_TIME_Absolute start_mlp;
 951         struct GNUNET_TIME_Relative duration_mlp;
 952         GNUNET_assert (NULL != solver);
 953
 954         if ((GNUNET_NO == mlp->mlp_prob_changed) && (GNUNET_NO == mlp->mlp_prob_updated))
 955         {
 956                 LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
 957                 return GNUNET_OK;
 958         }
 959
 960         if (GNUNET_YES == mlp->mlp_prob_changed)
 961         {
 962                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
 963                         mlp_delete_problem (mlp);
 964                         start_build = GNUNET_TIME_absolute_get();
 965                         if (GNUNET_SYSERR == mlp_create_problem (mlp, addresses))
 966                                 return GNUNET_SYSERR;
 967                         duration_build = GNUNET_TIME_absolute_get_duration (start_build);
 968                         mlp->control_param_lp.presolve = GLP_YES;
 969                         mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
 970         }
 971         else
 972         {
 973                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
 974                         duration_build.rel_value = 0;
 975         }
 976
 977         /* Run LP solver */
 978         LOG (GNUNET_ERROR_TYPE_DEBUG, "Running LP solver %s\n", (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver");
 979         start_lp = GNUNET_TIME_absolute_get();
 980         res_lp = mlp_solve_lp_problem (mlp);
 981         duration_lp = GNUNET_TIME_absolute_get_duration (start_lp);
 982
 983
 984   /* Run LP solver */
 985         LOG (GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
 986         start_mlp = GNUNET_TIME_absolute_get();
 987         res_mip = mlp_solve_mlp_problem (mlp);
 988
 989         duration_mlp = GNUNET_TIME_absolute_get_duration (start_mlp);
 990
 991         /* Save stats */
 992         mlp->ps.lp_res = res_lp;
 993         mlp->ps.mip_res = res_mip;
 994         mlp->ps.build_dur = duration_build;
 995         mlp->ps.lp_dur = duration_lp;
 996         mlp->ps.mip_dur = duration_mlp;
 997         mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
 998         mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
 999         mlp->ps.p_cols = glp_get_num_cols (mlp->p.prob);
1000         mlp->ps.p_rows = glp_get_num_rows (mlp->p.prob);
1001         mlp->ps.p_elements = mlp->p.num_elements;
1002
1003         LOG (GNUNET_ERROR_TYPE_DEBUG, "Execution time: Build %llu ms, LP %llu ms,  MLP %llu ms\n",
1004                         (unsigned long long) duration_build.rel_value,
1005                         (unsigned long long) duration_lp.rel_value,
1006                         (unsigned long long) duration_mlp.rel_value);
1007
1008         /* Propagate result*/
1009         if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip))
1010                 GNUNET_CONTAINER_multihashmap_iterate (addresses, &mlp_propagate_results, mlp);
1011
1012         struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get();
1013         if (GNUNET_YES == mlp->write_mip_mps)
1014         {
1015         /* Write problem and solution to disk */
1016         GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers, mlp->p.num_addresses, time.abs_value);
1017         glp_write_mps(mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1018         GNUNET_free (filename);
1019         }
1020         if (GNUNET_YES == mlp->write_mip_sol)
1021         {
1022                 GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers, mlp->p.num_addresses, time.abs_value);
1023                 glp_print_mip (mlp->p.prob, filename );
1024                 GNUNET_free (filename);
1025         }
1026
1027         /* Reset change and update marker */
1028         mlp->control_param_lp.presolve = GLP_NO;
1029         mlp->mlp_prob_updated = GNUNET_NO;
1030         mlp->mlp_prob_changed = GNUNET_NO;
1031
1032         if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip))
1033                 return GNUNET_OK;
1034         else
1035                 return GNUNET_SYSERR;
1036 }
1037
1038 /**
1039  * Add a single address to the solve
1040  *
1041  * @param solver the solver Handle
1042  * @param addresses the address hashmap containing all addresses
1043  * @param network network type of this address
1044  */
1045 void
1046 GAS_mlp_address_add (void *solver,
1047                                                                                 struct GNUNET_CONTAINER_MultiHashMap *addresses,
1048                                                                                 struct ATS_Address *address,
1049                                                                                 uint32_t network)
1050 {
1051   struct GAS_MLP_Handle *mlp = solver;
1052   struct ATS_Peer *p;
1053   struct MLP_information *mlpi;
1054   int c1;
1055   int c2;
1056
1057   GNUNET_assert (NULL != solver);
1058   GNUNET_assert (NULL != addresses);
1059   GNUNET_assert (NULL != address);
1060
1061
1062   if (NULL == address->solver_information)
1063   {
1064                 address->solver_information = GNUNET_malloc (sizeof (struct MLP_information));
1065                 mlpi = address->solver_information;
1066           for (c1 = 0; c1 < mlp->pv.m_q; c1++)
1067           {
1068                 mlpi->q_averaged[c1] = DEFAULT_QUALITY;
1069                 for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1070                         mlpi->q[c1][c2] = MLP_NaN;
1071           }
1072   }
1073   else
1074       LOG (GNUNET_ERROR_TYPE_ERROR, _("Adding address for peer `%s' multiple times\n"), GNUNET_i2s(&address->peer));
1075
1076   /* Is this peer included in the problem? */
1077   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1078   {
1079     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1080         return;
1081   }
1082
1083         LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1084         /* Problem size changed: new address for peer with pending request */
1085         mlp->mlp_prob_changed = GNUNET_YES;
1086         if (GNUNET_YES == mlp->mlp_auto_solve)
1087                 GAS_mlp_solve_problem (solver, addresses);
1088 }
1089
1090
1091 static void
1092 mlp_update_quality (struct GAS_MLP_Handle *mlp,
1093                 struct GNUNET_CONTAINER_MultiHashMap *addresses,
1094                 struct ATS_Address * address,
1095                 const struct GNUNET_ATS_Information *ats_prev, uint32_t ats_prev_count)
1096 {
1097   struct MLP_information *mlpi = address->solver_information;
1098   unsigned int c_ats_entry;
1099   unsigned int c_queue_entries;
1100   unsigned int c_cmp;
1101   unsigned int c_queue_it;
1102   unsigned int c_row;
1103   unsigned int c_qual;
1104   unsigned int c_net;
1105   int qual_changed;
1106   int type_index;
1107   int avg_index;
1108   uint32_t type;
1109   uint32_t prev_value;
1110   uint32_t new_value;
1111   double avg;
1112   double *queue;
1113   int rows;
1114   double *val;
1115   int *ind;
1116
1117
1118         LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating %u quality metrics for peer `%s'\n",
1119       ats_prev_count, GNUNET_i2s (&address->peer));
1120
1121         GNUNET_assert (NULL != mlp);
1122   GNUNET_assert (NULL != address);
1123   GNUNET_assert (NULL != address->solver_information);
1124   GNUNET_assert (NULL != ats_prev);
1125
1126   if (NULL == mlp->p.prob)
1127         return;
1128
1129   qual_changed = GNUNET_NO;
1130   for (c_ats_entry = 0; c_ats_entry < ats_prev_count; c_ats_entry++)
1131   {
1132                 type = ntohl (ats_prev[c_ats_entry].type);
1133                 prev_value = ntohl (ats_prev[c_ats_entry].value);
1134                 type_index = -1;
1135                 avg_index = -1;
1136
1137                 /* Check for network update */
1138                 if (type == GNUNET_ATS_NETWORK_TYPE)
1139                 {
1140                                 new_value = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE);
1141                         if (GNUNET_ATS_VALUE_UNDEFINED == new_value)
1142                                 new_value = GNUNET_ATS_NET_UNSPECIFIED;
1143                                 if (new_value != prev_value)
1144                                 {
1145                                 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating network for peer `%s' from `%s' to `%s'\n",
1146                               GNUNET_i2s (&address->peer),
1147                               GNUNET_ATS_print_network_type(prev_value),
1148                               GNUNET_ATS_print_network_type(new_value));
1149                                 }
1150
1151                                 if (mlpi->c_b == MLP_UNDEFINED)
1152                                         continue; /* This address is not yet in the matrix*/
1153
1154                           rows = glp_get_num_rows(mlp->p.prob);
1155                           ind = GNUNET_malloc (rows * sizeof (int) + 1);
1156                           val = GNUNET_malloc (rows * sizeof (double) + 1);
1157                           int length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val);
1158
1159                           for (c_net = 0; c_net <= length + 1; c_net ++)
1160                           {
1161                                 if (ind[c_net] == mlp->p.r_quota[prev_value])
1162                                         break; /* Found index for old network */
1163                           }
1164                           val[c_net] = 0.0;
1165                                 glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val);
1166                                 /* Set updated column */
1167                                 ind[c_net] = mlp->p.r_quota[new_value];
1168                                 val[c_net] = 1.0;
1169                                 glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val);
1170                           GNUNET_free (ind);
1171                           GNUNET_free (val);
1172
1173                           rows = glp_get_num_rows(mlp->p.prob);
1174                           ind = GNUNET_malloc (rows * sizeof (int) + 1);
1175                           val = GNUNET_malloc (rows * sizeof (double) + 1);
1176                           length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val);
1177
1178                           for (c_net = 0; c_net <= length + 1; c_net ++)
1179                           {
1180                                 if (ind[c_net] == mlp->p.r_quota[prev_value])
1181                                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Removing old network index [%u] == [%f]\n",ind[c_net],val[c_net]);
1182                                 if (ind[c_net] == mlp->p.r_quota[new_value])
1183                                 {
1184                                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Setting new network index [%u] == [%f]\n",ind[c_net],val[c_net]);
1185                                         break;
1186                                 }
1187                           }
1188                           GNUNET_free (ind);
1189                           GNUNET_free (val);
1190                           mlp->mlp_prob_changed = GNUNET_YES;
1191                                 continue;
1192                 }
1193
1194
1195                 /* Find index for this ATS type */
1196           for (c_cmp = 0; c_cmp < mlp->pv.m_q; c_cmp++)
1197           {
1198             if (type == mlp->pv.q[c_cmp])
1199             {
1200                 type_index = c_cmp;
1201               break;
1202             }
1203           }
1204           if (-1 == type_index)
1205                 continue; /* quality index not found */
1206
1207           /* Get average queue index */
1208           avg_index = mlpi->q_avg_i[type_index];
1209
1210           /* Update averaging queue */
1211           new_value = get_performance_info (address, type);
1212       LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating peer `%s': `%s' from %u to %u\n",
1213         GNUNET_i2s (&address->peer),
1214         mlp_ats_to_string(mlp->pv.q[type_index]), prev_value, new_value);
1215           GNUNET_assert (GNUNET_ATS_VALUE_UNDEFINED != new_value);
1216           mlpi->q[type_index][avg_index] = new_value;
1217
1218           /* Update averaging index */
1219       if (mlpi->q_avg_i[type_index] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
1220         mlpi->q_avg_i[type_index] ++;
1221       else
1222         mlpi->q_avg_i[type_index] = 0;
1223
1224           /* Update average depending on ATS type */
1225       switch (type)
1226       {
1227         case GNUNET_ATS_QUALITY_NET_DISTANCE:
1228         case GNUNET_ATS_QUALITY_NET_DELAY:
1229                 c_queue_entries = 0;
1230                 avg = 0;
1231           for (c_queue_it = 0; c_queue_it < MLP_AVERAGING_QUEUE_LENGTH; c_queue_it++)
1232           {
1233             if (mlpi->q[type_index][c_queue_it] != MLP_NaN)
1234             {
1235               queue = mlpi->q[type_index] ;
1236               avg += queue[c_queue_it];
1237               c_queue_entries ++;
1238             }
1239           }
1240           if ((c_queue_entries > 0) && (avg > 0))
1241             /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1242             mlpi->q_averaged[type_index] = (double) c_queue_entries / avg;
1243           else
1244             mlpi->q_averaged[type_index] = 0.0;
1245
1246           LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating peer `%s': `%s' average sum of %u elements == %f, average == %f, weight == %f\n",
1247             GNUNET_i2s (&address->peer),
1248             mlp_ats_to_string(mlp->pv.q[type_index]),
1249             c_queue_entries,
1250             avg,
1251             avg / (double) c_queue_entries,
1252             mlpi->q_averaged[type_index]);
1253           qual_changed = GNUNET_YES;
1254                 break;
1255         default:
1256                 GNUNET_break (0);
1257                 LOG (GNUNET_ERROR_TYPE_DEBUG, _("Update for ATS type `%s' not implemented!\n"),
1258                                 mlp_ats_to_string(type));
1259       }
1260   }
1261
1262   /* Changed, but quality will be automatically set during rebuild */
1263   if ((GNUNET_YES == mlp->mlp_prob_changed) &&
1264           (GNUNET_YES == mlp->mlp_auto_solve))
1265   {
1266                 GAS_mlp_solve_problem (mlp, addresses);
1267                 return;
1268   }
1269
1270   /* Update problem matrix if required */
1271   if (GNUNET_NO == qual_changed)
1272         return;
1273
1274   /* Address not yet included in matrix */
1275   if (MLP_UNDEFINED == mlpi->c_b)
1276         return;
1277
1278   /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index]
1279    * Get column mlpi->c_b */
1280   rows = glp_get_num_rows(mlp->p.prob);
1281   ind = GNUNET_malloc (rows * sizeof (int) + 1);
1282   val = GNUNET_malloc (rows * sizeof (double) + 1);
1283   int length = glp_get_mat_col (mlp->p.prob, mlpi->c_b, ind, val);
1284
1285         for (c_qual = 0; c_qual < mlp->pv.m_q; c_qual++)
1286         {
1287                 for (c_row = 0; c_row <= length; c_row ++)
1288                 {
1289                                 if (ind[c_row] == mlp->p.r_q[c_qual])
1290                                         val[c_row] = mlpi->q_averaged[c_qual];
1291                 }
1292         }
1293         /* Set updated column */
1294         glp_set_mat_col (mlp->p.prob, mlpi->c_b, length, ind, val);
1295   GNUNET_free (ind);
1296   GNUNET_free (val);
1297   mlp->mlp_prob_updated = GNUNET_YES;
1298 }
1299
1300 /**
1301  * Updates a single address in the MLP problem
1302  *
1303  * If the address did not exist before in the problem:
1304  * The MLP problem has to be recreated and the problem has to be resolved
1305  *
1306  * ATS performance information in address are already updated, delta + previous
1307  * values are included in atsi_prev (value GNUNET_ATS_VALUE_UNDEFINED if not existing before)
1308  *
1309  * Otherwise the addresses' values can be updated and the existing base can
1310  * be reused
1311  *
1312  * @param solver the solver Handle
1313  * @param addresses the address hashmap containing all addresses
1314  * @param address the update address
1315  * @param session the new session (if changed otherwise current)
1316  * @param in_use the new address in use state (if changed otherwise current)
1317  * @param atsi_prev ATS information updated + previous values, GNUNET_ATS_VALUE_UNDEFINED if not existing before
1318  * @param atsi_count_prev number of atsi values updated
1319  */
1320 void
1321 GAS_mlp_address_update (void *solver,
1322                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
1323                         struct ATS_Address *address,
1324                         uint32_t session,
1325                         int in_use,
1326                         const struct GNUNET_ATS_Information *atsi_prev,
1327                         uint32_t atsi_count_prev)
1328 {
1329         struct ATS_Peer *p;
1330         struct GAS_MLP_Handle *mlp = solver;
1331         struct MLP_information *mlpi = address->solver_information;
1332
1333         GNUNET_assert (NULL != solver);
1334         GNUNET_assert (NULL != addresses);
1335         GNUNET_assert (NULL != address);
1336         GNUNET_assert ((NULL != atsi_prev) || (0 == atsi_count_prev));
1337
1338   if (NULL == mlpi)
1339   {
1340       LOG (GNUNET_ERROR_TYPE_ERROR, _("Updating address for peer `%s' not added before\n"), GNUNET_i2s(&address->peer));
1341       return;
1342   }
1343         mlp_update_quality (mlp, addresses, address, atsi_prev, atsi_count_prev);
1344
1345   /* Is this peer included in the problem? */
1346   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1347   {
1348     LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1349         return;
1350   }
1351         LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1352
1353         /* Problem size changed: new address for peer with pending request */
1354         mlp->mlp_prob_updated = GNUNET_YES;
1355         if (GNUNET_YES == mlp->mlp_auto_solve)
1356                 GAS_mlp_solve_problem (solver, addresses);
1357   return;
1358 }
1359
1360 /**
1361  * Deletes a single address in the MLP problem
1362  *
1363  * The MLP problem has to be recreated and the problem has to be resolved
1364  *
1365  * @param solver the MLP Handle
1366  * @param addresses the address hashmap
1367  *        the address has to be already removed from the hashmap
1368  * @param address the address to delete
1369  * @param session_only delete only session not whole address
1370  */
1371 void
1372 GAS_mlp_address_delete (void *solver,
1373     struct GNUNET_CONTAINER_MultiHashMap * addresses,
1374     struct ATS_Address *address,
1375     int session_only)
1376 {
1377         struct ATS_Peer *p;
1378         struct GAS_MLP_Handle *mlp = solver;
1379         struct MLP_information *mlpi;
1380
1381         GNUNET_assert (NULL != solver);
1382         GNUNET_assert (NULL != addresses);
1383         GNUNET_assert (NULL != address);
1384
1385         mlpi = address->solver_information;
1386
1387         if (NULL != mlpi)
1388         {
1389                         GNUNET_free (mlpi);
1390                         address->solver_information = NULL;
1391         }
1392
1393   /* Is this peer included in the problem? */
1394   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1395   {
1396     LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1397         return;
1398   }
1399         LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1400
1401         /* Problem size changed: new address for peer with pending request */
1402         mlp->mlp_prob_changed = GNUNET_YES;
1403         if (GNUNET_YES == mlp->mlp_auto_solve)
1404                 GAS_mlp_solve_problem (solver, addresses);
1405   return;
1406 }
1407
1408
1409 /**
1410  * Find the active address in the set of addresses of a peer
1411  * @param cls destination
1412  * @param key peer id
1413  * @param value address
1414  * @return GNUNET_OK
1415  */
1416 static int
1417 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1418 {
1419
1420   struct ATS_Address *aa = (struct ATS_Address *) cls;
1421   struct ATS_Address *addr = value;
1422   struct MLP_information *mlpi = addr->solver_information;
1423   if (mlpi == NULL)
1424     return GNUNET_YES;
1425   if (mlpi->n == GNUNET_YES)
1426   {
1427     aa = addr;
1428       aa->assigned_bw_in = mlpi->b_in;
1429       aa->assigned_bw_out = mlpi->b_out;
1430     return GNUNET_NO;
1431   }
1432   return GNUNET_YES;
1433 }
1434
1435
1436 /**
1437  * Get the preferred address for a specific peer
1438  *
1439  * @param solver the MLP Handle
1440  * @param addresses address hashmap
1441  * @param peer the peer
1442  * @return suggested address
1443  */
1444 const struct ATS_Address *
1445 GAS_mlp_get_preferred_address (void *solver,
1446                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
1447                                const struct GNUNET_PeerIdentity *peer)
1448 {
1449   struct GAS_MLP_Handle *mlp = solver;
1450   struct ATS_Peer *p;
1451   struct ATS_Address *res = NULL;
1452
1453   GNUNET_assert (NULL != solver);
1454   GNUNET_assert (NULL != addresses);
1455   GNUNET_assert (NULL != peer);
1456
1457   LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n",
1458                 GNUNET_i2s (peer));
1459
1460   /* Is this peer included in the problem? */
1461   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey)))
1462   {
1463           LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding peer `%s' to list of peers with requests\n",
1464                         GNUNET_i2s (peer));
1465
1466           p = GNUNET_malloc (sizeof (struct ATS_Peer));
1467           p->id = (*peer);
1468           p->f = DEFAULT_PEER_PREFERENCE;
1469           GNUNET_CONTAINER_multihashmap_put (mlp->peers, &peer->hashPubKey, p, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
1470
1471           /* Added new peer, we have to rebuild problem before solving */
1472           mlp->mlp_prob_changed = GNUNET_YES;
1473   }
1474   if (GNUNET_YES == mlp->mlp_auto_solve)
1475         GAS_mlp_solve_problem (mlp, addresses);
1476
1477   /* Get prefered address */
1478   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
1479                                                                                                                                                                                 mlp_get_preferred_address_it, res);
1480
1481   return res;
1482 }
1483
1484
1485 /**
1486  * Stop notifying about address and bandwidth changes for this peer
1487  *
1488  * @param solver the MLP handle
1489  * @param addresses address hashmap
1490  * @param peer the peer
1491  */
1492 void
1493 GAS_mlp_stop_get_preferred_address (void *solver,
1494                                      struct GNUNET_CONTAINER_MultiHashMap *addresses,
1495                                      const struct GNUNET_PeerIdentity *peer)
1496 {
1497   struct GAS_MLP_Handle *mlp = solver;
1498   struct ATS_Peer *p = NULL;
1499
1500   GNUNET_assert (NULL != solver);
1501   GNUNET_assert (NULL != addresses);
1502   GNUNET_assert (NULL != peer);
1503
1504   if (NULL != (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey)))
1505   {
1506         GNUNET_CONTAINER_multihashmap_remove (mlp->peers, &peer->hashPubKey, p);
1507         GNUNET_free (p);
1508   }
1509 }
1510
1511
1512 /**
1513  * Changes the preferences for a peer in the MLP problem
1514  *
1515  * @param solver the MLP Handle
1516  * @param client client
1517  * @param peer the peer
1518  * @param kind the kind to change the preference
1519  * @param score the score
1520  */
1521 void
1522 GAS_mlp_address_change_preference (void *solver,
1523                                    void *client,
1524                                    const struct GNUNET_PeerIdentity *peer,
1525                                    enum GNUNET_ATS_PreferenceKind kind,
1526                                    float score)
1527 {
1528   //struct GAS_MLP_Handle *mlp = solver;
1529
1530   LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n",
1531                 GNUNET_i2s(peer));
1532
1533   return;
1534 #if 0
1535   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1536
1537   //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1538   //FIXME to finish implementation
1539   /* Here we have to do the matching */
1540 #endif
1541 }
1542
1543
1544 static int
1545 mlp_free_peers (void *cls, const struct GNUNET_HashCode *key, void *value)
1546 {
1547         struct GNUNET_CONTAINER_MultiHashMap *map = cls;
1548         struct ATS_Peer *p = value;
1549
1550         GNUNET_CONTAINER_multihashmap_remove (map, key, value);
1551         GNUNET_free (p);
1552
1553         return GNUNET_OK;
1554 }
1555
1556
1557 /**
1558  * Shutdown the MLP problem solving component
1559  *
1560  * @param solver the solver handle
1561  */
1562 void
1563 GAS_mlp_done (void *solver)
1564 {
1565   struct GAS_MLP_Handle *mlp = solver;
1566   GNUNET_assert (mlp != NULL);
1567
1568   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n");
1569   mlp_delete_problem (mlp);
1570
1571   GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &mlp_free_peers, mlp->peers);
1572   GNUNET_CONTAINER_multihashmap_destroy (mlp->peers);
1573   mlp->peers = NULL;
1574
1575   /* Clean up GLPK environment */
1576   glp_free_env();
1577   GNUNET_free (mlp);
1578
1579   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n");
1580 }
1581
1582
1583 /**
1584  * Init the MLP problem solving component
1585  *
1586  * @param cfg the GNUNET_CONFIGURATION_Handle handle
1587  * @param stats the GNUNET_STATISTICS handle
1588  * @param network array of GNUNET_ATS_NetworkType with length dest_length
1589  * @param out_dest array of outbound quotas
1590  * @param in_dest array of outbound quota
1591  * @param dest_length array length for quota arrays
1592  * @param bw_changed_cb callback for changed bandwidth amounts
1593  * @param bw_changed_cb_cls cls for callback
1594  * @return struct GAS_MLP_Handle on success, NULL on fail
1595  */
1596 void *
1597 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1598               const struct GNUNET_STATISTICS_Handle *stats,
1599               int *network,
1600               unsigned long long *out_dest,
1601               unsigned long long *in_dest,
1602               int dest_length,
1603               GAS_bandwidth_changed_cb bw_changed_cb,
1604               void *bw_changed_cb_cls)
1605 {
1606   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1607
1608   double D;
1609   double R;
1610   double U;
1611   unsigned long long tmp;
1612   unsigned int b_min;
1613   unsigned int n_min;
1614   int c;
1615   int c2;
1616   int found;
1617
1618   struct GNUNET_TIME_Relative max_duration;
1619   long long unsigned int max_iterations;
1620
1621   /* Init GLPK environment */
1622   int res = glp_init_env();
1623   switch (res) {
1624     case 0:
1625         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1626           "initialization successful");
1627       break;
1628     case 1:
1629         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1630           "environment is already initialized");
1631       break;
1632     case 2:
1633         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1634           "initialization failed (insufficient memory)");
1635       GNUNET_free(mlp);
1636       return NULL;
1637       break;
1638     case 3:
1639         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1640           "initialization failed (unsupported programming model)");
1641       GNUNET_free(mlp);
1642       return NULL;
1643       break;
1644     default:
1645       break;
1646   }
1647
1648
1649   mlp->pv.BIG_M = (double) BIG_M_VALUE;
1650
1651   /* Get timeout for iterations */
1652   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MLP_MAX_DURATION", &max_duration))
1653   {
1654     max_duration = MLP_MAX_EXEC_DURATION;
1655   }
1656
1657   /* Get maximum number of iterations */
1658   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations))
1659   {
1660     max_iterations = MLP_MAX_ITERATIONS;
1661   }
1662
1663   /* Get diversity coefficient from configuration */
1664   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1665                                                       "MLP_COEFFICIENT_D",
1666                                                       &tmp))
1667     D = (double) tmp / 100;
1668   else
1669     D = DEFAULT_D;
1670
1671   /* Get proportionality coefficient from configuration */
1672   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1673                                                       "MLP_COEFFICIENT_R",
1674                                                       &tmp))
1675     R = (double) tmp / 100;
1676   else
1677     R = DEFAULT_R;
1678
1679   /* Get utilization coefficient from configuration */
1680   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1681                                                       "MLP_COEFFICIENT_U",
1682                                                       &tmp))
1683     U = (double) tmp / 100;
1684   else
1685     U = DEFAULT_U;
1686
1687   /* Get quality metric coefficients from configuration */
1688   int i_delay = MLP_NaN;
1689   int i_distance = MLP_NaN;
1690   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1691   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1692   {
1693     /* initialize quality coefficients with default value 1.0 */
1694                 mlp->pv.co_Q[c] = DEFAULT_QUALITY;
1695
1696     mlp->pv.q[c] = q[c];
1697     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1698       i_delay = c;
1699     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1700       i_distance = c;
1701   }
1702
1703   if ((i_delay != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1704                                                       "MLP_COEFFICIENT_QUALITY_DELAY",
1705                                                       &tmp)))
1706
1707         mlp->pv.co_Q[i_delay] = (double) tmp / 100;
1708   else
1709         mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY;
1710
1711   if ((i_distance != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1712                                                       "MLP_COEFFICIENT_QUALITY_DISTANCE",
1713                                                       &tmp)))
1714         mlp->pv.co_Q[i_distance] = (double) tmp / 100;
1715   else
1716         mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY;
1717
1718   /* Get minimum bandwidth per used address from configuration */
1719   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1720                                                       "MLP_MIN_BANDWIDTH",
1721                                                       &tmp))
1722     b_min = tmp;
1723   else
1724   {
1725     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1726   }
1727
1728   /* Get minimum number of connections from configuration */
1729   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1730                                                       "MLP_MIN_CONNECTIONS",
1731                                                       &tmp))
1732     n_min = tmp;
1733   else
1734     n_min = DEFAULT_MIN_CONNECTIONS;
1735
1736   /* Init network quotas */
1737   int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
1738   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1739   {
1740                 found = GNUNET_NO;
1741           for (c2 = 0; c2 < dest_length; c2++)
1742           {
1743                         if (quotas[c] == network[c2])
1744                   {
1745                                         mlp->pv.quota_index[c] = network[c2];
1746                                         mlp->pv.quota_out[c] = out_dest[c2];
1747                       mlp->pv.quota_in[c] = in_dest[c2];
1748                       found = GNUNET_YES;
1749                       LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n",
1750                                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1751                                                                 mlp->pv.quota_out[c],
1752                                                                 mlp->pv.quota_in[c]);
1753                       break;
1754                   }
1755           }
1756
1757       /* Check if defined quota could make problem unsolvable */
1758       if ((n_min * b_min) > mlp->pv.quota_out[c])
1759       {
1760         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
1761                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1762                         mlp->pv.quota_out[c],
1763                         (n_min * b_min));
1764         mlp->pv.quota_out[c] = (n_min * b_min);
1765       }
1766       if ((n_min * b_min) > mlp->pv.quota_in[c])
1767       {
1768         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
1769                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1770                         mlp->pv.quota_in[c],
1771                         (n_min * b_min));
1772         mlp->pv.quota_in[c] = (n_min * b_min);
1773       }
1774
1775       /* Check if bandwidth is too big to make problem solvable */
1776       if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
1777       {
1778         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
1779                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1780                         mlp->pv.quota_out[c],
1781                         mlp->pv.BIG_M);
1782         mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
1783       }
1784       if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
1785       {
1786         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
1787                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1788                         mlp->pv.quota_in[c],
1789                         mlp->pv.BIG_M);
1790         mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
1791       }
1792
1793           if (GNUNET_NO == found)
1794                         {
1795                 mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1796                 mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1797                                 LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"),
1798                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
1799                                                 mlp->pv.quota_in[c],
1800                                                 mlp->pv.quota_out[c]);
1801                         }
1802   }
1803
1804   /* Assign options to handle */
1805   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1806   mlp->bw_changed_cb = bw_changed_cb;
1807   mlp->bw_changed_cb_cls = bw_changed_cb_cls;
1808   /* Setting MLP Input variables */
1809   mlp->pv.co_D = D;
1810   mlp->pv.co_R = R;
1811   mlp->pv.co_U = U;
1812   mlp->pv.b_min = b_min;
1813   mlp->pv.n_min = n_min;
1814   mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount;
1815   mlp->write_mip_mps = GNUNET_NO;
1816   mlp->write_mip_sol = GNUNET_NO;
1817   mlp->mlp_prob_changed = GNUNET_NO;
1818   mlp->mlp_prob_updated = GNUNET_NO;
1819   mlp->mlp_auto_solve = GNUNET_YES;
1820   mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO);
1821
1822   /* Setup GLPK */
1823   /* Redirect GLPK output to GNUnet logging */
1824   glp_term_hook (&mlp_term_hook, (void *) mlp);
1825
1826   /* Init LP solving parameters */
1827   glp_init_smcp(&mlp->control_param_lp);
1828   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1829 #if VERBOSE_GLPK
1830   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1831 #endif
1832   mlp->control_param_lp.it_lim = max_iterations;
1833   mlp->control_param_lp.tm_lim = max_duration.rel_value;
1834
1835   /* Init MLP solving parameters */
1836   glp_init_iocp(&mlp->control_param_mlp);
1837   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1838 #if VERBOSE_GLPK
1839   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1840 #endif
1841   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1842
1843   LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
1844
1845   return mlp;
1846 }
1847
1848 /* end of gnunet-service-ats_addresses_mlp.c */