Giáo trình Mạng máy tính - Chương 5: Tầng liên kết dữ liệu

1-1
Mạng máy tính
Bộ môn Kỹ thuật máy tính và Mạng
Khoa Công nghệ Thông tin
Đại học Sư phạm Hà Nội
1-2
Chương 5: Tầng liên kết dữ liệu
Mục đích:
‰ Hiểu các nguyên tắc bên trong của các dịch vụ
tầng liên kết dữ liệu:
 Phát hiện và sửa lỗi
 Chia sẻ một kênh broadcast: đa truy cập
 Đánh địa chỉ tầng liên kết dữ liệu
 Truyền dữ liệu tin cậy, điều khiển luồng: có!
‰ Ví dụ và cài đặt của các công nghệ tầng liên kết
dữ liệu khác nhau
1-3
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-4
Tầng liên kết dữ liệu: Giới thiệu
Một số thuật ngữ:
‰ host và router: nút
‰ Kênh truyền thông kết nối các
nút kề dọc theo đường truyền
thông gọi là liên kết (link)
 Liên kết có dây
 Liên kết không dây
 LAN
‰ Các gói tin tầng 2 gọi là khung
(frame), đóng gói các datagram
“liên kết”
Tầng liên kết dữ liệu có vai trò truyền các datagram từ một
nút tới nút kề qua một liên kết
1-5
Tầng liên kết dữ liệu: 
Xem xét với tầng khác
‰ Datagram được truyền bởi các
giao thức liên kết dữ liệu khác
nhau qua các liên kết khác
nhau:
 Ví dụ: Ethernet ở liên kết đầu
tiên, frame relay ở liên kết giữa, 
802.11 ở liên kết cuối cùng
‰ Mỗi giao thức liên kết dữ liệu
cung cấp các dịch vụ khác nhau
 Ví dụ: có thể hoặc không cung
cấp truyền tin cậy qua liên kết
Tương tự vận tải: 
‰ Chuyến đi từ Hà Nội tới Cần Thơ
 Đường sắt (tàu hỏa): HN -> Đà
Nẵng
 Đường không (máy bay): Đà
Nẵng -> Tp HCM
 Đường bộ (ô tô): Tp HCM -> 
Cần Thơ
‰ khách du lịch = datagram
‰ transport segment = liên kết
truyền thông (communication 
link)
‰ hình thức vận tải = giao thức
tầng liên kết dữ liệu
‰ đại lý du lịch = thuật toán dẫn
đường
1-6
Các dịch vụ tầng liên kết dữ liệu
‰ Đóng khung, truy cập liên kết:
 Đóng gói datagram thành các khung, thêm header, trailer
 Truy cập kênh nếu phương tiện dùng chung (shared 
medium)
 Các địa chỉ “MAC” sử dụng trong header của khung để định
danh nguồn, đích
• Khác với địa chỉ IP!
‰ Truyền tin cậy giữa các nút kề
 Đã học cách để thực hiện truyền tin cậy (chương 3)!
 Ít khi sử dụng trên các liên kết lỗi bít thấp (ví dụ: cáp quang, 
cáp xoắn đôi)
 Liên kết không dây: tỷ lệ lỗi cao
• Q: Tại sao xét tin cậy cả mức liên kết dữ liệu và end-
end?
1-7
Các dịch vụ tầng liên kết dữ liệu
‰ Điều khiển luồng:
 Tốc độ giữa nút nhận và nút gửi kề nhau
‰ Phát hiện lỗi:
 Các lỗi gây ra bởi suy hao và nhiễu tín hiệu
 Bên nhận phát hiện sự tồn tại của lỗi: 
• Báo hiệu cho bên gửi biết để gửi lại hoặc loại bỏ khung
‰ Sửa lỗi:
 Bên nhận xác định và sửa các bít lỗi không phải sử dụng
đến việc truyền lại
‰ Half-duplex và full-duplex
 Với half duplex, các nút tại cả hai điểm cuối của liên kết có
thể truyền nhưng không tại cùng thời điểm
1-8
Truyền thông thích nghi
‰ Tầng liên kết dữ liệu
được cài đặt trong
“adaptor” (còn gọi là NIC)
 Ethernet card, PCMCI card, 
