本記事は James Kurose, Keith Ross 著 Computer Networking: A Top-Down Approach (6th Edition) の教科書を基にまとめた内容です。

1. 信頼性のあるデータ転送とは

下位チャネル（ネットワーク層）が**信頼性がない**としても、上位層には**信頼性のある転送**を提供することが目標である。

アプリケーション層：「データは確実に届くはず」

↕ 信頼性のあるチャネル（抽象化）

トランスポート層(rdt)：信頼性を保証するプロトコル実装

↕ 信頼性のないチャネル（現実）

ネットワーク層： パケット損失、ビットエラーが発生する可能性

1.1 インタフェース

送信側：

rdt_send(data) ← 上位層がデータを渡す

udt_send(packet) ← 信頼性のないチャネルにパケット送信

受信側：

rdt_rcv(packet) ← 信頼性のないチャネルからパケット受信

deliver_data(data) ← 上位層にデータを渡す

2. 段階的なプロトコル構築

2.1 rdt 1.0：完璧なチャネル上の信頼性のある転送

仮定：下位チャネルが完璧（ビットエラーなし、パケット損失なし）

送信側FSM：

[待機] --rdt_send(data)-->

packet = make_pkt(data)

udt_send(packet)

-->[待機]

受信側FSM：

[待機] --rdt_rcv(packet)-->

data = extract(packet)

deliver_data(data)

-->[待機]

追加メカニズムは一切不要。現実にはこのようなチャネルは存在しない。

2.2 rdt 2.0：ビットエラーがあるチャネル

仮定：ビットエラー発生可能、パケット損失なし

必要なメカニズム

1. エラー検出：チェックサムでビットエラーを発見

2. フィードバック：受信者が送信者に結果を通知

- ACK（Acknowledgment）：「正しく受け取った」

- NAK（Negative Acknowledgment）：「エラー発生」

3. 再送：NAKを受け取ったらパケットを再送

このようなプロトコルを**ARQ（Automatic Repeat reQuest）**プロトコルと呼ぶ。

rdt 2.0の動作

送信側：

[データ待機] --rdt_send(data)-->

pkt = make_pkt(data, checksum)

udt_send(pkt)

-->[ACK/NAK待機]

[ACK/NAK待機] --rdt_rcv(pkt) && isACK(pkt)-->

-->[データ待機] （成功、次のデータ待機）

[ACK/NAK待機] --rdt_rcv(pkt) && isNAK(pkt)-->

udt_send(pkt) （再送）

-->[ACK/NAK待機]

受信側：

[待機] --rdt_rcv(pkt) && !corrupt(pkt)-->

deliver_data(extract(pkt))

udt_send(ACK)

-->[待機]

[待機] --rdt_rcv(pkt) && corrupt(pkt)-->

udt_send(NAK)

-->[待機]

rdt 2.0の致命的な欠陥

> **ACK/NAK自体にビットエラーが発生したら？**

送信者はACKを受け取ったのかNAKを受け取ったのか分からない！

2.3 rdt 2.1：シーケンス番号の導入

解決策：**シーケンス番号（sequence number）**を追加する。

解決戦略：

1. 破損したACK/NAKを受け取ったら現在のパケットを再送

2. 受信者はシーケンス番号で重複パケットを区別

3. 停止待機（stop-and-wait）プロトコルなので

シーケンス番号0と1で十分（1ビット）

rdt 2.1 送信側（簡略）：

[seq=0待機] --rdt_send(data)-->

pkt = make_pkt(0, data, checksum)

udt_send(pkt)

-->[ACK待機 for 0]

[ACK待機 for 0]

--ACK受信、正常--> [seq=1待機] （次のデータ）

--NAK受信または破損--> 再送 pkt [ACK待機 for 0]

[seq=1待機] ...（seq=0と対称）

rdt 2.1 受信側（簡略）：

[seq=0期待]

--pkt正常、seq=0--> deliver、ACK送信 → [seq=1期待]

--pkt正常、seq=1--> 重複！ACK送信 → [seq=0期待]（データ無視）

--pkt破損--> NAK送信 → [seq=0期待]

2.4 rdt 2.2：NAKなしプロトコル

NAKを使用せず、**前のパケットに対するACK**を送る方式である。

rdt 2.2の核心：

ACKにシーケンス番号を含む：ACK(0)、ACK(1)

受信者がseq=1パケットを期待しているのにseq=0パケットが到着：

→ ACK(0)送信（= 「seq=0までは受け取ったが、seq=1はまだ」）

→ 送信者の観点ではこれはNAKと同じ効果

送信者がseq=1パケットに対してACK(0)を受け取ったら：

→ 「seq=1が正しく届かなかった」→ 再送

