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