CSIE - Networking Introduction

CSIE - Networking Introduction

LAVI
  2022-11-06 2022-11-06 Created   2024-09-11 2024-09-11 Updated    

Chapter 1

What’s the Internet

  • hosts = endsystems
  • routers: forward packets
  • I nternet standards
    • RFC: Request For Comments
      • 網際網路標準可以是一個或一組特殊的RFC
    • IETf: Internet Engineering Task Force
      • 由網際網路工程任務組（IETF）創建與發布

What’s a protocol

  • protocol: 定義 format, orders of msgs send and receive in Internet, transmittion of msgs send and 接收的協定
  • control sending, receiving of msgs
    • 定義格式、定義 msgs 傳送與接收方式、定義 msg 傳輸與接收中的行為
    • tcp, ip, http, skype, ethernet

A closer look at network structure

  • network edge: applications and hosts
  • access networks, physical media: wired, wireless communication links
  • network core: 互聯的 routers, network of networks

The network edge

  • end systems (hosts): run application programs, at edge of network
    • web, email
  • client/server model: client host requests/receives service from always-on server
    • web browser/server
    • 一定需要有 client 和 server 兩端，且 client 端只能發出請求，而 server 端只能接收請求
  • peer-peer model: minimal use of 投入的 servers
    • skype, BitTorrent
    • 互相溝通的兩端既是 client 端也是 server 端，兩端皆考發出與接收請求

Access networks and Core networks

  • access network: 一般使用之電腦設備等，與 ISP 連接的 network
  • core network: access network 由非常多 part 組成，每一個 part 都透過 core network 連接(又稱為 backbones)，core network 同時提供 gateway 連接其他 network

Dial-up Modem 撥號連線

A dial-up is a connection that’s established using a modem

  • 通過本地電話網連接
  • 使用公共交換電話網絡(PSTN) 的設施通過撥打傳統電話線路上的電話號碼來建立與Internet 服務提供商(ISP) 的連接
  • home is connected to central office
  • cant’s surf and phone at same time: not “always on”

Digital Subscriber Line (DSL)

  • 通過本地電話網提供數位連接的一種技術
  • 使用者終端裝置是DSL數據機。它轉換二進位資料到數位電脈波，使得訊號在數位音訊流的頻段內傳輸
  • 在交換局端使用數位使用者線接入復用裝置（DSLAM）將DSL電路上的資料匯聚然後轉發到其他的網路。它還能分離出語音部分

Residential access: cable modems

  • 不是用本地電話網提供連接，而是用 TV 網
  • 利用有線電視雙向同軸電纜提供網際網路相關應用服務的技術
  • HFC: hybrid fiber coax
    • asymmetric: up to 30Mbps downstream, 2 Mbps upstream
  • network of cable and fiber 連接 homes to ISP router
    • homes share access to router
    • 不像 DSL 有專用訪問(dedicated access)

Fiber to the Home

optical fiber 光纖

  • optical links from central office to the home
  • two competing optical technologies:
    1. Passive Optical network (PON)
      • PON是一種點對多點的網絡結構，採用無源分光器對光信號進行分離和收集。光纖分路器允許 PON 網絡在單根光纖中為多個用戶提供服務，而無需在集線器和最終用戶之間部署單獨的光纖
    2. Active Optical Network (AON)
      • AON 是一種點對點網絡結構，其中每個用戶都有自己的光纖線路，該線路端接在光集中器上。AON 網絡涵蓋電動交換設備，例如路由器或交換聚合器，以管理信號分配和向特定客戶的方向信號

Ethernet Internet access

Wireless access networks

  • shared wireless access network connects end system to router
  • via base station “access point”
  • wireless LANs
  • wider-area wireless access

Home networks

  • typical home network components
    1. DSL or cable modem
    2. router/firewall/NAT(Network Address Translation，IP 掩蔽)
    3. Ethernet
    4. wireless access point

Physical Media

  • Bit: 傳播 between transmitter pairs
  • physical link: what lies betwwen transmitter & receiver
  • guided media: signals propagate in 堅硬的 media
    • copper, fiber coax
  • unguided media: signals propagate freely
    • radio
  • Twisted Pair (TP): two 絕緣 copper wires
    • 是一種 guided media 的型態

Circuit Switching

  • Circuit Switching vs Packet Switching
  • circuit switching: 會保留通道(像是被提前預約)和資源給發出請求的對象，但該對象即便不立即使用該通道，也不會把該通道優先讓給別人先做，ex 你買斷你家的傳輸線路，就不會讓給別家用
    • 電路交換要求必須首先在通訊雙方之間建立連接通道。在連接建立成功之後，雙方的通訊活動才能開始。通訊雙方需要傳遞的信息都是通過已經建立好的連接來進行傳遞的，而且這個連接也將一直被維持到雙方的通訊結束。在某次通訊活動的整個過程中，這個連接將始終占用著
  • packet switching: 不會保留通道給特定對象，會依照特定優先權讓對象進入
    • 封包在節點間單獨路由，不需要在傳輸前先建立通訊路徑

