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      1024
  44
  45 #define DEFAULT_D 1.0
  46 #define DEFAULT_R 1.0
  47 #define DEFAULT_U 1.0
  48 #define DEFAULT_QUALITY 1.0
  49 #define DEFAULT_MIN_CONNECTIONS 4
  50
  51 #define NaN -1
  52
  53 struct ATS_Peer
  54 {
  55   struct ATS_Peer *next;
  56   struct ATS_Peer *prev;
  57
  58   struct GNUNET_PeerIdentity id;
  59
  60   /* Array of quality preferences */
  61   double f_q[GNUNET_ATS_QualityPropertiesCount];
  62   /* Legacy preference value */
  63   double f;
  64
  65   /* constraint 2: 1 address per peer*/
  66   unsigned int r_c2;
  67
  68   /* constraint 9: relativity */
  69   unsigned int r_c9;
  70
  71   struct ATS_Address *head;
  72   struct ATS_Address *tail;
  73 };
  74
  75 struct GAS_MLP_SolutionContext
  76 {
  77   int lp_result;
  78   int mlp_result;
  79   struct GNUNET_TIME_Relative lp_duration;
  80   struct GNUNET_TIME_Relative mlp_duration;
  81 };
  82
  83
  84
  85 struct MLP_Problem
  86 {
  87   /**
  88    * GLPK (MLP) problem object
  89    */
  90 #if HAVE_LIBGLPK
  91   glp_prob *prob;
  92 #else
  93   void *prob;
  94 #endif
  95   /* Number of addresses in problem */
  96   unsigned int num_addresses;
  97   /* Number of peers in problem */
  98   unsigned int num_peers;
  99
 100   /* Row index constraint 2: */
 101   unsigned int r_c2;
 102   /* Row index constraint 4: minimum connections */
 103   unsigned int r_c4;
 104   /* Row index constraint 6: maximize diversity */
 105   unsigned int r_c6;
 106   /* Row index constraint 8: utilization*/
 107   unsigned int r_c8;
 108   /* Row index constraint 9: relativity*/
 109   unsigned int r_c9;
 110   /* Row indices quality metrics  */
 111   int r_q[GNUNET_ATS_QualityPropertiesCount];
 112   /* Row indices ATS network quotas */
 113   int r_quota[GNUNET_ATS_NetworkTypeCount];
 114
 115   /* Column index Diversity (D) column */
 116   int c_d;
 117   /* Column index Utilization (U) column */
 118   int c_u;
 119   /* Column index Proportionality (R) column */
 120   int c_r;
 121   /* Column index quality metrics  */
 122   int c_q[GNUNET_ATS_QualityPropertiesCount];
 123   /* column index ressource costs  */
 124   int c_rc[GNUNET_ATS_QualityPropertiesCount];
 125   /* Column indices ATS network quotas */
 126   int c_quota[GNUNET_ATS_NetworkTypeCount];
 127
 128   /* Problem matrix */
 129   /* Current index */
 130   unsigned int ci;
 131   /* Row index array */
 132   int *ia;
 133   /* Column index array */
 134   int *ja;
 135   /* Column index value */
 136   double *ar;
 137 };
 138
 139 struct MLP_Variables
 140 {
 141         /* Big M value for bandwidth capping */
 142   double BIG_M;
 143
 144   /* ATS Quality metrics
 145    *
 146    * Array with GNUNET_ATS_QualityPropertiesCount elements
 147    * contains mapping to GNUNET_ATS_Property*/
 148   int q[GNUNET_ATS_QualityPropertiesCount];
 149
 150   /* Number of quality metrics */
 151   int m_q;
 152
 153   /* Number of quality metrics */
 154   int m_rc;
 155
 156   /* Quality metric coefficients*/
 157   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 158
 159   /* Ressource costs coefficients*/
 160   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 161
 162   /* Diversity coefficient */
 163   double co_D;
 164
 165   /* Utility coefficient */
 166   double co_U;
 167
 168   /* Relativity coefficient */
 169   double co_R;
 170
 171   /* Minimum bandwidth assigned to an address */
 172   unsigned int b_min;
 173
 174   /* Minimum number of addresses with bandwidth assigned */
 175   unsigned int n_min;
 176
 177   /* Quotas */
 178   /* Array mapping array index to ATS network */
 179   int quota_index [GNUNET_ATS_NetworkTypeCount];
 180   /* Outbound quotas */
 181   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 182   /* Inbound quotas */
 183
 184   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 185
 186   /* ATS ressource costs
 187    * array with GNUNET_ATS_QualityPropertiesCount elements
 188    * contains mapping to GNUNET_ATS_Property
 189    * */
 190   int rc[GNUNET_ATS_QualityPropertiesCount];
 191
 192 };
 193
 194
 195 /**
 196  * MLP Handle
 197  */
 198 struct GAS_MLP_Handle
 199 {
 200   /**
 201    * Statistics handle
 202    */
 203   struct GNUNET_STATISTICS_Handle *stats;
 204
 205   /**
 206    * Addresses' bandwidth changed callback
 207    */
 208   GAS_bandwidth_changed_cb bw_changed_cb;
 209
 210   /**
 211    * Addresses' bandwidth changed callback closure
 212    */
 213   void *bw_changed_cb_cls;
 214
 215   struct MLP_Problem p;
 216
 217   struct MLP_Variables pv;
 218
 219
 220
 221   /**
 222    * GLPK LP control parameter
 223    */
 224 #if HAVE_LIBGLPK
 225   glp_smcp control_param_lp;
 226 #else
 227   void *control_param_lp;
 228 #endif
 229
 230   /**
 231    * GLPK LP control parameter
 232    */
 233 #if HAVE_LIBGLPK
 234   glp_iocp control_param_mlp;
 235 #else
 236   void *control_param_mlp;
 237 #endif
 238
 239   /**
 240    * Peers with pending address requests
 241    */
 242   struct GNUNET_CONTAINER_MultiHashMap *peers;
 243
 244   /**
 245    * Was the problem updated since last solution
 246    */
 247   int mlp_prob_updated;
 248
 249   /**
 250    * Has the problem size changed since last solution
 251    */
 252   int mlp_prob_changed;
 253
 254   /**
 255    * Solves the task in an regular interval
 256    */
 257   GNUNET_SCHEDULER_TaskIdentifier mlp_task;
 258
 259   /**
 260    * Interval between scheduled problem solving
 261    */
 262   struct GNUNET_TIME_Relative exec_interval;
 263
 264   /**
 265    * Maximum execution time per problem solving
 266    */
 267   struct GNUNET_TIME_Relative max_exec_duration;
 268
 269   /**
 270    * Maximum number of LP iterations per problem solving
 271    */
 272   unsigned int max_iterations;
 273
 274   /**
 275    * Solve the problem automatically when updates occur?
 276    * Default: GNUNET_YES
 277    * Can be disabled for test and measurements
 278    */
 279   int auto_solve;
 280
 281   /**
 282    * Is a solution attemp running?
 283    */
 284   int semaphore;
 285
 286   /* state information */
 287
 288   /**
 289    * Do we need to use the LP presolver?
 290    *
 291    * If the problem addresses were added or removed and the last basis was we
 292    * need to use the presolver.
 293    * presolver_required == GNUNET_YES
 294    *
 295    * If values were modified, we can reuse a valid basis
 296    * presolver_required == GNUNET_NO
 297    */
 298   int presolver_required;
 299
 300   /* statistics */
 301
 302   /**
 303    * Time of last execution
 304    */
 305   struct GNUNET_TIME_Absolute last_execution;
 306
 307
 308   /**
 309    * How often was the LP problem solved
 310    */
 311   unsigned int lp_solved;
 312
 313   /**
 314    * total duration of all lp solver executions
 315    */
 316   uint64_t lp_total_duration;
 317
 318   /**
 319    * How often was the MLP problem solved
 320    */
 321   unsigned int mlp_solved;
 322
 323   /**
 324    * total duration of all mlp solver executions
 325    */
 326   uint64_t mlp_total_duration;
 327
 328   /* Information about the problem */
 329
 330   struct ATS_Peer *peer_head;
 331   struct ATS_Peer *peer_tail;
 332 };
 333
 334
 335 /**
 336  * Address specific MLP information
 337  */
 338 struct MLP_information
 339 {
 340   double b;
 341
 342   int n;
 343
 344   /* bandwidth column index */
 345   signed int c_b;
 346
 347   /* address usage column */
 348   signed int c_n;
 349
 350   /* row indexes */
 351
 352   /* constraint 1: bandwidth capping */
 353   unsigned int r_c1;
 354
 355   /* constraint 3: minimum bandwidth */
 356   unsigned int r_c3;
 357
 358   /* Quality information row indices */
 359   unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
 360
 361   /* Quality information */
 362   double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH];
 363
 364   /* Quality information averaged */
 365   double q_averaged[GNUNET_ATS_QualityPropertiesCount];
 366
 367   /* Averaging index */
 368   int q_avg_i[GNUNET_ATS_QualityPropertiesCount];
 369 };
 370
 371 /**
 372  * Solves the MLP problem
 373  *
 374  * @param solver the MLP Handle
 375  * @param addresses the address hashmap
 376  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 377  */
 378 int
 379 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses);
 380
 381
 382 /**
 383  * Init the MLP problem solving component
 384  *
 385  * @param cfg configuration handle
 386  * @param stats the GNUNET_STATISTICS handle
 387  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 388  * @param out_dest array of outbound quotas
 389  * @param in_dest array of outbound quota
 390  * @param dest_length array length for quota arrays
 391  * @param bw_changed_cb callback for changed bandwidth amounts
 392  * @param bw_changed_cb_cls cls for callback
 393  * @return struct GAS_MLP_Handle on success, NULL on fail
 394  */
 395 void *
 396 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 397               const struct GNUNET_STATISTICS_Handle *stats,
 398               int *network,
 399               unsigned long long *out_dest,
 400               unsigned long long *in_dest,
 401               int dest_length,
 402               GAS_bandwidth_changed_cb bw_changed_cb,
 403               void *bw_changed_cb_cls);
 404
 405
 406 /**
 407  * Add a single address to the solve
 408  *
 409  * @param solver the solver Handle
 410  * @param addresses the address hashmap containing all addresses
 411  * @param address the address to add
 412  */
 413 void
 414 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 415
 416 /**
 417  * Updates a single address in the MLP problem
 418  *
 419  * If the address did not exist before in the problem:
 420  * The MLP problem has to be recreated and the problem has to be resolved
 421  *
 422  * Otherwise the addresses' values can be updated and the existing base can
 423  * be reused
 424  *
 425  * @param solver the solver Handle
 426  * @param addresses the address hashmap containing all addresses
 427  * @param address the update address
 428  * @param session the new session (if changed otherwise current)
 429  * @param in_use the new address in use state (if changed otherwise current)
 430  * @param atsi the latest ATS information
 431  * @param atsi_count the atsi count
 432  */
 433 void
 434 GAS_mlp_address_update (void *solver,
 435                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 436                         struct ATS_Address *address,
 437                         uint32_t session,
 438                         int in_use,
 439                         const struct GNUNET_ATS_Information *atsi,
 440                         uint32_t atsi_count);
 441
 442
 443 /**
 444  * Deletes a single address in the MLP problem
 445  *
 446  * The MLP problem has to be recreated and the problem has to be resolved
 447  *
 448  * @param solver the MLP Handle
 449  * @param addresses the address hashmap
 450  *        the address has to be already removed from the hashmap
 451  * @param address the address to delete
 452  * @param session_only delete only session not whole address
 453  */
 454 void
 455 GAS_mlp_address_delete (void *solver,
 456                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 457                         struct ATS_Address *address,
 458                         int session_only);
 459
 460
 461 /**
 462  * Changes the preferences for a peer in the MLP problem
 463  *
 464  * @param solver the MLP Handle
 465  * @param client client
 466  * @param peer the peer
 467  * @param kind the kind to change the preference
 468  * @param score the score
 469  */
 470 void
 471 GAS_mlp_address_change_preference (void *solver,
 472                                    void *client,
 473                                    const struct GNUNET_PeerIdentity *peer,
 474                                    enum GNUNET_ATS_PreferenceKind kind,
 475                                    float score);
 476
 477
 478 /**
 479  * Get the preferred address for a specific peer
 480  *
 481  * @param solver the MLP Handle
 482  * @param addresses address hashmap
 483  * @param peer the peer
 484  * @return suggested address
 485  */
 486 const struct ATS_Address *
 487 GAS_mlp_get_preferred_address (void *solver,
 488                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
 489                                const struct GNUNET_PeerIdentity *peer);
 490
 491 /**
 492  * Shutdown the MLP problem solving component
 493  *
 494  * @param solver the solver handle
 495  */
 496 void
 497 GAS_mlp_done (void *solver);
 498
 499 #endif
 500 /* end of gnunet-service-ats_addresses_mlp.h */