Đề 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. 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.