[SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Gerrit Renker]

This summarizes the issues that have been discussed, 
     reviews Ian's patch, and
     tries to identify related problems which impede progress.


1) List of known bugs affecting this problem
======================

The following problems are still unresolved:

BUG#1: No attempt is made to ensure that losses are within the same RTT. This code is 
       missing. Ian has pointed this out already in December and I think he is working
       on it (patch `fix_consecutive_loss.diff'). Now we have another problem:

BUG#2: RTT estimation from CCVal does currently not work. There is code which goes towards
       this, but only for the first loss interval (function ccid3_hc_rx_calc_first_li, lines
       793 ... 835). Currently the code uses timestamps everywhere, hence we are not conforming
       to [RFC 4342, sec. 10.3]. This impedes fixing BUG#1; I have been working on this but not
       completed testing yet.

BUG#3: ccid3_hc_rx_detect_loss does not update hcrx->ccid3hcrx_ccval_nonloss in sync with
       hcrx->ccid3hcrx_seqno_nonloss  => this makes it difficult to fix BUG#1, since as a conseqence
       we now longer know which non-loss CCVal belongs to which non-loss sequence number.

BUG#4: Weights are scaled by 4 but the end result, in dccp_li_hist_calc_i_mean, is not divided by 4.
       This is fixed in Ian's patch, but _not_ in the existing code.

WISH#1: Using an array for the loss history would much simplify the code (as per earlier emails).


2) Issues raised by Eddie
============The following are quotes from earlier emails.

(a) "From Ian's patch, it appears that the OLD code DID NOT include the most 
     recent loss interval (i.e., the incomplete loss interval, the one that has no 
     losses) in its calculation of i_tot1.  Ian has added the following line to do 
     this:

     > +    i_tot1 += non_loss * dccp_li_hist_w[0];

     This is correct.  The RFC requires that one of the i_tots include the 
     incomplete loss interval.  So this part of the patch is required for RFC 
     compliance.

     I am assuming however that the incomplete loss interval is NOT included in the 
     'hcrx->ccid3hcrx_li_hist' list.  If that list DOES include the incomplete loss 
     interval, then the code would need to be different."

   => This is the crucial point: the last loss interval is always added to the list first;
       both before and in Ian's patch. To illustrate, the calling path for this is as follows.

	ccid3_hc_rx_packet_recv():
		loss = ccid3_hc_rx_detect_loss(sk, packet);

        ccid3_hc_rx_detect_loss():
		while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) > TFRC_RECV_NUM_LATE_LOSS) {
			loss = 1;
			ccid3_hc_rx_update_li(sk, hcrx->ccid3hcrx_seqno_nonloss,
		 	       	        	  hcrx->ccid3hcrx_ccval_nonloss);

	ccid3_hc_rx_update_li(): adds interval to hcrx->ccid3hcrx_li_hist

        Back in ccid3_hc_rx_packet_recv(), dccp_li_hist_calc_i_mean() is only executed when loss = 1,
        hence in dccp_li_hist_calc_i_mean() the most recent interval I_0 is always at the top of the list.


(b) "i_tot0 should include non_loss, but in the code i_tot1 does."
    => Please see below.

(c) "Also, the weights in dccp_li_hist_w appear to be wrong.  They should be 5, 5, 5, 5, 4, 3, 2, 1"
    => Please see BUG#4. To me it seems better to use exact values, but the implication behind these
        powers of 2 is that the implicitly get converted into bit-shifts and hence execute faster (as
        Arnaldo taught me).

		
3) Auditing against RFC 3448 (draft 3448bis)
======================
I am referring to the more recent draft 3448bis, section 5.4, since the description in that draft is better
with regard to the case where k < 8 loss intervals have been found.

The following preconditions and terminology apply:

	* n is set to 7 and indices run 0..7, hence this is in accordance with [RFC 3448, 5.4]: we are
          never using more than 8 loss intervals, as is suggested there.

	* I_0 is the most recent loss interval. It is always included (see above for explanation).

	* The loss interval list is managed in LIFO manner (list_add), hence I_0 is at the head, and
          I_7 is at the tail.

	* Due to static allocation in dccp_li_hist_interval_new() and due to the add/delete cycle in 
          ccid3_hc_rx_update_li, the list always contains a constant number of 8 elements.


(a) Checking the way I_tot0 and W_tot are added
-----------------------------------------------    
The specification states the following (irrelevant statements have been removed):
	I_tot0 = 0;
	W_tot = 0;
        for (i = 0 to k-1) {
           I_tot0 = I_tot0 + (I_i * w_i);
           W_tot  = W_tot  + w_i;
         }
	
	=> In the current code we have 

	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
		if (li_entry->dccplih_interval != ~0) {
			i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
			w_tot  += dccp_li_hist_w[i];
			
	=> In the current code, w_tot is added correctly, but i_tot0 is not, since I_tot7 will
            currentlly be added. Or, if k < 7, I_tot_k will be added (and it should not be).
            This is _not_ fixed by Ian's patch.

			
(b) Checking the way I_tot1 is summed
-------------------------------------
Here the specification states the following (again only relevant parts printed):

         I_tot1 = 0;
         for (i = 1 to k) {
           I_tot1 = I_tot1 + (I_i * w_(i-1));
         }

	 => In the current code we have:
	
	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
		if (li_entry->dccplih_interval != ~0) {
			if (i != 0)
				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];

	 => This is correct, since it sums up all I_i's from 1..k as required

	 => By contrast, Ian's patch does the following.
	
	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
 		if (li_entry->dccplih_interval != ~0U) {
			/* ... */
			if (i != 7)
				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i + 1];
			if (i = 0) {
				non_loss = dccp_hdr_seq(skb);
				sub48(&non_loss, li_entry->dccplih_seqno);
			}
		}
		if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
 			break;
 	}
	/* ... */
	i_tot1 += non_loss * dccp_li_hist_w[0];

	=> This stores the value of the first interval in the list into `non_loss' after recomputing it 
            (which is not necessary, since the first interval is always at the head of the list).
            Furthermore, transcribed into pseudo code, the loop does the following:

	    I_tot1 = 0;
	    for (i = 0 to k) {           		/* k is less than or equal to 8 */
		if (i != 7 )
                   I_tot1 = I_tot1 + (I_i * w_(i+1));
            }
            
            This is not conform with [RFC 3448, 5.4], even if i_tot0 and i_tot1 are switched. 

           The other problem with this code is that if k < 7 then I_tot0 and I_tot1 always contain _all_ 
           intervals, from 0..k, - which is again not conform with the specification.

4) Conclusion
======The current code does not in all cases conform with [RFC 3448, 5.4], Ian's patch changes parts which currently
conform to non-conform ones and fixes one existing bug (BUG#4). On the whole, neither is a satisfactory solution.

5) Suggested fix
========
I think we should migrate to an array-based implementation and fix the issues flagged up above there. In particular,
 * the statement 
	if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
 			break;
   is currently redundant: due to static allocation, we never have more than DCCP_LI_HIST_IVAL_F_LENGTH elements

 * we have to resort to the clumsy comparison against ~0U to identify empty loss intervals. With a ring-buffer-like        
   array solution, we could keep track of the current fill level of the list

 * if k < 8 we have no way of knowing this before the loop, hence the problem with updating I_tot0 will persist
   as long as we don't record the `fill level' of the buffer

