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 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 SOÁ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 SOÁ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 Hoàng Thu Hà. Nhờ sự hướng dẫn tận tình của thầy mà chúng em có thể hoàn thành tốt ñề tài này. 4 PHẦN I CƠ SỞ LÝ THUYẾT VỀ KIỂM SOÁ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 ngoà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 soát lỗi thuận và cơ chế thứ hai là kiểm soát lỗi phản hồi. • Kiểm soá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 soá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 toá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 toá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 toán CRC ðể tính toá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 ngoài.Trong thực tế không bao giờ ñạt ñược ñộ tin cậy hoàn toàn hoà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 ngoà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 soá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 soá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 soá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 soát lỗi như vậy gọi là ARQ(AUTOMATIC REPEAT REQUEST). PHẦN II KỸ THUẬT KIỂM SOÁ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 soá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 SOÁ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 ngoà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 ngoà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 soá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 ngoà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 toá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 toà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 hoàn toà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, ngoà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.