lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Wed, 27 Feb 2008 23:40:42 -0300
From:	"Leandro Sales" <leandroal@...il.com>
To:	"Gerrit Renker" <gerrit@....abdn.ac.uk>
Cc:	acme@...hat.com, dccp@...r.kernel.org, netdev@...r.kernel.org
Subject: Re: [PATCH 3/4] [CCID2]: Replace broken RTT estimator with better algorithm

On Wed, Feb 27, 2008 at 11:23 AM, Gerrit Renker <gerrit@....abdn.ac.uk> wrote:
> 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.
>
>
>  Signed-off-by: Gerrit Renker <gerrit@....abdn.ac.uk>
>  ---
>   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 @@ 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;
>  --- 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 void ccid2_start_rto_timer(struct sock *sk);
>
>   static void ccid2_hc_tx_rto_expire(unsigned long data)
>  @@ -124,7 +118,6 @@ static void ccid2_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,
>  -                                struct ccid2_seq *seqp,
>  -                                unsigned int *maxincr)
>  +/**
>  + * ccid2_rtt_estimator - Sample RTT and compute RTO using RFC2988 algorithm
>  + * This code is almost identical with TCP's tcp_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 void ccid2_rtt_estimator(struct sock *sk, const long mrtt)
>  +{
>  +       struct ccid2_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.
>  +                */
>  +               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?

>  +                       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=20). 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 int ccid2_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 majordomo@...r.kernel.org
>  More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists