src/transport/gnunet-service-transport_ats.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2010,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 transport/gnunet-service-transport_ats.h
  23  * @brief common internal definitions for transport service's ats code
  24  * @author Matthias Wachs
  25  */
  26 #ifndef GNUNET_SERVICE_TRANSPORT_ATS_H
  27 #define GNUNET_SERVICE_TRANSPORT_ATS_H
  28
  29 #include "platform.h"
  30 #include "gnunet_constants.h"
  31 #include "gnunet_scheduler_lib.h"
  32 #include "gnunet_statistics_service.h"
  33 #include "gnunet_time_lib.h"
  34
  35
  36 #if HAVE_LIBGLPK
  37 #include <glpk.h>
  38 #endif
  39
  40 /*
  41  *  ATS defines
  42  */
  43
  44 #define DEBUG_ATS GNUNET_NO
  45 #define VERBOSE_ATS GNUNET_NO
  46
  47
  48 /* Minimum time between to calculations*/
  49 #define ATS_MIN_INTERVAL  GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 15)
  50 #define ATS_EXEC_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
  51 #define ATS_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3)
  52 #define ATS_MAX_ITERATIONS INT_MAX
  53
  54 #define ATS_DEFAULT_D 1.0
  55 #define ATS_DEFAULT_U 1.0
  56 #define ATS_DEFAULT_R 1.0
  57 #define ATS_DEFAULT_B_MIN 64000
  58 #define ATS_DEFAULT_N_MIN 10
  59
  60 #define VERY_BIG_DOUBLE_VALUE 100000000000LL
  61
  62
  63 /*
  64  * Callback Functions
  65  */
  66
  67 struct ATS_mechanism;
  68 struct ATS_peer;
  69
  70 typedef void (*GNUNET_TRANSPORT_ATS_AddressNotification)
  71     (struct ATS_peer ** peers,
  72      int *c_p, struct ATS_mechanism ** mechanisms, int *c_m);
  73
  74 typedef void (*GNUNET_TRANSPORT_ATS_ResultCallback) (void);
  75
  76 enum ATS_problem_state
  77 {
  78   /**
  79    * Problem is new
  80    */
  81   ATS_NEW = 0,
  82
  83   /**
  84    * Problem quality properties were modified
  85    */
  86   ATS_QUALITY_UPDATED = 1,
  87
  88   /**
  89    * Problem ressource properties were modified
  90    */
  91   ATS_COST_UPDATED = 2,
  92
  93   /**
  94    * Problem quality and ressource properties were modified
  95    */
  96   ATS_QUALITY_COST_UPDATED = 3,
  97
  98   /**
  99    * Problem is modified and needs to be completely recalculated
 100    * due to e.g. connecting or disconnecting peers
 101    */
 102   ATS_MODIFIED = 4,
 103
 104   /**
 105    * Problem is unmodified
 106    */
 107   ATS_UNMODIFIED = 8
 108 };
 109
 110 /*
 111 *  ATS data structures
 112 */
 113
 114 struct ATS_internals
 115 {
 116     /**
 117      * result of last GLPK run
 118      * 5 == OPTIMAL
 119      */
 120   int solution;
 121
 122     /**
 123      * Ressource costs or quality metrics changed
 124      * update problem before solving
 125      */
 126   int modified_resources;
 127
 128     /**
 129      * Ressource costs or quality metrics changed, update matrix
 130      * update problem before solving
 131      */
 132   int modified_quality;
 133
 134     /**
 135      * Peers have connected or disconnected
 136      * problem has to be recreated
 137      */
 138   int recreate_problem;
 139
 140     /**
 141      * Was the available basis invalid and we needed to rerun simplex?
 142      */
 143   int simplex_rerun_required;
 144
 145     /**
 146      * is problem currently valid and can it be solved
 147      */
 148   int valid;
 149
 150     /**
 151      * Number of transport mechanisms in the problem
 152      */
 153   int c_mechs;
 154
 155     /**
 156      * Number of transport mechanisms in the problem
 157      */
 158   int c_peers;
 159
 160     /**
 161      * row index where quality related rows start
 162      */
 163   int begin_qm;
 164
 165     /**
 166      * row index where quality related rows end
 167      */
 168   int end_qm;
 169
 170     /**
 171      * row index where ressource cost related rows start
 172      */
 173   int begin_cr;
 174
 175     /**
 176      * row index where ressource cost related rows end
 177      */
 178   int end_cr;
 179
 180     /**
 181      * column index for objective function value d
 182      */
 183   int col_d;
 184
 185     /**
 186      * column index for objective function value u
 187      */
 188   int col_u;
 189
 190     /**
 191      * column index for objective function value r
 192      */
 193   int col_r;
 194
 195     /**
 196      * column index for objective function value quality metrics
 197      */
 198   int col_qm;
 199
 200     /**
 201      * column index for objective function value cost ressources
 202      */
 203   int col_cr;
 204 };
 205
 206 struct ATS_Handle
 207 {
 208   /*
 209    *  Callback functions
 210    */
 211
 212   GNUNET_TRANSPORT_ATS_AddressNotification addr_notification;
 213
 214   GNUNET_TRANSPORT_ATS_ResultCallback result_cb;
 215
 216
 217     /**
 218      * Statistics handle
 219      */
 220   struct GNUNET_STATISTICS_Handle *stats;
 221
 222     /**
 223      * Maximum execution time per calculation
 224      */
 225   struct GNUNET_TIME_Relative max_exec_duration;
 226
 227     /**
 228      * GLPK (MLP) problem object
 229      */
 230 #if HAVE_LIBGLPK
 231
 232   glp_prob *prob;
 233 #else
 234   void *prob;
 235 #endif
 236
 237     /**
 238      * Internal information state of the GLPK problem
 239      */
 240   struct ATS_internals internal;
 241
 242     /**
 243      * mechanisms used in current problem
 244      * needed for problem modification
 245      */
 246   struct ATS_mechanism *mechanisms;
 247
 248     /**
 249      * peers used in current problem
 250      * needed for problem modification
 251      */
 252   struct ATS_peer *peers;
 253
 254     /**
 255      * State of the MLP problem
 256      * value of ATS_problem_state
 257      *
 258      */
 259   int state;
 260
 261     /**
 262      * number of successful executions
 263      */
 264   int successful_executions;
 265
 266     /**
 267      * number with an invalid result
 268      */
 269   int invalid_executions;
 270
 271     /**
 272      * Maximum number of LP iterations per calculation
 273      */
 274   int max_iterations;
 275
 276
 277   /*
 278    * ATS configuration
 279    */
 280
 281
 282     /**
 283      * Diversity weight
 284      */
 285   double D;
 286
 287     /**
 288      * Utility weight
 289      */
 290   double U;
 291
 292     /**
 293      * Relativity weight
 294      */
 295   double R;
 296
 297     /**
 298      * Minimum bandwidth per peer
 299      */
 300   int v_b_min;
 301
 302     /**
 303      * Minimum number of connections per peer
 304      */
 305   int v_n_min;
 306
 307
 308     /**
 309      * Logging related variables
 310      */
 311
 312
 313     /**
 314      * Dump problem to a file?
 315      */
 316   int save_mlp;
 317
 318     /**
 319      * Dump solution to a file
 320      */
 321   int save_solution;
 322
 323     /**
 324      * Dump solution when minimum peers:
 325      */
 326   int dump_min_peers;
 327
 328     /**
 329      * Dump solution when minimum addresses:
 330      */
 331   int dump_min_addr;
 332
 333     /**
 334      * Dump solution overwrite file:
 335      */
 336   int dump_overwrite;
 337 };
 338
 339 struct ATS_mechanism
 340 {
 341   struct ATS_mechanism *prev;
 342   struct ATS_mechanism *next;
 343   struct ForeignAddressList *addr;
 344   struct ATS_quality_entry *quality;
 345   struct ATS_ressource_entry *ressources;
 346   struct TransportPlugin *plugin;
 347   struct ATS_peer *peer;
 348   int col_index;
 349   int id;
 350   struct ATS_ressource_cost *rc;
 351 };
 352
 353 struct ATS_peer
 354 {
 355   struct GNUNET_PeerIdentity peer;
 356
 357   struct ATS_mechanism *m_head;
 358   struct ATS_mechanism *m_tail;
 359
 360   /* preference value f */
 361   double f;
 362
 363   //struct NeighbourList * n;
 364 };
 365
 366 struct ATS_ressource
 367 {
 368   /* index in ressources array */
 369   int index;
 370   /* depending ATSi parameter to calculcate limits */
 371   int atis_index;
 372   /* cfg option to load limits */
 373   char *cfg_param;
 374   /* lower bound */
 375   double c_min;
 376   /* upper bound */
 377   double c_max;
 378
 379   /* cofficients for the specific plugins */
 380   double c_unix;
 381   double c_tcp;
 382   double c_udp;
 383   double c_http;
 384   double c_https;
 385   double c_wlan;
 386   double c_default;
 387 };
 388
 389
 390 struct ATS_ressource_entry
 391 {
 392   /* index in ressources array */
 393   int index;
 394   /* depending ATSi parameter to calculcate limits */
 395   int atis_index;
 396   /* lower bound */
 397   double c;
 398 };
 399
 400
 401 struct ATS_quality_metric
 402 {
 403   int index;
 404   int atis_index;
 405   char *name;
 406 };
 407
 408 struct ATS_quality_entry
 409 {
 410   int index;
 411   int atsi_index;
 412   uint32_t values[3];
 413   int current;
 414 };
 415
 416 /*
 417  * ATS ressources
 418  */
 419
 420
 421 static struct ATS_ressource ressources[] = {
 422   /* FIXME: the coefficients for the specific plugins */
 423   {1, 7, "LAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 1, 3},
 424   {2, 7, "WAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 2, 3},
 425   {3, 4, "WLAN_ENERGY_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 0, 0, 0, 0, 2, 1}
 426 /*
 427     {4, 4, "COST_ENERGY_CONSUMPTION", VERY_BIG_DOUBLE_VALUE},
 428     {5, 5, "COST_CONNECT", VERY_BIG_DOUBLE_VALUE},
 429     {6, 6, "COST_BANDWITH_AVAILABLE", VERY_BIG_DOUBLE_VALUE},
 430     {7, 7, "COST_NETWORK_OVERHEAD", VERY_BIG_DOUBLE_VALUE},*/
 431 };
 432
 433 #define available_ressources (sizeof(ressources)/sizeof(*ressources))
 434
 435 /*
 436  * ATS quality metrics
 437  */
 438
 439 static struct ATS_quality_metric qm[] = {
 440   {1, 1028, "QUALITY_NET_DISTANCE"},
 441   {2, 1034, "QUALITY_NET_DELAY"},
 442 };
 443
 444 #define available_quality_metrics (sizeof(qm)/sizeof(*qm))
 445
 446
 447 /*
 448  * ATS functions
 449  */
 450 struct ATS_Handle *ats_init (double D,
 451                              double U,
 452                              double R,
 453                              int v_b_min,
 454                              int v_n_min,
 455                              int max_iterations,
 456                              struct GNUNET_TIME_Relative max_duration,
 457                              GNUNET_TRANSPORT_ATS_AddressNotification
 458                              address_not,
 459                              GNUNET_TRANSPORT_ATS_ResultCallback res_cb);
 460
 461 void ats_shutdown (struct ATS_Handle *ats);
 462
 463 void ats_delete_problem (struct ATS_Handle *ats);
 464
 465 int
 466 ats_create_problem (struct ATS_Handle *ats,
 467                     struct ATS_internals *stat,
 468                     struct ATS_peer *peers,
 469                     int c_p, struct ATS_mechanism *mechanisms, int c_m);
 470
 471 void ats_modify_problem_state (struct ATS_Handle *ats,
 472                                enum ATS_problem_state s);
 473
 474 void ats_calculate_bandwidth_distribution (struct ATS_Handle *ats);
 475
 476 void
 477 ats_solve_problem (struct ATS_Handle *ats,
 478                    unsigned int max_it,
 479                    unsigned int max_dur,
 480                    unsigned int c_peers,
 481                    unsigned int c_mechs, struct ATS_internals *stat);
 482
 483 int ats_evaluate_results (int result, int solution, char *problem);
 484
 485 void ats_update_problem_qm (struct ATS_Handle *ats);
 486
 487 void ats_update_problem_cr (struct ATS_Handle *ats);
 488
 489
 490 void
 491 ats_set_logging_options (struct ATS_Handle *ats,
 492                          struct GNUNET_STATISTICS_Handle *stats,
 493                          const struct GNUNET_CONFIGURATION_Handle *cfg);
 494
 495 #endif
 496 /* end of file gnunet-service-transport_ats.h */