Re: [SUMMARY]: Problems with loss interval recalculation / audit

[Eddie Kohler]

Gerrit, this summary is not right.

RFC 3448 says that I_0 "represents the number of packets received since the 
last loss event".  (Section 5.5)  In the Linux implementation, this number is 
NOT stored in the li_entry list.  It must be calculated.  This is what Ian's 
nonloss manipulations do.

There are a number of errors in your discussion.  You claim that I_0 is the 
"most recent loss interval", and that it is stored in the li_entry structures. 
  But what RFC 3448 means by I_0 is not stored in the Linux DCCP 
implementation's li_entry structures.  Your comments under "This is the 
crucial point" do not seem to realize this.

Your comments about Ian's patch are also wrong, for the same reason.  I 
believe Ian's patch calculates I_tot0 and I_tot1 correctly, although with 
swapped names.  Certainly if there is a problem it is not the one you have 
identified.

As a side note, you say: "if k < 7 then I_tot0 and I_tot1 always contain _all_ 
intervals, from 0..k, - which is again not conform with the specification". 
What do you think the specification demands here?  I think the specification 
DOES want I_tot0 and I_tot1 to contain all intervals when there are fewer than 8.

So your conclusion is wrong as well.  Ian's patch is a strict improvement on 
the existing code.  I don't see how it worsens compliance.

It would be useful to migrate to an array-based implementation but not a panacea.

Again, Ian's patch seems good to apply.

Eddie



