TCP の再送タイムアウト

首藤 一幸

 2006年 11月 2日

Back to

信頼性のない通信路でのタイムアウト時間をどう決めたらいいかを考えていて、 TCP のアルゴリズムを学ぶに至りました。 Linux カーネルでは tcp_rtt_estimator という関数として実装されています。
linux-2.6.16.18/net/ipv4/tcp_input.c:545-555 

  545: /* Called to compute a smoothed rtt estimate. The data fed to this
  546:  * routine either comes from timestamps, or from segments that were
  547:  * known _not_ to have been retransmitted [see Karn/Partridge
  548:  * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88
  549:  * piece by Van Jacobson.
  550:  * NOTE: the next three routines used to be one big routine.
  551:  * To save cycles in the RFC 1323 implementation it was better to break
  552:  * it up into three procedures. -- erics
  553:  */
  554: static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt)
  555: {

次の論文の Appendix A に書かれているアルゴリズムが実装されています。 

Van Jacobson, Michael J. Karels, "Congestion Avoidance and Control", Proc. SIGCOMM'88.

タイムアウト時間は、次の式で決めます。 

a + 4 * v
a は RTT (round trip time, 通信の往復時間) の予測値であるところの指数重み付きの平均値 (exponential weighted mean)、 v は RTT の平均偏差 (mean deviation) です。 4v の項は、本当は分散 (σ^2) の平方根であるところの標準偏差 (σ) を使うのが定石だけれど、 乗算は計算時にオーバーフローを起こし得るとか、 平方根の計算は重いとかいう問題があるので、妥協案として単に 「ズレの (指数重み付き) 平均」 を使います。ズレの平均は標準偏差以上の値となるので、 より保守的（大きな偏差を仮定する）と言えます。

実際の提案アルゴリズムでは、 a と v の代わりに、それぞれ 8倍、4倍にした sa と sv を計算していき、再送タイムアウト rto は rto = (sa >> 3) + sv として算出します。 m を最近の RTT として、上記論文 Appendix A の最後あたりに書かれている rto 算出アルゴリズムは次の通りです。 

m -= (sa >> 3);
sa += m;
if (m < 0)
    m = -m;
m -= (sv >> 2);
sv += m;
rto = (sa >> 3) + sv;

このアルゴリズムに該当するコードはここです。
linux-2.6.16.18/net/ipv4/tcp_input.c:578-606 

  578:                 m -= (tp->srtt >> 3); /* m is now error in rtt est */
  579:                 tp->srtt += m;                /* rtt = 7/8 rtt + 1/8 new */
  580:                 if (m < 0) {
  581:                         m = -m;              /* m is now abs(error) */
  582:                         m -= (tp->mdev >> 2);   /* similar update on mdev */
  583:                         /* This is similar to one of Eifel findings.
  584:                          * Eifel blocks mdev updates when rtt decreases.
  585:                          * This solution is a bit different: we use finer gain
  586:                          * for mdev in this case (alpha*beta).
  587:                          * Like Eifel it also prevents growth of rto,
  588:                          * but also it limits too fast rto decreases,
  589:                          * happening in pure Eifel.
  590:                          */
  591:                         if (m > 0)
  592:                                 m >>= 3;
  593:                 } else {
  594:                         m -= (tp->mdev >> 2);   /* similar update on mdev */
  595:                 }
  596:                 tp->mdev += m;               /* mdev = 3/4 mdev + 1/4 new */
  597:                 if (tp->mdev > tp->mdev_max) {
  598:                         tp->mdev_max = tp->mdev;
  599:                         if (tp->mdev_max > tp->rttvar)
  600:                                 tp->rttvar = tp->mdev_max;
  601:                 }
  602:                 if (after(tp->snd_una, tp->rtt_seq)) {
  603:                         if (tp->mdev_max < tp->rttvar)
  604:                                 tp->rttvar -= (tp->rttvar-tp->mdev_max)>>2;
  605:                         tp->rtt_seq = tp->snd_nxt;
  606:                         tp->mdev_max = TCP_RTO_MIN;
論文中のアルゴリズム記述と Linux カーネル中の変数名の対応は、次の通りです。

参考文献