[2/5] Implement loss counting on TFRC-SP receiver

| Implement loss counting on TFRC-SP receiver. 
| Consider transmission's hole size as loss count.
The implementation of loss counts as the basis for Dropped Packet option has
problems and can in its current form not be used. Please see below.


                    packets (there are cases where this is not exact).

But your formula computes N_B - D, i.e. it negates this value. What you
want is dccp_loss_count(S_A, S_B, N_B) := max(S_B - S_A - 1 - N_B, 0).

A short implementation would be:

/**
 * dccp_loss_count - Approximate the number of data packets lost in a row
 * @s1:   last known sequence number before the loss ('hole')
 * @s2:   first sequence number seen after the 'hole'
 * @ndp:  ndp count associated with packet having sequence number @s2
 */
u64 dccp_loss_count(const u64 s1, const u64 s2, const u64 ndp)
{
	s64 delta = dccp_delta_seqno(s1, s2);
	
	WARN_ON(delta < 0);
	delta -= ndp + 1;

	return delta > 0 ? delta : 0;
}

But then dccp_loss_free reduces to a specialisation of the above:
bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
{
	return dccp_loss_count(s1, s2, ndp) == 0;
}

But please see above -- the function needs to be called for each hole in a row.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

In the same way, my comments follow below


>                s64 len = dccp_delta_seqno(cur->li_seqno, cong_evt_seqno);
>                if ((len <= 0) ||
>                    (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval))) {
> +                       cur->li_losses += rh->num_losses;
>                        return false;
>                }
> This has a multiplicative effect, since rh->num_losses is added to cur->li_losses
> each time the condition is evaluated. E.g. if 3 times in a row reordered (earlier)
> sequence numbers arrive, or if the CCvals do not differ (high-speed networks),
> we end up with 3 * rh->num_losses, which can't be correct.
>
>


The following code would be correct then?

              if ((len <= 0) ||
                  (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval))) {
+                       cur->li_losses += rh->num_losses;
+                       rh->num_losses  = 0;
                      return false;
With this change I suppose the could be fixed. With that, the
rh->num_losses couldn't added twice. Am I correct?




>
> --- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c
> +++ dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c
> @@ -244,6 +244,7 @@
>                h->loss_count = 3;
>                tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3),
>                                               skb, n3);
> +               h->num_losses = dccp_loss_count(s2, s3, n3);
>                return 1;
>        }
> This only measures the gap between s2 and s3, but the "hole" starts at s0,
> so it would need to be dccp_loss_count(s0, s3, n3). Algorithm is documented at
> http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\
> ccid3/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt
>

<snip>

>  }
> Here it is also between s0 and s2, not between s0 and s3. It is case VI(c.3).
>
> However, the above still is a crude approximation, since it only measures between
> the last sequence number received before the loss and the third sequence number
> after the loss. It would be better to either
>
>  * use the first sequence number after the loss (this can be s1, s2, or s3) or
>  * check if there are more holes between the first/second and the second/third
>   sequence numbers after the loss.
>
> The second option would be the correct one, it should also take the NDP counts
> of each gap into account. And already we have a fairly complicated algorithm.
>



I'll study loss_detection_algorithm_notes.txt and correct the code.
But I have one question, that i don't know if is already answered by
the documentation:
Further holes, between the the first and third packet received after
the hole are accounted only in future calls to the function, right?
Because the receiver needs to receive more packets to confirm loss,
right?
So, it's really necessary to look for other holes after the loss? Will
not this other holes be identified as losses in future?



> Another observation is that this function is only called in packet_history_sp.c,
> and only in __two_after_loss(), so that dccp_loss_count() could be made static,
> and without the need for the WARN_ON (see below), since in all above cases it is
> ensured that the first sequence number argument is "before" the second one.
>

Okay.
>
> --- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.h
> +++ dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.h
> @@ -113,6 +113,7 @@
>        u32                       packet_size,
>                                  bytes_recvd;
>        ktime_t                   bytes_start;
> +       u8                        num_losses;
>  };
> No more than 255 losses? NDP count option has space for up to 6 bytes, i.e. 2^48-1.
> Suggest u64 for consistency with the other parts.
>

Okay.


>
> --- dccp_tree_work4.orig/net/dccp/dccp.h
> +++ dccp_tree_work4/net/dccp/dccp.h
> @@ -168,6 +168,21 @@
>        return (u64)delta <= ndp + 1;

<snip>

> But then dccp_loss_free reduces to a specialisation of the above:
> bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
> {
>        return dccp_loss_count(s1, s2, ndp) == 0;
> }
>
> But please see above -- the function needs to be called for each hole in a row.
>

