[PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828

[PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828

[Ivo Calado]

Implement TFRC-SP calc of mean length of loss intervals accordingly to
section 3 of RFC 4828

Changes:
- Modify tfrc_sp_lh_calc_i_mean header, now receiving the current ccval,
so it can determine
   if a loss interval is too recent
- Consider number of losses in each loss interval
- Only consider open loss interval if it is at least 2 rtt old
- Changes function signatures as necessary

Signed-off-by: Ivo Calado, Erivaldo Xavier, Leandro Sales
<ivocalado@embedded.ufcg.edu.br>, <desadoc@gmail.com>,
<leandroal@gmail.com>

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 23:00:24.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.c 2009-09-03
23:00:31.000000000 -0300
@@ -67,10 +67,11 @@
}
}

-static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh)
+static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8
curr_ccval)
{
u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
+ u32 losses;

if (k <= 0)
return;
@@ -78,6 +79,15 @@
for (i = 0; i <= k; i++) {
i_i = tfrc_lh_get_interval(lh, i);

+ if (SUB16(curr_ccval,
+     tfrc_lh_get_loss_interval(lh, i)->li_ccval) <= 8) {
+
+ losses = tfrc_lh_get_loss_interval(lh, i)->li_losses;
+
+ if (losses > 0)
+ i_i = div64_u64(i_i, losses);
+ }
+
if (i < k) {
i_tot0 += i_i * tfrc_lh_weights[i];
w_tot  += tfrc_lh_weights[i];
@@ -87,6 +97,11 @@
}

lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+ BUG_ON(w_tot == 0);
+ if (SUB16(curr_ccval, tfrc_lh_get_loss_interval(lh, 0)->li_ccval) > 8)
+ lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+ else
+ lh->i_mean = i_tot1 / w_tot;
}

/**
@@ -127,7 +142,7 @@
return;

cur->li_length = len;
- tfrc_sp_lh_calc_i_mean(lh);
+ tfrc_sp_lh_calc_i_mean(lh, dccp_hdr(skb)->dccph_ccval);
}

/* RFC 4342, 10.2: test for the existence of packet with sequence number
S */
@@ -148,7 +163,8 @@
bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *lh,
     struct tfrc_rx_hist *rh,
     u32 (*calc_first_li)(struct sock *),
-      struct sock *sk)
+      struct sock *sk,
+      __u8 ccval)
{
struct tfrc_loss_interval *cur = tfrc_lh_peek(lh);
struct tfrc_rx_hist_entry *cong_evt;
@@ -217,7 +233,7 @@
if (lh->counter > (2*LIH_SIZE))
lh->counter -= LIH_SIZE;

- tfrc_sp_lh_calc_i_mean(lh);
+ tfrc_sp_lh_calc_i_mean(lh, ccval);
}

return true;
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 23:00:24.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/loss_interval_sp.h 2009-09-03
23:00:31.000000000 -0300
@@ -73,7 +73,8 @@
extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *,
    struct tfrc_rx_hist *,
    u32 (*first_li)(struct sock *),
-     struct sock *);
+     struct sock *,
+     __u8 ccval);
extern void tfrc_sp_lh_update_i_mean(struct tfrc_loss_hist *lh,
     struct sk_buff *);
