Tầng liên kết dữ liệu và giao thức

Chia sẻ: Nguyễn Peter | Ngày: | Loại File: PPT | Số trang:44

0
127
lượt xem
45
download

Tầng liên kết dữ liệu và giao thức

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tầng liên kết dữ liệu • Chức năng của tầng liêt kết dữ liệu (DLL) • Phương pháp framing • Điều khiển luồng • Kiểm soát

Chủ đề:
Lưu

Nội dung Text: Tầng liên kết dữ liệu và giao thức

  1. 8/2006 Chủ đề 5. Tầng liên kết dữ liệu và giao thức Chủ đề 5 Tầng liên kết dữ liệu • Chức năng của tầng liêt kết dữ liệu (DLL) • Phương pháp framing • Điều khiển luồng • Kiểm soát lỗi • Các giao thức của tầng liên kết dữ liêu • Phương pháp kết nối mạng ở tầng liên kết dữ liếu Hanoi University of Technology Faculty of Electronics and Telecommunications
  2. 8/2006 Chủ đề 5 • Chức năng của tầng liên kết dữ liệu  Khả năng truyền khung tin cậy trên đường liên kết vật lý không tin cậy Source node Destination node Application Application Layer Layer Presentation Presentation Layer Layer Session Session Layer Layer Transport Intermediate node Transport Layer Layer Packets Network Network Network Layer Layer Layer Data Link Frames Data Link Data Link Layer Layer Layer Physical Bits Physical Physical Layer Layer Layer Hanoi University of Technology Faculty of Electronics and Telecommunications
  3. 8/2006 Chủ đề 5 • Phương pháp Framing  DLL tổ chức bit stream thành các frame  Bắt đầu và kết thúc của frame được xác định: Character count, control character, flag, …  Character count o Số ký tự được chỉ ra trong vị trí xác định của header o Bên nhận đếm số ký tự để xác định nơi kết thúc frame o Ví dụ: DDCMP 8 8 8 14 42 16 Class CRC SYN SYN Count Header Body Hanoi University of Technology Faculty of Electronics and Telecommunications
  4. 8/2006 Chủ đề 5  Control character o Mỗi frame bắt đầu và kết thúc với chuỗi ký tự đặc biệt  Ví dụ: bắt đầu với DLE STX (data link escape start of text) và kết thúc với DLE ETX (end of text) o Phần dữ liệu phải là số nguyên lần các ký tự o Character stuffing: chèn DLE trước mỗi ký tự DLE trong dữ liệu, ngăn chặn khả năng xuất hiện các ký tự bắt đầu và kết thúc xuất hiện bên trong frame  Ví dụ: BISYNC Data to be sent A DLE B ETX DLE STX E After stuffing and framing DLE STX A DLE DLE B ETX DLE DLE STX E DLE ETX  STX: 0x02, ETX: 0x03  DLE: 0x01 (non-printable) Hanoi University of Technology Faculty of Electronics and Telecommunications
  5. 8/2006 Chủ đề 5  Flagging o Mỗi frame bắt đầu và kết thúc bằng chuỗi ký tự đặc biệt – flag o Flag byte: 01111110 (0x7E) o Phần dữ liệu của frame có thể chứa số bit bất kỳ o Bit stuffing: chèn bit 0 vào sau mỗi chuỗi 5 bit 1 liên tiếp o Ví dụ: SDLC, HDLC, LAPB 01111110111101011111011110111110001111110 Flag Frame Flag Hanoi University of Technology Faculty of Electronics and Telecommunications
  6. 8/2006 Chủ đề 5 • Điều khiển luồng (flow control)  Khái niệm điều khiển luồng o Kích thước bộ đệm đê lưu giữ các frame nhận được bi giới hạn o Tràn bộ đệm có thể xảy ra nếu tốc độ xử lý tại phía thu chậm hơn tốc độ truyền frame o Điều khiển luồng ngăn chặn tràn bộ đệm bằng cách điều khiển tốc độ truyền dẫn từ phía phát (Tx) đến phía thu (Rx) o Các phương pháp phổ biến:  X-ON/X-OFF  Stop and wait  Sliding window Hanoi University of Technology Faculty of Electronics and Telecommunications
  7. 8/2006 Chủ đề 5  X-ON/X-OFF o Rx truyền X-OFF (DC3) nếu bộ đệm đầy o Tx dừng truyền khi nhận được X-OFF o Rx truyền X-ON (DC1) khi bộ đệm được giải phóng o Tx bắt đầu truyền lại khi nhận được X-ON o Có thể sử dụng các frame RR (Receive Ready) và RNR (Receive not Ready) o Nếu số bit trong bộ đệm vượt quá ngưỡng 2tprop·R, X-OFF được gửi tới Tx o Phương pháp: Stop-and-wait, sliding window Threshold Transmitter Receiver X-OFF X-ON Hanoi University of Technology Faculty of Electronics and Telecommunications
  8. 8/2006 Chủ đề 5 o Stop-and-wait  Tx ngừng truyền frame tiếp theo cho đến khi nhận được ACK từ Rx  Rx truyền frame ACK khi đã sẵn sàng nhận frame tiếp theo  Đơn giản, nhưng không hiệu quả khi trễ đáp ứng đường truyền lớn  Utilization: Tx Rx t frame 1 t d/ v U= = , a = prop = 2t prop + t frame 2a + 1 t frame L / R Data tframe T tprop  Satellite link: tprop = 270 ms, L = 500 byte R = 56 kbps  tframe = 4/56 = 71 ms, ACK  a = tprop / tframe = 270/71 = 3.8, Data  U = 0.12 = 12% của 56 kbps  Short link: tprop = 5 µs, L = 500 byte R = 10 Mbps  tframe = 4k/10 M = 400 µs, ACK  a = tprop / tframe = 5/400 =0.012  U = 0,98 = 98% của 10 Mbps Hanoi University of Technology Faculty of Electronics and Telecommunications
  9. 8/2006 Chủ đề 5 o Sliding window  Window WS bằng kích thước bộ đệm của bên nhận có thể sử dụng để nhận các frame liên tiếp từ Tx không cần ACK  Có thể tránh hiện tượng tràn bộ đệm của Rx  Phải chọn WS lớn hơn a (delay of bandwidth) System A System B F0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 F1 F2 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 ACK3 F3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 F4 F5 F6 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 ACK7 Hanoi University of Technology Faculty of Electronics and Telecommunications
  10. 8/2006 Chủ đề 5  Utilization: 1 N ≥ 1+ 2a t prop d/ v Nt frame  , a= = U= = N 2t prop + t frame  N < 1+ 2a t frame L/R 1+ 2a Tx Rx Data tframe N frames tprop T ACK Hanoi University of Technology Faculty of Electronics and Telecommunications
  11. 8/2006 Chủ đề 5 • Kiểm soát lỗi (error control)  Khái niệm o Lỗi do môi trường truyền dẫn o Quá trình kiểm soát lỗi có 2 chức năng: phát hiện và sửa lỗi o 2 loại lỗi phổ biến: mất frame và lỗi frame  Các phương pháp kiểm soát lỗi o Forward error control: sửa lỗi tại phía Rx (Forward Error Correction) o Backward error control: truyền lại frame (Automatic Repeat Request)  cần backward channel Hanoi University of Technology Faculty of Electronics and Telecommunications
  12. 8/2006 Chủ đề 5  Automatic Repeat reQuest (ARQ) o Cơ chế  Phát hiện lỗi  Positive acknowledgement (ACK): frame nhận OK tại Rx  Truyền lại sau timeout  Negative acknowledgement (NACK): truyền lại frame o Các phương pháp ARQ  Stop and Wait ARQ  Continuous ARQ  Go-back-N ARQ  Selective-reject (or repeat) ARQ Hanoi University of Technology Faculty of Electronics and Telecommunications
  13. 8/2006 Chủ đề 5 o Stop and wait ARQ  Tx gửi 1 frame và đợi ACK từ Rx trước khi truyền next frame  Tx phải giữ bản copy của frame đã gửi đến khi nhận đươc ACK  Sử dụng timeout cho các frame hoặc ACK bị mất  Đánh số các frame gửi và nhận để nhận biết khi lặp frame  Ví dụ: sử dụng 1 bit để đánh số frame Frame lost ACK 0 lost A retransmits A retransmits Timeout Timeout A Fra 0 1 0 0 Fra Fra Fra Fra Fra 1 Fra * ACK ACK ACK ACK ACK m m m m me me m * e0 e0 e1 e1 e0 1 0 B B discards duplicated frame Hanoi University of Technology Faculty of Electronics and Telecommunications
  14. 8/2006 Chủ đề 5 o Go-back-N ARQ  Tx có thể truyền liên tiếp các frame  Rx gửi negative acknowledgement (REJ) khi phát hiện lỗi  Tx phải truyền lại tất cả các frame từ frame bi lỗi  Tx phải giữ bản copy của tất cả các frame đã gửi Frame 2, 3, 4 retransmitted Tx Fra Fra Fra Fra Fra Fra Fra Fra Fra m m m m m m m m m e4 e2 e3 e1 e0 e4 e2 e3 e5 3 1 3 2 4 5 K ACK ACK * ACK ACK ACK NAC Rx Discarded by Rx Hanoi University of Technology Faculty of Electronics and Telecommunications
  15. 8/2006 Chủ đề 5 o Selective-repeat ARQ  Tx có thể truyền liên tiếp các frame  Rx gửi negative acknowledge (SREJ) khi phát hiện lỗi  Rx lưu lại tất cả các frame OK sau frame bị lỗi  Tx chỉ gửi lại duy nhất frame bị lỗi  Rx phải sắp xếp lại các frame đã lưu sau khi nhận được frame truyền lại Frame 2 retransmitted Tx Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra m m m m me me me m m m e4 e5 e1 e0 e0 e3 e7 6 2 2 K3 1 5 2 6 7 0 ACK * ACK ACK ACK ACK ACK NAC Rx Error Buffered Frame 2, 3, 4 by Rx released Hanoi University of Technology Faculty of Electronics and Telecommunications
  16. 8/2006 Chủ đề 5 o Performance  Lựa chọn maximum window size, khi dùng n bit để đánh số frame  Go-back-N ARQ: N = 2n – 1  Ví dụ: Go-back-N, n = 2 N = 22 = 4, Go-back- 4 N = 22 - 1 = 3, Go-back- 3 Tx goes back 4 Tx goes back 3 A A Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra Fra m m m m m m m m me m me m me m e0 e1 e1 e1 e0 e2 e1 e3 e0 e3 e0 2 2 2 4 * 3 * * 1 3 2 * * * 1 2 ACK ACK ACK ACK ACK ACK ACK B B Rx does not know Rx reject old frame 0 or new one the old frame 0 Hanoi University of Technology Faculty of Electronics and Telecommunications
  17. 8/2006 Chủ đề 5  Selective-repeat ARQ: N = 2n – 1  Ví dụ: Selective-repeat ARQ, n = 2 N = 22 = 4, Send win = Receive win = 3 N = 22 = 4, Send win = Receive win = 2 Frame 0 resent Frame 0 resent A A Fra Fra Fra Fra Fra Fra Fra m m me me me m m e1 e0 e0 e2 1 0 2 3 * * 1 2 * * 1 2 ACK ACK ACK ACK ACK B B Frame 0 rejected Receiver window [3, 0, 1] Receiver window [2,3] Hanoi University of Technology Faculty of Electronics and Telecommunications
  18. 8/2006 Chủ đề 5  Performance: Stop-and-wait ARQ Tx Rx  P: xác suất lỗi khung tframe tprop  Nf = số lần truyền khung trung bình NACK 1 U= Uerror − free Nr 1 NACK Nr = ∑ i ⋅ Pi−1(1− P) = 1− P 1 1 1− P  U= ⋅ = ACK Nr 1+ 2a 1+ 2a Hanoi University of Technology Faculty of Electronics and Telecommunications
  19. 8/2006 Chủ đề 5  Performance: Go-back-N ARQ  P: xác suất lỗi khung  Nf = số lần truyền khung trung bình Tx Rx Nr ≈ 1⋅ (1− P) + (1+ K) ⋅ P ⋅ (1− P) + (1+ 2K) ⋅ P 2 ⋅ (1− P) +  + 1+ P(K − 1) tf = 0 1− P tp 1 • N ≥ 1+ 2a : K = 1+ 2a 2 NACK • N < 1+ 2a : K = N 3  1− P 1− P 0 = 1+ P(K − 1) 1+ 2aP , N ≥ 1+ 2a  1  U= 2  1− P ⋅ N = N(1− P) , N < 1+ 2a 1+ P(K − 1) 1+ 2a (1+ 2a)(1− P + NP)  3 4 Hanoi University of Technology Faculty of Electronics and Telecommunications
  20. 8/2006 Chủ đề 5  Performance: Selective-repeat ARQ  P: xác suất lỗi khung  Nf = số lần truyền khung trung bình Tx Rx 1 Nr = ∑ i ⋅ Pi−1(1− P) = 1− P tf 0 tp 1 1 - P, N ≥ 1+ 2a  2 U = N(1− P) NACK  1+ 2a , N < 1+ 2a  3 0 4 5 6 Hanoi University of Technology Faculty of Electronics and Telecommunications
Đồng bộ tài khoản