# Introduction to Computer Networks

###### tags: `MyNTUST`

{%hackmd @CA-Lee/MyNTUST_banner %}

[TOC]

Introduction
===

What is the Internet?
---

### "Nuts and Bolts" View (元件論)

graph TD

gi(("global ISP"))
ri(("regional ISP"))
mn(("mobile network"))
hn(("home network"))
in(("institutional<br>network"))
gi --- ri --- hn
ri --- in
gi --- mn

- Hosts
- PC
- Laptop
- IoT devices
- End systems which connected each other
- ~billions
- Communication links (傳輸媒介)
- Fiber (光纖)
- SNG car
- Copper (銅纜)
- Radio
- Limited by **bandwidth (頻寬)**
- Packet switches
- Router (路由器)
- Switch (交換器)
- Forward packets (封包) (chunk of data), like post office
- Internet (網際網路)
- Network of networks
- Protocols (通訊協定)
- TCP
- IP
- HTTP
- 802.11
- Skype
- Internet standards
- RFC (Request for comments)
- [RFC1149](https://datatracker.ietf.org/doc/html/rfc1149)
- IETF (Internet Engineering Task Force)

### A service view

> Internet 提供哪些服務

- Distributing applications, providing services
- Instant messaging
- VoIP
- Online games
- E-commerce
- Social nets
- Socket interface
- Platform providing communication services for applications

### What's a protocol

- The rule to communication
- Human protocol

    sequenceDiagram
    Alice ->> Bob: Hi
    Bob ->> Alice: Hi
    Alice ->> Bob: Got the time?
    Bob ->> Alice: 2:00

- Machine protocol

    sequenceDiagram
    Client ->> Server: TCP connection request
    Server ->> Client: TCP connection response 
    Client ->> Server: Get http://www.awl.com/kurose-ross
    Server ->> Client: <file>

Network edge
---

### Network Structure

- Host (主機)
- Clients (客戶端)
- Servers (伺服器)
- Often in datacenter
- Edge computing / cloud computing
- 在靠近 client 的地方增設 server，在靠近 client 的 server 運算稱為 edge-computing，在離 client 較遠的 server 上運算稱為 cloud-computing
> 實際上沒有這麼單純
- Offloading (卸載)
- Server 自己負擔不了，所以交給別的 server 處理
- Edge server 卸載給 cloud server
- 4G 卸載給 3G
- Access networks, physical media
- 存取網路的媒介
- Wire: fiber, copper, etc.
- Wireless: WiFi, starlink, etc.
- Network core
- Interconnected routers

### Access Networks and Physical Media

- Connect end systems to edge router
- Bandwidth
- 每秒可以傳多少資料
- Often use bits per second (bps)
- May be dedicated (專屬) or shared
- DSL: digital subscriber line
- 用 modem 將信號藉由既有的電話線傳輸至 DSLAM (DSL access multiplexer), DSLAM 將電話線上的網路訊號分離 (解調變) 出來
- ADSL: 非對稱 DSL
- 上傳下載速度不一樣
- Cable Network

    graph LR
    TV --- cm["cable modem"] --- |tv cable| ctms["CTMS"] --- ISP

- Use TV cable (deliver in other frequency)
- Frequency division multiplexing (FDM)
- HFC (hybrid fiber coax)
- 混和光纖同軸電纜
- https://en.wikipedia.org/wiki/Hybrid_fiber-coaxial
- Home network
- Access point
- 家用 WiFi
- Enterprise network
- 有自己的 network、switches、routers、gateway、firewall
- 10Mbps~10Gbps
- Wireless access networks
- Wireless LAN
- 室內 (通常)
- Wi-Fi (802.11 b/g/n)
- 11, 54, 450 Mbps
- Wide-area wireless access (WAN)
- Telcom
- 10's km 等級的距離
- 1 ~ 10 Mbps
- 3G, 4G: LTE
- Host sending function of data
1. Takes message
2. Split into chunks of length *L(bits)*
3. Transmits in network by transmission rate *R(bits/sec)*
- Transmission rate = bandwidth
- Transmission delay(sec) = *L*/*R*

### Physical media

- Guided media
- 訊號在導線內傳輸
- TP (雙絞線)
- UTP
- STP
- Cat 5: 100 Mbps ~ 1 Gbps
- Cat 6: 10 Gbps
- 
- Fiber
- 傳輸媒介是玻璃
- 10 Gbps ~ 100 Gbps
- 低出錯率
- 不怕電磁干擾
- Coax (同軸電纜)
- 
- Unguided media
- 訊號自由四處擴散
- Radio
- 透過電磁波傳遞
- 會被反射、阻擋、干擾
- Link types
- Terrestrial microwave (地面微波站)
- 45 Mbps
- LAN
- WiFi
- 54 Mbps
- Wide-area
- 4G cellular
- 10 Mbps
- Satellite
- 45 Mbps
- 270 ms end-to-end delay
- geosynchronous (同步衛星) or low altitude (低軌道衛星)

Network core
---

- Mesh of routers

### Packet Switching

- Hosts break app-layer messages into packets
- Store-and-forward
- Entire packet must arrive at router before it can be transmitted (先儲存再轉送)
- End-to-end delay = 2L/R (忽略其他delay)
- Queueing delay & loss
- Arriving rate > transmission rate $\to$ queueing
- Buffer full $\to$ packet dropped (lost)
- Routing and Forwarding
- Routing: 透過 routing algorithm 決定 source-destination route (封包傳送的路線)，產生 forwarding table
- Forwarding: 參考 forwarding table 來轉送封包

### Circuit Switching

- End-end resources allocated to, reserved for "call" between source & dest
- Dedicated resources
- Guaranteed performance
- Circuit segment idle if not used by call (no sharing)
- E.g. telephone network
- FDM
- Split by frequency
- 在不同頻段同時傳輸
- TDM
- Split by time
- 在不同時間（同個頻段）傳輸

### Packet Switching vs. Circuit Switching

- Packet switching allows more users to use network
- n 個使用時間百分比為 p 的使用者中 k 個人同時上線的機率是 $\mathrm{ C }^n_k \cdot p^k \cdot (1-p)^{n-k}$ (二項式分布)
- E.g. 35 個 user，每人只使用 10% 的時間，則 10 人以上同時上線的機率小於 0.0004
- Advantages of packet switching
- Great for bursty (短時間大量的) data
- Resource sharing
- No call setup
- Disadvantages of packet switching
- Excessive congestion (壅塞) will cause packet delay and loss
- Protocols needed for reliable data transfer, congestion control
- Virtual circuit (VC)
- Provide circuit-like behavior in packet switched network
- https://en.wikipedia.org/wiki/Virtual_circuit

### Internet Structure


- Access ISPs
- Internet Service Provider
- 住家、公司、學校網路
- 提供終端使用者連線到網際網路的服務
- 發展性受**經濟**及**政治**影響
- Regional ISP
- 提供地理位置鄰近的 Access ISP 之間的連線交換
- Peering link
- 提供兩個 ISP network 互連
- Internet exchange point (IXP)
- 在 ISP scope 外，提供多個 ISP 之間的連線交換
- Tier 1 ISP
- 涵蓋範圍為一個或多個國家
- PS: tier 1 需要 full mesh
- e.g. Level 3, AT&T, Sprint, NTT
- Content provoder network
- 由大公司提供的網路服務，等級和 tier 1 ISP 差不多

> 參考資料：[從 0 開始的 Web Security 系列](https://ithelp.ithome.com.tw/users/20129897/ironman/3431)

Delay, loss, throughput
---

- Delay
- 處理 packet 所耗的時間
- Transmission delay
- packet 從開始傳送到完全送完所耗的時間
- delay = bits/bps
- Propogation delay
- 從 router A to B 之間所耗的時間
- 主要是物理因素
- $\simeq 2 \times 10^8$ m/s
- Nodal processing delay
- 在 router 內部傳遞所耗的時間
- check error bit
- determine output link
- $\lt 10^{-3}$ s
- Queueing delay
- 排 queue 所耗的時間
- Congestion level
- 塞車嚴重程度
- Delay
- R: 可處理的頻寬 (bps)
- L: packet length (bits)
- a: packet arrival rate
- delay = La/R
- $La/R \simeq 0$ : small delay
- $La/R \to 1$ : very large delay
- $La/R \gt 1$ : unstable, arriving more than consuming
- [M/M/1 queue](https://en.wikipedia.org/wiki/M/M/1_queue)
- Real world Internet delay & routes
- `traceroute` on Linux
- `tracert` on Windows

        C:\Users\CA-Lee>tracert ntust.edu.tw

        在上限 30 個躍點上
        追蹤 ntust.edu.tw [140.118.31.99] 的路由:

          1     2 ms     2 ms     3 ms  192.168.64.158
          2   163 ms   139 ms   180 ms  10.156.65.145
          3    26 ms    23 ms    17 ms  10.156.65.97
          4    22 ms    16 ms    23 ms  10.156.71.23
          5    19 ms    18 ms    20 ms  10.156.71.34
          6    28 ms    21 ms    23 ms  tpdb-3312.hinet.net [210.65.126.98]
          7    17 ms    23 ms    36 ms  tpdb-3031.hinet.net [220.128.1.254]
          8    18 ms    26 ms    29 ms  tpdt-3308.hinet.net [220.128.1.101]
          9    22 ms    23 ms    22 ms  tp-pc1-c12r2.router.hinet.net [203.75.135.1]
         10    20 ms    23 ms    28 ms  192.192.61.49
         11    23 ms    23 ms    21 ms  192.192.61.81
         12    22 ms    23 ms    30 ms  192.192.7.198
         13     *        *        *     要求等候逾時。
         14     *        *        *     要求等候逾時。
         15    28 ms    22 ms    29 ms  140.118.250.6
         16    19 ms    53 ms    25 ms  ntust.edu.tw [140.118.31.99]

        追蹤完成。

- Loss
- Router's buffer 塞滿了，後面來的 packet 直接噴掉，不會進到 queue 也不會被處理
- May be retransmission by previous node or source
- M/M/1/k
- Throughput
- 單位時間內可以通過（進入&離開）的資料量 (bps)
- 分 instantaneous/average
- 區段的 throughput 等於區段內最小的 throughput

Protocol Layers, Service Model
---

> 分層分工，模組化

- Internet protocol stack
- Application (most top)
- FTP, HTTP
- Transport
- TCP, UDP
- Network
- Routing
- IP, routing protocols
- Link
- Transfer data to neighboring devices
- Ethernet, 802.11 (Wi-Fi), PPP
- Physical (most bottom)
- 實體媒介，如線路
- Physical is layer 1, application is layer 5
- OSI reference model
- Published by ISO
- 7 layer
- Application
- Presentation
- Encrypt, decrypt, compression, etc.
- Session
- Manage connection (synchronization, checkpointing, recovery of data exchange)
- Transport
- Network
- Link
- Physical
- Two layers was merged into application layer in Internet stack
- Encapsulation（封裝）

    graph TD
    subgraph "frame(link layer)"
    lheader["link header"]
    subgraph "datagram(network layer)"
    nheader["network header"]
    subgraph "segment(transport layer)"
    theader["transport header"]
    subgraph "message(application layer)"
    data
    end
    end
    end
    end

- 不是每個 node 都要處理全部的layer
- Only layer 1 (physical): Repeater
- Only layer 1~2: Switch
- Only layer 1~3: Router

Scurity
---

- Field
- How to attack
- How to defend
- How to design an architechture that is immune to attacks
- 網際網路一開始並沒有考慮安全性
- 預期大家都可以互相信任
- 每一層都可以做安全性防護

### 把惡意程式透過網際網路植入目標

- Virus
- 透過使用者接收/執行某個程式
- Worm
- 透過被動接收/感染
- Spyware
- 可以記錄使用者金鑰、瀏覽紀錄
- 可以暗中上傳資料到伺服器
- Botnet
- 將電腦 compromised (攻破) 後用作殭屍主機，常被拿來進行 DDoS
- Denial of Service (DoS)
- 惡意佔滿伺服器的處理資源，使服務無法被其他使用者使用
- 步驟
1. 找到目標
2. 取得附近的網路中的殭屍電腦
3. 使用大量的殭屍電腦發送服務請求給目標伺服器
- Packet sniffing
- 嗅探（竊聽）
- 工具軟體: wireshark
- IP spoofing
- 偽造
- 使用假的 IP 發送封包

History
---

### Early packet-switching priciples

- 1961: queueing theory，透過理論建立封包交換機制
- 1964: Baran - packet-switching in military nets
- 1967: ARPAnet (美國軍方網路) concevied by Advanced Research Projects
- 1969: 第一個 ARPAnet 節點開始運作
- 1972
- ARPAnet 發布
- NCP: 第一個 host to host 協定
- 第一個email程式
- ARPAnet 達到15個節點

### Internetworking, new and proprietary nets

- 1970: ALOHAnet satellite network in Hawaii
- 1974: Architechture for interconnecting networks
- mininalism, autonomy
- best effort
- stateless routers
- 去中心化控制 (管理)
- 1976: Ethernet at Xerox PARC
- late70's: proprietary architectures: DECnet, SNA, XNA
- switching fixed length packets (ATM precursor)
- 1979: ARPAnet has 200 nodes
- Cerf and Kahn's internetworking principles
- Minimalism, autonomy - no internal changes required to interconnect networks
- Best effort service model
- Stateless routers
- Decentralized control

> 1973 年的*整個* Internet ([src.](https://www.weforum.org/agenda/2019/03/this-paper-map-shows-the-extent-of-the-entire-internet-in-1973))
> 

### New protocols, a proliferation of networks

- 1982: 制定 SMTP
- 1983: TCP/IP 上線
- 1983: 制定 DNS
- 1985: 制定 FTP
- 1988: 制定 TCP 流量控制規範
- 100,000 hosts

### Commercialization, the Web, new apps

- 1990's: ARPAnet 除役
- 1990's: Web 技術出現
- 1995: NSFnet 除役
- 1990 ~ 2000
- Instant messaging, P2P file sharing
- ~ 50 million hosts

### Present

- ~ 5B devices attached to Internet
- 更積極地布建寬頻設備
- 高速無線網路普及化
- 出現社群網路 (FB)
- Service providers (Google, Microsoft) 建立自己的網路
- 電子商務、大學、企業開始使用雲端運算

Application Layer
===

Principles of network applications
---

- 目標是把實際的應用功能實作出來

### Network app

- A program that runs on (different) end system
- Communicate over network
- No need to write program for network-core device (e.g. routers)
- P2P
- 每個 end system 都是 client & server

### Client-server architecture

- Server
- Always on
- Permanent IP address
- Data centers (串聯多台硬體主機) for scaling
- Client
- Communicate with server
- May be intermittently (間歇性地) connected
- May have dynamic IP addresses
- Do not communicate directly with each other

### P2P architecture

- No always-on server
- Arbitary (數個) end systems directly communicate
- Peers reauests server from other peers, provide service in return to other peers
- Self scalability
- More peer, more capacity
- Peer may have no permanent connection and IP address
- Cause more complexity to management
- 有時會有中心伺服器負責協調節點
- Pure P2P: have no central server to manage peers
- E.g. file sharing

### Processes communicating

- Process is a program running within a host
- Communicating
- In same host
- Inter-process communication
- Defined by OS
- In different hosts
- By exchanging messages
- Communicated over network
- Client process
- Process that initiates (create) communication
- 主動發起連線
- Server process
- Process that waits for connections
- 被動接受連線

### Sockets

- 應用層和傳輸層的對話窗口
- 可以當成傳送門，資料丟進去就會傳到對方那邊，剩下的不用管

### Addressing processes

- 為了分辨不同的 process，所以分派不同的 port 編號給不同的 process
- IP 定位 host，port 定位 host 內的 process

### App-layer protocol defines

- Types of messages exchanged
- E.g. request, response
- Message syntax (語法)
- What fields in messages
- How fields are delineated (描述)
- Message semantics (語意)
- Meaning of information in fields
- Rules for when and how processes send respond to messages
- Open protocols
- Defined in RFCs
- Allows for interoperability
- E.g. HTTP, SMTP
- Proprietary protocols
- E.g. Skype
- Private
- Usually used in company

### What transport service providing

- Data intergrity
- 100% reliable date transfer
- Other apps (audio) can tolerate (容許) some loss
- Timing
- Some apps require low delay to be "effective"
- Throughput
- Some apps (multimedia) require minimum amount of throughput to be "effective"
- Other apps ("elastic apps") make use if whatever throughput they get
- transport service requirements of common apps
> 右下區多空了一行

### Internet transport protocols services

- TCP sevice
- Reliable transport
- Flow control
- Congestion control
- Does not provide
- timing
- minimum throughput guarantee
- security
- Connection-oriented
- UDP service
- Unreliable date transfer
- Does not provide
- reliability
- flow control
- congestion control
- timing
- throughput guarantee
- security
- connection setup
- Protocol 沒有提供的功能，你可以自己做
- Internet apps: application, transport protocols


### Securing TCP

- TCP & UDP
- no encryption
- cleartext passwords sent into socket traverse Internet in cleartext
- SSL
- Socket layer
- Provieds incrypted TCP
- Data integrity
- End-point authentication
- SSL is at app layer
- Apps use SSL libraries, that "talk" to TCP
- SSL socket API
- Cleartext in secured tunnel

Web (網頁) and HTTP
---

- Web page consists of objects
- Object can be HTML file, JPEG image, JAVA applet, audio file, etc.
- Web page consists of base HTML-file (base file) includes several refrenced objects
- Each object is addressable by a [URL (網址)](https://en.wikipedia.org/wiki/URL)
- 一台主機上的一個路徑下的物件

### HTTP overview

- HTTP: **h**yper**t**ext **t**ransfer **p**rotocol
- Application layer protocol
- Use TCP in transport layer
- Often use port 80
- SSL often use port 443
- Use client/server architecture
- Client intiates TCP connection to server, send request, receive response
- Server accepts TCP connection from client
- HTTP messages and Web server
- TCP connection closed
- HTTP is **stateless**
- Server maintains no information about past client requests
- 因為記狀態太複雜了
- 如果其中一邊 crash，會造成 client/server 狀態不同步
- 如果 client 很多，會造成 server 很大的負擔

### HTTP connections

- **RTT**: time for a small packet to travel from client to server and back
- Non-persistent HTTP
- At most one object sent over TCP connection
- Connection then closed
- Downloading multiple objects required multiple connections
- Response time
- 1 RTT: initiate TCP connection
- 1 RTT: HTTP request
- File transmission time (F)
- Total = 2 \* RTT + F (for every file/object)
- Persistent HTTP
- Multiple objects can be sent over single TCP connection between client, server
- Non-persistent HTTP issues
- Requires 2 RTTs per object
- OS overhead for each TCP connection
- Browsers often open **parallel** TCP connections to fetch refrenced objects
- Less response time
- Limited by system restriction of parallel connections at the same time
- Server leaves connection open after sending response
- Subsequent HTTP messages between same client/server sent over open connection
- Client sends requests as soon as it encounters a refrenced object
- As little as one RTT for all the referenced objects
- Pipelining
- Request N files at one HTTP request
- Response time: RTT + NF for N files
- Response time
- Total = 2RTT + F (for base file) + RTT + NF (for referenced file/object)

### HTTP messages

- Header lines
- last line is `\r\n`
- `\r\n` indicate end of line
- Request
- Request line
- Method
- HTTP 1.0
- GET
- POST
- HEAD
- HTTP 1.1
- GET
- POST
- HEAD
- PUT
- DELETE
- Path
- HTTP version
- Header lines
- Only ASCII code are allowed
- Response
- Status line
- Protocol
- Status code
- 200 OK
- 301 Moved Permanently
- 400 Bad Request
- 404 Not Found
- 505 HTTP Version Not Supported
- Status phrase
- Header lines
- Body

### User-server state: cookies

- 把狀態記在自己的電腦 (client)
- Components of cookie
- Header line of HTTP response
- Header line in next HTTP request
- Files on user's host, managed by browser
- Back-end database on server
- Step of using cookie
- 
- 使用領域
- Authorization
- 購物車
- 推薦系統
- User session state in web mail
- Cookie and privacy
- Cookies permit sites to know more about you
- May cause personal information leaking

---
以下尚未整理的分隔線
---

### Cache (Proxy server)

> 讀作 cash

- 讓 client 不用跟原 server 拿資料
- Proxy server 如果沒有資料，就會跟 server 拿，然後回給 client 且自己留一份，當 client 下次再要求一樣的檔案時，proxy 就會將自己留存的那份回傳給 client。
- Edge-cloud architecture
- Proxy server 是 client 也是 server
- Often set by ISP
- Pros
- Reduce response time
- Reduce traffic on access link
- Enable poor content providers to effectively deliver content

E-mail
---

DNS
---
- hostname to IP address translation
- TLD: Top-Level Domain, com, org, fr, uk, edu

P2P
---
- peer to peer, in comparison to C-S
- BitTorrent: group of peers exchanging chunks of a file.
tracker & peers, tracker tracks peers participating in torrent,peer sends chunks in tit-for-tat way, if you help me, I help you, other Ps are choked if they do not receive chunks from a specific P Alice.

Video streaming and content distribution networks (CDN)
---
- CDN: Content Distribution Network,
- enter deep: push CDN S deep into many access network.
- bring home: smaller num of larger clusters in POPs near access network.

Socket programming with UDP and TCP
---

Transport layer
---

- network layer
- logical communication between hosts
- transport layer:
- logical communication between processes
- relies on, enhances, network layer services

demultiplexing
---
- host revieces IP datagrams
- each datagram has source IP address destination IP address
- each datagram carries one transport-layer segment
- each segment has source, destination port number
- host uses IP address & port numbers to direct segment to appropriate socket
- TCP socket identified by 4-tubpe
- source IP address
- source port number
- dest IP address
- dest port number
- demux
- reciever uses all four values to directo segment to appropriate socket

UDP
---
- User Datagram Protocol, unreliable data transfer between S/R process, no flow control, timing, throughput gurantee, security connection setup, applied in multimedia, telephony, net manager.

---
以上尚未整理的分隔線
---

Transport Layer
===
- logical communication between application processes running on different hosts
- 一個譬喻
| 電腦系統 | 郵政系統 |
| -------- | -------- |
| application messages | 信封裡的信 |
| processes | 特定屋子裡的原收寄件人 |
| hosts | 屋子 |
| transport-layer protocol | 特定屋子裡收集郵件集中收發的某甲 |
| network-layer protocol | 公用郵政系統 |
| demultiplexing | 從郵差收到信後，某甲根據收件人分派郵件 |
- 可以同時存在運行不同的傳輸協定
- 可以在網路層基礎上提供額外特定服務（如：加密）

Transport-layer services
---
- segment: transport-layer packet **(in this book!!!)**
- RFC 使用 segment 指 TCP packet, 用 datagram 指 UDP packet, 但也用 datagram 指 network-layer packet
- IP(Network-layer):
- best-effort delivery service 最佳努力遞送服務，但不保證結果、順序與完整性
- unreliable 不可靠
- TCP:
- reliable data transfer 可靠資料傳輸
- congestion control 壅塞控制

Multiplexing and demultiplexing
---
- Extending host-to-host delivery to process-to process delivery
- Demultiplexing:
- delivering the data in a transport-layer segment to the correct socket
- Multiplexing:
1. gathering data chunks at source host from different sockets
2. encapsulating each data chunk with header information to create segments
3. passing the segments to the network layer
- required:
- sockets have unique identifer
- segment have **source port number field** and **destination port number field** to indicate the socket to which the segments have to be delivered
- well-known port numbers: ranged from 0 to 1023
- 由知名應用協定使用的埠號
- given in RFC 1700, updated at http://www.iana.org

### Connectionless Multiplexing and Demultiplexing
- 通常 client side 會讓 transport layer 自動指派 port
- server side 需指派 port

### Web server and TCP
- client 對 Web server 的 segments port 都是同一個
- Web server use only one process and create a new thread with a new connection socket for each new client connection

Connectionless transport: UDP
---
- protocol 功能內容:
- multiplexing/demultiplexing
- light error checking
- no further things
- (if use UDP rather than TCP) almost directing talking with IP
- example: DNS
- Adventage:
- Finer applection-level control over what data is sent and when
- No connection establishment
- No conneection state
- Small packet header overhead

| Application | Application Protocol | Transport Protocol |
| ---------------------- | --------------------- | ------------------ |
| Electronic mail | SMTP | TCP |
| Remote terminal access | Telnet | TCP |
| Web | HTTP | TCP |
| File transfer | FTP | TCP |
| Remote file server | NFS | (Typically) UDP |
| Streaming multimedia | typically proprietary | UDP or TCP |
| Internet telephony | typically proprietary | UDP or TCP |
| Network management | SNMP | (Typically) UDP |
| Name translation | DNS | (Typically) UDP |

- Segment Structure
- Source port #
- Dest. port #
- Length
- Checksum
- error detection (determine whether bits within the UDP segment have been altered)
- sender side: 1s complement of the sum of all the 16-bit words in segment
- receiver side: add all words and checksum to become 1111 1111 1111 1111
- Application data
- end-end principle
- functions placed at the lower levels may redundant or of little value when compared to the cost of providing them at the higher level
- checksum exist because:
- no guarantee that all the links between source and desination provide error checking
- bit error may be introduced when segment is stored in a router's memory

Principles of reliable data transfer
---
- Provided service and service implementation
- 走傳輸層可靠 和 可靠地將資料封包送進(不可靠的)網路層傳輸後並可靠的解析
- unidirectional data transfer: 單向將資料從送出側到接收側
- bidirectional data transfer(雙向)在此不討論
### Building Reliable Data Transfer
- Over a Perfectly Reliable Channel (rdt 1.0)
- 發送端:
1. 等待上層呼叫
2. 從上層接收data
3. 創造packet
4. 發送packet至下層
5. 回到 1.
- 接收端:
1. 等待下層呼叫
2. 從下層接收packet
3. 從packet提取data
4. 將data通至上層
5. 回到 1.
- Over a Channel with Bit Errors
- Term:
- positive acknowledgment (ACK)
- negative acknowledgment (NAK)
- Automatic Repeat reQuest protocol (ARQ protocol)
- function:
- Error detection
- Receiver feedback
- Retransmission
- rdt 2.0 (stop-and-wait)
- 發送端:
1. 等待上層呼叫
2. 從上層接收data
3. 用data與checksum創造packet
4. 發送packet至下層
5. 等待接收ACK或NAK
6. 接收ACK: 傳輸完成, 回到 1.
7. 接收NAK: 傳輸失敗, 重新發送packet, 回到 5.
- 接收端:
1. 等待下層呼叫
2. 從下層接收packet並檢查bit error
3. 未毀損: 從packet提取data, 將data通至上層, 發送ACK, 回到 1.
4. 毀損: 發送NAK, 回到 1.
- rdt 2.1
- 解決 rdt 2.0 不能檢查ACK/NAK的corrupt
- 加入 sequence number
- 發送端:
1. 等待上層呼叫**0**
2. 從上層接收data
3. 用data與checksum創造packet
4. 發送packet至下層
5. 等待接收ACK0或NAK0
6. 接收ACK0: 傳輸完成, 前往 8.
7. 接收NAK0: 傳輸失敗, 重新發送packet, 回到 5.
8. 等待上層呼叫**1**
9. 從上層接收data
10. 用data與checksum創造packet
11. 發送packet至下層
12. 等待接收ACK1或NAK1
13. 接收ACK1: 傳輸完成, 前往 1.
14. 接收NAK1: 傳輸失敗, 重新發送packet, 回到 12.
- 接收端:
1. 等待下層呼叫0
2. 從下層接收packet並檢查bit error
3. 未毀損: 從packet提取data, 將data通至上層, 發送ACK0, 前往 5.
4. 毀損: 發送NAK0, 回到 1.
5. 等待下層呼叫1
6. 從下層接收packet並檢查bit error與sequence number
7. 未毀損: 從packet提取data, 將data通至上層, 發送ACK1, 前往 1.
8. 毀損: 發送NAK0, 回到 5.
- rdt 2.2
- 將ACK0/NAK1整合、ACK1/NAK0整合（僅修改發送端）
- rdt 3.0 (alternating-bit protocol)
- 以 2.2 為基礎，加入timeout檢查(by countdown timer)
- Pipelined
- rdt 3.0 的效率問題(等到timeout才做事 OR timeout太快白做工)
- lost packet
- lost ack
- premature timeout
- utilization:$U_{sender}=\frac{L/R}{RTT+L/R}$
- Go-Back-N(GBN) protocol
- sliding-window protocol
- 連續送N(window size)個封包，收到一個ACK就發下一個，收到NAK就從NAK起重發
- 接收端不需暫存
- 要會畫operation圖（投影片50頁、課本254頁）
- Selective Repeat(SR)
- 在window size中只重發錯誤的，window size必須是ack number數量的一半否則無法區分重發或新資料
- 要會畫operation圖（投影片54頁、課本257頁）
### 詞彙彙整表
- Checksum: 檢查傳輸封包中的bit error
- Timer: 計算timeout/retransmit封包，造成此需要的原因通常是因為傳輸過程中遺失(請求或ACK)
- Sequence number: 標明封包的序列編號，確定ACK/NAK是在回應一串請求的哪一個
- Acknowledgment: 接收端回應送出端成功
- Negative acknowledgment: 回應不成功
- Window, pipelining: 連續傳送一定區間長度的請求

Connection-oriented transport: TCP
---
- connection-oriented: before one application process can begin to send data to another, the two processes must first "handshake" with each other
> TCP "connection" is a logical circuit, not TDM or FDM
> only in end system
- full-duplex: At the ame time can do both from A to B and from B to A
- point-to-point
- three-way handshake: 第三個segment才有可能攜帶payload, 前兩個沒有
- MSS = maximum segment size
- MTU = maximum transmissioon unit

### Segment Structure (typically 20 bytes, 12 bytes more than UDP)
- source and dest port #
- sequence number (32 bits)
- TCP 將資料視為無結構有序位元組流，此區就是用來標示標示此封包第一個位元組的編號
- acknowledgment number (32 bits)
- ACK#就是對方傳的下一個seq# (cumulative acknowledgments)
- receive window (16 bits)
- header length (4 bits)
- options field
- flag (6 bits)
- ACK bit: 指示 ACK# 攜帶的值是否正確
- RST, SYN, FIN: 建立與撤除連線用
- CWR, ECE
- PSH: 指示是否需立即將資料通過到上層
- URG: 指示發送端被標記為 urgent 的上層實體
- urgent data pointer

### Round-Trip Time Estimation and Timeout
- Estimating RTT
- SampleRTT: the amount of time between when the segment is sent and when an acknowledgment for the segment is received
- EstimatedRTT: average of the SampleRTT values
- $EstimatedRTT(new)=(1-\alpha)·EstimatedRTT(previous)+\alpha·SampleRTT$
- recommended alpha value: 0.125 [RFC 6298]
- exponential weighted moving average (EWMA)
- DevRTT: estimate of how much SampleRTT typically deviates from EstimatedRTT
- $DevRTT(new)=(1-\beta)·DevRTT(previous)+\beta·|SampleRTT-EstimatedRTT|$
- recommended beta value: 0.25
- also an EWMA
- Setting and Managing Timeout Interval
- $TimeoutInterval=EstimatedRTT+4·DevRTT$
- initial Timeout recommended 1 sec [RFC 6298]
- when timeout occurs, double TimeoutInterval

### Reliable Data Transfer
- the recommended TCP timer management procedures use only a single retransmission timer
- Scenarios
- 送一個 segment 然後 ACK loss 所以 timeout -> retransmisson
- 送兩個 segment 然後 timeout 所以 resent 第一個 segment，並在這次的 timeout 期間收到第一次的兩個 ACK -> 不必 retransmisson 第二個 segment
- 送兩個 segment 然後第一個 loss 第二個 ACK，且在 timeout 前都收到 -> 第一個 segment 因為 cumulative ACK 的特性而不被 retransmisson
- TCP ACK Generation Recommendation
- 接收預期的 segment 且沒有尚未發送 ACK 的資料 -> delayed ACK, 等待 500ms 後若無接收到新的合乎預期的 segment 則 ACK
- 接收預期的 segment 且有尚未發送 ACK 的資料 -> single cumulative ACK, 根據此特性可以一次 ACK 兩筆資料
- 接收非預期的 segment (序列編號高於預期)，偵測到 gap -> duplicate ACK, 要求從預期的位置重新發送資料
- 接收填補 gap 的 segment -> ACK
- fast retransmit: 一序列連續傳送的資料若中間漏了某項的 ACK，可以在 timeout 前就重新發送(預期已 loss)
- selective ACK: 結合 GBN(只紀錄最小已傳輸序列編號) 與 SR(錯誤發生時可以只重傳gap資料)

### Flow Control
- eliminate the possibility of the sender overflowing the receiver's buffer
- receive window (sender)
- rwnd = RcvBuffer - [LastByteRcvd - LastByteRead]
- LastByteRead: last byte read by application
- LastByteRcvd: last byte receive from net
- RcvBuffer $\geq$ LastByteRcvd - LastByteRead
- rwnd initial is RcvbBuffer
- rwnd $\geq$ LastByteSent - LastByteACKed

### TCP Connection Management
- establish connection: three-way shaking
1. SYN = 1, seq = client_isn (client to server)
2. SYN = 1, seq = server_isn, ack = client_isn + 1 (s to c)
3. SYN = 0, seq = client_isn + 1, ack = server_isn + 1 (c to s)
- close connection:
1. FIN = 1 (c to s)
2. ACK (s to c)
3. FIN = 1 (s to c)
4. ACK (c to s)

Principles of congestion control
---
- scenario 1: two senders, a router with infinite buffer
- $\lambda_{in}$: sending avg rate
- $\lambda_{in}$ 大到一定程度會因為 $\lambda_{out}$ 無法再增加的線路傳輸速率($R/2$)限制導致 buffer 越來越多暫存，delay 也會逐漸趨向無限
- scenario 2: two senders, a router with finite buffer
- $\lambda'_{in}$: 包含原始資料與重傳輸資料的速率，有時稱為 offered load
- 因為原始資料與重傳輸資料都在 router，故 $\lambda_{out}$ 對 $\lambda'_{in}$ 的比值可以逐漸下降（不處理重複資料）
- scenario 3: four senders, routers with finite buffer, multihop paths
- $\lambda_{out}$ 對 $\lambda'_{in}$ 的圖是鐘形曲線
- end-to-end congestion control
- TCP
- network-assisited congestion control
- ATM Available Bite Rate(ABR)

TCP congestion control
---
- congestion window: a constraint on the rate at which a TCP sender can send traffic into the network
- LastByteSent - LastByteACKed $\leq$ min{cwnd, rwnd}
- self-clocking: use ACK to trigger its increase in congestion window size
- TCP congestion-control algorithm (Reno)
- Slow start
- cwnd initialized as 1
- cwnd = cwnd + MSS
- when congestion happend, reset cwnd to 1 and set ssthresh(slow start threshold) = cwnd / 2
- when cwnd = ssthresh, go to Congestion Avoidance
- when 3 duplicate ACKs detect, go to Fast Recovery
- Congestion Avoidance
- increase cwnd more carefully (cwnd = cwnd + MSS*(MSS/cwnd))
- when timeout, go to Slow start
- when 3 duplicate ACKs detect, go to Fast Recovery
- Fast Recovery (recommended, not required)
- cwnd = cwnd + MSS
- when new ACK received, go to Congestion Avoidance
- when timeout, go to Slow start
- TCP Tahoe didn't has it (when duplicate ACK happend also go to Slow start)
- TCP congestion control: Retorspective
- additive-increase, multiplicative-decrease (AIMD)
- TCP Vegas: detect cogestion before loss, lower the rate linerly
- Ubuntu Linux: slow start, congestion avoidance, fast recovery, fast retransmit, SACK (also support Vegas and BIC)
- Macroscopic Description: average throughput of a connection = $\frac{0.75*W}{RTT}$
- W: window size when a loss event occur
- Over High-Bandwidth Path: average throughput of a connection = $\frac{1.22*MSS}{RTT\sqrt L}$
- L: loss rate

### Fairness
- 頻寬理想情況是平均分配
- 在擁塞演算法的動態調整下會逐漸趨於平均
- UDP: 定速傳輸，封包丟失就不管(not being fair for perspective of TCP)
- 也有在開發 UDP Congestion control
- Parallel TCP: 使用越多 parallel 的會分配到更多頻寬資源

### Explicit Congestion Notification (ECN)
- network-assisting congestion control
- 2 bit ECN 在 router 標示擁塞情況，接收端在 ACK 夾帶 ECN Echo (ECE) 回傳

Delay Modeling
---
- Influenced by:
- TCP connection establishment
- data transmission delay
- **slow start**
- Notation
- R: rate of one link between client and server
- S: MSS(bits)
- O: object size(bits)
- no retransmissions: no loss, no corruption
- fixed congestion window, W segments
- WS/R > RTT + S/R (no gap, 兩次傳輸間無間隔)
- delay = 2RTT + O/R
- WS/R < RTT + S/R (gap, 兩次傳輸間有間隔)
- delay = 2RTT + O/R + (K-1)[S/R + RTT - WS/R]
- dynamic window, modeling slow start
- $Latency=2RTT+\frac OR+P[RTT+\frac SR]-(2^P-1)\frac SR$
- P = min{Q, K-1}, the number of times TCP idles at server (due to slow start)
- Q: the number of times the server idles
- K: the number of windows that cover the object
- $K=\lceil log_2(\frac OS+1)\rceil$
- Delay components:
- 2 RTT: connection estab and request
- O/R: transmit object
- HTTP Modeling
- Assume
- 1 base HTML page
- M images
- Non-persistent
- M+1 TCP connections
- Response time = (M+1)O/R + (M+1)2RTT + sum of idle times
- Persistent
- 2 RTT to request and receive base HTML file, 1 RTT to request and receive M images
- Response time = (M+1)O/R + 3RTT + sum of idle times
- Non-persistent with X parallel connections
- Suppose M/X integer
- 1 TCP connection for base file, M/X sets of parallel connections for images
- Response time = (M+1)O/R + (M/X + 1)2RTT + sum of idle times

---
以下還需再補
---

The Network Layer: Data Plane
===

Overview of Network Layer
---
- transport segment from sending to receiving host
- in every host, router
- encapsulates segments into datagrams (on sending side)
- delivers segments to transport layer (on receiving side)
- examines header fields in all IP datagrams passing (on router)
- function
- forwarding: 從 router 的輸入轉到合適的 router 輸出
- routing: 決定從起點到終點的路徑選擇
- Data plane
- local, per-router function
- how datagram arriving on router input is forwarded to output (forwarding function)
- Control plane
- network-wide logic
- how datagram is routed among routers from source to destination
- traditional routing algorithms: in router
- software-defined networking (SDN): in (remote) server

Router
---

The Internet Protocol
---
- IPv4 Datagram Format
- version number: 4bit
- header lenght: 4bit, 一般沒有選項, 就是20bytes
- type of service(TOS): 表示此封包的服務用途
- datagram length: 16bit(因此datagram的理論最大大小是65535bytes, 但一般很少超過1500bytes), header+data的總長度
- identifier(16bit), flags, fragmentation offset(13bit): IP fragmentation(IP分片)使用, 在IPv6刪除
- time-to-live(TTL): 確保datagram不會在網路中迴圈傳輸, 每經過一個router就會減少, 到達0時會被router丟棄
- protocol: 標示使用的應用層協定, 通常是到達目標才有用的區塊
- header checksum: 16bit, 偵測bit error
- source and destination IP addresses: 各32bit, 來源與目標IP位址
- options: 擴充用區塊, 很少使用, 在IPv6刪除
- data(payload): 傳輸的資料
- Addressing
- interface 介面:
- 連接host/router與實體鏈路
- router通常有複數介面
- host通常有1或2個介面
- subnet:
- device interface with same subnet part of IP addresses
- physically reach each other without intervening router
- subnet mask: 由位元數(8bit)決定在一個subnet能放幾個IP
- CIDR(Classless InterDomain Routing):
- 讓subnet長度不必為8的倍數
- how to get IP
- hard-coded
- DHCP(Dynamic Host Configuration Protocol)
- allow host to dynamically obtain its IP address from network server when it joins network
1. DHCP discover: client 廣播詢問是否有 DHCP server
2. DHCP offer: server 回覆 client 可用的位址與持續時間（目標位址標示可用位址）
3. DHCP request: client 確認使用該位址
4. DHCP ACK: server 確認 client 使用該位址
- 可以給的東西
- address of first-hop router for client
- name and IP address of DNS sever
- network mask
- 應用層協定（傳輸層使用UDP，連結層使用802.1 Ethernet）
- IPv6
- 32 bit address
- 40 byte header
- next header
- checksum: removed
- options: Next Header
- ICMPv6
- tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers
- 使用:
- Google: 8%
- NIST: 1/3 of all US government domains

Generalized Forwarding and SDN
---
- flow table of router
- SDN
- openflow
- pattern
- action
- priorty
- counter

The Network Layer: Control Plane
===
- router
- per-router control(traditional)
- 個別的路由演算法在每個路由器中皆有且皆須計算

- BGP (Border Gateway Protocol)
- eBGP: obtain subnet reachability info from neighbor to ASes
- iBGP: propagate reachability info to all AS-internal routers
- Attributs
- AS-PATH: list of ASes been passed
- NEXT-HOP: # of links been traversed
- hot potato routing: choose local gateway w/ least intra-domain cost.

Contributors
===

- [calee](https://calee.tw)
- [Issues](https://github.com/jp05451)
- [alston](https://github.com/Alston-Jan)
- [Eliot](https://github.com/eliot0507)
- [semvlu](https://github.com/semvlu)

:::info
@CA-Lee : 目前 line 631 前都已經整理過了
@alston : 我不想努力了
> 據說更新到 line 739。此外，好像第三章開頭那裡重複了兩次前兩三節的章節標題，剛才寫時沒注意到非標準格式的那段，交給整理的人合併好了。 [name=Silverfish Epic][time=Mon, Nov 22, 2021 9:50 AM]
:::