Skip to contentSkip to conversation

Implement loss counting on TFRC-SP receiver

PATCH Superseded Ivo Calado 3 participants 11 messages Sep 8, 2009 – Nov 6, 2009 1 message not in the archive

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Ivo Calado

author
#0 lore raw

PATCH 2/5 Implement loss counting on TFRC-SP receiver

Implement loss counting on TFRC-SP receiver. Consider transmission's hole size as loss count.

Changes:
- Adds field li_losses to tfrc_loss_interval to track loss count per interval
- Adds field num_losses to tfrc_rx_hist, used to store loss count per loss event
- Adds dccp_loss_count function to net/dccp/dccp.h, responsible for loss count using sequence numbers

Index: dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.c
=================================--- dccp_tree_work4.orig/net/dccp/ccids/lib/loss_interval_sp.c 2009-09-03 22:58:17.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.c 2009-09-03 23:00:24.000000000 -0300
@@ -187,6 +187,7 @@
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;
}

@@ -204,6 +205,7 @@
cur->li_seqno = cong_evt_seqno;
cur->li_ccval = cong_evt->tfrchrx_ccval;
cur->li_is_closed = false;
+ cur->li_losses = rh->num_losses;

if (++lh->counter = 1)
lh->i_mean = cur->li_length = (*calc_first_li)(sk);
Index: dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.h
=================================--- dccp_tree_work4.orig/net/dccp/ccids/lib/loss_interval_sp.h 2009-09-03 22:58:17.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.h 2009-09-03 23:00:24.000000000 -0300
@@ -30,12 +30,14 @@

  *  @li_ccval:		The CCVal belonging to @li_seqno
  *  @li_is_closed:	Whether @li_seqno is older than 1 RTT
  *  @li_length:		Loss interval sequence length
+ *  @li_losses: 	Number of losses counted on this interval

*/
struct tfrc_loss_interval {
u64 li_seqno:48,
li_ccval:4,
li_is_closed:1;
u32 li_length;
+ u32 li_losses;
};

/*
Index: dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c
=================================--- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c 2009-09-03 22:58:17.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c 2009-09-03 23:00:24.000000000 -0300
@@ -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;
}

@@ -257,6 +258,7 @@
tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2),
skb, n3);
h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s1, s3, n3);
return 1;
}

@@ -293,6 +295,7 @@
h->loss_start = tfrc_rx_hist_index(h, 3); tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s0, s3, n3);

return 1;
}
Index: dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.h
=================================--- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.h 2009-09-03 22:58:17.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.h 2009-09-03 22:58:29.000000000 -0300
@@ -113,6 +113,7 @@
u32 packet_size,
bytes_recvd;
ktime_t bytes_start;
+ u8 num_losses;
};

/*
Index: dccp_tree_work4/net/dccp/dccp.h
=================================--- dccp_tree_work4.orig/net/dccp/dccp.h 2009-09-03 22:58:17.000000000 -0300
+++ dccp_tree_work4/net/dccp/dccp.h 2009-09-03 22:58:29.000000000 -0300
@@ -168,6 +168,21 @@
return (u64)delta <= ndp + 1;
}

+static inline u64 dccp_loss_count(const u64 s1, const u64 s2, const u64 ndp) +{
+ s64 delta, count;
+
+ delta = dccp_delta_seqno(s1, s2);
+ WARN_ON(delta < 0);
+
+ count = ndp + 1;
+ count -= delta;
+
+ count = (count > 0) ? count : 0;
+
+ return (u64) count;
+}
+
enum {
DCCP_MIB_NUM = 0,
DCCP_MIB_ACTIVEOPENS, /* ActiveOpens */

#1 lore raw

| 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.

net/dccp/ccids/lib/loss_interval_sp.c +1 -0
@@ -187,6 +187,7 @@
 		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.

net/dccp/ccids/lib/packet_history_sp.c +1 -0
@@ -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

@@ -257,6 +258,7 @@
tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2),
skb, n3);
h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s1, s3, n3);
return 1;
}
In this case, the "hole" is between s0 and s2, it is case VI(d) in the above.

