前の記事では、UDPがチェックサムで損傷を検出するだけで、損失や順序の入れ替わりは解決しないことを整理しました。
それではファイル転送や決済リクエストのように、1つも欠けてはいけないデータはどのように信頼性を得るのでしょうか。
この記事では、データを失ったり壊したりしうる下位層の上に、
信頼性のあるデータ転送
(reliable data transfer, rdt)を作る原理を段階的に見ていきます。
TCPはこれらの原理を実際に実装しているので、ここで作る構造をTCPと比べながら読むと理解しやすくなります。
信頼性のある転送は、下のチャネルがデータを失ったり損傷させたりしうるという前提から始まります。
いちばん単純な場合から始め、チャネルの問題が1つ増えるたびにプロトコルを改良していきます。
チャネルがデータを失わず、変えもしないなら、送信側はデータを送るだけで十分です。
受信側は受け取ったデータをそのまま上位層に渡せばよいのです。
データがビット誤りで損傷しうるなら、まずチェックサムで損傷を検出する必要があります。
受信側は損傷のないデータを受け取ると
ACK
(肯定応答)を、損傷したデータを受け取ると
NAK
(否定応答)を送ります。
送信側はNAKを受け取ると、同じデータを送り直します。
問題は、ACKやNAK自体が損傷しうることです。
ACKが壊れて送信側が状況をつかめない場合は、どうすればよいのでしょうか。
送信側は、パケットごとに
0と
1のシーケンス番号を交互に付けます。
受信側は、すでに受け取った番号が再び届いたら重複と判断して破棄し、ACKだけを送り直します。
こうすれば、ACKが失われて再送されたパケットも重複として取り除けます。
ACKに最後に正しく受け取ったパケットの番号を入れておけば、NAKは不要になります。
損傷したパケットが届いたら、受信側は直前の番号のACKを送り直し、送信側はそのACKを見て同じパケットを再送します。
パケットがまるごと消えると、受信側は何も送らないため、送信側は永遠に待つことになります。
そこで送信側はパケットを送るときに
タイマー
を始動し、時間内にACKが来なければ再送します。
タイマーが短すぎると、まだ転送中のパケットまで再送されますが、シーケンス番号があるので受信側はその重複を取り除けます。
rdt 3.0は正しく動きますが、送信側は各ACKを待ってから次のパケットを送ります。
これを
stop-and-wait
(待機方式)と呼びます。
たとえば1 Gbpsのリンクで1,000バイトのパケットを送り、往復時間(RTT)が30 msだとします。
1つのパケットをリンクに送り出す時間
L/Rは、8,000ビット ÷ 1 Gbps = 8 µsです。
送信側の利用率は次のとおりです。
U = (L/R) / (RTT + L/R) = 0.008 ms / 30.008 ms ≈ 0.027%
1 Gbpsのリンクがあっても、送信側が使えるのは0.027%にすぎません。
残りの時間はすべてACKを待つことに使われます。
解決策は
パイプライン
(pipelining)です。各ACKを待たずに、複数のパケットを続けて送ります。
送信側は確認されていないパケットを最大
N個まで送ることができ、この範囲を
ウィンドウ
と呼びます。
U = N·(L/R) / (RTT + L/R)
同じ条件で
N = 1000にすると、利用率は約26.7%まで上がります。
この数値は損失がないと仮定した理論値です。
パイプラインを使うには、2つの判断が必要になります。
損失をどう扱うかと、順序が入れ替わって届いたパケットを受信側がどう扱うかです。
| 区分 | Go-Back-N | 選択的再送(Selective Repeat) |
|---|
| 確認応答 | 累積ACK(n まで受信済み) | パケットごとの個別ACK |
|---|
| タイマー | 最も古い未確認パケットに1つ | パケットごとに1つ |
|---|
| 再送の範囲 | タイムアウト時にウィンドウ全体 | 失われたパケットだけ |
|---|
| 受信側のバッファ | 不要。順序どおりにだけ受け取る | 順序の乱れたパケットをバッファリング |
|---|
Go-Back-N
は受信側を単純に保てますが、1つのパケットが失われると、その後に正しく届いたパケットも破棄され、ウィンドウ全体を送り直す必要があります。
選択的再送
は失われたパケットだけを再送するので帯域を節約できますが、受信側は順序の乱れたパケットを保存しておかなければなりません。

パイプライン方式の送信側がウィンドウ内の複数のパケットを連続して送り、受信側が累積確認応答を返す流れ
👨💻
TCPは、シーケンス番号、累積ACK、タイマーを組み合わせてこの原理を実装しています。
そのため、TCP接続で再送が多いように見えるときは、損失が起きているかどうかと、タイマーがどれくらいの長さに設定されているかを確認してみてください。
Node.jsで損失がある状況の再送を確かめる 🔗
次の例では、stop-and-waitの方式をUDP上で実装しています。
受信側はデータグラムの30%をわざと破棄し、損失を再現しています。
rdt-stop-and-wait.mjsimport dgram from "node:dgram";
const PORT = 7171;
const messages = ["m0", "m1", "m2", "m3", "m4"];
const server = dgram.createSocket("udp4");
const received = [];
let expected = 0;
server.on("message", (buf, rinfo) => {
if (Math.random() < 0.3) {
console.log(` [net] drop seq=${buf[0]}`);
return;
}
const seq = buf[0];
if (seq === expected) {
received.push(buf.subarray(1).toString());
expected = 1 - expected;
}
server.send(Buffer.from([seq]), rinfo.port, rinfo.address);
});
const client = dgram.createSocket("udp4");
let seq = 0;
let i = 0;
let timer;
function sendCurrent() {
const payload = Buffer.concat([Buffer.from([seq]), Buffer.from(messages[i])]);
client.send(payload, PORT, "127.0.0.1");
timer = setTimeout(() => {
console.log(` timeout, retransmit seq=${seq}`);
sendCurrent();
}, 100);
}
client.on("message", (ack) => {
if (ack[0] !== seq) return;
clearTimeout(timer);
console.log(`ack seq=${seq} for ${messages[i]}`);
i++;
seq = 1 - seq;
if (i < messages.length) {
sendCurrent();
} else {
console.log("received:", received);
client.close();
server.close();
}
});
server.bind(PORT, () => sendCurrent());
実行するたびに損失が起きる場所が変わるので、再送の回数も実行ごとに変わります。
それでも最後の
receivedの行には、常に
m0から
m4までが順番どおりに入ります。
シーケンス番号、ACK、タイマーだけで、順序を保ったまま損失に耐えられることがわかります。
ただし、この例はデータの損失だけを再現しており、ACKの損失は扱っていません。
信頼性のあるデータ転送は、
シーケンス番号で重複と順序を見分け、確認応答で受信を知らせ、タイマーで損失から回復する
という3つの道具で作られます。
そのままでは、stop-and-waitはリンクの容量のごく一部しか使えないため、パイプラインでウィンドウを使って複数のパケットを送る必要があります。
Go-Back-Nは実装が単純で、選択的再送は帯域を節約します。どちらを選ぶかは、損失率と受信側のバッファの余裕によって決まります。