Tài liệu Mạng máy tính - Chương 5: Giao thức tầng liên kết dữ liệu (data link) - Trần Quang Diệu: Chương 5.
Giao thức tầng liên kiết dữ liệu (data link)
Quang Dieu Tran, PhD
Faculty of Information Technology
University of Communication and Transport (Branch in
Ho Chi Minh City)
Email: dieutq@gmail.com
Website: sites.google.com/sites/tranlectures
Chương 5. Tầng liên kết dữ liệu 2
Ch5. Giao thức tầng liên kết dữ liệu
5.1 - Introduction and services
5.2 - Error detection and correction
5.3 - Multiple access protocols & LAN
5.4 - Link-layer addressing & ARP
5.5 - Specific link layer technologies
17/01/2018
Chương 5. Tầng liên kết dữ liệu 3
Introduction & services
17/01/2018
Chương 5. Tầng liên kết dữ liệu 4
Data Link
Data link: Liên kết dữ
liệu; tầng 2.
PDU: frame.
packet nhiều frame
Nhiệm vụ của tầng data
link là truyền các các
packet (datagram) từ nút
này tới nút khác.
“link”
17/01/2018
Chương 5. Tầng liên kết dữ liệu 5
Data Link & frame
Link:
router-router; host-host; router-host
frame: dữ liệu của tầng data link
application
t...
45 trang |
Chia sẻ: putihuynh11 | Lượt xem: 1208 | Lượt tải: 2
Bạn đang xem trước 20 trang mẫu tài liệu Mạng máy tính - Chương 5: Giao thức tầng liên kết dữ liệu (data link) - Trần Quang Diệu, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Chương 5.
Giao thức tầng liên kiết dữ liệu (data link)
Quang Dieu Tran, PhD
Faculty of Information Technology
University of Communication and Transport (Branch in
Ho Chi Minh City)
Email: dieutq@gmail.com
Website: sites.google.com/sites/tranlectures
Chương 5. Tầng liên kết dữ liệu 2
Ch5. Giao thức tầng liên kết dữ liệu
5.1 - Introduction and services
5.2 - Error detection and correction
5.3 - Multiple access protocols & LAN
5.4 - Link-layer addressing & ARP
5.5 - Specific link layer technologies
17/01/2018
Chương 5. Tầng liên kết dữ liệu 3
Introduction & services
17/01/2018
Chương 5. Tầng liên kết dữ liệu 4
Data Link
Data link: Liên kết dữ
liệu; tầng 2.
PDU: frame.
packet nhiều frame
Nhiệm vụ của tầng data
link là truyền các các
packet (datagram) từ nút
này tới nút khác.
“link”
17/01/2018
Chương 5. Tầng liên kết dữ liệu 5
Data Link & frame
Link:
router-router; host-host; router-host
frame: dữ liệu của tầng data link
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys. link
data link
protocol
17/01/2018
Chương 5. Tầng liên kết dữ liệu 6
Các dịch vụ của tầng data link
Đóng frame và truy cập đường truyền (framing,
link access)
đóng gói tin vào các frame
truy nhập đường truyền (đường truyền dùng chung cần
có quy tắc truy nhập)
địa chỉ vật lý (physical addr) được sử dụng.
Truyền tin cậy (reliable delivery): rdt.
đảm bảo các gói tin của tầng mạng không bị lỗi.
tuỳ thuộc chất lượng đường truyền.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 7
Các dịch vụ của tầng data link (cont)
Flow control (điều khiển lưu lượng!!!)
đảm bảo lưu lượng truyền hợp lý, nút nhận không bị quá tải
Error detection
lỗi có thể phát sinh do nhiễu, tín hiệu yếu
nút nhận phát hiện lỗi, bỏ qua hoặc yêu cầu nút gửi gửi lại.
Error correction
nút nhận xác định bit bị lỗi và sửa lỗi.
Half-duplex and Full-duplex
half-duplex: các nút không thể truyền nhận đồng thời.
full-duplex: các nút có thể truyền nhận đồng thời.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 8
Implementation
Link layer được thực thi tại network adapter (NIC – Network
Interface Card):
NIC = RAM + DSP chips + host bus interface + link
interface
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys. link
data link
protocol
adapter card
17/01/2018
Chương 5. Tầng liên kết dữ liệu 9
Ch5. Giao thức tầng liên kết dữ liệu
5.1 - Introduction and services
5.2 - Error detection and correction
5.3 - Multiple access protocols & LAN
5.4 - Link-layer addressing & ARP
5.5 - Specific link layer technologies
17/01/2018
Chương 5. Tầng liên kết dữ liệu 10
Error detection and correction
D = Data
EDC= Error Detection and Correction bits
Bits thêm vào với mục đích kiểm soát lỗi.
Số lượng bit càng cao thì khả năng kiểm soát lỗi càng tốt.
Error detection: không phải lúc nào cũng phát hiện được lỗi!
17/01/2018
Chương 5. Tầng liên kết dữ liệu 11
Parity
Parity: cân bằng!!! (chẵn lẻ).
Parity chẵn (even parity)
tổng số các bit 1 (bao gồm cả bit parity) là chẵn.
vd: parity của 101010101 là 1 (tổng số bit 1 = 5+1).
parity bit = (số bit 1 của data là lẻ) ? 1 : 0
Parity lẻ (odd parity):
tổng số các bit 1 (bao gồm cả bit parity) là lẻ.
vd: parity của 101010101 là 0 (tổng số bit 1 = 5).
parity bit = (số bit 1 của data là chẵn)? 1:0
17/01/2018
Chương 5. Tầng liên kết dữ liệu 12
Parity checking
Single Bit Parity:
Detect single bit errors
Two Dimensional Bit Parity:
Detect and correct single bit errors
0 0
17/01/2018
Parity checking (cont.)
Biết rằng đơn vị dữ liệu sau khi thêm bit kiểm tra là
7. Hãy tính ma trận kiểm tra chẵn lẻ hai chiều của
chuỗi ký tự “SING”
Giải: các ký tự trong chuỗi có mã 83-73-78-71
Chương 5. Tầng liên kết dữ liệu 1317/01/2018
0 1 0 1 0 0 0
1 1 0 1 0 0 1
1 0 0 1 0 1 1
0 0 1 1 1 0 1
0 1 0 0 0 1 0
1 1 0 0 0 0 0
1 0 1 0 1 0 1
Chương 5. Tầng liên kết dữ liệu 14
Internet Checksum
Sender:
Coi segment là một dãy các
số nguyên 16 bit
checksum: tổng bù 1của các
số 16-bit có segment
Sender chèn giá trị tổng bù 1
trên vào trường checksum
trong UDP
Receiver:
Tính checksum của segment
nhận được
So sánh giá trị tính được với
giá trị tại trường checksum:
NO – Có lỗi
YES – Không có lỗi.
nhưng vẫn có thể có lỗi?
.
Goal: Phát hiện “errors” (vd: đảo bit) trong quá trình
truyền/nhận các segment (lưu ý: chỉ dùng ở tầng transport)
17/01/2018
Chương 5. Tầng liên kết dữ liệu 15
CRC – Cyclic Redundancy Check
Data = d bits dữ liệu (D).
Sender chọn r+1 bit sinh (G - generator).
Chọn r CRC bits (R) sao cho:
DR chia hết cho G (modulo 2)
DR = D*2r XOR R. (= (D << r ) XOR R)
receiver: nhận D’R’; biết trước G; chia D’R’ cho G, nếu phép chia có dư có
lỗi.
có thể phát hiện lỗi <= r bit.
CRC được sử dụng rộng rãi trong thực tế.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 16
Phép tính modulo 2
Phép tính modulo N:
K/quả modulo N = kết quả bình thường mod N.
Vd: 5+9 (mod 4) = 14 mod 4 = 2.
Phép tính modulo 2 với số nhị phân:
Thực hiện với từng bit.
1+1 (mod 2) = 0; 1+0 (mod 2) = 1 (không nhớ!!!)
1-0 (mod 2) = 0 – 1 (mod 2) = 1
Với hai số nhị phân b1 và b2 (cộng không nhớ):
b1 + b2 = b2 + b1 = b1 XOR b2
17/01/2018
Chương 5. Tầng liên kết dữ liệu 17
CRC Example
Biết: D,G. Tìm R?
DR chia hết cho G (mod 2) nghĩa là:
D.2r XOR R = nG
=> D.2r = nG XOR R
Do vậy:Nếu chia D.2r cho G, phần
dư sẽ là R
R = remainder[ ]
D.2r
G
17/01/2018
Chương 5. Tầng liên kết dữ liệu 18
Ch5. Giao thức tầng liên kết dữ liệu
5.1 - Introduction and services
5.2 - Error detection and correction
5.3 - Multiple access protocols & LAN
5.4 - Link-layer addressing & ARP
5.5 - Specific link layer technologies
17/01/2018
Chương 5. Tầng liên kết dữ liệu 19
Multiple Access
Hai loại “links”:
point-to-point
PPP (dial-up access: kết nối Internet tại nhà qua modem)
point-to-point link giữa Ethernet switch và host
broadcast (chia sẻ: shared wire or medium)
Radio; Bus LAN;
802.11 wireless LAN
17/01/2018
Chương 5. Tầng liên kết dữ liệu 20
MAP: Multiple Access Protocols
Các nút mạng dùng chung một đường truyền.
Có lúc nhiều nút mạng cùng muốn truyền dữ liệu.
xung đột (collision).
chỉ có một nút truyền thành công!!!
Multiple Access Protocol (MAP):
các quy tắc quy định việc sử dụng đường truyền chung
giữa các nút mạng.
Human MAP examples:
Class: đôi khi SV mất trật tự xung đột (collision).
Cocktail party: multiple languages
17/01/2018
Chương 5. Tầng liên kết dữ liệu 21
Ideal Mulitple Access Protocol
Đường truyền có tốc độ (rate) = R
Khi một nút muốn truyền, tốc độ là R.
Khi M nút muốn truyền, tốc độ TB là R/M.
Điều khiển truy nhập phân tán:
không cần một nút đặc biệt để điều khiển (các nút tự
điều khiển).
không cần các tín hiệu đồng bộ
Đơn giản.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 22
MAP: taxonomy (phân loại)
Channel partitioning (phân mảnh kênh truyền)
kênh truyền được chia thành các “miếng” nhỏ (theo thời gian, tần
số, code).
mỗi “miếng” sẽ được một nút dùng riêng không xung đột
(collision).
Random access (truy nhập ngẫu nhiên)
nút nào muốn truyền, ngẫu nhiên truy cập kênh truyền có khả
năng xung đột; xử lý xung đột?
Taking turns (truy nhập lần lượt)
các nút phối hợp chặt chẽ trong việc sử dụng đường truyền
không xung đột.
Goal: efficient, fair, simple, decentralized
17/01/2018
Chương 5. Tầng liên kết dữ liệu 23
Channel Partitioning MAP: TDMA
TDMA: time division multiple access
Các nút được lần lượt truy cập đường truyền trong
khoảng thời gian xác định (time slot).
Không phải nút nào cũng muốn truyền: unused slot
(idle slot).
Vd: 6 slots, 3 idle do nút 2,5,6 không có nhu cầu.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 24
Channel Partitioning MAP: TDMA
FDMA: frequency division multiple access
Phổ của kênh truyền được chia thành nhiều dải tần.
Mỗi dải tần dành riêng cho một nút.
Như vậy, nút không có nhu cầu truyền thì dải tần
dành cho nó bị lãng phí (unused, idle).
Vd: 2,5,6 idle
f
re
q
u
e
n
c
y
b
a
n
d
s
17/01/2018
Chương 5. Tầng liên kết dữ liệu 25
Channel Partitioning MAP: CDMA
CDMA (Code Division Multiple Access)
Mỗi nút được xác định bởi mã duy nhất (code).
Tất cả các nút sử dụng chung tần số nhưng lại có
mã riêng (CQ - chipping sequence) để mã hoá và
giải mã dữ liệu.
encoded signal = (data) X (CQ)
decoding: tích trong của encoded signal và CQ.
Sử dụng chủ yếu trong mạng wireless (cellular,
satellite).
17/01/2018
Chương 5. Tầng liên kết dữ liệu 26
CDMA example: encode/decode
17/01/2018
Chương 5. Tầng liên kết dữ liệu 27
CDMA example: two-sender interference
sender 1
sender 2
17/01/2018
Chương 5. Tầng liên kết dữ liệu 28
Random Access Protocols
Khi nút muốn truyền:
truy nhập đường truyền và truyền với tốc độ R
không có chế độ ưu tiên cho nút nào cả.
Nếu nhiều nút cùng truyền xung đột.
cần có cơ chế phát hiện xung đột (collision detection).
khôi phục khi có xung đột (recovery): chờ một lúc rồi
truyền lại
Một số giao thức:
slotted ALOHA, ALOHA.
CSMA, CSMA/CD.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 29
Slotted ALOHA
Chia thành các khoảng thời gian (time slot) = thời
gian cần để truyền một frame.
Nút luôn bắt đầu truyền từ thời điểm bắt đầu slot.
Nếu xung đột, sẽ truyền lại frame tại thời điểm bắt
đầu slot tiếp theo với xác suất p chọn trước.
Success (S), Collision (C), Empty (E) slots
VD
At best: channel
use for useful
transmissions 37%
of time!
17/01/2018
Chương 5. Tầng liên kết dữ liệu 30
CSMA (Carrier Sense Multiple Access)
Carrier Sense:
lắng nghe trước khi truyền.
Nếu kênh truyền rỗi thì truyền toàn bộ frame.
Nếu kênh truyền bận, tuỳ cơ ứng biến:
thử lại ngay lập tức với xác suất p cho tới khi kênh
truyền rỗi.
thử lại sau một khoảng thời gian ngẫu nhiên.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 31
CSMA collisions
space:
khoảng cách giữa các
nút.
time: thời gian.
Xung đột vẫn có thể xảy
ra nếu trong khoảng
thời gian t1-t0 tín hiệu
chưa lan truyền được từ
B tới D.
Lãng phí!, cần cơ chế
phát hiện xung đột.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 32
CSMA/CD (Collision Detection)
CSMA/CD:
nghe trước khi truyền.
dò xung đột trong một khoảng thời gian ngắn (đủ lớn).
nếu phát hiện xung đột thì dừng truyền để tránh lãng
phí.
Phát hiện xung đột:
wired LAN: đo hiệu điện thế.
wireless: ???
17/01/2018
Chương 5. Tầng liên kết dữ liệu 33
CSMA/CD: example
17/01/2018
Chương 5. Tầng liên kết dữ liệu 34
“Taking Turns” MAP
Channel partitioning MAP:
hiệu quả khi nhiều nút cùng sử dụng
ngược lại, gây lãng phí khi chỉ có vài nút cần truyền tin.
Random Access MAP:
hiệu quả khi ít nút sử dụng: một nút có thể toàn quyền
sử dụng đường truyền với tốc độ cao nhất.
nhiều nút cùng sử dụng: xung đột.
Taking turns:
Tìm kiếm giải pháp tốt cho cả hai tình huống.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 35
“Taking Turns” MAP: Polling & Token passing
Polling
Có một nút điều khiển (master)
có nhiệm vụ:
lần lượt “thông báo” cho các nút
khác biết đến lượt truyền và được
phép truyền tối đa một số lượng
frame nào đó.
khi một nút kết thúc truyền,
master thông báo cho nút khác.
Không xung đột.
Vấn đề:
mất thời gian thông báo: tốc độ
trung bình < R.
khi master gặp sự cố thì cả mạng
ngừng hoạt động!
Token passing
Thẻ bài (token) là một thông
báo đặc biệt mà nút nào nắm
giữ nó sẽ được phép sử dụng
đường truyền.
Thẻ bài được luân chuyển giữa
các nút.
Vấn đề:
Một nút gặp sự cố ảnh hưởng tới
toàn mạng.
nút nào đó sao nhãng việc chuyển
thẻ bài cho nút khác cần một
vài thủ tục để khôi phục.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 36
LAN
MAP được sử dụng rộng rãi:
satellite, wireless
LAN (Local Area Network).
LAN:
Mạng nội bộ, có phạm vi hẹp (toàn nhà, trường ĐH)
Vd: LAN kết nối Internet
chia sẻ đường truyền.
Các loại LAN:
Ethernet: phổ biến, sử dụng Random Access MAP.
FDDI (Fiber Distributed Data Interface): Token-passing.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 37
Ch5. Giao thức tầng liên kết dữ liệu
5.1 - Introduction and services
5.2 - Error detection and correction
5.3 - Multiple access protocols & LAN
5.4 - Link-layer addressing & ARP
5.5 - Specific link layer technologies
17/01/2018
Chương 5. Tầng liên kết dữ liệu 38
Link layer address
32-bit IP address:
network-layer address
IP được đóng trong các gói tin (nguồn, đích).
LAN (or MAC or physical) address:
48 bit (6 bytes) MAC address (đối với hầu hết LANs)
được ghi trong adapter ROM
*MAC: Media Access Control (Link layer = MAC + LLC
(Logical Link Control)
17/01/2018
Chương 5. Tầng liên kết dữ liệu 39
LAN Addresses and ARP
Mỗi adapter có một địa chỉ vật lý duy nhất, tương tự như số CMTND.
Broadcast address =
FF-FF-FF-FF-FF-FF
= adapter
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
(wired or
wireless)
17/01/2018
Chương 5. Tầng liên kết dữ liệu 40
MAC address (cont)
Địa chỉ vật lý được phân bổ bởi IEEE.
Nhà sản xuất phải đăng ký dải địa chỉ với IEEE.
Khi di chuyển từ mạng này sang mạng khác: địa
chỉ IP thay đổi nhưng địa chỉ vật lý không thay đổi.
So sánh:
địa chỉ vật lý: số CMTND.
địa chỉ IP: địa chỉ hòm thư.
Các frame muốn gửi tới đích thì cần chứa địa chỉ
vật lý của nút đích.
17/01/2018
Chương 5. Tầng liên kết dữ liệu 41
When packet sent from A to B
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
B
E
A gửi packet tới B, A sẽ:
Tra cứu địa chỉ mạng của B,
phát hiện ra B cùng mạng với A
link layer gửi packet tới B thông
qua frame.
B’s MAC
addr
A’s MAC
addr
A’s IP
addr
B’s IP
addr
IP payload
datagram
frame
frame source,
dest address
packet source,
dest address
17/01/2018
Chương 5. Tầng liên kết dữ liệu 42
ARP: Address Resolution Protocol
Mỗi nút mạng (Host,
Router) đều có ARP
table
ARP Table: cho phép từ
IP tra cứu ra MAC addr
Cấu tạo bản ghi:
TTL (Time To Live):
thời gian tồn tại của bản
ghi tới khi bị xoá.
???: Làm thế nào để
biết địa chỉ vật lý của B khi
biết IP của B?
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
237.196.7.23
237.196.7.78
237.196.7.14
237.196.7.88
17/01/2018
Chương 5. Tầng liên kết dữ liệu 43
Trường hợp chưa biết MAC addr của nút
Nếu A muốn biết MAC addr của B (không có trong
ARP table)
A đã biết IP của B (ipb).
A gửi ARP query packet tới tất cả các nút (broadcast),
trong đó có chứa IP của B (ipb) hỏi xem nút nào có
địa chỉ IP là ipb.
Tất cả các nút đều nhận được và kiểm tra xem ipb có
trùng với IP của mình không, nếu trùng thì trả lời (nút
B).
17/01/2018
Chương 5. Tầng liên kết dữ liệu 44
Trường hợp hai nút ở hai mạng khác nhau
A (111.111.111.111) muốn gửi tin tới B (222.222.222.222)
A không biết MAC addr của B, nếu gửi ARP pkt hỏi
LAN1 không có nút nào trả lời.
A
R
B
17/01/2018
Chương 5. Tầng liên kết dữ liệu 45
A tạo IP packet với địa chỉ IP gửi = A, và địa chỉ IP nhận = B
A dùng ARP để xác định MAC của R ứng với interface 111.111.111.110
A tạo frame với dest. MAC = MAC của R, frame này chứa IP
datagram từ A đến B.
A’s data link layer sends frame
R’s data link layer receives frame
R lấy IP datagram khỏi frame, và coi đích đến là B
R dùng ARP lấy địa chỉ MAC của B
R tạo frame chứa IP datagram A-to-B IP rồi gửi đến B
A
R
B
17/01/2018
Các file đính kèm theo tài liệu này:
- mang_may_tinh_chapter5a_7099_135_1995536.pdf