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