@@ -293,6 +295,7 @@
h->loss_start = tfrc_rx_hist_index(h, 3); tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s0, s3, n3);

return 1;
}
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.

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.

net/dccp/ccids/lib/packet_history_sp.h +1 -0
@@ -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.

net/dccp/dccp.h +14 -0
@@ -168,6 +168,21 @@
 	return (u64)delta <= ndp + 1;
 }
 
+static inline u64 dccp_loss_count(const u64 s1, const u64 s2, const u64 ndp)
+{
+	s64 delta, count;
+
+	delta = dccp_delta_seqno(s1, s2);
+	WARN_ON(delta < 0);
+
+	count = ndp + 1;
+	count -= delta;
+
+	count = (count > 0) ? count : 0;
+
+	return (u64) count;
+}

Let S_A, S_B be sequence numbers such that S_B is "after" S_A, and let N_B be the NDP count of packet S_B. Then, using module-2^48 arithmetic,
D = S_B - S_A - 1 is an upper bound of the number of lost data packets,
D - N_B is an approximation of the number of lost data
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.

author
#2 lore raw

In the same way, my comments follow below

Quoted 12 lines

               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?

Quoted 15 lines
net/dccp/ccids/lib/packet_history_sp.c +1 -0
@@ -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>

Quoted 7 lines

 }
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

Quoted 7 lines

 * 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?

Quoted 5 lines

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.

Quoted 9 lines
net/dccp/ccids/lib/packet_history_sp.h +1 -0
@@ -113,6 +113,7 @@
        u32                       packet_size,
                                  bytes_recvd;
        ktime_t                   bytes_start;
+       u8                        num_losses;
  };
Quoted 3 lines

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.

Quoted 5 lines
net/dccp/dccp.h +0 -0
@@ -168,6 +168,21 @@
        return (u64)delta <= ndp + 1;

<snip>

Quoted 8 lines

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!

Signature · 9 lines
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab - http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center - http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Quidquid latine dictum sit, altum viditur.
#3 lore raw
Quoted 9 lines
Quoted 9 lines

               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

Quoted 1 line
Quoted 1 line

each time the condition is evaluated. E.g. if 3 times in a row

reordered

Quoted 2 lines
Quoted 2 lines

(earlier)
sequence numbers arrive, or if the CCvals do not differ (high-speed

networks),

Quoted 7 lines
Quoted 1 line

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)))

{

Quoted 7 lines
net/dccp/ccids/lib/loss_interval_sp.c +2 -0
+                       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.

Quoted 1 line
Quoted 1 line

--- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c +++

dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c

Quoted 3 lines

net/dccp/ccids/lib/packet_history_sp.c line 245

Quoted 3 lines
net/dccp/ccids/lib/packet_history_sp.c +0 -0
@@ -244,6 +244,7 @@
                h->loss_count = 3;
                tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3),

                                              skb, n3);

Quoted 5 lines
Quoted 5 lines
net/dccp/ccids/lib/packet_history_sp.c +1 -0
+               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

Quoted 7 lines
Quoted 2 lines

http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\
ccid3/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt

<snip>

Quoted 2 lines

 }
Here it is also between s0 and s2, not between s0 and s3. It is case

VI(c.3).

Quoted 1 line
Quoted 1 line

However, the above still is a crude approximation, since it only

measures between

Quoted 1 line
Quoted 1 line

the last sequence number received before the loss and the third

sequence

Quoted 3 lines
Quoted 3 lines

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

Quoted 1 line
Quoted 1 line

 * check if there are more holes between the first/second and the

second/third

Quoted 2 lines
Quoted 2 lines

  sequence numbers after the loss.
The second option would be the correct one, it should also take the NDP

counts

Quoted 1 line
Quoted 1 line

of each gap into account. And already we have a fairly complicated

algorithm.

Quoted 4 lines

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:

Quoted 1 line

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?

Quoted 1 line

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?