TDM vs FDM

  • TDM: 會把時間切割成多個 time slot，每次放一個 user 進去，大家輪流占用時間做，類似 OS 的 RR 排班法
    • TDM是將一個connection的duration切成frame，每個frame中在切出time slot，User開始傳遞資訊時便會被塞到time slot，也就是在一個固定的時間內切割頻寬，同時允許多個使用者傳遞資料，time slot越多，相對地速率也會趨緩
  • FDM: 大家一起占用時間同時做
    • FDM則是依頻率來切割link區段，而使用者同時在同一個切割區域裡面做傳輸，不同於TDM是一個一個將使用者塞到slot裡面去做動作，FDM是一起將user丟到一個pool的感覺

ISP

Internet Service Provide 網際網路連線服務公司

  • 譬如L 電信業者
    • responsibility: 確保網路通訊的穩定、連接眾一般使用使用之電腦，構成 access network，且 ISP 與 ISP 之間形成 core network 彼此連接
  • Tier1 ISP、Tier2 ISP、Tier3 ISP、local ISP
  • 一個封包的傳輸可能經過非常多 networks

How do loss and delay occur

  • delay:
    1. packet being transmitted
    2. packets queueing
  • loss
    1. arriving packets dropped(loss) if no free buffers

Four sources of packet delay

  1. nodal processing: check bit error、determine output link
    • 檢查 bit error 和決定將該封包導向何處的 link 設定所需要的時間
  2. queueing: time waiting at output link for transmission、depends on 壅塞程度 of router
    • 在 queue 裡等待花費的時間，一個特定封包的排隊時延將取決於先期到達的、正在排隊等待向鏈路傳輸的封包的數量
  3. Transmission delay: 從 queue 離開，到傳送上網路所花費的時間，= 傳送封包大小/link通道的頻寬
  4. Propagation delay: Router A -> Router B 線路傳輸時間，= physical link 長度/傳輸速度

Packet loss

  1. queue 的 capacity 有限
  2. packet arriving 到了已經滿的 queue 會 loss
  3. 網路硬體設備壞掉
  4. wireless 傳輸本身即會造成 packet loss
  • lost 的 packet 可能會被原先的 source end system 重新傳送

Throughput

吞吐量

  • throughput: 可傳送的數據容量，rate of bits transferred between sender/receiver，又可以區分為瞬間重送量和平均傳送量

Internet protocol stack: 5 層 Layer

Internet protocol stack
Application 應用層 supporting network applicatinos: FTP、SMTP、HTTP
Transport 傳輸層 process-process data transfer: TCP、UDP
Network 網路層 routing of datagrams from source to destination: IP，routing protocols
Link 連接層 data transfer between neighboring network elements
Physical 實體層 bits “on the wire”
ISO model
Application 應用層
Presentation 展示層
Session 會議層
Transport 傳輸層
Network 網路層
Link 連接層
Physical 實體層
  • ISO model 與 Internet protocol stack 差在 Internet protocol stack 把會議層和展示層合併在應用層裡
  1. 第一層︰實體層（Physical Layer）
    • 實體層是OSI模型的最底層，它用來定義網路裝置之間的位元資料傳輸，也就是在電線或其他物理線材上，傳遞0與1電子訊號
  2. 第二層︰資料連結層（Data Link Layer）
    • 資料連結層介於實體層與網路層之間，主要是在網路之間建立邏輯連結，並且在傳輸過程中處理流量控制及錯誤偵測，讓資料傳送與接收更穩定
  3. 第三層︰網路層（Network Layer）
    • 網路層定義網路路由及定址功能，讓資料能夠在網路間傳遞。這一層中最主要的通訊協定是網際網路協定（Internet Protocol，IP），資料在傳輸時，該協定將IP位址加入傳輸資料內，並把資料組成封包（Packet），在網路上傳輸時，封包裡面的IP位址會告訴網路設備這筆資料的來源及目的地
  4. 第四層︰傳輸層（Transport Layer）
    • 傳輸層主要負責電腦整體的資料傳輸及控制，TCP 是我們常接觸具有傳輸層功能的協定，它在傳輸資料內加入驗證碼，當對方收到後，就會依這個驗證碼，回傳對應的確認訊息（ACK），若對方未及時傳回確認訊息，資料就會重新傳遞一次，以確保資料傳輸的完整性
  5. 第五層︰會議層（Session Layer）
    • 這個層級負責建立網路連線，等到資料傳輸結束時，再將連線中斷，運作過程有點像召集多人開會（建立連線），然後彼此之間意見交換（資料傳輸），完成後，宣布散會（中斷連線）
  6. 第六層︰展示層（Presentation Layer）
    • 應用層收到的資料後，透過展示層可轉換表達方式，例如將ASCII編碼轉成應用層可以使用的資料
  7. 第七層︰應用層（Application Layer）
    • 應用層主要功能是處理應用程式，進而提供使用者網路應用服務，例如 TCP、HTTP

Encapsulation 封裝

  • 封裝是各種網路協定的基本實作方法
Frame Header Datagram Header Segment Header Message
Application — — — V
Transport — — V V
Network — V V V
Link V V V V

Chapter 2

Client-server architecture

  • server: always-on host, permanent IP address, server farms for scaling
  • clients: communicate with server, may be 間歇性的 connected, dynamic IP address, do not communicate directly with each other

