Bài giảng Mạng máy tính - Chương 5: Giao thức tầng liên kiết dữ liệu (Data link) - Trần Quang Diệu

Chương 5.Giao thức tầng liên kiết dữ liệu (data link) 
Quang Dieu Tran, PhD 
Faculty of Information Technology 
University of Communication and Transport ( Branch in Ho Chi Minh City) 
Email : dieutq@gmail.com 
Website: sites.google.com/sites/tranlectures 
Chương 5. Tầng liên kết dữ liệu 
2 
Ch5. Giao thức tầng liên kết dữ liệu 
5.1 - Introduction and services 
5.2 - Error detection and correction 
5.3 - Multiple access protocols & LAN 
5.4 - Link-layer addressing & ARP 
5.5 - Specific link layer technologies 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
3 
Introduction & services 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
4 
Data Link 
Data link: Liên kết dữ liệu; tầng 2. 
PDU: frame . 
packet nhiều frame 
Nhiệm vụ của tầng data link là truyền các các packet (datagram) từ nút này tới nút khác. 
“link” 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
5 
Data Link & frame 
Link: 
router-router; host-host; router-host 
frame: dữ liệu của tầng data link 
application 
transport 
network 
link 
physical 
network 
link 
physical 
M 
M 
M 
M 
H 
t 
H 
t 
H 
n 
H 
t 
H 
n 
H 
l 
M 
H 
t 
H 
n 
H 
l 
frame 
phys. link 
data link 
protocol 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
6 
Các dịch vụ của tầng data link 
Đóng frame và truy cập đường truyền (framing, link access) 
đóng gói tin vào các frame 
truy nhập đường truyền (đường truyền dùng chung cần có quy tắc truy nhập) 
địa chỉ vật lý (physical addr) được sử dụng. 
Truyền tin cậy (reliable delivery): rdt. 
đảm bảo các gói tin của tầng mạng không bị lỗi. 
tuỳ thuộc chất lượng đường truyền. 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
7 
Các dịch vụ của tầng data link (cont) 
Flow control (điều khiển lưu lượng!!!) 
đảm bảo lưu lượng truyền hợp lý, nút nhận không bị quá tải 
Error detection 
lỗi có thể phát sinh do nhiễu, tín hiệu yếu 
nút nhận phát hiện lỗi, bỏ qua hoặc yêu cầu nút gửi gửi lại. 
Error correction 
nút nhận xác định bit bị lỗi và sửa lỗi. 
Half-duplex and Full-duplex 
half-duplex: các nút không thể truyền nhận đồng thời. 
full-duplex: các nút có thể truyền nhận đồng thời. 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
8 
Implementation 
Link layer được thực thi tại network adapter (NIC – Network Interface Card): 
NIC = RAM + DSP chips + host bus interface + link interface 
application 
transport 
network 
link 
physical 
network 
link 
physical 
M 
M 
M 
M 
H 
t 
H 
t 
H 
n 
H 
t 
H 
n 
H 
l 
M 
H 
t 
H 
n 
H 
l 
frame 
phys. link 
data link 
protocol 
adapter card 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
9 
Ch5. Giao thức tầng liên kết dữ liệu 
5.1 - Introduction and services 
5.2 - Error detection and correction 
5.3 - Multiple access protocols & LAN 
5.4 - Link-layer addressing & ARP 
5.5 - Specific link layer technologies 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
10 
Error detection and correction 
D = Data 
EDC= Error Detection and Correction bits 
Bits thêm vào với mục đích kiểm soát lỗi. 
Số lượng bit càng cao thì khả năng kiểm soát lỗi càng tốt. 
Error detection: không phải lúc nào cũng phát hiện được lỗi! 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
11 
Parity 
Parity: cân bằng!!! (chẵn lẻ). 
Parity chẵn (even parity) 
tổng số các bit 1 (bao gồm cả bit parity) là chẵn. 
vd: parity của 101010101 là 1 (tổng số bit 1 = 5+1). 
parity bit = (số bit 1 của data là lẻ) ? 1 : 0 
Parity lẻ (odd parity): 
tổng số các bit 1 (bao gồm cả bit parity) là lẻ. 
vd: parity của 101010101 là 0 (tổng số bit 1 = 5). 
parity bit = (số bit 1 của data là chẵn)? 1:0 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
12 
Parity checking 
Single Bit Parity: 
Detect single bit errors 
Two Dimensional Bit Parity : 
Detect and correct single bit errors 
0 
0 
14/02/2024 
Parity checking (cont.) 
Biết rằng đơn vị dữ liệu sau khi thêm bit kiểm tra là 7. Hãy tính ma trận kiểm tra chẵn lẻ hai chiều của chuỗi ký tự “SING” 
Giải: các ký tự trong chuỗi có mã 83 - 73 - 78 -71 
Chương 5. Tầng liên kết dữ liệu 
13 
14/02/2024 
0 
1 
0 
1 
0 
0 
0 
1 
1 
0 
1 
0 
0 
1 
1 
0 
0 
1 
0 
1 
1 
0 
0 
1 
1 
1 
0 
1 
0 
1 
0 
0 
0 
1 
0 
1 
1 
0 
0 
0 
0 
0 
1 
0 
1 
0 
1 
0 
1 
Chương 5. Tầng liên kết dữ liệu 
14 
Internet Checksum 
Sender: 
Coi segment là một dãy các số nguyên 16 bit 
checksum: tổng bù 1của các số 16-bit có segment 
Sender chèn giá trị tổng bù 1 trên vào trường checksum trong UDP 
Receiver: 
Tính checksum của segment nhận được 
So sánh giá trị tính được với giá trị tại trường checksum: 
NO – Có lỗi 
YES – Không có lỗi. nhưng vẫn có thể có lỗi? . 
Goal: Phát hiện “errors” (vd: đảo bit) trong quá trình truyền/nhận các segment (lưu ý: chỉ dùng ở tầng transport) 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
15 
CRC – Cyclic Redundancy Check 
Data = d bits dữ liệu ( D ). 
Sender chọn r+1 bit sinh ( G - generator). 
Chọn r CRC bits ( R ) sao cho: 
DR chia hết cho G (modulo 2) 
DR = D*2 r XOR R. (= (D << r ) XOR R) 
receiver: nhận D’R’; biết trước G; chia D’R’ cho G, nếu phép chia có dư có lỗi. 
có thể phát hiện lỗi <= r bit. 
CRC được sử dụng rộng rãi trong thực tế. 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
16 
Phép tính modulo 2 
Phép tính modulo N: 
K/quả modulo N = kết quả bình thường mod N. 
Vd: 5+9 (mod 4) = 14 mod 4 = 2. 
Phép tính modulo 2 với số nhị phân: 
Thực hiện với từng bit. 
1+1 (mod 2) = 0; 1+0 (mod 2) = 1 (không nhớ!!!) 
1-0 (mod 2) = 0 – 1 (mod 2) = 1 
Với hai số nhị phân b1 và b2 (cộng không nhớ): 
b1 + b2 = b2 + b1 = b1 XOR b2 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
17 
CRC Example 
Biết: D,G. Tìm R? 
DR chia hết cho G (mod 2) nghĩa là: 
 D . 2 r XOR R = nG 
=> D . 2 r = nG XOR R 
	Do vậy: Nếu chia D . 2 r cho G, phần dư sẽ là R 
R = remainder[ ] 
D . 2 r 
G 
14/02/2024 
Chương 5. Tầng liên kết dữ liệu 
18 
Ch5. Giao thức tầng