RTT（Round Trip Time）推定
RTTはその名の通り、送信元から送信先へ行って帰っての往復時間（ラウンドトリップ時間）のことで、TCPでは非常に重要なパラメータである。インターネット環境では他のトラフィックの影響を受けたり、経路が変わったりとRTTがばらつくのは当たり前であり、再送タイムアウトなどの計算にはRTTを平滑化したSmoothed RTT (SRTT)が使われる。TCPの標準仕様であるRFC793によるとSRTTは以下の式から計算される。
R←αR + (1 - α)M
Mは直近のRTTの計測値であり、αとして0.8〜0.9の値が推奨されている。ただし、カーネル内では小数点演算を避けてシフト演算で実装するため、LinuxやBSDは、下記に示すSIGCOMM88のVan Jacobsonのアルゴリズム（論文）を使っている。Linuxのソースコード中にたびたびVJと出てくるのは彼のこと。
m −= (sa >> 3);
sa += m; /* sa = 7/8 sa + 1/8 m */
if (m < 0)
m = −m;
m −= (sv >> 2);
sv += m; /* sv = 3/4 sv + 1/4 m */
rto = (sa >> 3) + sv;RTT関係のパラメータは、tcp_sock構造体に格納されている。Linuxの実装では、saがsrtt_us、svがmdev_usに相当し、それぞれ実際のSRTTの8倍（<< 3）、SRTTと測定値の誤差の平均偏差を4倍（<< 2）した値が入っている。このように下駄を履いているのでちょっと読みにくい。
commit 740b0f1841f6e39085b711d41db9ffb07198682b
Author: Eric Dumazet <edumazet@google.com>
Date: Wed Feb 26 14:02:48 2014 -0800
tcp: switch rtt estimations to usec resolution
<snip>
diff --git a/include/linux/tcp.h b/include/linux/tcp.h
index 4ad0706d40eb..239946868142 100644
--- a/include/linux/tcp.h
+++ b/include/linux/tcp.h
@@ -201,10 +201,10 @@ struct tcp_sock {
u32 tlp_high_seq; /* snd_nxt at the time of TLP retransmit. */
/* RTT measurement */
- u32 srtt; /* smoothed round trip time << 3 */
- u32 mdev; /* medium deviation */
- u32 mdev_max; /* maximal mdev for the last rtt period */
- u32 rttvar; /* smoothed mdev_max */
+ 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 packets_out; /* Packets which are "in flight" */「ソケットバッファとタイムスタンプ」に書いた流れとも連動しているが、このパッチによって、RTT関係のパラメータもマイクロ秒精度に変更されている。
さて、RTT推定をやっているのはtcp_rtt_estimator関数である。
net/ipv4/tcp_input.c
733 static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)
734 {
735 struct tcp_sock *tp = tcp_sk(sk);
736 long m = mrtt_us; /* RTT */
737 u32 srtt = tp->srtt_us;
738
739 /* The following amusing code comes from Jacobson's
740 * article in SIGCOMM '88. Note that rtt and mdev
741 * are scaled versions of rtt and mean deviation.
742 * This is designed to be as fast as possible
743 * m stands for "measurement".
744 *
745 * On a 1990 paper the rto value is changed to:
746 * RTO = rtt + 4 * mdev
747 *
748 * Funny. This algorithm seems to be very broken.
749 * These formulae increase RTO, when it should be decreased, increase
750 * too slowly, when it should be increased quickly, decrease too quickly
751 * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
752 * does not matter how to _calculate_ it. Seems, it was trap
753 * that VJ failed to avoid. 8)
754 */
755 if (srtt != 0) {
756 m -= (srtt >> 3); /* m is now error in rtt est */
757 srtt += m; /* rtt = 7/8 rtt + 1/8 new */
758 if (m < 0) {
759 m = -m; /* m is now abs(error) */
760 m -= (tp->mdev_us >> 2); /* similar update on mdev */
761 /* This is similar to one of Eifel findings.
762 * Eifel blocks mdev updates when rtt decreases.
763 * This solution is a bit different: we use finer gain
764 * for mdev in this case (alpha*beta).
765 * Like Eifel it also prevents growth of rto,
766 * but also it limits too fast rto decreases,
767 * happening in pure Eifel.
768 */
769 if (m > 0)
770 m >>= 3;
771 } else {
772 m -= (tp->mdev_us >> 2); /* similar update on mdev */
773 }
774 tp->mdev_us += m; /* mdev = 3/4 mdev + 1/4 new */
775 if (tp->mdev_us > tp->mdev_max_us) {
776 tp->mdev_max_us = tp->mdev_us;
777 if (tp->mdev_max_us > tp->rttvar_us)
778 tp->rttvar_us = tp->mdev_max_us;
779 }
780 if (after(tp->snd_una, tp->rtt_seq)) {
781 if (tp->mdev_max_us < tp->rttvar_us)
782 tp->rttvar_us -= (tp->rttvar_us - tp->mdev_max_us) >> 2;
783 tp->rtt_seq = tp->snd_nxt;
784 tp->mdev_max_us = tcp_rto_min_us(sk);
785
786 tcp_bpf_rtt(sk);
787 }
788 } else {
789 /* no previous measure. */
790 srtt = m << 3; /* take the measured time to be rtt */
791 tp->mdev_us = m << 1; /* make sure rto = 3*rtt */
792 tp->rttvar_us = max(tp->mdev_us, tcp_rto_min_us(sk));
793 tp->mdev_max_us = tp->rttvar_us;
794 tp->rtt_seq = tp->snd_nxt;
795
796 tcp_bpf_rtt(sk);
797 }
798 tp->srtt_us = max(1U, srtt);
799 }tcp_rtt_estimator関数の呼び出し元にむかって遡ると、tcp_ack_update_rtt関数、tcp_clean_rtx_queue関数、tcp_ack関数、tcp_rcv_established関数となる。tcp_rcv_established関数はTCPのステートマシンがESTABLISHED状態のときの受信処理を担う。受信パケットにACKが含まれていて、再送キューからACK済みのパケットを取り除くときに、RTTを更新する流れになる。
RTOの更新は、tcp_rtt_estimatorの直後に呼ばれるtcp_set_rto関数にて行われる。upper/lower boundチェックはあるけど、「rto = (sa >> 3) + sv」に相当するのは次のコード。
include/net/tcp.h
671 static inline u32 __tcp_set_rto(const struct tcp_sock *tp)
672 {
673 return usecs_to_jiffies((tp->srtt_us >> 3) + tp->rttvar_us);
674 }見てわかるようにtp->mdev_ns (sv)をそのままではなくtp->rttvar_usを加えている。rttvar_nsの設定もtcp_rtt_estimator関数内でやっているので、775行目以降をみてみよう。まず、tp->mdev_max_nsは1 RTT内での平均偏差の最大値になる。ちょうどafter(tp->snd_una, tp->rtt_seq)が真になるのが、次のRTTに移ったときだ。RTTが上昇傾向にあるときはtp->rttvar_nsはすぐにmdev_max_nsに追従し、下降傾向にあるときは徐々に差を詰めていく。この辺の実装はBSDと違うので、Web上のブログ等をぱらぱら眺めた感じだと誤解しているものが散見された。ちなみにBSD（Net/3とか）の変数名は、srttとrttvarだったはずだ。
で、Ackが帰ってこないとRTOタイマーが発動して、RTOを倍々にバックオフしていく。この辺は割愛。
話は変わって、RTTは遅延ベースの輻輳制御など（例えばTCP Vegas）でも使われるが、少し前までマイクロ秒解像度のRTTが必要なときはTCP_CONG_RTT_STAMPフラグを立てていた。このフラグが立っている場合は、tcp_congestion_ops.pkts_acked関数の引数としてマイクロ秒解像度のSRTTが渡されるので、輻輳制御モジュールではこれを利用していた。きれいな実装ではないけど、モジュール以外への影響を極力抑えるための策だろう。
static struct tcp_congestion_ops tcp_vegas = {
.flags = TCP_CONG_RTT_STAMP,
.init = tcp_vegas_init,
.ssthresh = tcp_reno_ssthresh,
.cong_avoid = tcp_vegas_cong_avoid,
.min_cwnd = tcp_reno_min_cwnd,
.pkts_acked = tcp_vegas_pkts_acked,
.set_state = tcp_vegas_state,
.cwnd_event = tcp_vegas_cwnd_event,
.get_info = tcp_vegas_get_info,
.owner = THIS_MODULE,
.name = "vegas",
};上のコードは2.6.xの頃のものだけど、5.8.10の時点ではTCP_CONG_RTT_STAMPフラグはすでにobsoleteになっていた。冒頭に示したパッチによりRTTの解像度がミリ秒からマイクロ秒になったので、pkts.acked関数で裏口としてSRTTを渡す必要がなくなったからだ。
この記事が気に入ったらサポートをしてみませんか？