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