2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file ats/gnunet-service-ats_addresses_mlp.h
23 * @brief ats mlp problem solver
24 * @author Matthias Wachs
25 * @author Christian Grothoff
28 #include "gnunet_statistics_service.h"
29 #include "gnunet-service-ats_addresses.h"
34 #ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
35 #define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
37 #define DEBUG_MLP GNUNET_EXTRA_LOGGING
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, 3)
45 #define MLP_MAX_ITERATIONS INT_MAX
49 struct ATS_Peer *next;
50 struct ATS_Peer *prev;
52 struct GNUNET_PeerIdentity id;
54 /* Array of quality preferences */
55 double f_q[GNUNET_ATS_QualityPropertiesCount];
56 /* Legacy preference value */
59 /* constraint 2: 1 address per peer*/
62 /* constraint 9: relativity */
65 struct ATS_Address *head;
66 struct ATS_Address *tail;
69 struct ATS_PreferedAddress
71 uint32_t bandwidth_out;
72 uint32_t bandwidth_in;
73 struct ATS_Address *address;
76 struct GAS_MLP_SolutionContext
80 struct GNUNET_TIME_Relative lp_duration;
81 struct GNUNET_TIME_Relative mlp_duration;
92 struct GNUNET_STATISTICS_Handle *stats;
95 * GLPK (MLP) problem object
106 * GLPK LP control parameter
108 glp_smcp control_param_lp;
111 * GLPK LP control parameter
113 glp_iocp control_param_mlp;
116 * Solves the task in an regular interval
118 GNUNET_SCHEDULER_TaskIdentifier mlp_task;
121 * Interval between scheduled problem solving
123 struct GNUNET_TIME_Relative exec_interval;
126 * Maximum execution time per problem solving
128 struct GNUNET_TIME_Relative max_exec_duration;
131 * Maximum number of LP iterations per problem solving
133 unsigned int max_iterations;
136 * Solve the problem automatically when updates occur?
137 * Default: GNUNET_YES
138 * Can be disabled for test and measurements
144 /* state information */
147 * Do we need to use the LP presolver?
149 * If the problem addresses were added or removed and the last basis was we
150 * need to use the presolver.
151 * presolver_required == GNUNET_YES
153 * If values were modified, we can reuse a valid basis
154 * presolver_required == GNUNET_NO
156 int presolver_required;
161 * Time of last execution
163 struct GNUNET_TIME_Absolute last_execution;
167 * How often was the LP problem solved
169 unsigned int lp_solved;
172 * total duration of all lp solver executions
174 uint64_t lp_total_duration;
177 * How often was the MLP problem solved
179 unsigned int mlp_solved;
182 * total duration of all mlp solver executions
184 uint64_t mlp_total_duration;
186 unsigned int addr_in_problem;
188 /* Information about the problem */
190 struct ATS_Peer *peer_head;
191 struct ATS_Peer *peer_tail;
193 /* Number of peers */
196 /* current problem matrix */
197 /* row index array */
199 /* column index array */
201 /* column index array */
203 /* current size of the constraint matrix |indices| */
204 unsigned int cm_size;
207 /* Row index constraint 2: */
209 /* Row index constraint 4: minimum connections */
211 /* Row index constraint 6: maximize diversity */
213 /* Row index constraint 8: utilization*/
215 /* Row index constraint 9: relativity*/
218 /* column index Diversity (D) column */
222 /* column index Utilization (U) column */
226 /* column index Proportionality (R) column */
230 /* ATS Quality metrics
232 * array with GNUNET_ATS_QualityPropertiesCount elements
233 * contains mapping to GNUNET_ATS_Property*/
234 int q[GNUNET_ATS_QualityPropertiesCount];
236 /* column index quality metrics */
237 int c_q[GNUNET_ATS_QualityPropertiesCount];
239 /* column index quality metrics */
240 int r_q[GNUNET_ATS_QualityPropertiesCount];
242 /* quality metric coefficients*/
243 double co_Q[GNUNET_ATS_QualityPropertiesCount];
245 /* number of quality metrics */
248 /* ATS network quotas */
249 int c_quota[GNUNET_ATS_NetworkTypeCount];
250 int r_quota[GNUNET_ATS_NetworkTypeCount];
251 int quota_index [GNUNET_ATS_NetworkTypeCount];
252 unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
253 unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
255 /* ATS ressource costs
257 * array with GNUNET_ATS_QualityPropertiesCount elements
258 * contains mapping to GNUNET_ATS_Property*/
259 int rc[GNUNET_ATS_QualityPropertiesCount];
261 /* column index ressource costs */
262 int c_rc[GNUNET_ATS_QualityPropertiesCount];
264 /* ressource costs coefficients*/
265 double co_RC[GNUNET_ATS_QualityPropertiesCount];
267 /* number of quality metrics */
270 /* minimum bandwidth assigned to an address */
273 /* minimum number of addresses with bandwidth assigned */
279 * Address specific MLP information
281 struct MLP_information
287 /* bandwidth column index */
290 /* address usage column */
295 /* constraint 1: bandwidth capping */
298 /* constraint 3: minimum bandwidth */
301 /* Quality information row indices */
302 unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
304 /* Quality information */
305 double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH];
307 /* Quality information averaged */
308 double q_averaged[GNUNET_ATS_QualityPropertiesCount];
310 /* Averaging index */
311 int q_avg_i[GNUNET_ATS_QualityPropertiesCount];
316 * Init the MLP problem solving component
318 * @param cfg configuration handle
319 * @param stats the GNUNET_STATISTICS handle
320 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
321 * @param max_iterations maximum time limit for the LP/MLP Solver
322 * @return struct GAS_MLP_Handle * on success, NULL on fail
325 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
326 const struct GNUNET_STATISTICS_Handle *stats);
329 * Solves the MLP problem on demand
331 * @param mlp the MLP Handle
332 * @param ctx solution context
333 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
336 GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *ctx);
340 * Updates a single address in the MLP problem
342 * If the address did not exist before in the problem:
343 * The MLP problem has to be recreated and the problem has to be resolved
345 * Otherwise the addresses' values can be updated and the existing base can
348 * @param mlp the MLP Handle
349 * @param addresses the address hashmap
350 * the address has to be already added from the hashmap
351 * @param address the address to update
354 GAS_mlp_address_update (void *solver,
355 struct GNUNET_CONTAINER_MultiHashMap * addresses,
356 struct ATS_Address *address);
360 * Deletes a single address in the MLP problem
362 * The MLP problem has to be recreated and the problem has to be resolved
364 * @param mlp the MLP Handle
365 * @param addresses the address hashmap
366 * the address has to be already removed from the hashmap
367 * @param address the address to delete
370 GAS_mlp_address_delete (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
374 * Changes the preferences for a peer in the MLP problem
376 * @param mlp the MLP Handle
377 * @param peer the peer
378 * @param kind the kind to change the preference
379 * @param score the score
382 GAS_mlp_address_change_preference (void *solver,
383 const struct GNUNET_PeerIdentity *peer,
384 enum GNUNET_ATS_PreferenceKind kind,
389 * Get the preferred address for a specific peer
391 * @param mlp the MLP Handle
392 * @param addresses address hashmap
393 * @param peer the peer
394 * @return suggested address
396 struct ATS_PreferedAddress *
397 GAS_mlp_get_preferred_address (void *solver,
398 struct GNUNET_CONTAINER_MultiHashMap * addresses,
399 const struct GNUNET_PeerIdentity *peer);
402 * Shutdown the MLP problem solving component
405 GAS_mlp_done (void *solver);
408 /* end of gnunet-service-ats_addresses_mlp.h */