TCP再送タイムアウト時間の規格と実装

先日、アンドリュー・タネンバウム先生のコンピュータネットワーク第5版を読んでいると気になる記述が出てきた。 曰く、TCP再送タイムアウト時間(RTO)は下記の式で求められる。  

RTO = SRTT + 4 * RTTVAR

SRTTとは平滑化したRTT値、RTTVARとは標準偏差…ではなく平均偏差(計算の簡略化のため)である。単にRTT値だけを元にタイムアウト時間を設定してしまうと、RTT値のブレが大きいときに不要なタイムアウトが発生しやすくなる。なので平均偏差も足しましょう…それも4倍もしておけば、いくらなんでもパケットが到達して相手が生きているならば応答が返ってくるはずだろう、と。そういう式である。OK、話はわかった。 しかし信じがたい記述が続く。

再送タイマー最小値は1秒となっている。これはスプリアス再送を防ぐために選ばれた値である。

本当だろうか?だったら計算なんてする必要はない。常に1秒をタイムアウト値にすればいいのではないか?東京から西海岸までのRTTは100msecかそこらだろう。RTTが1秒を超える通信なんて、現代では余程劣悪な環境でもなければありえそうにもない。

この記述の根拠となる規格は RFC 2988 - Computing TCP's Retransmission Timer で、下記のような記述がある。

  (2.4) Whenever RTO is computed, if it is less than 1 second then the RTO SHOULD be rounded up to 1 second.

「計算されたRTOがいくつであれ、1秒未満であるならは1秒に丸めるべきです」、なるほど、タネンバウム先生の言うとおりのことが書いてある(ただしMUSTではなくSHOULDなので、あくまで推奨だ)。だがこの規格は2000年に定められたものだ。きょうびのTCP実装が、果たしてこの推奨に従っているのだろうか?

幸いなことに、我々は世界一使われているであろうTCP実装のコードにアクセスできる。 Linuxカーネルのコードを読むと、/net/ipv4/tcp_input.c にRTOを設定している箇所があった。以下に引用しよう。

static void tcp_set_rto(struct sock *sk)
{
    const struct tcp_sock *tp = tcp_sk(sk);
    /* Old crap is replaced with new one. 8)
    *
    * More seriously:
    * 1. If rtt variance happened to be less 50msec, it is hallucination.
    *    It cannot be less due to utterly erratic ACK generation made
    *    at least by solaris and freebsd. "Erratic ACKs" has _nothing_
    *    to do with delayed acks, because at cwnd>2 true delack timeout
    *    is invisible. Actually, Linux-2.4 also generates erratic
    *    ACKs in some circumstances.
    */
    inet_csk(sk)->icsk_rto = __tcp_set_rto(tp);

    /* 2. Fixups made earlier cannot be right.
    *    If we do not estimate RTO correctly without them,
    *    all the algo is pure shit and should be replaced
    *    with correct one. It is exactly, which we pretend to do.
    */

    /* NOTE: clamping at TCP_RTO_MIN is not required, current algo
    * guarantees that rto is higher.
    */
    tcp_bound_rto(sk);
}

__tcp_set_rtoでRTO値を計算し、tcp_bound_rtoで丸めているのだろう。この2つの関数の実装は /include/net/tcp.h にある。

static inline u32 __tcp_set_rto(const struct tcp_sock *tp)
{
    return usecs_to_jiffies((tp->srtt_us >> 3) + tp->rttvar_us);
}

フム、srrt_us と rttvar_usの単位を揃えて足しているだけのようだ。しかしRTTVARを4倍するという話はどこにいった? 丸めているところも見よう。

static inline void tcp_bound_rto(const struct sock *sk)
{
    if (inet_csk(sk)->icsk_rto > TCP_RTO_MAX)
        inet_csk(sk)->icsk_rto = TCP_RTO_MAX;
}

こちらもRFCにあるように最小値を超えた場合に丸めているのでなく、最大値を超えた場合に丸めているではないか。

