# 計算機網路筆記-ch5
Control plane : 決定封包從來源端送到目的地的路徑。
* per-router control (傳統)
* logically centralized control (software defined networking)

## Routing protocol
決定來源端到目的地的經過routers的good paths
* path : 一串routers packet從給定的初始來源遍歷到最終目標host
* good : 最少的cost，最快，最不塞

### routing algorithm 分類(<font color=orange>我認為必考</font>)

## 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資訊給其他 n 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)

### 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
complexity:
* LS : n router, O(n^2^)
* DV : 每個router收斂的時間不同

speed of convergence(收斂):
* LS : 有可能會震盪，但一定會收斂
* DV : 每個node收斂時間都不同
* 可能有無限循環的問題
* count-to-infinity的問題

robustness(穩健性，可靠度):
* LS
* 可能會broadcst到不正確的link cost
* 每個router都只計算自己的table
* DV
* 可能會傳遞不正確的最短路徑資訊
* 錯誤可能會藉由鄰居交換慢慢傳開

## intra-ISP routing : OSPF
目前的路由研究都太過理想化了，事實上無法做到每個router地位相同
* 現在的路由器已經太多了，根本沒辦法儲存所有的目的地到routing table中
* 方法:可將routers匯集至“autonomous systems” (AS) 自治系統 (a.k.a. domains)

AS (Autonomous System)：自治系統，是指在網際網路中，一個（有時是多個）實體管轄下的所有IP網路和路由器的組合，它們對網際網路執行共同的路由策略。

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 perform inter-domain routing (as well as 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中與目的地的距離，廣播到backbone中
* local routers:
* 廣播 LS in area only
* 計算在area中的路由
* 經由area border router去跟外界傳遞封包
* boundary router:
* 連接其他AS的router

### inter-AS routing : BGP
* BGP (Border Gateway Protocol)
* 可讓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鄰居傳來的prefix資訊，得知新的可傳達的目的地與傳遞到該目的地的路徑
* 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去決定要走哪條路徑或是要拒絕還是接收廣播訊息
* 可用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 : ISP例子
* 真實的policy例子
* 當ISP可以選擇不告訴其他ISP業者自己的存在，就可以不用幫忙傳遞封包
* 如圖，當A告訴B與C("W, A")，B可以選擇不要告訴C("W, A, B")，這樣C就沒辦法透過B來幫忙傳遞封包
* 如圖，如果X不想幫助B傳封包到C，X就會不告訴B C的存在

## SDN control plane
為什麼要用中心化的control plane:
* 易於管理與更改，且使用上比較彈性
* table-based forwarding
* 集中運算，再分配給routers
* 讓網路的管理(如:流量管理、特別的傳送路徑)是可以程式化彈性控制的

SDN 分為三層:
* network-control apps
* SDN controller
* Data-plane switches

### Data-plane switches
* 快速簡單，做forwarding的硬體
* 會被安裝controller已計算好的flow(forwarding) table
* 會有table-based switch control的API(如:OpenFlow)
* 會有跟controller溝通的protocol(如:OpenFlow)

### SDN Controller (network OS)
* 保留網路狀態、switch的資訊(分散式的database)
* 藉由northbound API去與上層的network-control app作互動
* 藉由southbound API去與下層的network switch作互動
* 用分散式系統，表現出好的性能、延展性、容錯性

### network-control apps
* control的腦袋
* 利用control function去使用SDN conrtoller 提供的 lower-level service 跟 API
* 未綁定的(unbundled)，可以透過第三方去提供，可以自己去安裝或是更新想用的app

## OpenFlow protocol
* 運行在controller 與 switch 之間
* 利用TCP來交換訊息
* OpenFlow分為三種類別:
* controller-to-switch
* asynchronous(switch to controller)
* symmetric(雜的，各式各樣的)
* 與Openflow API不同
* Openflow API是用來標明generalized forwarding action

### controller-to-switch messages
* feature : controller 詢問(queries) switch 的 features
* configure : controller 詢問或設定 switch 的 配置參數(configuration parameters)
* modify-state : 新增、刪除或改變OpenFlow tables裡的flow 項目
* packet-out : controller可以傳送特定的封包給特定的switch做處理

### switch-to-controller message
* packet-in : 將指定封包傳給controller
* flow-removed : switch把flow table裡的entry刪掉
* port status : switch 告訴controller目前的狀態

藉由OpenFlow訊息的傳輸，就可以不去程式化switches

### 範例
1. S1, 遇到狀況會用OpenFlow status訊息通知controller
2. SDN controller收到訊息後，會更新link-status資訊
3. 當link status改變時，Dijkstra's路由演算法會被呼叫
4. Dijkstra's路由演算法會存取controller裡網路圖與state資訊等資料，接著計算新的路由
5. link state routing app會再與SDN contoller裡的flow table做互動，計算新的flow table
6. controller再利用OpenFlow去安裝新的table到switch上


### SDN的挑戰
* control plane是非常可靠、有延展性的分布系統
* 滿足即時、可靠、安全
* 延展性:可以控制超過一個AS
* 在5G時代非常重要

## ICMP : Internet control message protocol
* 用在hosts與routers在網路資訊上的溝通
* 如 error reporting 錯誤回報 : 無法接觸到的host, network, port, protocol
* 傳出request/reply(被ping使用)
* ICMP訊息藉由IP datagram傳遞

ping : 一種電腦網路工具，用來測試封包能否透過IP協定到達特定主機。ping的運作原理是向目標主機傳出一個ICMP的請求回顯封包，並等待接收回顯回應封包。程式會按時間和成功回應的次數估算遺失封包率（丟包率）和封包往返時間（網路時延，Round-trip delay time）。

### Traceroute and ICMP
來源端會傳送UDP segment到目的地端，並在第一次將ICMP訊息裡的TTL設為1，第二次將TTL設為2，依此類推，直到真的傳達到目的地端為止。而在第n次傳送的第n個被傳送到的router會將TTL=0的封包丟棄，並回傳一個ICMP訊息(TTL expired)，而來源端可藉由ICMP訊息得到router的IP跟name，且還可以計算RTTs。當對終封包傳達到目的地或是找不到目的地時整個trace結束。

## network management, configuration

* 管理伺服器
* 網路管理protocol
* 用來讓management server query, configure 與管理deivce
* 用來讓device通知server事情
* 被管理的device
* 裝備著可被管理的硬體與軟體元件
* Data
* 裝置的state, configuration data, ....

### SNMP : Simple Network Management Protocol
* 可以set或query device data(MIB:management information base)
* 有兩種方式傳遞MIB資訊或指令:
* request/response mode (皆為manager request, agent response)
* trap mode (agent-to-manager, 通知管理server一些特殊事件)

###### tags: `計算機網路`