計算機網路和網際網路 — Data Link Layer

Computer Networks and Internet — Data Link Layer

5 min readNov 17, 2020

Version 0.4.1

Principle

Router and Router 間為一個 link
error detection, correction
sharing a broadcast channel (使用單一通道傳送資料): multiple access
link layer addressing
reliable data transfer, flow control

Content:
+ Link Layer Services
+ Techniques for Error Detection
+ Multiple Access Links and Protocols
+ MAC address and ARP (位址解析 protocol)
+ Ethernet
+ Hub and Switch
+ Point to Point
+ Virtualization
+ ATM
+ Multi-protocol label switching (MPLS)
+ Reference

Link Layer Services

Framing (打包)

encapsulate datagram into frame, adding header, trailer

Trailer: 包含錯誤檢查碼

‘physical addresses’ used in frame headers to identify source, destination => different from IP address!

Link access

Media access control (MAC) protocol
Coordinate the frame transmissions of many nodes if multiple nodes share a medium

Reliable delivery between adjacent nodes

Timeout 重送等等
Rare used on low bit error link (fiber, some twisted pair)
Always used on wireless links: high error rates => Correct an error locally at link level

Flow control
Error Detection, Error Correction
Half-duplex (能互送 + 不能同時送) and full-duplex (能互送 + 能同時送)

Techniques for Error Detection

Parity checks
Checksumming methods

Checksumming methods => used at transport layer only

Cyclic redundancy checks

Multiple Access Links and Protocols

Two types of “links”:

point-to-point
broadcast (shared wire or medium)

point-to-point

PPP (point-to-point protocol) for dial-up access
point-to-point link between Ethernet switch and host

broadcast (shared wire or medium)

traditional Ethernet
upstream HFC (Hybrid fiber coaxial cable)
802.11 wireless LAN

Multiple Access protocols

single shared broadcast channel => 只有一個通道，所以大家一起送資料的話會發生衝撞 (collision)
MAP => 決定誰可以送
但是是在同一條通道上決定，沒有另外開通道 (no out-of-band channel for coordination)
方法：TDMA (切時間), FDMA (切空間), Random Access, Taking-turns (802.5, 大家輪流)

Random Access: E.g. slotted ALOHA (from 夏威夷大學, 應該已經被淘汰), ALOHA, CSMA (送資料前先聽聽看), CSMA/CD, CSMA/CA
Taking-turns: E.g. polling, use token run on cycle

MAC address and ARP (位址解析 protocol)

MAC address

又稱 LAN or physical or Ethernet address
資料在 router 間傳送是靠 MAC address 不是靠 IP address
48 bit (vs. IP address 32 bit)
通常不可變更
若要廣播 = FF-FF-FF-FF-FF-FF (48個1)
administered by IEEE
有一部份的 bit 代表來自哪個廠商

How to determine MAC address of B knowing B’s IP address? (如何知道目的地的 MAC address?)

Use ARP Table: IP/MAC address mappings for some LAN nodes

Address Resolution Protocol (ARP)

A wants to send datagram to B, and B’s MAC address not in A’s ARP table.
A broadcasts ARP query packet, containing B’s IP address

=> Destination MAC address = FF-FF-FF-FF-FF-FF

=> all machines on LAN receive ARP query (大家都要收)

3. B receives ARP packet, replies to A with its (B’s) MAC address

4. A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)

=> soft state (持續更新 table): information that times out (goes away) unless refreshed

ARP is “plug-and-play”: nodes create their ARP tables without intervention from net administrator (不受 administrator 干預)

一個傳送的例子

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

Ethernet

802.3
dominant wired LAN technology => cheap, fast
Unreliable, connectionless service
Use CSMA/CD

Ethernet CSMA/CD algorithm

