Bài giảng Mạng máy tính - Chương 8, Phần 1: Tầng liên kết dữ liệu - Ngô Hồng Sơn

1Chương 8: 
Tầng liên kết dữ liệu
Giảng viên: Ngô Hồng Sơn
Khoa CNTT- ðHBK Hà Nội
Bộ môn Truyền thông và Mạng máy tính
2Tổng quan

 Tuần trước: Tầng ứng dụng

 Mô hình: client-server vs. P2P

 Case study: HTTP, Mail, FTP

 Tuần này: Tầng liên kết dữ liệu

 Dịch vụ:

 ðóng gói, ñịa chỉ hóa

 Phát hiện và sửa lỗi

 Kiểm soát luồng

 Kiểm soát truy nhập ñường
truyền

 Công nghệ mạng LAN (Local 
Area Network)

 Ethernet

 Wireless LAN

 Công nghệ mạng WAN (Wide 
Area Network)

 Frame relay

 ATM

 .
3Giới thiệu về
Tầng liên kết dữ liệu
4Nút mạng và liên kết

 Nút mạng:

 PCs, Laptop, Routers, 
Server

 Liên kết:

 Kênh truyền thông giữa
các nút kế tiếp

 Hữu tuyến: Ethernet LAN, 
ADSL, fiber optic

 Không dây: Wi-fi, Wi-Max, 
vệ tinh,

 Tầng liên kết dữ liệu: 
Truyền dữ liệu giữa các
thành phần kế tiếp
“link”
5Tầng liên kết dữ liệu và kiến trúc
phân tầng
LLC
(Logical Link Control)
MAC
(Media Access Control)
Application
Transport
Network
Data-link
Physical
802.2 LLC
802.3
Ethernet
802.4
Token Bus
802.5
Token Ring
802.11
Wi-Fi
802.16
Wi-Max
..
IEEE 802.x series
Media independent 
sub-layer
Media dependent 
sub-layer
6Tổng quan về các chức năng
Framing
Addressing
Flow control
Error control
Media Access Control
Datalink layer
7Các chức năng (1)

 ðóng gói - Framing:

 ðơn vị dữ liệu: Frame (khung tin)

 Bên gửi: ñặt gói tin tầng mạng vào khung tin, 
thêm phần ñầu, phần ñuôi

 Bên nhận: Bỏ phần ñầu, phần ñuôi và lấy gói tin 
truyền lên tầng mạng

 ðịa chỉ hóa - Addressing: 

 ðịa chỉ vật lý ñặt trong phần ñầu gói tin ñể ñịnh
danh nút nguồn, nút ñích
8Các chức năng (2)

 ðiều khiển truy nhập ñường truyền

 Nếu là mạng ña truy nhập, cần có các giao thức
truy nhập ñường truyền cho nhiều máy trạm

 Kiểm soát luồng: 

 Kiểm soát tốc ñộ truyền của bên gửi sao cho bên
nhận hoạt ñộng tốt, không bị quá tải

 Kiểm soát lỗi: 

 Phát hiện và sửa các lỗi bít

 e.g. parity check, checksum, CRC check
9Kiểm soát lỗi
Phát hiện lỗi
Phát hiện và sửa lỗi
10
Nguyên lý phát hiện lỗi
EDC= Error Detection Code (redundancy)
Mã phát hiện lỗi
Data
Data EDC
Data
Data’ EDC’
All bit in 
Data’ OK?
Y
N
Error
Link with bit errors
11
Mã chẵn lẻ

 Mã ñơn

 Phát hiện lỗi bít ñơn

 Mã hai chiều

 Phát hiện và sửa lỗi bít ñơn

 Khái niệm về checksum của
Internet?
101011
111100
011101
001010
101011
101100
011101
001010
12
Internet checksum (nhắc lại)

 Mã kiểm tra lỗi ñộ dài 16 bit

 Tại bên gửi

 ðặt 16 bit của checksum = 0

 Tổng theo các số 16 bits

 ðảo bit tất cả

 Tại bên nhận

 Tổng tất cả theo các số 16 bit

 Phải thu ñược toàn các bit 1

 Nếu không, gói tin bị lỗi
13
CRC: Cyclic Redundancy Check
Mã vòng

 Dữ liệu ñược xem như một số nhị phân: D

 Chọn một chuỗi r+1 bit, G (chuỗi sinh – Generator)

 Tìm một chuỗi R ñộ dài r bit, sao cho chuỗi ghép của D và R 
là một số nhị phân chia hết cho G (chia modulo 2)

 chia hết cho G 
D
D R
D
D’ R’
 mod G = 0 ?
Y
N
Link with bit errors
 mod G = 0
