---
# System prepended metadata

title: Introduction to Computer Networks
tags: [MyNTUST]

---

# Introduction to Computer Networks

###### tags: `MyNTUST`

{%hackmd @CA-Lee/MyNTUST_banner %}

[TOC]

Introduction
===

What is the Internet?
---

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

```mermaid
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
    ```mermaid
    sequenceDiagram
    Alice ->> Bob: Hi
    Bob ->> Alice: Hi
    Alice ->> Bob: Got the time?
    Bob ->> Alice: 2:00
    ```
- Machine protocol
    ```mermaid
    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
    ```mermaid
    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
        - ![](https://i.imgur.com/NWxfEq0.png =300x)
    - Fiber
        - 傳輸媒介是玻璃
        - 10 Gbps ~ 100 Gbps
        - 低出錯率
            - 不怕電磁干擾
    - Coax (同軸電纜)
        - ![](https://i.imgur.com/KEJi9fW.png)
- 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
    ![](https://i.imgur.com/foKGPAz.png)
    - 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
    ![](https://i.imgur.com/AvLNmgm.png)
    - 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

![](https://i.imgur.com/JCZrBch.png)

- 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（封裝）
    ```mermaid
    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))
> ![](https://i.imgur.com/2w4Aycj.png)

### 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
    ![](https://i.imgur.com/Dx3cu2W.png)
    > 右下區多空了一行

### 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
    ![](https://i.imgur.com/5NmKz9B.png)

![](https://i.imgur.com/tNTdMGj.png =300x)

### 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
    - ![](https://i.imgur.com/vA2WIbf.png)
- 使用領域
    - 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]
::: 
