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