src/transport/gnunet-service-transport_ats.h

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009 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 TRANSPORT_ATS_H
  27 #define 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,
  73               struct ATS_mechanism ** 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 {
 425     /* FIXME: the coefficients for the specific plugins */
 426     {1, 7, "LAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 1, 3},
 427     {2, 7, "WAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 2, 3},
 428     {3, 4, "WLAN_ENERGY_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 0, 0, 0, 0, 2, 1}
 429 /*
 430     {4, 4, "COST_ENERGY_CONSUMPTION", VERY_BIG_DOUBLE_VALUE},
 431     {5, 5, "COST_CONNECT", VERY_BIG_DOUBLE_VALUE},
 432     {6, 6, "COST_BANDWITH_AVAILABLE", VERY_BIG_DOUBLE_VALUE},
 433     {7, 7, "COST_NETWORK_OVERHEAD", VERY_BIG_DOUBLE_VALUE},*/
 434 };
 435
 436 #define available_ressources (sizeof(ressources)/sizeof(*ressources))
 437
 438 /*
 439  * ATS quality metrics
 440  */
 441
 442 static struct ATS_quality_metric qm[] =
 443 {
 444   {1, 1028, "QUALITY_NET_DISTANCE"},
 445   {2, 1034, "QUALITY_NET_DELAY"},
 446 };
 447
 448 #define available_quality_metrics (sizeof(qm)/sizeof(*qm))
 449
 450
 451 /*
 452  * ATS functions
 453  */
 454 struct ATS_Handle *
 455 ats_init (double D,
 456           double U,
 457           double R,
 458           int v_b_min,
 459           int v_n_min,
 460           int max_iterations,
 461           struct GNUNET_TIME_Relative max_duration,
 462           GNUNET_TRANSPORT_ATS_AddressNotification address_not,
 463           GNUNET_TRANSPORT_ATS_ResultCallback res_cb);
 464
 465 void
 466 ats_shutdown (struct ATS_Handle * ats);
 467
 468 void
 469 ats_delete_problem (struct ATS_Handle * ats);
 470
 471 int
 472 ats_create_problem (struct ATS_Handle *ats,
 473                     struct ATS_internals *stat,
 474                     struct ATS_peer *peers,
 475                     int c_p,
 476                     struct ATS_mechanism *mechanisms,
 477                     int c_m);
 478
 479 void ats_modify_problem_state (struct ATS_Handle * ats,
 480     enum ATS_problem_state s);
 481
 482 void
 483 ats_calculate_bandwidth_distribution (struct ATS_Handle * ats);
 484
 485 void
 486 ats_solve_problem (struct ATS_Handle * ats,
 487     unsigned int max_it,
 488     unsigned int  max_dur,
 489     unsigned int c_peers,
 490     unsigned int  c_mechs,
 491     struct ATS_internals *stat);
 492
 493 int
 494 ats_evaluate_results (int result,
 495     int solution,
 496     char * problem);
 497
 498 void
 499 ats_update_problem_qm (struct ATS_Handle * ats);
 500
 501 void
 502 ats_update_problem_cr (struct ATS_Handle * ats);
 503
 504
 505 void
 506 ats_set_logging_options (struct ATS_Handle * ats,
 507                          struct GNUNET_STATISTICS_Handle *stats,
 508                          const struct GNUNET_CONFIGURATION_Handle *cfg);
 509
 510 #endif
 511 /* end of file gnunet-service-transport_ats.h */