802.11 card
‰ Bên gửi:
 Đóng gói datagram trong
một frame
 Thêm các bít kiểm tra lỗi, 
rdt, điều khiển luồng,
‰ Bên nhận
 Tìm kiếm lỗi, rdt, điều khiển
luồng,
 Tách ra datagram, chuyển
tới nút nhận
‰ adapter là bán tự trị
‰ Tầng vật lý và liên kết dữ
liệu
Nút
gửi
frame
nút
nhận
datagram
frame
adapter adapter
giao thức tầng liên kết dữ liệu
1-9
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-10
Phát hiện lỗi
EDC= Error Detection and Correction bits (phần dôi thừa)
D = Dữ liệu được bảo vệ bằng kiểm tra lỗi, có thể bao gồm các trường
header
• Phát hiện lỗi không 100% tin cậy!
• Giao thức có thể không phát hiện ra một số lỗi nhưng tỷ lệ rất thấp
• Trường EDC càng rộng thì phát hiện và sửa lỗi càng tốt
1-11
Kiểm tra tính chẵn lẻ
Bít chẵn lẻ đơn:
Phát hiện một bít lỗi
Bít chẵn lẻ 2 chiều:
Phát hiện và sửa một bít lỗi
0 0
1-12
Internet checksum
Bên gửi:
‰ Xem xét nội dung của các
segment như một chuỗi các
số nguyên 16 bít
‰ checksum: tổng (bù 1) của
nội dung segment
‰ Bên gửi đặt giá trị
checksum vào trong trường
checksum của UDP
Bên nhận:
‰ Tính toán checksum của
segment đã nhận
‰ Kiểm tra nếu giá trị checksum 
đã tính bằng giá trị trường
checksum:
 NO – Lỗi được phát hiện
 YES – Không phát hiện ra
lỗi. Nhưng có thể có lỗi?
Mục đích: Phát hiện lỗi trong segment đã truyền (Chú ý: 
chỉ sử dụng tại tầng giao vận)
1-13
Checksumming: Cyclic Redundancy Check
‰ Coi các bít dữ liệu D như một số nhị phân
‰ Chọn r+1 bít mẫu (generator), G
‰ Mục đích: chọn r bít CRC, R, ví dụ
 chia hết cho G (modulo 2) 
 Bên nhận biết G, chia cho G. Nếu phần dư khác không: lỗi
được phát hiện!
 Có thể phát hiện các lỗi ít hơn r+1 bít
‰ Sử dụng rộng rãi trong thực tế (ATM, HDCL)
1-14
Ví dụ CRC
Muốn:
D.2r XOR R = nG
Tương đương:
D.2r = nG XOR R 
Tương đương:
Nếu D.2r chia G, 
phần dư là R
R = Phần dư [ ]D
.2r
G
1-15
CRC
‰ Chuẩn quốc tế đã định nghĩa 8-, 12-, 16- và 32-bit 
generator, G.
‰ 8-bit CRC sử dụng để phát hiện lỗi trong ATM cell
‰ 32-bit bít CRC sử dụng để phát hiện lỗi trong giao thức
IEEE của tầng liên kết dữ liệu, sử dụng
GCRC-32 = 10000010 01100000 10001110 110110111 
1-16
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-17
Các giao thức và liên kết đa truy cập
Hai kiểu liên kết:
‰ point-to-point
 PPP trong truy cập dial-up
 Liên kết point-to-point giữa Ethernet switch và host
‰ broadcast (chia sẻ phương tiện)
 Ethernet
 upstream HFC
 802.11 wireless LAN
1-18
Các giao thức đa truy cập
‰ Kênh quảng bá, dùng chung, đơn
‰ hai hoặc nhiều nút truyền đồng thời: đan xen
 Đụng độ nếu nút nhận hai hoặc nhiều tín hiệu tại cùng
một thời điểm
Giao thức đa truy cập
‰ Thuật toán phân tán xác định cách nút dùng
chung kênh (xác định khi nào một nút có thể
truyền)
‰ Truyền thông về việc dùng chung kênh phải sử
dụng chính kênh đó! 
 Không có kênh ở ngoài cùng phối hợp hoạt động
