# 計算機網路筆記-ch6

## Link-layer簡介
* nodes : hosts and routers
* links : wired, wireless, LANs
* packet : frame (將datagram 封裝, header用Mac address來識別)

#### 比喻(先忽略)

### link layer 的服務
* framing(封裝datagram)
* 存取共享的介質
* 兩個節點間做reliable delivery
* flow control (傳遞與接收間作配速)
* error detection (音訊號衰減與雜訊導致)(會進行重傳或drop掉)
* error correction (不用透過重傳就能更正bit error)
* 單向(half-duplex)或多項(full-duplex)傳輸
* 節點間可以互相傳遞，但無法同時

NIC : network interface card

* link layer 實施在每個host的NIC或是chip(芯片)
* 會連接在host的system bus(連接CPU與memory)


## Error detection
EDC : error detection and correction bits
D : 被error checking保護的data
Error detection not 100% reliable!
* protocol可能會miss掉一些error, 但很少發生
* EDC欄位越大，detection跟correction就會越好

### Parity checking
* 一維的bit parity只能detect
* 二維的bit parity能detect並且correct

### Internet checksum
* sender:
* 會將UDP segment(包含header跟IP)分成一列一列(一列16-bit)
* checksum : 將他們全部做相加，如有overflow會再將overflow與sum做相加，最後再取1補數作為checksum。
* receiver:
* 計算收到的segment的checksum
* 不相等 - error detected
* 相等 - no error detected

### Cyclic Redundancy Check (CRC)
* 比較強大的error-detecting coding
看不懂(有空再翻課本)

## Mutiple access links, protocol
* point-to-point
* Ethernet switch 跟 host 之間的 point-to-point link
* ex : ppp(point to point protocol)
* boardcast (共享線路或介質)
* 多個傳送端&接收端連接到同一條broadcast link
* ex : 乙太網路or無線網路

### Multiple access protocol
* single shared broadcast channel
* 當兩個node以上同時傳輸會互相干擾
* 碰撞 : 當node同時收到兩個以上的訊號
* 分散式演算法決定node如何共用channel
* ex : 決定甚麼時候node可以傳輸
* 協調channel如何共享也需要經由channel本身

#### 理想的multiple access protocol
* 給定 rate 為 R bps 的 multiple access channel(MAC)
* 當1個node想傳輸，可以用R bps傳輸
* 當M個node想傳輸，每個node平均可以用R/M的速率傳輸
* 完全去中心化
* 沒有一個特殊的node去協調傳輸
* 沒有同步的clock, slots
* 簡單

### MAC protocol
* channel partitioning
* 分割channel成小塊一點(time slots, 頻率, code)
* 提供一塊給node供他獨自使用
* random access
* channel不分割，允許碰撞
* 會將碰撞復原
* taking turn
* node輪流使用，想傳很多資料的的node可以用比較久

### channel partitioning MAC protocol
#### TDMA : time division multiple access

* 輪流存取channel
* 每輪每個node都有固定的封包傳遞時間，一次一個node傳輸
* 缺點 : 有些node未在他被輪到的時間使用，會有idle發生

#### FDMA : frequency division multiple access

* channel spectrum(頻譜)照頻率分割成一個一個的bands
* 節點會個別被分配或指定固定的frequency band(有些效率比較好的band，需要花錢競標)
* 缺點 : 有些node未時時刻刻都在傳遞，當沒傳遞時，會造成該band idle

### Random access protocols
* 當有node想傳遞封包，會直接使用整個channel rate R去傳遞
* 不會事先溝通協調好
* 兩個以上的節點在傳輸 : 碰撞
* random access MAC protocol 規範了
* 如何 detect 碰撞
* 如何 recover from 碰撞

#### Slotted ALOHA
* 時間被分為相等大小的slots(一次傳一個frame的時間)
* 當傳輸端有封包想傳送時，傳輸端會直接傳入channel
* 接收端收到封包後，會ACK傳輸端
* 封包有錯誤的話，接收端會向傳輸端發送NACK
* 當channel中有兩個以上傳輸點同時在傳輸封包，會發生衝突，所有的node都需特自等待一段隨機長度的時間後，再次嘗試傳送

它把頻道在時間上分段，每個傳輸點只能在一個分段的開始處進行傳送。每次傳送的數據必須少於或者等於一個頻道的一個時間分段。這樣大大的減少了傳輸頻道的衝突。
##### 優點
* 恰好只有一個node在傳輸時，可以享有整個channel的rate
* 高強度的去中心化(高分散性)
* 簡單
##### 缺點
* 當發生碰撞衝突的時候，會浪費那一個slot的時間
* 會發生idle
* 需要clock同步