A message that is not in the archive (sent off-list or not yet received): [email protected]

author
#5 lore raw
Quoted 49 lines · On Sat, Sep 19, 2009 at 9:11 AM,  <[email protected]> wrote:
Quoted 9 lines
Quoted 9 lines

               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

Quoted 1 line
Quoted 1 line

each time the condition is evaluated. E.g. if 3 times in a row

reordered

Quoted 2 lines
Quoted 2 lines

(earlier)
sequence numbers arrive, or if the CCvals do not differ (high-speed

networks),

Quoted 7 lines
Quoted 1 line

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)))

{

Quoted 7 lines

+                       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

Quoted 8 lines

   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.

Quoted 7 lines

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.

Quoted 44 lines
Quoted 1 line
Quoted 1 line

--- dccp_tree_work4.orig/net/dccp/ccids/lib/packet_history_sp.c +++

dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c

Quoted 3 lines

net/dccp/ccids/lib/packet_history_sp.c line 245

Quoted 3 lines
net/dccp/ccids/lib/packet_history_sp.c +0 -0
@@ -244,6 +244,7 @@
                h->loss_count = 3;
                tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3),

                                              skb, n3);

Quoted 5 lines
Quoted 5 lines
net/dccp/ccids/lib/packet_history_sp.c +1 -0
+               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

Quoted 7 lines
Quoted 2 lines

http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/\
ccid3/ccid3_packet_reception/loss_detection/loss_detection_algorithm_notes.txt

<snip>

Quoted 2 lines

 }
Here it is also between s0 and s2, not between s0 and s3. It is case

VI(c.3).

Quoted 1 line
Quoted 1 line

However, the above still is a crude approximation, since it only

measures between

Quoted 1 line
Quoted 1 line

the last sequence number received before the loss and the third

sequence

Quoted 3 lines
Quoted 3 lines

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

Quoted 1 line
Quoted 1 line

 * check if there are more holes between the first/second and the

second/third

Quoted 2 lines
Quoted 2 lines

  sequence numbers after the loss.
The second option would be the correct one, it should also take the NDP

counts

Quoted 1 line
Quoted 1 line

of each gap into account. And already we have a fairly complicated

algorithm.

Quoted 4 lines

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:

Quoted 1 line

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?

Quoted 7 lines
Quoted 1 line

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.

Quoted 23 lines

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).

Quoted 2 lines

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.

Signature · 9 lines
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab - http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center - http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Quidquid latine dictum sit, altum viditur.
#6 lore raw
| >> 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).

author
#7 lore raw

PATCH v2 2/4 Implement loss counting on TFRC-SP receiver

Implement loss counting on TFRC-SP receiver. Consider transmission's hole size as loss count.

Changes:
- Adds field li_losses to tfrc_loss_interval to track loss count per interval
- Adds field num_losses to tfrc_rx_hist, used to store loss count per loss event
- Adds dccp_loss_count function to net/dccp/dccp.h, responsible for loss count using sequence numbers

Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c
=================================--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.c 2009-10-08 22:54:16.819408361 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.c 2009-10-08 22:59:07.439908552 -0300
@@ -183,8 +183,11 @@
if (len <= 0)
return false;

- if (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval))
+ if (!tfrc_lh_closed_check(cur, cong_evt->tfrchrx_ccval)) {
+ cur->li_losses += rh->num_losses;
+ rh->num_losses = 0;
return false;
+ }

/* RFC 5348, 5.3: length between subsequent intervals */ cur->li_length = len;
@@ -200,6 +203,8 @@
cur->li_seqno = cong_evt_seqno;
cur->li_ccval = cong_evt->tfrchrx_ccval;
cur->li_is_closed = false;
+ cur->li_losses = rh->num_losses;
+ rh->num_losses = 0;