2.5 rdt 3.0：ビットエラー + パケット損失

仮定：ビットエラー発生可能、**パケット損失も発生**可能

タイマーメカニズム

新しい問題：パケットが完全に消失したらどうするか？

- ACKが永遠に来ない

- 送信者が無限に待機

解決：タイマー（Timer）！

- パケット送信後にタイマー開始

- 合理的な時間内にACKが来なければ再送

- パケットが損失したのではなく遅延した場合？

→ 重複パケット発生 → シーケンス番号で処理（既に解決済み）

rdt 3.0のシナリオ

シナリオ1：パケット損失なし（正常）

送信者 受信者

|--pkt(0)-->|

|<--ACK(0)--|

|--pkt(1)-->|

|<--ACK(1)--|

シナリオ2：パケット損失

送信者 受信者

|--pkt(0)--> X（損失）

| タイマー満了

|--pkt(0)-->|（再送）

|<--ACK(0)--|

シナリオ3：ACK損失

送信者 受信者

|--pkt(0)-->|

| ACK(0) X （ACK損失）

| タイマー満了

|--pkt(0)-->|（再送、重複）

|<--ACK(0)--|（受信者は重複を無視）

シナリオ4：タイマーの早期満了

送信者 受信者

|--pkt(0)-->|

| タイマー満了（ACKがまだ移動中）

|--pkt(0)-->|（不要な再送）

|<--ACK(0)--|（元のACK到着）

|--pkt(1)-->|

|<--ACK(0)--|（重複pkt(0)に対するACK、無視）

|<--ACK(1)--|

3. 停止待機プロトコルの性能

rdt 3.0は正しく動作するが、性能が非常に悪い。

例：1 Gbpsリンク、RTT = 30ms、パケットサイズ = 8000 bits

伝送遅延：L/R = 8000 / 10^9 = 0.008ms = 8us

利用率（Utilization）：

U = (L/R) / (RTT + L/R)

= 0.008 / (30 + 0.008)

= 0.00027

= 0.027%

1 Gbpsリンクでの実際のスループット：

0.00027 * 1 Gbps = 267 kbps ← 極めて非効率的！

停止待機のタイムダイアグラム：

送信者 受信者

|─pkt─> |

| |

| （待機） |

| |

| <─ACK─|

|─pkt─> |

| |

...

大部分の時間をACK待ちで浪費！

4. パイプラインプロトコル

4.1 パイプライニングの概念

ACKを待たずに**複数のパケットを連続して送信**する。

停止待機： パイプライニング（ウィンドウ=3）：

|─pkt0─>| |─pkt0─>|

| 待機 | |─pkt1─>|

|<─ACK──| |─pkt2─>|

|─pkt1─>| |<─ACK0─|

| 待機 | |─pkt3─>|

|<─ACK──| |<─ACK1─|

|─pkt2─>| |<─ACK2─|

...

利用率3倍向上！

パイプライニングの結果

パイプライニングがもたらす変化：

1. シーケンス番号の範囲が拡大（1ビットでは不足）

2. 送受信バッファが必要（複数パケットの管理）

3. エラー処理方式の決定が必要：

├── Go-Back-N（GBN）

└── Selective Repeat（SR）

利用率計算（ウィンドウサイズ = W）：

U = W * (L/R) / (RTT + L/R)

W=3の例：

U = 3 * 0.008 / 30.008 = 0.0008 = 0.08%

（3倍向上、しかしまだ低い）

W=1000の例：

U = 1000 * 0.008 / 30.008 = 0.267 = 26.7%

（大幅に改善！）

4.2 Go-Back-N（GBN）

ウィンドウの概念

送信者のシーケンス番号空間：

[ACK済み][送信済み未ACK][使用可能][使用不可]

─────────|────────────────|──────────|────────

base nextseqnum base+N

ウィンドウサイズ = N

base：最も古い未確認パケット

nextseqnum：次に送信するパケット

GBN送信者のルール

GBN送信者：

1. 上位層からデータ要求時：

- ウィンドウに空きがあればパケット送信

- 満杯なら拒否（またはバッファリング）

2. タイマー管理：

- 最も古い未確認パケットに対して1つのタイマーを使用

- タイマー満了時にウィンドウ内の全未確認パケットを再送

3. ACK(n)受信時：

- n番までのすべてのパケットを確認（累積確認：cumulative ACK）

- base = n + 1に更新

GBN受信者のルール

GBN受信者（非常にシンプル）：

- 期待するシーケンス番号のパケットのみ受容

- 順序が合わないパケットはすべて破棄

- 最後に正常受信したパケットのACKを送信

GBNの動作例

ウィンドウサイズN=4、パケット2が損失：

送信者 受信者

|──pkt0──>| ← 受信、ACK(0)送信

