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 VERBOSE GNUNET_EXTRA_LOGGING
  38 #define DEBUG_MLP GNUNET_EXTRA_LOGGING
  39
  40 #define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3)
  41 #define MLP_MAX_ITERATIONS      INT_MAX
  42
  43 /**
  44  * MLP Handle
  45  */
  46 struct GAS_MLP_Handle
  47 {
  48   /**
  49    * Statistics handle
  50    */
  51   struct GNUNET_STATISTICS_Handle *stats;
  52
  53   /**
  54    * GLPK (MLP) problem object
  55    */
  56 #if HAVE_LIBGLPK
  57   glp_prob *prob;
  58 #else
  59   void *prob;
  60 #endif
  61
  62   /**
  63    * GLPK LP control parameter
  64    */
  65   glp_smcp control_param_lp;
  66
  67   /**
  68    * GLPK LP control parameter
  69    */
  70   glp_iocp control_param_mlp;
  71
  72   /**
  73    * Solves the task in an regular interval
  74    */
  75   GNUNET_SCHEDULER_TaskIdentifier mlp_task;
  76
  77   /**
  78    * Interval between scheduled problem solving
  79    */
  80   struct GNUNET_TIME_Relative exec_interval;
  81
  82   /**
  83    * Maximum execution time per problem solving
  84    */
  85   struct GNUNET_TIME_Relative max_exec_duration;
  86
  87   /**
  88    * Maximum number of LP iterations per problem solving
  89    */
  90   unsigned int max_iterations;
  91
  92   /* state information */
  93
  94   /**
  95    * Do we need to use the LP presolver?
  96    *
  97    * If the problem addresses were added or removed and the last basis was we
  98    * need to use the presolver.
  99    * presolver_required == GNUNET_YES
 100    *
 101    * If values were modified, we can reuse a valid basis
 102    * presolver_required == GNUNET_NO
 103    */
 104   int presolver_required;
 105
 106   /* statistics */
 107
 108   /**
 109    * Time of last execution
 110    */
 111   struct GNUNET_TIME_Absolute last_execution;
 112
 113
 114   /**
 115    * How often was the LP problem solved
 116    */
 117   unsigned int lp_solved;
 118
 119   /**
 120    * total duration of all lp solver executions
 121    */
 122   uint64_t lp_total_duration;
 123
 124   /**
 125    * How often was the MLP problem solved
 126    */
 127   unsigned int mlp_solved;
 128
 129   /**
 130    * total duration of all mlp solver executions
 131    */
 132   uint64_t mlp_total_duration;
 133
 134   unsigned int addr_in_problem;
 135
 136   /* Information about the problem */
 137
 138   /* current problem matrix */
 139   /* row index array */
 140   int *ia;
 141   /* column index array */
 142   int *ja;
 143   /* column index array */
 144   double *ar;
 145   /* current size of the constraint matrix |indices| */
 146   unsigned int cm_size;
 147   unsigned int ci;
 148
 149   /* Row index constraint 4: minimum connections */
 150   unsigned int r_c4;
 151
 152   /* column index Diversity (D) column */
 153   int c_d;
 154   double co_D;
 155
 156   /* column index Utilization (U) column */
 157   int c_u;
 158   double co_U;
 159
 160   /* column index Proportionality (R) column */
 161   int c_r;
 162   double co_R;
 163
 164   /* ATS Quality metrics
 165    * array with GNUNET_ATS_QualityPropertiesCount elements
 166    * contains mapping to GNUNET_ATS_Property*/
 167   int q[GNUNET_ATS_QualityPropertiesCount];
 168
 169   /* column index quality metrics  */
 170   int c_q[GNUNET_ATS_QualityPropertiesCount];
 171
 172   /* quality metric coefficients*/
 173   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 174
 175   /* number of quality metrics */
 176   int m;
 177
 178   /* minimum bandwidth assigned to an address */
 179   unsigned int b_min;
 180
 181   /* minimum number of addresses with bandwidth assigned */
 182   unsigned int n_min;
 183 };
 184
 185
 186 /**
 187  * Address specific MLP information
 188  */
 189 struct MLP_information
 190 {
 191   /* bandwidth column index */
 192   signed int c_b;
 193
 194   /* address usage column */
 195   signed int c_n;
 196
 197   /* row indexes */
 198
 199   /* constraint 1: bandwidth capping */
 200   unsigned int r_c1;
 201
 202   /* constraint 3: minimum bandwidth */
 203   unsigned int r_c3;
 204 };
 205
 206
 207 /**
 208  * Init the MLP problem solving component
 209  *
 210  * @param cfg configuration handle
 211  * @param stats the GNUNET_STATISTICS handle
 212  * @param max_duration maximum numbers of iterations for the LP/MLP Solver
 213  * @param max_iterations maximum time limit for the LP/MLP Solver
 214  * @return struct GAS_MLP_Handle * on success, NULL on fail
 215  */
 216 struct GAS_MLP_Handle *
 217 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 218               const struct GNUNET_STATISTICS_Handle *stats,
 219               struct GNUNET_TIME_Relative max_duration,
 220               unsigned int max_iterations);
 221
 222
 223 /**
 224  * Updates a single address in the MLP problem
 225  *
 226  * If the address did not exist before in the problem:
 227  * The MLP problem has to be recreated and the problem has to be resolved
 228  *
 229  * Otherwise the addresses' values can be updated and the existing base can
 230  * be reused
 231  *
 232  * @param mlp the MLP Handle
 233  * @param addresses the address hashmap
 234  * @param address the address to update
 235  */
 236 void
 237 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 238
 239
 240 /**
 241  * Deletes a single address in the MLP problem
 242  *
 243  * The MLP problem has to be recreated and the problem has to be resolved
 244  *
 245  * @param mlp the MLP Handle
 246  * @param addresses the address hashmap
 247  * @param address the address to delete
 248  */
 249 void
 250 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 251
 252
 253 /**
 254  * Deletes a single address in the MLP problem
 255  *
 256  * @param mlp the MLP Handle
 257  * @param addresses the address hashmap
 258  * @param address the address to change the preference
 259  */
 260 void
 261 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 262
 263
 264 /**
 265  * Shutdown the MLP problem solving component
 266  */
 267 void
 268 GAS_mlp_done ();
 269
 270 #endif
 271 /* end of gnunet-service-ats_addresses_mlp.h */