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 callback to get relative preferences for a peer
 375  * @param get_properties_cls for callback to get relative properties
 376  * @param get_properties_cls cls for callback to get relative properties
 377  * @return struct GAS_MLP_Handle on success, NULL on fail
 378  */
 379 void *
 380 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 381               const struct GNUNET_STATISTICS_Handle *stats,
 382               const struct GNUNET_CONTAINER_MultiHashMap *addresses,
 383               int *network,
 384               unsigned long long *out_dest,
 385               unsigned long long *in_dest,
 386               int dest_length,
 387               GAS_bandwidth_changed_cb bw_changed_cb,
 388               void *bw_changed_cb_cls,
 389               GAS_get_preferences get_preference,
 390               void *get_preference_cls,
 391               GAS_get_properties get_properties,
 392               void *get_properties_cls);
 393
 394
 395 /**
 396  * Add a single address within a network to the solver
 397  *
 398  * @param solver the solver Handle
 399  * @param address the address to add
 400  * @param network network type of this address
 401  */
 402 void
 403 GAS_mlp_address_add (void *solver,
 404                                                                                 struct ATS_Address *address,
 405                                                                                 uint32_t network);
 406
 407
 408 /**
 409  * Transport properties for this address have changed
 410  *
 411  * @param solver solver handle
 412  * @param address the address
 413  * @param type the ATSI type in HBO
 414  * @param abs_value the absolute value of the property
 415  * @param rel_value the normalized value
 416  */
 417 void
 418 GAS_mlp_address_property_changed (void *solver,
 419                                                                                                                         struct ATS_Address *address,
 420                                                                                                                         uint32_t type,
 421                                                                                                                         uint32_t abs_value,
 422                                                                                                                         double rel_value);
 423
 424
 425 /**
 426  * Transport session for this address has changed
 427  *
 428  * NOTE: values in addresses are already updated
 429  *
 430  * @param solver solver handle
 431  * @param address the address
 432  * @param cur_session the current session
 433  * @param new_session the new session
 434  */
 435 void
 436 GAS_mlp_address_session_changed (void *solver,
 437                                                                                                                  struct ATS_Address *address,
 438                                                                                                                  uint32_t cur_session,
 439                                                                                                                  uint32_t new_session);
 440
 441
 442 /**
 443  * Usage for this address has changed
 444  *
 445  * NOTE: values in addresses are already updated
 446  *
 447  * @param solver solver handle
 448  * @param address the address
 449  * @param in_use usage state
 450  */
 451 void
 452 GAS_mlp_address_inuse_changed (void *solver,
 453                                                                                                          struct ATS_Address *address,
 454                                                                                                          int in_use);
 455
 456
 457 /**
 458  * Network scope for this address has changed
 459  *
 460  * NOTE: values in addresses are already updated
 461  *
 462  * @param solver solver handle
 463  * @param address the address
 464  * @param current_network the current network
 465  * @param new_network the new network
 466  */
 467 void
 468 GAS_mlp_address_change_network (void *solver,
 469                                                                                                                          struct ATS_Address *address,
 470                                                                                                                          uint32_t current_network,
 471                                                                                                                          uint32_t new_network);
 472
 473 /**
 474  * Deletes a single address in the MLP problem
 475  *
 476  * The MLP problem has to be recreated and the problem has to be resolved
 477  *
 478  * @param solver the MLP Handle
 479  * @param address the address to delete
 480  * @param session_only delete only session not whole address
 481  */
 482 void
 483 GAS_mlp_address_delete (void *solver,
 484                         struct ATS_Address *address,
 485                         int session_only);
 486
 487
 488 /**
 489  * Changes the preferences for a peer in the MLP problem
 490  *
 491  * @param solver the MLP Handle
 492  * @param peer the peer
 493  * @param kind the kind to change the preference
 494  * @param pref_rel the relative score
 495  */
 496 void
 497 GAS_mlp_address_change_preference (void *solver,
 498                                                                    const struct GNUNET_PeerIdentity *peer,
 499                                                                    enum GNUNET_ATS_PreferenceKind kind,
 500                                                                    double pref_rel);
 501
 502
 503 /**
 504  * Get application feedback for a peer
 505  *
 506  * @param solver the solver handle
 507  * @param application the application
 508  * @param peer the peer to change the preference for
 509  * @param scope the time interval for this feedback: [now - scope .. now]
 510  * @param kind the kind to change the preference
 511  * @param score the score
 512  */
 513 void
 514 GAS_mlp_address_preference_feedback (void *solver,
 515                                                                                         void *application,
 516                                                                                         const struct GNUNET_PeerIdentity *peer,
 517                                                                                         const struct GNUNET_TIME_Relative scope,
 518                                                                                         enum GNUNET_ATS_PreferenceKind kind,
 519                                                                                         double score);
 520
 521
 522
 523 /**
 524  * Start a bulk operation
 525  *
 526  * @param solver the solver
 527  */
 528 void
 529 GAS_mlp_bulk_start (void *solver);
 530
 531
 532 /**
 533  * Bulk operation done
 534  */
 535 void
 536 GAS_mlp_bulk_stop (void *solver);
 537
 538
 539 /**
 540  * Get the preferred address for a specific peer until
 541  * GAS_mlp_stop_get_preferred_address is called
 542  *
 543  * @param solver the MLP Handle
 544  * @param peer the peer
 545  * @return suggested address
 546  */
 547 const struct ATS_Address *
 548 GAS_mlp_get_preferred_address (void *solver,
 549                                const struct GNUNET_PeerIdentity *peer);
 550
 551
 552 /**
 553  * Stop notifying about address and bandwidth changes for this peer
 554  *
 555  * @param solver the MLP handle
 556  * @param peer the peer
 557  */
 558 void
 559 GAS_mlp_stop_get_preferred_address (void *solver,
 560                                      const struct GNUNET_PeerIdentity *peer);
 561
 562
 563 /**
 564  * Shutdown the MLP problem solving component
 565  *
 566  * @param solver the solver handle
 567  */
 568 void
 569 GAS_mlp_done (void *solver);
 570
 571 #endif
 572 /* end of gnunet-service-ats_addresses_mlp.h */