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