#### Pure ALOHA
* 簡單，不同步
* node一收到frame就傳出，slotted會在時間分段的開始處進行傳送
* 會發生很多次的衝突(所以才改成slotted)

#### CSMA (carrier sense multiple access)
##### simple CSMA :
* 傳遞前先觀察
* 如感應到channel是idle的 : 傳遞整個frame
* 如感應到channel是busy的 : 暫時延緩傳輸(等待隨機的時間再傳)
* 比喻 : 不打斷對方

##### CSMA/CD
* 有碰撞偵測
* 可以短時間內偵測碰撞衝突
* 發生碰撞衝突，馬上停止傳輸(因為一次傳整個frame，減少channel的浪費)
* 在有線網路偵測容易，無線網路偵測難
* 比喻 : 有禮貌的人

##### CSMA : collisions
* 即使會先觀察，還是會有碰撞衝突發生
* 由於傳輸資料時會有propagation delay，假如有兩個同一時間欲傳出封包的node，他們會感應到對方正要傳輸(因為delay)，這樣就會造成碰撞衝突。
* 由於一次傳遞都是送整個frame，發生碰撞後，會浪費傳遞的時間(由於沒有碰撞偵測)

##### CSMA/CD (CSMA with Collision Detection)
* 有碰撞偵測
* 可以短時間內偵測傳輸中的碰撞
* 偵測到碰撞，馬上停止傳輸(因為node會一次傳整個frame，如能在發現碰撞後立即停止傳輸，可以減少channel的浪費)
* 在有線網路偵測容易，無線網路偵測難
* 比喻 : 有禮貌的人

##### CSMA/CD
* 減少因為碰撞所發生的時間浪費
* 傳輸會因為偵測到碰撞而立即中止
* 演算法:
1. NIC收到網路層傳來的datagram，並將他封裝成frame
2. 觀察channel:
* if idle : 開始傳遞frame
* if busy : 等待到channel idle再傳
3. 假如NIC成功在沒發生碰撞的情況下傳遞完frame，就順利結束
4. 假如傳遞的途中發生碰撞，會直接中止傳送，並送出jam signal(用來強化碰撞，使其它裝置能儘快檢測到碰撞發生)
5. 中止以後，NIC會利用binary exponential backoff演算法計算一段隨機的等待時間，並等待那段隨機的等待時間後，會再回到第2步驟。
* binary exponential backoff
* 如已經發生了m次碰撞，NIC會隨機選擇{0,1,2...,2^m^-1}的其中一數K，且等待K*512 bit times
* 比ALOHA更簡單、便宜且分散

### Taking turns MAC protocols
* channel partitioning MAC protocols:
* (at high load)在node都要傳輸時，有效率且公平的共享channel
* (at low load)在只有幾個node要傳輸時，會造成資源的浪費(每個node不會因為比較少人使用channel而可以使用更多的rate)
* random access MAC protocols
* (at low load)當node順利傳資料的時候(同時只有一個node在傳)，可以享有整個channel的rate
* (at high load)但在每個node都要傳時，碰撞衝突會一直發生(導致一直等待)
* taking turn protocol
* 尋找兩全其美的方法

#### polling 倫詢
* master node 會輪流邀請其他bode傳送資料
* 用於啞巴deivce
* 優點 : 避免隨機存取的碰撞和頻道分割的idle問題
* 問題
* polling overhead
* 假如master掛掉了，整個網路就都掛掉了

#### token passing
* 會藉由傳遞token，來決定誰可以傳遞資料
* 假如拿到token，就可以傳遞data，如沒資料要傳或是以傳送完畢，就會把token給下一個node
* 有token message
* 優點 : 分散且有效率
* 問題
* token overhead
* 假如其中一個node掛了或是token壞了，就整個掛掉了