Processes communicating

  • Process: program running within a host
  • within same host, two processes communicate using **inter-process communication **
  • processes in different hosts communicate by exchanging messages
  • Client process: process that initiates communication
  • Server process: process that waits to be contacted

Socket

  • process sends/receives messages to/from its socket
  • socket 就像門一樣，send process 推 msgs 出門
  • 以API的形式提供出來使用，提供process跟process之間通訊
    1. choice of transport protocol
    2. ability to fix a few parameters 有修復參數的能力

process identifier

  • to receive messages, process must have identifier
  • identifier includes both IP address and port numbers associated with process on host
  • Example port numbers:
    • HTTP server: 80
    • Mail server: 25

What transport service does an app need

  • data loss: 有些 app 可以容忍 data loss, 有些要求一定要 100% transfer data
  • throughput: 有些 app 為了效率要求吞吐量要是最小，有些你給他什麼他就用什麼
  • timing: 有些 app 要求 delay 越低越好
  • security: 加密、數據完整性… 等等

TCP vs UDP

  • TCP:
    1. connection-oriented: 在 client 和 server process 之間 require 時 setup
    2. reliable transport: 會確認是否對方有接收到資訊，才會繼續傳輸，如果缺失了會再傳一次
    3. flow control: 會控制傳輸量，以免 overwhelm
    4. congestion control: 在壅塞時會控制發送方的傳輸數量
    5. does not provide: timing, minimum throughput guarantees, security
  • UDP:
    • 並不會運用確認機制來保證資料是否正確的被接收、不需要重傳遺失的資料、資料的接收可不必按順序進行、也不提供回傳機制來控制資料流的速度
  • 速度
    • UDP 比 TCP 快，因為它可以做的事情更少。TCP 不僅要建立連接，還要處理錯誤控制並保證文件按順序到達。
  • 流量和擁塞控制
    • TCP 的流量和擁塞控制機制可確保發送方不會因過快傳輸過多數據而壓倒接收方。UDP 不提供流量和擁塞控制
  • 面向連接和無連接
    • UDP 是無連接協議，而 TCP 是面向連接的協議。在 TCP 中，發送方和接收方在發送數據之前建立連接。對於 UDP，它不需要顯式連接來發送數據。
  • TCP 傳輸順序:
    1. TCP 為每個封包分配一個唯一的識別碼和一個序號，這些號碼能讓接收端識別封包的完整性，以及封包的順序。
    2. 當接收端收到封包後，如果順序正確，會向發送端傳送一個確認信號（Acknowledgement），以此確認接收端已經收到封包。
    3. 發送端傳送另一個封包。
    4. 如果封包遺失或發送順序錯誤，接收端會保持沈默，不發送確認信號。這表示發送端需要重新傳送封包

HTTP

  • HTTP: hypertext transfer protocol
  • client/server model:
    • client: browser require/receive display Web objects
    • server: Web server sends objects in response to requests
  • Uses TCP:
    1. client 初始化 TCP connection (creates socket) to server, port 80
    2. server 接收 TCP connection from client
    3. HTTP messages 在 browser (HTTP client) 和 Web server (HTTP server) 之間交換
    4. TCP connection closed
  • HTTP is “stateless”
    • server 不會紀錄上一個 client 的 requests

Nonpersistent vs Persistent HTTP

  • RTT: Round Trip Time，一個東西來回的時間
    • response time = 2RTT + transmit time
  • Nonpersistent HTTP: 一個 TCP 連線傳一個東西
    • 每一次傳輸都要 2RTT
  • Persistent HTTP: 一個 TCP 連線傳多個東西
    • server 在第一個 TCP 傳輸結束後並沒有關閉 TCP 連線，於是下一個要傳輸的 object 就可以利用此 open connection 傳輸
    • 後面的 object 都只要 1RTT 就可以傳輸

HTTP request message

  • HTTP request message:

  • method: http1.1
    1. head：和get一樣，只是head只會取的HTTP header的資料。
    2. get：取得我們想要的資料。
    3. post：新增一項資料。（如果存在會新增一個新的）
    4. put：新增一項資料，如果存在就覆蓋過去。（還是只有一筆資料）。
    5. patch：附加新的資料在已經存在的資料後面。（資料必須已經存在，patch會擴充這項資料）
    6. delete：刪除資料
  • HTTP response message:
  • HTTP response status codes:
    • 200 OK
    • 301 Moved Permanently: 被請求的資源已永久移動到新位置
    • 400 Bad Request: 客戶端錯誤，request 不被 server 理解
    • 403 Forbidden: 伺服器已經理解請求，但是拒絕執行它
    • 404 Not Found
    • 505 HTTP Version Not Supported: 伺服器不支援，或者拒絕支援在請求中使用的HTTP版本

Cookies

  • cookies 應用:
    1. 驗證身分
    2. 購物車
    3. user session state

Web caches (proxy server)

  • 目的: 在不涉及源服務器的情況下滿足客戶端請求
  • cache 同時是 client and server
  • Why Web caching?
    1. 減少 client request 的 response time
    2. 減少機構的 access link 壅塞可能性

FTP

  • FTP: file transfer protocol
  • transfer file to/from remote host
  • client/server model:
    • client: 發起 transfer 的一方
    • server: remote host
  • ftp: RFC 959
  • ftp server: port 21

