Bài giảng Mạng máy tính - Chương 3: Tầng liên kết dữ liệu

CHƯƠNG 3.

TẦNG LIÊN KẾT DỮ LIỆU

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

1

1. TỔNG QUAN

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

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

Đị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

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

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

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

Mã CRC – Ví dụ

Frame : 1101011011

Generator : G(x) = x⁴+ x + 1  P = 10011

Dividend : Fk = 11010110110000

R = Fk mod P = 1110

Send : 11010110111110

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

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

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)

application

hoặc trên chip tích hợp

transport

• Cùng với tầng vật lý

cpu

memory

network

link

• NIC được kết nối với hệ

thống bus

host

bus

(e.g., PCI)

controller

physical

link

physical

•

transmission

network adapter

card

12

6

2. ĐIỀU KHIỂN TRUY NHẬP

ĐƯỜNG TRUYỀN

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

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

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

8

Ví dụ:

4 máy

TDMAvà FDMA

FDMA

frequency

time

TDMA:

frequency

time

17

CDMA

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

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

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

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

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

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

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

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

13

3. CHUYỂN TIẾP DỮ LIỆU

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

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

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

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

A

A’

1

4

31

Nối các switch với nhau

• Các switch có thể được nối với nhau

S₄

S₁

S₃

S₂

A

F

I

D

C

B

H

G

E

^Cũng dùng cơ chế tự học

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

4. MẠNG CỤC BỘ (LAN)

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

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

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

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

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

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

20

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