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

Chương 8: Tầng liên kết dữ liệu

Giảng viên: Ngô Hồng Sơn

Khoa CNTT- ðHBK Hà Nội Bộ môn Truyền thông và Mạng máy tính

Tổng quan

(cid:1) Công nghệ mạng LAN (Local

(cid:1) Dịch vụ:

Area Network) (cid:1) Ethernet (cid:1) Wireless LAN

(cid:1) Công nghệ mạng WAN (Wide

(cid:1) ðóng gói, ñịa chỉ hóa (cid:1) Phát hiện và sửa lỗi (cid:1) Kiểm soát luồng (cid:1) Kiểm soát truy nhập ñường

truyền

Area Network) (cid:1) Frame relay (cid:1) ATM (cid:1) ….

(cid:1) Tuần trước: Tầng ứng dụng (cid:1) Mô hình: client-server vs. P2P (cid:1) Case study: HTTP, Mail, FTP… (cid:1) Tuần này: Tầng liên kết dữ liệu

Giới thiệu về Tầng liên kết dữ liệu

Nút mạng và liên kết

“link”

(cid:1) Nút mạng:

(cid:1) PCs, Laptop, Routers,

Server…

(cid:1) Liên kết:

(cid:1) Kênh truyền thông giữa

các nút kế tiếp

(cid:1) Hữu tuyến: Ethernet LAN,

ADSL, fiber optic…

(cid:1) Không dây: Wi-fi, Wi-Max,

vệ tinh,…

(cid:1) Tầng liên kết dữ liệu:

Truyền dữ liệu giữa các thành phần kế tiếp

Tầng liên kết dữ liệu và kiến trúc phân tầng

Application

Media independent sub-layer

Transport

Network

LLC

(Logical Link Control)

Data-link

MAC

Physical

(Media Access Control)

Media dependent sub-layer

802.2 LLC

802.3 802.4 802.5 802.11 ….. 802.16

Ethernet Token Bus Token Ring Wi-Fi Wi-Max

IEEE 802.x series

Tổng quan về các chức năng

Flow control

Framing

Media Access Control

Error control

Addressing

Datalink layer

Các chức năng (1)

(cid:1) ðóng gói - Framing:

thêm phần ñầu, phần ñuôi

(cid:1) ðơn vị dữ liệu: Frame (khung tin) (cid:1) Bên gửi: ñặt gói tin tầng mạng vào khung tin,

truyền lên tầng mạng (cid:1) ðịa chỉ hóa - Addressing:

(cid:1) Bên nhận: Bỏ phần ñầu, phần ñuôi và lấy gói tin

danh nút nguồn, nút ñích

(cid:1) ðịa chỉ vật lý ñặt trong phần ñầu gói tin ñể ñịnh

Các chức năng (2)

(cid:1) ðiều khiển truy nhập ñường truyền

(cid:1) Kiểm soát luồng:

(cid:1) Nếu là mạng ña truy nhập, cần có các giao thức truy nhập ñường truyền cho nhiều máy trạm

nhận hoạt ñộng tốt, không bị quá tải

(cid:1) Kiểm soát lỗi:

(cid:1) Kiểm soát tốc ñộ truyền của bên gửi sao cho bên

(cid:1) Phát hiện và sửa các lỗi bít (cid:1) e.g. parity check, checksum, CRC check

Kiểm soát lỗi

Phát hiện lỗi Phát hiện và sửa lỗi

Nguyên lý phát hiện lỗi

EDC= Error Detection Code (redundancy)

Mã phát hiện lỗi

Data Data

Error

All bit in Data’ OK?

Data’ EDC’ Data EDC

Link with bit errors

Mã chẵn lẻ

(cid:1) Phát hiện lỗi bít ñơn

(cid:1) Mã ñơn

(cid:1) Phát hiện và sửa lỗi bít ñơn

(cid:1) Mã hai chiều

101011 111100 011101 001010

101011 101100 011101 001010

Internet?

(cid:1) Khái niệm về checksum của

Internet checksum (nhắc lại)

(cid:1) Mã kiểm tra lỗi ñộ dài 16 bit (cid:1) Tại bên gửi

