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