TCPは、エンドトゥーエンドで信頼性のあるデータ転送を行なうと同時に、フロー制御を行ないます。つまり、到達性に関して信頼性の無いIPパケット交換網(パケットは容易に失われます)上で、あるエンドから出たデータを確実に相手のエンドに届けます。同時に、高速な相手エンドにはその高速性を生かすようにデータ転送し、低速な相手エンドには相手のバッファがあふれないように速度調整を行ないます。またネットワークが混雑してパケットが消失した時(輻輳)、出力パケットを減らして輻輳を回避しようとします。
これはまるで、コミュニケーションに関して信頼性の無い人間関係網(言葉は容易に失われます)上で、ある上司が部下にタスクアサインをして確実に遂行させると同時に、仕事の速い部下にはその能力を生かすようにタスクアサインを行ない、仕事の遅い部下には相手の(能力)バッファがあふれないようにアサイン調整をするかのようです。また部下がタスクを納期内に終わらせなかった場合、次からそういうことが無いようにタスクアサインの量を抑制するかのようです。

TCPは現実的なプロトコルなので、過度な期待はせず、以下のような冷酷な仮定と性質を持っています(カッコ内は技術的な用語)。
- 完全に終わったという報告しか信用しない(選択的あるいは否定的な確認応答を返せない)
- 余力があるかどうかを、部下にしょっちゅう自己申告させる(スライディング・ウィンドウ)
- 余力があると言った奴でも、実績の無い奴は信用しない。しかし、可能な限り速く、能力一杯までタスクアサインする(スロースタート)
- 部下の仕事の速さを測定して、状況再確認のタイミングに生かす(RTTの測定とタイムアウトの計算)
- 納期に遅れた(タスクを落とした)奴の信用度は一気に落とす。しかし、タスクを落とさない、ぎりぎりの能力を速やかに見つける(輻輳回避アルゴリズム)

これはまるで、人間を信頼することをやめて、「信用できるのは数字だけ」を信条とするマネージャのためにあるかのようです。

人に仕事をアサインして遂行させることに例えて、TCPのフロー制御を説明したいと思います。
読む前の注意です。部下に例えられる受信側の能力は、直感的には受信バッファだと思うかもしれません。実際は、受信バッファと途中のネットワーク能力(帯域、遅延、輻輳状態)を合わせたものと思って読んでください。


* TCPは選択的あるいは否定的な確認応答を返せない
スティーブンス本で、TCPを一言で説明すると「選択的あるいは否定的な確認応答が返せないスライディング・ウィンドウ・プロトコルである」と言っています。それぐらい、TCPを特徴づける、TCPの現実主義的側面を示す特徴です(*注記1)。
TCP は信頼性を持ったストリーム転送を満たすために、受け取ったデータセグメント(バイト列)に対して確認応答(以下、ack)を返します。データセグメントはバイト単位で振られるシーケンス番号(以下、seq)を持ち、seqに対するackを返します。seq100で200バイト長のセグメントを受け取ると、100+200でseq300まで受け取ったというackを返します(ちなみにTCPは全二重なので、シーケンス番号は両方向で独立にあります)。

- seq100:200バイトセグメント ===>
- <=== ack300

「スライディング・ウィンドウ」で説明するようにTCPのフロー制御は、ackが返ってくるまで次のセグメントを送信しないアルゴリズム(スティーブンス本ではこれをストップ・アンド・ウェイト型と呼んでいます)ではありません。今、次のような3つのセグメントがそれぞのackを待たずに送信されたとします。

- seq100:200バイトセグメント
- seq300:200バイトセグメント
- seq500:200バイトセグメント

2 番目のセグメントだけがIP交換網上で消失したとします。TCP受信側は、3番目のセグメントを受け取っても、返すackは、seq100から200バイト受け取ったというack300だけです。seq300-seq499を取り落としたことを伝える術も無いですし、seq500-seq699を受け取っているという事実を伝える術もありません。

通信プロトコルの設計としては、かなり思い切った割り切りです。
ここから学ぶべき、タスクをアサインした部下に対する対処としては、次のようになるでしょう。

+ 終わったという報告以外は信用しない
++ 「順調です」や「予定通りです」、などの調子の良い途中経過は無視する
++ 何も報告が無いのは、できていないと判断する