if (++lh->counter = 1)
lh->i_mean = cur->li_length = (*calc_first_li)(sk);
Index: dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h
=================================--- dccp_tree_work03.orig/net/dccp/ccids/lib/loss_interval_sp.h 2009-10-08 22:54:16.838907787 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/loss_interval_sp.h 2009-10-08 22:59:07.439908552 -0300
@@ -30,12 +30,14 @@

  *  @li_ccval:		The CCVal belonging to @li_seqno
  *  @li_is_closed:	Whether @li_seqno is older than 1 RTT
  *  @li_length:		Loss interval sequence length
+ *  @li_losses:        Number of losses counted on this interval

*/
struct tfrc_loss_interval {
u64 li_seqno:48,
li_ccval:4,
li_is_closed:1;
u32 li_length;
+ u32 li_losses;
};

/**
Index: dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.h
=================================--- dccp_tree_work03.orig/net/dccp/ccids/lib/packet_history_sp.h 2009-10-08 22:58:53.134907870 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.h 2009-10-08 22:59:07.439908552 -0300
@@ -104,6 +104,7 @@
* @packet_size: Packet size in bytes (as per RFC 3448, 3.1)
* @bytes_recvd: Number of bytes received since @bytes_start
* @bytes_start: Start time for counting @bytes_recvd
+ * @num_losses: Number of losses detected
*/
struct tfrc_rx_hist {
struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1];
@@ -116,6 +117,7 @@
u32 packet_size,
bytes_recvd;
ktime_t bytes_start;
+ u64 num_losses;
};

/**
Index: dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.c
=================================--- dccp_tree_work03.orig/net/dccp/ccids/lib/packet_history_sp.c 2009-10-08 22:58:21.418908270 -0300
+++ dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.c 2009-10-08 22:59:07.442411383 -0300
@@ -243,6 +243,7 @@
{
u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,
s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,
+ n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp,
s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, s3 = DCCP_SKB_CB(skb)->dccpd_seq;

@@ -250,6 +251,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(s0, s1, n1);
return 1;
}

@@ -263,6 +265,7 @@
tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2),
skb, n3);
h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s0, s1, n1);
return 1;
}

@@ -299,6 +302,7 @@
h->loss_start = tfrc_rx_hist_index(h, 3); tfrc_sp_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); h->loss_count = 3;
+ h->num_losses = dccp_loss_count(s0, s3, n3);

return 1;
}
Index: dccp_tree_work03/net/dccp/dccp.h
=================================--- dccp_tree_work03.orig/net/dccp/dccp.h 2009-10-08 22:54:16.858907920 -0300
+++ dccp_tree_work03/net/dccp/dccp.h 2009-10-08 22:59:07.442411383 -0300
@@ -154,6 +154,22 @@
}

/**
+ * 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

+ */
+static inline 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;
+}
+
+/**
* dccp_loss_free - Evaluates condition for data loss from RFC 4340, 7.7.1
* @s1: start sequence number
* @s2: end sequence number
@@ -162,10 +178,7 @@
*/
static inline bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp) {
- s64 delta = dccp_delta_seqno(s1, s2);
-
- WARN_ON(delta < 0);
- return (u64)delta <= ndp + 1;
+ return dccp_loss_count(s1, s2, ndp) = 0;
}

enum {

#8 lore raw

dccp-test-tree [PATCH 1/1]: Count lost data packets in a burst loss

dccp: Generalise data-loss condition

This patch is thanks to Ivo Calado who had integrated this function into one of the TFRC-SP patches.

It generalises the task of determining data loss from RFC 43430, 7.7.1.

Let S_A, S_B be sequence numbers such that S_B is "after" S_A, and let N_B be the NDP count of packet S_B. Then, using module-2^48 arithmetic,
D = S_B - S_A - 1 is an upper bound of the number of lost data packets,
D - N_B is an approximation of the number of lost data packets
(there are cases where this is not exact).

The patch implements this as
dccp_loss_count(S_A, S_B, N_B) := max(S_B - S_A - 1 - N_B, 0)

---
 net/dccp/dccp.h |   21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
net/dccp/dccp.h +15 -6
@@ -153,18 +153,27 @@ static inline u64 max48(const u64 seq1, 
 }
 