|──pkt1──>| ← 受信、ACK(1)送信

|──pkt2──> X（損失）

|──pkt3──>| ← 順序不一致！破棄、ACK(1)再送

|──pkt4──>| ← 順序不一致！破棄、ACK(1)再送

|──pkt5──>| ← 順序不一致！破棄、ACK(1)再送

| |

|（タイマー満了：pkt2から再送）

|──pkt2──>| ← 受信、ACK(2)送信

|──pkt3──>| ← 受信、ACK(3)送信

|──pkt4──>| ← 受信、ACK(4)送信

|──pkt5──>| ← 受信、ACK(5)送信

GBNの欠点

- 1つのパケットエラーで**ウィンドウ全体を再送**（無駄）

- エラー率が高いとパイプラインが不要なパケットで埋まる

4.3 Selective Repeat（SR）

GBNとの違い

GBN：エラー発生時にウィンドウ全体を再送

SR：エラーが発生したパケットのみ選択的に再送

SRのウィンドウ

送信者ウィンドウ：

[ACK][ACK][未確認][ACK][未確認][使用可能]

─────────|────────────────────|─────────

base base+N

各パケットに対して個別タイマーを維持！

受信者ウィンドウ：

[受信][未受信][受信][未受信]

─────|───────────────────|

base base+N

順序が合わないパケットもバッファに保管！

SRの動作例

ウィンドウサイズN=4、パケット2が損失：

送信者 受信者

|──pkt0──>| ← 受信、ACK(0)送信、配信

|──pkt1──>| ← 受信、ACK(1)送信、配信

|──pkt2──> X（損失）

|──pkt3──>| ← 受信、ACK(3)送信、バッファに保管

|──pkt4──>| ← 受信、ACK(4)送信、バッファに保管

| |

|（pkt2タイマー満了、pkt2のみ再送）

|──pkt2──>| ← 受信、ACK(2)送信

| | pkt2、pkt3、pkt4を順番に上位に配信

SRのジレンマ：シーケンス番号の範囲

ウィンドウサイズとシーケンス番号範囲の関係：

シーケンス番号の範囲が小さすぎると

新しいパケットと再送パケットを区別できない！

ルール：シーケンス番号範囲 >= 2 * ウィンドウサイズ

（ウィンドウサイズNなら、シーケンス番号は最低2N個必要）

5. GBN vs Selective Repeat比較

| 基準 | Go-Back-N | Selective Repeat |

| ------------------ | --------------------- | -------------------------- |

| 再送範囲 | ウィンドウ全体 | 損失パケットのみ |

| 受信者バッファ | 不要 | 必要（順序外パケット保管） |

| タイマー | 1つ（最古のパケット） | パケット別個別タイマー |

| ACK方式 | 累積ACK | 個別ACK |

| 実装の複雑さ | シンプル | 複雑 |

| 効率性（エラー時） | 低い | 高い |

6. まとめ

信頼性のあるデータ転送メカニズムの発展：

rdt 1.0：完璧なチャネル → 何も必要なし

rdt 2.0：+ ビットエラー → チェックサム + ACK/NAK

rdt 2.1：+ ACK/NAKエラー → シーケンス番号

rdt 2.2：NAK除去 → 重複ACK活用

rdt 3.0：+ パケット損失 → タイマー

性能改善：

停止待機 → パイプライニング（GBNまたはSR）

核心メカニズムの要約：

├── チェックサム：ビットエラー検出

├── ACK：正常受信確認

├── シーケンス番号：重複パケット識別

├── タイマー：パケット損失への対応

└── パイプライニング：利用率向上

7. 確認問題

パケットが完全に損失すると受信者は何も受け取らないためACKも送らない。タイマーがなければ送信者はACKを永遠に待つことになる。タイマーを使用すれば、合理的な時間が経過してもACKが来ない時にパケットを**再送**できる。タイマーが早すぎに満了すると不要な再送が発生するが、シーケンス番号のおかげで受信者が重複を処理できる。

GBN受信者は**期待するシーケンス番号のパケットのみ受容**し、順序が合わないパケットはすべて破棄する（バッファリングなし）。したがって中間のパケットが損失するとその後のすべてのパケットも破棄される。送信者のタイマーが満了すると、最も古い未確認パケットからウィンドウ内のすべてのパケットを再送しなければならない。

シーケンス番号の範囲が十分に大きくないと、受信者が新しいパケットと再送されたパケットを区別できない。例えば、ウィンドウサイズが3でシーケンス番号が0、1、2しかない場合、すべてのACKが損失した状況で送信者が再送したパケット0を受信者が新しいパケット0と誤認する可能性がある。シーケンス番号が最低 `2N` あればこの混同を防げる。