Bài giảng Truyền số liệu - Chương V: Các nghi thức cơ cở

Bài giảng Truyền số liệu 
Chương 5: Các nghi thức cơ cở 
GV: Nguyen Tam Hien 
9/2012 
Nội dung 
Idle ARQ 5.2 
Continuous ARQ 5.3 
Kiểm soát lỗi 5.1 
Nội dung 
Idle ARQ 5.2 
Continuous ARQ 5.3 
Kiểm soát lỗi 5.1 
Kiểm soát lỗi 
 Khi truyền dữ liệu từ phía phát tới phía thu thì thông 
thường phía thu sẽ kiểm tra các khung nhận được và trả 
về phía phát một thông điệp để xác nhận là đã nhận 
đúng hoặc là yêu cầu gửi một bản sao khác 
 Loại kiểm soát lỗi như vậy gọi là ARQ (Automatic 
Repeat Request) 
 ARQ có hai loại 
 Idle RQ 
 Continuous RQ (RQ liên tục) 
Nội dung 
Idle ARQ 5.2 
Continuous ARQ 5.3 
Kiểm soát lỗi 5.1 
Idle RQ 
 Phía gửi (nguồn) : Primary hay Sender 
 Phía nhận (đích): Secondary hay Receiver 
 Khung dữ liệu: I-frame 
 Khung giám sát: ACK, NACK frame 
 Có 2 cách thực hiện nguyên lý này: 
 Stop and wait ARQ hiểu ngầm 
 Stop and wait ARQ tường minh 
Stop and Wait ARQ 
 Việc truyền lại được hiểu ngầm: phía thu 
chỉ xác nhận khung truyền nào nhận đúng 
và nếu phía thu không xác nhận thì phía 
phát phải tự hiểu ngầm là có một khung 
truyền sai hay mất 
 Phía phát (Primary- P) phát một frame tại 
một thời điểm 
 Nếu phía thu (Secondary - S) nhận đúng 
thì trả về một ACK- frame 
Stop and Wait ARQ 
 Nếu P nhận đúng một ACK- frame thì sẽ 
phát một khung kế tiếp 
 Khi P truyền một frame nó sẽ bắt đầu đếm 
thời gian và chờ 
 Nếu bộ đếm thời gian kết thúc trước khi P 
nhận được ACK- frame thì P sẽ phát lại 
khung cũ 
 Nếu một khung ACK bị lỗi hay mất thì S sẽ 
nhận một bản sao khác và S tự động loại 
bỏ 
Stop and Wait ARQ 
 Các trường hợp có thể xảy ra 
 Hoạt động bình thường 
 Mất khung dữ liệu (I-frame) 
 Mất khung ACK (ACK- frame) 
 Khung ACK tới trễ 
Trường hợp bình thường 
• Sender seõ khoâng göûi 
khung tieáp theo neáu 
khoâng chaéc chaén 
khung tröôùc ñoù nhận 
được ñuùng. 
• Soá tuaàn töï caàn thieát ñeå 
kieåm tra khung nhaän 
ñöôïc laø môùi hay cuõ. 
• ACK – khi khung 
ñuùng vaø NACK - khi 
khung hoûng. 
 10 
