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, 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   /* Number of addresses in problem */
 114   unsigned int num_addresses;
 115   /* Number of peers in problem */
 116   unsigned int num_peers;
 117   /* Number of elements in problem matrix */
 118   unsigned int num_elements;
 119
 120   /* Row index constraint 2: */
 121   unsigned int r_c2;
 122   /* Row index constraint 4: minimum connections */
 123   unsigned int r_c4;
 124   /* Row index constraint 6: maximize diversity */
 125   unsigned int r_c6;
 126   /* Row index constraint 8: utilization*/
 127   unsigned int r_c8;
 128   /* Row index constraint 9: relativity*/
 129   unsigned int r_c9;
 130   /* Row indices quality metrics  */
 131   int r_q[GNUNET_ATS_QualityPropertiesCount];
 132   /* Row indices ATS network quotas */
 133   int r_quota[GNUNET_ATS_NetworkTypeCount];
 134
 135   /* Column index Diversity (D) column */
 136   int c_d;
 137   /* Column index Utilization (U) column */
 138   int c_u;
 139   /* Column index Proportionality (R) column */
 140   int c_r;
 141   /* Column index quality metrics  */
 142   int c_q[GNUNET_ATS_QualityPropertiesCount];
 143
 144   /* Problem matrix */
 145   /* Current index */
 146   unsigned int ci;
 147   /* Row index array */
 148   int *ia;
 149   /* Column index array */
 150   int *ja;
 151   /* Column index value */
 152   double *ar;
 153 };
 154
 155 struct MLP_Variables
 156 {
 157         /* Big M value for bandwidth capping */
 158   double BIG_M;
 159
 160   /* ATS Quality metrics
 161    *
 162    * Array with GNUNET_ATS_QualityPropertiesCount elements
 163    * contains mapping to GNUNET_ATS_Property*/
 164   int q[GNUNET_ATS_QualityPropertiesCount];
 165
 166   /* Number of quality metrics */
 167   int m_q;
 168
 169   /* Number of quality metrics */
 170   int m_rc;
 171
 172   /* Quality metric coefficients*/
 173   double co_Q[GNUNET_ATS_QualityPropertiesCount];
 174
 175   /* Ressource costs coefficients*/
 176   double co_RC[GNUNET_ATS_QualityPropertiesCount];
 177
 178   /* Diversity coefficient */
 179   double co_D;
 180
 181   /* Utility coefficient */
 182   double co_U;
 183
 184   /* Relativity coefficient */
 185   double co_R;
 186
 187   /* Minimum bandwidth assigned to an address */
 188   unsigned int b_min;
 189
 190   /* Minimum number of addresses with bandwidth assigned */
 191   unsigned int n_min;
 192
 193   /* Quotas */
 194   /* Array mapping array index to ATS network */
 195   int quota_index [GNUNET_ATS_NetworkTypeCount];
 196   /* Outbound quotas */
 197   unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
 198   /* Inbound quotas */
 199
 200   unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
 201
 202   /* ATS ressource costs
 203    * array with GNUNET_ATS_QualityPropertiesCount elements
 204    * contains mapping to GNUNET_ATS_Property
 205    * */
 206   int rc[GNUNET_ATS_QualityPropertiesCount];
 207
 208 };
 209
 210
 211 /**
 212  * MLP Handle
 213  */
 214 struct GAS_MLP_Handle
 215 {
 216   /**
 217    * Statistics handle
 218    */
 219   struct GNUNET_STATISTICS_Handle *stats;
 220
 221   /**
 222    * Addresses' bandwidth changed callback
 223    */
 224   GAS_bandwidth_changed_cb bw_changed_cb;
 225
 226   /**
 227    * Addresses' bandwidth changed callback closure
 228    */
 229   void *bw_changed_cb_cls;
 230
 231   struct MLP_Problem p;
 232
 233   struct MLP_Variables pv;
 234
 235   struct MLP_Solution ps;
 236
 237   /**
 238    * GLPK LP control parameter
 239    */
 240 #if HAVE_LIBGLPK
 241   glp_smcp control_param_lp;
 242 #else
 243   void *control_param_lp;
 244 #endif
 245
 246   /**
 247    * GLPK LP control parameter
 248    */
 249 #if HAVE_LIBGLPK
 250   glp_iocp control_param_mlp;
 251 #else
 252   void *control_param_mlp;
 253 #endif
 254
 255   /**
 256    * Peers with pending address requests
 257    */
 258   struct GNUNET_CONTAINER_MultiHashMap *peers;
 259
 260   /**
 261    * Was the problem updated since last solution
 262    */
 263   int mlp_prob_updated;
 264
 265   /**
 266    * Has the problem size changed since last solution
 267    */
 268   int mlp_prob_changed;
 269
 270   /**
 271    * Solve the problem automatically when updates occur?
 272    * Default: GNUNET_YES
 273    * Can be disabled for test and measurements
 274    */
 275   int mlp_auto_solve;
 276
 277   /**
 278    * Write MILP problem to a MPS file
 279    */
 280   int write_mip_mps;
 281
 282   /**
 283    * Write MILP problem to a MPS file
 284    */
 285   int write_mip_sol;
 286
 287 };
 288
 289
 290 /**
 291  * Address specific MLP information
 292  */
 293 struct MLP_information
 294 {
 295
 296         /* Bandwidth assigned */
 297   struct GNUNET_BANDWIDTH_Value32NBO b_out;
 298   struct GNUNET_BANDWIDTH_Value32NBO b_in;
 299
 300   /* Address selected */
 301   int n;
 302
 303   /* bandwidth column index */
 304   signed int c_b;
 305
 306   /* address usage column */
 307   signed int c_n;
 308
 309   /* row indexes */
 310
 311   /* constraint 1: bandwidth capping */
 312   unsigned int r_c1;
 313
 314   /* constraint 3: minimum bandwidth */
 315   unsigned int r_c3;
 316
 317   /* Quality information row indices */
 318   unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
 319
 320   /* Quality information */
 321   double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH];
 322
 323   /* Quality information averaged */
 324   double q_averaged[GNUNET_ATS_QualityPropertiesCount];
 325
 326   /* Averaging index */
 327   int q_avg_i[GNUNET_ATS_QualityPropertiesCount];
 328 };
 329
 330 /**
 331  * Solves the MLP problem
 332  *
 333  * @param solver the MLP Handle
 334  * @param addresses the address hashmap
 335  * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
 336  */
 337 int
 338 GAS_mlp_solve_problem (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses);
 339
 340
 341 /**
 342  * Init the MLP problem solving component
 343  *
 344  * @param cfg configuration handle
 345  * @param stats the GNUNET_STATISTICS handle
 346  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 347  * @param out_dest array of outbound quotas
 348  * @param in_dest array of outbound quota
 349  * @param dest_length array length for quota arrays
 350  * @param bw_changed_cb callback for changed bandwidth amounts
 351  * @param bw_changed_cb_cls cls for callback
 352  * @return struct GAS_MLP_Handle on success, NULL on fail
 353  */
 354 void *
 355 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 356               const struct GNUNET_STATISTICS_Handle *stats,
 357               int *network,
 358               unsigned long long *out_dest,
 359               unsigned long long *in_dest,
 360               int dest_length,
 361               GAS_bandwidth_changed_cb bw_changed_cb,
 362               void *bw_changed_cb_cls);
 363
 364
 365 /**
 366  * Add a single address to the solve
 367  *
 368  * @param solver the solver Handle
 369  * @param addresses the address hashmap containing all addresses
 370  * @param address the address to add
 371  */
 372 void
 373 GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
 374
 375 /**
 376  * Updates a single address in the MLP problem
 377  *
 378  * If the address did not exist before in the problem:
 379  * The MLP problem has to be recreated and the problem has to be resolved
 380  *
 381  * Otherwise the addresses' values can be updated and the existing base can
 382  * be reused
 383  *
 384  * @param solver the solver Handle
 385  * @param addresses the address hashmap containing all addresses
 386  * @param address the update address
 387  * @param session the new session (if changed otherwise current)
 388  * @param in_use the new address in use state (if changed otherwise current)
 389  * @param atsi the latest ATS information
 390  * @param atsi_count the atsi count
 391  */
 392 void
 393 GAS_mlp_address_update (void *solver,
 394                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 395                         struct ATS_Address *address,
 396                         uint32_t session,
 397                         int in_use,
 398                         const struct GNUNET_ATS_Information *atsi,
 399                         uint32_t atsi_count);
 400
 401
 402 /**
 403  * Deletes a single address in the MLP problem
 404  *
 405  * The MLP problem has to be recreated and the problem has to be resolved
 406  *
 407  * @param solver the MLP Handle
 408  * @param addresses the address hashmap
 409  *        the address has to be already removed from the hashmap
 410  * @param address the address to delete
 411  * @param session_only delete only session not whole address
 412  */
 413 void
 414 GAS_mlp_address_delete (void *solver,
 415                         struct GNUNET_CONTAINER_MultiHashMap *addresses,
 416                         struct ATS_Address *address,
 417                         int session_only);
 418
 419
 420 /**
 421  * Changes the preferences for a peer in the MLP problem
 422  *
 423  * @param solver the MLP Handle
 424  * @param client client
 425  * @param peer the peer
 426  * @param kind the kind to change the preference
 427  * @param score the score
 428  */
 429 void
 430 GAS_mlp_address_change_preference (void *solver,
 431                                    void *client,
 432                                    const struct GNUNET_PeerIdentity *peer,
 433                                    enum GNUNET_ATS_PreferenceKind kind,
 434                                    float score);
 435
 436
 437 /**
 438  * Get the preferred address for a specific peer
 439  *
 440  * @param solver the MLP Handle
 441  * @param addresses address hashmap
 442  * @param peer the peer
 443  * @return suggested address
 444  */
 445 const struct ATS_Address *
 446 GAS_mlp_get_preferred_address (void *solver,
 447                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
 448                                const struct GNUNET_PeerIdentity *peer);
 449
 450
 451 /**
 452  * Stop notifying about address and bandwidth changes for this peer
 453  *
 454  * @param solver the MLP handle
 455  * @param addresses address hashmap
 456  * @param peer the peer
 457  */
 458
 459 void
 460 GAS_mlp_stop_get_preferred_address (void *solver,
 461                                      struct GNUNET_CONTAINER_MultiHashMap *addresses,
 462                                      const struct GNUNET_PeerIdentity *peer);
 463
 464
 465 /**
 466  * Shutdown the MLP problem solving component
 467  *
 468  * @param solver the solver handle
 469  */
 470 void
 471 GAS_mlp_done (void *solver);
 472
 473 #endif
 474 /* end of gnunet-service-ats_addresses_mlp.h */