extern void tfrc_sp_lh_cleanup(struct tfrc_loss_hist *lh);
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 23:00:24.000000000 -0300
+++ dccp_tree_work4/net/dccp/ccids/lib/packet_history_sp.c 2009-09-03
23:00:31.000000000 -0300
@@ -369,7 +369,8 @@
/*
* Update Loss Interval database and recycle RX records
*/
- new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+ new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
+ dccp_hdr(skb)->dccph_ccval);
__three_after_loss(h);

} else if (dccp_data_packet(skb) && dccp_skb_is_ecn_ce(skb)) {
@@ -378,7 +379,8 @@
* the RFC considers ECN marks - a future implementation may
* find it useful to also check ECN marks on non-data packets.
*/
- new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+ new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
+ dccp_hdr(skb)->dccph_ccval);
/*
* Also combinations of loss and ECN-marks (as per the warning)
* are not supported. The permutations of loss combined with or

[PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828

[Ivo Calado]

Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828

Changes:
 - Modify tfrc_sp_lh_calc_i_mean header, now receiving the current ccval, so it can determine
   if a loss interval is too recent
 - Consider number of losses in each loss interval
 - Only consider open loss interval if it is at least 2 rtt old
 - Changes function signatures as necessary

Signed-off-by: Ivo Calado, Erivaldo Xavier, Leandro Sales <ivocalado@embedded.ufcg.edu.br>, <desadoc@gmail.com>, <leandroal@gmail.com>

Index: dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.c
===================================================================
--- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.c	2009-09-08 10:37:16.000000000 -0300
+++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.c	2009-09-08 10:42:30.000000000 -0300
@@ -67,10 +67,11 @@
 		}
 }
 
-static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh)
+static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8 curr_ccval)
 {
 	u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
 	int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
+	u32 losses;
 
 	if (k <= 0)
 		return;
@@ -78,6 +79,15 @@
 	for (i = 0; i <= k; i++) {
 		i_i = tfrc_lh_get_interval(lh, i);
 
+		if (SUB16(curr_ccval,
+		    tfrc_lh_get_loss_interval(lh, i)->li_ccval) <= 8) {
+
+			losses = tfrc_lh_get_loss_interval(lh, i)->li_losses;
+
+			if (losses > 0)
+				i_i = div64_u64(i_i, losses);
+		}
+
 		if (i < k) {
 			i_tot0 += i_i * tfrc_lh_weights[i];
 			w_tot  += tfrc_lh_weights[i];
@@ -87,6 +97,11 @@
 	}
 
 	lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+	BUG_ON(w_tot == 0);
+	if (SUB16(curr_ccval, tfrc_lh_get_loss_interval(lh, 0)->li_ccval) > 8)
+		lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+	else
+		lh->i_mean = i_tot1 / w_tot;
 }
 
 /*
@@ -127,7 +142,7 @@
 		return;
 
 	cur->li_length = len;
-	tfrc_sp_lh_calc_i_mean(lh);
+	tfrc_sp_lh_calc_i_mean(lh, dccp_hdr(skb)->dccph_ccval);
 }
 
 /* RFC 4342, 10.2: test for the existence of packet with sequence number S */
@@ -148,7 +163,8 @@
 bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *lh,
 			     struct tfrc_rx_hist *rh,
 			     u32 (*calc_first_li)(struct sock *),
-			     struct sock *sk)
+			     struct sock *sk,
+			     __u8 ccval)
 {
 	struct tfrc_loss_interval *cur = tfrc_lh_peek(lh);
 	struct tfrc_rx_hist_entry *cong_evt;
@@ -217,7 +233,7 @@
 		if (lh->counter > (2*LIH_SIZE))
 			lh->counter -= LIH_SIZE;
 
-		tfrc_sp_lh_calc_i_mean(lh);
+		tfrc_sp_lh_calc_i_mean(lh, ccval);
 	}
 
 	return true;
Index: dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.h
===================================================================
--- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.h	2009-09-08 10:37:16.000000000 -0300
+++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.h	2009-09-08 10:42:30.000000000 -0300
@@ -73,7 +73,8 @@
 extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *,
 				    struct tfrc_rx_hist *,
 				    u32 (*first_li)(struct sock *),
-				    struct sock *);
+				    struct sock *,
+				    __u8 ccval);
 extern void tfrc_sp_lh_update_i_mean(struct tfrc_loss_hist *lh,
 				     struct sk_buff *);
 extern void tfrc_sp_lh_cleanup(struct tfrc_loss_hist *lh);
Index: dccp_tree_work5/net/dccp/ccids/lib/packet_history_sp.c
===================================================================
--- dccp_tree_work5.orig/net/dccp/ccids/lib/packet_history_sp.c	2009-09-08 10:37:16.000000000 -0300
+++ dccp_tree_work5/net/dccp/ccids/lib/packet_history_sp.c	2009-09-08 10:42:30.000000000 -0300
@@ -369,7 +369,8 @@
 		/*
 		* Update Loss Interval database and recycle RX records
 		*/
