データセンター向けTCPとeBPF実装

最近のLinuxではeBPFで輻輳制御アルゴリズムを実装し、カーネル内で実行できる。今日はDCTCP実装を眺めてみたいと思う。その前にオリジナルのDCTCPについて確認する。マージされたのはバージョン3.17の頃。

commit e3118e8359bb7c59555aca60c725106e6d78c5ce
Author: Daniel Borkmann <daniel@iogearbox.net>
Date:   Fri Sep 26 22:37:36 2014 +0200

   net: tcp: add DCTCP congestion control algorithm

DCTCPはRFCにもなっているけど、オリジナルは2010年にMSRとスタンフォード大のチームによって提案された（Data Center TCP (DCTCP) [SIGCOMM2010]）。一般的な輻輳制御アルゴリズムでは、遅延の増加やパケットロスによって輻輳の発生を間接的に検出するのだけど、DCTCPの基本的なアイデアはネットワーク側から直接的に輻輳を教えてもらうというもの。このために昔からあるECN (Explicit Congestion Notification) [RFC3168]を使う。ECN自体は、ルータがバッファがあふれる前に送信者に輻輳を伝える仕組みで、IPヘッダのToSフィールドの2ビットを使う。2000年代頭にはECNを使ったトランスポートプロトコルにはXCP (eXplicit Control Protocol)ってのが提案されていたりもした。

DCTCPは、データセンターというクローズなネットワーク向けにECNを使った輻輳制御を実装しようという試みになる。簡単に言えば、RTTあたりのECNビットの割合に応じて輻輳ウィンドウを縮小させる。例えば、100%がECNビットが立っていれば（Renoと同様に）輻輳ウィンドウを1/2まで、50%であれば3/4まで縮小する。サーバとネットワーク機器すべてが連動する必要があるので、インターネット環境で使うのは難しいが、データセンターネットワークであれば有効そうだ。

commit 09903869f69f37fd7a465183545b5739c6274654
Author: Martin KaFai Lau <kafai@fb.com>
Date:   Wed Jan 8 16:35:17 2020 -0800

   bpf: Add bpf_dctcp example

eBPFの実装自体はFacebookが取り組んでいるようだが、FacebookのデータセンターでDCTCPを使っていたりするのだろうか？ 参考：「Experiences Evaluating DCTCP」[LPC2018]

tools/testing/selftests/bpf/progs/bpf_dctcp.c

 51 SEC("struct_ops/dctcp_init")
 52 void BPF_PROG(dctcp_init, struct sock *sk)
 53 {
 54     const struct tcp_sock *tp = tcp_sk(sk);
 55     struct dctcp *ca = inet_csk_ca(sk);
 56     int *stg;
 57     
 58     ca->prior_rcv_nxt = tp->rcv_nxt;
 59     ca->dctcp_alpha = min(dctcp_alpha_on_init, DCTCP_MAX_ALPHA);
 60     ca->loss_cwnd = 0;
 61     ca->ce_state = 0;
 62     
 63     stg = bpf_sk_storage_get(&sk_stg_map, (void *)tp, NULL, 0);
 64     if (stg) {
 65         stg_result = *stg;
 66         bpf_sk_storage_delete(&sk_stg_map, (void *)tp);
 67     }
 68     dctcp_reset(tp, ca);
 69 }

<snip>

221 SEC(".struct_ops")
222 struct tcp_congestion_ops dctcp = {
223     .init       = (void *)dctcp_init,
224     .in_ack_event   = (void *)dctcp_update_alpha,
225     .cwnd_event = (void *)dctcp_cwnd_event,
226     .ssthresh   = (void *)dctcp_ssthresh,
227     .cong_avoid = (void *)tcp_reno_cong_avoid,
228     .undo_cwnd  = (void *)dctcp_cwnd_undo,
229     .set_state  = (void *)dctcp_state,
230     .flags      = TCP_CONG_NEEDS_ECN,
231     .name       = "bpf_dctcp",
232 };   

これがeBPF版の実装の一部になる。基本的にはnet/ipv4/tcp_dctcp.cのものと同じだが、微妙にeBPF用に修正が加わっている。最後にある構造体tcp_congestion_opsは輻輳制御関連の関数ポインタ等を格納したもの。違うのは221行のSECマクロ。これによりオブジェクトファイルにするときに「.struct_ops」セクションに配置される。

関数の実体はもっと前に定義されている。上にはdctcp_init関数の定義を示している。こちらも通常の実装に似ているが、SECマクロによって「struct_ops/関数名」セクションに配置される。また、BPF_PROGマクロ（tools/lib/bpf/bpf_tracing.h）で関数定義部分がラップされているが、細かいので詳細は割愛。あとストレージマップに関するコードが追加されているけど、これは何に使っているのかな。

 20 struct {
 21     __uint(type, BPF_MAP_TYPE_SK_STORAGE);
 22     __uint(map_flags, BPF_F_NO_PREALLOC);
 23     __type(key, int);
 24     __type(value, int);
 25 } sk_stg_map SEC(".maps");

マップの定義はここ。

で、そもそもこれはどうやって使うのかな。。