Bài giảng Truyền số liệu và mạng thông tin số - Chương 3: Các nghi thức lớp liên kết dữ liệu - Đặng Ngọc Hạnh

Nội dung text: Bài giảng Truyền số liệu và mạng thông tin số - Chương 3: Các nghi thức lớp liên kết dữ liệu - Đặng Ngọc Hạnh

1. CÁC NGHI THỨC LỚP LIÊN KẾT DỮ LIỆU  Kiểm soát lỗi (Errror Control)  Kiểm soát luồng (Flow Control)  Quản lý kết nối (Connection management)  Các nghi thức lớp liên kết dữ liệu 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 1
2. CÁC NGHI THỨC LỚP LIÊN KẾT DỮ LIỆU  Một số ký hiệu :  P : Primary (phía sơ cấp) là phía gửi đi các frame dữ liệu.  S : Secondary (phía thứ cấp) là phía thu các frame dữ liệu từ P. I -frame P  S ACK frame or NAK frame  I-frame (Information frame): khung thông tin chứa dữ liệu phía phát truyền cho phía thu.  I(N) : N là số tuần tự của khung thông tin đó  ACK frame (Acknowledge frame) : S truyền tới P để báo là đã nhận dữ liệu tốt (không bị lỗi).  NAK frame (Negative Acknowledge frame: S truyền tới P để báo là đã nhận dữ liệu sai (bị lỗi). 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 3
3. Idle RQ ( Stop and Wait )  Ứng dụng:  Trong kiểu truyền số liệu định hướng ký tự (character- oriented).  Hoạt động theo chế độ bán song công.  Định dạng của các frame trong Idle RQ như sau:  Có 3 loạl frame : I-frame, ACK-frame, NAK-frame.  Các frame này gọi là PDU (Protocol Data Unit) trong Idle RQ 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 5
4. Idle RQ ( Stop and Wait )  Đặc điểm :  P chỉ có một I – frame đang chờ ACK tại một thời điểm  Khi nhận một I – frame không bị lỗi, S truyền lại P một ACK frame,  Khi P nhận đựơc ACK của frame N, P sẽ tiếp tục truyền I – frame kế tiếp (N+1).  Khi P bắt đầu truyền I – frame, nó sẽ khởi động bộ định thời (Timer start), nếu quá khoảng thời gian giới hạn (time expires/restarts) mà không nhận được frame trả lời từ S thì P sẽ truyền lại frame đó.  Nếu S nhận được cùng 1 frame 2 lần thì sẽ loại bỏ bản copy. Điều này thực hiện được do trong mỗi I-frame P đều truyền kèm theo số tuần tự của frame.  Không tốn nhiều bộ nhớ đệm  Hiệu suất sử dụng đường truyền thấp 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 7
5. Idle RQ ( Stop and Wait )  Idle RQ - Explicit (Tường minh)  Khi S nhận được một frame bị lỗi, S truyền lại P một NAK frame, khi P nhận đựơc NAK của frame N, P sẽ truyền lại I(N). 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 9
6. Idle RQ ( Stop and Wait )  Hiệu suất sử dụng đường truyền 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 11
7. Idle RQ ( Stop and Wait )  Trường hợp có lỗi, các frame bị lỗi phải thực hiện việc truyền lại. Giả sử để truyền thành công 1 frame thì trung bình có Nr frame truyền lại, do đó xác suất một frame không lỗi là 1/Nr và thời gian truyền tổng cộng :  Hiệu suất:  Gọi P là xác suất một bit bị lỗi, khi đó xác suất một frame (chiều dài Ni) bị lỗi là: Ni Pf = 1 – (1 – P) NiP , nếu P <<1  Khi đó, xác suất frame không bị lỗi là 1 – Pf và do vậy 1 1 Pf 1 U Nr 1 P Nr (1 2a) 1 2a f 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 13
8. Idle RQ ( Stop and Wait )  S=10km, BER=10-4, R=9600bps 3 S10*10 5  Thời gian lan truyền sóng: T5*10(s) p V2*10 8 L1000  T0.1(s)ix Thời gian phát một khung dữ liệu: R9600 1000 L 4  Xác suất truyền đúng mỗi khung: Pf 1 BER 1 10 0.905 T * P0.1*0.905 U ix f 0.905  Hiệu suất liên kết: 1 5 T2*Tixp 0.1 2*5*10  S=100km, BER=10-4, R=10Mbps T * P 10 4 *0.905 UU ix f 0.0905  21 45 Tix 2*T r 10 2*50*10 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 15
9. Continuous RQ  Trong trường hợp có lỗi xảy ra trong quá trình truyền dẫn, có 2 cách truyền lại được áp dụng như sau:  S phát hiện và yêu cầu P truyền lại chỉ những frame bị lỗi. Kieu truyền lại nay được goi la truyền lại co lựa chon (selective – repeat).  S phát hiện và yêu cầu P truyền lại những frame chưa được trả lời ACK, nghĩa là tất cả các frame kể từ frame cuối cùng nhận đúng. Kiểu truyền này được gọi là lặp lại N (go-back-N).  Hiệu suất sử dụng đường truyền cao.  Cần bộ đệm lớn. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 17
10. Continuous RQ  Go back N  Giả sử I(N+1) bị lỗi  S nhận I(N+2) không đúng thứ tự (chưa nhận được frame N+1)  S gửi NAK (N+1) cho P để báo P bắt đầu truyền lại từ frame N+1 và bắt đầu khởi động timer để chờ nhận I(N+1), nếu qua một khoảng thời gian xác định mà không nhận được I(N+1) thì S truyền lại NAK(N+1) (đề phòng trường hợp NAK(N+1) bị lỗi).  S vào trạng thái truyền lại (Retransmission), tạm thời không trả lời ACK cho bất kỳ frame nào nhận được và chờ I(N+1).  Khi nhận được frame N+1, S trả lời ACK (N+1) và ra khỏi trạng thái truyền lại.  Bên S khi gởi một I–frame thì cũng khởi động timer. Sau khoảng thời gian Time Expires mà không nhận được tín hiệu trả lời của frame này thì sẽ truyền lại frame đó.  Bộ đệm thu không cần dung lương lớn. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 19
11. Continuous RQ 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 21
12. Continuous RQ  Selective repeat - Implicit Retransmission:  Giả sử I-frame N+1 bị lỗi :  S trả về ACK frame cho những I-frame đúng (N, N+2, N+3, ).  Khi nhận được ACK của I-frame N+2, P nhận thấy ACK (N+1) chưa nhận được P coi như N+1 bị lỗi P xóa I-frame N+2 ra khỏi bộ đệm và truyền lại frame N+1.  Giả sử ACK(N) bị lỗi :  Khi nhận được ACK của frame N+1, P phát hiện ACK(N) chưa nhận được, P nghĩ là frame N bị lỗi do đó P truyền lại frame N.  Khi nhận frame N lần thứ 2, S xác định được sự trùng lặp và do đó bỏ qua frame N, tuy nhiên S vẫn truyền trở về ACK(N) để đảm bảo P xóa I-frame N ra khỏi bộ đệm. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 23
13. Continuous RQ 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 25
14. Continuous RQ 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 27
15. KIỂM SOÁT LUỒNG (FLOW CONTROL)  Mục đích :  Điều khiển việc truyền dữ liệu giữa bên phát và bên thu sao cho đảm bảo bên thu luôn luôn có thể nhận được dữ liệu vào bộ đệm trước khi xử lý.  Theo các cơ chế điều khiển lỗi trên, có những thời điểm bộ đệm bên thu bị quá tải do lượng lớn dữ liệu truyền đến nhưng chưa được xử lý. Do đó việc mất dự liệu có thể xảy ra. Vì vậy phải báo bên phát biết để ngưng phát và chỉ phát lại khi bên thu đã sẵn sàng nhận.  Có 2 phương pháp điều khiển luồng :  X-ON/X-OFF  Sliding Window 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 29
16. KIỂM SOÁT LUỒNG (FLOW CONTROL)  Sliding Window  Trong kiểu truyền continuous RQ, P truyền liên tiếp các frame không phải chờ nhận ACK giống như trong idle RQ.  Nếu tốc độ xử lý tại S chậm S sẽ truyền chậm (hoặc ngừng) truyền về các ACK frame, danh sách chờ truyền lại tại P tăng liên tuc. Hoặc bên P gởi liên tục các I-frame trong khi bên S chưa kịp xử lý sẽ làm bộ đệm thu quá tải.  Phương pháp cửa sổ trựợt được thực hiện bằng cách quan sát các I frame chờ truyền lại tại P (ví dụ K frame ). Giới hạn này được xem là cửa sổ truyền (send window). Nếu đến giới hạn này P sẽ ngưng truyền đợi đến khi nhận được tín hiệu ACK từ bên thu. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 31
17. KIỂM SOÁT LUỒNG (FLOW CONTROL) 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 33
18. KIỂM SOÁT LUỒNG (FLOW CONTROL)  Nguyên tắc đánh số :  Để nhận dạng các frame với nhau mỗi frame được gán một số thứ tự (Sequence number), theo nguyên tắc thì có thể gán đến vô cùng.  Tuy nhiên để hạn chế, kết hợp với cửa sổ trượt, số tuần tự được giới hạn theo nguyên tắc đánh xoay vòng.  Số lượng các số nhận dạng được hạn chế và quyết định bởi kích thước cửa sổ và nghi thức. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 35
19. KIỂM SOÁT LUỒNG (FLOW CONTROL) Ví dụ: K=3 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 37
20. Continuous RQ  Trường hợp đường truyền lỗi  Selective Repeat . K ≥ 1 + 2a : U 1 Pf K K(1 P ) . K < 1+2a : U f Nr (1 2a) 1 2a  Go Back N 1 Pf . K ≥ 1 + 2a : U 1 Pf (K 1) K(1 P . K < 1+2a : U f ) (1 2a)(1 Pf (K 1)) 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 39
21. NGHI THỨC LỚP LIÊN KẾT DỮ LIỆU (DATA LINK PROTOCOL)  Chức năng:  Lớp điều khiển liên kết dữ liệu (data link control layer) liên quan đến việc truyền dữ liệu qua một tuyến dữ liệu nối tiếp  Gồm các nghi thức truyền trong cấu hình điểm – điểm, hoặc đa điểm với các thành phần quan trọng như định dạng khung, kiểm soát lỗi, kiểm soát luồng và quản lý kết nối.  Tùy thuộc vào ứng dụng mà cung cấp 2 loại hình dịch vụ chính connectionless (kết nối không định hướng ) và connection-oriented (kết nối có định hướng) . 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 41
22. NGHI THỨC LỚP LIÊN KẾT DỮ LIỆU (DATA LINK PROTOCOL) DTE DTE DTE: Data Terminal Equipment DLP: Data Link Protocol DCE: Data Circuit Terminating Equipment DLP  : Communication Subsystem DTE DCE DCE DTE PSTN Mode Mode m m DLP 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 43
23. NGHI THỨC LỚP LIÊN KẾT DỮ LIỆU (DATA LINK PROTOCOL) 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 45
24. BSC  Nghi thức điều khiển lỗi là Idle RQ  Thuộc nghi thức đồng bộ, định hướng kết nối (connection Oriented).  Dữ liệu được truyền theo kiểu bán song công (Half-Duplex )  Ứng dụng trong cấu hình điểm–điểm hoặc đa điểm.  Trong cấu hình đa điểm, có một Master điều khiển việc truyền và nhận dữ liệu từ nhiều trạm Slave. 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 47
25. BSC DTE Twisted pair LD/R Line termination LD/R LD/R LD/R Master (Supervisor) DTE DTE DTE Slave Slave Slave LD/R: Line Driver/Receiver 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 49
26. BSC Cấu trúc một khung dữ liệu SYN SYN STX Data (128bytes) ETX BCC đơn giản Cấu trúc một khung dữ liệu SYN SYN SOH Header Data (128bytes) ETX BCC đơn giản với Header Cấu trúc một SYN SYN SOH Header STX Data IBT BCC STX Data ETX ETXBCC khung đa khối Data block Khung đầu Cấu trúc một SYN SYN SOH Header STX Data ETB BCC khung đa tiên khung Khung cuối SYN SYN SOH Header STX Data ETX BCC cùng SOH – Start of Header STX – Start of Text ETX – End of Text BCC – Block (sum) Check Character ETB – End of Tranmission Block 51
27. BSC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 53
28. Select - NAK : Y không sẵn sàng nhận. - ACK : Y sẵn sàng nhận. - ACK(0) : Xác nhận khung dữ liệu chẵn nhận tốt. - ACK(1) : Xác nhận khung dữ liệu lẻ nhận tốt. - NAK(0) : Xác nhận khung dữ liệu chẵn bị lỗi - NAK(1) : Xác nhận khung dữ liệu lẻ bị lỗi. - EOT : Kết thúc truyền dữ liệu 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 55
29. Select / Poll 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 57
30. Command HDLC Primary Secondary Response Command Primary Response Response Secondary Secondary Command Response Primary Secondary Command Response Command / Response Primary Secondary / Secondary Command / Response / Primary 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 59
31. HDLC  Các chế độ truyền HDLC  Chế độ đáp ứng bất đồng bộ (ARM – Asynchronuos Response Mode)  Có cấu hình không cân bằng  Trạm thứ cấp có thể khởi tạo quá trình truyền mà không cần sự cho phép của trạm sơ cấp  Trạm sơ cấp chịu trách nhiệm có đường truyền  Ít được sử dụng 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 61
32. HDLC  Cấu trúc khung  Truyền đồng bộ  Tất cả truyền dẫn dạng khung  Dạng khung đơn cho trao đổi dữ liệu và điều khiển 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 63
33. HDLC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 65
34. HDLC  Trường điều khiển  Có cấu trúc khác nhau ứng với những loại khung khác nhau, có 3 loại khung trong HDLC  Thông tin (I-frame) : Mang dữ liệu cần gởi  Giám sát (S-frame) : điều khiển lỗi và luồng, chứa số thứ tự khung gởi và nhận  Không đánh số (U-frame) :Thiết lập và kết thúc kết nối.  Độ dài có thể 1 hay 2 byte 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 67
35. HDLC  Trường điều khiển  1 hay 2 bit đầu tiên của trường điều khiển chỉ ra loại khung  N(S) : Số thứ tự frame gởi  N(R) : Số thứ tự frame nhận  P/F : Có 2 chức năng Poll hoặc Final phụ thuộc hoàn cảnh sử dụng  Khung lệnh . Bit P . 1 để yêu cầu đáp ứng từ đối phương  Khung đáp ứng . Bit F . 1 chỉ rằng đây là trả lời cho lệnh 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 69
36. HDLC  Trường điều khiển: M gồm 5 bit xác định các loại U-frame Ñaùp M Leänh öùng 00 001 SNRM 11 011 SNRME 11 000 SARM DM 11 010 SARME Set Initilization 11 100 SABM Mode (SIM) 11 110 SABME Unnumbered Poll Unnumbered 00 000 UI UI (UP) Information (UI) 00 110 UA Request Exchange ID (XID) 00 101 DISC RD Disconnect (RD) 10 000 SIM RIM 00 100 UP Request Information Mode 11 001 RSET (RIM) 11 101 XID XID 10 001 FRMR
37. HDLC  Trường kiểm tra  Phát hiện sai  16 bit CRC  Tuỳ chọn 32 bit CRC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 73
38. HDLC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 75
39. HDLC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 77
40. HDLC 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 79
41. HDLC  Quá trình đóng khung trong HDLC Beân phaùt Beân thu PACKET Lôùp maïng 3 PACKET Taïo C vaø C PACKET C PACKET giaûi C Taïo A vaø A C PACKET A C PACKET giaûi A Taïo FCS vaø A C PACKET FCS A C PACKET FCS giaûi FCS Nhoài bit vaø A' C' PACKET' FCS' A' C' PACKET' FCS' taùch bit F A' C' PACKET' FCS' F Gaén côø F A' C' PACKET' FCS' F Lôùp vaät lyù 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 81
42. Bài tập Các Nghi Thức Lớp Liên Kết Dư Liệu 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 83
43. Bài 2  DTE A truyền cho DTE B 4 khung dư liệu (đánh số 0-3) theo nghi thức Idle- RQ loại không tường minh, thoả mãn các giả sử sau:  khung dữ liệu thứ 1 I(0) bị mất gói một lần,  khung dữ liệu thứ 3 I(2) truyền ngay lần đầu tiên bị lỗi mất gói và khung xác nhận cho lần truyền lại bị lỗi.  Vẽ tiến trình trao đổi khung (có ghi chú thông tin cần thiết) 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 85
44. Bài 4  DTE A truyền DTE B 6 khung dư liệu dùng nghi thức điều khiển lỗi Selective Repeat dạng tường minh, kích thước cửa sổ k = 3. Vẽ tiến trình trao đổi khung với các giả sử sau:  Khung dư liệu thứ 2 bị lỗi 1 lần  Khung trả lời của khung thứ 3 bị lỗi 1 lần.  Khung thứ 5 và khung trả lời của khung 5 bị lỗi 1 lần 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 87
45. Bài 6 Một chuỗi các khung dữ liệu có chiều dài L = 1000 bits được phát trên đường truyền có chiều dài S = 4000Km, tốc độ bit là R = 2Mbps, tỉ lệ lỗi bit là BER = 10-4. Tính hiệu suất liên kết khi sử dụng các giao thức sau (bỏ qua thời gian của gói ACK/NAK và thời gian xử lý, tốc độ truyền sóng là C = 3 x 108 m/s):  Stop & Wait  Selective Repeat với kích thước cửa sổ là N=7  Go-back-N với kích thước cửa sổ là N=12  Go-back-N với kích thước cửa sổ là N=127 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 89
46. Bài 9  Xác định frame HDLC để phát đi từ sơ cấp với giả sử sau:  Data : phát chữ “vo” theo mã ASCII 7 bits, kiểm tra chẵn  Số thứ tự của frame phát là 7, sử dụng Stop and Wait ARQ.  Dữ liệu được gửi đến mọi terminal trong mạng.  Bỏ qua FCS 8/14/2019 Khoa Điện – Điện tử - ĐHBK TP.HCM 91