2 (C) 2011 Christian Grothoff (and other contributing authors)
4 GNUnet is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published
6 by the Free Software Foundation; either version 3, or (at your
7 option) any later version.
9 GNUnet is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with GNUnet; see the file COPYING. If not, write to the
16 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 Boston, MA 02111-1307, USA.
21 * @file ats/plugin_ats_mlp.h
22 * @brief ats MLP problem solver
23 * @author Matthias Wachs
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
28 #include "gnunet_ats_service.h"
29 #include "gnunet_ats_plugin.h"
30 #include "gnunet-service-ats_addresses.h"
31 #include "gnunet_statistics_service.h"
36 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
37 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
39 #define BIG_M_VALUE (UINT32_MAX) /10
40 #define BIG_M_STRING "unlimited"
42 #define MLP_AVERAGING_QUEUE_LENGTH 3
44 #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
45 #define MLP_MAX_ITERATIONS 4096
50 #define DEFAULT_QUALITY 1.0
51 #define DEFAULT_MIN_CONNECTIONS 4
52 #define DEFAULT_PEER_PREFERENCE 1.0
55 #define MLP_UNDEFINED 0
77 struct GNUNET_PeerIdentity id;
79 /* Was this peer already added to the current problem? */
82 /* constraint 2: 1 address per peer*/
85 /* constraint 9: relativity */
88 /* Legacy preference value */
95 * GLPK (MLP) problem object
103 /* Number of addresses in problem */
104 unsigned int num_addresses;
105 /* Number of peers in problem */
106 unsigned int num_peers;
107 /* Number of elements in problem matrix */
108 unsigned int num_elements;
110 /* Row index constraint 2: */
112 /* Row index constraint 4: minimum connections */
114 /* Row index constraint 6: maximize diversity */
116 /* Row index constraint 8: utilization*/
118 /* Row index constraint 9: relativity*/
120 /* Row indices quality metrics */
121 int r_q[GNUNET_ATS_QualityPropertiesCount];
122 /* Row indices ATS network quotas */
123 int r_quota[GNUNET_ATS_NetworkTypeCount];
125 /* Column index Diversity (D) column */
127 /* Column index Utilization (U) column */
129 /* Column index Proportionality (R) column */
131 /* Column index quality metrics */
132 int c_q[GNUNET_ATS_QualityPropertiesCount];
137 /* Row index array */
139 /* Column index array */
141 /* Column index value */
148 /* Big M value for bandwidth capping */
151 /* ATS Quality metrics
153 * Array with GNUNET_ATS_QualityPropertiesCount elements
154 * contains mapping to GNUNET_ATS_Property*/
155 int q[GNUNET_ATS_QualityPropertiesCount];
157 /* Number of quality metrics */
160 /* Number of quality metrics */
163 /* Quality metric coefficients*/
164 double co_Q[GNUNET_ATS_QualityPropertiesCount];
166 /* Ressource costs coefficients*/
167 double co_RC[GNUNET_ATS_QualityPropertiesCount];
169 /* Diversity coefficient */
172 /* Utility coefficient */
175 /* Relativity coefficient */
178 /* Minimum bandwidth assigned to an address */
181 /* Minimum number of addresses with bandwidth assigned */
185 /* Array mapping array index to ATS network */
186 int quota_index[GNUNET_ATS_NetworkTypeCount];
187 /* Outbound quotas */
188 unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
191 unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
193 /* ATS ressource costs
194 * array with GNUNET_ATS_QualityPropertiesCount elements
195 * contains mapping to GNUNET_ATS_Property
197 int rc[GNUNET_ATS_QualityPropertiesCount];
204 struct GAS_MLP_Handle
206 struct GNUNET_ATS_PluginEnvironment *env;
211 struct GNUNET_STATISTICS_Handle *stats;
214 * Address hashmap for lookups
216 const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
219 * Addresses' bandwidth changed callback
221 GAS_bandwidth_changed_cb bw_changed_cb;
224 * Addresses' bandwidth changed callback closure
226 void *bw_changed_cb_cls;
229 * ATS function to get preferences
231 GAS_get_preferences get_preferences;
234 * Closure for ATS function to get preferences
236 void *get_preferences_cls;
239 * ATS function to get properties
241 GAS_get_properties get_properties;
244 * Closure for ATS function to get properties
246 void *get_properties_cls;
249 * Exclude peer from next result propagation
251 const struct GNUNET_PeerIdentity *exclude_peer;
254 * Encapsulation for the MLP problem
256 struct MLP_Problem p;
259 * Encapsulation for the MLP problem variables
261 struct MLP_Variables pv;
264 * Encapsulation for the MLP solution
266 struct MLP_Solution ps;
275 * Number of changes while solver was locked
277 int stat_bulk_requests;
280 * GLPK LP control parameter
283 glp_smcp control_param_lp;
285 void *control_param_lp;
289 * GLPK LP control parameter
292 glp_iocp control_param_mlp;
294 void *control_param_mlp;
298 * Peers with pending address requests
300 struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
303 * Was the problem updated since last solution
305 int stat_mlp_prob_updated;
308 * Has the problem size changed since last solution
310 int stat_mlp_prob_changed;
313 * Solve the problem automatically when updates occur?
314 * Default: GNUNET_YES
315 * Can be disabled for test and measurements
317 int opt_mlp_auto_solve;
320 * Write all MILP problems to a MPS file
322 int opt_dump_problem_all;
325 * Write all MILP problem solutions to a file
327 int opt_dump_solution_all;
330 * Write MILP problems to a MPS file when solver fails
332 int opt_dump_problem_on_fail;
335 * Write MILP problem solutions to a file when solver fails
337 int opt_dump_solution_on_fail;
342 int opt_glpk_verbose;
347 * Address specific MLP information
349 struct MLP_information
352 /* Bandwidth assigned */
353 struct GNUNET_BANDWIDTH_Value32NBO b_out;
354 struct GNUNET_BANDWIDTH_Value32NBO b_in;
356 /* Address selected */
359 /* bandwidth column index */
362 /* address usage column */
367 /* constraint 1: bandwidth capping */
370 /* constraint 3: minimum bandwidth */
376 * Solves the MLP problem
378 * @param solver the MLP Handle
379 * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
382 GAS_mlp_solve_problem (void *solver);
386 * Init the MLP problem solving component
388 * @param cfg the GNUNET_CONFIGURATION_Handle handle
389 * @param stats the GNUNET_STATISTICS handle
390 * @param addresses Hashmap containing addresses
391 * @param network array of GNUNET_ATS_NetworkType with length dest_length
392 * @param out_dest array of outbound quotas
393 * @param in_dest array of outbound quota
394 * @param dest_length array length for quota arrays
395 * @param bw_changed_cb callback for changed bandwidth amounts
396 * @param bw_changed_cb_cls cls for callback
397 * @param get_preference callback to get relative preferences for a peer
398 * @param get_preference_cls cls for callback to get relative preferences for a peer
399 * @param get_properties callback to get relative properties
400 * @param get_properties_cls cls for callback to get relative properties
401 * @return struct GAS_MLP_Handle on success, NULL on fail
404 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
405 const struct GNUNET_STATISTICS_Handle *stats,
406 const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
408 unsigned long long *out_dest,
409 unsigned long long *in_dest,
411 GAS_bandwidth_changed_cb bw_changed_cb,
412 void *bw_changed_cb_cls,
413 GAS_get_preferences get_preference,
414 void *get_preference_cls,
415 GAS_get_properties get_properties,
416 void *get_properties_cls);
420 * Add a single address within a network to the solver
422 * @param solver the solver Handle
423 * @param address the address to add
424 * @param network network type of this address
427 GAS_mlp_address_add (void *solver, struct ATS_Address *address,
432 * Transport properties for this address have changed
434 * @param solver solver handle
435 * @param address the address
436 * @param type the ATSI type in HBO
437 * @param abs_value the absolute value of the property
438 * @param rel_value the normalized value
441 GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
442 uint32_t type, uint32_t abs_value, double rel_value);
446 * Transport session for this address has changed
448 * NOTE: values in addresses are already updated
450 * @param solver solver handle
451 * @param address the address
452 * @param cur_session the current session
453 * @param new_session the new session
456 GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
457 uint32_t cur_session, uint32_t new_session);
461 * Usage for this address has changed
463 * NOTE: values in addresses are already updated
465 * @param solver solver handle
466 * @param address the address
467 * @param in_use usage state
470 GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
474 * Network scope for this address has changed
476 * NOTE: values in addresses are already updated
478 * @param solver solver handle
479 * @param address the address
480 * @param current_network the current network
481 * @param new_network the new network
484 GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
485 uint32_t current_network, uint32_t new_network);
488 * Deletes a single address in the MLP problem
490 * The MLP problem has to be recreated and the problem has to be resolved
492 * @param solver the MLP Handle
493 * @param address the address to delete
494 * @param session_only delete only session not whole address
497 GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
501 * Changes the preferences for a peer in the MLP problem
503 * @param solver the MLP Handle
504 * @param peer the peer
505 * @param kind the kind to change the preference
506 * @param pref_rel the relative score
509 GAS_mlp_address_change_preference (void *solver,
510 const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
514 * Get application feedback for a peer
516 * @param solver the solver handle
517 * @param application the application
518 * @param peer the peer to change the preference for
519 * @param scope the time interval for this feedback: [now - scope .. now]
520 * @param kind the kind to change the preference
521 * @param score the score
524 GAS_mlp_address_preference_feedback (void *solver, void *application,
525 const struct GNUNET_PeerIdentity *peer,
526 const struct GNUNET_TIME_Relative scope,
527 enum GNUNET_ATS_PreferenceKind kind, double score);
530 * Start a bulk operation
532 * @param solver the solver
535 GAS_mlp_bulk_start (void *solver);
538 * Bulk operation done
541 GAS_mlp_bulk_stop (void *solver);
544 * Get the preferred address for a specific peer until
545 * GAS_mlp_stop_get_preferred_address is called
547 * @param solver the MLP Handle
548 * @param peer the peer
549 * @return suggested address
551 const struct ATS_Address *
552 GAS_mlp_get_preferred_address (void *solver,
553 const struct GNUNET_PeerIdentity *peer);
556 * Stop notifying about address and bandwidth changes for this peer
558 * @param solver the MLP handle
559 * @param peer the peer
562 GAS_mlp_stop_get_preferred_address (void *solver,
563 const struct GNUNET_PeerIdentity *peer);
566 * Shutdown the MLP problem solving component
568 * @param solver the solver handle
571 GAS_mlp_done (void *solver);
574 /* end of plugin_ats_mlp.h */