Gerrit Renker wrote:
> This summarizes the issues that have been discussed, 
>      reviews Ian's patch, and
>      tries to identify related problems which impede progress.
> 
> 
> 1) List of known bugs affecting this problem
> ======================
> 
> The following problems are still unresolved:
> 
> BUG#1: No attempt is made to ensure that losses are within the same RTT. This code is 
>        missing. Ian has pointed this out already in December and I think he is working
>        on it (patch `fix_consecutive_loss.diff'). Now we have another problem:
> 
> BUG#2: RTT estimation from CCVal does currently not work. There is code which goes towards
>        this, but only for the first loss interval (function ccid3_hc_rx_calc_first_li, lines
>        793 ... 835). Currently the code uses timestamps everywhere, hence we are not conforming
>        to [RFC 4342, sec. 10.3]. This impedes fixing BUG#1; I have been working on this but not
>        completed testing yet.
> 
> BUG#3: ccid3_hc_rx_detect_loss does not update hcrx->ccid3hcrx_ccval_nonloss in sync with
>        hcrx->ccid3hcrx_seqno_nonloss  => this makes it difficult to fix BUG#1, since as a conseqence
>        we now longer know which non-loss CCVal belongs to which non-loss sequence number.
> 
> BUG#4: Weights are scaled by 4 but the end result, in dccp_li_hist_calc_i_mean, is not divided by 4.
>        This is fixed in Ian's patch, but _not_ in the existing code.> 
> WISH#1: Using an array for the loss history would much simplify the code (as per earlier emails).
> 
> 
> 2) Issues raised by Eddie
> ============> The following are quotes from earlier emails.
> 
> (a) "From Ian's patch, it appears that the OLD code DID NOT include the most 
>      recent loss interval (i.e., the incomplete loss interval, the one that has no 
>      losses) in its calculation of i_tot1.  Ian has added the following line to do 
>      this:
> 
>      > +    i_tot1 += non_loss * dccp_li_hist_w[0];
> 
>      This is correct.  The RFC requires that one of the i_tots include the 
>      incomplete loss interval.  So this part of the patch is required for RFC 
>      compliance.
> 
>      I am assuming however that the incomplete loss interval is NOT included in the 
>      'hcrx->ccid3hcrx_li_hist' list.  If that list DOES include the incomplete loss 
>      interval, then the code would need to be different."
> 
>    => This is the crucial point: the last loss interval is always added to the list first;
>        both before and in Ian's patch. To illustrate, the calling path for this is as follows.
> 
> 	ccid3_hc_rx_packet_recv():
> 		loss = ccid3_hc_rx_detect_loss(sk, packet);
> 
>         ccid3_hc_rx_detect_loss():
> 		while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) > TFRC_RECV_NUM_LATE_LOSS) {
> 			loss = 1;
> 			ccid3_hc_rx_update_li(sk, hcrx->ccid3hcrx_seqno_nonloss,
> 		 	       	        	  hcrx->ccid3hcrx_ccval_nonloss);
> 
> 	ccid3_hc_rx_update_li(): adds interval to hcrx->ccid3hcrx_li_hist
> 
>         Back in ccid3_hc_rx_packet_recv(), dccp_li_hist_calc_i_mean() is only executed when loss = 1,
>         hence in dccp_li_hist_calc_i_mean() the most recent interval I_0 is always at the top of the list.
> 
> 
> (b) "i_tot0 should include non_loss, but in the code i_tot1 does."
>     => Please see below.
> 
> (c) "Also, the weights in dccp_li_hist_w appear to be wrong.  They should be 5, 5, 5, 5, 4, 3, 2, 1"
>     => Please see BUG#4. To me it seems better to use exact values, but the implication behind these
>         powers of 2 is that the implicitly get converted into bit-shifts and hence execute faster (as
>         Arnaldo taught me).
> 
> 		
> 3) Auditing against RFC 3448 (draft 3448bis)
> ======================
> I am referring to the more recent draft 3448bis, section 5.4, since the description in that draft is better
> with regard to the case where k < 8 loss intervals have been found.
> 
> The following preconditions and terminology apply:
> 
> 	* n is set to 7 and indices run 0..7, hence this is in accordance with [RFC 3448, 5.4]: we are
>           never using more than 8 loss intervals, as is suggested there.
> 
> 	* I_0 is the most recent loss interval. It is always included (see above for explanation).
> 
> 	* The loss interval list is managed in LIFO manner (list_add), hence I_0 is at the head, and
>           I_7 is at the tail.
> 
> 	* Due to static allocation in dccp_li_hist_interval_new() and due to the add/delete cycle in 
>           ccid3_hc_rx_update_li, the list always contains a constant number of 8 elements.
> 
> 
> (a) Checking the way I_tot0 and W_tot are added
> -----------------------------------------------    
> The specification states the following (irrelevant statements have been removed):
> 	I_tot0 = 0;
> 	W_tot = 0;
>         for (i = 0 to k-1) {
>            I_tot0 = I_tot0 + (I_i * w_i);
>            W_tot  = W_tot  + w_i;
>          }
> 	
> 	=> In the current code we have 
> 
> 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
> 		if (li_entry->dccplih_interval != ~0) {
> 			i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
> 			w_tot  += dccp_li_hist_w[i];
> 			
> 	=> In the current code, w_tot is added correctly, but i_tot0 is not, since I_tot7 will
>             currentlly be added. Or, if k < 7, I_tot_k will be added (and it should not be).
>             This is _not_ fixed by Ian's patch.
> 
> 			
> (b) Checking the way I_tot1 is summed
> -------------------------------------
> Here the specification states the following (again only relevant parts printed):
> 
>          I_tot1 = 0;
>          for (i = 1 to k) {
>            I_tot1 = I_tot1 + (I_i * w_(i-1));
>          }
> 
> 	 => In the current code we have:
> 	
> 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
> 		if (li_entry->dccplih_interval != ~0) {
> 			if (i != 0)
> 				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];
> 
> 	 => This is correct, since it sums up all I_i's from 1..k as required
> 
> 	 => By contrast, Ian's patch does the following.
> 	
> 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
>  		if (li_entry->dccplih_interval != ~0U) {
> 			/* ... */
> 			if (i != 7)
> 				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i + 1];
> 			if (i = 0) {
> 				non_loss = dccp_hdr_seq(skb);
> 				sub48(&non_loss, li_entry->dccplih_seqno);
> 			}
> 		}
> 		if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
>  			break;
>  	}
> 	/* ... */
> 	i_tot1 += non_loss * dccp_li_hist_w[0];
> 
> 	=> This stores the value of the first interval in the list into `non_loss' after recomputing it 
>             (which is not necessary, since the first interval is always at the head of the list).
>             Furthermore, transcribed into pseudo code, the loop does the following:
> 
> 	    I_tot1 = 0;
> 	    for (i = 0 to k) {           		/* k is less than or equal to 8 */
> 		if (i != 7 )
>                    I_tot1 = I_tot1 + (I_i * w_(i+1));
>             }
>             
>             This is not conform with [RFC 3448, 5.4], even if i_tot0 and i_tot1 are switched. 
> 
>            The other problem with this code is that if k < 7 then I_tot0 and I_tot1 always contain _all_ 
>            intervals, from 0..k, - which is again not conform with the specification.
> 
> 4) Conclusion
> ======> The current code does not in all cases conform with [RFC 3448, 5.4], Ian's patch changes parts which currently
> conform to non-conform ones and fixes one existing bug (BUG#4). On the whole, neither is a satisfactory solution.
> 
> 5) Suggested fix
> ========
> I think we should migrate to an array-based implementation and fix the issues flagged up above there. In particular,
>  * the statement 
> 	if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
>  			break;
>    is currently redundant: due to static allocation, we never have more than DCCP_LI_HIST_IVAL_F_LENGTH elements
> 
>  * we have to resort to the clumsy comparison against ~0U to identify empty loss intervals. With a ring-buffer-like        
>    array solution, we could keep track of the current fill level of the list
> 
>  * if k < 8 we have no way of knowing this before the loop, hence the problem with updating I_tot0 will persist
>    as long as we don't record the `fill level' of the buffer

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Gerrit Renker]

Thank you for your feedback.

|  Gerrit, this summary is not right.
I am just a human being and so it can happen that I am not right. 
To keep this constructive, please let's examine the facts, ok?

There are some good points you are making, but even using these the problem is not
fully solved, there are further problems which also need to be tackled and which did
not before appear in the analysis.

