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

Mạng máy tính

Bộ môn Kỹ thuật máy tính và Mạng Khoa Công nghệ Thông tin Đại học Sư phạm Hà Nội

1-1

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

Mục đích: (cid:137) Hiểu các nguyên tắc bên trong của các dịch vụ

tầng liên kết dữ liệu: (cid:129) Phát hiện và sửa lỗi (cid:129) Chia sẻ một kênh broadcast: đa truy cập (cid:129) Đánh địa chỉ tầng liên kết dữ liệu (cid:129) Truyền dữ liệu tin cậy, điều khiển luồng: có!

dữ liệu khác nhau

1-2

(cid:137) Ví dụ và cài đặt của các công nghệ tầng liên kết

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-3

(cid:137) 5.5 Ethernet

“liên kết”

Tầng liên kết dữ liệu: Giới thiệu Một số thuật ngữ: (cid:137) host và router: nút (cid:137) Kênh truyền thông kết nối các nút kề dọc theo đường truyền thông gọi là liên kết (link) (cid:129) Liên kết có dây (cid:129) Liên kết không dây (cid:129) LAN

(cid:137) Các gói tin tầng 2 gọi làkhung

(frame), đóng gói các datagram

Tầng liên kết dữ liệu có vai trò truyền các datagram từ một nút tới nút kề qua một liên kết

1-4

tầng khác

(cid:129) Đường sắt (tàu hỏa): HN -> Đà

Nẵng

Tương tự vận tải: (cid:137) Chuyến đi từ Hà Nội tới Cần Thơ

Tầng liên kết dữ liệu: Xem xét với (cid:137) Datagram được truyền bởi các giao thức liên kết dữ liệu khác nhau qua các liên kết khác nhau: (cid:129) Ví dụ: Ethernet ở liên kết đầu

(cid:129) Đường không (máy bay): Đà

Nẵng -> Tp HCM

(cid:129) Đường bộ (ô tô): Tp HCM ->

tiên, frame relay ở liên kết giữa, 802.11 ở liên kết cuối cùng (cid:137) Mỗi giao thức liên kết dữ liệu

Cần Thơ

(cid:137) khách du lịch = datagram (cid:137) transport segment = liên kết

cung cấp các dịch vụ khác nhau (cid:129) Ví dụ: có thể hoặc không cung cấp truyền tin cậy qua liên kết

(cid:137) hình thức vận tải = giao thức

truyền thông (communication link)

(cid:137) đại lý du lịch = thuật toán dẫn

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

1-5

đường

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

(cid:129) Đóng gói datagram thành các khung, thêm header, trailer (cid:129) Truy cập kênh nếu phương tiện dùng chung (shared

(cid:137) Đóng khung, truy cập liên kết:

(cid:129) Các địa chỉ “MAC” sử dụng trong header của khung để định

medium)

danh nguồn, đích

(cid:129) Đã học cách để thực hiện truyền tin cậy (chương 3)! (cid:129) Ít khi sử dụng trên các liên kết lỗi bít thấp (ví dụ: cáp quang,

• Khác với địa chỉ IP! (cid:137) Truyền tin cậy giữa các nút kề

(cid:129) Liên kết không dây: tỷ lệ lỗi cao

cáp xoắn đôi)

• Q: Tại sao xét tin cậy cả mức liên kết dữ liệu và end-

1-6

end?

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

(cid:129) Tốc độ giữa nút nhận và nút gửi kề nhau

(cid:137) Điều khiển luồng:

(cid:129) Các lỗi gây ra bởi suy hao và nhiễu tín hiệu (cid:129) Bên nhận phát hiện sự tồn tại của lỗi:

(cid:137) Phát hiện lỗi:

• Báo hiệu cho bên gửi biết để gửi lại hoặc loại bỏ khung

(cid:129) Bên nhận xác định và sửa các bít lỗi không phải sử dụng

(cid:137) Sửa lỗi:

(cid:129) Với half duplex, các nút tại cả hai điểm cuối của liên kết có

đến việc truyền lại (cid:137) Half-duplex và full-duplex

1-7

thể truyền nhưng không tại cùng thời điểm

Truyền thông thích nghi

datagram

giao thức tầng liên kết dữ liệu

nút nhận

Nút gửi

frame

adapter

(cid:129) Tìm kiếm lỗi, rdt, điều khiển

