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/gnunet-service-ats-solver_mlp.h
22 * @brief ats MLP problem solver
23 * @author Matthias Wachs
24 * @author Christian Grothoff
27 #include "gnunet_statistics_service.h"
28 #include "gnunet-service-ats_addresses.h"
33 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
34 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
36 #define BIG_M_VALUE (UINT32_MAX) /10
37 #define BIG_M_STRING "unlimited"
39 #define MLP_AVERAGING_QUEUE_LENGTH 3
41 #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
42 #define MLP_MAX_ITERATIONS 4096
47 #define DEFAULT_QUALITY 1.0
48 #define DEFAULT_MIN_CONNECTIONS 4
49 #define DEFAULT_PEER_PREFERENCE 1.0
52 #define MLP_UNDEFINED 0
58 struct GNUNET_TIME_Relative build_dur;
59 struct GNUNET_TIME_Relative lp_dur;
60 struct GNUNET_TIME_Relative mip_dur;
78 struct GNUNET_PeerIdentity id;
80 /* Was this peer already added to the current problem? */
83 /* constraint 2: 1 address per peer*/
86 /* constraint 9: relativity */
89 /* Legacy preference value */
96 * GLPK (MLP) problem object
104 /* Number of addresses in problem */
105 unsigned int num_addresses;
106 /* Number of peers in problem */
107 unsigned int num_peers;
108 /* Number of elements in problem matrix */
109 unsigned int num_elements;
111 /* Row index constraint 2: */
113 /* Row index constraint 4: minimum connections */
115 /* Row index constraint 6: maximize diversity */
117 /* Row index constraint 8: utilization*/
119 /* Row index constraint 9: relativity*/
121 /* Row indices quality metrics */
122 int r_q[GNUNET_ATS_QualityPropertiesCount];
123 /* Row indices ATS network quotas */
124 int r_quota[GNUNET_ATS_NetworkTypeCount];
126 /* Column index Diversity (D) column */
128 /* Column index Utilization (U) column */
130 /* Column index Proportionality (R) column */
132 /* Column index quality metrics */
133 int c_q[GNUNET_ATS_QualityPropertiesCount];
138 /* Row index array */
140 /* Column index array */
142 /* Column index value */
149 /* Big M value for bandwidth capping */
152 /* ATS Quality metrics
154 * Array with GNUNET_ATS_QualityPropertiesCount elements
155 * contains mapping to GNUNET_ATS_Property*/
156 int q[GNUNET_ATS_QualityPropertiesCount];
158 /* Number of quality metrics */
161 /* Number of quality metrics */
164 /* Quality metric coefficients*/
165 double co_Q[GNUNET_ATS_QualityPropertiesCount];
167 /* Ressource costs coefficients*/
168 double co_RC[GNUNET_ATS_QualityPropertiesCount];
170 /* Diversity coefficient */
173 /* Utility coefficient */
176 /* Relativity coefficient */
179 /* Minimum bandwidth assigned to an address */
182 /* Minimum number of addresses with bandwidth assigned */
186 /* Array mapping array index to ATS network */
187 int quota_index[GNUNET_ATS_NetworkTypeCount];
188 /* Outbound quotas */
189 unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
192 unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
194 /* ATS ressource costs
195 * array with GNUNET_ATS_QualityPropertiesCount elements
196 * contains mapping to GNUNET_ATS_Property
198 int rc[GNUNET_ATS_QualityPropertiesCount];
205 struct GAS_MLP_Handle
210 struct GNUNET_STATISTICS_Handle *stats;
213 * Address hashmap for lookups
215 const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
218 * Addresses' bandwidth changed callback
220 GAS_bandwidth_changed_cb bw_changed_cb;
223 * Addresses' bandwidth changed callback closure
225 void *bw_changed_cb_cls;
228 * ATS function to get preferences
230 GAS_get_preferences get_preferences;
233 * Closure for ATS function to get preferences
235 void *get_preferences_cls;
238 * ATS function to get properties
240 GAS_get_properties get_properties;
243 * Closure for ATS function to get properties
245 void *get_properties_cls;
248 * Exclude peer from next result propagation
250 const struct GNUNET_PeerIdentity *exclude_peer;
253 * Encapsulation for the MLP problem
255 struct MLP_Problem p;
258 * Encapsulation for the MLP problem variables
260 struct MLP_Variables pv;
263 * Encapsulation for the MLP solution
265 struct MLP_Solution ps;
274 * Number of changes while solver was locked
279 * GLPK LP control parameter
282 glp_smcp control_param_lp;
284 void *control_param_lp;
288 * GLPK LP control parameter
291 glp_iocp control_param_mlp;
293 void *control_param_mlp;
297 * Peers with pending address requests
299 struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
302 * Was the problem updated since last solution
304 int mlp_prob_updated;
307 * Has the problem size changed since last solution
309 int mlp_prob_changed;
312 * Solve the problem automatically when updates occur?
313 * Default: GNUNET_YES
314 * Can be disabled for test and measurements
319 * Write MILP problem to a MPS file
324 * Write MILP problem to a MPS file
331 * Address specific MLP information
333 struct MLP_information
336 /* Bandwidth assigned */
337 struct GNUNET_BANDWIDTH_Value32NBO b_out;
338 struct GNUNET_BANDWIDTH_Value32NBO b_in;
340 /* Address selected */
343 /* bandwidth column index */
346 /* address usage column */
351 /* constraint 1: bandwidth capping */
354 /* constraint 3: minimum bandwidth */
360 * Solves the MLP problem
362 * @param solver the MLP Handle
363 * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
366 GAS_mlp_solve_problem (void *solver);
370 * Init the MLP problem solving component
372 * @param cfg the GNUNET_CONFIGURATION_Handle handle
373 * @param stats the GNUNET_STATISTICS handle
374 * @param network array of GNUNET_ATS_NetworkType with length dest_length
375 * @param out_dest array of outbound quotas
376 * @param in_dest array of outbound quota
377 * @param dest_length array length for quota arrays
378 * @param bw_changed_cb callback for changed bandwidth amounts
379 * @param bw_changed_cb_cls cls for callback
380 * @param get_preference callback to get relative preferences for a peer
381 * @param get_preference callback to get relative preferences for a peer
382 * @param get_properties_cls for callback to get relative properties
383 * @param get_properties_cls cls for callback to get relative properties
384 * @return struct GAS_MLP_Handle on success, NULL on fail
387 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
388 const struct GNUNET_STATISTICS_Handle *stats,
389 const struct GNUNET_CONTAINER_MultiPeerMap *addresses, int *network,
390 unsigned long long *out_dest, unsigned long long *in_dest, int dest_length,
391 GAS_bandwidth_changed_cb bw_changed_cb, void *bw_changed_cb_cls,
392 GAS_get_preferences get_preference, void *get_preference_cls,
393 GAS_get_properties get_properties, void *get_properties_cls);
397 * Add a single address within a network to the solver
399 * @param solver the solver Handle
400 * @param address the address to add
401 * @param network network type of this address
404 GAS_mlp_address_add (void *solver, struct ATS_Address *address,
409 * Transport properties for this address have changed
411 * @param solver solver handle
412 * @param address the address
413 * @param type the ATSI type in HBO
414 * @param abs_value the absolute value of the property
415 * @param rel_value the normalized value
418 GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
419 uint32_t type, uint32_t abs_value, double rel_value);
423 * Transport session for this address has changed
425 * NOTE: values in addresses are already updated
427 * @param solver solver handle
428 * @param address the address
429 * @param cur_session the current session
430 * @param new_session the new session
433 GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
434 uint32_t cur_session, uint32_t new_session);
438 * Usage for this address has changed
440 * NOTE: values in addresses are already updated
442 * @param solver solver handle
443 * @param address the address
444 * @param in_use usage state
447 GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
451 * Network scope for this address has changed
453 * NOTE: values in addresses are already updated
455 * @param solver solver handle
456 * @param address the address
457 * @param current_network the current network
458 * @param new_network the new network
461 GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
462 uint32_t current_network, uint32_t new_network);
465 * Deletes a single address in the MLP problem
467 * The MLP problem has to be recreated and the problem has to be resolved
469 * @param solver the MLP Handle
470 * @param address the address to delete
471 * @param session_only delete only session not whole address
474 GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
478 * Changes the preferences for a peer in the MLP problem
480 * @param solver the MLP Handle
481 * @param peer the peer
482 * @param kind the kind to change the preference
483 * @param pref_rel the relative score
486 GAS_mlp_address_change_preference (void *solver,
487 const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
491 * Get application feedback for a peer
493 * @param solver the solver handle
494 * @param application the application
495 * @param peer the peer to change the preference for
496 * @param scope the time interval for this feedback: [now - scope .. now]
497 * @param kind the kind to change the preference
498 * @param score the score
501 GAS_mlp_address_preference_feedback (void *solver, void *application,
502 const struct GNUNET_PeerIdentity *peer,
503 const struct GNUNET_TIME_Relative scope,
504 enum GNUNET_ATS_PreferenceKind kind, double score);
507 * Start a bulk operation
509 * @param solver the solver
512 GAS_mlp_bulk_start (void *solver);
515 * Bulk operation done
518 GAS_mlp_bulk_stop (void *solver);
521 * Get the preferred address for a specific peer until
522 * GAS_mlp_stop_get_preferred_address is called
524 * @param solver the MLP Handle
525 * @param peer the peer
526 * @return suggested address
528 const struct ATS_Address *
529 GAS_mlp_get_preferred_address (void *solver,
530 const struct GNUNET_PeerIdentity *peer);
533 * Stop notifying about address and bandwidth changes for this peer
535 * @param solver the MLP handle
536 * @param peer the peer
539 GAS_mlp_stop_get_preferred_address (void *solver,
540 const struct GNUNET_PeerIdentity *peer);
543 * Shutdown the MLP problem solving component
545 * @param solver the solver handle
548 GAS_mlp_done (void *solver);
551 /* end of gnunet-service-ats_addresses_mlp.h */