# 隨機存取協議：Pure ALOHA、CSMA

[TOC]

Hello Guys, I'm LukeTseng. 本篇將來介紹什麼是 Pure ALOHA、CSMA、CSMA/CD 等等，這些都是運作在 Data link layer 上面的。若本篇文章有誤，歡迎各位指正，若你也喜歡這篇文章，不妨按下愛心跟追蹤我的個人頁面吧！

另外本篇文章主要針對上課內容製作筆記，斟酌參考～

## 什麼是隨機存取協議（Random Access Protocols：RAPs）？

這是計算機網路中的資料鏈結層（Data Link Layer）的 MAC 子層中非常重要的一類機制。因此這篇所有的協議像是 Pure ALOHA、Slotted ALOHA、CSMA、CSMA/CD、CSMA/CA 全都是在 Data link layer 上運作的。

隨機存取的相對是循序存取，循序存取的最佳例子就是錄音帶，如果要在第一首歌切到第四首歌，必須要先切第二首、第三首，慢慢切才能切到第四首歌。而隨機存取相反，就可以隨便切，想切就切，所以才會有 RAM（Random-access memory）隨機存取記憶體。

### 為什麼需要 RAPs？

在網路中的傳輸介質往往是廣播式（Broadcast）的，所以會有多個設備連在同一條線上。

若無規則，大家同時送訊號，訊號就會混在一起變成雜訊產生碰撞（Collision）。隨機存取協議就像一套交通規則，用來解決多個使用者如何共用一條路的問題。

### RAPs 的三大特徵

1. 無預定時間：站點發送資料的時間是隨機的，不像 TDMA（分時多工）那樣每個人有固定的時間槽。
2. 無中心控制：通常不用一個中央伺服器來指揮誰能發言，每個站點自己決定。
3. 碰撞處理：Protocol 必須包含如何偵測碰撞跟發生碰撞後如何恢復的機制。

### 那些常見的 RAPs

- Pure ALOHA（盲目發送，想發就發封包）
- CSMA（先聽再說）
- CSMA/CD（邊說邊聽） - 現今有線網路主流
- CSMA/CA（避免碰撞） - 現今無線網路主流

## Pure ALOHA


Image Source：https://www.geeksforgeeks.org/computer-networks/what-is-pure-aloha/

聽這名字就知道，一定是夏威夷人發明的XD。

> ALOHA 協議誕生於 1970 年代的夏威夷大學（University of Hawaii），最初是為了利用無線電波將分散在各個島嶼上的終端機連接到中央電腦而設計的。

Pure ALOHA 的特點就是不管怎樣，封包就是一直發下去就對了。

在 Pure ALOHA 中，任何一個站點（Station）只要有資料幀（Frame）生成，它就會立即將資料發送到通道上，而不進行任何偵測或排程。

### 運作流程

1. 發送（Transmission）：使用者在封包準備好時立即發送。
2. 確認（Acknowledgment）：發送方送出資料後，會等待接收方回傳一個確認信號（ACK）。
3. 碰撞偵測（Collision Detection）：
- 如果收到 ACK，表示發送成功。
- 如果在一段時間內沒有收到 ACK，發送方就判定發生了碰撞（Collision）（即資料跟別人的訊號混在一起，壞掉了）。
4. 重傳（Random Back-off）：
- 發生碰撞後，發送方不能立刻重傳（否則會跟剛才相撞的人再次相撞）。
- 它須等待一段隨機的時間（Random Backoff time），然後再嘗試重新發送。

### Vulnerable Time

Pure ALOHA 效率低落的問題主要在於 Vulnerable Time（脆弱時間），指的是一段可能發生碰撞的危險時間區間。

假設傳送一個標準的資料幀（Frame）需要的時間為 $T$（Frame Time）。

如站點 A 在時間點 $t_0$ 開始發送，它會在 $t_0 + T$ 結束。

前碰撞：如果站點 B 在 $t_0 - T$ 到 $t_0$ 之間曾開始發送，雖 B 比 A 早送，但 B 的尾巴會跟 A 的開頭撞在一起。

