: Further CCID-2 clean-ups
Subsystems (2)
A message that is not in the archive (sent off-list or not yet received): ccid2_clean_ups
cover : Further CCID-2 clean-ups
Further CCID-2 work - 3 patches are clean-ups, removing unnecessary bits so that the code becomes clearer. Patch #3 replaces the RTT estimator algorithm - much work has gone into testing, and the TCP RTO estimator has been chosen - not simply because it is easy to copy someone else's code, but because it offers a much better solution, with evidence given.
Patch #1: After finding that the CCID-2 sanity tests are redundant,
they are removed.
Patch #2: Simplifies decrementing the `pipe' variable in CCID-2, also
removing redundancies.
Patch #3: Replaces the partly broken RTT estimator with a better
alternative - reusing the TCP RTT estimator.
Patch #4: Removes wrappers around sk_timer functions, since these
do not add any further functionality / benefit.
All patches have been uploaded - to the end - of the test tree at
git://eden-feed.erg.abdn.ac.uk/dccp_exp [dccp]
PLEASE NOTE - there will be a server outage of this server from
Friday 29th Feb, 12:00 UTC until Monday 3rd Mar, > 12:00 UTC
due to unavoidable brick and construction work in the building.
PATCH 1/4 : Remove redundant sanity tests
This removes the ccid2_hc_tx_check_sanity function: it is redundant.
Details:
====
The tx_check_sanity function performs three tests:
1) it checks that the circular TX list is sorted
- in ascending order of sequence number (ccid2s_seq)
- and time (ccid2s_sent),
- in the direction from tail' (hctx_seqt) to head' (hctx_seqh);
2) it ensures that the entire list has the length seqbufc * CCID2_SEQBUF_LEN;
3) it ensures that ccid2hctx_pipe equals the number of packets that were not marked acked' (ccid2s_acked) between tail' and `head'.
The following argues that each of these tests is redundant, this can be verified by going through the code.
(1) is not necessary, since both time and GSS increase from one packet to the next, so that subsequent insertions in tx_packet_sent (which advance the `head' pointer) will be in ascending order of time and sequence number.
In (2), the length of the list is always equal to seqbufc times CCID2_SEQBUF_LEN (set to 1024) unless allocation caused an earlier failure, because:
* at initialisation (tx_init), there is one chunk of size 1024 and seqbufc=1;
* subsequent calls to tx_alloc_seq take place whenever head->next = tail in tx_packet_sent; then a new chunk of size 1024 is inserted between head and tail, and seqbufc is incremented by one.
To show that (3) is redundant requires looking at two cases.
The `pipe' variable of the TX socket is incremented only in tx_packet_sent, and decremented in tx_packet_recv. When head = tail (TX history empty) then pipe should be 0, which is the case directly after initialisation and after a retransmission timeout has occurred (ccid2_hc_tx_rto_expire).
The first case involves parsing Ack Vectors for packets recorded in the live portion of the buffer, between tail and head. For each packet marked by the receiver as received (state 0) or ECN-marked (state 1), pipe is decremented by one, so for all such packets the BUG_ON in tx_check_sanity will not trigger.
The second case is the loss detection in the second half of tx_packet_recv, below the comment "Check for NUMDUPACK".
The first while-loop here ensures that the sequence number of seqp' is either above or equal to high_ack', or otherwise equal to the highest sequence number sent so far (of the entry head->prev, as head points to the next unsent entry). The next while-loop ("while (1)") counts the number of acked packets starting from that position of seqp, going backwards in the direction from head->prev to tail. If NUMDUPACK=3 such packets were counted within this loop, `seqp' points to the last acknowledged packet of these, and the "if (done = NUMDUPACK)" block is entered next.
The while-loop contained within that block in turn traverses the list backwards, from head to tail; the position of seqp' is saved in the variable last_acked'. For each packet not marked as acked', a congestion event is triggered within the loop, and pipe is decremented. The loop terminates when seqp' has reached tail', whereupon tail is set to the position previously stored in last_acked'. Thus, between last_acked' and the previous position of tail',
- pipe has been decremented earlier if the packet was marked as state 0 or 1;
- pipe was decremented if the packet was not marked as acked.
That is, pipe has been decremented by the number of packets between last_acked' and the previous position of tail'. As a consequence, pipe now again reflects the number of packets which have not (yet) been acked between the new position of tail (at `last_acked') and head->prev, or 0 if head=tail. The result is that the BUG_ON condition in check_sanity will also not be triggered, hence the test
(3) is also redundant.
--- net/dccp/ccids/ccid2.c | 51 ------------------------------------------------ 1 files changed, 0 insertions(+), 51 deletions(-)
net/dccp/ccids/ccid2.c +0 -51
@@ -34,51 +34,8 @@#ifdef CONFIG_IP_DCCP_CCID2_DEBUG static int ccid2_debug; #define ccid2_pr_debug(format, a...) DCCP_PR_DEBUG(ccid2_debug, format, ##a) - -static void ccid2_hc_tx_check_sanity (const struct ccid2_hc_tx_sock *hctx) -{ -int len =0 ; -int pipe =0 ; -struct ccid2_seq *seqp = hctx->ccid2hctx_seqh; - -/* there is data in the chain */ -if (seqp != hctx->ccid2hctx_seqt) { - seqp = seqp->ccid2s_prev; - len++; -if (!seqp->ccid2s_acked) - pipe++; - -while (seqp != hctx->ccid2hctx_seqt) { -struct ccid2_seq *prev = seqp->ccid2s_prev; - - len++; -if (!prev->ccid2s_acked) - pipe++; - -/* packets are sent sequentially */ -BUG_ON (dccp_delta_seqno (seqp->ccid2s_seq, - prev->ccid2s_seq ) >=0 ); -BUG_ON (time_before (seqp->ccid2s_sent, - prev->ccid2s_sent)); - - seqp = prev; - } - } - -BUG_ON (pipe != hctx->ccid2hctx_pipe); -ccid2_pr_debug ("len of chain=%d\n" , len); - -do { - seqp = seqp->ccid2s_prev; - len++; - }while (seqp != hctx->ccid2hctx_seqh); - -ccid2_pr_debug ("total len=%d\n" , len); -BUG_ON (len != hctx->ccid2hctx_seqbufc *CCID2_SEQBUF_LEN ); -}#else #define ccid2_pr_debug(format, a...) -#define ccid2_hc_tx_check_sanity (hctx)#endif static int ccid2_hc_tx_alloc_seq (struct ccid2_hc_tx_sock *hctx)
@@ -178,8 +135,6 @@ static void ccid2_hc_tx_rto_expire(unsigned long data)ccid2_pr_debug ("RTO_EXPIRE\n" ); -ccid2_hc_tx_check_sanity (hctx); -/* back-off timer */ hctx->ccid2hctx_rto <<=1 ;
@@ -202,7 +157,6 @@ static void ccid2_hc_tx_rto_expire(unsigned long data) hctx->ccid2hctx_rpseq =0 ; hctx->ccid2hctx_rpdupack =-1 ;ccid2_change_l_ack_ratio (sk,1 ); -ccid2_hc_tx_check_sanity (hctx);/* if we were blocked before, we may now send cwnd=1 packet */ if (sender_was_blocked)
@@ -317,7 +271,6 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, unsigned int len) } }while (0 );ccid2_pr_debug ("=====\n" ); -ccid2_hc_tx_check_sanity (hctx);#endif }
@@ -467,7 +420,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)int done =0 ;unsigned int maxincr =0 ; -ccid2_hc_tx_check_sanity (hctx);/* check reverse path congestion */ seqno =DCCP_SKB_CB (skb)->dccpd_seq;
@@ -644,7 +596,6 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next; } -ccid2_hc_tx_check_sanity (hctx); done:/* check if incoming Acks allow pending packets to be sent */ if (sender_was_blocked && !ccid2_cwnd_network_limited (hctx))
@@ -685,8 +636,6 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)setup_timer (&hctx->ccid2hctx_rtotimer, ccid2_hc_tx_rto_expire, (unsigned long )sk);INIT_LIST_HEAD (&hctx->ccid2hctx_av_chunks); - -ccid2_hc_tx_check_sanity (hctx);return 0 ; }
PATCH 2/4 : Simplify dec_pipe and rearming of RTO timer
This removes the dec_pipe function and improves the way the RTO timer is rearmed when a new acknowledgment comes in.
Details and justification for removal:
--------------------------------------
1) The BUG_ON in dec_pipe is never triggered: pipe is only decremented for TX history entries between tail and head, for which it had previously been incremented in tx_packet_sent; and it is not decremented twice for the same entry, since it is
- either decremented when a corresponding Ack Vector cell in state 0 or 1 was received (and then ccid2s_acked=1),
- or it is decremented when ccid2s_acked=0, as part of the loss detection in tx_packet_recv (and hence it can not have been decremented earlier).
2) Restarting the RTO timer happens for every single entry in each Ack Vector parsed by tx_packet_recv (according to RFC 4340, 11.4 this can happen up to 16192 times per Ack Vector).
3) The RTO timer should not be restarted when all outstanding data has been acknowledged. This is currently done similar to (2), in dec_pipe, when pipe has reached 0.
The patch onsolidates the code which rearms the RTO timer, combining the segments from new_ack and dec_pipe. As a result, the code becomes clearer (compare with tcp_rearm_rto()).
--- net/dccp/ccids/ccid2.c | 27 ++++++++------------------- 1 files changed, 8 insertions(+), 19 deletions(-)
net/dccp/ccids/ccid2.c +8 -19
@@ -356,23 +356,6 @@ static inline void ccid2_new_ack(struct sock *sk, hctx->ccid2hctx_srtt, hctx->ccid2hctx_rttvar, hctx->ccid2hctx_rto, HZ, r); } - -/* we got a new ack, so re-start RTO timer */ -ccid2_hc_tx_kill_rto_timer (sk); -ccid2_start_rto_timer (sk); -} - -static void ccid2_hc_tx_dec_pipe (struct sock *sk) -{ -struct ccid2_hc_tx_sock *hctx =ccid2_hc_tx_sk (sk); - -if (hctx->ccid2hctx_pipe =0 ) -DCCP_BUG ("pipe = 0" ); -else - hctx->ccid2hctx_pipe--; - -if (hctx->ccid2hctx_pipe =0 ) -ccid2_hc_tx_kill_rto_timer (sk); }static void ccid2_congestion_event (struct sock *sk,struct ccid2_seq *seqp)
@@ -522,7 +505,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) seqp->ccid2s_acked =1 ;ccid2_pr_debug ("Got ack for %llu\n" , (unsigned long long )seqp->ccid2s_seq); -ccid2_hc_tx_dec_pipe (sk); + hctx->ccid2hctx_pipe--; }if (seqp = hctx->ccid2hctx_seqt) { done =1 ;
@@ -578,7 +561,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)* one ack vector. */ ccid2_congestion_event (sk, seqp); -ccid2_hc_tx_dec_pipe (sk); + hctx->ccid2hctx_pipe--; }if (seqp = hctx->ccid2hctx_seqt)break ;
@@ -596,6 +579,12 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next; } +/* restart RTO timer if not all outstanding data has been acked */ +if (hctx->ccid2hctx_pipe =0 ) +sk_stop_timer (sk, &hctx->ccid2hctx_rtotimer); +else +sk_reset_timer (sk, &hctx->ccid2hctx_rtotimer, + jiffies + hctx->ccid2hctx_rto); done:/* check if incoming Acks allow pending packets to be sent */ if (sender_was_blocked && !ccid2_cwnd_network_limited (hctx))
PATCH 3/4 : Replace broken RTT estimator with better algorithm
The current CCID-2 RTT estimator code is in parts broken and lags behind the suggestions in RFC2988 of using scaled variants for SRTT/RTTVAR. That code is replaced by the present patch, which reuses the Linux TCP RTT estimator code - reasons for this code duplication are given below.
Further details:
----------------
1. The minimum RTO of previously one second has been replaced with TCP's, since
RFC4341, sec. 5 says that the minimum of 1 sec. (suggested in RFC2988, 2.4)
is not necessary. Instead, the TCP_RTO_MIN is used, which agrees with DCCP's
concept of a default RTT (RFC 4340, 3.4).
2. The maximum RTO has been set to DCCP_RTO_MAX (64 sec), which agrees with
RFC2988, (2.5). 3. De-inlined the function ccid2_new_ack().
4. Added a FIXME: the RTT is sampled several times per Ack Vector, which will give the wrong estimate. It should be replaced with one sample per Ack. However, at the moment this can not be resolved easily, since
- it depends on TX history code (which also needs some work),
- the cleanest solution is not to use the `sent' time at all (saves 4 bytes per entry) and use DCCP timestamps / elapsed time to estimated the RTT, which however is non-trivial to get right (but needs to be done).
Reasons for reusing the Linux TCP estimator algorithm:
------------------------------------------------------
Some time was spent to find a better alternative, using basic RFC2988 as a first step. Further analysis and experimentation showed that the Linux TCP RTO estimator is superior to a basic RFC2988 implementation. A summary is on
http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid2/rto_estimator/
In addition, this estimator fared well in a recent empirical evaluation:
Rewaskar, Sushant, Jasleen Kaur and F. Donelson Smith. A Performance Study of Loss Detection/Recovery in Real-world TCP Implementations. Proceedings of 15th IEEE International Conference on Network Protocols (ICNP-07). 2007.
Thus there is significant benefit in reusing the existing TCP code.
--- net/dccp/ccids/ccid2.c | 168 ++++++++++++++++++++++++++--------------------- net/dccp/ccids/ccid2.h | 20 ++++-- 2 files changed, 107 insertions(+), 81 deletions(-)
net/dccp/ccids/ccid2.h +14 -6
@@ -43,8 +43,13 @@ struct ccid2_seq {/** struct ccid2_hc_tx_sock - CCID2 TX half connection * * @ccid2hctx_{cwnd,ssthresh,pipe}: as per RFC 4341, section 5 -* @ccid2hctx_packets_acked - Ack counter for deriving cwnd growth (RFC 3465) -* @ccid2hctx_lastrtt -time RTT was last measured +* @ccid2hctx_packets_acked: Ack counter for deriving cwnd growth (RFC 3465) +* @ccid2hctx_srtt: smoothed RTT estimate, scaled by 2^3 +* @ccid2hctx_mdev: smoothed RTT variation, scaled by 2^2 +* @ccid2hctx_mdev_max: maximum of @mdev during one flight +* @ccid2hctx_rttvar: moving average/maximum of @mdev_max +* @ccid2hctx_rto: RTO value deriving from SRTT and RTTVAR (RFC 2988) +* @ccid2hctx_rtt_seq: to decay RTTVAR at most once per flight * @ccid2hctx_rpseq - last consecutive seqno * @ccid2hctx_rpdupack - dupacks since rpseq * @ccid2hctx_av_chunks: list of Ack Vectors received on current skb
@@ -58,10 +63,13 @@ struct ccid2_hc_tx_sock {int ccid2hctx_seqbufc;struct ccid2_seq *ccid2hctx_seqh;struct ccid2_seq *ccid2hctx_seqt; -long ccid2hctx_rto; -long ccid2hctx_srtt; -long ccid2hctx_rttvar; -unsigned long ccid2hctx_lastrtt; +/* RTT measurement: variables/principles are the same as in TCP */ +u32 ccid2hctx_srtt, + ccid2hctx_mdev, + ccid2hctx_mdev_max, + ccid2hctx_rttvar, + ccid2hctx_rto; + u64 ccid2hctx_rtt_seq:48;struct timer_list ccid2hctx_rtotimer;u64 ccid2hctx_rpseq;int ccid2hctx_rpdupack;
net/dccp/ccids/ccid2.c +93 -75
204 lines not on this page · raw message
PATCH 4/4 : Remove wrappers around sk_{reset,stop}_timer()
This removes the wrappers around the sk timer functions as it makes the code clearer and not much is gained from using wrappers: the BUG_ON in start_rto_timer will never trigger since that function was called only when
* the RTO timer expired (rto_expire, and then timer_pending() is false);
* in tx_packet_sent only if !timer_pending() (BUG_ON is redundant here);
* previously in new_ack, after stopping the timer (timer_pending() false).
One further motive behind this patch is to replace the RTO timer with the icsk retransmission timer, as it is already part of the DCCP socket.
--- net/dccp/ccids/ccid2.c | 30 ++++++------------------------ 1 files changed, 6 insertions(+), 24 deletions(-)
net/dccp/ccids/ccid2.c +6 -24
@@ -111,8 +111,6 @@ static void ccid2_change_l_ack_ratio(struct sock *sk, u32 val) dp->dccps_l_ack_ratio = val; } -static void ccid2_start_rto_timer (struct sock *sk); -static void ccid2_hc_tx_rto_expire (unsigned long data) {struct sock *sk = (struct sock *)data;
@@ -152,23 +150,14 @@ static void ccid2_hc_tx_rto_expire(unsigned long data)/* if we were blocked before, we may now send cwnd=1 packet */ if (sender_was_blocked)tasklet_schedule (&dccp_sk (sk)->dccps_xmitlet); -ccid2_start_rto_timer (sk); +/* restart backed-off timer */ +sk_reset_timer (sk, &hctx->ccid2hctx_rtotimer, + jiffies + hctx->ccid2hctx_rto); out:bh_unlock_sock (sk);sock_put (sk); } -static void ccid2_start_rto_timer (struct sock *sk) -{ -struct ccid2_hc_tx_sock *hctx =ccid2_hc_tx_sk (sk); - -ccid2_pr_debug ("setting RTO timeout=%ld\n" , hctx->ccid2hctx_rto); - -BUG_ON (timer_pending (&hctx->ccid2hctx_rtotimer)); -sk_reset_timer (sk, &hctx->ccid2hctx_rtotimer, - jiffies + hctx->ccid2hctx_rto); -} -static void ccid2_hc_tx_packet_sent (struct sock *sk,unsigned int len) {struct dccp_sock *dp =dccp_sk (sk);
@@ -248,7 +237,8 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, unsigned int len)/* setup RTO timer */ if (!timer_pending (&hctx->ccid2hctx_rtotimer)) -ccid2_start_rto_timer (sk); +sk_reset_timer (sk, &hctx->ccid2hctx_rtotimer, + jiffies + hctx->ccid2hctx_rto); #ifdef CONFIG_IP_DCCP_CCID2_DEBUG do {
@@ -265,14 +255,6 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, unsigned int len)#endif } -static void ccid2_hc_tx_kill_rto_timer (struct sock *sk) -{ -struct ccid2_hc_tx_sock *hctx =ccid2_hc_tx_sk (sk); - -sk_stop_timer (sk, &hctx->ccid2hctx_rtotimer); -ccid2_pr_debug ("deleted RTO timer\n" ); -} -/** * ccid2_rtt_estimator - Sample RTT and compute RTO using RFC2988 algorithm * This code is almost identical with TCP's tcp_rtt_estimator(), since
@@ -651,7 +633,7 @@ static void ccid2_hc_tx_exit(struct sock *sk)struct ccid2_hc_tx_sock *hctx =ccid2_hc_tx_sk (sk);int i; -ccid2_hc_tx_kill_rto_timer (sk); +sk_stop_timer (sk, &hctx->ccid2hctx_rtotimer);for (i =0 ; i < hctx->ccid2hctx_seqbufc; i++)kfree (hctx->ccid2hctx_seqbuf[i]);
Re: [PATCH 3/4] [CCID2]: Replace broken RTT estimator with better algorithm
In reply to Gerrit RenkerQuoted 181 lines · Gerrit Renker
The current CCID-2 RTT estimator code is in parts broken and lags behind the
suggestions in RFC2988 of using scaled variants for SRTT/RTTVAR. That code is replaced by the present patch, which reuses the Linux TCP RTT estimator code - reasons for this code duplication are given below.Further details:
----------------
1. The minimum RTO of previously one second has been replaced with TCP's, sinceRFC4341, sec. 5 says that the minimum of 1 sec. (suggested in RFC2988, 2.4) is not necessary. Instead, the TCP_RTO_MIN is used, which agrees with DCCP's concept of a default RTT (RFC 4340, 3.4). 2. The maximum RTO has been set to DCCP_RTO_MAX (64 sec), which agrees with RFC2988, (2.5).3. De-inlined the function
ccid2_new_ack().
4. Added a FIXME: the RTT is sampled several times per Ack Vector, which will give the wrong estimate. It should be replaced with one sample per Ack. However, at the moment this can not be resolved easily, since
- it depends on TX history code (which also needs some work),
- the cleanest solution is not to use the `sent' time at all (saves 4 bytes per entry) and use DCCP timestamps / elapsed time to estimated the RTT, which however is non-trivial to get right (but needs to be done).Reasons for reusing the Linux TCP estimator algorithm:
------------------------------------------------------
Some time was spent to find a better alternative, using basic RFC2988 as a first step. Further analysis and experimentation showed that the Linux TCP RTO estimator is superior to a basic RFC2988 implementation. A summary is on
http://www.erg.abdn.ac.uk/users/gerrit/dccp/notes/ccid2/rto_estimator/In addition, this estimator fared well in a recent empirical evaluation:
Rewaskar, Sushant, Jasleen Kaur and F. Donelson Smith. A Performance Study of Loss Detection/Recovery in Real-world TCP Implementations. Proceedings of 15th IEEE International Conference on Network Protocols (ICNP-07). 2007.
Thus there is significant benefit in reusing the existing TCP code.
Signed-off-by Gerrit Renker <[email protected]>---
net/dccp/ccids/ccid2.c | 168 ++++++++++++++++++++++++++--------------------- net/dccp/ccids/ccid2.h | 20 ++++-- 2 files changed, 107 insertions(+), 81 deletions(-)---
a/net/dccp/ccids/ccid2.h
+++b/net/dccp/ccids/ccid2.h
@@ -43,8 +43,13 @@ structccid2_seq{
/** structccid2_hc_tx_sock- CCID2 TX half connection
*
* @ccid2hctx_{cwnd,ssthresh,pipe}: as per RFC 4341, section 5
- * @ccid2hctx_packets_acked - Ack counter for deriving cwnd growth (RFC 3465)
- * @ccid2hctx_lastrtt -time RTT was last measured
+ * @ccid2hctx_packets_acked: Ack counter for deriving cwnd growth (RFC 3465)
+ * @ccid2hctx_srtt: smoothed RTT estimate, scaled by 2^3
+ * @ccid2hctx_mdev: smoothed RTT variation, scaled by 2^2
+ * @ccid2hctx_mdev_max: maximum of @mdev during one flight
+ * @ccid2hctx_rttvar: moving average/maximum of @mdev_max
+ * @ccid2hctx_rto: RTO value deriving from SRTT and RTTVAR (RFC 2988)
+ * @ccid2hctx_rtt_seq: to decay RTTVAR at most once per flight
* @ccid2hctx_rpseq - last consecutive seqno
* @ccid2hctx_rpdupack - dupacks since rpseq
* @ccid2hctx_av_chunks: list of Ack Vectors received on current skb@@ -58,10 +63,13 @@ struct ccid2_hc_tx_sock { int ccid2hctx_seqbufc; struct ccid2_seq *ccid2hctx_seqh; struct ccid2_seq *ccid2hctx_seqt; - long ccid2hctx_rto; - long ccid2hctx_srtt; - long ccid2hctx_rttvar; - unsigned long ccid2hctx_lastrtt; + /* RTT measurement: variables/principles are the same as in TCP */ + u32 ccid2hctx_srtt, + ccid2hctx_mdev, + ccid2hctx_mdev_max, + ccid2hctx_rttvar, + ccid2hctx_rto; + u64 ccid2hctx_rtt_seq:48; struct timer_list ccid2hctx_rtotimer; u64 ccid2hctx_rpseq; int ccid2hctx_rpdupack; --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -111,12 +111,6 @@ static void ccid2_change_l_ack_ratio(struct sock *sk, u32 val) dp->dccps_l_ack_ratio = val;}
-static void
ccid2_change_srtt(struct ccid2_hc_tx_sock *hctx, long val)-{
-ccid2_pr_debug("change SRTT to %ld\n", val);
-hctx->ccid2hctx_srtt= val;
-}
-
static voidccid2_start_rto_timer(struct sock *sk);static void
ccid2_hc_tx_rto_expire(unsigned long data)
@@ -124,7 +118,6 @@ static voidccid2_hc_tx_rto_expire(unsigned long data)struct sock *sk = (struct sock *)data; struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); const bool sender_was_blocked = ccid2_cwnd_network_limited(hctx);- long s;
bh_lock_sock(sk); if (sock_owned_by_user(sk)) {@@ -137,10 +130,8 @@ static void
ccid2_hc_tx_rto_expire(unsigned long data)/* back-off timer */ hctx->ccid2hctx_rto <<= 1;-
- s =hctx->ccid2hctx_rto/ HZ;
- if (s > 60)
-hctx->ccid2hctx_rto= 60 * HZ;
+ if (hctx->ccid2hctx_rto>DCCP_RTO_MAX)
+hctx->ccid2hctx_rto=DCCP_RTO_MAX;/* adjust pipe, cwnd etc */ hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd / 2; @@ -282,9 +273,87 @@ static void ccid2_hc_tx_kill_rto_timer(struct sock *sk) ccid2_pr_debug("deleted RTO timer\n");}
-static inline void ccid2_new_ack(struct sock *sk,
- structccid2_seq*seqp,
- unsigned int *maxincr)
+/**
+ *ccid2_rtt_estimator- Sample RTT and compute RTO using RFC2988 algorithm
+ * This code is almost identical with TCP'stcp_rtt_estimator(), since
+ * - it has a higher sampling frequency (recommended by RFC 1323),
+ * - the RTO does not collapse into RTT due to RTTVAR going towards zero,
+ * - it is simple (cf. more complex proposals such as Eifel timer or research
+ * which suggests that the gain should be set according to window size),
+ * - in tests it was found to work well with CCID2 [gerrit].
+ */
+static voidccid2_rtt_estimator(struct sock *sk, const long mrtt)+{
+ structccid2_hc_tx_sock*hctx =ccid2_hc_tx_sk(sk);
+ long m = mrtt ? : 1;
+
+ if (hctx->ccid2hctx_srtt= 0) {+ /* First measurement m */ + hctx->ccid2hctx_srtt = m << 3; + hctx->ccid2hctx_mdev = m << 1; + + hctx->ccid2hctx_mdev_max = max(TCP_RTO_MIN, hctx->ccid2hctx_mdev); + hctx->ccid2hctx_rttvar = hctx->ccid2hctx_mdev_max; + hctx->ccid2hctx_rtt_seq = dccp_sk(sk)->dccps_gss; + } else { + /* Update scaled SRTT as SRTT += 1/8 * (m - SRTT) */ + m -= (hctx->ccid2hctx_srtt >> 3); + hctx->ccid2hctx_srtt += m; + + /* Similarly, update scaled mdev with regard to |m| */ + if (m < 0) { + m = -m; + m -= (hctx->ccid2hctx_mdev >> 2); + /* + * This neutralises RTO increase when RTT < SRTT - mdev + * (see P. Sarolahti and * A. Kuznetsov, + * "Congestion Control in Linux TCP", + * USENIX 2002, pp. 49-62). + */ + if (m > 0) + m >>= 3; + } else { + m -= (hctx->ccid2hctx_mdev >> 2); + } + hctx->ccid2hctx_mdev += m; + + if (hctx->ccid2hctx_mdev > hctx->ccid2hctx_mdev_max) { + hctx->ccid2hctx_mdev_max = hctx->ccid2hctx_mdev; + if (hctx->ccid2hctx_mdev_max > hctx->ccid2hctx_rttvar) + hctx->ccid2hctx_rttvar = hctx->ccid2hctx_mdev_max; + } + + /* + * Decay RTTVAR at most once per flight, exploiting that + * 1) pipe <= cwnd <= Sequence_Window = W (RFC 4340, 7.5.2) + * 2) AWL = GSS-W+1 <= GAR <= GSS (RFC 4340, 7.5.1) + * GAR is a useful bound for FlightSize = pipe, AWL is probably + * too low as it over-estimates pipe. + */
Quoted 3 lines
+ if (
after48(dccp_sk(sk)->dccps_gar, hctx->ccid2hctx_rtt_seq)) {
+ if (hctx->ccid2hctx_mdev_max<hctx->ccid2hctx_rttvar)
+hctx->ccid2hctx_rttvar-= (hctx->ccid2hctx_rttvar-hctx->ccid2hctx_mdev_max) >> 2;
More than 80 chars in this line! 87 chars. Is this ok?
Quoted 114 lines
+
hctx->ccid2hctx_rtt_seq= dccp_sk(sk)->dccps_gss;
+hctx->ccid2hctx_mdev_max=TCP_RTO_MIN;
+ }
+ }
+
+ /*+ * Set RTO from SRTT and RTTVAR + * Clock granularity is ignored since the minimum error for RTTVAR is + * clamped to 50msec (corresponding to HZ ). This leads to a minimum + * RTO of 200msec. This agrees with TCP and RFC 4341, 5.: "Because DCCP + * does not retransmit data, DCCP does not require TCP's recommended + * minimum timeout of one second". + */ + hctx->ccid2hctx_rto = (hctx->ccid2hctx_srtt >> 3) + hctx->ccid2hctx_rttvar; + + if (hctx->ccid2hctx_rto > DCCP_RTO_MAX) + hctx->ccid2hctx_rto = DCCP_RTO_MAX; +} + +static void ccid2_new_ack(struct sock *sk, struct ccid2_seq *seqp, + unsigned int *maxincr) { struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);@@ -298,64 +367,15 @@ static inline void ccid2_new_ack(struct sock *sk,
hctx->ccid2hctx_cwnd += 1; hctx->ccid2hctx_packets_acked = 0; } - - /* update RTO */ - if (hctx->ccid2hctx_srtt = -1 || - time_after(jiffies, hctx->ccid2hctx_lastrtt + hctx->ccid2hctx_srtt)) { - unsigned long r = (long)jiffies - (long)seqp->ccid2s_sent; - int s; - - /* first measurement */ - if (hctx->ccid2hctx_srtt = -1) { - ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n", - r, jiffies, - (unsigned long long)seqp->ccid2s_seq); - ccid2_change_srtt(hctx, r); - hctx->ccid2hctx_rttvar = r >> 1; - } else { - /* RTTVAR */ - long tmp = hctx->ccid2hctx_srtt - r; - long srtt; - - if (tmp < 0) - tmp *= -1; - - tmp >>= 2; - hctx->ccid2hctx_rttvar *= 3; - hctx->ccid2hctx_rttvar >>= 2; - hctx->ccid2hctx_rttvar += tmp; - - /* SRTT */ - srtt = hctx->ccid2hctx_srtt; - srtt *= 7; - srtt >>= 3; - tmp = r >> 3; - srtt += tmp; - ccid2_change_srtt(hctx, srtt); - } - s = hctx->ccid2hctx_rttvar << 2; - /* clock granularity is 1 when based on jiffies */ - if (!s) - s = 1; - hctx->ccid2hctx_rto = hctx->ccid2hctx_srtt + s; - - /* must be at least a second */ - s = hctx->ccid2hctx_rto / HZ; - /* DCCP doesn't require this [but I like it cuz my code sux] */ -#if 1 - if (s < 1) - hctx->ccid2hctx_rto = HZ; -#endif - /* max 60 seconds */ - if (s > 60) - hctx->ccid2hctx_rto = HZ * 60; - - hctx->ccid2hctx_lastrtt = jiffies; - - ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n", - hctx->ccid2hctx_srtt, hctx->ccid2hctx_rttvar, - hctx->ccid2hctx_rto, HZ, r); - } + /* + * FIXME: RTT is sampled several times per acknowledgment (for each + * entry in the Ack Vector), instead of once per Ack (as in TCP SACK). + * This causes the RTT to be over-estimated, since the older entries + * in the Ack Vector have earlier sending times. + * The cleanest solution is to not use the ccid2s_sent field at all + * and instead use DCCP timestamps - need to be resolved at some time. + */+
ccid2_rtt_estimator(sk, jiffies - seqp->ccid2s_sent);
}static void
ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp)
@@ -617,9 +637,7 @@ static intccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)if (ccid2_hc_tx_alloc_seq(hctx)) return -ENOMEM;- hctx->ccid2hctx_rto = 3 * HZ; - ccid2_change_srtt(hctx, -1); - hctx->ccid2hctx_rttvar = -1; + hctx->ccid2hctx_rto = DCCP_TIMEOUT_INIT; hctx->ccid2hctx_rpdupack = -1; hctx->ccid2hctx_last_cong = jiffies; setup_timer(&hctx->ccid2hctx_rtotimer, ccid2_hc_tx_rto_expire,-
To unsubscribe from this list: send the line "unsubscribe dccp" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/4] [CCID2]: Replace broken RTT estimator with better algorithm
| > + * Decay RTTVAR at most once per flight, exploiting that
| > + * 1) pipe <= cwnd <= Sequence_Window = W (RFC 4340, 7.5.2)
| > + * 2) AWL = GSS-W+1 <= GAR <= GSS (RFC 4340, 7.5.1)
| > + * GAR is a useful bound for FlightSize = pipe, AWL is probably
| > + * too low as it over-estimates pipe.
| > + */
| > + if (after48(dccp_sk(sk)->dccps_gar, hctx->ccid2hctx_rtt_seq)) {
| > + if (hctx->ccid2hctx_mdev_max < hctx->ccid2hctx_rttvar)
| > + hctx->ccid2hctx_rttvar -= (hctx->ccid2hctx_rttvar - hctx->ccid2hctx_mdev_max) >> 2;
|
| More than 80 chars in this line! 87 chars. Is this ok?
| There are actually 120 characters in this line. The 80-characters constraint has become a recommendation, i.e. it is possible and legal to make exceptions. I kept it in to allow a better comparison to the original TCP code.
If anything, it shows how the ubiquitous `hctx->ccid?hctx_' prefixes make it hard to read the code.