計算機網路和網際網路 - Network layer

Computer Networks and Internet - Network layer

5 min readNov 4, 2020

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:

https://drive.google.com/drive/folders/1qGWvoR6cvZgb_AfKCPQXvk9mEOQQVjlU

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 link cost
each node computes only its own table

DV:

DV node can advertise incorrect path cost => 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 (私人連結)