src/ats/plugin_ats_mlp.h

   1 /*
   2  (C) 2011 Christian Grothoff (and other contributing authors)
   3
   4  GNUnet is free software; you can redistribute it and/or modify
   5  it under the terms of the GNU General Public License as published
   6  by the Free Software Foundation; either version 3, or (at your
   7  option) any later version.
   8
   9  GNUnet is distributed in the hope that it will be useful, but
  10  WITHOUT ANY WARRANTY; without even the implied warranty of
  11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  General Public License for more details.
  13
  14  You should have received a copy of the GNU General Public License
  15  along with GNUnet; see the file COPYING.  If not, write to the
  16  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  Boston, MA 02111-1307, USA.
  18  */
  19
  20 /**
  21  * @file ats/plugin_ats_mlp.h
  22  * @brief ats MLP problem solver
  23  * @author Matthias Wachs
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "gnunet_ats_service.h"
  29 #include "gnunet_ats_plugin.h"
  30 #include "gnunet-service-ats_addresses.h"
  31 #include "gnunet_statistics_service.h"
  32 #include <float.h>
  33 #if HAVE_LIBGLPK
  34 #include "glpk.h"
  35 #endif
  36
  37 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  38 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  39
  40 #define BIG_M_VALUE (UINT32_MAX) /10
  41 #define BIG_M_STRING "unlimited"
  42
  43 #define MLP_AVERAGING_QUEUE_LENGTH 3
  44
  45 #define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
  46 #define MLP_MAX_ITERATIONS      4096
  47
  48 #define DEFAULT_D 1.0
  49 #define DEFAULT_R 1.0
  50 #define DEFAULT_U 1.0
  51 #define DEFAULT_QUALITY 1.0
  52 #define DEFAULT_MIN_CONNECTIONS 4
  53 #define DEFAULT_PEER_PREFERENCE 1.0
  54
  55 #define MLP_NaN -1
  56 #define MLP_UNDEFINED 0
  57 #define GLP_YES 1.0
  58 #define GLP_NO  0.0
  59
  60 enum MLP_Output_Format
  61 {
  62   MLP_MPS,
  63   MLP_CPLEX,
  64   MLP_GLPK
  65 };
  66
  67
  68 struct MLP_Solution
  69 {
  70   int lp_res;
  71   int lp_presolv;
  72   int mip_res;
  73   int mip_presolv;
  74
  75   double lp_objective_value;
  76   double mlp_objective_value;
  77   double mlp_gap;
  78   double lp_mlp_gap;
  79
  80   int p_elements;
  81   int p_cols;
  82   int p_rows;
  83
  84   int n_peers;
  85   int n_addresses;
  86
  87 };
  88
  89 struct ATS_Peer
  90 {
  91   struct GNUNET_PeerIdentity id;
  92
  93   /* Was this peer already added to the current problem? */
  94   int processed;
  95
  96   /* constraint 2: 1 address per peer*/
  97   unsigned int r_c2;
  98
  99   /* constraint 9: relativity */
 100   unsigned int r_c9;
 101
 102   /* Legacy preference value */
 103   double f;
 104 };
 105
 106 struct MLP_Problem
 107 {
 108   /**
 109    * GLPK (MLP) problem object
 110    */
 111 #if HAVE_LIBGLPK
 112   glp_prob *prob;
 113 #else
 114   void *prob;
 115 #endif
 116
 117   /* Number of addresses in problem */
 118   unsigned int num_addresses;
 119   /* Number of peers in problem */
 120   unsigned int num_peers;
 121   /* Number of elements in problem matrix */
 122   unsigned int num_elements;
 123
 124   /* Row index constraint 2: */
 125   unsigned int r_c2;
 126   /* Row index constraint 4: minimum connections */
 127   unsigned int r_c4;
 128   /* Row index constraint 6: maximize diversity */
 129   unsigned int r_c6;
 130   /* Row index constraint 8: utilization*/
 131   unsigned int r_c8;
 132   /* Row index constraint 9: relativity*/
 133   unsigned int r_c9;
 134   /* Row indices quality metrics  */
 135   int r_q[GNUNET_ATS_QualityPropertiesCount];
 136   /* Row indices ATS network quotas */
 137   int r_quota[GNUNET_ATS_NetworkTypeCount];
 138
 139   /* Column index Diversity (D) column */
 140   int c_d;
 141   /* Column index Utilization (U) column */
 142   int c_u;
 143   /* Column index Proportionality (R) column */
 144   int c_r;
 145   /* Column index quality metrics  */
 146   int c_q[GNUNET_ATS_QualityPropertiesCount];
 147
 148   /* Problem matrix */
 149   /* Current index */
 150   unsigned int ci;
 151   /* Row index array */
 152   int *ia;
 153   /* Column index array */
 154   int *ja;
 155   /* Column index value */
 156   double *ar;
 157
 158 };
 159
 160 struct MLP_Variables
 161 {
 162   /* Big M value for bandwidth capping */
 163   double BIG_M;
 164
 165   /* MIP Gap */
 166   double mip_gap;
 167
 168   /* LP MIP Gap */
 169   double lp_mip_gap;
 170
 171   /* ATS Quality metrics
 172    *
 173    * Array with GNUNET_ATS_QualityPropertiesCount elements
 174    * contains mapping to GNUNET_ATS_Property*/
 175   int q[GNUNET_ATS_QualityPropertiesCount];
 176
 177   /* Number of quality metrics */
 178   int m_q;
 179
 180   /* Number of quality metrics */
 181   int m_rc;
 182
 183   /* Quality metric coefficients*/
 184   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 185
 186   /* Ressource costs coefficients*/
 187   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 188
 189   /* Diversity coefficient */
 190   double co_D;
 191
 192   /* Utility coefficient */
 193   double co_U;
 194
 195   /* Relativity coefficient */
 196   double co_R;
 197
 198   /* Minimum bandwidth assigned to an address */
 199   unsigned int b_min;
 200
 201   /* Minimum number of addresses with bandwidth assigned */
 202   unsigned int n_min;
 203
 204   /* Quotas */
 205   /* Array mapping array index to ATS network */
 206   int quota_index[GNUNET_ATS_NetworkTypeCount];
 207   /* Outbound quotas */
 208   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 209   /* Inbound quotas */
 210
 211   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 212
 213   /* ATS ressource costs
 214    * array with GNUNET_ATS_QualityPropertiesCount elements
 215    * contains mapping to GNUNET_ATS_Property
 216    * */
 217   int rc[GNUNET_ATS_QualityPropertiesCount];
 218
 219 };
 220
 221 /**
 222  * MLP Handle
 223  */
 224 struct GAS_MLP_Handle
 225 {
 226   struct GNUNET_ATS_PluginEnvironment *env;
 227
 228   /**
 229    * Statistics handle
 230    */
 231   struct GNUNET_STATISTICS_Handle *stats;
 232
 233   /**
 234    * Address hashmap for lookups
 235    */
 236   const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
 237
 238   /**
 239    * Addresses' bandwidth changed callback
 240    */
 241   GAS_bandwidth_changed_cb bw_changed_cb;
 242
 243   /**
 244    * Addresses' bandwidth changed callback closure
 245    */
 246   void *bw_changed_cb_cls;
 247
 248   /**
 249    * ATS function to get preferences
 250    */
 251   GAS_get_preferences get_preferences;
 252
 253   /**
 254    * Closure for ATS function to get preferences
 255    */
 256   void *get_preferences_cls;
 257
 258   /**
 259    * ATS function to get properties
 260    */
 261   GAS_get_properties get_properties;
 262
 263   /**
 264    * Closure for ATS function to get properties
 265    */
 266   void *get_properties_cls;
 267
 268   /**
 269    * Exclude peer from next result propagation
 270    */
 271   const struct GNUNET_PeerIdentity *exclude_peer;
 272
 273   /**
 274    * Encapsulation for the MLP problem
 275    */
 276   struct MLP_Problem p;
 277
 278   /**
 279    * Encapsulation for the MLP problem variables
 280    */
 281   struct MLP_Variables pv;
 282
 283   /**
 284    * Encapsulation for the MLP solution
 285    */
 286   struct MLP_Solution ps;
 287
 288   /**
 289    * Bulk lock
 290    */
 291
 292   int stat_bulk_lock;
 293
 294   /**
 295    * Number of changes while solver was locked
 296    */
 297   int stat_bulk_requests;
 298
 299   /**
 300    * GLPK LP control parameter
 301    */
 302 #if HAVE_LIBGLPK
 303   glp_smcp control_param_lp;
 304 #else
 305   void *control_param_lp;
 306 #endif
 307
 308   /**
 309    * GLPK LP control parameter
 310    */
 311 #if HAVE_LIBGLPK
 312   glp_iocp control_param_mlp;
 313 #else
 314   void *control_param_mlp;
 315 #endif
 316
 317   /**
 318    * Peers with pending address requests
 319    */
 320   struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
 321
 322   /**
 323    * Was the problem updated since last solution
 324    */
 325   int stat_mlp_prob_updated;
 326
 327   /**
 328    * Has the problem size changed since last solution
 329    */
 330   int stat_mlp_prob_changed;
 331
 332   /**
 333    * Solve the problem automatically when updates occur?
 334    * Default: GNUNET_YES
 335    * Can be disabled for test and measurements
 336    */
 337   int opt_mlp_auto_solve;
 338
 339   /**
 340    * Write all MILP problems to a MPS file
 341    */
 342   int opt_dump_problem_all;
 343
 344   /**
 345    * Write all MILP problem solutions to a file
 346    */
 347   int opt_dump_solution_all;
 348
 349   /**
 350    * Write MILP problems to a MPS file when solver fails
 351    */
 352   int opt_dump_problem_on_fail;
 353
 354   /**
 355    * Write MILP problem solutions to a file when solver fails
 356    */
 357   int opt_dump_solution_on_fail;
 358
 359   /**
 360    * solve feasibility only
 361    */
 362   int opt_dbg_feasibility_only;
 363
 364   /**
 365    * solve autoscale the problem
 366    */
 367   int opt_dbg_autoscale_problem;
 368
 369   /**
 370    * use the intopt presolver instead of simplex
 371    */
 372   int opt_dbg_intopt_presolver;
 373
 374   /**
 375    * Print GLPK output
 376    */
 377   int opt_dbg_glpk_verbose;
 378
 379   /**
 380    * solve autoscale the problem
 381    */
 382   int opt_dbg_optimize_relativity;
 383
 384   /**
 385    * solve autoscale the problem
 386    */
 387   int opt_dbg_optimize_diversity;
 388
 389   /**
 390    * solve autoscale the problem
 391    */
 392   int opt_dbg_optimize_quality;
 393
 394   /**
 395    * solve autoscale the problem
 396    */
 397   int opt_dbg_optimize_utility;
 398
 399
 400   /**
 401    * Output format
 402    */
 403   enum MLP_Output_Format opt_log_format;
 404 };
 405
 406 /**
 407  * Address specific MLP information
 408  */
 409 struct MLP_information
 410 {
 411
 412   /* Bandwidth assigned */
 413   struct GNUNET_BANDWIDTH_Value32NBO b_out;
 414   struct GNUNET_BANDWIDTH_Value32NBO b_in;
 415
 416   /* Address selected */
 417   int n;
 418
 419   /* bandwidth column index */
 420   signed int c_b;
 421
 422   /* address usage column */
 423   signed int c_n;
 424
 425   /* row indexes */
 426
 427   /* constraint 1: bandwidth capping */
 428   unsigned int r_c1;
 429
 430   /* constraint 3: minimum bandwidth */
 431   unsigned int r_c3;
 432 };
 433
 434
 435 /**
 436  * Solves the MLP problem
 437  *
 438  * @param solver the MLP Handle
 439  * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 440  */
 441 int
 442 GAS_mlp_solve_problem (void *solver);
 443
 444
 445 /**
 446  * Init the MLP problem solving component
 447  *
 448  * @param cfg the GNUNET_CONFIGURATION_Handle handle
 449  * @param stats the GNUNET_STATISTICS handle
 450  * @param addresses Hashmap containing addresses
 451  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 452  * @param out_dest array of outbound quotas
 453  * @param in_dest array of outbound quota
 454  * @param dest_length array length for quota arrays
 455  * @param bw_changed_cb callback for changed bandwidth amounts
 456  * @param bw_changed_cb_cls cls for callback
 457  * @param get_preference callback to get relative preferences for a peer
 458  * @param get_preference_cls cls for callback to get relative preferences for a peer
 459  * @param get_properties callback to get relative properties
 460  * @param get_properties_cls cls for callback to get relative properties
 461  * @return struct GAS_MLP_Handle on success, NULL on fail
 462  */
 463 void *
 464 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 465               const struct GNUNET_STATISTICS_Handle *stats,
 466               const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
 467               int *network,
 468               unsigned long long *out_dest,
 469               unsigned long long *in_dest,
 470               int dest_length,
 471               GAS_bandwidth_changed_cb bw_changed_cb,
 472               void *bw_changed_cb_cls,
 473               GAS_get_preferences get_preference,
 474               void *get_preference_cls,
 475               GAS_get_properties get_properties,
 476               void *get_properties_cls);
 477
 478
 479 /**
 480  * Add a single address within a network to the solver
 481  *
 482  * @param solver the solver Handle
 483  * @param address the address to add
 484  * @param network network type of this address
 485  */
 486 void
 487 GAS_mlp_address_add (void *solver, struct ATS_Address *address,
 488     uint32_t network);
 489
 490
 491 /**
 492  * Transport properties for this address have changed
 493  *
 494  * @param solver solver handle
 495  * @param address the address
 496  * @param type the ATSI type in HBO
 497  * @param abs_value the absolute value of the property
 498  * @param rel_value the normalized value
 499  */
 500 void
 501 GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
 502     uint32_t type, uint32_t abs_value, double rel_value);
 503
 504
 505 /**
 506  * Transport session for this address has changed
 507  *
 508  * NOTE: values in addresses are already updated
 509  *
 510  * @param solver solver handle
 511  * @param address the address
 512  * @param cur_session the current session
 513  * @param new_session the new session
 514  */
 515 void
 516 GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
 517                                  uint32_t cur_session, uint32_t new_session);
 518
 519
 520 /**
 521  * Usage for this address has changed
 522  *
 523  * NOTE: values in addresses are already updated
 524  *
 525  * @param solver solver handle
 526  * @param address the address
 527  * @param in_use usage state
 528  */
 529 void
 530 GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
 531     int in_use);
 532
 533 /**
 534  * Network scope for this address has changed
 535  *
 536  * NOTE: values in addresses are already updated
 537  *
 538  * @param solver solver handle
 539  * @param address the address
 540  * @param current_network the current network
 541  * @param new_network the new network
 542  */
 543 void
 544 GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
 545     uint32_t current_network, uint32_t new_network);
 546
 547 /**
 548  * Deletes a single address in the MLP problem
 549  *
 550  * The MLP problem has to be recreated and the problem has to be resolved
 551  *
 552  * @param solver the MLP Handle
 553  * @param address the address to delete
 554  * @param session_only delete only session not whole address
 555  */
 556 void
 557 GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
 558     int session_only);
 559
 560 /**
 561  * Changes the preferences for a peer in the MLP problem
 562  *
 563  * @param solver the MLP Handle
 564  * @param peer the peer
 565  * @param kind the kind to change the preference
 566  * @param pref_rel the relative score
 567  */
 568 void
 569 GAS_mlp_address_change_preference (void *solver,
 570     const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
 571     double pref_rel);
 572
 573 /**
 574  * Get application feedback for a peer
 575  *
 576  * @param solver the solver handle
 577  * @param application the application
 578  * @param peer the peer to change the preference for
 579  * @param scope the time interval for this feedback: [now - scope .. now]
 580  * @param kind the kind to change the preference
 581  * @param score the score
 582  */
 583 void
 584 GAS_mlp_address_preference_feedback (void *solver, void *application,
 585     const struct GNUNET_PeerIdentity *peer,
 586     const struct GNUNET_TIME_Relative scope,
 587     enum GNUNET_ATS_PreferenceKind kind, double score);
 588
 589 /**
 590  * Start a bulk operation
 591  *
 592  * @param solver the solver
 593  */
 594 void
 595 GAS_mlp_bulk_start (void *solver);
 596
 597 /**
 598  * Bulk operation done
 599  */
 600 void
 601 GAS_mlp_bulk_stop (void *solver);
 602
 603 /**
 604  * Get the preferred address for a specific peer until
 605  * GAS_mlp_stop_get_preferred_address is called
 606  *
 607  * @param solver the MLP Handle
 608  * @param peer the peer
 609  * @return suggested address
 610  */
 611 const struct ATS_Address *
 612 GAS_mlp_get_preferred_address (void *solver,
 613     const struct GNUNET_PeerIdentity *peer);
 614
 615 /**
 616  * Stop notifying about address and bandwidth changes for this peer
 617  *
 618  * @param solver the MLP handle
 619  * @param peer the peer
 620  */
 621 void
 622 GAS_mlp_stop_get_preferred_address (void *solver,
 623     const struct GNUNET_PeerIdentity *peer);
 624
 625 /**
 626  * Shutdown the MLP problem solving component
 627  *
 628  * @param solver the solver handle
 629  */
 630 void
 631 GAS_mlp_done (void *solver);
 632
 633 #endif
 634 /* end of plugin_ats_mlp.h */