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 #if 0
 343 /**
 344  * Find the required ATS information for an address
 345  *
 346  * @param addr the address
 347  * @param ats_index the desired ATS index
 348  *
 349  * @return the index on success, otherwise GNUNET_SYSERR
 350  */
 351 static int
 352 mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
 353 {
 354   struct GNUNET_ATS_Information * ats = addr->ats;
 355   int c = 0;
 356   int found = GNUNET_NO;
 357   for (c = 0; c < addr->ats_count; c++)
 358   {
 359     if (ats[c].type == ats_index)
 360     {
 361       found = GNUNET_YES;
 362       break;
 363     }
 364   }
 365   if (found == GNUNET_YES)
 366     return c;
 367   else
 368     return GNUNET_SYSERR;
 369 }
 370 #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  * @param network array of GNUNET_ATS_NetworkType with length dest_length
1077  * @param out_dest array of outbound quotas
1078  * @param in_dest array of outbound quota
1079  * @param dest_length array length for quota arrays
1080  * @param bw_changed_cb callback for changed bandwidth amounts
1081  * @param bw_changed_cb_cls cls for callback
1082  * @return struct GAS_MLP_Handle on success, NULL on fail
1083  */
1084 void *
1085 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
1086               const struct GNUNET_STATISTICS_Handle *stats,
1087               int *network,
1088               unsigned long long *out_dest,
1089               unsigned long long *in_dest,
1090               int dest_length,
1091               GAS_bandwidth_changed_cb bw_changed_cb,
1092               void *bw_changed_cb_cls)
1093 {
1094   struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle));
1095
1096   double D;
1097   double R;
1098   double U;
1099   unsigned long long tmp;
1100   unsigned int b_min;
1101   unsigned int n_min;
1102   struct GNUNET_TIME_Relative i_exec;
1103   int c;
1104   char * quota_out_str;
1105   char * quota_in_str;
1106
1107   struct GNUNET_TIME_Relative max_duration;
1108   long long unsigned int max_iterations;
1109
1110   /* Init GLPK environment */
1111   int res = glp_init_env();
1112   switch (res) {
1113     case 0:
1114       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1115           "initialization successful");
1116       break;
1117     case 1:
1118       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
1119           "environment is already initialized");
1120       break;
1121     case 2:
1122       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1123           "initialization failed (insufficient memory)");
1124       GNUNET_free(mlp);
1125       return NULL;
1126       break;
1127     case 3:
1128       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
1129           "initialization failed (unsupported programming model)");
1130       GNUNET_free(mlp);
1131       return NULL;
1132       break;
1133     default:
1134       break;
1135   }
1136
1137   /* Create initial MLP problem */
1138   mlp->prob = glp_create_prob();
1139   GNUNET_assert (mlp->prob != NULL);
1140
1141   mlp->BIG_M = (double) BIG_M_VALUE;
1142
1143   /* Get timeout for iterations */
1144   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(cfg, "ats", "MAX_DURATION", &max_duration))
1145   {
1146     max_duration = MLP_MAX_EXEC_DURATION;
1147   }
1148
1149   /* Get maximum number of iterations */
1150   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(cfg, "ats", "MAX_ITERATIONS", &max_iterations))
1151   {
1152     max_iterations = MLP_MAX_ITERATIONS;
1153   }
1154
1155   /* Get diversity coefficient from configuration */
1156   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1157                                                       "COEFFICIENT_D",
1158                                                       &tmp))
1159     D = (double) tmp / 100;
1160   else
1161     D = 1.0;
1162
1163   /* Get proportionality coefficient from configuration */
1164   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1165                                                       "COEFFICIENT_R",
1166                                                       &tmp))
1167     R = (double) tmp / 100;
1168   else
1169     R = 1.0;
1170
1171   /* Get utilization coefficient from configuration */
1172   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1173                                                       "COEFFICIENT_U",
1174                                                       &tmp))
1175     U = (double) tmp / 100;
1176   else
1177     U = 1.0;
1178
1179   /* Get quality metric coefficients from configuration */
1180   int i_delay = -1;
1181   int i_distance = -1;
1182   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
1183   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1184   {
1185     /* initialize quality coefficients with default value 1.0 */
1186     mlp->co_Q[c] = 1.0;
1187
1188     mlp->q[c] = q[c];
1189     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
1190       i_delay = c;
1191     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
1192       i_distance = c;
1193   }
1194
1195   if ((i_delay != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1196                                                       "COEFFICIENT_QUALITY_DELAY",
1197                                                       &tmp)))
1198
1199     mlp->co_Q[i_delay] = (double) tmp / 100;
1200   else
1201     mlp->co_Q[i_delay] = 1.0;
1202
1203   if ((i_distance != -1) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1204                                                       "COEFFICIENT_QUALITY_DISTANCE",
1205                                                       &tmp)))
1206     mlp->co_Q[i_distance] = (double) tmp / 100;
1207   else
1208     mlp->co_Q[i_distance] = 1.0;
1209
1210   /* Get minimum bandwidth per used address from configuration */
1211   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1212                                                       "MIN_BANDWIDTH",
1213                                                       &tmp))
1214     b_min = tmp;
1215   else
1216   {
1217     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
1218   }
1219
1220   /* Get minimum number of connections from configuration */
1221   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (cfg, "ats",
1222                                                       "MIN_CONNECTIONS",
1223                                                       &tmp))
1224     n_min = tmp;
1225   else
1226     n_min = 4;
1227
1228   /* Init network quotas */
1229   int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType;
1230   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1231   {
1232     mlp->quota_index[c] = quotas[c];
1233     static char * entry_in = NULL;
1234     static char * entry_out = NULL;
1235     unsigned long long quota_in = 0;
1236     unsigned long long quota_out = 0;
1237
1238     switch (quotas[c]) {
1239       case GNUNET_ATS_NET_UNSPECIFIED:
1240         entry_out = "UNSPECIFIED_QUOTA_OUT";
1241         entry_in = "UNSPECIFIED_QUOTA_IN";
1242         break;
1243       case GNUNET_ATS_NET_LOOPBACK:
1244         entry_out = "LOOPBACK_QUOTA_OUT";
1245         entry_in = "LOOPBACK_QUOTA_IN";
1246         break;
1247       case GNUNET_ATS_NET_LAN:
1248         entry_out = "LAN_QUOTA_OUT";
1249         entry_in = "LAN_QUOTA_IN";
1250         break;
1251       case GNUNET_ATS_NET_WAN:
1252         entry_out = "WAN_QUOTA_OUT";
1253         entry_in = "WAN_QUOTA_IN";
1254         break;
1255       case GNUNET_ATS_NET_WLAN:
1256         entry_out = "WLAN_QUOTA_OUT";
1257         entry_in = "WLAN_QUOTA_IN";
1258         break;
1259       default:
1260         break;
1261     }
1262
1263     if ((entry_in == NULL) || (entry_out == NULL))
1264       continue;
1265
1266     if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_out, &quota_out_str))
1267     {
1268       if (0 == strcmp(quota_out_str, BIG_M_STRING) ||
1269           (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_out_str, &quota_out)))
1270         quota_out = mlp->BIG_M;
1271
1272       GNUNET_free (quota_out_str);
1273       quota_out_str = NULL;
1274     }
1275     else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1276     {
1277       quota_out = mlp->BIG_M;
1278     }
1279     else
1280     {
1281       quota_out = mlp->BIG_M;
1282     }
1283
1284     if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_string(cfg, "ats", entry_in, &quota_in_str))
1285     {
1286       if (0 == strcmp(quota_in_str, BIG_M_STRING) ||
1287           (GNUNET_SYSERR == GNUNET_STRINGS_fancy_size_to_bytes (quota_in_str, &quota_in)))
1288         quota_in = mlp->BIG_M;
1289
1290       GNUNET_free (quota_in_str);
1291       quota_in_str = NULL;
1292     }
1293     else if (GNUNET_ATS_NET_UNSPECIFIED == quotas[c])
1294     {
1295       quota_in = mlp->BIG_M;
1296     }
1297     else
1298     {
1299       quota_in = mlp->BIG_M;
1300     }
1301
1302     /* Check if defined quota could make problem unsolvable */
1303     if (((n_min * b_min) > quota_out) && (GNUNET_ATS_NET_UNSPECIFIED != quotas[c]))
1304     {
1305       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Inconsistent quota configuration value `%s': "
1306                   "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);
1307
1308       GAS_mlp_done(mlp);
1309       mlp = NULL;
1310       return NULL;
1311     }
1312
1313     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found `%s' quota %llu and `%s' quota %llu\n",
1314                 entry_out, quota_out, entry_in, quota_in);
1315     GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_out, quota_out, GNUNET_NO);
1316     GNUNET_STATISTICS_update ((struct GNUNET_STATISTICS_Handle *) stats, entry_in, quota_in, GNUNET_NO);
1317     mlp->quota_out[c] = quota_out;
1318     mlp->quota_in[c] = quota_in;
1319   }
1320
1321   /* Get minimum number of connections from configuration */
1322   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_time (cfg, "ats",
1323                                                         "ATS_EXEC_INTERVAL",
1324                                                         &i_exec))
1325     mlp->exec_interval = i_exec;
1326   else
1327     mlp->exec_interval = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30);
1328
1329   mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
1330   mlp->max_iterations = max_iterations;
1331   mlp->max_exec_duration = max_duration;
1332   mlp->auto_solve = GNUNET_YES;
1333
1334   /* Redirect GLPK output to GNUnet logging */
1335   glp_error_hook((void *) mlp, &mlp_term_hook);
1336
1337   /* Init LP solving parameters */
1338   glp_init_smcp(&mlp->control_param_lp);
1339
1340   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
1341 #if VERBOSE_GLPK
1342   mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
1343 #endif
1344
1345   mlp->control_param_lp.it_lim = max_iterations;
1346   mlp->control_param_lp.tm_lim = max_duration.rel_value;
1347
1348   /* Init MLP solving parameters */
1349   glp_init_iocp(&mlp->control_param_mlp);
1350
1351   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
1352 #if VERBOSE_GLPK
1353   mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
1354 #endif
1355   mlp->control_param_mlp.tm_lim = max_duration.rel_value;
1356
1357   mlp->last_execution = GNUNET_TIME_UNIT_FOREVER_ABS;
1358
1359   mlp->co_D = D;
1360   mlp->co_R = R;
1361   mlp->co_U = U;
1362   mlp->b_min = b_min;
1363   mlp->n_min = n_min;
1364   mlp->m_q = GNUNET_ATS_QualityPropertiesCount;
1365   mlp->semaphore = GNUNET_NO;
1366   return mlp;
1367 }
1368
1369 static void
1370 update_quality (struct GAS_MLP_Handle *mlp, struct ATS_Address * address)
1371 {
1372   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality metrics for peer `%s'\n",
1373       GNUNET_i2s (&address->peer));
1374
1375   GNUNET_assert (NULL != address);
1376   GNUNET_assert (NULL != address->solver_information);
1377 //  GNUNET_assert (NULL != address->ats);
1378
1379   struct MLP_information *mlpi = address->solver_information;
1380   //struct GNUNET_ATS_Information *ats = address->ats;
1381   GNUNET_assert (mlpi != NULL);
1382
1383   int c;
1384   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1385   {
1386
1387     /* FIXME int index = mlp_lookup_ats(address, mlp->q[c]); */
1388     int index = GNUNET_SYSERR;
1389
1390     if (index == GNUNET_SYSERR)
1391       continue;
1392     /* FIXME
1393     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s' value `%s': %f\n",
1394         GNUNET_i2s (&address->peer),
1395         mlp_ats_to_string(mlp->q[c]),
1396         (double) ats[index].value);
1397
1398     int i = mlpi->q_avg_i[c];*/
1399     double * qp = mlpi->q[c];
1400     /* FIXME
1401     qp[i] = (double) ats[index].value;
1402     */
1403
1404     int t;
1405     for (t = 0; t < MLP_AVERAGING_QUEUE_LENGTH; t++)
1406     {
1407       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' queue[%u]: %f\n",
1408         GNUNET_i2s (&address->peer),
1409         mlp_ats_to_string(mlp->q[c]),
1410         t,
1411         qp[t]);
1412     }
1413
1414     if (mlpi->q_avg_i[c] + 1 < (MLP_AVERAGING_QUEUE_LENGTH))
1415       mlpi->q_avg_i[c] ++;
1416     else
1417       mlpi->q_avg_i[c] = 0;
1418
1419
1420     int c2;
1421     int c3;
1422     double avg = 0.0;
1423     switch (mlp->q[c])
1424     {
1425       case GNUNET_ATS_QUALITY_NET_DELAY:
1426         c3 = 0;
1427         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1428         {
1429           if (mlpi->q[c][c2] != -1)
1430           {
1431             double * t2 = mlpi->q[c] ;
1432             avg += t2[c2];
1433             c3 ++;
1434           }
1435         }
1436         if ((c3 > 0) && (avg > 0))
1437           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1438           mlpi->q_averaged[c] = (double) c3 / avg;
1439         else
1440           mlpi->q_averaged[c] = 0.0;
1441
1442         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1443           GNUNET_i2s (&address->peer),
1444           mlp_ats_to_string(mlp->q[c]),
1445           avg,
1446           avg / (double) c3,
1447           mlpi->q_averaged[c]);
1448
1449         break;
1450       case GNUNET_ATS_QUALITY_NET_DISTANCE:
1451         c3 = 0;
1452         for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1453         {
1454           if (mlpi->q[c][c2] != -1)
1455           {
1456             double * t2 = mlpi->q[c] ;
1457             avg += t2[c2];
1458             c3 ++;
1459           }
1460         }
1461         if ((c3 > 0) && (avg > 0))
1462           /* avg = 1 / ((q[0] + ... + q[l]) /c3) => c3 / avg*/
1463           mlpi->q_averaged[c] = (double) c3 / avg;
1464         else
1465           mlpi->q_averaged[c] = 0.0;
1466
1467         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s': `%s' average sum: %f, average: %f, weight: %f\n",
1468           GNUNET_i2s (&address->peer),
1469           mlp_ats_to_string(mlp->q[c]),
1470           avg,
1471           avg / (double) c3,
1472           mlpi->q_averaged[c]);
1473
1474         break;
1475       default:
1476         break;
1477     }
1478
1479     if ((mlpi->c_b != 0) && (mlpi->r_q[c] != 0))
1480     {
1481
1482       /* Get current number of columns */
1483       int found = GNUNET_NO;
1484       int cols = glp_get_num_cols(mlp->prob);
1485       int *ind = GNUNET_malloc (cols * sizeof (int) + 1);
1486       double *val = GNUNET_malloc (cols * sizeof (double) + 1);
1487
1488       /* Get the matrix row of quality */
1489       int length = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
1490       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "cols %i, length %i c_b %i\n", cols, length, mlpi->c_b);
1491       int c4;
1492       /* Get the index if matrix row of quality */
1493       for (c4 = 1; c4 <= length; c4++ )
1494       {
1495         if (mlpi->c_b == ind[c4])
1496         {
1497           /* Update the value */
1498           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating quality `%s' column `%s' row `%s' : %f -> %f\n",
1499               mlp_ats_to_string(mlp->q[c]),
1500               glp_get_col_name (mlp->prob, ind[c4]),
1501               glp_get_row_name (mlp->prob, mlp->r_q[c]),
1502               val[c4],
1503               mlpi->q_averaged[c]);
1504           val[c4] = mlpi->q_averaged[c];
1505           found = GNUNET_YES;
1506           break;
1507         }
1508       }
1509
1510       if (found == GNUNET_NO)
1511         {
1512
1513           ind[length+1] = mlpi->c_b;
1514           val[length+1] = mlpi->q_averaged[c];
1515           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]);
1516           glp_set_mat_row (mlp->prob, mlpi->r_q[c], length+1, ind, val);
1517         }
1518       else
1519         {
1520         /* Get the index if matrix row of quality */
1521         glp_set_mat_row (mlp->prob, mlpi->r_q[c], length, ind, val);
1522         }
1523
1524       GNUNET_free (ind);
1525       GNUNET_free (val);
1526     }
1527   }
1528 }
1529
1530
1531 /**
1532  * Add a single address to the solve
1533  *
1534  * @param solver the solver Handle
1535  * @param addresses the address hashmap containing all addresses
1536  * @param address the address to add
1537  */
1538 void
1539 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1540 {
1541
1542 }
1543
1544 /**
1545  * Updates a single address in the MLP problem
1546  *
1547  * If the address did not exist before in the problem:
1548  * The MLP problem has to be recreated and the problem has to be resolved
1549  *
1550  * Otherwise the addresses' values can be updated and the existing base can
1551  * be reused
1552  *
1553  * @param solver the solver Handle
1554  * @param addresses the address hashmap containing all addresses
1555  * @param address the update address
1556  * @param session the new session (if changed otherwise current)
1557  * @param in_use the new address in use state (if changed otherwise current)
1558  * @param atsi the latest ATS information
1559  * @param atsi_count the atsi count
1560  */
1561 void
1562 GAS_mlp_address_update (void *solver,
1563                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
1564                         struct ATS_Address *address,
1565                         uint32_t session,
1566                         int in_use,
1567                         const struct GNUNET_ATS_Information *atsi,
1568                         uint32_t atsi_count)
1569 {
1570   struct GAS_MLP_Handle *mlp = solver;
1571   int new;
1572   struct MLP_information *mlpi;
1573   struct GAS_MLP_SolutionContext ctx;
1574
1575   GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1576
1577   /* We add a new address */
1578   if (address->solver_information == NULL)
1579     new = GNUNET_YES;
1580   else
1581     new = GNUNET_NO;
1582
1583   /* Do the update */
1584   if (new == GNUNET_YES)
1585   {
1586     mlpi = GNUNET_malloc (sizeof (struct MLP_information));
1587
1588     int c;
1589     for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1590     {
1591       int c2;
1592       mlpi->r_q[c] = 0;
1593       for (c2 = 0; c2 < MLP_AVERAGING_QUEUE_LENGTH; c2++)
1594         mlpi->q[c][c2] = -1.0; /* -1.0: invalid value */
1595       mlpi->q_avg_i[c] = 0;
1596       mlpi->q_averaged[c] = 0.0;
1597     }
1598
1599     address->solver_information = mlpi;
1600     mlp->addr_in_problem ++;
1601     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", 1, GNUNET_NO);
1602
1603     /* Check for and add peer */
1604     struct ATS_Peer *peer = mlp_find_peer (mlp, &address->peer);
1605     if (peer == NULL)
1606     {
1607
1608       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer `%s'\n",
1609           GNUNET_i2s (&address->peer));
1610
1611       peer = GNUNET_malloc (sizeof (struct ATS_Peer));
1612       peer->head = NULL;
1613       peer->tail = NULL;
1614
1615       int c;
1616       for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
1617       {
1618         peer->f_q[c] = 1.0;
1619       }
1620       peer->f = 1.0;
1621
1622       memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
1623       GNUNET_assert(address->prev == NULL);
1624       GNUNET_assert(address->next == NULL);
1625       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1626       GNUNET_CONTAINER_DLL_insert (mlp->peer_head, mlp->peer_tail, peer);
1627       mlp->c_p ++;
1628       GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", 1, GNUNET_NO);
1629     }
1630     else
1631     {
1632
1633       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Adding address to peer `%s'\n",
1634           GNUNET_i2s (&address->peer));
1635
1636       GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
1637     }
1638     update_quality (mlp, address);
1639   }
1640   else
1641   {
1642     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Updating existing address to peer `%s'\n",
1643         GNUNET_i2s (&address->peer));
1644
1645     update_quality (mlp, address);
1646   }
1647
1648   /* Recalculate */
1649   if (new == GNUNET_YES)
1650   {
1651     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1652
1653     mlp_delete_problem (mlp);
1654     mlp_create_problem (mlp, addresses);
1655     mlp->presolver_required = GNUNET_YES;
1656   }
1657   if (mlp->auto_solve == GNUNET_YES)
1658     GAS_mlp_solve_problem (mlp, &ctx);
1659 }
1660
1661 /**
1662  * Deletes a single address in the MLP problem
1663  *
1664  * The MLP problem has to be recreated and the problem has to be resolved
1665  *
1666  * @param solver the MLP Handle
1667  * @param addresses the address hashmap
1668  *        the address has to be already removed from the hashmap
1669  * @param address the address to delete
1670  * @param session_only delete only session not whole address
1671  */
1672 void
1673 GAS_mlp_address_delete (void *solver,
1674     struct GNUNET_CONTAINER_MultiHashMap * addresses,
1675     struct ATS_Address *address,
1676     int session_only)
1677 {
1678   struct GAS_MLP_Handle *mlp = solver;
1679   GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1680   struct GAS_MLP_SolutionContext ctx;
1681
1682   /* Free resources */
1683   if (address->solver_information != NULL)
1684   {
1685     GNUNET_free (address->solver_information);
1686     address->solver_information = NULL;
1687
1688     mlp->addr_in_problem --;
1689     GNUNET_STATISTICS_update (mlp->stats, "# addresses in MLP", -1, GNUNET_NO);
1690   }
1691
1692   /* Remove from peer list */
1693   struct ATS_Peer *head = mlp_find_peer (mlp, &address->peer);
1694   GNUNET_assert (head != NULL);
1695
1696   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for `%s'\n", GNUNET_i2s (&address->peer));
1697
1698   GNUNET_CONTAINER_DLL_remove (head->head, head->tail, address);
1699   if ((head->head == NULL) && (head->tail == NULL))
1700   {
1701     /* No address for peer left, remove peer */
1702
1703     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Deleting peer `%s'\n", GNUNET_i2s (&address->peer));
1704
1705     GNUNET_CONTAINER_DLL_remove (mlp->peer_head, mlp->peer_tail, head);
1706     GNUNET_free (head);
1707     mlp->c_p --;
1708     GNUNET_STATISTICS_update (mlp->stats, "# peers in MLP", -1, GNUNET_NO);
1709   }
1710
1711   /* Update problem */
1712   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Recreating problem: new address\n");
1713
1714   mlp_delete_problem (mlp);
1715   if ((GNUNET_CONTAINER_multihashmap_size (addresses) > 0) && (mlp->c_p > 0))
1716   {
1717     mlp_create_problem (mlp, addresses);
1718
1719     /* Recalculate */
1720     mlp->presolver_required = GNUNET_YES;
1721     if (mlp->auto_solve == GNUNET_YES)
1722       GAS_mlp_solve_problem (mlp, &ctx);
1723   }
1724 }
1725
1726 static int
1727 mlp_get_preferred_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
1728 {
1729
1730   struct ATS_Address *aa = (struct ATS_Address *) cls;
1731   struct ATS_Address *addr = value;
1732   struct MLP_information *mlpi = addr->solver_information;
1733   if (mlpi == NULL)
1734     return GNUNET_YES;
1735   if (mlpi->n == GNUNET_YES)
1736   {
1737     aa = addr;
1738     if (mlpi->b > (double) UINT32_MAX)
1739       aa->assigned_bw_out.value__ = htonl (UINT32_MAX);
1740     else
1741       aa->assigned_bw_out.value__ = htonl((uint32_t) mlpi->b);
1742     aa->assigned_bw_in.value__ = htonl(0);
1743     return GNUNET_NO;
1744   }
1745   return GNUNET_YES;
1746 }
1747
1748
1749 /**
1750  * Get the preferred address for a specific peer
1751  *
1752  * @param solver the MLP Handle
1753  * @param addresses address hashmap
1754  * @param peer the peer
1755  * @return suggested address
1756  */
1757 const struct ATS_Address *
1758 GAS_mlp_get_preferred_address (void *solver,
1759                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
1760                                const struct GNUNET_PeerIdentity *peer)
1761 {
1762   struct ATS_Address * aa = NULL;
1763   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", GNUNET_i2s (peer));
1764   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey, mlp_get_preferred_address_it, aa);
1765   return aa;
1766 }
1767
1768
1769 /**
1770  * Changes the preferences for a peer in the MLP problem
1771  *
1772  * @param solver the MLP Handle
1773  * @param peer the peer
1774  * @param kind the kind to change the preference
1775  * @param score the score
1776  */
1777 void
1778 GAS_mlp_address_change_preference (void *solver,
1779                                    void *client,
1780                                    const struct GNUNET_PeerIdentity *peer,
1781                                    enum GNUNET_ATS_PreferenceKind kind,
1782                                    float score)
1783 {
1784   struct GAS_MLP_Handle *mlp = solver;
1785   GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO);
1786
1787   //struct ATS_Peer *p = mlp_find_peer (mlp, peer);
1788   //FIXME to finish implementation
1789   /* Here we have to do the matching */
1790
1791 }
1792
1793 /**
1794  * Shutdown the MLP problem solving component
1795  *
1796  * @param solver the solver handle
1797  */
1798 void
1799 GAS_mlp_done (void *solver)
1800 {
1801   struct GAS_MLP_Handle *mlp = solver;
1802   struct ATS_Peer * peer;
1803   struct ATS_Address *addr;
1804
1805   GNUNET_assert (mlp != NULL);
1806
1807   if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
1808   {
1809     GNUNET_SCHEDULER_cancel(mlp->mlp_task);
1810     mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK;
1811   }
1812
1813   /* clean up peer list */
1814   peer = mlp->peer_head;
1815   while (peer != NULL)
1816   {
1817     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Cleaning up peer `%s'\n", GNUNET_i2s (&peer->id));
1818     GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
1819     for (addr = peer->head; NULL != addr; addr = peer->head)
1820     {
1821       GNUNET_CONTAINER_DLL_remove(peer->head, peer->tail, addr);
1822       GNUNET_free (addr->solver_information);
1823       addr->solver_information = NULL;
1824     }
1825     GNUNET_free (peer);
1826     peer = mlp->peer_head;
1827   }
1828   mlp_delete_problem (mlp);
1829
1830   /* Clean up GLPK environment */
1831   glp_free_env();
1832
1833   GNUNET_free (mlp);
1834 }
1835
1836
1837 /* end of gnunet-service-ats_addresses_mlp.c */