# 第03講 IEEE 802.11 Wireless LAN
計算機網路概論 黃能富教授

IEEE 802.11
---
1. 為了有限範圍所設計的
2. 透過空氣(air space,無線電波)傳輸
3. 俗稱 Wi-Fi
4. 特色功能：
* Power management(電源管理)
* Security mechanisms (加密)

Physical layer
---
* defined two radiobased physical layer standard：
1. frequency hopping(跳頻)
2. direct sequence(直接序列)
* 兩種標準都運作在2.4-GHz頻段，傳輸速度最高可以到 2 Mbps

Standards
---
1. **802.11b**
* 提供 **11Mbps** 的速度
* Uses license-exempt 2.4-GHz band
2. **802.11a**
* 用OFDM技術，並提供 **54Mbps** 的速度
* Uses license-exempt 5GHz band
3. **802.11g**，與 802.11b compatible
* 使用 2.4-GHz band和OFDM技術，且傳輸速度可達 **54Mbps**
4. **802.11n**
* 用MIMO(多輸入多輸出)技術，使傳輸速度可達 **108Mbps**

Hidden node problem
---
* Example：假設這四個節點都只能跟鄰近左右邊的節點傳收訊息
* B 可以跟 A 和 C 通訊，但不能和 D 通訊
* C 可以跟 B 和 D 通訊，但不能和 A 通訊
* 假設 A 和 C 都想跟 B 通訊，他們各自對 B 傳送一個frames，但因為A 和 C 都在彼此的傳送範圍之外，所以並不知道對方的存在
=> 因此 A 和 C同時傳輸frames給B時，會在B發生collision
* B無法同時收到兩個訊號
* 且又因為此傳輸方式不像Ethernet有collision detection的機制，故A 和 C 都無法感測到collision
* 所以A 和 C 被稱作是彼此的**Hidden node**

Exposed node problem
---
* Exposed node problem：
* 假設 B 要傳送訊息給 A，且 C想傳送訊息給D，但因為節點 C 因為聽得見 B 正在傳送訊息，使得 C下了錯誤的判斷，以為自己不能傳送訊息給任何節點，但其實 C 的傳送不會造成問題，因為要傳送給 D 並不會干擾到 A 接收 B 的訊息
* 雙方雖然聽得到對方的訊號, 但同時可傳送給不同的對象

CSMA/CA
---
* 802.11 使用演算法來解決Hidden node和Exposed node 的問題：
* **Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)**
* Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)概念：
* 在傳送端實際傳送資料前，Sender and receiver 交換 control frames
* 此次交換是用來告知附近所有的節點傳送要即將開始
* Sender 先送出 **Request to Send (RTS)** frame 給Receiver
* RTS 訊框包含一個欄位說明要傳多久，和frame的長度
* Receiver replies with a **Clear to Send (CTS)** frame
* 這個frame會回覆長度欄位給Sender

RTS/CTS Frames
---
* 藍色圈圈聽到的是Request to Send(RTS)
* 灰色圈圈聽到的是Clear to Send(CTS)
* frame中有一個duration field(持續時間欄位)
* 因此根據上圖聽到CTS(即紅色node)的node無法傳送給C

---
* 如果兩個或以上的node且同時去嘗試發送RTS frame
=> RTS frame 會 Collision
* 如何發現Collision => 一段時間後，節點沒收到CTS frame
* 等待的時間長度是由**exponential backoff algorithm**決定

Not Support Collision Detection的Solution
---
1. **CSMA** protocol -> 但效能不夠好
2. using **ACK** frame in CSMA/CA
* Receiver sends an ACK frame to the sender after successfully receiving a frame
* 點在嘗試要傳送之前，都必須等待這個ACK

Frame Types
---
* Control Frames：
1. RTS
2. CTS
3. ACK
4. 採 Polling的方法
* Management Frames：
1. Probe Request/Response(試探)
2. Beacon(信標)
3. Authentication(認證)

Distribution System
---
* 因為node可以自由移動，所以為了 **mobility(移動性)和 partial connectivity**
* 有些nodes are allowed to **roam**(可移動)
* 有些nodes連接在wired network(不能移動)
* **Access Points(AP)**
* 透過**distribution system(DS)** 彼此相連
---
* Distribution System:
1. 一個 DS 連接 AP
2. 在 **layer 2** 的架構下運作
* 每個node只跟一個 AP 連接
* A -> C: A -> AP1 -> C
* A -> E: A -> AP1 -> DS -> AP3 -> E

