diff options
author | Matthias Wachs <wachs@net.in.tum.de> | 2012-01-19 16:01:21 +0000 |
---|---|---|
committer | Matthias Wachs <wachs@net.in.tum.de> | 2012-01-19 16:01:21 +0000 |
commit | ac6004e54595513ceb3dd9e9eb75f728e2dc65fb (patch) | |
tree | 2755b1b36c34acfe7ae66f48e4cab995885d6313 /src/ats | |
parent | 17fc0828058e47ea0bd8428056fe88ee7e46749a (diff) | |
download | gnunet-ac6004e54595513ceb3dd9e9eb75f728e2dc65fb.tar.gz gnunet-ac6004e54595513ceb3dd9e9eb75f728e2dc65fb.zip |
- more working constraints
Diffstat (limited to 'src/ats')
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_mlp.c | 82 | ||||
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_mlp.h | 14 | ||||
-rw-r--r-- | src/ats/test_ats_mlp.c | 40 |
3 files changed, 108 insertions, 28 deletions
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c index badad5588..17b4697d4 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.c +++ b/src/ats/gnunet-service-ats_addresses_mlp.c | |||
@@ -32,7 +32,8 @@ | |||
32 | #include "glpk.h" | 32 | #include "glpk.h" |
33 | 33 | ||
34 | #define WRITE_MLP GNUNET_NO | 34 | #define WRITE_MLP GNUNET_NO |
35 | #define DEBUG_ATS GNUNET_EXTRA_LOGGING | 35 | #define DEBUG_ATS GNUNET_YES |
36 | #define VERBOSE_GLPK GNUNET_NO | ||
36 | 37 | ||
37 | /** | 38 | /** |
38 | * Translate glpk solver error codes to text | 39 | * Translate glpk solver error codes to text |
@@ -313,7 +314,6 @@ static void | |||
313 | mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) | 314 | mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) |
314 | { | 315 | { |
315 | unsigned int n_addresses; | 316 | unsigned int n_addresses; |
316 | int row_index; | ||
317 | //int c; | 317 | //int c; |
318 | char *name; | 318 | char *name; |
319 | 319 | ||
@@ -357,9 +357,17 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON | |||
357 | * c 7) quality | 357 | * c 7) quality |
358 | * #rows: |quality properties| | 358 | * #rows: |quality properties| |
359 | * #indices:|quality properties| + |n_addresses| | 359 | * #indices:|quality properties| + |n_addresses| |
360 | * | ||
361 | * c 8) utilization | ||
362 | * #rows: 1 | ||
363 | * #indices: |n_addresses| + 1 | ||
364 | * | ||
365 | * c 9) relativity | ||
366 | * #rows: |peers| | ||
367 | * #indices: |n_addresses| + |peers| | ||
360 | * */ | 368 | * */ |
361 | 369 | ||
362 | int pi = ((7 * n_addresses) + (2 * n_addresses + mlp->m_q + 1)); | 370 | int pi = ((7 * n_addresses) + (3 * n_addresses + mlp->m_q + 2)); |
363 | mlp->cm_size = pi; | 371 | mlp->cm_size = pi; |
364 | mlp->ci = 1; | 372 | mlp->ci = 1; |
365 | 373 | ||
@@ -412,30 +420,73 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON | |||
412 | * | 420 | * |
413 | * c 2) 1 address per peer | 421 | * c 2) 1 address per peer |
414 | * sum (n_p1_1 + ... + n_p1_n) = 1 | 422 | * sum (n_p1_1 + ... + n_p1_n) = 1 |
415 | */ | 423 | * |
424 | * c 8) utilization | ||
425 | * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0 | ||
426 | * | ||
427 | * c 9) relativity | ||
428 | * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0 | ||
429 | * */ | ||
416 | 430 | ||
417 | /* Adding rows for c 2) */ | 431 | /* Adding rows for c 8) */ |
418 | row_index = glp_add_rows (mlp->prob, mlp->c_p); | 432 | mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p); |
433 | glp_set_row_name (mlp->prob, mlp->r_c8, "c8"); | ||
434 | /* Set row bound == 0 */ | ||
435 | glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0); | ||
436 | /* -u */ | ||
437 | ia[mlp->ci] = mlp->r_c8; | ||
438 | ja[mlp->ci] = mlp->c_u; | ||
439 | ar[mlp->ci] = -1; | ||
440 | mlp->ci++; | ||
419 | 441 | ||
420 | struct ATS_Peer * peer = mlp->peer_head; | 442 | struct ATS_Peer * peer = mlp->peer_head; |
421 | while (peer != NULL) | 443 | while (peer != NULL) |
422 | { | 444 | { |
423 | struct ATS_Address *addr = peer->head; | 445 | struct ATS_Address *addr = peer->head; |
424 | struct MLP_information *mlpi = NULL; | 446 | struct MLP_information *mlpi = NULL; |
425 | /* Adding row for c 2) */ | 447 | |
448 | /* Adding rows for c 2) */ | ||
449 | peer->r_c2 = glp_add_rows (mlp->prob, 1); | ||
426 | GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id)); | 450 | GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id)); |
427 | glp_set_row_name (mlp->prob, row_index, name); | 451 | glp_set_row_name (mlp->prob, peer->r_c2, name); |
428 | GNUNET_free (name); | 452 | GNUNET_free (name); |
429 | /* Set row bound == 1 */ | 453 | /* Set row bound == 1 */ |
430 | glp_set_row_bnds (mlp->prob, row_index, GLP_FX, 1.0, 1.0); | 454 | glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0); |
455 | |||
456 | |||
457 | /* Adding rows for c 9) */ | ||
458 | peer->r_c9 = glp_add_rows (mlp->prob, 1); | ||
459 | GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id)); | ||
460 | glp_set_row_name (mlp->prob, peer->r_c9, name); | ||
461 | GNUNET_free (name); | ||
462 | /* Set row bound == 0 */ | ||
463 | glp_set_row_bnds (mlp->prob, peer->r_c9, GLP_LO, 0.0, 0.0); | ||
464 | |||
465 | /* Set -r */ | ||
466 | ia[mlp->ci] = peer->r_c9; | ||
467 | ja[mlp->ci] = mlp->c_r; | ||
468 | ar[mlp->ci] = -1; | ||
469 | mlp->ci++; | ||
431 | 470 | ||
432 | while (addr != NULL) | 471 | while (addr != NULL) |
433 | { | 472 | { |
434 | mlpi = (struct MLP_information *) addr->mlp_information; | 473 | mlpi = (struct MLP_information *) addr->mlp_information; |
435 | ia[mlp->ci] = row_index; | 474 | |
475 | ia[mlp->ci] = peer->r_c2; | ||
436 | ja[mlp->ci] = mlpi->c_n; | 476 | ja[mlp->ci] = mlpi->c_n; |
437 | ar[mlp->ci] = 1; | 477 | ar[mlp->ci] = 1; |
438 | mlp->ci++; | 478 | mlp->ci++; |
479 | |||
480 | ia[mlp->ci] = mlp->r_c8; | ||
481 | ja[mlp->ci] = mlpi->c_b; | ||
482 | ar[mlp->ci] = peer->f; | ||
483 | mlp->ci++; | ||
484 | |||
485 | ia[mlp->ci] = peer->r_c9; | ||
486 | ja[mlp->ci] = mlpi->c_b; | ||
487 | ar[mlp->ci] = 1; | ||
488 | mlp->ci++; | ||
489 | |||
439 | addr = addr->next; | 490 | addr = addr->next; |
440 | } | 491 | } |
441 | peer = peer->next; | 492 | peer = peer->next; |
@@ -553,7 +604,7 @@ mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHas | |||
553 | glp_set_obj_coef (mlp->prob, col, mlp->co_D); | 604 | glp_set_obj_coef (mlp->prob, col, mlp->co_D); |
554 | /* Column lower bound = 0.0 */ | 605 | /* Column lower bound = 0.0 */ |
555 | glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); | 606 | glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); |
556 | #if 0 | 607 | |
557 | /* Utilization u column */ | 608 | /* Utilization u column */ |
558 | 609 | ||
559 | col = glp_add_cols (mlp->prob, 1); | 610 | col = glp_add_cols (mlp->prob, 1); |
@@ -574,7 +625,7 @@ mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHas | |||
574 | glp_set_obj_coef (mlp->prob, col, mlp->co_R); | 625 | glp_set_obj_coef (mlp->prob, col, mlp->co_R); |
575 | /* Column lower bound = 0.0 */ | 626 | /* Column lower bound = 0.0 */ |
576 | glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); | 627 | glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0); |
577 | 628 | #if 0 | |
578 | /* Quality metric columns */ | 629 | /* Quality metric columns */ |
579 | col = glp_add_cols(mlp->prob, mlp->m_q); | 630 | col = glp_add_cols(mlp->prob, mlp->m_q); |
580 | for (c = 0; c < mlp->m_q; c++) | 631 | for (c = 0; c < mlp->m_q; c++) |
@@ -841,7 +892,7 @@ mlp_solve_problem (struct GAS_MLP_Handle *mlp) | |||
841 | } | 892 | } |
842 | 893 | ||
843 | #if DEBUG_ATS | 894 | #if DEBUG_ATS |
844 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved: %i %s\n", res, mlp_status_to_string(res)); | 895 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved\n"); |
845 | #endif | 896 | #endif |
846 | 897 | ||
847 | /* Process result */ | 898 | /* Process result */ |
@@ -975,7 +1026,7 @@ GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg, | |||
975 | 1026 | ||
976 | /* Init LP solving parameters */ | 1027 | /* Init LP solving parameters */ |
977 | glp_init_smcp(&mlp->control_param_lp); | 1028 | glp_init_smcp(&mlp->control_param_lp); |
978 | #if DEBUG_ATS | 1029 | #if VERBOSE_GLPK |
979 | mlp->control_param_lp.msg_lev = GLP_MSG_ALL; | 1030 | mlp->control_param_lp.msg_lev = GLP_MSG_ALL; |
980 | #else | 1031 | #else |
981 | mlp->control_param_lp.msg_lev = GLP_MSG_OFF; | 1032 | mlp->control_param_lp.msg_lev = GLP_MSG_OFF; |
@@ -985,7 +1036,7 @@ GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg, | |||
985 | 1036 | ||
986 | /* Init MLP solving parameters */ | 1037 | /* Init MLP solving parameters */ |
987 | glp_init_iocp(&mlp->control_param_mlp); | 1038 | glp_init_iocp(&mlp->control_param_mlp); |
988 | #if DEBUG_ATS | 1039 | #if VERBOSE_GLPK |
989 | mlp->control_param_mlp.msg_lev = GLP_MSG_ALL; | 1040 | mlp->control_param_mlp.msg_lev = GLP_MSG_ALL; |
990 | #else | 1041 | #else |
991 | mlp->control_param_mlp.msg_lev = GLP_MSG_OFF; | 1042 | mlp->control_param_mlp.msg_lev = GLP_MSG_OFF; |
@@ -1057,6 +1108,7 @@ GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_Mult | |||
1057 | { | 1108 | { |
1058 | peer->f_q[c] = 1.0; | 1109 | peer->f_q[c] = 1.0; |
1059 | } | 1110 | } |
1111 | peer->f = 1.0; | ||
1060 | 1112 | ||
1061 | memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity)); | 1113 | memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity)); |
1062 | GNUNET_assert(address->prev == NULL); | 1114 | GNUNET_assert(address->prev == NULL); |
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.h b/src/ats/gnunet-service-ats_addresses_mlp.h index f1a045dda..f5c243071 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.h +++ b/src/ats/gnunet-service-ats_addresses_mlp.h | |||
@@ -48,6 +48,14 @@ struct ATS_Peer | |||
48 | 48 | ||
49 | /* Array of quality preferences */ | 49 | /* Array of quality preferences */ |
50 | double f_q[GNUNET_ATS_QualityPropertiesCount]; | 50 | double f_q[GNUNET_ATS_QualityPropertiesCount]; |
51 | /* Legacy preference value */ | ||
52 | double f; | ||
53 | |||
54 | /* constraint 2: 1 address per peer*/ | ||
55 | unsigned int r_c2; | ||
56 | |||
57 | /* constraint 9: relativity */ | ||
58 | unsigned int r_c9; | ||
51 | 59 | ||
52 | struct ATS_Address *head; | 60 | struct ATS_Address *head; |
53 | struct ATS_Address *tail; | 61 | struct ATS_Address *tail; |
@@ -167,10 +175,16 @@ struct GAS_MLP_Handle | |||
167 | unsigned int cm_size; | 175 | unsigned int cm_size; |
168 | unsigned int ci; | 176 | unsigned int ci; |
169 | 177 | ||
178 | /* Row index constraint 2: */ | ||
179 | unsigned int r_c2; | ||
170 | /* Row index constraint 4: minimum connections */ | 180 | /* Row index constraint 4: minimum connections */ |
171 | unsigned int r_c4; | 181 | unsigned int r_c4; |
172 | /* Row index constraint 6: maximize diversity */ | 182 | /* Row index constraint 6: maximize diversity */ |
173 | unsigned int r_c6; | 183 | unsigned int r_c6; |
184 | /* Row index constraint 8: utilization*/ | ||
185 | unsigned int r_c8; | ||
186 | /* Row index constraint 9: relativity*/ | ||
187 | unsigned int r_c9; | ||
174 | 188 | ||
175 | /* column index Diversity (D) column */ | 189 | /* column index Diversity (D) column */ |
176 | int c_d; | 190 | int c_d; |
diff --git a/src/ats/test_ats_mlp.c b/src/ats/test_ats_mlp.c index b265c4bd7..145e748b8 100644 --- a/src/ats/test_ats_mlp.c +++ b/src/ats/test_ats_mlp.c | |||
@@ -29,7 +29,7 @@ | |||
29 | #include "gnunet_statistics_service.h" | 29 | #include "gnunet_statistics_service.h" |
30 | #include "gnunet-service-ats_addresses_mlp.h" | 30 | #include "gnunet-service-ats_addresses_mlp.h" |
31 | 31 | ||
32 | #define VERBOSE GNUNET_EXTRA_LOGGING | 32 | #define VERBOSE GNUNET_YES |
33 | #define VERBOSE_ARM GNUNET_EXTRA_LOGGING | 33 | #define VERBOSE_ARM GNUNET_EXTRA_LOGGING |
34 | 34 | ||
35 | #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3) | 35 | #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 3) |
@@ -53,38 +53,52 @@ check (void *cls, char *const *args, const char *cfgfile, | |||
53 | ret = 1; | 53 | ret = 1; |
54 | return; | 54 | return; |
55 | #endif | 55 | #endif |
56 | struct ATS_Address addr; | 56 | struct ATS_Address addr[10]; |
57 | 57 | ||
58 | stats = GNUNET_STATISTICS_create("ats", cfg); | 58 | stats = GNUNET_STATISTICS_create("ats", cfg); |
59 | 59 | ||
60 | addresses = GNUNET_CONTAINER_multihashmap_create (10); | 60 | addresses = GNUNET_CONTAINER_multihashmap_create (10); |
61 | 61 | ||
62 | GNUNET_CRYPTO_hash_create_random(GNUNET_CRYPTO_QUALITY_WEAK, &addr.peer.hashPubKey); | 62 | GNUNET_CRYPTO_hash_create_random(GNUNET_CRYPTO_QUALITY_WEAK, &addr[0].peer.hashPubKey); |
63 | addr.mlp_information = NULL; | 63 | addr[0].mlp_information = NULL; |
64 | addr.next = NULL; | 64 | addr[0].next = NULL; |
65 | addr.prev = NULL; | 65 | addr[0].prev = NULL; |
66 | addr.plugin = strdup ("dummy"); | 66 | addr[0].plugin = strdup ("dummy"); |
67 | GNUNET_CONTAINER_multihashmap_put(addresses, &addr.peer.hashPubKey, &addr, GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | 67 | |
68 | addr[1].peer = addr[0].peer; | ||
69 | addr[1].mlp_information = NULL; | ||
70 | addr[1].next = NULL; | ||
71 | addr[1].prev = NULL; | ||
72 | addr[1].plugin = strdup ("dummy2"); | ||
73 | |||
74 | GNUNET_CONTAINER_multihashmap_put(addresses, &addr[0].peer.hashPubKey, &addr[0], GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | ||
68 | 75 | ||
69 | mlp = GAS_mlp_init (cfg, NULL, MLP_MAX_EXEC_DURATION, MLP_MAX_ITERATIONS); | 76 | mlp = GAS_mlp_init (cfg, NULL, MLP_MAX_EXEC_DURATION, MLP_MAX_ITERATIONS); |
70 | 77 | ||
71 | /* Add a new address */ | 78 | /* Add a new address */ |
72 | GAS_mlp_address_update (mlp, addresses, &addr); | 79 | GAS_mlp_address_update (mlp, addresses, &addr[0]); |
73 | 80 | ||
74 | GNUNET_assert (mlp != NULL); | 81 | GNUNET_assert (mlp != NULL); |
75 | GNUNET_assert (mlp->addr_in_problem == 1); | 82 | GNUNET_assert (mlp->addr_in_problem == 1); |
76 | 83 | ||
77 | /* Update an new address */ | 84 | /* Update an new address */ |
78 | GAS_mlp_address_update (mlp, addresses, &addr); | 85 | GAS_mlp_address_update (mlp, addresses, &addr[0]); |
79 | GNUNET_assert (mlp->addr_in_problem == 1); | 86 | GNUNET_assert (mlp->addr_in_problem == 1); |
80 | 87 | ||
88 | /* Add a second address for same peer */ | ||
89 | GNUNET_CONTAINER_multihashmap_put(addresses, &addr[0].peer.hashPubKey, &addr[1], GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | ||
90 | GAS_mlp_address_update (mlp, addresses, &addr[1]); | ||
91 | GNUNET_assert (mlp->addr_in_problem == 2); | ||
92 | |||
81 | /* Delete an address */ | 93 | /* Delete an address */ |
82 | GNUNET_CONTAINER_multihashmap_remove (addresses, &addr.peer.hashPubKey, &addr); | 94 | GNUNET_CONTAINER_multihashmap_remove (addresses, &addr[0].peer.hashPubKey, &addr[0]); |
83 | GAS_mlp_address_delete (mlp, addresses, &addr); | 95 | GAS_mlp_address_delete (mlp, addresses, &addr[0]); |
96 | GAS_mlp_address_delete (mlp, addresses, &addr[1]); | ||
84 | 97 | ||
85 | GAS_mlp_done (mlp); | 98 | GAS_mlp_done (mlp); |
86 | 99 | ||
87 | GNUNET_free (addr.plugin); | 100 | GNUNET_free (addr[0].plugin); |
101 | GNUNET_free (addr[1].plugin); | ||
88 | GNUNET_CONTAINER_multihashmap_destroy (addresses); | 102 | GNUNET_CONTAINER_multihashmap_destroy (addresses); |
89 | GNUNET_STATISTICS_destroy(stats, GNUNET_NO); | 103 | GNUNET_STATISTICS_destroy(stats, GNUNET_NO); |
90 | 104 | ||