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