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 #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->num_addresses != 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 mlp_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   /* Check if we have to add this peer due to a pending request */
 743   if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
 744         return GNUNET_OK;
 745
 746   GNUNET_assert (address->solver_information != NULL);
 747   mlpi = (struct MLP_information *) address->solver_information;
 748
 749   /* c 1) bandwidth capping
 750    * b_t  + (-M) * n_t <= 0
 751    * */
 752   row_index = glp_add_rows (p->prob, 1);
 753   mlpi->r_c1 = row_index;
 754   /* set row name */
 755   GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 756   glp_set_row_name (p->prob, row_index, name);
 757   /* set row bounds: <= 0 */
 758   glp_set_row_bnds (p->prob, row_index, GLP_UP, 0.0, 0.0);
 759 #if  DEBUG_MLP_PROBLEM_CREATION
 760                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 761                                 row_index, name,
 762                                 "<=", 0);
 763 #endif
 764         GNUNET_free (name);
 765
 766   p->ia[p->ci] = row_index;
 767   p->ja[p->ci] = mlpi->c_b;
 768   p->ar[p->ci] = 1;
 769 #if  DEBUG_MLP_PROBLEM_CREATION
 770         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 771                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 772 #endif
 773   p->ci++;
 774
 775   p->ia[p->ci] = row_index;
 776   p->ja[p->ci] = mlpi->c_n;
 777   p->ar[p->ci] = -mlp->pv.BIG_M;
 778 #if  DEBUG_MLP_PROBLEM_CREATION
 779         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 780                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 781 #endif
 782   p->ci++;
 783
 784   /* c 3) minimum bandwidth
 785    * b_t + (-n_t * b_min) >= 0
 786    * */
 787   row_index = glp_add_rows (p->prob, 1);
 788   mlpi->r_c3 = row_index;
 789   /* set row name */
 790   GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 791   glp_set_row_name (p->prob, row_index, name);
 792   /* set row bounds: >= 0 */
 793   glp_set_row_bnds (p->prob, row_index, GLP_LO, 0.0, 0.0);
 794 #if  DEBUG_MLP_PROBLEM_CREATION
 795                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 796                                 row_index, name,
 797                                 "<=", 0);
 798 #endif
 799         GNUNET_free (name);
 800
 801   p->ia[p->ci] = row_index;
 802   p->ja[p->ci] = mlpi->c_b;
 803   p->ar[p->ci] = 1;
 804 #if  DEBUG_MLP_PROBLEM_CREATION
 805         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 806                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 807 #endif
 808   p->ci++;
 809
 810   p->ia[p->ci] = row_index;
 811   p->ja[p->ci] = mlpi->c_n;
 812   p->ar[p->ci] = - (double) mlp->pv.b_min;
 813 #if  DEBUG_MLP_PROBLEM_CREATION
 814         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 815                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 816 #endif
 817   p->ci++;
 818
 819   /* c 4) minimum connections
 820    * (1)*n_1 + ... + (1)*n_m >= n_min
 821    */
 822   p->ia[p->ci] = p->r_c4;
 823   p->ja[p->ci] = mlpi->c_n;
 824   p->ar[p->ci] = 1;
 825 #if  DEBUG_MLP_PROBLEM_CREATION
 826         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 827                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 828 #endif
 829   p->ci++;
 830
 831   /* c 6) maximize diversity
 832    * (1)*n_1 + ... + (1)*n_m - d == 0
 833    */
 834   p->ia[p->ci] = p->r_c6;
 835   p->ja[p->ci] = mlpi->c_n;
 836   p->ar[p->ci] = 1;
 837 #if  DEBUG_MLP_PROBLEM_CREATION
 838         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 839                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 840 #endif
 841   p->ci++;
 842
 843   /* c 10) obey network specific quotas
 844    * (1)*b_1 + ... + (1)*b_m <= quota_n
 845    */
 846   int cur_row = 0;
 847   int c;
 848   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 849     {
 850     if (mlp->pv.quota_index[c] == address->atsp_network_type)
 851     {
 852       cur_row = p->r_quota[c];
 853       break;
 854     }
 855   }
 856
 857   if (cur_row != 0)
 858   {
 859     p->ia[p->ci] = cur_row;
 860     p->ja[p->ci] = mlpi->c_b;
 861     p->ar[p->ci] = 1;
 862 #if  DEBUG_MLP_PROBLEM_CREATION
 863         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
 864                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
 865 #endif
 866     p->ci++;
 867   }
 868   else
 869   {
 870     GNUNET_break (0);
 871   }
 872
 873   return GNUNET_OK;
 874 }
 875
 876
 877 /**
 878  * Adds the problem constraints for all addresses
 879  * Required for problem recreation after address deletion
 880  *
 881  * @param mlp the mlp handle
 882  * @param addresses all addresses
 883  */
 884
 885 static void
 886 mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
 887 {
 888   unsigned int n_addresses;
 889   struct MLP_Problem *p = &mlp->p;
 890   int c;
 891   char *name;
 892
 893   /* Problem matrix*/
 894   n_addresses = p->num_addresses;
 895
 896   /* Required indices in the constrain matrix
 897    *
 898    * feasibility constraints:
 899    *
 900    * c 1) bandwidth capping
 901    * #rows: |n_addresses|
 902    * #indices: 2 * |n_addresses|
 903    *
 904    * c 2) one active address per peer
 905    * #rows: |peers|
 906    * #indices: |n_addresses|
 907    *
 908    * c 3) minium bandwidth assigned
 909    * #rows: |n_addresses|
 910    * #indices: 2 * |n_addresses|
 911    *
 912    * c 4) minimum number of active connections
 913    * #rows: 1
 914    * #indices: |n_addresses|
 915    *
 916    * c 5) maximum ressource consumption
 917    * #rows: |ressources|
 918    * #indices: |n_addresses|
 919    *
 920    * c 10) obey network specific quota
 921    * #rows: |network types
 922    * #indices: |n_addresses|
 923    *
 924    * Sum for feasibility constraints:
 925    * #rows: 3 * |n_addresses| +  |ressources| + |peers| + 1
 926    * #indices: 7 * |n_addresses|
 927    *
 928    * optimality constraints:
 929    *
 930    * c 6) diversity
 931    * #rows: 1
 932    * #indices: |n_addresses| + 1
 933    *
 934    * c 7) quality
 935    * #rows: |quality properties|
 936    * #indices: |n_addresses| + |quality properties|
 937    *
 938    * c 8) utilization
 939    * #rows: 1
 940    * #indices: |n_addresses| + 1
 941    *
 942    * c 9) relativity
 943    * #rows: |peers|
 944    * #indices: |n_addresses| + |peers|
 945    * */
 946
 947   /* last +1 caused by glpk index starting with one: [1..pi]*/
 948   int pi = ((7 * n_addresses) + (5 * n_addresses +  mlp->pv.m_q + p->num_peers + 2) + 1);
 949   p->ci = 1;
 950
 951   /* row index */
 952   int *ia = GNUNET_malloc (pi * sizeof (int));
 953   p->ia = ia;
 954
 955   /* column index */
 956   int *ja = GNUNET_malloc (pi * sizeof (int));
 957   p->ja = ja;
 958
 959   /* coefficient */
 960   double *ar= GNUNET_malloc (pi * sizeof (double));
 961   p->ar = ar;
 962
 963   /* Adding constraint rows
 964    * This constraints are kind of "for all addresses"
 965    * Feasibility constraints:
 966    *
 967    * c 1) bandwidth capping
 968    * c 3) minimum bandwidth
 969    * c 4) minimum number of connections
 970    * c 6) maximize diversity
 971    * c 10) obey network specific quota
 972    */
 973
 974   /* Row for c4) minimum connection */
 975   name = "c4";
 976   int min = mlp->pv.n_min;
 977   /* Number of minimum connections is min(|Peers|, n_min) */
 978   if (mlp->pv.n_min > p->num_peers)
 979     min = p->num_peers;
 980   p->r_c4 = glp_add_rows (p->prob, 1);
 981   glp_set_row_name (p->prob, p->r_c4, name);
 982   glp_set_row_bnds (p->prob, p->r_c4, GLP_LO, min, min);
 983 #if  DEBUG_MLP_PROBLEM_CREATION
 984         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 985                         p->r_c4, name,
 986                         ">=", min);
 987 #endif
 988
 989   /* Add row for c6) */
 990         name = "c6";
 991   p->r_c6 = glp_add_rows (p->prob, 1);
 992   /* Set type type to fix */
 993   glp_set_row_name (p->prob, p->r_c6, name);
 994   glp_set_row_bnds (p->prob, p->r_c6, GLP_FX, 0.0, 0.0);
 995 #if  DEBUG_MLP_PROBLEM_CREATION
 996         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
 997                         p->r_c6, name,
 998                         "==", 0);
 999 #endif
