Contents:
+ Key Network-Layer Functions
+ Network layer service models
+ Virtual circuits and Datagram networks
+ Router and Router Algorithms
+ Internet protocol (IP)
Key Network-Layer Functions
Forwarding vs. Routing
- Forwarding: move packets from router’s input to appropriate router output (走一步)
- Routing: determine route taken by packets from source to destination (走全部)
Network layer service models:
- Internet 只是 Network layer 的其中一種 architecture
- Internet attributes: 不建連線 (建連線例如依靠 TCP), best effort (盡力傳送), 不保證頻寬、順序、送達時間、也沒有壅塞 feedback
- ATM (Asynchronous Transfer Mode): 建連線
VC network vs. Datagram network:
Datagram network: provides network-layer connectionless service
VC network: provides network-layer connection service
Virtual circuits
- 像電話系統，連線前要先將電話線打通
- 建連線 => For ATM 等 architectures, not for Internet
- VC consists of path from source to destination
- A series of VC numbers, one number for each link along path
- Entries in forwarding tables in routers along path
- Each packet carries VC identifier (not destination host address)
VC identifier 值小，能提升傳送速度
- Every router on source-dest path maintains “state” for each passing connection
Datagram networks
- 像郵政系統
- No call setup at network layer
- Routers: no state about end-to-end connections (不用記憶前後的 routers)
=> no network-level concept of “connection”
- Packets forwarded using destination host address
=> packets between same source-dest pair may take different paths
Internet (Datagram network)
Internet architecture has three protocols: routing protocol, Internet protocol (IP) and ICMP protocol
- Data exchange among computers
=> “elastic” service, no strict timing req.
- “Smart” end systems (computers)
=> can adapt, perform control, error recovery
=> simple inside network, complexity at “edge” (中間簡單, edge 複雜)
- Easier to interconnect networks that use different link types (satellite, Ethernet, fiber, radio)
=> different characteristics
=> uniform service difficult
Router
Router = input port + switching fabric + output port
- input port = line termination + datalink processing + lookup forwarding queueing
- switching fabric = 常見種類: memory (應該已經被淘汰), bus, crossbar
- output port = queueing (buffer management) + datalink processing + line termination
Two key router functions:
- run routing algorithms/protocol (RIP, OSPF, BGP)
- forwarding datagrams from incoming to outgoing link
Routing Algorithms
Global (“link state” algorithms) vs. Decentralized information (“distance vector” algorithms)
Static vs. Dynamic
Link state
<空>
Distance vector
- 每個 router 知道自己的 distance vector+ 鄰居的 distance vector
- Asynchronous (有需要在更新資訊)
何謂有需要？ When node x receives new DV estimate from neighbor, it updates its own DV using B-F equation.
- Link cost 減少，table 更新速度變快，反之變慢
Hierarchical Routing
- 將 router們 分群
- = Autonomous Systems (AS, 自治區)
=> 集合的 router 規範自己的 policy
=> Same AS run same protocol (intra-AS protocol)
- Gateway router: 用於跟其他 AS 溝通
Link state vs. Distance vector
Message complexity
LS: with n nodes, E links, O(n*E) messages sent
DV: exchange between neighbors only => convergence time varies (Table 收斂時間不同)
Speed of Convergence (收斂速度)
LS: O(n^2) algorithm requires O(n*E) messages => may have oscillations (可能有震盪現象：路徑不停改變)
DV: convergence time varies
=> may be routing loops
=> count-to-infinity problem
Robustness: what happens if router malfunctions? (出錯應對)
LS:
- more robust
- node can advertise incorrect
linkcost - each node computes only its own table
DV:
- DV node can advertise incorrect
pathcost => less robust - each node’s table used by others => error propagate through network
Dijsktra’s Algorithm
- Belong to link state algorithm
- 結果用於 create forwarding table
Notation:
- c(x, y): Link cost from node x to y; = ∞ if not direct neighbors
- D(v): Current value of cost of path from source to destination v (彼此間的 cost)
- p(v): Predecessor node along path from source to v
- N’: Set of nodes whose least cost path definitively known
2. 從 node u 開始 (任意起點)
3. 對於所有 node v
4-6.
若 v,u 相連(adjacent) => 彼此間的 cost D(v) = c(u, v)
否則 => 彼此間的 cost D(v) = ∞Algorithm complexity: n nodes
- Each iteration: need to check all nodes, w, not in N
- n(n+1)/2 comparisons: O(n^2)
- more efficient implementations possible: O(nlogn) =>好的 sorting 有機會加速
Oscillations possible (震盪現象):
- 路徑會不停改變 => 因為要找最少 cost
Bellman-Ford algorithm
- Belong to distance vector algorithm
- 結果用於 create forwarding table
Routing in the Internet
Intra-AS Routing
- AS 內部的 routing
- Also known as Interior Gateway Protocols (IGP)
Interior: 內部
Most common Intra-AS routing protocols:
- RIP: Routing Information Protocol (業界標準)
- OSPF: Open Shortest Path First (找最短路徑，業界標準)
- IGRP: Interior Gateway Routing Protocol (Cisco proprietary, 非業界標準，私人 protocol)
RIP (Routing Information Protocol)
- Distance vector algorithm
- Included in BSD-UNIX Distribution in 1982
- Distance metric: # of hops (max = 15 hops)
=> 每個 Router 間的 link 距離為1 (不論傳送速度)，Router 間最遠距離為15個 Routers
OSPF (Open Shortest Path First)
- “open source”: publicly available — defined in RFC 2328
- Uses Link State algorithm
=> Link-State packet dissemination (廣播 LS packet 給所有 routers)
=> Topology map at each node
=> Route computation using Dijkstra’s algorithm
- OSPF advertisement carries one entry per neighbor router
- Advertisements disseminated to entire AS (via flooding)
=> Carried in OSPF messages directly over IP (rather than TCP or UDP)
OSPF “advanced” features (not in RIP)
- Security: all OSPF messages authenticated (to prevent malicious intrusion)
- Multiple same-cost paths allowed (only one path in RIP) => 有替代路徑可以走
- For each link, multiple cost metrics for different TOS (Type of Service)
=> e.g., satellite link cost set “low” for best effort; high for real time)
- Integrated uni- and multicast support:
=> Multicast OSPF (MOSPF) uses same topology data base as OSPF
- Hierarchical OSPF in large domains.
Inter-AS Routing
- AS彼此間的 routing
- BGP (Border Gateway Protocol): the de facto standard
BGP
- 可以告訴全世界你的 AS 在哪
- AS 間成對的 Routers (Gateway router) 建 TCP 連線交換資料
Intra-AS routing vs. Inter-AS routing
Policy
- Inter-AS: administrator wants control over how AS’s traffic routed, who routes through its net.
- Intra-AS: single admin, so no policy decisions needed
Scale
- hierarchical routing saves table size, reduced update traffic
Performance
- Intra-AS: can focus on performance (效能越快越好)
- Inter-AS: policy may dominate over performance (管制比效能重要)
Broadcast and multicast routing
- 對於多人連線遊戲非常重要
- Broadcast routing: deliver a packet from a source node to all other nodes
- Multicast routing: deliver a packet from a source node to a subset of other nodes
Broadcast routing
廣播到所有的 node
Spanning Tree
- First construct a spanning tree
- 建完樹後，不論哪個 node 只對樹廣播
Multicast routing
- more complicated than broadcast
source-based tree: one tree per source
- shortest path trees
- reverse path forwarding: 能避免不必要的轉送
group-shared tree: group uses one tree
- minimal spanning (Steiner): 實際沒使用, NP-complete
- center-based trees: one router identified as “center” of tree, DVMR protocol (看下面介紹)
DVMRP (Distance Vector Multicast Routing Protocol) [RFC1075]
- Internet 實際使用的 protocol
- flood and prune: reverse path forwarding
prune: 如果 router 之下沒有 member ，送 prune message 給 tree => 砍掉不必要的傳送
- 先讓全部人連進來，再砍掉不需掉的 Router
- 使用者可以快速進入群組: 使用 IGMP to join at leaf
Internet protocol (IP)
懶得看架構索以跳過了
IP address
- 每一個 port (介面卡) 都有一個 IP adress
=> 所以一個 Router 可能很多個 IP
CIDR 技術 (Classless InterDomain Routing)
可以任意切割 Subnet 的技術
NAT: Network Address Translation
- 目的：解決網址不夠的問題
ICMP
- Internet Control Message Protocol
Reference
[1] 黃能富教授 — 計算機網路概論: https://www.youtube.com/playlist?list=PLS0SUwlYe8czNZ9rRVFwp-5we8oEoVN0D
[2] 黃能富教授計算機網路概論講義https://drive.google.com/drive/folders/1qGWvoR6cvZgb_AfKCPQXvk9mEOQQVjlU (私人連結)