src/ats/gnunet-service-ats-solver_mlp.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 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/gnunet-service-ats_addresses_mlp.h
  23  * @brief ats MLP problem solver
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_statistics_service.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #if HAVE_LIBGLPK
  31 #include "glpk.h"
  32 #endif
  33
  34 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  35 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
  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 DEFAULT_D 1.0
  46 #define DEFAULT_R 1.0
  47 #define DEFAULT_U 1.0
  48 #define DEFAULT_QUALITY 1.0
  49 #define DEFAULT_MIN_CONNECTIONS 4
  50 #define 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
  58 struct MLP_Solution
  59 {
  60         struct GNUNET_TIME_Relative build_dur;
  61         struct GNUNET_TIME_Relative lp_dur;
  62         struct GNUNET_TIME_Relative mip_dur;
  63
  64         int lp_res;
  65         int lp_presolv;
  66         int mip_res;
  67         int mip_presolv;
  68
  69         int p_elements;
  70         int p_cols;
  71         int p_rows;
  72
  73         int n_peers;
  74         int n_addresses;
  75
  76 };
  77
  78 struct ATS_Peer
  79 {
  80         struct GNUNET_PeerIdentity id;
  81
  82         /* Was this peer already added to the current problem? */
  83         int processed;
  84
  85   /* constraint 2: 1 address per peer*/
  86   unsigned int r_c2;
  87
  88   /* constraint 9: relativity */
  89   unsigned int r_c9;
  90
  91   /* Legacy preference value */
  92   double f;
  93
  94 #if 0
  95   /* Array of quality preferences */
  96   double f_q[GNUNET_ATS_QualityPropertiesCount];
  97
  98 #endif
  99 };
 100
 101
 102
 103 struct MLP_Problem
 104 {
 105   /**
 106    * GLPK (MLP) problem object
 107    */
 108 #if HAVE_LIBGLPK
 109   glp_prob *prob;
 110 #else
 111   void *prob;
 112 #endif
 113   /* Number of addresses in problem */
 114   unsigned int num_addresses;
 115   /* Number of peers in problem */
 116   unsigned int num_peers;
 117   /* Number of elements in problem matrix */
 118   unsigned int num_elements;
 119
 120   /* Row index constraint 2: */
 121   unsigned int r_c2;
 122   /* Row index constraint 4: minimum connections */
 123   unsigned int r_c4;
 124   /* Row index constraint 6: maximize diversity */
 125   unsigned int r_c6;
 126   /* Row index constraint 8: utilization*/
 127   unsigned int r_c8;
 128   /* Row index constraint 9: relativity*/
 129   unsigned int r_c9;
 130   /* Row indices quality metrics  */
 131   int r_q[GNUNET_ATS_QualityPropertiesCount];
 132   /* Row indices ATS network quotas */
 133   int r_quota[GNUNET_ATS_NetworkTypeCount];
 134
 135   /* Column index Diversity (D) column */
 136   int c_d;
 137   /* Column index Utilization (U) column */
 138   int c_u;
 139   /* Column index Proportionality (R) column */
 140   int c_r;
 141   /* Column index quality metrics  */
 142   int c_q[GNUNET_ATS_QualityPropertiesCount];
 143
 144   /* Problem matrix */
 145   /* Current index */
 146   unsigned int ci;
 147   /* Row index array */
 148   int *ia;
 149   /* Column index array */
 150   int *ja;
 151   /* Column index value */
 152   double *ar;
 153 };
 154
 155 struct MLP_Variables
 156 {
 157         /* Big M value for bandwidth capping */
 158   double BIG_M;
 159
 160   /* ATS Quality metrics
 161    *
 162    * Array with GNUNET_ATS_QualityPropertiesCount elements
 163    * contains mapping to GNUNET_ATS_Property*/
 164   int q[GNUNET_ATS_QualityPropertiesCount];
 165
 166   /* Number of quality metrics */
 167   int m_q;
 168
 169   /* Number of quality metrics */
 170   int m_rc;
 171
 172   /* Quality metric coefficients*/
 173   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 174
 175   /* Ressource costs coefficients*/
 176   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 177
 178   /* Diversity coefficient */
 179   double co_D;
 180
 181   /* Utility coefficient */
 182   double co_U;
 183
 184   /* Relativity coefficient */
 185   double co_R;
 186
 187   /* Minimum bandwidth assigned to an address */
 188   unsigned int b_min;
 189
 190   /* Minimum number of addresses with bandwidth assigned */
 191   unsigned int n_min;
 192
 193   /* Quotas */
 194   /* Array mapping array index to ATS network */
 195   int quota_index [GNUNET_ATS_NetworkTypeCount];
 196   /* Outbound quotas */
 197   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 198   /* Inbound quotas */
 199
 200   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 201
 202   /* ATS ressource costs
 203    * array with GNUNET_ATS_QualityPropertiesCount elements
 204    * contains mapping to GNUNET_ATS_Property
 205    * */
 206   int rc[GNUNET_ATS_QualityPropertiesCount];
 207
 208 };
 209
 210
 211 /**
 212  * MLP Handle
 213  */
 214 struct GAS_MLP_Handle
 215 {
 216   /**
 217    * Statistics handle
 218    */
 219   struct GNUNET_STATISTICS_Handle *stats;
 220
 221   /**
 222    * Addresses' bandwidth changed callback
 223    */
 224   GAS_bandwidth_changed_cb bw_changed_cb;
 225
 226   /**
 227    * Addresses' bandwidth changed callback closure
 228    */
 229   void *bw_changed_cb_cls;
 230
 231   GAS_get_preferences get_preferences;
 232
 233   void *get_preferences_cls;
 234
 235   struct MLP_Problem p;
 236
 237   struct MLP_Variables pv;
 238
 239   struct MLP_Solution ps;
 240
 241   /**
 242    * GLPK LP control parameter
 243    */
 244 #if HAVE_LIBGLPK
 245   glp_smcp control_param_lp;
 246 #else
 247   void *control_param_lp;
 248 #endif
 249
 250   /**
 251    * GLPK LP control parameter
 252    */
 253 #if HAVE_LIBGLPK
 254   glp_iocp control_param_mlp;
 255 #else
 256   void *control_param_mlp;
 257 #endif
 258
 259   /**
 260    * Peers with pending address requests
 261    */
 262   struct GNUNET_CONTAINER_MultiHashMap *peers;
 263
 264   /**
 265    * Was the problem updated since last solution
 266    */
 267   int mlp_prob_updated;
 268
 269   /**
 270    * Has the problem size changed since last solution
 271    */
 272   int mlp_prob_changed;
 273
 274   /**
 275    * Solve the problem automatically when updates occur?
 276    * Default: GNUNET_YES
 277    * Can be disabled for test and measurements
 278    */
 279   int mlp_auto_solve;
 280
 281   /**
 282    * Write MILP problem to a MPS file
 283    */
 284   int write_mip_mps;
 285
 286   /**
 287    * Write MILP problem to a MPS file
 288    */
 289   int write_mip_sol;
 290
 291 };
 292
 293
 294 /**
 295  * Address specific MLP information
 296  */
 297 struct MLP_information
 298 {
 299
 300         /* Bandwidth assigned */
 301   struct GNUNET_BANDWIDTH_Value32NBO b_out;
 302   struct GNUNET_BANDWIDTH_Value32NBO b_in;
 303
 304   /* Address selected */
 305   int n;
 306
 307   /* bandwidth column index */
 308   signed int c_b;
 309
 310   /* address usage column */
 311   signed int c_n;
 312
 313   /* row indexes */
 314
 315   /* constraint 1: bandwidth capping */
 316   unsigned int r_c1;
 317
 318   /* constraint 3: minimum bandwidth */
 319   unsigned int r_c3;
 320
 321   /* Quality information row indices */
 322   unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
 323
 324   /* Quality information */
 325   double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH];
 326
 327   /* Quality information averaged */
 328   double q_averaged[GNUNET_ATS_QualityPropertiesCount];
 329
 330   /* Averaging index */
 331   int q_avg_i[GNUNET_ATS_QualityPropertiesCount];
 332 };
 333
 334 /**
 335  * Solves the MLP problem
 336  *
 337  * @param solver the MLP Handle
 338  * @param addresses the address hashmap
 339  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 340  */
 341 int
 342 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses);
 343
 344
 345 /**
 346  * Init the MLP problem solving component
 347  *
 348  * @param cfg configuration handle
 349  * @param stats the GNUNET_STATISTICS handle
 350  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 351  * @param out_dest array of outbound quotas
 352  * @param in_dest array of outbound quota
 353  * @param dest_length array length for quota arrays
 354  * @param bw_changed_cb callback for changed bandwidth amounts
 355  * @param bw_changed_cb_cls cls for callback
 356  * @return struct GAS_MLP_Handle on success, NULL on fail
 357  */
 358 void *
 359 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 360               const struct GNUNET_STATISTICS_Handle *stats,
 361               int *network,
 362               unsigned long long *out_dest,
 363               unsigned long long *in_dest,
 364               int dest_length,
 365               GAS_bandwidth_changed_cb bw_changed_cb,
 366               void *bw_changed_cb_cls,
 367               GAS_get_preferences get_preference,
 368               void *get_preference_cls);
 369
 370
 371 /**
 372  * Add a single address within a network to the solver
 373  *
 374  * @param solver the solver Handle
 375  * @param addresses the address hashmap containing all addresses
 376  * @param address the address to add
 377  * @param network network type of this address
 378  */
 379 void
 380 GAS_mlp_address_add (void *solver,
 381                                                                                 struct GNUNET_CONTAINER_MultiHashMap *addresses,
 382                                                                                 struct ATS_Address *address,
 383                                                                                 uint32_t network);
 384
 385 /**
 386  * Updates a single address in the MLP problem
 387  *
 388  * If the address did not exist before in the problem:
 389  * The MLP problem has to be recreated and the problem has to be resolved
 390  *
 391  * ATS performance information in address are already updated, delta + previous
 392  * values are included in atsi_prev (value GNUNET_ATS_VALUE_UNDEFINED if not existing before)
 393  *
 394  * Otherwise the addresses' values can be updated and the existing base can
 395  * be reused
 396  *
 397  * @param solver the solver Handle
 398  * @param addresses the address hashmap containing all addresses
 399  * @param address the update address
 400  * @param prev_session the new session (if changed otherwise current)
 401  * @param prev_in_use the new address in use state (if changed otherwise current)
 402  * @param prev_atsi ATS information updated + previous values, GNUNET_ATS_VALUE_UNDEFINED if not existing before
 403  * @param prev_atsi_count number of atsi values updated
 404  */
 405 void
 406 GAS_mlp_address_update (void *solver,
 407                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 408                         struct ATS_Address *address,
 409                         uint32_t prev_session,
 410                         int prev_in_use,
 411                         const struct GNUNET_ATS_Information *prev_atsi,
 412                         uint32_t prev_atsi_count);
 413
 414
 415 /**
 416  * Deletes a single address in the MLP problem
 417  *
 418  * The MLP problem has to be recreated and the problem has to be resolved
 419  *
 420  * @param solver the MLP Handle
 421  * @param addresses the address hashmap
 422  *        the address has to be already removed from the hashmap
 423  * @param address the address to delete
 424  * @param session_only delete only session not whole address
 425  */
 426 void
 427 GAS_mlp_address_delete (void *solver,
 428                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 429                         struct ATS_Address *address,
 430                         int session_only);
 431
 432
 433 /**
 434  * Changes the preferences for a peer in the MLP problem
 435  *
 436  * @param solver the MLP Handle
 437  * @param addresses the address hashmap
 438  * @param peer the peer
 439  * @param kind the kind to change the preference
 440  * @param pref_rel the relative score
 441  */
 442 void
 443 GAS_mlp_address_change_preference (void *solver,
 444                                                                    struct GNUNET_CONTAINER_MultiHashMap *addresses,
 445                                                                    const struct GNUNET_PeerIdentity *peer,
 446                                                                    enum GNUNET_ATS_PreferenceKind kind,
 447                                                                    double pref_rel);
 448
 449
 450 /**
 451  * Get the preferred address for a specific peer
 452  *
 453  * @param solver the MLP Handle
 454  * @param addresses address hashmap
 455  * @param peer the peer
 456  * @return suggested address
 457  */
 458 const struct ATS_Address *
 459 GAS_mlp_get_preferred_address (void *solver,
 460                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
 461                                const struct GNUNET_PeerIdentity *peer);
 462
 463
 464 /**
 465  * Stop notifying about address and bandwidth changes for this peer
 466  *
 467  * @param solver the MLP handle
 468  * @param addresses address hashmap
 469  * @param peer the peer
 470  */
 471
 472 void
 473 GAS_mlp_stop_get_preferred_address (void *solver,
 474                                      struct GNUNET_CONTAINER_MultiHashMap *addresses,
 475                                      const struct GNUNET_PeerIdentity *peer);
 476
 477
 478 /**
 479  * Shutdown the MLP problem solving component
 480  *
 481  * @param solver the solver handle
 482  */
 483 void
 484 GAS_mlp_done (void *solver);
 485
 486 #endif
 487 /* end of gnunet-service-ats_addresses_mlp.h */