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

Chương 03

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

MẠNG MÁY TÍNH

Tháng 09/2011

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

3

Giới thiệu - 1

application

transport

network

transport

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

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

nhau

network

data link

physical

data link

network

data link

physical

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

application

transport

network

. Mỗi link có thể dùng

giao thức khác nhau

để truyền tải frame

data link

physical

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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)

Transport

Network

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

Logical Link Control

Data link

Physical

Media Access Control

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

EDC= Error Detection and Correction

D = Data

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

8

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)

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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)

0111000110101011

1

(mô hình lẻ)

0

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

101011 111100 011101 001010

Không có lỗi

Có lỗi

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

18

Hamming code – 3

Ví dụ:

. M = 7

. Dùng parity lẻ

. Thông tin cần^Tg^hôởⁿi^g:^ti1ⁿ0^cầ1ⁿ1^gửi:

1 0 1 1

1 2 3 4 5 6 7

Vị trí

2⁰2¹

2²

Tính check bits:

3 =

5 = 2²

2¹+ 2⁰= 0 1 1

+ 2⁰= 1 0 1

6 = 2²+ 2¹+ = 1 1 0

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

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

19

Hamming code - 4

Thông tin cần gửi:

1 0 1 1

1

0 1 1

1

Vị trí

1 2 3 4 5 6 7

2⁰2¹

2 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 =

5 = 2²

6 = 2²+ 2¹+ = 1 1 0

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

2¹+ 2⁰= 0 1 1

+ 2⁰= 1 0 1

Khoa Công nghệ thông tin - Đại học Khoa học tự nhiên TP Hồ Chí Minh

20