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