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