aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMatthias Wachs <wachs@net.in.tum.de>2013-02-22 13:32:12 +0000
committerMatthias Wachs <wachs@net.in.tum.de>2013-02-22 13:32:12 +0000
commitbffcd22f748a25a90fb3140bf5a820879e8d93ab (patch)
tree01f9baa77a50792ea4f704ac74790823000aba7c
parent42d065891b5fbb7bb59b0c60a4018709b1589a01 (diff)
downloadgnunet-bffcd22f748a25a90fb3140bf5a820879e8d93ab.tar.gz
gnunet-bffcd22f748a25a90fb3140bf5a820879e8d93ab.zip
implementing restructured problem creation
-rw-r--r--src/ats/gnunet-service-ats_addresses_mlp.c226
1 files changed, 142 insertions, 84 deletions
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c
index 74b54026c..943b2883b 100644
--- a/src/ats/gnunet-service-ats_addresses_mlp.c
+++ b/src/ats/gnunet-service-ats_addresses_mlp.c
@@ -814,32 +814,7 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON
814 * c 10) obey network specific quota 814 * c 10) obey network specific quota
815 */ 815 */
816 816
817 /* Row for c4) minimum connection */
818 name = "c4";
819 int min = mlp->pv.n_min;
820 /* Number of minimum connections is min(|Peers|, n_min) */
821 if (mlp->pv.n_min > p->num_peers)
822 min = p->num_peers;
823 p->r_c4 = glp_add_rows (p->prob, 1);
824 glp_set_row_name (p->prob, p->r_c4, name);
825 glp_set_row_bnds (p->prob, p->r_c4, GLP_LO, min, min);
826#if DEBUG_MLP_PROBLEM_CREATION
827 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
828 p->r_c4, name,
829 ">=", min);
830#endif
831 817
832 /* Add row for c6) */
833 name = "c6";
834 p->r_c6 = glp_add_rows (p->prob, 1);
835 /* Set type type to fix */
836 glp_set_row_name (p->prob, p->r_c6, name);
837 glp_set_row_bnds (p->prob, p->r_c6, GLP_FX, 0.0, 0.0);
838#if DEBUG_MLP_PROBLEM_CREATION
839 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
840 p->r_c6, name,
841 "==", 0);
842#endif
843 /* Setting -D */ 818 /* Setting -D */
844 ia[p->ci] = p->r_c6 ; 819 ia[p->ci] = p->r_c6 ;
845 ja[p->ci] = p->c_d; 820 ja[p->ci] = p->c_d;
@@ -850,23 +825,6 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON
850#endif 825#endif
851 p->ci++; 826 p->ci++;
852 827
853 /* Add rows for c 10) */
854 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
855 {
856 p->r_quota[c] = glp_add_rows (p->prob, 1);
857 char * text;
858 GNUNET_asprintf(&text, "quota_ats_%s", GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
859 glp_set_row_name (p->prob, p->r_quota[c], text);
860 /* Set bounds to 0 <= x <= quota_out */
861 glp_set_row_bnds (p->prob, p->r_quota[c], GLP_UP, 0.0, mlp->pv.quota_out[c]);
862#if DEBUG_MLP_PROBLEM_CREATION
863 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
864 p->r_quota[c], text,
865 "<=", mlp->pv.quota_out[c]);
866#endif
867 GNUNET_free (text);
868 }
869
870 GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_constraint_it, mlp); 828 GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_constraint_it, mlp);
871 829
872 /* Adding constraint rows 830 /* Adding constraint rows
@@ -883,18 +841,6 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON
883 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0 841 * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
884 * */ 842 * */
885 843
886 /* Adding rows for c 8) */
887 p->r_c8 = glp_add_rows (p->prob, p->num_peers);
888 name = "c8";
889 glp_set_row_name (p->prob, p->r_c8, "c8");
890 /* Set row bound == 0 */
891 glp_set_row_bnds (p->prob, p->r_c8, GLP_FX, 0.0, 0.0);
892#if DEBUG_MLP_PROBLEM_CREATION
893 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
894 p->r_c8, name,
895 "==", 0);
896#endif
897
898 /* -u */ 844 /* -u */
899 ia[p->ci] = p->r_c8; 845 ia[p->ci] = p->r_c8;
900 ja[p->ci] = p->c_u; 846 ja[p->ci] = p->c_u;
@@ -1040,7 +986,7 @@ mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CON
1040 } 986 }
1041} 987}
1042 988
1043 989#if 0
1044/** 990/**
1045 * Add columns for all addresses 991 * Add columns for all addresses
1046 * 992 *
@@ -1116,48 +1062,111 @@ mlp_create_address_columns_it (void *cls, const struct GNUNET_HashCode * key, vo
1116 1062
1117 return GNUNET_OK; 1063 return GNUNET_OK;
1118} 1064}
1065#endif
1119 1066
1120/** 1067/**
1121 * Create the MLP problem 1068 * Create the invariant columns c4, c6, c10, c8, c7
1122 *
1123 * @param mlp the MLP handle
1124 * @param addresses the hashmap containing all adresses
1125 * @return GNUNET_OK or GNUNET_SYSERR
1126 */ 1069 */
1127static int 1070static void
1128mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses) 1071mlp_create_problem_add_address_information (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1072{
1073
1074}
1075
1076
1077/**
1078 * Create the invariant columns c4, c6, c10, c8, c7
1079 */
1080static void
1081mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1129{ 1082{
1130 struct MLP_Problem *p = &mlp->p;
1131 int res = GNUNET_OK;
1132 int c;
1133 int cur_col;
1134 char *name; 1083 char *name;
1084 int c;
1135 1085
1136 LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n", 1086 /* Row for c4) minimum connection */
1137 GNUNET_CONTAINER_multihashmap_size(mlp->peers)); 1087 name = "c4";
1088 int min = mlp->pv.n_min;
1089 /* Number of minimum connections is min(|Peers|, n_min) */
1090 if (mlp->pv.n_min > p->num_peers)
1091 min = p->num_peers;
1092 p->r_c4 = glp_add_rows (p->prob, 1);
1093 glp_set_row_name (p->prob, p->r_c4, name);
1094 glp_set_row_bnds (p->prob, p->r_c4, GLP_LO, min, min);
1095#if DEBUG_MLP_PROBLEM_CREATION
1096 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1097 p->r_c4, name,
1098 ">=", min);
1099#endif
1138 1100
1139 GNUNET_assert (p->prob == NULL); 1101 /* Add row for c6) */
1140 GNUNET_assert (p->ia == NULL); 1102 name = "c6";
1141 GNUNET_assert (p->ja == NULL); 1103 p->r_c6 = glp_add_rows (p->prob, 1);
1142 GNUNET_assert (p->ar == NULL); 1104 /* Set type type to fix */
1105 glp_set_row_name (p->prob, p->r_c6, name);
1106 glp_set_row_bnds (p->prob, p->r_c6, GLP_FX, 0.0, 0.0);
1107#if DEBUG_MLP_PROBLEM_CREATION
1108 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1109 p->r_c6, name,
1110 "==", 0);
1111#endif
1143 1112
1113 /* Add rows for c 10) */
1114 for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
1115 {
1116 p->r_quota[c] = glp_add_rows (p->prob, 1);
1117 char * text;
1118 GNUNET_asprintf(&text, "quota_ats_%s", GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
1119 glp_set_row_name (p->prob, p->r_quota[c], text);
1120 /* Set bounds to 0 <= x <= quota_out */
1121 glp_set_row_bnds (p->prob, p->r_quota[c], GLP_UP, 0.0, mlp->pv.quota_out[c]);
1122#if DEBUG_MLP_PROBLEM_CREATION
1123 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1124 p->r_quota[c], text,
1125 "<=", mlp->pv.quota_out[c]);
1126#endif
1127 GNUNET_free (text);
1128 }
1144 1129
1145 /* Reset MLP problem struct */ 1130 /* Adding rows for c 8) */
1146 p->num_addresses = 0; 1131 p->r_c8 = glp_add_rows (p->prob, p->num_peers);
1147 p->num_peers = GNUNET_CONTAINER_multihashmap_size (mlp->peers); 1132 name = "c8";
1133 glp_set_row_name (p->prob, p->r_c8, "c8");
1134 /* Set row bound == 0 */
1135 glp_set_row_bnds (p->prob, p->r_c8, GLP_FX, 0.0, 0.0);
1136#if DEBUG_MLP_PROBLEM_CREATION
1137 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1138 p->r_c8, name,
1139 "==", 0);
1140#endif
1148 1141
1149 /* create the glpk problem */ 1142 /* c 7) For all quality metrics */
1150 p->prob = glp_create_prob (); 1143 for (c = 0; c < mlp->pv.m_q; c++)
1151 p->num_addresses = 0;; 1144 {
1152 GNUNET_assert (NULL != p->prob); 1145 p->r_q[c] = glp_add_rows (p->prob, 1);
1146 GNUNET_asprintf(&name, "c7_q%i_%s", c, mlp_ats_to_string(mlp->pv.q[c]));
1147 glp_set_row_name (p->prob, p->r_q[c], name);
1148 /* Set row bound == 0 */
1149 glp_set_row_bnds (p->prob, p->r_q[c], GLP_FX, 0.0, 0.0);
1150#if DEBUG_MLP_PROBLEM_CREATION
1151 LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s %u\n",
1152 p->r_q[c], name,
1153 "<=", 0);
1154#endif
1155 GNUNET_free (name);
1156 }
1157}
1153 1158
1154 /* Set a problem name */
1155 glp_set_prob_name (p->prob, "GNUnet ats bandwidth distribution");
1156 1159
1157 /* Set optimization direction to maximize */ 1160/**
1158 glp_set_obj_dir (p->prob, GLP_MAX); 1161 * Create the invariant columns d, u, r, q0 ... qm
1162 */
1163static void
1164mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
1165{
1166 char *name;
1167 int c;
1168 int cur_col;
1159 1169
1160 /* Adding invariant columns */
1161 /* Diversity d column */ 1170 /* Diversity d column */
1162 p->c_d = glp_add_cols (p->prob, 1); 1171 p->c_d = glp_add_cols (p->prob, 1);
1163 /* Column name */ 1172 /* Column name */
@@ -1215,7 +1224,55 @@ mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHas
1215#endif 1224#endif
1216 GNUNET_free (name); 1225 GNUNET_free (name);
1217 } 1226 }
1227}
1228
1229
1230/**
1231 * Create the MLP problem
1232 *
1233 * @param mlp the MLP handle
1234 * @param addresses the hashmap containing all adresses
1235 * @return GNUNET_OK or GNUNET_SYSERR
1236 */
1237static int
1238mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
1239{
1240 struct MLP_Problem *p = &mlp->p;
1241 int res = GNUNET_OK;
1242
1243 LOG (GNUNET_ERROR_TYPE_DEBUG, "Rebuilding problem for %u peer(s) \n",
1244 GNUNET_CONTAINER_multihashmap_size(mlp->peers));
1218 1245
1246 GNUNET_assert (p->prob == NULL);
1247 GNUNET_assert (p->ia == NULL);
1248 GNUNET_assert (p->ja == NULL);
1249 GNUNET_assert (p->ar == NULL);
1250
1251
1252 /* Reset MLP problem struct */
1253 p->num_addresses = 0;
1254 p->num_peers = GNUNET_CONTAINER_multihashmap_size (mlp->peers);
1255
1256 /* create the glpk problem */
1257 p->prob = glp_create_prob ();
1258 p->num_addresses = 0;;
1259 GNUNET_assert (NULL != p->prob);
1260
1261 /* Set a problem name */
1262 glp_set_prob_name (p->prob, "GNUnet ats bandwidth distribution");
1263 /* Set optimization direction to maximize */
1264 glp_set_obj_dir (p->prob, GLP_MAX);
1265
1266 /* Adding invariant columns */
1267 mlp_create_problem_add_invariant_columns (mlp, p);
1268
1269 /* Adding address independent constraint rows */
1270 mlp_create_problem_add_invariant_rows (mlp, p);
1271
1272 /* Adding address independent constraint rows */
1273 mlp_create_problem_add_address_information (mlp, p);
1274
1275#if 0
1219 /* Add columns for addresses */ 1276 /* Add columns for addresses */
1220 GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_address_columns_it, mlp); 1277 GNUNET_CONTAINER_multihashmap_iterate (addresses, mlp_create_address_columns_it, mlp);
1221 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problems contains %u peers, %u addresses, %u addresses skipped \n", 1278 LOG (GNUNET_ERROR_TYPE_DEBUG, "Problems contains %u peers, %u addresses, %u addresses skipped \n",
@@ -1224,6 +1281,7 @@ mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHas
1224 1281
1225 /* Add constraints rows */ 1282 /* Add constraints rows */
1226 mlp_add_constraints_all_addresses (mlp, addresses); 1283 mlp_add_constraints_all_addresses (mlp, addresses);
1284# endif
1227 1285
1228 /* Load the matrix */ 1286 /* Load the matrix */
1229 LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n"); 1287 LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");