* [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828
@ 2009-09-02 2:45 ` Ivo Calado
0 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-02 2:45 UTC (permalink / raw)
To: dccp; +Cc: netdev
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
^ permalink raw reply [flat|nested] 10+ messages in thread* [PATCH 3/5] Implement TFRC-SP calc of mean length of loss
@ 2009-09-04 12:25 ` Ivo Calado
0 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-04 12:25 UTC (permalink / raw)
To: dccp
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
^ permalink raw reply [flat|nested] 10+ messages in thread* [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828
@ 2009-09-04 12:25 ` Ivo Calado
0 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-04 12:25 UTC (permalink / raw)
To: dccp; +Cc: netdev
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals,
@ 2009-09-08 18:28 ` Ivo Calado
0 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-08 18:28 UTC (permalink / raw)
To: dccp
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
^ permalink raw reply [flat|nested] 10+ messages in thread* [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828
@ 2009-09-08 18:28 ` Ivo Calado
0 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-08 18:28 UTC (permalink / raw)
To: dccp; +Cc: netdev
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss
2009-09-08 18:28 ` [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828 Ivo Calado
@ 2009-09-13 17:28 ` Gerrit Renker
-1 siblings, 0 replies; 10+ messages in thread
From: Gerrit Renker @ 2009-09-13 17:28 UTC (permalink / raw)
To: dccp
| 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ïf253c4272cd2aac95ccff46d3d2e1a495f22b1
@@ -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.
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals, accordingly to section 3 of RFC 4828
@ 2009-09-13 17:28 ` Gerrit Renker
0 siblings, 0 replies; 10+ messages in thread
From: Gerrit Renker @ 2009-09-13 17:28 UTC (permalink / raw)
To: Ivo Calado; +Cc: dccp, netdev
| 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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss
2009-09-02 2:45 ` [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828 Ivo Calado
` (3 preceding siblings ...)
(?)
@ 2009-09-15 0:39 ` Ivo Calado
-1 siblings, 0 replies; 10+ messages in thread
From: Ivo Calado @ 2009-09-15 0:39 UTC (permalink / raw)
To: dccp
The comments follow below
On Sun, Sep 13, 2009 at 14:28, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> | 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.)
>
Oh, all right. I understood it was wrong. I thought that the loss
interval needed to be less than 2 rtt old
but the correct is that it needs to be less than 2 rtt long, right?
> 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.
When the loss count (losses) could be greater than loss interval length (i_i)?
>
> 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ïf253c4272cd2aac95ccff46d3d2e1a495f22b1
>
> @@ -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.
>
Thanks for observing these points!
--
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.
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [PATCH 3/5] Implement TFRC-SP calc of mean length of loss
2009-09-02 2:45 ` [PATCH 3/5] Implement TFRC-SP calc of mean length of loss intervals accordingly to section 3 of RFC 4828 Ivo Calado
` (4 preceding siblings ...)
(?)
@ 2009-09-19 12:23 ` gerrit
-1 siblings, 0 replies; 10+ messages in thread
From: gerrit @ 2009-09-19 12:23 UTC (permalink / raw)
To: dccp
>> 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.)
>>
>
>
> Oh, all right. I understood it was wrong. I thought that the loss
> interval needed to be less than 2 rtt old
> but the correct is that it needs to be less than 2 rtt long, right?
>
I think we need to continue this in the other thread: if there is agreement
to keep the CCID-4 implementation receiver-based (i.e. the receiver computes
the Loss Event Rate), then the struct can be extended to record also the
number of lost packets. Depending on whether CCID-3 (TFRC) or CCID-4
(TFRC-SP) is in use, it would then use the division.
>> 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.
>
>
> When the loss count (losses) could be greater than loss interval length
> (i_i)?
Excellent point, you are fully right, it is in the spec. (RFC 5622,8.7):
By definition, this number MUST NOT exceed the corresponding loss
interval's Loss Length.
To be on the safe side, I think it would be good to catch the case when
this rule is violated, e.g.
WARN_ON(losses > i_i);
if (losses < i_i)
// some smart solution taking care of the truncation problem
^ permalink raw reply [flat|nested] 10+ messages in thread