1-19
Ý tưởng của giao thức đa truy cập
Kênh quảng bá tốc độ R bps
1. Khi một nút muốn truyền, nó có thể gửi với tốc độ R
2. Khi M nút muốn truyền, mỗi nút có thể gửi với tốc độ
trung bình R/M
3. Hoàn toàn không tập trung:
 Không có nút đặc biệt để phối hợp việc truyền
 Không có sự đồng bộ của đồng hồ hay khe
4. Đơn giản
1-20
Giao thức MAC: Phân loại
Ba lớp lớn:
‰ Phân chia kênh
 Chia kênh thành các phần nhỏ (khe thời gian, tần số, mã)
 Cấp phát phần cho nút sử dụng riêng
‰ Truy cập ngẫu nhiên
 Không chia kênh, cho phép đụng độ
 “Khôi phục” từ đụng độ
‰ Theo phiên lần lượt
 Các nút lần lượt truyền theo phiên nhưng nút cần gửi nhiều
có thể chiếm phiên dài hơn
1-21
Giao thức MAC kiểu phân chia kênh: TDMA
TDMA: time division multiple access
‰ Truy cập tới kênh theo vòng
‰ Mỗi trạm nhận một khe chiều dài cố định (chiều dài = thời gian
truyền gói tin) trong mỗi vòng
‰ Các khe không sử dụng sẽ rỗi
‰ Ví dụ: 6 trạm LAN, 1,3,4 có gói tin, khe 2,5,6 rỗi
‰ TDM (Time Division Multiplexing): kênh được chia thành N khe
thời gian, một khe cho một người sử dụng; không hiệu quả với
người sử dụng chu kỳ thấp và tải nặng.
‰ FDM (Frequency Division Multiplexing): chia theo tần số
1-22
Giao thức MAC kiểu phân chia kênh: FDMA
FDMA: frequency division multiple access
‰ Phổ của kênh được chia thành các băng tần
‰ Mỗi trạm được gán một băng tần cố định
‰ Thời gian truyền không sử dụng trong băng tần thì sẽ rỗi
‰ Ví dụ: 6 trạm LAN; 1,3,4 có gói tin; băng tần 2,5,6 rỗi
‰ TDM (Time Division Multiplexing): kênh được chia thành N khe thời gian, 
một khe cho một người sử dụng; không hiệu quả với người sử dụng chu kỳ
thấp và tải nặng
‰ FDM (Frequency Division Multiplexing): chia theo tần số
b
ă
n
g
t
ầ
n
thời gian
1-23
Giao thức MAC kiểu phân chia kênh: CDMA
1-24
Giao thức truy cập ngẫu nhiên
‰ Khi nút có gói tin để gửi
 Truyền trên toàn kênh với tốc độ dữ liệu R
 Không có sự phối hợp trước giữa các nút
‰ Hai hoặc nhiều nút truyền➜ “đụng độ”
‰ Giao thức MAC truy cập ngẫu nhiên chỉ ra:
 Cách phát hiện đụng độ
 Cách khôi phục từ đụng độ (ví dụ: đợi một khoảng thời gian
rồi truyền lại)
‰ Ví dụ của giao thức MAC kiểu truy cập ngẫu nhiên
 slotted ALOHA
 ALOHA
 CSMA, CSMA/CD, CSMA/CA
