Earliest Departure Timeモデル

バージョン4.20から導入されたEDTモデルについて。EDTの考えは前述したVan Jacobsonの「Evolving from AFAP: Teaching NICs about time」を見てもらうのが手っ取り早い。今まではNICに対して「何」を送るかしか指定しなかったが、「何」に加えて「いつ」送るかも指定すべきと言うのが基本的なアイデアだろうか。EDTの実装として、SIGCOMM17で発表されたCarousel（日本語で言うとメリーゴーランド）が例示されているけど、残念ながら現時点で実装は公開されていない。

Linuxに取り込まれているEDTパッチセットは次の８つのパッチから構成される。

72b0094f9182 tcp: switch tcp_clock_ns() to CLOCK_TAI base
2fd66ffba507 tcp: introduce tcp_skb_timestamp_us() helper
9799ccb0e984 tcp: add tcp_wstamp_ns socket field
d3edd06ea8ea tcp: provide earliest departure time in skb->tstamp
fd2bca2aa789 tcp: switch internal pacing timer to CLOCK_TAI
ab408b6dc744 tcp: switch tcp and sch_fq to new earliest departure time model
c092dd5f4a7f tcp: switch tcp_internal_pacing() to tcp_wstamp_ns
90caf67b01fa net_sched: sch_fq: remove dead code dealing with retransmits

さらに第2弾のパッチセットがこちら。

5f6188a8003d tcp: do not change tcp_wstamp_ns in tcp_mstamp_refresh
76a9ebe811fb net: extend sk_pacing_rate to unsigned long
a7a2563064e9 tcp: mitigate scheduling jitter in EDT pacing model
7baf33bdac37 net_sched: sch_fq: no longer use skb_is_tcp_pure_ack()
864e5c090749 tcp: optimize tcp internal pacing
825e1c523d50 tcp: cdg: use tcp high resolution clock cache

ちょっとだけソースを眺める。TCPコントロールブロック（tcp_sock）に追加されたtcp_wstamp_nsがキモで、これは次に送る予定のパケットの送信時刻を示している。つまりソケットごとにEDTを保持できることを意味する。

net/ipv4/tcp_output.c

static void tcp_update_skb_after_send(struct sock *sk, struct sk_buff *skb,
				      u64 prior_wstamp)
{
	struct tcp_sock *tp = tcp_sk(sk);

	if (sk->sk_pacing_status != SK_PACING_NONE) {
		unsigned long rate = sk->sk_pacing_rate;

		/* Original sch_fq does not pace first 10 MSS
		 * Note that tp->data_segs_out overflows after 2^32 packets,
		 * this is a minor annoyance.
		 */
		if (rate != ~0UL && rate && tp->data_segs_out >= 10) {
			u64 len_ns = div64_ul((u64)skb->len * NSEC_PER_SEC, rate);
			u64 credit = tp->tcp_wstamp_ns - prior_wstamp;

			/* take into account OS jitter */
			len_ns -= min_t(u64, len_ns / 2, credit);
			tp->tcp_wstamp_ns += len_ns;
		}
	}
	list_move_tail(&skb->tcp_tsorted_anchor, &tp->tsorted_sent_queue);
}

パケット送信後に呼ばれるtcp_update_skb_after_send関数にて、ペーシングが有効な場合、次に送信されるパケットサイズに応じてtcp_wstamp_nsが更新される。で、この値はsch_sqやTCP BBRから参照される。以下ではinternal TCP pacingの場合を見ていく。

static bool tcp_pacing_check(struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);

	if (!tcp_needs_internal_pacing(sk))
		return false;

	if (tp->tcp_wstamp_ns <= tp->tcp_clock_cache)
		return false;

	if (!hrtimer_is_queued(&tp->pacing_timer)) {
		hrtimer_start(&tp->pacing_timer,
			      ns_to_ktime(tp->tcp_wstamp_ns),
			      HRTIMER_MODE_ABS_PINNED_SOFT);
		sock_hold(sk);
	}
	return true;
}

<snip>

static bool tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle,
			   int push_one, gfp_t gfp)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct sk_buff *skb;
	unsigned int tso_segs, sent_pkts;
	int cwnd_quota;
	int result;
	bool is_cwnd_limited = false, is_rwnd_limited = false;
	u32 max_segs;

	sent_pkts = 0;

	tcp_mstamp_refresh(tp);

<snip>

	while ((skb = tcp_send_head(sk))) {

<snip>

		if (tcp_pacing_check(sk))
			break;

tcp_write_xmit関数はパケット送信関数。tcp_pacing_check関数で次のパケットの送信予定時刻に達してない場合は、pacing_timerを起動して送信は行わない。

/* Note: Called under soft irq.
* We can call TCP stack right away, unless socket is owned by user.
*/
enum hrtimer_restart tcp_pace_kick(struct hrtimer *timer)
{
	struct tcp_sock *tp = container_of(timer, struct tcp_sock, pacing_timer);
	struct sock *sk = (struct sock *)tp;

	tcp_tsq_handler(sk);
	sock_put(sk);

	return HRTIMER_NORESTART;
}

pacing_timerハンドラに登録されているのはtcp_pace_kick関数で、中身はTSQ (TCP Small Queues)関係の処理。TSQについては割愛するが、条件が揃えば再送処理を実行する。