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