1-25
Slotted ALOHA
Giả sử
‰ Mọi frame có cùng kích
thước
‰ Thời gian được chia
thành các khe có kích
thước bằng nhau, thời
gian để truyền 1 frame
‰ Nút bắt đầu truyền frame 
chỉ tại bắt đầu của khe
‰ Các nút được đồng bộ
‰ Nếu 2 hoặc nhiều nút
truyền trong khe, mọi nút
phát hiện đụng độ
Hoạt động
‰ Khi nút giành khung mới, 
nó truyền trong khe tiếp
theo
‰ Không đụng độ, nút có thể
gửi frame mới trong khe
tiếp
‰ Nếu đụng độ, nút truyền lại
frame trong khe sau ngẫu
nhiên tới khi thành công
1-26
Slotted ALOHA
Pros
‰ Nút kích hoạt đơn có
thể liên tục truyền với
tốc độ của cả kênh
‰ Không tập chung cao: 
chỉ các khe trong nút
cần được đồng bộ
‰ Đơn giản
Cons
‰ Đụng độ, lãng phí khe
‰ Các khe rỗi
‰ Các nút có thể có khả
năng phát hiện đụng độ
nhỏ hơn thời gian
truyền gói tin
‰ Đồng bộ đồng hồ
1-27
Hiệu suất của Slotted Aloha
‰ Giả sử có N nút với
nhiều frame để gửi, mỗi
nút truyền trong khe với
xác suất là p
‰ Xác suất nút 1 có sự
thành công trong một
khe = p(1-p)N-1
‰ xác suất một nút bất kỳ
có sự thành công = 
Np(1-p)N-1
‰ Để tối đa hiệu suất với
N nút, tìm p để tối đa
Np(1-p)N-1
‰ Đối với nhiều nút, giới
hạn của Np*(1-p*)N-1 khi
N tiến ra vô hạn bằng
1/e = 0.37
Hiệu suất là phần thời gian dài
của các khe thành công khi có
nhiều nút, mỗi nút có nhiều
frame để gửi
Tốt nhất: kênh sử dụng
cho việc truyền hữu ích
chiếm 37% thời gian
1-28
Pure (unslotted) ALOHA
‰ unslotted Aloha: đơn giản, không đồng bộ
‰ Khi frame đầu tiên đến
 truyền ngay lập tức