### Cable access network : FDM, TDM and random access
* multiple downstream (broadcast) FDM channel
* single access
* 只有CMTS(Cable modem termination system)在這個channel傳輸
* multiple upstream channel
* multiple access
* 所有的user用random access競爭upstream channel
* 其他也可能用TDM(??
* DOCSIS(Data Over Cable Service Interface Specifications）
* (先略)

## LANs
### MAC addresses
* 32-bit 的 IP address:
* 給interface的網路層的位址
* 給網路層做forwarding
* ex : 127.0.0.1
* 48-bit 的 MAC(or LAN, Physical, Ethernet) address
* 使一個interface可以得到與他實體相連的interface給他的frame
* ex : 1A-2F-BB-76-09-AD
* 每個在LAN上的interface
* 皆有 獨有的 48-bit MAC address
* 皆有 <font color=red>locally unique</font> 的 IP address

* MAC address的分配由IEEE管理
* 製造商會購買一部分的MAC address
* 比喻:
* MAC address : 像是身分證字號
* IP address : 像是郵寄地址
* MAC address有可攜性
* 可以隨意地攜帶到另一個LAN
* IP address 不能攜帶，需要看當時interface連接到哪一個子網域

### ARP : address resolution protocol
* APR table : 所有在LAN裡的ndoe都有自己的table
* 紀錄其他在LAN上的node的 IP address 與 MAC address
* <IP address; MAC address; TTL>
* TTL(Time ot live) : TTL會記錄過期的時間，當時間一到，就會將該IP與對應到的MAC address忘記(通常是20min)
#### 例子(A想傳datagram到B，但沒有B的MAC address)

1. A會廣播ARP query
* Target IP address : B的IP address
* destination MAC address :　FF-FF-FF-FF-FF-FF(廣播)
* 所有的節點都會收到這個ARP query
2. B收到廣播後，會回傳ARP response給A
* 回傳了自己的MAC address
3. A收到B的回覆後，會在將B的IP、MAC、TTL寫入A的APR table內
4. A就可以查表做傳輸了

### Routing to another Subnet : addressing(詢址)
#### A經由R傳送datagram給B
* A知道B的IP address
* A知道first hop router R的IP address 跟MAC address
1. A建立IP datagrame(含來源端A的IP與目的地端B的IP)
2. A建立frame(含來源端A的MAC addr.與first hop router R的MAC addr.)
3. frame由A送到R，R將frame拆解成datagram，然後送到網路層
4. 藉由datagram的header資料，R判斷要由哪一個interface送出資料
5. 判斷完後，R建立frame(含R的MAC addr.與目的地端B的MAC addr.)
6. B收到後，拆解frame，將datagram丟到網路層，就完成了(能知道是哪個IP傳來的(A的IP))

### Ethernet
* "主導的"有線LAN技術
* bus形式會發生碰撞衝突
* 目前是使用switched形式，能達到no collision，store-and-forward 的封包傳輸。
* connectionless : 傳送端NIC與接收端NIC沒有handshaking
* unreliable : 接收端NIC不會傳送ACKs或NAKs給傳送端NIC
* 如需可靠傳輸，可以藉由傳輸層做TCP
* 使用 CSMA/CD 這個MAC protocol

### Switch
#### Ethernet switch
* store and forward Ethernet 的 frames
* 查看進來的frame的MAC address資訊，決定該forward frame 到哪一個outgoing link
* 用CSMA/CD存取封包
* 透明性 : host不會知道switch的存在
* plug-and-play, self learning
* switch 不需要做配置

#### mulitple simultaneous transmissions
(此圖有六個interface)
* switch能buffer packet
* no collision; full duplex
* 每個傳送的來源端與目的地端都不相同時，可以同時傳送，不會有碰撞發生
* AtoA', BtoB'同時傳
* 但AtoA',CtoA'不能同時傳
* 每一個link都有自己的碰撞區域，同一個link上不能同時傳輸

#### Switch forwarding table
* switch如何知道藉由哪個interface可以將資料傳到A'
* 每個switch皆有自己的switch table
* (MAC address of host; interface to reach host; TTl)

#### self-learning
* 當有封包傳入時，switch會去將他從哪個interface進來，與他frame中的MAC address記錄到switch table中

#### frame filtering/forwarding
當frame到達switch:
1. 紀錄他的incoming link與MAC address
2. 利用他的MAC address當索引，將以上資訊存入switch table
3. if 在table找的到目的地的話:
* dest == source : drop
* else : 從表上給的interface forward frame
4. else : flood
Flooding : 是一種簡單的路由演算法，將收到的封包，往所有的可能連結路徑上遞送，直到封包到達為止。
switch 沒有 IP address

#### Switches vs. router
* 皆是 store-and-forward
* 都有 forwarding table
* routers : 利用routing演算法與IP address去計算table
* switches : 透過flooding與learning跟MAC address去製作table

### VLAN
* 支持VLAN的switch可以在一個實體LAN中定義出多個虛擬的LAN
* port-based VLAN:
* 可以定義switch中哪幾個port為同一個VLAN
* 也可以利用MAC address來定義該node屬於哪個VLAN
* trunk port : 在不同實體switch上定義的同一個VLAN中傳遞訊息

## MPLS : Multiprototcol label switching
* 在支持MPLS的router利用固定長度的label進行高速度的IP forwarding
* 但IP datagram會還是會持有IP address

### MPLS capable routers (label-switched router)
* 只經由label value(完全不用IP address)去forwarding packet 到outgoing interface
* MPLS forwarding table 跟 IP forwarding table是分開的
* 比IP forwarding彈性，可以做分流，不一定要照著原路走。也可以先事先規劃好備份路徑，link發生錯誤就可以直接快速切換

#### 比較


//IP 跟 MAC 的差別?
###### tags: `計算機網路`