1000   /* Setting -D */
1001   ia[p->ci] = p->r_c6 ;
1002   ja[p->ci] = p->c_d;
1003   ar[p->ci] = -1;
1004 #if  DEBUG_MLP_PROBLEM_CREATION
1005         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1006                         ia[p->ci], ja[p->ci], ar[p->ci]);
1007 #endif
1008   p->ci++;
1009
1010   /* Add rows for c 10) */
1011   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1012   {
1013     p->r_quota[c] = glp_add_rows (p->prob, 1);
1014     char * text;
1015     GNUNET_asprintf(&text, "quota_ats_%i", mlp->pv.quota_index[c]);
1016     glp_set_row_name (p->prob, p->r_quota[c], text);
1017     /* Set bounds to 0 <= x <= quota_out */
1018     glp_set_row_bnds (p->prob, p->r_quota[c], GLP_UP, 0.0, mlp->pv.quota_out[c]);
1019 #if  DEBUG_MLP_PROBLEM_CREATION
1020                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1021                                 p->r_quota[c], name,
1022                                 "<=", mlp->pv.quota_out[c]);
1023 #endif
1024     GNUNET_free (text);
1025   }
1026
1027   GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_constraint_it, mlp);
1028
1029   /* Adding constraint rows
1030    * This constraints are kind of "for all peers"
1031    * Feasibility constraints:
1032    *
1033    * c 2) 1 address per peer
1034    * sum (n_p1_1 + ... + n_p1_n) = 1
1035    *
1036    * c 8) utilization
1037    * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
1038    *
1039    * c 9) relativity
1040    * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
1041    * */
1042
1043   /* Adding rows for c 8) */
1044   p->r_c8 = glp_add_rows (p->prob, p->num_peers);
1045   name = "c8";
1046   glp_set_row_name (p->prob, p->r_c8, "c8");
1047   /* Set row bound == 0 */
1048   glp_set_row_bnds (p->prob, p->r_c8, GLP_FX, 0.0, 0.0);
1049 #if  DEBUG_MLP_PROBLEM_CREATION
1050                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1051                                 p->r_c8, name,
1052                                 "==", 0);
1053 #endif
1054
1055   /* -u */
1056   ia[p->ci] = p->r_c8;
1057   ja[p->ci] = p->c_u;
1058   ar[p->ci] = -1;
1059 #if  DEBUG_MLP_PROBLEM_CREATION
1060         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1061                         ia[p->ci], ja[p->ci], ar[p->ci]);
1062 #endif
1063   p->ci++;
1064
1065 #if 0
1066   struct ATS_Peer * peer = mlp->peer_head;
1067   /* For all peers */
1068   while (peer != NULL)
1069   {
1070     struct ATS_Address *addr = peer->head;
1071     struct MLP_information *mlpi = NULL;
1072
1073     /* Adding rows for c 2) */
1074     peer->r_c2 = glp_add_rows (p->prob, 1);
1075     GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
1076     glp_set_row_name (p->prob, peer->r_c2, name);
1077     /* Set row bound == 1 */
1078     glp_set_row_bnds (p->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
1079 #if  DEBUG_MLP_PROBLEM_CREATION
1080                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1081                                 peer->r_c2, name,
1082                                 "==", 1);
1083 #endif
1084                 GNUNET_free (name);
1085
1086     /* Adding rows for c 9) */
1087     peer->r_c9 = glp_add_rows (p->prob, 1);
1088     GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
1089     glp_set_row_name (p->prob, peer->r_c9, name);
1090     /* Set row bound == 0 */
1091     glp_set_row_bnds (p->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
1092 #if  DEBUG_MLP_PROBLEM_CREATION
1093                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1094                                 peer->r_c9, name,
1095                                 "<=", 1);
1096 #endif
1097     GNUNET_free (name);
1098
1099     /* Set -r */
1100     ia[p->ci] = peer->r_c9;
1101     ja[p->ci] = p->c_r;
1102     ar[p->ci] = -peer->f;
1103 #if  DEBUG_MLP_PROBLEM_CREATION
1104                         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1105                                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1106 #endif
1107     p->ci++;
1108
1109     /* For all addresses of this peer */
1110     while (addr != NULL)
1111     {
1112       mlpi = (struct MLP_information *) addr->solver_information;
1113
1114       /* coefficient for c 2) */
1115       ia[p->ci] = peer->r_c2;
1116       ja[p->ci] = mlpi->c_n;
1117       ar[p->ci] = 1;
1118 #if  DEBUG_MLP_PROBLEM_CREATION
1119                         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1120                                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1121 #endif
1122       p->ci++;
1123
1124       /* coefficient for c 8) */
1125       ia[p->ci] = p->r_c8;
1126       ja[p->ci] = mlpi->c_b;
1127       ar[p->ci] = peer->f;
1128 #if  DEBUG_MLP_PROBLEM_CREATION
1129                         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1130                                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1131 #endif
1132       p->ci++;
1133
1134       /* coefficient for c 9) */
1135       ia[p->ci] = peer->r_c9;
1136       ja[p->ci] = mlpi->c_b;
1137       ar[p->ci] = 1;
1138 #if  DEBUG_MLP_PROBLEM_CREATION
1139                         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1140                                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1141 #endif
1142       p->ci++;
1143       addr = addr->next;
1144     }
1145     peer = peer->next;
1146   }
1147 #endif
1148
1149   /* c 7) For all quality metrics */
1150   for (c = 0; c < mlp->pv.m_q; c++)
1151   {
1152     struct ATS_Peer *tp;
1153     struct ATS_Address *ta;
1154     struct MLP_information * mlpi;
1155     double value = 1.0;
1156
1157     /* Adding rows for c 7) */
1158     p->r_q[c] = glp_add_rows (p->prob, 1);
1159     GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c]));
1160     glp_set_row_name (p->prob, p->r_q[c], name);
1161     /* Set row bound == 0 */
1162     glp_set_row_bnds (p->prob, p->r_q[c], GLP_FX, 0.0, 0.0);
1163 #if  DEBUG_MLP_PROBLEM_CREATION
1164                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1165                                 p->r_q[c], name,
1166                                 "<=", 0);
1167 #endif
1168     GNUNET_free (name);
1169
1170     ia[p->ci] = p->r_q[c];
1171     ja[p->ci] = p->c_q[c];
1172     ar[p->ci] = -1;
1173 #if  DEBUG_MLP_PROBLEM_CREATION
1174                 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1175                                 p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1176 #endif
1177     p->ci++;
1178
1179     for (tp = mlp->peer_head; tp != NULL; tp = tp->next)
1180       for (ta = tp->head; ta != NULL; ta = ta->next)
1181         {
1182           mlpi = ta->solver_information;
1183           value = mlpi->q_averaged[c];
1184
1185           mlpi->r_q[c] = p->r_q[c];
1186
1187           ia[p->ci] = p->r_q[c];
1188           ja[p->ci] = mlpi->c_b;
1189           ar[p->ci] = tp->f_q[c] * value;
1190 #if  DEBUG_MLP_PROBLEM_CREATION
1191           LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Set value [%u,%u] ==  %.2f\n",
1192                         p->ia[p->ci], p->ja[p->ci], p->ar[p->ci]);
1193 #endif
1194           p->ci++;
1195         }
1196   }
1197 }
1198
1199
1200 /**
1201  * Add columns for all addresses
1202  *
1203  * @param cls GAS_MLP_Handle
1204  * @param key Hashcode
1205  * @param value ATS_Address
1206  *
1207  * @return GNUNET_OK to continue
1208  */
1209 static int
1210 mlp_create_address_columns_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1211 {
1212   struct GAS_MLP_Handle *mlp = cls;
1213   struct MLP_Problem *p = &mlp->p;
1214   struct ATS_Address *address = value;
1215   struct MLP_information *mlpi;
1216   unsigned int col;
1217   char *name;
1218
1219   if (NULL != address->solver_information)
1220   {
1221         GNUNET_free (address->solver_information);
1222                 address->solver_information = NULL;
1223   }
1224
1225   /* Check if we have to add this peer due to a pending request */
1226   if (GNUNET_NO == GNUNET_CONTAINER_multihashmap_contains(mlp->peers, key))
1227         return GNUNET_OK;
1228
1229         p->num_addresses ++;
1230   mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1231   address->solver_information = mlpi;
1232
1233   /* Add bandwidth column */
1234   col = glp_add_cols (p->prob, 2);
1235   mlpi->c_b = col;
1236   mlpi->c_n = col + 1;
1237
1238
1239   GNUNET_asprintf (&name, "b_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1240   glp_set_col_name (p->prob, mlpi->c_b , name);
1241   /* Lower bound == 0 */
1242   glp_set_col_bnds (p->prob, mlpi->c_b , GLP_LO, 0.0, 0.0);
1243   /* Continuous value*/
1244   glp_set_col_kind (p->prob, mlpi->c_b , GLP_CV);
1245   /* Objective function coefficient == 0 */
1246   glp_set_obj_coef (p->prob, mlpi->c_b , 0);
1247 #if  DEBUG_MLP_PROBLEM_CREATION
1248         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1249                         mlpi->c_b, name, GNUNET_i2s(&address->peer), address);
1250 #endif
1251   GNUNET_free (name);
1252
1253   /* Add usage column */
1254   GNUNET_asprintf (&name, "n_%s_%s", GNUNET_i2s (&address->peer), address->plugin);
1255   glp_set_col_name (p->prob, mlpi->c_n, name);
1256   /* Limit value : 0 <= value <= 1 */
1257   glp_set_col_bnds (p->prob, mlpi->c_n, GLP_DB, 0.0, 1.0);
1258   /* Integer value*/
1259   glp_set_col_kind (p->prob, mlpi->c_n, GLP_IV);
1260   /* Objective function coefficient == 0 */
1261   glp_set_obj_coef (p->prob, mlpi->c_n, 0);
1262 #if  DEBUG_MLP_PROBLEM_CREATION
1263         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': `%s' address %p\n",
1264                         mlpi->c_n, name, GNUNET_i2s(&address->peer), address);
1265 #endif
1266   GNUNET_free (name);
1267
1268   return GNUNET_OK;
1269 }
1270
1271 /**
1272  * Create the MLP problem
1273  *
1274  * @param mlp the MLP handle
1275  * @param addresses the hashmap containing all adresses
1276  * @return GNUNET_OK or GNUNET_SYSERR
1277  */
1278 static int
1279 mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1280 {
1281   struct MLP_Problem *p = &mlp->p;
1282         int res = GNUNET_OK;
1283   int c;
1284   int cur_col;
1285   char *name;
1286
1287         LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n",
1288                         GNUNET_CONTAINER_multihashmap_size(mlp->peers));
1289
1290   GNUNET_assert (p->prob == NULL);
1291   GNUNET_assert (p->ia == NULL);
1292   GNUNET_assert (p->ja == NULL);
1293   GNUNET_assert (p->ar == NULL);
1294
1295
1296   /* Reset MLP problem struct */
1297   p->num_addresses = 0;
1298   p->num_peers = GNUNET_CONTAINER_multihashmap_size (mlp->peers);
1299
1300   /* create the glpk problem */
1301   p->prob = glp_create_prob ();
1302   p->num_addresses = 0;;
1303   GNUNET_assert (NULL != p->prob);
1304
1305   /* Set a problem name */
1306   glp_set_prob_name (p->prob, "GNUnet ats bandwidth distribution");
1307
1308   /* Set optimization direction to maximize */
1309   glp_set_obj_dir (p->prob, GLP_MAX);
1310
1311   /* Adding invariant columns */
1312   /* Diversity d column  */
1313   p->c_d = glp_add_cols (p->prob, 1);
1314   /* Column name */
1315   glp_set_col_name (p->prob, p->c_d, "d");
1316   /* Column objective function coefficient */
1317   glp_set_obj_coef (p->prob, p->c_d, mlp->pv.co_D);
1318   /* Column lower bound = 0.0 */
1319   glp_set_col_bnds (p->prob, p->c_d, GLP_LO, 0.0, 0.0);
1320 #if  DEBUG_MLP_PROBLEM_CREATION
1321         LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1322                         p->c_d, "d", mlp->pv.co_D);
1323 #endif
1324
1325
1326   /* Utilization u column  */
1327   p->c_u = glp_add_cols (p->prob, 1);
1328   /* Column name */
1329   glp_set_col_name (p->prob, p->c_u, "u");
1330   /* Column objective function coefficient */
1331   glp_set_obj_coef (p->prob, p->c_u, mlp->pv.co_U);
1332   /* Column lower bound = 0.0 */
1333   glp_set_col_bnds (p->prob, p->c_u, GLP_LO, 0.0, 0.0);
1334 #if  DEBUG_MLP_PROBLEM_CREATION
1335   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1336                          p->c_u, "u", mlp->pv.co_U);
1337 #endif
1338
1339   /* Relativity r column  */
1340   p->c_r = glp_add_cols (p->prob, 1);
1341   /* Column name */
1342   glp_set_col_name (p->prob, p->c_r, "r");
1343   /* Column objective function coefficient */
1344   glp_set_obj_coef (p->prob, p->c_r, mlp->pv.co_R);
1345   /* Column lower bound = 0.0 */
1346   glp_set_col_bnds (p->prob, p->c_r, GLP_LO, 0.0, 0.0);
1347 #if  DEBUG_MLP_PROBLEM_CREATION
1348   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1349                         p->c_r, "r", mlp->pv.co_R);
1350 #endif
1351
1352   /* Quality metric columns */
1353   cur_col = glp_add_cols(p->prob, mlp->pv.m_q);
1354   for (c = 0; c < mlp->pv.m_q; c++)
1355   {
1356     p->c_q[c] = cur_col + c;
1357     GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]);
1358     glp_set_col_name (p->prob, p->c_q[c], name);
1359     /* Column lower bound = 0.0 */
1360     glp_set_col_bnds (p->prob, p->c_q[c], GLP_LO, 0.0, 0.0);
1361     /* Coefficient == Qm */
1362     glp_set_obj_coef (p->prob, p->c_q[c], mlp->pv.co_Q[c]);
1363 #if  DEBUG_MLP_PROBLEM_CREATION
1364     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%i] `%s': %.2f \n",
1365                         p->c_q[c], name, mlp->pv.co_Q[c]);
1366 #endif
1367         GNUNET_free (name);
1368   }
1369
1370   /* Add columns for addresses */
1371   GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_address_columns_it, mlp);
1372         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problems contains %u peers, %u addresses, %u addresses skipped \n",
1373                         GNUNET_CONTAINER_multihashmap_size(mlp->peers),
1374                         p->num_addresses, GNUNET_CONTAINER_multihashmap_size(addresses)- p->num_addresses);
1375
1376   /* Add constraints rows */
1377   mlp_add_constraints_all_addresses (mlp, addresses);
1378
1379   /* Load the matrix */
1380         LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1381   //glp_load_matrix(mlp->prob, (mlp->ci-1), mlp->ia, mlp->ja, mlp->ar);
1382
1383   return res;
1384 }
1385
1386
1387 /**
1388  * Solves the MLP problem
1389  *
1390  * @param solver the MLP Handle
1391  * @param addresses the address hashmap
1392  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
1393  */
1394 int
1395 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1396 {
1397         struct GAS_MLP_Handle *mlp = solver;
1398         int res = 0;
1399
1400         GNUNET_assert (NULL != solver);
1401
1402         if ((GNUNET_NO == mlp->mlp_prob_changed) && (GNUNET_NO == mlp->mlp_prob_updated))
1403         {
1404                 LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1405                 return GNUNET_OK;
1406         }
1407
1408         if (GNUNET_YES == mlp->mlp_prob_changed)
1409         {
1410                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1411                         mlp_delete_problem (mlp);
1412                         mlp_create_problem (mlp, addresses);
1413         }
1414         else
1415         {
1416                         LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1417         }
1418
1419         /* Solve problem */
1420 #if 0
1421   struct GAS_MLP_Handle *mlp = solver;
1422   int res;
1423
1424   GNUNET_assert (NULL != solver);
1425   GNUNET_assert (NULL != ctx);
1426
1427   /* Check if solving is already running */
1428   if (GNUNET_YES == mlp->semaphore)
1429   {
1430     if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1431     {
1432       GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1433       mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1434     }
1435     mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1436     return GNUNET_SYSERR;
1437   }
1438   mlp->semaphore = GNUNET_YES;
1439
1440   mlp->last_execution = GNUNET_TIME_absolute_get ();
1441
1442   ctx->lp_result = GNUNET_SYSERR;
1443   ctx->mlp_result = GNUNET_SYSERR;
1444   ctx->lp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1445   ctx->mlp_duration = GNUNET_TIME_UNIT_FOREVER_REL;
1446
1447   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve LP problem\n");
1448 #if WRITE_MLP
1449   char * name;
1450   static int i;
1451   i++;
1452   GNUNET_asprintf(&name, "problem_%i", i);
1453   glp_write_lp (mlp->prob, 0, name);
1454   GNUNET_free (name);
1455 # endif
1456
1457   res = mlp_solve_lp_problem (mlp, ctx);
1458   ctx->lp_result = res;
1459   if (res != GNUNET_OK)
1460   {
1461     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "LP Problem solving failed\n");
1462     mlp->semaphore = GNUNET_NO;
1463     return GNUNET_SYSERR;
1464   }
1465
1466 #if WRITE_MLP
1467   GNUNET_asprintf(&name, "problem_%i_lp_solution", i);
1468   glp_print_sol (mlp->prob,  name);
1469   GNUNET_free (name);
1470 # endif
1471
1472
1473   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Solve MLP problem\n");
1474   res = mlp_solve_mlp_problem (mlp, ctx);
1475   ctx->mlp_result = res;
1476   if (res != GNUNET_OK)
1477   {
1478     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "MLP Problem solving failed\n");
1479     mlp->semaphore = GNUNET_NO;
1480     return GNUNET_SYSERR;
1481   }
1482 #if WRITE_MLP
1483   GNUNET_asprintf(&name, "problem_%i_mlp_solution", i);
1484   glp_print_mip (mlp->prob, name);
1485   GNUNET_free (name);
1486 # endif
1487
1488   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved %s (LP duration %llu / MLP duration %llu)\n",
1489       (GNUNET_OK == res) ? "successfully" : "failed",
1490       ctx->lp_duration.rel_value,
1491       ctx->mlp_duration.rel_value);
1492   /* Process result */
1493   struct ATS_Peer *p = NULL;
1494   struct ATS_Address *a = NULL;
1495   struct MLP_information *mlpi = NULL;
1496
1497   for (p = mlp->peer_head; p != NULL; p = p->next)
1498   {
1499     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s'\n", GNUNET_i2s (&p->id));
1500     for (a = p->head; a != NULL; a = a->next)
1501     {
1502       double b = 0.0;
1503       double n = 0.0;
1504
1505       mlpi = a->solver_information;
1506
1507       b = glp_mip_col_val(mlp->prob, mlpi->c_b);
1508       mlpi->b = b;
1509
1510       n = glp_mip_col_val(mlp->prob, mlpi->c_n);
1511       if (n == 1.0)
1512       {
1513         /* This is the address to be used */
1514         mlpi->n = GNUNET_YES;
1515       }
1516       else
1517       {
1518         /* This is the address not used */
1519         mlpi->n = GNUNET_NO;
1520       }
1521
1522       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "\tAddress %s %f\n",
1523           (n == 1.0) ? "[x]" : "[ ]", b);
1524
1525       /* Notify addresses */
1526       if ((ntohl(a->assigned_bw_in.value__) != b) ||
1527                 (ntohl(a->assigned_bw_out.value__) != b) ||
1528                 (mlpi->n != a->active))
1529       {
1530                 a->assigned_bw_in.value__ = htonl(b);
1531                 a->assigned_bw_out.value__ = htonl(b);
1532                 a->active = mlpi->n;
1533                 mlp->bw_changed_cb (mlp->bw_changed_cb_cls, a);
1534       }
1535     }
1536   }
1537
1538   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1539   {
1540     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1541     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1542   }
1543   mlp->mlp_task = GNUNET_SCHEDULER_add_delayed (mlp->exec_interval, &mlp_scheduler, mlp);
1544   mlp->semaphore = GNUNET_NO;
1545   return res;
1546 #endif
1547
1548         /* Reset change and update marker */
1549         mlp->mlp_prob_updated = GNUNET_NO;
1550         mlp->mlp_prob_changed = GNUNET_NO;
1551
1552         return res;
1553 }
1554
1555 /**
1556  * Add a single address to the solve
1557  *
1558  * @param solver the solver Handle
1559  * @param addresses the address hashmap containing all addresses
1560  * @param address the address to add
1561  */
1562 void
1563 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1564 {
1565   struct GAS_MLP_Handle *mlp = solver;
1566   struct ATS_Peer *p;
1567
1568   GNUNET_assert (NULL != solver);
1569   GNUNET_assert (NULL != addresses);
1570   GNUNET_assert (NULL != address);
1571
1572         /* TODO Add address here */
1573
1574   /* Is this peer included in the problem? */
1575   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1576   {
1577     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1578         return;
1579   }
1580   if (NULL != address->solver_information)
1581   {
1582                 GNUNET_break (0);
1583   }
1584
1585         LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1586         /* Problem size changed: new address for peer with pending request */
1587         mlp->mlp_prob_changed = GNUNET_YES;
1588         GAS_mlp_solve_problem (solver, addresses);
1589 }
1590
1591 /**
1592  * Updates a single address in the MLP problem
1593  *
1594  * If the address did not exist before in the problem:
1595  * The MLP problem has to be recreated and the problem has to be resolved
1596  *
1597  * Otherwise the addresses' values can be updated and the existing base can
1598  * be reused
1599  *
1600  * @param solver the solver Handle
1601  * @param addresses the address hashmap containing all addresses
1602  * @param address the update address
1603  * @param session the new session (if changed otherwise current)
1604  * @param in_use the new address in use state (if changed otherwise current)
1605  * @param atsi the latest ATS information
1606  * @param atsi_count the atsi count
1607  */
1608 void
1609 GAS_mlp_address_update (void *solver,
1610                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
1611                         struct ATS_Address *address,
1612                         uint32_t session,
1613                         int in_use,
1614                         const struct GNUNET_ATS_Information *atsi,
1615                         uint32_t atsi_count)
1616 {
1617         struct ATS_Peer *p;
1618         struct GAS_MLP_Handle *mlp = solver;
1619
1620         GNUNET_assert (NULL != solver);
1621         GNUNET_assert (NULL != addresses);
1622         GNUNET_assert (NULL != address);
1623         GNUNET_assert ((NULL != atsi) || (0 == atsi_count));
1624
1625         /* TODO Update address here */
1626
1627   /* Is this peer included in the problem? */
1628   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1629   {
1630     LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1631         return;
1632   }
1633         LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1634
1635         /* Problem size changed: new address for peer with pending request */
1636         mlp->mlp_prob_updated = GNUNET_YES;
1637         GAS_mlp_solve_problem (solver, addresses);
1638   return;
1639
1640 #if 0
1641   GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1642
1643   /* We add a new address */
1644   if (address->solver_information == NULL)
1645     new = GNUNET_YES;
1646   else
1647     new = GNUNET_NO;
1648
1649   /* Do the update */
1650   if (new == GNUNET_YES)
1651   {
1652     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1653
1654     int c;
1655     for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1656     {
1657       int c2;
1658       mlpi->r_q[c] = 0;
1659       for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1660         mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1661       mlpi->q_avg_i[c] = 0;
1662       mlpi->q_averaged[c] = 0.0;
1663     }
1664
1665     address->solver_information = mlpi;
1666     mlp->num_addresses ++;
1667     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1668
1669     /* Check for and add peer */
1670     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1671     if (peer == NULL)
1672     {
1673
1674       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1675           GNUNET_i2s (&address->peer));
1676
1677       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1678       peer->head = NULL;
1679       peer->tail = NULL;
1680
1681       int c;
1682       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1683       {
1684         peer->f_q[c] = 1.0;
1685       }
1686       peer->f = 1.0;
1687
1688       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1689       GNUNET_assert(address->prev == NULL);
1690       GNUNET_assert(address->next == NULL);
1691       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1692       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1693       mlp->c_p ++;
1694       GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1695     }
1696     else
1697     {
1698
1699       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1700           GNUNET_i2s (&address->peer));
1701
1702       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1703     }
1704     update_quality (mlp, address);
1705   }
1706   else
1707   {
1708     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1709         GNUNET_i2s (&address->peer));
1710
1711     update_quality (mlp, address);
1712   }
1713
1714   /* Recalculate */
1715   if (new == GNUNET_YES)
1716   {
1717     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1718
1719     mlp_delete_problem (mlp);
1720     mlp_create_problem (mlp, addresses);
1721     mlp->presolver_required = GNUNET_YES;
1722   }
1723   if (mlp->auto_solve == GNUNET_YES)
1724     GAS_mlp_solve_problem (mlp, &ctx);
1725 #endif
1726 }
1727
1728 /**
1729  * Deletes a single address in the MLP problem
1730  *
1731  * The MLP problem has to be recreated and the problem has to be resolved
1732  *
1733  * @param solver the MLP Handle
1734  * @param addresses the address hashmap
1735  *        the address has to be already removed from the hashmap
1736  * @param address the address to delete
1737  * @param session_only delete only session not whole address
1738  */
1739 void
1740 GAS_mlp_address_delete (void *solver,
1741     struct GNUNET_CONTAINER_MultiHashMap * addresses,
1742     struct ATS_Address *address,
1743     int session_only)
1744 {
1745         struct ATS_Peer *p;
1746         struct GAS_MLP_Handle *mlp = solver;
1747
1748         GNUNET_assert (NULL != solver);
1749         GNUNET_assert (NULL != addresses);
1750         GNUNET_assert (NULL != address);
1751
1752         /* TODO Delete address here */
1753         if (NULL != address->solver_information)
1754         {
1755                         GNUNET_free (address->solver_information);
1756                         address->solver_information = NULL;
1757         }
1758
1759   /* Is this peer included in the problem? */
1760   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &address->peer.hashPubKey)))
1761   {
1762     LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' without address request \n", GNUNET_i2s(&address->peer));
1763         return;
1764   }
1765         LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s' with address request \n", GNUNET_i2s(&address->peer));
1766
1767         /* Problem size changed: new address for peer with pending request */
1768         mlp->mlp_prob_changed = GNUNET_YES;
1769         GAS_mlp_solve_problem (solver, addresses);
1770   return;
1771
1772 #if 0
1773   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1774   struct GAS_MLP_SolutionContext ctx;
1775
1776   /* Free resources */
1777   if (address->solver_information != NULL)
1778   {
1779     GNUNET_free (address->solver_information);
1780     address->solver_information = NULL;
1781
1782     mlp->num_addresses --;
1783     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1784   }
1785
1786   /* Remove from peer list */
1787   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1788   GNUNET_assert (head != NULL);
1789
1790   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1791
1792   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1793   if ((head->head == NULL) && (head->tail == NULL))
1794   {
1795     /* No address for peer left, remove peer */
1796
1797     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1798
1799     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1800     GNUNET_free (head);
1801     mlp->c_p --;
1802     GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1803   }
1804
1805   /* Update problem */
1806   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1807
1808   mlp_delete_problem (mlp);
1809   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1810   {
1811     mlp_create_problem (mlp, addresses);
1812
1813     /* Recalculate */
1814     mlp->presolver_required = GNUNET_YES;
1815     if (mlp->auto_solve == GNUNET_YES)
1816       GAS_mlp_solve_problem (mlp, &ctx);
1817   }
1818 #endif
1819 }
1820
1821
1822 /**
1823  * Find the active address in the set of addresses of a peer
1824  * @param cls destination
1825  * @param key peer id
1826  * @param value address
1827  * @return GNUNET_OK
1828  */
1829 static int
1830 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1831 {
1832
1833   struct ATS_Address *aa = (struct ATS_Address *) cls;
1834   struct ATS_Address *addr = value;
1835   struct MLP_information *mlpi = addr->solver_information;
1836   if (mlpi == NULL)
1837     return GNUNET_YES;
1838   if (mlpi->n == GNUNET_YES)
1839   {
1840     aa = addr;
1841     if (mlpi->b > (double) UINT32_MAX)
1842       aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1843     else
1844       aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1845     aa->assigned_bw_in.value__ = htonl(0);
1846     return GNUNET_NO;
1847   }
1848   return GNUNET_YES;
1849 }
1850
1851
1852 /**
1853  * Get the preferred address for a specific peer
1854  *
1855  * @param solver the MLP Handle
1856  * @param addresses address hashmap
1857  * @param peer the peer
1858  * @return suggested address
1859  */
1860 const struct ATS_Address *
1861 GAS_mlp_get_preferred_address (void *solver,
1862                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
1863                                const struct GNUNET_PeerIdentity *peer)
1864 {
1865   struct GAS_MLP_Handle *mlp = solver;
1866   struct ATS_Peer *p;
1867   struct ATS_Address *res = NULL;
1868
1869   GNUNET_assert (NULL != solver);
1870   GNUNET_assert (NULL != addresses);
1871   GNUNET_assert (NULL != peer);
1872
1873   LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n",
1874                 GNUNET_i2s (peer));
1875
1876   /* Is this peer included in the problem? */
1877   if (NULL == (p = GNUNET_CONTAINER_multihashmap_get (mlp->peers, &peer->hashPubKey)))
1878   {
1879           LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding peer `%s' to list of peers with requests\n",
1880                         GNUNET_i2s (peer));
1881
1882           p = GNUNET_malloc (sizeof (struct ATS_Peer));
1883           p->id = (*peer);
1884           GNUNET_CONTAINER_multihashmap_put (mlp->peers, &peer->hashPubKey, p, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
1885
1886           /* Added new peer, we have to rebuild problem before solving */
1887           mlp->mlp_prob_changed = GNUNET_YES;
1888   }
1889   GAS_mlp_solve_problem (mlp, addresses);
1890
1891   /* Get prefered address */
1892   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
1893                                                                                                                                                                                 mlp_get_preferred_address_it, res);
1894
1895   return res;
1896 }
1897
1898
1899 /**
1900  * Changes the preferences for a peer in the MLP problem
1901  *
1902  * @param solver the MLP Handle
1903  * @param client client
1904  * @param peer the peer
1905  * @param kind the kind to change the preference
1906  * @param score the score
1907  */
1908 void
1909 GAS_mlp_address_change_preference (void *solver,
1910                                    void *client,
1911                                    const struct GNUNET_PeerIdentity *peer,
1912                                    enum GNUNET_ATS_PreferenceKind kind,
1913                                    float score)
1914 {
1915   //struct GAS_MLP_Handle *mlp = solver;
1916
1917   LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s'\n",
1918                 GNUNET_i2s(peer));
1919
1920   return;
1921 #if 0
1922   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1923
1924   //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1925   //FIXME to finish implementation
1926   /* Here we have to do the matching */
1927 #endif
1928 }
1929
1930
1931 static int
1932 mlp_free_peers (void *cls, const struct GNUNET_HashCode *key, void *value)
1933 {
1934         struct GNUNET_CONTAINER_MultiHashMap *map = cls;
1935         struct ATS_Peer *p = value;
1936
1937         GNUNET_CONTAINER_multihashmap_remove (map, key, value);
1938         GNUNET_free (p);
1939
1940         return GNUNET_OK;
1941 }
1942
1943
1944 /**
1945  * Shutdown the MLP problem solving component
1946  *
1947  * @param solver the solver handle
1948  */
1949 void
1950 GAS_mlp_done (void *solver)
1951 {
1952   struct GAS_MLP_Handle *mlp = solver;
1953   struct ATS_Peer * peer;
1954   struct ATS_Address *addr;
1955
1956   GNUNET_assert (mlp != NULL);
1957
1958   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n");
1959
1960   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1961   {
1962     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1963     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1964   }
1965
1966   /* clean up peer list */
1967   peer = mlp->peer_head;
1968   while (peer != NULL)
1969   {
1970     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1971     GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1972     for (addr = peer->head; NULL != addr; addr = peer->head)
1973     {
1974       GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1975       GNUNET_free (addr->solver_information);
1976       addr->solver_information = NULL;
1977     }
1978     GNUNET_free (peer);
1979     peer = mlp->peer_head;
1980   }
1981   mlp_delete_problem (mlp);
1982
1983   GNUNET_CONTAINER_multihashmap_iterate (mlp->peers, &mlp_free_peers, mlp->peers);
1984   GNUNET_CONTAINER_multihashmap_destroy (mlp->peers);
1985   mlp->peers = NULL;
1986
1987   /* Clean up GLPK environment */
1988   glp_free_env();
1989   GNUNET_free (mlp);
1990
1991   LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n");
1992 }
1993
1994
1995 /**
1996  * Init the MLP problem solving component
1997  *
1998  * @param cfg the GNUNET_CONFIGURATION_Handle handle
1999  * @param stats the GNUNET_STATISTICS handle
2000  * @param network array of GNUNET_ATS_NetworkType with length dest_length
2001  * @param out_dest array of outbound quotas
2002  * @param in_dest array of outbound quota
2003  * @param dest_length array length for quota arrays
2004  * @param bw_changed_cb callback for changed bandwidth amounts
2005  * @param bw_changed_cb_cls cls for callback
2006  * @return struct GAS_MLP_Handle on success, NULL on fail
2007  */
2008 void *
2009 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
2010               const struct GNUNET_STATISTICS_Handle *stats,
2011               int *network,
2012               unsigned long long *out_dest,
2013               unsigned long long *in_dest,
2014               int dest_length,
2015               GAS_bandwidth_changed_cb bw_changed_cb,
2016               void *bw_changed_cb_cls)
2017 {
2018   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
2019
2020   double D;
2021   double R;
2022   double U;
2023   unsigned long long tmp;
2024   unsigned int b_min;
2025   unsigned int n_min;
2026   struct GNUNET_TIME_Relative i_exec;
2027   int c;
2028   int c2;
2029   int found;
2030
2031   struct GNUNET_TIME_Relative max_duration;
2032   long long unsigned int max_iterations;
2033
2034   /* Init GLPK environment */
2035   int res = glp_init_env();
2036   switch (res) {
2037     case 0:
2038         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2039           "initialization successful");
2040       break;
2041     case 1:
2042         LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2043           "environment is already initialized");
2044       break;
2045     case 2:
2046         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2047           "initialization failed (insufficient memory)");
2048       GNUNET_free(mlp);
2049       return NULL;
2050       break;
2051     case 3:
2052         LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2053           "initialization failed (unsupported programming model)");
2054       GNUNET_free(mlp);
2055       return NULL;
2056       break;
2057     default:
2058       break;
2059   }
2060
2061
2062   mlp->pv.BIG_M = (double) BIG_M_VALUE;
2063
2064   /* Get timeout for iterations */
2065   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MLP_MAX_DURATION", &max_duration))
2066   {
2067     max_duration = MLP_MAX_EXEC_DURATION;
2068   }
2069
2070   /* Get maximum number of iterations */
2071   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations))
2072   {
2073     max_iterations = MLP_MAX_ITERATIONS;
2074   }
2075
2076   /* Get diversity coefficient from configuration */
2077   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2078                                                       "MLP_COEFFICIENT_D",
2079                                                       &tmp))
2080     D = (double) tmp / 100;
2081   else
2082     D = DEFAULT_D;
2083
2084   /* Get proportionality coefficient from configuration */
2085   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2086                                                       "MLP_COEFFICIENT_R",
2087                                                       &tmp))
2088     R = (double) tmp / 100;
2089   else
2090     R = DEFAULT_R;
2091
2092   /* Get utilization coefficient from configuration */
2093   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2094                                                       "MLP_COEFFICIENT_U",
2095                                                       &tmp))
2096     U = (double) tmp / 100;
2097   else
2098     U = DEFAULT_U;
2099
2100   /* Get quality metric coefficients from configuration */
2101   int i_delay = NaN;
2102   int i_distance = NaN;
2103   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
2104   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
2105   {
2106     /* initialize quality coefficients with default value 1.0 */
2107                 mlp->pv.co_Q[c] = DEFAULT_QUALITY;
2108
2109     mlp->pv.q[c] = q[c];
2110     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
2111       i_delay = c;
2112     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
2113       i_distance = c;
2114   }
2115
2116   if ((i_delay != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2117                                                       "MLP_COEFFICIENT_QUALITY_DELAY",
2118                                                       &tmp)))
2119
2120         mlp->pv.co_Q[i_delay] = (double) tmp / 100;
2121   else
2122         mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY;
2123
2124   if ((i_distance != NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2125                                                       "MLP_COEFFICIENT_QUALITY_DISTANCE",
2126                                                       &tmp)))
2127         mlp->pv.co_Q[i_distance] = (double) tmp / 100;
2128   else
2129         mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY;
2130
2131   /* Get minimum bandwidth per used address from configuration */
2132   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2133                                                       "MLP_MIN_BANDWIDTH",
2134                                                       &tmp))
2135     b_min = tmp;
2136   else
2137   {
2138     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2139   }
2140
2141   /* Get minimum number of connections from configuration */
2142   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
2143                                                       "MLP_MIN_CONNECTIONS",
2144                                                       &tmp))
2145     n_min = tmp;
2146   else
2147     n_min = DEFAULT_MIN_CONNECTIONS;
2148
2149   /* Init network quotas */
2150   int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
2151   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
2152   {
2153                 found = GNUNET_NO;
2154           for (c2 = 0; c2 < dest_length; c2++)
2155           {
2156                         if (quotas[c] == network[c2])
2157                   {
2158                                         mlp->pv.quota_index[c] = network[c2];
2159                                         mlp->pv.quota_out[c] = out_dest[c2];
2160                       mlp->pv.quota_in[c] = in_dest[c2];
2161                       found = GNUNET_YES;
2162                       LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n",
2163                                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2164                                                                 mlp->pv.quota_out[c],
2165                                                                 mlp->pv.quota_in[c]);
2166                       break;
2167                   }
2168           }
2169
2170       /* Check if defined quota could make problem unsolvable */
2171       if ((n_min * b_min) > mlp->pv.quota_out[c])
2172       {
2173         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2174                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2175                         mlp->pv.quota_out[c],
2176                         (n_min * b_min));
2177         mlp->pv.quota_out[c] = (n_min * b_min);
2178       }
2179       if ((n_min * b_min) > mlp->pv.quota_in[c])
2180       {
2181         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2182                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2183                         mlp->pv.quota_in[c],
2184                         (n_min * b_min));
2185         mlp->pv.quota_in[c] = (n_min * b_min);
2186       }
2187
2188       /* Check if bandwidth is too big to make problem solvable */
2189       if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2190       {
2191         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2192                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2193                         mlp->pv.quota_out[c],
2194                         mlp->pv.BIG_M);
2195         mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
2196       }
2197       if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2198       {
2199         LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2200                         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2201                         mlp->pv.quota_in[c],
2202                         mlp->pv.BIG_M);
2203         mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
2204       }
2205
2206           if (GNUNET_NO == found)
2207                         {
2208                 mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2209                 mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2210                                 LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"),
2211                                                 GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2212                                                 mlp->pv.quota_in[c],
2213                                                 mlp->pv.quota_out[c]);
2214                         }
2215   }
2216
2217   /* Get minimum number of connections from configuration */
2218   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
2219                                                         "MLP_EXEC_INTERVAL",
2220                                                         &i_exec))
2221     mlp->exec_interval = i_exec;
2222   else
2223     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
2224
2225   /* Assign options to handle */
2226   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
2227   mlp->bw_changed_cb = bw_changed_cb;
2228   mlp->bw_changed_cb_cls = bw_changed_cb_cls;
2229   /* Setting MLP Input variables */
2230   mlp->pv.co_D = D;
2231   mlp->pv.co_R = R;
2232   mlp->pv.co_U = U;
2233   mlp->pv.b_min = b_min;
2234   mlp->pv.n_min = n_min;
2235   mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount;
2236
2237   mlp->semaphore = GNUNET_NO;
2238   mlp->max_iterations = max_iterations;
2239   mlp->max_exec_duration = max_duration;
2240   mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
2241   mlp->auto_solve = GNUNET_YES;
2242   mlp->mlp_prob_changed = GNUNET_NO;
2243   mlp->mlp_prob_updated = GNUNET_NO;
2244
2245   mlp->peers = GNUNET_CONTAINER_multihashmap_create (10, GNUNET_NO);
2246
2247   /* Setup GLPK */
2248   /* Redirect GLPK output to GNUnet logging */
2249   glp_term_hook (&mlp_term_hook, (void *) mlp);
2250
2251   /* Init LP solving parameters */
2252   glp_init_smcp(&mlp->control_param_lp);
2253   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2254 #if VERBOSE_GLPK
2255   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2256 #endif
2257   mlp->control_param_lp.it_lim = max_iterations;
2258   mlp->control_param_lp.tm_lim = max_duration.rel_value;
2259
2260   /* Init MLP solving parameters */
2261   glp_init_iocp(&mlp->control_param_mlp);
2262   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2263 #if VERBOSE_GLPK
2264   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2265 #endif
2266   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
2267
2268   LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2269
2270   return mlp;
2271 }
2272
2273 /* end of gnunet-service-ats_addresses_mlp.c */