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 #define WRITE_MLP GNUNET_NO
 139 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_YES
 140 #define VERBOSE_GLPK GNUNET_NO
 141
 142 /**
 143  * Intercept GLPK terminal output
 144  * @param info the mlp handle
 145  * @param s the string to print
 146  * @return 0: glpk prints output on terminal, 0 != surpress output
 147  */
 148 static int
 149 mlp_term_hook (void *info, const char *s)
 150 {
 151   /* Not needed atm struct MLP_information *mlp = info; */
 152   LOG (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
 153   return 1;
 154 }
 155
 156
 157
 158
 159 /**
 160  * Delete the MLP problem and free the constrain matrix
 161  *
 162  * @param mlp the MLP handle
 163  */
 164 static void
 165 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 166 {
 167   if (mlp != NULL)
 168   {
 169     if (mlp->p.prob != NULL)
 170       glp_delete_prob(mlp->p.prob);
 171
 172     /* delete row index */
 173     if (mlp->p.ia != NULL)
 174     {
 175       GNUNET_free (mlp->p.ia);
 176       mlp->p.ia = NULL;
 177     }
 178
 179     /* delete column index */
 180     if (mlp->p.ja != NULL)
 181     {
 182       GNUNET_free (mlp->p.ja);
 183       mlp->p.ja = NULL;
 184     }
 185
 186     /* delete coefficients */
 187     if (mlp->p.ar != NULL)
 188     {
 189       GNUNET_free (mlp->p.ar);
 190       mlp->p.ar = NULL;
 191     }
 192     mlp->p.ci = 0;
 193     mlp->p.prob = NULL;
 194   }
 195 }
 196
 197
 198 /**
 199  * Translate ATS properties to text
 200  * Just intended for debugging
 201  *
 202  * @param ats_index the ATS index
 203  * @return string with result
 204  */
 205 const char *
 206 mlp_ats_to_string (int ats_index)
 207 {
 208   switch (ats_index) {
 209     case GNUNET_ATS_ARRAY_TERMINATOR:
 210       return "GNUNET_ATS_ARRAY_TERMINATOR";
 211     case GNUNET_ATS_UTILIZATION_UP:
 212       return "GNUNET_ATS_UTILIZATION_UP";
 213     case GNUNET_ATS_UTILIZATION_DOWN:
 214       return "GNUNET_ATS_UTILIZATION_DOWN";
 215     case GNUNET_ATS_COST_LAN:
 216       return "GNUNET_ATS_COST_LAN";
 217     case GNUNET_ATS_COST_WAN:
 218       return "GNUNET_ATS_COST_LAN";
 219     case GNUNET_ATS_COST_WLAN:
 220       return "GNUNET_ATS_COST_WLAN";
 221     case GNUNET_ATS_NETWORK_TYPE:
 222       return "GNUNET_ATS_NETWORK_TYPE";
 223     case GNUNET_ATS_QUALITY_NET_DELAY:
 224       return "GNUNET_ATS_QUALITY_NET_DELAY";
 225     case GNUNET_ATS_QUALITY_NET_DISTANCE:
 226       return "GNUNET_ATS_QUALITY_NET_DISTANCE";
 227     default:
 228       GNUNET_break (0);
 229       return "unknown";
 230   }
 231 }
 232
 233 #if 0
 234
 235 /**
 236  * Translate glpk solver error codes to text
 237  * @param retcode return code
 238  * @return string with result
 239  */
 240 const char *
 241 mlp_solve_to_string (int retcode)
 242 {
 243   switch (retcode) {
 244     case 0:
 245       return "ok";
 246     case GLP_EBADB:
 247       return "invalid basis";
 248     case GLP_ESING:
 249       return "singular matrix";
 250     case GLP_ECOND:
 251       return "ill-conditioned matrix";
 252     case GLP_EBOUND:
 253       return "invalid bounds";
 254     case GLP_EFAIL:
 255       return "solver failed";
 256     case GLP_EOBJLL:
 257       return "objective lower limit reached";
 258     case GLP_EOBJUL:
 259       return "objective upper limit reached";
 260     case GLP_EITLIM:
 261       return "iteration limit exceeded";
 262     case GLP_ETMLIM:
 263       return "time limit exceeded";
 264     case GLP_ENOPFS:
 265       return "no primal feasible solution";
 266     case GLP_EROOT:
 267       return "root LP optimum not provided";
 268     case GLP_ESTOP:
 269       return "search terminated by application";
 270     case GLP_EMIPGAP:
 271       return "relative mip gap tolerance reached";
 272     case GLP_ENOFEAS:
 273       return "no dual feasible solution";
 274     case GLP_ENOCVG:
 275       return "no convergence";
 276     case GLP_EINSTAB:
 277       return "numerical instability";
 278     case GLP_EDATA:
 279       return "invalid data";
 280     case GLP_ERANGE:
 281       return "result out of range";
 282     default:
 283       GNUNET_break (0);
 284       return "unknown error";
 285   }
 286 }
 287
 288
 289 /**
 290  * Translate glpk status error codes to text
 291  * @param retcode return code
 292  * @return string with result
 293  */
 294 const char *
 295 mlp_status_to_string (int retcode)
 296 {
 297   switch (retcode) {
 298     case GLP_UNDEF:
 299       return "solution is undefined";
 300     case GLP_FEAS:
 301       return "solution is feasible";
 302     case GLP_INFEAS:
 303       return "solution is infeasible";
 304     case GLP_NOFEAS:
 305       return "no feasible solution exists";
 306     case GLP_OPT:
 307       return "solution is optimal";
 308     case GLP_UNBND:
 309       return "solution is unbounded";
 310     default:
 311       GNUNET_break (0);
 312       return "unknown error";
 313   }
 314 }
 315
 316
 317 /**
 318  * Find a peer in the DLL
 319  *
 320  * @param mlp the mlp handle
 321  * @param peer the peer to find
 322  * @return the peer struct
 323  */
 324 static struct ATS_Peer *
 325 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
 326 {
 327   struct ATS_Peer *res = mlp->peer_head;
 328   while (res != NULL)
 329   {
 330     if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
 331       break;
 332     res = res->next;
 333   }
 334   return res;
 335 }
 336
 337
 338
 339 #if 0
 340 /**
 341  * Find the required ATS information for an address
 342  *
 343  * @param addr the address
 344  * @param ats_index the desired ATS index
 345  *
 346  * @return the index on success, otherwise GNUNET_SYSERR
 347  */
 348 static int
 349 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
 350 {
 351   struct GNUNET_ATS_Information * ats = addr->ats;
 352   int c = 0;
 353   int found = GNUNET_NO;
 354   for (c = 0; c < addr->ats_count; c++)
 355   {
 356     if (ats[c].type == ats_index)
 357     {
 358       found = GNUNET_YES;
 359       break;
 360     }
 361   }
 362   if (found == GNUNET_YES)
 363     return c;
 364   else
 365     return GNUNET_SYSERR;
 366 }
 367 #endif
 368
 369 /**
 370  * Solves the LP problem
 371  *
 372  * @param mlp the MLP Handle
 373  * @param s_ctx context to return results
 374  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 375  */
 376 static int
 377 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
 378 {
 379   int res;
 380   struct GNUNET_TIME_Relative duration;
 381   struct GNUNET_TIME_Absolute end;
 382   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 383
 384   /* LP presolver?
 385    * Presolver is required if the problem was modified and an existing
 386    * valid basis is now invalid */
 387   if (mlp->presolver_required == GNUNET_YES)
 388     mlp->control_param_lp.presolve = GLP_ON;
 389   else
 390     mlp->control_param_lp.presolve = GLP_OFF;
 391
 392   /* Solve LP problem to have initial valid solution */
 393 lp_solv:
 394   res = glp_simplex(mlp->prob, &mlp->control_param_lp);
 395   if (res == 0)
 396   {
 397     /* The LP problem instance has been successfully solved. */
 398   }
 399   else if (res == GLP_EITLIM)
 400   {
 401     /* simplex iteration limit has been exceeded. */
 402     // TODO Increase iteration limit?
 403   }
 404   else if (res == GLP_ETMLIM)
 405   {
 406     /* Time limit has been exceeded.  */
 407     // TODO Increase time limit?
 408   }
 409   else
 410   {
 411     /* Problem was ill-defined, retry with presolver */
 412     if (mlp->presolver_required == GNUNET_NO)
 413     {
 414       mlp->presolver_required = GNUNET_YES;
 415       goto lp_solv;
 416     }
 417     else
 418     {
 419       /* Problem was ill-defined, no way to handle that */
 420       GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
 421           "ats-mlp",
 422           "Solving LP problem failed: %i %s\n", res, mlp_solve_to_string(res));
 423       return GNUNET_SYSERR;
 424     }
 425   }
 426
 427   end = GNUNET_TIME_absolute_get ();
 428   duration = GNUNET_TIME_absolute_get_difference (start, end);
 429   mlp->lp_solved++;
 430   mlp->lp_total_duration += duration.rel_value;
 431   s_ctx->lp_duration = duration;
 432
 433   GNUNET_STATISTICS_update (mlp->stats,"# LP problem solved", 1, GNUNET_NO);
 434   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time (ms)", duration.rel_value, GNUNET_NO);
 435   GNUNET_STATISTICS_set (mlp->stats,"# LP execution time average (ms)",
 436                          mlp->lp_total_duration / mlp->lp_solved,  GNUNET_NO);
 437
 438   /* Analyze problem status  */
 439   res = glp_get_status (mlp->prob);
 440   switch (res) {
 441     /* solution is optimal */
 442     case GLP_OPT:
 443     /* solution is feasible */
 444     case GLP_FEAS:
 445       break;
 446
 447     /* Problem was ill-defined, no way to handle that */
 448     default:
 449       GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
 450           "ats-mlp",
 451           "Solving LP problem failed, no solution: %s\n", mlp_status_to_string(res));
 452       return GNUNET_SYSERR;
 453       break;
 454   }
 455
 456   /* solved sucessfully, no presolver required next time */
 457   mlp->presolver_required = GNUNET_NO;
 458
 459   return GNUNET_OK;
 460 }
 461
 462
 463 /**
 464  * Solves the MLP problem
 465  *
 466  * @param mlp the MLP Handle
 467  * @param s_ctx context to return results
 468  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 469  */
 470 int
 471 mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *s_ctx)
 472 {
 473   int res;
 474   struct GNUNET_TIME_Relative duration;
 475   struct GNUNET_TIME_Absolute end;
 476   struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
 477
 478   /* solve MLP problem */
 479   res = glp_intopt(mlp->prob, &mlp->control_param_mlp);
 480
 481   if (res == 0)
 482   {
 483     /* The MLP problem instance has been successfully solved. */
 484   }
 485   else if (res == GLP_EITLIM)
 486   {
 487     /* simplex iteration limit has been exceeded. */
 488     // TODO Increase iteration limit?
 489   }
 490   else if (res == GLP_ETMLIM)
 491   {
 492     /* Time limit has been exceeded.  */
 493     // TODO Increase time limit?
 494   }
 495   else
 496   {
 497     /* Problem was ill-defined, no way to handle that */
 498     GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
 499         "ats-mlp",
 500         "Solving MLP problem failed:  %s\n", mlp_solve_to_string(res));
 501     return GNUNET_SYSERR;
 502   }
 503
 504   end = GNUNET_TIME_absolute_get ();
 505   duration = GNUNET_TIME_absolute_get_difference (start, end);
 506   mlp->mlp_solved++;
 507   mlp->mlp_total_duration += duration.rel_value;
 508   s_ctx->mlp_duration = duration;
 509
 510   GNUNET_STATISTICS_update (mlp->stats,"# MLP problem solved", 1, GNUNET_NO);
 511   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time (ms)", duration.rel_value, GNUNET_NO);
 512   GNUNET_STATISTICS_set (mlp->stats,"# MLP execution time average (ms)",
 513                          mlp->mlp_total_duration / mlp->mlp_solved,  GNUNET_NO);
 514
 515   /* Analyze problem status  */
 516   res = glp_mip_status(mlp->prob);
 517   switch (res) {
 518     /* solution is optimal */
 519     case GLP_OPT:
 520     /* solution is feasible */
 521     case GLP_FEAS:
 522       break;
 523
 524     /* Problem was ill-defined, no way to handle that */
 525     default:
 526       GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG,
 527           "ats-mlp",
 528           "Solving MLP problem failed, %s\n\n", mlp_status_to_string(res));
 529       return GNUNET_SYSERR;
 530       break;
 531   }
 532
 533   return GNUNET_OK;
 534 }
 535
 536 int GAS_mlp_solve_problem (void *solver, struct GAS_MLP_SolutionContext *ctx);
 537
 538
 539 static void
 540 mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 541 {
 542   struct GAS_MLP_Handle *mlp = cls;
 543   struct GAS_MLP_SolutionContext ctx;
 544
 545   mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
 546
 547   if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 548     return;
 549
 550   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
 551
 552   if (mlp->addresses_in_problem != 0)
 553     GAS_mlp_solve_problem(mlp, &ctx);
 554 }
 555
 556
 557
 558
 559 static void
 560 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
 561 {
 562   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
 563       GNUNET_i2s (&address->peer));
 564
 565   GNUNET_assert (NULL != address);
 566   GNUNET_assert (NULL != address->solver_information);
 567 //  GNUNET_assert (NULL != address->ats);
 568
 569   struct MLP_information *mlpi = address->solver_information;
 570   //struct GNUNET_ATS_Information *ats = address->ats;
 571   GNUNET_assert (mlpi != NULL);
 572
 573   int c;
 574   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 575   {
 576
 577     /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */
 578     int index = GNUNET_SYSERR;
 579
 580     if (index == GNUNET_SYSERR)
 581       continue;
 582     /* FIXME
 583     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
 584         GNUNET_i2s (&address->peer),
 585         mlp_ats_to_string(mlp->q[c]),
 586         (double) ats[index].value);
 587
 588     int i = mlpi->q_avg_i[c];*/
 589     double * qp = mlpi->q[c];
 590     /* FIXME
 591     qp[i] = (double) ats[index].value;
 592     */
 593
 594     int t;
 595     for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
 596     {
 597       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
 598         GNUNET_i2s (&address->peer),
 599         mlp_ats_to_string(mlp->q[c]),
 600         t,
 601         qp[t]);
 602     }
 603
 604     if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
 605       mlpi->q_avg_i[c] ++;
 606     else
 607       mlpi->q_avg_i[c] = 0;
 608
 609
 610     int c2;
 611     int c3;
 612     double avg = 0.0;
 613     switch (mlp->q[c])
 614     {
 615       case GNUNET_ATS_QUALITY_NET_DELAY:
 616         c3 = 0;
 617         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
 618         {
 619           if (mlpi->q[c][c2] != -1)
 620           {
 621             double * t2 = mlpi->q[c] ;
 622             avg += t2[c2];
 623             c3 ++;
 624           }
 625         }
 626         if ((c3 > 0) && (avg > 0))
 627           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
 628           mlpi->q_averaged[c] = (double) c3 / avg;
 629         else
 630           mlpi->q_averaged[c] = 0.0;
 631
 632         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
 633           GNUNET_i2s (&address->peer),
 634           mlp_ats_to_string(mlp->q[c]),
 635           avg,
 636           avg / (double) c3,
 637           mlpi->q_averaged[c]);
 638
 639         break;
 640       case GNUNET_ATS_QUALITY_NET_DISTANCE:
 641         c3 = 0;
 642         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
 643         {
 644           if (mlpi->q[c][c2] != -1)
 645           {
 646             double * t2 = mlpi->q[c] ;
 647             avg += t2[c2];
 648             c3 ++;
 649           }
 650         }
 651         if ((c3 > 0) && (avg > 0))
 652           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
 653           mlpi->q_averaged[c] = (double) c3 / avg;
 654         else
 655           mlpi->q_averaged[c] = 0.0;
 656
 657         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
 658           GNUNET_i2s (&address->peer),
 659           mlp_ats_to_string(mlp->q[c]),
 660           avg,
 661           avg / (double) c3,
 662           mlpi->q_averaged[c]);
 663
 664         break;
 665       default:
 666         break;
 667     }
 668
 669     if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
 670     {
 671
 672       /* Get current number of columns */
 673       int found = GNUNET_NO;
 674       int cols = glp_get_num_cols(mlp->prob);
 675       int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
 676       double *val = GNUNET_malloc (cols * sizeof (double) + 1);
 677
 678       /* Get the matrix row of quality */
 679       int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
 680       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
 681       int c4;
 682       /* Get the index if matrix row of quality */
 683       for (c4 = 1; c4 <= length; c4++ )
 684       {
 685         if (mlpi->c_b == ind[c4])
 686         {
 687           /* Update the value */
 688           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
 689               mlp_ats_to_string(mlp->q[c]),
 690               glp_get_col_name (mlp->prob, ind[c4]),
 691               glp_get_row_name (mlp->prob, mlp->r_q[c]),
 692               val[c4],
 693               mlpi->q_averaged[c]);
 694           val[c4] = mlpi->q_averaged[c];
 695           found = GNUNET_YES;
 696           break;
 697         }
 698       }
 699
 700       if (found == GNUNET_NO)
 701         {
 702
 703           ind[length+1] = mlpi->c_b;
 704           val[length+1] = mlpi->q_averaged[c];
 705           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%i ind[%i] val[%i]:  %i %f\n", length+1,  length+1, length+1, mlpi->c_b, mlpi->q_averaged[c]);
 706           glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
 707         }
 708       else
 709         {
 710         /* Get the index if matrix row of quality */
 711         glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
 712         }
 713
 714       GNUNET_free (ind);
 715       GNUNET_free (val);
 716     }
 717   }
 718 }
 719
 720 #endif
 721
 722 /**
 723  * Add constraints that are iterating over "forall addresses"
 724  * and collects all existing peers for "forall peers" constraints
 725  *
 726  * @param cls GAS_MLP_Handle
 727  * @param key Hashcode
 728  * @param value ATS_Address
 729  *
 730  * @return GNUNET_OK to continue
 731  */
 732 static int
 733 create_constraint_it (void *cls, const struct GNUNET_HashCode * key, void *value)
 734 {
 735   struct GAS_MLP_Handle *mlp = cls;
 736   struct MLP_Problem *p = &mlp->p;
 737   struct ATS_Address *address = value;
 738   struct MLP_information *mlpi;
 739   unsigned int row_index;
 740   char *name;
 741
 742   GNUNET_assert (address->solver_information != NULL);
 743   mlpi = (struct MLP_information *) address->solver_information;
 744
 745   /* c 1) bandwidth capping
 746    * b_t  + (-M) * n_t <= 0
 747    */
 748   row_index = glp_add_rows (p->prob, 1);
 749   mlpi->r_c1 = row_index;
 750   /* set row name */
 751   GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 752   glp_set_row_name (p->prob, row_index, name);
 753   GNUNET_free (name);
 754   /* set row bounds: <= 0 */
 755   glp_set_row_bnds (p->prob, row_index, GLP_UP, 0.0, 0.0);
 756   p->ia[p->ci] = row_index;
 757   p->ja[p->ci] = mlpi->c_b;
 758   p->ar[p->ci] = 1;
 759   p->ci++;
 760
 761   p->ia[p->ci] = row_index;
 762   p->ja[p->ci] = mlpi->c_n;
 763   p->ar[p->ci] = -mlp->BIG_M;
 764   p->ci++;
 765
 766   /* c 3) minimum bandwidth
 767    * b_t + (-n_t * b_min) >= 0
 768    */
 769
 770   row_index = glp_add_rows (p->prob, 1);
 771   /* set row name */
 772   GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 773   glp_set_row_name (p->prob, row_index, name);
 774   GNUNET_free (name);
 775   mlpi->r_c3 = row_index;
 776   /* set row bounds: >= 0 */
 777   glp_set_row_bnds (p->prob, row_index, GLP_LO, 0.0, 0.0);
 778
 779   p->ia[p->ci] = row_index;
 780   p->ja[p->ci] = mlpi->c_b;
 781   p->ar[p->ci] = 1;
 782   p->ci++;
 783
 784   p->ia[p->ci] = row_index;
 785   p->ja[p->ci] = mlpi->c_n;
 786   p->ar[p->ci] = - (double) mlp->pv.b_min;
 787   p->ci++;
 788
 789   /* c 4) minimum connections
 790    * (1)*n_1 + ... + (1)*n_m >= n_min
 791    */
 792   p->ia[p->ci] = p->r_c4;
 793   p->ja[p->ci] = mlpi->c_n;
 794   p->ar[p->ci] = 1;
 795   p->ci++;
 796
 797   /* c 6) maximize diversity
 798    * (1)*n_1 + ... + (1)*n_m - d == 0
 799    */
 800   p->ia[p->ci] = p->r_c6;
 801   p->ja[p->ci] = mlpi->c_n;
 802   p->ar[p->ci] = 1;
 803   p->ci++;
 804
 805   /* c 10) obey network specific quotas
 806    * (1)*b_1 + ... + (1)*b_m <= quota_n
 807    */
 808
 809   int cur_row = 0;
 810   int c;
 811   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 812     {
 813     if (mlp->pv.quota_index[c] == address->atsp_network_type)
 814     {
 815       cur_row = p->r_quota[c];
 816       break;
 817     }
 818   }
 819
 820   if (cur_row != 0)
 821   {
 822     p->ia[p->ci] = cur_row;
 823     p->ja[p->ci] = mlpi->c_b;
 824     p->ar[p->ci] = 1;
 825     p->ci++;
 826   }
 827   else
 828   {
 829     GNUNET_break (0);
 830   }
 831
 832   return GNUNET_OK;
 833 }
 834
 835
 836 /**
 837  * Adds the problem constraints for all addresses
 838  * Required for problem recreation after address deletion
 839  *
 840  * @param mlp the mlp handle
 841  * @param addresses all addresses
 842  */
 843
 844 static void
 845 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 846 {
 847   unsigned int n_addresses;
 848   struct MLP_Problem *p = &mlp->p;
 849   int c;
 850   char *name;
 851
 852   /* Problem matrix*/
 853   n_addresses = p->addresses_in_problem;
 854
 855   /* Required indices in the constrain matrix
 856    *
 857    * feasibility constraints:
 858    *
 859    * c 1) bandwidth capping
 860    * #rows: |n_addresses|
 861    * #indices: 2 * |n_addresses|
 862    *
 863    * c 2) one active address per peer
 864    * #rows: |peers|
 865    * #indices: |n_addresses|
 866    *
 867    * c 3) minium bandwidth assigned
 868    * #rows: |n_addresses|
 869    * #indices: 2 * |n_addresses|
 870    *
 871    * c 4) minimum number of active connections
 872    * #rows: 1
 873    * #indices: |n_addresses|
 874    *
 875    * c 5) maximum ressource consumption
 876    * #rows: |ressources|
 877    * #indices: |n_addresses|
 878    *
 879    * c 10) obey network specific quota
 880    * #rows: |network types
 881    * #indices: |n_addresses|
 882    *
 883    * Sum for feasibility constraints:
 884    * #rows: 3 * |n_addresses| +  |ressources| + |peers| + 1
 885    * #indices: 7 * |n_addresses|
 886    *
 887    * optimality constraints:
 888    *
 889    * c 6) diversity
 890    * #rows: 1
 891    * #indices: |n_addresses| + 1
 892    *
 893    * c 7) quality
 894    * #rows: |quality properties|
 895    * #indices: |n_addresses| + |quality properties|
 896    *
 897    * c 8) utilization
 898    * #rows: 1
 899    * #indices: |n_addresses| + 1
 900    *
 901    * c 9) relativity
 902    * #rows: |peers|
 903    * #indices: |n_addresses| + |peers|
 904    * */
 905
 906   /* last +1 caused by glpk index starting with one: [1..pi]*/
 907   int pi = ((7 * n_addresses) + (5 * n_addresses +  mlp->pv.m_q + mlp->c_p + 2) + 1);
 908   mlp->cm_size = pi;
 909   p->ci = 1;
 910
 911   /* row index */
 912   int *ia = GNUNET_malloc (pi * sizeof (int));
 913   p->ia = ia;
 914
 915   /* column index */
 916   int *ja = GNUNET_malloc (pi * sizeof (int));
 917   p->ja = ja;
 918
 919   /* coefficient */
 920   double *ar= GNUNET_malloc (pi * sizeof (double));
 921   p->ar = ar;
 922
 923   /* Adding constraint rows
 924    * This constraints are kind of "for all addresses"
 925    * Feasibility constraints:
 926    *
 927    * c 1) bandwidth capping
 928    * c 3) minimum bandwidth
 929    * c 4) minimum number of connections
 930    * c 6) maximize diversity
 931    * c 10) obey network specific quota
 932    */
 933
 934   /* Row for c4) minimum connection */
 935   name = "c4";
 936   int min = mlp->pv.n_min;
 937   /* Number of minimum connections is min(|Peers|, n_min) */
 938   if (mlp->pv.n_min > mlp->c_p)
 939     min = mlp->c_p;
 940   p->r_c4 = glp_add_rows (p->prob, 1);
 941   glp_set_row_name (p->prob, p->r_c4, name);
 942   glp_set_row_bnds (p->prob, p->r_c4, GLP_LO, min, min);
 943 #if  DEBUG_MLP_PROBLEM_CREATION
 944         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 945                         p->r_c4, name,
 946                         ">=", min);
 947 #endif
 948
 949   /* Add row for c6) */
 950         name = "c6";
 951   p->r_c6 = glp_add_rows (p->prob, 1);
 952   /* Set type type to fix */
 953   glp_set_row_name (p->prob, p->r_c6, name);
 954   glp_set_row_bnds (p->prob, p->r_c6, GLP_FX, 0.0, 0.0);
 955 #if  DEBUG_MLP_PROBLEM_CREATION
 956         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 957                         p->r_c6, name,
 958                         "==", 0);
 959 #endif
 960   /* Setting -D */
 961   ia[p->ci] = p->r_c6 ;
 962   ja[p->ci] = p->c_d;
 963   ar[p->ci] = -1;
 964   p->ci++;
 965 #if  DEBUG_MLP_PROBLEM_CREATION
 966         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 967                         ia[p->ci], ja[p->ci], ar[p->ci]);
 968 #endif
 969
 970
 971   /* Add rows for c 10) */
 972   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 973   {
 974     p->r_quota[c] = glp_add_rows (p->prob, 1);
 975     char * text;
 976     GNUNET_asprintf(&text, "quota_ats_%i", mlp->pv.quota_index[c]);
 977     glp_set_row_name (p->prob, p->r_quota[c], text);
 978     /* Set bounds to 0 <= x <= quota_out */
 979     glp_set_row_bnds (p->prob, p->r_quota[c], GLP_UP, 0.0, mlp->pv.quota_out[c]);
 980 #if  DEBUG_MLP_PROBLEM_CREATION
 981                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 982                                 p->r_quota[c], name,
 983                                 "<=", mlp->pv.quota_out[c]);
 984 #endif
 985     GNUNET_free (text);
 986   }
 987
 988   //GNUNET_CONTAINER_multihashmap_iterate (addresses, create_constraint_it, mlp);
 989
 990   /* Adding constraint rows
 991    * This constraints are kind of "for all peers"
 992    * Feasibility constraints:
 993    *
 994    * c 2) 1 address per peer
 995    * sum (n_p1_1 + ... + n_p1_n) = 1
 996    *
 997    * c 8) utilization
 998    * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
 999    *
1000    * c 9) relativity
1001    * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
1002    * */
1003
1004   /* Adding rows for c 8) */
1005   p->r_c8 = glp_add_rows (p->prob, mlp->c_p);
1006   name = "c8";
1007   glp_set_row_name (p->prob, p->r_c8, "c8");
1008   /* Set row bound == 0 */
1009   glp_set_row_bnds (p->prob, p->r_c8, GLP_FX, 0.0, 0.0);
1010 #if  DEBUG_MLP_PROBLEM_CREATION
1011                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1012                                 p->r_c8, name,
1013                                 "==", 0);
1014 #endif
1015
1016   /* -u */
1017   ia[p->ci] = p->r_c8;
1018   ja[p->ci] = p->c_u;
1019   ar[p->ci] = -1;
1020   p->ci++;
1021 #if  DEBUG_MLP_PROBLEM_CREATION
1022         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1023                         ia[p->ci], ja[p->ci], ar[p->ci]);
1024 #endif
1025
1026   struct ATS_Peer * peer = mlp->peer_head;
1027   /* For all peers */
1028   while (peer != NULL)
1029   {
1030     struct ATS_Address *addr = peer->head;
1031     struct MLP_information *mlpi = NULL;
1032
1033     /* Adding rows for c 2) */
1034     peer->r_c2 = glp_add_rows (p->prob, 1);
1035     GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
1036     glp_set_row_name (p->prob, peer->r_c2, name);
1037     GNUNET_free (name);
1038     /* Set row bound == 1 */
1039     glp_set_row_bnds (p->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
1040
1041     /* Adding rows for c 9) */
1042     peer->r_c9 = glp_add_rows (p->prob, 1);
1043     GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
1044     glp_set_row_name (p->prob, peer->r_c9, name);
1045     GNUNET_free (name);
1046     /* Set row bound == 0 */
1047     glp_set_row_bnds (p->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
1048
1049     /* Set -r */
1050     ia[p->ci] = peer->r_c9;
1051     ja[p->ci] = p->c_r;
1052     ar[p->ci] = -peer->f;
1053     p->ci++;
1054
1055     /* For all addresses of this peer */
1056     while (addr != NULL)
1057     {
1058       mlpi = (struct MLP_information *) addr->solver_information;
1059
1060       /* coefficient for c 2) */
1061       ia[p->ci] = peer->r_c2;
1062       ja[p->ci] = mlpi->c_n;
1063       ar[p->ci] = 1;
1064       p->ci++;
1065
1066       /* coefficient for c 8) */
1067       ia[p->ci] = p->r_c8;
1068       ja[p->ci] = mlpi->c_b;
1069       ar[p->ci] = peer->f;
1070       p->ci++;
1071
1072 #if ENABLE_C9
1073       /* coefficient for c 9) */
1074       ia[p->ci] = peer->r_c9;
1075       ja[p->ci] = mlpi->c_b;
1076       ar[p->ci] = 1;
1077       p->ci++;
1078 #endif
1079
1080       addr = addr->next;
1081     }
1082     peer = peer->next;
1083   }
1084
1085   /* c 7) For all quality metrics */
1086   for (c = 0; c < mlp->pv.m_q; c++)
1087   {
1088     struct ATS_Peer *tp;
1089     struct ATS_Address *ta;
1090     struct MLP_information * mlpi;
1091     double value = 1.0;
1092
1093     /* Adding rows for c 7) */
1094     p->r_q[c] = glp_add_rows (p->prob, 1);
1095     GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c]));
1096     glp_set_row_name (p->prob, p->r_q[c], name);
1097     GNUNET_free (name);
1098     /* Set row bound == 0 */
1099     glp_set_row_bnds (p->prob, p->r_q[c], GLP_FX, 0.0, 0.0);
1100
1101     ia[p->ci] = p->r_q[c];
1102     ja[p->ci] = p->c_q[c];
1103     ar[p->ci] = -1;
1104     p->ci++;
1105
1106     for (tp = mlp->peer_head; tp != NULL; tp = tp->next)
1107       for (ta = tp->head; ta != NULL; ta = ta->next)
1108         {
1109           mlpi = ta->solver_information;
1110           value = mlpi->q_averaged[c];
1111
1112           mlpi->r_q[c] = p->r_q[c];
1113
1114           ia[p->ci] = p->r_q[c];
1115           ja[p->ci] = mlpi->c_b;
1116           ar[p->ci] = tp->f_q[c] * value;
1117           p->ci++;
1118         }
1119   }
1120 }
1121
1122
1123 /**
1124  * Add columns for all addresses
1125  *
1126  * @param cls GAS_MLP_Handle
1127  * @param key Hashcode
1128  * @param value ATS_Address
1129  *
1130  * @return GNUNET_OK to continue
1131  */
1132 static int
1133 mlp_create_address_columns_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1134 {
1135   struct GAS_MLP_Handle *mlp = cls;
1136   struct MLP_Problem *p = &mlp->p;
1137   struct ATS_Address *address = value;
1138   struct MLP_information *mlpi;
1139   unsigned int col;
1140   char *name;
1141
1142   if (NULL != address->solver_information)
1143   {
1144         GNUNET_free (address->solver_information);
1145                 address->solver_information = NULL;
1146   }
1147
1148   /* Check if we have to add this peer due to a pending request */
1149   if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
1150         return GNUNET_OK;
1151
1152         p->addresses_in_problem ++;
1153   mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1154   address->solver_information = mlpi;
1155
1156   /* Add bandwidth column */
1157   col = glp_add_cols (p->prob, 2);
1158   mlpi->c_b = col;
1159   mlpi->c_n = col + 1;
1160
1161
1162   GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1163   glp_set_col_name (p->prob, mlpi->c_b , name);
1164   /* Lower bound == 0 */
1165   glp_set_col_bnds (p->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
1166   /* Continuous value*/
1167   glp_set_col_kind (p->prob, mlpi->c_b , GLP_CV);
1168   /* Objective function coefficient == 0 */
1169   glp_set_obj_coef (p->prob, mlpi->c_b , 0);
1170 #if  DEBUG_MLP_PROBLEM_CREATION
1171         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1172                         mlpi->c_b, name, GNUNET_i2s(&address->peer), address);
1173 #endif
1174   GNUNET_free (name);
1175
1176   /* Add usage column */
1177   GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1178   glp_set_col_name (p->prob, mlpi->c_n, name);
1179   /* Limit value : 0 <= value <= 1 */
1180   glp_set_col_bnds (p->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
1181   /* Integer value*/
1182   glp_set_col_kind (p->prob, mlpi->c_n, GLP_IV);
1183   /* Objective function coefficient == 0 */
1184   glp_set_obj_coef (p->prob, mlpi->c_n, 0);
1185 #if  DEBUG_MLP_PROBLEM_CREATION
1186         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1187                         mlpi->c_n, name, GNUNET_i2s(&address->peer), address);
1188 #endif
1189   GNUNET_free (name);
1190
1191   return GNUNET_OK;
1192 }
1193
1194 /**
1195  * Create the MLP problem
1196  *
1197  * @param mlp the MLP handle
1198  * @param addresses the hashmap containing all adresses
1199  * @return GNUNET_OK or GNUNET_SYSERR
1200  */
1201 static int
1202 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1203 {
1204   struct MLP_Problem *p = &mlp->p;
1205         int res = GNUNET_OK;
1206   int c;
1207   int cur_col;
1208   char *name;
1209
1210         LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n",
1211                         GNUNET_CONTAINER_multihashmap_size(mlp->peers));
1212
1213   GNUNET_assert (p->prob == NULL);
1214
1215   /* create the glpk problem */
1216   p->prob = glp_create_prob ();
1217   p->addresses_in_problem = 0;;
1218   GNUNET_assert (NULL != p->prob);
1219
1220   /* Set a problem name */
1221   glp_set_prob_name (p->prob, "GNUnet ats bandwidth distribution");
1222
1223   /* Set optimization direction to maximize */
1224   glp_set_obj_dir (p->prob, GLP_MAX);
1225
1226   /* Adding invariant columns */
1227   /* Diversity d column  */
1228   p->c_d = glp_add_cols (p->prob, 1);
1229   /* Column name */
1230   glp_set_col_name (p->prob, p->c_d, "d");
1231   /* Column objective function coefficient */
1232   glp_set_obj_coef (p->prob, p->c_d, mlp->pv.co_D);
1233   /* Column lower bound = 0.0 */
1234   glp_set_col_bnds (p->prob, p->c_d, GLP_LO, 0.0, 0.0);
1235 #if  DEBUG_MLP_PROBLEM_CREATION
1236         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1237                         p->c_d, "d", mlp->pv.co_D);
1238 #endif
1239
1240
1241   /* Utilization u column  */
1242   p->c_u = glp_add_cols (p->prob, 1);
1243   /* Column name */
1244   glp_set_col_name (p->prob, p->c_u, "u");
1245   /* Column objective function coefficient */
1246   glp_set_obj_coef (p->prob, p->c_u, mlp->pv.co_U);
1247   /* Column lower bound = 0.0 */
1248   glp_set_col_bnds (p->prob, p->c_u, GLP_LO, 0.0, 0.0);
1249 #if  DEBUG_MLP_PROBLEM_CREATION
1250   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1251                          p->c_u, "u", mlp->pv.co_U);
1252 #endif
1253
1254   /* Relativity r column  */
1255   p->c_r = glp_add_cols (p->prob, 1);
1256   /* Column name */
1257   glp_set_col_name (p->prob, p->c_r, "r");
1258   /* Column objective function coefficient */
1259   glp_set_obj_coef (p->prob, p->c_r, mlp->pv.co_R);
1260   /* Column lower bound = 0.0 */
1261   glp_set_col_bnds (p->prob, p->c_r, GLP_LO, 0.0, 0.0);
1262 #if  DEBUG_MLP_PROBLEM_CREATION
1263   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1264                         p->c_r, "r", mlp->pv.co_R);
1265 #endif
1266
1267   /* Quality metric columns */
1268   cur_col = glp_add_cols(p->prob, mlp->pv.m_q);
1269   for (c = 0; c < mlp->pv.m_q; c++)
1270   {
1271     p->c_q[c] = cur_col + c;
1272     GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]);
1273     glp_set_col_name (p->prob, p->c_q[c], name);
1274     /* Column lower bound = 0.0 */
1275     glp_set_col_bnds (p->prob, p->c_q[c], GLP_LO, 0.0, 0.0);
1276     /* Coefficient == Qm */
1277     glp_set_obj_coef (p->prob, p->c_q[c], mlp->pv.co_Q[c]);
1278 #if  DEBUG_MLP_PROBLEM_CREATION
1279     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1280                         p->c_q[c], name, mlp->pv.co_Q[c]);
1281 #endif
1282         GNUNET_free (name);
1283   }
1284
1285   /* Add columns for addresses */
1286   GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_address_columns_it, mlp);
1287         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problems contains %u addresses, %u addresses skipped \n",
1288                         p->addresses_in_problem, GNUNET_CONTAINER_multihashmap_size(addresses)- p->addresses_in_problem);
1289
1290   /* Add constraints rows */
1291   mlp_add_constraints_all_addresses (mlp, addresses);
1292
1293   /* Load the matrix */
1294   //glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
1295
1296   return res;
1297 }
1298
1299
1300 /**
1301  * Solves the MLP problem
1302  *
1303  * @param solver the MLP Handle
1304  * @param addresses the address hashmap
1305  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
1306  */
1307 int
1308 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1309 {
1310         struct GAS_MLP_Handle *mlp = solver;
1311         int res = 0;
1312
1313         GNUNET_assert (NULL != solver);
1314
1315         if ((GNUNET_NO == mlp->mlp_prob_changed) && (GNUNET_NO == mlp->mlp_prob_updated))
1316         {
1317                 LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1318                 return GNUNET_OK;
1319         }
1320
1321         if (GNUNET_YES == mlp->mlp_prob_changed)
1322         {
1323                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1324                         mlp_delete_problem (mlp);
1325                         mlp_create_problem (mlp, addresses);
1326         }
1327         else
1328         {
1329                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1330         }
1331
1332         /* Solve problem */
1333 #if 0
1334   struct GAS_MLP_Handle *mlp = solver;
1335   int res;
1336
1337   GNUNET_assert (NULL != solver);
1338   GNUNET_assert (NULL != ctx);
1339
1340   /* Check if solving is already running */
1341   if (GNUNET_YES == mlp->semaphore)
1342   {
1343     if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1344     {
1345       GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1346       mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1347     }
1348     mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1349     return GNUNET_SYSERR;
1350   }
1351   mlp->semaphore = GNUNET_YES;
1352
1353   mlp->last_execution = GNUNET_TIME_absolute_get ();
1354
1355   ctx->lp_result = GNUNET_SYSERR;
1356   ctx->mlp_result = GNUNET_SYSERR;
1357   ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1358   ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1359
1360   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n");
1361 #if WRITE_MLP
1362   char * name;
1363   static int i;
1364   i++;
1365   GNUNET_asprintf(&name, "problem_%i", i);
1366   glp_write_lp (mlp->prob, 0, name);
1367   GNUNET_free (name);
1368 # endif
1369
1370   res = mlp_solve_lp_problem (mlp, ctx);
1371   ctx->lp_result = res;
1372   if (res != GNUNET_OK)
1373   {
1374     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n");
1375     mlp->semaphore = GNUNET_NO;
1376     return GNUNET_SYSERR;
1377   }
1378
1379 #if WRITE_MLP
1380   GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
1381   glp_print_sol (mlp->prob,  name);
1382   GNUNET_free (name);
1383 # endif
1384
1385
1386   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n");
1387   res = mlp_solve_mlp_problem (mlp, ctx);
1388   ctx->mlp_result = res;
1389   if (res != GNUNET_OK)
1390   {
1391     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n");
1392     mlp->semaphore = GNUNET_NO;
1393     return GNUNET_SYSERR;
1394   }
1395 #if WRITE_MLP
1396   GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
1397   glp_print_mip (mlp->prob, name);
1398   GNUNET_free (name);
1399 # endif
1400
1401   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n",
1402       (GNUNET_OK == res) ? "successfully" : "failed",
1403       ctx->lp_duration.rel_value,
1404       ctx->mlp_duration.rel_value);
1405   /* Process result */
1406   struct ATS_Peer *p = NULL;
1407   struct ATS_Address *a = NULL;
1408   struct MLP_information *mlpi = NULL;
1409
1410   for (p = mlp->peer_head; p != NULL; p = p->next)
1411   {
1412     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id));
1413     for (a = p->head; a != NULL; a = a->next)
1414     {
1415       double b = 0.0;
1416       double n = 0.0;
1417
1418       mlpi = a->solver_information;
1419
1420       b = glp_mip_col_val(mlp->prob, mlpi->c_b);
1421       mlpi->b = b;
1422
1423       n = glp_mip_col_val(mlp->prob, mlpi->c_n);
1424       if (n == 1.0)
1425       {
1426         /* This is the address to be used */
1427         mlpi->n = GNUNET_YES;
1428       }
1429       else
1430       {
1431         /* This is the address not used */
1432         mlpi->n = GNUNET_NO;
1433       }
1434
1435       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n",
1436           (n == 1.0) ? "[x]" : "[ ]", b);
1437
1438       /* Notify addresses */
1439       if ((ntohl(a->assigned_bw_in.value__) != b) ||
1440                 (ntohl(a->assigned_bw_out.value__) != b) ||
1441                 (mlpi->n != a->active))
1442       {
1443                 a->assigned_bw_in.value__ = htonl(b);
1444                 a->assigned_bw_out.value__ = htonl(b);
1445                 a->active = mlpi->n;
1446                 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, a);
1447       }
1448     }
1449   }
1450
1451   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1452   {
1453     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1454     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1455   }
1456   mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1457   mlp->semaphore = GNUNET_NO;
1458   return res;
1459 #endif
1460
1461         /* Reset change and update marker */
1462         mlp->mlp_prob_updated = GNUNET_NO;
1463         mlp->mlp_prob_changed = GNUNET_NO;
1464
1465         return res;
1466 }
1467
1468 /**
1469  * Add a single address to the solve
1470  *
1471  * @param solver the solver Handle
1472  * @param addresses the address hashmap containing all addresses
1473  * @param address the address to add
1474  */
1475 void
1476 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1477 {
1478   struct GAS_MLP_Handle *mlp = solver;
1479   struct ATS_Peer *p;
1480
1481   GNUNET_assert (NULL != solver);
1482   GNUNET_assert (NULL != addresses);
1483   GNUNET_assert (NULL != address);
1484
1485         /* TODO Add address here */
1486
1487   /* Is this peer included in the problem? */
1488   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1489   {
1490     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1491         return;
1492   }
1493   if (NULL != address->solver_information)
1494   {
1495                 GNUNET_break (0);
1496   }
1497
1498         LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1499         /* Problem size changed: new address for peer with pending request */
1500         mlp->mlp_prob_changed = GNUNET_YES;
1501         GAS_mlp_solve_problem (solver, addresses);
1502 }
1503
1504 /**
1505  * Updates a single address in the MLP problem
1506  *
1507  * If the address did not exist before in the problem:
1508  * The MLP problem has to be recreated and the problem has to be resolved
1509  *
1510  * Otherwise the addresses' values can be updated and the existing base can
1511  * be reused
1512  *
1513  * @param solver the solver Handle
1514  * @param addresses the address hashmap containing all addresses
1515  * @param address the update address
1516  * @param session the new session (if changed otherwise current)
1517  * @param in_use the new address in use state (if changed otherwise current)
1518  * @param atsi the latest ATS information
1519  * @param atsi_count the atsi count
1520  */
1521 void
1522 GAS_mlp_address_update (void *solver,
1523                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
1524                         struct ATS_Address *address,
1525                         uint32_t session,
1526                         int in_use,
1527                         const struct GNUNET_ATS_Information *atsi,
1528                         uint32_t atsi_count)
1529 {
1530         struct ATS_Peer *p;
1531         struct GAS_MLP_Handle *mlp = solver;
1532
1533         GNUNET_assert (NULL != solver);
1534         GNUNET_assert (NULL != addresses);
1535         GNUNET_assert (NULL != address);
1536         GNUNET_assert ((NULL != atsi) || (0 == atsi_count));
1537
1538         /* TODO Update address here */
1539
1540   /* Is this peer included in the problem? */
1541   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1542   {
1543     LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1544         return;
1545   }
1546         LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1547
1548         /* Problem size changed: new address for peer with pending request */
1549         mlp->mlp_prob_updated = GNUNET_YES;
1550         GAS_mlp_solve_problem (solver, addresses);
1551   return;
1552
1553 #if 0
1554   GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1555
1556   /* We add a new address */
1557   if (address->solver_information == NULL)
1558     new = GNUNET_YES;
1559   else
1560     new = GNUNET_NO;
1561
1562   /* Do the update */
1563   if (new == GNUNET_YES)
1564   {
1565     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1566
1567     int c;
1568     for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1569     {
1570       int c2;
1571       mlpi->r_q[c] = 0;
1572       for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1573         mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1574       mlpi->q_avg_i[c] = 0;
1575       mlpi->q_averaged[c] = 0.0;
1576     }
1577
1578     address->solver_information = mlpi;
1579     mlp->addresses_in_problem ++;
1580     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1581
1582     /* Check for and add peer */
1583     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1584     if (peer == NULL)
1585     {
1586
1587       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1588           GNUNET_i2s (&address->peer));
1589
1590       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1591       peer->head = NULL;
1592       peer->tail = NULL;
1593
1594       int c;
1595       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1596       {
1597         peer->f_q[c] = 1.0;
1598       }
1599       peer->f = 1.0;
1600
1601       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1602       GNUNET_assert(address->prev == NULL);
1603       GNUNET_assert(address->next == NULL);
1604       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1605       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1606       mlp->c_p ++;
1607       GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1608     }
1609     else
1610     {
1611
1612       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1613           GNUNET_i2s (&address->peer));
1614
1615       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1616     }
1617     update_quality (mlp, address);
1618   }
1619   else
1620   {
1621     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1622         GNUNET_i2s (&address->peer));
1623
1624     update_quality (mlp, address);
1625   }
1626
1627   /* Recalculate */
1628   if (new == GNUNET_YES)
1629   {
1630     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1631
1632     mlp_delete_problem (mlp);
1633     mlp_create_problem (mlp, addresses);
1634     mlp->presolver_required = GNUNET_YES;
1635   }
1636   if (mlp->auto_solve == GNUNET_YES)
1637     GAS_mlp_solve_problem (mlp, &ctx);
1638 #endif
1639 }
1640
1641 /**
1642  * Deletes a single address in the MLP problem
1643  *
1644  * The MLP problem has to be recreated and the problem has to be resolved
1645  *
1646  * @param solver the MLP Handle
1647  * @param addresses the address hashmap
1648  *        the address has to be already removed from the hashmap
1649  * @param address the address to delete
1650  * @param session_only delete only session not whole address
1651  */
1652 void
1653 GAS_mlp_address_delete (void *solver,
1654     struct GNUNET_CONTAINER_MultiHashMap * addresses,
1655     struct ATS_Address *address,
1656     int session_only)
1657 {
1658         struct ATS_Peer *p;
1659         struct GAS_MLP_Handle *mlp = solver;
1660
1661         GNUNET_assert (NULL != solver);
1662         GNUNET_assert (NULL != addresses);
1663         GNUNET_assert (NULL != address);
1664
1665         /* TODO Delete address here */
1666         if (NULL != address->solver_information)
1667         {
1668                         GNUNET_free (address->solver_information);
1669                         address->solver_information = NULL;
1670         }
1671
1672   /* Is this peer included in the problem? */
1673   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1674   {
1675     LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1676         return;
1677   }
1678         LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1679
1680         /* Problem size changed: new address for peer with pending request */
1681         mlp->mlp_prob_changed = GNUNET_YES;
1682         GAS_mlp_solve_problem (solver, addresses);
1683   return;
1684
1685 #if 0
1686   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1687   struct GAS_MLP_SolutionContext ctx;
1688
1689   /* Free resources */
1690   if (address->solver_information != NULL)
1691   {
1692     GNUNET_free (address->solver_information);
1693     address->solver_information = NULL;
1694
1695     mlp->addresses_in_problem --;
1696     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1697   }
1698
1699   /* Remove from peer list */
1700   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1701   GNUNET_assert (head != NULL);
1702
1703   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1704
1705   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1706   if ((head->head == NULL) && (head->tail == NULL))
1707   {
1708     /* No address for peer left, remove peer */
1709
1710     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1711
1712     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1713     GNUNET_free (head);
1714     mlp->c_p --;
1715     GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1716   }
1717
1718   /* Update problem */
1719   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1720
1721   mlp_delete_problem (mlp);
1722   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1723   {
1724     mlp_create_problem (mlp, addresses);
1725
1726     /* Recalculate */
1727     mlp->presolver_required = GNUNET_YES;
1728     if (mlp->auto_solve == GNUNET_YES)
1729       GAS_mlp_solve_problem (mlp, &ctx);
1730   }
1731 #endif
1732 }
1733
1734
1735 /**
1736  * Find the active address in the set of addresses of a peer
1737  * @param cls destination
1738  * @param key peer id
1739  * @param value address
1740  * @return GNUNET_OK
1741  */
1742 static int
1743 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1744 {
1745
1746   struct ATS_Address *aa = (struct ATS_Address *) cls;
1747   struct ATS_Address *addr = value;
1748   struct MLP_information *mlpi = addr->solver_information;
1749   if (mlpi == NULL)
1750     return GNUNET_YES;
1751   if (mlpi->n == GNUNET_YES)
1752   {
1753     aa = addr;
1754     if (mlpi->b > (double) UINT32_MAX)
1755       aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1756     else
1757       aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1758     aa->assigned_bw_in.value__ = htonl(0);
1759     return GNUNET_NO;
1760   }
1761   return GNUNET_YES;
1762 }
1763
1764
1765 /**
1766  * Get the preferred address for a specific peer
1767  *
1768  * @param solver the MLP Handle
1769  * @param addresses address hashmap
1770  * @param peer the peer
1771  * @return suggested address
1772  */
1773 const struct ATS_Address *
1774 GAS_mlp_get_preferred_address (void *solver,
1775                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
1776                                const struct GNUNET_PeerIdentity *peer)
1777 {
1778   struct GAS_MLP_Handle *mlp = solver;
1779   struct ATS_Peer *p;
1780   struct ATS_Address *res = NULL;
1781
1782   GNUNET_assert (NULL != solver);
1783   GNUNET_assert (NULL != addresses);
1784   GNUNET_assert (NULL != peer);
1785
1786   LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n",
1787                 GNUNET_i2s (peer));
1788
1789   /* Is this peer included in the problem? */
1790   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey)))
1791   {
1792           LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding peer `%s' to list of peers with requests\n",
1793                         GNUNET_i2s (peer));
1794
1795           p = GNUNET_malloc (sizeof (struct ATS_Peer));
1796           p->id = (*peer);
1797           GNUNET_CONTAINER_multihashmap_put (mlp->peers, &peer->hashPubKey, p, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
1798
1799           /* Added new peer, we have to rebuild problem before solving */
1800           mlp->mlp_prob_changed = GNUNET_YES;
1801   }
1802   GAS_mlp_solve_problem (mlp, addresses);
1803
1804   /* Get prefered address */
1805   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
1806                                                                                                                                                                                 mlp_get_preferred_address_it, res);
1807
1808   return res;
1809 }
1810
1811
1812 /**
1813  * Changes the preferences for a peer in the MLP problem
1814  *
1815  * @param solver the MLP Handle
1816  * @param client client
1817  * @param peer the peer
1818  * @param kind the kind to change the preference
1819  * @param score the score
1820  */
1821 void
1822 GAS_mlp_address_change_preference (void *solver,
1823                                    void *client,
1824                                    const struct GNUNET_PeerIdentity *peer,
1825                                    enum GNUNET_ATS_PreferenceKind kind,
1826                                    float score)
1827 {
1828   //struct GAS_MLP_Handle *mlp = solver;
1829
1830   LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n",
1831                 GNUNET_i2s(peer));
1832
1833   return;
1834 #if 0
1835   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1836
1837   //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1838   //FIXME to finish implementation
1839   /* Here we have to do the matching */
1840 #endif
1841 }
1842
1843
1844 static int
1845 mlp_free_peers (void *cls, const struct GNUNET_HashCode *key, void *value)
1846 {
1847         struct GNUNET_CONTAINER_MultiHashMap *map = cls;
1848         struct ATS_Peer *p = value;
1849
1850         GNUNET_CONTAINER_multihashmap_remove (map, key, value);
1851         GNUNET_free (p);
1852
1853         return GNUNET_OK;
1854 }
1855
1856
1857 /**
1858  * Shutdown the MLP problem solving component
1859  *
1860  * @param solver the solver handle
1861  */
1862 void
1863 GAS_mlp_done (void *solver)
1864 {
1865   struct GAS_MLP_Handle *mlp = solver;
1866   struct ATS_Peer * peer;
1867   struct ATS_Address *addr;
1868
1869   GNUNET_assert (mlp != NULL);
1870
1871   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n");
1872
1873   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1874   {
1875     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1876     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1877   }
1878
1879   /* clean up peer list */
1880   peer = mlp->peer_head;
1881   while (peer != NULL)
1882   {
1883     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1884     GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1885     for (addr = peer->head; NULL != addr; addr = peer->head)
1886     {
1887       GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1888       GNUNET_free (addr->solver_information);
1889       addr->solver_information = NULL;
1890     }
1891     GNUNET_free (peer);
1892     peer = mlp->peer_head;
1893   }
1894   mlp_delete_problem (mlp);
1895
1896   GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &mlp_free_peers, mlp->peers);
1897   GNUNET_CONTAINER_multihashmap_destroy (mlp->peers);
1898   mlp->peers = NULL;
1899
1900   /* Clean up GLPK environment */
1901   glp_free_env();
1902   GNUNET_free (mlp);
1903
1904   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n");
1905 }
1906
1907
1908 /**
1909  * Init the MLP problem solving component
1910  *
1911  * @param cfg the GNUNET_CONFIGURATION_Handle handle
1912  * @param stats the GNUNET_STATISTICS handle
1913  * @param network array of GNUNET_ATS_NetworkType with length dest_length
1914  * @param out_dest array of outbound quotas
1915  * @param in_dest array of outbound quota
1916  * @param dest_length array length for quota arrays
1917  * @param bw_changed_cb callback for changed bandwidth amounts
1918  * @param bw_changed_cb_cls cls for callback
1919  * @return struct GAS_MLP_Handle on success, NULL on fail
1920  */
1921 void *
1922 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1923               const struct GNUNET_STATISTICS_Handle *stats,
1924               int *network,
1925               unsigned long long *out_dest,
1926               unsigned long long *in_dest,
1927               int dest_length,
1928               GAS_bandwidth_changed_cb bw_changed_cb,
1929               void *bw_changed_cb_cls)
1930 {
1931   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1932
1933   double D;
1934   double R;
1935   double U;
1936   unsigned long long tmp;
1937   unsigned int b_min;
1938   unsigned int n_min;
1939   struct GNUNET_TIME_Relative i_exec;
1940   int c;
1941   int c2;
1942   int found;
1943
1944   struct GNUNET_TIME_Relative max_duration;
1945   long long unsigned int max_iterations;
1946
1947   /* Init GLPK environment */
1948   int res = glp_init_env();
1949   switch (res) {
1950     case 0:
1951         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1952           "initialization successful");
1953       break;
1954     case 1:
1955         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1956           "environment is already initialized");
1957       break;
1958     case 2:
1959         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1960           "initialization failed (insufficient memory)");
1961       GNUNET_free(mlp);
1962       return NULL;
1963       break;
1964     case 3:
1965         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1966           "initialization failed (unsupported programming model)");
1967       GNUNET_free(mlp);
1968       return NULL;
1969       break;
1970     default:
1971       break;
1972   }
1973
1974
1975   mlp->BIG_M = (double) BIG_M_VALUE;
1976
1977   /* Get timeout for iterations */
1978   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MLP_MAX_DURATION", &max_duration))
1979   {
1980     max_duration = MLP_MAX_EXEC_DURATION;
1981   }
1982
1983   /* Get maximum number of iterations */
1984   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations))
1985   {
1986     max_iterations = MLP_MAX_ITERATIONS;
1987   }
1988
1989   /* Get diversity coefficient from configuration */
1990   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1991                                                       "MLP_COEFFICIENT_D",
1992                                                       &tmp))
1993     D = (double) tmp / 100;
1994   else
1995     D = DEFAULT_D;
1996
1997   /* Get proportionality coefficient from configuration */
1998   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1999                                                       "MLP_COEFFICIENT_R",
2000                                                       &tmp))
2001     R = (double) tmp / 100;
2002   else
2003     R = DEFAULT_R;
2004
2005   /* Get utilization coefficient from configuration */
2006   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2007                                                       "MLP_COEFFICIENT_U",
2008                                                       &tmp))
2009     U = (double) tmp / 100;
2010   else
2011     U = DEFAULT_U;
2012
2013   /* Get quality metric coefficients from configuration */
2014   int i_delay = NaN;
2015   int i_distance = NaN;
2016   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
2017   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
2018   {
2019     /* initialize quality coefficients with default value 1.0 */
2020                 mlp->pv.co_Q[c] = DEFAULT_QUALITY;
2021
2022     mlp->pv.q[c] = q[c];
2023     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
2024       i_delay = c;
2025     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
2026       i_distance = c;
2027   }
2028
2029   if ((i_delay != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2030                                                       "MLP_COEFFICIENT_QUALITY_DELAY",
2031                                                       &tmp)))
2032
2033         mlp->pv.co_Q[i_delay] = (double) tmp / 100;
2034   else
2035         mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY;
2036
2037   if ((i_distance != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2038                                                       "MLP_COEFFICIENT_QUALITY_DISTANCE",
2039                                                       &tmp)))
2040         mlp->pv.co_Q[i_distance] = (double) tmp / 100;
2041   else
2042         mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY;
2043
2044   /* Get minimum bandwidth per used address from configuration */
2045   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2046                                                       "MLP_MIN_BANDWIDTH",
2047                                                       &tmp))
2048     b_min = tmp;
2049   else
2050   {
2051     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2052   }
2053
2054   /* Get minimum number of connections from configuration */
2055   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2056                                                       "MLP_MIN_CONNECTIONS",
2057                                                       &tmp))
2058     n_min = tmp;
2059   else
2060     n_min = DEFAULT_MIN_CONNECTIONS;
2061
2062   /* Init network quotas */
2063   int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
2064   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
2065   {
2066                 found = GNUNET_NO;
2067           for (c2 = 0; c2 < dest_length; c2++)
2068           {
2069                         if (quotas[c] == network[c2])
2070                   {
2071                                         mlp->pv.quota_index[c] = network[c2];
2072                                         mlp->pv.quota_out[c] = out_dest[c2];
2073                       mlp->pv.quota_in[c] = in_dest[c2];
2074                       found = GNUNET_YES;
2075                       LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n",
2076                                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2077                                                                 mlp->pv.quota_out[c],
2078                                                                 mlp->pv.quota_in[c]);
2079                       break;
2080                   }
2081           }
2082
2083       /* Check if defined quota could make problem unsolvable */
2084       if ((n_min * b_min) > mlp->pv.quota_out[c])
2085       {
2086         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2087                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2088                         mlp->pv.quota_out[c],
2089                         (n_min * b_min));
2090         mlp->pv.quota_out[c] = (n_min * b_min);
2091       }
2092       if ((n_min * b_min) > mlp->pv.quota_in[c])
2093       {
2094         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2095                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2096                         mlp->pv.quota_in[c],
2097                         (n_min * b_min));
2098         mlp->pv.quota_in[c] = (n_min * b_min);
2099       }
2100
2101       /* Check if bandwidth is too big to make problem solvable */
2102       if (mlp->BIG_M < mlp->pv.quota_out[c])
2103       {
2104         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2105                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2106                         mlp->pv.quota_out[c],
2107                         mlp->BIG_M);
2108         mlp->pv.quota_out[c] = mlp->BIG_M;
2109       }
2110       if (mlp->BIG_M < mlp->pv.quota_in[c])
2111       {
2112         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2113                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2114                         mlp->pv.quota_in[c],
2115                         mlp->BIG_M);
2116         mlp->pv.quota_in[c] = mlp->BIG_M;
2117       }
2118
2119           if (GNUNET_NO == found)
2120                         {
2121                 mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2122                 mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2123                                 LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"),
2124                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2125                                                 mlp->pv.quota_in[c],
2126                                                 mlp->pv.quota_out[c]);
2127                         }
2128   }
2129
2130   /* Get minimum number of connections from configuration */
2131   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
2132                                                         "MLP_EXEC_INTERVAL",
2133                                                         &i_exec))
2134     mlp->exec_interval = i_exec;
2135   else
2136     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
2137
2138   /* Assign options to handle */
2139   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
2140   mlp->bw_changed_cb = bw_changed_cb;
2141   mlp->bw_changed_cb_cls = bw_changed_cb_cls;
2142   /* Setting MLP Input variables */
2143   mlp->pv.co_D = D;
2144   mlp->pv.co_R = R;
2145   mlp->pv.co_U = U;
2146   mlp->pv.b_min = b_min;
2147   mlp->pv.n_min = n_min;
2148   mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount;
2149
2150   mlp->semaphore = GNUNET_NO;
2151   mlp->max_iterations = max_iterations;
2152   mlp->max_exec_duration = max_duration;
2153   mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
2154   mlp->auto_solve = GNUNET_YES;
2155   mlp->mlp_prob_changed = GNUNET_NO;
2156   mlp->mlp_prob_updated = GNUNET_NO;
2157
2158   mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO);
2159
2160   /* Setup GLPK */
2161   /* Redirect GLPK output to GNUnet logging */
2162   glp_term_hook (&mlp_term_hook, (void *) mlp);
2163
2164   /* Init LP solving parameters */
2165   glp_init_smcp(&mlp->control_param_lp);
2166   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2167 #if VERBOSE_GLPK
2168   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2169 #endif
2170   mlp->control_param_lp.it_lim = max_iterations;
2171   mlp->control_param_lp.tm_lim = max_duration.rel_value;
2172
2173   /* Init MLP solving parameters */
2174   glp_init_iocp(&mlp->control_param_mlp);
2175   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2176 #if VERBOSE_GLPK
2177   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2178 #endif
2179   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
2180
2181   LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2182
2183   return mlp;
2184 }
2185
2186 /* end of gnunet-service-ats_addresses_mlp.c */