# CSE350期末筆記
###### tags: `NSYSU`
[TOC]
## Chapter4
### Network layer service models
+ PPT 4-10
+ CBR \: constant bit rate
+ VBR \: variable bit rate
+ ABR \: available bit rate
+ UBR \: unspecified bit rate

### Input port functions
+ PPT 4-13
+ destination-based forwarding \: based only on destination IP address
+ generalized forwarding \: based on any set of header field values

### Head-of-line blocking(HOL blocking)
Definition
> queued datagram at front of queue prevents others in queue from moving forward.

左圖上方的紅色$packet$與下方紅色$packet$都想傳到output port，但是只有一個$packet$能傳，所以下方紅色$packet$被擋下來
右圖為一個$packet$之後，綠色$packet$因為紅色$packet$沒有傳出去而須等待，這稱為$HOL\ blocking$
### 為何需要output buffer?
Ans:
+ 當datagram從switch fabric傳過來的速度比datagram傳到link上的速度快時，就需要output buffer避免封包遺失。
+ 當buffer滿時，新來的datagram還是會遺失。
### $\frac{RTT \dot\ c}{\sqrt(N)}$: 為何N愈大，buffer愈小
Ans: 根據公式，因$C$與$RTT$固定，所以當$N$愈大，buffer愈小。
### Weighted fair queue (WFQ)
+ Generalized Round Robin
+ Each class gets weighted amount of service in each cycle

### PPT4-33 IP fragmentation
+ MTU: Max Transfer Size
+ network links have MTU\( largest possible link-level frame \)
+ different link types\, different MTUs.
+ Large IP datagram divided(fragmented) within net.
+ one datagram becomes several datagrams.
+ "Reassembled" only at final destination.
+ IP header bits used to identify, order related fragments
+ PTT 4-34 example

digraph hierarchy {
nodesep=1.0 // increases the separation between nodes
node [color=black,fontname=Courier,shape=box] 
//All nodes will this shape and colour
edge [color=red, style=dashed] 
//All the lines look like this
"MTU segmentaion"->{header data offset}
header->"20 bytes"
data->"1480 bytes"
offset->"1480/8"
}

PS: 20 byte 只有包含IP的標頭
並不包含TCP的標頭(TCP的標頭在分割時並不會複製到各封包)
每個新的封包會有一樣的20 byte IP的標頭+1480被切割的TCP封包
為什麼offset要/8 ??
> 做IP fragmentation要確保切出來的封包對齊[name=Chia-Chih][color=red][time=Sun, Jun 24, 2018 6:24 PM]
### subnet
Definition
> device interfaces with same subnet part of IP address
> each isolated network is called a subnet
> can physically reach each other without intervening router
> IP具有相同subnet part(子網路部分)的裝置介面
> 可以在沒有路由器的狀況下，實體地互相連結
+ IP address
+ subnet part: high order bits
+ host part: low order bits
+ recipe
+ determin the subnets
+ detach each interface from its host or router
+ creating islands of ioslated networks
### PPT 4-50 分配子網路
Q: how does network get subnet part of IP addr?
A: gets allocated portion of its provider ISP’s address space

---
### PPT 4-57 NAT pro and con
+ pro
1. 可自行操作
2. Isolation
3. 換一個ISP業者也不需要更改local network
4. 利用一個IP就可以使許多裝置與外部網路溝通
+ controversial(爭議):
1. 違反 end to end
2. router只能處理到layer3的事情
3. address 短缺應該由IPv6解決
4. local network如果要與外部的server連線會有問題(TCP 三向交握，P2P)
### Tunneling (PPT 4-63)
利用encapsulation達到Tunneling的功能

---
### SDN, flow table:彈性並說明 PPT4-72
+ SDN
+ 各個router會先計算自己與其他router之間的資訊並傳給remote controller，接著remote controller會將這些資訊做最佳化並傳回給各個router
+ flow table
+ Each router contains a flow table that is computed and distributed by a logically centralized routing controller
+ flow table in a router define router's match-plus-action rules.

Generalized forwarding: simple packet-handling rules
+ Pattern: match values in packet header fields
+ Actions: for matched packet: drop, forward, modify, matched packet or send matched packet to controller
+ Priority: disambiguate overlapping patterns
+ Counters: #bytes and #packets