(cid:137) Bên nhận

(cid:129) Tách ra datagram, chuyển

luồng,…

(cid:137) Tầng liên kết dữ liệu được cài đặt trong “adaptor” (còn gọi là NIC) (cid:129) Ethernet card, PCMCI card,

802.11 card

(cid:129) Đóng gói datagram trong

(cid:137) Bên gửi:

tới nút nhận (cid:137) adapter là bán tự trị (cid:137) Tầng vật lý và liên kết dữ

liệu

1-8

(cid:129) Thêm các bít kiểm tra lỗi, rdt, điều khiển luồng,…

một frame

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-9

(cid:137) 5.5 Ethernet

Phát hiện lỗi

EDC= Error Detection and Correction bits (phần dôi thừa) D = Dữ liệu được bảo vệ bằng kiểm tra lỗi, có thể bao gồm các trường header

• Phát hiện lỗi không 100% tin cậy!

1-10

• Giao thức có thể không phát hiện ra một số lỗi nhưng tỷ lệ rất thấp • Trường EDC càng rộng thì phát hiện và sửa lỗi càng tốt

Kiểm tra tính chẵn lẻ

Bít chẵn lẻ 2 chiều: Phát hiện và sửa một bít lỗi

Bít chẵn lẻ đơn: Phát hiện một bít lỗi

1-11

0 0

Internet checksum

Mục đích: Phát hiện lỗi trong segment đã truyền (Chú ý:

chỉ sử dụng tại tầng giao vận)

Bên nhận: (cid:137) Tính toán checksum của

Bên gửi: (cid:137) Xem xét nội dung của các

segment đã nhận

(cid:137) checksum: tổng (bù 1) của

segment như một chuỗi các số nguyên 16 bít

(cid:137) Kiểm tra nếu giá trị checksum đã tính bằng giá trị trường checksum: (cid:129) NO – Lỗi được phát hiện (cid:129) YES – Không phát hiện ra lỗi. Nhưng có thể có lỗi?

nội dung segment (cid:137) Bên gửi đặt giá trị

1-12

checksum vào trong trường checksum của UDP

Checksumming: Cyclic Redundancy Check

(cid:137) Coi các bít dữ liệu D như một số nhị phân (cid:137) Chọn r+1 bít mẫu (generator), G (cid:137) Mục đích: chọn r bít CRC, R, ví dụ (cid:129) chia hết cho G (modulo 2) (cid:129) Bên nhận biết G, chia cho G. Nếu phần dư khác không: lỗi

được phát hiện!

(cid:129) Có thể phát hiện các lỗi ít hơn r+1 bít

(cid:137) Sử dụng rộng rãi trong thực tế (ATM, HDCL)

1-13

Ví dụ CRC

Muốn:

D.2r XOR R = nG

Tương đương:

D.2r = nG XOR R

Tương đương:

Nếu D.2r chia G, phần dư là R

R = Phần dư [ ]

D.2r G

1-14

CRC

generator, G.

(cid:137) Chuẩn quốc tế đã định nghĩa 8-, 12-, 16- và 32-bit

IEEE của tầng liên kết dữ liệu, sử dụng GCRC-32 = 10000010 01100000 10001110 110110111

1-15

(cid:137) 8-bit CRC sử dụng để phát hiện lỗi trong ATM cell (cid:137) 32-bit bít CRC sử dụng để phát hiện lỗi trong giao thức

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-16

(cid:137) 5.5 Ethernet

Các giao thức và liên kết đa truy cập

Hai kiểu liên kết: (cid:137) point-to-point

(cid:129) PPP trong truy cập dial-up (cid:129) Liên kết point-to-point giữa Ethernet switch và host

(cid:129) Ethernet (cid:129) upstream HFC (cid:129) 802.11 wireless LAN

1-17

(cid:137) broadcast (chia sẻ phương tiện)

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

(cid:137) Kênh quảng bá, dùng chung, đơn (cid:137) hai hoặc nhiều nút truyền đồng thời: đan xen

(cid:129) Đụng độ nếu nút nhận hai hoặc nhiều tín hiệu tại cùng

một thời điểm Giao thức đa truy cập (cid:137) Thuật toán phân tán xác định cách nút dùng chung kênh (xác định khi nào một nút có thể truyền)

(cid:137) Truyền thông về việc dùng chung kênh phải sử