後碰撞：如果站點 C 在 $t_0$ 到 $t_0 + T$ 之間開始發送，C 的開頭會跟 A 的身體或尾巴撞在一起。

結論就是當任一個持續時間為 $T$ 的封包，需要保證在前後共 $2T$ 的時間內，沒有其他人在發送，才能確保成功。

$$\text{Vulnerable Time} = 2 \times T$$ 若在此期間內有其他的傳輸開始發送，兩個封包都會被銷毀。

### 吞吐量（Throughput）分析

冗長的數學公式推導就不在這邊細講，主要是靠機率的帕松分佈來計算吞吐量的。

吞吐量數學公式的結論： $S = G \times e^{-2G}$

- S = 吞吐量（每個封包時間內成功傳輸數）。
- G = 每個封包時間產生的封包平均數。

當 G = 0.5 的時候，吞吐量是最大的，這時候代進去公式做計算，得到： $S_{max} = 0.5 \times e^{-1} \approx 0.184$

這個表示啥呢？就是 Pure ALOHA 這東西的頻寬利用率最多只有 $18.4\%$ ，而且都只用於有效的成功傳輸，這是效率非常低的事情。另外即使網路完全飽和，大部分的時間也都浪費在碰撞上。

### 優缺

- 優點：
- 非常簡單：不需要時鐘同步（Synchronization），不需要載波偵測（Carrier Sense）。
- 低延遲（在輕負載下）：如果網路上沒人用，你想發就發，幾乎沒有等待時間。
- 缺點：
- 效率極低：最高只有 $18.4\%$ 的利用率。
- 不穩定：當發送請求增加（ $G > 0.5$ ），碰撞會急劇增加，導致吞吐量 $S$ 迅速下降至 0，網路會陷入癱瘓（Congestion Collapse）。

為了改進 Pure ALOHA，後來就提出了 Slotted ALOHA（分槽 ALOHA） 這東西。

### Pure ALOHA vs. Slotted ALOHA


Slotted ALOHA 示意圖。

Image Source：https://www.geeksforgeeks.org/computer-networks/differences-between-pure-and-slotted-aloha/

Slotted ALOHA 強制將時間切成一個個的時槽（Slot），每個時槽長度剛好是 $T$。使用者只能在時槽的起點開始發送。

那這樣哪裡改進了呢？這樣做消除了「前碰撞」的可能性，因為封包不會跨越時槽重疊。Vulnerable Time 從 $2T$ 縮減為 $T$。

這樣子的效率就從原本的 $18.4\%$ 提升至 $36.8\%$ ，很剛好的是原本 Pure ALOHA 的兩倍。

以下是這兩者之間的比較表：

| 特性 | Pure ALOHA | Slotted ALOHA |
| -------- | -------- | -------- |
| 發送時間 | 隨時隨地，想發就發 | 只能在時槽（Slot）開始時發送 |
| 同步需求 | 不需要 | 需要全網時間同步 |
| Vulnerable Time | $2 \times T$ | $T$ |
| 最大效率 | 18.4% | 36.8% |

## CSMA（Carrier Sense Multiple Access）

CSMA 的中文翻譯是載波檢測多重存取，非常的難懂又饒口XD。

> CSMA 是一種用於電腦網路的方法，幫助裝置共享通訊通道，避免彼此間干擾。裝置在傳送資料前，會監聽頻道（或偵測電信業者）以確認是否有空。

概括來說就是「先聽再說」。

在 CSMA 中每個站點要發送封包前，必須先做偵測載波（Carrier Sense）的動作。

- Sense（偵測 / 聽）：檢查通訊線路上是否有訊號（聽有無聲音）。
- Idle（閒置）：如果沒聽到聲音，表示線路沒人，可準備發送。
- Busy（忙碌）： 如果聽到有人在說話，就先不送，等下再送。

> CSMA 的設計目的是降低網路流量碰撞的機率，讓通訊更順暢且更有效率。透過在傳輸前檢查媒介，使用 CSMA 的裝置能提升整體網路效能。

### CSMA 種類

就兩種：

1. CSMA/CA
2. CSMA/CD

### Vulnerable Time


Image Source：https://www.geeksforgeeks.org/computer-networks/carrier-sense-multiple-access-csma/