(cid:1) ðặt 16 bit của checksum = 0 (cid:1) Tổng theo các số 16 bits (cid:1) ðảo bit tất cả (cid:1) Tại bên nhận

(cid:1) Tổng tất cả theo các số 16 bit (cid:1) Phải thu ñược toàn các bit 1 (cid:1) Nếu không, gói tin bị lỗi

CRC: Cyclic Redundancy Check Mã vòng

(cid:1) Dữ liệu ñược xem như một số nhị phân: D (cid:1) Chọn một chuỗi r+1 bit, G (chuỗi sinh – Generator) (cid:1) Tìm một chuỗi R ñộ dài r bit, sao cho chuỗi ghép của D và R

là một số nhị phân chia hết cho G (chia modulo 2) (cid:1) chia hết cho G

D D

mod G = 0

N mod G = 0 ?

D’ R’ D R

Link with bit errors

CRC: Cách tìm R

(cid:1) có thể viết dưới dạng

(cid:1) D.2r XOR R

(cid:1) Ví dụ 10101001000 1001 1001 1011110

(cid:1) chia hết cho G (cid:1) D.2r XOR R = n.G (cid:1) D.2r = n.G XOR R

1110 1001

(cid:1) Có nghĩa là R là số dư khi chia D.2r

1110 1001

cho G (phép chia modulo 2)

1111 1001

R= D.2r mod G

1100 1001

1010 1001

110

R=110, chuỗi bít gửi ñi là 10101001110

D R

CRC biểu diễn dưới dạng ña thức

(cid:1) 1011 : x3 +x +1 (cid:1) Ví dụ một số mã CRC ñược sử dụng trong thực tế:

(cid:1) CRC-8 = x8 + x2 + x + 1 (cid:1) CRC-12 = x12+x11+x3+x2+x (cid:1) CRC-16-CCITT = x16 + x12 + x5 + 1 (cid:1) CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5

+ x4 + x2 + x + 1

(cid:1) G càng dài, mã CRC phát hiện lỗi càng hiệu quả (cid:1) CRC ñược sử dụng rộng rãi trong thực tế

(cid:1) Wi-fi, ATM, Ethernet… (cid:1) Phép toán XOR ñược cài ñặt bởi phần cứng (cid:1) Phát hiện chuỗi bít bị lỗi có ñộ dài nhỏ hơn r+1 bit

Kiểm soát truy nhập ñường truyền

Các dạng liên kết

(cid:1) ADSL (cid:1) Telephone modem (cid:1) Leased Line….

(cid:1) ðiểm-nối-ñiểm

(cid:1) Mạng LAN truyền thống với hình trạng bus hay mạng hình

sao dùng hub (công nghệ lỗi thời)

(cid:1) Wireless LAN, radio network, mobile network (cid:1) HFC: (cid:1) …

(cid:1) Quảng bá

(cid:1) Các mạng quảng bá cần giao thức ñiều khiển truy nhập ñể tránh xung ñột -> Giao thức ña truy nhập

Phân loại các giao thức ña truy nhập

(cid:1) 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)

(cid:1) Chia từng phần nhỏ ñó cho các nút mạng

(cid:1) Chia kênh:

(cid:1) Kênh không ñược chia, cho phép ñồng thời truy nhập, chấp

nhận là có xung ñột (collision)

(cid:1) Cần có cơ chế ñể phát hiện và tránh xung ñột (cid:1) e.g. Pure Aloha, Slotted Aloha, CSMA/CD, CSMA/CA…

(cid:1) Truy nhập ngẫu nhiên:

(cid:1) Theo hình thức quay vòng (cid:1) Token Ring, Token Bus….

(cid:1) Lần lượt:

Các phương pháp chia kênh

(cid:1) FDMA: frequency division multiple access (cid:1) TDMA: time division multiple access (cid:1) CDMA: code division multiple access

Ví dụ:

TDMA và FDMA

4 kênh

FDMA

frequency

time

TDMA:

frequency

time

TDMA: Ví dụ