dụng chính kênh đó! (cid:129) Không có kênh ở ngoài cùng phối hợp hoạt động

1-18

Ý tưởng của giao thức đa truy cập

Kênh quảng bá tốc độ R bps 1. Khi một nút muốn truyền, nó có thể gửi với tốc độ R 2. Khi M nút muốn truyền, mỗi nút có thể gửi với tốc độ

trung bình R/M

3. Hoàn toàn không tập trung:

(cid:129) Không có nút đặc biệt để phối hợp việc truyền (cid:129) Không có sự đồng bộ của đồng hồ hay khe

4. Đơn giản

1-19

Giao thức MAC: Phân loại

Ba lớp lớn: (cid:137) Phân chia kênh

(cid:129) Chia kênh thành các phần nhỏ (khe thời gian, tần số, mã) (cid:129) Cấp phát phần cho nút sử dụng riêng

(cid:129) Không chia kênh, cho phép đụng độ (cid:129) “Khôi phục” từ đụng độ

(cid:137) Truy cập ngẫu nhiên

(cid:129) Các nút lần lượt truyền theo phiên nhưng nút cần gửi nhiều

(cid:137) Theo phiên lần lượt

1-20

có thể chiếm phiên dài hơn

Giao thức MAC kiểu phân chia kênh: TDMA

TDMA: time division multiple access (cid:137) Truy cập tới kênh theo vòng (cid:137) Mỗi trạm nhận một khe chiều dài cố định (chiều dài = thời gian

(cid:137) TDM (Time Division Multiplexing): kênh được chia thành N khe thời gian, một khe cho một người sử dụng; không hiệu quả với người sử dụng chu kỳ thấp và tải nặng.

(cid:137) FDM (Frequency Division Multiplexing): chia theo tần số

1-21

truyền gói tin) trong mỗi vòng (cid:137) Các khe không sử dụng sẽ rỗi (cid:137) Ví dụ: 6 trạm LAN, 1,3,4 có gói tin, khe 2,5,6 rỗi

Giao thức MAC kiểu phân chia kênh: FDMA

thời gian

n ầ

g n ă b

(cid:137) TDM (Time Division Multiplexing): kênh được chia thành N khe thời gian,

một khe cho một người sử dụng; không hiệu quả với người sử dụng chu kỳ thấp và tải nặng

1-22

(cid:137) FDM (Frequency Division Multiplexing): chia theo tần số

FDMA: frequency division multiple access (cid:137) Phổ của kênh được chia thành các băng tần (cid:137) Mỗi trạm được gán một băng tần cố định (cid:137) Thời gian truyền không sử dụng trong băng tần thì sẽ rỗi (cid:137) Ví dụ: 6 trạm LAN; 1,3,4 có gói tin; băng tần 2,5,6 rỗi

Giao thức MAC kiểu phân chia kênh: CDMA

1-23

Giao thức truy cập ngẫu nhiên

(cid:129) Truyền trên toàn kênh với tốc độ dữ liệu R (cid:129) Không có sự phối hợp trước giữa các nút (cid:137) Hai hoặc nhiều nút truyền ➜ “đụng độ” (cid:137) Giao thức MAC truy cập ngẫu nhiên chỉ ra:

(cid:129) Cách phát hiện đụng độ (cid:129) Cách khôi phục từ đụng độ (ví dụ: đợi một khoảng thời gian

(cid:137) Khi nút có gói tin để gửi

rồi truyền lại)

(cid:129) slotted ALOHA (cid:129) ALOHA (cid:129) CSMA, CSMA/CD, CSMA/CA

1-24

(cid:137) Ví dụ của giao thức MAC kiểu truy cập ngẫu nhiên

Slotted ALOHA

Giả sử (cid:137) Mọi frame có cùng kích

thước

Hoạt động (cid:137) Khi nút giành khung mới, nó truyền trong khe tiếp theo

(cid:137) Thời gian được chia

(cid:137) Không đụng độ, nút có thể gửi frame mới trong khe tiếp

thành các khe có kích thước bằng nhau, thời gian để truyền 1 frame (cid:137) Nút bắt đầu truyền frame chỉ tại bắt đầu của khe (cid:137) Các nút được đồng bộ (cid:137) Nếu 2 hoặc nhiều nút

1-25