14
CRC: Cách tìm R

 có thể viết dưới dạng

 D.2r XOR R

 chia hết cho G

 D.2r XOR R = n.G

 D.2r = n.G XOR R

 Có nghĩa là R là số dư khi chia D.2r 
cho G (phép chia modulo 2)
R= D.2r mod G

 Ví dụ
10101001000 1001 
1001 1011110
1110
1001
1110
1001
1111
1001
1100
1001
1010
1001
110
R=110, chuỗi bít gửi ñi là
10101001110
D
G
R
D R
15
CRC biểu diễn dưới dạng ña thức

 1011 : x3 +x +1

 Ví dụ một số mã CRC ñược sử dụng trong thực tế:

 CRC-8 = x8 + x2 + x + 1

 CRC-12 = x12+x11+x3+x2+x

 CRC-16-CCITT = x16 + x12 + x5 + 1

 CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5
+ x4 + x2 + x + 1

 G càng dài, mã CRC phát hiện lỗi càng hiệu quả

 CRC ñược sử dụng rộng rãi trong thực tế

 Wi-fi, ATM, Ethernet

 Phép toán XOR ñược cài ñặt bởi phần cứng

 Phát hiện chuỗi bít bị lỗi có ñộ dài nhỏ hơn r+1 bit
16
Kiểm soát truy nhập
ñường truyền
17
Các dạng liên kết

 ðiểm-nối-ñiểm

 ADSL

 Telephone modem

 Leased Line.

 Quảng bá

 Mạng LAN truyền thống với hình trạng bus hay mạng hình
sao dùng hub (công nghệ lỗi thời)

 Wireless LAN, radio network, mobile network

 HFC:

 

 Các mạng quảng bá cần giao thức ñiều khiển truy
nhập ñể tránh xung ñột -> Giao thức ña truy nhập
18
Phân loại các giao thức ña truy
nhập

 Chia kênh: 

 Chia tài nguyên của ñường truyền thành nhiều phần nhỏ
(Thời gian - TDMA, Tần số - FDMA, Mã - CDMA)

 Chia từng phần nhỏ ñó cho các nút mạng

 Truy nhập ngẫu nhiên: 

 Kênh không ñược chia, cho phép ñồng thời truy nhập, chấp
nhận là có xung ñột (collision)

 Cần có cơ chế ñể phát hiện và tránh xung ñột

 e.g. Pure Aloha, Slotted Aloha, CSMA/CD, CSMA/CA

 Lần lượt:

 Theo hình thức quay vòng

 Token Ring, Token Bus.
19
Các phương pháp chia kênh

 FDMA: frequency division multiple access

 TDMA: time division multiple access

 CDMA: code division multiple access
20
TDMA và FDMA
FDMA
frequency
time
TDMA:
frequency
time
4 kênh
Ví dụ:
21
TDMA: Ví dụ

 Mạng LAN có 6 máy, 1,3,4 hoạt ñộng. 2, 5, 6 
nghỉ
1 3 4 1 3 4
6-slot
frame
22
FDMA: Ví dụ
f
r
e
q
u
e
n
c
y
b
a
n
d
s
time
FDM cable
23
Các phương pháp
truy cập ngẫu nhiên
24
Aloha

 Packet-Switched Radio Network

 Các nút truyền trên một tần số (f0) 

 Nút trung tâm nhận và truyền lại một
tần số khác (f1)
Nếu có hai nút cùng truyền: Xung ñột

 Nếu có xung ñột, nút vừa truyền sẽ
nhận ñược một gói tin bị lỗi, nó sẽ ñợi
một thời gian ngẫu nhiên trước khi
truyền lại
Central Node
Host 1 Host 3Host 2
f0 f1
25
Slotted ALOHA

 Thời gian ñược chia làm các khe (slot) bằng nhau

 Dữ liệu có cùng kích thước (1 slot)

 Các nút phải ñồng bộ hóa thời gian
26
Pure ALOHA
Hi
u qu kém hn Slotted ALOHA!
27
CSMA/CD

 Carrier Sense Multiple Access with Collision 
Detection (ða truy nhập, có phát hiện xung ñột)

 Thế nào là CSMA/CD: trong một cuộc họp

 Multiple Access: 

 Collision:

 CSMA: “Listen before talk”

 CD

 “Listen while talking”
b l a h
blah b l a h b l a h
28
CSMA/CD

 CSMA: Các máy nghe trước muốn truyền:

 Nếu kênh rỗi, truyền toàn bộ dữ liệu

 Nếu kênh bận, chờ (rút lui và quay lại)

 Tại sao lại có xung ñột?
ðộ trễ lan truyền
29
Xung ñột trong CSMA

 Giả sử kênh truyền có 4 
