[コンピュータネットワーク] 15. リンク層：エラー検出と多重アクセスプロトコル

リンク層が提供するサービス
============================

1. フレーミング（Framing）
   - ネットワーク層データグラムをフレームにカプセル化
   - フレームヘッダにMACアドレスを含む

2. リンクアクセス（Link Access）
   - 共有メディアでのアクセス制御（多重アクセスプロトコル）
   - MACアドレスを使用したフレーム転送

3. 信頼性のある配送（Reliable Delivery）
   - エラー率の高いリンク（無線）でARQを使用
   - 有線リンクでは通常使用しない

4. エラー検出および訂正
   - ビットエラー検出：パリティ、CRCなど
   - エラー訂正：FEC（Forward Error Correction）

リンク層の実装
================

[アプリケーション層]
[トランスポート層]       CPU / ソフトウェア
[ネットワーク層]
-----------------------
[リンク層]              NIC（ハードウェア + ファームウェア）
[物理層]

単一パリティビット（偶数パリティ）
====================================

データ：     1011010
パリティビット：0（1の数が偶数になるように）
送信：       10110100

受信：       10110110（5番目のビットにエラー）
1の数：      5（奇数）--> エラー検出！

限界：偶数個のビットが同時にエラーになると検出不可

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行目 --> エラー位置を特定し訂正可能

インターネットチェックサム計算
================================

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 であること

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ならエラーなし

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ビットの余りで非常に強力な検出

多重アクセスプロトコルの分類
==============================

1. チャネル分割（Channel Partitioning）
   - TDMA、FDMA、CDMA
   - 衝突なしだが非効率的

2. ランダムアクセス（Random Access）
   - ALOHA、Slotted ALOHA、CSMA、CSMA/CD
   - 衝突を許容、検出・回復メカニズム

3. 順番方式（Taking-Turns）
   - ポーリング、トークンパッシング
   - 中間的な妥協点

TDMAの動作
===========

タイムフレーム：
  [スロット1][スロット2][スロット3][スロット4][スロット1][スロット2][スロット3][スロット4]
   ノードA    ノードB    ノードC    ノードD    ノードA    ノードB    ノードC    ノードD

利点：衝突なし
欠点：ノードAだけにデータがあっても自分のスロットでのみ送信可能
  --> チャネル帯域幅の1/Nしか使用できない（無駄）

FDMAの動作
===========

周波数
  ^
  |  [ノードD帯域]
  |  [ノードC帯域]
  |  [ノードB帯域]
  |  [ノードA帯域]
  +--------------------> 時間

TDMAと同じ利点・欠点
  - 衝突なしだが帯域幅の無駄

Pure ALOHA
===========

動作：
  1. 送信するフレームがあれば即座に送信
  2. 衝突発生時、確率pで即座に再送、(1-p)で待機

時間：
  [A送信]
      [B送信]  <-- Aと重なり、衝突！
                    [A再送]
                         [C送信]  <-- 衝突なし

最大効率：1/(2e) = 約18%
  （チャネル容量の18%のみ実際の送信に使用）

Slotted ALOHA
===============

タイムスロット：
  | スロット1 | スロット2 | スロット3 | スロット4 | スロット5 |
  | A送信    | A+B衝突  | B送信    |          | C送信    |
  | 成功     | 失敗     | 成功     | 空き     | 成功     |

最大効率：1/e = 約37%
  （Pure ALOHAの2倍）

仮定：
  - すべてのフレームが同じサイズ
  - 時間がスロットに同期化
  - スロット開始時点でのみ送信開始

CSMAの動作
===========

1. チャネル検知（Listen before talk）
   - チャネルが空いていれば --> 送信
   - チャネルが使用中であれば --> 待機

2. それでも衝突が発生する理由：伝播遅延！

時間
  |
  | Aが送信開始
  |   [Aの信号がBに到達中...]
  |   Bがチャネルを検知：「空いている！」--> Bも送信開始
  |      [衝突発生！]
  v

伝播遅延が大きいほど衝突確率が増加

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まで）

CSMA/CD効率の公式
====================

効率 = 1 / (1 + 5 * d_prop / d_trans)

d_prop:  最大伝播遅延（2ノード間の最大距離）
d_trans: 最大サイズフレームの送信時間

特性：
  - d_prop -> 0 なら効率 -> 1（理想的）
  - d_trans -> 無限大なら効率 -> 1
  - 大きなフレーム、短い距離で効率的

ポーリングプロトコル
=====================

[マスター]
    |
    |--> 「ノードA、送信してください」--> [ノードA] 送信
    |
    |--> 「ノードB、送信してください」--> [ノードB] 送信（データなし、パス）
    |
    |--> 「ノードC、送信してください」--> [ノードC] 送信
    |
    |--> 再びノードAから...

欠点：
  - ポーリングオーバーヘッド（ポーリングメッセージ）
  - ポーリング遅延（順番を待つ）
  - マスターノード故障時にネットワーク全体が麻痺（単一障害点）

トークンパッシングプロトコル
==============================

   [A] --> [B] --> [C] --> [D]
    ^                       |
    |_______________________|
         （トークン巡回）

動作：
  1. トークンがAに到着
  2. Aにデータがある場合：データ送信後トークンをBに渡す
  3. Aにデータがない場合：トークンをそのままBに渡す
  4. 繰り返し

利点：公平性保証、衝突なし
欠点：
  - トークンオーバーヘッド
  - トークン紛失時に回復が必要
  - 1つのノード故障でネットワーク障害

プロトコル比較まとめ
======================

プロトコル    | 効率      | 遅延      | 公平性 | 複雑度
--------------+----------+----------+--------+--------
TDMA          | 低(1/N)  | 保証     | 公平   | 単純
FDMA          | 低(1/N)  | 保証     | 公平   | 単純
Pure ALOHA    | 18%      | 可変     | 公平   | 単純
Slotted ALOHA | 37%      | 可変     | 公平   | 単純
CSMA/CD       | 高       | 可変     | 公平   | 中程度
ポーリング    | 高       | ポーリング遅延| 可変 | 中程度
トークン      | 高       | トークン遅延| 公平  | 高