src/ats/plugin_ats_mlp.c

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