FTP data connections

  • 傳輸:
    1. FTP client 連接 FTP server at port 21 利用 TCP
    2. client 認證控制連接
    3. client 透過指令瀏覽遠端資料
    4. 當 server receive file transfer command，server 開啟第二次 TCP 連接 client
    5. 在傳輸完一個資料後，server 關閉連接
    6. server 開啟另一個 TCP 連接傳輸另一個資料
    7. control connection: “out of band”(即便關機狀態，也可以維護與管理)
    8. FTP server 會維持 “state”: current directory, earlier authentication

SMTP

  • three major components:
    1. user agents
    2. mail servers
    3. simple mail transfer protocol: SMTP
  • SMTP
    • 僅負責發信
    • client: sending mail server
    • server: receiving mail server
  • POP、IMAP、HTTP
    • 收信
  • uses TCP、 port 25、direct transfer: sending server to receiving server
  • three 階段 of transfer
    1. handshaking (greeting): 在資料通信中，在進行資訊交換之前，需要對操作模式的狀態互相達成協定
    2. 傳送 messages
    3. 關閉
  • command/response interaction
    • commands: ASCII text
    • response: status code and phrase

SMTP transfer

  • 傳輸:
    1. A 使用 user agent 寫信和指定寄出對象(對方的郵件信箱)
    2. A 的 user agent sends msgs 到他的 mail server，此時 msgs 在 queue 裡等候
    3. SMTP client 開啟 TCP 連接至 B 的 mail server
    4. SMTP client sendss A 的 msgs 透過 TCP 連線
    5. B 的 mail server 收到 msgs，並將其放在 B 的信箱
    6. B 打開他的 user agent 去閱讀 msgs

HTTP vs SMTP

  • HTTP: 每個 object 都封裝在他的 response msg
  • SMTP: multiple objects 發送給多個對象

POP3 & IMAP

  • POP3: Post Office Protocol 3
    • authorization phase
    • transaction phase
    • Bob cannot re-read e-mail if he changes client
    • POP3 is stateless across sessions
  • IMAP: Internet Mail Access Protocol
    • Keep all messages in one place: the server
    • Allows user to organize messages in folders
    • IMAP keeps user state across sessions

DNS

  • Domain Name System
  • service: hostname to IP address translation
  • 如何查詢:
    1. client 查詢 root server 以查詢 DNS server
    2. client 查詢 DNS server 已獲得 amazon.com DNS server
    3. client 查詢 amazon.com DNS server 已獲得 IP address 來獲得 www.amazon.com
  • 如何運作:
    • iterated query:
    • recursive query:
  • Top-level domain (TLD) servers: responsible for com, org, net, edu, etc, and all top-level country domains uk, fr, ca, jp
  • Authoritative DNS servers: organization’s DNS servers, providing authoritative hostname to IP mappings for organization’s servers
  • Local Name Server: when host makes DNS query, query is sent to its local DNS server

Pure P2P architecture

  • no always-on server
  • peer are 間歇性的 connected and change IP address
  • 有著高擴展性，但難以維護

Hybrid of client-server and P2P

  • Skype:
    1. voice-over-IP P2P application
    2. centralized server: finding address of remote party
    3. client-client connection: direct
  • Instant messaging:
    1. chatting between two users is P2P
    2. centralized service: client presence detection/location
    3. 使用者註冊 IP address with central server when it comes online
    4. 使用者 central server to find IP addresses of 其他聊天對象

File distribution time:

  • server-client
    • server sequentially sends N copies: NF/us time
    • client i takes F/di time to download
    • Time to distribute F to N clients using client/server approach
      • = dcs = max { NF/us, F/min(di) }
      • us: server upload bandwidth
      • di: peer i download bandwidth
  • P2P
    • server must send one copy: F/us time
    • client i takes F/di time to download
    • NF bits must be downloaded (aggregate)
    • fastest possible upload rate: us + ui
      • dP2P = max { F/us, F/min(di) , NF/(us + ui) }
      • us: server upload bandwidth
      • di: peer i download bandwidth
      • ui: peer i upload bandwidth

  • P2P 長時間會比 CS 好，短時間看不出來

File distribution: BitTorrent

筆記

分配器或文件的持有者將文件發送給其中一名用户，再由這名用户轉發給其它用户，用户之間相互轉發自己所擁有的文件部分，直到每個用户的下載都全部完成。
這種方法可以使下載服務器同時處理多個大體積文件的下載請求，而無須佔用大量帶寬