 /**
- * dccp_loss_free  -  Evaluates condition for data loss from RFC 4340, 7.7.1
- * @s1:	 start sequence number
- * @s2:  end sequence number
+ * dccp_loss_count - Approximate the number of lost data packets in a burst loss
+ * @s1:  last known sequence number before the loss ('hole')
+ * @s2:  first sequence number seen after the 'hole'
  * @ndp: NDP count on packet with sequence number @s2
- * Returns true if the sequence range s1...s2 has no data loss.
  */
-static inline bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
+static inline u64 dccp_loss_count(const u64 s1, const u64 s2, const u64 ndp)
 {
 	s64 delta = dccp_delta_seqno(s1, s2);
 
 	WARN_ON(delta < 0);
-	return (u64)delta <= ndp + 1;
+	delta -= ndp + 1;
+
+	return delta > 0 ? delta : 0;
+}
+
+/**
+ * dccp_loss_free - Evaluate condition for data loss from RFC 4340, 7.7.1
+ */
+static inline bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
+{
+	return dccp_loss_count(s1, s2, ndp) = 0;
 }
 
 enum {
author
#9 lore raw

Re: dccp-test-tree [PATCH 1/1]: Count lost data packets in a burst loss

Quoted 48 lines · Gerrit Renker

dccp: Generalise data-loss condition

This patch is thanks to Ivo Calado who had integrated this function into one of the TFRC-SP patches.

It generalises the task of determining data loss from RFC 43430, 7.7.1.

Let S_A, S_B be sequence numbers such that S_B is "after" S_A, and let N_B be the NDP count of packet S_B. Then, using module-2^48 arithmetic, D = S_B - S_A - 1  is an upper bound of the number of lost data packets, D - N_B            is an approximation of the number of lost data packets (there are cases where this is not exact).

The patch implements this as
 dccp_loss_count(S_A, S_B, N_B) := max(S_B - S_A - 1 - N_B, 0)

---
 net/dccp/dccp.h |   21 +++++++++++++++------

 1 file changed, 15 insertions(+), 6 deletions(-)
net/dccp/dccp.h +8 -6
@@ -153,18 +153,27 @@ static inline u64 max48(const u64 seq1,
  }
 
