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