それはそうと、丸め関数 tcp_bound_rto を呼ぶ直前のコメントには「TCP_RTO_MINは不要である。今のアルゴリズムではRTOは十分大きいことを保証する」と書いてある。 どういうことだろう。TCP_RTO_MIN という定数が最小値で、かつ、ここで用いられている rttvar_us は TCP_RTO_MIN よりも十分に大きいことが保証されているのだろうか?

ではsrtt_usとrttvar_usを求める箇所を確認してみよう。これも /net/ipv4/tcp_input.c にある。

static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)
{
    struct tcp_sock *tp = tcp_sk(sk);
    long m = mrtt_us; /* RTT */
    u32 srtt = tp->srtt_us;

    /* The following amusing code comes from Jacobson's
    *  article in SIGCOMM '88.  Note that rtt and mdev
    *  are scaled versions of rtt and mean deviation.
    *  This is designed to be as fast as possible
    *  m stands for "measurement".
    *
    *  On a 1990 paper the rto value is changed to:
    *  RTO = rtt + 4 * mdev
    *
    * Funny. This algorithm seems to be very broken.
    * These formulae increase RTO, when it should be decreased, increase
    * too slowly, when it should be increased quickly, decrease too quickly
    * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
    * does not matter how to _calculate_ it. Seems, it was trap
    * that VJ failed to avoid. 8)
    */
    if (srtt != 0) {
        m -= (srtt >> 3);    /* m is now error in rtt est */
        srtt += m;      /* rtt = 7/8 rtt + 1/8 new */
        if (m < 0) {
            m = -m;     /* m is now abs(error) */
            m -= (tp->mdev_us >> 2);   /* similar update on mdev */
            /* This is similar to one of Eifel findings.
            * Eifel blocks mdev updates when rtt decreases.
            * This solution is a bit different: we use finer gain
            * for mdev in this case (alpha*beta).
            * Like Eifel it also prevents growth of rto,
            * but also it limits too fast rto decreases,
            * happening in pure Eifel.
            */
            if (m > 0)
                m >>= 3;
        } else {
            m -= (tp->mdev_us >> 2);   /* similar update on mdev */
        }
        tp->mdev_us += m;        /* mdev = 3/4 mdev + 1/4 new */
        if (tp->mdev_us > tp->mdev_max_us) {
            tp->mdev_max_us = tp->mdev_us;
            if (tp->mdev_max_us > tp->rttvar_us)
                tp->rttvar_us = tp->mdev_max_us;
        }
        if (after(tp->snd_una, tp->rtt_seq)) {
            if (tp->mdev_max_us < tp->rttvar_us)
                tp->rttvar_us -= (tp->rttvar_us - tp->mdev_max_us) >> 2;
            tp->rtt_seq = tp->snd_nxt;
            tp->mdev_max_us = tcp_rto_min_us(sk);
        }
    } else {
        /* no previous measure. */
        srtt = m << 3;       /* take the measured time to be rtt */
        tp->mdev_us = m << 1; /* make sure rto = 3*rtt */
        tp->rttvar_us = max(tp->mdev_us, tcp_rto_min_us(sk));
        tp->mdev_max_us = tp->rttvar_us;
        tp->rtt_seq = tp->snd_nxt;
    }
    tp->srtt_us = max(1U, srtt);
}

未知の変数が増えてきた。こんなときは構造体の定義のコメントを頼ろう。 /include/linux/tcp.hを見ると下記のように書いてある。

u32  srtt_us;    /* smoothed round trip time << 3 in usecs */
u32 mdev_us;    /* medium deviation            */
u32 mdev_max_us;    /* maximal mdev for the last rtt period    */
u32 rttvar_us;  /* smoothed mdev_max           */
u32 rtt_seq;    /* sequence number to update rttvar    */

u32 snd_nxt;    /* Next sequence we send       */
u32 snd_una;    /* First byte we want an ack for   */

