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