truyền trong khe, mọi nút phát hiện đụng độ

(cid:137) Nếu đụng độ, nút truyền lại frame trong khe sau ngẫu nhiên tới khi thành công

Slotted ALOHA

Cons (cid:137) Đụng độ, lãng phí khe (cid:137) Các khe rỗi (cid:137) Các nút có thể có khả

Pros (cid:137) Nút kích hoạt đơn có thể liên tục truyền với tốc độ của cả kênh (cid:137) Không tập chung cao: chỉ các khe trong nút cần được đồng bộ

năng phát hiện đụng độ nhỏ hơn thời gian truyền gói tin (cid:137) Đồng bộ đồng hồ

1-26

(cid:137) Đơn giản

Hiệu suất của Slotted Aloha

(cid:137) Để tối đa hiệu suất với N nút, tìm p để tối đa Np(1-p)N-1

Hiệu suất là phần thời gian dài của các khe thành công khi có nhiều nút, mỗi nút có nhiều frame để gửi

(cid:137) Đối với nhiều nút, giới

hạn của Np*(1-p*)N-1 khi N tiến ra vô hạn bằng 1/e = 0.37

nhiều frame để gửi, mỗi nút truyền trong khe với xác suất là p

(cid:137) Giả sử có N nút với

Tốt nhất: kênh sử dụng cho việc truyền hữu ích chiếm 37% thời gian

1-27

(cid:137) Xác suất nút 1 có sự thành công trong một khe = p(1-p)N-1

(cid:137) xác suất một nút bất kỳ có sự thành công = Np(1-p)N-1

Pure (unslotted) ALOHA

(cid:129) frame gửi tại t0 đụng độ với frame khác gửi trong khoảng [t0-

(cid:137) unslotted Aloha: đơn giản, không đồng bộ (cid:137) Khi frame đầu tiên đến (cid:129) truyền ngay lập tức (cid:137) Xác suất đụng độ tăng:

1-28

1,t0+1]

Hiệu suất của Pure Aloha

P(sự thành công của một nút) = P(nút truyền) .

