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