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

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
17/01/2018
Chương 5. Tầng liên kết dữ liệu 3
Introduction & services
17/01/2018
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”
17/01/2018
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
Ht
HtHn
HtHnHl MHtHnHl
framephys. link
data link
protocol
17/01/2018
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.
17/01/2018
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.
17/01/2018
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
Ht
HtHn
HtHnHl MHtHnHl
framephys. link
data link
protocol
adapter card
17/01/2018
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
17/01/2018
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!
17/01/2018
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
17/01/2018
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
17/01/2018
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 1317/01/2018
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)
17/01/2018
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*2r 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ế.
17/01/2018
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
17/01/2018
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.2r XOR R = nG
=> D.2r = nG XOR R 
Do vậy:Nếu chia D.2r cho G, phần 
dư sẽ là R
R = remainder[ ]
D.2r
G
17/01/2018
Chương 5. Tầng liên kết dữ liệu 18
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
17/01/2018
Chương 5. Tầng liên kết dữ liệu 19
Multiple Access
Hai loại “links”:
 point-to-point
 PPP (dial-up access: kết nối Internet tại nhà qua modem)
 point-to-point link giữa Ethernet switch và host
 broadcast (chia sẻ: shared wire or medium)
 Radio; Bus LAN;
 802.11 wireless LAN
17/01/2018
Chương 5. Tầng liên kết dữ liệu 20
MAP: Multiple Access Protocols
 Các nút mạng dùng chung một đường truyền.
 Có lúc nhiều nút mạng cùng muốn truyền dữ liệu.
xung đột (collision).
chỉ có một nút truyền thành công!!!
 Multiple Access Protocol (MAP):
các quy tắc quy định việc sử dụng đường truyền chung 
giữa các nút mạng.
 Human MAP examples:
Class: đôi khi SV mất trật tự xung đột (collision).
Cocktail party: multiple languages
17/01/2018
Chương 5. Tầng liên kết dữ liệu 21
Ideal Mulitple Access Protocol
Đường truyền có tốc độ (rate) = R
 Khi một nút muốn truyền, tốc độ là R.
 Khi M nút muốn truyền, tốc độ TB là R/M.
 Điều khiển truy nhập phân tán:
không cần một nút đặc biệt để điều khiển (các nút tự 
điều khiển).
không cần các tín hiệu đồng bộ
 Đơn giản.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 22
MAP: taxonomy (phân loại)
 Channel partitioning (phân mảnh kênh truyền)
 kênh truyền được chia thành các “miếng” nhỏ (theo thời gian, tần 
số, code).
 mỗi “miếng” sẽ được một nút dùng riêng không xung đột 
(collision).
 Random access (truy nhập ngẫu nhiên)
 nút nào muốn truyền, ngẫu nhiên truy cập kênh truyền có khả 
năng xung đột; xử lý xung đột?
 Taking turns (truy nhập lần lượt)
 các nút phối hợp chặt chẽ trong việc sử dụng đường truyền 
không xung đột.
 Goal: efficient, fair, simple, decentralized
17/01/2018
Chương 5. Tầng liên kết dữ liệu 23
Channel Partitioning MAP: TDMA
TDMA: time division multiple access
 Các nút được lần lượt truy cập đường truyền trong 
khoảng thời gian xác định (time slot).
 Không phải nút nào cũng muốn truyền: unused slot 
(idle slot).
Vd: 6 slots, 3 idle do nút 2,5,6 không có nhu cầu.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 24
Channel Partitioning MAP: TDMA
FDMA: frequency division multiple access
 Phổ của kênh truyền được chia thành nhiều dải tần.
 Mỗi dải tần dành riêng cho một nút.
 Như vậy, nút không có nhu cầu truyền thì dải tần 
dành cho nó bị lãng phí (unused, idle).
Vd: 2,5,6 idle
f
re
q
u
e
n
c
y
 b
a
n
d
s
17/01/2018
Chương 5. Tầng liên kết dữ liệu 25
Channel Partitioning MAP: CDMA
CDMA (Code Division Multiple Access)
 Mỗi nút được xác định bởi mã duy nhất (code).
 Tất cả các nút sử dụng chung tần số nhưng lại có 