-		new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+		new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
+						dccp_hdr(skb)->dccph_ccval);
 		__three_after_loss(h);
 
 	} else if (dccp_data_packet(skb) && dccp_skb_is_ecn_ce(skb)) {
@@ -378,7 +379,8 @@
 		* the RFC considers ECN marks - a future implementation may
 		* find it useful to also check ECN marks on non-data packets.
 		*/
-		new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+		new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
+						dccp_hdr(skb)->dccph_ccval);
 		/*
 		* Also combinations of loss and ECN-marks (as per the warning)
 		* are not supported. The permutations of loss combined with or

Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828

[Gerrit Renker]

| Implement TFRC-SP calc of mean length of loss intervals accordingly to
| section 3 of RFC 4828
Sorry this also has problems.

--- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.c
+++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.c
@@ -67,10 +67,11 @@
 		}
 }
 
-static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh)
+static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8 curr_ccval)
 {
 	u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
 	int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
+	u32 losses;
 
 	if (k <= 0)
 		return;
@@ -78,6 +79,15 @@
 	for (i = 0; i <= k; i++) {
 		i_i = tfrc_lh_get_interval(lh, i);
 
+		if (SUB16(curr_ccval,
+		    tfrc_lh_get_loss_interval(lh, i)->li_ccval) <= 8) {
+
+			losses = tfrc_lh_get_loss_interval(lh, i)->li_losses;
+
+			if (losses > 0)
+				i_i = div64_u64(i_i, losses);
+		}
+
(Both 'i_i' and 'losses' are u32, so could write "i_i /= losses" instead.)

However, this computation is done in the wrong place: here it is already too
late. The N/K in RFC 4828 refers to entering each individual interval I_0, so
the division (and the check whether this is a "short" interval) needs to be
done when adding the interval, in tfrc_sp_lh_interval_add(). (There also exists
a special rule for the open interval I_0, see RFC 5348, 5.3.)

A second problem is a divide-by-zero condition encoded in the above: if
i_i < losses, the result is 0, if all intervals are 0 then I_mean = 0, and
thus p = 1/I_mean triggers a panic. In all other cases, the integer arithmetic
has the effect of floor(N/K), i.e. it decreases the interval length.

A way out (which does not fix the truncation problem) is to round up:

	if (losses > 0)
		i_i = DIV_ROUND_UP(i_i, losses);

In fact, we have to do this, to avoid the divide-by-zero condition.

The third problem is that the CCVal can be wrong, i.e. "less than 8" can
also mean that it just wrapped around one or more times. But this is noted
already in RFC 5622, it is a problem of the specification.

@@ -87,6 +97,11 @@
 	}
 
 	lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+	BUG_ON(w_tot == 0);
+	if (SUB16(curr_ccval, tfrc_lh_get_loss_interval(lh, 0)->li_ccval) > 8)
+		lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+	else
+		lh->i_mean = i_tot1 / w_tot;
 }
The line above the BUG_ON is probably a leftover. For the BUG_ON, this would
be too late (division by zero). 
In fact, the BUG_ON is not needed, due to testing for k <= 0, see
http://mirror.celinuxforum.org/gitstat//commit-detail.php?commit=eff253c4272cd2aac95ccff46d3d2e1a495f22b1

@@ -127,7 +142,7 @@
 		return;
 
 	cur->li_length = len;
-	tfrc_sp_lh_calc_i_mean(lh);
+	tfrc_sp_lh_calc_i_mean(lh, dccp_hdr(skb)->dccph_ccval);
 }
Should be division as per above.

--- dccp_tree_work5.orig/net/dccp/ccids/lib/loss_interval_sp.h
+++ dccp_tree_work5/net/dccp/ccids/lib/loss_interval_sp.h
@@ -73,7 +73,8 @@
 extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *,
 				    struct tfrc_rx_hist *,
 				    u32 (*first_li)(struct sock *),
-				    struct sock *);
+				    struct sock *,
+				    __u8 ccval);
This function already has the ccval available, so could use it instead
of just passing it through.

[PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828

[Ivo Calado]

Implement TFRC-SP calc of mean length of loss intervals accordingly to
section 3 of RFC 4828

Changes:
 - Modify tfrc_sp_lh_calc_i_mean header, now receiving the current
ccval, so it can determine
  if a loss interval is too recent
 - Consider number of losses in each loss interval
 - Only consider open loss interval if it is at least 2 rtt old
 - Changes function signatures as necessary

Signed-off-by: Ivo Calado, Erivaldo Xavier, Leandro Sales
<ivocalado@embedded.ufcg.edu.br>, <desadoc@gmail.com>,
<leandroal@gmail.com>

Index: b/net/dccp/ccids/lib/loss_interval_sp.c
===================================================================
--- a/net/dccp/ccids/lib/loss_interval_sp.c     2009-08-26
23:28:27.000000000 -0300
+++ b/net/dccp/ccids/lib/loss_interval_sp.c     2009-08-26
23:53:32.000000000 -0300
@@ -66,10 +66,11 @@
               }
 }

-static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh)
+static void tfrc_sp_lh_calc_i_mean(struct tfrc_loss_hist *lh, __u8 curr_ccval)
 {
       u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
       int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */
+       u32 losses;

       if (k <= 0)
               return;
@@ -77,6 +78,14 @@
       for (i = 0; i <= k; i++) {
               i_i = tfrc_lh_get_interval(lh, i);

+               if (SUB16(curr_ccval,
tfrc_lh_get_loss_interval(lh,i)->li_ccval) <= 8)
+               {
+                       losses = tfrc_lh_get_loss_interval(lh,i)->li_losses;
+
+                       if (losses > 0)
+                               i_i = div64_u64(i_i, losses);
+               }
+
               if (i < k) {
                       i_tot0 += i_i * tfrc_lh_weights[i];
                       w_tot  += tfrc_lh_weights[i];
@@ -86,6 +95,12 @@
       }

       lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+       BUG_ON(w_tot == 0);
+       if (SUB16(curr_ccval, tfrc_lh_get_loss_interval(lh,0)->li_ccval) > 8) {
+               lh->i_mean = max(i_tot0, i_tot1) / w_tot;
+       } else {
+               lh->i_mean = i_tot1 / w_tot;
+       }
 }

 /**
@@ -126,7 +141,7 @@
               return;

       cur->li_length = len;
-       tfrc_sp_lh_calc_i_mean(lh);
+       tfrc_sp_lh_calc_i_mean(lh, dccp_hdr(skb)->dccph_ccval);
 }

 /* RFC 4342, 10.2: test for the existence of packet with sequence number S */
@@ -145,7 +160,7 @@
 * Updates I_mean and returns 1 if a new interval has in fact been
added to @lh.
 */
 bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *lh, struct
tfrc_rx_hist *rh,
-                            u32 (*calc_first_li)(struct sock *),
struct sock *sk)
+                            u32 (*calc_first_li)(struct sock *),
struct sock *sk, __u8 ccval)
 {
       struct tfrc_loss_interval *cur = tfrc_lh_peek(lh);
       struct tfrc_rx_hist_entry *cong_evt;
@@ -214,7 +229,7 @@
               if (lh->counter > (2*LIH_SIZE))
                       lh->counter -= LIH_SIZE;

-               tfrc_sp_lh_calc_i_mean(lh);
+               tfrc_sp_lh_calc_i_mean(lh, ccval);
       }

       return true;
Index: b/net/dccp/ccids/lib/loss_interval_sp.h
===================================================================
--- a/net/dccp/ccids/lib/loss_interval_sp.h     2009-08-26
22:52:20.000000000 -0300
+++ b/net/dccp/ccids/lib/loss_interval_sp.h     2009-08-26
23:44:20.000000000 -0300
@@ -71,7 +71,7 @@
 #endif

 extern bool tfrc_sp_lh_interval_add(struct tfrc_loss_hist *, struct
tfrc_rx_hist *,
-                                   u32 (*first_li)(struct sock *),
struct sock *);
+                                   u32 (*first_li)(struct sock *),
struct sock *, __u8 ccval);
 extern void tfrc_sp_lh_update_i_mean(struct tfrc_loss_hist *lh,
struct sk_buff *);
 extern void tfrc_sp_lh_cleanup(struct tfrc_loss_hist *lh);

Index: b/net/dccp/ccids/lib/packet_history_sp.c
===================================================================
--- a/net/dccp/ccids/lib/packet_history_sp.c    2009-08-26
22:55:01.000000000 -0300
+++ b/net/dccp/ccids/lib/packet_history_sp.c    2009-08-26
23:49:59.000000000 -0300
@@ -359,7 +359,7 @@
               /*
               * Update Loss Interval database and recycle RX records
               */
-               new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+               new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
dccp_hdr(skb)->dccph_ccval);
               __three_after_loss(h);

       } else if (dccp_data_packet(skb) && dccp_skb_is_ecn_ce(skb)) {
@@ -368,7 +368,7 @@
               * the RFC considers ECN marks - a future implementation may
               * find it useful to also check ECN marks on non-data packets.
               */
-               new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk);
+               new_event = tfrc_sp_lh_interval_add(lh, h, first_li, sk,
dccp_hdr(skb)->dccph_ccval);
               /*
               * Also combinations of loss and ECN-marks (as per the warning)
               * are not supported. The permutations of loss combined with or