Bài giảng Computer networking - Chương 5: Tầng liên kết dữ liệu (Data Link layer)

Chapter 5

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

(Data Link layer)

A note on the use of these ppt slides:

Computer

We’re making these slides freely available to all (faculty, students, readers).

They’re in PowerPoint form so you see the animations; and can add, modify,

and delete slides (including this one) and slide content to suit your needs.

They obviously represent a lot of work on our part. In return for use, we only

ask the following:

Networking:ATop

Down Approach

❖ If you use these slides (e.g., in a class) that you mention their source

(after all, we’d like people to use our book!)

6^thedition

Jim Kurose, Keith Ross

Addison-Wesley

March 2012

❖ If you post any slides on a www site, that you note that they are adapted

from (or perhaps identical to) our slides, and note our copyright of this

material.

Thanks and enjoy! JFK/KWR

Tầng Link 5-1

Các dịch vụ tầng Liên kết dữ liệu (tt)

❖ Điều khiển luồng (flow control):

▪ Điều khiển tốc độ truyền giữa các node gửi và nhận liền kề

nhau

❖ Phát hiện lỗi (error detection):

▪ Lỗi gây ra bởi suy giảm tín hiệu, nhiễu.

▪ Bên nhận phát hiện sự xuất hiện lỗi:

• Thông báo bên gửi truyền lại hoặc bỏ frame đó

❖ Sửa lỗi (error correction):

▪ Bên nhận xác định và sửa các bit lỗi mà không cần phải

truyền lại

❖ half-duplex và full-duplex

▪ Các node tại các đầu cuối của mỗi kết nối đều có thể truyền

và nhận, nhưng với half duplex thì thao tác này không được

thực hiện đồng thời

Tầng Link 5-2

Tầng Liên kết dữ liệu và mạng LAN

5.1 Giới thiệu và các 5.5 link virtualization:

dịch vụ

MPLS

5.2 phát hiện lỗi và sửa 5.6 mạng trung tâm dữ

lỗi liệu

5.3 các giao thức đa 5.7 Hoạt động thường

truy cập

ngày - truy cập web

5.4 mạng LAN

▪ Định địa chỉ, ARP

▪ Ethernet

▪ switches

▪ VLANS

Tầng Link 5-3

Phát hiện lỗi

EDC= Error Detection and Correction bits (redundancy)

D = phần dữ liệu được bảo vệ bởi trường EDC, có thể chứa các trường

header

• Việc phát hiện lỗi không bảo đảm 100%!

• giao thức có thể bỏ qua một số lỗi

• trường EDC càng lớn thì việc phát hiện và sửa lỗi càng tốt hơn

otherwise

Tầng Link 5-4

Kiểm tra chẵn lẻ (Parity checking)

Tại sao gọi là :

Even

paritychecking

EVEN = 0

ODD = 1

CÓ SỐ CHẴN SỐ 1 = 0

CÓ SỐ LẺ SỐ 1 = 1

Tầng Link 5-5

Kiểm tra chẵn lẻ (Parity checking)

bit parity 2 chiều:

❖ Phát hiện và sửa các lỗi bit đơn

Tầng Link 5-6

10010111 01111101|1

10101010 10011110|1

01001000 10110000|1

01101011 01010000|0

10011000 01110001|1

-------------------------------

10000110 01110000|0

A

B

C

Hàng 4 , Cột 15

Hàng 3 , Cột 8

Hàng 4 , Cột 16

Đáp án khác

D

Internet checksum

Mục tiêu: phát hiện “các lỗi” (ví dụ, các bit bị đảo) trong

packet được truyền (chú ý: chỉ được dùng tại tầng

Vận chuyển)

Bên gửi:

Bên nhận:

❖ Xử lý các nội dung của

segment như một

chuỗi các số nguyên

16-bit

❖ Tính toán checksum của

segment vừa nhận

❖ Kiểm tra xem giá trị của

checksum vừa được tính

có bằng với giá trị trong

trường checksum không:

❖ checksum: là (tổng bù

1) của các nội dung

của segment

▪ khô ng – phát hiện lỗi

▪ có – không phát hiện

lỗi. Nhưng có thể còn

có lỗi khác không?

❖ Bên gửi đặt giá trị

checksum vào trong

trường checksum của

UDP

Tầng Link 5-8

Data Link Layer 5-9

Cyclic redundancy check

❖ Thuật toán phát hiện lỗi tốt hơn

❖ Xem đoạn bit dữ liệu, D, như một số nhị phân

❖ Chọn mẫu chiều dài r+1 bit (bộ khởi tạo), G

❖ Mục tiêu: chọn r bit CRC, R, sao cho

▪ <D,R> chia hết cho G (theo cơ số 2)

▪ Bên nhận biết G, chia <D,R> cho G. Nếu phần dư khác

không: phát hiện lỗi!

▪ Có thể phát hiện tất cả các lỗi nhỏ hơn r+1 bits

❖ Được sử dụng rộng rãi trong thực tế (Ethernet,

802.11 WiFi, ATM)

Tầng Link 5-10

CRC ví dụ

