リンク層：エラー検出と多重アクセスプロトコル
リンク層（Link Layer）は、隣接する2つのノード間でフレームを安全に転送する役割を担います。ネットワーク層がホスト間のパケット転送を担当するのに対し、リンク層は1ホップ（hop）単位の通信を担当します。
この記事では、リンク層のサービス、エラー検出技法、そして共有メディアにおける多重アクセス（Multiple Access）プロトコルを見ていきます。
1. リンク層サービス
1.1 基本サービス
リンク層が提供するサービス
============================
1. フレーミング（Framing）
- ネットワーク層データグラムをフレームにカプセル化
- フレームヘッダにMACアドレスを含む
2. リンクアクセス（Link Access）
- 共有メディアでのアクセス制御（多重アクセスプロトコル）
- MACアドレスを使用したフレーム転送
3. 信頼性のある配送（Reliable Delivery）
- エラー率の高いリンク（無線）でARQを使用
- 有線リンクでは通常使用しない
4. エラー検出および訂正
- ビットエラー検出：パリティ、CRCなど
- エラー訂正：FEC（Forward Error Correction）
1.2 実装場所
リンク層は主に**NIC（Network Interface Card）**に実装されます。NICのハードウェアチップがフレーミング、CRC計算、MACプロトコルなどを処理します。
リンク層の実装
================
[アプリケーション層]
[トランスポート層] CPU / ソフトウェア
[ネットワーク層]
-----------------------
[リンク層] NIC（ハードウェア + ファームウェア）
[物理層]
2. エラー検出技法
2.1 パリティビット（Parity Bit）
最も単純なエラー検出方法で、データビットにパリティビット1つを追加します。
単一パリティビット（偶数パリティ）
====================================
データ： 1011010
パリティビット：0（1の数が偶数になるように）
送信： 10110100
受信： 10110110（5番目のビットにエラー）
1の数： 5（奇数）--> エラー検出！
限界：偶数個のビットが同時にエラーになると検出不可
**2次元パリティ**：行と列の両方にパリティビットを追加することで、単一ビットエラーを訂正することも可能です。
2次元パリティ
===============
データ + 行パリティ：
1 0 1 1 | 1
0 1 1 0 | 0
1 1 0 1 | 1
----------
0 0 0 0 （列パリティ）
エラー発生：
1 0 1 1 | 1
0 1 0 0 | 0 <-- 行パリティ不一致
1 1 0 1 | 1
----------
0 0 1 0 <-- 列パリティ不一致
^
3列目、2行目 --> エラー位置を特定し訂正可能
2.2 インターネットチェックサム（Internet Checksum）
トランスポート層（TCP、UDP）で使用される簡単なエラー検出方法です。
インターネットチェックサム計算
================================
1. データを16ビットワード単位で分割
2. すべてのワードを1の補数加算
3. 結果の1の補数をチェックサムとして使用
例：
ワード1：0110 0110 0110 0000
ワード2：0101 0101 0101 0101
-------------------------
合計： 1011 1011 1011 0101
チェックサム：0100 0100 0100 1010（1の補数）
検証：受信側でチェックサムを含むすべてのワードを加算すると
結果が 1111 1111 1111 1111 であること
2.3 CRC（Cyclic Redundancy Check）
CRCはリンク層で最も広く使用される強力なエラー検出方法です。多項式除算に基づいています。
CRC計算過程
=============
1. 生成多項式Gを決定（送信者と受信者が共有）
例：G = 1001 (x^3 + 1), r = 3ビット
2. データDにr個の0を付加
D = 101110, D * 2^r = 101110 000
3. D * 2^rをGでXOR除算して余りRを求める
101110 000 / 1001
----------------
101110 000
XOR 1001
--------
0101 10 000
XOR 1001
--------
0000 1000 0
XOR 1001
------
0001 0
余り R = 011
4. 送信ビット：DとRを連結 = 101110 011
5. 受信側：受信ビットをGで割って余り = 0ならエラーなし
2.4 CRCのエラー検出能力
CRCの強力な検出能力
======================
rビットCRCで検出可能なエラー：
- すべての単一ビットエラー
- すべての2ビットエラー（適切なG選択時）
- 奇数個のビットエラー（Gがx+1を因数として含む場合）
- rビット以下の連続エラー（バーストエラー）
標準CRC多項式：
CRC-8: x^8 + x^2 + x + 1
CRC-16: x^16 + x^15 + x^2 + 1
CRC-32: イーサネット、WiFi、ZIPなどで使用
32ビットの余りで非常に強力な検出
3. 多重アクセスプロトコル
複数のノードが1つの共有ブロードキャストリンクを使用する場合、同時送信による衝突（collision）を解決する必要があります。
3.1 分類
多重アクセスプロトコルの分類
==============================
1. チャネル分割（Channel Partitioning）
- TDMA、FDMA、CDMA
- 衝突なしだが非効率的
2. ランダムアクセス（Random Access）
- ALOHA、Slotted ALOHA、CSMA、CSMA/CD
- 衝突を許容、検出・回復メカニズム
3. 順番方式（Taking-Turns）
- ポーリング、トークンパッシング
- 中間的な妥協点
4. チャネル分割プロトコル
4.1 TDMA（Time Division Multiple Access）
時間を固定サイズのスロットに分割し、各ノードに専用スロットを割り当てます。
TDMAの動作
===========
タイムフレーム：
[スロット1][スロット2][スロット3][スロット4][スロット1][スロット2][スロット3][スロット4]
ノードA ノードB ノードC ノードD ノードA ノードB ノードC ノードD
利点：衝突なし
欠点：ノードAだけにデータがあっても自分のスロットでのみ送信可能
--> チャネル帯域幅の1/Nしか使用できない（無駄）
4.2 FDMA（Frequency Division Multiple Access）
周波数帯域を分割して各ノードに専用周波数を割り当てます。
FDMAの動作
===========
周波数
^
| [ノードD帯域]
| [ノードC帯域]
| [ノードB帯域]
| [ノードA帯域]
+--------------------> 時間
TDMAと同じ利点・欠点
- 衝突なしだが帯域幅の無駄
5. ランダムアクセスプロトコル
5.1 ALOHA
ハワイ大学で開発された最初のランダムアクセスプロトコルです。
Pure ALOHA
===========
動作：
1. 送信するフレームがあれば即座に送信
2. 衝突発生時、確率pで即座に再送、(1-p)で待機
時間：
[A送信]
[B送信] <-- Aと重なり、衝突！
[A再送]
[C送信] <-- 衝突なし
最大効率：1/(2e) = 約18%
（チャネル容量の18%のみ実際の送信に使用）
5.2 Slotted ALOHA
時間をスロットに分割し、スロットの開始時点でのみ送信を許可して衝突可能区間を削減します。
Slotted ALOHA
===============
タイムスロット：
| スロット1 | スロット2 | スロット3 | スロット4 | スロット5 |
| A送信 | A+B衝突 | B送信 | | C送信 |
| 成功 | 失敗 | 成功 | 空き | 成功 |
最大効率：1/e = 約37%
（Pure ALOHAの2倍）
仮定：
- すべてのフレームが同じサイズ
- 時間がスロットに同期化
- スロット開始時点でのみ送信開始
5.3 CSMA（Carrier Sense Multiple Access）
送信前にチャネルを聴取（carrier sense）し、他のノードが送信中であれば待機します。
CSMAの動作
===========
1. チャネル検知（Listen before talk）
- チャネルが空いていれば --> 送信
- チャネルが使用中であれば --> 待機
2. それでも衝突が発生する理由：伝播遅延！
時間
|
| Aが送信開始
| [Aの信号がBに到達中...]
| Bがチャネルを検知：「空いている！」--> Bも送信開始
| [衝突発生！]
v
伝播遅延が大きいほど衝突確率が増加
5.4 CSMA/CD（CSMA with Collision Detection）
衝突を検知すると即座に送信を中断してチャネルの無駄を削減します。**イーサネット**で使用される方式です。
CSMA/CDの動作過程
====================
1. NICがフレームを受信しチャネルを検知
2. チャネルが空いていれば送信開始
3. 送信中に衝突を検知：
a. 送信を即座に中断
b. ジャム（Jam）信号送信（48ビット）
c. 2進指数バックオフ（Binary Exponential Backoff）
2進指数バックオフ：
n回目の衝突後、0 ~ (2^n - 1)からランダムに選択して待機
1回目の衝突：0または1から選択
2回目の衝突：0、1、2、3から選択
3回目の衝突：0 ~ 7から選択
...
10回目の衝突：0 ~ 1023から選択（最大10まで）
5.5 CSMA/CDの効率
CSMA/CD効率の公式
====================
効率 = 1 / (1 + 5 * d_prop / d_trans)
d_prop: 最大伝播遅延（2ノード間の最大距離）
d_trans: 最大サイズフレームの送信時間
特性：
- d_prop -> 0 なら効率 -> 1（理想的）
- d_trans -> 無限大なら効率 -> 1
- 大きなフレーム、短い距離で効率的
6. 順番方式（Taking-Turns）プロトコル
6.1 ポーリング（Polling）
マスターノードが各スレーブノードを順番に指定して送信機会を付与します。
ポーリングプロトコル
=====================
[マスター]
|
|--> 「ノードA、送信してください」--> [ノードA] 送信
|
|--> 「ノードB、送信してください」--> [ノードB] 送信（データなし、パス）
|
|--> 「ノードC、送信してください」--> [ノードC] 送信
|
|--> 再びノードAから...
欠点：
- ポーリングオーバーヘッド（ポーリングメッセージ）
- ポーリング遅延（順番を待つ）
- マスターノード故障時にネットワーク全体が麻痺（単一障害点）
6.2 トークンパッシング（Token Passing）
特殊なトークンフレームがノード間を巡回し、トークンを持つノードだけが送信できます。
トークンパッシングプロトコル
==============================
[A] --> [B] --> [C] --> [D]
^ |
|_______________________|
（トークン巡回）
動作：
1. トークンがAに到着
2. Aにデータがある場合：データ送信後トークンをBに渡す
3. Aにデータがない場合：トークンをそのままBに渡す
4. 繰り返し
利点：公平性保証、衝突なし
欠点：
- トークンオーバーヘッド
- トークン紛失時に回復が必要
- 1つのノード故障でネットワーク障害
7. 多重アクセスプロトコルの比較
プロトコル比較まとめ
======================
プロトコル | 効率 | 遅延 | 公平性 | 複雑度
--------------+----------+----------+--------+--------
TDMA | 低(1/N) | 保証 | 公平 | 単純
FDMA | 低(1/N) | 保証 | 公平 | 単純
Pure ALOHA | 18% | 可変 | 公平 | 単純
Slotted ALOHA | 37% | 可変 | 公平 | 単純
CSMA/CD | 高 | 可変 | 公平 | 中程度
ポーリング | 高 | ポーリング遅延| 可変 | 中程度
トークン | 高 | トークン遅延| 公平 | 高
8. まとめ
| 概念 | 核心内容 |
| ------------------ | -------------------------------------------------- |
| パリティビット | 最も単純なエラー検出、偶数エラーは検出不可 |
| CRC | 多項式除算ベース、強力なバーストエラー検出 |
| CSMA/CD | 検知後送信、衝突時即座に中断 + バックオフ |
| Slotted ALOHA | スロット同期化で効率37% |
| 2進指数バックオフ | 衝突繰り返し時に待機範囲が2倍ずつ増加 |
| ポーリング | マスターが順番を指定、単一障害点のリスク |
| トークンパッシング | トークン保持ノードのみ送信、公平だがオーバーヘッド |
次の記事では、リンク層の代表的な実装であるイーサネット、リンク層スイッチ、そしてVLANを見ていきます。
参考資料
- James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 5
- IEEE 802.3 - Ethernet Standard
- Andrew S. Tanenbaum, "Computer Networks", 5th Edition, Chapter 4
현재 단락 (1/256)
リンク層（Link Layer）は、隣接する2つのノード間でフレームを安全に転送する役割を担います。ネットワーク層がホスト間のパケット転送を担当するのに対し、リンク層は1ホップ（hop）単位の通信を担...