aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2008-09-04 01:30:19 -0400
committerGerrit Renker <gerrit@erg.abdn.ac.uk>2008-09-04 01:45:42 -0400
commit22338f09bd60434a3f1d6608f0fa55972067985f (patch)
treec7ec32e782d5c96a060e56cf4b34ddf78c60aadf /net
parent49ffc29a0223adbe0ea7005eea3ab2a03abbeb06 (diff)
dccp tfrc: Increase number of RTT samples
This improves the receiver RTT sampling algorithm so that it tries harder to get as many RTT samples as possible. The algorithm is based the concepts presented in RFC 4340, 8.1, using timestamps and the CCVal window counter. There exist 4 cases for the CCVal difference: * == 0: less than RTT/4 passed since last packet -- unusable; * > 4: (much) more than 1 RTT has passed since last packet -- also unusable; * == 4: perfect sample (exactly one RTT has passed since last packet); * 1..3: sub-optimal sample (between RTT/4 and 3*RTT/4 has passed). In the last case the algorithm tried to optimise by storing away the candidate and then re-trying next time. The problem is that * a large number of samples is needed to smooth out the inaccuracies of the algorithm; * the sender may not be sending enough packets to warrant a "next time"; * hence it is better to use suboptimal samples whenever possible. The algorithm now stores away the current sample only if the difference is 0. Applicability and background ---------------------------- A realistic example is MP3 streaming where packets are sent at a rate of less than one packet per RTT, which means that suitable samples are absent for a very long time. The effectiveness of using suboptimal samples (with a delta between 1 and 4) was confirmed by instrumenting the algorithm with counters. The results of two 20 second test runs were: * With the old algorithm and a total of 38442 function calls, only 394 of these calls resulted in usable RTT samples (about 1%), and 378 out of these were "perfect" samples and 28013 (unused) samples had a delta of 1..3. * With the new algorithm and a total of 37057 function calls, 1702 usable RTT samples were retrieved (about 4.6%), 5 out of these were "perfect" samples. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ccids/lib/packet_history.c83
1 files changed, 24 insertions, 59 deletions
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index e2e250aa5c89..5c4ded1cf422 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -428,31 +428,16 @@ int tfrc_rx_hist_init(struct tfrc_rx_hist *h, struct sock *sk)
428EXPORT_SYMBOL_GPL(tfrc_rx_hist_init); 428EXPORT_SYMBOL_GPL(tfrc_rx_hist_init);
429 429
430/** 430/**
431 * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against
432 */
433static inline struct tfrc_rx_hist_entry *
434 tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist *h)
435{
436 return h->ring[0];
437}
438
439/**
440 * tfrc_rx_hist_rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry
441 */
442static inline struct tfrc_rx_hist_entry *
443 tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist *h)
444{
445 return h->ring[h->rtt_sample_prev];
446}
447
448/**
449 * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal 431 * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal
450 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able 432 * Based on ideas presented in RFC 4342, 8.1. This function expects that no loss
451 * to compute a sample with given data - calling function should check this. 433 * is pending and uses the following history entries (via rtt_sample_prev):
434 * - h->ring[0] contains the most recent history entry prior to @skb;
435 * - h->ring[1] is an unused `dummy' entry when the current difference is 0;
452 */ 436 */
453void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) 437void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb)
454{ 438{
455 u32 sample = 0, delta_v; 439 struct tfrc_rx_hist_entry *last = h->ring[0];
440 u32 sample, delta_v;
456 441
457 /* 442 /*
458 * When not to sample: 443 * When not to sample:
@@ -466,47 +451,27 @@ void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb)
466 tfrc_rx_hist_loss_pending(h)) 451 tfrc_rx_hist_loss_pending(h))
467 return; 452 return;
468 453
469 delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, 454 h->rtt_sample_prev = 0; /* reset previous candidate */
470 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
471
472 if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */
473 if (h->rtt_sample_prev == 2) { /* previous candidate stored */
474 sample = SUB16(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval,
475 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
476 if (sample)
477 sample = 4 / sample *
478 ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_tstamp,
479 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp);
480 else /*
481 * FIXME: This condition is in principle not
482 * possible but occurs when CCID is used for
483 * two-way data traffic. I have tried to trace
484 * it, but the cause does not seem to be here.
485 */
486 DCCP_BUG("please report to dccp@vger.kernel.org"
487 " => prev = %u, last = %u",
488 tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval,
489 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
490 } else if (delta_v < 1) {
491 h->rtt_sample_prev = 1;
492 goto keep_ref_for_next_time;
493 }
494
495 } else if (delta_v == 4) /* optimal match */
496 sample = ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp));
497 else { /* suboptimal match */
498 h->rtt_sample_prev = 2;
499 goto keep_ref_for_next_time;
500 }
501 455
502 if (unlikely(sample > DCCP_SANE_RTT_MAX)) { 456 delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, last->tfrchrx_ccval);
503 DCCP_WARN("RTT sample %u too large, using max\n", sample); 457 if (delta_v == 0) { /* less than RTT/4 difference */
504 sample = DCCP_SANE_RTT_MAX; 458 h->rtt_sample_prev = 1;
459 return;
505 } 460 }
461 sample = dccp_sane_rtt(ktime_to_us(net_timedelta(last->tfrchrx_tstamp)));
506 462
507 h->rtt_sample_prev = 0; /* use current entry as next reference */ 463 if (delta_v <= 4) /* between RTT/4 and RTT */
508keep_ref_for_next_time: 464 sample *= 4 / delta_v;
465 else if (!(sample < h->rtt_estimate && sample > h->rtt_estimate/2))
466 /*
467 * Optimisation: CCVal difference is greater than 1 RTT, yet the
468 * sample is less than the local RTT estimate; which means that
469 * the RTT estimate is too high.
470 * To avoid noise, it is not done if the sample is below RTT/2.
471 */
472 return;
509 473
510 h->rtt_estimate = tfrc_ewma(h->rtt_estimate, sample, 9); 474 /* Use a lower weight than usual to increase responsiveness */
475 h->rtt_estimate = tfrc_ewma(h->rtt_estimate, sample, 5);
511} 476}
512EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); 477EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt);