Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Mạng máy tínhĐọc trong 10 phút

Truyền dữ liệu tin cậy: từ rdt1.0 đến rdt3.0

Mạng bên dưới có thể đảo bit và làm mất gói tin. Truyền dữ liệu tin cậy là công thức để che giấu điều đó, và nó được xây từ chỉ bốn công cụ, mỗi công cụ được thêm vào để sửa một vấn đề cụ thể.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Mạng máy tính

Chương 3 · Các nguyên lý của truyền dữ liệu tin cậy
Biên soạn từ

Quá trình phát triển từng bước chuẩn của truyền dữ liệu tin cậy được dùng trong các môn mạng máy tính theo hướng từ trên xuống (Kurose và Ross, mục 3.4). Các con số về mức sử dụng đã được tính bằng mã trước khi xuất bản.

Cách sử dụng

Hãy đọc mỗi phiên bản như lời đáp cho một câu hỏi: bây giờ điều gì có thể sai, và công cụ nào sửa nó? Nếu bạn nói được vấn đề và cách sửa cho từng bước, bạn đã hiểu chủ đề này. Các sơ đồ máy trạng thái hữu hạn trong bài giảng của bạn chính là những ý tưởng này được vẽ thành các hộp và mũi tên.

Ghi chú về nguồn

Một số bộ bài giảng chỉ đề cập phần mở đầu của chủ đề này: vì sao độ tin cậy khó, và bốn lời gọi giao diện. Số khác đi tiếp đến toàn bộ chuỗi rdt2.0 đến rdt3.0 và các giao thức pipelining. Bài hướng dẫn này bao quát các nguyên lý đến hết rdt3.0 và lập luận về mức sử dụng của stop-and-wait, và nêu tên pipelining mà không đi vào chi tiết. Nếu môn học của bạn bỏ qua một phần, nhiều khả năng bài thi của bạn cũng vậy, nhưng chính những ý tưởng ở đây làm cho TCP trở nên dễ hiểu.

Hình dung: đọc số điện thoại qua đường dây tệ#

Bạn đang đọc một số điện thoại cho bạn mình qua đường dây rè. Làm sao bạn chắc chắn họ nhận đúng?

  • Họ đọc lại cho bạn nghe, hoặc nói “nhận rồi”. Nếu họ nói “xin lỗi, bạn nói gì cơ?”, bạn nói lại.
  • Nếu tiếng “nhận rồi” của họ bị nhiễu, bạn không chắc, nên bạn đọc lại số đó. Bây giờ họ cần biết đó là cùng số đó nói lại hay là một số mới.
  • Nếu bạn không nghe thấy gì cả, bạn chờ một lát, rồi đọc lại.

Đó là toàn bộ chủ đề. Phần còn lại là đặt cho mỗi thói quen ấy một cái tên đúng nghĩa.

Từ vựng, trước khi dùng đến#

Thuật ngữÝ nghĩa
Kênh tin cậyMột kênh mà không bit nào bị đảo, không gì bị mất, và mọi thứ đến theo đúng thứ tự.
Kênh không tin cậyThứ mà tầng mạng thực sự cung cấp: các bit có thể bị hỏng và các gói tin có thể bị mất.
ACKXác nhận (acknowledgment): bên nhận nói với bên gửi “tôi đã nhận đúng gói tin đó”.
NAKXác nhận phủ định (negative acknowledgment): “gói tin đó đến bị hỏng, hãy gửi lại”.
Truyền lạiGửi một gói tin lần nữa.
Số thứ tựMột con số trên mỗi gói tin để bên nhận phân biệt gói tin mới với gói tin lặp lại.
Bản trùng lặp (duplicate)Một bản sao thứ hai của gói tin mà bên nhận đã có.
Bộ đếm giờ (timeout)Một bộ đếm ngược ở bên gửi. Nếu không có ACK nào đến trước khi nó chạy hết, bên gửi truyền lại.
Stop-and-waitGửi một gói tin, rồi chờ ACK của nó trước khi gửi gói tiếp theo.
ARQAutomatic Repeat reQuest: họ các giao thức sửa lỗi bằng cách truyền lại.

Bốn lời gọi: rdt nằm ở đâu#

Một giao thức truyền dữ liệu tin cậy, rdt, nằm giữa ứng dụng ở trên và kênh không tin cậy ở dưới. Nó có bốn lời gọi được đặt tên, và bài thi có hỏi về chúng:

Lời gọiỞ đâuÝ nghĩa
rdt_send()Bên gửi, được gọi từ trên xuốngỨng dụng giao dữ liệu cho rdt để được chuyển đi.
udt_send()Bên gửi, được rdt gọirdt đẩy một gói tin vào kênh không tin cậy (unreliable).
rdt_rcv()Bên nhận, được gọi từ dưới lênMột gói tin đã đến từ kênh.
deliver_data()Bên nhận, được rdt gọirdt chuyển dữ liệu đúng lên ứng dụng.

Mục tiêu: bất cứ thứ gì đi vào rdt_send() ở một đầu phải đi ra từ deliver_data() ở đầu kia, đúng, đầy đủ và theo thứ tự, dù udt_send() không tin cậy. Việc đó khó đến đâu hoàn toàn phụ thuộc vào kênh có thể làm sai điều gì.

Câu ghi nhớ

rdt là tin cậy, udt là không tin cậy. Ứng dụng chỉ thấy các lời gọi rdt.

Xây dựng dần, từng vấn đề một#

rdt1.0: một kênh hoàn hảo

Nếu kênh không bao giờ làm hỏng hay làm mất thứ gì, bên gửi cứ gửi và bên nhận cứ chuyển lên. Không cần gì thêm. Phiên bản này chỉ tồn tại làm điểm xuất phát.

rdt2.0: kênh có thể đảo bit

Vấn đề: một số bit có thể đến bị đảo. Cách sửa: ba công cụ.

  1. Phát hiện lỗi: một checksum, để bên nhận biết một gói tin bị hỏng.
  2. Phản hồi từ bên nhận: ACK cho gói tin tốt, NAK cho gói tin bị hỏng.
  3. Truyền lại: khi nhận NAK, bên gửi gửi lại gói tin.

Bên gửi chờ ACK hoặc NAK trước khi gửi bất cứ thứ gì mới, nên rdt2.0 là một giao thức stop-and-wait.

rdt2.1: bản thân ACK hoặc NAK có thể bị hỏng

Vấn đề: rdt2.0 có một lỗ hổng chí mạng. Nếu ACK hoặc NAK bị hỏng, bên gửi không biết đó là cái nào. Gửi lại là lựa chọn an toàn, nhưng khi đó bên nhận có thể nhận cùng một gói tin hai lần và chuyển lên hai lần. Cách sửa: một số thứ tự trên mọi gói tin. Với stop-and-wait, một bit là đủ: các gói tin luân phiên 0, 1, 0, 1. Một bên nhận đang chờ 1 mà nhận được 0 biết đó là bản trùng lặp, bỏ nó đi, và ACK lần nữa.

rdt2.2: bỏ NAK

Việc tương tự có thể được thực hiện chỉ bằng ACK. Thay vì NAK, bên nhận gửi lại ACK cho gói tin tốt cuối cùng, kèm số thứ tự của gói tin đó. Một bên gửi nhận được một ACK trùng lặp cho gói tin trước đó biết rằng gói tin hiện tại đã không đến được. Hãy nhớ mẹo này: TCP dùng nó.

rdt3.0: kênh cũng có thể làm mất gói tin

Vấn đề: bây giờ các gói tin, hoặc các ACK, có thể biến mất hoàn toàn. Chờ một phản hồi không bao giờ đến sẽ chờ mãi mãi. Cách sửa: một bộ đếm giờ đếm ngược. Sau khi gửi, bên gửi khởi động bộ đếm giờ. Nếu ACK chưa đến khi bộ đếm giờ chạy hết, nó truyền lại.

Nếu gói tin chỉ bị trễ, không bị mất thì sao? Khi đó việc truyền lại tạo ra một bản trùng lặp, và các số thứ tự từ rdt2.1 đã xử lý được điều đó. Vì số thứ tự luân phiên giữa 0 và 1, rdt3.0 còn được gọi là giao thức bit luân phiên (alternating-bit protocol).

Phiên bảnVấn đề mớiCông cụ mới
rdt1.0Không có gì saiKhông cần gì
rdt2.0Các bit bị đảoChecksum, ACK/NAK, truyền lại
rdt2.1Bản thân ACK/NAK bị đảoSố thứ tự (0 và 1) để phát hiện bản trùng lặp
rdt2.2Giống 2.1, không có NAKACK trùng lặp cho gói tin tốt cuối cùng
rdt3.0Gói tin bị mấtBộ đếm giờ đếm ngược, rồi truyền lại
Đừng nhầm lẫn các khái niệm này

Checksum phát hiện hư hỏng. Bộ đếm giờ phát hiện mất mát. Một gói tin bị mất không có checksum nào để kiểm tra sai, vì không có gì đến cả. Đó là lý do cần bộ đếm giờ như một công cụ riêng.

Ví dụ có lời giải: vì sao stop-and-wait lãng phí đường truyền#

rdt3.0 hoạt động được, nhưng chậm. Bên gửi đặt một gói tin lên đường truyền rồi ngồi nhàn rỗi cả một vòng khứ hồi, chờ ACK. Phần thời gian bên gửi thực sự bận gửi là mức sử dụng (utilization) của nó:

Usender = (L / R) / (RTT + L / R)

Câu hỏi

Một đường truyền 1 Gbps nối hai máy với thời gian khứ hồi là 20 ms. Các gói tin dài 12.000 bit (1.500 byte). Mức sử dụng của bên gửi dưới stop-and-wait là bao nhiêu, và nó cho thông lượng bao nhiêu?

Bước 1: Thời gian để đặt một gói tin lên đường truyền.

L / R = 12.000 / 1.000.000.000 = 0,000012 s = 0,012 ms

Bước 2: Mức sử dụng.

U = 0,012 / (20 + 0,012) ≈ 0,0006

Bên gửi chỉ bận khoảng 0,06% thời gian.

Bước 3: Thông lượng. Một gói tin được chuyển đến nơi mỗi RTT + L/R.

12.000 bits / 0,020012 s ≈ 600 kbps

Một đường truyền 1 Gbps, chỉ chuyển được khoảng 600 kbps. Chính giao thức, chứ không phải đường truyền, là nút thắt cổ chai.

Cách sửa là pipelining: để bên gửi có nhiều gói tin “đang bay” (in flight) trước khi cần một ACK. Với 3 gói tin đang bay, mức sử dụng tăng gấp ba. Pipelining cần một dải số thứ tự lớn hơn, và bộ đệm ở bên gửi (và, với Selective Repeat, ở cả bên nhận). Hai thiết kế pipelining kinh điển được gọi là Go-Back-N và Selective Repeat, và TCP mượn ý tưởng từ cả hai.

Một câu để mang vào phòng thi

Checksum bắt các bit bị hỏng, ACK cho bên gửi biết cái gì đã đến, số thứ tự cho phép bên nhận phát hiện bản trùng lặp, và bộ đếm giờ bắt trường hợp mất gói; stop-and-wait đúng nhưng để đường truyền nhàn rỗi gần như cả một vòng khứ hồi.

Luyện tập#

Với mỗi phiên bản, hãy nêu vấn đề trước khi nêu cách sửa. Thứ tự đó là điều bài thi chấm điểm.

  1. Hãy nêu tên bốn lời gọi giao diện rdt và nói mỗi lời gọi ở bên nào.
  2. rdt2.0 thêm ba công cụ nào, và chúng giải quyết vấn đề gì?
  3. Lỗ hổng chí mạng của rdt2.0 là gì, và rdt2.1 sửa nó thế nào?
  4. Vì sao một bit là đủ cho số thứ tự trong một giao thức stop-and-wait?
  5. rdt2.2 báo hiệu một gói tin bị hỏng như thế nào mà không dùng NAK?
  6. rdt3.0 xử lý vấn đề mới nào, và bằng công cụ gì?
  7. Trong rdt3.0, bộ đếm giờ hết hạn, nhưng gói tin gốc chỉ bị trễ. Điều gì xảy ra ở bên nhận, và vì sao điều đó an toàn?
  8. Một đường truyền 100 Mbps, gói tin 10.000 bit, RTT 10 ms. Mức sử dụng của stop-and-wait là bao nhiêu?
  9. Pipelining là gì, và vì sao nó có ích?

Lời giải#

Cách học tốt nhất

Hãy tìm dòng đầu tiên mà cách làm của bạn khác với lời giải, rồi làm lại bài từ dòng đó. Đừng chỉ đọc đáp án rồi gật đầu.

  1. rdt_send() và udt_send() ở bên gửi; rdt_rcv() và deliver_data() ở bên nhận. rdt_send được ứng dụng ở trên gọi; udt_send đẩy vào kênh không tin cậy; rdt_rcv được gọi khi một gói tin đến; deliver_data chuyển dữ liệu lên.
  2. Checksum, phản hồi ACK/NAK, truyền lại; lỗi bit. Checksum phát hiện hư hỏng, bên nhận báo ACK hoặc NAK, và bên gửi truyền lại khi nhận NAK.
  3. ACK/NAK bị hỏng; số thứ tự. Nếu ACK hoặc NAK bị hỏng, bên gửi không biết đã xảy ra chuyện gì. Gửi lại có thể tạo ra một bản trùng lặp. rdt2.1 đánh số mỗi gói tin để bên nhận có thể phát hiện và loại bỏ bản trùng lặp.
  4. Chỉ có hai gói tin cần phân biệt. Trong stop-and-wait, bên nhận chỉ cần biết gói tin đến là gói tin nó vừa nhận lại lần nữa hay là gói tin mới kế tiếp. Hai giá trị, 0 và 1, phân biệt hai trường hợp đó.
  5. Một ACK trùng lặp. Bên nhận gửi lại ACK cho gói tin được nhận đúng gần nhất, kèm số thứ tự của nó. Bên gửi đọc một ACK trùng lặp cho gói tin trước đó là “gói tin hiện tại đã thất bại” và truyền lại.
  6. Mất gói tin; một bộ đếm giờ đếm ngược. Nếu không có ACK nào đến trước khi bộ đếm giờ hết hạn, bên gửi truyền lại.
  7. Bên nhận nhận một bản trùng lặp và loại bỏ nó. Số thứ tự của nó cho thấy đó là bản lặp lại, nên bên nhận bỏ nó đi và gửi lại ACK. Không có gì được chuyển lên hai lần.
  8. Khoảng 0,0099, xấp xỉ 1%. L/R = 10.000 / 100.000.000 = 0,0001 s = 0,1 ms. U = 0,1 / (10 + 0,1) ≈ 0,0099.
  9. Nhiều gói tin đang bay. Bên gửi có thể gửi nhiều gói tin trước khi nhận một ACK, thay vì một. Đường truyền được giữ bận trong suốt vòng khứ hồi, nên mức sử dụng tăng lên xấp xỉ bằng số gói tin đang bay.

