src/ats/gnunet-service-ats_addresses_mlp.c

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