Tài liệu Đề tài Tìm hiểu kỹ thuật kiểm soát lỗi ARQ: 1
TRƯỜNG ðH TễN ðỨC THẮNG
KHOA ðIỆN-ðIỆN TỬ
NHIỆM VỤ ðỒ ÁN 2
KHOA : ðIỆN-ðIỆN TỬ
NGÀNH: ðIỆN TỬ VIỄN THễNG
GIÁO VIấN HƯỚNG DẪN: TS. HOÀNG THU HÀ
SINH VIấN THỰC HIỆN: HỒ THANH TÀI MSSV:910512D
NGUYỄN NAM VŨ MSSV:
ðỀN TÀI: TèM HIỂU KỸ THUẬT KIỂM SOÁT LỖI ARQ
Nhận xột của giỏo viờn hướng dẫn:
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
Ngày thỏng năm 2009
(ký tờn)
2
Mục lục:
Lời núi ủầu 3
PHẦN I CƠ SỞ Lí THUYẾT VỀ KIỂM SOÁT LỔI 4
I )HỆ THỐNG THễNG TÍN SỐ 4
II) CÁC PHƯƠNG PHÁP PHÁT HIỆN LỖI 5
II.1 Phương phỏp truyền phản hồi 6
II.2 Phương phỏp truyền dư thừa 7
II.3 Phương phỏp kiểm tra chẳn lẽ 7
II.4 Phương phỏp CRC 8
II.5 Phương phỏp...
32 trang |
Chia sẻ: hunglv | Lượt xem: 3508 | Lượt tải: 2
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài Tìm hiểu kỹ thuật kiểm soát lỗi ARQ, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
1
TRƯỜNG ðH TƠN ðỨC THẮNG
KHOA ðIỆN-ðIỆN TỬ
NHIỆM VỤ ðỒ ÁN 2
KHOA : ðIỆN-ðIỆN TỬ
NGÀNH: ðIỆN TỬ VIỄN THƠNG
GIÁO VIÊN HƯỚNG DẪN: TS. HỒNG THU HÀ
SINH VIÊN THỰC HIỆN: HỒ THANH TÀI MSSV:910512D
NGUYỄN NAM VŨ MSSV:
ðỀN TÀI: TÌM HIỂU KỸ THUẬT KIỂM SỐT LỖI ARQ
Nhận xét của giáo viên hướng dẫn:
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
Ngày tháng năm 2009
(ký tên)
2
Mục lục:
Lời nĩi đầu 3
PHẦN I CƠ SỞ LÝ THUYẾT VỀ KIỂM SỐT LỔI 4
I )HỆ THỐNG THƠNG TÍN SỐ 4
II) CÁC PHƯƠNG PHÁP PHÁT HIỆN LỖI 5
II.1 Phương pháp truyền phản hồi 6
II.2 Phương pháp truyền dư thừa 7
II.3 Phương pháp kiểm tra chẳn lẽ 7
II.4 Phương pháp CRC 8
II.5 Phương pháp kiểm tra tổng khối 9
III LỖI DỮ LIỆU KÊNH TRUYỀN 11
PHẦN II KỶ THUẬT KIỂM SỐT LỔI ARQ 12
I )ðẶC ðIỂM ARQ 12
I.1 Vấn đề khi trao đổi dữ liệu 13
I.2PHÂN KHUNG 14
II )PHÂN LOẠI KỸ THUẬT KIỂM SỐT LỖI ARQ 19
Các cơ chế phát lại được chia ra làm 3 loại chính:
-Cơ chế phát lại dừng và đợi (Stop-and-Wait ARQ)
-Cơ chế phát lại theo nhĩm (Go-back-N ARQ)
-Cơ chế phát lại cĩ lựa chọn (Selective repeat ARQ)
II.1 Stop–and–Wait 19
*Cửa sổ trượt ARQ 24
II.2 Go–back–N 25
III.3 Selective Repeat ARQ 28
So sánh giữa Stop and Wait, Go-back-n và Selective-reject ARQ 31
PHẦN III ỨNG DỤNG ARQ 31
3
Lời nĩi đầu
Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, ngành viễn
thơng đã cĩ nhiều bước tiến vượt bậc, nhiều hệ thống thơng tin hiện đại đã ra
đời nhằm đáp ứng nhu cầu trao đổi thơng tin và giải trí của con người.ðặc
biệt là hệ thống thơng tin số với các đường truyền tốc độ cao đã dần thay thế
hệ thống thơng tin tương tự .Vấn đề đặt ra với hệ thống thơng tin số làtruyền
với khoảng cách xa mà vẩn đảm bảo độ chính xác thơng tin hay chất lượng
dịch vụ của hệ thống.
ðĩ là sự ra đời của các phương pháp phát hiện và sửa lổi, nhằm sửa
chữa những lổi, sai sĩt trên đường truyền, đảm bảo sự tin cậy, độ chính xác
thơng tin. ðể hiểu thêm về quá trình phát hiện lổi và sữa lổi của thơng tin
trước hết ta cần hiểu về hệ thống thơng tin.
Nhĩm em trân trọng cảm ơn sự giúp đỡ tận tình của quý thầy cơ
cũng như Khoa ðiện – ðiện Tử trường đại học Tơn ðức Thắng. Và đặc biệt
chúng em xin gửi lời cảm ơn sâu sắc đến giáo viên hướng dẫn của chúng em
–TS Hồng Thu Hà. Nhờ sự hướng dẫn tận tình của thầy mà chúng em cĩ
thể hồn thành tốt đề tài này.
4
PHẦN I CƠ SỞ LÝ THUYẾT VỀ KIỂM SỐT LỖI
I )HỆ THỐNG THƠNG TÍN SỐ
Hệ thống thơng tin số là hệ thống mà tín hiệu được truyền được truyền
dưới dạng số nhị phân.Sơ đồ tổng quát của hệ thống số được trình bày ở
hình:
Nguồn tin: là nơi tạo ra hay chứa các tập tin truyền đi.Nguồn tin cĩ
thể là tương tự hoặc số.
ðịnh dạng:cĩ chứa năng tạo ra tập hợp các tín hiệu rời rạc,riêng biệt.
Khi nguồn tin là tương tự thì định dạng sẽ rời rạc hĩa tín hiệu tương tự thành
các giá trị điện áp tại các khoản thời gian lấy mẫu.
Mã hĩa nguồn:biến đổi các tin tức,ký tự..thành các bit nhị phân.Cĩ rất
nhiều loại mã dùng để mã hĩa nguồn như:mã ACSII,mã BCD,mã tối ưu
Huffman,mã tối ưu Shannon,mã tối ưu Fano..
5
Mã bảo mật:mục đích là bảo mật nguồn thơng tin,chống lại sự ăn cắp
hay sự làm nhiểu làm sai lệch thơng tin của các yếu tố bên ngồi tại bất kỳ
một vị trí trên đường truyền
Mã hĩa kênh:mục đích làm giảm thiểu xác suất sai thơng tin khi
truyền qua kênh truyền đảm bảo độ tin cậy của thơng tin,cĩ thể sửa lỗi được
khi thơng tin đến phía thu bị lỗi.
Việc giảm thiểu xác suất sai dựa vào việc phát hiện sai và sửa sai cĩ
thể dẩn đến việc giảm tỉ số tín hiệu trên nhiễu(SNR) cần thiết,nhờ đĩ sẽ làm
thuận lợi cho việc bảo mật,trải phổ và tăng độ chính xác của thơng tin
nhận,đây là mục đích quan trọng của truyền thơng.
Ghép kênh: ghép các nguồn tin lại với nhau để truyền trên một kênh
chung.
ðiều chế: biến đổi tín hiệu thích ứng với kênh truyền,nhằm nâng cao
chất lượng và độ tin cậy của quá trình thơng tin.
Trải phổ: biến đổi tín hiệu băng hẹp thành tín hiệu băng rộng,nhằm
bảo mật thơng tin và sử dụng băng tần một cách cĩ hiệu quả.
ða truy cập: cho phép nhiều user cĩ thể truy cập vào
Kênh truyền: hữu tuyến (dùng các loại cáp đồng trục,cáp quang…để
truyền dẩn) và vơ tuyến
Hai vấn đề chính cơ bản của hệ thống thơng tin :
-Vấn đề hiệu suất,nĩi cách khác là tốc độ truyền tin của hệ thống.
-Vấn đề độ chính xác,nĩi cách khác là khả năng chống nhiễu của hệ
thống.
II) CÁC PHƯƠNG PHÁP PHÁT HIỆN LỖI
Phát hiện lỗi là quá trình kiểm tra và giám sát và xác định xem giữ liệu
thu cĩ bị lỗi khơng.Việc phát hiện lỗi đĩ cĩ khi chỉ cần biết đoạn từ mã hoặc
đoạn tin truyền đĩ cĩ bị lỗi hay khơng mà khơng cần biết bit lỗi cụ thể.
6
Do đĩ cần cĩ cơ chế phát hiện lỗi nhằm mục truyền lại hoặc sữa lỗi.Cơ
chế thứ nhất là kiểm sốt lỗi thuận và cơ chế thứ hai là kiểm sốt lỗi phản
hồi.
• Kiểm sốt lỗi thuận thường khơng yêu cầu truyền lại chỉ nhằm phát
hiện lỗi hoặc cĩ khả năng sửa hạn chế các bit lỗi.Phương pháp này
thường áp dụng cho các đường truyền cĩ cự ly rất xa với thời gian trể
là quan trọng,hoặc áp dụng trường hợp truyền đơn cơng
• Kiểm sốt lỗi phản hồi nhằm mục đích phát hiện sai và yêu cầu phía
phát gửi lại cho đến khi nhận được là chính xác.
Sau đây là một số phương pháp phát hiện lỗi đơn giản.
II.1 Phương pháp truyền phản hồi
Hay cịn gọi là phương pháp dội.Trong phương pháp này phía phát sẽ
truyền phía thu thơng điệp hay đoạn tin,khi phía thu nhận được thơng điệp
hay đoạn tin,khi phía thu nhận được thơng điệp sẽ phát lại bản sao về phía
phát:
Như vậy phía phát sẽ so sánh dữ liệu nằm trong vùng điệm để biết là dữ
liệu truyền đúng hay sai.
◄Ưu điểm: phương pháp này cĩ khả năng phát hiện sai rất chính xác từ
trường hợp các bit ở thơng điệp và bản sao sai trùng nhau,tuy nhiên khả
năng để cĩ các sai trùng nhau là rất bé.
Bộ phát Bộ thu
Bản sao
Thơng điệp
7
◄Nhược điểm: phương pháp này cho hiệu suất đường truyền thấp vì
cùng một thơng điệp truyền phải truyền hai lần.Trong trường hợp ở phía thu
nhận được ký tự đúng nhưng cĩ thể truyền lại phía phát bị lỗi.
II.2 Phương pháp truyền dư thừa
Hay cịn gọi là phương pháp truyền lặp lại.Phía phát sẽ truyền thơng điệp
và kèm theo bản sao của nĩ.
Ở bộ thu sẽ so sánh bản thơng điệp và bản sao,nếu khơng giống nhau
tức lỗi truyền suất hiện.
◄Ưu điểm: phương pháp này cĩ khả năng phát sai rất chính xác trừ
trường hợp các bit ở thơng điệp và bản sao sai trùng nhau,tuy nhiên khả
năng để cĩ các sai trùng nhau rất bé.
◄Nhược điểm: phương pháp này cĩ hiệu suất đường truyền thấp vì
cùng một thơng phải truyền hai lần.Trong trường hợp ở phía thu nhận được
ký tự đúng nhưng cĩ thể bản sao bị lỗi,như vậy việc truyền đúng sẽ trở thành
truyền bị lỗi
II.3 Phương pháp kiểm tra chẳn lẽ
Kiễm tra chẳn lẽ (parity) là phương pháp đơn giản nhất thường được
áp dụng trong các hệ thống truyền dữ liệu để phát hiện sai dữ liệu
truyền.Việc kiểm tra chẳn lẽ một đoạn tin truyền cĩ thể kiểm tra theo hàng
ngang hoặc kiểm tra theo cột dọc.Một bit đơn được gọi là bit kiểm tra được
thêm vào hàng hoặc cột để thực hiện việc kiểm tra.Phụ thuộc vào số bit 1 cĩ
Bộ phát Bộ thu
Thơng điệp Bản sao
8
trong hàng và phương thức kiểm tra lẻ hoặc chẳn mà giá trị bit kiểm tra P cĩ
giá trị là o hoặc 1.
◄Ưu điểm: phương pháp kiểm tra chẳn lẽ là đơn giản và rất thích hợp
đường truyền ngắn hoặc mơi trường cĩ nhiễu ít và cĩ khả năng phát hiện tất
cả các bit sai
◄Nhược điểm: nếu như cĩ một số chẳn các bit lổi thì phương pháp
kiểm tra chẳn lẽ khơng phát hiện được.
II.4 Phương pháp CRC
CRC (cyclic redundancy check) là một loại hàm băm, được dùng để
sinh ra giá trị kiểm thử, của một chuỗi bit cĩ chiều dài ngắn và cố định, của
các gĩi tin vận chuyển qua mạng hay một khối nhỏ của tệp dữ liệu. Giá trị
kiểm thử được dùng để dị lỗi khi dữ liệu được truyền hay lưu vào thiết bị
lưu trữ. Giá trị của CRC sẽ được tính tốn và đính kèm vào dữ liệu trước khi
dữ liệu được truyền đi hay lưu trữ. Khi dữ liệu được sử dụng, nĩ sẽ được
kiểm thử bằng cách sinh ra mã CRC và so khớp với mã CRC trong dữ liệu.
CRC rất phổ biến, vì nĩ rất đơn giản để lắp đặt trong các máy tính sử
dụng hệ cơ số nhị phân, dễ dàng phân tích tính đúng, và rất phù hợp để dị
các lỗi gây ra bởi nhiễu trong khi truyền dữ liệu.
Giải thuật đơn giản nhất cho việc sửa sai là tự động lặp lại thơng điệp:
- ðầu thu tính tốn CRC của thơng điệp và so sánh với CRC đã nhận
được
- Nếu kết quả khơng khớp thì đầu thu sẽ khơng xác nhận dữ liệu hợp
lệ
- ðầu phát sẽ tự động truyền lại thơng điệp đĩ nếu khơng nhận được
xác nhận dữ liệu hợp lệ
Tính tốn CRC
ðể tính tốn một mã nhị phân n bit CRC, xếp các bít biểu diễn đầu
vào thành một hàng, và đặt mẫu (n+1) bit biểu diễn số chia của CRC (gọi là
9
một "đa thức") vào bên dưới bên trái ở cuối hàng. Sau đây là phép tính đầu
tiên để tính một hàm CRC 3 bít:
11010011101100 <--- ðầu vào
1011 <--- Số chia (4 bit = 3 + 1 bit)
--------------
01100011101100 Lại đưa vào đầu vào của phép tính tiếp
theo)
Nếu dãy nhị phân đầu vào bên trên cĩ bít cực tả (đầu tiên bên trái) là
0, khơng làm gì hết và dịch số chia sang phải một bít. Nếu dãy nhị phân đầu
vào bên trên cĩ bít cực tả là 1, lấy dãy số đầu vào trừ đi số chia (hay nĩi
cách khác, lấy từng bít ở dãy số đầu vào trên trừ đi từng bít ở số chia). Số
chia sau đĩ dịch vị trí 1 bít sang phải, quá trình cứ tiếp diễn như vậy đến khi
số chia chạm tới tận cùng bên phải của dãy số đầu vào. ðây là phép tính cuối
cùng:
00000000001110 <--- Kết quả của phép nhân
1011 <--- Số chia
--------------
00000000000101 <--- Số dư (3 bits)
Do cực tả của số chia sẽ làm các bít tương ứng của dãy số đầu vào trở
về 0 qua mỗi lần dịch, khi quá trình này kết thúc, chỉ cịn những bít ở dãy
đầu vào cĩ thể khơng là 0 trở thành n bit cuối bên phải của dãy số. n bit này
là số dư của bước chia, và cũng sẽ là giá trị hàm CRC (trừ khi hàm CRC
được chọn đặc biệt được gọi cho một số cơng đoạn tiền xử lý).
II.5 Phương pháp kiểm tra tổng khối
ðể khắc phục nhược điểm của kiểm tra chẳn lẽ là khơng thể phát hiện
được tổng số bit sai là chẳn.Hơn nữa thường dữ liệu thường được truyền
thành từng khối tự nên,cho nên để cải thiện khả năng phát hiện lổi thì
phương pháp kiểm tra tổng khối được sử dụng
Phương pháp kiểm tra tổng khối thực hiện kiểm tra chẳn lẽ trên cả hàng
ngang lẩn cột dọc.
10
• Kiểm tra theo cột dọc : là mạch phát hiện lổi sử dụng phương pháp
kiểm tra chẳn lẻ để xác định lổi truyền trong một ký tự.Theo phương
pháp VRC (vertical redundancy checking) thì mỗi bit ký tự được
cộng thêm bit P trước khi truyền.Việc cộng thêm bit P đĩ cĩ thể là
kiểm tra chẳn hoặc kiểm tra lẽ.
• Kiểm tra theo hàng ngang (HRC-hozontal redundancy checking) là
một kiểu phát hiện lổi sử dụng phương pháp kiểm tra chẳn lẻ để xác
định lổi truyền trong một đoạn tin.Ở phương pháp HRC thì ứng với
mỗi vị trí bit cĩ một bit kiểm tra .Các bit b0 của các từ mã khác nhau
trong đoạn tin cũng được XOR với nhau.Tương tự như vậy các bit
b1,b2,b3…b6 của các từ mã trong đoạn tin cũng được XOR với
nhau.Kết quả sẽ cho bit kiểm tra HRC.Dãy bit HRC được thực hiện ở
phía phát trước khi truyền dữ liệu.Tại phía thu,bit HRC cũng sẽ được
kiểm tra so sánh giống như kiểm tra so sánh lổi bit ký tự bit.
◄Ưu điểm:
-Cĩ khả năng phát hiện tất cả các bit sai lẽ
-Cĩ khả năng phát hiện tất cả các bit lổi chẳn thậm chí cùng hàng cùng cột.
PR B6 B5 B4 B3 B2 B1 B0
0 0 0 0 0 0 1 0
1 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0
0 0 1 0 0 0 0 0
1 0 1 0 1 1 0 1
0 1 0 0 0 0 0 0
1 1 1 0 0 0 1 1
1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1
= STX
= ETX
= BCC
Duyệt theo cột (chẵn)
Duyệt theo
hàng (lẻ)
Frame Data
Kiểm tra tổng BSC (Block Sum Check)
Hướng
Truyền
Vị trí tổ hợp lỗi khơng
phát hiện được
11
-Cĩ khả năng sửa được một bit sai,vì nếu chỉ cĩ một bit sai thì hàng và cột
tương ứng sẽ chỉ ra tọa độ bit sai.
◄Nhược điểm: khơng phát hiện được lỗi truyền nếu như trong đoạn tin
cịn số chẳn các ký tự cĩ vị trí lỗi bit giống nhau.
III LỖI DỮ LIỆU KÊNH TRUYỀN
Các đường truyền dữ liệu cĩ thể cĩ khoảng cách ngắn vài m và cũng
cĩ thể dài hàng nghìn km,mơi trường truyền dữ liệu cĩ thể là hệ thống dây
đồng ,vi ba,vệ tinh,sợi cáp quang,hoặc vơ tuyến.Do các đặc tính khơng lý
tưởng của kênh truyền cũng như tác động của các yếu tố can nhiễu bên
ngồi.Trong thực tế khơng bao giờ đạt được độ tin cậy hồn tồn hồn
hảo.Sai hoặc lổi xuất hiện trong quá trình truyền dữ liệu là khơng tránh khỏi.
Trong các kênh truyền tin số,nếu như xem rằng các chuỗi ký hiệu
truyền vẩn được giữ nguyên trật tự và chỉ sai số ở dạng bit,các lổi kênh
truyền,các lổi trong kenh truyền nhị phân đĩ cĩ thể chia làm 2 loại:
-Lổi xác suất cĩ ký hiệu một,xảy ra ở các kênh truyền cĩ tốc độ
thấp,độ tin cậy truyền tin lớn.xác lỗi thường độc lập khơng phụ thuộc vào
nhau.
-Lổi cĩ tính chất cụm:thường do các yếu tố tạp nhiễu bên ngồi tác
động làm cho 1 số bít liên tiếp hay 1 cụm bit nào đĩ bị sai lệt.
* Kiểm sốt lổi
Khi nhập dữ liệu được nhập vào máy tính bằng bàn phím thì chương
trình sẽ đọc và chứ ký tự nhận được rồi gửi lên màn hình.Như vậy nếu ký tự
nhập bị sai thì người sử dụng cĩ thể dùng các ký tự điều khiển như “delete”
hoặc “backspace” để loại bỏ lý tự sai và nhập lại.Cơng việc như vậy gọi là
kiểm sốt lỗi bằng tay.
ðối với việc truyền dữ liệu ,khi 1 thiết bị đầu cuối chuyển các khối ký
tự hay là khung dọc theo 1 đường truyền nối tiếp đến các thiết bị đầu cuối
khác,chương trình bên phía thu sẽ thực 1 một thủ tục kiểm sốt lỗi tự động
trong suốt đối với người sử dụng.Thơng thường bên phía thu sẽ kiểm tra các
khung vừa nhận được và trả về phía phát một thơng điệp để xác nhận là
12
đúng hoặc yêu cầu gửi một bản sao khác.Loại kiểm sốt lỗi như vậy gọi là
ARQ(AUTOMATIC REPEAT REQUEST).
PHẦN II KỸ THUẬT KIỂM SỐT LỖI ARQ
I )ðẶC ðIỂM ARQ
Trong thực tế cĩ 2 loại cơ sở ARQ đĩ là idle RQ được dùng với
truyền định hướng ký tự ,continious RQ được dùng với các loại truyền lại
selective repeat hoặc goback N.Loại RQ liên tục thường dùng với truyền
định hướng bit.
Nguyên lý kiểm sốt lỗi idle RQ được định nghĩa để cho phép các
khung của ký tự được truyền một cách tin cậy .ðể phân biệt phía gửi
(nguồn),và phía nhận đích các thuật ngữ P (primary) và S(secondary) sẽ
được sử dụng.ðể phân biệt các khung dữ liệu và các khung giám sát ta
thường dùng các thuật ngữ I-Frame và ACK hay NAK Frame.
Idle RQ hoạt động ở chế độ mode bán song cơng,bởi vì sau khi P gửi
một I-Frame nĩ phải chờ bên S báo cho biết là khung trước đĩ đã nhận đúng
hay sai.Và P sẽ truyền một khung mới nếu thơng tin nhận được là đúng ,và
yêu cầu gửi lại khung cũ nếu thơng tin nhận được là sai.
Cĩ 2 cách thực hiện nguyên lý này là truyền hiểu ngầm và truyền
tường minh
Khi truyền thơng tin trong mạng, thơng tin truyền từ phía phát sang
phía thu cĩ thể bị sai lỗi hoặc mất. Trong trường hợp thơng tin bị mất, cần
phải thực hiện truyền lại thơng tin. Với trường hợp thơng tin bị sai, cĩ thể
sửa sai bằng một trong hai cách:
-Sửa lỗi trực tiếp bên thu: phía thu sau khi phát hiện lỗi cĩ thể sửa lỗi
trực tiếp ngay bên thu mà khơng yêu cầu phải phát lại. ðể cĩ thể thực hiện
được điều này, thơng tin trước khi truyền đi phải được cài các mã sửa lỗi
(bên cạnh việc cĩ khả năng phát hiện lỗi, cần cĩ khả năng sửa lỗi).
-Yêu cầu phía phát truyền lại: phía thu sau khi kiểm tra và phát hiện
cĩ lỗi sẽ yêu cầu phía phát truyền lại thơng tin.
13
ARQ (Automatic Repeat Request) , cĩ thể dịch là cơ chế tự động phát
lại , ở giao thức TCP cĩ sử dụng đến cơ chế này . Nĩ dùng để điều khiển
luồng và điều khiển chống tắc nghẽn .
I.1 Vấn đề khi trao đổi dữ liệu
Một số vấn đề khi hai thiết bị kết nối trực tiếp truyền nhận dữ liệu
ðồng bộ khung
ðiều khiển tốc độ truyền dữ liệu
Xử lý lỗi gặp phải trên đường truyền
ðịnh vị địa chỉ (trong cấu hình multipoint)
Phân biệt dữ liệu và thơng tin điều khiển
Quản lý liên kết
Nội dung
ðiều khiển dịng dữ liệu
ðiều khiển lỗi
Một số nghi thức điều khiển liên kết dữ liệu
ðiều khiển dịng dữ liệu
Bên nhận thường cĩ bộ đệm để nhận dữ liệu
Khi dữ liệu đến, bên nhận thường thực hiện một số xử lý trước khi
gửi lên lớp cao hơn
ðiều khiển dịng: đảm bảo bên phát khơng gởi dữ liệu quá nhanh.
Ngăn ngừa việc tràn bộ đệm
14
*Mơ hình truyền khung
I.2 PHÂN KHUNG
Khối lớn dữ liệu cĩ thể chia thành các khung nhỏ.
Phù hợp với bộ nhớ đệm giới hạn
Phát hiện các lỗi nhanh hơn ( khi cả khung được nhận xong )
Trong trường hợp lỗi, chỉ cần truyền lại các khung nhỏ hơn.
Tránh trường hợp một trạm bất kỳ chiếm đường truyền quá lâu
ðiều kiện giả định
Tất cả frame đều đến đích
Khơng cĩ frame lỗi
Các frame đến đúng thứ tự
Nghi thức Idle RQ (Stop–and–Wait)
ðặc điểm
Phương pháp đơn giản nhất
ðược dùng chủ yếu trong các ứng dụng character-oriented.(byte-
oriented)
Sử dụng kênh truyền hoạt động trong chế độ half-duplex
15
Cơ chế hoạt động
Nguồn phát dữ liệu (dưới dạng các frame)
ðích nhận dữ liệu và trả lời bằng ACK
Nguồn phải đợi ACK trước khi phát tiếp dữ liệu
ðích cĩ thể ngưng truyền dữ liệu bằng cách khơng gởi ACK
Idle RQ – Hiệu suất
Khái niệm
Thời gian truyền (tframe): thời gian cần thiết để gởi tất cả các bit dữ
liệu lên đường truyền
Thời gian lan truyền (tprop): thời gian cần thiết để 1 bit đi từ nguồn
đến đích
Thời gian tổng cộng TD= n(2tprop + tframe)
Hiệu suất đường truyền
Thời gian tổng cộng TD= n(2tprop + tframe)
Hiệu suất đường truyền
Vấn đề kích thước frame
Hiệu quả đường truyền cao nếu frame kích thước lớn
Thực tế dữ liệu lớn được chia thành các frame cĩ kích thước nhỏ
Kích thước bộ đệm cĩ giới hạn
Frame kích thước nhỏ khĩ xảy ra lỗi
Lỗi được phát hiện sớm
Khi cĩ lỗi, chỉ cần truyền lại frame nhỏ
16
Ngăn ngừa tình trạng 1 trạm làm việc chiếm đường truyền lâu
Sliding windows
Cơ chế hoạt động
Cho phép nhiều frame cĩ thể truyền đồng thời
Bên thu cĩ bộ đệm với kích thước W (cĩ thể nhận W frame)
Bên phát cĩ thể truyền tối đa W-1 frame mà khơng cần đợi ACK
ðánh số thứ tự cho các frame
ACK cĩ chứa số thứ tự của frame kế tiếp cĩ thể truyền
Số thứ tự được quay vịng bởi kích thước cửa sổ (modulo 2k)
17
Cải tiến
Bên thu cĩ thể gởi ACK mà khơng cho phép bên phát gởi tiếp dữ liệu
(Receive Not Ready)
Trong trường hợp này, bên thu phải gởi ACK để bình thường hĩa
việc truyền nhận dữ liệu khi nĩ sẵn sàng
Nếu đường truyền là full-duplex, dùng cơ chế “piggybacking”: tích
hợp ACK vào frame dữ liệu
Nếu khơng cĩ dữ liệu để truyền, dùng ACK frame
Nếu cĩ dữ liệu để truyền nhưng khơng cĩ ACK để truyền, gởi lại
ACK cuối cùng, hoặc cĩ cờ ACK hợp lệ (TCP)
Hiệu suất
Full- Duplex
ðiều khiển lỗi là gì ?
ðiều khiển lỗi là các kỹ thuật để phát hiện và sữa lỗi xảy ra trong quá
trình truyền các frame
Bảo đảm truyền nhận dữ liệu chính xác
Kỹ thuật điều khiển lỗi
Phân loại lỗi đối với frame
18
Mất frame: frame khơng đến đích hoặc đến nhưng thơng tin điều khiển
trên frame bị hư (bên nhận khơng thể xác định là frame nào)
Frame hư: thơng tin điều khiển trên frame xác định được, nhưng dữ
liệu trong frame bị lỗi
Phát hiện lỗi (CRC, Parity, …)
Positive ACK – xác nhận các frame nhận được
Negative ACK (NAK) – yêu cầu truyền lại cho các frame bị hư
Truyền lại sau một thời gian time-out
Cơ chế
Dựa trên điều khiển dịng
Kỹ thuật ARQ (Automatic Repeat Request)
Cho phép các nghi thức liên kết dữ liệu quản lý và yêu cầu truyền
lại
Phân loại
Idle RQ (stop-and-wait)
Dùng với cơ chế điều khiển dịng stop-wait
Continuous RQ
Dùng với cơ chế điều khiển dịng sliding-window
Selective repeat
Go-back-N
Idle RQ
Cơ chế hoạt động
A gởi một I-Frame (Information
Frame) đến B
A đợi phản hồi từ B trước khi gởi tiếp frame
ACK-Frame – A gởi dữ liệu mới
NAK-Frame – A gởi lại dữ liệu
Khơng nhận được trả lời – A gởi lại sau thời gian time-out
Ưu/khuyết điểm
ðơn giản
ðộ hiệu quả đường truyền thấp
19
II )PHÂN LOẠI KỸ THUẬT KIỂM SỐT LỖI ARQ
Các cơ chế phát lại được chia ra làm 3 loại chính:
-Cơ chế phát lại dừng và đợi (Stop-and-Wait ARQ)
-Cơ chế phát lại theo nhĩm (Go-back-N ARQ)
-Cơ chế phát lại cĩ lựa chọn (Selective repeat ARQ)
II.1 Stop–and–Wait
Stop –and-wait ARQ là một dạng của điều khiển dịng truyền dừng
và đợi đã mở rộng để chứa các chức năng truyền lại dữ liệu trong trường hợp
dữ liệu bị mất hoặc hư hỏng. để việc truyền lại cĩ thể thực hiện được bổ
sung vào cơ cấu dịng truyền 4 tính chất sau:
Thiết bị gửi lưu bản copy khung được truyền cuối cùng cho đến khi
nĩ nhận được ACK của khung đĩ. Việc này cho phép thiết bị gửi truyền lại
khung bị mất hoặc khung bị hư hỏng đến khi chúng được nhận đúng.
20
ðể nhận dạng đúng, cả khung dữ liệu lẫn khung ACK được đánh số
luân phiên 0 và 1. Khung dữ liệu 1 được nhận biết bởi khung ACK1 cĩ
nghĩa là thiết bị nhận đã nhận được dữ liệu 1 và bây giờ đang chờ nhậnn dữ
liệu 0. việc đánh số này cho phép nhận dạng khung dữ liệu trong trường hợp
dữ liệu truyền 2 lần (điều này là quan trọng khi các khung ACK bị mất).
Nếu một lỗi được phát hiện trong khung dữ liệu thì nơi nhận gửi
khung NAK. Các khung NAK khơng được đánh số , thiết bị tự hiểu cần phải
truyền lại khung cuối. Stop –and-wait ARQ địi hỏi thiết bị gửi đợi đến khi
nhận ACK khung cuối, trước khi truyền khung tiếp theo. Khi thiết bị gửi
nhận khung NAK nĩ gửi lại khung đã được truyền sau ACK cuối mà bỏ qua
số khung của nĩ.
Thiết bị gửi được trang bị đồng hồ. Nếu chờ khung NAK trong một
thời gian xác định mà khơng thấy thì cho rằng khung dữ liệu cuối đã bị mất
và gửi lại khung đĩ.
Cơ chế hoạt động:
• Nghi thức điều khiển lỗi đơn giản nhất.
• Máy phát gởi một frame sau đĩ dừng và chờ một xác nhận từ máy thu.
• Nếu xác nhận là ACK thì frame kế tiếp sẽ được gởi đi.
• Nếu xác nhận là NAK thì truyền lại frame vừa truyền.
• Nếu nhận một frame hỏng, bỏ đi
• Máy phát cĩ timeout
• Nếu khơng cĩ ACK trả về trong thời gian timeout thì truyền lại.
• Nếu ACK bị hỏng, máy phát khơng nhận ra
• Máy phát sẽ truyền lại
• Máy thu nhận hai bản copy của khung
• Dùng ACK0 và ACK1
21
•
22
Các loại lỗi
(E1) I-Frame khơng đến được bên nhận
(E2) I-Frame đến được bên nhận nhưng nội dung I-Frame bị sai
(E3) ACK-Frame khơng đến được bên gởi hay ACK-Frame đến
được bên gởi nhưng nội dung ACK-Frame bị sai
Sửa lỗi E1
Sử dụng timer: bên gởi sau khi gởi đi một I-Frame thì khởi động một
bộ đếm thời gian, sau khoảng thời gian đợi T mà chưa nhận được tín hiệu
ACK/ NAK báo về thì xem như I-Frame chưa tới và gởi lại frame này.
Giới
hạn
thời
gian
chờ
đợi
Data 0
Data 0
Data 0
lost
.
.
.
.
Mất khung dữ liệu
ACK0
23
Sửa lỗi E2
Khi một khung được nhận bị lỗi thì thiết bị nhận sẽ gởi khung NAK và
truyền lại khung cuối.
Sửa lỗi E3
Trong trường hợp khung dữ liệu nhận đúng ở phía nhận. Khung
ACK(NAK) mà thiết bị nhận gởi bị mất trên đường truyền thì:
Thiết bị gởi đợi hết hời gian qui định, sau đĩ truyền lại khung dữ liệu
cuối. Thiết bị nhận kiểm tra số khung dữ liệu mới. Nếu khung bị mất là
Data 0
ACK0
Data 1
Data 1
NAK
ACK1
Lỗ khung dữ liệu
24
NAK thiết bị nhận nhận khung mới này và trả lời ACK(khung mới khơng bị
hỏng).
Nếu khung mất là ACK thì thiết bị nhận nhận khung mới này như bản
sao khác nữa sau đĩ gửi ACK rồi bỏ qua những bản sao này và đợi khung
tiếp theo
*Cửa sổ trượt ARQ
Trong nhiều cơ cấu điều khiển lỗi truyền thơng, cĩ 2 thủ tục phổ biến
nhất:Go-back-n ARQ và chọn lựa từ chối ARQ. Cả 2 đều dựa vào điều
khiển dịng truyền cửa sổ trượt. ðể mở rộng cửa sổ trượt cho truyền lại các
khung bị mất hoặc bị hỏng phải bổ sung 3 điểm vào điều khiển dịng truyền:
Thiềt bị gởi lưu bản copy tất cả các khung đã được truyền cho đến khi
nhận được khung ACK. Nếu các khung từ 0 đến 6 đã được truyền và nhận
biết cuối cùng cho khung 2 (chờ khung 3 )thì thiết bị gửi lưu bản copy của
khung 3 đến khung 6 cho đến khi nĩ biết rằng những khung này đã được
nhận đúng.
Giới
hạn
thời
gian
chờ
đợi
Data 0
Data 0
Data 0
Data 0
Bản copy thứ
nhất bị bỏ
quabỏquaData
ACK0
lost
.
.
.
Mất khung nhận biết ACK0
.
25
Bên cạnh các khung ACK thiết bị nhận cịn gởi các khung NAK nếu
dữ liệu nhận được bị lỗi. Bởi cửa sổ trượt là cơ cấu truyền liên tục, cả khung
ACK và NAK đều đượ đánh số để nhận diện. Các khung ACK mang số của
khung sẽ gởi tiếp theo. Các khung NAK mang số của chính khung hỏng.
Trong cả 2 trường hợp đều cho biết số khung mà thiết bị nhận đang chờ đợi.
Nếu ACK trước đĩ được đánh số 3, thì ACK 6 hiện tời cho biết đã nhận tốt
các khung 3,4,5. Nếu NAK 4 cĩ nghĩa là tất cả các khung nhận được trước
khung 4 dều đúng.
Giống như Stop –and-wait ARQ, ở đây thiết bị gởi theo dõi thời gian
để điều khiển khi ACK và NAK bị mất.
II.2 Go–back–N
Cơ chế hoạt động
ðiều khiển
RR = receive ready = ACK = acknowledge
REJ = reject = NAK = negative acknowledge
Dựa trên cơ chế sliding window
A gởi liên tục các I-Frame đến B (trong khi cơ chế điều khiển dịng
cịn cho phép)
B chỉ nhận I-Frame theo đúng chỉ số tuần tự
Truyền lại tất cả các Frame kể từ Frame sai đầu tiên trở đi
Các kiểu lỗi tương tự như trong Idle RQ (cĩ thể xảy ra đồng thời trên
nhiều frame)
(E1) I-Frame khơng đến được bên nhận
(E2) I-Frame đến được bên nhận, nội dung I-Frame sai
(E3) ACK-Frame khơng đến được bên gửi
26
Sửa lỗi E1
Thủ tục cửa sổ trượt yêu cầu các khung dữ liệu phải truyền một cách tuần
tự.thiết bị nhận kiểm tra số nhận diện trên mỗi khung và nhận thấy rằng một
hoặc nhiều khung bị mất, nĩ sẽ gửi khung NAK cho khung bị mất đầu tiên
và yêu cầu truyền lại.
Dữ liệu 0 và 1 truyền đến chính xác nhưng dữ liệu 2 bị mất. Khung
tiếp theo truyền đến thiết bị nhận là khung 3.Thiết bị nhận đang chờ khung 2
và nĩ coi dữ liệu 3 là lỗi và bỏ qua, nĩ gửi khung NAK2 báo rằng khung 0,1
đã nhận nhưng khung 2 bị lỗi (khung 2 bị mất)
Thiết bị gởi đã truyền khung 3,4,5 trước khi nhận NAK2, khi thiết bị
gởi nhận được NAK2 nĩ truyền lại cả 4 khung 2,3,4,5.
Data 0
lost
Mất khung dữ liệu 2
Data 2
Data 3
Data 4
Data 5
Data 3
Data 4
Data 5
Data 1
Loại bỏ
Data 0
Data 1
NAK2
Data 2
Data 3
Data 4
Loại bỏ
Data 5
Data 2
Loại bỏ
27
Sửa lỗi E2
Bên nhận phát hiện lỗi ở frame i
Bên nhận báo cho bên gởi bằng NAKi và loại bỏ các frame sau i
Bên gởi gởi lại các frame từ framei
Thời gian đáp ứng nhanh hơn so với dùng timeout.
ACK3 báo cho thiết bị gửi biết rằng khung 0,1,2 đã được nhận đúng.
Khung 3 bị phát hiện cĩ lỗi, nên NAK3 được gởi tức thì và các khung 4,5 bị
bỏ qua khi chúng đến bên nhận.
Thiết bị gửi truyền lại cả 3 khung (3,4,5)đã được gởi từ khi cĩ nhận biết
cuối và quá trình cứ tiếp tục.
Sửa lỗi E3
ACKi bị mất
Nếu sau đĩ cĩ ACKi+1, ACKi+2... thì truyền bình thường
Nếu hết timeout bên gởi sẽ gởi lại I-Frame
Data 0
Lỗi khung 3
Lỗi khung dữ liệu 3
Data 2
Data 3
Data 4
Data 5
Data 3
Data 4
Data 5
Data 1
Loại bỏ
Data 0
Data 1
Data 2
ACK3
NAK3
Data 3
Data 4
Data 5
Loại bỏ
28
Bên nhận phát hiện frame truyền lại này đã nhận nên sẽ báo lại ACK
(hoặc NAK) tương ứng
Khi nhận ACK, bên phát khơng cần truyền lại tất cả các frame mà cĩ
thể truyền frame từ chỉ số trong ACK
II.3 Selective Repeat ARQ
Phương pháp này chỉ truyền lại những khung bị hỏng hoặc bị thất lạc.
nếu khung bị hỏng thiết bị gởi nhận được khung NAK và khung đĩ sẽ được
truyền lại ngồi tuần tự thơng thường. Thiết bị nhận phải sắp xếp lại các
khung và chèn chính xác khung vào vị trí thích hợp của nĩ theo đúng tuần
tự.ðể cĩ được khả năng chọn lựa đĩ hệ thống Selective-reject ARQ khác hệ
thống Go-back-n ARQ những điểm sau:
Giới hạn thời
gian chờ đợi
Data 0 0
Mất nhận biết ACK3
Data 2
Data 0
Data 1
Data 2
Data 1
Data 0
Data 1
Data 2
ACK3
Data 0
Data 1
Data 2
lost
29
Thiết bị nhận phải chứa các cổng logic sắp xếp để sắp xếp tuần tự các
khung được nhận lại. Nĩ cũng phải sắp xếp các khung nhận sau khi đã gởi
khung NAK cho đến khi khung hỏng được sửa đổi.
Thiết bị gởi phải cĩ cơ cấu tìm kiếm, cho phép nĩ tìm và chọn chỉ
khung yêu cầu truyền lại.
ðệm trong thiết bị nhận phải giữ tất cả các khung nhận được cho đến
khi tất cả những khung truyền lại đều được sắp xếp và bỏ qua nhữnng khung
nhận được lần 2.
ðể giúp cho việc chọn lựa, các số ACK cũng như các số NAK phải
gán cho các khung nhận (hoặc bị mất ) mà khơng gán cho khung chờ nhận
tiếp theo.
Kích thước cửa sổ theo phương pháp này nhỏ hơn kích thước của sổ
của phương pháp Go-back-n ARQ. Kích thước đĩ bằng hay nhỏ hơn (n+1)/2
trong khi đĩ cử sổ của Go-back-n ARQ là ( n-1).
Cơ chế hoạt động
Tương tự như Go-Back-N
Chỉ gởi lại các frame bị NAK hoặc time-out
Bên nhận cĩ thể nhận I-frame khơng theo đúng chỉ số tuần tự
Βên nhận phải cĩ buffer để lưu lại các frame đến khơng theo đúng
chỉ số tuần tự
Vấn đề kích thước cửa sổ
Tình huống: window kích thước 7
A gởi các frame từ 0 đến 6 qua B
B xác nhận tất cả, nhưng tất cả ACK đều bị mất
A đợi bị timeout, nên gởi lại frame 0
B lúc này đã dịch cửa sổ nhận, cĩ thể nhận các frame 7,0,1,...5. Nĩ
tưởng frame 7 bị mất và 0 là frame mới, nên chấp nhận (trùng frame)
ðây là vấn đề trùng lắp giữa cửa sổ gởi và cửa sổ nhận
Do đĩ kích thước cửa sổ tối đa là ½(N) (N là chỉ số tuần tự lớn nhất)
30
Sửa lỗi E1
Nếu một khung bị mất, khung tiếp theo sẽ truyền tới ngồi tuần tự. Khi đĩ
thiết bị nhận sẽ sắp xếp lại những khung cĩ mặt.
Tất nhiên, thiết bị nhận chỉ nhận ra sự mất khung nếu cĩ các khung
tiếp theo.
Sửa lỗi E2
I-Frame truyền đến bên nhận nhưng bị lỗi
Bên nhận báo cho bên gởi biết thơng qua NAK-Frame
Bên nhận vẫn lấy các frame tiếp theo vào bộ đệm(nhưng chưa đưa
lên lớp trên)
Bên gởi chỉ truyền lại I-Frame bị lỗi
Bên nhận nhận đúng các frame theo trình tự thì cĩ thể đưa dữ liệu lên
lớp trên
Data 0
Cơ cấu truyền khung bị lỗi trong
Selective-reject ARQ
Data 2
Data 3
Data 4
Data 5
Data 4
Data 5
Data 1
Data 0
Data 1
NAK2
Data 2
Data 3
Data 2
31
Sửa lỗi E3
Sử dụng chỉ số tuần tự frame (sequential number):
Khi ACK-frame bị lỗi hay khơng đến được bên gởi, sau thời gian
timeout bên gởi sẽ gởi lại I-Frame này
* So sánh giữa Stop and Wait, Go-back-n và Selective-reject ARQ:
Stop and Wait là kỹ thuật kiểm sốt lỗi đơn giản nhất và hiệu quả. Bên
gởi chỉ việc gởi data và đợi xác nhận từ bên nhận. Nếu bên nhận xác nhận
data là đúng thì bên phát sẽ tiếp tục phát tiếp những data tiếp theo. Hiệu suất
sử dụng đường truyền thấp do phaic chờ xác nhận bên nhận mới được phát
tiếp hoặc sau thời gian của bộ định thời.
Mặc dù chỉ truyền lại những khung bị mất và bị lỗi nhưng Selective-
reject ARQ khơng hiệu quả hơn việc truyền lại tất cả các khung. Sự phức
tạp ở chỗ yêu cầu thiết bị nhận phải sắp xếp và lưu giữ các khung và thiết bị
gửi phải cĩ cổng logic ngồi để chọn ra những khung truyền lại nhất định.
Selective-reject ARQ đắt hơn và ít được sử dụng. Trong thự tế sử dụng Go-
back-n đơn giản và tiên lợi hơn.
PHẦN III ỨNG DỤNG ARQ
TRONG CƠNG NGHỆ WIREMAX DI ðỘNG
Thuật tốn ARQ trở nên phổ biến trong mạng khơng dây và mạng hữu
tuyến để truyền lại các thơng tin bị lỗi.Tuy nhiên,hiện qua các việc sử
dụng ARQ yêu cầu sự lựa chọn chính xác về cơng suất phát và tốc độ dữ
liệu trong quá trình truyền tải phát,về mặt khác đường truyền trở nên
bị lỗi.Khi quá trình duy trì các thiết lập tối ưu này trong mơi trường
thời gian khơng ổn định trở thành một thách thức cho các dịch vụ băng
rộng di động.Kỷ thuật Hyrid ARQ được phát triển.H-ARQ trở thành
một phần thơng số wimax di động khối thu tập hợp các thơng tin từ một
gĩi lỗi với hiện tượng tái truyền phát tín hiệu của cùng một gĩi tin cho
tới khi thơng tin tập hợp đủ lại để lấy lại tồn bộ gĩi tin
32
Khi vận hành HSDPA ở lân cận hiệu suất phổ cao nhất, tỉ lệ lỗi khối BLER sau lần
truyền dẫn đầu tiên được khuyến nghị trong khoảng từ 10- 20%. Cơ chế yêu cầu lặp tự
động lai H-ARQ được ứng dụng trong giải pháp HSDPA nhằm giảm trễ và tăng hiệu suất
của quá trình tái truyền dẫn dữ liệu. Thực tế, H- ARQ là một giao thức dạng dừng lại và
chờ SAW (Stop And Wait).
Trong cơ chế SAW, phía truyền dẫn luơn luơn ở quá trình truyền dẫn các block đang
hiện hành cho tới khi thiết bị người sử dụng hồn tồn nhận được dữ liệu. ðể tận dụng
thời gian khi Node- B chờ các báo nhận, cĩ thể thiết lập N tiến trình SAW-ARQ song
song cho thiết bị người dùng. Do đĩ, các tiến trình khác nhau truyền dẫn trong các TTI
riêng biệt. Số tiến trình SAW-ARQ song song được thiết lập tối đa là 8 (N=8), tuy nhiên
thơng thường chọn giá trị N từ 4-6. Thời gian trễ nhỏ nhất cho phép giữa quá trình truyền
dữ liệu gốc so với quá trình tái truyền dẫn dữ liệu lần đầu tiên trong HSDPA là 12ms.
ðiều khiển H- ARQ lớp 1 được đặt tại Node-B, do đĩ việc lưu trữ các gĩi dữ liệu phi
báo nhận cùng với chức năng sắp xếp các gĩi của quá trình tái truyền dẫn là khơng phụ
thuộc vào RNC. Như vậy sẽ tránh được trễ tái truyền dẫn, ngồi ra các trễ này sẽ thấp
hơn trễ gây ra bởi quá trình tái truyền dẫn RLC thơng thường.
Các file đính kèm theo tài liệu này:
- TH095.pdf