|  RFC 3448 says that I_0 "represents the number of packets received since the 
|  last loss event".  (Section 5.5)  In the Linux implementation, this number is 
|  NOT stored in the li_entry list.  It must be calculated.  This is what Ian's 
|  nonloss manipulations do.
|  
|  There are a number of errors in your discussion.  You claim that I_0 is the 
|  "most recent loss interval", and that it is stored in the li_entry structures. 
|    But what RFC 3448 means by I_0 is not stored in the Linux DCCP 
|  implementation's li_entry structures.  Your comments under "This is the 
|  crucial point" do not seem to realize this.
There is truth in this, but I need to put it in relation to how the list is handled. 
What I stated below in "This is the crucial point" is that the highest received seqno
and CCVal are always stored at the head of the list. 

( I just found out that there is another
  PROBLEM#1: For the first loss interval (as per [RFC 3448, 6.3.1]), the timestamp
            and sequence number are not stored, only the interval is. )

For all other loss events, timestamp and sequence number are stored. This also holds
for I_0; it could be that the interval is 0 here due to (seq_temp becomes `interval')
   seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_nonloss);
but I am not entirely sure about that. And it is probably safer to encode this
case more explicitly.

In any way, this clarification leads to 
PROBLEM#2: Since I_0 always sits at the head of the list, there are at most n=7 
           completed loss interval entries (not 8 as the RFC recommends).
  
|  Your comments about Ian's patch are also wrong, for the same reason.  I 
|  believe Ian's patch calculates I_tot0 and I_tot1 correctly, although with 
|  swapped names.  Certainly if there is a problem it is not the one you have 
|  identified.
If the above assumption that the interval of I_0 is 0 holds then in Ian's patch
(where I_0' is the interval called `non_loss' in Ian's patch) we have that
 -  I_tot0 is the sum  I_1 * w_1 + ... I_7 * w_7  
 -  I_tot1 is the sum  I_0' * w_0 + I_1 * w_2 +  I_2 * w3 + ... + I_6 * w_7
This can't be right.

  
|  As a side note, you say: "if k < 7 then I_tot0 and I_tot1 always contain _all_ 
|  intervals, from 0..k, - which is again not conform with the specification". 
|  What do you think the specification demands here?  I think the specification 
|  DOES want I_tot0 and I_tot1 to contain all intervals when there are fewer than 8.
|  
|  So your conclusion is wrong as well.  Ian's patch is a strict improvement on 
|  the existing code.  I don't see how it worsens compliance.
As said, I agree with you that there are points in the analysis which need revision.
However, as there are problems with Ian's patch such as the one stated above, 
and as there are yet unresolved problems with the current code, we need to work a little
harder to really resolve the problems - and without introducing new bugs.

  
|  It would be useful to migrate to an array-based implementation but not a panacea.
|  
|  Again, Ian's patch seems good to apply.
Disagree due to the reasons above.

Again thanks for your input, such discussion helps clarifying where the real issues are.
I will try to compile an update of the problems discussed so far, further comments are welcome.

Gerrit

