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"
37 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
38 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
40 #define BIG_M_VALUE (UINT32_MAX) /10
41 #define BIG_M_STRING "unlimited"
43 #define MLP_AVERAGING_QUEUE_LENGTH 3
45 #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
46 #define MLP_MAX_ITERATIONS 4096
51 #define DEFAULT_QUALITY 1.0
52 #define DEFAULT_MIN_CONNECTIONS 4
53 #define DEFAULT_PEER_PREFERENCE 1.0
56 #define MLP_UNDEFINED 0
60 enum MLP_Output_Format
75 double lp_objective_value;
76 double mlp_objective_value;
91 struct GNUNET_PeerIdentity id;
93 /* Was this peer already added to the current problem? */
96 /* constraint 2: 1 address per peer*/
99 /* constraint 9: relativity */
102 /* Legacy preference value */
109 * GLPK (MLP) problem object
117 /* Number of addresses in problem */
118 unsigned int num_addresses;
119 /* Number of peers in problem */
120 unsigned int num_peers;
121 /* Number of elements in problem matrix */
122 unsigned int num_elements;
124 /* Row index constraint 2: */
126 /* Row index constraint 4: minimum connections */
128 /* Row index constraint 6: maximize diversity */
130 /* Row index constraint 8: utilization*/
132 /* Row index constraint 9: relativity*/
134 /* Row indices quality metrics */
135 int r_q[GNUNET_ATS_QualityPropertiesCount];
136 /* Row indices ATS network quotas */
137 int r_quota[GNUNET_ATS_NetworkTypeCount];
139 /* Column index Diversity (D) column */
141 /* Column index Utilization (U) column */
143 /* Column index Proportionality (R) column */
145 /* Column index quality metrics */
146 int c_q[GNUNET_ATS_QualityPropertiesCount];
151 /* Row index array */
153 /* Column index array */
155 /* Column index value */
162 /* Big M value for bandwidth capping */
171 /* ATS Quality metrics
173 * Array with GNUNET_ATS_QualityPropertiesCount elements
174 * contains mapping to GNUNET_ATS_Property*/
175 int q[GNUNET_ATS_QualityPropertiesCount];
177 /* Number of quality metrics */
180 /* Number of quality metrics */
183 /* Quality metric coefficients*/
184 double co_Q[GNUNET_ATS_QualityPropertiesCount];
186 /* Ressource costs coefficients*/
187 double co_RC[GNUNET_ATS_QualityPropertiesCount];
189 /* Diversity coefficient */
192 /* Utility coefficient */
195 /* Relativity coefficient */
198 /* Minimum bandwidth assigned to an address */
201 /* Minimum number of addresses with bandwidth assigned */
205 /* Array mapping array index to ATS network */
206 int quota_index[GNUNET_ATS_NetworkTypeCount];
207 /* Outbound quotas */
208 unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
211 unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
213 /* ATS ressource costs
214 * array with GNUNET_ATS_QualityPropertiesCount elements
215 * contains mapping to GNUNET_ATS_Property
217 int rc[GNUNET_ATS_QualityPropertiesCount];
224 struct GAS_MLP_Handle
226 struct GNUNET_ATS_PluginEnvironment *env;
231 struct GNUNET_STATISTICS_Handle *stats;
234 * Address hashmap for lookups
236 const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
239 * Addresses' bandwidth changed callback
241 GAS_bandwidth_changed_cb bw_changed_cb;
244 * Addresses' bandwidth changed callback closure
246 void *bw_changed_cb_cls;
249 * ATS function to get preferences
251 GAS_get_preferences get_preferences;
254 * Closure for ATS function to get preferences
256 void *get_preferences_cls;
259 * ATS function to get properties
261 GAS_get_properties get_properties;
264 * Closure for ATS function to get properties
266 void *get_properties_cls;
269 * Exclude peer from next result propagation
271 const struct GNUNET_PeerIdentity *exclude_peer;
274 * Encapsulation for the MLP problem
276 struct MLP_Problem p;
279 * Encapsulation for the MLP problem variables
281 struct MLP_Variables pv;
284 * Encapsulation for the MLP solution
286 struct MLP_Solution ps;
295 * Number of changes while solver was locked
297 int stat_bulk_requests;
300 * GLPK LP control parameter
303 glp_smcp control_param_lp;
305 void *control_param_lp;
309 * GLPK LP control parameter
312 glp_iocp control_param_mlp;
314 void *control_param_mlp;
318 * Peers with pending address requests
320 struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
323 * Was the problem updated since last solution
325 int stat_mlp_prob_updated;
328 * Has the problem size changed since last solution
330 int stat_mlp_prob_changed;
333 * Solve the problem automatically when updates occur?
334 * Default: GNUNET_YES
335 * Can be disabled for test and measurements
337 int opt_mlp_auto_solve;
340 * Write all MILP problems to a MPS file
342 int opt_dump_problem_all;
345 * Write all MILP problem solutions to a file
347 int opt_dump_solution_all;
350 * Write MILP problems to a MPS file when solver fails
352 int opt_dump_problem_on_fail;
355 * Write MILP problem solutions to a file when solver fails
357 int opt_dump_solution_on_fail;
360 * solve feasibility only
362 int opt_dbg_feasibility_only;
365 * solve autoscale the problem
367 int opt_dbg_autoscale_problem;
370 * use the intopt presolver instead of simplex
372 int opt_dbg_intopt_presolver;
377 int opt_dbg_glpk_verbose;
380 * solve autoscale the problem
382 int opt_dbg_optimize_relativity;
385 * solve autoscale the problem
387 int opt_dbg_optimize_diversity;
390 * solve autoscale the problem
392 int opt_dbg_optimize_quality;
395 * solve autoscale the problem
397 int opt_dbg_optimize_utility;
403 enum MLP_Output_Format opt_log_format;
407 * Address specific MLP information
409 struct MLP_information
412 /* Bandwidth assigned */
413 struct GNUNET_BANDWIDTH_Value32NBO b_out;
414 struct GNUNET_BANDWIDTH_Value32NBO b_in;
416 /* Address selected */
419 /* bandwidth column index */
422 /* address usage column */
427 /* constraint 1: bandwidth capping */
430 /* constraint 3: minimum bandwidth */
436 * Solves the MLP problem
438 * @param solver the MLP Handle
439 * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
442 GAS_mlp_solve_problem (void *solver);
446 * Init the MLP problem solving component
448 * @param cfg the GNUNET_CONFIGURATION_Handle handle
449 * @param stats the GNUNET_STATISTICS handle
450 * @param addresses Hashmap containing addresses
451 * @param network array of GNUNET_ATS_NetworkType with length dest_length
452 * @param out_dest array of outbound quotas
453 * @param in_dest array of outbound quota
454 * @param dest_length array length for quota arrays
455 * @param bw_changed_cb callback for changed bandwidth amounts
456 * @param bw_changed_cb_cls cls for callback
457 * @param get_preference callback to get relative preferences for a peer
458 * @param get_preference_cls cls for callback to get relative preferences for a peer
459 * @param get_properties callback to get relative properties
460 * @param get_properties_cls cls for callback to get relative properties
461 * @return struct GAS_MLP_Handle on success, NULL on fail
464 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
465 const struct GNUNET_STATISTICS_Handle *stats,
466 const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
468 unsigned long long *out_dest,
469 unsigned long long *in_dest,
471 GAS_bandwidth_changed_cb bw_changed_cb,
472 void *bw_changed_cb_cls,
473 GAS_get_preferences get_preference,
474 void *get_preference_cls,
475 GAS_get_properties get_properties,
476 void *get_properties_cls);
480 * Add a single address within a network to the solver
482 * @param solver the solver Handle
483 * @param address the address to add
484 * @param network network type of this address
487 GAS_mlp_address_add (void *solver, struct ATS_Address *address,
492 * Transport properties for this address have changed
494 * @param solver solver handle
495 * @param address the address
496 * @param type the ATSI type in HBO
497 * @param abs_value the absolute value of the property
498 * @param rel_value the normalized value
501 GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
502 uint32_t type, uint32_t abs_value, double rel_value);
506 * Transport session for this address has changed
508 * NOTE: values in addresses are already updated
510 * @param solver solver handle
511 * @param address the address
512 * @param cur_session the current session
513 * @param new_session the new session
516 GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
517 uint32_t cur_session, uint32_t new_session);
521 * Usage for this address has changed
523 * NOTE: values in addresses are already updated
525 * @param solver solver handle
526 * @param address the address
527 * @param in_use usage state
530 GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
534 * Network scope for this address has changed
536 * NOTE: values in addresses are already updated
538 * @param solver solver handle
539 * @param address the address
540 * @param current_network the current network
541 * @param new_network the new network
544 GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
545 uint32_t current_network, uint32_t new_network);
548 * Deletes a single address in the MLP problem
550 * The MLP problem has to be recreated and the problem has to be resolved
552 * @param solver the MLP Handle
553 * @param address the address to delete
554 * @param session_only delete only session not whole address
557 GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
561 * Changes the preferences for a peer in the MLP problem
563 * @param solver the MLP Handle
564 * @param peer the peer
565 * @param kind the kind to change the preference
566 * @param pref_rel the relative score
569 GAS_mlp_address_change_preference (void *solver,
570 const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
574 * Get application feedback for a peer
576 * @param solver the solver handle
577 * @param application the application
578 * @param peer the peer to change the preference for
579 * @param scope the time interval for this feedback: [now - scope .. now]
580 * @param kind the kind to change the preference
581 * @param score the score
584 GAS_mlp_address_preference_feedback (void *solver, void *application,
585 const struct GNUNET_PeerIdentity *peer,
586 const struct GNUNET_TIME_Relative scope,
587 enum GNUNET_ATS_PreferenceKind kind, double score);
590 * Start a bulk operation
592 * @param solver the solver
595 GAS_mlp_bulk_start (void *solver);
598 * Bulk operation done
601 GAS_mlp_bulk_stop (void *solver);
604 * Get the preferred address for a specific peer until
605 * GAS_mlp_stop_get_preferred_address is called
607 * @param solver the MLP Handle
608 * @param peer the peer
609 * @return suggested address
611 const struct ATS_Address *
612 GAS_mlp_get_preferred_address (void *solver,
613 const struct GNUNET_PeerIdentity *peer);
616 * Stop notifying about address and bandwidth changes for this peer
618 * @param solver the MLP handle
619 * @param peer the peer
622 GAS_mlp_stop_get_preferred_address (void *solver,
623 const struct GNUNET_PeerIdentity *peer);
626 * Shutdown the MLP problem solving component
628 * @param solver the solver handle
631 GAS_mlp_done (void *solver);
634 /* end of plugin_ats_mlp.h */