mã riêng (CQ - chipping sequence) để mã hoá và 
giải mã dữ liệu.
 encoded signal = (data) X (CQ)
 decoding: tích trong của encoded signal và CQ.
 Sử dụng chủ yếu trong mạng wireless (cellular, 
satellite).
17/01/2018
Chương 5. Tầng liên kết dữ liệu 26
CDMA example: encode/decode
17/01/2018
Chương 5. Tầng liên kết dữ liệu 27
CDMA example: two-sender interference
sender 1
sender 2
17/01/2018
Chương 5. Tầng liên kết dữ liệu 28
Random Access Protocols
 Khi nút muốn truyền:
 truy nhập đường truyền và truyền với tốc độ R
không có chế độ ưu tiên cho nút nào cả.
 Nếu nhiều nút cùng truyền xung đột.
cần có cơ chế phát hiện xung đột (collision detection).
khôi phục khi có xung đột (recovery): chờ một lúc rồi 
truyền lại
 Một số giao thức:
slotted ALOHA, ALOHA.
CSMA, CSMA/CD.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 29
Slotted ALOHA
 Chia thành các khoảng thời gian (time slot) = thời 
gian cần để truyền một frame.
 Nút luôn bắt đầu truyền từ thời điểm bắt đầu slot.
 Nếu xung đột, sẽ truyền lại frame tại thời điểm bắt 
đầu slot tiếp theo với xác suất p chọn trước.
Success (S), Collision (C), Empty (E) slots
VD
At best: channel
use for useful 
transmissions 37%
of time!
17/01/2018
Chương 5. Tầng liên kết dữ liệu 30
CSMA (Carrier Sense Multiple Access)
 Carrier Sense: 
 lắng nghe trước khi truyền.
 Nếu kênh truyền rỗi thì truyền toàn bộ frame.
 Nếu kênh truyền bận, tuỳ cơ ứng biến:
 thử lại ngay lập tức với xác suất p cho tới khi kênh 
truyền rỗi.
 thử lại sau một khoảng thời gian ngẫu nhiên.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 31
CSMA collisions
 space:
 khoảng cách giữa các 
nút.
 time: thời gian.
 Xung đột vẫn có thể xảy 
ra nếu trong khoảng 
thời gian t1-t0 tín hiệu 
chưa lan truyền được từ 
B tới D.
 Lãng phí!, cần cơ chế 
phát hiện xung đột.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 32
CSMA/CD (Collision Detection)
 CSMA/CD:
nghe trước khi truyền.
dò xung đột trong một khoảng thời gian ngắn (đủ lớn).
nếu phát hiện xung đột thì dừng truyền để tránh lãng 
phí.
 Phát hiện xung đột:
wired LAN: đo hiệu điện thế.
wireless: ???
17/01/2018
Chương 5. Tầng liên kết dữ liệu 33
CSMA/CD: example
17/01/2018
Chương 5. Tầng liên kết dữ liệu 34
“Taking Turns” MAP
 Channel partitioning MAP:
hiệu quả khi nhiều nút cùng sử dụng
ngược lại, gây lãng phí khi chỉ có vài nút cần truyền tin.
 Random Access MAP:
hiệu quả khi ít nút sử dụng: một nút có thể toàn quyền 
sử dụng đường truyền với tốc độ cao nhất.
nhiều nút cùng sử dụng: xung đột.
 Taking turns:
Tìm kiếm giải pháp tốt cho cả hai tình huống.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 35
“Taking Turns” MAP: Polling & Token passing
Polling
 Có một nút điều khiển (master) 
có nhiệm vụ:
 lần lượt “thông báo” cho các nút 
khác biết đến lượt truyền và được 
phép truyền tối đa một số lượng 
frame nào đó.
 khi một nút kết thúc truyền, 
master thông báo cho nút khác.
 Không xung đột.
 Vấn đề:
 mất thời gian thông báo: tốc độ 
trung bình < R.
 khi master gặp sự cố thì cả mạng 
ngừng hoạt động!
Token passing
 Thẻ bài (token) là một thông 
báo đặc biệt mà nút nào nắm 
giữ nó sẽ được phép sử dụng 
đường truyền.
 Thẻ bài được luân chuyển giữa 
các nút.
 Vấn đề:
 Một nút gặp sự cố ảnh hưởng tới 
toàn mạng.
 nút nào đó sao nhãng việc chuyển 