match-plus-action
Router
+ match: longest destination IP prefix
+ action: forward out a link

Switch
+ match: destination MAC address
+ action: forward or flood

Firewall
+ match: IP addresses and TCP/UDP port numbers
+ action: permit or deny

NAT
+ match: IP address and port
+ action: rewrite address and port
### 如何支援mobile network slicing, mobile network computing

## Chapter5
### Data plane, control plane, management plane
+ 為何需要三個plane?
????Application Layer、Control Layer、Infrastructure Layer 三個layer??
+ Data plane
+ local, per-router function
+ determines how datagram arriving on router input port is forwarded to router output port
+ forwarding function
+ Control plane
+ network-wide logic
+ determines how datagram is routed among routers along end-end path from source host to destination host
+ two control-plane approaches:
+ traditional routing algorithms: implemented in routers
+ software-defined networking (SDN): implemented in (remote) servers
+ Management plane
????
////////////////
+ Data plane switches
+ fast, simple, commodity switches implementing generalized data-plane forwarding
+ switch flow table computed, installed by controller
+ API for table-based switch control
+ protocol for communicating with controller
+ SDN controller (network OS):
+ maintain network state information
+ interacts with network control applications “above” via northbound API
+ interacts with network switches “below” via southbound API
+ implemented as distributed system for performance, scalability, fault-tolerance, robustness
+ network-control apps
+ “brains” of control
+ unbundled\: can be provided by 3rd party \: distinct from routing vendor, or SDN controller

### PPT 5-6 利用圖說明SDN的好處；從傳統上開始說明
+ 傳統
+ SDN
+ easier network management\:避免router過於複雜、提升傳輸彈性
+ 中心化\: 提供網路可編程性
+ open (non-proprietary) implementation of control plane