Muốn:

D^.2^rXOR R = nG

Tương đương:

D^.2^r= nG XOR R

Tương đương:

nếu chúng ta chia

D^.2^rcho G, có được

phần dư R thỏa:

_{R = remainder[}D^.2^r

]

G

Tầng Link 5-11

Data Link Layer 5-12

A

B

C

01100

11011

110101

D

Đáp án khác

Tầng Liên kết dữ liệu và mạng LAN

5.1 Giới thiệu và các 5.5 link virtualization:

dịch vụ

MPLS

5.2 phát hiện lỗi và sửa 5.6 mạng trung tâm dữ

lỗi liệu

5.3 các giao thức đa 5.7 Hoạt động thường

truy cập

ngày - truy cập web

5.4 mạng LAN

▪ Định địa chỉ, ARP

▪ Ethernet

▪ switches

▪ VLANS

Tầng Link 5-14

Các giao thức đa truy cập

❖ Chia sẻ chung kênh quảng bá (broadcast) đơn

❖ 2 hoặc nhiều phiên truyền đồng thời bởi các node: nhiễu -

giao thoa gây biến đổi mức tín hiệu

▪ collision (đụng độ) xảy ra nếu node nhận được 2 hoặc

nhiều tín hiệu tại cùng thời điểm

Giao thức đa truy cập

❖ Dùng thuật toán phân phân tán (distributed algorithm) xác

định cách các node chia sẻ kênh truyền, ví dụ: xác định

khi nào node có thể truyền

❖ Các thông báo về việc chia sẻ kênh truyền phải sử dụng

chính kênh đó!

▪ Không dùng thêm kênh khác để phối hợp

Tầng Link 5-15

Các giao thức MAC: phân loại

3 loại chính:

❖ Phân hoạch kênh (channel partitioning)

▪ Chia kênh truyền thành “các mảnh” nhỏ hơn (các slot thời

gian - TDM, tần số - FDM, mã - CDM)

▪ Cấp phát mảnh này cho node để sử dụng độc quyền

❖ Truy cập ngẫu nhiên (random access)

▪ Kênh truyền không được chia, cho phép đụng độ

▪ “giải quyết” đụng độ

❖ “Xoay vò ng”

▪ Các node thay phiên nhau, nhưng nút có nhiều dữ liệu hơn

được giữ thời gian truyền lâu hơn

Tầng Link 5-16

Các giao thức MAC phân hoạch kênh:TDMA

TDMA

TDMA: time division multiple access

❖ Truy cập kênh truyền theo hình thức “xoay

vòng”

❖ Mỗi trạm (station) có slot với độ dài cố định

(độ dài = thời gian truyền packet) trong mỗi

vò ng (round)

❖ Các slot không sử dụng sẽ nhàn rỗi

❖ Ví dụ: LAN có 6 trạm, 1,3,4 có gói được gửi,

các slot 2,5,6 sẽ nhàn rỗi

6-slot

frame

6-slot

frame

3

4

1

Tầng Link 5-17

Các giao thức MAC phân hoạch kênh: FDMA

FDMA: frequency division multiple access

❖ Phổ kênh truyền được chia thành các dải tần số

❖ Mỗi trạm được gán một dải tần số cố định

❖ Trong thời gian không truyền, các dải tần rảnh

❖ Ví dụ: LAN có 6 station, 1,3,4 có packet truyền, các dải

tần số 2,5,6 nhàn rỗi

FDM cable

Tầng Link 5-18

Các giao thức truy cập ngẫu nhiên

❖ Khi 1 node có packet cần gởi

▪ Truyền dữ liệu với trọn tốc độ của kênh dữ liệu R.

▪ Không có sự ưu tiên giữa các node

❖ 2 hoặc nhiều node truyền → “đụng độ”,

❖ Giao thức truy cập ngẫu nhiên MAC xác định:

▪ Cách để phát hiện đụng độ

▪ Cách để giải quyết đụng độ (ví dụ: truyền lại sau đó)

❖ Ví dụ các giao thức MAC truy cập ngẫu nhiên:

▪ slotted ALOHA

▪ ALOHA

▪ CSMA, CSMA/CD, CSMA/CA

Tầng Link 5-19

Slotted ALOHA

Giả thuyết:

Hoạt động:

❖ Tất cả các frame có cùng

❖ Khi node có được frame

mới, nó sẽ truyền trong slot

kế tiếp

kích thước

❖ Thời gian được chia thành

các slot có kích thước bằng

nhau (thời gian để truyền

đủ 1 frame)

▪ Nếu không có đụng độ:

node có thể gửi frame

mới trong slot kế tiếp

▪ Nếu có đụng độ: node

truyền lại frame trong

mỗi slot tiếp theo với xác

suất p cho đến khi thành

cô ng

❖ Các node bắt đầu truyền chỉ

ngay tại lúc bắt đầu slot

❖ Các node được đồng bộ

hó a

❖ Nếu 2 hoặc nhiều node

truyền trong cùng 1 slot, thì

tất cả các node đều phát

hiện đụng độ

Tầng Link 5-20