(cid:1) Mạng LAN có 6 máy, 1,3,4 hoạt ñộng. 2, 5, 6

nghỉ

3

4 6-slot frame 3 4

1 FDMA: Ví dụ

time

s d n a b y c n e u q e r f

FDM cable

Các phương pháp truy cập ngẫu nhiên

Aloha

Central Node

(cid:1) Packet-Switched Radio Network (cid:1) Các nút truyền trên một tần số (f0) (cid:1) Nút trung tâm nhận và truyền lại một

tần số khác (f1)

Nếu có hai nút cùng truyền: Xung ñột

(cid:1) Nếu có xung ñột, nút vừa truyền sẽ

nhận ñược một gói tin bị lỗi, nó sẽ ñợi một thời gian ngẫu nhiên trước khi truyền lại

Host 1 Host 2 Host 3

Slotted ALOHA

(cid:1) Thời gian ñược chia làm các khe (slot) bằng nhau (cid:1) Dữ liệu có cùng kích thước (1 slot) (cid:1) Các nút phải ñồng bộ hóa thời gian

Pure ALOHA

Hi(cid:1)u qu(cid:2) kém h(cid:3)n Slotted ALOHA!

CSMA/CD

(cid:1) Carrier Sense Multiple Access with Collision

Detection (ða truy nhập, có phát hiện xung ñột)

blah blah

b l a h

(cid:1) Thế nào là CSMA/CD: trong một cuộc họp

b l a h

(cid:1) Multiple Access: (cid:1) Collision: (cid:1) CSMA: “Listen before talk” (cid:1) CD

(cid:1) “Listen while talking”

CSMA/CD

(cid:1) CSMA: Các máy nghe trước muốn truyền:

(cid:1) Tại sao lại có xung ñột?

(cid:1) Nếu kênh rỗi, truyền toàn bộ dữ liệu (cid:1) Nếu kênh bận, chờ (rút lui và quay lại)

ðộ trễ lan truyền

Xung ñột trong CSMA

(cid:1) Giả sử kênh truyền có 4

nút

(cid:1) 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)

(cid:1) Ví dụ:

CSMA/CD: Tóm tắt

(cid:1) Máy trạm nghe trước khi muốn truyền (cid:1) Bận: Rút lui, sau ñó quay lại tiếp tục nghe (cid:1) Rỗi: Bắt ñầu truyền, vừa truyền vừa “nghe ngóng”

xem có xung ñột hay không (cid:1) Nghe trong thời gian bao lâu?

truyền và quay lại trạng thái rút lui (cid:1) Sau khi rút lui, khi nào thì quay lại

(cid:1) Nếu phát hiện thấy xung ñột: Hủy bỏ quá trình

(cid:1) Exponential back-off

So sánh chia kênh và truy nhập ngẫu nhiên

(cid:1) Hiệu quả, công bằng cho ñường truyền với lưu lượng lớn (cid:1) 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ỏ

(cid:1) Chia kênh

(cid:1) Khi tải nhỏ: Hiệu quả vì mỗi nút có thể sử dụng toàn bộ

kênh truyền

(cid:1) Tải lớn: Xung ñột tăng lên

(cid:1) Truy nhập ngẫu nhiên

của hai phương pháp trên

(cid:1) Phương pháp quay vòng: Có thể dung hòa ưu ñiểm

Token Ring – Mạng vòng dùng thẻ bài

(cid:1) Một “thẻ bài” luân

chuyển lần lượt qua từng nút mạng (cid:1) Nút nào giữ thẻ bài sẽ ñược gửi dữ liệu

(nothing to send)

chuyển thẻ bài ñi

(cid:1) Gửi xong phải T

(cid:1) Tốn thời gian chuyền

(cid:1) Một số vấn ñề

thẻ (cid:1) Trễ (cid:1) Mất thẻ bài….

data

Tổng kết các phương pháp kiểm soát ña truy nhập

(cid:1) Chia kênh (cid:1) Truy nhập ngẫu nhiên (cid:1) Quay vòng (cid:1) Phân tích ưu, nhược ñiểm

Thảo luận