なるほど、rttvar_usというのは平均偏差だと思っていたが、「平均偏差の最大値」と書いてあるではないか。変数名と実態が一致していない(上にmdevの扱いの異なるmaxを示す変数が二つもある!)ので混乱させられるが、恐らく過去は違ったのだろう。それに srtt_us には us とサフィックスが付いているが、実際には3bit左シフト(つまり8倍)しないと単位は us にはならないようだ(これは既に上述の__tcp_set_rto関数内でやっている)。

ところで、コメントにRFCにあった式が書いてあるではないか。(あまり英語は得意ではないが)ちょっと翻訳してみよう。

次の愉快なコードは SIGCOMM '88 における Jacobson の記事に拠る。rttとmdevは平滑化されたRTTと平均偏差であることに注意して欲しい。これは可能な限り高速に計測できるように設計されている。

1990年の論文では rto の値は下記の式で求められる。

RTO = rtt + 4 * mdev

馬鹿馬鹿しい。このアルゴリズムは壊れているとしか思えない。 この計算式はRTOを下げるべき時に上げてしまい、上げるべき時には非常に低速にしか上昇しない。そして高速に上げなくてはならない時には素早く下げてしまう…といった具合だ。思うに、BSDのRTOは1つの値しか取らないので*1、どのように計算されるかは問題にならないのだろう。こいつはVJ*2が避けるのに失敗したトラップだったようだ。

確かにRFCにあるRTOの計算式では、RTTが上昇している傾向だとか、下降している傾向といったものはまったく考慮されていない。例えばRTTが大きく下降し始めたときでも偏差は大きくなるので、RTTの下降分を4 * mdev の部分が打ち消してしまうかもしれない。 だが上記のコードでは、今回の偏差が正であるか負であるかによって計算が異なり、値が大きすぎる場合も修正が加えられているようだ(RTOが肥大化しにくく、縮小しやすい)。

そして基本的には求めた mdev_us の値で mdev_max_us を更新し、mdev_max_us で rttvar_us を計算する。そしてRTTの計測期間の切り替わりで mdev_max_us を tcp_rto_min_us 関数で初期化しなおすようだ。ならば、 tcp_rto_min_us 関数の中に本当の最小値があるのだろう。

static inline u32 tcp_rto_min_us(struct sock *sk)
{
    return jiffies_to_usecs(tcp_rto_min(sk));
}

/* Compute the actual rto_min value */
static inline u32 tcp_rto_min(struct sock *sk)
{
    const struct dst_entry *dst = __sk_dst_get(sk);
    u32 rto_min = TCP_RTO_MIN;

    if (dst && dst_metric_locked(dst, RTAX_RTO_MIN))
        rto_min = dst_metric_rtt(dst, RTAX_RTO_MIN);
    return rto_min;
}

どうやら TCP_RTO_MIN に到達したようだ。これが静的に与えられる理論上の最小値ということになる*3TCP_RTO_MINの値を確認しよう。この定義は /include/net/tcp.h にある。

#define TCP_RTO_MIN ((unsigned)(HZ/5))

0.2秒である。やはり予測通りというべきか、Linuxにおいて再送タイムアウト値が1秒に丸められるということはないようだ。 しかしそれ以前に、先のRFCにおいて定義されたRTTVARの計算式はMUSTとされているのだが、Linuxでの実装は値の大きさ、正負によって計算式が異なる。これには驚いた。

まとめ
  • 世間で使われているTCP実装がRFCに準拠しているとは限らない
  • Linuxカーネルのコメント面白い

それはそうとタネンバウム先生のコンピュータネットワークという本の価値がこれによって損なわれるという話ではない。あれはあくまで(TCP/IPに限らず)ネットワークの規格や歴史、それに纏わる逸話を記した偉大なる手引書であり、TCPの一実装に関するような本ではないのだ。

*1:調べてはいないが、これはRFCの規格どおりに1秒に丸めているということだろうか?

*2:元のRTO計測の式を書いたVan Jacobson氏のことと思われる

*3:もちろんRTTがゼロなどということは有り得ないので、この値がそのまま最小値になることはないだろうが