電腦網路 - HackMD

chapter 12

DSL

Uses existing telephone infrastructure
up to 8Mbps downstream, 1Mbps upstream
dedicated physical line to telephone central office
multiplexing by spliting the frequency

Cable Modem

Uses cable TV infrastructure
HFC: hybrid fiber coax
- asymmetric: up to 30Mbps downstream, 2 Mbps upstream
net work of cable and fiber attaches homes to ISP router
- homes share access to router
FDM: frequency devision multiplexing

FTTH

Optical links from CO(central office) to the home
Two competing optical technologies:
- Passive Optical network (PON)
- Active Optical network (AON): signal amplification
Much higher Internet rates; fiber also carries television and phone services

Ethernet Internet access

Typically used in companies, universities, etc
10 Mbps, 100Mbps, 1Gbps, 1Gbps, 10Gbps Ethernet
Today, end systems typically connect into Ethernet switch

Wireless access networks

shared wireless access network connects end system to router
- via base station aka "access point"
wireless LANs:
- 802.11/g (WIFI): 11 or 54 Mbps
wider area wireless access
- provide by telco operator
- ~1Mbps over cellular system(EVDO, HSDPA)

chapter 13

circuit switching

defdicated circuit per call: telephone net

End-end resources reserved for "call"

link bandwidth, switch capacity
dedicated resources: no sharing
circuit-like (low delay and no loss) (guaranteed) performance
call setup required (缺點)
network resources divided into calls
resource piece idle if not used by owning call (no sharing) (缺點，資源閒置)
devided link bandwidth into "pieces"
- frequency division
- time division

packet switching

data sent thru net in discrete "chunks" (packet)

each end-end data stream divided into packets

user A, B packets share network resources
each packet uses full link backwidth
resources used as needed
resource contention (缺點，資源爭奪)
aggregate resource demand can exceed amount available
congestion: packets queue, wait for link use might loss (缺點，會掉包)
store and forward: packets move one hop at a time (缺點，會等到封包完整抵達之後才會傳送)
- Node receivescomplete packet before forwarding
- Takes L/R seconds to transmit (push out) packet of L bits on to link of R bps
  - bps: bits per second
- Entire packet must arrive at router before it can be transmitted on next link: store and forward
- "store and forward" delay = 3L/R
- So larger packet takes more delay, because of store and forward
  Message Segment
piplining: each link works in parallel
the reason why keep small packets，越小store and forward造成的延遲越低
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →

Statistical Multiplexing
Why store and forward?

Two key network-core functions
- routing: determines source-destination route taken by packets
  - routing algorithms
- forwarding: move packets from router's input to appropriate router output
- Image Not Showing Possible Reasons
  The image was uploaded to a note which you don't have access to
  The note which the image was originally uploaded to has been deleted
  Learn More →
- Because of the forwarding functionality, so we need to store the entire packet
  forwarding
Goad: move packets through routers from source to destination
datagram network:
- destination address in packet determines next hop
- routes may change during session
- analogy: driving, asking directions
virtual circuit network:
- each packet carries tag (virtual circuit ID), tag determines next hop
- fixed path determined at call setup time, remains fixed thru call
- routers maintain per-call state

Packet switching vs. Circuit switching

Packet switching allows more users to use network!

1Mb/s link
each user:
- 100kb/s when "active"
- active 10% of time
circuit-switching:
- 10 users
packet switching:
- with 35 users, probability > 10 active at same time is less than 0.0004

Is packet switching a "slam duck winner" ?

Great for bursty data
- resource sharing
- simpler, no call setup
Excessive congestion: packet delay and loss
- protocols needed for reliable data transfer, congestion control
Q: How to probide circui-like behavior?
- bandwidth guarantees needed for audio/video apps
- still an unsolved problem (chapter 9)

chapter 14

Four sources of packet delay