「Jacobsonの高速再転送アルゴリズム」が次のように動作して、無意味な再送を防ぐこともあります。
- 受信側は、途中が抜けたseq500-seq699のようなセグメントを受け取ると、すぐにack300(1番目のセグメントに対するack)を返します。これは既に送信済みのackと同じなので重複ackと呼ばれます。seq700など、更に後続する受信セグメントを受信した時もすぐに重複ackを返します。
- 送信側は、1番目のセグメントに対する重複ackを連続して受け取ると、2番目のセグメントが落ちたと判断して、seq300:200バイトセグメントを再送します。この時、次に続くseq500:200バイトセグメントは再送しません。なぜなら、重複ackが後続するセグメントの到達を暗示しているからです(もちろん、その保証は無くて、重複ackは更に後続のseq700以降に対する重複ackかもしれませんが)
- seq500-seq699などの後続する受信セグメントは受信側のバッファに残っています。再送されたseq300:200バイトセグメントを受信すると、受信バッファ上で連結して、正しいackを返します。これにより、正しく受信できていた3番目のセグメントを再送してしまう無駄が防げます。


* スライディング・ウィンドウ
上に述べたように、TCPはackが返る前にも次のセグメントをどんどん送信します。
タスクアサインの例で言うと、週に1回しか部下の状況を確認できないケースを想像してください。1日で終わるタスクをアサインしても、週に1回の完了報告を受けるまで次のアサインをできないのでは効率が悪すぎます。当然、週1の完了報告を待つ前に後続するタスクアサインをするはずです。しかし、能力を越えるタスクアサインをして、「できませんでした」という報告は聞きたくないはずです。こういう状況でTCPはスライディング・ウィンドウアルゴリズムを使います(これはあくまで序章で、実際はいくつかのアルゴリズムを組み合わせます)。

送信側から見た受信側の能力は、受信バッファだけではなく、途中のネットワーク能力(帯域、遅延、輻輳状態)も合わせたものだと言いました。しかし、受信側が確実に分かるのは、自分の受信バッファの余力だけです。受信側は受信バッファの空き(オファード・ウィンドウ)を広告します(ウィンドウサイズはバイト単位です)。送信側はオファード・ウィンドウと送信済みセグメントサイズから、利用可能ウィンドウサイズを計算して、その上限まで送信しようとします。しかし、後で述べるように、上限はそんなに簡単には信用しません。一方、利用可能ウィンドウサイズを越えて送信することはありません。

ここから学ぶべき、タスクをアサインした部下に対する対処としては、次のようになるでしょう。
+ 余力があるかどうかを、部下にしょっちゅう自己申告させる
+ 余力があるという言葉は、半信半疑で聞く
+ 余力が無いという言葉は、信用する


* スロースタートアルゴリズム
上で、オファード・ウィンドウの上限はそんなに簡単に信用しないと書きました。
技術的には、受信側の広告するオファード・ウィンドウの値を信用していないわけではなく、送信側から見た受信側の能力が途中のネットワーク能力にも依存するためです。
このため、送信セグメントを一気に連続して送ることはしないで、徐々に増やしていきます。
後で述べる輻輳制御とも関連して、TCPのこの戦略を某教授は「ゆっくり増やして、急激に落とす」と表現していました。
スロースタートのため、送信側は輻輳ウィンドウ(cwnd:congestion window)と呼ばれる値を保持します。cwndを1に初期化して、最初に1セグメント送信し、ackが返るのを待ちます。ackが返るとcwndに+ 1して、次はackを待たずに2つのセグメントを送ります。2つの送信に対するackが返ると(ackはふたつかもしれないし、省略されて1つかもしれませんが、cwnd的には等価です)、cwndに+2して4とします。これで今度は4つまでackを待たずにセグメントを連続して送信します。こうして、送信側は、オファード・ウィンドウ値に達するまで、cwndを指数的に増加させます。
アルゴリズム的に言うと、送信セグメント数はMIN(cwnd, オファード・ウィンドウ値)となります。
後で述べる輻輳制御は、指数的な増加(スロースタート)と線形的な増加を組み合わせます。線形増加との比較で言うと指数増加は急峻です。スロースタートという呼び方とは裏腹に、実は結構、素早い立上りと言えます。

ここから学ぶべき、タスクをアサインした部下に対する対処としては、次のようになるでしょう。
+ 余力があると言う部下でも、実績の無い相手は信用しない
+ 徐々にタスクアサインを増やして様子を見る(能力を見極める)
+ のんびりしてはいられないので、タスクアサインの量は倍々で増やして、能力一杯を素早く見極める