cần gửi tăng lên thì: (cid:1) Xung ñột tăng lên? (cid:1) Thông lượng tăng lên?

(cid:1) Trong phương pháp CSMA/CD, khi lượng dữ liệu

lượng dữ liệu cần gửi tăng lên?

(cid:1) Trong phương pháp TDMA, xung ñột sẽ tăng lên khi

Token Ring là kém hơn so với CSMA/CD

(cid:1) Khi lượng dữ liệu cần gửi là rất nhiều, phương pháp

(cid:1) Câu hỏi: Giải thích một cách ñịnh lượng hiệu quả của các phương pháp truy cập ñường truyền (Bài tập lớn)

LAN: Local Area Network

LAN topology

WLAN

hub, switch

Bus

Star Ring

Mạng Lan Ethernet

(cid:1) Ethernet: 10BaseT, 10Base2… (cid:1) Fast Ethernet: 100BaseT (cid:1) Giga Ethernet

(cid:1) IEEE 802.3 (cid:1) Tốc ñộ ña dạng: 10 Mbps – 10 Gbps…

Metcalfe’s Ethernet sketch

Mạng hình sao

(cid:1) Mạng dạng bus từng phổ biến trước ñây

(cid:1) Các nút mạng cùng chia sẻ một ñường trục

(cid:1) Ngày nay: Chủ yếu là mạng hình sao

(cid:1) Một bộ chuyển mạch trung tâm với nhiều cổng Ethernet (cid:1) Bộ chuyển mạch có thể tạo liên kết ñộc lập cho 2 nút mạng

bất kỳ

(cid:1) Không xung ñột (cid:1) Không giao thức ña truy nhập .

switch

bus: coaxial cable star

Cấu trúc ñơn vị dữ liệu của Ethernet

PAD

(cid:1) 6 bytes

(cid:1) Preamble: Bắt ñầu một khung tin (cid:1) Address: ðịa chỉ vật lý của trạm nguồn, trạm ñích

AppleTalk, …)

(cid:1) Type: Giao thức tầng trên (IP, Novell IPX,

(nếu cần thiết)

(cid:1) PAD: Phần thêm vào cho khung tin ñủ ñộ dài

(cid:1) CRC: Mã kiểm soát lỗi

Chuẩn mạng cục bộ 802.3 Ethernet Standards

(cid:1) Link & Physical Layers (cid:1) MAC: CSMA/CD (cid:1) Có nhiều chuẩn Ethernet khác nhau

(cid:1) Cùng giao thức MAC và cấu trúc Frame (cid:1) Tốc ñộ khác nhau: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps (cid:1) Phương tiện truyền khác nhau: Cáp quang, cáp ñồng trục, cáp

xoắn ñôi.

MAC protocol and frame format

100BASE-T2

100BASE-FX

100BASE-TX

100BASE-BX

100BASE-SX

100BASE-T4

application transport network link physical

fiber physical layer

copper (twister pair) physical layer

Ethernet cổ ñiển

Bộ lặp 500m

10Mb/s

1500

Cáp ñồng trục

PROP

/ cl

5.2/

s m

max TRANSP

TRANSP

1500 ⇒ )

