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