src/ats/plugin_ats_mlp.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2011-2014 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/plugin_ats_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_ats_service.h"
  30 #include "gnunet_ats_plugin.h"
  31 #include "gnunet-service-ats_addresses.h"
  32 #include "gnunet_statistics_service.h"
  33 #include <float.h>
  34 #include <glpk.h>
  35
  36
  37 #define BIG_M_VALUE (UINT32_MAX) /10
  38 #define BIG_M_STRING "unlimited"
  39
  40 #define MLP_AVERAGING_QUEUE_LENGTH 3
  41
  42 #define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
  43 #define MLP_MAX_ITERATIONS      4096
  44
  45 #define MLP_DEFAULT_D 1.0
  46 #define MLP_DEFAULT_R 1.0
  47 #define MLP_DEFAULT_U 1.0
  48 #define MLP_DEFAULT_QUALITY 1.0
  49 #define MLP_DEFAULT_MIN_CONNECTIONS 4
  50 #define MLP_DEFAULT_PEER_PREFERENCE 1.0
  51
  52 #define MLP_NaN -1
  53 #define MLP_UNDEFINED 0
  54 #define GLP_YES 1.0
  55 #define GLP_NO  0.0
  56
  57 enum MLP_Output_Format
  58 {
  59   MLP_MPS,
  60   MLP_CPLEX,
  61   MLP_GLPK
  62 };
  63
  64
  65 struct MLP_Solution
  66 {
  67   int lp_res;
  68   int lp_presolv;
  69   int mip_res;
  70   int mip_presolv;
  71
  72   double lp_objective_value;
  73   double mlp_objective_value;
  74   double mlp_gap;
  75   double lp_mlp_gap;
  76
  77   int p_elements;
  78   int p_cols;
  79   int p_rows;
  80
  81   int n_peers;
  82   int n_addresses;
  83
  84 };
  85
  86 struct ATS_Peer
  87 {
  88   struct GNUNET_PeerIdentity id;
  89
  90   /* Was this peer already added to the current problem? */
  91   int processed;
  92
  93   /* constraint 2: 1 address per peer*/
  94   unsigned int r_c2;
  95
  96   /* constraint 9: relativity */
  97   unsigned int r_c9;
  98
  99   /* Legacy preference value */
 100   double f;
 101 };
 102
 103 struct MLP_Problem
 104 {
 105   /**
 106    * GLPK (MLP) problem object
 107    */
 108   glp_prob *prob;
 109
 110   /* Number of addresses in problem */
 111   unsigned int num_addresses;
 112   /* Number of peers in problem */
 113   unsigned int num_peers;
 114   /* Number of elements in problem matrix */
 115   unsigned int num_elements;
 116
 117   /* Row index constraint 2: */
 118   unsigned int r_c2;
 119   /* Row index constraint 4: minimum connections */
 120   unsigned int r_c4;
 121   /* Row index constraint 6: maximize diversity */
 122   unsigned int r_c6;
 123   /* Row index constraint 8: utilization*/
 124   unsigned int r_c8;
 125   /* Row index constraint 9: relativity*/
 126   unsigned int r_c9;
 127   /* Row indices quality metrics  */
 128   int r_q[GNUNET_ATS_QualityPropertiesCount];
 129   /* Row indices ATS network quotas */
 130   int r_quota[GNUNET_ATS_NetworkTypeCount];
 131
 132   /* Column index Diversity (D) column */
 133   int c_d;
 134   /* Column index Utilization (U) column */
 135   int c_u;
 136   /* Column index Proportionality (R) column */
 137   int c_r;
 138   /* Column index quality metrics  */
 139   int c_q[GNUNET_ATS_QualityPropertiesCount];
 140
 141   /* Problem matrix */
 142   /* Current index */
 143   unsigned int ci;
 144   /* Row index array */
 145   int *ia;
 146   /* Column index array */
 147   int *ja;
 148   /* Column index value */
 149   double *ar;
 150
 151 };
 152
 153 struct MLP_Variables
 154 {
 155   /* Big M value for bandwidth capping */
 156   double BIG_M;
 157
 158   /* MIP Gap */
 159   double mip_gap;
 160
 161   /* LP MIP Gap */
 162   double lp_mip_gap;
 163
 164   /* ATS Quality metrics
 165    *
 166    * Array with GNUNET_ATS_QualityPropertiesCount elements
 167    * contains mapping to GNUNET_ATS_Property*/
 168   int q[GNUNET_ATS_QualityPropertiesCount];
 169
 170   /* Number of quality metrics */
 171   int m_q;
 172
 173   /* Number of quality metrics */
 174   int m_rc;
 175
 176   /* Quality metric coefficients*/
 177   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 178
 179   /* Ressource costs coefficients*/
 180   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 181
 182   /* Diversity coefficient */
 183   double co_D;
 184
 185   /* Utility coefficient */
 186   double co_U;
 187
 188   /* Relativity coefficient */
 189   double co_R;
 190
 191   /* Minimum bandwidth assigned to an address */
 192   unsigned int b_min;
 193
 194   /* Minimum number of addresses with bandwidth assigned */
 195   unsigned int n_min;
 196
 197   /* Quotas */
 198   /* Array mapping array index to ATS network */
 199   int quota_index[GNUNET_ATS_NetworkTypeCount];
 200   /* Outbound quotas */
 201   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 202   /* Inbound quotas */
 203
 204   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 205
 206   /* ATS ressource costs
 207    * array with GNUNET_ATS_QualityPropertiesCount elements
 208    * contains mapping to GNUNET_ATS_Property
 209    * */
 210   int rc[GNUNET_ATS_QualityPropertiesCount];
 211
 212 };
 213
 214 /**
 215  * MLP Handle
 216  */
 217 struct GAS_MLP_Handle
 218 {
 219   struct GNUNET_ATS_PluginEnvironment *env;
 220
 221   /**
 222    * Exclude peer from next result propagation
 223    */
 224   const struct GNUNET_PeerIdentity *exclude_peer;
 225
 226   /**
 227    * Encapsulation for the MLP problem
 228    */
 229   struct MLP_Problem p;
 230
 231   /**
 232    * Encapsulation for the MLP problem variables
 233    */
 234   struct MLP_Variables pv;
 235
 236   /**
 237    * Encapsulation for the MLP solution
 238    */
 239   struct MLP_Solution ps;
 240
 241   /**
 242    * Bulk lock
 243    */
 244   int stat_bulk_lock;
 245
 246   /**
 247    * Number of changes while solver was locked
 248    */
 249   int stat_bulk_requests;
 250
 251   /**
 252    * GLPK LP control parameter
 253    */
 254   glp_smcp control_param_lp;
 255
 256   /**
 257    * GLPK LP control parameter
 258    */
 259   glp_iocp control_param_mlp;
 260
 261   /**
 262    * Peers with pending address requests
 263    */
 264   struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
 265
 266   /**
 267    * Was the problem updated since last solution
 268    */
 269   int stat_mlp_prob_updated;
 270
 271   /**
 272    * Has the problem size changed since last solution
 273    */
 274   int stat_mlp_prob_changed;
 275
 276   /**
 277    * Solve the problem automatically when updates occur?
 278    * Default: GNUNET_YES
 279    * Can be disabled for test and measurements
 280    */
 281   int opt_mlp_auto_solve;
 282
 283   /**
 284    * Write all MILP problems to a MPS file
 285    */
 286   int opt_dump_problem_all;
 287
 288   /**
 289    * Write all MILP problem solutions to a file
 290    */
 291   int opt_dump_solution_all;
 292
 293   /**
 294    * Write MILP problems to a MPS file when solver fails
 295    */
 296   int opt_dump_problem_on_fail;
 297
 298   /**
 299    * Write MILP problem solutions to a file when solver fails
 300    */
 301   int opt_dump_solution_on_fail;
 302
 303   /**
 304    * solve feasibility only
 305    */
 306   int opt_dbg_feasibility_only;
 307
 308   /**
 309    * solve autoscale the problem
 310    */
 311   int opt_dbg_autoscale_problem;
 312
 313   /**
 314    * use the intopt presolver instead of simplex
 315    */
 316   int opt_dbg_intopt_presolver;
 317
 318   /**
 319    * Print GLPK output
 320    */
 321   int opt_dbg_glpk_verbose;
 322
 323   /**
 324    * solve autoscale the problem
 325    */
 326   int opt_dbg_optimize_relativity;
 327
 328   /**
 329    * solve autoscale the problem
 330    */
 331   int opt_dbg_optimize_diversity;
 332
 333   /**
 334    * solve autoscale the problem
 335    */
 336   int opt_dbg_optimize_quality;
 337
 338   /**
 339    * solve autoscale the problem
 340    */
 341   int opt_dbg_optimize_utility;
 342
 343
 344   /**
 345    * Output format
 346    */
 347   enum MLP_Output_Format opt_log_format;
 348 };
 349
 350 /**
 351  * Address specific MLP information
 352  */
 353 struct MLP_information
 354 {
 355
 356   /**
 357    * Bandwidth assigned outbound
 358    */
 359   uint32_t b_out;
 360
 361   /**
 362    * Bandwidth assigned inbound
 363    */
 364   uint32_t b_in;
 365
 366   /**
 367    * Address selected
 368    */
 369   int n;
 370
 371   /**
 372    * bandwidth column index
 373    */
 374   signed int c_b;
 375
 376   /**
 377    * address usage column
 378    */
 379   signed int c_n;
 380
 381   /* row indexes */
 382
 383   /**
 384    * constraint 1: bandwidth capping
 385    */
 386   unsigned int r_c1;
 387
 388   /**
 389    * constraint 3: minimum bandwidth
 390    */
 391   unsigned int r_c3;
 392 };
 393
 394
 395
 396 /**
 397  *
 398  * NOTE: Do not modify this documentation. This documentation is based on
 399  * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
 400  * use build_txt.sh to generate plaintext output
 401  *
 402  *    The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
 403  *    optimizing an mixed integer programming problem. The MLP solver uses a
 404  *    number of constraints to find the best adddress for a peer and an optimal
 405  *    bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
 406  *    MLP problem.
 407  *
 408  *    We defined a constraint system to find an optimal bandwidth assignment.
 409  *    This constraint system uses as an input data addresses, bandwidth quotas,
 410  *    preferences and quality values. This constraint system is stored in an
 411  *    matrix based equotation system.
 412  *
 413  *   5 Using GLPK
 414  *
 415  *    A (M)LP problem consists of a target function to optimizes, constraints
 416  *    and rows and columns. FIXME GLP uses three arrays to index the matrix: two
 417  *    integer arrays storing the row and column indices in the matrix and an
 418  *    float array to store the coeeficient.
 419  *
 420  *    To solve the problem we first find an initial solution for the LP problem
 421  *    using the LP solver and then find an MLP solution based on this solution
 422  *    using the MLP solver.
 423  *
 424  *    Solving (M)LP problems has the property that finding an initial solution
 425  *    for the LP problem is computationally expensive and finding the MLP
 426  *    solution is cheaper. This is especially interesting an existing LP
 427  *    solution can be reused if only coefficients in the matrix have changed
 428  *    (addresses updated). Only when the problem size changes (addresses added
 429  *    or deleted) a new LP solution has to be found.
 430  *
 431  *    Intended usage
 432  *    The mlp solver solves the bandwidth assignment problem only on demand when
 433  *    an address suggestion is requested. When an address is requested mlp the
 434  *    solves the mlp problem and if the active address or the bandwidth assigned
 435  *    changes it calls the callback to addresses. The mlp solver gets notified
 436  *    about new addresses (adding sessions), removed addresses (address
 437  *    deletions) and address updates. To benefit from the mlp properties
 438  *    mentioned in section 5 the solver rembers if since the last solution
 439  *    addresses were added or deleted (problem size changed, problem has to be
 440  *    rebuild and solved from sratch) or if addresses were updated and the
 441  *    existing solution can be reused.
 442  *
 443  *     5.1 Input data
 444  *
 445  *    The quotas for each network segment are passed by addresses. MLP can be
 446  *    adapted using configuration settings and uses the following parameters:
 447  *      * MLP_MAX_DURATION:
 448  *        Maximum duration for a MLP solution procees (default: 3 sec.)
 449  *      * MLP_MAX_ITERATIONS:
 450  *        Maximum number of iterations for a MLP solution process (default:
 451  *        1024)
 452  *      * MLP_MIN_CONNECTIONS:
 453  *        Minimum number of desired connections (default: 4)
 454  *      * MLP_MIN_BANDWIDTH:
 455  *        Minimum amount of bandwidth assigned to an address (default: 1024)
 456  *      * MLP_COEFFICIENT_D:
 457  *        Diversity coefficient (default: 1.0)
 458  *      * MLP_COEFFICIENT_R:
 459  *        Relativity coefficient (default: 1.0)
 460  *      * MLP_COEFFICIENT_U:
 461  *        Utilization coefficient (default: 1.0)
 462  *      * MLP_COEFFICIENT_D:
 463  *        Diversity coefficient (default: 1.0)
 464  *      * MLP_COEFFICIENT_QUALITY_DELAY:
 465  *        Quality delay coefficient (default: 1.0)
 466  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 467  *        Quality distance coefficient (default: 1.0)
 468  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 469  *        Quality distance coefficient (default: 1.0)
 470  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 471  *        Quality distance coefficient (default: 1.0)
 472  *      * MLP_COEFFICIENT_QUALITY_DISTANCE:
 473  *        Quality distance coefficient (default: 1.0)
 474  *
 475  *     5.2 Data structures used
 476  *
 477  *    mlp has for each known peer a struct ATS_Peer containing information about
 478  *    a specific peer. The address field solver_information contains information
 479  *    about the mlp properties of this address.
 480  *
 481  *     5.3 Initializing
 482  *
 483  *    During initialization mlp initializes the GLPK libray used to solve the
 484  *    MLP problem: it initializes the glpk environment and creates an initial LP
 485  *    problem. Next it loads the configuration values from the configuration or
 486  *    uses the default values configured in -addresses_mlp.h. The quotas used
 487  *    are given by addresses but may have to be adjusted. mlp uses a upper limit
 488  *    for the bandwidth assigned called BIG M and a minimum amount of bandwidth
 489  *    an address gets assigned as well as a minium desired number of
 490  *    connections. If the configured quota is bigger than BIG M, it is reduced
 491  *    to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
 492  *    *MLP_MIN_BANDWIDTH it is increased to this value.
 493  *
 494  *     5.4 Shutdown
 495
 496  */
 497
 498 #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
 499
 500 /**
 501  * Print debug output for mlp problem creation
 502  */
 503 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
 504
 505
 506 /**
 507  * Intercept GLPK terminal output
 508  * @param info the mlp handle
 509  * @param s the string to print
 510  * @return 0: glpk prints output on terminal, 0 != surpress output
 511  */
 512 static int
 513 mlp_term_hook (void *info, const char *s)
 514 {
 515   struct GAS_MLP_Handle *mlp = info;
 516
 517   if (mlp->opt_dbg_glpk_verbose)
 518     LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
 519   return 1;
 520 }
 521
 522
 523 /**
 524  * Reset peers for next problem creation
 525  *
 526  * @param cls not used
 527  * @param key the key
 528  * @param value ATS_Peer
 529  * @return #GNUNET_OK
 530  */
 531 static int
 532 reset_peers (void *cls,
 533              const struct GNUNET_PeerIdentity *key,
 534              void *value)
 535  {
 536    struct ATS_Peer *peer = value;
 537    peer->processed = GNUNET_NO;
 538    return GNUNET_OK;
 539  }
 540
 541 /**
 542  * Delete the MLP problem and free the constrain matrix
 543  *
 544  * @param mlp the MLP handle
 545  */
 546 static void
 547 mlp_delete_problem (struct GAS_MLP_Handle *mlp)
 548 {
 549   int c;
 550   if (mlp == NULL)
 551     return;
 552   if (mlp->p.prob != NULL)
 553   {
 554     glp_delete_prob(mlp->p.prob);
 555     mlp->p.prob = NULL;
 556   }
 557
 558   /* delete row index */
 559   if (mlp->p.ia != NULL)
 560   {
 561     GNUNET_free (mlp->p.ia);
 562     mlp->p.ia = NULL;
 563   }
 564
 565   /* delete column index */
 566   if (mlp->p.ja != NULL)
 567   {
 568     GNUNET_free (mlp->p.ja);
 569     mlp->p.ja = NULL;
 570   }
 571
 572   /* delete coefficients */
 573   if (mlp->p.ar != NULL)
 574   {
 575     GNUNET_free (mlp->p.ar);
 576     mlp->p.ar = NULL;
 577   }
 578   mlp->p.ci = 0;
 579   mlp->p.prob = NULL;
 580
 581   mlp->p.c_d = MLP_UNDEFINED;
 582   mlp->p.c_r = MLP_UNDEFINED;
 583   mlp->p.r_c2 = MLP_UNDEFINED;
 584   mlp->p.r_c4 = MLP_UNDEFINED;
 585   mlp->p.r_c6 = MLP_UNDEFINED;
 586   mlp->p.r_c9 = MLP_UNDEFINED;
 587   for (c = 0; c < mlp->pv.m_q ; c ++)
 588     mlp->p.r_q[c] = MLP_UNDEFINED;
 589   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++)
 590     mlp->p.r_quota[c] = MLP_UNDEFINED;
 591   mlp->p.ci = MLP_UNDEFINED;
 592
 593
 594   GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
 595                                          &reset_peers, NULL);
 596 }
 597
 598
 599 /**
 600  * Translate glpk status error codes to text
 601  * @param retcode return code
 602  * @return string with result
 603  */
 604 static const char *
 605 mlp_status_to_string (int retcode)
 606 {
 607   switch (retcode) {
 608     case GLP_UNDEF:
 609       return "solution is undefined";
 610     case GLP_FEAS:
 611       return "solution is feasible";
 612     case GLP_INFEAS:
 613       return "solution is infeasible";
 614     case GLP_NOFEAS:
 615       return "no feasible solution exists";
 616     case GLP_OPT:
 617       return "solution is optimal";
 618     case GLP_UNBND:
 619       return "solution is unbounded";
 620     default:
 621       GNUNET_break (0);
 622       return "unknown error";
 623   }
 624 }
 625
 626
 627 /**
 628  * Translate glpk solver error codes to text
 629  * @param retcode return code
 630  * @return string with result
 631  */
 632 static const char *
 633 mlp_solve_to_string (int retcode)
 634 {
 635   switch (retcode) {
 636     case 0:
 637       return "ok";
 638     case GLP_EBADB:
 639       return "invalid basis";
 640     case GLP_ESING:
 641       return "singular matrix";
 642     case GLP_ECOND:
 643       return "ill-conditioned matrix";
 644     case GLP_EBOUND:
 645       return "invalid bounds";
 646     case GLP_EFAIL:
 647       return "solver failed";
 648     case GLP_EOBJLL:
 649       return "objective lower limit reached";
 650     case GLP_EOBJUL:
 651       return "objective upper limit reached";
 652     case GLP_EITLIM:
 653       return "iteration limit exceeded";
 654     case GLP_ETMLIM:
 655       return "time limit exceeded";
 656     case GLP_ENOPFS:
 657       return "no primal feasible solution";
 658     case GLP_ENODFS:
 659       return "no dual feasible solution";
 660     case GLP_EROOT:
 661       return "root LP optimum not provided";
 662     case GLP_ESTOP:
 663       return "search terminated by application";
 664     case GLP_EMIPGAP:
 665       return "relative mip gap tolerance reached";
 666     case GLP_ENOFEAS:
 667       return "no dual feasible solution";
 668     case GLP_ENOCVG:
 669       return "no convergence";
 670     case GLP_EINSTAB:
 671       return "numerical instability";
 672     case GLP_EDATA:
 673       return "invalid data";
 674     case GLP_ERANGE:
 675       return "result out of range";
 676     default:
 677       GNUNET_break (0);
 678       return "unknown error";
 679   }
 680 }
 681
 682 /**
 683  * Extract an ATS performance info from an address
 684  *
 685  * @param address the address
 686  * @param type the type to extract in HBO
 687  * @return the value in HBO or GNUNET_ATS_VALUE_UNDEFINED in HBO if value does not exist
 688  */
 689 static uint32_t
 690 get_performance_info (struct ATS_Address *address, uint32_t type)
 691 {
 692   int c1;
 693   GNUNET_assert (NULL != address);
 694
 695   if ((NULL == address->atsi) || (0 == address->atsi_count))
 696     return GNUNET_ATS_VALUE_UNDEFINED;
 697
 698   for (c1 = 0; c1 < address->atsi_count; c1++)
 699   {
 700     if (ntohl (address->atsi[c1].type) == type)
 701       return ntohl (address->atsi[c1].value);
 702   }
 703   return GNUNET_ATS_VALUE_UNDEFINED;
 704 }
 705
 706
 707 struct CountContext
 708 {
 709   const struct GNUNET_CONTAINER_MultiPeerMap *map;
 710   int result;
 711 };
 712
 713 static int
 714 mlp_create_problem_count_addresses_it (void *cls,
 715                                        const struct GNUNET_PeerIdentity *key,
 716                                        void *value)
 717 {
 718   struct CountContext *cctx = cls;
 719
 720   /* Check if we have to add this peer due to a pending request */
 721   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
 722     cctx->result++;
 723   return GNUNET_OK;
 724 }
 725
 726
 727 static int
 728 mlp_create_problem_count_addresses (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
 729                                     const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
 730 {
 731   struct CountContext cctx;
 732
 733   cctx.map = requested_peers;
 734   cctx.result = 0;
 735   GNUNET_CONTAINER_multipeermap_iterate (addresses,
 736            &mlp_create_problem_count_addresses_it, &cctx);
 737   return cctx.result;
 738 }
 739
 740
 741 static int
 742 mlp_create_problem_count_peers_it (void *cls,
 743                                    const struct GNUNET_PeerIdentity *key,
 744                                    void *value)
 745 {
 746   struct CountContext *cctx = cls;
 747
 748   /* Check if we have to addresses for the requested peer */
 749   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
 750     cctx->result++;
 751   return GNUNET_OK;
 752 }
 753
 754
 755 static int
 756 mlp_create_problem_count_peers (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
 757     const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
 758 {
 759   struct CountContext cctx;
 760
 761   cctx.map = addresses;
 762   cctx.result = 0;
 763   GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
 764            &mlp_create_problem_count_peers_it, &cctx);
 765   return cctx.result;
 766 }
 767
 768
 769 /**
 770  * Updates an existing value in the matrix
 771  *
 772  * Extract the row, updates the value and updates the row in the problem
 773  *
 774  * @param p the mlp problem
 775  * @param row the row to create the value in
 776  * @param col the column to create the value in
 777  * @param val the value to set
 778  * @param line calling line for debbuging
 779  * @return GNUNET_YES value changed, GNUNET_NO value did not change, GNUNET_SYSERR
 780  * on error
 781  */
 782 static int
 783 mlp_create_problem_update_value (struct MLP_Problem *p,
 784                               int row, int col, double val,
 785                               int line)
 786 {
 787   int c_cols;
 788   int c_elems;
 789   int c1;
 790   int res;
 791   int found;
 792   double *val_array;
 793   int *ind_array;
 794
 795   GNUNET_assert (NULL != p);
 796   GNUNET_assert (NULL != p->prob);
 797
 798   /* Get number of columns and prepare data structure */
 799   c_cols = glp_get_num_cols(p->prob);
 800   if (0 >= c_cols)
 801     return GNUNET_SYSERR;
 802
 803   val_array = GNUNET_malloc ((c_cols +1)* sizeof (double));
 804   GNUNET_assert (NULL != val_array);
 805   ind_array = GNUNET_malloc ((c_cols+1) * sizeof (int));
 806   GNUNET_assert (NULL != ind_array);
 807   /* Extract the row */
 808
 809   /* Update the value */
 810   c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
 811   found = GNUNET_NO;
 812   for (c1 = 1; c1 < (c_elems+1); c1++)
 813   {
 814     if (ind_array[c1] == col)
 815     {
 816       found = GNUNET_YES;
 817       break;
 818     }
 819   }
 820   if (GNUNET_NO == found)
 821   {
 822     ind_array[c_elems+1] = col;
 823     val_array[c_elems+1] = val;
 824     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
 825         glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
 826         val);
 827     glp_set_mat_row (p->prob, row, c_elems+1, ind_array, val_array);
 828     GNUNET_free (ind_array);
 829     GNUNET_free (val_array);
 830     return GNUNET_YES;
 831   }
 832   else
 833   {
 834     /* Update value */
 835     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
 836         glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
 837         val_array[c1], val);
 838     if (val != val_array[c1])
 839       res = GNUNET_YES;
 840     else
 841       res = GNUNET_NO;
 842     val_array[c1] = val;
 843     /* Update the row in the matrix */
 844     glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
 845   }
 846
 847   GNUNET_free (ind_array);
 848   GNUNET_free (val_array);
 849   return res;
 850 }
 851
 852 /**
 853  * Creates a new value in the matrix
 854  *
 855  * Sets the row and column index in the problem array and increments the
 856  * position field
 857  *
 858  * @param p the mlp problem
 859  * @param row the row to create the value in
 860  * @param col the column to create the value in
 861  * @param val the value to set
 862  * @param line calling line for debbuging
 863  */
 864 static void
 865 mlp_create_problem_set_value (struct MLP_Problem *p,
 866                               int row, int col, double val,
 867                               int line)
 868 {
 869   if ((p->ci) >= p->num_elements)
 870   {
 871     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
 872         line, p->ci + 1, p->num_elements);
 873     GNUNET_break (0);
 874     return;
 875   }
 876   if ((0 == row) || (0 == col))
 877   {
 878     GNUNET_break (0);
 879     LOG (GNUNET_ERROR_TYPE_ERROR, "[P]: Invalid call from line %u: row = %u, col = %u\n",
 880         line, row, col);
 881   }
 882   p->ia[p->ci] = row ;
 883   p->ja[p->ci] = col;
 884   p->ar[p->ci] = val;
 885 #if  DEBUG_MLP_PROBLEM_CREATION
 886   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u ==  %.2f\n",
 887       line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
 888 #endif
 889   p->ci++;
 890 }
 891
 892 static int
 893 mlp_create_problem_create_column (struct MLP_Problem *p, char *name,
 894     unsigned int type, unsigned int bound, double lb, double ub,
 895     double coef)
 896 {
 897   int col = glp_add_cols (p->prob, 1);
 898   glp_set_col_name (p->prob, col, name);
 899   glp_set_col_bnds (p->prob, col, bound, lb, ub);
 900   glp_set_col_kind (p->prob, col, type);
 901   glp_set_obj_coef (p->prob, col, coef);
 902 #if  DEBUG_MLP_PROBLEM_CREATION
 903   LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
 904       col, name, coef);
 905 #endif
 906   return col;
 907 }
 908
 909 static int
 910 mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name,
 911     unsigned int bound, double lb, double ub)
 912 {
 913   char * op;
 914   int row = glp_add_rows (p->prob, 1);
 915   /* set row name */
 916   glp_set_row_name (p->prob, row, name);
 917   /* set row bounds: <= 0 */
 918   glp_set_row_bnds (p->prob, row, bound, lb, ub);
 919   switch (bound)
 920   {
 921     case GLP_UP:
 922             GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
 923             break;
 924     case GLP_DB:
 925             GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
 926             break;
 927     case GLP_FX:
 928             GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
 929             break;
 930     case GLP_LO:
 931             GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
 932             break;
 933     default:
 934             GNUNET_asprintf(&op, "ERROR");
 935             break;
 936   }
 937 #if  DEBUG_MLP_PROBLEM_CREATION
 938     LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
 939         row, name, op);
 940 #endif
 941   GNUNET_free (op);
 942   return row;
 943 }
 944
 945 /**
 946  * Create the
 947  * - address columns b and n
 948  * - address dependent constraint rows c1, c3
 949  * - peer dependent rows c2 and c9
 950  * - Set address dependent entries in problem matrix as well
 951  */
 952 static int
 953 mlp_create_problem_add_address_information (void *cls,
 954                                             const struct GNUNET_PeerIdentity *key,
 955                                             void *value)
 956 {
 957   struct GAS_MLP_Handle *mlp = cls;
 958   struct MLP_Problem *p = &mlp->p;
 959   struct ATS_Address *address = value;
 960   struct ATS_Peer *peer;
 961   struct MLP_information *mlpi;
 962   char *name;
 963   double prop;
 964   double cur_bigm;
 965   uint32_t addr_net;
 966   uint32_t addr_net_index;
 967   unsigned long long max_quota;
 968   int c;
 969
 970   /* Check if we have to add this peer due to a pending request */
 971   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(mlp->requested_peers, key))
 972     return GNUNET_OK;
 973
 974   mlpi = address->solver_information;
 975   if (NULL == mlpi)
 976   {
 977       fprintf (stderr, "%s %p\n",GNUNET_i2s (&address->peer), address);
 978       GNUNET_break (0);
 979       return GNUNET_OK;
 980   }
 981
 982   addr_net = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE);
 983   for (addr_net_index = 0; addr_net_index < GNUNET_ATS_NetworkTypeCount; addr_net_index++)
 984   {
 985     if (mlp->pv.quota_index[addr_net_index] == addr_net)
 986       break;
 987   }
 988
 989   if (addr_net_index >= GNUNET_ATS_NetworkTypeCount)
 990   {
 991     GNUNET_break (0);
 992     return GNUNET_OK;
 993   }
 994
 995   max_quota = 0;
 996   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
 997   {
 998     if (mlp->pv.quota_out[c] > max_quota)
 999       max_quota = mlp->pv.quota_out[c];
1000     if (mlp->pv.quota_in[c] > max_quota)
1001       max_quota = mlp->pv.quota_in[c];
1002   }
1003   if (max_quota > mlp->pv.BIG_M)
1004     cur_bigm = (double) mlp->pv.BIG_M;
1005   else
1006     cur_bigm = max_quota;
1007
1008
1009   /* Get peer */
1010   peer = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, key);
1011   GNUNET_assert (NULL != peer);
1012   if (peer->processed == GNUNET_NO)
1013   {
1014       /* Add peer dependent constraints */
1015       /* Add c2) One address active per peer */
1016       GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
1017       peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0);
1018       GNUNET_free (name);
1019       if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1020       {
1021         if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1022         {
1023           /* Add c9) Relativity */
1024           GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
1025           peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1026           GNUNET_free (name);
1027           /* c9) set coefficient */
1028           mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f , __LINE__);
1029         }
1030       }
1031       peer->processed = GNUNET_YES;
1032   }
1033
1034   /* Reset addresses' solver information */
1035   mlpi->c_b = 0;
1036   mlpi->c_n = 0;
1037   mlpi->n = 0;
1038   mlpi->r_c1 = 0;
1039   mlpi->r_c3 = 0;
1040
1041   /* Add bandwidth column */
1042   GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1043   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1044   {
1045     mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
1046   }
1047   else
1048   {
1049     /* Maximize for bandwidth assignment in feasibility testing */
1050     mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
1051   }
1052   GNUNET_free (name);
1053
1054   /* Add address active column */
1055   GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1056   mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
1057   GNUNET_free (name);
1058
1059   /* Add address dependent constraints */
1060   /* Add c1) bandwidth capping: b_t  + (-M) * n_t <= 0 */
1061   GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1062   mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
1063   GNUNET_free (name);
1064   /*  c1) set b = 1 coefficient */
1065   mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1066   /*  c1) set n = - min (M, quota) coefficient */
1067   cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
1068   if (cur_bigm > mlp->pv.BIG_M)
1069     cur_bigm = (double) mlp->pv.BIG_M;
1070   mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1071
1072   /* Add constraint c 3) minimum bandwidth
1073    * b_t + (-n_t * b_min) >= 0
1074    * */
1075   GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1076   mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1077   GNUNET_free (name);
1078
1079   /*  c3) set b = 1 coefficient */
1080   mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1081   /*  c3) set n = -b_min coefficient */
1082   mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__);
1083
1084
1085   /* Set coefficient entries in invariant rows */
1086
1087   /* Feasbility */
1088
1089   /* c 4) minimum connections */
1090   mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
1091   /* c 2) 1 address peer peer */
1092   mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1093   /* c 10) obey network specific quotas
1094    * (1)*b_1 + ... + (1)*b_m <= quota_n
1095    */
1096   mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1, __LINE__);
1097
1098   /* Optimality */
1099   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1100   {
1101     /* c 6) maximize diversity */
1102     mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
1103     /* c 9) relativity */
1104     if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1105       mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1106     /* c 8) utility */
1107     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1108       mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
1109     /* c 7) Optimize quality */
1110     /* For all quality metrics, set quality of this address */
1111     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1112     {
1113       for (c = 0; c < mlp->pv.m_q; c++)
1114       {
1115         prop = address->atsin[c].norm;
1116         if ((prop < 1.0) && (prop > 2.0))
1117         {
1118           GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1119                       "PROP == %.3f \t ",
1120                       prop);
1121           GNUNET_break (0);
1122         }
1123         mlp_create_problem_set_value (p,
1124                                       p->r_q[c],
1125                                       mlpi->c_b,
1126                                       prop,
1127                                       __LINE__);
1128       }
1129     }
1130   }
1131
1132   return GNUNET_OK;
1133 }
1134
1135
1136 /**
1137  * Create the invariant columns c4, c6, c10, c8, c7
1138  */
1139 static void
1140 mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1141 {
1142   int c;
1143
1144   /* Feasibility */
1145
1146   /* Row for c4) minimum connection */
1147   /* Number of minimum connections is min(|Peers|, n_min) */
1148   p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0);
1149
1150   /* Rows for c 10) Enforce network quotas */
1151   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1152   {
1153     char * text;
1154     GNUNET_asprintf(&text, "c10_quota_ats_%s",
1155         GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
1156     p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
1157     GNUNET_free (text);
1158   }
1159
1160   /* Optimality */
1161   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1162   {
1163     char *name;
1164     /* Add row for c6) Maximize for diversity */
1165     if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1166     {
1167       p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0);
1168       /* Set c6 ) Setting -D */
1169       mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
1170     }
1171
1172     /* Adding rows for c 8) Maximize utility */
1173     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1174     {
1175       p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0);
1176       /* -u */
1177       mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
1178     }
1179
1180     /* For all quality metrics:
1181      * c 7) Maximize quality, austerity */
1182     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1183     {
1184       for (c = 0; c < mlp->pv.m_q; c++)
1185       {
1186         GNUNET_asprintf (&name, "c7_q%i_%s", c,
1187                          GNUNET_ATS_print_property_type (mlp->pv.q[c]));
1188         p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0);
1189         GNUNET_free (name);
1190         mlp_create_problem_set_value (p, p->r_q[c], p->c_q[c], -1, __LINE__);
1191       }
1192     }
1193   }
1194 }
1195
1196
1197 /**
1198  * Create the invariant columns d, u, r, q0 ... qm
1199  */
1200 static void
1201 mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1202 {
1203   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1204   {
1205     char *name;
1206     int c;
1207
1208     /* Diversity d column  */
1209     if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
1210       p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
1211
1212     /* Utilization u column  */
1213     if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
1214       p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
1215
1216     /* Relativity r column  */
1217     if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
1218       p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
1219
1220     /* Quality metric columns */
1221     if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
1222     {
1223       for (c = 0; c < mlp->pv.m_q; c++)
1224       {
1225         GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]);
1226         p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
1227         GNUNET_free (name);
1228       }
1229     }
1230   }
1231 }
1232
1233
1234 /**
1235  * Create the MLP problem
1236  *
1237  * @param mlp the MLP handle
1238  * @return #GNUNET_OK or #GNUNET_SYSERR
1239  */
1240 static int
1241 mlp_create_problem (struct GAS_MLP_Handle *mlp)
1242 {
1243   struct MLP_Problem *p = &mlp->p;
1244   int res = GNUNET_OK;
1245
1246   GNUNET_assert (p->prob == NULL);
1247   GNUNET_assert (p->ia == NULL);
1248   GNUNET_assert (p->ja == NULL);
1249   GNUNET_assert (p->ar == NULL);
1250   /* Reset MLP problem struct */
1251
1252   /* create the glpk problem */
1253   p->prob = glp_create_prob ();
1254   GNUNET_assert (NULL != p->prob);
1255   p->num_peers = mlp_create_problem_count_peers (mlp->requested_peers, mlp->env->addresses);
1256   p->num_addresses = mlp_create_problem_count_addresses (mlp->requested_peers,
1257                                                          mlp->env->addresses);
1258
1259   /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1260   p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +
1261       mlp->pv.m_q + p->num_peers + 2 + 1);
1262   LOG (GNUNET_ERROR_TYPE_DEBUG,
1263        "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1264        p->num_peers,
1265        p->num_addresses,
1266        mlp->pv.m_q,
1267        p->num_elements);
1268
1269   /* Set a problem name */
1270   glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
1271   /* Set optimization direction to maximize */
1272   glp_set_obj_dir (p->prob, GLP_MAX);
1273
1274   /* Create problem matrix */
1275   /* last +1 caused by glpk index starting with one: [1..elements]*/
1276   p->ci = 1;
1277   /* row index */
1278   p->ia = GNUNET_malloc (p->num_elements * sizeof (int));
1279   /* column index */
1280   p->ja = GNUNET_malloc (p->num_elements * sizeof (int));
1281   /* coefficient */
1282   p->ar = GNUNET_malloc (p->num_elements * sizeof (double));
1283
1284   if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1285   {
1286       LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
1287       return GNUNET_SYSERR;
1288   }
1289
1290   /* Adding invariant columns */
1291   mlp_create_problem_add_invariant_columns (mlp, p);
1292
1293   /* Adding address independent constraint rows */
1294   mlp_create_problem_add_invariant_rows (mlp, p);
1295
1296   /* Adding address dependent columns constraint rows */
1297   GNUNET_CONTAINER_multipeermap_iterate (mlp->env->addresses,
1298                                          &mlp_create_problem_add_address_information,
1299                                          mlp);
1300
1301   /* Load the matrix */
1302   LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1303   glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar);
1304   if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
1305   {
1306     glp_scale_prob (p->prob, GLP_SF_AUTO);
1307   }
1308
1309   return res;
1310 }
1311
1312
1313 /**
1314  * Solves the LP problem
1315  *
1316  * @param mlp the MLP Handle
1317  * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1318  */
1319 static int
1320 mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
1321 {
1322   int res = 0;
1323   int res_status = 0;
1324   res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
1325   if (0 == res)
1326     LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1327         mlp_solve_to_string (res));
1328   else
1329     LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1330         mlp_solve_to_string (res));
1331
1332   /* Analyze problem status  */
1333   res_status = glp_get_status (mlp->p.prob);
1334   switch (res_status) {
1335     case GLP_OPT: /* solution is optimal */
1336       LOG (GNUNET_ERROR_TYPE_INFO,
1337           "Solving LP problem: %s, %s\n",
1338           mlp_solve_to_string(res),
1339           mlp_status_to_string(res_status));
1340       return GNUNET_OK;
1341     default:
1342       LOG (GNUNET_ERROR_TYPE_ERROR,
1343           "Solving LP problem failed: %s %s\n",
1344           mlp_solve_to_string(res),
1345           mlp_status_to_string(res_status));
1346       return GNUNET_SYSERR;
1347   }
1348 }
1349
1350
1351 /**
1352  * Propagates the results when MLP problem was solved
1353  *
1354  * @param cls the MLP handle
1355  * @param key the peer identity
1356  * @param value the address
1357  * @return #GNUNET_OK to continue
1358  */
1359 static int
1360 mlp_propagate_results (void *cls,
1361                        const struct GNUNET_PeerIdentity *key,
1362                        void *value)
1363 {
1364   struct GAS_MLP_Handle *mlp = cls;
1365   struct ATS_Address *address;
1366   struct MLP_information *mlpi;
1367   double mlp_bw_in = MLP_NaN;
1368   double mlp_bw_out = MLP_NaN;
1369   double mlp_use = MLP_NaN;
1370
1371   /* Check if we have to add this peer due to a pending request */
1372   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers,
1373                                                            key))
1374   {
1375     return GNUNET_OK;
1376   }
1377   address = value;
1378   GNUNET_assert (address->solver_information != NULL);
1379   mlpi = address->solver_information;
1380
1381   mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
1382   if (mlp_bw_in > (double) UINT32_MAX)
1383   {
1384       LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1385       mlp_bw_in = (double) UINT32_MAX;
1386   }
1387   mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
1388   if (mlp_bw_out > (double) UINT32_MAX)
1389   {
1390       LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1391       mlp_bw_out = (double) UINT32_MAX;
1392   }
1393   mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
1394
1395   /*
1396    * Debug: solution
1397    * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1398    *    GNUNET_i2s(&address->peer), address->plugin,
1399    *    address->addr_len, address->session_id);
1400    */
1401
1402   if (GLP_YES == mlp_use)
1403   {
1404     /* This address was selected by the solver to be used */
1405     mlpi->n = GNUNET_YES;
1406     if (GNUNET_NO == address->active)
1407     {
1408             /* Address was not used before, enabling address */
1409       LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1410           (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1411       address->active = GNUNET_YES;
1412       address->assigned_bw_in = mlp_bw_in;
1413       mlpi->b_in = mlp_bw_in;
1414       address->assigned_bw_out = mlp_bw_out;
1415       mlpi->b_out = mlp_bw_out;
1416       if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
1417         mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1418       return GNUNET_OK;
1419     }
1420     else if (GNUNET_YES == address->active)
1421     {
1422       /* Address was used before, check for bandwidth change */
1423       if ((mlp_bw_out != address->assigned_bw_out) ||
1424               (mlp_bw_in != address->assigned_bw_in))
1425       {
1426           LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1427               (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1428           address->assigned_bw_in = mlp_bw_in;
1429           mlpi->b_in = mlp_bw_in;
1430           address->assigned_bw_out = mlp_bw_out;
1431           mlpi->b_out = mlp_bw_out;
1432           if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
1433             mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1434           return GNUNET_OK;
1435       }
1436     }
1437     else
1438       GNUNET_break (0);
1439   }
1440   else if (GLP_NO == mlp_use)
1441   {
1442     /* This address was selected by the solver to be not used */
1443     mlpi->n = GNUNET_NO;
1444     if (GNUNET_NO == address->active)
1445     {
1446       /* Address was not used before, nothing to do */
1447       LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1448           (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1449       return GNUNET_OK;
1450     }
1451     else if (GNUNET_YES == address->active)
1452     {
1453     /* Address was used before, disabling address */
1454     LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1455         (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1456       address->active = GNUNET_NO;
1457       /* Set bandwidth to 0 */
1458       address->assigned_bw_in = 0;
1459       mlpi->b_in = 0;
1460       address->assigned_bw_out = 0;
1461       mlpi->b_out = 0;
1462       return GNUNET_OK;
1463     }
1464     else
1465       GNUNET_break (0);
1466   }
1467   else
1468     GNUNET_break (0);
1469
1470   return GNUNET_OK;
1471 }
1472
1473
1474 static void
1475 notify (struct GAS_MLP_Handle *mlp,
1476         enum GAS_Solver_Operation op,
1477         enum GAS_Solver_Status stat,
1478         enum GAS_Solver_Additional_Information add)
1479 {
1480   mlp->env->info_cb (mlp->env->cls,
1481                      op,
1482                      stat,
1483                      add);
1484 }
1485
1486
1487 static void
1488 mlp_branch_and_cut_cb (glp_tree *tree, void *info)
1489 {
1490   struct GAS_MLP_Handle *mlp = info;
1491   double mlp_obj = 0;
1492
1493   switch (glp_ios_reason (tree))
1494   {
1495     case GLP_ISELECT:
1496         /* Do nothing here */
1497       break;
1498     case GLP_IPREPRO:
1499         /* Do nothing here */
1500       break;
1501     case GLP_IROWGEN:
1502         /* Do nothing here */
1503       break;
1504     case GLP_IHEUR:
1505         /* Do nothing here */
1506       break;
1507     case GLP_ICUTGEN:
1508         /* Do nothing here */
1509       break;
1510     case GLP_IBRANCH:
1511         /* Do nothing here */
1512       break;
1513     case GLP_IBINGO:
1514         /* A better solution was found  */
1515       mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
1516       mlp_obj = glp_mip_obj_val (mlp->p.prob);
1517       mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) / (abs(mlp_obj) + DBL_EPSILON);
1518
1519       LOG (GNUNET_ERROR_TYPE_INFO,
1520           "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1521           mlp->ps.mlp_gap, mlp->pv.mip_gap,
1522           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1523
1524       if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1525       {
1526         LOG (GNUNET_ERROR_TYPE_INFO,
1527           "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1528           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1529         glp_ios_terminate (tree);
1530       }
1531
1532       if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1533       {
1534         LOG (GNUNET_ERROR_TYPE_INFO,
1535           "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1536           mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1537         glp_ios_terminate (tree);
1538       }
1539
1540       break;
1541     default:
1542       break;
1543   }
1544   //GNUNET_break (0);
1545 }
1546
1547
1548 /**
1549  * Solves the MLP problem
1550  *
1551  * @param solver the MLP Handle
1552  * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
1553  */
1554 static int
1555 GAS_mlp_solve_problem (void *solver)
1556 {
1557   struct GAS_MLP_Handle *mlp = solver;
1558   char *filename;
1559   int res_lp = 0;
1560   int mip_res = 0;
1561   int mip_status = 0;
1562
1563   struct GNUNET_TIME_Absolute start_total;
1564   struct GNUNET_TIME_Absolute start_cur_op;
1565   struct GNUNET_TIME_Relative dur_total;
1566   struct GNUNET_TIME_Relative dur_setup;
1567   struct GNUNET_TIME_Relative dur_lp;
1568   struct GNUNET_TIME_Relative dur_mlp;
1569
1570   GNUNET_assert(NULL != solver);
1571
1572   if (GNUNET_YES == mlp->stat_bulk_lock)
1573     {
1574       mlp->stat_bulk_requests++;
1575       return GNUNET_NO;
1576     }
1577   notify(mlp, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS,
1578       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1579   start_total = GNUNET_TIME_absolute_get();
1580
1581   if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->requested_peers))
1582     {
1583       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1584       return GNUNET_OK; /* No pending requests */
1585     }
1586   if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->env->addresses))
1587     {
1588       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1589       return GNUNET_OK; /* No addresses available */
1590     }
1591
1592   if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1593       && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1594     {
1595       LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1596       notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
1597       return GNUNET_OK;
1598     }
1599   if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1600   {
1601     LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1602     notify(mlp, GAS_OP_SOLVE_SETUP_START, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1603     mlp_delete_problem(mlp);
1604     if (GNUNET_SYSERR == mlp_create_problem(mlp))
1605       {
1606         notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_FAIL, GAS_INFO_FULL);
1607         return GNUNET_SYSERR;
1608       }
1609     notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_SUCCESS, GAS_INFO_FULL);
1610     if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1611     {
1612     mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1613     mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1614     }
1615     else
1616     {
1617       mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1618       mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1619       dur_lp = GNUNET_TIME_UNIT_ZERO;
1620     }
1621   }
1622   else
1623   {
1624     LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1625   }
1626
1627   /* Reset solution info */
1628   mlp->ps.lp_objective_value = 0.0;
1629   mlp->ps.mlp_gap = 1.0;
1630   mlp->ps.mlp_objective_value = 0.0;
1631   mlp->ps.lp_mlp_gap = 0.0;
1632
1633   dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
1634
1635   /* Run LP solver */
1636   if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1637   {
1638     notify(mlp, GAS_OP_SOLVE_MLP_LP_START, GAS_STAT_SUCCESS,
1639         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1640     LOG(GNUNET_ERROR_TYPE_DEBUG,
1641         "Running LP solver %s\n",
1642         (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver");
1643     start_cur_op = GNUNET_TIME_absolute_get();
1644
1645     /* Solve LP */
1646     /* Only for debugging:
1647      * Always use LP presolver:
1648      * mlp->control_param_lp.presolve = GLP_YES; */
1649     res_lp = mlp_solve_lp_problem(mlp);
1650     if (GNUNET_OK == res_lp)
1651     {
1652         mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
1653         LOG (GNUNET_ERROR_TYPE_DEBUG,
1654              "LP solution was: %.3f\n",
1655              mlp->ps.lp_objective_value);
1656     }
1657
1658     dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1659     notify(mlp, GAS_OP_SOLVE_MLP_LP_STOP,
1660         (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1661         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1662   }
1663
1664   if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1665     res_lp = GNUNET_OK;
1666
1667   /* Run MLP solver */
1668   if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1669   {
1670     LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1671     notify(mlp, GAS_OP_SOLVE_MLP_MLP_START, GAS_STAT_SUCCESS,
1672         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1673     start_cur_op = GNUNET_TIME_absolute_get();
1674
1675     /* Solve MIP */
1676
1677     /* Only for debugging, always use LP presolver */
1678     if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
1679       mlp->control_param_mlp.presolve = GNUNET_YES;
1680
1681     mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
1682     switch (mip_res)
1683     {
1684         case 0:
1685           /* Successful */
1686           LOG (GNUNET_ERROR_TYPE_INFO,
1687                "Solving MLP problem: %s\n",
1688                mlp_solve_to_string (mip_res));
1689           break;
1690         case GLP_ETMLIM: /* Time limit reached */
1691         case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1692         case GLP_ESTOP: /* Solver was instructed to stop*/
1693           /* Semi-successful */
1694           LOG (GNUNET_ERROR_TYPE_INFO,
1695                "Solving MLP problem solution was interupted: %s\n",
1696                mlp_solve_to_string (mip_res));
1697           break;
1698         case GLP_EBOUND:
1699         case GLP_EROOT:
1700         case GLP_ENOPFS:
1701         case GLP_ENODFS:
1702         case GLP_EFAIL:
1703         default:
1704          /* Fail */
1705           LOG (GNUNET_ERROR_TYPE_INFO,
1706               "Solving MLP problem failed: %s\n",
1707               mlp_solve_to_string (mip_res));
1708         break;
1709     }
1710
1711     /* Analyze problem status  */
1712     mip_status = glp_mip_status(mlp->p.prob);
1713     switch (mip_status)
1714     {
1715       case GLP_OPT: /* solution is optimal */
1716         LOG (GNUNET_ERROR_TYPE_WARNING,
1717             "Solution of MLP problem is optimal: %s, %s\n",
1718             mlp_solve_to_string (mip_res),
1719             mlp_status_to_string (mip_status));
1720         mip_res = GNUNET_OK;
1721         break;
1722       case GLP_FEAS: /* solution is feasible but not proven optimal */
1723
1724         if ( (mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1725              (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap) )
1726         {
1727           LOG (GNUNET_ERROR_TYPE_INFO,
1728                  "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1729                  mlp_solve_to_string (mip_res),
1730                  mlp_status_to_string (mip_status));
1731           mip_res = GNUNET_OK;
1732         }
1733         else
1734         {
1735           LOG (GNUNET_ERROR_TYPE_WARNING,
1736                "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1737                mlp_solve_to_string (mip_res),
1738                mlp_status_to_string (mip_status));
1739           mip_res = GNUNET_SYSERR;
1740         }
1741         break;
1742       case GLP_UNDEF: /* Solution undefined */
1743       case GLP_NOFEAS: /* No feasible solution */
1744       default:
1745         LOG (GNUNET_ERROR_TYPE_ERROR,
1746             "Solving MLP problem failed: %s %s\n",
1747             mlp_solve_to_string (mip_res),
1748             mlp_status_to_string (mip_status));
1749         mip_res = GNUNET_SYSERR;
1750         break;
1751     }
1752
1753     dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1754     dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1755
1756     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP,
1757         (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1758         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1759   }
1760   else
1761   {
1762     /* Do not execute mip solver since lp solution is invalid */
1763     dur_mlp = GNUNET_TIME_UNIT_ZERO;
1764     dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1765
1766     notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP, GAS_STAT_FAIL,
1767         (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1768     mip_res = GNUNET_SYSERR;
1769   }
1770
1771   /* Notify about end */
1772   notify(mlp, GAS_OP_SOLVE_STOP,
1773       ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1774       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1775
1776   LOG (GNUNET_ERROR_TYPE_DEBUG,
1777       "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1778       (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1779       (unsigned long long) dur_total.rel_value_us,
1780       (unsigned long long) dur_setup.rel_value_us,
1781       (unsigned long long) dur_lp.rel_value_us,
1782       (unsigned long long) dur_mlp.rel_value_us);
1783
1784   /* Save stats */
1785   mlp->ps.lp_res = res_lp;
1786   mlp->ps.mip_res = mip_res;
1787   mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1788   mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1789   mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
1790   mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob);
1791   mlp->ps.p_elements = mlp->p.num_elements;
1792
1793   /* Propagate result*/
1794   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
1795       (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1796       GAS_INFO_NONE);
1797   if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1798     {
1799       GNUNET_CONTAINER_multipeermap_iterate(mlp->env->addresses,
1800           &mlp_propagate_results, mlp);
1801     }
1802   notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
1803       (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1804       GAS_INFO_NONE);
1805
1806   struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get();
1807   if ( (GNUNET_YES == mlp->opt_dump_problem_all) ||
1808       (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1809     {
1810       /* Write problem to disk */
1811       switch (mlp->opt_log_format) {
1812         case MLP_CPLEX:
1813           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.cplex", mlp->p.num_peers,
1814               mlp->p.num_addresses, time.abs_value_us);
1815           glp_write_lp (mlp->p.prob, NULL, filename);
1816           break;
1817         case MLP_GLPK:
1818           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.glpk", mlp->p.num_peers,
1819               mlp->p.num_addresses, time.abs_value_us);
1820           glp_write_prob (mlp->p.prob, 0, filename);
1821           break;
1822         case MLP_MPS:
1823           GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1824               mlp->p.num_addresses, time.abs_value_us);
1825           glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1826           break;
1827         default:
1828           break;
1829       }
1830       LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1831       GNUNET_free(filename);
1832     }
1833   if ( (mlp->opt_dump_solution_all) ||
1834       (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1835   {
1836     /* Write solution to disk */
1837     GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1838         mlp->p.num_addresses, time.abs_value_us);
1839     glp_print_mip(mlp->p.prob, filename);
1840     LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1841     GNUNET_free(filename);
1842   }
1843
1844   /* Reset change and update marker */
1845   mlp->control_param_lp.presolve = GLP_NO;
1846   mlp->stat_mlp_prob_updated = GNUNET_NO;
1847   mlp->stat_mlp_prob_changed = GNUNET_NO;
1848
1849   if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1850     return GNUNET_OK;
1851   else
1852     return GNUNET_SYSERR;
1853 }
1854
1855 /**
1856  * Add a single address to the solve
1857  *
1858  * @param solver the solver Handle
1859  * @param address the address to add
1860  * @param network network type of this address
1861  */
1862 static void
1863 GAS_mlp_address_add (void *solver,
1864                     struct ATS_Address *address,
1865                     uint32_t network)
1866 {
1867   struct GAS_MLP_Handle *mlp = solver;
1868
1869   GNUNET_assert (NULL != solver);
1870   GNUNET_assert (NULL != address);
1871
1872   if (GNUNET_ATS_NetworkTypeCount <= network)
1873   {
1874    GNUNET_break (0);
1875    return;
1876   }
1877
1878   if (NULL == address->solver_information)
1879   {
1880       address->solver_information = GNUNET_new (struct MLP_information);
1881   }
1882   else
1883       LOG (GNUNET_ERROR_TYPE_ERROR,
1884            _("Adding address for peer `%s' multiple times\n"),
1885            GNUNET_i2s(&address->peer));
1886
1887   /* Is this peer included in the problem? */
1888   if (NULL ==
1889       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
1890                                          &address->peer))
1891   {
1892     /* FIXME: should this be an error? */
1893     LOG (GNUNET_ERROR_TYPE_DEBUG,
1894          "Adding address for peer `%s' without address request\n",
1895          GNUNET_i2s(&address->peer));
1896     return;
1897   }
1898
1899   LOG (GNUNET_ERROR_TYPE_DEBUG,
1900        "Adding address for peer `%s' with address request \n",
1901        GNUNET_i2s(&address->peer));
1902   /* Problem size changed: new address for peer with pending request */
1903   mlp->stat_mlp_prob_changed = GNUNET_YES;
1904   if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1905     GAS_mlp_solve_problem (solver);
1906 }
1907
1908
1909 /**
1910  * Transport properties for this address have changed
1911  *
1912  * @param solver solver handle
1913  * @param address the address
1914  * @param type the ATSI type in HBO
1915  * @param abs_value the absolute value of the property
1916  * @param rel_value the normalized value
1917  */
1918 static void
1919 GAS_mlp_address_property_changed (void *solver,
1920                                   struct ATS_Address *address,
1921                                   enum GNUNET_ATS_Property type,
1922                                   uint32_t abs_value,
1923                                   double rel_value)
1924 {
1925   struct MLP_information *mlpi = address->solver_information;
1926   struct GAS_MLP_Handle *mlp = solver;
1927   int c1;
1928   int type_index;
1929
1930   GNUNET_assert (NULL != solver);
1931   GNUNET_assert (NULL != address);
1932
1933   if (NULL == mlpi)
1934   {
1935       LOG (GNUNET_ERROR_TYPE_INFO,
1936           _("Updating address property `%s' for peer `%s' %p not added before\n"),
1937           GNUNET_ATS_print_property_type (type),
1938           GNUNET_i2s(&address->peer),
1939           address);
1940       GNUNET_break (0);
1941       return;
1942   }
1943
1944   if (NULL ==
1945       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
1946                                          &address->peer))
1947   {
1948     /* Peer is not requested, so no need to update problem */
1949     return;
1950   }
1951   LOG (GNUNET_ERROR_TYPE_INFO, "Updating property `%s' address for peer `%s' to abs %llu rel %.3f\n",
1952       GNUNET_ATS_print_property_type (type),
1953       GNUNET_i2s(&address->peer),
1954       abs_value,
1955       rel_value);
1956
1957   if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
1958     return;
1959
1960   /* Find row index */
1961   type_index = -1;
1962   for (c1 = 0; c1 < mlp->pv.m_q; c1++)
1963   {
1964     if (type == mlp->pv.q[c1])
1965     {
1966       type_index = c1;
1967       break;
1968     }
1969   }
1970   if (-1 == type_index)
1971   {
1972     GNUNET_break (0);
1973     return; /* quality index not found */
1974   }
1975
1976   /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
1977   if (GNUNET_YES == mlp_create_problem_update_value (&mlp->p,
1978       mlp->p.r_q[type_index], mlpi->c_b, rel_value, __LINE__))
1979   {
1980     mlp->stat_mlp_prob_updated = GNUNET_YES;
1981     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1982       GAS_mlp_solve_problem (solver);
1983   }
1984
1985 }
1986
1987
1988 /**
1989  * Find the active address in the set of addresses of a peer
1990  * @param cls destination
1991  * @param key peer id
1992  * @param value address
1993  * @return #GNUNET_OK
1994  */
1995 static int
1996 mlp_get_preferred_address_it (void *cls,
1997                               const struct GNUNET_PeerIdentity *key,
1998                               void *value)
1999 {
2000   static int counter = 0;
2001   struct ATS_Address **aa = cls;
2002   struct ATS_Address *addr = value;
2003   struct MLP_information *mlpi = addr->solver_information;
2004
2005   if (mlpi == NULL)
2006     return GNUNET_YES;
2007
2008   /*
2009    * Debug output
2010    * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2011    *           "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
2012    *           counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
2013    *           (GNUNET_YES == addr->active) ? "active" : "inactive",
2014    *           (GNUNET_YES == mlpi->n) ? "active" : "inactive");
2015    */
2016
2017   if (GNUNET_YES == mlpi->n)
2018   {
2019
2020     (*aa) = addr;
2021     (*aa)->assigned_bw_in = mlpi->b_in;
2022     (*aa)->assigned_bw_out = mlpi->b_out;
2023     return GNUNET_NO;
2024   }
2025   counter++;
2026   return GNUNET_YES;
2027 }
2028
2029
2030 static double
2031 get_peer_pref_value (struct GAS_MLP_Handle *mlp,
2032                      const struct GNUNET_PeerIdentity *peer)
2033 {
2034   double res;
2035   const double *preferences = NULL;
2036   int c;
2037
2038   preferences = mlp->env->get_preferences (mlp->env->cls, peer);
2039   res = 0.0;
2040   for (c = 0; c < GNUNET_ATS_PreferenceCount; c++)
2041   {
2042     if (c != GNUNET_ATS_PREFERENCE_END)
2043     {
2044       /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2045        *        c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2046       res += preferences[c];
2047     }
2048   }
2049
2050   res /= (GNUNET_ATS_PreferenceCount -1);
2051   res += 1.0;
2052
2053   LOG (GNUNET_ERROR_TYPE_DEBUG,
2054        "Peer preference for peer  `%s' == %.2f\n",
2055        GNUNET_i2s(peer), res);
2056
2057   return res;
2058 }
2059
2060
2061 /**
2062  * Get the preferred address for a specific peer
2063  *
2064  * @param solver the MLP Handle
2065  * @param peer the peer
2066  * @return suggested address
2067  */
2068 static const struct ATS_Address *
2069 GAS_mlp_get_preferred_address (void *solver,
2070                                const struct GNUNET_PeerIdentity *peer)
2071 {
2072   struct GAS_MLP_Handle *mlp = solver;
2073   struct ATS_Peer *p;
2074   struct ATS_Address *res;
2075
2076   GNUNET_assert (NULL != solver);
2077   GNUNET_assert (NULL != peer);
2078
2079   LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n",
2080       GNUNET_i2s (peer));
2081
2082   /* Is this peer included in the problem? */
2083   if (NULL ==
2084       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2085                                          peer))
2086     {
2087       LOG (GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n",
2088           GNUNET_i2s (peer));
2089
2090       p = GNUNET_new (struct ATS_Peer);
2091       p->id = (*peer);
2092       p->f = get_peer_pref_value (mlp, peer);
2093       GNUNET_CONTAINER_multipeermap_put (mlp->requested_peers,
2094                                          peer, p,
2095                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
2096
2097       /* Added new peer, we have to rebuild problem before solving */
2098       mlp->stat_mlp_prob_changed = GNUNET_YES;
2099
2100       if ((GNUNET_YES == mlp->opt_mlp_auto_solve)&&
2101           (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(mlp->env->addresses,
2102                                                                 peer)))
2103       {
2104         mlp->exclude_peer = peer;
2105         GAS_mlp_solve_problem (mlp);
2106         mlp->exclude_peer = NULL;
2107       }
2108   }
2109   /* Get prefered address */
2110   res = NULL;
2111   GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses, peer,
2112                                               &mlp_get_preferred_address_it, &res);
2113   return res;
2114 }
2115
2116
2117 /**
2118  * Deletes a single address in the MLP problem
2119  *
2120  * The MLP problem has to be recreated and the problem has to be resolved
2121  *
2122  * @param solver the MLP Handle
2123  * @param address the address to delete
2124  * @param session_only delete only session not whole address
2125  */
2126 static void
2127 GAS_mlp_address_delete (void *solver,
2128                         struct ATS_Address *address,
2129                         int session_only)
2130 {
2131   struct GAS_MLP_Handle *mlp = solver;
2132   struct MLP_information *mlpi;
2133   int was_active;
2134
2135   GNUNET_assert (NULL != solver);
2136   GNUNET_assert (NULL != address);
2137
2138   mlpi = address->solver_information;
2139   if ((GNUNET_NO == session_only) && (NULL != mlpi))
2140   {
2141     /* Remove full address */
2142     GNUNET_free (mlpi);
2143     address->solver_information = NULL;
2144   }
2145   was_active = address->active;
2146   address->active = GNUNET_NO;
2147   address->assigned_bw_in = 0;
2148   address->assigned_bw_out = 0;
2149
2150   /* Is this peer included in the problem? */
2151   if (NULL ==
2152       GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2153                                          &address->peer))
2154   {
2155     LOG (GNUNET_ERROR_TYPE_INFO,
2156          "Deleting %s for peer `%s' without address request \n",
2157          (session_only == GNUNET_YES) ? "session" : "address",
2158          GNUNET_i2s(&address->peer));
2159     return;
2160   }
2161   LOG (GNUNET_ERROR_TYPE_INFO, "Deleting %s for peer `%s' with address request \n",
2162       (session_only == GNUNET_YES) ? "session" : "address",
2163       GNUNET_i2s(&address->peer));
2164
2165   /* Problem size changed: new address for peer with pending request */
2166   mlp->stat_mlp_prob_changed = GNUNET_YES;
2167   if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2168   {
2169     GAS_mlp_solve_problem (solver);
2170   }
2171   if (GNUNET_YES == was_active)
2172   {
2173     if (NULL == GAS_mlp_get_preferred_address (solver, &address->peer))
2174     {
2175       /* No alternative address, disconnecting peer */
2176       mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
2177     }
2178   }
2179
2180   return;
2181 }
2182
2183
2184 /**
2185  * Start a bulk operation
2186  *
2187  * @param solver the solver
2188  */
2189 static void
2190 GAS_mlp_bulk_start (void *solver)
2191 {
2192   struct GAS_MLP_Handle *s = solver;
2193
2194   LOG (GNUNET_ERROR_TYPE_DEBUG,
2195        "Locking solver for bulk operation ...\n");
2196   GNUNET_assert (NULL != solver);
2197   s->stat_bulk_lock ++;
2198 }
2199
2200
2201 static void
2202 GAS_mlp_bulk_stop (void *solver)
2203 {
2204   struct GAS_MLP_Handle *s = solver;
2205
2206   LOG (GNUNET_ERROR_TYPE_DEBUG,
2207        "Unlocking solver from bulk operation ...\n");
2208   GNUNET_assert (NULL != solver);
2209
2210   if (s->stat_bulk_lock < 1)
2211   {
2212     GNUNET_break (0);
2213     return;
2214   }
2215   s->stat_bulk_lock --;
2216
2217   if (0 < s->stat_bulk_requests)
2218   {
2219     GAS_mlp_solve_problem (solver);
2220     s->stat_bulk_requests= 0;
2221   }
2222 }
2223
2224
2225
2226 /**
2227  * Stop notifying about address and bandwidth changes for this peer
2228  *
2229  * @param solver the MLP handle
2230  * @param peer the peer
2231  */
2232 static void
2233 GAS_mlp_stop_get_preferred_address (void *solver,
2234                                      const struct GNUNET_PeerIdentity *peer)
2235 {
2236   struct GAS_MLP_Handle *mlp = solver;
2237   struct ATS_Peer *p = NULL;
2238
2239   GNUNET_assert (NULL != solver);
2240   GNUNET_assert (NULL != peer);
2241   if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2242   {
2243     GNUNET_assert (GNUNET_YES ==
2244                    GNUNET_CONTAINER_multipeermap_remove (mlp->requested_peers, peer, p));
2245     GNUNET_free (p);
2246
2247     mlp->stat_mlp_prob_changed = GNUNET_YES;
2248     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2249     {
2250       GAS_mlp_solve_problem (solver);
2251     }
2252   }
2253 }
2254
2255
2256 /**
2257  * Changes the preferences for a peer in the MLP problem
2258  *
2259  * @param solver the MLP Handle
2260  * @param peer the peer
2261  * @param kind the kind to change the preference
2262  * @param pref_rel the relative score
2263  */
2264 static void
2265 GAS_mlp_address_change_preference (void *solver,
2266                    const struct GNUNET_PeerIdentity *peer,
2267                    enum GNUNET_ATS_PreferenceKind kind,
2268                    double pref_rel)
2269 {
2270   struct GAS_MLP_Handle *mlp = solver;
2271   struct ATS_Peer *p;
2272
2273   LOG (GNUNET_ERROR_TYPE_DEBUG,
2274        "Changing preference for address for peer `%s' to %.2f\n",
2275        GNUNET_i2s(peer),
2276        pref_rel);
2277
2278   GNUNET_STATISTICS_update (mlp->env->stats,
2279                             "# LP address preference changes", 1, GNUNET_NO);
2280   /* Update the constraints with changed preferences */
2281
2282
2283
2284   /* Update relativity constraint c9 */
2285   if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2286   {
2287     LOG (GNUNET_ERROR_TYPE_INFO,
2288          "Updating preference for unknown peer `%s'\n",
2289          GNUNET_i2s(peer));
2290     return;
2291   }
2292
2293   if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2294   {
2295     p->f = get_peer_pref_value (mlp, peer);
2296     mlp_create_problem_update_value (&mlp->p,
2297                                      p->r_c9,
2298                                      mlp->p.c_r,
2299                                      - p->f,
2300                                      __LINE__);
2301
2302     /* Problem size changed: new address for peer with pending request */
2303     mlp->stat_mlp_prob_updated = GNUNET_YES;
2304     if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2305       GAS_mlp_solve_problem (solver);
2306   }
2307 }
2308
2309
2310 /**
2311  * Get application feedback for a peer
2312  *
2313  * @param solver the solver handle
2314  * @param application the application
2315  * @param peer the peer to change the preference for
2316  * @param scope the time interval for this feedback: [now - scope .. now]
2317  * @param kind the kind to change the preference
2318  * @param score the score
2319  */
2320 static void
2321 GAS_mlp_address_preference_feedback (void *solver,
2322                                      struct GNUNET_SERVER_Client *application,
2323                                      const struct GNUNET_PeerIdentity *peer,
2324                                      const struct GNUNET_TIME_Relative scope,
2325                                      enum GNUNET_ATS_PreferenceKind kind,
2326                                      double score)
2327 {
2328   struct GAS_PROPORTIONAL_Handle *s = solver;
2329
2330   GNUNET_assert (NULL != solver);
2331   GNUNET_assert (NULL != peer);
2332   GNUNET_assert (NULL != s);
2333 }
2334
2335
2336 static int
2337 mlp_free_peers (void *cls,
2338                 const struct GNUNET_PeerIdentity *key, void *value)
2339 {
2340   struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2341   struct ATS_Peer *p = value;
2342
2343   GNUNET_assert (GNUNET_YES ==
2344                  GNUNET_CONTAINER_multipeermap_remove (map, key, value));
2345   GNUNET_free (p);
2346
2347   return GNUNET_OK;
2348 }
2349
2350
2351 /**
2352  * Shutdown the MLP problem solving component
2353  *
2354  * @param cls the solver handle
2355  * @return NULL
2356  */
2357 void *
2358 libgnunet_plugin_ats_mlp_done (void *cls)
2359 {
2360   struct GNUNET_ATS_SolverFunctions *sf = cls;
2361   struct GAS_MLP_Handle *mlp = sf->cls;
2362
2363   LOG (GNUNET_ERROR_TYPE_DEBUG,
2364        "Shutting down mlp solver\n");
2365   mlp_delete_problem (mlp);
2366   GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
2367                                          &mlp_free_peers,
2368                                          mlp->requested_peers);
2369   GNUNET_CONTAINER_multipeermap_destroy (mlp->requested_peers);
2370   mlp->requested_peers = NULL;
2371
2372   /* Clean up GLPK environment */
2373   glp_free_env();
2374   GNUNET_free (mlp);
2375
2376   LOG (GNUNET_ERROR_TYPE_DEBUG,
2377        "Shutdown down of mlp solver complete\n");
2378   return NULL;
2379 }
2380
2381
2382 void *
2383 libgnunet_plugin_ats_mlp_init (void *cls)
2384 {
2385   static struct GNUNET_ATS_SolverFunctions sf;
2386   struct GNUNET_ATS_PluginEnvironment *env = cls;
2387   struct GAS_MLP_Handle * mlp = GNUNET_new (struct GAS_MLP_Handle);
2388   float f_tmp;
2389   unsigned long long tmp;
2390   unsigned int b_min;
2391   unsigned int n_min;
2392   int c;
2393   char *outputformat;
2394
2395   struct GNUNET_TIME_Relative max_duration;
2396   long long unsigned int max_iterations;
2397
2398   /* Init GLPK environment */
2399   int res = glp_init_env();
2400   switch (res) {
2401     case 0:
2402       LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2403           "initialization successful");
2404       break;
2405     case 1:
2406       LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2407           "environment is already initialized");
2408       break;
2409     case 2:
2410       LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2411           "initialization failed (insufficient memory)");
2412       GNUNET_free(mlp);
2413       return NULL;
2414       break;
2415     case 3:
2416       LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2417           "initialization failed (unsupported programming model)");
2418       GNUNET_free(mlp);
2419       return NULL;
2420       break;
2421     default:
2422       break;
2423   }
2424
2425   mlp->opt_dump_problem_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2426      "ats", "MLP_DUMP_PROBLEM_ALL");
2427   if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2428    mlp->opt_dump_problem_all = GNUNET_NO;
2429
2430   mlp->opt_dump_solution_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2431      "ats", "MLP_DUMP_SOLUTION_ALL");
2432   if (GNUNET_SYSERR == mlp->opt_dump_solution_all)
2433    mlp->opt_dump_solution_all = GNUNET_NO;
2434
2435   mlp->opt_dump_problem_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2436      "ats", "MLP_DUMP_PROBLEM_ON_FAIL");
2437   if (GNUNET_SYSERR == mlp->opt_dump_problem_on_fail)
2438    mlp->opt_dump_problem_on_fail = GNUNET_NO;
2439
2440   mlp->opt_dump_solution_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2441      "ats", "MLP_DUMP_SOLUTION_ON_FAIL");
2442   if (GNUNET_SYSERR == mlp->opt_dump_solution_on_fail)
2443    mlp->opt_dump_solution_on_fail = GNUNET_NO;
2444
2445   mlp->opt_dbg_glpk_verbose = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2446      "ats", "MLP_DBG_GLPK_VERBOSE");
2447   if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2448    mlp->opt_dbg_glpk_verbose = GNUNET_NO;
2449
2450   mlp->opt_dbg_feasibility_only = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2451      "ats", "MLP_DBG_FEASIBILITY_ONLY");
2452   if (GNUNET_SYSERR == mlp->opt_dbg_feasibility_only)
2453    mlp->opt_dbg_feasibility_only = GNUNET_NO;
2454   if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
2455     LOG (GNUNET_ERROR_TYPE_WARNING,
2456         "MLP solver is configured to check feasibility only!\n");
2457
2458   mlp->opt_dbg_autoscale_problem = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2459      "ats", "MLP_DBG_AUTOSCALE_PROBLEM");
2460   if (GNUNET_SYSERR == mlp->opt_dbg_autoscale_problem)
2461    mlp->opt_dbg_autoscale_problem = GNUNET_NO;
2462   if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
2463     LOG (GNUNET_ERROR_TYPE_WARNING,
2464         "MLP solver is configured automatically scale the problem!\n");
2465
2466   mlp->opt_dbg_intopt_presolver = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2467      "ats", "MLP_DBG_INTOPT_PRESOLVE");
2468   if (GNUNET_SYSERR == mlp->opt_dbg_intopt_presolver)
2469    mlp->opt_dbg_intopt_presolver = GNUNET_NO;
2470   if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
2471     LOG (GNUNET_ERROR_TYPE_WARNING,
2472         "MLP solver is configured use the mlp presolver\n");
2473
2474   mlp->opt_dbg_optimize_diversity = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2475      "ats", "MLP_DBG_OPTIMIZE_DIVERSITY");
2476   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_diversity)
2477    mlp->opt_dbg_optimize_diversity = GNUNET_YES;
2478   if (GNUNET_NO == mlp->opt_dbg_optimize_diversity)
2479     LOG (GNUNET_ERROR_TYPE_WARNING,
2480         "MLP solver is not optimizing for diversity\n");
2481
2482   mlp->opt_dbg_optimize_relativity= GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2483      "ats", "MLP_DBG_OPTIMIZE_RELATIVITY");
2484   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_relativity)
2485    mlp->opt_dbg_optimize_relativity = GNUNET_YES;
2486   if (GNUNET_NO == mlp->opt_dbg_optimize_relativity)
2487     LOG (GNUNET_ERROR_TYPE_WARNING,
2488         "MLP solver is not optimizing for relativity\n");
2489
2490   mlp->opt_dbg_optimize_quality = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2491      "ats", "MLP_DBG_OPTIMIZE_QUALITY");
2492   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_quality)
2493    mlp->opt_dbg_optimize_quality = GNUNET_YES;
2494   if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2495     LOG (GNUNET_ERROR_TYPE_WARNING,
2496         "MLP solver is not optimizing for quality\n");
2497
2498   mlp->opt_dbg_optimize_utility = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
2499      "ats", "MLP_DBG_OPTIMIZE_UTILITY");
2500   if (GNUNET_SYSERR == mlp->opt_dbg_optimize_utility)
2501    mlp->opt_dbg_optimize_utility = GNUNET_YES;
2502   if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2503     LOG (GNUNET_ERROR_TYPE_WARNING,
2504         "MLP solver is not optimizing for utility\n");
2505
2506   if ( (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2507        (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2508        (GNUNET_NO == mlp->opt_dbg_optimize_relativity) &&
2509        (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2510        (GNUNET_NO == mlp->opt_dbg_feasibility_only))
2511   {
2512     LOG (GNUNET_ERROR_TYPE_ERROR,
2513         _("MLP solver is not optimizing for anything, changing to feasibility check\n"));
2514     mlp->opt_dbg_feasibility_only = GNUNET_YES;
2515   }
2516
2517   if (GNUNET_SYSERR == GNUNET_CONFIGURATION_get_value_string (env->cfg,
2518      "ats", "MLP_LOG_FORMAT", &outputformat))
2519    mlp->opt_log_format = MLP_CPLEX;
2520   else
2521   {
2522     GNUNET_STRINGS_utf8_toupper(outputformat, outputformat);
2523     if (0 == strcmp (outputformat, "MPS"))
2524     {
2525       mlp->opt_log_format = MLP_MPS;
2526     }
2527     else if (0 == strcmp (outputformat, "CPLEX"))
2528     {
2529       mlp->opt_log_format = MLP_CPLEX;
2530     }
2531     else if (0 == strcmp (outputformat, "GLPK"))
2532     {
2533       mlp->opt_log_format = MLP_GLPK;
2534     }
2535     else
2536     {
2537       LOG (GNUNET_ERROR_TYPE_WARNING,
2538           "Invalid log format `%s' in configuration, using CPLEX!\n",
2539           outputformat);
2540       mlp->opt_log_format = MLP_CPLEX;
2541     }
2542     GNUNET_free (outputformat);
2543   }
2544
2545   mlp->pv.BIG_M = (double) BIG_M_VALUE;
2546
2547   mlp->pv.mip_gap = (double) 0.0;
2548   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2549       "MLP_MAX_MIP_GAP", &f_tmp))
2550   {
2551     if ((f_tmp < 0.0) || (f_tmp > 1.0))
2552     {
2553       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2554           "MIP gap", f_tmp);
2555     }
2556     else
2557     {
2558       mlp->pv.mip_gap = f_tmp;
2559       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2560           "MIP gap", f_tmp);
2561     }
2562   }
2563
2564   mlp->pv.lp_mip_gap = (double) 0.0;
2565   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2566       "MLP_MAX_LP_MIP_GAP", &f_tmp))
2567   {
2568     if ((f_tmp < 0.0) || (f_tmp > 1.0))
2569     {
2570       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2571           "LP/MIP", f_tmp);
2572     }
2573     else
2574     {
2575       mlp->pv.lp_mip_gap = f_tmp;
2576       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2577           "LP/MIP", f_tmp);
2578     }
2579   }
2580
2581   /* Get timeout for iterations */
2582   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats",
2583       "MLP_MAX_DURATION", &max_duration))
2584   {
2585     max_duration = MLP_MAX_EXEC_DURATION;
2586   }
2587
2588   /* Get maximum number of iterations */
2589   if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(env->cfg, "ats",
2590       "MLP_MAX_ITERATIONS", &max_iterations))
2591   {
2592     max_iterations = MLP_MAX_ITERATIONS;
2593   }
2594
2595   /* Get diversity coefficient from configuration */
2596   mlp->pv.co_D = MLP_DEFAULT_D;
2597   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2598       "MLP_COEFFICIENT_D", &f_tmp))
2599   {
2600     if ((f_tmp < 0.0))
2601     {
2602       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2603           "MLP_COEFFICIENT_D", f_tmp);
2604     }
2605     else
2606     {
2607       mlp->pv.co_D = f_tmp;
2608       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2609           "MLP_COEFFICIENT_D", f_tmp);
2610     }
2611   }
2612
2613   /* Get relativity coefficient from configuration */
2614   mlp->pv.co_R = MLP_DEFAULT_R;
2615   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2616       "MLP_COEFFICIENT_R", &f_tmp))
2617   {
2618     if ((f_tmp < 0.0))
2619     {
2620       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2621           "MLP_COEFFICIENT_R", f_tmp);
2622     }
2623     else
2624     {
2625       mlp->pv.co_R = f_tmp;
2626       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2627           "MLP_COEFFICIENT_R", f_tmp);
2628     }
2629   }
2630
2631
2632   /* Get utilization coefficient from configuration */
2633   mlp->pv.co_U = MLP_DEFAULT_U;
2634   if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
2635       "MLP_COEFFICIENT_U", &f_tmp))
2636   {
2637     if ((f_tmp < 0.0))
2638     {
2639       LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2640           "MLP_COEFFICIENT_U", f_tmp);
2641     }
2642     else
2643     {
2644       mlp->pv.co_U = f_tmp;
2645       LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2646           "MLP_COEFFICIENT_U", f_tmp);
2647     }
2648   }
2649
2650   /* Get quality metric coefficients from configuration */
2651   int i_delay = MLP_NaN;
2652   int i_distance = MLP_NaN;
2653   int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties;
2654   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
2655   {
2656     /* initialize quality coefficients with default value 1.0 */
2657       mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2658
2659     mlp->pv.q[c] = q[c];
2660     if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY)
2661       i_delay = c;
2662     if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE)
2663       i_distance = c;
2664   }
2665
2666   if ( (i_delay != MLP_NaN) &&
2667        (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2668           "MLP_COEFFICIENT_QUALITY_DELAY", &tmp)) )
2669     mlp->pv.co_Q[i_delay] = (double) tmp / 100;
2670   else
2671     mlp->pv.co_Q[i_delay] = MLP_DEFAULT_QUALITY;
2672
2673   if ( (i_distance != MLP_NaN) &&
2674         (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2675           "MLP_COEFFICIENT_QUALITY_DISTANCE", &tmp)) )
2676     mlp->pv.co_Q[i_distance] = (double) tmp / 100;
2677   else
2678     mlp->pv.co_Q[i_distance] = MLP_DEFAULT_QUALITY;
2679
2680   /* Get minimum bandwidth per used address from configuration */
2681   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2682                                                       "MLP_MIN_BANDWIDTH",
2683                                                       &tmp))
2684     b_min = tmp;
2685   else
2686   {
2687     b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2688   }
2689
2690   /* Get minimum number of connections from configuration */
2691   if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
2692                                                       "MLP_MIN_CONNECTIONS",
2693                                                       &tmp))
2694     n_min = tmp;
2695   else
2696     n_min = MLP_DEFAULT_MIN_CONNECTIONS;
2697
2698   /* Init network quotas */
2699   for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
2700   {
2701     mlp->pv.quota_index[c] = c;
2702     mlp->pv.quota_out[c] = env->out_quota[c];
2703     mlp->pv.quota_in[c] = env->in_quota[c];
2704
2705     LOG (GNUNET_ERROR_TYPE_INFO,
2706          "Quota for network `%s' (in/out) %llu/%llu\n",
2707          GNUNET_ATS_print_network_type (c),
2708          mlp->pv.quota_out[c],
2709          mlp->pv.quota_in[c]);
2710     /* Check if defined quota could make problem unsolvable */
2711     if ((n_min * b_min) > mlp->pv.quota_out[c])
2712     {
2713       LOG (GNUNET_ERROR_TYPE_INFO,
2714            _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2715            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2716            mlp->pv.quota_out[c],
2717            (n_min * b_min));
2718       mlp->pv.quota_out[c] = (n_min * b_min);
2719     }
2720     if ((n_min * b_min) > mlp->pv.quota_in[c])
2721     {
2722       LOG (GNUNET_ERROR_TYPE_INFO,
2723            _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2724            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2725            mlp->pv.quota_in[c],
2726            (n_min * b_min));
2727       mlp->pv.quota_in[c] = (n_min * b_min);
2728     }
2729     /* Check if bandwidth is too big to make problem solvable */
2730     if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2731     {
2732       LOG (GNUNET_ERROR_TYPE_INFO,
2733            _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2734            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2735            mlp->pv.quota_out[c],
2736            mlp->pv.BIG_M);
2737       mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
2738     }
2739     if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2740     {
2741       LOG (GNUNET_ERROR_TYPE_INFO,
2742            _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2743            GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
2744            mlp->pv.quota_in[c],
2745            mlp->pv.BIG_M);
2746       mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
2747     }
2748   }
2749   mlp->env = env;
2750   sf.cls = mlp;
2751   sf.s_add = &GAS_mlp_address_add;
2752   sf.s_address_update_property = &GAS_mlp_address_property_changed;
2753   sf.s_get = &GAS_mlp_get_preferred_address;
2754   sf.s_get_stop = &GAS_mlp_stop_get_preferred_address;
2755   sf.s_pref = &GAS_mlp_address_change_preference;
2756   sf.s_feedback = &GAS_mlp_address_preference_feedback;
2757   sf.s_del = &GAS_mlp_address_delete;
2758   sf.s_bulk_start = &GAS_mlp_bulk_start;
2759   sf.s_bulk_stop = &GAS_mlp_bulk_stop;
2760
2761   /* Setting MLP Input variables */
2762   mlp->pv.b_min = b_min;
2763   mlp->pv.n_min = n_min;
2764   mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount;
2765   mlp->stat_mlp_prob_changed = GNUNET_NO;
2766   mlp->stat_mlp_prob_updated = GNUNET_NO;
2767   mlp->opt_mlp_auto_solve = GNUNET_YES;
2768   mlp->requested_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
2769   mlp->stat_bulk_requests = 0;
2770   mlp->stat_bulk_lock = 0;
2771
2772   /* Setup GLPK */
2773   /* Redirect GLPK output to GNUnet logging */
2774   glp_term_hook (&mlp_term_hook, (void *) mlp);
2775
2776   /* Init LP solving parameters */
2777   glp_init_smcp(&mlp->control_param_lp);
2778   mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2779   if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2780     mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2781
2782   mlp->control_param_lp.it_lim = max_iterations;
2783   mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2784
2785   /* Init MLP solving parameters */
2786   glp_init_iocp(&mlp->control_param_mlp);
2787   /* Setting callback function */
2788   mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2789   mlp->control_param_mlp.cb_info = mlp;
2790   mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2791   mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2792   if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2793     mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2794   mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2795
2796   LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2797
2798   return &sf;
2799 }
2800
2801 /* end of plugin_ats_mlp.c */