[PATCH 28/43]: Make computation of X_recv conform to TFRC

[PATCH 28/43]: Make computation of X_recv conform to TFRC

[Gerrit Renker]

[CCID3]: Make computation of X_recv conform to TFRC

The computation of X_recv does currently not conform to TFRC/RFC 3448,
since this specification requires that X_recv be computed over the last
R_m seconds (sec. 6.2).  
The code, in contrast, computes X_recv over the time the last feedback was 
sent. This results in sending wrong estimates of X_recv, making it impossible
for the sender to find its allowed sending rate.

The patch
 * explicitly distinguishes the types of feedback (using an enum);
 * uses previous value of X_recv when sending feedback due to a parameter change;
 * makes all state changes local to ccid3_hc_tx_packet_recv;
 * assigns feedback type according to incident (previously only used flag `do_feedback').

Detailed justifications and explanations are provided online at
http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/#8._Computing_X_recv_ 

As a result, not only is the computation of X_recv more accurate, but also the
feedback handling is much less clumsy as before: states are clearly separated.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/ccid3.c |   45 +++++++++++++++++++++++++++++++--------------
 net/dccp/ccids/ccid3.h |   10 +++++++++-
 2 files changed, 40 insertions(+), 15 deletions(-)

--- a/net/dccp/ccids/ccid3.h
+++ b/net/dccp/ccids/ccid3.h
@@ -125,13 +125,21 @@ static inline struct ccid3_hc_tx_sock *c
 	return ccid3_tx_priv;
 }
 
-/* TFRC receiver states */
+/* CCID3 receiver states */
 enum ccid3_hc_rx_states {
 	TFRC_RSTATE_NO_DATA = 1,
 	TFRC_RSTATE_DATA,
 	TFRC_RSTATE_TERM    = 127,
 };
 
+/* CCID3 feedback types */
+enum ccid3_fback_type {
+	FBACK_NONE = 0,
+	FBACK_INITIAL,
+	FBACK_PERIODIC,
+	FBACK_PARAM_CHANGE
+};
+
 /** struct ccid3_hc_rx_sock - CCID3 receiver half-connection socket
  *
  *  @ccid3hcrx_last_counter  -  Tracks window counter (RFC 4342, 8.1)
--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -720,30 +720,46 @@ static inline void ccid3_hc_rx_update_s(
 		TFRC_EWMA(hcrx->ccid3hcrx_s, len, 9);
 }
 
-static void ccid3_hc_rx_send_feedback(struct sock *sk, struct sk_buff *skb)
+static void ccid3_hc_rx_send_feedback(struct sock *sk, struct sk_buff *skb,
+				      enum ccid3_fback_type fbtype)
 {
 	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
 	struct dccp_sock *dp = dccp_sk(sk);
 	struct timeval now, t_recv;
 	suseconds_t delta = 0;
 
+	if (unlikely(hcrx->ccid3hcrx_state = TFRC_RSTATE_TERM))
+		return;
+
 	do_gettimeofday(&now);
 
-	switch (hcrx->ccid3hcrx_state) {
-	case TFRC_RSTATE_NO_DATA:
+	switch (fbtype) {
+	case FBACK_INITIAL:
 		hcrx->ccid3hcrx_x_recv = 0;
 		hcrx->ccid3hcrx_pinv   = ~0U;	/* see RFC 4342, 8.5 */
-		ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
 		break;
-	case TFRC_RSTATE_DATA:
+	case FBACK_PARAM_CHANGE:
+		/*
+		 * When parameters change (new loss or p > p_prev), we do not
+		 * have a reliable estimate for R_m of [RFC 3448, 6.2] and so
+		 * need to  reuse the previous value of X_recv. However, when
+		 * X_recv was 0 (due to early loss), this would kill X down to
+		 * s/t_mbi (i.e. one packet in 64 seconds).
+		 * To avoid such drastic reduction, we approximate X_recv as
+		 * the number of bytes since last feedback.
+		 * This is a safe fallback, since X is bounded above by X_calc.
+		 */
+		if (hcrx->ccid3hcrx_x_recv > 0)
+			break;
+		/* fall through */
+	case FBACK_PERIODIC:
 		delta = timeval_delta(&now,
 				      &hcrx->ccid3hcrx_tstamp_last_feedback);
 		DCCP_BUG_ON(delta < 0);
 		hcrx->ccid3hcrx_x_recv  			scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta);
 		break;
-	case TFRC_RSTATE_TERM:
-		DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk);
+	default:
 		return;
 	}
 	ccid3_pr_debug("Interval %ldusec, X_recv=%u, 1/p=%u\n", (long)delta,
@@ -838,16 +854,17 @@ static u32 ccid3_first_li(struct sock *s
 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
 {
 	struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
+	enum   ccid3_fback_type  do_feedback = FBACK_NONE;
 	u32 sample, ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp,
 	    payload_size = skb->len - dccp_hdr(skb)->dccph_doff * 4;
-	u8  is_data_packet = dccp_data_packet(skb), do_feedback = 0;
+	u8  is_data_packet = dccp_data_packet(skb);
 
 	spin_lock(&hcrx->ccid3hcrx_hist.lock);
 
 	if (unlikely(hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA)) {
-		/* Handle initial feedback */
 		if (is_data_packet) {
-			do_feedback = 1;
+			do_feedback = FBACK_INITIAL;
+			ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
 			ccid3_hc_rx_update_s(hcrx, payload_size);
 		}
 		goto update_records;
@@ -868,7 +885,7 @@ static void ccid3_hc_rx_packet_recv(stru
 	    tfrc_rx_handle_loss(&hcrx->ccid3hcrx_hist,
 				&hcrx->ccid3hcrx_li_hist,
 				skb, ndp, ccid3_first_li, sk) ) {
-		do_feedback = 1;
+		do_feedback = FBACK_PARAM_CHANGE;
 		goto sending_feedback;
 	}
 
@@ -896,12 +913,12 @@ static void ccid3_hc_rx_packet_recv(stru
 		 * Step (3) of [RFC 3448, 6.1]: Recompute I_mean and, if I_mean
 		 * has decreased (resp. p has increased), send feedback now.
 		 */
-		do_feedback = 1;
+		do_feedback = FBACK_PARAM_CHANGE;
 
 
 	/* check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3 */
 	if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
-		do_feedback = 1;
+		do_feedback = FBACK_PERIODIC;
 
 update_records:
 	tfrc_rx_hist_update(&hcrx->ccid3hcrx_hist, skb, ndp);
@@ -910,7 +927,7 @@ sending_feedback:
 	spin_unlock(&hcrx->ccid3hcrx_hist.lock);
 
 	if (do_feedback)
-		ccid3_hc_rx_send_feedback(sk, skb);
+		ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
 }
 
 static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk)

Re: [PATCH 28/43]: Make computation of X_recv conform to TFRC

[Ian McDonald]

On 4/6/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [CCID3]: Make computation of X_recv conform to TFRC
>
> The computation of X_recv does currently not conform to TFRC/RFC 3448,
> since this specification requires that X_recv be computed over the last
> R_m seconds (sec. 6.2).
> The code, in contrast, computes X_recv over the time the last feedback was
> sent. This results in sending wrong estimates of X_recv, making it impossible
> for the sender to find its allowed sending rate.
>

I think this is one of those (rare) instances where RFC4342 overrides
RFC3448. Have a look in particular at section 10.3 of 4342 and 8.1/8.3

As such this patch is not correct I think.

Thoughts?

Ian
-- 
Web: http://wand.net.nz/~iam4/
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

Re: [PATCH 28/43]: Make computation of X_recv conform to TFRC

[Gerrit Renker]

|  I think this is one of those (rare) instances where RFC4342 overrides
|  RFC3448. Have a look in particular at section 10.3 of 4342 and 8.1/8.3
|  
|  As such this patch is not correct I think.
|  
|  Thoughts?
There are two points here: 

(1) The title is a bit unfortunate, as 90% of the patch are concerned with
    improving the interface from rx_packet_recv() to send_feedback().

(2) With regards to the 3448/4342 relationship, you are correct. 
    I had overlooked the following passage in section 8.3 of RFC 4342:

     "To calculate this receive rate, the receiver sets t to the larger of 
      the estimated round-trip time and the time since the last Receive Rate
      option was sent."

    However, though I wish I had read that earlier, this additional rule causes
    no contradiction - in fact, it simplifies the issue.


What follows shows that the patch conforms to above rule from [RFC 4342, 8.3]. The 
documentation of how the patch works is on 
  http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/#8._Computing_X_recv_
The time `t' here corresponds to delta = t_now - ccid3hcrx_last_feedback


 1. Periodic feedback (FBACK_PERIODIC) triggered by the window counter.

    This is using the rule specified by [RFC 4340,  10.3]. 

      (a) Time between window counter changes larger than or equal to RTT
          This corresponds to a window counter difference of 4 or larger 
          and is in agreement with above rule from 8.3 with regard to "the
          larger of the estimated round-trip time".

      (b) Time between window counter changes less than RTT.
          No periodic feedback  is sent due to 10.3.


 2. Feedback due to parameter change (FBACK_PARAM_CHANGE).

    There are thw possible cases, both need to be handled correctly.

      (i) Parameter change directly after sending periodic feedback.
          In this case few (worst case: none) packets have been received since the last
          feedback was sent. The code does not (as was done previously) use the number
          of bytes received since the last feedback was received: the time interval 
          since sending the last feedback is less than the estimated RTT used in sending
          periodic feedback. 
          RFC 4342, 8.3 requires to compute X_recv over an interval larger than the 
          estimated RTT and this time interval. The code therefore uses the longer interval 
          of the RTT estimate, by reusing X_recv computed previously. Note that both feedback
          packets are sent within the same RTT. In addition, last_counter is reset to correctly
          trigger the next periodic feedback.

     (ii) Parameter change when no periodic feedback has been sent yet.
 
          Here X_recv is 0. This case can happen due to early loss. We have no reasonable RTT 
          estimate, the only feedback that has been sent is the initial feedback from [RFC 3448, 6.3].
          Here X_recv is computed over the interval since last_counter was last set (at the same time
          when the initial feedback packet was sent). This again does not contradict the rule from
          RFC 4342, 8.3; rather it is a special case with the premise that there is no reliable RTT
          estimate yet. Furthermore, this case is an exception - it occurs only when there is loss
          immediately after the first data packet and before the first periodic feedback is due. 

Re: [PATCH 28/43]: Make computation of X_recv conform to TFRC

[Eddie Kohler]

This is a question, not a comment:

Sally and I are actually discussing whether, as a result of the RFC3448bis 
work, we should update RFC4342 so that the Receive Rate option in CCID 3 
*always* reports the receive rate over the last RTT, rather the max of (RTT, 
time since last RR option).

If, as implementors, you have opinions about which definition would be easier, 
we would like to hear them.

Thanks,
Eddie


Gerrit Renker wrote:
> |  I think this is one of those (rare) instances where RFC4342 overrides
> |  RFC3448. Have a look in particular at section 10.3 of 4342 and 8.1/8.3
> |  
> |  As such this patch is not correct I think.
> |  
> |  Thoughts?
> There are two points here: 
> 
> (1) The title is a bit unfortunate, as 90% of the patch are concerned with
>     improving the interface from rx_packet_recv() to send_feedback().
> 
> (2) With regards to the 3448/4342 relationship, you are correct. 
>     I had overlooked the following passage in section 8.3 of RFC 4342:
> 
>      "To calculate this receive rate, the receiver sets t to the larger of 
>       the estimated round-trip time and the time since the last Receive Rate
>       option was sent."
> 
>     However, though I wish I had read that earlier, this additional rule causes
>     no contradiction - in fact, it simplifies the issue.
> 
> 
> What follows shows that the patch conforms to above rule from [RFC 4342, 8.3]. The 
> documentation of how the patch works is on 
>   http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/#8._Computing_X_recv_
> The time `t' here corresponds to delta = t_now - ccid3hcrx_last_feedback
> 
> 
>  1. Periodic feedback (FBACK_PERIODIC) triggered by the window counter.
> 
>     This is using the rule specified by [RFC 4340,  10.3]. 
> 
>       (a) Time between window counter changes larger than or equal to RTT
>           This corresponds to a window counter difference of 4 or larger 
>           and is in agreement with above rule from 8.3 with regard to "the
>           larger of the estimated round-trip time".
> 
>       (b) Time between window counter changes less than RTT.
>           No periodic feedback  is sent due to 10.3.
> 
> 
>  2. Feedback due to parameter change (FBACK_PARAM_CHANGE).
> 
>     There are thw possible cases, both need to be handled correctly.
> 
>       (i) Parameter change directly after sending periodic feedback.
>           In this case few (worst case: none) packets have been received since the last
>           feedback was sent. The code does not (as was done previously) use the number
>           of bytes received since the last feedback was received: the time interval 
>           since sending the last feedback is less than the estimated RTT used in sending
>           periodic feedback. 
>           RFC 4342, 8.3 requires to compute X_recv over an interval larger than the 
>           estimated RTT and this time interval. The code therefore uses the longer interval 
>           of the RTT estimate, by reusing X_recv computed previously. Note that both feedback
>           packets are sent within the same RTT. In addition, last_counter is reset to correctly
>           trigger the next periodic feedback.
> 
>      (ii) Parameter change when no periodic feedback has been sent yet.
>  
>           Here X_recv is 0. This case can happen due to early loss. We have no reasonable RTT 
>           estimate, the only feedback that has been sent is the initial feedback from [RFC 3448, 6.3].
>           Here X_recv is computed over the interval since last_counter was last set (at the same time
>           when the initial feedback packet was sent). This again does not contradict the rule from
>           RFC 4342, 8.3; rather it is a special case with the premise that there is no reliable RTT
>           estimate yet. Furthermore, this case is an exception - it occurs only when there is loss
>           immediately after the first data packet and before the first periodic feedback is due. 
> -
> To unsubscribe from this list: send the line "unsubscribe dccp" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 28/43]: Make computation of X_recv conform to TFRC

[Gerrit Renker]

|  This is a question, not a comment:
|  Sally and I are actually discussing whether, as a result of the RFC3448bis 
|  work, we should update RFC4342 so that the Receive Rate option in CCID 3 
|  *always* reports the receive rate over the last RTT, rather the max of (RTT, 
|  time since last RR option).

I get the impression that this could be resolved with a `should' clause.

The problem is that the receiver may sometimes sample X_recv over more
than a full RTT - e.g. when the window counter CCVal distance from one
data packet to the next one is more than 4, indicating a time difference
of more than 1 RTT.

In such cases, it seems better to allow the receiver to use this value, 
being as close to an RTT sample as one can get.

In other cases, when the receiver is able to choose between sampling over one RTT
and a longer period, it does seem better to use the RTT, since the sending rate
could have changed during the last RTT - which would not show as sharply when
the longer sampling period is preferred.

But, as said, the sender may not always have this choice.

Gerrit


|  If, as implementors, you have opinions about which definition would be easier, 
|  we would like to hear them.
|  
|  Thanks,
|  Eddie
|  
|  
|  Gerrit Renker wrote:
|  > |  I think this is one of those (rare) instances where RFC4342 overrides
|  > |  RFC3448. Have a look in particular at section 10.3 of 4342 and 8.1/8.3
|  > |  
|  > |  As such this patch is not correct I think.
|  > |  
|  > |  Thoughts?
|  > There are two points here: 
|  > 
|  > (1) The title is a bit unfortunate, as 90% of the patch are concerned with
|  >     improving the interface from rx_packet_recv() to send_feedback().
|  > 
|  > (2) With regards to the 3448/4342 relationship, you are correct. 
|  >     I had overlooked the following passage in section 8.3 of RFC 4342:
|  > 
|  >      "To calculate this receive rate, the receiver sets t to the larger of 
|  >       the estimated round-trip time and the time since the last Receive Rate
|  >       option was sent."
|  > 
|  >     However, though I wish I had read that earlier, this additional rule causes
|  >     no contradiction - in fact, it simplifies the issue.
|  > 
|  > 
|  > What follows shows that the patch conforms to above rule from [RFC 4342, 8.3]. The 
|  > documentation of how the patch works is on 
|  >   http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/#8._Computing_X_recv_
|  > The time `t' here corresponds to delta = t_now - ccid3hcrx_last_feedback
|  > 
|  > 
|  >  1. Periodic feedback (FBACK_PERIODIC) triggered by the window counter.
|  > 
|  >     This is using the rule specified by [RFC 4340,  10.3]. 
|  > 
|  >       (a) Time between window counter changes larger than or equal to RTT
|  >           This corresponds to a window counter difference of 4 or larger 
|  >           and is in agreement with above rule from 8.3 with regard to "the
|  >           larger of the estimated round-trip time".
|  > 
|  >       (b) Time between window counter changes less than RTT.
|  >           No periodic feedback  is sent due to 10.3.
|  > 
|  > 
|  >  2. Feedback due to parameter change (FBACK_PARAM_CHANGE).
|  > 
|  >     There are thw possible cases, both need to be handled correctly.
|  > 
|  >       (i) Parameter change directly after sending periodic feedback.
|  >           In this case few (worst case: none) packets have been received since the last
|  >           feedback was sent. The code does not (as was done previously) use the number
|  >           of bytes received since the last feedback was received: the time interval 
|  >           since sending the last feedback is less than the estimated RTT used in sending
|  >           periodic feedback. 
|  >           RFC 4342, 8.3 requires to compute X_recv over an interval larger than the 
|  >           estimated RTT and this time interval. The code therefore uses the longer interval 
|  >           of the RTT estimate, by reusing X_recv computed previously. Note that both feedback
|  >           packets are sent within the same RTT. In addition, last_counter is reset to correctly
|  >           trigger the next periodic feedback.
|  > 
|  >      (ii) Parameter change when no periodic feedback has been sent yet.
|  >  
|  >           Here X_recv is 0. This case can happen due to early loss. We have no reasonable RTT 
|  >           estimate, the only feedback that has been sent is the initial feedback from [RFC 3448, 6.3].
|  >           Here X_recv is computed over the interval since last_counter was last set (at the same time
|  >           when the initial feedback packet was sent). This again does not contradict the rule from
|  >           RFC 4342, 8.3; rather it is a special case with the premise that there is no reliable RTT
|  >           estimate yet. Furthermore, this case is an exception - it occurs only when there is loss
|  >           immediately after the first data packet and before the first periodic feedback is due. 
|  > -
|  > To unsubscribe from this list: send the line "unsubscribe dccp" in
|  > the body of a message to majordomo@vger.kernel.org
|  > More majordomo info at  http://vger.kernel.org/majordomo-info.html
|  -
|  To unsubscribe from this list: send the line "unsubscribe dccp" in
|  the body of a message to majordomo@vger.kernel.org
|  More majordomo info at  http://vger.kernel.org/majordomo-info.html
|  
|