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