Danh sách kiểm tra trước khi thi#

  • ☐  Tôi có thể nêu tên bốn lời gọi rdt và nói mỗi lời gọi ở bên nào và theo hướng nào.
  • ☐  Tôi có thể liệt kê vấn đề và cách sửa của rdt1.0, 2.0, 2.1, 2.2 và 3.0.
  • ☐  Tôi có thể giải thích vì sao cần số thứ tự và vì sao 0 và 1 là đủ cho stop-and-wait.
  • ☐  Tôi có thể giải thích cách một ACK trùng lặp có thể thay thế một NAK.
  • ☐  Tôi có thể giải thích vì sao cần bộ đếm giờ và vì sao một timeout sớm là vô hại.
  • ☐  Tôi có thể tính mức sử dụng và thông lượng của stop-and-wait.
  • ☐  Tôi có thể giải thích trong một câu vì sao pipelining có ích.
Một quy tắc cuối cùng

Hãy nêu vấn đề trước, rồi mới đến công cụ. Chỉ nói “số thứ tự” là mới được nửa câu trả lời; “số thứ tự, vì một ACK bị nhiễu khiến bên gửi gửi lại và bên nhận phải nhận ra bản trùng lặp” mới là câu trả lời đầy đủ.

Câu hỏi thường gặp#

rdt2.0, rdt2.1, rdt2.2 và rdt3.0 khác nhau thế nào?

rdt2.0 xử lý lỗi bit bằng checksum, ACK/NAK và truyền lại. rdt2.1 thêm số thứ tự vì bản thân ACK/NAK cũng có thể bị hỏng. rdt2.2 làm điều tương tự mà không cần NAK, bằng cách dùng ACK trùng lặp. rdt3.0 thêm một bộ đếm giờ đếm ngược vì gói tin cũng có thể bị mất.

Vì sao truyền dữ liệu tin cậy cần số thứ tự?

Vì bên gửi có thể truyền lại một gói tin mà bên nhận đã nhận đúng, ví dụ khi một ACK bị hỏng hoặc bị trễ. Số thứ tự cho phép bên nhận nhận ra bản trùng lặp và loại bỏ nó thay vì chuyển lên hai lần.

Vì sao rdt3.0 được gọi là giao thức bit luân phiên (alternating-bit)?

Vì các gói tin của nó mang một số thứ tự dài một bit luân phiên giữa 0 và 1, và đó là tất cả những gì một giao thức stop-and-wait cần để phân biệt một gói tin mới với một gói tin được truyền lại.

Làm thế nào để tính mức sử dụng của stop-and-wait?

Mức sử dụng = (L/R) / (RTT + L/R), trong đó L/R là thời gian truyền một gói tin. Với đường truyền nhanh và RTT dài, kết quả rất nhỏ, vì bên gửi nhàn rỗi gần như suốt cả vòng khứ hồi.

Bốn lời gọi giao diện rdt là gì?

rdt_send() được ứng dụng gọi ở bên gửi, udt_send() gửi một gói tin vào kênh không tin cậy, rdt_rcv() được gọi khi một gói tin đến bên nhận, và deliver_data() chuyển dữ liệu lên ứng dụng nhận.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn mong chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có một bài hướng dẫn mới.

Tự kiểm tra về chủ đề này

Ứng dụng luyện tập mạng máy tính miễn phí có 19 câu hỏi về chủ đề này và 500 câu cho toàn bộ môn học, mỗi đáp án đều có giải thích. Dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập chủ đề này →