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