使用者越多，下載同一檔案的人越多，下載該檔案的速度越快。
且下載後，繼續維持上傳的狀態，就可以「分享」

  • P2P file distribution
    • tracker: 追蹤 peer 在 torrent 理的參與度
    • torrent: 一群 peer 交換一堆 file
  • 概念:
    • 剛加入的 peer 沒有任何 chunks，但會持續累積
    • tracker 獲得註冊的 peers 後，會將他們與鄰居彼此連接
    • 當 downloading，peer 上傳 chunks 到其他 peers
    • peers 來來去去
    • 一個 peer 有整份 file，他有可能自私的帶走，或無私地留下 file
  • Pulling Chunks
    • at any given time, different peers have different subsets of file chunks
    • periodically, a peer (Alice) asks each neighbor for list of chunks that they have.
    • Alice sends requests for her missing chunks
      • rarest first
  • Sending Chunks: tit-for-tat
    1. Alice sends chunks to four neighbors currently sending her chunks at the highest rate
      • re-evaluate top 4 every 10 secs
    2. every 30 secs: randomly select another peer, starts sending chunks
    3. newly chosen peer may join top 4
    • “optimistically unchoke
      1. Alice “optimistically unchokes” Bob
      2. Alice becomes one of Bob’s top-four providers; Bob reciprocates
      3. Bob becomes one of Alice’s top-four providers

Chapter 3

Multiplexing/demultiplexing

  • 多工/分工

    Multiplexing/demultiplexing

    一個 process 可以有多個 socket，每個socket 有一個獨立的 id
    網絡上的數據通過這些 socket 發送給 process，process 也可以將數據通過 socket 發送到網絡
    也就是說，傳輸層並不是將數據傳輸給一個 process，而是給一個 socket

    每個傳輸層的數據包包頭都包含接收 socket 信息，可以將數據引導到對應 socket
    將數據從傳輸層數據包分發到不同 socket 的過程稱爲 demultiplexing
    而從不同 socket 蒐集數據並創建數據包然後發送給網絡層的過程稱爲 multiplexing

  • host uses IP addresses & port numbers to direct segment to appropriate socket

datagram vs packet

  • datagram（數據報） – 在網絡層中的傳輸單元（例如IP）
    • 一個datagram可能被壓縮成一個或幾個packets，在數據鏈路層中傳輸。
  • packet（數據包） – 封裝的基本單元，它穿越網絡層和數據鏈路層的分解面
    • 通常一個packet映射成一個frame，但也有例外：即當數據鏈路層執行拆分或將幾個packet合成一個frame的時候

TCP vs UDP

  • TCP 與 UDP
    1. TCP 為每個封包分配一個唯一的識別碼和一個序號，這些號碼能讓接收端識別封包的完整性，以及封包的順序
    2. 當接收端收到封包後，如果順序正確，會向發送端傳送一個確認信號（Acknowledgement），以此確認接收端已經收到封包。
    3. 發送端傳送另一個封包
    4. 如果封包遺失或發送順序錯誤，接收端會保持沈默，不發送確認信號。這表示發送端需要重新傳送封包

checksum

  • TCP checksum
  • 檢驗和 (Checksum)，提供 傳送方 與 接收方 一種計算方式，用來檢查 區段 (segment) 是否受損
  • 發送方:
    • 欲發送 TCP 區段前，利用此計算方式 算出 Checksum 值，並置於 Checksum 欄位。
  • 接收方:
    • 將收到的區段，透過相同的計算方式算出 Checksum 值
    • 並與收到 TCP 區段的 Checksum 欄位值做比較，若兩者不相等，目的端會丟棄此區段，並視同區段遺失
  • Example: add two 16-bit integers

Reliable data transfer

  • rdt ithome(上)
  • rdt ithome(下)
  • rdt1.0
    • 最理想的假設(也最不切實際)，rdt1.0假設下面的傳輸非常可靠，不會出錯或是資料遺失的發生。
    • 如圖，虛線箭頭指的是初始狀態，sender等上面的資料傳上來，傳完訊息下去就回原狀態；receiver等待下方訊息到來，收完訊息之後往上傳完就回原狀態
  • rdt2.0
    • 該假設中有考慮到flip bits的出現，我們用checksum來偵錯
    • 問題是我們如果找到錯要怎麼處理?這時我們有了回饋機制，正確無誤時receiver傳”ACK”(acknowledgement)；錯誤時傳”NAKs”(也稱”NACKs”)，一旦接收NACKs，sender就重傳該錯誤封包
    • 但rdt2.0只有考慮到sender可能出錯，但是沒有考慮receiver出錯
  • rdt2.1
    • 它是怎麼解決2.0的回饋時出現錯誤呢?
    • ACK或NACK 出錯時，只要sender看不懂，sender就會重傳該封包，如果是NACK發生錯誤還好，但如果是ACK發生錯誤，receiver不就重複收到兩個一樣的封包嗎?事實上在rdt2.1有料到這件事情，因此sender會在封包上添加序號。如此receiver就會丟掉重複的封包
  • rdt2.2
    • 在rdt2.2，在回饋機制上我們把NACK省略掉，只留ACK
  • rdt3.0
    • rdt3.0 開始考慮到packet loss的情形，它怎麼解決呢?
    • 採用”倒數計時”的方式，sender每送一個封包就會設定一個timer，如果超過時間還沒收到receiver的回饋，sender就會重傳該封包
    • 如果receiver有回饋，但可能因為網路太慢使得ACK遲到sender會如何?sender還是重傳啊!於是receiver就會收到重複的封包，不過沒關係，有sequence number就可以辨認哪個是重複的封包
    • 下圖分別為正常情況與sender packet loss
    • RTT: Round Trip Time