|  Gerrit Renker wrote:
|  > This summarizes the issues that have been discussed, 
|  >      reviews Ian's patch, and
|  >      tries to identify related problems which impede progress.
|  > 
|  > 
|  > 1) List of known bugs affecting this problem
|  > ======================
|  > 
|  > The following problems are still unresolved:
|  > 
|  > BUG#1: No attempt is made to ensure that losses are within the same RTT. This code is 
|  >        missing. Ian has pointed this out already in December and I think he is working
|  >        on it (patch `fix_consecutive_loss.diff'). Now we have another problem:
|  > 
|  > BUG#2: RTT estimation from CCVal does currently not work. There is code which goes towards
|  >        this, but only for the first loss interval (function ccid3_hc_rx_calc_first_li, lines
|  >        793 ... 835). Currently the code uses timestamps everywhere, hence we are not conforming
|  >        to [RFC 4342, sec. 10.3]. This impedes fixing BUG#1; I have been working on this but not
|  >        completed testing yet.
|  > 
|  > BUG#3: ccid3_hc_rx_detect_loss does not update hcrx->ccid3hcrx_ccval_nonloss in sync with
|  >        hcrx->ccid3hcrx_seqno_nonloss  => this makes it difficult to fix BUG#1, since as a conseqence
|  >        we now longer know which non-loss CCVal belongs to which non-loss sequence number.
|  > 
|  > BUG#4: Weights are scaled by 4 but the end result, in dccp_li_hist_calc_i_mean, is not divided by 4.
|  >        This is fixed in Ian's patch, but _not_ in the existing code.> 
|  > WISH#1: Using an array for the loss history would much simplify the code (as per earlier emails).
|  > 
|  > 
|  > 2) Issues raised by Eddie
|  > ============|  > The following are quotes from earlier emails.
|  > 
|  > (a) "From Ian's patch, it appears that the OLD code DID NOT include the most 
|  >      recent loss interval (i.e., the incomplete loss interval, the one that has no 
|  >      losses) in its calculation of i_tot1.  Ian has added the following line to do 
|  >      this:
|  > 
|  >      > +    i_tot1 += non_loss * dccp_li_hist_w[0];
|  > 
|  >      This is correct.  The RFC requires that one of the i_tots include the 
|  >      incomplete loss interval.  So this part of the patch is required for RFC 
|  >      compliance.
|  > 
|  >      I am assuming however that the incomplete loss interval is NOT included in the 
|  >      'hcrx->ccid3hcrx_li_hist' list.  If that list DOES include the incomplete loss 
|  >      interval, then the code would need to be different."
|  > 
|  >    => This is the crucial point: the last loss interval is always added to the list first;
|  >        both before and in Ian's patch. To illustrate, the calling path for this is as follows.
|  > 
|  > 	ccid3_hc_rx_packet_recv():
|  > 		loss = ccid3_hc_rx_detect_loss(sk, packet);
|  > 
|  >         ccid3_hc_rx_detect_loss():
|  > 		while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) > TFRC_RECV_NUM_LATE_LOSS) {
|  > 			loss = 1;
|  > 			ccid3_hc_rx_update_li(sk, hcrx->ccid3hcrx_seqno_nonloss,
|  > 		 	       	        	  hcrx->ccid3hcrx_ccval_nonloss);
|  > 
|  > 	ccid3_hc_rx_update_li(): adds interval to hcrx->ccid3hcrx_li_hist
|  > 
|  >         Back in ccid3_hc_rx_packet_recv(), dccp_li_hist_calc_i_mean() is only executed when loss = 1,
|  >         hence in dccp_li_hist_calc_i_mean() the most recent interval I_0 is always at the top of the list.
|  > 
|  > 
|  > (b) "i_tot0 should include non_loss, but in the code i_tot1 does."
|  >     => Please see below.
|  > 
|  > (c) "Also, the weights in dccp_li_hist_w appear to be wrong.  They should be 5, 5, 5, 5, 4, 3, 2, 1"
|  >     => Please see BUG#4. To me it seems better to use exact values, but the implication behind these
|  >         powers of 2 is that the implicitly get converted into bit-shifts and hence execute faster (as
|  >         Arnaldo taught me).
|  > 
|  > 		
|  > 3) Auditing against RFC 3448 (draft 3448bis)
|  > ======================
|  > I am referring to the more recent draft 3448bis, section 5.4, since the description in that draft is better
|  > with regard to the case where k < 8 loss intervals have been found.
|  > 
|  > The following preconditions and terminology apply:
|  > 
|  > 	* n is set to 7 and indices run 0..7, hence this is in accordance with [RFC 3448, 5.4]: we are
|  >           never using more than 8 loss intervals, as is suggested there.
|  > 
|  > 	* I_0 is the most recent loss interval. It is always included (see above for explanation).
|  > 
|  > 	* The loss interval list is managed in LIFO manner (list_add), hence I_0 is at the head, and
|  >           I_7 is at the tail.
|  > 
|  > 	* Due to static allocation in dccp_li_hist_interval_new() and due to the add/delete cycle in 
|  >           ccid3_hc_rx_update_li, the list always contains a constant number of 8 elements.
|  > 
|  > 
|  > (a) Checking the way I_tot0 and W_tot are added
|  > -----------------------------------------------    
|  > The specification states the following (irrelevant statements have been removed):
|  > 	I_tot0 = 0;
|  > 	W_tot = 0;
|  >         for (i = 0 to k-1) {
|  >            I_tot0 = I_tot0 + (I_i * w_i);
|  >            W_tot  = W_tot  + w_i;
|  >          }
|  > 	
|  > 	=> In the current code we have 
|  > 
|  > 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
|  > 		if (li_entry->dccplih_interval != ~0) {
|  > 			i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
|  > 			w_tot  += dccp_li_hist_w[i];
|  > 			
|  > 	=> In the current code, w_tot is added correctly, but i_tot0 is not, since I_tot7 will
|  >             currentlly be added. Or, if k < 7, I_tot_k will be added (and it should not be).
|  >             This is _not_ fixed by Ian's patch.
|  > 
|  > 			
|  > (b) Checking the way I_tot1 is summed
|  > -------------------------------------
|  > Here the specification states the following (again only relevant parts printed):
|  > 
|  >          I_tot1 = 0;
|  >          for (i = 1 to k) {
|  >            I_tot1 = I_tot1 + (I_i * w_(i-1));
|  >          }
|  > 
|  > 	 => In the current code we have:
|  > 	
|  > 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
|  > 		if (li_entry->dccplih_interval != ~0) {
|  > 			if (i != 0)
|  > 				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1];
|  > 
|  > 	 => This is correct, since it sums up all I_i's from 1..k as required
|  > 
|  > 	 => By contrast, Ian's patch does the following.
|  > 	
|  > 	list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) {
|  >  		if (li_entry->dccplih_interval != ~0U) {
|  > 			/* ... */
|  > 			if (i != 7)
|  > 				i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i + 1];
|  > 			if (i = 0) {
|  > 				non_loss = dccp_hdr_seq(skb);
|  > 				sub48(&non_loss, li_entry->dccplih_seqno);
|  > 			}
|  > 		}
|  > 		if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
|  >  			break;
|  >  	}
|  > 	/* ... */
|  > 	i_tot1 += non_loss * dccp_li_hist_w[0];
|  > 
|  > 	=> This stores the value of the first interval in the list into `non_loss' after recomputing it 
|  >             (which is not necessary, since the first interval is always at the head of the list).
|  >             Furthermore, transcribed into pseudo code, the loop does the following:
|  > 
|  > 	    I_tot1 = 0;
|  > 	    for (i = 0 to k) {           		/* k is less than or equal to 8 */
|  > 		if (i != 7 )
|  >                    I_tot1 = I_tot1 + (I_i * w_(i+1));
|  >             }
|  >             
|  >             This is not conform with [RFC 3448, 5.4], even if i_tot0 and i_tot1 are switched. 
|  > 
|  >            The other problem with this code is that if k < 7 then I_tot0 and I_tot1 always contain _all_ 
|  >            intervals, from 0..k, - which is again not conform with the specification.
|  > 
|  > 4) Conclusion
|  > ======|  > The current code does not in all cases conform with [RFC 3448, 5.4], Ian's patch changes parts which currently
|  > conform to non-conform ones and fixes one existing bug (BUG#4). On the whole, neither is a satisfactory solution.
|  > 
|  > 5) Suggested fix
|  > ========
|  > I think we should migrate to an array-based implementation and fix the issues flagged up above there. In particular,
|  >  * the statement 
|  > 	if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
|  >  			break;
|  >    is currently redundant: due to static allocation, we never have more than DCCP_LI_HIST_IVAL_F_LENGTH elements
|  > 
|  >  * we have to resort to the clumsy comparison against ~0U to identify empty loss intervals. With a ring-buffer-like        
|  >    array solution, we could keep track of the current fill level of the list
|  > 
|  >  * if k < 8 we have no way of knowing this before the loop, hence the problem with updating I_tot0 will persist
|  >    as long as we don't record the `fill level' of the buffer
|  -
|  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: [SUMMARY]: Problems with loss interval recalculation / audit

