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

Tầng Liên kết dữ liệu

MỤC TIÊU

 điều khiển truy cập đường truyền

 Điều khiển liên kết

Application

Presentation

Session

Transport

Network

Data link

Physical

2

NỘI DUNG

 Giới thiệu

 Kỹ thuật phát hiện và sửa lỗi

 Điều khiển truy cập đường truyền

 ARP

 Ethernet

3

GIỚI THIỆU - 1

 Link: “kết nối/liên

kết”giữa các nodes kề

nhau

application

transport

network

data link

physical

data link

network

data link

physical

 Wired

network

data link

physical

 Wireless

network

data link

physical

 Data link layer: chuyển

gói tin (frame) từ một

node đến node kề qua 1

link

network

data link

physical

application

 Mỗi link có thể dùng giao

thức khác nhau để

truyền tải frame

transport

network

data link

physical

4

GIỚI THIỆU - 2

 Tại nơi gởi:

 Nhận các packet từ tầng network  đóng gói thành các

frame

 Truy cập đường truyền (nếu dùng đường truyền chung)

 Tại nơi nhận:

 Nhận các frame dữ liệu từ tầng physical

 Kiểm tra lỗi

 Chuyển cho tầng network

5

GIỚI THIỆU - 3

 LLC (Logical Link Control)

 Điều khiển luồng

 Kiểm tra lỗi

Application

Presentation

Session

 Báo nhận

 MAC (Media Access Control)

 Truy cập đường truyền

Transport

Network

Logical Link Control

Data link

Physical

Media Access Control

6

NỘI DUNG

 Giới thiệu

 Kỹ thuật phát hiện và sửa lỗi

 Điều khiển truy cập đường truyền

 ARP

 Ethernet

7

KỸ THUẬT PHÁT HIỆN VÀ SỬA LỖI - 1

Datagram

N

D có lỗi?

Y

Detected Error

D

EDC

D’

EDC’

Link

8

EDC= Error Detection and Correction

D = Data

KỸ THUẬT PHÁT HIỆN VÀ SỬA LỖI - 2

 Các phương pháp:

 Parity Check (bit chẵn lẻ)

 Checksum

 Cylic Redundancy Check (CRC)

9

PARITY CHECK

 Dùng thêm một số bit để đánh dấu tính chẵn lẻ

 Dựa trên số bit 1 trong dữ liệu

 Phân loại:

 Even Parity: số bit 1 phải là một số chẵn

 Odd Parity: số bit 1 phải là một số lẻ

 Các phương pháp:

 Parity 1 chiều

 Parity 2 chiều

 Hamming code

10

PARITY 1 CHIỀU - 1

 Số bit parity: 1 bit

 Chiều dài của dữ liệu cần gởi đi: d bit

 DL gởi đi sẽ có (d+1) bit

 Bên gởi:

 Thêm 1 bit parity vào dữ liệu cần gởi đi

 Mô hình chẵn (Even parity)

 số bit 1 trong d+1 bit là một số chẵn

 Mô hình lẻ (Odd Parity)

 số bit 1 trong d+1 bit là một số lẻ

d bits Parity bit

(mô hình chẵn)

(mô hình lẻ)

0111000110101011

1

0

11

PARITY 1 CHIỀU - 2

 Bên nhận:

 Nhận D’ có (d+1) bits

 Đếm số bit 1 trong (d+1) bits = x

 Mô hình chẵn: nếu x lẻ  error

 Mô hình lẻ: nếu x chẵn  error

 Ví dụ: nhận 0111000110101011

 Parity chẵn: sai

 Parity lẻ: đúng

 Dữ liệu thật: 011100011010101

 Đặc điểm:

 Phát hiện được lỗi khi số bit lỗi trong dữ liệu là số lẻ

 Không sửa được lỗi

12

PARITY 2 CHIỀU - 1

 Dữ liệu gởi đi được biểu diễn thành ma trận NxM

 Số bit parity: (N + M + 1) bit

 Đặc điểm:

 Phát biện và sửa được 1 bit lỗi

 Bên gởi

 Biểu diễn dữ liệu cần gởi đi thành ma trận NxM

 Tính giá trị bit parity của từng dòng, từng cột

13

PARITY 2 CHIỀU - 2

 Ví dụ:

 Dùng parity chẵn

 N = 3, M = 5

 Dữ liệu cần gởi đi: 10101 11110 01110

14

PARITY 2 CHIỀU - 1

 Bên nhận:

 Biễu diễn dữ liệu nhận thành ma trận (N+1)x(M+1)

 Kiểm tra tính đúng đắn của từng dòng/cột

 Đánh dấu các dòng/cột dữ liệu bị lỗi

 Bit lỗi: bit tại vị trí giao giữa dòng và cột bị lỗi

15

PARITY 2 CHIỀU - 2

 Ví dụ:

 Dùng parity chẵn

 N = 3, M = 5

Dữ liệu nhận:

101011 101100 011101 001010

Dữ liệu nhận:

101011 111100 011101 001010

Không có lỗi

Có lỗi

Dữ liệu thật: 10101 11110 01110

16

HAMMING CODE - 1

 Mỗi hamming code

 có M bit, đánh số từ 1 đến M

 Bit parity: log₂M bits, tại các vị trí lũy thừa của 2

 Dữ liệu thật được đặt tại các vị trí không là lũy thừa của 2

 VD: M = 7

 log₂7 = 3: dùng 3 bits làm bit parity (1, 2, 4)

 Có 4 vị trí có thể đặt dữ liệu (3, 5, 6, 7)

 Đặc điểm:

 sửa lỗi 1 bit

 nhận dạng được 2 bit lỗi

 Sửa lỗi nhanh hơn Parity code 2 chiều

17

HAMMING CODE - 2

 Bên gởi:

 Chia dữ liệu cần gởi đi thành các khối dữ liệu (với số bit là

số vị trí có thể đặt vào Hamming Code)

 Với mỗi khối dữ liệu  tạo 1 Hamming Code

 Đặt các bit dữ liệu vào các vị trí không phải là lũy thừa của 2 trong

Hamming Code

 lưu ý: vị trí được đánh số từ 1 đến M

 Tính check bits

 Tính giá trị của các bit parity

18

HAMMING CODE – 3

 Ví dụ:

 M = 7

 Dùng parity lẻ

 Thông tin cần gởi: 1011

1 0 1 1

Thông tin cần gửi:

1

0

1

2

3

4

5

6

7

Vị trí

2⁰2¹

2²

Tính check bits:

3 =

2¹+ 2⁰= 0 1 1

+ 2⁰= 1 0 1

5 = 2²

6 = 2²+ 2¹+

= 1 1 0

7 = 2²+ 2¹+ 2⁰= 1 1 1

19

HAMMING CODE - 4

1 0 1 1

Thông tin cần gửi:

1

3

0

5

1

6

1

7

2

4

Vị trí

2⁰2¹

2²

Vị trí 2⁰:

• Xét cột 2⁰trong check bit 

Check bits:

các vị trí có bit 1

• Lấy các bit DL tại các vị trí

có bit 1 trong check bit 

tính bit parity cho các bit dữ

liệu này

3 =

2¹+ 2⁰= 0 1 1

+ 2⁰= 1 0 1

5 = 2²

6 = 2²+ 2¹+

= 1 1 0

7 = 2²+ 2¹+ 2⁰= 1 1 1

20