src/ats/plugin_ats_mlp.c

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