Các kỹ thuật điều khiển, kiểm soát luồng dữ liệu và kiểm soát lỗi

Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 1 CÁC KỸ THUẬT ĐIỀU KHIỂN, KIỂM SOÁT LUỒNG DỮ LIỆU VÀ KIỂM SOÁT LỖI Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 2 I. Các kỹ thuật điều khiển, kiểm soát luồng dữ liệu. 1. Điều khiển luồng dữ liệu. Điều khiển luồng dữ liệu là một kỹ thuật để đảm bảo rằng bên nhận không bị ngập tràn dữ liệu đã được gửi bởi bên gửi. Thông thường bên nhận phân phối một vùng đệm dữ liệu với một độ lớn nào đó. Khi nhận được dữ liệu bên nhận phải thực hiện một vài quá trình xử lý trước khi gửi dữ liệu tới phần mềm ở mức bên trên. Một số kỹ thuật dùng để điều khiển luồng: 2.Dừng và đợi (Stop – and – Wait) Đây là dạng đơn giản nhất của điều khiển luồng, hoạt động như sau: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 3 Bên gửi truyền đi một frame sau đó dừng việc gửi các frame tiếp theo. Sau khi bên nhận nhận được frame này nó sẽ thông báo cho bên gửi rằng bên nhận đã sẵn sàng nhận frame khác bằng cách gửi trả lại một ack cho frame nó vừa nhận được. Bên gửi bắt buộc phải đợi cho đến khi nó nhận được ack trước khi nó gửi đi frane tiếp theo. Bên nhận cũng có thể dừng dòng dữ liệu bằng cách không gửi ack Thủ tục này làm việc có hiệu quả và có thể được tận dụng khi một thông báo được gửi đi dưới dạng một vài frame lớn. Tuy nhiên bên gửi có thể chia một khối dữ liệu lớn thành các khối nhỏ và truyền dữ liệu đi bằng nhiều frame do các lý do sau: -Kích thước vùng đệm của bên nhận có thể bị hạn chế Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 4 - Khi truyền frame với kích thước lớn cần thời gian truyền lâu hơn do đó khả năng bị lỗi sẽ cao hơn và như vậy sẽ cần nhiều thời gian để truyền lại hơn. - Với các việc truyền các frame có kích thước nhỏ, các lỗi sẽ được phát hiện sớm hơn và một khối lượng dữ liệu nhỏ hơn sẽ được truyền lại khi gặp lỗi. - Trên các đường tryền dùng chung, chẳng hạn như các LAN, không nên cho phép một trạm chiếm giữ đường truyền quá lâu điều này sẽ làm các trạm khác phải đợi lâu hơn để đến lượt được truyền. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 5 Sử dụng nhiều frame cho một thông báo, thủ tục dừng và đợi có thể không hiệu quả vì tại một thời điểm chỉ có một frame được truyền đi. Ta có thể nhận thấy rõ vấn đề này qua công thức: B=R*d/V (1) Trong đó: - B = độ dài của liên kết tính bằng bit, đây là số lượng bits hiện có trên liên kết khi một chuỗi bit chiếm giữ hoàn toàn liên kết - R= tốc độ dữ liệu trong liên kết (bit/giây) - d= độ dài hay khoảng cách của liên kết (mét) - V= Vận tốc truyền (met/giây) 3. Cửa sổ trượt (Sliding – Window) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 6 Để khắc phục sự không hiệu quả của phương pháp dừng và đợi, nhiều frame được truyền trong cùng một khoảng thời gian. Ví dụ hai trạm A và B được kết nối qua một liên kết hai chiều đồng thời (full - duplex link). Trạm B phân phối một vùng đệm cho W frame, do đó B có thể chấp nhận W frame và A được cho phép truyền W frame mà không cần đợi sự phản hồi. Để kiểm soát xem frame nào đã được phản hồi mỗi frame được gán với một số thứ tự. B phản hồi cho một frame bằng cách gửi một ack bao gồm số hiệu của frame đang đợi để nhận tiếp theo, điều này cũng có ngầm định rằng B đã sẵn sàng nhận W frame tiếp theo kể từ frame đang đợi này. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 7 Cơ chế này cũng có thể phản hồi cho nhiều frame, chẳng hạn B có thể nhận các frame 2, 3 và 4 nhưng B chưa phản hồi ngay khi nhận được các frame 2 và 3, B đợi khi đã nhận được frame 4 mới phản hồi bằng một ack với số hiệu 5, như vậy B phản hồi các frame 2,3 và 4 cùng một lúc. A cần duy trì một danh sách gồm các số của các frame đã được phép gửi đi, B duy trì một danh sách gồm các số của các frame chuNn bị được nhận, mỗi một danh sách được ví như là một của sổ của các frame và hoạt động trên cửa sổ này gọi là cửa sổ trượt. Vì các số hiệu của frame chiếm một trường trong frame và trường này là vị giới hạn về kích thước, ví dụ với một trường có độ dài 3 bits Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 8 các số hiệu sẽ được phân bố từ 0 đến 7 do đó các frame sẽ được đánh số theo các số dư của phép chia cho 8 (1 đến 7) do đó sau số 7, số tiếp theo sẽ là số 0, khi đó độ lớn của cửa sổ là 8. Một cách tổng quát, với trường có độ dài k bits, số hiệu của các số sẽ từ 0 đến 2k-1 và các frame sẽ được đánh số theo các số dư của phép chia cho 2k Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 9 Frames đã được gửi đi Các frames được lưu giữ trong buffer cho đến khi nhận được trả lời … 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Số thứ tự Cửa sổ thu hẹp lại từ cuối Cửa sổ mở rộng Khi các frames được gửi khi nhận được ACK Frame cuối được trả lời Frame cuối cùng đã được truyền đi Bên gửi Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 10 Frames đã nhận được … 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Số thứ tự Frame cuối được trả lời Frame cuối cùng đã nhận được Bên nhận II. CÁC KỸ THUẬT ĐIỀU KHIỂN, KIỂM SOÁT LỖI. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 11 1. Kiểm soát lỗi Kiểm soát lỗi liên qua đến các cơ chế để phát hiện và sửa các lỗi nảy sinh trong quá trình truyền các frame. Các frame được truyền đi theo một thứ tự, các frame này đến đích theo thứ tự này và mỗi một frame bị ảnh hưởng bởi một khoảng trễ ngẫu nhiên trước khi được nhận. Có hai loại lỗi có thể sảy ra, đó là: mất frame và hỏng frame. + Mất frame: Một frame không đến được bên nhận. Ví dụ các tạp nhiễu có thể phá hủy một frame đến một mức mà bên nhận không biết được rằng một frame đã được truyền đi. + Hỏng frame: Một frame đã được nhận nhưng một vài bit bị lỗi. Các kỹ thuật phổ biến nhất để kiểm soát lỗi là: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 12 - Phát hiện lỗi - Xác nhận dương: Bên nhận trả lại một xác nhận rõ ràng để thông báo đã nhận được frame không có lỗi. - Truyền lại sau khi đã hết thời gian phản hồi: Bên gửi gửi lại frame khi không nhận được trả lời của bên nhận và đã hết thời gian phản hồi. - Xác nhận âm và truyền lại: Bên nhận trả lời bằng một xác nhận âm cho một frame bị lỗi do đó bên gửi sẽ gửi lại frame này. Một cách chung nhất, các cơ chế này liên quan đến tự động lặp lại yêu cầu (Automatic Repeat Request – ARQ). Tác dụng của ARQ là Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 13 chuyển một liên kết dữ liệu không tin cậy thành một liên kết dữ liệu đáng tin cậy. Có ba phiên bản của ARQ đã được chuNn hóa: + Dừng và đợi ARQ (Stop and Wait) + Quay lui - N ARQ (Go back – n) + Loại bỏ có lựa chọn (Selective Reject ARQ) 2. Dừng và đợi (Stop – and – Wait – ARQ) Dừng và đợi dựa trên kỹ thuật điều khiển luồng dừng và đợi. Máy gửi gửi đị một frame sau đó bắt buộc phải đợi cho đến khi nhận được trả lời của bên nhận, không có dữ liệu nào được gởi đi trong khi đợi này. Có hai loại lỗi có thể sảy ra đó là: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 14 a, Một frame đến được máy đích có thể bị lỗi: bên nhận sử dụng kỹ thuật phát hiện lỗi nên phát hiện được lỗi này, do đó vứt bỏ frame này. Để đối phó với khả năng này, bên gửi sử dụng một thiết bị đếm thời gian, sau khi gửi đi một frame bên gửi đợi nhận đựợc sự trả lời của bên gửi. Nếu sau một khoảng thời gian được tính toán trước mà bên gửi không nhận được bất kỳ sự trả lời nào của bên nhận do đó bộ đếm thời gian đã hết, bên gửi sẽ tiến hành gửi lại frame này. Với phương pháp này bên gửi cần duy trì một bản sao chép của frame vừa gửi cho đến khi nhận được sự trả lời của bên nhận để khi cần có thể gửi lại frame. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 15 b, Khả năng hỏng ACK: Bên gửi gửi đi một frame, bên nhận nhận được frame này không bị lỗi, khi đó bên nhận sẽ trả lời bằng một ACK, trên đường truyền ACK này có thể bị hỏng do đó bên gửi không nhận được ACK này, do dó sau khi hết thời gian đợi sự trả lời bên gửi sẽ gửi lại frame này, do đó bên nhận sẽ nhận được một frame giống hệt nhau nhưng không biết đấy chỉ là một frame. Để tránh trường hợp này các frame sẽ được đánh số lần lượt là 0, 1 và các trả lời sẽ được đánh số là ACK0 và ACK 1, trong đó ACK0 được dùng để trả lời cho frame 1 (bên nhận đã nhận được frame 1 và đang đợi frame 0) và ngược lại. Khi bên nhận nhận được hai frame có cùng số Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 16 hiệu (cùng là frame 1 hoặc frame 0) nó sẽ bỏ đi frame thứ hai vừa nhận được. Ưu điểm chính của phương pháp này là đơn giản, nhược điểm chính của phương pháp này không hiệu quả. 3. Quay lui n (Go back n – ARQ) Phương pháp điều khiển lỗi dựa trên điều khiển luồng bằng cửa sổ trượt được gọi là quay lui n ARQ. Trong phương pháp này, một trạm có thể gửi đi một chuỗi các frame các frame được đánh số theo như cách điều khiển luồng bằng cửa sổ trượt. Số hiệu của các frame chưa được trả lời được xác định bởi cửa sổ trượt sử dụng kỹ thuật điều khiển luồng bằng cửa sổ trượt. Khi không có lỗi sảy ra bên nhận sẽ Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 17 trả lời frame vừa nhận được bằng một RR (receive ready - sẵn sàng nhận), nếu một frame nhận được bị lỗi, bên nhận gửi lại một thông báo REJ (Reject - vứt bỏ) cho frame này, bên nhận sẽ vứt bỏ frame vừa nhận được và tất cả các frame nhận được sau đó cho đến khi nhận được frame này không bị lỗi. Bên gửi khi nhận được REJ sẽ phải truyền lại frame bị lỗi và tất cả các fram đã truyền sau frame bị lỗi này. Giả sử rằng máy A đang gửi các frame cho máy B, sau mỗi lần truyền đi một frame, bên A sẽ thiết lập bộ đếm thời gian cho sự trả lời của frame này. Giả sử rằng máy B đã nhận được frame i-1 không bị Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 18 lỗi và máy A vừa gửi đi frame i. Kỹ thuật quay lui n cần phải giải quyết các khả năng sau: a, Hỏng frame: Nếu một frame nhận được bởi B bị lỗi hoặc frame này bị lỗi nên B không nhận biết được frame này do đó B sẽ vứt bỏ frame này và không có hành động gì, có hai khả năng nhỏ sau: i, Sau 1 khoảng thời gian đợi hợp lý, A sẽ gửi đi frame thứ i+1, bên B nhận được frame i+1 không đúng thứ tự (B đang đợi frame i) do đó B sẽ gửi thông báo REJi, A sẽ phải gửi lại frame i và các frame đã gửi sau frame i này. ii, A không gửi đi thêm frame nào, B không nhận được frame nào nên không gửi trả lời cho A (hoặc là RR hoặc REJ) do đó bộ đếm Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 19 thời gian của A bị hết, A sẽ gửi đi một frame có tên là RR với một bit p được gán giá trị 1. B sau khi nhận được frame này với bit p bằng 1 thì hiểu rằng A yêu cầu trả lời của B với số hiệu của frame tiếp theo mà B đang đợi (đó là frame i), A sau khi nhận được RR từ B sẽ gửi lại frame i. Một cách giải quyết khác là sau khi hết thời gian đợi sự trả lời của B, A sẽ gửi lại frame i. b, Hỏng RR: Có hai khả năng sau: i, B nhận được frame i không có lỗi nên sẽ gửi trả lời RR (i+1), trả lời này bị hỏng, do trả lời có thể là tích tụ dần (đã giải thích ở trên) nên A có thể nhận được một RR cho một frame gửi sau và RR này có thể đến được A trước khi bộ đếm thời gian cho frame i hết hạn. Khi Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 20 đó A không nhận được RR(i+1) nhưng nhận được một RR(i+2) do đó A biết rằng frame i và i+1 đã nhận được không có lỗi. ii, Nếu bộ đếm thời gian đã hết mà chưa nhận được trả lời của B, A sẽ gửi đi một RR frame như trường hợp thứ hai của hỏng frame và thiết lập lại bộ đếm thời gian khác được gọi là bộ đếm thời gian p bit. Nếu không có trả lời của B cho RR frame của A thì bộ đếm thời gian của p bit sẽ bị hết, A lặp lại thao tác này một số lần nữa mà vẫn không nhận được trả lời của B thì nó sẽ thiết lập lại thủ tục gửi tin giữa hai máy. + Hỏng REJ: Trường hợp bị lỗi REJ tương tự như trường hợp a(ii) 4. Loại bỏ có lựa chọn (Selective Reject – ARQ) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 21 Với loại bỏ có lựa chon ARQ chỉ các các frames nhận được với xác nhận âm hoặc các frames không nhận được phản hồi sau khi đã hết thời gian là phải truyền lại. Ví dụ: bên B nhận được frame 5 không đúng thứ tự (B đang đợi nhận frame 4) khi đó B sẽ gửi đi SREJ4 điều này có nghĩa là B đang đợi frame 4, và B vẫn tiếp tục nhận các frame khác, khi đó A sẽ gửi lại frame 4. Loại bỏ có lựa chon ARQ hoạt động có hiệu quả hơn so với quay lui N ARQ vì chỉ có một số ít các frames phải truyền lại, tuy nhiên bên nhận phải duy trì một bộ đệm tương đối lớn để lưu giữ các frames đã nhận được cho đến khi nhận được frame bị lỗi trước đó và sắp xếp frame này vào đúng vị trí. Bên gửi cũng phải có khả năng để Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 22 gửi một frame không theo đúng thứ tự. Vì những lý do phức tạp trên nên Loại bỏ có lựa chon ARQ ít được sử dụng rộng rãi như là quay lui N ARQ. Loại bỏ có lựa chon ARQ được áp dụng cho truyền vệ tinh vì thời gian trễ trong truyền thông vệ tinh tương đối cao.