Go-Back-N

  • GBN SR TCP 比較
  • GBN
    • GBN 接收端無需暫存任何順序不正確的封包，因為 GBN 傳送端會重送所有未經確認的封包，GBN 的單一封包錯誤，將導致需重送大量無需重送的封包
    • 使用一個 Timer 綁定最早送出且未經確認的封包(Base)；當 Timeout 時，若還未收到最早送出封包所回傳的確認，則重送所有未經確認的封包
      • 收到順序不正確的 ACK：不做任何事情
      • 收到順序正確的 ACK：
        • 將 base 設定為 ACK 的序號+1
        • 若還有可用封包可傳送的請況下，則重新啟動Timer傳送新的封包
    • 收到正確順序的封包事件：回傳該封包序號的 ACK 給傳送端
    • 收到錯誤順序的封包事件：回傳最後一次收到正確序號的 ACK 給傳送端

Selective Repeat

  • SR
    • SR 傳送端只重送接收端未正確收到的封包，可能是遺失或毀損
    • SR 會將脫序的封包暫存
      • 逾時事件: 每個封包都綁有 timer，當各個封包的 ACK 逾時未收到，則重送該封包
      • 收到 ACK：
        • 標記對應序號的封包為已確認。
        • 若收到的 ACK 序號是 Base，則將 Base 移動到下個最小未經確認的封包上。
        • 若窗格移動到了尚未傳送的封包上，則同時送出這些未被送出的可用封包。

TCP (Transmission Control Protocol)

  • TCP
    • TCP 傳送端只需要維護「最小已送出未經確認的封包之序號」及「下一個要傳送的封包之序號」
    • TCP 最多只重送一筆區段
    • TCP 之 ACK 與 GBN、SR 兩者的 ACK 不同，TCP 傳送端所發出的 ACK，表示期待下一次要收到的封包之序號， 而 GBN、SR 的 ACK 用來告知已經收到的封包之序號。
    • TCP 同 SR 會將脫序的封包暫存
    • TCP傳送端重點
      • 逾時事件：重送封包。
      • 收到重複三次 ACK(Duplicated Ack)：重送封包，又稱快速重送
        • 因為接收端總是收到非預期的封包，而連續回傳希望收到的封包之序號，此時傳送端就會立刻重送接收端所預期的封包，這將會在 timeout 前就送出
    • TCP 接收端重點
      • 預期封包抵達事件：回傳下一次期望收到的封包序號 ACK
      • 非預期封包抵達事件：暫存封包，送出期望收到的封包之序號 ACK

Compare GBN SR TCP

  • 比較 GBN、SR、TCP 的範例
    • 假設 timeout 時間內足夠傳送5筆區段，包含回應的 ACK 被傳送端收到。 傳送端傳送給接收端的 5 個區段，當中有 2 個區段遺失，且最後接收端會收到所有的區段， 在上面兩個前提下，下列為 GBN、SR、TCP 三者傳送端、接收端的比較：
    • GBN
      • 傳送端：共送出9個區段(1、2、3、4、5)和補送的(2、3、4、5)
      • 接收端：回應8個ACK(1、1、1、1、2、3、4、5)
    • SR
      • 傳送端：共送出6個區段(1、2、3、4、5)和補送的(2)
      • 接收端：共回應5個ACK(1、3、4、5、2)
    • TCP
      • 傳送端：共送出6個區段(1、2、3、4、5)和快速重送的(2)
      • 接收端：共回應5個ACK(2、2、2、2、6)

TCP Flow Control

  • TCP Flow Control
  • 目的是用來平衡傳送端與接收端之間的流量，避免傳送端送出的流量大於接收端可處理的流量；透過兩端設置 Buffers 來處理

TCP Congestion Control

TCP 三次握手

Chapter 4

Virtual Circuit

  • virtual circuit network 虛擬電路
    1. 提供 network-layer connection 服務，必須預訂 connection 指定路徑，例如特定 buffer、CPU、bandwidth
    2. 第一個發送的封包在路徑上保留資源，在連接時間內後續封包將遵循與發送封包相同的數路徑
    3. 需要 global header，只有第一個封包需要 golbal header，後續皆不需要
    4. 按順序接收封包
    5. 可確保所有封包成功到達接收端
    6. 不會因資源不可用丟棄任何封包
    7. 由 ATM 網路使用

Datagram networks

  • datagram network 資料封包網路
    1. 提供 network-layer connection less 服務，不須預定 connection 的指定路徑
    2. 所有封包可以自由使用任何路徑
    3. 每個封包有各自標頭
    4. 亂序接收封包
    5. 不如 virtual circuit network 可靠
    6. 只有在 buffer、CPU 資源可用時才能轉發封包，否則會被丟棄
    7. 由 IP 網路使用

Longest prefix matching

  • ex:
    • DA: 11001000 00010111 00010110 10100001
      • Which interface?
      • 0
    • DA: 11001000 00010111 00011000 10101010
      • Which interface?
      • 1

Subnet

  • 具有相同子網部分IP地址的設備接口
  • 可以在沒有路由器介入的情況下，相互之間進行物理連接

