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