Bài giảng Mạng máy tính - Chương 3: Tầng liên kết dữ liệu - Bùi Trọng Tùng
CHƯƠNG 3.
TẦNG LIÊN KẾT DỮ LIỆU
1
1
Nội dung
1. Tổng quát về tầng liên kết dữ liệu
2. Điều khiển truy nhập đường truyền
3. Chuyển tiếp dữ liệu
4. Mạng cục bộ (LAN)
5. Mạng diện rộng (WAN)
2
2
1
1. TỔNG QUAN
3
3
Tầng liên kết dữ liệu trên mô hình TCP/IP
Application
Transport
Logic Link Control sublayer
•
•
Kiểm soát luồng
Dồn kênh, phân kênh các giao thức
Network
Media Access Control sublayer
•
•
•
•
Đóng gói dữ liệu
Định địa chỉ vật lý
Phát hiện và sửa lỗi
Điều khiển truy nhập đường truyền
Data-link
Physical
802.3
Ethernet
802.4
Token Bus
802.5
Token Ring
802.11
WiFi
…
802.16
WiMax
4
4
2
Các chức năng chính
• Đóng gói:
• Đơn vị dữ liệu: khung tin (frame)
• Bên gửi: thêm header, trailer cho gói tin nhận được từ tầng mạng
• Bên nhận: bỏ header và trailer, đẩy lên tầng mạng
• Địa chỉ hóa: sử dụng địa chỉ MAC
• Điều khiển truy nhập đường truyền: nếu mạng đa truy
nhập, cần có giao thức điều khiển đa truy nhập
• Kiểm soát luồng: đảm bảo bên nhận không bị quá tải
• Kiểm soát lỗi: phát hiện và sửa lỗi bit trong các khung tin
• Chế độ truyền: simplex, half-duplex, full-duplex
5
5
Định địa chỉ
• Địa chỉ MAC: 48 bit, được quản lý bởi IEEE
• Mỗi cổng mạng được gán một MAC
• Không thể thay đổi địa chỉ vật lý
• Không phân cấp, có tính di động
• Không cần thay đổi địa chỉ MAC khi host chuyển sang
mạng khác
• Địa chỉ quảng bá trong mạng LAN:
FF-FF-FF-FF-FF-FF
6
6
3
Kiểm soát lỗi
Data’
N
Data
Phát
Y
hiện lỗi bit
Báo lỗi
Tính EDC
H
Data
EDC
H
Data’
EDC’
Kênh truyền có lỗi bit
EDC: Error Dectection Code
•
•
•
Mã parity
Mã checksum
Mã vòng CRC (được sử dụng chủ yếu trong các giao thức trên tầng liên
kết dữ liệu)
7
7
Mã Checksum
• Phát hiện lỗi bit trong các đoạn tin/gói tin
• Gửi:(nguyên lý chung)
• Chia dữ liệu thành các phần có kích thước n bit
• Tính tổng các phần. Nếu kết quả tràn quá n bit, cộng các bit tràn
vào phần kết quả
• Đảo bit kết quả cuối cùng được checksum
• Truyền checksum kèm theo dữ liệu
• Nhận:
• Tách dữ liệu và checksum
• Chia dữ liệu thành các phần có kích thước n bit
• Tính tổng các phần và checksum. Nếu kết quả tràn quá n bit, cộng
các bit tràn vào phần kết quả
• Nếu kết quả cuối xuất hiện bit 0 dữ liệu bị lỗi
8
8
4
Mã vòng CRC (Cyclic Redundanc Check)
•
Phía gửi
•
•
•
•
•
Chọn 1 đa thức sinh bậc k
Biểu diễn đa thức dưới dạng chuỗi bit P
Thêm k bit 0 vào frame dữ liệu F được Fk
Chia Fk cho P, lấy phần dư R
Ghép phần dư vào chuỗi dữ liệu được FR
•
Phía nhận : lấy FR chia cho P
•
•
Nếu chia hết truyền đúng
Nếu chia có dư, căn cứ vào số dư (syndrom) để phát
hiện và sửa lỗi (nếu được)
9
9
Mã CRC – Ví dụ
Frame : 1101011011
Generator : G(x) = x4 + x + 1 P = 10011
Dividend : Fk = 11010110110000
R = Fk mod P = 1110
Send : 11010110111110
10
10
5
Triển khai trên hệ thống mạng
application
transport
network
data link
• Điều khiển truyền dữ liệu trên
liên kết vật lý giữa 2 nút mạng
kế tiếp
physical
• Triển khai trên mọi nút mạng
network
data link
physical
network
data link
physical
network
data link
physical
• Các thức triển khai và cung cấp
dịch vụ phụ thuộc vào đường
truyền(WiFi, Wimax, 3G, cáp
quang, cáp đồng...)
network
data link
physical
network
data link
physical
network
network
data link
physical
data link
physical
network
data link
physical
• Truyền thông tin cậy (cơ chế
giống TCP nhưng đơn giản hơn)
hoặc không
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
• Đơn vị truyền: frame (khung tin)
11
11
Triển khai trên các nút mạng
• Tầng liên kết dữ liệu được
đặt trên cạc mạng (NIC-
Network Interface Card)
appication
hoặc trên chip tích hợp
• Cùng với tầng vật lý
cpu
memory
• NIC được kết nối với hệ
thống bus
host
bus
(e.g., PCI)
controller
physical
•
transmission
network adapter
card
12
12
6
2. ĐIỀU KHIỂN TRUY NHẬP
ĐƯỜNG TRUYỀN
13
13
2. Điều khiển truy nhập đường truyền
• Các dạng liên kết
• Điểm-điểm(point-to-point): ADSL, Telephone modem,
Leased line…
• Điểm-đa điểm (point-to-multipoint):
• Mạng LAN có dạng bus, mạng LAN hình sao dùng hub
• Mạng không dây
• Cần giao thức điều khiển truy nhập để tránh xung đột
shared RF
(e.g., 802.11 WiFi)
shared wire (e.g.,
cabled Ethernet)
shared RF
(satellite)
humans at a
cocktail party
(shared air, acoustical)
14
14
7
Phân loại các giao thức đa truy nhập
• Phân hoạch tài nguyên sử dụng kỹ thuật 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
• 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….
15
15
2.1. Các phương pháp chia kênh
• FDMA: frequency division multiple access
• TDMA: time division multiple access
• CDMA: code division multiple access
16
16
8
Ví dụ:
4 máy
TDMAvà FDMA
FDMA
frequency
time
TDMA:
frequency
time
17
17
CDMA
18
18
9
2.2. Các phương pháp điều khiển truy
nhập ngẫu nhiên
• Aloha
• Frame-time: thời gian để truyền hết một frame có kích thước lớn
nhất
• Khi một nút mạng cần truyền dữ liệu:
• Frame đầu tiên: truyền ngay. Nếu có đụng độ thì truyền lại với xác suất p
• Các frame sau: truyền với xác suất là p
• Trong 1 frame-time chỉ được truyền 1 frame
• Xác suất truyền thành công là ~18.4%
19
19
Slotted Aloha
• Hoạt động như Aloha với các yêu cầu:
• Frame-time là như nhau với mọi nút
• Tất cả các nút phải đồng bộ về thời gian
• Xác suất truyền thành công: 36.8%
20
20
10
Điều khiển truy nhập đường truyền cảm nhận
sóng mang
• CSMA:Carrier Sense Multiple Access
with Collision Detection
• Cảm nhận sóng mang để quyết định
đường truyền có bận hay không?
• Nghe trước khi nói
• Đụng độ xảy ra do trễ trên đường truyền
• CSMA/CD: Carrier Sense Multiple Access with Collision
Detection
• Phát hiện đụng độ : nghe trong khi nói
• Giải quyết đụng độ với backoff
21
21
spatial layout of nodes
Đụng độ 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ụ:
22
22
11
CSMA/CD
1: Yêu cầu truyền dữ liệu
2: Đường truyền bận ?
3: Tổ chức data thành Frame
4: Truyền Frame
5: Có đụng độ ?
6: Tiếp tục truyền
7: Hết dữ liệu cần truyền ?
8: Kết thúc
9: Truyền tín hiệu JAM
10: Inc(attemps)
11: attemps > Max Attemps
12: Error !!!
13: Tính toán khoảng thời gian backoff = t
14: Delay(t)
23
23
So sánh chia kênh và truy nhập ngẫu
nhiên
• Phân hoạch tài nguyên
• 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
24
24
12
2.3. Token passing
•Bit trạng thái : rỗi hay bận
•Nút mạng nhận được thẻ bài rỗi, không mang dữ liệu :
được phép truyền dữ liệu
Thiết lập trạng thái thẻ bài về trạng thái bận
Tổ chức dữ liệu để truyền, thẻ bài trở thành tiêu đề của frame
Sau khi truyền xong dữ liệu : thiết lập trạng thái thẻ bài là rỗi
•Nút đích : sao chép dữ liệu trên frame và trả lại frame
cho nút nguồn
•Token Ring : vòng luân chuyển thẻ bài là vòng vật lý
•Token Bus : vòng luân chuyển thẻ bài là vòng logic
•Hạn chế
25
25
Khuôn dạng thẻ bài và gói tin
SD
AC
ED
• Thẻ bài trống
• Starting Delimiter (8bit): bắt đầu frame
• Access Control (8bit): điều khiển
• Mức ưu tiên (3 bit): xác lập quyền ưu tiên sử dụng thẻ bài
• Trạng thái thẻ bài (1 bit)
• Giám sát (1bit)
• ED (8 bit): kết thúc frame
• Frame dữ liệu:
Địa chỉ Địa chỉ
Dữ liệu
SD
AC
FC
CRC
ED
FS
đích
nguồn
• FC(8 bit): kiểu frame dữ liệu mang theo trong thẻ bài
• FS (8bit): báo nhận
26
26
13
3. CHUYỂN TIẾP DỮ LIỆU
27
27
Chuyển tiếp dữ liệu trong mạng
• Bảng MAC Table
• Địa chỉ MAC của host
• Cổng kết nối với host
• TTL: thời gian giữ lại thông
tin trong bảng
• Cơ chế tự học
• Chuyển mạch
MAC Addr. Interface TTL
• Quảng bá : địa chỉ MAC
là FF:FF:FF:FF:FF:FF
28
28
14
Source: A
Dest: A’
Switch: Cơ chế tự học
A
4
A A’
• Cập nhật địa chỉ MAC
nguồn và cổng nhận gói
B
C’
1
tin nếuvào bảng MAC
Table:
• Địa chỉ nguồn chưa có trong
2
6
5
3
bảng MAC Table, hoặc
B’
C
• Địa chỉ nguồn đã có nhưng
nhận được gói tin trên cổng
khác
A’
MAC addr interface TTL
MAC Table
(ban đầu rỗng)
60
A
1
29
29
Switch: Cơ chế chuyển tiếp
Khi nhận được 1 frame
1. Tìm đ/c cổng vào (tự học)
2. Tìm địa chỉ cổng ra dùng bảng chuyển tiếp
3. if tìm thấy cổng ra
then {
if cổng ra == cổng vào
then hủy bỏ frame
else chuyển tiếp frame đến cổng ra
}
else quảng bá frame
30
30
15
Source: A
Dest: A’
Ví dụ
A
4
A A’
B
C’
• Không có cổng ra:
Quảng bá
1
2
6
A A’
• Đã biết địa chỉ A:
5
3
Chuyển trực tiếp
B’
C
A’ A
A’
MAC addr interface TTL
MAC Table
(ban đầu rỗng)
60
60
A
A’
1
4
31
31
Nối các switch với nhau
• Các switch có thể được nối với nhau
S4
S1
S3
S2
A
F
I
D
C
B
H
G
E
Cũng dùng cơ chế tự học
32
32
16
Các chế độ chuyển mạch
• Store and forward: nhận đầy đủ frame, kiểm tra lỗi và
chuyển mạch theo địa chỉ MAC đích
• Cut and through: chuyển frame ngay lập tức sau khi đã
xác định được cổng.
• Fragment free: kiểm tra 64 byte đầu tiên
• Frame tin bị lỗi do đụng độ có kích thước < 64 byte
• Adaptive: tự động lựa chọn 1 trong 3 chế độ trên
33
33
4. MẠNG CỤC BỘ (LAN)
34
34
17
4.1. Các thiết bị kết nối trong mạng LAN
• Repeater (bộ lặp), Hub(bộ chia)
• Đảm nhiệm chức năng tầng 1
• Tăng cường tín hiệu mở rộng phạm vi kết nối
• <=4 repeater / 1 đoạn mạng
• Bridge (Cầu), Switch (Bộ chuyển mạch)
• Đảm nhiệm chức năng tầng 1 và 2
• Cho phép kết nối các loại đường truyền vật lý khác nhau
• Chia nhỏ miền đụng độ
• Chuyển mạch cho khung tin dựa trên địa chỉ MAC
• Router (Bộ định tuyến)
35
35
Router vs Switch
application
transport
network
link
physical
• Xử lý gói tin: lưu và
datagram
frame
chuyển tiếp (store-and-
forward)
• Router: thiết bị tầng mạng
link
frame
physical
• Switch: thiêt bị tầng liên kết
dữ liệu
switch
• Chuyển tiếp gói tin:
network
link
physical
datagram
• Router: sử dụng thuật toán
định tuyến tính toán bảng
chuyển tiếp (Forwarding
Table), chuyển tiếp theo địa
chỉ IP đích
• Switch: sử dụng cơ chế tự
học tính toán bảng MAC
Table, chuyển tiếp theo địa
chỉ MAC đích
frame
application
transport
network
link
physical
36
36
18
4.2. Các hình trạng cơ bản của LAN
• Tất cả các nút mạng sử dụng
chung đường truyền – trục
(backbone)
• Mỗi nút mạng kết nối vào trục
bằng đầu nối chữ T
• Phương thức truyền : điểm – đa
điểm(point-to-multipoint)
• Dữ liệu truyền theo 2 hướng
• Nút nhận : kiểm tra địa chỉ
đích của dữ liệu
• Terminator
• Ưu điểm
• Nhược điểm
37
37
4.2. Các hình trạng cơ bản của LAN
Hình sao
• Một nút mạng đóng vai trò thiết
bị trung tâm
• Hub
• Switch
• Router
• Các nút mạng khác kết nối trực
tiếp với thiết bị trung tâm
• Phương thức truyền
• Điểm – điểm: switch, router
• Điểm – đa điểm: hub
• Ưu điểm
• Nhược điểm
38
38
19
4.2. Các hình trạng cơ bản của LAN
repeater
Hình vòng
• Các nút mạng chung đường truyền
khép kín
• Phương thức truyền : điểm – điểm
(point-to-point) hoặc điểm-đa điểm
• Dự phòng
điểm – đa điểm
• Ưu điểm
• Nhược điểm
điểm – điểm
39
39
4.3. Chuẩn Ethernet IEEE802.3
• Data-link & Physical Layers
• Điều khiển truy nhập: CSMA/CD
• Có nhiều chuẩn Ethernet khác nhau
• Cùng giao thức điều khiển truy nhập và cấu trúc Frame
• Hướng không liên kết, không báo nhận-phát lại
• 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.
40
40
20
Tải về để xem bản đầy đủ
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính - Chương 3: Tầng liên kết dữ liệu - Bùi Trọng Tùng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_may_tinh_chuong_3_tang_lien_ket_du_lieu_bui_t.pdf