[Eddie Kohler]

Gerrit,

First I would like to send a NEWBIE REQUEST.

How can I get a complete copy of the DCCP source checked out, including 
your/Ian's patches?  Where is there something on line that explains the git 
process?  Thanks for your/anyone's help.

Now:

> |  RFC 3448 says that I_0 "represents the number of packets received since the 
> |  last loss event".  (Section 5.5)  In the Linux implementation, this number is 
> |  NOT stored in the li_entry list.  It must be calculated.  This is what Ian's 
> |  nonloss manipulations do.
> |  
> |  There are a number of errors in your discussion.  You claim that I_0 is the 
> |  "most recent loss interval", and that it is stored in the li_entry structures. 
> |    But what RFC 3448 means by I_0 is not stored in the Linux DCCP 
> |  implementation's li_entry structures.  Your comments under "This is the 
> |  crucial point" do not seem to realize this.
> There is truth in this, but I need to put it in relation to how the list is handled. 
> What I stated below in "This is the crucial point" is that the highest received seqno
> and CCVal are always stored at the head of the list. 
> 
> ( I just found out that there is another
>   PROBLEM#1: For the first loss interval (as per [RFC 3448, 6.3.1]), the timestamp
>             and sequence number are not stored, only the interval is. )
> 
> For all other loss events, timestamp and sequence number are stored. This also holds
> for I_0; it could be that the interval is 0 here due to (seq_temp becomes `interval')
>    seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_nonloss);
> but I am not entirely sure about that. And it is probably safer to encode this
> case more explicitly.
> 
> In any way, this clarification leads to 
> PROBLEM#2: Since I_0 always sits at the head of the list, there are at most n=7 
>            completed loss interval entries (not 8 as the RFC recommends).

I find this difficult to follow, but is there still confusion?  According to 
my reading of the patches, and Ian confirmed this, what RFC3448 means by I_0 
**is not stored on the list at all**.  The list stores I_1...I_8.  Remember 
that I_0 is the incomplete loss interval.

> |  Your comments about Ian's patch are also wrong, for the same reason.  I 
> |  believe Ian's patch calculates I_tot0 and I_tot1 correctly, although with 
> |  swapped names.  Certainly if there is a problem it is not the one you have 
> |  identified.
> If the above assumption that the interval of I_0 is 0 holds then in Ian's patch
> (where I_0' is the interval called `non_loss' in Ian's patch) we have that
>  -  I_tot0 is the sum  I_1 * w_1 + ... I_7 * w_7  
>  -  I_tot1 is the sum  I_0' * w_0 + I_1 * w_2 +  I_2 * w3 + ... + I_6 * w_7
> This can't be right.

Your analysis is wrong, I think.  Ian's patch sent 12/27 calculates

   I_tot0 = I_1 * w_0 + ... + I_8 * w_7
   I_tot1 = I_0 * w_0 + I_1 * w_1 + ... + I_7 * w_7.

Because "i" starts at 0.  The relevant part of the patch.

  			i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
  			w_tot  += dccp_li_hist_w[i];
+			if (i != 7)
+				i_tot1 += li_entry->dccplih_interval
+				   * dccp_li_hist_w[i + 1];
+			if (i = 0) {
+				non_loss = dccp_hdr_seq(skb);
+				sub48(&non_loss, li_entry->dccplih_seqno);
+			}

When "i = 0", the loop is examining I_1.  Then i_tot0 += I_1*w[0], and i_tot1 
+= I_1*w[1], exactly as one would like.  The case "i=7" (that is, I_8) 
affects i_tot0 but not i_tot1, exactly as one would like.

Eddie

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Arnaldo Carvalho de Melo]

On 1/8/07, Eddie Kohler <kohler@cs.ucla.edu> wrote:
> Gerrit,
>
> First I would like to send a NEWBIE REQUEST.
>
> How can I get a complete copy of the DCCP source checked out, including
> your/Ian's patches?  Where is there something on line that explains the git
> process?  Thanks for your/anyone's help.

Git process:

Install git (if you have problems with this, let us know):

Then:

git-clone git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6.git

With this you should have David Miller networking tree, the canonical
one when working on linux networking code, mine is just a staging area
for David as his is a staging area for Linus.

At this point Gerrit is maintaining a set of patches, not using git,
so you'll have to get the patches he is staging for me at:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/patch-backlog/the_whole_lot.tar.gz

Apply them in order and you'll have the current status quo, I hope to
go over the patches Gerrit is graciously maintaining soon, but the
process above should be simple enough for you to follow.

Questions?

- Arnaldo

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Ian McDonald]

On 09/01/07, Arnaldo Carvalho de Melo <arnaldo.melo@gmail.com> wrote:
> On 1/8/07, Eddie Kohler <kohler@cs.ucla.edu> wrote:
> > Gerrit,
> >
> > First I would like to send a NEWBIE REQUEST.
> >
> > How can I get a complete copy of the DCCP source checked out, including
> > your/Ian's patches?  Where is there something on line that explains the git
> > process?  Thanks for your/anyone's help.
>
> Git process:
>
> Install git (if you have problems with this, let us know):
>
> Then:
>
> git-clone git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6.git
>
> With this you should have David Miller networking tree, the canonical
> one when working on linux networking code, mine is just a staging area
> for David as his is a staging area for Linus.
>
> At this point Gerrit is maintaining a set of patches, not using git,
> so you'll have to get the patches he is staging for me at:
>
> http://www.erg.abdn.ac.uk/users/gerrit/dccp/patch-backlog/the_whole_lot.tar.gz
>
> Apply them in order and you'll have the current status quo, I hope to
> go over the patches Gerrit is graciously maintaining soon, but the
> process above should be simple enough for you to follow.
>
> Questions?
>
> - Arnaldo