‰ Xác suất đụng độ tăng:
 frame gửi tại t0 đụng độ với frame khác gửi trong khoảng [t0-
1,t0+1]
1-29
Hiệu suất của Pure Aloha
P(sự thành công của một nút) = P(nút truyền) .
P(không có nút khác truyền trong
[p0-1,p0] .
P(không có nút khác truyền trong
[p0-1,p0] 
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
 chọn p tối ưu và cho n tiến tới vô hạn ...
= 1/(2e) = .18 
1-30
CSMA (Carrier Sense Multiple Access)
CSMA: Nghe trước khi truyền:
Nếu nghe thấy kênh rỗi: truyền toàn bộ frame
‰ Nếu nghe thấy kênh bận, tạm trì hoãn việc truyền
‰ Tương tự con người: đừng ngắt lời tôi!
1-31
Đụng độ trong CSMA
Đụng độ có thể vẫn xảy
ra:
Sự lan truyền độ trễ nghĩa là
hai nút có thể không nghe thấy
nút khác truyền
Đụng độ:
toàn bộ thời gian gói tin 
truyền bị lãng phí
Bố trí không gian của các nút
Chú ý:
vai trò của khoảng cách và độ trễ
lan truyền trong việc xác định xác
suất đụng độ
1-32
CSMA/CD (Collision Detection)
CSMA/CD: nghe ngóng đường truyền, gọi ngắn
như CSMA
 đụng độ phát hiện trong thời gian ngắn
 truyền đụng độ bỏ qua, giảm sự lãng phí kênh
‰ Phát hiện đụng độ:
 Dễ trong mạng có dây LAN: đo độ mạnh của tín hiệu, 
so sánh tín hiệu nhận, truyền
 Khó trong mạng không dây LAN: bên nhận dừng
trong khi truyền
‰ Tương tự con người: người nói chuyện lịch sự
1-33
Phát hiện đụng độ trong CSMA/CD 
1-34
Giao thức MAC “Taking Turns”
Giao thức MAC kiểu chia kênh:
 Dùng chung kênh hiệu quả và công bằng khi tải
nặng
 không hiệu quả khi tải nhẹ: trễ khi truy cập kênh, 
1/N bandwidth được cấp thậm chí chỉ có một nút
kích hoạt
Giao thức MAC truy cập ngẫu nhiên
 Hiệu quả khi tải nhẹ: một nút có thể sử dụng toàn
bộ kênh
 Tải nặng: đụng độ cao
Các giao thức “taking turns”
tốt cho cả hai trường hợp!
1-35
Giao thức MAC “Taking Turns”
Thăm dò:
‰ Nút chủ mời nút tớ
truyền theo thứ tự
‰ Xem xét:
 overhead của thăm dò
 trễ
 một điểm lỗi (nút chủ)
Chuyển thẻ bài:
‰ Điều khiển thẻ bài chuyển từ
một nút tới nút tiếp theo thứ
tự.
‰ Bản tin thẻ bài
‰ Xem xét:
 Overhead của thẻ bài
 Độ trễ
 Một điểm lỗi (thẻ bài)
1-36
Tổng kết về giao thức MAC
‰Chúng ta làm gì với phương tiện dùng
chung?
 Chia kênh theo thời gian, tần số, mã
• Time Division, Frequency Division
 Chia ngẫu nhiêu (động)
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• Nghe ngóng đường truyền: dễ trong một số công nghê
(có dây), khó trong một số công nghệ (không dây)
• CSMA/CD sử dụng trong Ethernet
• CSMA/CA sử dụng trong 802.11
 Taking Turns
• Thăm dò từ trung tâm, chuyển thẻ bài
1-37
Các công nghệ LAN
Tầng liên kết dữ liệu:
 Các dịch vụ, phát hiện/sửa lỗi, đa truy cập
Tiếp theo: Các công nghệ LAN
 Đánh địa chỉ
 Ethernet
 Hub, switch
 PPP
1-38
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-39
Địa chỉ MAC và ARP
‰32 bít địa chỉ IP:
 Địa chỉ tầng mạng
 Sử dụng để chuyển datagram tới IP subnet đích
‰Địa chỉ MAC (hay LAN, vật lý, Ethernet) :
 Sử dụng để chuyển datagram từ một giao diện này
tới giao diện kết nối vật lý khác (cùng mạng)
 48 bít địa chỉ MAC (cho hầu hết các mạng LAN) 
ghi trong adapter ROM
1-40
Địa chỉ LAN và ARP
Một adapter trong LAN có địa chỉ LAN duy nhất
Địa chỉ quảng bá =
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
(có dây hoặc
không dây)
1-41
Địa chỉ MAC
‰ Việc cấp địa chỉ MAC được quản lý bởi IEEE
‰ Các nhà sản xuất mua phần không gian địa chỉ MAC 
(để đảm bảo sự duy nhất)
‰ Sự tương tự:
(a) Địa chỉ MAC: giống Social Security Number
(b) Địa chỉ IP: giống địa chỉ thư bưu điện
‰ Địa chỉ MAC phẳng ➜ linh hoạt
 Có thể di chuyển LAN card từ mạng LAN này tới mạng LAN 
khác
‰ Địa chỉ phân cấp IP không có tính di chuyển
 Phụ thuộc vào IP subnet mà nút nối vào
1-42
ARP: Address Resolution Protocol
‰ Mỗi nút IP (host, router) 
trên mạng LAN có bảng
ARP
‰ Bảng ARP: Ánh xạ địa
chỉ IP/MAC cho một số
nút trong mạng LAN
 TTL (Time To Live): thời
gian mà ánh xạ địa chỉ có
giá trị (thường là 20 phút)
Q: Làm thế nào để xác định
địa chỉ MAC của B khi biết
địa chỉ 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
1-43
Giao thức ARP
‰ A muốn gửi datagram tới B 
và địa chỉ MAC của B không
trong bảng ARP của A
‰ Quảng bá gói tin truy vấn
ARP, chứa địa chỉ IP của B
 Địa chỉ MAC đích = FF-
FF-FF-FF-FF-FF
 Mọi máy trong mạng LAN 
nhận được truy vấn ARP 
‰ B nhận gói tin ARP, trả lời A 
địa chỉ MAC của nó
 frame gửi tới địa chỉ MAC 
của A (unicast)
‰ A ghi lại cặp địa chỉ IP-to-
MAC trong bảng ARP tới khi
thông tin bị quá hạn
 Trạng thái mềm: thông
tin bị quá hạn (biến mất) 
trừ khi được làm mới
‰ ARP là “plug-and-play”:
 Các nút tạo bảng ARP 
của nó không có sự can 
thiệp từ quản trị mạng
1-44
Dẫn đường tới mạng LAN khác
Gửi datagram từ A tới B qua R
Giả sử A biết địa chỉ IP của B
‰ Hai bảng ARP trong router R, mỗi bảng cho một mạng LAN
‰ Trong bảng dẫn đường tại host nguồn, tìm router 
111.111.111.110
‰ Trong bảng ARP tại nguồn, tìm địa chỉ MAC E6-E9-00-17-BB-
4B,
A
R
B
1-45
‰ A tạo datagram có địa chỉ nguồn A, địa chỉ đích B
‰ A sử dụng ARP để biết địa chỉ MAC của R 111.111.111.110
‰ A tạo frame tầng liên kết dữ liệu, sử dụng địa chỉ MAC của R là
địa chỉ đích, frame chứa IP datagram A-to-B
‰ Adapter của A gửi frame
‰ Adapter của R nhận frame
‰ R lấy IP datagram từ Ethernet frame, thấy địa chỉ đích là tới B
‰ R sử dụng ARP để có địa chỉ MAC của B
‰ R tạo frame chứa IP datagram A-to-B gửi tới B
A
R
B
1-46
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-47
Ethernet
Công nghệ LAN có dây phổ biến: 
‰ Rẻ $20 với 100Mbs!
‰ Công nghệ LAN đầu tiên sử dụng rộng rãi
‰ Đơn giản, rẻ hơn token LAN và ATM
‰ Có sự cạnh tranh về tốc độ : 10 Mbps – 10 Gbps
Phác thảo Ethernet của
Metcalfe
1-48
Star topology
‰ Bus topology phổ biến vào giữa những năm 90
‰ Hiện nay, star topology phổ biến
‰ Sự lựa chọn kết nối: hub hay switch
hub or
switch
1-49
Cấu trúc của Ethernet Frame 
Adapter bên gửi đóng gói IP datagram (hoặc các gói tin 
tầng mạng khác) trong Ethernet frame
Preamble:
‰ 7 bytes with pattern 10101010 theo sau là 1 byte với
with pattern 10101011
‰ Sử dụng để đồng bộ tốc độ bên nhận, bên gửi
1-50
Cấu trúc của Ethernet Frame 
‰ Address: 6 byte
 Nếu adapter nhận frame có địa chỉ đích tương ứng hoặc với
địa chỉ quảng bá (ví dụ: gói tin ARP), nó chuyển dữ liệu
trong frame tới giao thức tầng mạng
 Trường hợp khác, adapter loại bỏ frame
‰ Type: chỉ ra giao thức của tầng phía trên (hầu hết là
IP nhưng cũng có thể là Novell IPX hay AppleTalk)
‰ CRC: được kiểm tra tại bên nhận, nếu phát hiện ra
lỗi thì frame bị loại bỏ
1-51
Dịch vụ không hướng kết nối, không tin cậy
‰ Không hướng kết nối: Không bắt tay giữa adapter 
bên gửi và adapter bên nhận
‰ Không tin cậy: adapter bên nhận không gửi ack hoặc
nack cho adapter bên gửi
 Luồng datagram chuyển tới tầng mạng có thể khe hở
 Các khe hở sẽ được điền đầy nếu ứng dụng sử dụng TCP
 Ngược lại, ứng dụng sẽ thấy các khe hở
1-52
Ethernet sử dụng CSMA/CD
‰ Không slot
‰ Adapter không truyền nếu
nó nghe thấy một số
adapter đang truyền, gọi là
nghe ngóng đường truyền
(carrier sense)
‰ Adapter bỏ qua truyền khi
nó nghe thấy adapter khác
đang truyền, gọi là phát
hiện đụng độ (collision 
detection)
‰ Trước khi cố gắng
truyền lại, adapter đợi
một thời gian ngẫu
nhiên, gọi là truy cập
ngẫu nhiên (random 
access)
1-53
Thuật toán Ethernet CSMA/CD
1. Adaptor nhận datagram từ
tầng mạng và tạo frame
2. Nếu adapter nghe ngóng
thấy kênh rỗi, nó bắt đầu
truyền frame. Nếu nó nghe
ngóng thấy kênh bận, đợi
tới khi kênh rỗi và truyền
3. Nếu adapter truyền toàn bộ
frame không phát hiện thấy
việc truyền khác, adapter 
đã xong với frame !
4. Nếu adapter phát hiện việc
truyền khác trong khi
truyền, bỏ qua và gửi tín
hiệu jam
5. Sau khi bỏ qua, adapter 
vào exponential backoff: 
sau đụng độ thứ m, adapter 
chọn K ngẫu nhiên từ
{0,1,2,,2m-1}. Adapter đợi
K·512 bít thời gian và quay 
lại bước 2
1-54
Ethernet CSMA/CD
Jam Signal: đảm bảo chắc
chắn mọi bộ phát biết
về đụng độ; 48 bít
Bit time: .1 microsec cho
10 Mbps Ethernet;
với K=1023, thời gian
đợi là khoảng 50 msec
Exponential Backoff:
‰ Mục đích: thích nghi
việc thử truyền lại, ước
lượng tải hiện tại
 tải nặng: đợi ngẫu nhiên
sẽ lâu hơn
‰ Đụng độ đầu tiên: chọn
K từ {0,1}; độ trễ là K·
512 bít thời gian truyền
‰ Sau đụng độ thứ hai: 
chọn K từ {0,1,2,3}
‰ Sau 10 đụng độ, chọn K 
từ {0,1,2,3,4,,1023}
1-55
Hiệu suất của CSMA/CD
‰ Tprop = xác suất lớn nhất giữa 2 nút trong LAN
‰ ttrans = thời gian để truyền frame có kích thước lớn
nhất
‰ Hiệu suất tới 1 khi tprop tiến tới 0
‰ Tới 1 khi ttrans tiến tới vô hạn
‰ Tốt hơn nhiều ALOHA, nhưng vẫn không tập chung, 
đơn giản và rẻ
transprop tt /51
1efficiency +=
1-56
10BaseT và 100BaseT
‰ Tốc độ 10/100 Mbps; 100 Mbps gọi là “fast ethernet”
‰ T viết tắt của Twisted Pair
‰ Các nút kết nối tới hub: “star topology”; khoảng cách
giữa nút và hub tối đa 100m
twisted pair
hub
1-57
Hub
Hub là thiết bị lặp của tầng vật lý:
 Các bít đến từ một liên kết sẽ ra mọi liên kết khác
 Với cùng tốc độ
 Không có vùng đệm frame
 Không có CSMA/CD tại hub: adapter phát hiện
đụng độ
 Cung cấp chức năng quản trị mạng
twisted pair
hub
1-58
Mã Manchester
‰ Sử dụng 10BaseT
‰ Mỗi bít có một transition
‰ Cho phép đồng hồ trong nút gửi và nhận để đồng bộ
tại nút kia
 Không cần có trung tâm, đồng hồ chung giữa các nút!
‰ Xét ở tầng vật lý!
1-59
Gbit Ethernet
‰ Sử dụng định dạng Ethernet frame chuẩn
‰ Cho phép liên kết point-to-point và kênh quảng bá
dùng chung
‰ Trong chế độ dùng chung, sử dụng CSMA/CD; giữa
các nút đòi hỏi khoảng cách ngắn để có hiệu quả
‰ Sử dụng hub, gọi là “Buffered Distributors”
‰ Full-Duplex tại 1 Gbps cho liên kết point-to-point
‰ Hiện tại, 10 Gbps!
1-60
Tầng liên kết dữ liệu
‰ 5.1 Giới thiệu và các
dịch vụ
‰ 5.2 Phát hiện và sửa lỗi
‰ 5.3 Các giao thức đa
truy cập
‰ 5.4 Đánh địa chỉ tầng
liên kết dữ liệu
‰ 5.5 Ethernet
‰ 5.6 Hub và switch
1-61
Kết nối với hub
‰ Backbone hub kết nối các LAN segments
‰ Mở rộng khoảng cách tối đa giữa các nút
‰ Nhưng các vùng đụng độ của riêng segment trở thành
vùng đụng độ lớn
‰ Không thể kết nối 10BaseT và 100BaseT
hub hub hub
hub
1-62
Switch
‰ Thiết bị thực hiện tầng liên kết dữ liệu
 Lưu và chuyển tiếp Ethernet frames
 Kiểm tra frame header và chọn chuyển tiếp frame 
dựa trên địa chỉ đích MAC
 Khi frame được chuyển tiếp trên segment, sử
dụng CSMA/CD để truy cập segment
‰ Trong suốt
 Host không biết về sự tồn tại của switch
‰ plug-and-play, tự học
 Switch không cần phải cấu hình
1-63
Chuyển tiếp
• Cách xác định chuyển tiếp frame đến LAN segment 
nào?
• Giống bài toán dẫn đường...
hub hub
hub
switch
1
2 3
1-64
Tự học
‰ Switch có bảng switch
‰ Entry trong bảng switch: 
 (MAC Address, Interface, Time Stamp)
 Các entry cũ trong bảng sẽ bị xóa đi (TTL có thể 60 
phút)
‰ Switch học host nào có thể tới qua interface nào
 Khi nhận frame, switch học vị trí của địa chỉ gửi: 
incomming LAN segment
Ghi cặp địa chỉ gửi/vị trí trong bảng switch
1-65
Lọc/Chuyển tiếp
Khi switch nhận một frame:
Chỉ số bảng switch sử dụng địa chỉ MAC đích
if thấy entry cho đích
then{
if đích trong segment mà frame đến
then Loại bỏ frame
else Chuyển tiếp frame trên interface chỉ định
}
else Làm tràn
Chuyển tiếp trên tất cả interface trừ
interface mà frame đã tới
1-66
Ví dụ Switch
Giả sử C gửi frame tới D
‰ Switch nhận frame từ C
 Ghi vào bảng switch là C trên interface 1
 Bởi vì D không trong bảng, switch chuyển tiếp frame qua 
interface 2 và 3
‰ frame được nhận bởi D 
hub hub hub
switch
B C
D G H
A
E
F
I
address interface
A
B
E
G
1
1
2
3
1
2 3
1-67
Ví dụ Switch
Giả sử D gửi frame trả lời C 
‰ Switch nhận frame từ D
 Ghi vào bảng switch là D ở trên interface 2
 Bởi vì C có trong bảng, switch chuyển tiếp frame chỉ tới
interface 1
‰ frame được nhận bởi C 
hub hub hub
switch
B C
D G H
A
E
F
I
address interface
A
B
E
G
C
1
1
2
3
1
1-68
Switch: cô lập lưu lượng
‰ Cài đặt switch chia subnet thành các LAN segment
‰ Switch lọc gói tin:
 Frame cùng LAN-segment thường không chuyển
tiếp trên LAN segment khác
 Segment được phân tách các vùng đụng độ
hub hub hub
switch
vùng đụng độ vùng đụng độ
vùng đụng độ
1-69
Switch: truy cập dành riêng
‰ Switch có nhiều interface
‰ Các host có kết nối trực tiếp
tới switch
‰ Không đụng độ; full duplex
Switching: A-to-A’ và B-to-B’
đồng thời, không đụng độ
switch
A
A’
B
C
C’
B’
1-70
Một số thông tin khác về Switch
‰ cut-through switching: frame chuyển tiếp từ
input port tới output port không chờ nhận đủ
frame
Giảm một chút về độ trễ (latency)
‰ Sự kết của dùng chung/dành riêng, 
10/100/1000 Mbps interface
1-71
Mạng của một tổ chức
hub hub
hub
switch
Ra mạng bên ngoài
router
IP subnet
mail server
web server
1-72
So sánh Switch và Router
‰ Các thiết bị store-and-forward
 router: Thiết bị tầng mạng (kiểm tra header của tầng mạng)
 switch: Thiết bị tầng liên kết dữ liệu
‰ Routers duy trì bảng dẫn đường, thực hiện thuật toán
dẫn đường
‰ Switch duy trì bảng switch, thực hiện thuật toán lọc, 
học
1-73
Chương 5: Tổng kết
‰ Các nguyên tắc bên trong của các dịch vụ tầng liên
kết dữ liệu:
 Phát hiện và sửa lỗi
 Dùng chung một kênh quảng bá: đa truy cập
 Đánh địa chỉ tầng liên kết dữ liệu
‰ Ví dụ và thực hiện của các công nghệ tầng liên kết dữ
liệu khác nhau
 Ethernet
 Switched LANS