›
›

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

ppt 39 trang phuongnguyen 2830
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_truyen_thong_ky_thuat_so_chuong_4_cac_nghi_thuc_di.ppt

Nội dung text: 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

  1. 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.vn
  2. Nội dung Điều khiển liên kết dữ liệu (Data Link Control) Điều khiển dòng Điều khiển lỗi (Flow Control) (Error Control) CSE 501035 – Data Communication 2
  3. Vần đề khi trao đổi dữ liệu  Đồng bộ khung  Dữ 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ỗi  Xử 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ền  Tích hợp dữ liệu và điều khiển trên cùng đường truyền  Phân biệt dữ liệu và thông tin điều khiển  Quản lý liên kết  Cấp phát, duy trì và giải phóng đường truyền giữa 2 thiết bị CSE 501035 – Data Communication 3
  4. Điều khiển dòng dữ liệu  Bảo đảm cho việc bên phát không gởi dữ liệu quá nhanh  Ngăn ngừa việc tràn bộ đệm  Khái niệm thời gian  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. CSE 501035 – Data Communication 4
  5. Điều khiển dòng dữ liệu Mô hình truyền khung Điều khiển dòng (Flow Control) Idle RQ Sliding windows (Stop and Wait) CSE 501035 – Data Communication 5
  6. Idle 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-duplex  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 đợ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 ACK  Thích hợp khi chỉ có vài frame có kích thước lớn  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  Lỗ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ợp CSE 501035 – Data Communication 6
  7. Idle RQ (Stop–and–Wait) Animation CSE 501035 – Data Communication 7
  8. Idle RQ – Hiệu suất n t 1 U = frame =  Thời gian tổng cộng TD = n(2tprop + tframe) TD 1+ 2a d  Hiệu suất đường truyền t R d a = prop = V = t L L V frame R CSE 501035 – Data Communication 8
  9. 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  Bên phát có thể truyền tối đa W frame mà không cần đợi ACK  Cơ chế đánh số thứ tự cho các frame  ACK 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) CSE 501035 – Data Communication 9
  10. Sliding windows Animation CSE 501035 – Data Communication 10
  11. Sliding windows CSE 501035 – Data Communication 11
  12. Sliding windows CSE 501035 – Data Communication 12
  13. Điều khiển lỗi  Cung 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ền  Bảo đảm dữ liệu nhận được đúng và chính xác  Loại lỗi  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ư, không thể xác định được  Frame 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ỗi  Phát hiện lỗi (CRC, Parity, )  Positive ACK – xác nhận các frame nhận được  Truyền lại sau một thời gian time-out  Negative ACK (NAK) và truyền lại – yêu cầu truyền lại (NAK) cho các frame bị hư CSE 501035 – Data Communication 13
  14. Điều khiển lỗi  ARQ (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ại  Phân loại  Idle 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 RQ  Dù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-N Điều khiển lỗi (Error Control) ARQ ARQ Stop and Wait Sliding windows Go Back N Selective reject CSE 501035 – Data Communication 14
  15. Stop–and–Wait  Cơ chế hoạt động  A gởi một I-Frame (Information Frame) đến B  A đợi trả lời  ACK-Frame – A gới tiếp dữ liệu  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  Lặp lại các bước trên  Ưu/khuyết điểm  Đơn giản  Khô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? CSE 501035 – Data Communication 15
  16. Stop–and–Wait  Cơ chế hoạt động  Trong 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ị sai E3 Primary (P) I(N) I(N+1) E3 I(N) ACK(N) I(N+1) ACK(N+1) E1 I(N) I(N+1) Secondary (S) E2 CSE 501035 – Data Communication 16
  17. Stop–and–Wait  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 báo về thì xem như I-Frame chưa tới và gởi lại frame này. Timer expired Timer started Timer stopped restarted Primary (P) I(N) I(N) I(N) ACK(N) I(N) ACK(N) E1 I(N) I(N) Secondary (S) CSE 501035 – Data Communication 17
  18. Stop–and–Wait  Sửa lỗi E2  Implicit retransmission: sử dụng timer Timer expired Timer started Timer stopped restarted Primary (P) I(N) I(N) E2 I(N) I(N) ACK(N) I(N) I(N) Secondary (S)  Explicit retransmission: NAK-Frame (negative acknowledgement frame) Primary (P) I(N) I(N) E2 I(N) NAK(N) I(N) ACK(N) I(N) I(N) Secondary (S) CSE 501035 – Data Communication 18
  19. Stop–and–Wait  Sửa lỗi E3  Lỗi lặp lại frame (duplicated frame): dùng chỉ số tuần tự frame (sequential number) Timer expired Timer started Timer stopped restarted Primary (P) I(N) I(N) Sequential number E3 I(N) I(N) ACK(N) ACK(N) I(N) I(N) I(N) Secondary (S) I-Frame corrected Frame duplicated CSE 501035 – Data Communication 19
  20. Stop–and–Wait  Hoạt động tốt CSE 501035 – Data Communication 20
  21. Stop–and–Wait  I-Frame không đến CSE 501035 – Data Communication 21
  22. Stop–and–Wait  ACK-Frame hư/không đến CSE 501035 – Data Communication 22
  23. Stop–and–Wait  I-Frame hư CSE 501035 – Data Communication 23
  24. Primary (P) Go–back–N I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) I(N) ACK(N)  Cơ chế hoạt động I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5)  Điều khiển Secondary (S)  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ự ? thứ tự I-Frame truyền được bảo đảm  Truyề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 sai  I-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 i  Frame 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 i  Frame 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-out  ACK hư  B nhận được frame i, gởi ACKi, nhưng ACK này bị mất  A đợi hoài, sẽ gởi lại các frame, kể từ frame i  A gởi frame i, i+1, i+2. B gởi ACKi+2, được hiểu như bao gồm ACKi, ACKi+1  CSE 501035 – Data CommunicationNAK hư 24  A đợi hoài, sẽ gởi lại các frame, kể từ frame i
  25. Go–back–N Retransmitted I(N+2) I(N+3) I(N+4) mode I(N+1) I(N+1) I(N+2) I(N+3) I(N) I(N) I(N) I(N+1) I(N+2) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+2) I(N+3) I(N+4) Primary (P) E1 Timeout retransmitted I(N) ACK(N) Secondary (S) I(N) I(N+1) I(N+3) I(N+4) I(N+2) I(N+3) I(N+4) V(s)=N V(s)=N+1 V(s)=N+2 V(s)=N+2 V(s)=N+2 V(s)=N+2 V(s)=N+3 V(s)=N+4 Frame Frame Frame not Frame not Frame not Frame Frame Frame accepted accepted accepted accepted accepted accepted accepted accepted CSE 501035 – Data Communication 25
  26. 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-frame Primary (P) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) E1 I(N) ACK(N) E1 E3 I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) Secondary (S) E2 CSE 501035 – Data Communication 26
  27. Go–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ại  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ề (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ày CSE 501035 – Data Communication 27
  28. Go–back–N  Sửa lỗi E2  Implicit Retransmission: dùng timer  Khi 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 E1  Explicit 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ày CSE 501035 – Data Communication 28
  29. Go–back–N  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, 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 nhau  Do 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ất  Nế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 ACK CSE 501035 – Data Communication 29
  30. Go–back–N  Khái niệm  Giả sử dòng các I-Frame đi theo một chiều và chiều kia chỉ dùng cho ACK  Cá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 piggyback  ACKN xác nhận cho frame N-1 CSE 501035 – Data Communication 30
  31. Selective Reject  Cơ chế hoạt động  Tương tự như Go-Back-N, ngoại trừ việc chỉ gởi lại các frame bị NAK hoặc time-out  Bê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ống  A gởi 0-6 đến B  B xác nhận tất cả, nhưng tất cả ACK đều bị mất  A đợi hoài, nên gởi lại 0  B đã 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ận  Kích thước cửa sổ tối đa là ½(2n), tức 2n-1 CSE 501035 – Data Communication 31
  32. Selective Reject CSE 501035 – Data Communication 32
  33. Selective Reject  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 báo về thì xem như I-Frame chưa tới và gởi lại Frame này  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ề. 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ày CSE 501035 – Data Communication 33
  34. Selective Reject Retransmitted I(N+2) I(N+3) I(N+4) mode I(N+1) I(N+1) I(N+2) I(N+3) I(N) I(N) I(N) I(N+1) I(N+2) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+2) I(N+5) I(N+6) Primary (P) E1 Timeout retransmitted I(N) ACK(N) V(s)=N+1 Secondary (S) I(N) I(N+1) I(N+3) I(N+4) I(N+2) I(N+5) I(N+6) I(N) I(N+1) I(N+3) I(N+3) I(N+3) I(N+5) I(N+6) I(N+4) I(N+4) I(N+2) CSE 501035 – Data Communication 34
  35. Selective Reject  Sửa lỗi E2  Implicit Retransmission: dùng timer  Khi 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 E1  Explicit 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ày CSE 501035 – Data Communication 35
  36. Selective Reject  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, 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 nhau  Do 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ụng CSE 501035 – Data Communication 36
  37. Continuous ARQ – So sánh 0 1 2 3 4 5 2 3 4 5 6 7 0 ACK1 ACK2 NAK2 ACK3 ACK4 ACK5 ACK6 0 1 E D D D 2 3 4 5 6 Error Discarded frames Go-back-N protocol 0 1 2 3 4 5 2 6 7 0 ACK1 ACK2 NAK2 ACK3 ACK4 ACK5 ACK2 0 1 E 3 4 5 2 6 Error Buffered frames frames 2-5 released Selective repeat CSE 501035 – Data Communication 37
  38. Điều khiển lỗi – Hiệu suất  Stop-and-wait protocol 1− P U = 1+ 2a 1− P  Go-back-N protocol N 2a +1 1+ 2aP U = N(1- P) N 2a +1 (2a +1)(1- P + NP)  Selective reject protocol 1- P N 2a +1 U = N(1− P) N 2a +1 1+ 2a CSE 501035 – Data Communication 38
  39. Đọc thêm  W. Stallings, Data and Computer Communications (7th edition), Prentice Hall 2004, chapter 7 CSE 501035 – Data Communication 39