nút

 Tín hiệu ñiện từ lan truyền
từ nút này ñến nút kia mất
một thời gian nhất ñịnh
(trễ lan truyền)

 Ví dụ: 
30
CSMA/CD: Tóm tắt

 Máy trạm nghe trước khi muốn truyền

 Bận: Rút lui, sau ñó quay lại tiếp tục nghe

 Rỗi: Bắt ñầu truyền, vừa truyền vừa “nghe ngóng”
xem có xung ñột hay không

 Nghe trong thời gian bao lâu?

 Nếu phát hiện thấy xung ñột: Hủy bỏ quá trình
truyền và quay lại trạng thái rút lui

 Sau khi rút lui, khi nào thì quay lại

 Exponential back-off
31
So sánh chia kênh và truy
nhập ngẫu nhiên

 Chia kênh

 Hiệu quả, công bằng cho ñường truyền với lưu lượng lớn

 Lãng phí nếu chúng ta cấp kênh con cho một nút chỉ cần
lưu lượng nhỏ

 Truy nhập ngẫu nhiên

 Khi tải nhỏ: Hiệu quả vì mỗi nút có thể sử dụng toàn bộ
kênh truyền

 Tải lớn: Xung ñột tăng lên

 Phương pháp quay vòng: Có thể dung hòa ưu ñiểm
của hai phương pháp trên
32
Token Ring – Mạng vòng dùng thẻ bài

 Một “thẻ bài” luân
chuyển lần lượt qua 
từng nút mạng

 Nút nào giữ thẻ bài
sẽ ñược gửi dữ liệu

 Gửi xong phải
chuyển thẻ bài ñi

 Một số vấn ñề

 Tốn thời gian chuyền
thẻ

 Trễ

 Mất thẻ bài.
T
data
(nothing
to send)
T
33
Tổng kết các phương pháp kiểm
soát ña truy nhập

 Chia kênh

 Truy nhập ngẫu nhiên

 Quay vòng

 Phân tích ưu, nhược ñiểm
34
Thảo luận

 Trong phương pháp CSMA/CD, khi lượng dữ liệu
cần gửi tăng lên thì:

 Xung ñột tăng lên?

 Thông lượng tăng lên?

 Trong phương pháp TDMA, xung ñột sẽ tăng lên khi
lượng dữ liệu cần gửi tăng lên?

 Khi lượng dữ liệu cần gửi là rất nhiều, phương pháp
Token Ring là kém hơn so với CSMA/CD

 Câu hỏi: Giải thích một cách ñịnh lượng hiệu quả
của các phương pháp truy cập ñường truyền (Bài
tập lớn)
35
LAN: Local Area Network
36
LAN topology
Bus
Ring
WLAN
hub, switch
Star
37
Mạng Lan Ethernet

 IEEE 802.3

 Tốc ñộ ña dạng: 10 Mbps – 10 Gbps

 Ethernet: 10BaseT, 10Base2

 Fast Ethernet: 100BaseT

 Giga Ethernet
Metcalfe’s Ethernet
sketch
38
Mạng hình sao

 Mạng dạng bus từng phổ biến trước ñây

 Các nút mạng cùng chia sẻ một ñường trục

 Ngày nay: Chủ yếu là mạng hình sao

 Một bộ chuyển mạch trung tâm với nhiều cổng Ethernet 

 Bộ chuyển mạch có thể tạo liên kết ñộc lập cho 2 nút mạng
bất kỳ

 Không xung ñột

 Không giao thức ña truy nhập .
switch
bus: coaxial cable star
39
Cấu trúc ñơn vị dữ liệu của Ethernet

 Preamble: Bắt ñầu một khung tin

 Address: ðịa chỉ vật lý của trạm nguồn, trạm ñích

 6 bytes

 Type: Giao thức tầng trên (IP, Novell IPX, 
AppleTalk, )

 PAD: Phần thêm vào cho khung tin ñủ ñộ dài
(nếu cần thiết)

 CRC: Mã kiểm soát lỗi
PAD
40
Chuẩn mạng cục bộ 802.3 
Ethernet Standards

 Link & Physical Layers

 MAC: CSMA/CD

 Có nhiều chuẩn Ethernet khác nhau

 Cùng giao thức MAC và cấu trúc Frame

 Tốc ñộ khác nhau: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps

 Phương tiện truyền khác nhau: Cáp quang, cáp ñồng trục, cáp