thẻ bài cho nút khác cần một 
vài thủ tục để khôi phục.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 36
LAN
 MAP được sử dụng rộng rãi:
 satellite, wireless
 LAN (Local Area Network).
 LAN:
 Mạng nội bộ, có phạm vi hẹp (toàn nhà, trường ĐH)
 Vd: LAN kết nối Internet
 chia sẻ đường truyền.
 Các loại LAN:
 Ethernet: phổ biến, sử dụng Random Access MAP.
 FDDI (Fiber Distributed Data Interface): Token-passing.
 
17/01/2018
Chương 5. Tầng liên kết dữ liệu 37
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
17/01/2018
Chương 5. Tầng liên kết dữ liệu 38
Link layer address
32-bit IP address:
 network-layer address
 IP được đóng trong các gói tin (nguồn, đích).
LAN (or MAC or physical) address: 
 48 bit (6 bytes) MAC address (đối với hầu hết LANs)
 được ghi trong adapter ROM
*MAC: Media Access Control (Link layer = MAC + LLC 
(Logical Link Control)
17/01/2018
Chương 5. Tầng liên kết dữ liệu 39
LAN Addresses and ARP
Mỗi adapter có một địa chỉ vật lý duy nhất, tương tự như số CMTND.
Broadcast address =
FF-FF-FF-FF-FF-FF
= adapter
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
(wired or
wireless)
17/01/2018
Chương 5. Tầng liên kết dữ liệu 40
MAC address (cont)
 Địa chỉ vật lý được phân bổ bởi IEEE.
 Nhà sản xuất phải đăng ký dải địa chỉ với IEEE.
 Khi di chuyển từ mạng này sang mạng khác: địa 
chỉ IP thay đổi nhưng địa chỉ vật lý không thay đổi.
 So sánh:
địa chỉ vật lý: số CMTND.
địa chỉ IP: địa chỉ hòm thư.
 Các frame muốn gửi tới đích thì cần chứa địa chỉ 
vật lý của nút đích.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 41
When packet sent from A to B
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
B
E
A gửi packet tới B, A sẽ:
 Tra cứu địa chỉ mạng của B, 
phát hiện ra B cùng mạng với A
 link layer gửi packet tới B thông 
qua frame.
B’s MAC
addr
A’s MAC
addr
A’s IP
addr
B’s IP
addr
IP payload
datagram
frame
frame source,
dest address
packet source,
dest address
17/01/2018
Chương 5. Tầng liên kết dữ liệu 42
ARP: Address Resolution Protocol
 Mỗi nút mạng (Host, 
Router) đều có ARP 
table
 ARP Table: cho phép từ 
IP tra cứu ra MAC addr
Cấu tạo bản ghi:
 TTL (Time To Live): 
thời gian tồn tại của bản 
ghi tới khi bị xoá.
???: Làm thế nào để 
biết địa chỉ vật lý của B khi 
biết IP của B?
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
237.196.7.23
237.196.7.78
237.196.7.14
237.196.7.88
17/01/2018
Chương 5. Tầng liên kết dữ liệu 43
Trường hợp chưa biết MAC addr của nút
 Nếu A muốn biết MAC addr của B (không có trong 
ARP table)
A đã biết IP của B (ipb).
A gửi ARP query packet tới tất cả các nút (broadcast), 
trong đó có chứa IP của B (ipb) hỏi xem nút nào có 
địa chỉ IP là ipb.
Tất cả các nút đều nhận được và kiểm tra xem ipb có 
trùng với IP của mình không, nếu trùng thì trả lời (nút 
B).
17/01/2018
Chương 5. Tầng liên kết dữ liệu 44
Trường hợp hai nút ở hai mạng khác nhau
 A (111.111.111.111) muốn gửi tin tới B (222.222.222.222)
 A không biết MAC addr của B, nếu gửi ARP pkt hỏi 
LAN1 không có nút nào trả lời.
A
R
B
17/01/2018
Chương 5. Tầng liên kết dữ liệu 45
 A tạo IP packet với địa chỉ IP gửi = A, và địa chỉ IP nhận = B 
 A dùng ARP để xác định MAC của R ứng với interface 111.111.111.110
 A tạo frame với dest. MAC = MAC của R, frame này chứa IP 
datagram từ A đến B.
 A’s data link layer sends frame 
 R’s data link layer receives frame 
 R lấy IP datagram khỏi frame, và coi đích đến là B
 R dùng ARP lấy địa chỉ MAC của B
 R tạo frame chứa IP datagram A-to-B IP rồi gửi đến B
A
R
B
17/01/2018