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 #if HAVE_LIBGLPK
  33 #include "glpk.h"
  34 #endif
  35
  36 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  37 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  38
  39 #define BIG_M_VALUE (UINT32_MAX) /10
  40 #define BIG_M_STRING "unlimited"
  41
  42 #define MLP_AVERAGING_QUEUE_LENGTH 3
  43
  44 #define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
  45 #define MLP_MAX_ITERATIONS      4096
  46
  47 #define DEFAULT_D 1.0
  48 #define DEFAULT_R 1.0
  49 #define DEFAULT_U 1.0
  50 #define DEFAULT_QUALITY 1.0
  51 #define DEFAULT_MIN_CONNECTIONS 4
  52 #define DEFAULT_PEER_PREFERENCE 1.0
  53
  54 #define MLP_NaN -1
  55 #define MLP_UNDEFINED 0
  56 #define GLP_YES 1.0
  57 #define GLP_NO  0.0
  58
  59 struct MLP_Solution
  60 {
  61   int lp_res;
  62   int lp_presolv;
  63   int mip_res;
  64   int mip_presolv;
  65
  66   int p_elements;
  67   int p_cols;
  68   int p_rows;
  69
  70   int n_peers;
  71   int n_addresses;
  72
  73 };
  74
  75 struct ATS_Peer
  76 {
  77   struct GNUNET_PeerIdentity id;
  78
  79   /* Was this peer already added to the current problem? */
  80   int processed;
  81
  82   /* constraint 2: 1 address per peer*/
  83   unsigned int r_c2;
  84
  85   /* constraint 9: relativity */
  86   unsigned int r_c9;
  87
  88   /* Legacy preference value */
  89   double f;
  90 };
  91
  92 struct MLP_Problem
  93 {
  94   /**
  95    * GLPK (MLP) problem object
  96    */
  97 #if HAVE_LIBGLPK
  98   glp_prob *prob;
  99 #else
 100   void *prob;
 101 #endif
 102
 103   /* Number of addresses in problem */
 104   unsigned int num_addresses;
 105   /* Number of peers in problem */
 106   unsigned int num_peers;
 107   /* Number of elements in problem matrix */
 108   unsigned int num_elements;
 109
 110   /* Row index constraint 2: */
 111   unsigned int r_c2;
 112   /* Row index constraint 4: minimum connections */
 113   unsigned int r_c4;
 114   /* Row index constraint 6: maximize diversity */
 115   unsigned int r_c6;
 116   /* Row index constraint 8: utilization*/
 117   unsigned int r_c8;
 118   /* Row index constraint 9: relativity*/
 119   unsigned int r_c9;
 120   /* Row indices quality metrics  */
 121   int r_q[GNUNET_ATS_QualityPropertiesCount];
 122   /* Row indices ATS network quotas */
 123   int r_quota[GNUNET_ATS_NetworkTypeCount];
 124
 125   /* Column index Diversity (D) column */
 126   int c_d;
 127   /* Column index Utilization (U) column */
 128   int c_u;
 129   /* Column index Proportionality (R) column */
 130   int c_r;
 131   /* Column index quality metrics  */
 132   int c_q[GNUNET_ATS_QualityPropertiesCount];
 133
 134   /* Problem matrix */
 135   /* Current index */
 136   unsigned int ci;
 137   /* Row index array */
 138   int *ia;
 139   /* Column index array */
 140   int *ja;
 141   /* Column index value */
 142   double *ar;
 143
 144 };
 145
 146 struct MLP_Variables
 147 {
 148   /* Big M value for bandwidth capping */
 149   double BIG_M;
 150
 151   /* ATS Quality metrics
 152    *
 153    * Array with GNUNET_ATS_QualityPropertiesCount elements
 154    * contains mapping to GNUNET_ATS_Property*/
 155   int q[GNUNET_ATS_QualityPropertiesCount];
 156
 157   /* Number of quality metrics */
 158   int m_q;
 159
 160   /* Number of quality metrics */
 161   int m_rc;
 162
 163   /* Quality metric coefficients*/
 164   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 165
 166   /* Ressource costs coefficients*/
 167   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 168
 169   /* Diversity coefficient */
 170   double co_D;
 171
 172   /* Utility coefficient */
 173   double co_U;
 174
 175   /* Relativity coefficient */
 176   double co_R;
 177
 178   /* Minimum bandwidth assigned to an address */
 179   unsigned int b_min;
 180
 181   /* Minimum number of addresses with bandwidth assigned */
 182   unsigned int n_min;
 183
 184   /* Quotas */
 185   /* Array mapping array index to ATS network */
 186   int quota_index[GNUNET_ATS_NetworkTypeCount];
 187   /* Outbound quotas */
 188   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 189   /* Inbound quotas */
 190
 191   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 192
 193   /* ATS ressource costs
 194    * array with GNUNET_ATS_QualityPropertiesCount elements
 195    * contains mapping to GNUNET_ATS_Property
 196    * */
 197   int rc[GNUNET_ATS_QualityPropertiesCount];
 198
 199 };
 200
 201 /**
 202  * MLP Handle
 203  */
 204 struct GAS_MLP_Handle
 205 {
 206   struct GNUNET_ATS_PluginEnvironment *env;
 207
 208   /**
 209    * Statistics handle
 210    */
 211   struct GNUNET_STATISTICS_Handle *stats;
 212
 213   /**
 214    * Address hashmap for lookups
 215    */
 216   const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
 217
 218   /**
 219    * Addresses' bandwidth changed callback
 220    */
 221   GAS_bandwidth_changed_cb bw_changed_cb;
 222
 223   /**
 224    * Addresses' bandwidth changed callback closure
 225    */
 226   void *bw_changed_cb_cls;
 227
 228   /**
 229    * ATS function to get preferences
 230    */
 231   GAS_get_preferences get_preferences;
 232
 233   /**
 234    * Closure for ATS function to get preferences
 235    */
 236   void *get_preferences_cls;
 237
 238   /**
 239    * ATS function to get properties
 240    */
 241   GAS_get_properties get_properties;
 242
 243   /**
 244    * Closure for ATS function to get properties
 245    */
 246   void *get_properties_cls;
 247
 248   /**
 249    * Exclude peer from next result propagation
 250    */
 251   const struct GNUNET_PeerIdentity *exclude_peer;
 252
 253   /**
 254    * Encapsulation for the MLP problem
 255    */
 256   struct MLP_Problem p;
 257
 258   /**
 259    * Encapsulation for the MLP problem variables
 260    */
 261   struct MLP_Variables pv;
 262
 263   /**
 264    * Encapsulation for the MLP solution
 265    */
 266   struct MLP_Solution ps;
 267
 268   /**
 269    * Bulk lock
 270    */
 271
 272   int bulk_lock;
 273
 274   /**
 275    * Number of changes while solver was locked
 276    */
 277   int bulk_request;
 278
 279   /**
 280    * GLPK LP control parameter
 281    */
 282 #if HAVE_LIBGLPK
 283   glp_smcp control_param_lp;
 284 #else
 285   void *control_param_lp;
 286 #endif
 287
 288   /**
 289    * GLPK LP control parameter
 290    */
 291 #if HAVE_LIBGLPK
 292   glp_iocp control_param_mlp;
 293 #else
 294   void *control_param_mlp;
 295 #endif
 296
 297   /**
 298    * Peers with pending address requests
 299    */
 300   struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
 301
 302   /**
 303    * Was the problem updated since last solution
 304    */
 305   int mlp_prob_updated;
 306
 307   /**
 308    * Has the problem size changed since last solution
 309    */
 310   int mlp_prob_changed;
 311
 312   /**
 313    * Solve the problem automatically when updates occur?
 314    * Default: GNUNET_YES
 315    * Can be disabled for test and measurements
 316    */
 317   int mlp_auto_solve;
 318
 319   /**
 320    * Write MILP problem to a MPS file
 321    */
 322   int write_mip_mps;
 323
 324   /**
 325    * Write MILP problem to a MPS file
 326    */
 327   int write_mip_sol;
 328
 329 };
 330
 331 /**
 332  * Address specific MLP information
 333  */
 334 struct MLP_information
 335 {
 336
 337   /* Bandwidth assigned */
 338   struct GNUNET_BANDWIDTH_Value32NBO b_out;
 339   struct GNUNET_BANDWIDTH_Value32NBO b_in;
 340
 341   /* Address selected */
 342   int n;
 343
 344   /* bandwidth column index */
 345   signed int c_b;
 346
 347   /* address usage column */
 348   signed int c_n;
 349
 350   /* row indexes */
 351
 352   /* constraint 1: bandwidth capping */
 353   unsigned int r_c1;
 354
 355   /* constraint 3: minimum bandwidth */
 356   unsigned int r_c3;
 357 };
 358
 359
 360 /**
 361  * Solves the MLP problem
 362  *
 363  * @param solver the MLP Handle
 364  * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 365  */
 366 int
 367 GAS_mlp_solve_problem (void *solver);
 368
 369
 370 /**
 371  * Init the MLP problem solving component
 372  *
 373  * @param cfg the GNUNET_CONFIGURATION_Handle handle
 374  * @param stats the GNUNET_STATISTICS handle
 375  * @param addresses Hashmap containing addresses
 376  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 377  * @param out_dest array of outbound quotas
 378  * @param in_dest array of outbound quota
 379  * @param dest_length array length for quota arrays
 380  * @param bw_changed_cb callback for changed bandwidth amounts
 381  * @param bw_changed_cb_cls cls for callback
 382  * @param get_preference callback to get relative preferences for a peer
 383  * @param get_preference_cls cls for callback to get relative preferences for a peer
 384  * @param get_properties callback to get relative properties
 385  * @param get_properties_cls cls for callback to get relative properties
 386  * @return struct GAS_MLP_Handle on success, NULL on fail
 387  */
 388 void *
 389 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 390               const struct GNUNET_STATISTICS_Handle *stats,
 391               const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
 392               int *network,
 393               unsigned long long *out_dest,
 394               unsigned long long *in_dest,
 395               int dest_length,
 396               GAS_bandwidth_changed_cb bw_changed_cb,
 397               void *bw_changed_cb_cls,
 398               GAS_get_preferences get_preference,
 399               void *get_preference_cls,
 400               GAS_get_properties get_properties,
 401               void *get_properties_cls);
 402
 403
 404 /**
 405  * Add a single address within a network to the solver
 406  *
 407  * @param solver the solver Handle
 408  * @param address the address to add
 409  * @param network network type of this address
 410  */
 411 void
 412 GAS_mlp_address_add (void *solver, struct ATS_Address *address,
 413     uint32_t network);
 414
 415
 416 /**
 417  * Transport properties for this address have changed
 418  *
 419  * @param solver solver handle
 420  * @param address the address
 421  * @param type the ATSI type in HBO
 422  * @param abs_value the absolute value of the property
 423  * @param rel_value the normalized value
 424  */
 425 void
 426 GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
 427     uint32_t type, uint32_t abs_value, double rel_value);
 428
 429
 430 /**
 431  * Transport session for this address has changed
 432  *
 433  * NOTE: values in addresses are already updated
 434  *
 435  * @param solver solver handle
 436  * @param address the address
 437  * @param cur_session the current session
 438  * @param new_session the new session
 439  */
 440 void
 441 GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
 442                                  uint32_t cur_session, uint32_t new_session);
 443
 444
 445 /**
 446  * Usage for this address has changed
 447  *
 448  * NOTE: values in addresses are already updated
 449  *
 450  * @param solver solver handle
 451  * @param address the address
 452  * @param in_use usage state
 453  */
 454 void
 455 GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
 456     int in_use);
 457
 458 /**
 459  * Network scope for this address has changed
 460  *
 461  * NOTE: values in addresses are already updated
 462  *
 463  * @param solver solver handle
 464  * @param address the address
 465  * @param current_network the current network
 466  * @param new_network the new network
 467  */
 468 void
 469 GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
 470     uint32_t current_network, uint32_t new_network);
 471
 472 /**
 473  * Deletes a single address in the MLP problem
 474  *
 475  * The MLP problem has to be recreated and the problem has to be resolved
 476  *
 477  * @param solver the MLP Handle
 478  * @param address the address to delete
 479  * @param session_only delete only session not whole address
 480  */
 481 void
 482 GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
 483     int session_only);
 484
 485 /**
 486  * Changes the preferences for a peer in the MLP problem
 487  *
 488  * @param solver the MLP Handle
 489  * @param peer the peer
 490  * @param kind the kind to change the preference
 491  * @param pref_rel the relative score
 492  */
 493 void
 494 GAS_mlp_address_change_preference (void *solver,
 495     const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
 496     double pref_rel);
 497
 498 /**
 499  * Get application feedback for a peer
 500  *
 501  * @param solver the solver handle
 502  * @param application the application
 503  * @param peer the peer to change the preference for
 504  * @param scope the time interval for this feedback: [now - scope .. now]
 505  * @param kind the kind to change the preference
 506  * @param score the score
 507  */
 508 void
 509 GAS_mlp_address_preference_feedback (void *solver, void *application,
 510     const struct GNUNET_PeerIdentity *peer,
 511     const struct GNUNET_TIME_Relative scope,
 512     enum GNUNET_ATS_PreferenceKind kind, double score);
 513
 514 /**
 515  * Start a bulk operation
 516  *
 517  * @param solver the solver
 518  */
 519 void
 520 GAS_mlp_bulk_start (void *solver);
 521
 522 /**
 523  * Bulk operation done
 524  */
 525 void
 526 GAS_mlp_bulk_stop (void *solver);
 527
 528 /**
 529  * Get the preferred address for a specific peer until
 530  * GAS_mlp_stop_get_preferred_address is called
 531  *
 532  * @param solver the MLP Handle
 533  * @param peer the peer
 534  * @return suggested address
 535  */
 536 const struct ATS_Address *
 537 GAS_mlp_get_preferred_address (void *solver,
 538     const struct GNUNET_PeerIdentity *peer);
 539
 540 /**
 541  * Stop notifying about address and bandwidth changes for this peer
 542  *
 543  * @param solver the MLP handle
 544  * @param peer the peer
 545  */
 546 void
 547 GAS_mlp_stop_get_preferred_address (void *solver,
 548     const struct GNUNET_PeerIdentity *peer);
 549
 550 /**
 551  * Shutdown the MLP problem solving component
 552  *
 553  * @param solver the solver handle
 554  */
 555 void
 556 GAS_mlp_done (void *solver);
 557
 558 #endif
 559 /* end of plugin_ats_mlp.h */