src/ats/gnunet-service-ats_addresses_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, 3)
  43 #define MLP_MAX_ITERATIONS      1024
  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
  51 #define NaN -1
  52
  53 struct ATS_Peer
  54 {
  55   struct ATS_Peer *next;
  56   struct ATS_Peer *prev;
  57
  58   struct GNUNET_PeerIdentity id;
  59
  60   /* Array of quality preferences */
  61   double f_q[GNUNET_ATS_QualityPropertiesCount];
  62   /* Legacy preference value */
  63   double f;
  64
  65   /* constraint 2: 1 address per peer*/
  66   unsigned int r_c2;
  67
  68   /* constraint 9: relativity */
  69   unsigned int r_c9;
  70
  71   struct ATS_Address *head;
  72   struct ATS_Address *tail;
  73 };
  74
  75 struct GAS_MLP_SolutionContext
  76 {
  77   int lp_result;
  78   int mlp_result;
  79   struct GNUNET_TIME_Relative lp_duration;
  80   struct GNUNET_TIME_Relative mlp_duration;
  81 };
  82
  83 /**
  84  * MLP Handle
  85  */
  86 struct GAS_MLP_Handle
  87 {
  88   /**
  89    * Statistics handle
  90    */
  91   struct GNUNET_STATISTICS_Handle *stats;
  92
  93   /**
  94    * Addresses' bandwidth changed callback
  95    */
  96   GAS_bandwidth_changed_cb bw_changed_cb;
  97
  98   /**
  99    * Addresses' bandwidth changed callback closure
 100    */
 101   void *bw_changed_cb_cls;
 102
 103   /**
 104    * GLPK (MLP) problem object
 105    */
 106 #if HAVE_LIBGLPK
 107   glp_prob *prob;
 108 #else
 109   void *prob;
 110 #endif
 111
 112   double BIG_M;
 113
 114   /**
 115    * GLPK LP control parameter
 116    */
 117 #if HAVE_LIBGLPK
 118   glp_smcp control_param_lp;
 119 #else
 120   void *control_param_lp;
 121 #endif
 122
 123   /**
 124    * GLPK LP control parameter
 125    */
 126 #if HAVE_LIBGLPK
 127   glp_iocp control_param_mlp;
 128 #else
 129   void *control_param_mlp;
 130 #endif
 131
 132   /**
 133    * Solves the task in an regular interval
 134    */
 135   GNUNET_SCHEDULER_TaskIdentifier mlp_task;
 136
 137   /**
 138    * Interval between scheduled problem solving
 139    */
 140   struct GNUNET_TIME_Relative exec_interval;
 141
 142   /**
 143    * Maximum execution time per problem solving
 144    */
 145   struct GNUNET_TIME_Relative max_exec_duration;
 146
 147   /**
 148    * Maximum number of LP iterations per problem solving
 149    */
 150   unsigned int max_iterations;
 151
 152   /**
 153    * Solve the problem automatically when updates occur?
 154    * Default: GNUNET_YES
 155    * Can be disabled for test and measurements
 156    */
 157   int auto_solve;
 158
 159   /**
 160    * Is a solution attemp running?
 161    */
 162   int semaphore;
 163
 164   /* state information */
 165
 166   /**
 167    * Do we need to use the LP presolver?
 168    *
 169    * If the problem addresses were added or removed and the last basis was we
 170    * need to use the presolver.
 171    * presolver_required == GNUNET_YES
 172    *
 173    * If values were modified, we can reuse a valid basis
 174    * presolver_required == GNUNET_NO
 175    */
 176   int presolver_required;
 177
 178   /* statistics */
 179
 180   /**
 181    * Time of last execution
 182    */
 183   struct GNUNET_TIME_Absolute last_execution;
 184
 185
 186   /**
 187    * How often was the LP problem solved
 188    */
 189   unsigned int lp_solved;
 190
 191   /**
 192    * total duration of all lp solver executions
 193    */
 194   uint64_t lp_total_duration;
 195
 196   /**
 197    * How often was the MLP problem solved
 198    */
 199   unsigned int mlp_solved;
 200
 201   /**
 202    * total duration of all mlp solver executions
 203    */
 204   uint64_t mlp_total_duration;
 205
 206   unsigned int addr_in_problem;
 207
 208   /* Information about the problem */
 209
 210   struct ATS_Peer *peer_head;
 211   struct ATS_Peer *peer_tail;
 212
 213   /* Number of peers */
 214   unsigned int c_p;
 215
 216   /* current problem matrix */
 217   /* row index array */
 218   int *ia;
 219   /* column index array */
 220   int *ja;
 221   /* column index array */
 222   double *ar;
 223   /* current size of the constraint matrix |indices| */
 224   unsigned int cm_size;
 225   unsigned int ci;
 226
 227   /* Row index constraint 2: */
 228   unsigned int r_c2;
 229   /* Row index constraint 4: minimum connections */
 230   unsigned int r_c4;
 231   /* Row index constraint 6: maximize diversity */
 232   unsigned int r_c6;
 233   /* Row index constraint 8: utilization*/
 234   unsigned int r_c8;
 235   /* Row index constraint 9: relativity*/
 236   unsigned int r_c9;
 237
 238   /* column index Diversity (D) column */
 239   int c_d;
 240   double co_D;
 241
 242   /* column index Utilization (U) column */
 243   int c_u;
 244   double co_U;
 245
 246   /* column index Proportionality (R) column */
 247   int c_r;
 248   double co_R;
 249
 250   /* ATS Quality metrics
 251    *
 252    * array with GNUNET_ATS_QualityPropertiesCount elements
 253    * contains mapping to GNUNET_ATS_Property*/
 254   int q[GNUNET_ATS_QualityPropertiesCount];
 255
 256   /* column index quality metrics  */
 257   int c_q[GNUNET_ATS_QualityPropertiesCount];
 258
 259   /* column index quality metrics  */
 260   int r_q[GNUNET_ATS_QualityPropertiesCount];
 261
 262   /* quality metric coefficients*/
 263   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 264
 265   /* number of quality metrics */
 266   int m_q;
 267
 268   /* ATS network quotas */
 269   int c_quota[GNUNET_ATS_NetworkTypeCount];
 270   int r_quota[GNUNET_ATS_NetworkTypeCount];
 271   int quota_index [GNUNET_ATS_NetworkTypeCount];
 272   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 273   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 274
 275   /* ATS ressource costs
 276    *
 277    * array with GNUNET_ATS_QualityPropertiesCount elements
 278    * contains mapping to GNUNET_ATS_Property*/
 279   int rc[GNUNET_ATS_QualityPropertiesCount];
 280
 281   /* column index ressource costs  */
 282   int c_rc[GNUNET_ATS_QualityPropertiesCount];
 283
 284   /* ressource costs coefficients*/
 285   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 286
 287   /* number of quality metrics */
 288   int m_rc;
 289
 290   /* minimum bandwidth assigned to an address */
 291   unsigned int b_min;
 292
 293   /* minimum number of addresses with bandwidth assigned */
 294   unsigned int n_min;
 295 };
 296
 297
 298 /**
 299  * Address specific MLP information
 300  */
 301 struct MLP_information
 302 {
 303   double b;
 304
 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 /**
 336  * Init the MLP problem solving component
 337  *
 338  * @param cfg configuration handle
 339  * @param stats the GNUNET_STATISTICS handle
 340  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 341  * @param out_dest array of outbound quotas
 342  * @param in_dest array of outbound quota
 343  * @param dest_length array length for quota arrays
 344  * @param bw_changed_cb callback for changed bandwidth amounts
 345  * @param bw_changed_cb_cls cls for callback
 346  * @return struct GAS_MLP_Handle on success, NULL on fail
 347  */
 348 void *
 349 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 350               const struct GNUNET_STATISTICS_Handle *stats,
 351               int *network,
 352               unsigned long long *out_dest,
 353               unsigned long long *in_dest,
 354               int dest_length,
 355               GAS_bandwidth_changed_cb bw_changed_cb,
 356               void *bw_changed_cb_cls);
 357
 358
 359 /**
 360  * Add a single address to the solve
 361  *
 362  * @param solver the solver Handle
 363  * @param addresses the address hashmap containing all addresses
 364  * @param address the address to add
 365  */
 366 void
 367 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 368
 369 /**
 370  * Updates a single address in the MLP problem
 371  *
 372  * If the address did not exist before in the problem:
 373  * The MLP problem has to be recreated and the problem has to be resolved
 374  *
 375  * Otherwise the addresses' values can be updated and the existing base can
 376  * be reused
 377  *
 378  * @param solver the solver Handle
 379  * @param addresses the address hashmap containing all addresses
 380  * @param address the update address
 381  * @param session the new session (if changed otherwise current)
 382  * @param in_use the new address in use state (if changed otherwise current)
 383  * @param atsi the latest ATS information
 384  * @param atsi_count the atsi count
 385  */
 386 void
 387 GAS_mlp_address_update (void *solver,
 388                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 389                         struct ATS_Address *address,
 390                         uint32_t session,
 391                         int in_use,
 392                         const struct GNUNET_ATS_Information *atsi,
 393                         uint32_t atsi_count);
 394
 395
 396 /**
 397  * Deletes a single address in the MLP problem
 398  *
 399  * The MLP problem has to be recreated and the problem has to be resolved
 400  *
 401  * @param solver the MLP Handle
 402  * @param addresses the address hashmap
 403  *        the address has to be already removed from the hashmap
 404  * @param address the address to delete
 405  * @param session_only delete only session not whole address
 406  */
 407 void
 408 GAS_mlp_address_delete (void *solver,
 409                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 410                         struct ATS_Address *address,
 411                         int session_only);
 412
 413
 414 /**
 415  * Changes the preferences for a peer in the MLP problem
 416  *
 417  * @param solver the MLP Handle
 418  * @param client client
 419  * @param peer the peer
 420  * @param kind the kind to change the preference
 421  * @param score the score
 422  */
 423 void
 424 GAS_mlp_address_change_preference (void *solver,
 425                                    void *client,
 426                                    const struct GNUNET_PeerIdentity *peer,
 427                                    enum GNUNET_ATS_PreferenceKind kind,
 428                                    float score);
 429
 430
 431 /**
 432  * Get the preferred address for a specific peer
 433  *
 434  * @param solver the MLP Handle
 435  * @param addresses address hashmap
 436  * @param peer the peer
 437  * @return suggested address
 438  */
 439 const struct ATS_Address *
 440 GAS_mlp_get_preferred_address (void *solver,
 441                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
 442                                const struct GNUNET_PeerIdentity *peer);
 443
 444 /**
 445  * Shutdown the MLP problem solving component
 446  *
 447  * @param solver the solver handle
 448  */
 449 void
 450 GAS_mlp_done (void *solver);
 451
 452 #endif
 453 /* end of gnunet-service-ats_addresses_mlp.h */