### PPT 5-9 link(u, w)少畫
課本:
> E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
>
正確:
> E = set of links ={ (u,v), (u,x), <font color="red">(u,w)</font>, (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
### Dijsktra's algorithm, PPT 5-14時間複雜度說明及如何達到$O(n\log(n))$
Introduction
+ net topology, link costs known to all nodes
+ accomplished via “link state broadcast”
+ all nodes have same info
+ computes least cost paths from one node (‘source”) to all other nodes
+ gives forwarding table for that node
+ iterative: after k iterations, know least cost path to k dest.’s

Notation
+ c(x,y): link cost from node x to y; = ∞ if not direct neighbors
+ D(v): current value of cost of path from source to dest. v
+ p(v): predecessor node along path from source to v
+ N': set of nodes whose least cost path definitively known

Algorithm

Complexity: $n$ nodes
+ each iteration: need to check all nodes, $w$, not in $N$
+ $\frac{n(n+1)}{2}$ comparisons: $O(n^2)$

How to achieve $O(n\log(n))$
+ 選定兩個node執行演算法，若該路自己與另外一個node都沒走過那就走並存下資訊，若該路自己沒走過另一個node卻走過就不走

### distance vector algorithm PPT 5-20
iterative, asynchronous: each local iteration caused by:
+ local link cost change
+ DV update message from neighbor
distributed:
+ each node notifies neighbors only when its DV changes
+ neighbors then notify their neighbors if necessary

each node

### Analogy: mainframe to pc evolution
垂直整合
+ pro
+ 從硬體到應用都自己做，減少介面接口與硬體軟體衝突的問題
+ con
+ 發展慢，因每一層都要自己做

水平整合
+ pro
+ 自己只要負責自己的那一層還有對上或者對下的介面溝通就可
+ con
+ 發展很快導致介面上的溝通會因版本不同而有問題
### PPT5-70 controller-to-switch messages
Features
+ controller queries switch features, switch replies

Configure
+ controller queries/sets switch configuration parameters

Modify-state
+ add, delete, modify flow entries in the OpenFlow tables

packet-out
+ controller can send this packet out of specific switch port

:::info
Fortunately, network operators don’t “program” switches by creating/sending OpenFlow messages directly. Instead use higher-level abstraction at controller
:::
### PTT5-72畫圖
1. S1, experiencing link failure using OpenFlow port status message to notify controller
2. SDN controller receives OpenFlow message, updates link status info
3. Dijkstra’s routing algorithm application has previously registered to be called when ever link status changes. It is called.
4. Dijkstra’s routing algorithm access network graph info, link state info in controller, computes new routes
5. link state routing app interacts with flow-table-computation component in SDN controller, which computes new flow tables needed
6. Controller uses OpenFlow to install new tables in switches that need updating
## Chapter6
### 為何需要IP address與MAC address
Ans: 因為IP address就像地址一樣，有可能因為搬家或者其他原因而改變，而MAC address就像身分證一樣，除非更換網卡否則永遠不會改變
### CRC(Cyclic redundancy check) PPT6-15
Notation
+ D: d bits data.
+ G: r+1 bit pattern generator.
+ R: r bits CRC

Method

<D, R> exactly divisible by G(modulo 2)
receiver knows G:
	divides <D, R> by G
	if non-zero remainder: error detected.
	//can detect all burst errors less than r+1 bits

Mathematical formula
:::info
$R = remainder[\frac{D\cdot2^r}{G}]$
:::
### PPT6-20
MAC protocols: taxonomy
+ Channel partitioning
+ divide channel into smaller “pieces” (time slots, frequency, code)
+ allocate piece to node for exclusive use
+ random access
+ channel not divided, allow collisions
+ “recover” from collisions
+ taking turns
+ nodes take turns, but nodes with more to send can take longer turns
### PPT6-21
TDMA: time division multiple access
+ access to channel in "rounds"
+ each station gets fixed length slot (length = packet transmission time) in each round
+ unused slots go idle
+ example: 6-station LAN, 1,3,4 have packets to send, slots 2,5,6 idle

### PPT6-28 有誤
### PPT6-30, PPT6-32畫圖
CSMA collisions
+ collisions can still occur: propagation delay means two nodes may not hear each other’s transmission
+ collision: entire packet transmission time wasted
+ distance & propagation delay play role in in determining collision probability

### CSMA/CD 演算法說明
1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.

3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while transmitting, aborts and sends jam signal
5. After aborting, NIC enters binary (exponential) backoff:
+ after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2
+ longer backoff interval with more collisions

### PPT6-34 CSMA/CD 數學式解釋
$T_{prop}$ = max prop delay between 2 nodes in LAN
$t_{trans}$ = time to transmit max-size frame
$efficiency = \frac{1}{1+\frac{5t_{prop}}{t_{trans}}}$
efficiency = 1
+ as $t_{prop}$ = 0
+ as $t_{trans}$ = $\infty$
+ 當$t_{trans}$ 越大時，越容易偵測到碰撞，所以效能越好
pro
+ better performance than ALOHA: and simple, cheap, decentralized!
### PPT6-37
Token passing
+ control token passed from one node to next sequentially.
+ token message
+ concerns:
+ token overhead (有token才能送)
+ latency
+ single point of failure (token)

### PPT6-38
+ multiple 40Mbps downstream (broadcast) channels
+ single CMTS transmits into channels

+ multiple 30 Mbps upstream channels
+ multiple access: all users contend for certain upstream channel time slots (others assigned)

:::info
Cable access protocol 應用於LTE
:::

### PPT6-39, 圖 & DOCSIS協定
DOCSIS: data over cable service interface spec
+ FDM over upstream, downstream frequency channels
+ TDM upstream: some slots assigned, some have contention
+ downstream MAP frame: assigns upstream slots
+ request for upstream slots (and data) transmitted random access (binary backoff) in selected slots

### ARP, PPT6-45
ARP: address resolution protocol
ARP table
+ each IP node(host, router) on LAN has table
+ IP/MAC address mappings for some LAN nodes:
< IP address; MAC address; TTL>
+ TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)

### PPT6-55
bus: popular through mid 90s
+ all nodes in same collision domain (can collide with each other)

star: prevails today
+ active switch in center
+ each “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other)

:::info
星狀結構當發生碰撞時會藉由switch告知大家
:::
### PPT6-65 ALGORITHM
Switch: frame filtering / forwarding

when  frame received at switch:

