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