src/ats/gnunet-service-ats_addresses_mlp.c

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