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