nodal processing
- check bit errors
- determine output link
queueing
- time waiting at output link for transmission
- depends on congestion level of router
Transmission delay): (傳輸延遲
- R = link bandwidth (bps)
- L = packet length (bits)
- time to send bots into link = L/R
Propagation delay: (物理傳播延遲)
- d = length of physical link
- s = propagation speed in medium (~
  $2 * 10^{8} m / s e c$ )
- propagation delay = d/s

Nodal delay

d_{n o d a l} = d_{p r o c} + d_{q u e u e} + d_{t r a n s} + d_{p r o p}

$d_{p r o c}$ = processing delay
- typically a few microsecs or less
$d_{q u e u e}$ = queuing delay
- depends on congestion
$d_{t r a n s}$ = transmission delay
- = L/R, significant for low-speed links
$d_{p r o p}$ = propagation delay
- a few microsecs to hundreds of msecs

Queueing delay

R = link bandwidth (bps)
L = packet length (bits)
a = average packet arrival rate
traffic intensity = La/R
La/R ~0: average queueing delay small
La/R ->1: delays become large
La/R > 1: more "work" arriving than can be serviced, average delay infinite!

Packet loss

queue (aka buffer) preceding link in buffer jas finite capacity
packet arribing to full queue dropped (aka lost)
lost packet may be retransmitted by previous node, by source end system, or not at all

Throughput

throughput: rate (bits/time unit) at which bits transferred between sender/receiver

chapter 35

TCP: Overview

point-to-point:
- one sender, one receiver
reliable, in-order byte stream:
- no "message boundaries"
pipelined:
- TCP congestion and flow control set window size
full duplex data:
- bi-directional data flow in same connection
- MSS: maximum segment size
connection-oriented:
- handshaking (exchange of control msgs) inits sender, receiver state before data exchange
flow controlled:
- sender will not overwhelm receiver

TCP segment structure

head len: header length, UDP has the hole file length
A，ACK: 當A flag on，代表acknowledgement number有效，傳送者想要確定這些byte有收到

connection managment

表示封包有被做connection management
R，RST: reset connection，重設連接
S，SYN: setup connections，設定連接
F，FIN: tear down a connection，解除連接

P，PSH: push data now, 馬上回推資料 (不太用)
U，URG: urgent data，緊急資料 (也不太用)

其實也有在用的bits，在not used裡面

not really for rdt, not for connection
E、C bit: 工程師預留做condition controll的

Urg data pointer: 當URG flag on，會從Urg data pointer這邊去指向要尋找的資料
receive window: window size for flow controll，要變慢receive window數字會變小，要變快receive window數字就會變大

sequence number、acknowledgement number: rdt用的，注意TCP是用byte為單位傳輸，not packet

chapter 41

Network layer

transport segment from sending to receiving host
network layer protocols in every host, router
sending side: encapsulates segments into datagrams
receiving side: delivers segments to transport layer
router examines header fields in all IP datagrams passing through it

Two key network-layer functions

network-layer functions:
- forwarding: move packets from router's input to appropriate router output
- routing: determine route taken by packets from source to destination
  - routing algorithms
比喻: 旅行
- forwarding: 處理每一個中繼站的交換
- routing: 預處理旅行的起點和目的地

Network layer: data plane, control plane

Data plane
- local, per-router funciton
- determins 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
- 處理 routing funciton
- two control-plane approaches:
  - traditional routing演算法
    - distribute, locally
    - implemented in routers
  - software-defined networking(SDN)
    - centralized
    - implemented in (remote) servers

Per-router data plane

Forwarding table to allow fast output interface lookup

Network-wide logic in control plane

Traditional: Individual routing algorithm components in each and every router interact in the control plane

Logically centralized control plane

SDN: A distinct (typically remote) controller interacts with local control agents (CAs)

chapter 42

Router 架構

Input port functions

decentralized switching:
- using header field values,利用記憶體裡面的 forwarding table 查找 output port
目標: 在line speed下，完成input port處理
queuing: if datagrams arrive faster than forwarding rate into switch fabric
destination-based forwarding: forward based only on destination IP address (traditional) (比較快、便宜)
generalized forwarding: forward based on any set of header field values (SDN) (比較慢，所以要更快的lookup處理，所以比較貴)

Switching fabrics

transfer packet from input link to appropriate output link
switching rate: rate at which packets can be transfer from inputs to outputs
- often measured as multiple of input/output line rate
- N inputs: switching rate N times line rate desirable
three major types of switching fabrics

Switching via memory

first generation routers:

速度最慢，成本最低

Swtiching via a bus

多人傳送時有競爭
交換速度取決於bus的頻寬

Switching via interconnection network

每個人一個bus

Input port queuing

HOL問題: 第一個封包送不出去，所以影響到後面的封包

Output port queuing

進來速度 > 出去速度就會有queue問題

Buffer Management

drop
- 剛進來的先丟
- 有優先權的話，低的先丟

Packet Scheduling: FCFS

packet schefuling: 決定誰先傳
- 先進先服務(FCFS)
- 優先權
- 輪流
- 優先權決定服務權重
FCFS: 就是First-in-first-out(FIFO)

Scheduling policies: priority

priority scheduling:

把進來的東西分等級，根據等級排順序
同個等級FCFS

Scheduling policies: round robin

分等級，每個等級輪流輸出

Scheduling policies: weighted fair queuing

Weighted Fair Queuing (WFQ):

每個等級都給服務，但服務權重不同

chapter 43

Network Layer: Internet

host, router network layer functions:

IP Datagram format

ver: 版本
head len: header 有多長，新版ipv6是固定長度
tos(type of service): 資料欄位服務形式
length: 包含header的長度
如果ip要切割的話，需要這些欄位
time to live: 為了避免有些有問題的封包，找不到目的地，但是被一直繞送，所以每次轉送這個封包，這個欄位就會-1，當值為0，router就會把這個封包丟掉，然後告訴sender這個封包被丟掉了
upper layer: 說明上層的欄位哪個協定處理
header checksum: 判斷收到的封包有沒有錯誤
source ip: 就sender ip
destination ip: 就receiver ip
options: 選項增加的欄位

IP fragmentation/reassembly

當從MTU比較大的網路進入到MTU比較小的網路，封包就需要切割，在router切割
重組只能在receiver執行
16bit identifier: 辨識哪些原本是同一個ip封包的
flgs: 知道哪個ip分段是最後一個分段，辨識什麼時候結束，0代表後面沒有了，1代表後面還有
fragment offset: 辨識切割前順序的編號，8bytes為一單位

IP addressing: introduction

ip address: 32-bit identifire，定義到網卡上面，是定義在介面，一台機器可能會有多個ip，所以要說是某台機器的某一個介面的ip
interface: connection between host/router and physical link
- 通常一台router有多個介面，所以有多個ip
- host通常只有一或兩個介面(e.g., wired Ethernet, wireless 802.11)

Subnets 子網路

ip分為兩段，前段一樣的話代表在同一個子網路
互相連接的設備在同一個子網路的話不用透過router
IP addresses have structure
- subnet part: 設備在同一個子網路前面會有同樣的ip
- host part: 後面那段ip會不一樣

IP addressing: CIDR

CIDR: Classless InterDomain Routing

https://aws.amazon.com/tw/what-is/cidr/

DHCP: Dynamic Host Configuration Protocol

動態配置ip
goal: 當host加入網路時，動態配置ip給他

可以租借一個ip來用，server會說可以用多久
允許使用以前用過的ip
支援加入網路的mobile用戶
實現了少量ip服務多數人

DHCP: more than IP address

還會給default gateway和DNS
first-hop router 的地址
name and IP address of DNS server
network mask (indicating network versus host protion of address)

IP addresses: how to get one

ISP要跟國際組織申請

chapter 62

Internet checksum

https://www.cnblogs.com/shelmean/p/16091622.html

Cyclic redundancy check CRC

除法進行時，用XOR做餘數計算

chapter 63

multiple access protocols

Multiple access links, protocols

兩種links:

point-to-point 點對點
- point-to-point link between Ethernet switch, host
- PPP for dial-up access
broadcast (shared wire or medium) 被多人共享
- old-fashioned Ethernet
- upstream HFC in cable-based access network
- 802.11 wireless LAN, 4G/4G, satellite

Multiple access protocols

決定哪一個人哪一個節點何時傳送
決定發言的機制
用同一個頻道控制

理想的 multiple access protocols

用於判斷協定優缺
給定環境: multiple access channel of rate R bps

如果只有一個人在用，那他要可以用到全部rate R速度
當有M個節點要用，那平均速率要R/M
fully decentralized(完全分散式):
- 沒有一個特別的node去處理排程、協調、碰撞
- 節點彼此不用同步
simple 簡單

Random access protocols

沒有事先規劃好哪個節點在什麼時候傳送

when node has packet to send
- 傳送時使用完整rate R
- 沒有排程
two or more transmitting nodes: collision 碰撞
random access MAC protocol 著重於:
- 如何偵測碰撞
- 如何解決碰撞
examples of random access MAC protocols:
- ALOHA, slotted ALOHA
- CSMA, CSMA/CD, CSMA/CA

Pure ALOHA

幾乎沒有限制，沒有規定時間，沒有規定環境
很容易發生碰撞
發生碰撞的機率是兩個packet time，發送前、發送後
pure Aloha 效率: 18%

Slotted ALOPHA

假設:

所有封包大小一樣
時間切成大小一樣的time slot
nodes只能在slot開始的時候傳送
nodes同步了
如果有兩個含以上在slot裡面，全部nodes都偵測到碰撞

操作:

node要傳送只能在下一個slot開始的時候傳送
- 沒有碰撞就成功了
- 有碰撞就在後面的slot以機率p的方法決定傳送，直到成功

效率

優點:

一個人要使用可以使用全部資源
分散式的，但是要同步
簡單

缺點:

碰撞
idle slots
node可能會花很多時間在處理碰撞
要同步
很多人要用不能均分

Reference

好看影片: https://www.youtube.com/@pollyhuang
還有隔壁班老師的影片