xoắn ñôi.
application
transport
network
link
physical
MAC protocol
and frame format
100BASE-TX
100BASE-T4
100BASE-FX100BASE-T2
100BASE-SX 100BASE-BX
fiber physical layercopper (twister
pair) physical layer
41
Ethernet cổ ñiển
Cáp ñồng trục
ml 1500<
10Mb/s
( ) bitssMbsPacketsize
sTRANSPPROPTRANSP
sclPROP
120/1012
122
6105.2/1500/ 8max
=×≥∴
>⇒>
=×==
µ
µ
µ
Thực tế, Min packet size = 512 bits.
• Thêm thời gian phát hiện xung ñột.
• Cho phép “repeaters” ñủ thời gian khuếch ñại tín hiệu.
Bộ lặp
500m
42
Chuẩn Ethernet 10Mb/s 
Ethernet MAC Protocol
10Base-5 10Base-2 10Base-T 10Base-F
10Base-5: Cáp ñồng trục béo, max = 500m.
10Base-2: Cáp ñồng trục gầy, max ~ 200m (180m).
10Base-T: Dùng cáp xoắn ñôi (twisted-pair) CAT 3
10Base-F: Dùng cáp sợi quang.
43
10Base-T

 Sử dụng hub trung tâm, cáp TP CAT 3 (4 cặp
dây xoắn).

 Dễ lắp ñặt và quản trị

 Làm Ethernet trở nên phổ biến hơn
Hub
100m
44
“Fast Ethernet” 100Mb/s
Ethernet MAC Protocol
100Base-T4 100Base-TX 100Base-FX
Mạng hình sao, ðộ dài cáp 100m.
100Base-T4: Cáp TP CAT 3 .
100Base-TX: Cáp TP CAT 5.
100Base-FX: Cáp sợi quang.
Hub, switch
100m
45
“Gigabit Ethernet” 1Gbps
Ethernet MAC Protocol
1000Base-TX 1000Base-FX
1000Base-TX: 4 cặp dây xoắn, CAT 6.
1000Base-FX: Cáp sợi quang.
46
ðịa chỉ MAC và ARP

 ðịa chỉ IP : 

 32-bit

 Dùng trong tầng mạng IP

 ðịa chỉ MAC :

 Dùng trong tầng liên kết dữ liệu

 48 bit
47
48
ARP và ñịa chỉ MAC
Mỗi card mạng có một ñịa chỉ MAC
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)
49
ARP: Address Resolution Protocol

 Mỗi nút mạng (host, 
router) có một bảng
ARP

 ARP table: Ánh xạ ñịa
chỉ IP/MAC của một
số nút trong mạng
< IP address; MAC address; 
TTL>

 TTL (Time To Live): 
khoảng 20 min.)
Vấn ñề: Xác ñịnh ñịa chỉ MAC
từ ñịa chỉ IP
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
137.196.7.23
137.196.7.78
137.196.7.14
137.196.7.88
50
Giao thức ARP : Hoạt ñộng trên
cùng một mạng

 A muốn gửi dữ liệu tới B 
mà không biết ñ/c MAC 
của B

 A quảng bá một gói tin 
ARP, trong ñó chỉ ra ñ/c
IP của B

 Quảng bá ntn?

 Phạm vi gói tin ñược
quảng bá?

 B nhận ñược ñ/c này sẽ
trả lời A ñ/c MAC của
mình

 Làm sao biết A gửi?

 A lưu lại ñ/c MAC của
B và gửi tin ñến B

 ARP là một giao thức
“plug-and-play”

 Nếu muốn ARP mở
rộng phạm vi hoạt ñộng
sang một mạng khác?

 ARP Proxy
51
Ví dụ: chuyển gói tin giữa hai máy
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
A
74-29-9C-E8-FF-55
222.222.222.221
88-B2-2F-54-1A-0F
B
222.222.222.222
49-BD-D2-C7-56-2A
Giả sử A biết ñ/c IP của B
52

 A tạo một gói tin IP, ñịa chỉ nguồn A, ñịa chỉ ñích B

 A dùng ARP ñể lấy ñ/c MAC của router: 111.111.111.110

 A tạo một frame, ñ/c ñích là router, ñặt gói tin vào

 A chuyển frame tới R 

 R nhận frame 

 R ñọc ñịa chỉ IP của B từ trong khung tin

 R dùng ARP ñể tìm ñ/c MAC của B

 R tạo một frame, ñặt gói tin vào và chuyển ñến B
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
A
74-29-9C-E8-FF-55
222.222.222.221
88-B2-2F-54-1A-0F
B
222.222.222.222
49-BD-D2-C7-56-2A
53
Tuần tới

 More about LAN: 

 Bridge and Switch 

 WLAN

 Physical layer issues
54
Acknowledgment

 Bài giảng có sử dụng các tư liệu và hình vẽ
từ:

 Tài liệu của trường ñại học Keio và Ritsumekan

 Tài liệu “Computer Network, a top down 
approach” của J.F Kurose và K.W. Ross