Thanks for correcting the calculation for me!

>>                s64 len = dccp_delta_seqno(cur->li_seqno,
>> cong_evt_seqno);
>>                if ((len <= 0) ||
>>                    (!tfrc_lh_closed_check(cur,
>> cong_evt->tfrchrx_ccval))) {
>> +                       cur->li_losses += rh->num_losses;
>>                        return false;
>>                }
>> This has a multiplicative effect, since rh->num_losses is added to
cur->li_losses
>> each time the condition is evaluated. E.g. if 3 times in a row
reordered
>> (earlier)
>> sequence numbers arrive, or if the CCvals do not differ (high-speed
networks),
>> we end up with 3 * rh->num_losses, which can't be correct.
>
>
> The following code would be correct then?
>
>               if ((len <= 0) ||
>                   (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval)))
{
> +                       cur->li_losses += rh->num_losses;
> +                       rh->num_losses  = 0;
>                       return false;
> With this change I suppose the could be fixed. With that, the
> rh->num_losses couldn't added twice. Am I correct?
>
>
The function tfrc_lh_interval_add() is called when
 * __two_after_loss() returns true (a new loss is detected) or
 * a data packet is ECN-CE marked.

I am still not sure about the 'len <= 0' case; this would be true
if an ECN-marked packet arrives whose sequence number is 'before'
the start of the current loss interval, or if a loss is detected
which is older than the start of the current loss interval.

The other case (tfrc_lh_closed_check) returns 1 if the current loss
interval is 'closed' according to RFC 4342, 10.2.

Intuitively, in the first case it refers to the preceding loss
interval (i.e. not cur->...), in the second case it seems correct.

Doing the first case is complicated due to going back in history.
The simplest solution I can think of at the moment is to ignore
the exception-case of reordered packets and do something like

    if (len <= 0) {
       /* FIXME: this belongs into the previous loss interval */  
tfrc_pr_debug("Warning: ignoring loss due to reordering");
       return false;
    }
    if (!tfrc_lh_closed_check(...)) {
        // your code from above
    }

However, there is a much deeper underlying question: currently the
implementation is not really what the specification says; if we
wanted to abide by the letter of the law, we would have to implement
the Loss Intervals Option first, and then sort out such details as
above. Discussion continues further below.

>> --- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c +++
dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c
>> @@ -244,6 +244,7 @@
>>                h->loss_count = 3;
>>                tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3),
                                              skb, n3);
>> +               h->num_losses = dccp_loss_count(s2, s3, n3);
>>                return 1;
>>        }
>> This only measures the gap between s2 and s3, but the "hole" starts at s0,
>> so it would need to be dccp_loss_count(s0, s3, n3). Algorithm is
documented at
>> http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\
>> ccid3/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt
>
> <snip>
>
>>  }
>> Here it is also between s0 and s2, not between s0 and s3. It is case
VI(c.3).
>> However, the above still is a crude approximation, since it only
measures between
>> the last sequence number received before the loss and the third
sequence
>> number
>> after the loss. It would be better to either
>>  * use the first sequence number after the loss (this can be s1, s2, or
s3) or
>>  * check if there are more holes between the first/second and the
second/third
>>   sequence numbers after the loss.
>> The second option would be the correct one, it should also take the NDP
counts
>> of each gap into account. And already we have a fairly complicated
algorithm.
>
>
>
> I'll study loss_detection_algorithm_notes.txt and correct the code. But
I have one question, that i don't know if is already answered by the
documentation:
> Further holes, between the the first and third packet received after the
hole are accounted only in future calls to the function, right? Because
the receiver needs to receive more packets to confirm loss, right?
> So, it's really necessary to look for other holes after the loss? Will
not this other holes be identified as losses in future?
I stand corrected, you are right: only the hole between
 * the highest sequence number before the loss (S0) and
 * the first sequence number after the loss
   (S1 or S3 depending on reordering)
are relevant.

Continuing the point from above, I would like to ask which way you would
like to go with your implementation:
 (a) receiver computes the Loss Event Rate, sender just uses this value
 (b) receiver only gathers the data (loss intervals, lost packets),
     sender does all the verification, book-keeping, and computation.

From reading your patches, I think it is going in the direction of (a).
But if this is the case, we don't need the Dropped Packets Option from
RFC 5622, 8.7. By definition it only makes sense if Loss Intervals
Options are also present.

So it is necessary to decide whether to go the full way, which means
 * support Loss Intervals and Dropped Packets alike
 * modify TFRC library (it will be a redesign)
 * modify receiver code
 * modify sender code,
