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