是的沒錯，CSMA 也有 Vulnerable Time（訊號從一個裝置傳送到另一個裝置所需的時間）。

在基於 CSMA 的網路中，像是乙太網路或 Wi-Fi，每個裝置在傳輸前都會監聽該頻道。

CSMA 有傳播延遲（Propagation Delay）這件事，這是它的物理限制，就是因為這樣才會產生碰撞，進而產生了 Vulnerable Time 的問題。

可以來假設一個情境，模擬碰撞的情形（訊號比喻成聲音）：

時間 0：坐在桌子左邊的 A 確認沒人說話，開始喊「你好」。
時間 0.5：聲音（訊號）以光速傳播，但還沒傳到桌子右邊。
時間 0.8：坐在桌子右邊的 B 想說話。他「先聽」了一下。

此時因為 A 的聲音還在半路上，還沒傳到 B 的耳朵裡，所以 B 聽起來現在是安靜的，也就是此時的頻道可能是空的。

最後 B 以為沒人說話，於是也喊了出來。

結果就是 A 的聲音和 B 的聲音在桌子中間相撞。

只要當 Propagation Delay（or Propagation Time） > 0，CSMA 就無法完全避免碰撞。線路越長（延遲越大），CSMA 的偵測效果就越差。

然而以下也成立：Vulnerable Time = Propagation Time（Tp）

### CSMA 存取模式

- 1-Persistent（堅持, 急躁模式）
- 行為邏輯：
- 聽：先偵測共享頻道，看有沒有人。
- 若忙碌（Busy）：監聽到該頻道空閒（available）為止。
- 若閒置（Idle）：馬上傳送資料。
- 優點：延遲最低，一有機會就搶。
- 缺點：如果有兩個這種模式的人同時在等某個頻道空閒，當那個人離開的一瞬間，這兩個人會同時發瘋包，導致碰撞。
- Non-Persistent（不堅持, 隨緣模式）
- 行為邏輯：
- 聽：一樣先偵測共享頻道，看有沒有人。
- 若忙碌（Busy）：不繼續偵測，等待一段隨機時間後，回來再聽一次。
- 若閒置（Idle）：馬上傳送資料。
- 優點：大幅降低碰撞機率（因為大家回來的時間不同）。
- 缺點：效率變低。可能線路明明空出來了，但大家都在隨機等待，變得很浪費時間。
- P-Persistent（機率堅持, 看人品模式）：用於分槽（Slotted）通道。
- 行為邏輯：
- 聽：先偵測共享頻道，看有沒有人。
- 若忙碌（Busy）：等到下一個時槽再聽。
- 若閒置（Idle）：
- 以 $p$ 的機率立刻發送。
- 以 $1-p$ 的機率不發送，等到下一個時槽再看。
- 透過 $p$ 值來控制所有人的衝動，即使有很多人想發送，也能透過機率錯開，減少碰撞。
- O-Persistent（有序堅持, 排隊模式）：
- 行為邏輯：
- 聽：先偵測共享頻道，看有沒有人。
- 若忙碌（Busy）：等待下一個人發送。
- 若閒置（Idle）：依預定順序 / 優先級發送。

## CSMA/CD（Collision Detection）


Image Source：https://www.geeksforgeeks.org/computer-networks/collision-detection-csmacd/

CD 指的是 Collision Detection，碰撞偵測。

跟一般 CSMA 不一樣，他主要做的事情是「邊說邊聽，撞了就停」。

另外他還是一種 MAC（Media Access Control） 方法。

### 為什麼 CSMA/CD 適合有線網路？

因為有線網路的訊號衰減很小。發送者可以一邊把訊號送出去，一邊監聽線路上的電壓變化。如果電壓異常（疊加），就代表發生碰撞。

### 運作流程

1. 先聽（Sense）：確保是否線路閒置，是就發送（一般來說是 1-persistent）。
2. 邊說邊聽（Transmit & Listen）：發送封包的同時，持續監聽線路。
3. 碰撞偵測（Collision Detected）：
- 如果監聽到訊號錯亂，立刻停止發送目前的資料。
- 發送干擾訊號（Jam Signal）：停止同時會發出一個高強度的雜訊給所有人，讓網路上其他人都知道這邊塞車了，等下再用。
4. 退讓（Backoff）：等待一段隨機時間（二元指數退避演算法），回到步驟 1 重試。

