# 網路期末考-重點整理
###### tags: `計算機網路`
## 第三章傳輸層
### TCP 運作
1. 點對點的傳輸(one sender, one receiver)
2. 可靠的傳輸, 且按照順序傳遞資料
3. 有TCP congestion 與 flow control
4. 雙向傳輸
6. 連線導向(用handshcking在傳遞資料前建立連線)
### TCP seq. #’s and ACKs
* sequence number of a segment is the sequence number of the first byte in the data field
* segment的sequence number是data內第一個byte的sequence number
* 另解 : 要傳出的segment's data裡第一個byte在byte stream裡的number
* ACK is the sequence number of the next byte of data that the host is waiting for
* ACK是host正在等待的下個data中第一個byte的sequence number
* 另解 : 下一個預期會從另一端收到的第一個byte的seq #
### 範例 : 互相傳遞"CIA" (必考)
### UDP 運作
#### User Datagram Protocol
* 盡力的服務，但不可靠(希望又快又好，但往往無法)
* 會造成封包遺失、傳遞的順序不正確
* 傳遞間沒有hand-shacking
* 可以省去建立連線時所需花的時間
* 每個UDP segment都是獨自處理的
* 下層(傳輸層)沒有的服務，上層要自己加
* 可靠的資料傳輸、擁塞控制 應用層需要自己加
* 優點
* 快速(因為不須建立連線)
* header size較小
* 不會有擁塞的問題
* UDP不會管接收到的接收狀況，一收到資料就拼命傳
#### UDP傳遞流程
sender 動作:
1. 應用層會送message下來
2. 決定UDP segment 的 header 要放甚麼
3. 創造UDP segment
4. 將segment往網路層送
receiver 動作:
1. 由網路層拿到segment
2. <font color=red>進行UDP checksum</font>
3. 取出應用層的message
4. 藉由socket將訊息解多工到應用層
#### UDP checksum(<font color=red>應該不重要</font>)
目的: 為了偵測傳遞時是否有傳遞錯誤
sender會將segment(包含UDP header 跟 IP address)分成一列一列(一列16-bit)。接著會將他們全部做相加，如有overflow會再將overflow與剛剛的sum做相加，最後再取1補數作為checksum。checksum value會放在UDP的header中的欄位裡。
receiver收到segment後，會先計算收到的segment的checksum，接著再看看是不是與header內紀錄的checksum相符。相符:代表應該沒有error(實際上還是有可能會有，因為加法不是一個很好的方式)，不相符:偵測到error。
#### TCP VS. UDP
* TCP :
1. 可靠的, 按照順序的傳輸
2. 有congestion control
3. 有flow control
4. 有連線建立
* UDP :
1. 不可靠的, 傳輸不會按照順序
2. 只要收到資料就盡全力的傳輸
* 兩個protocol皆不包含delay保證 與 頻寬保證 等等。
### FLOW Control 與 Congestion Control
#### TCP flow control
* 在傳輸層中有TCP socket receiver buffers，用來暫存網路層傳來的資料，與讓應用層存取與存取後刪除資料。
* 但我們必須做流量控制，不然可能會因送太快，應用層來不及拿走，buffer就滿到不能再存，而遺失資料。
* 透過TCP segment header中的receive window來告訴sender RcvWindow(Rcv = receive)
* RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead]
#### Congestion Control
* 太多sources同時傳遞太快且太多資料導致網路無法handle
* 會導致較長的delay或是封包遺失
* end-end congestion control
* 利用推斷loss跟delay，去得知是否擁塞
* TCP採用的方法
* Network-assitsted congestion control
* routers會直接將擁塞的資訊透過經過的封包告訴傳送端與接收端
#### AIMD
* additive-increase/multiplicative-decrease
* 方法
* 將傳送速率再每個RTT都增加1個MSS(Max Segment Size)直到發生loss
* 當偵測到loss的時候
* 如果是收到到3次重複的ACK => rate/2
* 如果是因為timeout => 降成1MSS
#### TCP slow start
* 連線的初期，讓rate指數性成長
* 一開始Cwnd = 1MSS
* 每個RTT都會將Cwnd*2
* 每收到1個ACK，Cwnd就會增加一個MSS，傳出兩個MSS
#### TCP 的 congestion control
* ssthresh : slow start threshold 門檻值
* 當 Cwnd 低於 ssthresh，sender使用slow start，指數成長
* 當 Cwnd 高於 ssthresh，sender會進入congestion-avoidance，線性成長
* 當 偵測到loss時
* 如果是收到到3次重複的ACK => ssthresh會被設成Cwnd/2，Cwnd會設成ssthresh+3 MSS
* 如果是因為timeout => ssthresh會被設成Cwnd/2，Cwnd會降成1MSS
## 第四章網路層 Data Plane
### IPv4/IPv6
### IP addressing(尋址)
#### IP address : 用來識別<font color=red>host與router interface</font>的32-bit識別碼
#### interface : host或router與physical link的連接點
* router通常有多個interfaces
* host通常有一個或兩個interfaces(乙太+無線網路)
### Subnet
裝置與裝置間的interface<font color=red>不需經由中間路由器</font>就能相連的裝置
##### subnet part : 在相同subnet的裝置，IP address有相同的 high order bits
##### host part : 有自己獨有的 low order bits
將router或host與他們自己的interface分離，分離出的那塊孤立的區塊就是subnet(如下圖)
#### Ip addressing : CIDR
CIDR : Classes InterDomain Routing
* address中subnet部分的<font color=red>長度是隨意的</font>
* address format: a.b.c.d/x, x是subnet部分的長度
### IPv6
* 32-bit的IPv4快分配完了
* 固定的40-byte的header，加速了forwarding
* 可以讓其他網路層做流量處理
### datagram格式
* flow label : 同筆資料給予相同的label，可用來做流量控制及統計
與IPv4的比較:
* 由於沒有checksum，所以可以加速處理資料
* no fragmentation/reassembly
* no options
### Tunneling
由於不是所有的router都更新成使用IPv6的版本，
所以tunneling是將IPv6的datagram放入IPv4 datagram裡的payload(data)欄位中，在IPv4的routers中做傳遞。(封包放在封包內做傳遞)
* 廣泛用於4G/5G中，因為4G/5G是使用IPv6
### Route Aggregation
#### 位址分配屬於階層式
* 如圖，會有ISP層、組織企業的層...一層一層的階級
* ISP的router可以設定條件(如:adrress由200.23.16.0/20開始的都傳給我)，讓封包透過階層式的傳遞，傳到正確的目的地。
* 而封包會選擇條件符合最多的router做路由
### Router 架構
routing, management control plane(software) 須花較多時間
forwarding data plane(hardware) 非常快速
#### Input port function
* 去中心化的 Switching
* 利用header去forwarding table尋找適合的output port
* 假如datagrame到達的速率大於forwarding到switch fabric的速率，就會發生queueing
* destination-based forwarding : 根據destination IP address 去forward
* generalized forwarding : 根據header中其他的值去判斷如何forward
#### Longest prefix matching
* 在查表時，要選取destination IP address的 <font color=red>prefix 與表中項目中相符合最長</font>的那一項。
#### Switching fabrics
* 將 packet 從 input link 傳輸到合適的 output link
* 假設每個input port的傳輸速率是R，今天有N個input link，則理想的switching rate是N*R
#### Switching via memory
* 最初的的router，由一般電腦來完成，先將送進來的封包<font color=red>複製到處理器的記憶體中</font>，<font color=red>處理器找出適當的output port</font>，<font color=red>再複製到輸出埠的buffer</font>。
* 由電腦的CPU來決定output link
* 需先複製到記憶體中
* 速度會受限於memory的頻寬
#### Switching via bus
```
不需要處理器的介入，input port會在封包加一個標籤，
指定要傳送出去的output port，並由shared bus傳到每個output port，
output port判斷該標頭是不是指自己，是的就保留，不是則捨棄。
```
* inupt port藉由共享的bus傳到每個output port
* outport判斷不是自己的就會丟棄
* 是自己的就會保留
* <font color=red>**同一時間只有一個封包可以跨過bus，所以封包交換速度會受限於匯流排速度**</font>。
#### Switching via interconnection network
利用<font color=red>**棋盤式交換結構**</font>(crossbar switch)，若有N個輸入埠、N個輸出埠，會由2N條buses(N條水平、N條垂直)形成此結構，而<font color=red>**switch控制器可以決定哪些是斷開或閉合，此結構便可以實現同一時間多個input port轉送多個封包的功能**</font>。
### input port queuing
* 當switch fabric的速度比input port傳入的速度慢，input port就會發生queuing 甚至是 loss。
* head-of-the-line(HOL) blocking : <font color=red>**排在前面的datagram阻止其他也在排隊，但在後面的datagram前進**</font>。
### output port queuing
* 當今天datagram到達output port的速率大於output link的transmission rate，則會需要先將datagram buffer起來。(buffering when arrival rate via switch exceeds output line speed)
* Scheduling discipline : 選擇正在queueing的datagram進行傳送(擁有優先權的人可以享受到更好的效能)。
* output port buffer 滿了可能會造成loss
### Buffer Management
* Drop
* 當buffer滿的時候
* tail drop : 將正準備到達的packet(tail尾巴)drop掉
* priority : 依優先的順序drop甚至是remove掉在buffer的packet
* Marking
* router可以將congestion的訊號標記在packet，讓host知道(ECN、RED)
### Packet Scheduling
決定該要先送出哪個在buffer上的封包
#### FCFS
* first-in-first-out
#### Priority
* 進入buffer(queue)時會先分類
* 任何header裡的資訊都可以成為分類的依據
* 會優先傳送優先權高的封包
* 如果兩個封包來自同一個優先權分類，則用FCFS決定誰先傳
#### Round Robin(RR)
* 進入buffer(queue)時會先分類
* 任何header裡的資訊都可以成為分類的依據
* 會輪流的傳送每一個分類的封包
#### Weighted Fair Queueing(WFQ)
* 進入buffer(queue)時會先分類
* 任何header裡的資訊都可以成為分類的依據
* <font color=red>原理跟round robin很像</font>，一樣都會輪流傳送每一個class的封包
* 差別在於<font color=red>每個class都有自己的權重</font>
* 會<font color=red>根據每個class的權重大小</font>來決定這個class<font color=red>被輪到時一次可以傳送多少個封包</font>，而不是像RR一樣，每次輪到每個分類都是傳一樣的份量
### DHCP
* 目的 : 可讓想加入網路的host被server動態地分配IP address
* 同個IP可以不同時地分配給不同的host
* 因為可以將IP分配可以當下有需要的人，而不是IP永遠固定給某一台不是隨時在上網的host，這能減輕IP位置不夠的問題
* DHCP 細節
* host broadcast <font color=red>**DHCP discover**</font>訊息
* DHCP server 用<font color=red>**DHCP offer**</font>回應host，並告知host可以取得的IP adrress資訊
* host 用<font color=red>**DHCP request**</font>請求取得IP address
* DHCP server 用<font color=red>**DHCP ack**</font>確認
* 大部分 DHCP server 是<font color=red>被建置在router內，服務router所連接的子網路</font>。
* DHCP 還可傳遞IP位址外的資訊:
* 離client最近的router的IP位址
* 離client最近的DNS server的name跟IP位址
* network mask
DHCP流程:
1. host發出的DHCP REQUEST msg被<font color=red>UDP、IP與Ethernet</font>一層一層向下封裝
2. Ethernet frame 在 LAN 中broadcast(設destination IP address為255.255.255.255)
3. 被有DHCP server的router接收，然後一層一層的往上傳遞到DHCP協定
-----
4. DHCP server將要給client的IP位址、最接近的routerIP位址與最近的DNS名子與IP位址寫入DHCP ACK or offer內
#### 如何得到IP位址
1. 取得固定IP位址，然後將host寫死
2. DHCP
Q: 網路如何得到subnet part of IP位址
A: 向ISP租用ISP所擁有的IP位址
ISP會分配ISP所被分配到的address space(網段)給client，
如今天有n個組織向ISP租用網路，ISP會將他被分配到的IP位址區塊進行切割，切割成n等分給這n個組織去使用。
#### 那ISP如何取得網段
ICANN : Internet Coperation for assigned Names and Numbers
ICANN 會分配IP位址給5個regional registries(RRs)(區域網路註冊機構，是管理世界上某特定地區Internet資源的組織)
IPV4已經不夠用，但可以藉由NAT可以暫時解決IP位址不夠的問題。
而IPV6有128個bit，為未來將設法普及的定址方法，短時間內應該不會出現位址不夠分配的問題。
### 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會廣播<font color=red>ARP query</font>
* Target IP address : B的IP address
* destination MAC address : FF-FF-FF-FF-FF-FF(廣播)
* LAN上的所有節點都會收到這個ARP query
2. B收到廣播後，會回傳<font color=red>ARP response</font>給A
* 回傳自己的MAC address
3. A收到B的回覆後，會在將B的IP、MAC、TTL寫入A的APR table內
4. A就可以查表做傳輸了
## 第五章網路層 Control Plane
### Routing Algorithm LS/DV (Local Forwarding Table)
### Link state
#### Dijkstra's link-state routing algorithm
* 中心化的(centralized) : 每個node都知道網路中所有link的cost(成本)
* 藉由link state broadcast實現
* 所有node擁有的資訊是一樣的
* 計算從來源node到所有其他node的最小成本路徑(least cost paths)
* 會給予所有的node forwarding table
* iterative : 經過k個迴圈，可以得到由某個點到k個目的地的最小成本路徑
#### discussion
* 每個router都需要<font color=red>broadcast</font>自己的link state資訊給其他的router
#### route oscillation(震盪性)
如果將流量擁塞設為link cost，則會發生震盪的情形。
#### Distance Vector
* 每次循環時，會與直接相鄰的節點(鄰居)們進行訊息交換
* 根據 Bellman-Ford (BF) equation
#### KEY idea
* 每個節點會不時的傳遞自己distance vector estimate給鄰居
* 假設x節點收到鄰居傳的新DV estimate，x會藉由B-F equation去更新自己的DV
* 以上動作會一直重複做(重複交換訊息、更改自己的DV)，直到x算出真的對其他node的真正最小成本路徑
#### each node
* 以下三點重複循環:
1. 等待local link cost的改變 或是 鄰居傳來新的DV
2. 根據鄰居傳來的DV重新計算自己的DV
3. 如果重新計算的DV有改變，則會通知並傳給鄰居
* 每個節點是iterative與不同步的，他們各自的迭代取決於:
* local link cost的改變
* 鄰居傳來新的，改變過後的DV
* 每個節點也是分散式與self-stopping:
* node只會在必要的時候(自己DV有更新的時候)通知自己的鄰居自己的改變
* node假如沒有收到通知，就不會有動作(action taken)
#### DS的問題 : link cost change
cost突然由
* 大變小，是可以順利正常運作的
* 小變大，可能會造成無限loop(分散式的問題)
EX:
由於Z的DV告訴Y只需5就能到X，Y就會更新自己的DV(Y到X走Z，花6)，
Z會再由Y更改自己的DV(Z到X改成7)，......無限循環，count-to-infinity
#### 比較LS跟DV
* time complexity:
* LS : n router, O(n^2^)
* DV : 每個router收斂的時間不同
* speed of convergence(收斂):
* LS : n router, O(n^2^)，有可能會震盪
* DV : 每個node收斂時間都不同
* 可能有無限循環的問題
* robustness(穩健性，可靠度):
* LS
* 可能會broadcst到不正確的link cost
* 每個router都只計算自己的table
* DV
* 可能會傳遞不正確的最短路徑資訊
* 錯誤可能會藉由鄰居交換慢慢傳開
### OSPF
目前的路由研究都太過理想化了，事實上無法做到每個router地位相同
* 現在的路由器已經太多了，根本沒辦法儲存所有的目的地到routing table中
* 方法 : 可將routers匯集至“autonomous systems” (AS) 自治系統 (a.k.a. domains)
* OSPF 為 intra-ISP routing
```C
//擷取於網路
AS (Autonomous System)：自治系統，是指在網際網路中，
一個（有時是多個）實體管轄下的所有IP網路和路由器的組合，
它們對網際網路執行共同的路由策略。
```
* AS : 指在網際網路中，由一個實體管轄下的所有IP網路和routers的組合，同一個AS會執行共同的路由策略。
* intra-AS (aka "intra-domains"):
* routing在同一個AS裡
* 所有在AS裡的router只能跑同一個 intra-domain protocol
* 在不同AS的router可以跑不同的intra-domain routing protocol
* gateway router : 在所屬的AS的邊緣，連接其他AS的router
* inter-AS (aka "inter-domain"):
* gateways 表現 inter-domain routing (和 intra-domain routing)
* 被intra 與 inter-AS routing 演算法配置的forwarding table :
* intra-AS routing 決定在AS裡的dest.
* inter-AS & intra-AS 決定外部的dest.
### OSPF(Open Shortest Path First) routing
* Open : 公開的
* 使用link-state
* 每個router都會廣播自己的OSPF link-state給所有在AS裡的routers
* 可有多種的link costs，如參考bandwidth或是delay
* 每個router都會有完整的網路拓譜，利用Dijkstra’s演算法去計算forwarding table
#### 階層式的OSPF
* two-level 階層: local area, backbone
* link-state只廣播在area中或是backbone中
* 每個node只有自己area的網路拓譜
* area border routers:
* 統整在area中與目的地(Area中其他nodes)的距離，廣播到backbone中
* local routers:
* 只在area廣播LS
* 計算在area中的路由
* 經由area border router去跟外界傳遞封包
* boundary router:
* 連接其他AS的router
### BGP
* BGP (Border Gateway Protocol)
* inter-AS routing
* 可讓subnet去告訴其他網路說 "我在這裡"
* EBGP (Exterior BGP):
* 跟鄰居AS交換訊息用
* IBGP (Interior BGP):
* 跟自己AS內部的router交換訊息用
* 透過 TCP 連線，傳遞BGP訊息
* 所有的ASs 皆用同一個 inter-AS routing protocol
* glues the thousands of ISPs in the Internet together
* 透過得到AS<font color=red>鄰居傳來的prefix資訊</font>，<font color=red>得知新的可傳達的目的地與傳遞到該目的地的路徑</font>
* router可能會收到許多不同routers給的特別一個prefix，router會run a BGP route-selection procedure
#### BGP path advertisement
1. AS3會傳一個BGP訊息("AS3, X")給AS2，告訴AS2 X存在且在AS3裡面
2. 接著AS2會傳BGP訊息("AS2, AS3, X")給AS1，可以經由AS2到AS3找到X
* 藉由這個方式，AS不只可以知道X的存在，也可以知道到達X的路徑。
1. gateway router 3a 會先傳遞<font color=red>eBGP</font>訊息("AS3, X")給2c
2. gateway router 2c接著會傳遞<font color=red>iBGP</font>訊息("AS3, X")給所有在AS2裡的router
3. gateway router 2a接著會傳遞<font color=red>eBGP</font>訊息("AS2, AS3, X")給1c
4. gateway router 1c接著會傳遞<font color=red>iBGP</font>訊息("AS2, AS3, X")給所有在AS1裡的router
#### Determining the Best Routes
##### Based on policy
router可能收到同一個prefix但是是透過不同的路徑傳輸，如1c收到3a與2a送的eBGP訊息，皆是告訴1c有目的地x。
* 根據policy, 1c會選擇 path AS3,x，然後藉由iBGP廣播這個path給AS1裡的router
* 可以import policy去決定要走哪條路徑或是要拒絕or接收廣播訊息
* 可用policy來決定要不要廣播路徑與目的地給其他gateway router，可能是取決於其他AS有沒有付費
##### Hot potato routing
* 選擇有最小intra-domain cost的local gateway
#### BGP selection
可以依照以下條件選擇路徑:
* policy決定
* 最短的AS路徑(AS-PATH)
* 最近的NEXT-HOP(cost最小的local gateway router) router : hot potato routing
* 其他額外的標準
### Policy Routing
```c
//擷取自網路
原則型路由（英語：Policy-based routing，縮寫為PBR），
也稱為策略路由（policy route），一種決定路由的方式，
由網路管理者決定路由原則，再根據這些原則來決定路由。
當一個路由器接收到封包時，通常會被轉送到封包指定的目的位址。
但在某些狀況下，需要根據其他原則來決定封包要轉送到何處。
舉例來說，網路管理員可以根據封包的來源位址來轉送這些封包。
原則型路由可以根據封包的大小，封包內指定的通訊協定，
或是其他封包表頭及封包內容的資訊，來決定路由轉送的方式。
當有數個私有網路相互連結時，原則型路由對於網路管理員來說，
原則型路由是相當有用的。
```
* 可由網路管理者決定路由的policy
* 而當router收到封包的時候，會根據policy來決定封包要轉送到哪
* 可以根據封包的header與內容，來決定路由的轉送方式
* 私有網路互相連接，policy就能扮演重要的角色
#### 藉由廣播實踐policy : ISP例子
* 真實的policy例子
* 當ISP可以選擇不告訴其他ISP業者自己的存在，就可以不用幫忙傳遞封包
* 如圖，當A告訴B與C("W, A")，B可以選擇不要告訴C("W, A, B")，這樣C就沒辦法透過B來幫忙傳遞封包
* 如圖，如果X不想幫助B傳封包到C，X就會不告訴B C的存在
## 第六章資料連結層
### MAC 存取控制 與 CSMA、CSMA/CD
#### Multiple access protocol
* 單一共享的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輪流使用channel，想傳很多資料的的node可以用比較久
### channel partitioning MAC protocol
#### TDMA : time division multiple access
* 輪流存取channel
* 每輪每個node都有固定的時間可以傳遞封包，一次一個node傳輸
* 缺點 : 有些node未在他被輪到的時間使用channel傳遞封包，會有idle發生
#### FDMA : frequency division multiple access
* 將channel的spectrum(頻譜)依照頻率分割成一個一個的bands
* 每個節點會被分配或指定固定的frequency band(有些效率比較好的band，需要花錢競標)
* 缺點 : 有些node未時時刻刻都在傳遞，當沒傳遞時，會造成該band idle
### Random access protocols
* 當有node想傳遞封包，會直接使用整個channel的rate去傳遞
* 不會事先溝通協調好
* 兩個以上的節點在同時在同一個channel傳輸會發生碰撞
* random access MAC protocol 規範了
* 如何 detect 碰撞
* 如何 recover from 碰撞
#### Slotted ALOHA
* 時間被分為相等大小的slots(每個slots為傳一個frame的時間)
* 當傳輸端有封包想傳送時，傳輸端會<font color=red>**在一個slot的開始處**</font>傳入channel
* 接收端收到封包後，會ACK傳輸端
* 封包被偵測到錯誤的話，接收端會向傳輸端發送NACK
* 當channel中有兩個以上傳輸點同時在傳輸封包，會<font color=red>發生衝突</font>，所有的node都需特自<font color=red>等待一段隨機長度的時間後，再次嘗試傳送</font>
##### 優點
* 恰好只有一個node在傳輸時，可以享有整個channel的rate
* 高強度的去中心化(高分散性)
* 簡單
##### 缺點
* 當發生碰撞衝突的時候，會浪費那一個slot的時間
* 有些slots會發生idle
* 需要clock來同步
#### Pure ALOHA
* 簡單，不同步
* node一收到frame就會<font color=red>直接</font>將frame傳出，而slotted ALOHA會在時間分段的開始處進行傳送
* 會發生很多次的碰撞衝突(所以後來才改成使用slotted)
#### CSMA (carrier sense multiple access)
##### simple CSMA :
* 傳遞前先觀察
* 如感應到channel是idle的 : 傳遞整個frame
* 如感應到channel是busy的 : 暫緩傳輸
* 比喻 : 不打斷對方
##### 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; 在高負載時)在nodes都要傳輸時，有效率且公平的共享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 會輪流邀請其他slave nodes傳送資料
* 通常用於啞巴deivce
* 方法 :
1. master node 會傳送訊息給node1，告訴他可以開始傳資料
2. node1傳完後，master node就會傳訊息給下一個node(node2)，並告訴他可以開始傳資料
3. 依此類推，大家按照順序輪流的傳遞資料，共享channel
* 優點 : 避免隨機存取的碰撞和頻道分割的idle問題
* 問題
* 假如master掛掉了，整個網路就都掛掉了
#### token passing
* 會藉由在固定node順序中傳遞token，來決定誰可以傳遞資料
* 假如拿到token，就可以傳遞data，如沒資料要傳或是已經傳送完畢，就會把token給下一個node
* 藉由傳遞token message來傳遞token
* 優點 : 分散且有效率
* 問題
* 假如其中一個node掛了或是token壞了，就整個掛掉了
### Cable access network : FDM, TDM and random access
* DOCSIS(Data Over Cable Service Interface Specifications）
* 標示了cable data network的架構跟protocol
* 用FDM將channel分割成upstream(modem to CMTS)與downstream(CMTS to modem)
* 在downstream的channel中，由於只有一個CMTS在傳遞資料給modems，所以沒有mutiple access的問題
* upstream channel 使用TDM將一段一段的時間分配給modem
### SELF-LEARNING
* 當有封包傳入時，switch會將傳送端的MAC address與傳送端由哪個interface進來的資訊記錄到switch table中
#### frame filtering/forwarding
當frame到達switch:
1. 紀錄他的進來的link與MAC address
2. 利用他的MAC address當索引，將以上資訊存入switch table
3. if 在table找的到目的地的話:
* 當dest == source : drop
* else : 從表上給的interface傳出frame
4. else : flood
* Flooding : 是一種簡單的路由演算法，將收到的封包，往所有的可能連結路徑上遞送，直到封包到達為止。
#### 思考
#### 參考(看看就好)
* switch 沒有 IP address
#### Switches vs. Router
* 皆是 store-and-forward
* 都有 forwarding table
* routers : 利用routing演算法與IP address去計算table
* switches : 透過flooding與self-learning跟MAC address去製作table
## 第七章無線網路
### 無線網路優點與缺點
#### 優點
* 高移動性
* 可以不受網路實體線路影響，隨時地在無線網路訊號涵蓋的範圍中連線
* 成本較低，建構時間短
* 因為只要電波可以傳送的地方，就可以連線網路
* 不需要在架設實體的網路(耗時且成本高)
* 也能克服環境上的困難(如:河流、山派或交通要道)
#### 缺點
* 訊號會在傳遞中衰減
* 訊號容易受干擾
* 目前許多電子用品都會產生電磁訊號，常常會互相干擾
* 有資訊安全的疑慮
* 由於訊號皆在空中傳播，使任何人都可以在空中接收到訊號，可以容易的被有心人士竊聽
* 因此，無線網路的訊號傳遞需要使用身分認證、資料加密等等的發法提升網路的安全性
* 連線品質不穩定
* 可能受到不同介質、不同環境影響，導致訊號不佳
### Hidden Terminal Problem
#### 例子
node A與node C的傳輸範圍涵蓋node B，但A不包含C，C也不包含A。而假設今天A正在傳遞封包給B，但C會因為不包含在A的傳輸範圍，所以認為B在idle。當C剛好也想傳遞資料時，就會與A發生碰撞衝突。
### CDMA (Code Division Multiple Access)
* 屬於channel partitioning
* 所有的user共用一樣的頻率，並可同時全力傳送資料，但每個user都會被分配獨一無二的code
* Encode
* 為了數學方便，將0表示為-1做運算
* 假設今天有sender1與sender2皆要傳資料
* output Z<sub>i,m</sub> = sender 1的(d<sub>i</sub> * C<sub>m</sub>) + sender 2的(d<sub>i</sub> * C<sub>m</sub>)
* 設sender們欲傳出8個bit，CDMA code為8個bit。則i與m的範圍皆為0~7，d<sub>i</sub>為資料的第i個bit，C<sub>m</sub>為code的第m個bit
* Decode
* receiver 1的會得到d<sub>i</sub> = ( $\sum_{m=1}^8$Z<sub>i,m</sub>*C<sub>m</sub>) / 8
### CSMA/CA
802.11 sender
1. 假如感應到channel正在idle，會等待一個DIFS(Distributed Inter-frame Space)，再傳出整個frame
2. 假如感應到channel繁忙，則會延後一段時間(等待channel idle+DIFS+隨機延遲時間)再傳出整個frame
* 避免大家都偵測到idle然後等待DIFS後一起送出，發生碰撞
3. 如果傳完收到ACK，表示成功送達，如果沒收到ACK則須重做第2步驟
802.11 receiver
* 如果成功收到frame，且frame通過CRC，會等待一個SIFS(Short Interframe Space)再將ACK傳出
### RTS/CTS
* 可以解決Hidden Terminals Problem
1. sender先藉由CSMA廣播RTS frame(request-to-send)給所有傳輸涵蓋範圍裡的node(包括BS)
* RTSs可能會發生碰撞，但他們比較小，不會浪費太多資源
2. BS收到RTS後，會廣播CTS(clear-to-send)frame給所有傳輸涵蓋範圍的node
* 只有成功傳送RTS的sender可以傳送資料
* 其他的node必須避免傳輸，暫緩傳輸
### SSID Assoication
### 802.11 LAN
* 用CSMA/CA做多重存取
#### 架構
* 無線的host跟base station做聯繫
* base station = access point(AP)
* Basic Service Set (BSS) 在infrastructure mode:
* wire host
* AP : base station
* ad hoc mode : 只有host，沒有base station
#### channel, association
* AP 管理者可以挑選AP的frequency
* 假如跟鄰近APs都挑選同一個頻率，容易發生干擾
* 剛到達BSS的host : 需要聯繫AP
* 掃描channel，聆聽含有AP's name(SSID)與MAC address的beacon frames
* 挑選想連的AP(可能需要驗證)
* 通常會跑DHCP來得到IP
#### passive/active scanning
* passive:
* APs會不時的sent becon frames
* mobile host收到後可選擇，然後送出association request給想要的AP
* AP會在傳association response給mobile host
* active:
* mobile host會broadcast Probe Request
* AP們會回傳Probe Response給host
* mobile host收到後可選擇，然後送出association request給想要的AP
* AP會在傳association response給mobile host
Sign in with Wallet
Connect another wallet