src/ats/plugin_ats_mlp.c

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