If you're just wanting to test Arnaldo's advice is great. If you're
wanting to code for a bit longer and keep up to date I'd add to his
advice a bit.

What I'd advise at present is to clone off Linus' tree and then make a
copy of this off Dave M's tree if needed (at present it is not needed
as no outstanding DCCP patches). This is because you will have to keep
recloning Dave M's tree when he starts afresh off Linus' tree.

I would use a patch management tool such as stgit or quilt so you can
look at individual patches. I personally use stgit and I can type
something like "stg import -t -s ../gerrit/series" to pull in all
Gerrit's patches.

I've written a draft paper (more practical than academic) on this
process which can be found on my webpage. I also have put quite a few
notes up on my local LUG Wiki http://wlug.org.nz/KernelDevelopment

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

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Gerrit Renker]

|  How can I get a complete copy of the DCCP source checked out, including 
|  your/Ian's patches?  Where is there something on line that explains the git 
|  process?  Thanks for your/anyone's help.
I found the following tutorial useful:
  http://www.kernel.org/pub/software/scm/git/docs/tutorial.html
In addition, Ian's links are also very helpful - they have helped me in the past. 
In the git sources there are a few summary documents as well, I found Documentation/everyday.txt good

Both my patches on    http://www.erg.abdn.ac.uk/users/gerrit/dccp/patch-backlog/the_whole_lot.tar.gz
and Ian's patches on  http://wand.net.nz/~iam4/dccp/patches/
are `stacked': if you have the quilt tool then it is best to fork a new git branch and apply
them in order. (If not, one can use for p in `cat series`; do patch -p1 < $p; done).
There is overlap between Ian's and my patch set; I usually copy those patches from the list where
we have finished discussion. 

|  > ( I just found out that there is another
|  >   PROBLEM#1: For the first loss interval (as per [RFC 3448, 6.3.1]), the timestamp
|  >             and sequence number are not stored, only the interval is. )
I just noted that I was wrong here - timestamp and sequence number are stored, but by a
different routine (dccp_li_hist_interval_new) - it would be great if we could perform the
storing of timestamp/sequence number always in the same function (dccp_li_update_li).

|  > 
|  > For all other loss events, timestamp and sequence number are stored. This also holds
|  > for I_0; it could be that the interval is 0 here due to (seq_temp becomes `interval')
|  >    seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_nonloss);
|  > but I am not entirely sure about that. And it is probably safer to encode this
|  > case more explicitly.
|  > 
|  > In any way, this clarification leads to 
|  > PROBLEM#2: Since I_0 always sits at the head of the list, there are at most n=7 
|  >            completed loss interval entries (not 8 as the RFC recommends).
|  
|  I find this difficult to follow, but is there still confusion?  According to 
|  my reading of the patches, and Ian confirmed this, what RFC3448 means by I_0 
|  **is not stored on the list at all**.  The list stores I_1...I_8.  Remember 
|  that I_0 is the incomplete loss interval.
ACK - I_0 is the incomplete loss interval. The way the code is currently organised,
I_0 sits always on top of the list, which is due to:
 * in ccid3_hc_rx_packet_recv(), the call to ccid3_hc_rx_detect_loss() comes first
 * ccid3_hc_rx_detect_loss in turn calls dccp_li_update_li()
 * control then resumes in ccid3_hc_rx_packet_recv()
Hence the detection of a loss event always triggers insertion of the sequence number 
and timestamp at the head of the list. 
With regard to your above comment, we should probably change this so that I_0 is
not stored on top of the list - or adapt the list handling so that I_0 can be distinguished
from I_1 ... I_k (k <= 8).

 
|  > |  Your comments about Ian's patch are also wrong, for the same reason.  I 
|  > |  believe Ian's patch calculates I_tot0 and I_tot1 correctly, although with 
|  > |  swapped names.  Certainly if there is a problem it is not the one you have 
|  > |  identified.
|  > If the above assumption that the interval of I_0 is 0 holds then in Ian's patch
|  > (where I_0' is the interval called `non_loss' in Ian's patch) we have that
|  >  -  I_tot0 is the sum  I_1 * w_1 + ... I_7 * w_7  
|  >  -  I_tot1 is the sum  I_0' * w_0 + I_1 * w_2 +  I_2 * w3 + ... + I_6 * w_7
|  > This can't be right.
|  
|  Your analysis is wrong, I think.  Ian's patch sent 12/27 calculates
|  
|     I_tot0 = I_1 * w_0 + ... + I_8 * w_7
|     I_tot1 = I_0 * w_0 + I_1 * w_1 + ... + I_7 * w_7.
|  
|  Because "i" starts at 0.  The relevant part of the patch.
|  
|    			i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i];
|    			w_tot  += dccp_li_hist_w[i];
|  +			if (i != 7)
|  +				i_tot1 += li_entry->dccplih_interval
|  +				   * dccp_li_hist_w[i + 1];
|  +			if (i = 0) {
|  +				non_loss = dccp_hdr_seq(skb);
|  +				sub48(&non_loss, li_entry->dccplih_seqno);
|  +			}
|  
|  When "i = 0", the loop is examining I_1.  Then i_tot0 += I_1*w[0], and i_tot1 
|  += I_1*w[1], exactly as one would like.  The case "i=7" (that is, I_8) 
|  affects i_tot0 but not i_tot1, exactly as one would like.
I think it is different - that when 'i = 0' then we are looking at I_0. This is confirmed by the statement
		if (i = 0) {
			non_loss = dccp_hdr_seq(skb);
			sub48(&non_loss, li_entry->dccplih_seqno);
		}
