diff options
Diffstat (limited to 'src/ats/plugin_ats_mlp.c')
-rw-r--r-- | src/ats/plugin_ats_mlp.c | 2167 |
1 files changed, 2167 insertions, 0 deletions
diff --git a/src/ats/plugin_ats_mlp.c b/src/ats/plugin_ats_mlp.c new file mode 100644 index 000000000..0e6f60893 --- /dev/null +++ b/src/ats/plugin_ats_mlp.c | |||
@@ -0,0 +1,2167 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2011 Christian Grothoff (and other contributing authors) | ||
4 | |||
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. | ||
9 | |||
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. | ||
14 | |||
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. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file ats/plugin_ats_mlp.c | ||
23 | * @brief ats mlp problem solver | ||
24 | * @author Matthias Wachs | ||
25 | * @author Christian Grothoff | ||
26 | */ | ||
27 | |||
28 | #include "plugin_ats_mlp.h" | ||
29 | |||
30 | |||
31 | /** | ||
32 | * | ||
33 | * NOTE: Do not modify this documentation. This documentation is based on | ||
34 | * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex | ||
35 | * use build_txt.sh to generate plaintext output | ||
36 | * | ||
37 | * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby | ||
38 | * optimizing an mixed integer programming problem. The MLP solver uses a | ||
39 | * number of constraints to find the best adddress for a peer and an optimal | ||
40 | * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the | ||
41 | * MLP problem. | ||
42 | * | ||
43 | * We defined a constraint system to find an optimal bandwidth assignment. | ||
44 | * This constraint system uses as an input data addresses, bandwidth quotas, | ||
45 | * preferences and quality values. This constraint system is stored in an | ||
46 | * matrix based equotation system. | ||
47 | * | ||
48 | * 5 Using GLPK | ||
49 | * | ||
50 | * A (M)LP problem consists of a target function to optimizes, constraints | ||
51 | * and rows and columns. FIXME GLP uses three arrays to index the matrix: two | ||
52 | * integer arrays storing the row and column indices in the matrix and an | ||
53 | * float array to store the coeeficient. | ||
54 | * | ||
55 | * To solve the problem we first find an initial solution for the LP problem | ||
56 | * using the LP solver and then find an MLP solution based on this solution | ||
57 | * using the MLP solver. | ||
58 | * | ||
59 | * Solving (M)LP problems has the property that finding an initial solution | ||
60 | * for the LP problem is computationally expensive and finding the MLP | ||
61 | * solution is cheaper. This is especially interesting an existing LP | ||
62 | * solution can be reused if only coefficients in the matrix have changed | ||
63 | * (addresses updated). Only when the problem size changes (addresses added | ||
64 | * or deleted) a new LP solution has to be found. | ||
65 | * | ||
66 | * Intended usage | ||
67 | * The mlp solver solves the bandwidth assignment problem only on demand when | ||
68 | * an address suggestion is requested. When an address is requested mlp the | ||
69 | * solves the mlp problem and if the active address or the bandwidth assigned | ||
70 | * changes it calls the callback to addresses. The mlp solver gets notified | ||
71 | * about new addresses (adding sessions), removed addresses (address | ||
72 | * deletions) and address updates. To benefit from the mlp properties | ||
73 | * mentioned in section 5 the solver rembers if since the last solution | ||
74 | * addresses were added or deleted (problem size changed, problem has to be | ||
75 | * rebuild and solved from sratch) or if addresses were updated and the | ||
76 | * existing solution can be reused. | ||
77 | * | ||
78 | * 5.1 Input data | ||
79 | * | ||
80 | * The quotas for each network segment are passed by addresses. MLP can be | ||
81 | * adapted using configuration settings and uses the following parameters: | ||
82 | * * MLP_MAX_DURATION: | ||
83 | * Maximum duration for a MLP solution procees (default: 3 sec.) | ||
84 | * * MLP_MAX_DURATION: | ||
85 | * Maximum number of iterations for a MLP solution process (default: | ||
86 | * 1024) | ||
87 | * * MLP_MIN_CONNECTIONS: | ||
88 | * Minimum number of desired connections (default: 4) | ||
89 | * * MLP_MIN_BANDWIDTH: | ||
90 | * Minimum amount of bandwidth assigned to an address (default: 1024) | ||
91 | * * MLP_COEFFICIENT_D: | ||
92 | * Diversity coefficient (default: 1.0) | ||
93 | * * MLP_COEFFICIENT_R: | ||
94 | * Relativity coefficient (default: 1.0) | ||
95 | * * MLP_COEFFICIENT_U: | ||
96 | * Utilization coefficient (default: 1.0) | ||
97 | * * MLP_COEFFICIENT_D: | ||
98 | * Diversity coefficient (default: 1.0) | ||
99 | * * MLP_COEFFICIENT_QUALITY_DELAY: | ||
100 | * Quality delay coefficient (default: 1.0) | ||
101 | * * MLP_COEFFICIENT_QUALITY_DISTANCE: | ||
102 | * Quality distance coefficient (default: 1.0) | ||
103 | * * MLP_COEFFICIENT_QUALITY_DISTANCE: | ||
104 | * Quality distance coefficient (default: 1.0) | ||
105 | * * MLP_COEFFICIENT_QUALITY_DISTANCE: | ||
106 | * Quality distance coefficient (default: 1.0) | ||
107 | * * MLP_COEFFICIENT_QUALITY_DISTANCE: | ||
108 | * Quality distance coefficient (default: 1.0) | ||
109 | * | ||
110 | * 5.2 Data structures used | ||
111 | * | ||
112 | * mlp has for each known peer a struct ATS_Peer containing information about | ||
113 | * a specific peer. The address field solver_information contains information | ||
114 | * about the mlp properties of this address. | ||
115 | * | ||
116 | * 5.3 Initializing | ||
117 | * | ||
118 | * During initialization mlp initializes the GLPK libray used to solve the | ||
119 | * MLP problem: it initializes the glpk environment and creates an initial LP | ||
120 | * problem. Next it loads the configuration values from the configuration or | ||
121 | * uses the default values configured in -addresses_mlp.h. The quotas used | ||
122 | * are given by addresses but may have to be adjusted. mlp uses a upper limit | ||
123 | * for the bandwidth assigned called BIG M and a minimum amount of bandwidth | ||
124 | * an address gets assigned as well as a minium desired number of | ||
125 | * connections. If the configured quota is bigger than BIG M, it is reduced | ||
126 | * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS | ||
127 | * *MLP_MIN_BANDWIDTH it is increased to this value. | ||
128 | * | ||
129 | * 5.4 Shutdown | ||
130 | |||
131 | */ | ||
132 | |||
133 | #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__) | ||
134 | |||
135 | /** | ||
136 | * Print debug output for mlp problem creation | ||
137 | */ | ||
138 | #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO | ||
139 | |||
140 | /** | ||
141 | * Enable GLPK verbose output | ||
142 | */ | ||
143 | #define VERBOSE_GLPK GNUNET_NO | ||
144 | |||
145 | /** | ||
146 | * Maximize bandwidth assigned | ||
147 | * | ||
148 | * This option can be used to test if problem can be solved at all without | ||
149 | * optimizing for utility, diversity or relativity | ||
150 | * | ||
151 | */ | ||
152 | #define MAXIMIZE_FOR_BANDWIDTH_ASSIGNED GNUNET_NO | ||
153 | |||
154 | /** | ||
155 | * Intercept GLPK terminal output | ||
156 | * @param info the mlp handle | ||
157 | * @param s the string to print | ||
158 | * @return 0: glpk prints output on terminal, 0 != surpress output | ||
159 | */ | ||
160 | static int | ||
161 | mlp_term_hook (void *info, const char *s) | ||
162 | { | ||
163 | /* Not needed atm struct MLP_information *mlp = info; */ | ||
164 | LOG (GNUNET_ERROR_TYPE_DEBUG, "%s", s); | ||
165 | return 1; | ||
166 | } | ||
167 | |||
168 | |||
169 | /** | ||
170 | * Reset peers for next problem creation | ||
171 | * | ||
172 | * @param cls not used | ||
173 | * @param key the key | ||
174 | * @param value ATS_Peer | ||
175 | * @return GNUNET_OK | ||
176 | */ | ||
177 | static int | ||
178 | reset_peers (void *cls, | ||
179 | const struct GNUNET_PeerIdentity *key, | ||
180 | void *value) | ||
181 | { | ||
182 | struct ATS_Peer *peer = value; | ||
183 | peer->processed = GNUNET_NO; | ||
184 | return GNUNET_OK; | ||
185 | } | ||
186 | |||
187 | /** | ||
188 | * Delete the MLP problem and free the constrain matrix | ||
189 | * | ||
190 | * @param mlp the MLP handle | ||
191 | */ | ||
192 | static void | ||
193 | mlp_delete_problem (struct GAS_MLP_Handle *mlp) | ||
194 | { | ||
195 | int c; | ||
196 | if (mlp == NULL) | ||
197 | return; | ||
198 | if (mlp->p.prob != NULL) | ||
199 | { | ||
200 | glp_delete_prob(mlp->p.prob); | ||
201 | mlp->p.prob = NULL; | ||
202 | } | ||
203 | |||
204 | /* delete row index */ | ||
205 | if (mlp->p.ia != NULL) | ||
206 | { | ||
207 | GNUNET_free (mlp->p.ia); | ||
208 | mlp->p.ia = NULL; | ||
209 | } | ||
210 | |||
211 | /* delete column index */ | ||
212 | if (mlp->p.ja != NULL) | ||
213 | { | ||
214 | GNUNET_free (mlp->p.ja); | ||
215 | mlp->p.ja = NULL; | ||
216 | } | ||
217 | |||
218 | /* delete coefficients */ | ||
219 | if (mlp->p.ar != NULL) | ||
220 | { | ||
221 | GNUNET_free (mlp->p.ar); | ||
222 | mlp->p.ar = NULL; | ||
223 | } | ||
224 | mlp->p.ci = 0; | ||
225 | mlp->p.prob = NULL; | ||
226 | |||
227 | mlp->p.c_d = MLP_UNDEFINED; | ||
228 | mlp->p.c_r = MLP_UNDEFINED; | ||
229 | mlp->p.r_c2 = MLP_UNDEFINED; | ||
230 | mlp->p.r_c4 = MLP_UNDEFINED; | ||
231 | mlp->p.r_c6 = MLP_UNDEFINED; | ||
232 | mlp->p.r_c9 = MLP_UNDEFINED; | ||
233 | for (c = 0; c < mlp->pv.m_q ; c ++) | ||
234 | mlp->p.r_q[c] = MLP_UNDEFINED; | ||
235 | for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++) | ||
236 | mlp->p.r_quota[c] = MLP_UNDEFINED; | ||
237 | mlp->p.ci = MLP_UNDEFINED; | ||
238 | |||
239 | |||
240 | GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers, | ||
241 | &reset_peers, NULL); | ||
242 | } | ||
243 | |||
244 | |||
245 | /** | ||
246 | * Translate ATS properties to text | ||
247 | * Just intended for debugging | ||
248 | * | ||
249 | * @param ats_index the ATS index | ||
250 | * @return string with result | ||
251 | */ | ||
252 | const char * | ||
253 | mlp_ats_to_string (int ats_index) | ||
254 | { | ||
255 | switch (ats_index) { | ||
256 | case GNUNET_ATS_ARRAY_TERMINATOR: | ||
257 | return "GNUNET_ATS_ARRAY_TERMINATOR"; | ||
258 | case GNUNET_ATS_UTILIZATION_OUT: | ||
259 | return "GNUNET_ATS_UTILIZATION_OUT"; | ||
260 | case GNUNET_ATS_UTILIZATION_IN: | ||
261 | return "GNUNET_ATS_UTILIZATION_IN"; | ||
262 | case GNUNET_ATS_UTILIZATION_PAYLOAD_OUT: | ||
263 | return "GNUNET_ATS_UTILIZATION_PAYLOAD_OUT"; | ||
264 | case GNUNET_ATS_UTILIZATION_PAYLOAD_IN: | ||
265 | return "GNUNET_ATS_UTILIZATION_PAYLOAD_IN"; | ||
266 | case GNUNET_ATS_COST_LAN: | ||
267 | return "GNUNET_ATS_COST_LAN"; | ||
268 | case GNUNET_ATS_COST_WAN: | ||
269 | return "GNUNET_ATS_COST_LAN"; | ||
270 | case GNUNET_ATS_COST_WLAN: | ||
271 | return "GNUNET_ATS_COST_WLAN"; | ||
272 | case GNUNET_ATS_NETWORK_TYPE: | ||
273 | return "GNUNET_ATS_NETWORK_TYPE"; | ||
274 | case GNUNET_ATS_QUALITY_NET_DELAY: | ||
275 | return "GNUNET_ATS_QUALITY_NET_DELAY"; | ||
276 | case GNUNET_ATS_QUALITY_NET_DISTANCE: | ||
277 | return "GNUNET_ATS_QUALITY_NET_DISTANCE"; | ||
278 | default: | ||
279 | GNUNET_break (0); | ||
280 | return "unknown"; | ||
281 | } | ||
282 | } | ||
283 | |||
284 | /** | ||
285 | * Translate glpk status error codes to text | ||
286 | * @param retcode return code | ||
287 | * @return string with result | ||
288 | */ | ||
289 | const char * | ||
290 | mlp_status_to_string (int retcode) | ||
291 | { | ||
292 | switch (retcode) { | ||
293 | case GLP_UNDEF: | ||
294 | return "solution is undefined"; | ||
295 | case GLP_FEAS: | ||
296 | return "solution is feasible"; | ||
297 | case GLP_INFEAS: | ||
298 | return "solution is infeasible"; | ||
299 | case GLP_NOFEAS: | ||
300 | return "no feasible solution exists"; | ||
301 | case GLP_OPT: | ||
302 | return "solution is optimal"; | ||
303 | case GLP_UNBND: | ||
304 | return "solution is unbounded"; | ||
305 | default: | ||
306 | GNUNET_break (0); | ||
307 | return "unknown error"; | ||
308 | } | ||
309 | } | ||
310 | |||
311 | /** | ||
312 | * Translate glpk solver error codes to text | ||
313 | * @param retcode return code | ||
314 | * @return string with result | ||
315 | */ | ||
316 | const char * | ||
317 | mlp_solve_to_string (int retcode) | ||
318 | { | ||
319 | switch (retcode) { | ||
320 | case 0: | ||
321 | return "ok"; | ||
322 | case GLP_EBADB: | ||
323 | return "invalid basis"; | ||
324 | case GLP_ESING: | ||
325 | return "singular matrix"; | ||
326 | case GLP_ECOND: | ||
327 | return "ill-conditioned matrix"; | ||
328 | case GLP_EBOUND: | ||
329 | return "invalid bounds"; | ||
330 | case GLP_EFAIL: | ||
331 | return "solver failed"; | ||
332 | case GLP_EOBJLL: | ||
333 | return "objective lower limit reached"; | ||
334 | case GLP_EOBJUL: | ||
335 | return "objective upper limit reached"; | ||
336 | case GLP_EITLIM: | ||
337 | return "iteration limit exceeded"; | ||
338 | case GLP_ETMLIM: | ||
339 | return "time limit exceeded"; | ||
340 | case GLP_ENOPFS: | ||
341 | return "no primal feasible solution"; | ||
342 | case GLP_ENODFS: | ||
343 | return "no dual feasible solution"; | ||
344 | case GLP_EROOT: | ||
345 | return "root LP optimum not provided"; | ||
346 | case GLP_ESTOP: | ||
347 | return "search terminated by application"; | ||
348 | case GLP_EMIPGAP: | ||
349 | return "relative mip gap tolerance reached"; | ||
350 | case GLP_ENOFEAS: | ||
351 | return "no dual feasible solution"; | ||
352 | case GLP_ENOCVG: | ||
353 | return "no convergence"; | ||
354 | case GLP_EINSTAB: | ||
355 | return "numerical instability"; | ||
356 | case GLP_EDATA: | ||
357 | return "invalid data"; | ||
358 | case GLP_ERANGE: | ||
359 | return "result out of range"; | ||
360 | default: | ||
361 | GNUNET_break (0); | ||
362 | return "unknown error"; | ||
363 | } | ||
364 | } | ||
365 | |||
366 | /** | ||
367 | * Extract an ATS performance info from an address | ||
368 | * | ||
369 | * @param address the address | ||
370 | * @param type the type to extract in HBO | ||
371 | * @return the value in HBO or GNUNET_ATS_VALUE_UNDEFINED in HBO if value does not exist | ||
372 | */ | ||
373 | static int | ||
374 | get_performance_info (struct ATS_Address *address, uint32_t type) | ||
375 | { | ||
376 | int c1; | ||
377 | GNUNET_assert (NULL != address); | ||
378 | |||
379 | if ((NULL == address->atsi) || (0 == address->atsi_count)) | ||
380 | return GNUNET_ATS_VALUE_UNDEFINED; | ||
381 | |||
382 | for (c1 = 0; c1 < address->atsi_count; c1++) | ||
383 | { | ||
384 | if (ntohl(address->atsi[c1].type) == type) | ||
385 | return ntohl(address->atsi[c1].value); | ||
386 | } | ||
387 | return GNUNET_ATS_VALUE_UNDEFINED; | ||
388 | } | ||
389 | |||
390 | |||
391 | struct CountContext | ||
392 | { | ||
393 | const struct GNUNET_CONTAINER_MultiPeerMap *peers; | ||
394 | int result; | ||
395 | }; | ||
396 | |||
397 | static int | ||
398 | mlp_create_problem_count_addresses_it (void *cls, | ||
399 | const struct GNUNET_PeerIdentity *key, | ||
400 | void *value) | ||
401 | { | ||
402 | struct CountContext *cctx = cls; | ||
403 | |||
404 | /* Check if we have to add this peer due to a pending request */ | ||
405 | if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->peers, key)) | ||
406 | cctx->result++; | ||
407 | return GNUNET_OK; | ||
408 | } | ||
409 | |||
410 | |||
411 | static int | ||
412 | mlp_create_problem_count_addresses (const struct GNUNET_CONTAINER_MultiPeerMap *peers, | ||
413 | const struct GNUNET_CONTAINER_MultiPeerMap *addresses) | ||
414 | { | ||
415 | struct CountContext cctx; | ||
416 | |||
417 | cctx.peers = peers; | ||
418 | cctx.result = 0; | ||
419 | GNUNET_CONTAINER_multipeermap_iterate (addresses, | ||
420 | &mlp_create_problem_count_addresses_it, &cctx); | ||
421 | return cctx.result; | ||
422 | } | ||
423 | |||
424 | |||
425 | /** | ||
426 | * Updates an existing value in the matrix | ||
427 | * | ||
428 | * Extract the row, updates the value and updates the row in the problem | ||
429 | * | ||
430 | * @param p the mlp problem | ||
431 | * @param row the row to create the value in | ||
432 | * @param col the column to create the value in | ||
433 | * @param val the value to set | ||
434 | * @param line calling line for debbuging | ||
435 | * @return GNUNET_YES value changed, GNUNET_NO value did not change, GNUNET_SYSERR | ||
436 | * on error | ||
437 | */ | ||
438 | static int | ||
439 | mlp_create_problem_update_value (struct MLP_Problem *p, | ||
440 | int row, int col, double val, | ||
441 | int line) | ||
442 | { | ||
443 | int c_cols; | ||
444 | int c_elems; | ||
445 | int c1; | ||
446 | int res; | ||
447 | int found; | ||
448 | double *val_array; | ||
449 | int *ind_array; | ||
450 | |||
451 | GNUNET_assert (NULL != p); | ||
452 | GNUNET_assert (NULL != p->prob); | ||
453 | |||
454 | /* Get number of columns and prepare data structure */ | ||
455 | c_cols = glp_get_num_cols(p->prob); | ||
456 | if (0 >= c_cols) | ||
457 | return GNUNET_SYSERR; | ||
458 | |||
459 | val_array = GNUNET_malloc ((c_cols +1)* sizeof (double)); | ||
460 | GNUNET_assert (NULL != val_array); | ||
461 | ind_array = GNUNET_malloc ((c_cols+1) * sizeof (int)); | ||
462 | GNUNET_assert (NULL != ind_array); | ||
463 | /* Extract the row */ | ||
464 | |||
465 | /* Update the value */ | ||
466 | c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array); | ||
467 | found = GNUNET_NO; | ||
468 | for (c1 = 1; c1 < (c_elems+1); c1++) | ||
469 | { | ||
470 | if (ind_array[c1] == col) | ||
471 | { | ||
472 | found = GNUNET_YES; | ||
473 | break; | ||
474 | } | ||
475 | } | ||
476 | if (GNUNET_NO == found) | ||
477 | { | ||
478 | ind_array[c_elems+1] = col; | ||
479 | val_array[c_elems+1] = val; | ||
480 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n", | ||
481 | glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col), | ||
482 | val); | ||
483 | glp_set_mat_row (p->prob, row, c_elems+1, ind_array, val_array); | ||
484 | GNUNET_free (ind_array); | ||
485 | GNUNET_free (val_array); | ||
486 | return GNUNET_YES; | ||
487 | } | ||
488 | else | ||
489 | { | ||
490 | /* Update value */ | ||
491 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n", | ||
492 | glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col), | ||
493 | val_array[c1], val); | ||
494 | if (val != val_array[c1]) | ||
495 | res = GNUNET_YES; | ||
496 | else | ||
497 | res = GNUNET_NO; | ||
498 | val_array[c1] = val; | ||
499 | /* Update the row in the matrix */ | ||
500 | glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array); | ||
501 | } | ||
502 | |||
503 | GNUNET_free (ind_array); | ||
504 | GNUNET_free (val_array); | ||
505 | return res; | ||
506 | } | ||
507 | |||
508 | /** | ||
509 | * Creates a new value in the matrix | ||
510 | * | ||
511 | * Sets the row and column index in the problem array and increments the | ||
512 | * position field | ||
513 | * | ||
514 | * @param p the mlp problem | ||
515 | * @param row the row to create the value in | ||
516 | * @param col the column to create the value in | ||
517 | * @param val the value to set | ||
518 | * @param line calling line for debbuging | ||
519 | */ | ||
520 | static void | ||
521 | mlp_create_problem_set_value (struct MLP_Problem *p, | ||
522 | int row, int col, double val, | ||
523 | int line) | ||
524 | { | ||
525 | if ((p->ci) >= p->num_elements) | ||
526 | { | ||
527 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n", | ||
528 | line, p->ci + 1, p->num_elements); | ||
529 | GNUNET_break (0); | ||
530 | return; | ||
531 | } | ||
532 | if ((0 == row) || (0 == col)) | ||
533 | GNUNET_break (0); | ||
534 | p->ia[p->ci] = row ; | ||
535 | p->ja[p->ci] = col; | ||
536 | p->ar[p->ci] = val; | ||
537 | #if DEBUG_MLP_PROBLEM_CREATION | ||
538 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n", | ||
539 | line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]); | ||
540 | #endif | ||
541 | p->ci++; | ||
542 | } | ||
543 | |||
544 | static int | ||
545 | mlp_create_problem_create_column (struct MLP_Problem *p, char *name, | ||
546 | unsigned int type, unsigned int bound, double lb, double ub, | ||
547 | double coef) | ||
548 | { | ||
549 | int col = glp_add_cols (p->prob, 1); | ||
550 | glp_set_col_name (p->prob, col, name); | ||
551 | glp_set_col_bnds (p->prob, col, bound, lb, ub); | ||
552 | glp_set_col_kind (p->prob, col, type); | ||
553 | glp_set_obj_coef (p->prob, col, coef); | ||
554 | #if DEBUG_MLP_PROBLEM_CREATION | ||
555 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n", | ||
556 | col, name, coef); | ||
557 | #endif | ||
558 | return col; | ||
559 | } | ||
560 | |||
561 | static int | ||
562 | mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name, | ||
563 | unsigned int bound, double lb, double ub) | ||
564 | { | ||
565 | char * op; | ||
566 | int row = glp_add_rows (p->prob, 1); | ||
567 | /* set row name */ | ||
568 | glp_set_row_name (p->prob, row, name); | ||
569 | /* set row bounds: <= 0 */ | ||
570 | glp_set_row_bnds (p->prob, row, bound, lb, ub); | ||
571 | switch (bound) | ||
572 | { | ||
573 | case GLP_UP: | ||
574 | GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub); | ||
575 | break; | ||
576 | case GLP_DB: | ||
577 | GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub); | ||
578 | break; | ||
579 | case GLP_FX: | ||
580 | GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub); | ||
581 | break; | ||
582 | case GLP_LO: | ||
583 | GNUNET_asprintf(&op, "%.2f <= x <= inf", lb); | ||
584 | break; | ||
585 | default: | ||
586 | GNUNET_asprintf(&op, "ERROR"); | ||
587 | break; | ||
588 | } | ||
589 | #if DEBUG_MLP_PROBLEM_CREATION | ||
590 | LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n", | ||
591 | row, name, op); | ||
592 | #endif | ||
593 | GNUNET_free (op); | ||
594 | return row; | ||
595 | } | ||
596 | |||
597 | /** | ||
598 | * Create the | ||
599 | * - address columns b and n | ||
600 | * - address dependent constraint rows c1, c3 | ||
601 | * - peer dependent rows c2 and c9 | ||
602 | * - Set address dependent entries in problem matrix as well | ||
603 | */ | ||
604 | static int | ||
605 | mlp_create_problem_add_address_information (void *cls, | ||
606 | const struct GNUNET_PeerIdentity *key, | ||
607 | void *value) | ||
608 | { | ||
609 | struct GAS_MLP_Handle *mlp = cls; | ||
610 | struct MLP_Problem *p = &mlp->p; | ||
611 | struct ATS_Address *address = value; | ||
612 | struct ATS_Peer *peer; | ||
613 | struct MLP_information *mlpi; | ||
614 | char *name; | ||
615 | const double *props; | ||
616 | uint32_t addr_net; | ||
617 | int c; | ||
618 | |||
619 | /* Check if we have to add this peer due to a pending request */ | ||
620 | if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(mlp->requested_peers, key)) | ||
621 | return GNUNET_OK; | ||
622 | |||
623 | mlpi = address->solver_information; | ||
624 | if (NULL == mlpi) | ||
625 | { | ||
626 | fprintf (stderr, "%s %p\n",GNUNET_i2s (&address->peer), address); | ||
627 | GNUNET_break (0); | ||
628 | return GNUNET_OK; | ||
629 | } | ||
630 | |||
631 | /* Get peer */ | ||
632 | peer = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, key); | ||
633 | if (peer->processed == GNUNET_NO) | ||
634 | { | ||
635 | /* Add peer dependent constraints */ | ||
636 | /* Add constraint c2 */ | ||
637 | GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer)); | ||
638 | peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0); | ||
639 | GNUNET_free (name); | ||
640 | /* Add constraint c9 */ | ||
641 | GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer)); | ||
642 | peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0); | ||
643 | GNUNET_free (name); | ||
644 | /* c 9) set coefficient */ | ||
645 | mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f, __LINE__); | ||
646 | peer->processed = GNUNET_YES; | ||
647 | } | ||
648 | |||
649 | /* Reset addresses' solver information */ | ||
650 | mlpi->c_b = 0; | ||
651 | mlpi->c_n = 0; | ||
652 | mlpi->n = 0; | ||
653 | mlpi->r_c1 = 0; | ||
654 | mlpi->r_c3 = 0; | ||
655 | |||
656 | /* Add bandwidth column */ | ||
657 | GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address); | ||
658 | #if TEST_MAX_BW_ASSIGNMENT | ||
659 | mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0); | ||
660 | #else | ||
661 | mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0); | ||
662 | #endif | ||
663 | |||
664 | GNUNET_free (name); | ||
665 | |||
666 | /* Add usage column */ | ||
667 | GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address); | ||
668 | mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0); | ||
669 | GNUNET_free (name); | ||
670 | |||
671 | /* Add address dependent constraints */ | ||
672 | /* Add constraint c1) bandwidth capping | ||
673 | * b_t + (-M) * n_t <= 0 | ||
674 | * */ | ||
675 | GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address); | ||
676 | mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0); | ||
677 | GNUNET_free (name); | ||
678 | |||
679 | /* c1) set b = 1 coefficient */ | ||
680 | mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__); | ||
681 | /* c1) set n = -M coefficient */ | ||
682 | mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -mlp->pv.BIG_M, __LINE__); | ||
683 | |||
684 | /* Add constraint c 3) minimum bandwidth | ||
685 | * b_t + (-n_t * b_min) >= 0 | ||
686 | * */ | ||
687 | GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address); | ||
688 | mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0); | ||
689 | GNUNET_free (name); | ||
690 | |||
691 | /* c3) set b = 1 coefficient */ | ||
692 | mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__); | ||
693 | /* c3) set n = -b_min coefficient */ | ||
694 | mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__); | ||
695 | |||
696 | |||
697 | /* Set coefficient entries in invariant rows */ | ||
698 | /* c 4) minimum connections */ | ||
699 | mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__); | ||
700 | /* c 6) maximize diversity */ | ||
701 | mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__); | ||
702 | /* c 2) 1 address peer peer */ | ||
703 | mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__); | ||
704 | /* c 9) relativity */ | ||
705 | mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__); | ||
706 | /* c 8) utility */ | ||
707 | mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__); | ||
708 | |||
709 | /* c 10) obey network specific quotas | ||
710 | * (1)*b_1 + ... + (1)*b_m <= quota_n | ||
711 | */ | ||
712 | for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) | ||
713 | { | ||
714 | addr_net = get_performance_info (address, GNUNET_ATS_NETWORK_TYPE); | ||
715 | if (GNUNET_ATS_VALUE_UNDEFINED == addr_net) | ||
716 | addr_net = GNUNET_ATS_NET_UNSPECIFIED; | ||
717 | |||
718 | if (mlp->pv.quota_index[c] == addr_net) | ||
719 | { | ||
720 | mlp_create_problem_set_value (p, p->r_quota[c], mlpi->c_b, 1, __LINE__); | ||
721 | break; | ||
722 | } | ||
723 | } | ||
724 | |||
725 | /* c 7) Optimize quality */ | ||
726 | /* For all quality metrics, set quality of this address */ | ||
727 | props = mlp->get_properties (mlp->get_properties_cls, address); | ||
728 | for (c = 0; c < mlp->pv.m_q; c++) | ||
729 | mlp_create_problem_set_value (p, p->r_q[c], mlpi->c_b, props[c], __LINE__); | ||
730 | |||
731 | return GNUNET_OK; | ||
732 | } | ||
733 | |||
734 | /** | ||
735 | * Create the invariant columns c4, c6, c10, c8, c7 | ||
736 | */ | ||
737 | static void | ||
738 | mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p) | ||
739 | { | ||
740 | char *name; | ||
741 | int c; | ||
742 | |||
743 | /* Row for c4) minimum connection */ | ||
744 | /* Number of minimum connections is min(|Peers|, n_min) */ | ||
745 | p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0); | ||
746 | |||
747 | /* Add row for c6) */ | ||
748 | p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0); | ||
749 | /* c6 )Setting -D */ | ||
750 | mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__); | ||
751 | |||
752 | /* Add rows for c 10) */ | ||
753 | for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) | ||
754 | { | ||
755 | char * text; | ||
756 | GNUNET_asprintf(&text, "c10_quota_ats_%s", | ||
757 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c])); | ||
758 | p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]); | ||
759 | GNUNET_free (text); | ||
760 | } | ||
761 | |||
762 | /* Adding rows for c 8) */ | ||
763 | p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0); | ||
764 | /* -u */ | ||
765 | mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__); | ||
766 | |||
767 | /* c 7) For all quality metrics */ | ||
768 | for (c = 0; c < mlp->pv.m_q; c++) | ||
769 | { | ||
770 | GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c])); | ||
771 | p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0); | ||
772 | GNUNET_free (name); | ||
773 | mlp_create_problem_set_value (p, p->r_q[c], p->c_q[c], -1, __LINE__); | ||
774 | } | ||
775 | } | ||
776 | |||
777 | |||
778 | /** | ||
779 | * Create the invariant columns d, u, r, q0 ... qm | ||
780 | */ | ||
781 | static void | ||
782 | mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p) | ||
783 | { | ||
784 | char *name; | ||
785 | int c; | ||
786 | |||
787 | #if TEST_MAX_BW_ASSIGNMENT | ||
788 | mlp->pv.co_D = 0.0; | ||
789 | mlp->pv.co_U = 0.0; | ||
790 | |||
791 | #endif | ||
792 | //mlp->pv.co_R = 0.0; | ||
793 | |||
794 | /* Diversity d column */ | ||
795 | p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D); | ||
796 | |||
797 | /* Utilization u column */ | ||
798 | p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U); | ||
799 | |||
800 | /* Relativity r column */ | ||
801 | p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R); | ||
802 | |||
803 | /* Quality metric columns */ | ||
804 | for (c = 0; c < mlp->pv.m_q; c++) | ||
805 | { | ||
806 | GNUNET_asprintf (&name, "q_%u", mlp->pv.q[c]); | ||
807 | #if TEST_MAX_BW_ASSIGNMENT | ||
808 | p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0); | ||
809 | #else | ||
810 | p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]); | ||
811 | #endif | ||
812 | GNUNET_free (name); | ||
813 | } | ||
814 | } | ||
815 | |||
816 | |||
817 | /** | ||
818 | * Create the MLP problem | ||
819 | * | ||
820 | * @param mlp the MLP handle | ||
821 | * @return GNUNET_OK or GNUNET_SYSERR | ||
822 | */ | ||
823 | static int | ||
824 | mlp_create_problem (struct GAS_MLP_Handle *mlp) | ||
825 | { | ||
826 | struct MLP_Problem *p = &mlp->p; | ||
827 | int res = GNUNET_OK; | ||
828 | |||
829 | GNUNET_assert (p->prob == NULL); | ||
830 | GNUNET_assert (p->ia == NULL); | ||
831 | GNUNET_assert (p->ja == NULL); | ||
832 | GNUNET_assert (p->ar == NULL); | ||
833 | /* Reset MLP problem struct */ | ||
834 | |||
835 | /* create the glpk problem */ | ||
836 | p->prob = glp_create_prob (); | ||
837 | GNUNET_assert (NULL != p->prob); | ||
838 | p->num_peers = GNUNET_CONTAINER_multipeermap_size (mlp->requested_peers); | ||
839 | p->num_addresses = mlp_create_problem_count_addresses (mlp->requested_peers, mlp->addresses); | ||
840 | |||
841 | /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */ | ||
842 | p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses + | ||
843 | mlp->pv.m_q + p->num_peers + 2 + 1); | ||
844 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
845 | "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n", | ||
846 | p->num_peers, | ||
847 | p->num_addresses, | ||
848 | mlp->pv.m_q, | ||
849 | p->num_elements); | ||
850 | |||
851 | /* Set a problem name */ | ||
852 | glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution"); | ||
853 | /* Set optimization direction to maximize */ | ||
854 | glp_set_obj_dir (p->prob, GLP_MAX); | ||
855 | |||
856 | /* Create problem matrix */ | ||
857 | /* last +1 caused by glpk index starting with one: [1..elements]*/ | ||
858 | p->ci = 1; | ||
859 | /* row index */ | ||
860 | p->ia = GNUNET_malloc (p->num_elements * sizeof (int)); | ||
861 | /* column index */ | ||
862 | p->ja = GNUNET_malloc (p->num_elements * sizeof (int)); | ||
863 | /* coefficient */ | ||
864 | p->ar = GNUNET_malloc (p->num_elements * sizeof (double)); | ||
865 | |||
866 | if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar)) | ||
867 | { | ||
868 | LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n")); | ||
869 | return GNUNET_SYSERR; | ||
870 | } | ||
871 | |||
872 | /* Adding invariant columns */ | ||
873 | mlp_create_problem_add_invariant_columns (mlp, p); | ||
874 | |||
875 | /* Adding address independent constraint rows */ | ||
876 | mlp_create_problem_add_invariant_rows (mlp, p); | ||
877 | |||
878 | /* Adding address dependent columns constraint rows */ | ||
879 | GNUNET_CONTAINER_multipeermap_iterate (mlp->addresses, | ||
880 | &mlp_create_problem_add_address_information, | ||
881 | mlp); | ||
882 | |||
883 | /* Load the matrix */ | ||
884 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n"); | ||
885 | glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar); | ||
886 | |||
887 | return res; | ||
888 | } | ||
889 | |||
890 | /** | ||
891 | * Solves the LP problem | ||
892 | * | ||
893 | * @param mlp the MLP Handle | ||
894 | * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure | ||
895 | */ | ||
896 | static int | ||
897 | mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp) | ||
898 | { | ||
899 | int res = 0; | ||
900 | |||
901 | res = glp_simplex(mlp->p.prob, &mlp->control_param_lp); | ||
902 | if (0 == res) | ||
903 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", res, mlp_solve_to_string(res)); | ||
904 | else | ||
905 | LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res)); | ||
906 | |||
907 | /* Analyze problem status */ | ||
908 | res = glp_get_status (mlp->p.prob); | ||
909 | switch (res) { | ||
910 | /* solution is optimal */ | ||
911 | case GLP_OPT: | ||
912 | /* solution is feasible */ | ||
913 | case GLP_FEAS: | ||
914 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: 0x%02X %s\n", | ||
915 | res, mlp_status_to_string(res)); | ||
916 | return GNUNET_OK; | ||
917 | /* Problem was ill-defined, no way to handle that */ | ||
918 | default: | ||
919 | LOG (GNUNET_ERROR_TYPE_WARNING, "Solving LP problem failed, no solution: 0x%02X %s\n", | ||
920 | res, mlp_status_to_string(res)); | ||
921 | return GNUNET_SYSERR; | ||
922 | } | ||
923 | } | ||
924 | |||
925 | |||
926 | /** | ||
927 | * Solves the MLP problem | ||
928 | * | ||
929 | * @param mlp the MLP Handle | ||
930 | * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure | ||
931 | */ | ||
932 | int | ||
933 | mlp_solve_mlp_problem (struct GAS_MLP_Handle *mlp) | ||
934 | { | ||
935 | int res = 0; | ||
936 | res = glp_intopt(mlp->p.prob, &mlp->control_param_mlp); | ||
937 | if (0 == res) | ||
938 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_solve_to_string(res)); | ||
939 | else | ||
940 | LOG (GNUNET_ERROR_TYPE_WARNING, "Solving MLP problem failed: 0x%02X %s\n", res, mlp_solve_to_string(res)); | ||
941 | /* Analyze problem status */ | ||
942 | res = glp_mip_status(mlp->p.prob); | ||
943 | switch (res) { | ||
944 | /* solution is optimal */ | ||
945 | case GLP_OPT: | ||
946 | /* solution is feasible */ | ||
947 | case GLP_FEAS: | ||
948 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving MLP problem: 0x%02X %s\n", res, mlp_status_to_string(res)); | ||
949 | return GNUNET_OK; | ||
950 | /* Problem was ill-defined, no way to handle that */ | ||
951 | default: | ||
952 | LOG (GNUNET_ERROR_TYPE_WARNING,"Solving MLP problem failed, 0x%02X %s\n\n", res, mlp_status_to_string(res)); | ||
953 | return GNUNET_SYSERR; | ||
954 | } | ||
955 | } | ||
956 | |||
957 | /** | ||
958 | * Propagates the results when MLP problem was solved | ||
959 | * | ||
960 | * @param cls the MLP handle | ||
961 | * @param key the peer identity | ||
962 | * @param value the address | ||
963 | * @return #GNUNET_OK to continue | ||
964 | */ | ||
965 | int | ||
966 | mlp_propagate_results (void *cls, | ||
967 | const struct GNUNET_PeerIdentity *key, | ||
968 | void *value) | ||
969 | { | ||
970 | struct GAS_MLP_Handle *mlp = cls; | ||
971 | struct ATS_Address *address; | ||
972 | struct MLP_information *mlpi; | ||
973 | double mlp_bw_in = MLP_NaN; | ||
974 | double mlp_bw_out = MLP_NaN; | ||
975 | double mlp_use = MLP_NaN; | ||
976 | |||
977 | /* Check if we have to add this peer due to a pending request */ | ||
978 | if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers, | ||
979 | key)) | ||
980 | { | ||
981 | return GNUNET_OK; | ||
982 | } | ||
983 | address = value; | ||
984 | GNUNET_assert (address->solver_information != NULL); | ||
985 | mlpi = address->solver_information; | ||
986 | |||
987 | mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */ | ||
988 | if (mlp_bw_in > (double) UINT32_MAX) | ||
989 | { | ||
990 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" ); | ||
991 | mlp_bw_in = (double) UINT32_MAX; | ||
992 | } | ||
993 | mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b); | ||
994 | if (mlp_bw_out > (double) UINT32_MAX) | ||
995 | { | ||
996 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" ); | ||
997 | mlp_bw_out = (double) UINT32_MAX; | ||
998 | } | ||
999 | mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n); | ||
1000 | |||
1001 | /* | ||
1002 | * Debug: solution | ||
1003 | * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %f\n", | ||
1004 | * GNUNET_i2s(&address->peer), address->plugin, | ||
1005 | * address->addr_len, address->session_id); | ||
1006 | */ | ||
1007 | |||
1008 | if (GLP_YES == mlp_use) | ||
1009 | { | ||
1010 | /* This address was selected by the solver to be used */ | ||
1011 | mlpi->n = GNUNET_YES; | ||
1012 | if (GNUNET_NO == address->active) | ||
1013 | { | ||
1014 | /* Address was not used before, enabling address */ | ||
1015 | LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n", | ||
1016 | (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); | ||
1017 | address->active = GNUNET_YES; | ||
1018 | address->assigned_bw_in.value__ = htonl (mlp_bw_in); | ||
1019 | mlpi->b_in.value__ = htonl(mlp_bw_in); | ||
1020 | address->assigned_bw_out.value__ = htonl (mlp_bw_out); | ||
1021 | mlpi->b_out.value__ = htonl(mlp_bw_out); | ||
1022 | if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer)))) | ||
1023 | mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); | ||
1024 | return GNUNET_OK; | ||
1025 | } | ||
1026 | else if (GNUNET_YES == address->active) | ||
1027 | { | ||
1028 | /* Address was used before, check for bandwidth change */ | ||
1029 | if ((mlp_bw_out != ntohl(address->assigned_bw_out.value__)) || | ||
1030 | (mlp_bw_in != ntohl(address->assigned_bw_in.value__))) | ||
1031 | { | ||
1032 | LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n", | ||
1033 | (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); | ||
1034 | address->assigned_bw_in.value__ = htonl (mlp_bw_in); | ||
1035 | mlpi->b_in.value__ = htonl(mlp_bw_in); | ||
1036 | address->assigned_bw_out.value__ = htonl (mlp_bw_out); | ||
1037 | mlpi->b_out.value__ = htonl(mlp_bw_out); | ||
1038 | if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer)))) | ||
1039 | mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); | ||
1040 | return GNUNET_OK; | ||
1041 | } | ||
1042 | } | ||
1043 | else | ||
1044 | GNUNET_break (0); | ||
1045 | } | ||
1046 | else if (GLP_NO == mlp_use) | ||
1047 | { | ||
1048 | /* This address was selected by the solver to be not used */ | ||
1049 | mlpi->n = GNUNET_NO; | ||
1050 | if (GNUNET_NO == address->active) | ||
1051 | { | ||
1052 | /* Address was not used before, nothing to do */ | ||
1053 | LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n", | ||
1054 | (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); | ||
1055 | return GNUNET_OK; | ||
1056 | } | ||
1057 | else if (GNUNET_YES == address->active) | ||
1058 | { | ||
1059 | /* Address was used before, disabling address */ | ||
1060 | LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n", | ||
1061 | (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out); | ||
1062 | address->active = GNUNET_NO; | ||
1063 | /* Set bandwidth to 0 */ | ||
1064 | address->assigned_bw_in = BANDWIDTH_ZERO; | ||
1065 | mlpi->b_in.value__ = htonl(mlp_bw_in); | ||
1066 | address->assigned_bw_out = BANDWIDTH_ZERO; | ||
1067 | mlpi->b_out.value__ = htonl(mlp_bw_out); | ||
1068 | //mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); | ||
1069 | return GNUNET_OK; | ||
1070 | } | ||
1071 | else | ||
1072 | GNUNET_break (0); | ||
1073 | } | ||
1074 | else | ||
1075 | GNUNET_break (0); | ||
1076 | |||
1077 | return GNUNET_OK; | ||
1078 | } | ||
1079 | |||
1080 | static void notify (struct GAS_MLP_Handle *mlp, | ||
1081 | enum GAS_Solver_Operation op, | ||
1082 | enum GAS_Solver_Status stat, | ||
1083 | enum GAS_Solver_Additional_Information add) | ||
1084 | { | ||
1085 | if (NULL != mlp->env->info_cb) | ||
1086 | mlp->env->info_cb (mlp->env->info_cb_cls, op, stat, add); | ||
1087 | } | ||
1088 | /** | ||
1089 | * Solves the MLP problem | ||
1090 | * | ||
1091 | * @param solver the MLP Handle | ||
1092 | * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure | ||
1093 | */ | ||
1094 | int | ||
1095 | GAS_mlp_solve_problem (void *solver) | ||
1096 | { | ||
1097 | struct GAS_MLP_Handle *mlp = solver; | ||
1098 | char *filename; | ||
1099 | int res_lp = 0; | ||
1100 | int res_mip = 0; | ||
1101 | |||
1102 | struct GNUNET_TIME_Absolute start; | ||
1103 | struct GNUNET_TIME_Relative dur_total; | ||
1104 | struct GNUNET_TIME_Relative dur_setup; | ||
1105 | struct GNUNET_TIME_Relative dur_lp; | ||
1106 | struct GNUNET_TIME_Relative dur_mlp; | ||
1107 | |||
1108 | GNUNET_assert(NULL != solver); | ||
1109 | |||
1110 | if (GNUNET_YES == mlp->bulk_lock) | ||
1111 | { | ||
1112 | mlp->bulk_request++; | ||
1113 | return GNUNET_NO; | ||
1114 | } | ||
1115 | notify(mlp, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS, | ||
1116 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1117 | start = GNUNET_TIME_absolute_get(); | ||
1118 | |||
1119 | if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->requested_peers)) | ||
1120 | { | ||
1121 | notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE); | ||
1122 | return GNUNET_OK; /* No pending requests */ | ||
1123 | } | ||
1124 | if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->addresses)) | ||
1125 | { | ||
1126 | notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE); | ||
1127 | return GNUNET_OK; /* No addresses available */ | ||
1128 | } | ||
1129 | |||
1130 | if ((GNUNET_NO == mlp->mlp_prob_changed) | ||
1131 | && (GNUNET_NO == mlp->mlp_prob_updated)) | ||
1132 | { | ||
1133 | LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n"); | ||
1134 | notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE); | ||
1135 | return GNUNET_OK; | ||
1136 | } | ||
1137 | if (GNUNET_YES == mlp->mlp_prob_changed) | ||
1138 | { | ||
1139 | LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n"); | ||
1140 | notify(mlp, GAS_OP_SOLVE_SETUP_START, GAS_STAT_SUCCESS, GAS_INFO_FULL); | ||
1141 | mlp_delete_problem(mlp); | ||
1142 | if (GNUNET_SYSERR == mlp_create_problem(mlp)) | ||
1143 | { | ||
1144 | notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_FAIL, GAS_INFO_FULL); | ||
1145 | return GNUNET_SYSERR; | ||
1146 | } | ||
1147 | notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_SUCCESS, GAS_INFO_FULL); | ||
1148 | mlp->control_param_lp.presolve = GLP_YES; | ||
1149 | mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */ | ||
1150 | } | ||
1151 | else | ||
1152 | { | ||
1153 | LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n"); | ||
1154 | } | ||
1155 | |||
1156 | dur_setup = GNUNET_TIME_absolute_get_duration (start); | ||
1157 | mlp->control_param_lp.presolve = GLP_YES; | ||
1158 | /* Run LP solver */ | ||
1159 | |||
1160 | notify(mlp, GAS_OP_SOLVE_MLP_LP_START, GAS_STAT_SUCCESS, | ||
1161 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1162 | LOG(GNUNET_ERROR_TYPE_DEBUG, | ||
1163 | "Running LP solver %s\n", | ||
1164 | (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver"); | ||
1165 | res_lp = mlp_solve_lp_problem(mlp); | ||
1166 | notify(mlp, GAS_OP_SOLVE_MLP_LP_STOP, | ||
1167 | (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL, | ||
1168 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1169 | |||
1170 | dur_lp = GNUNET_TIME_absolute_get_duration (start); | ||
1171 | dur_lp = GNUNET_TIME_relative_subtract(dur_lp, dur_setup); | ||
1172 | |||
1173 | /* Run MLP solver */ | ||
1174 | LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n"); | ||
1175 | notify(mlp, GAS_OP_SOLVE_MLP_MLP_START, GAS_STAT_SUCCESS, | ||
1176 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1177 | res_mip = mlp_solve_mlp_problem(mlp); | ||
1178 | notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP, | ||
1179 | (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL, | ||
1180 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1181 | notify(mlp, GAS_OP_SOLVE_STOP, | ||
1182 | (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL, | ||
1183 | (GNUNET_YES == mlp->mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED); | ||
1184 | |||
1185 | dur_mlp = GNUNET_TIME_absolute_get_duration (start); | ||
1186 | dur_mlp = GNUNET_TIME_relative_subtract(dur_mlp, dur_setup); | ||
1187 | dur_mlp = GNUNET_TIME_relative_subtract(dur_mlp, dur_lp); | ||
1188 | dur_total = GNUNET_TIME_absolute_get_duration (start); | ||
1189 | |||
1190 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
1191 | "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n", | ||
1192 | (GNUNET_YES == mlp->mlp_prob_changed) ? "full" : "updated", | ||
1193 | (unsigned long long) dur_total.rel_value_us, | ||
1194 | (unsigned long long) dur_setup.rel_value_us, | ||
1195 | (unsigned long long) dur_lp.rel_value_us, | ||
1196 | (unsigned long long) dur_mlp.rel_value_us); | ||
1197 | |||
1198 | /* Save stats */ | ||
1199 | mlp->ps.lp_res = res_lp; | ||
1200 | mlp->ps.mip_res = res_mip; | ||
1201 | mlp->ps.lp_presolv = mlp->control_param_lp.presolve; | ||
1202 | mlp->ps.mip_presolv = mlp->control_param_mlp.presolve; | ||
1203 | mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob); | ||
1204 | mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob); | ||
1205 | mlp->ps.p_elements = mlp->p.num_elements; | ||
1206 | |||
1207 | /* Propagate result*/ | ||
1208 | notify(mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START, | ||
1209 | (GNUNET_OK == res_lp) && (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL, | ||
1210 | GAS_INFO_NONE); | ||
1211 | if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip)) | ||
1212 | { | ||
1213 | GNUNET_CONTAINER_multipeermap_iterate(mlp->addresses, | ||
1214 | &mlp_propagate_results, mlp); | ||
1215 | } | ||
1216 | notify(mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP, | ||
1217 | (GNUNET_OK == res_lp) && (GNUNET_OK == res_mip) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL, | ||
1218 | GAS_INFO_NONE); | ||
1219 | |||
1220 | struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get(); | ||
1221 | if (GNUNET_YES == mlp->write_mip_mps) | ||
1222 | { | ||
1223 | /* Write problem to disk */ | ||
1224 | GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers, | ||
1225 | mlp->p.num_addresses, time.abs_value_us); | ||
1226 | LOG(GNUNET_ERROR_TYPE_ERROR, "DUMP: %s \n", filename); | ||
1227 | glp_write_lp(mlp->p.prob, NULL, filename); | ||
1228 | GNUNET_free(filename); | ||
1229 | } | ||
1230 | if (GNUNET_YES == mlp->write_mip_sol) | ||
1231 | { | ||
1232 | /* Write solution to disk */ | ||
1233 | GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers, | ||
1234 | mlp->p.num_addresses, time.abs_value_us); | ||
1235 | glp_print_mip(mlp->p.prob, filename); | ||
1236 | LOG(GNUNET_ERROR_TYPE_ERROR, "DUMP: %s \n", filename); | ||
1237 | GNUNET_free(filename); | ||
1238 | } | ||
1239 | |||
1240 | /* Reset change and update marker */ | ||
1241 | mlp->control_param_lp.presolve = GLP_NO; | ||
1242 | mlp->mlp_prob_updated = GNUNET_NO; | ||
1243 | mlp->mlp_prob_changed = GNUNET_NO; | ||
1244 | |||
1245 | if ((GNUNET_OK == res_lp) && (GNUNET_OK == res_mip)) | ||
1246 | return GNUNET_OK; | ||
1247 | else | ||
1248 | return GNUNET_SYSERR; | ||
1249 | } | ||
1250 | |||
1251 | /** | ||
1252 | * Add a single address to the solve | ||
1253 | * | ||
1254 | * @param solver the solver Handle | ||
1255 | * @param address the address to add | ||
1256 | * @param network network type of this address | ||
1257 | */ | ||
1258 | void | ||
1259 | GAS_mlp_address_add (void *solver, | ||
1260 | struct ATS_Address *address, | ||
1261 | uint32_t network) | ||
1262 | { | ||
1263 | struct GAS_MLP_Handle *mlp = solver; | ||
1264 | struct ATS_Peer *p; | ||
1265 | |||
1266 | GNUNET_assert (NULL != solver); | ||
1267 | GNUNET_assert (NULL != address); | ||
1268 | |||
1269 | if (GNUNET_ATS_NetworkTypeCount <= network) | ||
1270 | { | ||
1271 | GNUNET_break (0); | ||
1272 | return; | ||
1273 | } | ||
1274 | |||
1275 | if (NULL == address->solver_information) | ||
1276 | { | ||
1277 | address->solver_information = GNUNET_new (struct MLP_information); | ||
1278 | } | ||
1279 | else | ||
1280 | LOG (GNUNET_ERROR_TYPE_ERROR, | ||
1281 | _("Adding address for peer `%s' multiple times\n"), | ||
1282 | GNUNET_i2s(&address->peer)); | ||
1283 | |||
1284 | /* Is this peer included in the problem? */ | ||
1285 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, | ||
1286 | &address->peer))) | ||
1287 | { | ||
1288 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' without address request \n", GNUNET_i2s(&address->peer)); | ||
1289 | return; | ||
1290 | } | ||
1291 | |||
1292 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s' with address request \n", GNUNET_i2s(&address->peer)); | ||
1293 | /* Problem size changed: new address for peer with pending request */ | ||
1294 | mlp->mlp_prob_changed = GNUNET_YES; | ||
1295 | if (GNUNET_YES == mlp->mlp_auto_solve) | ||
1296 | GAS_mlp_solve_problem (solver); | ||
1297 | } | ||
1298 | |||
1299 | |||
1300 | /** | ||
1301 | * Transport properties for this address have changed | ||
1302 | * | ||
1303 | * @param solver solver handle | ||
1304 | * @param address the address | ||
1305 | * @param type the ATSI type in HBO | ||
1306 | * @param abs_value the absolute value of the property | ||
1307 | * @param rel_value the normalized value | ||
1308 | */ | ||
1309 | void | ||
1310 | GAS_mlp_address_property_changed (void *solver, | ||
1311 | struct ATS_Address *address, | ||
1312 | uint32_t type, | ||
1313 | uint32_t abs_value, | ||
1314 | double rel_value) | ||
1315 | { | ||
1316 | struct MLP_information *mlpi = address->solver_information; | ||
1317 | struct GAS_MLP_Handle *mlp = solver; | ||
1318 | struct ATS_Peer *p; | ||
1319 | int c1; | ||
1320 | int type_index; | ||
1321 | |||
1322 | GNUNET_assert (NULL != solver); | ||
1323 | GNUNET_assert (NULL != address); | ||
1324 | |||
1325 | if (NULL == mlpi) | ||
1326 | { | ||
1327 | LOG (GNUNET_ERROR_TYPE_ERROR, | ||
1328 | _("Updating address property `%s' for peer `%s' %p not added before\n"), | ||
1329 | GNUNET_ATS_print_property_type (type), | ||
1330 | GNUNET_i2s(&address->peer), | ||
1331 | address); | ||
1332 | GNUNET_break (0); | ||
1333 | return; | ||
1334 | } | ||
1335 | |||
1336 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, | ||
1337 | &address->peer))) | ||
1338 | { | ||
1339 | /* Peer is not requested, so no need to update problem */ | ||
1340 | return; | ||
1341 | } | ||
1342 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating property `%s' address for peer `%s'\n", | ||
1343 | GNUNET_ATS_print_property_type (type), | ||
1344 | GNUNET_i2s(&address->peer)); | ||
1345 | |||
1346 | /* Find row index */ | ||
1347 | type_index = -1; | ||
1348 | for (c1 = 0; c1 < mlp->pv.m_q; c1++) | ||
1349 | { | ||
1350 | if (type == mlp->pv.q[c1]) | ||
1351 | { | ||
1352 | type_index = c1; | ||
1353 | break; | ||
1354 | } | ||
1355 | } | ||
1356 | if (-1 == type_index) | ||
1357 | { | ||
1358 | GNUNET_break (0); | ||
1359 | return; /* quality index not found */ | ||
1360 | } | ||
1361 | |||
1362 | /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */ | ||
1363 | if (GNUNET_YES == mlp_create_problem_update_value (&mlp->p, | ||
1364 | mlp->p.r_q[type_index], mlpi->c_b, rel_value, __LINE__)) | ||
1365 | { | ||
1366 | mlp->mlp_prob_updated = GNUNET_YES; | ||
1367 | if (GNUNET_YES == mlp->mlp_auto_solve) | ||
1368 | GAS_mlp_solve_problem (solver); | ||
1369 | } | ||
1370 | } | ||
1371 | |||
1372 | |||
1373 | /** | ||
1374 | * Transport session for this address has changed | ||
1375 | * | ||
1376 | * NOTE: values in addresses are already updated | ||
1377 | * | ||
1378 | * @param solver solver handle | ||
1379 | * @param address the address | ||
1380 | * @param cur_session the current session | ||
1381 | * @param new_session the new session | ||
1382 | */ | ||
1383 | void | ||
1384 | GAS_mlp_address_session_changed (void *solver, | ||
1385 | struct ATS_Address *address, | ||
1386 | uint32_t cur_session, | ||
1387 | uint32_t new_session) | ||
1388 | { | ||
1389 | /* Nothing to do here */ | ||
1390 | return; | ||
1391 | } | ||
1392 | |||
1393 | |||
1394 | /** | ||
1395 | * Transport session for this address has changed | ||
1396 | * | ||
1397 | * NOTE: values in addresses are already updated | ||
1398 | * | ||
1399 | * @param solver solver handle | ||
1400 | * @param address the address | ||
1401 | * @param in_use usage state | ||
1402 | */ | ||
1403 | void | ||
1404 | GAS_mlp_address_inuse_changed (void *solver, | ||
1405 | struct ATS_Address *address, | ||
1406 | int in_use) | ||
1407 | { | ||
1408 | /* Nothing to do here */ | ||
1409 | return; | ||
1410 | } | ||
1411 | |||
1412 | |||
1413 | /** | ||
1414 | * Network scope for this address has changed | ||
1415 | * | ||
1416 | * NOTE: values in addresses are already updated | ||
1417 | * | ||
1418 | * @param solver solver handle | ||
1419 | * @param address the address | ||
1420 | * @param current_network the current network | ||
1421 | * @param new_network the new network | ||
1422 | */ | ||
1423 | void | ||
1424 | GAS_mlp_address_change_network (void *solver, | ||
1425 | struct ATS_Address *address, | ||
1426 | uint32_t current_network, | ||
1427 | uint32_t new_network) | ||
1428 | { | ||
1429 | struct MLP_information *mlpi = address->solver_information; | ||
1430 | struct GAS_MLP_Handle *mlp = solver; | ||
1431 | struct ATS_Peer *p; | ||
1432 | int nets_avail[] = GNUNET_ATS_NetworkType; | ||
1433 | int c1; | ||
1434 | |||
1435 | GNUNET_assert (NULL != solver); | ||
1436 | GNUNET_assert (NULL != address); | ||
1437 | |||
1438 | if (GNUNET_ATS_NetworkTypeCount <= new_network) | ||
1439 | { | ||
1440 | GNUNET_break (0); | ||
1441 | return; | ||
1442 | } | ||
1443 | |||
1444 | if (NULL == mlpi) | ||
1445 | { | ||
1446 | GNUNET_break (0); | ||
1447 | return; | ||
1448 | } | ||
1449 | |||
1450 | if (mlpi->c_b == MLP_UNDEFINED) | ||
1451 | return; /* This address is not yet in the matrix*/ | ||
1452 | |||
1453 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, | ||
1454 | &address->peer))) | ||
1455 | { | ||
1456 | /* Peer is not requested, so no need to update problem */ | ||
1457 | GNUNET_break (0); | ||
1458 | return; | ||
1459 | } | ||
1460 | |||
1461 | if (current_network == new_network) | ||
1462 | { | ||
1463 | GNUNET_break (0); | ||
1464 | return; | ||
1465 | } | ||
1466 | |||
1467 | for (c1 = 0; c1 < GNUNET_ATS_NetworkTypeCount ; c1 ++) | ||
1468 | { | ||
1469 | if (nets_avail[c1] == new_network) | ||
1470 | break; | ||
1471 | } | ||
1472 | |||
1473 | if (GNUNET_ATS_NetworkTypeCount == c1) | ||
1474 | { | ||
1475 | /* Invalid network */ | ||
1476 | GNUNET_break (0); | ||
1477 | return; | ||
1478 | } | ||
1479 | |||
1480 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating network for peer `%s' from `%s' to `%s'\n", | ||
1481 | GNUNET_i2s (&address->peer), | ||
1482 | GNUNET_ATS_print_network_type(current_network), | ||
1483 | GNUNET_ATS_print_network_type(new_network)); | ||
1484 | |||
1485 | for (c1 = 0; c1 < GNUNET_ATS_NetworkTypeCount; c1++) | ||
1486 | { | ||
1487 | if (mlp->pv.quota_index[c1] == current_network) | ||
1488 | { | ||
1489 | /* Remove from old network */ | ||
1490 | mlp_create_problem_update_value (&mlp->p, | ||
1491 | mlp->p.r_quota[c1], | ||
1492 | mlpi->c_b, 0.0, __LINE__); | ||
1493 | break; | ||
1494 | } | ||
1495 | } | ||
1496 | |||
1497 | for (c1 = 0; c1 < GNUNET_ATS_NetworkTypeCount; c1++) | ||
1498 | { | ||
1499 | if (mlp->pv.quota_index[c1] == new_network) | ||
1500 | { | ||
1501 | /* Remove from old network */ | ||
1502 | if (GNUNET_SYSERR == mlp_create_problem_update_value (&mlp->p, | ||
1503 | mlp->p.r_quota[c1], | ||
1504 | mlpi->c_b, 1.0, __LINE__)) | ||
1505 | { | ||
1506 | /* This quota did not exist in the problem, recreate */ | ||
1507 | GNUNET_break (0); | ||
1508 | } | ||
1509 | break; | ||
1510 | } | ||
1511 | } | ||
1512 | |||
1513 | mlp->mlp_prob_changed = GNUNET_YES; | ||
1514 | } | ||
1515 | |||
1516 | |||
1517 | /** | ||
1518 | * Deletes a single address in the MLP problem | ||
1519 | * | ||
1520 | * The MLP problem has to be recreated and the problem has to be resolved | ||
1521 | * | ||
1522 | * @param solver the MLP Handle | ||
1523 | * @param address the address to delete | ||
1524 | * @param session_only delete only session not whole address | ||
1525 | */ | ||
1526 | void | ||
1527 | GAS_mlp_address_delete (void *solver, | ||
1528 | struct ATS_Address *address, | ||
1529 | int session_only) | ||
1530 | { | ||
1531 | struct ATS_Peer *p; | ||
1532 | struct GAS_MLP_Handle *mlp = solver; | ||
1533 | struct MLP_information *mlpi; | ||
1534 | int was_active; | ||
1535 | |||
1536 | GNUNET_assert (NULL != solver); | ||
1537 | GNUNET_assert (NULL != address); | ||
1538 | |||
1539 | mlpi = address->solver_information; | ||
1540 | if ((GNUNET_NO == session_only) && (NULL != mlpi)) | ||
1541 | { | ||
1542 | /* Remove full address */ | ||
1543 | GNUNET_free (mlpi); | ||
1544 | address->solver_information = NULL; | ||
1545 | } | ||
1546 | was_active = address->active; | ||
1547 | address->active = GNUNET_NO; | ||
1548 | address->assigned_bw_in = BANDWIDTH_ZERO; | ||
1549 | address->assigned_bw_out = BANDWIDTH_ZERO; | ||
1550 | |||
1551 | /* Is this peer included in the problem? */ | ||
1552 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, | ||
1553 | &address->peer))) | ||
1554 | { | ||
1555 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting %s for peer `%s' without address request \n", | ||
1556 | (session_only == GNUNET_YES) ? "session" : "address", | ||
1557 | GNUNET_i2s(&address->peer)); | ||
1558 | return; | ||
1559 | } | ||
1560 | LOG (GNUNET_ERROR_TYPE_INFO, "Deleting %s for peer `%s' with address request \n", | ||
1561 | (session_only == GNUNET_YES) ? "session" : "address", | ||
1562 | GNUNET_i2s(&address->peer)); | ||
1563 | |||
1564 | /* Problem size changed: new address for peer with pending request */ | ||
1565 | mlp->mlp_prob_changed = GNUNET_YES; | ||
1566 | if (GNUNET_YES == mlp->mlp_auto_solve) | ||
1567 | { | ||
1568 | GAS_mlp_solve_problem (solver); | ||
1569 | } | ||
1570 | if (GNUNET_YES == was_active) | ||
1571 | { | ||
1572 | if (NULL == GAS_mlp_get_preferred_address (solver, &address->peer)) | ||
1573 | { | ||
1574 | /* No alternative address, disconnecting peer */ | ||
1575 | mlp->bw_changed_cb (mlp->bw_changed_cb_cls, address); | ||
1576 | } | ||
1577 | } | ||
1578 | |||
1579 | return; | ||
1580 | } | ||
1581 | |||
1582 | |||
1583 | /** | ||
1584 | * Find the active address in the set of addresses of a peer | ||
1585 | * @param cls destination | ||
1586 | * @param key peer id | ||
1587 | * @param value address | ||
1588 | * @return GNUNET_OK | ||
1589 | */ | ||
1590 | static int | ||
1591 | mlp_get_preferred_address_it (void *cls, | ||
1592 | const struct GNUNET_PeerIdentity *key, | ||
1593 | void *value) | ||
1594 | { | ||
1595 | static int counter = 0; | ||
1596 | struct ATS_Address **aa = cls; | ||
1597 | struct ATS_Address *addr = value; | ||
1598 | struct MLP_information *mlpi = addr->solver_information; | ||
1599 | |||
1600 | if (mlpi == NULL) | ||
1601 | return GNUNET_YES; | ||
1602 | |||
1603 | /* | ||
1604 | * Debug output | ||
1605 | * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1606 | * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n", | ||
1607 | * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id, | ||
1608 | * (GNUNET_YES == addr->active) ? "active" : "inactive", | ||
1609 | * (GNUNET_YES == mlpi->n) ? "active" : "inactive"); | ||
1610 | */ | ||
1611 | |||
1612 | if (GNUNET_YES == mlpi->n) | ||
1613 | { | ||
1614 | |||
1615 | (*aa) = addr; | ||
1616 | (*aa)->assigned_bw_in = mlpi->b_in; | ||
1617 | (*aa)->assigned_bw_out = mlpi->b_out; | ||
1618 | return GNUNET_NO; | ||
1619 | } | ||
1620 | counter ++; | ||
1621 | return GNUNET_YES; | ||
1622 | } | ||
1623 | |||
1624 | |||
1625 | static double | ||
1626 | get_peer_pref_value (struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer) | ||
1627 | { | ||
1628 | double res; | ||
1629 | const double *preferences = NULL; | ||
1630 | int c; | ||
1631 | preferences = mlp->get_preferences (mlp->get_preferences_cls, peer); | ||
1632 | |||
1633 | res = 0.0; | ||
1634 | for (c = 0; c < GNUNET_ATS_PreferenceCount; c++) | ||
1635 | { | ||
1636 | if (c != GNUNET_ATS_PREFERENCE_END) | ||
1637 | { | ||
1638 | //fprintf (stderr, "VALUE[%u] %s %.3f \n", c, GNUNET_i2s (&cur->addr->peer), t[c]); | ||
1639 | res += preferences[c]; | ||
1640 | } | ||
1641 | } | ||
1642 | res /= (GNUNET_ATS_PreferenceCount -1); | ||
1643 | return res; | ||
1644 | } | ||
1645 | |||
1646 | |||
1647 | /** | ||
1648 | * Get the preferred address for a specific peer | ||
1649 | * | ||
1650 | * @param solver the MLP Handle | ||
1651 | * @param peer the peer | ||
1652 | * @return suggested address | ||
1653 | */ | ||
1654 | const struct ATS_Address * | ||
1655 | GAS_mlp_get_preferred_address (void *solver, | ||
1656 | const struct GNUNET_PeerIdentity *peer) | ||
1657 | { | ||
1658 | struct GAS_MLP_Handle *mlp = solver; | ||
1659 | struct ATS_Peer *p; | ||
1660 | struct ATS_Address *res; | ||
1661 | |||
1662 | GNUNET_assert (NULL != solver); | ||
1663 | GNUNET_assert (NULL != peer); | ||
1664 | |||
1665 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Getting preferred address for `%s'\n", | ||
1666 | GNUNET_i2s (peer)); | ||
1667 | |||
1668 | /* Is this peer included in the problem? */ | ||
1669 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, | ||
1670 | peer))) | ||
1671 | { | ||
1672 | LOG (GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n", | ||
1673 | GNUNET_i2s (peer)); | ||
1674 | |||
1675 | p = GNUNET_malloc (sizeof (struct ATS_Peer)); | ||
1676 | p->id = (*peer); | ||
1677 | p->f = get_peer_pref_value (mlp, peer); | ||
1678 | GNUNET_CONTAINER_multipeermap_put (mlp->requested_peers, | ||
1679 | peer, p, | ||
1680 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); | ||
1681 | |||
1682 | /* Added new peer, we have to rebuild problem before solving */ | ||
1683 | mlp->mlp_prob_changed = GNUNET_YES; | ||
1684 | |||
1685 | if ((GNUNET_YES == mlp->mlp_auto_solve)&& | ||
1686 | (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(mlp->addresses, | ||
1687 | peer))) | ||
1688 | { | ||
1689 | mlp->exclude_peer = peer; | ||
1690 | GAS_mlp_solve_problem (mlp); | ||
1691 | mlp->exclude_peer = NULL; | ||
1692 | } | ||
1693 | } | ||
1694 | /* Get prefered address */ | ||
1695 | res = NULL; | ||
1696 | GNUNET_CONTAINER_multipeermap_get_multiple (mlp->addresses, peer, | ||
1697 | mlp_get_preferred_address_it, &res); | ||
1698 | return res; | ||
1699 | } | ||
1700 | |||
1701 | |||
1702 | /** | ||
1703 | * Start a bulk operation | ||
1704 | * | ||
1705 | * @param solver the solver | ||
1706 | */ | ||
1707 | void | ||
1708 | GAS_mlp_bulk_start (void *solver) | ||
1709 | { | ||
1710 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Locking solver for bulk operation ...\n"); | ||
1711 | struct GAS_MLP_Handle *s = (struct GAS_MLP_Handle *) solver; | ||
1712 | |||
1713 | GNUNET_assert (NULL != solver); | ||
1714 | |||
1715 | s->bulk_lock ++; | ||
1716 | } | ||
1717 | |||
1718 | void | ||
1719 | GAS_mlp_bulk_stop (void *solver) | ||
1720 | { | ||
1721 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Unlocking solver from bulk operation ...\n"); | ||
1722 | |||
1723 | struct GAS_MLP_Handle *s = (struct GAS_MLP_Handle *) solver; | ||
1724 | GNUNET_assert (NULL != solver); | ||
1725 | |||
1726 | if (s->bulk_lock < 1) | ||
1727 | { | ||
1728 | GNUNET_break (0); | ||
1729 | return; | ||
1730 | } | ||
1731 | s->bulk_lock --; | ||
1732 | |||
1733 | if (0 < s->bulk_request) | ||
1734 | { | ||
1735 | GAS_mlp_solve_problem (solver); | ||
1736 | s->bulk_request= 0; | ||
1737 | } | ||
1738 | } | ||
1739 | |||
1740 | |||
1741 | |||
1742 | /** | ||
1743 | * Stop notifying about address and bandwidth changes for this peer | ||
1744 | * | ||
1745 | * @param solver the MLP handle | ||
1746 | * @param peer the peer | ||
1747 | */ | ||
1748 | void | ||
1749 | GAS_mlp_stop_get_preferred_address (void *solver, | ||
1750 | const struct GNUNET_PeerIdentity *peer) | ||
1751 | { | ||
1752 | struct GAS_MLP_Handle *mlp = solver; | ||
1753 | struct ATS_Peer *p = NULL; | ||
1754 | |||
1755 | GNUNET_assert (NULL != solver); | ||
1756 | GNUNET_assert (NULL != peer); | ||
1757 | if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer))) | ||
1758 | { | ||
1759 | GNUNET_CONTAINER_multipeermap_remove (mlp->requested_peers, peer, p); | ||
1760 | GNUNET_free (p); | ||
1761 | |||
1762 | mlp->mlp_prob_changed = GNUNET_YES; | ||
1763 | if (GNUNET_YES == mlp->mlp_auto_solve) | ||
1764 | { | ||
1765 | GAS_mlp_solve_problem (solver); | ||
1766 | } | ||
1767 | } | ||
1768 | } | ||
1769 | |||
1770 | |||
1771 | /** | ||
1772 | * Changes the preferences for a peer in the MLP problem | ||
1773 | * | ||
1774 | * @param solver the MLP Handle | ||
1775 | * @param peer the peer | ||
1776 | * @param kind the kind to change the preference | ||
1777 | * @param pref_rel the relative score | ||
1778 | */ | ||
1779 | void | ||
1780 | GAS_mlp_address_change_preference (void *solver, | ||
1781 | const struct GNUNET_PeerIdentity *peer, | ||
1782 | enum GNUNET_ATS_PreferenceKind kind, | ||
1783 | double pref_rel) | ||
1784 | { | ||
1785 | struct GAS_MLP_Handle *mlp = solver; | ||
1786 | struct ATS_Peer *p = NULL; | ||
1787 | |||
1788 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Changing preference for address for peer `%s' to %.2f\n", | ||
1789 | GNUNET_i2s(peer), pref_rel); | ||
1790 | |||
1791 | GNUNET_STATISTICS_update (mlp->stats,"# LP address preference changes", 1, GNUNET_NO); | ||
1792 | /* Update the constraints with changed preferences */ | ||
1793 | |||
1794 | /* Update quality constraint c7 */ | ||
1795 | |||
1796 | /* Update relativity constraint c9 */ | ||
1797 | if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer))) | ||
1798 | { | ||
1799 | LOG (GNUNET_ERROR_TYPE_ERROR, "Updating preference for unknown peer `%s'\n", GNUNET_i2s(peer)); | ||
1800 | return; | ||
1801 | } | ||
1802 | p->f = get_peer_pref_value (mlp, peer); | ||
1803 | /* | ||
1804 | LOG (GNUNET_ERROR_TYPE_ERROR, "PEER PREF: %s %.2f\n", | ||
1805 | GNUNET_i2s(peer), p->f);*/ | ||
1806 | mlp_create_problem_update_value (&mlp->p, p->r_c9, mlp->p.c_r, -p->f, __LINE__); | ||
1807 | |||
1808 | /* Problem size changed: new address for peer with pending request */ | ||
1809 | mlp->mlp_prob_updated = GNUNET_YES; | ||
1810 | if (GNUNET_YES == mlp->mlp_auto_solve) | ||
1811 | GAS_mlp_solve_problem (solver); | ||
1812 | return; | ||
1813 | } | ||
1814 | |||
1815 | |||
1816 | /** | ||
1817 | * Get application feedback for a peer | ||
1818 | * | ||
1819 | * @param solver the solver handle | ||
1820 | * @param application the application | ||
1821 | * @param peer the peer to change the preference for | ||
1822 | * @param scope the time interval for this feedback: [now - scope .. now] | ||
1823 | * @param kind the kind to change the preference | ||
1824 | * @param score the score | ||
1825 | */ | ||
1826 | void | ||
1827 | GAS_mlp_address_preference_feedback (void *solver, | ||
1828 | void *application, | ||
1829 | const struct GNUNET_PeerIdentity *peer, | ||
1830 | const struct GNUNET_TIME_Relative scope, | ||
1831 | enum GNUNET_ATS_PreferenceKind kind, | ||
1832 | double score) | ||
1833 | { | ||
1834 | struct GAS_PROPORTIONAL_Handle *s = solver; | ||
1835 | GNUNET_assert (NULL != solver); | ||
1836 | GNUNET_assert (NULL != peer); | ||
1837 | |||
1838 | GNUNET_assert (NULL != s); | ||
1839 | } | ||
1840 | |||
1841 | |||
1842 | static int | ||
1843 | mlp_free_peers (void *cls, | ||
1844 | const struct GNUNET_PeerIdentity *key, void *value) | ||
1845 | { | ||
1846 | struct GNUNET_CONTAINER_MultiPeerMap *map = cls; | ||
1847 | struct ATS_Peer *p = value; | ||
1848 | |||
1849 | GNUNET_CONTAINER_multipeermap_remove (map, key, value); | ||
1850 | GNUNET_free (p); | ||
1851 | |||
1852 | return GNUNET_OK; | ||
1853 | } | ||
1854 | |||
1855 | |||
1856 | /** | ||
1857 | * Shutdown the MLP problem solving component | ||
1858 | * | ||
1859 | * @param cls the solver handle | ||
1860 | * @return NULL | ||
1861 | */ | ||
1862 | void * | ||
1863 | libgnunet_plugin_ats_mlp_done (void *cls) | ||
1864 | { | ||
1865 | struct GAS_MLP_Handle *mlp = cls; | ||
1866 | GNUNET_assert (mlp != NULL); | ||
1867 | |||
1868 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down mlp solver\n"); | ||
1869 | mlp_delete_problem (mlp); | ||
1870 | |||
1871 | GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers, | ||
1872 | &mlp_free_peers, | ||
1873 | mlp->requested_peers); | ||
1874 | GNUNET_CONTAINER_multipeermap_destroy (mlp->requested_peers); | ||
1875 | mlp->requested_peers = NULL; | ||
1876 | |||
1877 | /* Clean up GLPK environment */ | ||
1878 | glp_free_env(); | ||
1879 | GNUNET_free (mlp); | ||
1880 | |||
1881 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutdown down of mlp solver complete\n"); | ||
1882 | return NULL; | ||
1883 | } | ||
1884 | |||
1885 | |||
1886 | void * | ||
1887 | libgnunet_plugin_ats_mlp_init (void *cls) | ||
1888 | { | ||
1889 | struct GNUNET_ATS_PluginEnvironment *env = cls; | ||
1890 | struct GAS_MLP_Handle * mlp = GNUNET_malloc (sizeof (struct GAS_MLP_Handle)); | ||
1891 | |||
1892 | double D; | ||
1893 | double R; | ||
1894 | double U; | ||
1895 | unsigned long long tmp; | ||
1896 | unsigned int b_min; | ||
1897 | unsigned int n_min; | ||
1898 | int c; | ||
1899 | int c2; | ||
1900 | int found; | ||
1901 | |||
1902 | struct GNUNET_TIME_Relative max_duration; | ||
1903 | long long unsigned int max_iterations; | ||
1904 | |||
1905 | GNUNET_assert (NULL != env->cfg); | ||
1906 | GNUNET_assert (NULL != env->stats); | ||
1907 | GNUNET_assert (NULL != env->addresses); | ||
1908 | GNUNET_assert (NULL != env->bandwidth_changed_cb); | ||
1909 | GNUNET_assert (NULL != env->get_preferences); | ||
1910 | GNUNET_assert (NULL != env->get_property); | ||
1911 | |||
1912 | /* Init GLPK environment */ | ||
1913 | int res = glp_init_env(); | ||
1914 | switch (res) { | ||
1915 | case 0: | ||
1916 | LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n", | ||
1917 | "initialization successful"); | ||
1918 | break; | ||
1919 | case 1: | ||
1920 | LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n", | ||
1921 | "environment is already initialized"); | ||
1922 | break; | ||
1923 | case 2: | ||
1924 | LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n", | ||
1925 | "initialization failed (insufficient memory)"); | ||
1926 | GNUNET_free(mlp); | ||
1927 | return NULL; | ||
1928 | break; | ||
1929 | case 3: | ||
1930 | LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n", | ||
1931 | "initialization failed (unsupported programming model)"); | ||
1932 | GNUNET_free(mlp); | ||
1933 | return NULL; | ||
1934 | break; | ||
1935 | default: | ||
1936 | break; | ||
1937 | } | ||
1938 | |||
1939 | mlp->write_mip_mps = GNUNET_CONFIGURATION_get_value_yesno (env->cfg, "ats", | ||
1940 | "DUMP_MLP"); | ||
1941 | if (GNUNET_SYSERR == mlp->write_mip_mps) | ||
1942 | mlp->write_mip_mps = GNUNET_NO; | ||
1943 | mlp->write_mip_sol = GNUNET_CONFIGURATION_get_value_yesno (env->cfg, "ats", | ||
1944 | "DUMP_SOLUTION"); | ||
1945 | if (GNUNET_SYSERR == mlp->write_mip_sol) | ||
1946 | mlp->write_mip_sol = GNUNET_NO; | ||
1947 | |||
1948 | mlp->pv.BIG_M = (double) BIG_M_VALUE; | ||
1949 | |||
1950 | /* Get timeout for iterations */ | ||
1951 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats", "MLP_MAX_DURATION", &max_duration)) | ||
1952 | { | ||
1953 | max_duration = MLP_MAX_EXEC_DURATION; | ||
1954 | } | ||
1955 | |||
1956 | /* Get maximum number of iterations */ | ||
1957 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(env->cfg, "ats", "MLP_MAX_ITERATIONS", &max_iterations)) | ||
1958 | { | ||
1959 | max_iterations = MLP_MAX_ITERATIONS; | ||
1960 | } | ||
1961 | |||
1962 | /* Get diversity coefficient from configuration */ | ||
1963 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
1964 | "MLP_COEFFICIENT_D", | ||
1965 | &tmp)) | ||
1966 | D = (double) tmp / 100; | ||
1967 | else | ||
1968 | D = DEFAULT_D; | ||
1969 | |||
1970 | /* Get proportionality coefficient from configuration */ | ||
1971 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
1972 | "MLP_COEFFICIENT_R", | ||
1973 | &tmp)) | ||
1974 | R = (double) tmp / 100; | ||
1975 | else | ||
1976 | R = DEFAULT_R; | ||
1977 | |||
1978 | /* Get utilization coefficient from configuration */ | ||
1979 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
1980 | "MLP_COEFFICIENT_U", | ||
1981 | &tmp)) | ||
1982 | U = (double) tmp / 100; | ||
1983 | else | ||
1984 | U = DEFAULT_U; | ||
1985 | |||
1986 | /* Get quality metric coefficients from configuration */ | ||
1987 | int i_delay = MLP_NaN; | ||
1988 | int i_distance = MLP_NaN; | ||
1989 | int q[GNUNET_ATS_QualityPropertiesCount] = GNUNET_ATS_QualityProperties; | ||
1990 | for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++) | ||
1991 | { | ||
1992 | /* initialize quality coefficients with default value 1.0 */ | ||
1993 | mlp->pv.co_Q[c] = DEFAULT_QUALITY; | ||
1994 | |||
1995 | mlp->pv.q[c] = q[c]; | ||
1996 | if (q[c] == GNUNET_ATS_QUALITY_NET_DELAY) | ||
1997 | i_delay = c; | ||
1998 | if (q[c] == GNUNET_ATS_QUALITY_NET_DISTANCE) | ||
1999 | i_distance = c; | ||
2000 | } | ||
2001 | |||
2002 | if ((i_delay != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
2003 | "MLP_COEFFICIENT_QUALITY_DELAY", | ||
2004 | &tmp))) | ||
2005 | |||
2006 | mlp->pv.co_Q[i_delay] = (double) tmp / 100; | ||
2007 | else | ||
2008 | mlp->pv.co_Q[i_delay] = DEFAULT_QUALITY; | ||
2009 | |||
2010 | if ((i_distance != MLP_NaN) && (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
2011 | "MLP_COEFFICIENT_QUALITY_DISTANCE", | ||
2012 | &tmp))) | ||
2013 | mlp->pv.co_Q[i_distance] = (double) tmp / 100; | ||
2014 | else | ||
2015 | mlp->pv.co_Q[i_distance] = DEFAULT_QUALITY; | ||
2016 | |||
2017 | /* Get minimum bandwidth per used address from configuration */ | ||
2018 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
2019 | "MLP_MIN_BANDWIDTH", | ||
2020 | &tmp)) | ||
2021 | b_min = tmp; | ||
2022 | else | ||
2023 | { | ||
2024 | b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); | ||
2025 | } | ||
2026 | |||
2027 | /* Get minimum number of connections from configuration */ | ||
2028 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats", | ||
2029 | "MLP_MIN_CONNECTIONS", | ||
2030 | &tmp)) | ||
2031 | n_min = tmp; | ||
2032 | else | ||
2033 | n_min = DEFAULT_MIN_CONNECTIONS; | ||
2034 | |||
2035 | /* Init network quotas */ | ||
2036 | int quotas[GNUNET_ATS_NetworkTypeCount] = GNUNET_ATS_NetworkType; | ||
2037 | for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++) | ||
2038 | { | ||
2039 | found = GNUNET_NO; | ||
2040 | for (c2 = 0; c2 < env->network_count; c2++) | ||
2041 | { | ||
2042 | if (quotas[c] == env->networks[c2]) | ||
2043 | { | ||
2044 | mlp->pv.quota_index[c] = env->networks[c2]; | ||
2045 | mlp->pv.quota_out[c] = env->out_quota[c2]; | ||
2046 | mlp->pv.quota_in[c] = env->in_quota[c2]; | ||
2047 | found = GNUNET_YES; | ||
2048 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Quota for network `%s' (in/out) %llu/%llu\n", | ||
2049 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2050 | mlp->pv.quota_out[c], | ||
2051 | mlp->pv.quota_in[c]); | ||
2052 | break; | ||
2053 | } | ||
2054 | } | ||
2055 | |||
2056 | /* Check if defined quota could make problem unsolvable */ | ||
2057 | if ((n_min * b_min) > mlp->pv.quota_out[c]) | ||
2058 | { | ||
2059 | LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"), | ||
2060 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2061 | mlp->pv.quota_out[c], | ||
2062 | (n_min * b_min)); | ||
2063 | mlp->pv.quota_out[c] = (n_min * b_min); | ||
2064 | } | ||
2065 | if ((n_min * b_min) > mlp->pv.quota_in[c]) | ||
2066 | { | ||
2067 | LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"), | ||
2068 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2069 | mlp->pv.quota_in[c], | ||
2070 | (n_min * b_min)); | ||
2071 | mlp->pv.quota_in[c] = (n_min * b_min); | ||
2072 | } | ||
2073 | |||
2074 | /* Check if bandwidth is too big to make problem solvable */ | ||
2075 | if (mlp->pv.BIG_M < mlp->pv.quota_out[c]) | ||
2076 | { | ||
2077 | LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"), | ||
2078 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2079 | mlp->pv.quota_out[c], | ||
2080 | mlp->pv.BIG_M); | ||
2081 | mlp->pv.quota_out[c] = mlp->pv.BIG_M ; | ||
2082 | } | ||
2083 | if (mlp->pv.BIG_M < mlp->pv.quota_in[c]) | ||
2084 | { | ||
2085 | LOG (GNUNET_ERROR_TYPE_INFO, _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"), | ||
2086 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2087 | mlp->pv.quota_in[c], | ||
2088 | mlp->pv.BIG_M); | ||
2089 | mlp->pv.quota_in[c] = mlp->pv.BIG_M ; | ||
2090 | } | ||
2091 | |||
2092 | if (GNUNET_NO == found) | ||
2093 | { | ||
2094 | mlp->pv.quota_in[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); | ||
2095 | mlp->pv.quota_out[c] = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__); | ||
2096 | LOG (GNUNET_ERROR_TYPE_INFO, _("Using default quota configuration for network `%s' (in/out) %llu/%llu\n"), | ||
2097 | GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]), | ||
2098 | mlp->pv.quota_in[c], | ||
2099 | mlp->pv.quota_out[c]); | ||
2100 | } | ||
2101 | } | ||
2102 | mlp->env = env; | ||
2103 | env->sf.s_add = &GAS_mlp_address_add; | ||
2104 | env->sf.s_address_update_property = &GAS_mlp_address_property_changed; | ||
2105 | env->sf.s_address_update_session = &GAS_mlp_address_session_changed; | ||
2106 | env->sf.s_address_update_inuse = &GAS_mlp_address_inuse_changed; | ||
2107 | env->sf.s_address_update_network = &GAS_mlp_address_change_network; | ||
2108 | env->sf.s_get = &GAS_mlp_get_preferred_address; | ||
2109 | env->sf.s_get_stop = &GAS_mlp_stop_get_preferred_address; | ||
2110 | env->sf.s_pref = &GAS_mlp_address_change_preference; | ||
2111 | env->sf.s_feedback = &GAS_mlp_address_preference_feedback; | ||
2112 | env->sf.s_del = &GAS_mlp_address_delete; | ||
2113 | env->sf.s_bulk_start = &GAS_mlp_bulk_start; | ||
2114 | env->sf.s_bulk_stop = &GAS_mlp_bulk_stop; | ||
2115 | |||
2116 | |||
2117 | /* Assign options to handle */ | ||
2118 | mlp->stats = (struct GNUNET_STATISTICS_Handle *) env->stats; | ||
2119 | mlp->addresses = env->addresses; | ||
2120 | mlp->bw_changed_cb = env->bandwidth_changed_cb; | ||
2121 | mlp->bw_changed_cb_cls = env->bw_changed_cb_cls; | ||
2122 | mlp->get_preferences = env->get_preferences; | ||
2123 | mlp->get_preferences_cls = env->get_preference_cls; | ||
2124 | mlp->get_properties = env->get_property; | ||
2125 | mlp->get_properties_cls = env->get_property_cls; | ||
2126 | /* Setting MLP Input variables */ | ||
2127 | |||
2128 | mlp->pv.co_D = D; | ||
2129 | mlp->pv.co_R = R; | ||
2130 | mlp->pv.co_U = U; | ||
2131 | mlp->pv.b_min = b_min; | ||
2132 | mlp->pv.n_min = n_min; | ||
2133 | mlp->pv.m_q = GNUNET_ATS_QualityPropertiesCount; | ||
2134 | mlp->mlp_prob_changed = GNUNET_NO; | ||
2135 | mlp->mlp_prob_updated = GNUNET_NO; | ||
2136 | mlp->mlp_auto_solve = GNUNET_YES; | ||
2137 | mlp->requested_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO); | ||
2138 | mlp->bulk_request = 0; | ||
2139 | mlp->bulk_lock = 0; | ||
2140 | |||
2141 | /* Setup GLPK */ | ||
2142 | /* Redirect GLPK output to GNUnet logging */ | ||
2143 | glp_term_hook (&mlp_term_hook, (void *) mlp); | ||
2144 | |||
2145 | /* Init LP solving parameters */ | ||
2146 | glp_init_smcp(&mlp->control_param_lp); | ||
2147 | mlp->control_param_lp.msg_lev = GLP_MSG_OFF; | ||
2148 | #if VERBOSE_GLPK | ||
2149 | mlp->control_param_lp.msg_lev = GLP_MSG_ALL; | ||
2150 | #endif | ||
2151 | mlp->control_param_lp.it_lim = max_iterations; | ||
2152 | mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL; | ||
2153 | |||
2154 | /* Init MLP solving parameters */ | ||
2155 | glp_init_iocp(&mlp->control_param_mlp); | ||
2156 | mlp->control_param_mlp.msg_lev = GLP_MSG_OFF; | ||
2157 | #if VERBOSE_GLPK | ||
2158 | mlp->control_param_mlp.msg_lev = GLP_MSG_ALL; | ||
2159 | #endif | ||
2160 | mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL; | ||
2161 | |||
2162 | LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n"); | ||
2163 | |||
2164 | return mlp; | ||
2165 | } | ||
2166 | |||
2167 | /* end of plugin_ats_mlp.c */ | ||