P(không có nút khác truyền trong

[p0-1,p0] .

P(không có nút khác truyền trong

[p0-1,p0]

= p . (1-p)N-1 . (1-p)N-1

= p . (1-p)2(N-1)

… chọn p tối ưu và cho n tiến tới vô hạn ...

= 1/(2e) = .18

1-29

CSMA (Carrier Sense Multiple Access)

CSMA: Nghe trước khi truyền: Nếu nghe thấy kênh rỗi: truyền toàn bộ frame (cid:137) Nếu nghe thấy kênh bận, tạm trì hoãn việc truyền

1-30

(cid:137) Tương tự con người: đừng ngắt lời tôi!

Đụng độ trong CSMA

Bố trí không gian của các nút

Đụng độ có thể vẫn xảy ra: Sự lan truyền độ trễ nghĩa là hai nút có thể không nghe thấy nút khác truyền

Đụng độ: toàn bộ thời gian gói tin truyền bị lãng phí

Chú ý: vai trò của khoảng cách và độ trễ lan truyền trong việc xác định xác suất đụng độ

1-31

CSMA/CD (Collision Detection)

CSMA/CD: nghe ngóng đường truyền, gọi ngắn

như CSMA (cid:129) đụng độ phát hiện trong thời gian ngắn (cid:129) truyền đụng độ bỏ qua, giảm sự lãng phí kênh

(cid:137) Phát hiện đụng độ:

(cid:129) Dễ trong mạng có dây LAN: đo độ mạnh của tín hiệu,

so sánh tín hiệu nhận, truyền

(cid:129) Khó trong mạng không dây LAN: bên nhận dừng

trong khi truyền

(cid:137) Tương tự con người: người nói chuyện lịch sự

1-32

Phát hiện đụng độ trong CSMA/CD

1-33

Giao thức MAC “Taking Turns”

Giao thức MAC kiểu chia kênh:

(cid:129) Dùng chung kênh hiệu quả và công bằng khi tải

nặng

(cid:129) không hiệu quả khi tải nhẹ: trễ khi truy cập kênh, 1/N bandwidth được cấp thậm chí chỉ có một nút kích hoạt

Giao thức MAC truy cập ngẫu nhiên

(cid:129) Hiệu quả khi tải nhẹ: một nút có thể sử dụng toàn

bộ kênh

(cid:129) Tải nặng: đụng độ cao Các giao thức “taking turns”

tốt cho cả hai trường hợp!

1-34

Giao thức MAC “Taking Turns”

Thăm dò: (cid:137) Nút chủ mời nút tớ truyền theo thứ tự

Chuyển thẻ bài: (cid:137) Điều khiển thẻ bài chuyển từ một nút tới nút tiếp theo thứ tự.

(cid:137) Xem xét:

(cid:129) overhead của thăm dò (cid:129) trễ (cid:129) một điểm lỗi (nút chủ)

(cid:129) Overhead của thẻ bài (cid:129) Độ trễ

(cid:129) Một điểm lỗi (thẻ bài)

1-35

(cid:137) Bản tin thẻ bài (cid:137) Xem xét:

Tổng kết về giao thức MAC

(cid:137) Chúng ta làm gì với phương tiện dùng

chung? (cid:129) Chia kênh theo thời gian, tần số, mã • Time Division, Frequency Division

(cid:129) Chia ngẫu nhiêu (động)

• ALOHA, S-ALOHA, CSMA, CSMA/CD • Nghe ngóng đường truyền: dễ trong một số công nghê

(có dây), khó trong một số công nghệ (không dây)

(cid:129) Taking Turns

• CSMA/CD sử dụng trong Ethernet • CSMA/CA sử dụng trong 802.11

1-36

• Thăm dò từ trung tâm, chuyển thẻ bài

Các công nghệ LAN

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

(cid:129) Các dịch vụ, phát hiện/sửa lỗi, đa truy cập

Tiếp theo: Các công nghệ LAN

(cid:129) Đánh địa chỉ (cid:129) Ethernet (cid:129) Hub, switch (cid:129) PPP

1-37

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-38

(cid:137) 5.5 Ethernet

Địa chỉ MAC và ARP

(cid:137)32 bít địa chỉ IP: (cid:129) Địa chỉ tầng mạng (cid:129) Sử dụng để chuyển datagram tới IP subnet đích (cid:137)Địa chỉ MAC (hay LAN, vật lý, Ethernet) : (cid:129) Sử dụng để chuyển datagram từ một giao diện này

tới giao diện kết nối vật lý khác (cùng mạng) (cid:129) 48 bít địa chỉ MAC (cho hầu hết các mạng LAN)

ghi trong adapter ROM

1-39

Địa chỉ LAN và ARP

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

Địa chỉ quảng bá = FF-FF-FF-FF-FF-FF

LAN

= adapter

(có dây hoặc không dây)

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

58-23-D7-FA-20-B0

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

1-40

Một adapter trong LAN có địa chỉ LAN duy nhất

Địa chỉ MAC

(để đảm bảo sự duy nhất)

(cid:137) Việc cấp địa chỉ MAC được quản lý bởi IEEE (cid:137) Các nhà sản xuất mua phần không gian địa chỉ MAC

(a) Địa chỉ MAC: giống Social Security Number (b) Địa chỉ IP: giống địa chỉ thư bưu điện

(cid:137) Sự tương tự:

(cid:129) Có thể di chuyển LAN card từ mạng LAN này tới mạng LAN

(cid:137) Địa chỉ MAC phẳng ➜ linh hoạt

khác

(cid:129) Phụ thuộc vào IP subnet mà nút nối vào

1-41

(cid:137) Địa chỉ phân cấp IP không có tính di chuyển

ARP: Address Resolution Protocol

Q: Làm thế nào để xác định địa chỉ MAC của B khi biết địa chỉ IP của B?

237.196.7.78

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

237.196.7.23

237.196.7.14

(cid:137) Mỗi nút IP (host, router) trên mạng LAN có bảng ARP

LAN

(cid:137) Bảng ARP: Ánh xạ địa chỉ IP/MAC cho một số nút trong mạng LAN < Địa chỉ IP; Địa chỉ MAC; TTL> (cid:129) TTL (Time To Live): thời

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

58-23-D7-FA-20-B0

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

237.196.7.88

1-42

gian mà ánh xạ địa chỉ có giá trị (thường là 20 phút)

Giao thức ARP

(cid:137) A ghi lại cặp địa chỉ IP-to-

(cid:137) A muốn gửi datagram tới B và địa chỉ MAC của B không trong bảng ARP của A (cid:137) Quảng bá gói tin truy vấn

MAC trong bảng ARP tới khi thông tin bị quá hạn (cid:129) Trạng thái mềm: thông

ARP, chứa địa chỉ IP của B (cid:129) Địa chỉ MAC đích = FF-

tin bị quá hạn (biến mất) trừ khi được làm mới FF-FF-FF-FF-FF

(cid:129) Mọi máy trong mạng LAN nhận được truy vấn ARP (cid:137) B nhận gói tin ARP, trả lời A

(cid:137) ARP là “plug-and-play”: (cid:129) Các nút tạo bảng ARP

của nó không có sự can thiệp từ quản trị mạng

của A (unicast)

1-43

địa chỉ MAC của nó (cid:129) frame gửi tới địa chỉ MAC

Dẫn đường tới mạng LAN khác

(cid:137) Hai bảng ARP trong router R, mỗi bảng cho một mạng LAN (cid:137) Trong bảng dẫn đường tại host nguồn, tìm router

Gửi datagram từ A tới B qua R Giả sử A biết địa chỉ IP của B

(cid:137) Trong bảng ARP tại nguồn, tìm địa chỉ MAC E6-E9-00-17-BB-

1-44

111.111.111.110

4B,…

(cid:137) A tạo datagram có địa chỉ nguồn A, địa chỉ đích B (cid:137) A sử dụng ARP để biết địa chỉ MAC của R 111.111.111.110 (cid:137) A tạo frame tầng liên kết dữ liệu, sử dụng địa chỉ MAC của R là

(cid:137) Adapter của A gửi frame (cid:137) Adapter của R nhận frame (cid:137) R lấy IP datagram từ Ethernet frame, thấy địa chỉ đích là tới B (cid:137) R sử dụng ARP để có địa chỉ MAC của B (cid:137) R tạo frame chứa IP datagram A-to-B gửi tới B

1-45

địa chỉ đích, frame chứa IP datagram A-to-B

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-46

(cid:137) 5.5 Ethernet

Ethernet

Công nghệ LAN có dây phổ biến: (cid:137) Rẻ $20 với 100Mbs! (cid:137) Công nghệ LAN đầu tiên sử dụng rộng rãi (cid:137) Đơn giản, rẻ hơn token LAN và ATM (cid:137) Có sự cạnh tranh về tốc độ : 10 Mbps – 10 Gbps

Phác thảo Ethernet của Metcalfe

1-47

Star topology

hub or switch

1-48

(cid:137) Bus topology phổ biến vào giữa những năm 90 (cid:137) Hiện nay, star topology phổ biến (cid:137) Sự lựa chọn kết nối: hub hay switch

Cấu trúc của Ethernet Frame

Adapter bên gửi đóng gói IP datagram (hoặc các gói tin

tầng mạng khác) trong Ethernet frame

Preamble: (cid:137) 7 bytes with pattern 10101010 theo sau là 1 byte với

with pattern 10101011

1-49

(cid:137) Sử dụng để đồng bộ tốc độ bên nhận, bên gửi

Cấu trúc của Ethernet Frame

(cid:129) Nếu adapter nhận frame có địa chỉ đích tương ứng hoặc với

(cid:137) Address: 6 byte

địa chỉ quảng bá (ví dụ: gói tin ARP), nó chuyển dữ liệu trong frame tới giao thức tầng mạng (cid:129) Trường hợp khác, adapter loại bỏ frame

lỗi thì frame bị loại bỏ

1-50

(cid:137) Type: chỉ ra giao thức của tầng phía trên (hầu hết là IP nhưng cũng có thể là Novell IPX hay AppleTalk) (cid:137) CRC: được kiểm tra tại bên nhận, nếu phát hiện ra

Dịch vụ không hướng kết nối, không tin cậy

bên gửi và adapter bên nhận

(cid:137) Không hướng kết nối: Không bắt tay giữa adapter

nack cho adapter bên gửi (cid:129) Luồng datagram chuyển tới tầng mạng có thể khe hở (cid:129) Các khe hở sẽ được điền đầy nếu ứng dụng sử dụng TCP (cid:129) Ngược lại, ứng dụng sẽ thấy các khe hở

1-51

(cid:137) Không tin cậy: adapter bên nhận không gửi ack hoặc

Ethernet sử dụng CSMA/CD

(cid:137) Trước khi cố gắng

truyền lại, adapter đợi một thời gian ngẫu nhiên, gọi là truy cập ngẫu nhiên (random access)

nó nghe thấy một số adapter đang truyền, gọi là nghe ngóng đường truyền (carrier sense)

(cid:137) Không slot (cid:137) Adapter không truyền nếu

1-52

(cid:137) Adapter bỏ qua truyền khi nó nghe thấy adapter khác đang truyền, gọi là phát hiện đụng độ (collision detection)

Thuật toán Ethernet CSMA/CD

4. Nếu adapter phát hiện việc

truyền khác trong khi truyền, bỏ qua và gửi tín hiệu jam

5. Sau khi bỏ qua, adapter

vào exponential backoff: sau đụng độ thứ m, adapter chọn K ngẫu nhiên từ {0,1,2,…,2m-1}. Adapter đợi K·512 bít thời gian và quay lại bước 2

1. Adaptor nhận datagram từ tầng mạng và tạo frame 2. Nếu adapter nghe ngóng thấy kênh rỗi, nó bắt đầu truyền frame. Nếu nó nghe ngóng thấy kênh bận, đợi tới khi kênh rỗi và truyền 3. Nếu adapter truyền toàn bộ frame không phát hiện thấy việc truyền khác, adapter đã xong với frame !

1-53

Ethernet CSMA/CD

Exponential Backoff: (cid:137) Mục đích: thích nghi

việc thử truyền lại, ước lượng tải hiện tại (cid:129) tải nặng: đợi ngẫu nhiên

Jam Signal: đảm bảo chắc chắn mọi bộ phát biết về đụng độ; 48 bít Bit time: .1 microsec cho 10 Mbps Ethernet; với K=1023, thời gian đợi là khoảng 50 msec

sẽ lâu hơn

(cid:137) Đụng độ đầu tiên: chọn K từ {0,1}; độ trễ là K· 512 bít thời gian truyền

1-54

(cid:137) Sau đụng độ thứ hai: chọn K từ {0,1,2,3}… (cid:137) Sau 10 đụng độ, chọn K từ {0,1,2,3,4,…,1023}

Hiệu suất của CSMA/CD

nhất

efficiency

51 t +

prop

trans

(cid:137) Tprop = xác suất lớn nhất giữa 2 nút trong LAN (cid:137) ttrans = thời gian để truyền frame có kích thước lớn

đơn giản và rẻ

1-55

(cid:137) Hiệu suất tới 1 khi tprop tiến tới 0 (cid:137) Tới 1 khi ttrans tiến tới vô hạn (cid:137) Tốt hơn nhiều ALOHA, nhưng vẫn không tập chung,

10BaseT và 100BaseT (cid:137) Tốc độ 10/100 Mbps; 100 Mbps gọi là “fast ethernet” (cid:137) T viết tắt của Twisted Pair (cid:137) Các nút kết nối tới hub: “star topology”; khoảng cách

giữa nút và hub tối đa 100m

twisted pair

hub

1-56

Hub Hub là thiết bị lặp của tầng vật lý:

(cid:129) Các bít đến từ một liên kết sẽ ra mọi liên kết khác (cid:129) Với cùng tốc độ (cid:129) Không có vùng đệm frame (cid:129) Không có CSMA/CD tại hub: adapter phát hiện

đụng độ

(cid:129) Cung cấp chức năng quản trị mạng

twisted pair

hub

1-57

Mã Manchester

tại nút kia (cid:129) Không cần có trung tâm, đồng hồ chung giữa các nút!

(cid:137) Sử dụng 10BaseT (cid:137) Mỗi bít có một transition (cid:137) Cho phép đồng hồ trong nút gửi và nhận để đồng bộ

1-58

(cid:137) Xét ở tầng vật lý!

Gbit Ethernet

dùng chung

(cid:137) Sử dụng định dạng Ethernet frame chuẩn (cid:137) Cho phép liên kết point-to-point và kênh quảng bá

(cid:137) Trong chế độ dùng chung, sử dụng CSMA/CD; giữa các nút đòi hỏi khoảng cách ngắn để có hiệu quả

1-59

(cid:137) Sử dụng hub, gọi là “Buffered Distributors” (cid:137) Full-Duplex tại 1 Gbps cho liên kết point-to-point (cid:137) Hiện tại, 10 Gbps!

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

dịch vụ

(cid:137) 5.1 Giới thiệu và các (cid:137) 5.6 Hub và switch

truy cập

(cid:137) 5.2 Phát hiện và sửa lỗi (cid:137) 5.3 Các giao thức đa

liên kết dữ liệu

(cid:137) 5.4 Đánh địa chỉ tầng

1-60

(cid:137) 5.5 Ethernet

Kết nối với hub

vùng đụng độ lớn

(cid:137) Backbone hub kết nối các LAN segments (cid:137) Mở rộng khoảng cách tối đa giữa các nút (cid:137) Nhưng các vùng đụng độ của riêng segment trở thành

hub

1-61

(cid:137) Không thể kết nối 10BaseT và 100BaseT

Switch

dựa trên địa chỉ đích MAC

(cid:129) Khi frame được chuyển tiếp trên segment, sử

dụng CSMA/CD để truy cập segment

(cid:137) Thiết bị thực hiện tầng liên kết dữ liệu (cid:129) Lưu và chuyển tiếp Ethernet frames (cid:129) Kiểm tra frame header và chọn chuyển tiếp frame

(cid:129) Host không biết về sự tồn tại của switch

(cid:137) Trong suốt

(cid:129) Switch không cần phải cấu hình

1-62

(cid:137) plug-and-play, tự học

Chuyển tiếp

switch

hub

• Cách xác định chuyển tiếp frame đến LAN segment nào? • Giống bài toán dẫn đường...

1-63

Tự học

(cid:129) (MAC Address, Interface, Time Stamp) (cid:129) Các entry cũ trong bảng sẽ bị xóa đi (TTL có thể 60

phút)

(cid:137) Switch có bảng switch (cid:137) Entry trong bảng switch:

(cid:129) Khi nhận frame, switch học vị trí của địa chỉ gửi:

incomming LAN segment

(cid:129) Ghi cặp địa chỉ gửi/vị trí trong bảng switch

1-64

(cid:137) Switch học host nào có thể tới qua interface nào

Lọc/Chuyển tiếp

Khi switch nhận một frame:

Chỉ số bảng switch sử dụng địa chỉ MAC đích if thấy entry cho đích

then{ if đích trong segment mà frame đến

then Loại bỏ frame else Chuyển tiếp frame trên interface chỉ định

}

else Làm tràn

Chuyển tiếp trên tất cả interface trừ interface mà frame đã tới

1-65

Ví dụ Switch

Giả sử C gửi frame tới D

address interface

switch

hub

1 1 2 3

A B E G

hub

(cid:129) Ghi vào bảng switch là C trên interface 1 (cid:129) Bởi vì D không trong bảng, switch chuyển tiếp frame qua

(cid:137) Switch nhận frame từ C

interface 2 và 3

1-66

(cid:137) frame được nhận bởi D

Ví dụ Switch

Giả sử D gửi frame trả lời C

address interface

switch

hub

1 1 2 3 1

A B E G C

(cid:129) Ghi vào bảng switch là D ở trên interface 2 (cid:129) Bởi vì C có trong bảng, switch chuyển tiếp frame chỉ tới

(cid:137) Switch nhận frame từ D

interface 1

1-67

(cid:137) frame được nhận bởi C

Switch: cô lập lưu lượng

(cid:129) Frame cùng LAN-segment thường không chuyển

tiếp trên LAN segment khác

(cid:129) Segment được phân tách các vùng đụng độ

switch

vùng đụng độ

hub

vùng đụng độ

1-68

vùng đụng độ

(cid:137) Cài đặt switch chia subnet thành các LAN segment (cid:137) Switch lọc gói tin:

Switch: truy cập dành riêng

C’

tới switch

(cid:137) Switch có nhiều interface (cid:137) Các host có kết nối trực tiếp

switch

Switching: A-to-A’ và B-to-B’ đồng thời, không đụng độ

B’

A’

1-69

(cid:137) Không đụng độ; full duplex

Một số thông tin khác về Switch

(cid:137) cut-through switching: frame chuyển tiếp từ input port tới output port không chờ nhận đủ frame (cid:129)Giảm một chút về độ trễ (latency) (cid:137) Sự kết của dùng chung/dành riêng,

10/100/1000 Mbps interface

1-70