若在這個傳播過程中未偵測到碰撞，發送端就會完成幀傳輸並重置 counter。

## 總結

隨機存取協議（Random Access Protocols）屬於資料鏈結層（Data Link Layer）中的 MAC 子層，主要用於管理多台設備共享同一媒介（通常是廣播式通道）時的傳輸行為。

目的：避免多台設備同時傳送資料造成碰撞（Collision），並在碰撞後能夠恢復。

### RAPs 的三大特性

1. 無預定時間：傳送時間無固定排程（不像 TDMA）。
2. 無中心控制：每個節點自行決定是否傳送。
3. 需處理碰撞：包含偵測碰撞與碰撞後恢復機制。

### Pure ALOHA

機制特性：使用者只要有資料就立即發送，不偵測通道。

流程：發送 → 等 ACK → 無 ACK 判定碰撞 → 隨機退避 → 重送。

Vulnerable Time：2T（前後各 T 的區間都可能造成碰撞）

最大效率：18.4%

優點：簡單、不需同步、不需偵測

缺點：效率極低，很容易碰撞

### Slotted ALOHA

改進方式：把時間分成長度為 T 的時槽（Slot），只能在時槽開始時發送。

效果：避免前碰撞 → Vulnerable Time 從 2T 降為 T

最大效率：36.8%

缺點：需全網同步。

### CSMA（Carrier Sense Multiple Access）

先聽再說，傳送前先感測媒介是否閒置。

主要問題：因為傳播延遲（Propagation Delay），聽到的狀態可能已過時，因此仍可能碰撞。

Vulnerable Time = Propagation Time（Tp）

CSMA 類型：

- 1-Persistent：忙等 → 空即送 → 撞機率高
- Non-Persistent：忙 → 隨機等 → 撞率低但效率下降
- P-Persistent：用於 Slotted → 以 p 機率決定是否送
- O-Persistent：排隊式發送

### CSMA/CD（Collision Detection）

邊說邊聽，有撞就停，廣泛用於傳統有線乙太網路。

流程：

1. Sense
2. Transmit & Listen
3. 偵測碰撞 → 停止發送
4. 發送 Jam Signal（通知他人）
5. Backoff（Binary Exponential Backoff）
6. 重試

適用有線環境（訊號衰減小，容易偵測）。

### 比較表

| 項目 | Pure ALOHA | Slotted ALOHA | CSMA | CSMA/CD |
| --------------- | -------------- | -------------- | -------------------- | -------------------------------- |
| 發送方式 | 想送就送 | 僅能在 Slot 開頭發送 | 先偵測，閒置才送 | 先偵測、邊送邊聽 |
| 需要同步 | 不需要 | 需要全網同步 | 不需 | 不需 |
| 是否感測媒介 | 完全不聽 | 不聽 | 傳送前要聽 | 傳送中也要聽 |
| 能否偵測碰撞 | 不偵測 | 不偵測 | 無碰撞偵測 | 有碰撞偵測 |
| 碰撞後處理 | Random Backoff | Random Backoff | 依模式退避 | Jam Signal + Exponential Backoff |
| Vulnerable Time | 2T | T | Propagation Time（Tp） | Propagation Time（Tp） |
| 最大效率 | **18.4%** | **36.8%** | 高於 ALOHA，依模式不同 | 最佳（有線環境最有效） |
| 運作環境 | 無線起源 | 無線可用 | 有線/無線皆可 | 主要用於有線乙太網路 |

## 參考資料

[Differences between Pure and Slotted Aloha - GeeksforGeeks](https://www.geeksforgeeks.org/computer-networks/differences-between-pure-and-slotted-aloha/)

[Multiple Access Protocols in Computer Network - GeeksforGeeks](https://www.geeksforgeeks.org/computer-networks/multiple-access-protocols-in-computer-network/)

[What is Pure ALOHA? - GeeksforGeeks](https://www.geeksforgeeks.org/computer-networks/what-is-pure-aloha/)