NAT Network Address Translation

  • NAT 網路位址轉譯、IP 掩蔽: 透過 router 重寫來源 IP 位址的技術
    • 詳細步驟
    1. 從 host 10.0.0.1 send 數據包到指定 128.119.40.186， 80 (指定 IP、Port)
    2. NAT router 改變數據包來源位址從 10.0.0.1， 3345 變成 138.76.29.7， 5001 (router 的 IP)，並更新 NAT translation table
    3. 從剛才傳送的 128.119.40.186， 80 位址收到回應，目的地為 138.76.29.7， 5001
    4. NAT router 改變數據包回應位址從 138.76.29.7， 5001 成 10.0.0.1， 3345

ICMP

  • ICMP 網際網路控制訊息協定，可用於 IP 中傳送控制訊息，主要目的為提供可能發生在通訊環境中的各種問題回饋，通過這些訊息使管理者可以對所發生的問題做出診斷並採取適當的措施解決

IPv4 vs IPv6

  • 參考資料
    Private Address Public Address
    local global
    在 network 內部通信 在 network 外部通信
    Private IP 統一不同 Public IP 可能以統一或非統一的方式有所不同
    僅用於 LAN (局域網) 用於獲取 Internet service
    用於 load network operating system 被 ISP controlled
    免費提供 不是免費提供
    可以利用 cmd 的 ipconfig 指令得知 需使用 what is my ip 搜尋
    有固定範圍 不是 private IP address 的皆是 Public IP
    Private IP 不是唯一，可能重複 Public IP 唯一，不會重複
    有安全性保證 沒有安全性
    需要求 NAT 才能在設備間通信 不需要要求 network translation
  • Link-State Routing
  • 動態演算法。路由器必須隨時依照最新消息計算出路由路徑，也隨時更新路由表
  • 每一個路由器必須定期測量它和鄰近路由器之間的費用，這費用可能和佇列延遲、頻寬等因素有關，不同通訊協定都有各自的定義。這費用又稱為『鏈路費用』（Link Cost）
  • 當每一路由器測出相鄰之間的費用後，定期廣播給其他『所有』路由器，該廣播的訊息又稱為『鏈路狀態』（Link State）訊息
  • 任何一部路由器也會接收到其他路由器廣播的鏈路狀態，再依照這些訊息計算出到達其他路由器的最短路徑，並建構路由表
  • 當每一路由器收到其他所有路由器的鏈路狀態封包，必須計算出它到達任何一部路由器的最佳路徑
  • 較被常用的是Dijkstra

Dijkstra’s algorithm

Distance Vector Algorithm

  • Distance Vector Algorithm
  • 一種動態的分散式路徑選擇演算法
  • 每一個路由器都必須維護一個二維的『向量表』（Vector Table），向量表格內紀錄本身路由器到每一個路由器的已知的最佳距離
  • 路由器定期和鄰近路由器交換向量表（並不廣播給所有路由器）來建立路由表。當路由器接收到鄰近傳來的向量表時再修正本身的向量表，向量表的內容就一直修正再傳送，整個網路狀況也就能漸漸地傳遞到每一個路由器上
  • 向量表中各個欄位，如果使用路由器之間距離的數值，稱之為『距離向量』（Distance Vector）。表示兩個路由器之間相距幾個路由器，向量表又稱為『距離表』（Distance Table）
    1. 每各路由器都須維護一只『距離向量表』，並依此表建立『路由表』。
    2. 將『路由表』傳遞給相鄰路由器。
    3. 路由器收到『路由表』後，結合原有『距離向量表』成為新的『距離向量表』，再建立新的『路由表』，並傳遞給下一個路由器。
    4. 依此類推，路由器定期將路由表傳遞給相鄰路由表
  • 較常使用 Bellman-Ford Equation (dynamic programming)

Hierarchical routing

  • 我們知道，在LS和DV算法中，每個路由器都需要保存其他路由器的一些信息。當網絡規模不斷擴大時，網絡中的路由器數量也會增加。因此，路由表的大小會增加，那麽路由器就不能有效地處理網絡流量。為了克服這個問題，我們使用了 Hierarchical routing
  • 在 Hierarchical routing 中，路由器被劃分為多個區域。每個路由器都有關於如何將數據包路由到自己區域內的目的地的完整細節。但它對其他區域的內部結構沒有任何了解

RIP ( Routing Information Protocol)

  • RIP Greeks
  • RIP 解析
  • RIP路由協定是採用距離向量（Distance Vector）路由演算法之一
  • Routing Information Protocol (RIP) is a dynamic routing protocol that uses hop count as a routing metric to find the best path between the source and the destination network
  • 路由器每隔30秒向與它相連的網路廣播自己的路由表，接到廣播的路由器將收到的資訊添加至自身的路由表中。每個路由器都如此廣播，最終網路上所有的路由器都會得知全部的路由資訊。正常情況下，每30秒路由器就可以收到一次路由資訊確認，如果經過180秒，即6個更新週期，一個路由項都沒有得到確認，路由器就認為它已失效了。如果經過240秒，即8個更新週期，路由項仍沒有得到確認，它就被從路由表中刪除
  • 每經過一台路由器，路徑的跳數加一。如此一來，跳數越多，路徑就越長，RIP演算法會優先選擇跳數少的路徑。RIP支持的最大跳數是15，跳數為16的網路被認為不可達

