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 MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3)
40 #define MLP_MAX_ITERATIONS INT_MAX
44 struct ATS_Peer *next;
45 struct ATS_Peer *prev;
47 struct GNUNET_PeerIdentity id;
49 /* Array of quality preferences */
50 double f_q[GNUNET_ATS_QualityPropertiesCount];
51 /* Legacy preference value */
54 /* constraint 2: 1 address per peer*/
57 /* constraint 9: relativity */
60 struct ATS_Address *head;
61 struct ATS_Address *tail;
72 struct GNUNET_STATISTICS_Handle *stats;
75 * GLPK (MLP) problem object
86 * GLPK LP control parameter
88 glp_smcp control_param_lp;
91 * GLPK LP control parameter
93 glp_iocp control_param_mlp;
96 * Solves the task in an regular interval
98 GNUNET_SCHEDULER_TaskIdentifier mlp_task;
101 * Interval between scheduled problem solving
103 struct GNUNET_TIME_Relative exec_interval;
106 * Maximum execution time per problem solving
108 struct GNUNET_TIME_Relative max_exec_duration;
111 * Maximum number of LP iterations per problem solving
113 unsigned int max_iterations;
116 * Solve the problem automatically when updates occur?
117 * Default: GNUNET_YES
118 * Can be disabled for test and measurements
122 /* state information */
125 * Do we need to use the LP presolver?
127 * If the problem addresses were added or removed and the last basis was we
128 * need to use the presolver.
129 * presolver_required == GNUNET_YES
131 * If values were modified, we can reuse a valid basis
132 * presolver_required == GNUNET_NO
134 int presolver_required;
139 * Time of last execution
141 struct GNUNET_TIME_Absolute last_execution;
145 * How often was the LP problem solved
147 unsigned int lp_solved;
150 * total duration of all lp solver executions
152 uint64_t lp_total_duration;
155 * How often was the MLP problem solved
157 unsigned int mlp_solved;
160 * total duration of all mlp solver executions
162 uint64_t mlp_total_duration;
164 unsigned int addr_in_problem;
166 /* Information about the problem */
168 struct ATS_Peer *peer_head;
169 struct ATS_Peer *peer_tail;
171 /* Number of peers */
174 /* current problem matrix */
175 /* row index array */
177 /* column index array */
179 /* column index array */
181 /* current size of the constraint matrix |indices| */
182 unsigned int cm_size;
185 /* Row index constraint 2: */
187 /* Row index constraint 4: minimum connections */
189 /* Row index constraint 6: maximize diversity */
191 /* Row index constraint 8: utilization*/
193 /* Row index constraint 9: relativity*/
196 /* column index Diversity (D) column */
200 /* column index Utilization (U) column */
204 /* column index Proportionality (R) column */
208 /* ATS Quality metrics
210 * array with GNUNET_ATS_QualityPropertiesCount elements
211 * contains mapping to GNUNET_ATS_Property*/
212 int q[GNUNET_ATS_QualityPropertiesCount];
214 /* column index quality metrics */
215 int c_q[GNUNET_ATS_QualityPropertiesCount];
217 /* column index quality metrics */
218 int r_q[GNUNET_ATS_QualityPropertiesCount];
220 /* quality metric coefficients*/
221 double co_Q[GNUNET_ATS_QualityPropertiesCount];
223 /* number of quality metrics */
226 /* ATS ressource costs
228 * array with GNUNET_ATS_QualityPropertiesCount elements
229 * contains mapping to GNUNET_ATS_Property*/
230 int rc[GNUNET_ATS_QualityPropertiesCount];
232 /* column index ressource costs */
233 int c_rc[GNUNET_ATS_QualityPropertiesCount];
235 /* ressource costs coefficients*/
236 double co_RC[GNUNET_ATS_QualityPropertiesCount];
238 /* number of quality metrics */
241 /* minimum bandwidth assigned to an address */
244 /* minimum number of addresses with bandwidth assigned */
250 * Address specific MLP information
252 struct MLP_information
258 /* bandwidth column index */
261 /* address usage column */
266 /* constraint 1: bandwidth capping */
269 /* constraint 3: minimum bandwidth */
272 /* Quality information row indices */
273 unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
275 /* Quality information column indices */
276 unsigned int c_q[GNUNET_ATS_QualityPropertiesCount];
278 /* Quality information */
279 double q[GNUNET_ATS_QualityPropertiesCount];
284 * Init the MLP problem solving component
286 * @param cfg configuration handle
287 * @param stats the GNUNET_STATISTICS handle
288 * @param max_duration maximum numbers of iterations for the LP/MLP Solver
289 * @param max_iterations maximum time limit for the LP/MLP Solver
290 * @return struct GAS_MLP_Handle * on success, NULL on fail
292 struct GAS_MLP_Handle *
293 GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
294 const struct GNUNET_STATISTICS_Handle *stats,
295 struct GNUNET_TIME_Relative max_duration,
296 unsigned int max_iterations);
299 * Solves the MLP problem on demand
301 * @param mlp the MLP Handle
302 * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
305 GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp);
309 * Updates a single address in the MLP problem
311 * If the address did not exist before in the problem:
312 * The MLP problem has to be recreated and the problem has to be resolved
314 * Otherwise the addresses' values can be updated and the existing base can
317 * @param mlp the MLP Handle
318 * @param addresses the address hashmap
319 * the address has to be already added from the hashmap
320 * @param address the address to update
323 GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
327 * Deletes a single address in the MLP problem
329 * The MLP problem has to be recreated and the problem has to be resolved
331 * @param mlp the MLP Handle
332 * @param addresses the address hashmap
333 * the address has to be already removed from the hashmap
334 * @param address the address to delete
337 GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
341 * Changes the preferences for a peer in the MLP problem
343 * @param mlp the MLP Handle
344 * @param peer the peer
345 * @param kind the kind to change the preference
346 * @param score the score
349 GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
350 const struct GNUNET_PeerIdentity *peer,
351 enum GNUNET_ATS_PreferenceKind kind,
356 * Get the preferred address for a specific peer
358 * @param mlp the MLP Handle
359 * @param peer the peer
360 * @return suggested address
363 GAS_mlp_get_preferred_address (struct GAS_MLP_Handle *mlp,
364 struct GNUNET_CONTAINER_MultiHashMap * addresses,
365 const struct GNUNET_PeerIdentity *peer);
368 * Shutdown the MLP problem solving component
374 /* end of gnunet-service-ats_addresses_mlp.h */