diff options
author | Matthias Wachs <wachs@net.in.tum.de> | 2012-01-18 11:14:55 +0000 |
---|---|---|
committer | Matthias Wachs <wachs@net.in.tum.de> | 2012-01-18 11:14:55 +0000 |
commit | a827aeaf11f556657ef75e6691ff685db14daadf (patch) | |
tree | 886d061a16653f6d15f4f12e4cfcd6bfdd0d84cc /src/ats | |
parent | 9bce094f751c1e80a41c4ea509845205e8842845 (diff) | |
download | gnunet-a827aeaf11f556657ef75e6691ff685db14daadf.tar.gz gnunet-a827aeaf11f556657ef75e6691ff685db14daadf.zip |
- adding constraint handling
Diffstat (limited to 'src/ats')
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_mlp.c | 128 | ||||
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_mlp.h | 9 |
2 files changed, 125 insertions, 12 deletions
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c index 452d782f8..a878ddd9e 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.c +++ b/src/ats/gnunet-service-ats_addresses_mlp.c | |||
@@ -34,6 +34,7 @@ | |||
34 | #endif | 34 | #endif |
35 | 35 | ||
36 | #define DEBUG_ATS GNUNET_YES | 36 | #define DEBUG_ATS GNUNET_YES |
37 | #define VERY_BIG_DOUBLE_VALUE DBL_MAX | ||
37 | 38 | ||
38 | /** | 39 | /** |
39 | * Translate glpk solver error codes to text | 40 | * Translate glpk solver error codes to text |
@@ -162,19 +163,117 @@ mlp_term_hook (void *info, const char *s) | |||
162 | } | 163 | } |
163 | 164 | ||
164 | /** | 165 | /** |
166 | * Delete the MLP problem and free the constrain matrix | ||
167 | * | ||
168 | * @param mlp the MLP handle | ||
169 | */ | ||
170 | static void | ||
171 | mlp_delete_problem (struct GAS_MLP_Handle *mlp) | ||
172 | { | ||
173 | if (mlp != NULL) | ||
174 | { | ||
175 | glp_delete_prob(mlp->prob); | ||
176 | |||
177 | /* delete row index */ | ||
178 | if (mlp->ia != NULL) | ||
179 | GNUNET_free (mlp->ia); | ||
180 | |||
181 | /* delete column index */ | ||
182 | if (mlp->ja != NULL) | ||
183 | GNUNET_free (mlp->ja); | ||
184 | |||
185 | /* delete coefficients */ | ||
186 | if (mlp->ar != NULL) | ||
187 | GNUNET_free (mlp->ar); | ||
188 | } | ||
189 | } | ||
190 | |||
191 | /** | ||
192 | * Adds the problem constraints for all addresses | ||
193 | * Required for problem recreation after address deletion | ||
194 | * | ||
195 | * @param addresses all addresses | ||
196 | */ | ||
197 | |||
198 | static void | ||
199 | mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) | ||
200 | { | ||
201 | //double M = VERY_BIG_DOUBLE_VALUE; | ||
202 | unsigned int n_addresses; | ||
203 | |||
204 | /* Problem matrix*/ | ||
205 | n_addresses = GNUNET_CONTAINER_multihashmap_size(addresses); | ||
206 | |||
207 | /* Required indices in the constrain matrix | ||
208 | * | ||
209 | * feasibility constraints: | ||
210 | * | ||
211 | * c 1) bandwidth capping | ||
212 | * #rows: |n_addresses| | ||
213 | * #indices: 2 * |n_addresses| | ||
214 | * | ||
215 | * c 2) one active address per peer | ||
216 | * #rows: |peers| | ||
217 | * #indices: |n_addresses| | ||
218 | * | ||
219 | * c 3) minium bandwidth assigned | ||
220 | * #rows: |n_addresses| | ||
221 | * #indices: 2 * |n_addresses| | ||
222 | * | ||
223 | * c 4) minimum number of active connections | ||
224 | * #rows: 1 | ||
225 | * #indices: |n_addresses| | ||
226 | * | ||
227 | * c 5) maximum ressource consumption | ||
228 | * #rows: |ressources| | ||
229 | * #indices: |n_addresses| | ||
230 | * | ||
231 | * Sum for feasibility constraints: | ||
232 | * #rows: 3 * |n_addresses| + |ressources| + |peers| + 1 | ||
233 | * #indices: 7 * |n_addresses| | ||
234 | * | ||
235 | * optimality constraints: | ||
236 | * tbc | ||
237 | * */ | ||
238 | |||
239 | int pi = (7 * n_addresses); | ||
240 | mlp->cm_size = pi; | ||
241 | |||
242 | /* row index */ | ||
243 | int *ia = GNUNET_malloc (pi * sizeof (int)); | ||
244 | mlp->ia = ia; | ||
245 | |||
246 | /* column index */ | ||
247 | int *ja = GNUNET_malloc (pi * sizeof (int)); | ||
248 | mlp->ja = ja; | ||
249 | |||
250 | /* coefficient */ | ||
251 | double *ar= GNUNET_malloc (pi * sizeof (double)); | ||
252 | mlp->ar = ar; | ||
253 | |||
254 | |||
255 | /* Adding constraint rows */ | ||
256 | /* Feasibility constraints */ | ||
257 | |||
258 | /* c 1) bandwidth capping */ | ||
259 | |||
260 | } | ||
261 | |||
262 | /** | ||
165 | * Create the MLP problem | 263 | * Create the MLP problem |
166 | * | 264 | * |
167 | * @param mlp the MLP handle | 265 | * @param mlp the MLP handle |
168 | * @return GNUNET_OK or GNUNET_SYSERR | 266 | * @return GNUNET_OK or GNUNET_SYSERR |
169 | */ | 267 | */ |
170 | static int | 268 | static int |
171 | mlp_create_problem (struct GAS_MLP_Handle *mlp) | 269 | mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) |
172 | { | 270 | { |
173 | int res = GNUNET_OK; | 271 | int res = GNUNET_OK; |
174 | int col; | 272 | int col; |
175 | int c; | 273 | int c; |
176 | char *name; | 274 | char *name; |
177 | 275 | ||
276 | |||
178 | /* Set a problem name */ | 277 | /* Set a problem name */ |
179 | glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution"); | 278 | glp_set_prob_name (mlp->prob, "gnunet ats bandwidth distribution"); |
180 | 279 | ||
@@ -229,6 +328,8 @@ mlp_create_problem (struct GAS_MLP_Handle *mlp) | |||
229 | glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]); | 328 | glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]); |
230 | } | 329 | } |
231 | 330 | ||
331 | /* Add columns for existing addresses */ | ||
332 | |||
232 | return res; | 333 | return res; |
233 | } | 334 | } |
234 | 335 | ||
@@ -585,7 +686,6 @@ GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg, | |||
585 | mlp->n_min = n_min; | 686 | mlp->n_min = n_min; |
586 | mlp->m = GNUNET_ATS_QualityPropertiesCount; | 687 | mlp->m = GNUNET_ATS_QualityPropertiesCount; |
587 | 688 | ||
588 | mlp_create_problem (mlp); | ||
589 | return mlp; | 689 | return mlp; |
590 | } | 690 | } |
591 | 691 | ||
@@ -614,10 +714,22 @@ GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_Mult | |||
614 | 714 | ||
615 | /* We add a new address */ | 715 | /* We add a new address */ |
616 | if (address->mlp_information == NULL) | 716 | if (address->mlp_information == NULL) |
617 | { | ||
618 | new = GNUNET_YES; | 717 | new = GNUNET_YES; |
718 | else | ||
719 | new = GNUNET_NO; | ||
720 | |||
721 | if (mlp->prob == NULL) | ||
722 | { | ||
723 | mlp_create_problem(mlp, addresses); | ||
724 | mlp_add_constraints_all_addresses (mlp, addresses); | ||
725 | } | ||
726 | |||
727 | /* Do the update */ | ||
728 | if (new == GNUNET_YES) | ||
729 | { | ||
619 | mlpi = GNUNET_malloc (sizeof (struct MLP_information)); | 730 | mlpi = GNUNET_malloc (sizeof (struct MLP_information)); |
620 | address->mlp_information = mlpi; | 731 | address->mlp_information = mlpi; |
732 | mlp->addr_in_problem ++; | ||
621 | 733 | ||
622 | /* Add bandwidth column */ | 734 | /* Add bandwidth column */ |
623 | col = glp_add_cols (mlp->prob, 2); | 735 | col = glp_add_cols (mlp->prob, 2); |
@@ -646,14 +758,7 @@ GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_Mult | |||
646 | glp_set_obj_coef (mlp->prob, mlpi->c_n, 0); | 758 | glp_set_obj_coef (mlp->prob, mlpi->c_n, 0); |
647 | 759 | ||
648 | /* Add */ | 760 | /* Add */ |
649 | |||
650 | |||
651 | mlp->addr_in_problem ++; | ||
652 | } | 761 | } |
653 | else | ||
654 | new = GNUNET_NO; | ||
655 | |||
656 | /* Do the update */ | ||
657 | 762 | ||
658 | /* Recalculate */ | 763 | /* Recalculate */ |
659 | if (new == GNUNET_YES) | 764 | if (new == GNUNET_YES) |
@@ -717,8 +822,7 @@ GAS_mlp_done (struct GAS_MLP_Handle *mlp) | |||
717 | mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; | 822 | mlp->mlp_task = GNUNET_SCHEDULER_NO_TASK; |
718 | } | 823 | } |
719 | 824 | ||
720 | if (mlp != NULL) | 825 | mlp_delete_problem (mlp); |
721 | glp_delete_prob(mlp->prob); | ||
722 | 826 | ||
723 | /* Clean up GLPK environment */ | 827 | /* Clean up GLPK environment */ |
724 | glp_free_env(); | 828 | glp_free_env(); |
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.h b/src/ats/gnunet-service-ats_addresses_mlp.h index f72cb7c23..56616ae85 100644 --- a/src/ats/gnunet-service-ats_addresses_mlp.h +++ b/src/ats/gnunet-service-ats_addresses_mlp.h | |||
@@ -135,6 +135,15 @@ struct GAS_MLP_Handle | |||
135 | 135 | ||
136 | /* Information about the problem */ | 136 | /* Information about the problem */ |
137 | 137 | ||
138 | /* current problem matrix */ | ||
139 | /* row index array */ | ||
140 | int *ia; | ||
141 | /* column index array */ | ||
142 | int *ja; | ||
143 | /* column index array */ | ||
144 | double *ar; | ||
145 | /* current size of the constraint matrix |indices| */ | ||
146 | unsigned int cm_size; | ||
138 | 147 | ||
139 | /* column index Diversity (D) column */ | 148 | /* column index Diversity (D) column */ |
140 | int c_d; | 149 | int c_d; |