OSPF (Open Shortest Path First)

  • OSPF Greeks
  • Open Shortest Path First (OSPF) is a link-state routing protocol that is used to find the best path between the source and the destination router using its own Shortest Path First
  • hierarchical OSPF in large domains
  • OSPF is hierarchical routing protocol，using area 0 (Autonomous System) at the top of the hierarchy.
  • 當router啟動後，它就初始化路由協議數據結構，然後等待下層協議關於接口已可用的通知信息.當router確認接口已準備好，就用OSPF Hello信息來獲取鄰居信息，即具有在共同的網絡上接口的router
  • router向鄰居發送Hello包並接收它們的Hello包，除了學習鄰居

BGP (Border Gateway Protocol)

  • BGP 是什麼

    當有人把一封信投進郵筒時，郵政服務就會處理這封郵件，並選擇一條快速、高效的路線將這封信投遞給收件人。同樣地，當有人通過網際網路提交資料時，BGP 負責尋找資料能傳播的所有可用路徑，並選擇最佳的路由，這通常意味著在自治系統之間跳躍

  • 如果 AS1 需要向 AS3 路由一個資料包，它有兩種不同的選擇：
    • 跳躍到 AS2，然後到 AS3： AS2 → AS3
    • 或跳躍到 AS6，然後到 AS5、AS4，最後到 AS3： AS6 → AS5 → AS4 → AS3
  • 在這個簡化的模型中，決策似乎很簡單直接。AS2 路由所需的躍點比 AS6 路由要少，因此它是最快、最高效的路由。現在假設有成百上千個 AS，而且躍點數只是一種複雜的路線選擇演算法中的一部分。這就是網際網路上 BGP 路由的實際情況
  • BGP Greeks
  • Border Gateway Protocol (BGP) is used to Exchange routing information for the internet and is the protocol used between ISP which are different ASes(Autonomous System)
  • BGP provides each AS a means to:
    1. 獲得 subnet 可被到達的訊息 from neighboring ASs.
    2. 將可被到達的訊息傳給所有 AS 內部的 routers.
    3. 決定”好的” routes 到 subnets 根據可被到達的訊息和規範

Broadcast Routing

  • 網路上封包傳遞三大模式-Unicast、Broadcast、Multicast
  • 一對多的傳遞模式，就像在社區內用廣播器廣播，封包在區域網路內所有的人都會收到，但是在主機收到封包後會確認這個封包是不是他的，如果不是他的就不理他，如果是他的才會收下。此種模式封包的傳遞會在Router擋下，而不會傳到別的區域網路，被稱之為One-to-One的通訊方式

Multicast Routing

  • 網路上封包傳遞三大模式-Unicast、Broadcast、Multicast
  • 一對多的傳遞模式，但是和Broadcast不同的是封包只會傳給指定的人，而不是所有的人皆傳送封包，網路視訊的最佳解決方案，來源端只會發送一份資料，頻寬並不會因為接收的人增加而增加，此種模式封包會傳給特定的多個人，封包是可以過路由器傳到外面的，而不像Broadcast只會在區域網路內傳播

Reference

振緯老師的網路概論課程簡報
Circuit Switching vs Packet Switching
TCP 與 UDP
TCP checksum
rdt ithome(上)
rdt ithome(下)
GBN SR TCP 比較
TCP Flow Control
TCP Congestion Control
Congestion Control 宅學習
TCP 三次握手
Link-State Routing
Distance Vector Algorithm
RIP Greeks
RIP 解析
OSPF Greeks
BGP 是什麼
BGP Greeks
網路 7 層架構
多工/分工
網路上封包傳遞三大模式-Unicast、Broadcast、Multicast

On this page
CSIE - Networking Introduction
  1. Chapter 1
    1. What’s a protocol
    2. Access networks and Core networks
    3. Dial-up Modem 撥號連線
    4. Digital Subscriber Line (DSL)
    5. Residential access: cable modems
    6. Circuit Switching
    7. How do loss and delay occur
    8. Four sources of packet delay
    9. Packet loss
    10. Throughput
    11. Internet protocol stack: 5 層 Layer
    12. Encapsulation 封裝
  2. Chapter 2
    1. Socket
    2. process identifier
    3. TCP vs UDP
    4. HTTP
    5. Cookies
    6. Web caches (proxy server)
    7. FTP
    8. SMTP
    9. DNS
  3. Chapter 3
    1. Multiplexing/demultiplexing
    2. TCP vs UDP
    3. checksum
    4. Reliable data transfer
    5. Go-Back-N
    6. Selective Repeat
    7. TCP (Transmission Control Protocol)
    8. TCP Flow Control
    9. TCP Congestion Control
    10. TCP 三次握手
  4. Chapter 4
    1. Virtual Circuit
    2. Datagram networks
    3. Longest prefix matching
    4. Subnet
    5. NAT Network Address Translation
    6. ICMP
    7. IPv4 vs IPv6
    8. Link-State Routing Algorithm
    9. Distance Vector Algorithm
    10. Hierarchical routing
    11. RIP ( Routing Information Protocol)
    12. OSPF (Open Shortest Path First)
    13. BGP (Border Gateway Protocol)
    14. Broadcast Routing
    15. Multicast Routing
  5. Reference