or to use the present approach where
 * the receiver computes the Loss Rate and
 * a Mandatory Send Loss Event Rate feature is present during feature
   negotiation, to avoid problems with incompatible senders
   (there is a comment explaining this, in net/dccp/feat.c).

Thoughts?

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Sat, Sep 19, 2009 at 9:11 AM,  <gerrit@erg.abdn.ac.uk> wrote:
>>>                s64 len = dccp_delta_seqno(cur->li_seqno,
>>> cong_evt_seqno);
>>>                if ((len <= 0) ||
>>>                    (!tfrc_lh_closed_check(cur,
>>> cong_evt->tfrchrx_ccval))) {
>>> +                       cur->li_losses += rh->num_losses;
>>>                        return false;
>>>                }
>>> This has a multiplicative effect, since rh->num_losses is added to
> cur->li_losses
>>> each time the condition is evaluated. E.g. if 3 times in a row
> reordered
>>> (earlier)
>>> sequence numbers arrive, or if the CCvals do not differ (high-speed
> networks),
>>> we end up with 3 * rh->num_losses, which can't be correct.
>>
>>
>> The following code would be correct then?
>>
>>               if ((len <= 0) ||
>>                   (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval)))
> {
>> +                       cur->li_losses += rh->num_losses;
>> +                       rh->num_losses  = 0;
>>                       return false;
>> With this change I suppose the could be fixed. With that, the
>> rh->num_losses couldn't added twice. Am I correct?
>>
>>
> The function tfrc_lh_interval_add() is called when
>  * __two_after_loss() returns true (a new loss is detected) or
>  * a data packet is ECN-CE marked.
>
> I am still not sure about the 'len <= 0' case; this would be true
> if an ECN-marked packet arrives whose sequence number is 'before'
> the start of the current loss interval, or if a loss is detected
> which is older than the start of the current loss interval.
>
> The other case (tfrc_lh_closed_check) returns 1 if the current loss
> interval is 'closed' according to RFC 4342, 10.2.
>
> Intuitively, in the first case it refers to the preceding loss
> interval (i.e. not cur->...), in the second case it seems correct.
>
> Doing the first case is complicated due to going back in history.
> The simplest solution I can think of at the moment is to ignore
> the exception-case of reordered packets and do something like
>
>    if (len <= 0) {
>       /* FIXME: this belongs into the previous loss interval */
> tfrc_pr_debug("Warning: ignoring loss due to reordering");
>       return false;
>    }
>    if (!tfrc_lh_closed_check(...)) {
>        // your code from above
>    }

Okay, i'll add your sugestion. But i don't know how this would be fixed at all.

>
> However, there is a much deeper underlying question: currently the
> implementation is not really what the specification says; if we
> wanted to abide by the letter of the law, we would have to implement
> the Loss Intervals Option first, and then sort out such details as
> above. Discussion continues further below.
>

Yes, the loss intervals options is mandatory. I'll discuss this too below.

>>> --- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c +++
> dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c
>>> @@ -244,6 +244,7 @@
>>>                h->loss_count = 3;
>>>                tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3),
>                                               skb, n3);
>>> +               h->num_losses = dccp_loss_count(s2, s3, n3);
>>>                return 1;
>>>        }
>>> This only measures the gap between s2 and s3, but the "hole" starts at s0,
>>> so it would need to be dccp_loss_count(s0, s3, n3). Algorithm is
> documented at
>>> http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\
>>> ccid3/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt
>>
>> <snip>
>>
>>>  }
>>> Here it is also between s0 and s2, not between s0 and s3. It is case
> VI(c.3).
>>> However, the above still is a crude approximation, since it only
> measures between
>>> the last sequence number received before the loss and the third
> sequence
>>> number
>>> after the loss. It would be better to either
>>>  * use the first sequence number after the loss (this can be s1, s2, or
> s3) or
>>>  * check if there are more holes between the first/second and the
> second/third
>>>   sequence numbers after the loss.
>>> The second option would be the correct one, it should also take the NDP
> counts
>>> of each gap into account. And already we have a fairly complicated
> algorithm.
>>
>>
>>
>> I'll study loss_detection_algorithm_notes.txt and correct the code. But
> I have one question, that i don't know if is already answered by the
> documentation:
>> Further holes, between the the first and third packet received after the
> hole are accounted only in future calls to the function, right? Because
> the receiver needs to receive more packets to confirm loss, right?
>> So, it's really necessary to look for other holes after the loss? Will
> not this other holes be identified as losses in future?
> I stand corrected, you are right: only the hole between
>  * the highest sequence number before the loss (S0) and
>  * the first sequence number after the loss
>   (S1 or S3 depending on reordering)
> are relevant.

