src/ats/gnunet-service-ats_addresses_mlp.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file ats/gnunet-service-ats_addresses_mlp.c
  23  * @brief ats mlp problem solver
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #include "gnunet-service-ats_addresses_mlp.h"
  31 #include "gnunet_statistics_service.h"
  32 #include "glpk.h"
  33
  34 #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
  35
  36 #define WRITE_MLP GNUNET_NO
  37 #define DEBUG_ATS GNUNET_NO
  38 #define VERBOSE_GLPK GNUNET_NO
  39
  40 #define ENABLE_C8 GNUNET_YES
  41 #define ENABLE_C9 GNUNET_YES
  42 /**
  43  * Translate glpk solver error codes to text
  44  * @param retcode return code
  45  * @return string with result
  46  */
  47 const char *
  48 mlp_solve_to_string (int retcode)
  49 {
  50   switch (retcode) {
  51     case 0:
  52       return "ok";
  53     case GLP_EBADB:
  54       return "invalid basis";
  55     case GLP_ESING:
  56       return "singular matrix";
  57     case GLP_ECOND:
  58       return "ill-conditioned matrix";
  59     case GLP_EBOUND:
  60       return "invalid bounds";
  61     case GLP_EFAIL:
  62       return "solver failed";
  63     case GLP_EOBJLL:
  64       return "objective lower limit reached";
  65     case GLP_EOBJUL:
  66       return "objective upper limit reached";
  67     case GLP_EITLIM:
  68       return "iteration limit exceeded";
  69     case GLP_ETMLIM:
  70       return "time limit exceeded";
  71     case GLP_ENOPFS:
  72       return "no primal feasible solution";
  73     case GLP_EROOT:
  74       return "root LP optimum not provided";
  75     case GLP_ESTOP:
  76       return "search terminated by application";
  77     case GLP_EMIPGAP:
  78       return "relative mip gap tolerance reached";
  79     case GLP_ENOFEAS:
  80       return "no dual feasible solution";
  81     case GLP_ENOCVG:
  82       return "no convergence";
  83     case GLP_EINSTAB:
  84       return "numerical instability";
  85     case GLP_EDATA:
  86       return "invalid data";
  87     case GLP_ERANGE:
  88       return "result out of range";
  89     default:
  90       GNUNET_break (0);
  91       return "unknown error";
  92   }
  93 }
  94
  95
  96 /**
  97  * Translate glpk status error codes to text
  98  * @param retcode return code
  99  * @return string with result
 100  */
 101 const char *
 102 mlp_status_to_string (int retcode)
 103 {
 104   switch (retcode) {
 105     case GLP_UNDEF:
 106       return "solution is undefined";
 107     case GLP_FEAS:
 108       return "solution is feasible";
 109     case GLP_INFEAS:
 110       return "solution is infeasible";
 111     case GLP_NOFEAS:
 112       return "no feasible solution exists";
 113     case GLP_OPT:
 114       return "solution is optimal";
 115     case GLP_UNBND:
 116       return "solution is unbounded";
 117     default:
 118       GNUNET_break (0);
 119       return "unknown error";
 120   }
 121 }
 122
 123 /**
 124  * Translate ATS properties to text
 125  * Just intended for debugging
 126  *
 127  * @param ats_index the ATS index
 128  * @return string with result
 129  */
 130 const char *
 131 mlp_ats_to_string (int ats_index)
 132 {
 133   switch (ats_index) {
 134     case GNUNET_ATS_ARRAY_TERMINATOR:
 135       return "GNUNET_ATS_ARRAY_TERMINATOR";
 136     case GNUNET_ATS_UTILIZATION_UP:
 137       return "GNUNET_ATS_UTILIZATION_UP";
 138     case GNUNET_ATS_UTILIZATION_DOWN:
 139       return "GNUNET_ATS_UTILIZATION_DOWN";
 140     case GNUNET_ATS_COST_LAN:
 141       return "GNUNET_ATS_COST_LAN";
 142     case GNUNET_ATS_COST_WAN:
 143       return "GNUNET_ATS_COST_LAN";
 144     case GNUNET_ATS_COST_WLAN:
 145       return "GNUNET_ATS_COST_WLAN";
 146     case GNUNET_ATS_NETWORK_TYPE:
 147       return "GNUNET_ATS_NETWORK_TYPE";
 148     case GNUNET_ATS_QUALITY_NET_DELAY:
 149       return "GNUNET_ATS_QUALITY_NET_DELAY";
 150     case GNUNET_ATS_QUALITY_NET_DISTANCE:
 151       return "GNUNET_ATS_QUALITY_NET_DISTANCE";
 152     default:
 153       GNUNET_break (0);
 154       return "unknown";
 155   }
 156 }
 157
 158 /**
 159  * Find a peer in the DLL
 160  *
 161  * @param mlp the mlp handle
 162  * @param peer the peer to find
 163  * @return the peer struct
 164  */
 165 static struct ATS_Peer *
 166 mlp_find_peer (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
 167 {
 168   struct ATS_Peer *res = mlp->peer_head;
 169   while (res != NULL)
 170   {
 171     if (0 == memcmp (peer, &res->id, sizeof (struct GNUNET_PeerIdentity)))
 172       break;
 173     res = res->next;
 174   }
 175   return res;
 176 }
 177
 178 /**
 179  * Intercept GLPK terminal output
 180  * @param info the mlp handle
 181  * @param s the string to print
 182  * @return 0: glpk prints output on terminal, 0 != surpress output
 183  */
 184 static int
 185 mlp_term_hook (void *info, const char *s)
 186 {
 187   /* Not needed atm struct MLP_information *mlp = info; */
 188   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s", s);
 189   return 1;
 190 }
 191
 192 /**
 193  * Delete the MLP problem and free the constrain matrix
 194  *
 195  * @param mlp the MLP handle
 196  */
 197 static void
 198 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 199 {
 200   if (mlp != NULL)
 201   {
 202     if (mlp->prob != NULL)
 203       glp_delete_prob(mlp->prob);
 204
 205     /* delete row index */
 206     if (mlp->ia != NULL)
 207     {
 208       GNUNET_free (mlp->ia);
 209       mlp->ia = NULL;
 210     }
 211
 212     /* delete column index */
 213     if (mlp->ja != NULL)
 214     {
 215       GNUNET_free (mlp->ja);
 216       mlp->ja = NULL;
 217     }
 218
 219     /* delete coefficients */
 220     if (mlp->ar != NULL)
 221     {
 222       GNUNET_free (mlp->ar);
 223       mlp->ar = NULL;
 224     }
 225     mlp->ci = 0;
 226     mlp->prob = NULL;
 227   }
 228 }
 229
 230 /**
 231  * Add constraints that are iterating over "forall addresses"
 232  * and collects all existing peers for "forall peers" constraints
 233  *
 234  * @param cls GAS_MLP_Handle
 235  * @param key Hashcode
 236  * @param value ATS_Address
 237  *
 238  * @return GNUNET_OK to continue
 239  */
 240 static int
 241 create_constraint_it (void *cls, const struct GNUNET_HashCode * key, void *value)
 242 {
 243   struct GAS_MLP_Handle *mlp = cls;
 244   struct ATS_Address *address = value;
 245   struct MLP_information *mlpi;
 246   unsigned int row_index;
 247   char *name;
 248
 249   GNUNET_assert (address->mlp_information != NULL);
 250   mlpi = (struct MLP_information *) address->mlp_information;
 251
 252   /* c 1) bandwidth capping
 253    * b_t  + (-M) * n_t <= 0
 254    */
 255   row_index = glp_add_rows (mlp->prob, 1);
 256   mlpi->r_c1 = row_index;
 257   /* set row name */
 258   GNUNET_asprintf(&name, "c1_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 259   glp_set_row_name (mlp->prob, row_index, name);
 260   GNUNET_free (name);
 261   /* set row bounds: <= 0 */
 262   glp_set_row_bnds (mlp->prob, row_index, GLP_UP, 0.0, 0.0);
 263   mlp->ia[mlp->ci] = row_index;
 264   mlp->ja[mlp->ci] = mlpi->c_b;
 265   mlp->ar[mlp->ci] = 1;
 266   mlp->ci++;
 267
 268   mlp->ia[mlp->ci] = row_index;
 269   mlp->ja[mlp->ci] = mlpi->c_n;
 270   mlp->ar[mlp->ci] = -mlp->BIG_M;
 271   mlp->ci++;
 272
 273   /* c 3) minimum bandwidth
 274    * b_t + (-n_t * b_min) >= 0
 275    */
 276
 277   row_index = glp_add_rows (mlp->prob, 1);
 278   /* set row name */
 279   GNUNET_asprintf(&name, "c3_%s_%s", GNUNET_i2s(&address->peer), address->plugin);
 280   glp_set_row_name (mlp->prob, row_index, name);
 281   GNUNET_free (name);
 282   mlpi->r_c3 = row_index;
 283   /* set row bounds: >= 0 */
 284   glp_set_row_bnds (mlp->prob, row_index, GLP_LO, 0.0, 0.0);
 285
 286   mlp->ia[mlp->ci] = row_index;
 287   mlp->ja[mlp->ci] = mlpi->c_b;
 288   mlp->ar[mlp->ci] = 1;
 289   mlp->ci++;
 290
 291   mlp->ia[mlp->ci] = row_index;
 292   mlp->ja[mlp->ci] = mlpi->c_n;
 293   mlp->ar[mlp->ci] = - (double) mlp->b_min;
 294   mlp->ci++;
 295
 296   /* c 4) minimum connections
 297    * (1)*n_1 + ... + (1)*n_m >= n_min
 298    */
 299   mlp->ia[mlp->ci] = mlp->r_c4;
 300   mlp->ja[mlp->ci] = mlpi->c_n;
 301   mlp->ar[mlp->ci] = 1;
 302   mlp->ci++;
 303
 304   /* c 6) maximize diversity
 305    * (1)*n_1 + ... + (1)*n_m - d == 0
 306    */
 307   mlp->ia[mlp->ci] = mlp->r_c6;
 308   mlp->ja[mlp->ci] = mlpi->c_n;
 309   mlp->ar[mlp->ci] = 1;
 310   mlp->ci++;
 311
 312   /* c 10) obey network specific quotas
 313    * (1)*b_1 + ... + (1)*b_m <= quota_n
 314    */
 315
 316   int cur_row = 0;
 317   int c;
 318   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 319     {
 320     if (mlp->quota_index[c] == address->atsp_network_type)
 321     {
 322       cur_row = mlp->r_quota[c];
 323       break;
 324     }
 325   }
 326
 327   if (cur_row != 0)
 328   {
 329     mlp->ia[mlp->ci] = cur_row;
 330     mlp->ja[mlp->ci] = mlpi->c_b;
 331     mlp->ar[mlp->ci] = 1;
 332     mlp->ci++;
 333   }
 334   else
 335   {
 336     GNUNET_break (0);
 337   }
 338
 339   return GNUNET_OK;
 340 }
 341
 342 /**
 343  * Find the required ATS information for an address
 344  *
 345  * @param addr the address
 346  * @param ats_index the desired ATS index
 347  *
 348  * @return the index on success, otherwise GNUNET_SYSERR
 349  */
 350 #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->mlp_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->mlp_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->mlp_information != NULL);
 647   mlpi = address->mlp_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->mlp_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, unsigned long long *in_dest, int dest_length)
1083 {
1084   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1085
1086   double D;
1087   double R;
1088   double U;
1089   unsigned long long tmp;
1090   unsigned int b_min;
1091   unsigned int n_min;
1092   struct GNUNET_TIME_Relative i_exec;
1093   int c;
1094   char * quota_out_str;
1095   char * quota_in_str;
1096
1097   struct GNUNET_TIME_Relative max_duration;
1098   long long unsigned int max_iterations;
1099
1100   /* Init GLPK environment */
1101   int res = glp_init_env();
1102   switch (res) {
1103     case 0:
1104       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1105           "initialization successful");
1106       break;
1107     case 1:
1108       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1109           "environment is already initialized");
1110       break;
1111     case 2:
1112       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1113           "initialization failed (insufficient memory)");
1114       GNUNET_free(mlp);
1115       return NULL;
1116       break;
1117     case 3:
1118       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1119           "initialization failed (unsupported programming model)");
1120       GNUNET_free(mlp);
1121       return NULL;
1122       break;
1123     default:
1124       break;
1125   }
1126
1127   /* Create initial MLP problem */
1128   mlp->prob = glp_create_prob();
1129   GNUNET_assert (mlp->prob != NULL);
1130
1131   mlp->BIG_M = (double) BIG_M_VALUE;
1132
1133   /* Get timeout for iterations */
1134   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MAX_DURATION", &max_duration))
1135   {
1136     max_duration = MLP_MAX_EXEC_DURATION;
1137   }
1138
1139   /* Get maximum number of iterations */
1140   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MAX_ITERATIONS", &max_iterations))
1141   {
1142     max_iterations = MLP_MAX_ITERATIONS;
1143   }
1144
1145   /* Get diversity coefficient from configuration */
1146   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1147                                                       "COEFFICIENT_D",
1148                                                       &tmp))
1149     D = (double) tmp / 100;
1150   else
1151     D = 1.0;
1152
1153   /* Get proportionality coefficient from configuration */
1154   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1155                                                       "COEFFICIENT_R",
1156                                                       &tmp))
1157     R = (double) tmp / 100;
1158   else
1159     R = 1.0;
1160
1161   /* Get utilization coefficient from configuration */
1162   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1163                                                       "COEFFICIENT_U",
1164                                                       &tmp))
1165     U = (double) tmp / 100;
1166   else
1167     U = 1.0;
1168
1169   /* Get quality metric coefficients from configuration */
1170   int i_delay = -1;
1171   int i_distance = -1;
1172   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1173   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1174   {
1175     /* initialize quality coefficients with default value 1.0 */
1176     mlp->co_Q[c] = 1.0;
1177
1178     mlp->q[c] = q[c];
1179     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1180       i_delay = c;
1181     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1182       i_distance = c;
1183   }
1184
1185   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1186                                                       "COEFFICIENT_QUALITY_DELAY",
1187                                                       &tmp)))
1188
1189     mlp->co_Q[i_delay] = (double) tmp / 100;
1190   else
1191     mlp->co_Q[i_delay] = 1.0;
1192
1193   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1194                                                       "COEFFICIENT_QUALITY_DISTANCE",
1195                                                       &tmp)))
1196     mlp->co_Q[i_distance] = (double) tmp / 100;
1197   else
1198     mlp->co_Q[i_distance] = 1.0;
1199
1200   /* Get minimum bandwidth per used address from configuration */
1201   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1202                                                       "MIN_BANDWIDTH",
1203                                                       &tmp))
1204     b_min = tmp;
1205   else
1206   {
1207     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1208   }
1209
1210   /* Get minimum number of connections from configuration */
1211   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1212                                                       "MIN_CONNECTIONS",
1213                                                       &tmp))
1214     n_min = tmp;
1215   else
1216     n_min = 4;
1217
1218   /* Init network quotas */
1219   int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
1220   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1221   {
1222     mlp->quota_index[c] = quotas[c];
1223     static char * entry_in = NULL;
1224     static char * entry_out = NULL;
1225     unsigned long long quota_in = 0;
1226     unsigned long long quota_out = 0;
1227
1228     switch (quotas[c]) {
1229       case GNUNET_ATS_NET_UNSPECIFIED:
1230         entry_out = "UNSPECIFIED_QUOTA_OUT";
1231         entry_in = "UNSPECIFIED_QUOTA_IN";
1232         break;
1233       case GNUNET_ATS_NET_LOOPBACK:
1234         entry_out = "LOOPBACK_QUOTA_OUT";
1235         entry_in = "LOOPBACK_QUOTA_IN";
1236         break;
1237       case GNUNET_ATS_NET_LAN:
1238         entry_out = "LAN_QUOTA_OUT";
1239         entry_in = "LAN_QUOTA_IN";
1240         break;
1241       case GNUNET_ATS_NET_WAN:
1242         entry_out = "WAN_QUOTA_OUT";
1243         entry_in = "WAN_QUOTA_IN";
1244         break;
1245       case GNUNET_ATS_NET_WLAN:
1246         entry_out = "WLAN_QUOTA_OUT";
1247         entry_in = "WLAN_QUOTA_IN";
1248         break;
1249       default:
1250         break;
1251     }
1252
1253     if ((entry_in == NULL) || (entry_out == NULL))
1254       continue;
1255
1256     if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_out, &quota_out_str))
1257     {
1258       if (0 == strcmp(quota_out_str, BIG_M_STRING) ||
1259           (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_out_str, &quota_out)))
1260         quota_out = mlp->BIG_M;
1261
1262       GNUNET_free (quota_out_str);
1263       quota_out_str = NULL;
1264     }
1265     else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1266     {
1267       quota_out = mlp->BIG_M;
1268     }
1269     else
1270     {
1271       quota_out = mlp->BIG_M;
1272     }
1273
1274     if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_in, &quota_in_str))
1275     {
1276       if (0 == strcmp(quota_in_str, BIG_M_STRING) ||
1277           (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_in_str, &quota_in)))
1278         quota_in = mlp->BIG_M;
1279
1280       GNUNET_free (quota_in_str);
1281       quota_in_str = NULL;
1282     }
1283     else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1284     {
1285       quota_in = mlp->BIG_M;
1286     }
1287     else
1288     {
1289       quota_in = mlp->BIG_M;
1290     }
1291
1292     /* Check if defined quota could make problem unsolvable */
1293     if (((n_min * b_min) > quota_out) && (GNUNET_ATS_NET_UNSPECIFIED != quotas[c]))
1294     {
1295       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Inconsistent quota configuration value `%s': "
1296                   "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);
1297
1298       GAS_mlp_done(mlp);
1299       mlp = NULL;
1300       return NULL;
1301     }
1302
1303     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found `%s' quota %llu and `%s' quota %llu\n",
1304                 entry_out, quota_out, entry_in, quota_in);
1305     GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_out, quota_out, GNUNET_NO);
1306     GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_in, quota_in, GNUNET_NO);
1307     mlp->quota_out[c] = quota_out;
1308     mlp->quota_in[c] = quota_in;
1309   }
1310
1311   /* Get minimum number of connections from configuration */
1312   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1313                                                         "ATS_EXEC_INTERVAL",
1314                                                         &i_exec))
1315     mlp->exec_interval = i_exec;
1316   else
1317     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1318
1319   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1320   mlp->max_iterations = max_iterations;
1321   mlp->max_exec_duration = max_duration;
1322   mlp->auto_solve = GNUNET_YES;
1323
1324   /* Redirect GLPK output to GNUnet logging */
1325   glp_error_hook((void *) mlp, &mlp_term_hook);
1326
1327   /* Init LP solving parameters */
1328   glp_init_smcp(&mlp->control_param_lp);
1329
1330   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1331 #if VERBOSE_GLPK
1332   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1333 #endif
1334
1335   mlp->control_param_lp.it_lim = max_iterations;
1336   mlp->control_param_lp.tm_lim = max_duration.rel_value;
1337
1338   /* Init MLP solving parameters */
1339   glp_init_iocp(&mlp->control_param_mlp);
1340
1341   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1342 #if VERBOSE_GLPK
1343   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1344 #endif
1345   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1346
1347   mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
1348
1349   mlp->co_D = D;
1350   mlp->co_R = R;
1351   mlp->co_U = U;
1352   mlp->b_min = b_min;
1353   mlp->n_min = n_min;
1354   mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1355   mlp->semaphore = GNUNET_NO;
1356   return mlp;
1357 }
1358
1359 static void
1360 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
1361 {
1362   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
1363       GNUNET_i2s (&address->peer));
1364
1365   GNUNET_assert (NULL != address);
1366   GNUNET_assert (NULL != address->mlp_information);
1367 //  GNUNET_assert (NULL != address->ats);
1368
1369   struct MLP_information *mlpi = address->mlp_information;
1370   //struct GNUNET_ATS_Information *ats = address->ats;
1371   GNUNET_assert (mlpi != NULL);
1372
1373   int c;
1374   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1375   {
1376
1377     /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */
1378     int index = GNUNET_SYSERR;
1379
1380     if (index == GNUNET_SYSERR)
1381       continue;
1382     /* FIXME
1383     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
1384         GNUNET_i2s (&address->peer),
1385         mlp_ats_to_string(mlp->q[c]),
1386         (double) ats[index].value);
1387
1388     int i = mlpi->q_avg_i[c];*/
1389     double * qp = mlpi->q[c];
1390     /* FIXME
1391     qp[i] = (double) ats[index].value;
1392     */
1393
1394     int t;
1395     for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
1396     {
1397       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
1398         GNUNET_i2s (&address->peer),
1399         mlp_ats_to_string(mlp->q[c]),
1400         t,
1401         qp[t]);
1402     }
1403
1404     if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
1405       mlpi->q_avg_i[c] ++;
1406     else
1407       mlpi->q_avg_i[c] = 0;
1408
1409
1410     int c2;
1411     int c3;
1412     double avg = 0.0;
1413     switch (mlp->q[c])
1414     {
1415       case GNUNET_ATS_QUALITY_NET_DELAY:
1416         c3 = 0;
1417         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1418         {
1419           if (mlpi->q[c][c2] != -1)
1420           {
1421             double * t2 = mlpi->q[c] ;
1422             avg += t2[c2];
1423             c3 ++;
1424           }
1425         }
1426         if ((c3 > 0) && (avg > 0))
1427           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1428           mlpi->q_averaged[c] = (double) c3 / avg;
1429         else
1430           mlpi->q_averaged[c] = 0.0;
1431
1432         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1433           GNUNET_i2s (&address->peer),
1434           mlp_ats_to_string(mlp->q[c]),
1435           avg,
1436           avg / (double) c3,
1437           mlpi->q_averaged[c]);
1438
1439         break;
1440       case GNUNET_ATS_QUALITY_NET_DISTANCE:
1441         c3 = 0;
1442         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1443         {
1444           if (mlpi->q[c][c2] != -1)
1445           {
1446             double * t2 = mlpi->q[c] ;
1447             avg += t2[c2];
1448             c3 ++;
1449           }
1450         }
1451         if ((c3 > 0) && (avg > 0))
1452           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1453           mlpi->q_averaged[c] = (double) c3 / avg;
1454         else
1455           mlpi->q_averaged[c] = 0.0;
1456
1457         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1458           GNUNET_i2s (&address->peer),
1459           mlp_ats_to_string(mlp->q[c]),
1460           avg,
1461           avg / (double) c3,
1462           mlpi->q_averaged[c]);
1463
1464         break;
1465       default:
1466         break;
1467     }
1468
1469     if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
1470     {
1471
1472       /* Get current number of columns */
1473       int found = GNUNET_NO;
1474       int cols = glp_get_num_cols(mlp->prob);
1475       int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
1476       double *val = GNUNET_malloc (cols * sizeof (double) + 1);
1477
1478       /* Get the matrix row of quality */
1479       int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
1480       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
1481       int c4;
1482       /* Get the index if matrix row of quality */
1483       for (c4 = 1; c4 <= length; c4++ )
1484       {
1485         if (mlpi->c_b == ind[c4])
1486         {
1487           /* Update the value */
1488           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
1489               mlp_ats_to_string(mlp->q[c]),
1490               glp_get_col_name (mlp->prob, ind[c4]),
1491               glp_get_row_name (mlp->prob, mlp->r_q[c]),
1492               val[c4],
1493               mlpi->q_averaged[c]);
1494           val[c4] = mlpi->q_averaged[c];
1495           found = GNUNET_YES;
1496           break;
1497         }
1498       }
1499
1500       if (found == GNUNET_NO)
1501         {
1502
1503           ind[length+1] = mlpi->c_b;
1504           val[length+1] = mlpi->q_averaged[c];
1505           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]);
1506           glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
1507         }
1508       else
1509         {
1510         /* Get the index if matrix row of quality */
1511         glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
1512         }
1513
1514       GNUNET_free (ind);
1515       GNUNET_free (val);
1516     }
1517   }
1518 }
1519
1520
1521 /**
1522  * Add a single address to the solve
1523  *
1524  * @param solver the solver Handle
1525  * @param addresses the address hashmap containing all addresses
1526  * @param address the address to add
1527  */
1528 void
1529 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1530 {
1531
1532 }
1533
1534 /**
1535  * Updates a single address in the MLP problem
1536  *
1537  * If the address did not exist before in the problem:
1538  * The MLP problem has to be recreated and the problem has to be resolved
1539  *
1540  * Otherwise the addresses' values can be updated and the existing base can
1541  * be reused
1542  *
1543  * @param solver the MLP Handle
1544  * @param addresses the address hashmap
1545  *        the address has to be already removed from the hashmap
1546  * @param address the address to update
1547  */
1548 void
1549 GAS_mlp_address_update (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1550 {
1551   struct GAS_MLP_Handle *mlp = solver;
1552   int new;
1553   struct MLP_information *mlpi;
1554   struct GAS_MLP_SolutionContext ctx;
1555
1556   GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1557
1558   /* We add a new address */
1559   if (address->mlp_information == NULL)
1560     new = GNUNET_YES;
1561   else
1562     new = GNUNET_NO;
1563
1564   /* Do the update */
1565   if (new == GNUNET_YES)
1566   {
1567     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1568
1569     int c;
1570     for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1571     {
1572       int c2;
1573       mlpi->r_q[c] = 0;
1574       for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1575         mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1576       mlpi->q_avg_i[c] = 0;
1577       mlpi->q_averaged[c] = 0.0;
1578     }
1579
1580     address->mlp_information = mlpi;
1581     mlp->addr_in_problem ++;
1582     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1583
1584     /* Check for and add peer */
1585     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1586     if (peer == NULL)
1587     {
1588
1589       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1590           GNUNET_i2s (&address->peer));
1591
1592       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1593       peer->head = NULL;
1594       peer->tail = NULL;
1595
1596       int c;
1597       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1598       {
1599         peer->f_q[c] = 1.0;
1600       }
1601       peer->f = 1.0;
1602
1603       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1604       GNUNET_assert(address->prev == NULL);
1605       GNUNET_assert(address->next == NULL);
1606       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1607       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1608       mlp->c_p ++;
1609       GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1610     }
1611     else
1612     {
1613
1614       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1615           GNUNET_i2s (&address->peer));
1616
1617       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1618     }
1619     update_quality (mlp, address);
1620   }
1621   else
1622   {
1623     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1624         GNUNET_i2s (&address->peer));
1625
1626     update_quality (mlp, address);
1627   }
1628
1629   /* Recalculate */
1630   if (new == GNUNET_YES)
1631   {
1632     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1633
1634     mlp_delete_problem (mlp);
1635     mlp_create_problem (mlp, addresses);
1636     mlp->presolver_required = GNUNET_YES;
1637   }
1638   if (mlp->auto_solve == GNUNET_YES)
1639     GAS_mlp_solve_problem (mlp, &ctx);
1640 }
1641
1642 /**
1643  * Deletes a single address in the MLP problem
1644  *
1645  * The MLP problem has to be recreated and the problem has to be resolved
1646  *
1647  * @param solver the MLP Handle
1648  * @param addresses the address hashmap
1649  *        the address has to be already removed from the hashmap
1650  * @param address the address to delete
1651  */
1652 void
1653 GAS_mlp_address_delete (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1654 {
1655   struct GAS_MLP_Handle *mlp = solver;
1656   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1657   struct GAS_MLP_SolutionContext ctx;
1658
1659   /* Free resources */
1660   if (address->mlp_information != NULL)
1661   {
1662     GNUNET_free (address->mlp_information);
1663     address->mlp_information = NULL;
1664
1665     mlp->addr_in_problem --;
1666     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1667   }
1668
1669   /* Remove from peer list */
1670   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1671   GNUNET_assert (head != NULL);
1672
1673   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1674
1675   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1676   if ((head->head == NULL) && (head->tail == NULL))
1677   {
1678     /* No address for peer left, remove peer */
1679
1680     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1681
1682     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1683     GNUNET_free (head);
1684     mlp->c_p --;
1685     GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1686   }
1687
1688   /* Update problem */
1689   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1690
1691   mlp_delete_problem (mlp);
1692   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1693   {
1694     mlp_create_problem (mlp, addresses);
1695
1696     /* Recalculate */
1697     mlp->presolver_required = GNUNET_YES;
1698     if (mlp->auto_solve == GNUNET_YES)
1699       GAS_mlp_solve_problem (mlp, &ctx);
1700   }
1701 }
1702
1703 static int
1704 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1705 {
1706
1707   struct ATS_Address *aa = (struct ATS_Address *) cls;
1708   struct ATS_Address *addr = value;
1709   struct MLP_information *mlpi = addr->mlp_information;
1710   if (mlpi == NULL)
1711     return GNUNET_YES;
1712   if (mlpi->n == GNUNET_YES)
1713   {
1714     aa = addr;
1715     if (mlpi->b > (double) UINT32_MAX)
1716       aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1717     else
1718       aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1719     aa->assigned_bw_in.value__ = htonl(0);
1720     return GNUNET_NO;
1721   }
1722   return GNUNET_YES;
1723 }
1724
1725
1726 /**
1727  * Get the preferred address for a specific peer
1728  *
1729  * @param solver the MLP Handle
1730  * @param addresses address hashmap
1731  * @param peer the peer
1732  * @return suggested address
1733  */
1734 const struct ATS_Address *
1735 GAS_mlp_get_preferred_address (void *solver,
1736                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
1737                                const struct GNUNET_PeerIdentity *peer)
1738 {
1739   struct ATS_Address * aa = NULL;
1740   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", GNUNET_i2s (peer));
1741   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, mlp_get_preferred_address_it, aa);
1742   return aa;
1743 }
1744
1745
1746 /**
1747  * Changes the preferences for a peer in the MLP problem
1748  *
1749  * @param solver the MLP Handle
1750  * @param peer the peer
1751  * @param kind the kind to change the preference
1752  * @param score the score
1753  */
1754 void
1755 GAS_mlp_address_change_preference (void *solver,
1756                                    const struct GNUNET_PeerIdentity *peer,
1757                                    enum GNUNET_ATS_PreferenceKind kind,
1758                                    float score)
1759 {
1760   struct GAS_MLP_Handle *mlp = solver;
1761   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1762
1763   //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1764   //FIXME to finish implementation
1765   /* Here we have to do the matching */
1766
1767 }
1768
1769 /**
1770  * Shutdown the MLP problem solving component
1771  *
1772  * @param solver the solver handle
1773  */
1774 void
1775 GAS_mlp_done (void *solver)
1776 {
1777   struct GAS_MLP_Handle *mlp = solver;
1778   struct ATS_Peer * peer;
1779   struct ATS_Address *addr;
1780
1781   GNUNET_assert (mlp != NULL);
1782
1783   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1784   {
1785     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1786     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1787   }
1788
1789   /* clean up peer list */
1790   peer = mlp->peer_head;
1791   while (peer != NULL)
1792   {
1793     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1794     GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1795     for (addr = peer->head; NULL != addr; addr = peer->head)
1796     {
1797       GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1798       GNUNET_free (addr->mlp_information);
1799       addr->mlp_information = NULL;
1800     }
1801     GNUNET_free (peer);
1802     peer = mlp->peer_head;
1803   }
1804   mlp_delete_problem (mlp);
1805
1806   /* Clean up GLPK environment */
1807   glp_free_env();
1808
1809   GNUNET_free (mlp);
1810 }
1811
1812
1813 /* end of gnunet-service-ats_addresses_mlp.c */