Bài giảng Truyền thông kỹ thuật số - Chương 4: Các nghi thức điều khiển liên kết dữ liệu - Trịnh Huy Hoàng

CHƯƠNG 4 CÁC NGHI THỨC ĐIỀU KHIỂN LIÊN KẾT DỮ LIỆU Giảng viên: Trịnh Huy Hoàng Email:hoangth@hcmup.edu.vnNội dungVần đề khi trao đổi dữ liệuĐồng bộ khungDữ liệu được truyền theo khungĐiều khiển dòng dữ liệuĐiều khiển tốc độ truyền dữ liệuĐiều khiển lỗiXử lý lỗi gặp phải trên đường truyềnĐịnh vị địa chỉXác định 2 thiết bị trao đổi dữ liệu trên đường truyềnTích hợp dữ liệu và điều khiển trên cùng đường truyềnPhân biệt dữ liệu và thông tin điều khiểnQuản lý liên kếtCấp phát, duy trì và giải phóng đường truyền giữa 2 thiết bịĐiều khiển dòng dữ liệuBảo đảm cho việc bên phát không gởi dữ liệu quá nhanhNgăn ngừa việc tràn bộ đệmKhái niệm thời gianThờ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.Điều khiển dòng dữ liệuMô hình truyền khungIdle RQ (Stop–and–Wait)Đặc điểmĐượ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-duplexCơ chế hoạt độngNguồ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 ACKNguồn đợi ACK trước khi phát tiếp dữ liệuĐích có thể ngưng bằng cách không gởi ACKThích hợp khi chỉ có vài frame có kích thước lớnDữ 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ạnLỗi được phát hiện sớm Khi có lỗi, chỉ cần truyền lại frame nhỏ Ngăn ngừa tình trạng 1 trạm làm việc chiếm đường truyền lâu  Stop-and-wait protocol không thích hợpIdle RQ (Stop–and–Wait)AnimationIdle RQ – Hiệu suấtThời gian tổng cộng Hiệu suất đường truyềnSliding windowsCơ chế hoạt độngCho phép nhiều frame có thể truyền đồng thờiBên thu có bộ đệm với kích thước WBên phát có thể truyền tối đa W frame mà không cần đợi ACKCơ chế đánh số thứ tự cho các frameACK có chứa số của frame kế tiếp đang được mong đợi Số thứ tự được quay vòng bởi kích thước cửa sổ (modulo 2k)Sliding windowsAnimationSliding windowsSliding windowsĐiều khiển lỗiCung cấp cơ chế cho việc truyền dữ liệu trong trường hợp dữ liệu bị mất hay sai sót trên đường truyềnBảo đảm dữ liệu nhận được đúng và chính xácLoại lỗiMất frame: frame không đến đích hoặc đến nhưng thông tin điều khiển trên frame bị hư, không thể xác định đượcFrame hư: thông tin điều khiển trên frame xác định được, nhưng dữ liệu trong frame bị hưKỹ thuật dùng để điều khiển lỗiPhát hiện lỗi (CRC, Parity, )Positive ACK – xác nhận các frame nhận đượcTruyền lại sau một thời gian time-outNegative ACK (NAK) và truyền lại – yêu cầu truyền lại (NAK) cho các frame bị hưĐiều khiển lỗiARQ (Automatic Repeat Request)Cơ chế cho phép các nghi thức liên kết dữ liệu quản lý lỗi và yêu cầu truyền lạiPhân loạiIdle RQ (stop-and-wait)Dùng với cơ chế điều khiển dòng stop-waitĐược dùng chủ yếu trong truyền dữ liệu là ký tự hay byte thông tin (character-oriented or byte-oriented)Continuous RQDùng với cơ chế điều khiển dòng sliding-windowĐược dùng chủ yếu trong truyền dữ liệu là bit thông tin (bit-oriented)Được chia làm hai loại tùy theo cách thức sửa lỗi: selective reject và go-back-NGo Back NSelective rejectStop–and–Wait Cơ chế hoạt độngA gởi một I-Frame (Information Frame) đến BA đợi trả lờiACK-Frame – A gới tiếp dữ liệuNAK-Frame – A gời lại dữ liệuKhông nhận được trả lời – A gởi lại sau thời gian time-outLặp lại các bước trênƯu/khuyết điểmĐơn giảnKhông hiệu quảVấn đềI-Frame nhận được, nhưng ACK bị mất/hư?Có dùng được cho cơ chế sliding-window không?Stop–and–WaitCơ chế hoạt độngTrong trường hợp lỗi xảy ra(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ị saiStop–and–Wait Sửa lỗi E1Sử 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 báo về thì xem như I-Frame chưa tới và gởi lại frame này.Stop–and–Wait Sửa lỗi E2Implicit retransmission: sử dụng timerExplicit retransmission: NAK-Frame (negative acknowledgement frame)Stop–and–Wait Sửa lỗi E3Lỗi lặp lại frame (duplicated frame): dùng chỉ số tuần tự frame (sequential number)Stop–and–Wait Hoạt động tốtStop–and–Wait I-Frame không đếnStop–and–Wait ACK-Frame hư/không đếnStop–and–Wait I-Frame hưGo–back–N Cơ chế hoạt độngĐiều khiểnRR = receive ready = ACK = acknowledgeREJ = reject = NAK = negative acknowledgeDựa trên cơ chế sliding windowA 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ự ? thứ tự I-Frame truyền được bảo đảmTruyền lại tất cả các Frame sai kể từ Frame sai đầu tiên trở đi, bất kể các I-Frame sau là đúng hay saiI-Frame hưA gởi frame i, B phát hiện lỗi và gới NAKi, A gởi lại các frame, kể từ frame iFrame i bị mất nhưng frame i+1 nhận được, B gởi NAKi, A gởi lại các frame kể từ frame iFrame i bị mất và sau i, không còn frame nào được gởi. A không nhận được trả lời, sẽ gởi lại frame I sau một thời gian time-outACK hưB nhận được frame i, gởi ACKi, nhưng ACK này bị mấtA đợi hoài, sẽ gởi lại các frame, kể từ frame iA gởi frame i, i+1, i+2. B gởi ACKi+2, được hiểu như bao gồm ACKi, ACKi+1NAK hưA đợi hoài, sẽ gởi lại các frame, kể từ frame iGo–back–N Go–back–N Trong trường hợp lỗi xảy ra: các kiểu lỗi cũng tương tự như trong Idle RQ (E1) I-Frame không đến được bên nhận, và lỗi này có thể xảy ra đồng thời trên cùng nhiều I-Frame(E2) I-Frame đến được bên nhận, nhưng nội dung I-Frame sai, lỗi này cùng có thể xảy ra đồng thời trên nhiều I-Frame(E3) ACK-Frame không đến được bên nhận, hay đến được bên nhận nhưng nội dung frame bị sai, lỗi này có thể xảy ra đồng thời trên nhiều ACK-frameGo–back–N Sửa lỗi E1 Sử dụng danh sách truyền lại (Retransmission list) để lưu các I-Frame gởi đi nhưng chưa có ACK báo về. Bên thu nếu nhận được các I-frame không đúng thứ tự sẽ yêu cầu truyền lại các frame kể từ frame không nhận được (bằng cách gởi NAK). Bên gởi sẽ lấy ra I-Frame từ danh sách này ra truyền lạiSử 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 báo về (có thể do bên thu không gởi NAK) thì xem như I-Frame này chưa tới và gởi lại các frame kể từ frame nàyGo–back–NSửa lỗi E2 Implicit Retransmission: dùng timerKhi một I-Frame truyền đến bên nhận nhưng bị lỗi, bên nhận không đáp ứng tín hiệu  sau thời gian timeout, bên gởi sẽ truyền lại I-Frame này. Nếu có nhiều I-Frame sai thì cách sửa lỗi cũng tương tự như trong trường hợp E1Explicit Retransmission: dùng NAK-FrameKhi một I-Frame truyền đến bên nhận nhưng bị lỗi, bên nhận sẽ báo lại cho bên gởi biết trường hợp này thông qua NAK-Frame. Như vậy thời gian đáp ứng sẽ nhanh hơn. Khi NAK-Frame bị lỗi hay không đến được bên gởi, sau thời gian timeout bên gởi cũng sẽ tiến hành gởi lại I-Frame nàyGo–back–NSử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, mặc dù lúc đó bên nhận đã nhận đúng I-Frame này (lỗi trùng I-frame)  phải dùng chỉ số tuần tự frame để phân biệt giữa các I-frame với nhauDo bên nhận chỉ nhận I-Frame theo đúng chỉ số tuần tự  nếu bên gởi nhận được ACK(N+i+1) thì biết chắc chắn là bên nhận đã nhận đúng tất cả các I-Frame có chỉ số từ N  N+1, do đó bên gởi vẫn không gởi lại các I-Frame từ N  N+1 mặc dù ACK của các I-Frame này có thể bị lỗi hay bị mất ? tăng hiệu suấtNếu sau thời gian timeout mà bên gởi vẫn không nhận được ACK/NAK nào, nó sẽ gởi lại các frame kể từ frame cuối cùng nhận được ACKGo–back–N Khái niệmGiả sử dòng các I-Frame đi theo một chiều và chiều kia chỉ dùng cho ACKCác frame thông tin điều khiển đủ chỗ để chứa ACK (piggybacked acknowledgment), do đó việc trao đổi dữ liệu full-duplex sẽ chứa ACK. NAK thường được gởi riêng, không theo kiểu piggybackACKN xác nhận cho frame N-1Selective RejectCơ chế hoạt độngTương tự như Go-Back-N, ngoại trừ việc chỉ gởi lại các frame bị NAK hoặc time-outBên nhận có thể nhận frame thông tin không theo đúng chỉ số tuần tự  thứ tự frame thông tin truyền không được bảo đảm và bê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ốngA gởi 0-6 đến BB xác nhận tất cả, nhưng tất cả ACK đều bị mấtA đợi hoài, nên gởi lại 0B đã dịch cửa sổ nhận, nên có thể nhận 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ậnKích thước cửa sổ tối đa là ½(2n), tức 2n-1Selective RejectSelective RejectSử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 báo về thì xem như I-Frame chưa tới và gởi lại Frame nàySử dụng danh sách truyền lại (Retransmission list) để lưu các I-Frame gởi đi nhưng chưa có ACK báo về. Lúc lỗi sẽ lấy ra I-Frame từ danh sách này ra truyền lạiĐối với selective reject, khi lỗi xảy ra sẽ truyền lại chỉ các I-Frame sai. Do đó thứ tự I-Frame đến bên nhận là không có thứ tự và bên nhận phải có buffer để lưu lại các I-frame đến không đúng thứ tự nàySelective RejectSelective RejectSửa lỗi E2 Implicit Retransmission: dùng timerKhi một I-Frame truyền đến bên nhận nhưng bị lỗi, bên nhận không đáp ứng tín hiệu ? sau thời gian timeout, bên gởi sẽ truyền lại I-Frame này. Nếu có nhiều I-Frame sai thì cách sửa lỗi cũng tương tự như trong trường hợp E1Explicit Retransmission: dùng NAK-Frame.Khi một I-Frame truyền đến bên nhận nhưng bị lỗi, bên nhận sẽ báo lại cho bên gởi biết trường hợp này thông qua NAK-Frame. Như vậy thời gian đáp ứng sẽ nhanh hơn. Khi NAK-Frame bị lỗi hay không đến được bên gởi, sau thời gian timeout bên gởi cũng sẽ tiến hành gởi lại I-Frame nàySelective RejectSử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, mặc dù lúc đó bên nhận đã nhận đúng I-Frame này (lỗi trùng I-frame) ? phải dùng chỉ số tuần tự frame để phân biệt giữa các I-frame với nhauDo bên gởi chỉ truyền lại các I-Frame bị sai nên thứ tự I-Frame đến bên nhận không theo thứ tự, vì vậy bên nhận phải có buffer để lưu lại các frame đến không theo chỉ số tuần tự này. Khi nhận được I-Frame có đúng chỉ số, bên nhận sẽ lấy các I-Frame tuần tự tiếp theo từ buffer để đưa lên ứng dụngContinuous ARQ – So sánhĐiều khiển lỗi – Hiệu suấtStop-and-wait protocolGo-back-N protocolSelective reject protocolĐọc thêmW. Stallings, Data and Computer Communications (7th edition), Prentice Hall 2004, chapter 7