1.  record incoming link, MAC address of sending host
2.  index switch table using MAC destination address
3.  if entry found for destination then {
    	if destination on segment from which frame arrived then drop frame
        else forward frame on interface indicated by entry
    }   
    else flood  /* forward on all interfaces except arriving interface */

### PPT6-67
Q: A如何送封包到G
A: self learning! (works exactly the same as in single-switch case!)
### switch vs router
switch 無法handle 7 hub
1. switch 為layer2機器，只負責作forwarding
2. router 為layer3機器，除了負責forwarding還需利用routing algorithm決定packet該怎麼走

### PPT6-74
VLAN之間互傳遇到的問題(硬體與協定的問題)
sol1:
:::warning
需換header $\to$ 速度慢且不一定相容
:::

sol2:
Encapsulation $\to$ 直接把header加上去

## 考古

1. There are two control-plane approaches, traditional routing algorithms and software defined networks(SDN). Please explain them to the point by your understanding.

traditional:
傳統上每一個router都需要先做routing algorithm(LS or DV)並建立好forwarding table。
SDN:
每個router(或switch)提供自己與其他機器的link資訊給remote controller，接著remote controller利用routing algorithm計算出flow table後再傳回給router(switch)

2. 

memory:
* adv:在CPU的直接控制下完成交換動作
* dis:速度會被記憶體頻寬所限制

bus:
* adv:不需經由routing processor的介入
* dis:交換速度受限於匯流排頻寬

crossbar:
* adv:克服單一一個公用匯流排的頻寬限制
* dis:結構複雜、成本高 [name=Chen-Wei]

3.
* FIFO
* round robin
* priority scheduling:

4.

5.
(mysol by JHOU)

header |length | ID| fragflag| offset
--------|-------|---|-------|--------
20 |5000 |X |0 | 0
20 |1600 |X |1 | 0
20 |1600 |X |1 |197
20 |1600 |X |1 |394
20 |240 |X |0 |591

6.
+ mobile IP
+ tunneling
+ DHCP
+ VLAN

7.
* 取消check sum - 增進速度(reduce processing time)
* address 增加到128bit - 32bit不夠用
> IPv6 不是增加到128bit嗎? [name=Chia-Chih][time=Sun, Jun 24, 2018 3:43 PM][color=red]
* 多了priority - 區分優先度
* flow Label: identify datagrams in same “flow.”
* next header: identify upper layer protocol for data

8.
SDN利用remote controller執行routing algorithm並把結果建成flow table然後給router(switch)，而flow table是基於match-plus-action rule來決定怎麼處理封包
例如:
+ 可設定防火牆規則:
match: IP address / prot number
action: permit / deny

+ 可設定不轉傳特定封包
match: IP address / subnet
action: forwarding / drop

9.
10.
11.
Data plane switches:
+ 把與自己相鄰的switch的link資訊傳給controller，若有相鄰的switch無法到達也會將資訊傳給controller

controller:
+ 負責接收switch上傳的status message並更新Link-state info
+ 當link status有更動的時候會自動呼叫network-control application重新計算出新的flow table
+ 將最新的flow table安裝在switch上

network-control application:
+ 這一層實作network-control function: 如: routin alogithm, access control, load balance.
+ 藉由controller給予switch的link status進行routing algorithm、access control或者load balance，最後將結果回傳給controller

12.
13.
+ r+1 bit 的G 雙方會先固定
+ 找到一個r bit的 R 與 D*2^r XOR 會 = nG
+ 收到D之後 若 (D*2^r)/G == R 則無誤

14.
TDMA:
+ 將單位時間定義為1個slot(長度通常為一個packet傳輸的時間)
+ 會先講好每個round那些裝置在第幾個slot可以傳packet
+ 若裝置不傳packet則該slot idle

FDMA:
+ 將頻率切成好幾個channel，使得多個裝置能同時間在不同的channel進行傳輸而不互相干擾

Random access:
+ 當node有packet要傳則直接傳，node間沒有協調功能
+ 同時間有多個node要傳則會發生碰撞
+ 需決定如何偵測碰撞與如何從碰撞復原

15.

16.
PS:以下範例只有經過一個router

17. 802.1q藉由encapsulation與decapsulation來增加/移除frame header使得trunk port間可以進行溝通