PROP ( m 12

120

Packetsize

/ sMb

bits

Thực tế, Min packet size = 512 bits. • Thêm thời gian phát hiện xung ñột. • Cho phép “repeaters” ñủ thời gian khuếch ñại tín hiệu.

· ‡ \

Chuẩn Ethernet 10Mb/s

Ethernet MAC Protocol

10Base-5

10Base-2

10Base-T

10Base-F

10Base-5: Cáp ñồng trục béo, max = 500m. 10Base-2: Cáp ñồng trục gầy, max ~ 200m (180m). 10Base-T: Dùng cáp xoắn ñôi (twisted-pair) CAT 3 10Base-F: Dùng cáp sợi quang.

10Base-T

Hub

(cid:1) Sử dụng hub trung tâm, cáp TP CAT 3 (4 cặp

dây xoắn).

(cid:1) Dễ lắp ñặt và quản trị (cid:1) Làm Ethernet trở nên phổ biến hơn

100m

“Fast Ethernet” 100Mb/s

Ethernet MAC Protocol

100Base-T4

100Base-TX

100Base-FX

Mạng hình sao, ðộ dài cáp 100m.

100m

Hub, switch

100Base-T4: Cáp TP CAT 3 . 100Base-TX: Cáp TP CAT 5. 100Base-FX: Cáp sợi quang.

“Gigabit Ethernet” 1Gbps

Ethernet MAC Protocol

1000Base-TX

1000Base-FX

1000Base-TX: 4 cặp dây xoắn, CAT 6. 1000Base-FX: Cáp sợi quang.

ðịa chỉ MAC và ARP

(cid:1) ðịa chỉ IP : (cid:1) 32-bit (cid:1) Dùng trong tầng mạng IP

(cid:1) ðịa chỉ MAC :

(cid:1) Dùng trong tầng liên kết dữ liệu (cid:1) 48 bit

ARP và ñịa chỉ MAC Mỗi card mạng có một ñịa chỉ MAC

1A-2F-BB-76-09-AD

Broadcast address = FF-FF-FF-FF-FF-FF

= adapter

71-65-F7-2B-08-53

58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98

LAN (wired or wireless)

ARP: Address Resolution Protocol

Vấn ñề: Xác ñịnh ñịa chỉ MAC từ ñịa chỉ IP

(cid:1) Mỗi nút mạng (host, router) có một bảng ARP

137.196.7.78

1A-2F-BB-76-09-AD

137.196.7.23

137.196.7.14

71-65-F7-2B-08-53

58-23-D7-FA-20-B0

(cid:1) ARP table: Ánh xạ ñịa chỉ IP/MAC của một số nút trong mạng < IP address; MAC address; TTL> (cid:1) TTL (Time To Live): khoảng 20 min.)

0C-C4-11-6F-E3-98

137.196.7.88

LAN

Giao thức ARP : Hoạt ñộng trên cùng một mạng

(cid:1) A lưu lại ñ/c MAC của B và gửi tin ñến B

(cid:1) A muốn gửi dữ liệu tới B mà không biết ñ/c MAC của B

“plug-and-play” (cid:1) Nếu muốn ARP mở

(cid:1) ARP là một giao thức

quảng bá?

rộng phạm vi hoạt ñộng sang một mạng khác? (cid:1) ARP Proxy

(cid:1) A quảng bá một gói tin ARP, trong ñó chỉ ra ñ/c IP của B (cid:1) Quảng bá ntn? (cid:1) Phạm vi gói tin ñược

(cid:1) B nhận ñược ñ/c này sẽ trả lời A ñ/c MAC của mình (cid:1) Làm sao biết A gửi?

Ví dụ: chuyển gói tin giữa hai máy

Giả sử A biết ñ/c IP của B

88-B2-2F-54-1A-0F

74-29-9C-E8-FF-55 A

E6-E9-00-17-BB-4B

222.222.222.221

1A-23-F9-CD-06-9B

111.111.111.111

222.222.222.220

111.111.111.110

222.222.222.222 B

111.111.111.112

49-BD-D2-C7-56-2A

CC-49-DE-D0-AB-7D

(cid:1) A tạo một gói tin IP, ñịa chỉ nguồn A, ñịa chỉ ñích B (cid:1) A dùng ARP ñể lấy ñ/c MAC của router: 111.111.111.110 (cid:1) A tạo một frame, ñ/c ñích là router, ñặt gói tin vào (cid:1) A chuyển frame tới R (cid:1) R nhận frame (cid:1) R ñọc ñịa chỉ IP của B từ trong khung tin (cid:1) R dùng ARP ñể tìm ñ/c MAC của B (cid:1) R tạo một frame, ñặt gói tin vào và chuyển ñến B

88-B2-2F-54-1A-0F

74-29-9C-E8-FF-55

E6-E9-00-17-BB-4B

222.222.222.221

1A-23-F9-CD-06-9B

111.111.111.111

222.222.222.222

222.222.222.220

111.111.111.110

111.111.111.112

49-BD-D2-C7-56-2A

CC-49-DE-D0-AB-7D