Adaptor receives datagram from network layer and creates frame
If adaptor senses channel idle, it starts to transmit frame. => If it senses channel busy, waits until channel idle and then transmits
If adapter transmits entire frame without detecting another transmission, the adapter is done with frame !
If adapter detects another transmission while transmitting, aborts and sends jam signal

jam signal: make sure all other transmitters are aware of collision; 48 bits; (讓他撞得更嚴重點)

5. After aborting, adapter enters exponential backoff: after the nth collision, adapter chooses a K at random from {0,1,2,…,2m-1} where m = min(n, 10). Adapter waits K*512 bit times and returns to Step 2

exponential backoff = 等等在 try 一次

Manchester encoding

在 Ethernet 上的編碼
Used in 10BaseT, 10Base2
Each bit has a transition — 1: up to down, 0: down to up
Allows clocks in sending and receiving nodes to synchronize to each other

=> no need for a centralized, global clock among nodes! (clock 和 data 混合在一起)

Hey, this is physical-layer stuff!

Hubs

physical-layer repeaters (訊號放大器)
沒 buffer (switch 做)
collision can be happened
no CSMA/CD

Switch

應該可以說是 Hub EX
Link layer device (不看IP但會處理 MAC)
smarter than Hub
one switch multiple port = multiple MAC
檢查 source 的 MAC address
Use CSMA/CD protocol
隨插即用，不需要設定
self-learning
Switches 可以彼此連結

Switches vs. Routers

Both store-and-forward devices

=> Routers: network layer devices (examine network layer headers)

=> Switches are link layer devices

Routers maintain routing tables, implement routing algorithms
Switches maintain switch tables, implement filtering, learning algorithms

Institutional network

IP subnet = broadcast domain (若廣播所有藍色內的 host 都收得到)

Point to Point

no MAC address

Point to point protocol (PPP, RFC 1557)

packet framing (有自己的 data frame): encapsulation of network-layer datagram in data link frame

=> carry network layer data of any network layer protocol (not just IP) at same time

=> ability to demultiplex upwards

bit transparency: must carry any bit pattern in the data field
error detection (no correction)
connection liveness: detect a link failure, signal link failure to network layer
network layer address negotiation: endpoint can learn/configure each other’s network address
no flow control (降低複雜度)

Virtualization

What is virtualized?

two layers of addressing: internetwork and local network
new layer (IP) makes everything homogeneous (一致) at internetwork layer
underlying local network technology (網路層下層不再重要)

=> cable, satellite, 56K telephone modem (早期), today: ATM, MPLS

=> … “invisible” at internetwork layer. Looks like a link layer technology to IP!

ATM (Asynchronous Transfer Mode)

設計時屬網路層，現在算是連接層
1990年代一個標準
當時目標: integrated, end-to-end transport for carrying voice, video, data
有timing, QoS (Internet 沒有 => best-effort)
連線之前要建連線
傳送最小單位: a cell => 5 byte ATM cell header + 48 byte payload
Virtual circuit transport
傳送看 VC identifier (hot destination ID)
兩大類: Permanent VCs (long lasting), Switched VCs (動態)

ATM Adaptation Layer (AAL)

“adapts” upper layers (IP or native ATM applications) to ATM layer below
AAL present only in end systems (網段末端的 Router), not in switches
AAL layer segment (header/trailer fields, data) is fragmented across multiple ATM cells

類比: TCP segment is fragmented in many IP packets

ATM cell

In ATM layer (under AAL Layer)
5 byte ATM cell header + 48 byte payload

Multi-protocol label switching (MPLS)

建連線
不看 IP address 看 label (也不看 MAC)
應該也是被 Ethernet 幹掉

Reference

[1] 黃能富教授 — 計算機網路概論: https://www.youtube.com/playlist?list=PLS0SUwlYe8czNZ9rRVFwp-5we8oEoVN0D

[2] 黃能富教授計算機網路概論講義https://drive.google.com/drive/folders/1qGWvoR6cvZgb_AfKCPQXvk9mEOQQVjlU (私人連結)