* RTTの測定とタイムアウトの計算
ackが返らない場合、TCPはセグメントの再送を行なう必要があります。
しかし、ackが返らないこととackが遅いことを区別するのは簡単ではありません。それはネットワークの状態に依存するからです。
少なくとも、普通のackがどれぐらいの往復時間(RTT:round trip time)で返ってくるかを知らないと区別できません。
TCPはRTTを随時測定して(測定値:M)、次のような平滑化(smoothing)された評価値Rを算出して、再転送タイムアウト値RTOを算出します。

+ R <- 0.9 * R + 0.1 * M
+ RTO = 2 * R

このアルゴリズムの心は、測定値を10%ずつ荷重平均した往復時間Rを計算しつつ、安全係数2でタイムアウト値を推測したものです。安全係数を2で取っているあたりが、良く言えば現実的、悪く言えばいい加減なところもあるアルゴリズムです。

TCP の研究は凄い人達が時間をかけてやってきただけあって、改良版アルゴリズムもでています。理想的には分散が分かると、より精度の良いタイムアウト値を推測可能です。計算が複雑にならないように、平均偏差を用い、かつ2の累乗の整数演算で済むような次のアルゴリズムになっています。ErrはRTTの測定値M と平滑化RTTのAの差分です。Dは平滑化された平均偏差です。

+ Err = M - A
+ A <- A + (1/8) * Err
+ D <- D + (1/8) * (|Err| - D)
+ RTO = A + 4 * D

このアルゴリズムの心は、測定値のずれを1/8ずつ荷重平均した往復時間Aと、ずれの幅(偏差)を1/8ずつ荷重平均した平均偏差Dを求め、平均偏差の4倍以内にほとんどのRTTは収まるという仮定でタイムアウト値を推定したものです。

ここから学ぶべき、タスクをアサインした部下に対する対処としては、次のようになるでしょう。
+ 見積りのために、仕事の速さを測定して、平均値と偏差を常に荷重補正して知っておく
+ 嘘っぽくても、正規分布を描いて、平均値を中心に平均偏差の4倍の範囲に99%以上が収まることを示して、それを越えて報告が無い場合、遅れていると見なすと宣言する


* 輻輳回避アルゴリズム
輻輳とは、ネットワークが混雑してパケットが消失する事態です。こんな時、TCPが慌ててセグメントを再送すると、ますますネットワークが混雑して輻輳がひどくなることは容易に想像できるでしょう。
このため、TCPは輻輳を抑えるため、セグメントの送出を抑制します。しかし、どれぐらい抑制すれば良いかは自明ではありません。あまりにも保守的に抑えすぎると、ネットワークの能力を生かしきれません。あまりにも急峻に再送速度を上げすぎると、また輻輳を誘発しかねません。TCPは次のような輻輳回避アルゴリズムを使います。
送信側は、スロースタートで説明したcwnd(輻輳ウィンドウ)とスロースタート閾値(ssthresh:slow start threshold)のふたつの値を保持します。
輻輳が発生すると(タイムアウトもしくは重複ackの受信)、次のように動作します。

- MIN(cwnd, オファード・ウィンドウ値)の1/2をssthreshにセット
- 輻輳がタイムアウトで示されている場合、cwndを1に戻す
- cwndがssthreshより小さい場合、スロースタートと同じように指数関数的に送信セグメント数を増やす
- cwndがssthreshを越えた場合、送信セグメント数は線形に増やす

本に載っているグラフを見た方が分かりやすいのですが、このアルゴリズムの心は、現cwndの1/2を閾値として、そこまでは指数的に増やして、それ以降は線形に増やすという戦略です。
輻輳が起きたので、以前のcwndと同じだけのペースで送信を続けると、また起きるかもしれません。しかし、あまりゆっくり増やすのも保守的すぎます。そこで、以前の1/2のペースまでは急峻(指数的)に上げて、それ以降はゆっくり(線形)上げようというアルゴリズムです。

ここから学ぶべき、タスクをアサインした部下に対する対処としては、次のようになるでしょう。
+ 納期に遅れた(タスクを落とした)部下の信用度は一気に落とす
+ 以前できていた1/2ぐらいのところまではできると仮定してタスクアサインする
+ それ以上に負荷をかけるとまた裏切られる可能性があるので、徐々にアサインを増やして様子を見る


*注記1
最近の多くのOSは、SACK(Selective Acknowledgment Options)を実装しています。
http://www.faqs.org/rfcs/rfc2018.html