## Distribution System - Scanning
* 選存AP的技術稱為**scanning**
1. 傳送**Probe frame**(探測)
2. 所有收到Probe的AP會回傳**Probe Response frame**
3. 從中選擇一個AP，並傳送一個**Association Request frame**
4. AP透過**Association Response frame**來回復

### Active Scanning
1. 週期性不斷的傳輸Probe frames
2. 在某個位置時，C偏好AP2更勝於AP1，所以它連上了AP2，此行為稱active scanning -> node主動去尋找AP
* -> 代表移動方向

### Passive Scanning
1. AP 定期的發送**Beacon frame**去廣告這台 AP 的能力
* node 可以根據 Beacon frame ，然後送 Association Request frame 給此 AP 來切換存取點

Frame Format
---
* Source and Destination addresses：48bits
* Data：最多 2312 bytes
* Duration/Conn ID：傳送RTS和CTS時，說明需要傳輸多久
* 會有 **4 個 Addr** 是因為802.11用到 Distribution System
* 考慮到frame可能 **across the Distribution System**：
* **To DS**：送到Distribution System
* **From DS**：來自Distribution System
* 0 0 => 直接傳送
* 1 0 => 從source Addr傳到 DS
* 0 1 => DS 傳到目的地Addr
* 1 1 => 跨過 DS 傳送到目的地Addr

MAC Architecture
---
* **Distributed Coordination Function(DCF)**
* 運用**Carrier Sense Multiple Access with Collision *Avoidance* (CSMA/CA)** 的技術
* 所有stations 和 AP 都要有DCF技術
* **Point Coordination Function(PCF)**
* 提供非競爭性服務
* 建構在 DCF 之上，利用**access priority mechanism**來優先存取
* **point coordinator** (polling master)用來決定輪到誰傳送
* 不同流量的存取透過**Inter-Frame Space(IFS)** 來決定
* Point IFS (PIFS) < Distributed IFS (DIFS)
* PIFS允許coordinator可以**seize control**(搶奪控制權)
* PCF為**contention-free**(免競爭)存取的方法，因為是透過polling方式來存取
* DCF 和 PCF 的共存
* DCF 和 PCF**可以共存**並容不互相影響
* Superframe：先有一段contention-free burst(免競爭式)，隨後是contention period(競爭式)
* contention-free burst -> 那段為PCF
* Superframe時間是不固定的，是有彈性的

## Distributed Coordination Function (DCF)
* 利用**CSMA/CA技術**和**random backoff time** 的機制，讓不同實體層間自動共享同一傳輸媒介
=>因為時間為random，所以還是無法100%避免Collision
* 所有正確收到的frame會立即回傳**ACK frame**，但如果沒有收到ACK，會安排重新傳送
* **Carrier Sense**可以透過**Physical和virtual**機制實現

### Virtual Carrier Sense mechanism
* Virtual Carrier Sense mechanism：
=>是傳送與接收端在實際傳送data frame前，透過RTS 和 CTS frame(包含 **duration field**)，來告知其他工作站傳輸媒介已被預約為忙碌的資訊(medium busy reservation)
* 由Medium Access Control(MAC) layer提供，又稱**Net Allocation Vector(NAV)**
=> 透過RTS/CTS frame中告知的持續時間來預測未來流量，並**將duration field放入NAV**
* **此機制只能使用在Unicast**
* **RTS_Threshold**(RTS門檻)：若封包很短，則不需要RTS/CTS機制

### Physical Carrier Sense Mechanism
* 由Physical layer提供

### MAC-Level Ack (Positive Acknowledgment)
* 收到一個封包必須**立即回傳ACK**，且要在最短時間回(**SIFS**)
* 下列類別的訊框必須被回傳一個 ACK 回覆訊框：
* Data
* Poll
* Request
* Response
* 沒有收到 ACK，表示該次傳送有錯誤發生

### DCF -- Inter-Frame Space (IFS)
* **Priority levels**：定義了三種不同的Inter-Frame Space (IFS)
1. ***Short*-IFS (SIFS)**：
* ACK frame
* CTS frame <-> RTS frame
* poll
2. **PCF-IFS (PIFS)**：
* PCF 使用**Contention Free Period frames**
3. **DCF-IFS (DIFS)**：
* 用在transmit **asynchronous**(非同步)
* 一個使用 DCF 且不處於backoff period的工作站只要偵測到傳輸媒介持續idle了 DIFS 的時間，就可以傳輸