Thanks, already corrected in next patch.

>
> Continuing the point from above, I would like to ask which way you would
> like to go with your implementation:
>  (a) receiver computes the Loss Event Rate, sender just uses this value
>  (b) receiver only gathers the data (loss intervals, lost packets),
>     sender does all the verification, book-keeping, and computation.
>
> From reading your patches, I think it is going in the direction of (a).
> But if this is the case, we don't need the Dropped Packets Option from
> RFC 5622, 8.7. By definition it only makes sense if Loss Intervals
> Options are also present.
>
> So it is necessary to decide whether to go the full way, which means
>  * support Loss Intervals and Dropped Packets alike
>  * modify TFRC library (it will be a redesign)
>  * modify receiver code
>  * modify sender code,
> or to use the present approach where
>  * the receiver computes the Loss Rate and
>  * a Mandatory Send Loss Event Rate feature is present during feature
>   negotiation, to avoid problems with incompatible senders
>   (there is a comment explaining this, in net/dccp/feat.c).
>
> Thoughts?
>

Initially I conceived that the receiver would compute the loss event
rate and send it, along with loss intervals and dropped packets
option. And this would enable the sender to just use the loss event
rate reported, as is done currently (in current implementation of
TFRC), or compute it itself, using loss intervals option (in case of
CCID3) and dropped packets option too (CCID4's case).
In my code, I compute the loss event rate using the options, then
compare the two values. I don't know if would be better to keep all
the loss event rate calc only at one side, sender or receiver.

I believe that the first way is better (to "support Loss Intervals and
Dropped Packets alike..."), because RFC requires loss intervals option
to be sent. And so, proceed and implement dropped packets option for
TFRC-SP. You are right, this would need a redesign and rewrite of
sender and receiver code.

| >> The following code would be correct then?
| >>
| >>	 if ((len <= 0) ||
| >>	     (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval)))
| > {
| >> +		 cur->li_losses += rh->num_losses;
| >> + 		 rh->num_losses  = 0;
| >> 		 return false;
| >> With this change I suppose the could be fixed. With that, the
| >> rh->num_losses couldn't added twice. Am I correct?
| >>
| >>
| > The function tfrc_lh_interval_add() is called when
| >  * __two_after_loss() returns true (a new loss is detected) or
| >  * a data packet is ECN-CE marked.
| >
| > I am still not sure about the 'len <= 0' case; this would be true
| > if an ECN-marked packet arrives whose sequence number is 'before'
| > the start of the current loss interval, or if a loss is detected
| > which is older than the start of the current loss interval.
| >
| > The other case (tfrc_lh_closed_check) returns 1 if the current loss
| > interval is 'closed' according to RFC 4342, 10.2.
| >
| > Intuitively, in the first case it refers to the preceding loss
| > interval (i.e. not cur->...), in the second case it seems correct.
| >
| > Doing the first case is complicated due to going back in history.
| > The simplest solution I can think of at the moment is to ignore
| > the exception-case of reordered packets and do something like
| >
| >  if (len <= 0) {
| >     /* FIXME: this belongs into the previous loss interval */
| >     tfrc_pr_debug("Warning: ignoring loss due to reordering");
| > 	return false;
| > }
| >  if (!tfrc_lh_closed_check(...)) {
| >     // your code from above
| > }
| 
| Okay, i'll add your sugestion. But i don't know how this would be fixed at all.
|
If it doesn't we will just do another iteration and fix it.



| > So it is necessary to decide whether to go the full way, which means
| >  * support Loss Intervals and Dropped Packets alike
| >  * modify TFRC library (it will be a redesign)
| >  * modify receiver code
| >  * modify sender code,
| >    or to use the present approach where
| >  * the receiver computes the Loss Rate and
| >  * a Mandatory Send Loss Event Rate feature is present during feature
| >    negotiation, to avoid problems with incompatible senders
| >   (there is a comment explaining this, in net/dccp/feat.c).
| >
| > Thoughts?
| 
<snip>

| I believe that the first way is better (to "support Loss Intervals and
| Dropped Packets alike..."), because RFC requires loss intervals option
| to be sent. And so, proceed and implement dropped packets option for
| TFRC-SP. You are right, this would need a redesign and rewrite of
| sender and receiver code.
| 
Agree, then let's do that. It requires some coordination on how to arrange
the patches, but we can simplify the process by using the test tree to 
store all intermediate results (i.e. use a separate tree for the rewrite
until it is sufficiently stable/useful).
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html