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:41 -0400
commit2b81143aa3505e2460b24b357996c2f21840ea58 (patch)
tree37f752fb85c563f965655cec834bb289fd831137 /net
parent2f3e3bbad917c426d3aba03a535809e5699de156 (diff)
dccp ccid-3: Always perform receiver RTT sampling
This updates the CCID-3 receiver in part with regard to errata 610 and 611 (http://www.rfc-editor.org/errata_list.php), which change RFC 4342 to use the Receive Rate as specified in rfc3448bis, requiring to constantly sample the RTT (or use a sender RTT). Doing this requires reusing the RX history structure after dealing with a loss. The patch does not resolve how to compute X_recv if the interval is less than 1 RTT. A FIXME has been added (and is resolved in subsequent patch). Furthermore, since this is all TFRC-based functionality, the RTT estimation is now also performed by the dccp_tfrc_lib module. This further simplifies the CCID-3 code. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ccids/ccid3.c43
-rw-r--r--net/dccp/ccids/ccid3.h2
-rw-r--r--net/dccp/ccids/lib/packet_history.c60
-rw-r--r--net/dccp/ccids/lib/packet_history.h17
4 files changed, 73 insertions, 49 deletions
diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c
index 04b183548aa8..8e64d9665a21 100644
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -556,8 +556,8 @@ static void ccid3_hc_rx_send_feedback(struct sock *sk,
556 * would bring X down to s/t_mbi. That is why we return 556 * would bring X down to s/t_mbi. That is why we return
557 * X_recv according to rfc3448bis-06 for the moment. 557 * X_recv according to rfc3448bis-06 for the moment.
558 */ 558 */
559 u32 rtt = hcrx->rtt ? : DCCP_FALLBACK_RTT, 559 u32 s = tfrc_rx_hist_packet_size(&hcrx->hist),
560 s = tfrc_rx_hist_packet_size(&hcrx->hist); 560 rtt = tfrc_rx_hist_rtt(&hcrx->hist);
561 561
562 hcrx->x_recv = scaled_div32(s, 2 * rtt); 562 hcrx->x_recv = scaled_div32(s, 2 * rtt);
563 break; 563 break;
@@ -576,6 +576,11 @@ static void ccid3_hc_rx_send_feedback(struct sock *sk,
576 break; 576 break;
577 /* fall through */ 577 /* fall through */
578 case CCID3_FBACK_PERIODIC: 578 case CCID3_FBACK_PERIODIC:
579 /*
580 * FIXME: check if delta is less than or equal to 1 RTT using
581 * the receiver RTT sample. This is described in Errata 610/611
582 * of RFC 4342 which reference section 6.2 of RFC 3448.
583 */
579 delta = ktime_us_delta(now, hcrx->tstamp_last_feedback); 584 delta = ktime_us_delta(now, hcrx->tstamp_last_feedback);
580 if (delta <= 0) 585 if (delta <= 0)
581 DCCP_BUG("delta (%ld) <= 0", (long)delta); 586 DCCP_BUG("delta (%ld) <= 0", (long)delta);
@@ -633,8 +638,8 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
633static u32 ccid3_first_li(struct sock *sk) 638static u32 ccid3_first_li(struct sock *sk)
634{ 639{
635 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); 640 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
636 u32 x_recv, p, delta, 641 u32 s = tfrc_rx_hist_packet_size(&hcrx->hist),
637 s = tfrc_rx_hist_packet_size(&hcrx->hist); 642 rtt = tfrc_rx_hist_rtt(&hcrx->hist), x_recv, p, delta;
638 u64 fval; 643 u64 fval;
639 644
640 /* 645 /*
@@ -645,11 +650,6 @@ static u32 ccid3_first_li(struct sock *sk)
645 if (unlikely(hcrx->feedback == CCID3_FBACK_NONE)) 650 if (unlikely(hcrx->feedback == CCID3_FBACK_NONE))
646 return 5; 651 return 5;
647 652
648 if (hcrx->rtt == 0) {
649 DCCP_WARN("No RTT estimate available, using fallback RTT\n");
650 hcrx->rtt = DCCP_FALLBACK_RTT;
651 }
652
653 delta = ktime_to_us(net_timedelta(hcrx->tstamp_last_feedback)); 653 delta = ktime_to_us(net_timedelta(hcrx->tstamp_last_feedback));
654 x_recv = scaled_div32(hcrx->hist.bytes_recvd, delta); 654 x_recv = scaled_div32(hcrx->hist.bytes_recvd, delta);
655 if (x_recv == 0) { /* would also trigger divide-by-zero */ 655 if (x_recv == 0) { /* would also trigger divide-by-zero */
@@ -661,7 +661,7 @@ static u32 ccid3_first_li(struct sock *sk)
661 x_recv = hcrx->x_recv; 661 x_recv = hcrx->x_recv;
662 } 662 }
663 663
664 fval = scaled_div32(scaled_div(s, hcrx->rtt), x_recv); 664 fval = scaled_div32(scaled_div(s, rtt), x_recv);
665 p = tfrc_calc_x_reverse_lookup(fval); 665 p = tfrc_calc_x_reverse_lookup(fval);
666 666
667 ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied " 667 ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
@@ -696,25 +696,10 @@ static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
696 return; /* done receiving */ 696 return; /* done receiving */
697 697
698 /* 698 /*
699 * Handle data packets: RTT sampling and monitoring p
700 */
701 if (unlikely(!is_data_packet))
702 goto update_records;
703
704 if (!tfrc_lh_is_initialised(&hcrx->li_hist)) {
705 const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->hist, skb);
706 /*
707 * Empty loss history: no loss so far, hence p stays 0.
708 * Sample RTT values, since an RTT estimate is required for the
709 * computation of p when the first loss occurs; RFC 3448, 6.3.1.
710 */
711 if (sample != 0)
712 hcrx->rtt = tfrc_ewma(hcrx->rtt, sample, 9);
713 }
714 /*
715 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3 699 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3
716 */ 700 */
717 if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->last_counter) > 3) 701 if (is_data_packet &&
702 SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->last_counter) > 3)
718 do_feedback = CCID3_FBACK_PERIODIC; 703 do_feedback = CCID3_FBACK_PERIODIC;
719 704
720update_records: 705update_records:
@@ -744,7 +729,7 @@ static void ccid3_hc_rx_exit(struct sock *sk)
744static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info) 729static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
745{ 730{
746 info->tcpi_options |= TCPI_OPT_TIMESTAMPS; 731 info->tcpi_options |= TCPI_OPT_TIMESTAMPS;
747 info->tcpi_rcv_rtt = ccid3_hc_rx_sk(sk)->rtt; 732 info->tcpi_rcv_rtt = tfrc_rx_hist_rtt(&ccid3_hc_rx_sk(sk)->hist);
748} 733}
749 734
750static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len, 735static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len,
@@ -759,7 +744,7 @@ static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len,
759 if (len < sizeof(rx_info)) 744 if (len < sizeof(rx_info))
760 return -EINVAL; 745 return -EINVAL;
761 rx_info.tfrcrx_x_recv = hcrx->x_recv; 746 rx_info.tfrcrx_x_recv = hcrx->x_recv;
762 rx_info.tfrcrx_rtt = hcrx->rtt; 747 rx_info.tfrcrx_rtt = tfrc_rx_hist_rtt(&hcrx->hist);
763 rx_info.tfrcrx_p = tfrc_invert_loss_event_rate(hcrx->p_inverse); 748 rx_info.tfrcrx_p = tfrc_invert_loss_event_rate(hcrx->p_inverse);
764 len = sizeof(rx_info); 749 len = sizeof(rx_info);
765 val = &rx_info; 750 val = &rx_info;
diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h
index 72e110a1100f..342235c57bf3 100644
--- a/net/dccp/ccids/ccid3.h
+++ b/net/dccp/ccids/ccid3.h
@@ -127,7 +127,6 @@ enum ccid3_fback_type {
127 * @last_counter - Tracks window counter (RFC 4342, 8.1) 127 * @last_counter - Tracks window counter (RFC 4342, 8.1)
128 * @feedback - The type of the feedback last sent 128 * @feedback - The type of the feedback last sent
129 * @x_recv - Receiver estimate of send rate (RFC 3448, sec. 4.3) 129 * @x_recv - Receiver estimate of send rate (RFC 3448, sec. 4.3)
130 * @rtt - Receiver estimate of RTT
131 * @tstamp_last_feedback - Time at which last feedback was sent 130 * @tstamp_last_feedback - Time at which last feedback was sent
132 * @hist - Packet history (loss detection + RTT sampling) 131 * @hist - Packet history (loss detection + RTT sampling)
133 * @li_hist - Loss Interval database 132 * @li_hist - Loss Interval database
@@ -137,7 +136,6 @@ struct ccid3_hc_rx_sock {
137 u8 last_counter:4; 136 u8 last_counter:4;
138 enum ccid3_fback_type feedback:4; 137 enum ccid3_fback_type feedback:4;
139 u32 x_recv; 138 u32 x_recv;
140 u32 rtt;
141 ktime_t tstamp_last_feedback; 139 ktime_t tstamp_last_feedback;
142 struct tfrc_rx_hist hist; 140 struct tfrc_rx_hist hist;
143 struct tfrc_loss_hist li_hist; 141 struct tfrc_loss_hist li_hist;
diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c
index ee34b4564242..e2e250aa5c89 100644
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -151,14 +151,31 @@ int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
151} 151}
152EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate); 152EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate);
153 153
154
155static void __tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b)
156{
157 struct tfrc_rx_hist_entry *tmp = h->ring[a];
158
159 h->ring[a] = h->ring[b];
160 h->ring[b] = tmp;
161}
162
154static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) 163static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b)
155{ 164{
156 const u8 idx_a = tfrc_rx_hist_index(h, a), 165 __tfrc_rx_hist_swap(h, tfrc_rx_hist_index(h, a),
157 idx_b = tfrc_rx_hist_index(h, b); 166 tfrc_rx_hist_index(h, b));
158 struct tfrc_rx_hist_entry *tmp = h->ring[idx_a]; 167}
159 168
160 h->ring[idx_a] = h->ring[idx_b]; 169/**
161 h->ring[idx_b] = tmp; 170 * tfrc_rx_hist_resume_rtt_sampling - Prepare RX history for RTT sampling
171 * This is called after loss detection has finished, when the history entry
172 * with the index of `loss_count' holds the highest-received sequence number.
173 * RTT sampling requires this information at ring[0] (tfrc_rx_hist_sample_rtt).
174 */
175static inline void tfrc_rx_hist_resume_rtt_sampling(struct tfrc_rx_hist *h)
176{
177 __tfrc_rx_hist_swap(h, 0, tfrc_rx_hist_index(h, h->loss_count));
178 h->loss_count = h->loss_start = 0;
162} 179}
163 180
164/* 181/*
@@ -200,8 +217,7 @@ static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2
200 217
201 if (dccp_loss_free(s2, s1, n1)) { 218 if (dccp_loss_free(s2, s1, n1)) {
202 /* hole is filled: S0, S2, and S1 are consecutive */ 219 /* hole is filled: S0, S2, and S1 are consecutive */
203 h->loss_count = 0; 220 tfrc_rx_hist_resume_rtt_sampling(h);
204 h->loss_start = tfrc_rx_hist_index(h, 1);
205 } else 221 } else
206 /* gap between S2 and S1: just update loss_prev */ 222 /* gap between S2 and S1: just update loss_prev */
207 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2); 223 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2);
@@ -254,8 +270,7 @@ static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3)
254 270
255 if (dccp_loss_free(s1, s2, n2)) { 271 if (dccp_loss_free(s1, s2, n2)) {
256 /* entire hole filled by S0, S3, S1, S2 */ 272 /* entire hole filled by S0, S3, S1, S2 */
257 h->loss_start = tfrc_rx_hist_index(h, 2); 273 tfrc_rx_hist_resume_rtt_sampling(h);
258 h->loss_count = 0;
259 } else { 274 } else {
260 /* gap remains between S1 and S2 */ 275 /* gap remains between S1 and S2 */
261 h->loss_start = tfrc_rx_hist_index(h, 1); 276 h->loss_start = tfrc_rx_hist_index(h, 1);
@@ -299,8 +314,7 @@ static void __three_after_loss(struct tfrc_rx_hist *h)
299 314
300 if (dccp_loss_free(s2, s3, n3)) { 315 if (dccp_loss_free(s2, s3, n3)) {
301 /* no gap between S2 and S3: entire hole is filled */ 316 /* no gap between S2 and S3: entire hole is filled */
302 h->loss_start = tfrc_rx_hist_index(h, 3); 317 tfrc_rx_hist_resume_rtt_sampling(h);
303 h->loss_count = 0;
304 } else { 318 } else {
305 /* gap between S2 and S3 */ 319 /* gap between S2 and S3 */
306 h->loss_start = tfrc_rx_hist_index(h, 2); 320 h->loss_start = tfrc_rx_hist_index(h, 2);
@@ -340,6 +354,7 @@ int tfrc_rx_handle_loss(struct tfrc_rx_hist *h,
340 354
341 if (h->loss_count == 0) { 355 if (h->loss_count == 0) {
342 __do_track_loss(h, skb, ndp); 356 __do_track_loss(h, skb, ndp);
357 tfrc_rx_hist_sample_rtt(h, skb);
343 } else if (h->loss_count == 1) { 358 } else if (h->loss_count == 1) {
344 __one_after_loss(h, skb, ndp); 359 __one_after_loss(h, skb, ndp);
345 } else if (h->loss_count != 2) { 360 } else if (h->loss_count != 2) {
@@ -435,11 +450,24 @@ static inline struct tfrc_rx_hist_entry *
435 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able 450 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able
436 * to compute a sample with given data - calling function should check this. 451 * to compute a sample with given data - calling function should check this.
437 */ 452 */
438u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) 453void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb)
439{ 454{
440 u32 sample = 0, 455 u32 sample = 0, delta_v;
441 delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, 456
442 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); 457 /*
458 * When not to sample:
459 * - on non-data packets
460 * (RFC 4342, 8.1: CCVal only fully defined for data packets);
461 * - when no data packets have been received yet
462 * (FIXME: using sampled packet size as indicator here);
463 * - as long as there are gaps in the sequence space (pending loss).
464 */
465 if (!dccp_data_packet(skb) || h->packet_size == 0 ||
466 tfrc_rx_hist_loss_pending(h))
467 return;
468
469 delta_v = SUB16(dccp_hdr(skb)->dccph_ccval,
470 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);
443 471
444 if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */ 472 if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */
445 if (h->rtt_sample_prev == 2) { /* previous candidate stored */ 473 if (h->rtt_sample_prev == 2) { /* previous candidate stored */
@@ -479,6 +507,6 @@ u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb)
479 h->rtt_sample_prev = 0; /* use current entry as next reference */ 507 h->rtt_sample_prev = 0; /* use current entry as next reference */
480keep_ref_for_next_time: 508keep_ref_for_next_time:
481 509
482 return sample; 510 h->rtt_estimate = tfrc_ewma(h->rtt_estimate, sample, 9);
483} 511}
484EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); 512EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt);
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index b7c87a1a2720..ba5832bbc348 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -91,6 +91,7 @@ struct tfrc_rx_hist_entry {
91 * @loss_count: Number of entries in circular history 91 * @loss_count: Number of entries in circular history
92 * @loss_start: Movable index (for loss detection) 92 * @loss_start: Movable index (for loss detection)
93 * @rtt_sample_prev: Used during RTT sampling, points to candidate entry 93 * @rtt_sample_prev: Used during RTT sampling, points to candidate entry
94 * @rtt_estimate: Receiver RTT estimate
94 * @packet_size: Packet size in bytes (as per RFC 3448, 3.1) 95 * @packet_size: Packet size in bytes (as per RFC 3448, 3.1)
95 * @bytes_recvd: Number of bytes received since last sending feedback 96 * @bytes_recvd: Number of bytes received since last sending feedback
96 */ 97 */
@@ -98,7 +99,10 @@ struct tfrc_rx_hist {
98 struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1]; 99 struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1];
99 u8 loss_count:2, 100 u8 loss_count:2,
100 loss_start:2; 101 loss_start:2;
102 /* Receiver RTT sampling */
101#define rtt_sample_prev loss_start 103#define rtt_sample_prev loss_start
104 u32 rtt_estimate;
105 /* Receiver sampling of application payload lengths */
102 u32 packet_size, 106 u32 packet_size,
103 bytes_recvd; 107 bytes_recvd;
104}; 108};
@@ -154,6 +158,15 @@ static inline u32 tfrc_rx_hist_packet_size(const struct tfrc_rx_hist *h)
154 return TCP_MIN_RCVMSS; 158 return TCP_MIN_RCVMSS;
155 } 159 }
156 return h->packet_size; 160 return h->packet_size;
161
162}
163static inline u32 tfrc_rx_hist_rtt(const struct tfrc_rx_hist *h)
164{
165 if (h->rtt_estimate == 0) {
166 DCCP_WARN("No RTT estimate available, using fallback RTT\n");
167 return DCCP_FALLBACK_RTT;
168 }
169 return h->rtt_estimate;
157} 170}
158 171
159extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, 172extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h,
@@ -167,8 +180,8 @@ extern int tfrc_rx_handle_loss(struct tfrc_rx_hist *h,
167 struct sk_buff *skb, const u64 ndp, 180 struct sk_buff *skb, const u64 ndp,
168 u32 (*first_li)(struct sock *sk), 181 u32 (*first_li)(struct sock *sk),
169 struct sock *sk); 182 struct sock *sk);
170extern u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, 183extern void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h,
171 const struct sk_buff *skb); 184 const struct sk_buff *skb);
172extern int tfrc_rx_hist_init(struct tfrc_rx_hist *h, struct sock *sk); 185extern int tfrc_rx_hist_init(struct tfrc_rx_hist *h, struct sock *sk);
173extern void tfrc_rx_hist_purge(struct tfrc_rx_hist *h); 186extern void tfrc_rx_hist_purge(struct tfrc_rx_hist *h);
174 187