### DCF -- Random Backoff Time
* Random Backoff Time的公式：
* CW 是一個介於 CWmin 和 CWmax 間的整數
* Random() 為介於 0 與 1 間的實數
* Slot Time
=Transmitter turn-on delay + medium propagation delay + medium busy detect response time
= 傳送器開啟延遲 +媒介傳遞延遲 +媒介忙碌偵測反應時間

### DCF Access Procedure
* 用到CSMA/CA Protocol，且主要用在Contention Period of a Superframe (競爭式的那一塊)
* 如何運作：
1. 偵測medium是否為free，且即使為free也不能馬上送，須等到**free medium大於或等於 DIFS 值後**，才可傳送
2. 若此時為busy，還是須等一個DIFS的時間+Random Backoff Time，才可傳送
* Example：

### DCF Access Procedure - Backoff Procedure
1. 首先選擇一個 backoff time
2. 在倒數計時(Backoff Timer)的過程中，medium變為busy，此時倒數計時須暫停，等到下次 **free period > DIFS**時，才可繼續倒數計時
3. 等到Backoff Timer為0時，即可開始傳輸
* 希望可達到FCFS的公平傳輸
* Example：
* 初始：B(19µs)、C(10µs)、D(15µs)
* 第一次等待10µs：B(9µs)、D(5µs) => C進入，且之後E(7µs)加入等待
* 第二次等待5µs：B(4µs)、E(2µs) => D進入
* 第三次等待2µs：B(2µs) => E進入
* 第四次等待2µs： => B進入
* 每次都需要先等一個DIFS時間

### DCF Access Procedure - Net Allocation Vector(NAV)
* 透過 RTS/CTS 來設定NAV
=> **從 RTS 或 CTS 結束之後開始計算，直到對應的ACK frame結束為止的這段時間**
* Example:
* RTS和CTS的NAV會不同
* 在搶到傳送權後，可以把所有Fragment傳完，但每個Fragment皆須對應到他的ACK，且傳輸時間有限制，其時間上限為**dwell time boundary**，超過則會終止傳輸
* Example：
* 如果目的工作站沒有回傳ACK，此時沒辦法更新NAV，導致其他工作站無法去存取通道，因此須等到NAV 降到0之後其他工作站才可以去競爭傳輸通道
* 因ACK傳輸失敗，所以需等到紅線處才可以去競爭傳輸通道
* 甚麼時候用RTS/CTS ? => 封包長度大於RTS_Threshold

Point Coordination Function (PCF)
---
* 提供**contention free**(免競爭式)的服務，採預約式或保留式的方式
* 選擇一個工作站為**Point Coordinator (PC)**
* **PC 可以產生Superframe**(SF,超級訊框)
* Superframe由Contention Free period和Contention period組成
* PCF is base on polling的機制上，由Point Coordinator (PC)控制
* 在SuperFrame開始時，會控制 Contention Free (CF) period，透過shorter time between transmissions (PIFS)的時間來控制
* CF-Down Frames(往下送) 和 CF-UP Frames(往上送)
* 如果現在為free得狀態，PC需等待一個PIFS時間後開始傳送：
1.透過找 **polling list**，找到下一個執行的station，並傳送帶有CF-Poll Subtype bit的set
2.沒有station要執行，則傳送**CF-End frame**
* PCF有**較高的 priority level**
* 因為**shorter PIFS gap**，所以可以比DIFS更早搶到控制權
* 在免競爭週期結束時，PC需傳輸CF-End frame，讓NAV欄位reset
* 當工作站收到 CF-Poll 時，必須在一個 **SIFS** 時間後**立即回傳 CF-UP**

IEEE 802.11 Standards
---
* IEEE 802.11：
1. IEEE 802.11, 2Mbps
2. IEEE 802.11b, 11Mbps
3. IEEE 802.11a, 54 Mbps
4. IEEE 802.11g, 54Mbps
5. IEEE 802.11n, 108Mbps

Summary
---
* IEEE 802.11運用CSMA/CA (Collision Avoidance)的方法
* 三種Priority levels:
=> SIFS < PIFS < DIFS
* PIFS -> PFC(Point Coordination Function)
* DIFS -> DFC(Distributed Coordination Function)