Mất khung dữ liệu hay khung dữ liệu hỏng 
11 
Treã khöù hoài 
Xöû lyù taïi ñaàu thu 
Mất ACK-frame 
12 
Taàm quan 
troïng cuûa vieäc 
ñaùnh soá 
ACK-frame tới trễ 
13 
Taàm quan 
troïng cuûa vieäc 
ñaùnh soá ACK 
Stop and Wait ARQ hiểu ngầm và tường 
minh 
• Loãi khung (Data bò sai) 
– Söû duïng NACK ñeå caûi tieán hieäu suaát. NACK ñöôïc thu tröôùc 
khi heát timeout. 14 
Stop and wait tường minh (có NACK) Stop and wait hiểu ngầm (không có 
NACK 
F1 
F0 
X 
ACK1 
F1 
F0 
X 
ACK1 
Timeout 
expired 
NACK1 
F1 
ACK0 
F0 
ACK1 
F1 
ACK0 
F1 
ACK0 
F0 
ACK1 
Duplex Stop-and-Wait 
• Keát hợp 
– Keát hôïp data với ACK (giaûm overhead & tieát kieäm BW) 
15 
Caáu truùc caùc loaïi khung 
16 
Haïn cheá cuûa Stop-and-Wait ARQ 
• Sau moãi moät khung göûi ñi, Host phaûi chôø 1 ACK 
– Khoâng hieäu quaû söû duïng bandwidth 
• Ñeå caûi thieän hieäu quaû, ACK neân ñöôïc göûi sau moät soá 
khung, goïi laø Continuous ARQ. 
. 
17 
Nội dung 
Idle ARQ 5.2 
Continuous ARQ 5.3 
Kiểm soát lỗi 5.1 
Continous ARQ 
• P gửi liên tục các I-frame không cần chờ ACK-frame 
• P duy trì một bản sao các I-frame trong một danh mục truyền lại 
hoạt động theo nguyên tắc FIFO 
• S trả về một ACK-frame mỗi khi nhận được một khung 
đúng 
• Mỗi I-frame chứa một định danh duy nhất sẽ được trả về trong các 
ACK tương ứng 
• S duy trì một danh mục theo thứ tự tức danh sách thu 
gồm n khung thu tốt sau cùng 
• P sẽ loại bỏ các I-frame sau khi nhận được các ACK-frame tương 
ứng 
. 
19 
Continous ARQ 
• 2 loại Continuous ARQ (Sliding Window protocols): 
1. Go-back-N ARQ 
2. Selective Repeat ARQ 
• Loại Go-back- N, S phát hiện việc nhận không 
đúng thứ tự của P và yêu cầu P truyền lại tất cả các 
khung từ khung cuối cùng thu tốt cho đến khi khôi 
phục lại được khung truyền đúng thứ tự bị mất 
• Loại Selective Repeat ARQ, S phát hiện và yêu cầu truyền lại 
chỉ những khung nào bị sai 
. 
20 
Sliding Window Protocols 
• Số tuần tự 
– Các khung phát được đánh số tuần tự 
– Số tuần tự của khung được lưu ở header của khung 
• Nếu số bit trong header là m thì số tuần tự đếm từ 0 đến 2m-
1 
• Cửa sổ trượt 
– Để giữ các khung chưa 
 báo phát 
– Kích thước cửa sổ nhận 
 luôn là 1 
21 
sequence 
number 
frame 
acknowledged 
frames 
Go-back-N 
• S- chæ soá tuaàn töï cuûa khung ñang ñöôïc phaùt 
• SF – chæ soá tuaàn töï cuûa khung ñaàu tieân trong cöûa soå 
• SL – chæ soá tuaàn töï cuûa khung cuoái cuøng trong cöûa soå 
• R – chæ soá tuaàn töï cuûa khung ñang chôø thu 
22 
Tại sao có tên Go-back-N? 
• Phaùt laïi khung 
– Khi moät khung bò hoûng, ñaàu phaùt seõ quay laïi 
vaø phaùt laïi moät taäp hôïp caùc khung tính töø 
khung khoâng coù baùo phaùt (ACK) 
– Soá löôïng khung ñöôïc phaùt laïi laø N 
Ví dụ: 
 Kích thước cửa laø 4. 
 Ñaàu phaùt vöøa phaùt khung 6 vaø heát thôøi 
gian ñeám khung 3 (khung 3 khoâng coù 
ACK). Ñaàu phaùt seõ phaùt laïi caùc khung 3, 4, 
5, 6. 23 
Go-back-N – trường hợp bình thường- 
• Coù bao nhieâu 
khung có theå 
phaùt maø 
khoâng chôø 
ACK? 
• ACK1 – khoâng 
caàn thieát neáu 
ACK2 ñöôïc 
phaùt ñi. 
24 
expected sequence 
number 
Go-back-N - mất khung hoặc lỗi khung- 
25 
Caùc khung hoûng bò 
loaïi boû! 
Taïi sao caùc khung 
vaãn được thu ñuùng 
thöù töï tuy khoâng 
coù boä ñeäm? 
Nhöôïc ñieåm cuûa 
phöông phaùp naøy 
laø gì? 
Go-back-N – kích thước cửa sổ gửi- 
26 
sequence 
number 
 Nhược điểm của Go-back-N 
• Khoâng hieäu quaû 
– Taát caû caùc khung khoâng ñuùng thöù töï ñeàu phaûi phaùt laïi 
• Neáu lieân keát coù taïp aâm seõ gaây ra vaán ñeà: 
– Nhieàu khung phaûi phaùt laïi -> toán bandwidth 
• Giaûi phaùp 
– Chæ phaùt laïi nhöõng khung hoûng 
• Selective Repeat ARQ 
– Choáng laïi vieäc phaùt laïi khoâng caàn thieát 
27 
Selective Repeat ARQ 
• Xöû lyù taïi ñaàu thu phöùc taïp hôn 
• Kích thöôùc cöûa soå giaûm xuoáng <= 2m-1 
• Ñaàu phaùt vaø ñaàu thu coù kích thöôùc cuûa 
soå nhö nhau 
• Ñaàu thu chôø thu moät taäp hôïp khung 
trong moät phaïm vi cuûa soá tuaàn töï 
28 
Selective Repeat ARQ – mất khung- 
29 
Selective Repeat ARQ-kích thước cửa sổ gửi- 
30