  /**
- * dccp_loss_free  -  Evaluates condition for data loss from RFC 4340, 7.7.1
- * @s1:         start sequence number
- * @s2:  end sequence number
+ * dccp_loss_count - Approximate the number of lost data packets in a burst loss
+ * @s1:  last known sequence number before the loss ('hole')
+ * @s2:  first sequence number seen after the 'hole'
  * @ndp: NDP count on packet with sequence number @s2
- * Returns true if the sequence range s1...s2 has no data loss.
  */
-static inline bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
+static inline u64 dccp_loss_count(const u64 s1, const u64 s2, const u64 ndp)
  {
        s64 delta = dccp_delta_seqno(s1, s2);
 
        WARN_ON(delta < 0);
-       return (u64)delta <= ndp + 1;
+       delta -= ndp + 1;
+
+       return delta > 0 ? delta : 0;
+}

net/dccp/dccp.h static inline u64 max48(const u64 seq1, · line 179

Quoted 10 lines
net/dccp/dccp.h +7 -0
+
+/**
+ * dccp_loss_free - Evaluate condition for data loss from RFC 4340, 7.7.1
+ */
+static inline bool dccp_loss_free(const u64 s1, const u64 s2, const u64 ndp)
+{
+       return dccp_loss_count(s1, s2, ndp) = 0;
  }
 
  enum {

Agree

Signature · 12 lines
Ivo Augusto Andrade Rocha Calado
MSc. Candidate
Embedded Systems and Pervasive Computing Lab - http://embedded.ufcg.edu.br
Systems and Computing Department - http://www.dsc.ufcg.edu.br
Electrical Engineering and Informatics Center - http://www.ceei.ufcg.edu.br
Federal University of Campina Grande - http://www.ufcg.edu.br

PGP: 0x03422935
Putt's Law:
       Technology is dominated by two types of people:
               Those who understand what they do not manage.
               Those who manage what they do not understand.
#10 lore raw
In reply to Ivo Calado
| --- dccp_tree_work03.orig/net/dccp/ccids/lib/packet_history_sp.c	2009-10-08 22:58:21.418908270 -0300
| +++ dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.c	2009-10-08 22:59:07.442411383 -0300
| @@ -243,6 +243,7 @@
|  {
|  	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,
|  	    s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,
| +	    n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp,
|  	    s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno,
|  	    s3 = DCCP_SKB_CB(skb)->dccpd_seq;

I have removed the old definition of n1, which was further below and which caused this warning.

net/dccp/ccids/lib/packet_history_sp.c:276:7: warning: symbol 'n1' shadows an earlier net/dccp/ccids/lib/packet_history_sp.c:247:6: originally declared here

I thought again about the earlier suggestion to make 'num_losses' u64. Since li_losses sums the values stored in num_losses, it needs to have the same size (currently it is u32). But then another thought is that if there are so many losses that u32 overflows, then the performance is so bad anyway that it is better to turn off the receiver. Hence I have reverted it to u32, as per your original patch.

Please find attached a patch of the changes I made. As per posting, I have separated out the dccp.h part, since it is also useful in general.

net/dccp/ccids/lib/packet_history_sp.c +0 -1
@@ -272,7 +272,6 @@ static int __two_after_loss(struct tfrc_
 	/* S0  <  S3  <  S1 */
 
 	if (dccp_loss_free(s0, s3, n3)) {
-		u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp;
 
 		if (dccp_loss_free(s3, s1, n1)) {
 			/* hole between S0 and S1 filled by S3 */
net/dccp/ccids/lib/packet_history_sp.h +1 -1
@@ -117,7 +117,7 @@ struct tfrc_rx_hist {
 	u32			  packet_size,
 				  bytes_recvd;
 	ktime_t			  bytes_start;
-	u64			  num_losses;
+	u32			  num_losses;
 };
 
 /**
net/dccp/ccids/lib/loss_interval_sp.c +2 -1
@@ -203,7 +203,8 @@ bool tfrc_sp_lh_interval_add(struct tfrc
 	cur->li_seqno	  = cong_evt_seqno;
 	cur->li_ccval	  = cong_evt->tfrchrx_ccval;
 	cur->li_is_closed = false;
-	cur->li_losses    = rh->num_losses;
+
+	cur->li_losses = rh->num_losses;
 	rh->num_losses = 0;
 
 	if (++lh->counter == 1)
#11 lore raw

Hi Gerrit,

Quoted 10 lines · Gerrit Renker
| --- dccp_tree_work03.orig/net/dccp/ccids/lib/packet_history_sp.c      2009-10-08 22:58:21.418908270 -0300
| +++ dccp_tree_work03/net/dccp/ccids/lib/packet_history_sp.c   2009-10-08 22:59:07.442411383 -0300
| @@ -243,6 +243,7 @@
|  {
|       u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,
|           s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,
| +         n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp,
|           s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno,
|           s3 = DCCP_SKB_CB(skb)->dccpd_seq;
Quoted 6 lines

I have removed the old definition of n1, which was further below and which caused this warning.

net/dccp/ccids/lib/packet_history_sp.c:276:7: warning: symbol 'n1' shadows an earlier net/dccp/ccids/lib/packet_history_sp.c:247:6: originally declared here

Well done!

Quoted 5 lines

I thought again about the earlier suggestion to make 'num_losses' u64. Since li_losses sums the values stored in num_losses, it needs to have the same size (currently it is u32). But then another thought is that if there are so many losses that u32 overflows, then the performance is so bad anyway that it is better to turn off the receiver. Hence I have reverted it to u32, as per your original patch.

OK

Quoted 2 lines

Please find attached a patch of the changes I made. As per posting, I have separated out the dccp.h part, since it is also useful in general.

OK, agreed!

Thank you,

BR,
Leandro.