6.4 NagleアルゴリズムとCORKアルゴリズム
6.4.1アルゴリズムの目的
送信側アプリケーションプロセスがデータを生成するのが遅い(例えばTelnetアプリケーション)場合、アプリケーションプロセス間で伝送されるTCPペイロードは小さく(1バイトしかないかもしれない)、伝送オーバーヘッドが40バイト(20バイトのIPヘッダ+20バイトのTCPヘッダ)の現象をペーストウィンドウ症候群(Silly Windw Syndrome)と呼ぶ.大量の小さなTCPメッセージがネットワークで送信されると、ネットワークが混雑します.Nagleアルゴリズムは,TCPデータ送信側の「ボケウィンドウ症候群」を解決するために生成される.
6.4.2アルゴリズムの原理
Nagleアルゴリズムは、送信バッファ内の一定数のメッセージを自動的に接続し(この処理プロセスをNaglingと呼ぶ)、送信しなければならないパケットの数を減らすことで、ネットワークアプリケーションシステムの効率を向上させ、ネットワークの混雑を緩和する.CORKとは栓のことで、CORKで接続を塞いでデータを出さずに栓を抜いてから出すというイメージです.このオプションを設定すると、カーネルはできるだけ小さなパケットを大きなパケット(MTU)につなぎ合わせて送信します.
NagleアルゴリズムはCORKアルゴリズムと非常に類似しているが,それらの着目点は異なり,Nagleアルゴリズムは主にネットワークが小さなパケット(プロトコルヘッダの割合が非常に大きい)のために混雑することを回避し,CORKアルゴリズムはネットワークの利用率を向上させ,全体的に合意ヘッダが占有する割合をできるだけ小さくするためである.しかし、どちらも小包の送信を避ける点で一致しています.またLinuxの実装ではNagleとCORKも結合している.しかしNagleアルゴリズムが関心を持っているのはネットワークの混雑問題であり、すべてのACKが戻ってくると発注するが、CORKアルゴリズムは内容に関心を持つことができ、前後のパケット送信間隔が短いことを前提に(そうでなければカーネルが分散したパケットを発行してくれる)、複数の小さなパケットを分散して送信しても、CORKアルゴリズムを1つのパケットにつなぐことができる.このときNagleアルゴリズムを使うと、それができないかもしれません.
6.4.3カーネル実装
前述したように、TCPは、データ送信時にtcp_を呼び出すwrite_xmit関数、Nagleアルゴリズムはtcp_write_xmitには「レベル」:tcp_が設定されています.nagle_test:
tcp_nagle_testはゲートのようなもので,Nagleアルゴリズムの意思に基づいてTCPメッセージの送信を制御している.どうやって作ったか見てみましょう
1461:tp->packets_out非0は、メッセージが送信されたが確認されていないことを意味する.tcp_minshall_checkが偽であることはsnd_を意味するmsl <= snd_una(snd_mslがsnd_nxtより大きいはずがない)、すなわち、送信された最新の小報文セグメントが確認された.tp->packets_out && tcp_minshall_check(tp)は、本当に送信されたが確認されていない小さなメッセージを意味する.Nonagleのタイプは次のとおりです.
ここでnonagelの値はTCPではないに違いない.NAGLE_PUSH(そうでなければ1477行で戻る)もTCPではありません.NAGLE_CORK、さもなくば1460行為は本当に1461行は行けません;だからnonagelは0かTCPかNAGLE_OFF
コード上、Nagleアルゴリズムは、以下の基準のいずれかを満たすようにデータを送信することを許可する.
(1)nonagleにTCPが設定されているNAGLE_PUSHマーク
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)tcp_nagle_チェック
まず(4)を見てみましょう.tcp_nagle_checkが偽である1459-1461行の論理が偽で成立する条件は、以下のいずれかである.
1)データ長がMSS以上である
2)nonagleにTCPが設定されていないNAGLE_CORKタグかつnonagleにTCP_があるNAGLE_OFFフラグ(nonagel==TCP_NAGLE_OFFが真)
3)nonagle==0は真で未確認のメッセージはありません
この3つの条件を(4)と置換して,新しいNagleアルゴリズムがデータの送信を可能にする条件を得た.
(1)nonagleにTCPが設定されているNAGLE_PUSHマーク
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)データ長がMSS以上
(5)nonagle == TCP_NAGLE_OFFが真
(6)nonagle==0が真で未確認のメッセージがない
(1)満足のいく状況を見る.nonagleはtcp_からwrite_xmit関数のnonagleパラメータが入力されます.tcp_sendmsg関数におけるtcp_write_xmit関数の呼び出しはtcp_を使用したことがあるpushシリーズ関数が完了しました:
1204-1206:forced_Pushの機能は、メッセージを外部にプッシュできるかどうかを確認することです.
1207:現在書き込まれているskbが送信するヘッダパケットである場合、この条件は真である.tcp_send_ヘッドポインタの設定はskb_Entailで完了し、skbを呼び出すには、新しい申請のskbでなければなりません.entailは送信キューに参加します.これは、現在のskbより前のすべてのskbがすべて送信されたことを意味する.
1213:メモリが不足している場合、確認を受けたときに送信キャッシュのスペースを空けるためにデータを送信する必要がある
tcp_sendmsgの1026,1028,1215,1226行には4回の送信データがあり,そのうち3回にTCP_がある.NAGLE_PUSHタグですが、このとき送信されるのはMSSいっぱいの大きなパッケージです.1226行の呼び出しにはtp->nonagleのタグが使用されますが、tcp_sendmsgはskb_を呼び出しますentail関数TCP除去_NAGLE_PUSHタグ:
tcp以外はsendmsg関数のほか、TCP_を設定NAGLE_PUSHタグのコードとsetsockoptシステム呼び出し:
1)TCP_の使用NODELAY SOcketオプションNagleアルゴリズムを閉じる場合(この場合条件(5)が成立)
2)TCP_の使用CORKソケットオプション「プラグ抜き」でNagleアルゴリズムがオフになっている場合
条件(1)の成立は、上記2つの条件のいずれかの成立に等しい.
条件(5)を成立させるもう一つの点は,TCPロスプローブタイマがタイムアウトしたときである.このタイマータイムアウトの関数はtcp_ですsend_loss_probe:
条件(6)を見てみましょう.nonagle==0は真の意味:
1)TCPなしNAGLE_OFFフラグ(つまりNagleアルゴリズムをオフにしていない)
2)TCPなしNAGLE_CORKタグ(つまりTCP_CORKアルゴリズムがオンになっていない)
3)TCPなしNAGLE_PUSHマーク(すなわち条件(1)は成立せず、1)が成立すると条件(1)は成立しない)
この3つの条件は同時に成立する.
以下、最新の結論に基づいて、Nagleアルゴリズムがデータの送信を許可する条件を更新する.
(1)TCP_の使用NODELAYソケットオプションNagleアルゴリズムを閉じる場合
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)データ長がMSS以上
(5)TCP_の使用CORKソケットオプション「プラグ抜き」でNagleアルゴリズムがオフになっている場合
(6)Nagleアルゴリズムを閉じることもTCPを開くこともない.CORKアルゴリズム、未確認のメッセージなし
(7)上記条件はいずれも満たされていないがタイマタイムアウト
上記の条件から分かるように、通常(Nagleアルゴリズムを閉じず、大量の小メッセージを送信し、タイマがタイムアウトしていない)では、Nagleアルゴリズムは、小メッセージが蓄積された送信キューに大きな送信を綴り、小データの送信を低減する.エンドACKへの応答が速ければ(条件(6)が成立する),Nagleアルゴリズムは混雑がなければパケットを多くつなぎ合わせることができず,ネットワークの混雑を招くことはないかもしれないが,ネットワーク全体の利用率は依然として低いと考えられる.
送信側アプリケーションプロセスがデータを生成するのが遅い(例えばTelnetアプリケーション)場合、アプリケーションプロセス間で伝送されるTCPペイロードは小さく(1バイトしかないかもしれない)、伝送オーバーヘッドが40バイト(20バイトのIPヘッダ+20バイトのTCPヘッダ)の現象をペーストウィンドウ症候群(Silly Windw Syndrome)と呼ぶ.大量の小さなTCPメッセージがネットワークで送信されると、ネットワークが混雑します.Nagleアルゴリズムは,TCPデータ送信側の「ボケウィンドウ症候群」を解決するために生成される.
6.4.2アルゴリズムの原理
Nagleアルゴリズムは、送信バッファ内の一定数のメッセージを自動的に接続し(この処理プロセスをNaglingと呼ぶ)、送信しなければならないパケットの数を減らすことで、ネットワークアプリケーションシステムの効率を向上させ、ネットワークの混雑を緩和する.CORKとは栓のことで、CORKで接続を塞いでデータを出さずに栓を抜いてから出すというイメージです.このオプションを設定すると、カーネルはできるだけ小さなパケットを大きなパケット(MTU)につなぎ合わせて送信します.
NagleアルゴリズムはCORKアルゴリズムと非常に類似しているが,それらの着目点は異なり,Nagleアルゴリズムは主にネットワークが小さなパケット(プロトコルヘッダの割合が非常に大きい)のために混雑することを回避し,CORKアルゴリズムはネットワークの利用率を向上させ,全体的に合意ヘッダが占有する割合をできるだけ小さくするためである.しかし、どちらも小包の送信を避ける点で一致しています.またLinuxの実装ではNagleとCORKも結合している.しかしNagleアルゴリズムが関心を持っているのはネットワークの混雑問題であり、すべてのACKが戻ってくると発注するが、CORKアルゴリズムは内容に関心を持つことができ、前後のパケット送信間隔が短いことを前提に(そうでなければカーネルが分散したパケットを発行してくれる)、複数の小さなパケットを分散して送信しても、CORKアルゴリズムを1つのパケットにつなぐことができる.このときNagleアルゴリズムを使うと、それができないかもしれません.
6.4.3カーネル実装
前述したように、TCPは、データ送信時にtcp_を呼び出すwrite_xmit関数、Nagleアルゴリズムはtcp_write_xmitには「レベル」:tcp_が設定されています.nagle_test:
1811 static bool tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle,
1812 int push_one, gfp_t gfp)
1813 {
...
1854 if (tso_segs == 1) { //
1855 if (unlikely(!tcp_nagle_test(tp, skb, mss_now,
1856 (tcp_skb_is_last(sk, skb) ?
1857 nonagle : TCP_NAGLE_PUSH))))
1858 break; //Nagle ，
...
1893 tcp_minshall_update(tp, mss_now, skb);
...
tcp_nagle_testはゲートのようなもので,Nagleアルゴリズムの意思に基づいてTCPメッセージの送信を制御している.どうやって作ったか見てみましょう
1442 static inline bool tcp_minshall_check(const struct tcp_sock *tp)
1443 {
1444 return after(tp->snd_sml, tp->snd_una) &&
1445 !after(tp->snd_sml, tp->snd_nxt); //snd_una < snd_sml <= snd_nxt
1446 }
1447
1448 /* Return false, if packet can be sent now without violation Nagle's rules:
1449 * 1. It is full sized.
1450 * 2. Or it contains FIN. (already checked by caller)
1451 * 3. Or TCP_CORK is not set, and TCP_NODELAY is set.
1452 * 4. Or TCP_CORK is not set, and all sent packets are ACKed.
1453 * With Minshall's modification: all sent small packets are ACKed.
1454 */
1455 static inline bool tcp_nagle_check(const struct tcp_sock *tp,
1456 const struct sk_buff *skb,
1457 unsigned int mss_now, int nonagle)
1458 {
1459 return skb->len < mss_now && // MSS
1460 ((nonagle & TCP_NAGLE_CORK) || // TCP_NAGLE_CORK
1461 (!nonagle && tp->packets_out && tcp_minshall_check(tp)));
1462 }
1463
1464 /* Return true if the Nagle test allows this packet to be
1465 * sent now.
1466 */
1467 static inline bool tcp_nagle_test(const struct tcp_sock *tp, const struct sk_buff *skb,
1468 unsigned int cur_mss, int nonagle)
1469 {
1470 /* Nagle rule does not apply to frames, which sit in the middle of the
1471 * write_queue (they have no chances to get new data).
1472 *
1473 * This is implemented in the callers, where they modify the 'nonagle'
1474 * argument based upon the location of SKB in the send queue.
1475 */
1476 if (nonagle & TCP_NAGLE_PUSH) // TCP_NAGLE_PUSH
1477 return true; //
1478
1479 /* Don't use the nagle rule for urgent data (or for the final FIN). */
1480 if (tcp_urg_mode(tp) || (TCP_SKB_CB(skb)->tcp_flags & TCPHDR_FIN))
1481 return true; //
1482
1483 if (!tcp_nagle_check(tp, skb, cur_mss, nonagle))
1484 return true; //
1485
1486 return false; //
1487 }1461:tp->packets_out非0は、メッセージが送信されたが確認されていないことを意味する.tcp_minshall_checkが偽であることはsnd_を意味するmsl <= snd_una(snd_mslがsnd_nxtより大きいはずがない)、すなわち、送信された最新の小報文セグメントが確認された.tp->packets_out && tcp_minshall_check(tp)は、本当に送信されたが確認されていない小さなメッセージを意味する.Nonagleのタイプは次のとおりです.
214 #define TCP_NAGLE_OFF 1 /* Nagle's algo is disabled */
215 #define TCP_NAGLE_CORK 2 /* Socket is corked */
216 #define TCP_NAGLE_PUSH 4 /* Cork is overridden for already queued data */ここでnonagelの値はTCPではないに違いない.NAGLE_PUSH(そうでなければ1477行で戻る)もTCPではありません.NAGLE_CORK、さもなくば1460行為は本当に1461行は行けません;だからnonagelは0かTCPかNAGLE_OFF
コード上、Nagleアルゴリズムは、以下の基準のいずれかを満たすようにデータを送信することを許可する.
(1)nonagleにTCPが設定されているNAGLE_PUSHマーク
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)tcp_nagle_チェック
まず(4)を見てみましょう.tcp_nagle_checkが偽である1459-1461行の論理が偽で成立する条件は、以下のいずれかである.
1)データ長がMSS以上である
2)nonagleにTCPが設定されていないNAGLE_CORKタグかつnonagleにTCP_があるNAGLE_OFFフラグ(nonagel==TCP_NAGLE_OFFが真)
3)nonagle==0は真で未確認のメッセージはありません
この3つの条件を(4)と置換して,新しいNagleアルゴリズムがデータの送信を可能にする条件を得た.
(1)nonagleにTCPが設定されているNAGLE_PUSHマーク
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)データ長がMSS以上
(5)nonagle == TCP_NAGLE_OFFが真
(6)nonagle==0が真で未確認のメッセージがない
(1)満足のいく状況を見る.nonagleはtcp_からwrite_xmit関数のnonagleパラメータが入力されます.tcp_sendmsg関数におけるtcp_write_xmit関数の呼び出しはtcp_を使用したことがあるpushシリーズ関数が完了しました:
1016 int tcp_sendmsg(struct kiocb *iocb, struct sock *sk, struct msghdr *msg,
1017 size_t size)
1018 {
...
1099 skb = tcp_write_queue_tail(sk); // skb
1100 if (tcp_send_head(sk)) { //skb
1101 if (skb->ip_summed == CHECKSUM_NONE)
1102 max = mss_now;
1103 copy = max - skb->len;
1104 }
1105
1106 if (copy <= 0) { //
1107 new_segment:
1108 /* Allocate new segment. If the interface is SG,
1109 * allocate skb fitting to single page.
1110 */
1111 if (!sk_stream_memory_free(sk))
1112 goto wait_for_sndbuf;
1113
1114 skb = sk_stream_alloc_skb(sk,
1115 select_size(sk, sg),
1116 sk->sk_allocation); //
1117 if (!skb)
1118 goto wait_for_memory;
...
1201 if (skb->len < max || (flags & MSG_OOB) || unlikely(tp->repair))
1202 continue;
1203 // MSS skb
1204 if (forced_push(tp)) { // forced_push
1205 tcp_mark_push(tp, skb);
1206 __tcp_push_pending_frames(sk, mss_now, TCP_NAGLE_PUSH);// tcp_write_xmit TCP_NAGLE_PUSH
1207 } else if (skb == tcp_send_head(sk)) //
1208 tcp_push_one(sk, mss_now); // tcp_write_xmit TCP_NAGLE_PUSH
1209 continue;
1210
1211 wait_for_sndbuf:
1212 set_bit(SOCK_NOSPACE, &sk->sk_socket->flags);
1213 wait_for_memory: //
1214 if (copied)
1215 tcp_push(sk, flags & ~MSG_MORE, mss_now, TCP_NAGLE_PUSH);// tcp_write_xmit TCP_NAGLE_PUSH
...
1223
1224 out:
1225 if (copied)
1226 tcp_push(sk, flags, mss_now, tp->nonagle); // TCP_NAGLE_PUSH tcp_write_xmit
...1204-1206:forced_Pushの機能は、メッセージを外部にプッシュできるかどうかを確認することです.
585 static inline void tcp_mark_push(struct tcp_sock *tp, struct sk_buff *skb)
586 {
587 TCP_SKB_CB(skb)->tcp_flags |= TCPHDR_PSH;
588 tp->pushed_seq = tp->write_seq;
589 }
590
591 static inline bool forced_push(const struct tcp_sock *tp)
592 {
593 return after(tp->write_seq, tp->pushed_seq + (tp->max_window >> 1));
594 }1207:現在書き込まれているskbが送信するヘッダパケットである場合、この条件は真である.tcp_send_ヘッドポインタの設定はskb_Entailで完了し、skbを呼び出すには、新しい申請のskbでなければなりません.entailは送信キューに参加します.これは、現在のskbより前のすべてのskbがすべて送信されたことを意味する.
1213:メモリが不足している場合、確認を受けたときに送信キャッシュのスペースを空けるためにデータを送信する必要がある
tcp_sendmsgの1026,1028,1215,1226行には4回の送信データがあり,そのうち3回にTCP_がある.NAGLE_PUSHタグですが、このとき送信されるのはMSSいっぱいの大きなパッケージです.1226行の呼び出しにはtp->nonagleのタグが使用されますが、tcp_sendmsgはskb_を呼び出しますentail関数TCP除去_NAGLE_PUSHタグ:
596 static inline void skb_entail(struct sock *sk, struct sk_buff *skb)
597 {
598 struct tcp_sock *tp = tcp_sk(sk);
599 struct tcp_skb_cb *tcb = TCP_SKB_CB(skb);
600
601 skb->csum = 0;
602 tcb->seq = tcb->end_seq = tp->write_seq;
603 tcb->tcp_flags = TCPHDR_ACK;
604 tcb->sacked = 0;
605 skb_header_release(skb);
606 tcp_add_write_queue_tail(sk, skb);
607 sk->sk_wmem_queued += skb->truesize;
608 sk_mem_charge(sk, skb->truesize);
609 if (tp->nonagle & TCP_NAGLE_PUSH)
610 tp->nonagle &= ~TCP_NAGLE_PUSH;
611 } 619 static inline void tcp_push(struct sock *sk, int flags, int mss_now,
620 int nonagle)
621 {
622 if (tcp_send_head(sk)) {
623 struct tcp_sock *tp = tcp_sk(sk);
624
625 if (!(flags & MSG_MORE) || forced_push(tp))
626 tcp_mark_push(tp, tcp_write_queue_tail(sk));
627
628 tcp_mark_urg(tp, flags);
629 __tcp_push_pending_frames(sk, mss_now,
630 (flags & MSG_MORE) ? TCP_NAGLE_CORK : nonagle);
631 }
632 }tcp以外はsendmsg関数のほか、TCP_を設定NAGLE_PUSHタグのコードとsetsockoptシステム呼び出し:
2371 static int do_tcp_setsockopt(struct sock *sk, int level,
2372 int optname, char __user *optval, unsigned int optlen)
2373 {
...
2423 case TCP_NODELAY:
2424 if (val) {
2425 /* TCP_NODELAY is weaker than TCP_CORK, so that
2426 * this option on corked socket is remembered, but
2427 * it is not activated until cork is cleared.
2428 *
2429 * However, when TCP_NODELAY is set we make
2430 * an explicit push, which overrides even TCP_CORK
2431 * for currently queued segments.
2432 */
2433 tp->nonagle |= TCP_NAGLE_OFF|TCP_NAGLE_PUSH;
2434 tcp_push_pending_frames(sk); // tp->nonagle tcp_write_xmit
...
2503 case TCP_CORK:
2504 /* When set indicates to always queue non-full frames.
2505 * Later the user clears this option and we transmit
2506 * any pending partial frames in the queue. This is
2507 * meant to be used alongside sendfile() to get properly
2508 * filled frames when the user (for example) must write
2509 * out headers with a write() call first and then use
2510 * sendfile to send out the data parts.
2511 *
2512 * TCP_CORK can be set together with TCP_NODELAY and it is
2513 * stronger than TCP_NODELAY.
2514 */
2515 if (val) {
2516 tp->nonagle |= TCP_NAGLE_CORK;
2517 } else {
2518 tp->nonagle &= ~TCP_NAGLE_CORK;
2519 if (tp->nonagle&TCP_NAGLE_OFF)
2520 tp->nonagle |= TCP_NAGLE_PUSH;
2521 tcp_push_pending_frames(sk);
2522 }
1)TCP_の使用NODELAY SOcketオプションNagleアルゴリズムを閉じる場合(この場合条件(5)が成立)
2)TCP_の使用CORKソケットオプション「プラグ抜き」でNagleアルゴリズムがオフになっている場合
条件(1)の成立は、上記2つの条件のいずれかの成立に等しい.
条件(5)を成立させるもう一つの点は,TCPロスプローブタイマがタイムアウトしたときである.このタイマータイムアウトの関数はtcp_ですsend_loss_probe:
1974 void tcp_send_loss_probe(struct sock *sk)
1975 {
1976 struct tcp_sock *tp = tcp_sk(sk);
1977 struct sk_buff *skb;
1978 int pcount;
1979 int mss = tcp_current_mss(sk);
1980 int err = -1;
1981
1982 if (tcp_send_head(sk) != NULL) {
1983 err = tcp_write_xmit(sk, mss, TCP_NAGLE_OFF, 2, GFP_ATOMIC);
1984 goto rearm_timer;
1985 }条件(6)を見てみましょう.nonagle==0は真の意味:
1)TCPなしNAGLE_OFFフラグ(つまりNagleアルゴリズムをオフにしていない)
2)TCPなしNAGLE_CORKタグ(つまりTCP_CORKアルゴリズムがオンになっていない)
3)TCPなしNAGLE_PUSHマーク(すなわち条件(1)は成立せず、1)が成立すると条件(1)は成立しない)
この3つの条件は同時に成立する.
以下、最新の結論に基づいて、Nagleアルゴリズムがデータの送信を許可する条件を更新する.
(1)TCP_の使用NODELAYソケットオプションNagleアルゴリズムを閉じる場合
(2)TCPが非常モード(緊急データあり)
(3)メッセージにFINマークがある
(4)データ長がMSS以上
(5)TCP_の使用CORKソケットオプション「プラグ抜き」でNagleアルゴリズムがオフになっている場合
(6)Nagleアルゴリズムを閉じることもTCPを開くこともない.CORKアルゴリズム、未確認のメッセージなし
(7)上記条件はいずれも満たされていないがタイマタイムアウト
上記の条件から分かるように、通常(Nagleアルゴリズムを閉じず、大量の小メッセージを送信し、タイマがタイムアウトしていない)では、Nagleアルゴリズムは、小メッセージが蓄積された送信キューに大きな送信を綴り、小データの送信を低減する.エンドACKへの応答が速ければ(条件(6)が成立する),Nagleアルゴリズムは混雑がなければパケットを多くつなぎ合わせることができず,ネットワークの混雑を招くことはないかもしれないが,ネットワーク全体の利用率は依然として低いと考えられる.