which shows how the code uses the last recorded loss sequence number li_entry->dccplih_seqno to compute
the interval length for non_loss = I_0. 
Hence we have here that i_tot0 += I_0' * w[0] and i_tot1 += I_0' * w[1], where I_0' is the interval
stored in li_entry. As per earlier email this could be 0 but I am still not entirely sure it is.
 
In the second iteration of the loop we have 

 i_tot0 += I_1 * w[1]
 i_tot1 += I_1 * w[2]

and in the third we have

 i_tot0 += I_2 * w[2]
 i_tot1 += I_2 * w[3]

but the RFC says

 I_tot0 = I_0 * w[0] + I_1 * w[1] + I_2 * w[2] + I_3 * w[3] + I_4 * w[4] + I_5 * w[5] + I_6 * w[6] + I_7 * w[7]
 I_tot1 = I_1 * w[0] + I_2 * w[1] + I_3 * w[2] + I_4 * w[3] + I_5 * w[4] + I_6 * w[5] + I_7 * w[6] + I_8 * w[7]

which is different from what the above code does. 

So I think what we can take home as `todo' items from this is
 * correct the list handling with regard to I_0 
 * ensure that I_1 ... I_8 all fit in the list
 * compute the interval length I_0 as done for `non_loss' in Ian's patch
 * change the summation loop so that it matches the one in the RFC

I am still trying to compile all this into (yet another :) summary, thanks for your comments.

Gerrit

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Ian McDonald]

On 09/01/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> Hence the detection of a loss event always triggers insertion of the sequence number
> and timestamp at the head of the list.
> With regard to your above comment, we should probably change this so that I_0 is
> not stored on top of the list - or adapt the list handling so that I_0 can be distinguished
> from I_1 ... I_k (k <= 8).
>
I_0 is not stored at the head of the list. It is stored in non-loss. I
can understand the confusion as my code wasn't clear.

> So I think what we can take home as `todo' items from this is
>  * correct the list handling with regard to I_0
>  * ensure that I_1 ... I_8 all fit in the list
>  * compute the interval length I_0 as done for `non_loss' in Ian's patch
>  * change the summation loop so that it matches the one in the RFC
>

I've changed all the code to match the RFC and added a few more
comments. I believe my logic was correct but extremely confusing as
I'd reversed i_tot0 and i_tot1 meanings not to mention how I had done
the loop counters!! I've not made it so you can read along the RFC
even though the same thing is done.

I'm glad to tidy this up as this was a bit messy in BSD, got munted in
the change to Linux. Being in arrays would help clarity (but not
results) quite a bit further I think too.

Patch to follow.

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

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Ian McDonald]

On 09/01/07, Ian McDonald <ian.mcdonald@jandi.co.nz> wrote:
> I've written a draft paper (more practical than academic) on this
> process which can be found on my webpage. I also have put quite a few
> notes up on my local LUG Wiki http://wlug.org.nz/KernelDevelopment
>
> Ian

Greg KH has also posted a book online (free) on this process which
should be really good:
http://www.kroah.com/lkn/
-- 
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

Re: [SUMMARY]: Problems with loss interval recalculation / audit against [RFC 3448, 5.4]

[Gerrit Renker]

|  > Hence the detection of a loss event always triggers insertion of the sequence number
|  > and timestamp at the head of the list.
|  > With regard to your above comment, we should probably change this so that I_0 is
|  > not stored on top of the list - or adapt the list handling so that I_0 can be distinguished
|  > from I_1 ... I_k (k <= 8).
|  >
|  I_0 is not stored at the head of the list. It is stored in non-loss. I
|  can understand the confusion as my code wasn't clear.
There is still some confusion here, but it is not due to your code. With regard to I_0, the
highest sequence number before the loss occurred and the accompanying CCVal is stored at the
head of the list. The interval length stored in this history entry is invalid, in your patch
the interval length is computed - which is correct.
But we do need a bit more clarification about the interval length of I_0 here:

 -> start from the highest sequence number received before the loss (as your code does) or
 -> use "the number of packets received since the last loss event" as specified in [RFC 3448, page 16]

Hence the previous email to Eddie which I hope he will be able to answer.

  
|  > So I think what we can take home as `todo' items from this is
|  >  * correct the list handling with regard to I_0
|  >  * ensure that I_1 ... I_8 all fit in the list
|  >  * compute the interval length I_0 as done for `non_loss' in Ian's patch
|  >  * change the summation loop so that it matches the one in the RFC
|  >
|  
|  I've changed all the code to match the RFC and added a few more
|  comments. I believe my logic was correct but extremely confusing as
|  I'd reversed i_tot0 and i_tot1 meanings not to mention how I had done
|  the loop counters!! I've not made it so you can read along the RFC
|  even though the same thing is done.
|
|  
|  I'm glad to tidy this up as this was a bit messy in BSD, got munted in
|  the change to Linux. Being in arrays would help clarity (but not
|  results) quite a bit further I think too.
|  
|  Patch to follow.
|  
I think you are jumping to conclusions too quickly. No one is blaming you or your patch. 
The problem is the current state of the CCID 3 module is full of bugs, some of which interact with the
code your patch takles - it is like opening a can of worms.

There are 12 bugs in the loss handling alone (and maybe I have missed some?), cf.
http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/detect_loss_algorithm/summary_of_loss_handling_issues.txt

Therefore, we need to be careful about what we are doing. Patches can only help at this stage if they
not only remove existing bugs, but also do not provide a hinderance in removing others. This is difficult.