diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-07-11 16:11:42 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-07-11 16:11:42 +0000 |
commit | 9b47032b08f64aec95566e0bbaffd39dc225fc51 (patch) | |
tree | 355d4815b6d9def4c7b6af8174415ac948337830 /src/fragmentation | |
parent | d8e0c3c330552300cacd49e3d48d8fd9ae233480 (diff) | |
download | gnunet-9b47032b08f64aec95566e0bbaffd39dc225fc51.tar.gz gnunet-9b47032b08f64aec95566e0bbaffd39dc225fc51.zip |
frag
Diffstat (limited to 'src/fragmentation')
-rw-r--r-- | src/fragmentation/defragmentation_new.c | 157 |
1 files changed, 140 insertions, 17 deletions
diff --git a/src/fragmentation/defragmentation_new.c b/src/fragmentation/defragmentation_new.c index 775885158..2e1136f9f 100644 --- a/src/fragmentation/defragmentation_new.c +++ b/src/fragmentation/defragmentation_new.c | |||
@@ -26,7 +26,6 @@ | |||
26 | #include "gnunet_fragmentation_lib.h" | 26 | #include "gnunet_fragmentation_lib.h" |
27 | #include "fragmentation.h" | 27 | #include "fragmentation.h" |
28 | 28 | ||
29 | |||
30 | /** | 29 | /** |
31 | * Timestamps for fragments. | 30 | * Timestamps for fragments. |
32 | */ | 31 | */ |
@@ -104,6 +103,11 @@ struct MessageContext | |||
104 | uint32_t fragment_id; | 103 | uint32_t fragment_id; |
105 | 104 | ||
106 | /** | 105 | /** |
106 | * Which 'bit' did the last fragment we received correspond to? | ||
107 | */ | ||
108 | unsigned int last_bit; | ||
109 | |||
110 | /** | ||
107 | * For the current ACK round, which is the first relevant | 111 | * For the current ACK round, which is the first relevant |
108 | * offset in 'frag_times'? | 112 | * offset in 'frag_times'? |
109 | */ | 113 | */ |
@@ -271,6 +275,126 @@ send_ack (void *cls, | |||
271 | 275 | ||
272 | 276 | ||
273 | /** | 277 | /** |
278 | * This function is from the GNU Scientific Library, linear/fit.c, | ||
279 | * (C) 2000 Brian Gough | ||
280 | */ | ||
281 | static void | ||
282 | gsl_fit_mul (const double *x, const size_t xstride, | ||
283 | const double *y, const size_t ystride, | ||
284 | const size_t n, | ||
285 | double *c1, double *cov_11, double *sumsq) | ||
286 | { | ||
287 | double m_x = 0, m_y = 0, m_dx2 = 0, m_dxdy = 0; | ||
288 | |||
289 | size_t i; | ||
290 | |||
291 | for (i = 0; i < n; i++) | ||
292 | { | ||
293 | m_x += (x[i * xstride] - m_x) / (i + 1.0); | ||
294 | m_y += (y[i * ystride] - m_y) / (i + 1.0); | ||
295 | } | ||
296 | |||
297 | for (i = 0; i < n; i++) | ||
298 | { | ||
299 | const double dx = x[i * xstride] - m_x; | ||
300 | const double dy = y[i * ystride] - m_y; | ||
301 | |||
302 | m_dx2 += (dx * dx - m_dx2) / (i + 1.0); | ||
303 | m_dxdy += (dx * dy - m_dxdy) / (i + 1.0); | ||
304 | } | ||
305 | |||
306 | /* In terms of y = b x */ | ||
307 | |||
308 | { | ||
309 | double s2 = 0, d2 = 0; | ||
310 | double b = (m_x * m_y + m_dxdy) / (m_x * m_x + m_dx2); | ||
311 | |||
312 | *c1 = b; | ||
313 | |||
314 | /* Compute chi^2 = \sum (y_i - b * x_i)^2 */ | ||
315 | |||
316 | for (i = 0; i < n; i++) | ||
317 | { | ||
318 | const double dx = x[i * xstride] - m_x; | ||
319 | const double dy = y[i * ystride] - m_y; | ||
320 | const double d = (m_y - b * m_x) + dy - b * dx; | ||
321 | d2 += d * d; | ||
322 | } | ||
323 | |||
324 | s2 = d2 / (n - 1.0); /* chisq per degree of freedom */ | ||
325 | |||
326 | *cov_11 = s2 * 1.0 / (n * (m_x * m_x + m_dx2)); | ||
327 | |||
328 | *sumsq = d2; | ||
329 | } | ||
330 | } | ||
331 | |||
332 | |||
333 | /** | ||
334 | * Estimate the latency between messages based on the most recent | ||
335 | * message time stamps. | ||
336 | * | ||
337 | * @param mc context with time stamps | ||
338 | * @return average delay between time stamps (based on least-squares fit) | ||
339 | */ | ||
340 | static struct GNUNET_TIME_Relative | ||
341 | estimate_latency (struct MessageContext *mc) | ||
342 | { | ||
343 | struct FragTimes *first; | ||
344 | size_t total = mc->frag_times_write_offset - mc->frag_times_start_offset; | ||
345 | double x[total]; | ||
346 | double y[total]; | ||
347 | size_t i; | ||
348 | double c1; | ||
349 | double cov11; | ||
350 | double sumsq; | ||
351 | struct GNUNET_TIME_Relative ret; | ||
352 | |||
353 | first = &mc->frag_times[mc->frag_times_start_offset]; | ||
354 | GNUNET_assert (total > 1); | ||
355 | for (i=0;i<total;i++) | ||
356 | { | ||
357 | x[i] = (double) i; | ||
358 | y[i] = (double) (first[i].time.abs_value - first[0].time.abs_value); | ||
359 | } | ||
360 | gsl_fit_mul (x, 1, y, 1, total, &c1, &cov11, &sumsq); | ||
361 | ret.rel_value = (uint64_t) c1; | ||
362 | return ret; | ||
363 | }; | ||
364 | |||
365 | |||
366 | /** | ||
367 | * Discard the message context that was inactive for the longest time. | ||
368 | * | ||
369 | * @param dc defragmentation context | ||
370 | */ | ||
371 | static void | ||
372 | discard_oldest_mc (struct GNUNET_DEFRAGMENT_Context *dc) | ||
373 | { | ||
374 | struct MessageContext *old; | ||
375 | struct MessageContext *pos; | ||
376 | |||
377 | old = NULL; | ||
378 | pos = dc->head; | ||
379 | while (NULL != pos) | ||
380 | { | ||
381 | if ( (old == NULL) || | ||
382 | (old->last_update.abs_value > pos->last_update.abs_value) ) | ||
383 | old = pos; | ||
384 | pos = pos->next; | ||
385 | } | ||
386 | GNUNET_assert (NULL != old); | ||
387 | GNUNET_CONTAINER_DLL_remove (dc->head, | ||
388 | dc->tail, | ||
389 | old); | ||
390 | dc->list_size--; | ||
391 | if (GNUNET_SCHEDULER_NO_TASK != old->ack_task) | ||
392 | GNUNET_SCHEDULER_cancel (old->ack_task); | ||
393 | GNUNET_free (old); | ||
394 | } | ||
395 | |||
396 | |||
397 | /** | ||
274 | * We have received a fragment. Process it. | 398 | * We have received a fragment. Process it. |
275 | * | 399 | * |
276 | * @param dc the context | 400 | * @param dc the context |
@@ -289,6 +413,8 @@ GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, | |||
289 | unsigned int bit; | 413 | unsigned int bit; |
290 | struct GNUNET_TIME_Absolute now; | 414 | struct GNUNET_TIME_Absolute now; |
291 | struct GNUNET_TIME_Relative delay; | 415 | struct GNUNET_TIME_Relative delay; |
416 | unsigned int bc; | ||
417 | unsigned int b; | ||
292 | 418 | ||
293 | if (ntohs(msg->size) < sizeof (struct FragmentHeader)) | 419 | if (ntohs(msg->size) < sizeof (struct FragmentHeader)) |
294 | { | 420 | { |
@@ -346,9 +472,7 @@ GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, | |||
346 | mc); | 472 | mc); |
347 | dc->list_size++; | 473 | dc->list_size++; |
348 | if (dc->list_size > dc->num_msgs) | 474 | if (dc->list_size > dc->num_msgs) |
349 | { | 475 | discard_oldest_mc (dc); |
350 | /* FIXME: discard oldest entry... */ | ||
351 | } | ||
352 | } | 476 | } |
353 | 477 | ||
354 | /* copy data to 'mc' */ | 478 | /* copy data to 'mc' */ |
@@ -360,6 +484,9 @@ GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, | |||
360 | &fh[1], | 484 | &fh[1], |
361 | ntohs (msg->size) - sizeof (struct FragmentHeader)); | 485 | ntohs (msg->size) - sizeof (struct FragmentHeader)); |
362 | mc->last_update = now; | 486 | mc->last_update = now; |
487 | if (bit < mc->last_bit) | ||
488 | mc->frag_times_start_offset = mc->frag_times_write_offset; | ||
489 | mc->last_bit = bit; | ||
363 | mc->frag_times[mc->frag_times_write_offset].time = now; | 490 | mc->frag_times[mc->frag_times_write_offset].time = now; |
364 | mc->frag_times[mc->frag_times_write_offset].bit = bit; | 491 | mc->frag_times[mc->frag_times_write_offset].bit = bit; |
365 | mc->frag_times_write_offset++; | 492 | mc->frag_times_write_offset++; |
@@ -382,19 +509,15 @@ GNUNET_DEFRAGMENT_process_fragment (struct GNUNET_DEFRAGMENT_Context *dc, | |||
382 | GNUNET_NO); | 509 | GNUNET_NO); |
383 | } | 510 | } |
384 | 511 | ||
385 | /* FIXME: update ACK timer (if 0==mc->bits, always ACK now!) */ | 512 | /* count number of missing fragments */ |
386 | delay = GNUNET_TIME_UNIT_SECONDS; /* FIXME: bad! */ | 513 | bc = 0; |
387 | if (mc->frag_times_write_offset == 1) | 514 | for (b=0;b<64;b++) |
388 | { | 515 | if (0 != (mc->bits & (1 << b))) bc++; |
389 | /* FIXME: use number-of-fragments * dc->delay */ | 516 | if (mc->frag_times_write_offset - mc->frag_times_start_offset > 1) |
390 | } | 517 | dc->latency = estimate_latency (mc); |
391 | else | 518 | delay = GNUNET_TIME_relative_multiply (dc->latency, |
392 | { | 519 | bc + 1); |
393 | /* FIXME: use best-fit regression */ | 520 | if (0 == mc->bits) /* message complete, ACK now! */ |
394 | } | ||
395 | /* FIXME: update dc->latency! */ | ||
396 | |||
397 | if (0 == mc->bits) | ||
398 | delay = GNUNET_TIME_UNIT_ZERO; | 521 | delay = GNUNET_TIME_UNIT_ZERO; |
399 | if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task) | 522 | if (GNUNET_SCHEDULER_NO_TASK != mc->ack_task) |
400 | GNUNET_SCHEDULER_cancel (mc->ack_task); | 523 | GNUNET_SCHEDULER_cancel (mc->ack_task); |