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/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      * Maximum execution time per calculation
 220      */
 221     struct GNUNET_TIME_Relative max_exec_duration;
 222
 223     /**
 224      * GLPK (MLP) problem object
 225      */
 226 #if HAVE_LIBGLPK
 227
 228     glp_prob *prob;
 229 #else
 230     void * prob;
 231 #endif
 232
 233     /**
 234      * Internal information state of the GLPK problem
 235      */
 236     struct ATS_internals internal;
 237
 238     /**
 239      * mechanisms used in current problem
 240      * needed for problem modification
 241      */
 242     struct ATS_mechanism * mechanisms;
 243
 244     /**
 245      * peers used in current problem
 246      * needed for problem modification
 247      */
 248     struct ATS_peer * peers;
 249
 250     /**
 251      * State of the MLP problem
 252      * value of ATS_problem_state
 253      *
 254      */
 255     int state;
 256
 257     /**
 258      * number of successful executions
 259      */
 260     int successful_executions;
 261
 262     /**
 263      * number with an invalid result
 264      */
 265     int invalid_executions;
 266
 267     /**
 268      * Maximum number of LP iterations per calculation
 269      */
 270     int max_iterations;
 271
 272
 273     /*
 274      * ATS configuration
 275      */
 276
 277
 278     /**
 279      * Diversity weight
 280      */
 281     double D;
 282
 283     /**
 284      * Utility weight
 285      */
 286     double U;
 287
 288     /**
 289      * Relativity weight
 290      */
 291     double R;
 292
 293     /**
 294      * Minimum bandwidth per peer
 295      */
 296     int v_b_min;
 297
 298     /**
 299      * Minimum number of connections per peer
 300      */
 301     int v_n_min;
 302
 303
 304     /**
 305      * Logging related variables
 306      */
 307
 308
 309     /**
 310      * Dump problem to a file?
 311      */
 312     int save_mlp;
 313
 314     /**
 315      * Dump solution to a file
 316      */
 317     int save_solution;
 318
 319     /**
 320      * Dump solution when minimum peers:
 321      */
 322     int dump_min_peers;
 323
 324     /**
 325      * Dump solution when minimum addresses:
 326      */
 327     int dump_min_addr;
 328
 329     /**
 330      * Dump solution overwrite file:
 331      */
 332     int dump_overwrite;
 333 };
 334
 335 struct ATS_mechanism
 336 {
 337     struct ATS_mechanism * prev;
 338     struct ATS_mechanism * next;
 339     struct ForeignAddressList * addr;
 340     struct ATS_quality_entry * quality;
 341     struct ATS_ressource_entry * ressources;
 342     struct TransportPlugin * plugin;
 343     struct ATS_peer * peer;
 344     int col_index;
 345     int     id;
 346     struct ATS_ressource_cost * rc;
 347 };
 348
 349 struct ATS_peer
 350 {
 351     struct GNUNET_PeerIdentity peer;
 352
 353     struct ATS_mechanism * m_head;
 354     struct ATS_mechanism * m_tail;
 355
 356     /* preference value f */
 357     double f;
 358
 359     //struct NeighbourList * n;
 360 };
 361
 362 struct ATS_ressource
 363 {
 364     /* index in ressources array */
 365     int index;
 366     /* depending ATSi parameter to calculcate limits */
 367     int atis_index;
 368     /* cfg option to load limits */
 369     char * cfg_param;
 370     /* lower bound */
 371     double c_min;
 372     /* upper bound */
 373     double c_max;
 374
 375     /* cofficients for the specific plugins */
 376     double c_unix;
 377     double c_tcp;
 378     double c_udp;
 379     double c_http;
 380     double c_https;
 381     double c_wlan;
 382     double c_default;
 383 };
 384
 385
 386 struct ATS_ressource_entry
 387 {
 388     /* index in ressources array */
 389     int index;
 390     /* depending ATSi parameter to calculcate limits */
 391     int atis_index;
 392     /* lower bound */
 393     double c;
 394 };
 395
 396
 397 struct ATS_quality_metric
 398 {
 399     int index;
 400     int atis_index;
 401     char * name;
 402 };
 403
 404 struct ATS_quality_entry
 405 {
 406     int index;
 407     int atsi_index;
 408     uint32_t values[3];
 409     int current;
 410 };
 411
 412 /*
 413  * ATS ressources
 414  */
 415
 416
 417 static struct ATS_ressource ressources[] =
 418 {
 419     /* FIXME: the coefficients for the specific plugins */
 420     {1, 7, "LAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 1, 3},
 421     {2, 7, "WAN_BW_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 1, 1, 2, 2, 2, 3},
 422     {3, 4, "WLAN_ENERGY_LIMIT", 0, VERY_BIG_DOUBLE_VALUE, 0, 0, 0, 0, 0, 2, 1}
 423 /*
 424     {4, 4, "COST_ENERGY_CONSUMPTION", VERY_BIG_DOUBLE_VALUE},
 425     {5, 5, "COST_CONNECT", VERY_BIG_DOUBLE_VALUE},
 426     {6, 6, "COST_BANDWITH_AVAILABLE", VERY_BIG_DOUBLE_VALUE},
 427     {7, 7, "COST_NETWORK_OVERHEAD", VERY_BIG_DOUBLE_VALUE},*/
 428 };
 429
 430 #define available_ressources (sizeof(ressources)/sizeof(*ressources))
 431
 432 /*
 433  * ATS quality metrics
 434  */
 435
 436 static struct ATS_quality_metric qm[] =
 437 {
 438   {1, 1028, "QUALITY_NET_DISTANCE"},
 439   {2, 1034, "QUALITY_NET_DELAY"},
 440 };
 441
 442 #define available_quality_metrics (sizeof(qm)/sizeof(*qm))
 443
 444
 445 /*
 446  * ATS functions
 447  */
 448 struct ATS_Handle *
 449 ats_init (double D,
 450           double U,
 451           double R,
 452           int v_b_min,
 453           int v_n_min,
 454           int max_iterations,
 455           struct GNUNET_TIME_Relative max_duration,
 456           GNUNET_TRANSPORT_ATS_AddressNotification address_not,
 457           GNUNET_TRANSPORT_ATS_ResultCallback res_cb);
 458
 459 void
 460 ats_shutdown (struct ATS_Handle * ats);
 461
 462 void
 463 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,
 470                     struct ATS_mechanism *mechanisms,
 471                     int c_m);
 472
 473 void ats_modify_problem_state (struct ATS_Handle * ats,
 474     enum ATS_problem_state s);
 475
 476 void
 477 ats_calculate_bandwidth_distribution (struct ATS_Handle * ats,
 478     struct GNUNET_STATISTICS_Handle *stats);
 479
 480 void
 481 ats_solve_problem (struct ATS_Handle * ats,
 482     unsigned int max_it,
 483     unsigned int  max_dur,
 484     unsigned int c_peers,
 485     unsigned int  c_mechs,
 486     struct ATS_internals *stat);
 487
 488 int
 489 ats_evaluate_results (int result,
 490     int solution,
 491     char * problem);
 492
 493 void
 494 ats_update_problem_qm (struct ATS_Handle * ats);
 495
 496 void
 497 ats_update_problem_cr (struct ATS_Handle * ats);
 498
 499
 500 void
 501 ats_set_logging_options (struct ATS_Handle * ats,
 502                         int minimum_addresses,
 503                         int minimum_peers,
 504                         int overwrite_dump,
 505                         int log_solution,
 506                         int log_problem);
 507
 508 #endif
 509 /* end of file transport_ats.h */