So sánh go back n và selective repeat
|
- Idle RQ (Stop – and – wait ARQ): là kỹ thuật kiểm soát lỗi được dùng với các lược đồ truyền số liệu thiên hướng ký tự (character oriented). - Continuous RQ được chia thành hai loại: truyền lại có chọn lựa (Selective – repeat ARQ) hoặc truyền lại một nhóm (Go – back – N ARQ). Continnuous RQ được dùng chủ yếu trong các lược đồ truyền thiên hướng bit (bit – oriented). Mặc dù cơ chế Idle RQ đang bị Continuous RQ thay thế trong nhiều ứng dụng để việc truyền đạt hiệu quả cao hơn, nhưng vẫn còn nhiều giao thức liên kết số liệu đang được dùng có cơ sở là Idle RQ. Tuy vậy, điều quan trọng hơn vẫn là do Idle RQ là lược đồ kiểm soát lỗi đơn giản nhất, nó tạo nên một phương tiện lý tưởng để lý giải nhiều vấn đề tổng quát hơn liên quan đến các giao thức liên kết số liệu. 5.4.1. Idle RQ Đặc điểm Idle RQ còn gọi là Stop - and - wait ARQ hay ARQ dừng - và - chờ, là dạng điều khiển lưu lượng truyền dạng ngừng và chờ, có nghĩa là sau khi máy phát gửi đi một khung dữ liệu thì nó phải đợi máy thu báo cho biết khung dữ liệu đó có được nhận thành công hay không. Sau đó, máy phát gửi khung kế tiếp nếu khung trước đó nhận tốt hoặc truyền lại một bản sao của nó nếu nhận được không thành công. Để có thể gửi lại dữ liệu, có đặc điểm cho cơ chế kiểm tra lỗi như sau: - Thiết bị phát lưu một bản sao của khung gửi cuối cùng cho đến khi nhận được tín hiệu chấp nhận khung này. Việc lưu giữ bản sao (copy) nhằm để bộ phát gửi lại khung bị thất lạc hoặc bị hỏng cho đến khi khung được nhận đúng. - Nhằm mục đích nhận dạng, tất cả các khung dữ liệu và ACK đều được đánh số tuần tự là 0 và 1. Nếu khung dữ liệu 0 thì sẽ có tín hiệu ACK là 1, cho thấy là bộ thu đã nhận được dữ liệu 0 và đang chờ dữ liệu 1. Cách đánh số này cho phép nhận dạng các khung dữ liệu trong trường hợp phải gửi lại nhiều lần. - Thiết bị phát được trang bị một bộ định thời (timer), nếu không nhận được tín hiệu xác nhận cần thiết trong một khoảng thời gian xác cho phép (timeout), máy thu sẽ hiểu là khung dữ liệu vừa gửi đã bị thất lạc và sẽ tiếp tục gửi lại lần nữa. Có hai phương pháp để thực hiện lược đồ Idle RQ. - Phương pháp thứ nhất là phương pháp truyền lại ngầm định (implicit retrainsmission). Máy thu chỉ gửi đi xác nhận dương ACK để báo nhận thành công với những khung được không phát hiện ra lỗi. Nếu khung dữ liệu bị lỗi thì máy thu không gửi gì cả. Máy phát không nhận được xác nhận dương ACK thì nó sẽ ngầm hiểu là khung dữ liệu đã bị hỏng và thực hiện việc gửi lại khung đó. - Phương pháp thứ hai là phương pháp yêu cầu (explicit request). Phương pháp này yêu cầu máy thu phải gửi báo nhận âm NAK cho khung dữ liệu bị mất hoặc khung dữ liệu nhận được bị lỗ. Idle RQ đòi hỏi máy phát phải chờ cho đến khi nhận được tín hiệu ACK của khung cuối cùng vừa gửi, trước khi chuyển khung kế tiếp. Khi máy phát nhận được NAK, máy phát phải gửi lại khung đã gửi của lần nhận ACK trước, không kể số lượng. Hoạt động Lỗi khung dữ liệu: Nếu máy thu phát hiện một khung vừa nhận có lỗi thì sẽ chuyển về một khung NAK và máy phát sẽ chuyển lại khung vừa chuyển. Ví dụ 5.8: trong hình bên dưới, máy phát chuyển một khung dữ liệu Data 0. Máy thu chuyển về một tín hiệu ACK1, cho biết data 0 đã đến tốt và máy thu đang chờ data 1. Máy phát chuyển tiếp khung dữ liệu Data 1. Tín hiệu được nhận tốt, máy thu chuyển về ACK 0. Máy phát chuyển tiếp khung dữ liệu mới: data 0. Máy thu nhận ra lỗi và gửi về NAK. Máy phát gửi lại data 0. Trường hợp này máy thu tốt, nên máy thu chuyển về tín hiệu ACK 1. Hình 5.19. Truyền dữ liệu trong giao thức Stop and Wait ARQ khi lỗi khung dữ liệu Mất khung - Bị mất khung dữ liệu trong quá trình truyền - Bị mất khung ACK trong quá trình truyền - Bị mất khung NAK trong quá trình truyền Mất khung data: Hình 5.20. Truyền dữ liệu trong giao thức Stop - and - wait ARQ khi mất khung dữ liệu Máy phát có trang bị bộ định thời khi truyền dữ liệu. Máy phát chờ đợi tín hiệu ACK hay NAK khi tín hiệu được nhận, nếu tín hiệu không đến nơi nhận, sẽ không có ACK hay NAK, máy thu đợi hết thời gian qui định, sẽ gửi lại bản tin vừa gửi rồi chờ đợi thông tin xác nhận từ máy thu. Mất khung ACK và NAK: Trường hợp này, khung dữ liệu đã tới được máy thu, nhưng tín hiệu ACK và NAK lại bị thất lạc trong khi gửi về. Máy phát chờ cho đến khi hết thời gian do timer qui định, và tiếp tục gửi khung vừa gửi. Máy thu nhận và kiểm tra, nếu tín hiệu là NAK, máy thu chấp nhận khung mới này và gửi trả lời bằng ACK. Nếu mất khung là ACK thì nhận khung copy này như là bản sao, chấp nhận rồi hủy đi để chờ bản tin kế tiếp đến. Hình 5.21. Truyền dữ liệu trong giao thức Stop and Wait ARQ khi mất ACK hoặc NAK Hiệu suất Stop and Wait ARQ - Hiệu suất truyền trên kênh không lỗi Có thể bạn quan tâm! Xem toàn bộ 210 trang tài liệu này. A B tprop Frame tf time tproc tack tprop Hình 5.22. Các phần tử trễ trong Stop and Wait ARQ Hình 5.22 chỉ ra các thành phần trễ cơ bản t0 trong giao thức Stop - and - Wait ARQ từ khi khung dữ liệu bắt đầu truyền vào kênh tới khi ACK được xác nhận. Bit đầu tiên được đặt vào kênh truyền cho tới khi xuất hiện tại đầu ra của kênh sau một thời gian truyền tprop; bit cuối cùng của khung được nhận tại trạm B sau khi cộng thêm tf giây. Trạm B yêu cầu tproc giây để chuẩn bị một khung ACK, nó sẽ yêu cầu tack giây thời gian truyền. Sau đó cộng thêm một thời gian trễ truyền để khung ACK nhận được tại trạm A. Cuối cùng là thời gian tproc được cộng thêm để lấy ra mã kiểm tra CRC. Như vậy tổng thời gian để gửi một khung và nhận một ACK trong trường hợp bỏ qua lỗi được tính như sau : t0 2t prop 2t proc t f tack 2t prop 2t proc n f R na R (5.7) Trong công thức trên, ta đã lấy xấp xỉ thời gian xử lý khung dữ liệu bằng thời gian xử lý khung ACK. Trong đó: nf là số bit trong khung dữ liệu. na là số bit trong khung ACK R là tốc độ của kênh truyền Tốc độ truyền tin hiệu quả: (5.8) Trong đó n0 là số bit của header và CRC trong một khung Như vậy hiệu suất truyền của Stop and Wait ARQ là tỉ số giữa Reff và R . h Reff 0 R n f n0 t0 R 1na n f 1n0 n f 2(t prop t n f proc)R (5.9) Trong thực tế hầu hết các trường hợp phù hợp với giao thức Idle RQ, thời gian xử lý tproc đều rất nhỏ so với thời gian truyền tprop, số bit khung ACK header và CRC n0 cũng nhỏ hơn rất nhiều so với khung dữ liệu nf nên qua. Biểu thức hiệu suất là: na và số bit của na , n0 có thể bỏ h Reff 0 R nf t nf R(2t t t f ) 2t t (5.10) Hay: h0 1 0 R 1 2tprop prop f prop f (5.11) Đặt: t f a tprop , do đó: t f h0 1 1 2a (5.12) - Hiệu suất truyền trên kênh có không lỗi Gọi Pf là xác suất để một khung truyền có lỗi. Ta giả sử rằng khung truyền có lỗi độc lập với các khung khác → xác suất truyền khung đến máy thu không lỗi f là 1 P . f Trong đó: 1P 1pnf en f p ; p : tỉ lệ lỗi bit trên đường truyền Để tính hiệu suất của truyền của Stop and Wait ARQ chúng ta cần tính tổng thời gian trung bình để tạo ra một khung không lỗi là Khi đó hiệu suất truyền sẽ là: t0 . 1 Pf n f n0 t0 1n0 hSW Reff R 1Pf R 1na n f 2(t n f prop t n f proc)R (1Pf ) (5.13) Tương tự như trong phần xét hiệu suất truyền trên kênh không lỗi, nếu xét trong các trường hợp thực tế, bỏ qua tproc , na và. Biểu thức hiệu suất là: hSW 1Pf 1 2a (5.14) Ví dụ 5.10: Truyền 1500 byte thông tin theo giao thức HDLC, sử dụng giao thức Stop - and - wait ARQ. Giả sử bỏ qua thời gian xử lý gói tin tại nút và chiều dài gói tin ACK là rất nhỏ. Xác định hiệu suất sử dụng đường truyền trong bốn trường hợp: Tốc độ truyền tín hiệu: - 1Kbaud - 1Mbaud Sử dụng kỹ thuật điều chế 4-ASK, tốc độ lan truyền tín hiệu là 2.108 m/s. Dữ liệu được truyền trên hai loại môi trường: - Cáp xoắn đôi chiều dài 1km. - Đường kênh thuê riêng chiều dài 1000 km. Giả thiết các đường truyền là không nhiễu. Đánh giá các kết quả thu được? Giải: Trường hợp 1: Tốc độ truyền 1Kbaud, Cáp xoắn đôi chiều dài 1km Vì sử dụng kỹ thuật điều chế 4-ASK nên tốc độ bit là: R= Rslog2M =103 log24 = 2. 103 bps Thời gian cần truyền 1 frame t f là: t f \= số bit trong frame/ tốc độ bit (bps) \=1500.8/2. 103 \= 6s Thời gian lan truyền: S t prop V \=103 /2.108 \= 5. 10-6 s h0 1 1 2a a=5. 10-6/6=83. 10-8 Do đó 1+2a 1 nên h0 1 Trường hợp 2: Tốc độ truyền 1Kbaud, đường kênh thuê riêng chiều dài 1000 km. 3 8 -3 t f \=1000. 10 /2.10 = 5. 10 s a=5. 10-3/6=83. 10-5 do đó 1+2a 1 nên h0 1 Trường hợp 3: Tốc độ truyền 1Mbaud, Cáp xoắn đôi chiều dài 1km Vì sử dụng kỹ thuật điều chế 4-ASK nên tốc độ bit là: R= Rslog2M \=106 log24 \= 2. 106 bps 6 -3 t f \=1500.8/2. 10 = 6. 10 s S t prop V \= 103 /2.108 \= 5. 10-6 s a =5. 10-6/6. 10-3\=0.83. 10-3 Do đó 1+2a 1 nên h0 1 Trường hợp 4: Tốc độ truyền 1Mbaud, Đường kênh thuê riêng chiều dài 1000 km. t prop S \= 1000.103 /2.108 \= 5. 10-3 s V a = 5. 10-3/6. 10-3\=0.83 h0 \= 1/(1+2*0.83)=0.38 Nhận xét Giao thức Stop - and - wait ARQ hoàn toàn thích hợp cho các liên kết ngắn và có tốc độ vừa phải. Các liên kết mặt đất dài hơn thì hiệu suất sử dụng liên kết sẽ cao ứng với tốc độ dữ liệu thấp và hiệu suất sẽ giảm đáng kể nếu tốc độ dữ liệu cao. Ưu điểm chính của giao thức Stop - and - wait ARQ là nó yêu cầu lượng bộ đệm tối thiểu để thực hiện vì cả máy phát và máy thu chỉ cần chứa đủ một khung, Ngoài ra máy phát chỉ phải duy trì một số định danh của khung nhận thành công sau cùng để phát hiện sự trùng lặp. 5.4.2. Continuous RQ 5.4.2.1. Go - back - N ARQ (Truyền lại một nhóm) Đặc điểm Có nhiều cơ chế dùng để kiểm tra lỗi khi truyền dữ liệu liên tục, có hai giao thức thông dụng là: Go - back - N ARQ và Selective - repeat ARQ. Cả hai phương pháp này đều dựa trên phương pháp điều khiển dùng cửa sổ trượt. Để mở rộng được cửa sổ nhằm bao hàm việc truyền lại các khung thất lạc hay bị lỗi. Có ba đặc điểm được vào trong cơ chế điều khiển lưu lượng: - Thiết bị phát lưu một bản sao của tất cả các khung gửi đi cho đến khi chúng được xác nhận. - Trong cửa sổ trượt ARQ được trang bị bộ định thời có khả năng xử lý các xác nhận bị thất lạc. - Trong cửa sổ trượt ARQ, (n-1) khung (kích thước của cửa sổ) có thể được gửi đi trước khi nhận được xác nhận. Nếu (n-1) khung là các xác nhận mong đợi, máy phát khởi động bộ định thời và chờ trước khi gửi nữa. Nếu đã hết thời gian cho phép mà không nhận được xác nhận thì máy phát giả sử là các khung chưa nhận được và gửi lại một hay tất cả các khung tùy theo từng giao thức. Chú ý rằng trong phương pháp Stop - and - wait ARQ, máy phát không có cách nào biết được là khung bị thất lạc là dữ liệu, ACK hay NAK. Bằng cách gửi lại các khung dữ liệu, có hai khả năng khôi phục: dữ liệu thất lạc và NAK thất lạc. Nếu thất lạc khung là khung ACK thì máy thu có thể nhận biết sự dư thừa thông qua số trên khung và loại các dữ liệu thừa. Hoạt động Trong phương pháp cửa sổ trượt Go - back - N ARQ, nếu một khung bị thất lạc hay hỏng, tất cả các khung được phát khi tín hiệu xác nhận cuối cùng được gửi đi. Có 3 dạng phát lại: Lỗi khung dữ liệu, mất khung dữ liệu và mất khung ACK. Để đơn giản ta giả sử với các trường hợp cụ thể như sau Lỗi khung dữ liệu: Việc gì xảy ra nếu các khung 0, 1, 2 và 3 đã được gửi đi, nhưng tín hiệu xác nhận đầu tiên lại là NAK 3? Chú ý rằng NAK có hai ý nghĩa: (1) một xác nhận về tất cả các khung nhận được trước khi có khung bị hỏng và (2) tín hiệu không xác nhận đối với khung hiện tại. Nếu NAK đầu tiên là NAK 3, có nghĩa là các khung dữ liệu 0, 1, và 2 đã được nhận tốt. Chỉ cần gửi lại khung số 3. Việc gì xảy ra nếu các khung từ 0 đến 4 đã được gửi đi trước khi nhận được NAK 2? Ngay vừa khi máy thu phát hiện lỗi, thì máy ngừng tiếp nhận các khung cho đến khi khung bị hỏng được thay thế xong. Trong trường hợp này thì dữ liệu 2 xuất hiện hỏng và bị loại, cùng các dữ liệu 3 và 4. Dữ liệu 0 và 1, đã được nhận trước khi có khung bị hỏng, đã được chấp nhận, bằng cách gửi về máy phát khung NAK 2. Như thế cần gửi lại các khung 2, 3 và 4. Sender Receiver ` ` Data 0 Data 1 Data 2 Data 3 Data 4 ACK 3 Error, Discarded Discarded NAK 3 Data 5 Discarded Resent Resent Data 3 Data 4 Resent Data 5 Time Time Hình 5.23. Hoạt động của Go - back - N khi lỗi khung dữ liệu Hình 5.23 là một ví dụ về hoạt động của Go - back – N, trong đó 6 khung được gửi đi trước khi phát hiện ra lỗi ở khung 3. Trường hợp này máy thu gửi về tín hiệu ACK 3 cho biết các khung 0, 1 và 2 đã được chấp nhận. Trong hình thì ACK 3 đã được gửi trước khi dữ liệu 3 đến. Phát hiện lỗi tại khung 3, tín hiệu NAK được gửi tức thì và |
