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