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