diff options
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_simplistic.c | 286 |
1 files changed, 169 insertions, 117 deletions
diff --git a/src/ats/gnunet-service-ats_addresses_simplistic.c b/src/ats/gnunet-service-ats_addresses_simplistic.c index b5df2a1f6..7b95eed2d 100644 --- a/src/ats/gnunet-service-ats_addresses_simplistic.c +++ b/src/ats/gnunet-service-ats_addresses_simplistic.c | |||
@@ -55,7 +55,7 @@ | |||
55 | * | 55 | * |
56 | */ | 56 | */ |
57 | 57 | ||
58 | #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1) | 58 | #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10) |
59 | #define PREF_AGING_FACTOR 0.95 | 59 | #define PREF_AGING_FACTOR 0.95 |
60 | 60 | ||
61 | #define DEFAULT_PREFERENCE 1.0 | 61 | #define DEFAULT_PREFERENCE 1.0 |
@@ -165,19 +165,6 @@ struct AddressWrapper | |||
165 | }; | 165 | }; |
166 | 166 | ||
167 | 167 | ||
168 | struct PreferencePeer | ||
169 | { | ||
170 | struct PreferencePeer *next; | ||
171 | struct PreferencePeer *prev; | ||
172 | struct GNUNET_PeerIdentity id; | ||
173 | |||
174 | double f[GNUNET_ATS_PreferenceCount]; | ||
175 | double f_rel[GNUNET_ATS_PreferenceCount]; | ||
176 | double f_rel_total; | ||
177 | |||
178 | GNUNET_SCHEDULER_TaskIdentifier aging_task; | ||
179 | }; | ||
180 | |||
181 | struct PreferenceClient | 168 | struct PreferenceClient |
182 | { | 169 | { |
183 | struct PreferenceClient *prev; | 170 | struct PreferenceClient *prev; |
@@ -191,6 +178,21 @@ struct PreferenceClient | |||
191 | }; | 178 | }; |
192 | 179 | ||
193 | 180 | ||
181 | struct PreferencePeer | ||
182 | { | ||
183 | struct PreferencePeer *next; | ||
184 | struct PreferencePeer *prev; | ||
185 | struct PreferenceClient *client; | ||
186 | struct GAS_SIMPLISTIC_Handle *s; | ||
187 | struct GNUNET_PeerIdentity id; | ||
188 | |||
189 | double f[GNUNET_ATS_PreferenceCount]; | ||
190 | double f_rel[GNUNET_ATS_PreferenceCount]; | ||
191 | double f_rel_total; | ||
192 | |||
193 | GNUNET_SCHEDULER_TaskIdentifier aging_task; | ||
194 | }; | ||
195 | |||
194 | /** | 196 | /** |
195 | * Get the prefered address for a specific peer | 197 | * Get the prefered address for a specific peer |
196 | * | 198 | * |
@@ -399,6 +401,7 @@ bw_available_in_network (struct Network *net) | |||
399 | return GNUNET_NO; | 401 | return GNUNET_NO; |
400 | } | 402 | } |
401 | 403 | ||
404 | |||
402 | /** | 405 | /** |
403 | * Update the quotas for a network type | 406 | * Update the quotas for a network type |
404 | * | 407 | * |
@@ -536,6 +539,15 @@ update_quota_per_network (struct GAS_SIMPLISTIC_Handle *s, | |||
536 | } | 539 | } |
537 | 540 | ||
538 | static void | 541 | static void |
542 | update_all_networks (struct GAS_SIMPLISTIC_Handle *s) | ||
543 | { | ||
544 | int i; | ||
545 | for (i = 0; i < s->networks; i++) | ||
546 | update_quota_per_network (s, &s->network_entries[i], NULL); | ||
547 | |||
548 | } | ||
549 | |||
550 | static void | ||
539 | addresse_increment (struct GAS_SIMPLISTIC_Handle *s, | 551 | addresse_increment (struct GAS_SIMPLISTIC_Handle *s, |
540 | struct Network *net, | 552 | struct Network *net, |
541 | int total, | 553 | int total, |
@@ -1076,72 +1088,99 @@ GAS_simplistic_get_preferred_address (void *solver, | |||
1076 | } | 1088 | } |
1077 | 1089 | ||
1078 | static void | 1090 | static void |
1079 | update_preference (struct GAS_SIMPLISTIC_Handle *s, | 1091 | recalculate_preferences (struct PreferencePeer *p) |
1080 | struct PreferenceClient *cur, | ||
1081 | struct PreferencePeer *p, | ||
1082 | enum GNUNET_ATS_PreferenceKind kind, | ||
1083 | float score_f) | ||
1084 | { | 1092 | { |
1085 | double p_rel_global; | 1093 | struct GAS_SIMPLISTIC_Handle *s = p->s; |
1094 | struct PreferencePeer *p_cur; | ||
1095 | struct PreferenceClient *c_cur = p->client; | ||
1096 | double p_rel_global; | ||
1086 | double *dest; | 1097 | double *dest; |
1087 | double score = score_f; | 1098 | int kind; |
1088 | struct PreferencePeer *p_cur; | 1099 | int rkind; |
1089 | int i; | ||
1090 | int clients; | 1100 | int clients; |
1091 | 1101 | ||
1092 | /* Update preference value according to type */ | 1102 | /** |
1093 | switch (kind) { | 1103 | * Idea: |
1094 | case GNUNET_ATS_PREFERENCE_BANDWIDTH: | 1104 | * |
1095 | case GNUNET_ATS_PREFERENCE_LATENCY: | 1105 | * We have: |
1096 | p->f[kind] = (p->f[kind] + score) / 2; | 1106 | * Set of clients c |
1097 | break; | 1107 | * Set of peers p_i in P |
1098 | case GNUNET_ATS_PREFERENCE_END: | 1108 | * Set of preference kinds k |
1099 | break; | 1109 | * A preference value f_k_p_i with an unknown range |
1100 | default: | 1110 | * |
1101 | break; | 1111 | * We get: |
1102 | } | 1112 | * A client specific relative preference f_p_i_rel [1..2] for all peers |
1103 | 1113 | * | |
1104 | /* Recalcalculate total preference for this quality kind over all peers*/ | 1114 | * For every client c |
1105 | cur->f_total[kind] = 0; | 1115 | * { |
1106 | for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) | 1116 | * For every preference kind k: |
1107 | cur->f_total[kind] += p_cur->f[kind]; | 1117 | * { |
1108 | 1118 | * We remember for the preference f_p_i for each peer p_i. | |
1109 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n", | 1119 | * We have a default preference value f_p_i = 0 |
1110 | cur->client, | 1120 | * We have a sum of all preferences f_t = sum (f_p_i) |
1111 | GNUNET_ATS_print_preference_type (kind), | 1121 | * So we can calculate a relative preference value fr_p_i: |
1112 | cur->f_total[kind]); | 1122 | * |
1123 | * f_k_p_i_rel = (f_t + f_p_i) / f_t | ||
1124 | * f_k_p_i_rel = [1..2], default 1.0 | ||
1125 | * } | ||
1126 | * f_p_i_rel = sum (f_k_p_i_rel) / #k | ||
1127 | * } | ||
1128 | * | ||
1129 | **/ | ||
1113 | 1130 | ||
1114 | /* Recalcalculate relative preference for all peers */ | 1131 | /* For this client: for all preferences, except TERMINATOR */ |
1115 | for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) | 1132 | for (kind = GNUNET_ATS_PREFERENCE_END + 1 ; kind < GNUNET_ATS_PreferenceCount; kind ++) |
1116 | { | 1133 | { |
1117 | /* Calculate relative preference for specific kind */ | 1134 | /* Recalcalculate total preference for this quality kind over all peers*/ |
1118 | p_cur->f_rel[kind] = (cur->f_total[kind] + p_cur->f[kind]) / cur->f_total[kind]; | 1135 | c_cur->f_total[kind] = 0; |
1119 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n", | 1136 | for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) |
1120 | cur->client, | 1137 | c_cur->f_total[kind] += p_cur->f[kind]; |
1121 | GNUNET_i2s (&p_cur->id), | 1138 | |
1122 | GNUNET_ATS_print_preference_type (kind), | 1139 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n", |
1123 | p_cur->f_rel[kind]); | 1140 | c_cur->client, |
1124 | 1141 | GNUNET_ATS_print_preference_type (kind), | |
1125 | /* Calculate peer relative preference | 1142 | c_cur->f_total[kind]); |
1126 | * Start with i = 1 to exclude terminator */ | 1143 | |
1127 | p_cur->f_rel_total = 0; | 1144 | /* Recalcalculate relative preference for all peers */ |
1128 | for (i = 1; i < GNUNET_ATS_PreferenceCount; i ++) | 1145 | for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) |
1129 | { | 1146 | { |
1130 | p_cur->f_rel_total += p_cur->f_rel[i]; | 1147 | /* Calculate relative preference for specific kind */ |
1131 | } | 1148 | if (0.0 == c_cur->f_total[kind]) |
1132 | p_cur->f_rel_total /= (GNUNET_ATS_PreferenceCount - 1.0); /* -1 due to terminator */ | 1149 | { |
1133 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has total relative preference of %.3f\n", | 1150 | /* No one has preference, so set default preference */ |
1134 | cur->client, | 1151 | p_cur->f_rel[kind] = DEFAULT_PREFERENCE; |
1135 | GNUNET_i2s (&p_cur->id), | 1152 | } |
1136 | p_cur->f_rel_total); | 1153 | else |
1154 | { | ||
1155 | p_cur->f_rel[kind] = (c_cur->f_total[kind] + p_cur->f[kind]) / c_cur->f_total[kind]; | ||
1156 | } | ||
1157 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n", | ||
1158 | c_cur->client, | ||
1159 | GNUNET_i2s (&p_cur->id), | ||
1160 | GNUNET_ATS_print_preference_type (kind), | ||
1161 | p_cur->f_rel[kind]); | ||
1162 | |||
1163 | /* Calculate peer relative preference */ | ||
1164 | /* Start with kind = 1 to exclude terminator */ | ||
1165 | p_cur->f_rel_total = 0; | ||
1166 | for (rkind = GNUNET_ATS_PREFERENCE_END + 1; rkind < GNUNET_ATS_PreferenceCount; rkind ++) | ||
1167 | { | ||
1168 | p_cur->f_rel_total += p_cur->f_rel[rkind]; | ||
1169 | } | ||
1170 | p_cur->f_rel_total /= (GNUNET_ATS_PreferenceCount - 1.0); /* -1 due to terminator */ | ||
1171 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has total relative preference of %.3f\n", | ||
1172 | c_cur->client, | ||
1173 | GNUNET_i2s (&p_cur->id), | ||
1174 | p_cur->f_rel_total); | ||
1175 | } | ||
1137 | } | 1176 | } |
1138 | 1177 | ||
1139 | /* Calculcate global total relative peer preference over all clients */ | 1178 | /* Calculcate global total relative peer preference over all clients */ |
1140 | p_rel_global = 0.0; | 1179 | p_rel_global = 0.0; |
1141 | clients = 0; | 1180 | clients = 0; |
1142 | for (cur = s->pc_head; NULL != cur; cur = cur->next) | 1181 | for (c_cur = s->pc_head; NULL != c_cur; c_cur = c_cur->next) |
1143 | { | 1182 | { |
1144 | for (p_cur = cur->p_head; NULL != p_cur; p_cur = p_cur->next) | 1183 | for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) |
1145 | if (0 == memcmp (&p_cur->id, &p->id, sizeof (p_cur->id))) | 1184 | if (0 == memcmp (&p_cur->id, &p->id, sizeof (p_cur->id))) |
1146 | break; | 1185 | break; |
1147 | if (NULL != p_cur) | 1186 | if (NULL != p_cur) |
@@ -1169,16 +1208,56 @@ update_preference (struct GAS_SIMPLISTIC_Handle *s, | |||
1169 | } | 1208 | } |
1170 | } | 1209 | } |
1171 | 1210 | ||
1211 | static void | ||
1212 | update_preference (struct PreferencePeer *p, | ||
1213 | enum GNUNET_ATS_PreferenceKind kind, | ||
1214 | float score_f) | ||
1215 | { | ||
1216 | double score = score_f; | ||
1217 | |||
1218 | /* Update preference value according to type */ | ||
1219 | switch (kind) { | ||
1220 | case GNUNET_ATS_PREFERENCE_BANDWIDTH: | ||
1221 | case GNUNET_ATS_PREFERENCE_LATENCY: | ||
1222 | p->f[kind] = (p->f[kind] + score) / 2; | ||
1223 | break; | ||
1224 | case GNUNET_ATS_PREFERENCE_END: | ||
1225 | break; | ||
1226 | default: | ||
1227 | break; | ||
1228 | } | ||
1229 | recalculate_preferences(p); | ||
1230 | update_all_networks (p->s); | ||
1231 | } | ||
1232 | |||
1172 | 1233 | ||
1173 | static void | 1234 | static void |
1174 | preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | 1235 | preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) |
1175 | { | 1236 | { |
1237 | int i; | ||
1238 | double backup; | ||
1176 | struct PreferencePeer *p = cls; | 1239 | struct PreferencePeer *p = cls; |
1177 | GNUNET_assert (NULL != p); | 1240 | GNUNET_assert (NULL != p); |
1241 | |||
1242 | |||
1178 | p->aging_task = GNUNET_SCHEDULER_NO_TASK; | 1243 | p->aging_task = GNUNET_SCHEDULER_NO_TASK; |
1179 | 1244 | ||
1180 | /* LOG (GNUNET_ERROR_TYPE_ERROR, "Aging preferences for peer `%s'\n", | 1245 | LOG (GNUNET_ERROR_TYPE_ERROR, "Aging preferences for peer `%s'\n", |
1181 | GNUNET_i2s (&p->id));*/ | 1246 | GNUNET_i2s (&p->id)); |
1247 | |||
1248 | for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) | ||
1249 | { | ||
1250 | if (p->f[1] > 1.0) | ||
1251 | { | ||
1252 | backup = p->f[i]; | ||
1253 | p->f[i] *= PREF_AGING_FACTOR; | ||
1254 | LOG (GNUNET_ERROR_TYPE_ERROR, "Aged preference for peer `%s' from %.3f to %.3f\n", | ||
1255 | GNUNET_i2s (&p->id), backup, p->f[i]); | ||
1256 | } | ||
1257 | } | ||
1258 | |||
1259 | recalculate_preferences (p); | ||
1260 | update_all_networks (p->s); | ||
1182 | 1261 | ||
1183 | p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, | 1262 | p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, |
1184 | &preference_aging, p); | 1263 | &preference_aging, p); |
@@ -1203,8 +1282,8 @@ GAS_simplistic_address_change_preference (void *solver, | |||
1203 | { | 1282 | { |
1204 | static struct GNUNET_TIME_Absolute next_update; | 1283 | static struct GNUNET_TIME_Absolute next_update; |
1205 | struct GAS_SIMPLISTIC_Handle *s = solver; | 1284 | struct GAS_SIMPLISTIC_Handle *s = solver; |
1206 | struct PreferenceClient *cur; | 1285 | struct PreferenceClient *c_cur; |
1207 | struct PreferencePeer *p; | 1286 | struct PreferencePeer *p_cur; |
1208 | int i; | 1287 | int i; |
1209 | 1288 | ||
1210 | GNUNET_assert (NULL != solver); | 1289 | GNUNET_assert (NULL != solver); |
@@ -1223,72 +1302,45 @@ GAS_simplistic_address_change_preference (void *solver, | |||
1223 | return; | 1302 | return; |
1224 | } | 1303 | } |
1225 | 1304 | ||
1226 | /** | ||
1227 | * Idea: | ||
1228 | * | ||
1229 | * We have: | ||
1230 | * Set of clients c | ||
1231 | * Set of peers p_i in P | ||
1232 | * Set of preference kinds k | ||
1233 | * A preference value f_k_p_i with an unknown range | ||
1234 | * | ||
1235 | * We get: | ||
1236 | * A client specific relative preference f_p_i_rel [1..2] for all peers | ||
1237 | * | ||
1238 | * For every client c | ||
1239 | * { | ||
1240 | * For every preference kind k: | ||
1241 | * { | ||
1242 | * We remember for the preference f_p_i for each peer p_i. | ||
1243 | * We have a default preference value f_p_i = 0 | ||
1244 | * We have a sum of all preferences f_t = sum (f_p_i) | ||
1245 | * So we can calculate a relative preference value fr_p_i: | ||
1246 | * | ||
1247 | * f_k_p_i_rel = (f_t + f_p_i) / f_t | ||
1248 | * f_k_p_i_rel = [1..2], default 1.0 | ||
1249 | * } | ||
1250 | * f_p_i_rel = sum (f_k_p_i_rel) / #k | ||
1251 | * } | ||
1252 | * | ||
1253 | **/ | ||
1254 | |||
1255 | /* Find preference client */ | 1305 | /* Find preference client */ |
1256 | for (cur = s->pc_head; NULL != cur; cur = cur->next) | 1306 | for (c_cur = s->pc_head; NULL != c_cur; c_cur = c_cur->next) |
1257 | { | 1307 | { |
1258 | if (client == cur->client) | 1308 | if (client == c_cur->client) |
1259 | break; | 1309 | break; |
1260 | } | 1310 | } |
1261 | /* Not found: create new preference client */ | 1311 | /* Not found: create new preference client */ |
1262 | if (NULL == cur) | 1312 | if (NULL == c_cur) |
1263 | { | 1313 | { |
1264 | cur = GNUNET_malloc (sizeof (struct PreferenceClient)); | 1314 | c_cur = GNUNET_malloc (sizeof (struct PreferenceClient)); |
1265 | cur->client = client; | 1315 | c_cur->client = client; |
1266 | GNUNET_CONTAINER_DLL_insert (s->pc_head, s->pc_tail, cur); | 1316 | GNUNET_CONTAINER_DLL_insert (s->pc_head, s->pc_tail, c_cur); |
1267 | } | 1317 | } |
1268 | 1318 | ||
1269 | /* Find entry for peer */ | 1319 | /* Find entry for peer */ |
1270 | for (p = cur->p_head; NULL != p; p = p->next) | 1320 | for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) |
1271 | if (0 == memcmp (&p->id, peer, sizeof (p->id))) | 1321 | if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id))) |
1272 | break; | 1322 | break; |
1273 | 1323 | ||
1274 | /* Not found: create new peer entry */ | 1324 | /* Not found: create new peer entry */ |
1275 | if (NULL == p) | 1325 | if (NULL == p_cur) |
1276 | { | 1326 | { |
1277 | p = GNUNET_malloc (sizeof (struct PreferencePeer)); | 1327 | p_cur = GNUNET_malloc (sizeof (struct PreferencePeer)); |
1278 | p->id = (*peer); | 1328 | p_cur->s = s; |
1329 | p_cur->client = c_cur; | ||
1330 | p_cur->id = (*peer); | ||
1279 | for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) | 1331 | for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) |
1280 | { | 1332 | { |
1281 | /* Default value per peer absolut preference for a quality: | 1333 | /* Default value per peer absolut preference for a quality: |
1282 | * No value set, so absolute preference 0 */ | 1334 | * No value set, so absolute preference 0 */ |
1283 | p->f[i] = 0.0; | 1335 | p_cur->f[i] = 0.0; |
1284 | /* Default value per peer relative preference for a quality: 1.0 */ | 1336 | /* Default value per peer relative preference for a quality: 1.0 */ |
1285 | p->f_rel[i] = DEFAULT_PREFERENCE; | 1337 | p_cur->f_rel[i] = DEFAULT_PREFERENCE; |
1286 | } | 1338 | } |
1287 | p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p); | 1339 | p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p_cur); |
1288 | GNUNET_CONTAINER_DLL_insert (cur->p_head, cur->p_tail, p); | 1340 | GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur); |
1289 | } | 1341 | } |
1290 | 1342 | ||
1291 | update_preference (s, cur, p, kind, score_f); | 1343 | update_preference (p_cur, kind, score_f); |
1292 | 1344 | ||
1293 | /* FIXME: We should update quotas if UPDATE_INTERVAL is reached */ | 1345 | /* FIXME: We should update quotas if UPDATE_INTERVAL is reached */ |
1294 | if (GNUNET_TIME_absolute_get().abs_value > next_update.abs_value) | 1346 | if (GNUNET_TIME_absolute_get().abs_value > next_update.abs_value) |